FAST color counting of a pixmap.

BlitzMax Forums/BlitzMax Beginners Area/FAST color counting of a pixmap.

Ryan Burnside(Posted 2008) [#1]
Hello,

I wrote a function to count and store the number of colors in a pixmap derived from a timage. My problem is that the function is very slow. My function does work great but again speed is a HUGE issue. I would advise testing it with an extreamly low color image. It took about 5 minutes to process a normal photograph. I have created my own color object that stores values and have created a list to keep track of the color objects. This function will be built upon later and I will eventually need a tlist full of unique color objects.

Type color_data
	Field r#=0,g#=0,b#=0,h#=0,s#=0,v#=0
	' R=0-255
	'G=0-255
	'B=0-255
	'H=0-360 degrees
	'S=0-1
	'V=0-1
	Method set_rgb(R#,G#,B#)
	'set the r g b values directly then adjust the hsv
	Self.r=R
	Self.g=G
	Self.b=B
	
	' *now update hsv values*
	
	' now we need to convert our HSV values to base 1
	R=R/255
	G=G/255
	B=B/255
	' find the largest and smallest of the rgb colors
	Local Max_#=Max(r,Max(g,b))
	Local Min_#=Min(r,Min(g,b))
	
	' solve the hue value
	' if max=min (no hue)  hue is irrevelant here so we will just go with 0
	If max_=min_
		Self.h=0
	End If
	
	' if red is the highest with green greater or equal to blue
	If max_= R and G >= B
		Self.h=60*( (G-B)/(max_-Min_))+0
	End If
	' if red is the highest with green less than blue
	If max_= R and G < B
		Self.h=60*( (G-B)/(max_-Min_))+360
	End If
	' if the max is green
	If max_=G
		Self.h=60*( (B-R)/(max_-Min_))+120
	End If
	' if the max is blue
	If max_=B
		Self.h=60*( (R-G)/(max_-Min_))+240
	End If
	
	' now for the saturation value
	If max_ = 0
		Self.s=0
		Else
		Self.s= 1-(min_/max_)
	End If
	' finally the value
	Self.v=max_
	End Method
	
	Method set_hsv(H#,S#,V#)
	'set the h s v values directly then adjust the r g b values
	Self.h=H
	Self.s=S
	Self.v=V
	
	' now start adjusting the RGB values
	
	Local Hi%=(H/60.0) mod 6.0
	Local f#=(H/60.0)-Hi
	Local p#=V*(1.0-S)
	Local q#=V*(1.0-(f*S))
	Local t#=V*(1.0-(1.0-f)*S)
	
	' now preform the checks
	If Hi = 0
		R=V
		G=t
		B=p
	End If
	
	If Hi = 1
		R=q
		G=V
		B=p
	End If
	
	If Hi = 2
		R=p
		G=V
		B=t
	End If
	
	If Hi = 3
		R=p
		G=q
		B=V
	End If
	
	If Hi = 4
		R=t
		G=p
		B=V
	End If
	
	If Hi = 5
		R=V
		G=p
		B=q
	End If
	
	'convert to base 255
	Self.r=R*255.0
	Self.g=G*255.0
	Self.b=B*255.0
	
	
	EndMethod
End Type



Function count_colors(source:TImage) 
	Local sourcePixmap:TPixmap = LockImage(source) 
	Local sourcePixmapPtr:Byte Ptr = PixmapPixelPtr(sourcePixmap, 0, 0) 
	Local tmpPixmap:TPixmap = CopyPixmap(sourcePixmap)
	Local tmpPixmapPtr:Byte Ptr = PixmapPixelPtr(tmpPixmap,0,0)
	Local x:Int,y:Int
	Local w:Float = tmpPixmap.width
	Local h:Float = tmpPixmap.height
	
	Local color_list:TList = New TList

	For Local x:Float = 0.0 To w - 1
		For Local y:Float = 0 To h - 1
			Local red = sourcePixmapPtr[x * 4 + y * 4 * w] 
			Local green = sourcePixmapPtr[x * 4 + y * 4 * w + 1] 
			Local blue = sourcePixmapPtr[x * 4 + y * 4 * w + 2] 
	
			Local my_color:color_data = New color_data
			my_color.set_rgb(red, green, blue) 
			' see if the color is in the lsit
			Local in_list:Int = 0
			For Local i:color_data = EachIn(color_list) 
			
				If my_color.r = i.r
					If my_color.g = i.g
						If my_color.b = i.b
							in_list = 1
							Exit
						End If
					EndIf
				End If
				
				
			Next
			If Not in_list
				ListAddLast(color_list, my_color) 
			End If
			
		Next
	Next
	Notify("There are " + CountList(color_list) + " colors in this image.") 
	Return Null
EndFunction



ImaginaryHuman(Posted 2008) [#2]
I think there are algorithms for this kind of thing, like building a histogram, which should be much faster. Counting colors should be pretty quick to do.


Ryan Burnside(Posted 2008) [#3]
I think so too. The problem is storing the data for later use. I need to build a virtual palette of colors used and I think this adds some extensive overhead. I'm fairly new to pixmap editing and such.


Azathoth(Posted 2008) [#4]
I made this in afew minutes.

Type color_counter
	Field colors:Tmap
	
	Method New()
		colors=CreateMap()
	EndMethod
	
	Method Add(r,g,b)
		Local i
		
		If MapContains(colors,tos(r,g,b))
			i=Int(String(MapValueForKey(colors,tos(r,g,b))))
		EndIf
		i:+1
		MapInsert(colors,tos(r,g,b),String(i))
			
	EndMethod
	
	Method Count:Int()
		Local i
		For Local o:Object=EachIn MapKeys(colors)
			i:+1
		Next
		Return i
	EndMethod 
	
	Function Tos:String(r,g,b)	' rgb to a string
		Return String(r)+"-"+String(g)+"-"+String(b)
	EndFunction
EndType

Function count_colors(source:TImage) 
	Local sourcePixmap:TPixmap = LockImage(source) 
	Local sourcePixmapPtr:Byte Ptr = PixmapPixelPtr(sourcePixmap, 0, 0) 
	Local tmpPixmap:TPixmap = CopyPixmap(sourcePixmap)
	Local tmpPixmapPtr:Byte Ptr = PixmapPixelPtr(tmpPixmap,0,0)
	'Local x:Int,y:Int
	Local w:Int = tmpPixmap.width
	Local h:Int = tmpPixmap.height
	
	Local colors:color_counter=New color_counter
	
	For Local x:Int = 0 To w - 1
		For Local y:Int = 0 To h - 1
			Local red = sourcePixmapPtr[x * 4 + y * 4 * w] 
			Local green = sourcePixmapPtr[x * 4 + y * 4 * w + 1] 
			Local blue = sourcePixmapPtr[x * 4 + y * 4 * w + 2] 
			
			colors.Add(red,green,blue)
					
		Next
	Next
	Notify("There are " + colors.Count() + " colors in this image.") 
	Return Null
EndFunction



tonyg(Posted 2008) [#5]
How about
a) Create Type 'Pixel_colour' with fields argb, (possibly a,r,g,b) and count
b) Create a TMap.
c) Readpixel
d) Check whether there is a TMAP entry for string(argb)
e) If not, create a map entry with a new pixel_colour indexed to string(argb)
f) Repeat from c).
<edit> Took out code as didn'treally see Azathoth's post.


