Search in array of colors


Warning: count(): Parameter must be an array or an object that implements Countable in /home/styllloz/public_html/qa-theme/donut-theme/qa-donut-layer.php on line 274
0 like 0 dislike
55 views
There are an array of colors (rgb). Items — about a million. The array is searched for the closest color to the specified (criterion of proximity is the closeness of the point to point rgb r1g1b1, i.e. the root of sum of squares of differences of each of the three color components). The task such — to carry out the search as quickly as possible. To iterate through all the elements of the array and for each to seek proximity to a specified colour — too expensive (the task is to populate a new array even several millions of elements for everyone to do a full bust — long). How can I implement this search? Maybe what algorithms exist?
by | 55 views

6 Answers

0 like 0 dislike
by
0 like 0 dislike
I used the following algorithm (I was really not a task to completely close the value, but just the color from the close zone, but suddenly I draw for myself):
\r
1. A uniform three-dimensional array (P) in a given space with a certain step, for example 4. That is to say the coordinates in the RGB elements will be 000, 400, 040, 440, etc.
\r
2. Loop over all elements in the source array (A) flowers and filled on the basis of these data our uniform pattern (R). If we have for example the original array (A) is the color of 511, then remember these data for the closest element in the array (P): R[400]=511 otherwise subject to R[400]=0
\r
3. Now we need to search for the closest color (In) just go directly to the nearest grid element of the array (P):
In[301] -> nearest color in the grid 400 -> R[400]=511 -> closest source color 511...
by
0 like 0 dislike
A million elements 16 million elements of possible positions. You can try to create a map of positions, i.e., array[rgb] = 1 | 0.
\r
If each position is described by one byte, that is 16 MB of memory. Not so much for modern cars?
Pretty simple addressing, a simple query so you can use the search breadth. If you search to do duplex, then the speed will be quite acceptable. (first search areas 16х16х16, then search for the points inside suitable regions).
by
0 like 0 dislike
If the distance between colors in the array are the same, it is possible to store colors as 3-dimensional array. And then the search is binary. If there is no sorrow I'll keep thinking...
by
0 like 0 dislike
Google spatial database and spatial index for two dimensional data is full of decisions, you may be able to find something ready and three-dimensional.
by
0 like 0 dislike
Understand that many years have passed, but suddenly someone come in handy later :)
In fact, the situation with flowers - it is simple, because it is a discrete space. Roughly speaking, we have RGB - coordinates of a point in three-dimensional space. The point is the area of a sphere of a certain radius. The points that lie on the surface of the sphere equidistant from the starting point to a distance equal to the radius of the sphere. Task is to limit the search to direct the search, i.e., we take a sphere with a radius of 0 - point different from ours - so they are coming, not - increase the radius to 1, there are points - excellent, found no increase the radius further, etc. is Possible, then you can not use direct search and a bisection in a specified interval - there is the creative moment :) As all of this deal to realize (it would work well for the situation above, when the search on a fixed set it is necessary to perform very many times).
1. Create three array [0..255]. Arrays R, G, B. the array Element is the set of indices of elements in the source array of pixels. Ie let the point with color 100, 25, 250 has an index of outcome in the array 200. Then we should make R[100].add(200); G[25].add(200); B[250].add(200);
2. As we fill the arrays in a sequence, each element of the arrays R,G,B will have an ordered set. If, for some reason, it's not that the second step should be to organize each set.
3. Build three two-dimensional UR array[0..255,0..255]. UG. UB. Where UR[i,j] = the intersection of the sets R[i] and R[j]. The beauty is that many have already ordered and their intersection is being built quite quickly. You can read more here https://habrahabr.ru/post/250191/
Our preparatory work has ended. It will take some time, but further search will be carried out very quickly.

So, actually the search itself is the nearest point to the desired simple. For i=0 to 255. the coordinates of the required point r, g, b. Take a set of values UR[r-i, r+i] is concatenated to the URi, so for each array. Then look at the intersection of the sets URi, UGi, UBi - if empty, i++, otherwise any (or many - depending on tasks) of the found elements of the original. Of course, it is necessary to watch, that would not overstep the bounds of arrays, etc., the main thing - the idea - we are looking for the closest points as the points lying on the surface of a sphere centered at the origin, with the smallest radius. But that would not run every time through the array - we have prepared three arrays with the projected points for each axis.
Would be limited to arrays R, G and B, but then each search would have to find a junction is, perhaps, more profitable for a small number of iterations of the search. For a large more profitable to build many intersections and look for them.
by

Related questions

0 like 0 dislike
2 answers
0 like 0 dislike
4 answers
0 like 0 dislike
2 answers
0 like 0 dislike
2 answers
110,608 questions
257,186 answers
0 comments
27,873 users