Color Array Search

Question

Algorithms

There is an array of colors (rgb). Elements - about a million. The closest color to the given color is searched in the array (the proximity criterion is the proximity of the rgb point to the r1g1b1 point, i.e. the root of the sum of the squared differences of each of the three color components). The goal is to search as quickly as possible. Iterating over all the elements of the array and looking for proximity to a given color for each one is too expensive (the task is to fill a new array with several million more elements, for each one it takes a long time to do a complete enumeration). How can this search be done? Maybe what algorithms exist?

Answer 1

en.wikipedia.org/wiki/Nearest_neighbor_search
en.wikipedia.org/wiki/Kd-tree

Answer 2

I once used the following algorithm (I really had the task not to get an absolutely close value, but just a color from a close zone, but suddenly you can get something for yourself):
1. A uniform three-dimensional array (P) is created in a given space with a certain step , for example 4. That is, the RGB coordinates of the elements will be 000, 400, 040, 440, etc.
2. We go through all the elements of the original array (A) of colors and fill in our uniform array (P) based on this data. If, for example, we have color 511 in the original array (A), then we remember this data for the closest element in the array (P): P[400]=511 otherwise we leave P[400]=0
3. Now it’s enough for us when searching nearest color (B) just go directly to the nearest array element on the grid (P):
B[301] -> closest color in grid 400 -> P[400]=511 -> closest source color 511…

Answer 3

One million elements out of 16 million elements of possible positions. You can try to create a position map, i.e. array[rgb] = 1 | 0.
If each position is described by one byte, then this is 16 MB of memory. Not so much, for modern cars?
Pretty simple addressing, a simple query, so you can use the search in breadth. If the search is made two-level, then the speed will be quite acceptable. (First search by areas 16x16x16, then search by points inside suitable areas).

Answer 4

If the distance between the colors in the array is the same, then you can store the colors as a 3-dimensional array. And then the search will be binary. If not, sadness, I will think further ...

Answer 5

Google spatial database and spatial index - there are plenty of ready-made solutions for 2D data, you may be able to find something ready-made for 3D as well.

Answer 6

I understand that many years have passed, but suddenly someone will come in handy later :)
In fact, the situation with flowers is simple, because. this is a discrete space. Roughly speaking, our RGB is the coordinates of a point in three-dimensional space. A point has neighborhoods - spheres, with a certain radius. The points that lie on the surface of this sphere are equidistant from the starting point at a distance equal to the radius of the sphere. The task is to reduce the search to a direct search, i.e. we take a sphere with a radius of 0 - there are points that are different from ours - it means they are closest, no - we increase the radius by 1, there are points - excellent, found, no, increase the radius further, etc. Perhaps, here you can use not a direct search, but a division in half in a given interval - this is already a creative moment :) How to implement this whole thing (this will work just fine for the situation above, when you need to search a fixed set a lot of times).
1. Create three arrays [0..255]. Arrays R, G, B. An array element is a set of indexes of elements of the initial array of points. Those. let point with color 100, 25, 250 have index 200 in the output array. Then we should do R[100].add(200); G[25].add(200); B[250].add(200);
2. Since we fill the arrays sequentially, then each element of the arrays R, G, B will already be an ordered set. If, for some reason, this is not the case, then the second step is to order each set.
3. We build three two-dimensional arrays UR[0..255,0..255]. U.G. U.B. Where UR[i,j] = the intersection of the sets R[i] and R[j]. The beauty is that we already have ordered sets and their intersection is built quite quickly. You can learn more here https://habrahabr.ru/post/250191/
This concludes our preparatory work. It will take some time, but then the search will be carried out very quickly.
So, in fact, the search for the nearest point to the desired one is simple. For i=0 to 255. coordinates of the desired point r, g, b. We take a set of values ​​UR[ri, r+i] - unite in URi, so for each array. Then we look at the intersection of the sets URi, UGi, UBi - if empty, i++, otherwise - any (or set - depends on the task) of the found elements is the original one. Of course, here you need to be careful not to go beyond the boundaries of arrays, etc., the main thing is the idea - we are looking for the nearest points, like points lying on the surface of a sphere with a center at the starting point, with the smallest radius. And in order not to run around the array every time - we prepared three arrays - with projections of points along each axis.
It would be possible to limit ourselves to the arrays R, G and B, but then with each search it would be necessary to find the intersection - this is probably more profitable for a small number of search iterations. For a large one, it is more profitable to construct sets of intersections and search for them.