15,964,307 members
See more:
I am trying to find an efficient algorithem to search from a given Pixel array the closest Pixel to another given Pixel. The best match is the one where the difference between its R, G, B values are the lowest - i.e. The minimal of abs(Pixel1.R - Pixel2.R) + abs(Pixel1.G - Pixel2.G) + abs(Pixel1.B - Pixel2.B).
Is there an algorithem that allows me to search for this Pixel in way that won't require me to run on all my array, i.e. an algorithem that will run in less than O(n)? I am free to organize my array of Pixels any way I want.
Thanks for the help!
Posted

## Solution 2

Well if you must do many searches, I guess you can consider iterating through the array, finding the best match for each pixel, and storing it.

This will sure take some time ( O(n2) ), but once it's done all queries will take no time at all. :)

RanCohen 29-May-10 6:20am
The problem is I need to do each search with a different color, which means every time I need to iterate through the entire array, and unfortunately I do this search many many times, So I want something better than O(n)
Moreno Airoldi 29-May-10 7:51am
Humm ok so you are mathing a pixel from the array with a pixel which is outside the array (a "randomly" chosen color) then ?

In that case the only optimization I can think of is keeping a list of matches, so that if you query the same color again you won't have to go through the whole pixel array. Not much but... hehe :)

You may also prepare an initial matching list using the pixels from the array. How much that would help really depends on how the color/pixel you want to match is picked ofc.

## Solution 3

Excellent question. I believe I have an answer for you.

Sort the pixels into 3 lists. Each list would be sorted by the color intensity of a color component (red, green, or blue). Now, make a grid and set each point to store information about where in the 3 arrays that pixel is located. The lists also store where in the grid their corresponding pixel is. That is your basic data structure.

As far as the algorithm, I'd go for one that basically finds the position of the pixel in the 3 lists, then moves outward in each direction, scanning for pixels that are similar in color. You make the first six pixels candidates for being the closest pixel by color. However, since you have 3 factors (red, green, and blue) that determine the difference in color, those 6 pixels may not be the closest in color (though they will be closest by perhaps one component of the color). You calculate exactly how big the color difference is for those 6 pixels, and call that the minimum so far. You then continue spreading those 6 pixels outward from their originating point in the list. If you find pixels that are closer by color to the original pixel, you make those the new minimums. If you travel so far away from the original pixel that it would be impossible for a new pixel to have a closer color, then you stop searching that color list. Once you have stopped searching all the lists, you have your pixel that is the closest by color to the original pixel.

