Efficient way to find same pixel?

This topic is 3210 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

Hi, Let's say this is to be done: Given an image with 32bit RGBA pixels, I wish to list down all the unique pixels, such that: R:G:B:A = 5:230:5:90 = occurs 5x in image R:G:B:A = 2: 42:5:10 = occurs 2x in image and so on... I could go and compare each pixel one by one through a loop (comparing first pixel with the rest of the image, then comparing 2nd pixel with the rest of the image, and so on). But that would be slow? is there a faster way? Or is there a method / tool already that does this? Thanks!

Share on other sites
1) Create a 4 dimensional array of integers, indexed by r, g, b and a.
2) Zero all entries
3) For each pixel, increment the correct array entry
4) Win (if you have enough memory)

Share on other sites
Quote:
 Original post by helloworld123I could go and compare each pixel one by one through a loop (comparing first pixel with the rest of the image, then comparing 2nd pixel with the rest of the image, and so on).But that would be slow?is there a faster way? Or is there a method / tool already that does this?

That can be performed much more efficiently if you sort the image's pixel values. Assuming img is a pointer to the image (if it's already a 32-bit type pointer, the cast is unnecessary).
unsigned int *img32bit = reinterpret_cast<unsigned int *>(img);std::sort(img32bit, img32bit+width*height);

Now all you have to do is find adjacent pixel values with the same color, instead of searching the whole image for the same color.

Quote:
 Original post by pbryant1) Create a 4 dimensional array of integers, indexed by r, g, b and a.2) Zero all entries3) For each pixel, increment the correct array entry4) Win (if you have enough memory)

And how much memory do you think would such an array require, even for a moderate color space such as 8-bits per component?

Share on other sites
Quote:
 Original post by Brother BobAnd how much memory do you think would such an array require, even for a moderate color space such as 8-bits per component?

16gb, but that is the speed/memory trade off (which incidentally, is the point I was trying to make)

Depending on your environment, you might not be able to allocate such a big array, so it would have to be split up. However, testing with a 1024x1024 rgb image gets the counts 33x faster than the required std::sort call alone (which essentially just does exactly what he stated in the original post - a compare of each pixel to every other pixel in the image).

Share on other sites
What if instead of int you'd store a bool value, so when the value is true, you know there's at least 1 pixel of that color. It would work when you only need to know whether color is unique not how many times it occurs.

Share on other sites
Quote:
 Original post by EigenWhat if instead of int you'd store a bool value, so when the value is true, you know there's at least 1 pixel of that color. It would work when you only need to know whether color is unique not how many times it occurs.

Yeah, if you just need to know if each color occurs then you can shave it down to 4gb, assuming your compiler has 1 byte bools.

Share on other sites
Quote:
 Original post by pbryant(which essentially just does exactly what he stated in the original post - a compare of each pixel to every other pixel in the image).

No, that's not what the sort method does. It doesn't compare with every pixel of the image, it compares values, and only as much as is needed to determine how many there are. Sorting only rearranges the order so you can make efficient assumptions about the order of equal pixels that you cannot do about the original image.

Quote:
Original post by pbryant
Quote:
 Original post by EigenWhat if instead of int you'd store a bool value, so when the value is true, you know there's at least 1 pixel of that color. It would work when you only need to know whether color is unique not how many times it occurs.

Yeah, if you just need to know if each color occurs then you can shave it down to 4gb, assuming your compiler has 1 byte bools.

If the task is only to find duplicate values, not how many of them (and that is, indeed, how he formulated it), you can even cut it down to 4 Gbits, or 512 MB. (edit: Scrap that; you need 2 bits to determine the second time a color is seen, so 1 GB.)

Share on other sites
What are you going to do with such a dataset?

Would it instead suffice that when an user provides a given color, the app would report the count of pixels with that particular color? This way, you wouldn't have to store anything but the actual image.

Share on other sites
Quote:
 Original post by Brother BobNo, that's not what the sort method does. It doesn't compare with every pixel of the image, it compares values, and only as much as is needed to determine how many there are. Sorting only rearranges the order so you can make efficient assumptions about the order of equal pixels that you cannot do about the original image.

~Essentially~

I realize that it doesn't actually compare each pixel with all the rest.
std::sort certainly doesn't determine "how many there are".

The point remains that massive gains can be made in terms of speed (far and above sorting) if you are willing to sacrifice memory.

Edit: In fact, you could probably just use a comparatively small hash table rather than a huge array, and still come out ahead by a factor of 30 over sorting.

Share on other sites
512MB with one bit per color would be enough to check for dublication (but the helloworld123 wants the count, so probably it's really 16GB).

which version is faster depends on the image size, the bit table has contant cost regarding the amount of pixel O(1) while the sorting is probably O(n log n).

Sometimes you can reduce the color range, e.g. if you want to generate a 256-color palette, you'd be fine with probably 6bit/channel, cause you'll quantitize the image anyway. 2^(3*6) bit are just 262144entries, even using int32, you'll end up with 1MB.

So I think both versions are valid, the better choice depends on the particular case:
-bit/channel
-image resolution
-checking for doublication vs. counting

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 10
• 9
• 9
• 11
• 11
• Forum Statistics

• Total Topics
633682
• Total Posts
3013314
×