FAST color counting of a pixmap.

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

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


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.

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.

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


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.

Yah, some kind of hash table thing, or some other kind of acceleration structure.

Thanks for the help. Where are "maps" discussed in the help menu?

Other than a command list... they're not.
This might help

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.

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.
SuperStrict

Local Colors:Byte[256, 256, 256] 
Local Pix:TPixmap, PixPtr:Byte Ptr, TimerEnd:Int
Local i:Int, ii:Int, iii:Int
Local W:Int, H:Int, X:Int, Y:Int
Local ColorCount:Int
Local TimerStart:Int
Local Image:TImage



Image = LoadImage(RequestFile("Pixmap..")) 
Pix = LockImage(Image) 
W = pix.width
h = pix.height
PixPtr = pix.PixelPtr(0, 0) 




TimerStart = MilliSecs() 
For x = 0 To w - 1
	For y = 0 To pix.height - 1
		Colors[PixPtr[x * 4 + y * 4 * w] , PixPtr[x * 4 + y * 4 * w + 1] , PixPtr[x * 4 + y * 4 * w + 2] ] = 1
	Next
Next

'counting

For i = 0 To 255
	For ii = 0 To 255
		For iii = 0 To 255
			If colors[i, ii, iii] Then ColorCount:+1
		Next
	Next
Next

TimerEnd = MilliSecs() 

Print "Colors: " + colorcount
Print "Width: " + pix.width + "  Height: " + pix.height
Print "{" + pix.width * pix.height + " pixels Processed in " + (timerend - timerstart) + "ms}"



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


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)

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.