Counting colors used in an image.
BlitzMax Forums/BlitzMax Beginners Area/Counting colors used in an image.
| ||
| What is the best way to get how many colors are used in a loaded pixmap? This is for a graphics application I'm working on. At the moment the only thing I can think of is iterating through the image pixel by pixel but this may be very slow for larger images. Can anyone find a better way? |
| ||
| If you want to know how many unique colors are there you have to look at every single pixel, no way to avoid it. It's just a matter of how efficiently you keep your list of unique colors that you've found so far and their quantities, and how efficiently you search for an existing unique color vs adding a new one. Isn't this what a histogram is for? I would just use an array of bank with pointers to access your stored results, and go through the image one pixel at a time at the pointer level. You might make use of the `map` functionality, to create a hash table for quick access to entries in your running totals. Process the image one row at a time from left to right, as it is organized in memory that way. It won't take as long as you think. |
| ||
| i remember: the fastest routine was a sort-algoritm (quick-sort) and then count unique colors - use also integers (argb) you need only a array you don't need map |
| ||
| Ok thank you, I'll look into these. |
| ||
| You can use an array, but at the simplest this would mean on a 24bit image you would be looking at 64Mb (16Gig if you count alphas), which I suppose isnt outragious nowadays, but its something to remember. At least with a map you only need a node for the colours that actualy exist. I suppose you could have 2d array with the fist index being a colour that exists, and the second the number of times that colour is used, but I for one would call that a "Map", in which case you might as well use the map funtionality |
| ||
| Thats a good idea MrCredo - sort all the pixels and then as you go through them when the next pixel is different to the previous one you start a new count (or add 1 to a count), and then store or print it later. |
| ||
| you don't need map Nope. But it's faster. Inserting into a Red/Black tree is O=(log n), where as quicksort is O=(n log n).Also as H&K suggests the Red/Black tree will probably use up significantly less memory. |
| ||
| i testet blitz-map a time ago... i think it was wrong implemented... it was much slower then all other stuff... |
| ||
| Did you test it before this ? P.S. @ Ryan, Try the pixel by pixel method. It might be quicker than you think. |
| ||
| i don't know... 11 months ago... hmmm |
| ||
In either case, here is the smart data / dumb algorithm version. It does pretty much everything you could want. It processes the test image in about 170ms.SuperStrict
Local myPix:TPixmap = LoadPixmap("fucklars.jpg")
Local key:String
Local colours:TMap = New TMap
Local count:Int = 0
Local time:Int = MilliSecs()
For Local y:Int = 0 Until myPix.height
For Local x:Int = 0 Until myPix.width
key = Hex( myPix.readPixel( x,y ) )
key = key [2..]
If Not colours.contains(key)
colours.insert(key , "1")
count:+1
Else
Local inc:String = colours.valueForKey( key ).toString()
inc = String( Int(inc) + 1 )
EndIf
Next
Next
Print "Pixels : " + (myPix.width * myPix.height)
Print "Colors : " + count
Print "Time : " + (MilliSecs() - time) +" ms."
Print "Memory : " + GCMemAlloced()/1024/1024.0 + " MB." |
| ||
| yes but... you use strings! this is a overkill |
| ||
I wrote this just for you, based on the quicksort & count algorithm...
Strict
'Get a picture
Local myPix:TPixmap=LoadPixmap(RequestFile("Load a picture,"))
If myPix=Null Then End
If PixmapFormat(myPix)<>PF_RGBA8888 Then myPix=ConvertPixmap(myPix,PF_RGBA8888) 'Avoid if possible
Local Total:Int=myPix.width*myPix.height
Print "Pixels: " + Total
Print "Memory: " + (Total Shl 3)
Print "Sorting..."
'Start timing - as if picture was already in memory
Local Time:Int=MilliSecs()
Local Base:Byte Ptr=PixmapPixelPtr(myPix)
Local PitchBytes:Int=PixmapPitch(myPix) 'in bytes
'Convert to memory area with same Pitch as Pixels*4
Local bnk:TBank=CreateBank(Total Shl 2)
Local bnkmem:Byte Ptr=BankBuf(bnk)
Local rowsize:Int=myPix.width Shl 2
Local bnkmem2:Byte Ptr=bnkmem
For Local count:Int=0 Until myPix.height
MemCopy(bnkmem2,Base+(count*PitchBytes),rowsize)
bnkmem2:+rowsize
Next
'Here you need a sort algorithm to sort all the pixels into order by value
'This is a quick sort - very fast, recursive
'Sorts based on whole pixel value including Alpha
Local IBase:Int Ptr=Int Ptr(bnkmem)
QuickSort(IBase,0,Total-1)
Function QuickSort(IBase:Int Ptr,Bottom:Int,Top:Int)
If Bottom=Top Then Return
Local Pivot:Int
Local Temp:Int
Local BottomTemp:Int
Local TopTemp:Int
BottomTemp=Bottom
TopTemp=Top
Pivot=IBase[(Bottom+Top) Shr 1]
While BottomTemp<=TopTemp
'< Comparison of the values is a descending sort
While (IBase[BottomTemp]<Pivot) And (BottomTemp<Top)
BottomTemp:+1
Wend
While (Pivot<IBase[TopTemp]) And (TopTemp>Bottom)
TopTemp:-1
Wend
'Swap
If BottomTemp<TopTemp
Temp=IBase[BottomTemp]
IBase[BottomTemp]=IBase[TopTemp]
IBase[TopTemp]=Temp
End If
If BottomTemp<=TopTemp
BottomTemp:+1
TopTemp:-1
End If
Wend
'The function calls itself until everything is in good order
If (Bottom<TopTemp) Then QuickSort(IBase,Bottom,TopTemp)
If (BottomTemp<Top) Then QuickSort(IBase,BottomTemp,Top)
End Function
Local Time2:Int=MilliSecs()
Print "Sort took: "+(Time2-Time) + " MilliSecs"
Print "Counting..."
'Count the unique colors
Local ColorCount:Int=0
Local PrevColor:Int=0
Const Mask:Int=$FFFFFF00 'to mask out alpha in RGBA
'Const Mask:Int=$FFFFFFFF 'to include Alpha
If (IBase[0] & Mask)=(IBase[1] & Mask) Then ColorCount=1 'handle the first pixel
For Local pix:Int=0 Until Total-1
Local Pixel:Int=IBase[pix] & Mask
If Pixel<>PrevColor Then ColorCount:+1
PrevColor=Pixel
Next
'Report
Local Time3:Int=MilliSecs()
Print "Count took: "+(Time3-Time2) + " MilliSecs"
Print "Total time: " + (Time3-Time) + " Millisecs"
Print "~nColors found: " + ColorCount
On my 2Ghz Intel iMac (Core 2 Duo) (the program only uses one core), on a 1100 x 797 32-bit JPEG image, it takes about 131 Millisecs. Almost all but 2 millisecs are taken with sorting, and the remaining 2 with counting unique colors. You can't really compare it to FlameDucks time result because not only is it a different CPU/computer/os but also a different image and size. Just see if it's good enough for you. A pixmap of your choice is loaded. If needed it is converted to RGBA8888 format to make sure it is 1 Integer per pixel. The pixel data is then copied into a Bank to trim off any difference between the number of bytes consumed by pixels in a row, and the pitch of the row (ie no gaps so it ends up as one solid stream of pixel data - which it might already be). You could take out this step but it will only save you about 1 millisecond. The QuickSort was adapted from VisualBasic code found online, to use Int Ptr access rather than strings. I wrote the rest of it, and of course you can use it however you wish. The quicksort is probably useful elsewhere too - it's definitely WAY faster than a bubble sort (I initially coded this with a bubble sort and it took like 35000 Millisecs!) I did create a small 5-color image to test that the count is working and it did count 5 unique colors, so I think this is working right. [EDIT] Minor correction, the if IBase[0] & Mask = IBase[0] & Mask should've been if IBase[0] & Mask = Ibase[1] & Mask [/EDIT] |
| ||
| Wow you are the man! This is really great and I shall credit you if you wish. |
| ||
| @Flameduck: .. Local myPix:TPixmap = LoadPixmap("fucklars.jpg") .. that wasn't very nice.. :p |
| ||
| LOOOOOOOOOOOOOOL |
| ||
| Go ahead and use it how you wish. If you'd like to mention me then feel free. I was thinking, last night, that maybe if you are trying to count color components only and not alpha, then also the sort should be adapted to sort values based on RGB instead of RGBA ..... but I think actually it doesn't matter because all #FE379A pixels (for example) would all be next to each other, and the any variations in alpha values would be in sequence like #FE379A34, #FE379A35, #FE379A36 etc. So It should be compatible for including alpha or excluding alpha. I'm still not sure why some other apps report different color counts. I tried it with a lossless compression image (PNG) and still got different numbers. Maybe do some tests and see what you come up with. That quicksort is cool to use for other situations where you need to sort data ... it's like 1000 times faster than a bubble sort! Actually I got quite caught up in writing this code, and totally avoided doing my own project ;-) But maybe this will be handy for me also at some point - I'm working on what is partly a graphics app as well. |
| ||
| I made a minor bug correction, see the end of the original code post above. |
| ||
| you use strings! this is a overkill No it isn't. For starters you need an object type to key the map (and Int's aren't). Secondly whether having them in Hex representation is usful, depends on what you're using them for. |
   |