Counting unique colors in an image
Blitz3D Forums/Blitz3D Programming/Counting unique colors in an image
| ||
| Hi, I´m looking for the best way to count the unique colors in an image. Now, I can think of several pretty easy ways to do this, but most of them seems to me to be inefficient and slow. After doing some research I found a method used for quantizing colors that uses an octree for storing and sorting the RGB values. And from what I understood the unique colors gets counted aswell. Which means I could get a color palette, and each palette index with a pixelcounter in one "run-through" of the image. But I´m new to the idea of an octree and how to implement that. And the code examples i found weren´t that easy to understand. So I´m wondering if anyone could give me some help here on how to do this? |
| ||
| All you need to do is to create an RGB table that increases as you find new colors. It will be slow, but you only have one pass through your image, and a loop through your growing list of colors. Finally, you count your entries in your list. Cheers. |
| ||
| Well, I thought of that. But since I need to go through the whole list once for each pixel in the image, I´d guess that it could take a while for large images with millions of unique rgb values. There has to be some faster way, I hope? |
| ||
Dim ColorTable(16777215) for x=0 to imagewidth(image)-1 for y=0 to imageheight(image)-1 col=readpixel(x,y,imagebuffer(image)) and 16777215 ColorTable(col)=1 next next type TUniqueColor field rGB end type for i=0 to 16777215 if ColorTable(i)=1 then UniqueColor.TUniqueColor=new TUniqueColor UniqueColor\RGB=i endif next may need some changes though |
| ||
LOL, there's your faster answer:Dim ColorTable(16777215)I just didn't want to mention that you'd have to reserve 64 megs (16 million times ints). But, you could always reserve a bank (CreateBank) of 16 megs. |
| ||
| You could create a bank to act as one huge bit field (16+ million bits). That'll only use about 2 megs. :P |
| ||
| OMG, so true! |
| ||
| Well, that method is as fast as it can get. But Dim ColorTable(16777215) is LARGE, and if I wanted to include the alpha channel..? Dim ColorTable(4.3 billions?) is a bit to much for me.. ;) But what about using 3 or 4 smaller arrays? Dim Red(255) Dim Green(255) Dim Blue(255) Dim Alpha(255,1) (the extra dimension used for counting every color independantly.) That should work, shouldn´t it? If I´m counting correct it would take around 5k of memory? |
| ||
| i don't think that will work as imagine two colours one thats, 255, 0,0 and another 255,1,0 - how would you store this? Looking at the above then the arrasy would contain... Red = 2 Green = 1 Blue = 0 How would that help determine the number of unique colours :-( |
| ||
| Your potential data set has 16+ million (excluding alpha) values - there's no getting around that. However, any image is unlikely to contain anything approaching that many colours, I would think. An image containing all 16+ million colours would be ~4000x4000 in size at it's smallest (1 pixel for each colour). As such, I'd look into storing found colours in some kind of hash table/tree data structure. This would mean the structure would only grow in relation to the number of colours found, and would make searching for already found colours much faster/efficient. |
| ||
| Or why bother? Go to the beach instead :-) |
| ||
| lol :P |
| ||
| Hmmm, true, true.. My idea of 3 arrays lacks the relations info. As I stated in my first post, I found some info on using octrees(or some other kind of treestructure), but couldn´t quite grasp how to code that. Any ideas on how to do that? ps. you can always think about this while you´re on the beach. why else go there? ;) |
| ||
| Got a link to that article about using tree structures for this? |
| ||
| I used this method a decade ago using Blitz Basic on the Amiga which worked pretty well:- Create a list of 256 child node pointers. Each child node index represents the RED value in the RGB color. Create another child node at the index referenced by the RED component if there is'nt one there already. This new child node becomes the new "List" as it also has 256 child node pointers which are indexed by the GREEN component of the RGB colour. Create another child node at the index specified by the GREEN component. This becomes the new "List" for the BLUE component only this time, instead of 256 pointers to another child node it simply contains 256 counters which are incremented by 1 at the index specified by the BLUE component. As the RGB color can be used to index the nodes in the list you can find the count for any 1 color very quickly. To find the total number of colours used simply add all the counters in the blue nodes. As big10p pointed out an image with millions of unique colours in it can produce a large data set but there are very few images that use all 16m colours. Cheers, Roy |
| ||
| big10p: There are lots of articles. Just google on "octree color count" for example. Most of these describe ways to quantize images to reduce their numbers to a preset max value and get a good result. But most of these methods use octrees in similar ways that RoyFerriby describes. RoyFerriby: Thanks! Great explanation! Could you perhaps explain how to do this with some basic code example? I feel my brain is lost in all these nodes and trees and leaves. ;) Should I use arrays for pointers, or types? Just to clarify, as far as I can tell an octree seems to be bound to max 8 element in each level. The method RoyFerriby describes is the same but each level contains up to 256 elements. So the name octree might not be 100% accurate here... but who cares? Were going to the beach right? ;) |
| ||
| Sure! I've included some sample sourcecode below. There's enough there to get you started ;) Cheers, Roy |
| ||
| Thank you! I´ll give it go! |
| ||
| I´m back... ;) Just wanted to let you know that I have a complete function now that counts all colors. I took RoyFerribys code and modified it into an octree. So instead of 3 levels, it uses 8 levels and each node has 8 pointers. The reason for this is that when I have it in an octree there are lots of methods to reduce the number of colors if I wanted to. Here´s one link that shows how an octree is set up and used: http://www.cs.wfu.edu/~burg/nsf-due-0340969/worksheets/OctreeAlgorithm.pdf |
   |