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

;*** colorList - R Ferriby

Type cnode
	Field cnode.cnode[256]
	Field count%
End Type

Global mpopRed%,mpopGreen%,mpopBlue%
Global lpopRed%,lpopGreen%,lpopBlue%

colorList.cnode=New cnode

;*** test 8 colors of which 5 should be unique
AddColorToList(colorList,255,0,0)
AddColorToList(colorList,0,255,0)
AddColorToList(colorList,0,0,255)
AddColorToList(colorList,0,0,0)
AddColorToList(colorList,255,255,255)
AddColorToList(colorList,0,255,0)
AddColorToList(colorList,0,255,0)
AddColorToList(colorList,0,255,0)

totalcolors%=TotalColorCount(colorList)
Print "totalcolors= "+totalcolors
uniquecolors%=UniqueColorCount(colorList)
Print "uniquecolors= "+uniquecolors
mpopcolor%=MostPopularColor(colorList)
Print "most popular color= "+mpopRed+", "+mpopGreen+", "+mpopBlue+" count="+mpopcolor
lpopcolor%=LeastPopularColor(colorList)
Print "least popular color= "+lpopRed+", "+lpopGreen+", "+lpopBlue+" count="+lpopcolor
WaitKey
End

Function AddColorToList(clist.cnode,r%,g%,b%)
	;*** first RED
	If clist\cnode[r]=Null
		clist\cnode[r]=New cnode
	EndIf
	clist\cnode[r]\count=clist\cnode[r]\count+1
	;*** next GREEN
	If clist\cnode[r]\cnode[g]=Null
		clist\cnode[r]\cnode[g]=New cnode
	EndIf
	clist\cnode[r]\cnode[g]\count=clist\cnode[r]\cnode[g]\count+1
	;*** last BLUE
	If clist\cnode[r]\cnode[g]\cnode[b]=Null
		clist\cnode[r]\cnode[g]\cnode[b]=New cnode
	EndIf
	clist\cnode[r]\cnode[g]\cnode[b]\count=clist\cnode[r]\cnode[g]\cnode[b]\count+1
End Function

Function TotalColorCount%(clist.cnode)
	Local i%,c%
	For i=0 To 255
		If clist\cnode[i]<>Null
			c=c+clist\cnode[i]\count
		EndIf
	Next
	Return c
End Function

Function UniqueColorCount%(clist.cnode)
	Local r%,g%,b%,c%
	c=0
	For r=0 To 255
		If clist\cnode[r]<>Null
			Local gnode.cnode=clist\cnode[r]
			For g=0 To 255
				If gnode\cnode[g]<>Null
					Local bnode.cnode=gnode\cnode[g]
					For b=0 To 255
						If bnode\cnode[b]<>Null
							c=c+1
						EndIf
					Next
				EndIf
			Next
		EndIf
	Next
	Return c
End Function

Function MostPopularColor%(clist.cnode)
	Local r%,g%,b%,c%
	Local popular.cnode=Null
	c=0
	For r=0 To 255
		If clist\cnode[r]<>Null
			If clist\cnode[r]\count>c
				popular=clist\cnode[r]
				c=popular\count
				mpopRed=r
			EndIf
		EndIf
	Next
	If popular<>Null
		clist=popular
		c=0
		For g=0 To 255
			If clist\cnode[g]<>Null
				If clist\cnode[g]\count>c
					popular=clist\cnode[g]
					c=popular\count
					mpopGreen=g
				EndIf
			EndIf
		Next
		If popular<>Null
			clist=popular
			c=0
			For b=0 To 255
				If clist\cnode[b]<>Null
					If clist\cnode[b]\count>c
						popular=clist\cnode[b]
						c=popular\count
						mpopBlue=b
					EndIf
				EndIf
			Next
		EndIf
	EndIf
	Return c
End Function

Function LeastPopularColor%(clist.cnode)
	Local r%,g%,b%,c%
	Local popular.cnode=Null
	c=$7fffffff
	For r=0 To 255
		If clist\cnode[r]<>Null
			If clist\cnode[r]\count<c
				popular=clist\cnode[r]
				c=popular\count
				lpopRed=r
			EndIf
		EndIf
	Next
	If popular<>Null
		clist=popular
		c=$7fffffff
		For g=0 To 255
			If clist\cnode[g]<>Null
				If clist\cnode[g]\count<c
					popular=clist\cnode[g]
					c=popular\count
					lpopGreen=g
				EndIf
			EndIf
		Next
		If popular<>Null
			clist=popular
			c=$7fffffff
			For b=0 To 255
				If clist\cnode[b]<>Null
					If clist\cnode[b]\count<c
						popular=clist\cnode[b]
						c=popular\count
						lpopBlue=b
					EndIf
				EndIf
			Next
		EndIf
	EndIf
	Return c
End Function

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