ImaginaryHuman(Posted 2008) [#6]
Yah, some kind of hash table thing, or some other kind of acceleration structure.


Ryan Burnside(Posted 2008) [#7]
Thanks for the help. Where are "maps" discussed in the help menu?


tonyg(Posted 2008) [#8]
Other than a command list... they're not.
This might help


Ryan Burnside(Posted 2008) [#9]
Ok I thought I may have missed something. Damn shame so much basic information is missing in the documentation. Well, that comment is a bit like beating a dead horse now.


Retimer(Posted 2008) [#10]
I tried a different way of counting colors in images, working from what i've seen here. Fastest way is probobly array:

Code is an example, should be able to run this as is.



Colors: 178127
Width: 2304  Height: 1728
{3981312 pixels Processed in 918ms}



xlsior(Posted 2008) [#11]
Seems pretty speedy:

Colors: 434230
Width: 2288 Height: 1712
{3917056 pixels Processed in 175ms}

or a huge image:

Colors: 89588
Width: 5400 Height: 3600
{19440000 pixels Processed in 662ms}

(Core 2 Duo E6600 @ 2.4GHz)


Retimer(Posted 2008) [#12]
Yeah, calls to lists or maps is an organized way of checking previously found colors, but extremely non-optimistic in terms of speed.

With the array, you only check once if a color has been met. With tlist/maps your checking EVERY single pixel whether a color has been added or not.
With an array, you can even count how many times a color was found, with no real loss in speed (talking 5-10%, maybe).

My method (derived from burnsides pixel ptr method of getting r,g,b values) could probobly still be optimized some. I would assume this is the idea that programs like paintshop pro & adobe use for counting colors.