Using a radix sort (basically, a bucket sort), the sorting of the 3 lists could be done in O(n) where "n" is the number of pixels. But, that would only have to be done up front once. Each time you need to find a "closest pixel" would take less than O(n) (though I'm not exactly sure what the big-O notation would be).

## Solution 4

Just to add to my previous answer, I thought of another optimization. In each of the 3 lists, you could store sublists. Say you have 10 pixels that have a red value of 0. Then redList[0] would contain a list of those pixels sorted accorded to their green values. So, redList[0][1] would store a list of pixels sorted according to their blue values. So, redList[0][1][0] would contain a pixel with, say, a red value of 0, a green value of 20, and a blue value of 30. Then, redList[0][2][0] would have to contain a pixel with a greater green value than the pixel stored in redList[0][1][0]. That would allow you to eliminate possibilities faster. That's beginning to look like a tree structure... you might want to think about that some more and maybe a tree would be another good data structer to help you solve your problem.

RanCohen 29-May-10 7:37am
Let me see if I got it right - You are suggesting 3 lists: One sorted by R, G, B, One sortet by say G, B, R and a third sorted by B, R, G. I iterate the first until the difference in the R factor is greater then the total difference of the minimal RGB, Then I iterate the second list, then the third, with each time its faster then the last because the minimum is less in each iteration? It seems a good solution and its certainly less then iterating through the whole list, but is it realy much less then O(n)? Won't it be possible that in some cases i might run on most of the Red values before finding a match?
AspDotNetDev 29-May-10 19:40pm
In most cases, the algorithm will be very quick, especially if you have a fairly even distribution of colors. I think my optimization might help with some of the fringe cases. Still, it might approach O(n) for the very worst cases, though I expect those to be very uncommon. It would probably usually be more like O(1). And, no, I'm not saying you iterate the RGB list, then the GBR list, then then BRG list. You essentially create "bots" that iterate each list at the same time. So any time you move once in the RGB list, you then move once in the GBR list,t hen once in the BRG list. That should help you find the minimum color difference faster than iterating each list in succession (as you will be more likely to encounter a smaller color difference faster). So, even if your reds are a fringe case that would lead to a long search, your blues and green should help balance that out.

## Solution 5

One more thing to optimize my previous suggestion. If you travel 1 color value at a time in all 3 lists at once, then you can keep track of how far you've travelled in the other lists to know what the best possible minimum color you could achieve is. That way, you can use that as an exit condition to stop early. So, if you've reds are at 5 away, greens are at 2 away, and blues are at 4 away, and you already have a color that is a total of 10 color values different from the original color, you can stop.

RanCohen 2-Jun-10 8:08am
I think I thought of a somewhat simpler method - I look at the pixel as a coordinate in a space, and thus matching pixels are the ones that have the minimal distance between them. So instead of running on three lists, I can sort the array by the pixel distance to (0, 0, 0), and then do what you suggested - running up and down on the closest pixel, until the difference in the distances is greater then the minimal distance so far.
This is basicly the same algorithem, only now i run on a single list instead of three different lists that have to be interconnected.
AspDotNetDev 2-Jun-10 14:21pm
That will not work, unless there is a known relationship between color and location. You would still have to traverse the entire image to find the color which is closest to the original color. When they are sorted by color, you can detect when you've definitely reached the best color before scanning all of the pixels.
RanCohen 3-Jun-10 9:08am
Look at this for simplification as coordiantes in a 2D space. If I want to search for the closest match for (x1, y1), and assume that distance(x1, y1, 0, 0) is r1, I can look for the color with a distance to (0, 0) which is closest to r1. If the two colors distance is r2 between them, it means that the best possible match is between r1+r2, r1-r2 (its like a circle which has (x1, x2) in its circle and a radius of r2, and i am searching for the best match in that circle).
This is the same for a 3D space as well.
Is there an error in my logic?

## Solution 6

Hi,

There are many ways to achieve this.

1) The best way would be using a clustering algorithm with a maximum likelihood function. On the result of it each pixel will have a cluster membership. So in your subsequent search's you only need to search within the cluster members, not all the pixels again and again. If you use a unsupervised clustering technique then it will evolve into automatic clusters to number of cluster you asked. But if you want to control the clusters according to the nature of the image (For example if the image has forest and river only you may willing to have two clusters) then go for supervised clustering algorithm.

2) Second way is use Frequency mapping. Create each dictionary for R,G and B where keys are the color values (0 - 255) and values will be a list of pixel index. Say if you have 100 pixel , so say index it from 1 to 100. Now map the pixels against its R, store the list of pixels in the R dictionary with key as the R value. Once you mapped all pixels like this. Then say you pixel has R: 40, G:43: B:56 then using these values as key you will get a list of pixels in each band. Find the common pixels in these 3 lists( For this you can query the list using LinQ). If not present then find the lists for R+1,R-1,G+1,G-1,B+1, B-1.....the iteration goes in that way. In any case you wont be searching all pixels, in fact in a few iterations. Let me know if it confuse you I will write detailed note.

3) The third way would be an optimization of the second one. Human eye can found the nearest pixel to a certain extent. How we do that, obliviously we say both are same color. So why don't transform the waves in to color? I mean RGB in IHS where I is the intensity (bright or dull), S is the saturation (pure or impure) and H is the Hue otherwise the Color. So if you map the pixels to its Hue then from the pixels having same hue you can calculating the closest matching of the intensity and saturation.

Still lot of other ways also there. Choice is yours.