Page 1 of 1
fastest way to compare bit maps
Posted: Thu Feb 16, 2012 8:53 am
by alokdube
Hi,
I have to compare one 1024x1024 image with another 1024x1024 image
the idea is to compare "dot/no dot" or rather "1"s and "0"s with another set of 1s and 0s.
Was wondering if ASM is the best way to carry this out?
so if you have say 6x4 grid
101010
101010
101010
101010
, it should match
010101
010101
010101
010101
Essentially the pattern of the 3 straight lines is the same.
Fastest seems to be the inline ASM with right/left shift across the zeros (without knocking off any of the 1s in the image in this case?
Any other suggestions?
Re: fastest way to compare bit maps
Posted: Thu Feb 16, 2012 10:50 am
by idle
Ok but what are you intending to do with the result, it will make a difference.
Re: fastest way to compare bit maps
Posted: Thu Feb 16, 2012 12:00 pm
by djes
Maybe OpenCV could do the job ? Why always reinvent the wheel ?
Re: fastest way to compare bit maps
Posted: Thu Feb 16, 2012 2:18 pm
by DarkDragon
I made this one for a PureBasic user a while ago, maybe it helps for your problem, too, as the usage of summed area tables or integral images is good when comparing two images, but here we find a sub image:
Code: Select all
EnableExplicit
Structure RGB
R.l
G.l
B.l
EndStructure
Structure IntegralImage
Width.i
Height.i
*ValuesPointer.i
EndStructure
Procedure.i IntegralImage(PBImage.i, *Image.IntegralImage)
Protected Color.i
Protected *Cursor.RGB
Protected *CursorAbove.RGB
Protected *CursorAboveLeft.RGB
Protected *CursorLeft.RGB
Protected X.i, Y.i
If Not IsImage(PBImage)
ProcedureReturn #False
EndIf
*Image\Width = ImageWidth(PBImage)
*Image\Height = ImageHeight(PBImage)
*Image\ValuesPointer = AllocateMemory(*Image\Width * *Image\Height * SizeOf(RGB))
If *Image\ValuesPointer = #Null
ProcedureReturn #False
EndIf
*Cursor = *Image\ValuesPointer
*CursorAbove = *Image\ValuesPointer - *Image\Width * SizeOf(RGB)
*CursorAboveLeft = *Image\ValuesPointer - *Image\Width * SizeOf(RGB) - SizeOf(RGB)
*CursorLeft = *Image\ValuesPointer - SizeOf(RGB)
StartDrawing(ImageOutput(PBImage))
For Y = 0 To OutputHeight() - 1
For X = 0 To OutputWidth() - 1
Color = Point(X, Y)
*Cursor\R = Red(Color)
*Cursor\G = Green(Color)
*Cursor\B = Blue(Color)
If X > 0
*Cursor\R + *CursorLeft\R
*Cursor\G + *CursorLeft\G
*Cursor\B + *CursorLeft\B
If Y > 0
*Cursor\R - *CursorAboveLeft\R
*Cursor\G - *CursorAboveLeft\G
*Cursor\B - *CursorAboveLeft\B
EndIf
EndIf
If Y > 0
*Cursor\R + *CursorAbove\R
*Cursor\G + *CursorAbove\G
*Cursor\B + *CursorAbove\B
EndIf
*CursorLeft + SizeOf(RGB)
*CursorAbove + SizeOf(RGB)
*CursorAboveLeft + SizeOf(RGB)
*Cursor + SizeOf(RGB)
Next X
Next Y
StopDrawing()
ProcedureReturn #True
EndProcedure
Procedure.i ToPBImage(*Image.IntegralImage, PBImage.i)
Protected X.i, Y.i
Protected Result.i
Protected *Cursor.RGB
Protected Max.RGB
Result = CreateImage(PBImage, *Image\Width, *Image\Height)
If PBImage = #PB_Any : PBImage = Result : EndIf
StartDrawing(ImageOutput(PBImage))
*Cursor = *Image\ValuesPointer
CopyStructure(*Image\ValuesPointer + OutputWidth() * OutputHeight() * SizeOf(RGB) - SizeOf(RGB), @Max, RGB)
For Y = 0 To OutputHeight() - 1
For X = 0 To OutputWidth() - 1
Plot(X, Y, RGB(*Cursor\R * 255 / Max\R, *Cursor\G * 255 / Max\G, *Cursor\B * 255 / Max\B))
*Cursor + SizeOf(RGB)
Next X
Next Y
StopDrawing()
ProcedureReturn Result
EndProcedure
Procedure.i GetMeanColor(*Image.IntegralImage, X.i, Y.i, Width.i, Height.i)
Protected ResultRGB.RGB
Protected *RGBPointer.RGB
Protected Result.i = 0
Protected Right.i, Bottom.i
Protected Index.i
Protected Factor.d
Right = X + Width - 1
Bottom = Y + Height - 1
Index = Right + Bottom * *Image\Width
If Index >= 0
CopyStructure(*Image\ValuesPointer + Index * SizeOf(RGB), @ResultRGB, RGB)
EndIf
Index = X + Bottom * *Image\Width
If Index >= 0
*RGBPointer = *Image\ValuesPointer + Index * SizeOf(RGB)
ResultRGB\R - *RGBPointer\R
ResultRGB\G - *RGBPointer\G
ResultRGB\B - *RGBPointer\B
EndIf
Index = X + Y * *Image\Width
If Index >= 0
*RGBPointer = *Image\ValuesPointer + Index * SizeOf(RGB)
ResultRGB\R + *RGBPointer\R
ResultRGB\G + *RGBPointer\G
ResultRGB\B + *RGBPointer\B
EndIf
Index = Right + Y * *Image\Width
If Index >= 0
*RGBPointer = *Image\ValuesPointer + Index * SizeOf(RGB)
ResultRGB\R - *RGBPointer\R
ResultRGB\G - *RGBPointer\G
ResultRGB\B - *RGBPointer\B
EndIf
Factor = 1.0 / (Width * Height)
ProcedureReturn RGB(ResultRGB\R * Factor, ResultRGB\G * Factor, ResultRGB\B * Factor)
EndProcedure
Procedure.i CompareRecursive(*Image1.IntegralImage, OffX1.i, OffY1.i, *Image2.IntegralImage, OffX2.i = -1, OffY2.i = -1, Width.i = -1, Height.i = -1)
Protected NewSize.i
If Width = -1
Width = *Image2\Width
EndIf
If Height = -1
Height = *Image2\Height
EndIf
If OffX2 = -1
OffX2 = 0
EndIf
If OffY2 = -1
OffY2 = 0
EndIf
If GetMeanColor(*Image1, OffX1, OffY1, Width, Height) = GetMeanColor(*Image2, OffX2, OffY2, Width, Height)
If Width >= Height
If Width >= 2
NewSize = Width >> 1
If Not (CompareRecursive(*Image1, OffX1, OffY1, *Image2, OffX2, OffY2, NewSize, Height) And CompareRecursive(*Image1, OffX1 + NewSize, OffY1, *Image2, OffX2 + NewSize, OffY2, NewSize + (Width & $01), Height))
ProcedureReturn #False
EndIf
EndIf
Else
If Height >= 2
NewSize = Height >> 1
If Not (CompareRecursive(*Image1, OffX1, OffY1, *Image2, OffX2, OffY2, Width, NewSize) And CompareRecursive(*Image1, OffX1, OffY1 + NewSize, *Image2, OffX2, OffY2 + NewSize, Width, NewSize + (Height & $01)))
ProcedureReturn #False
EndIf
EndIf
EndIf
ProcedureReturn #True
EndIf
ProcedureReturn #False
EndProcedure
Structure Position
X.i
Y.i
EndStructure
Define Image.IntegralImage
Define ImageSearch.IntegralImage
UsePNGImageDecoder()
UsePNGImageEncoder()
LoadImage(0, "test.png")
LoadImage(1, "testsearch.png")
IntegralImage(1, @ImageSearch)
Define X.i, Y.i
Define Time.i
NewList FoundEntries.Position()
Time = ElapsedMilliseconds()
IntegralImage(0, @Image)
For X = 0 To Image\Width - ImageSearch\Width
For Y = 0 To Image\Height - ImageSearch\Height
If CompareRecursive(@Image, X, Y, @ImageSearch)
AddElement(FoundEntries())
FoundEntries()\X = X
FoundEntries()\Y = Y
EndIf
Next Y
Next X
Time = ElapsedMilliseconds() - Time
ToPBImage(@Image, 2)
SaveImage(2, "integral.png", #PB_ImagePlugin_PNG)
FreeImage(2)
ToPBImage(@ImageSearch, 2)
SaveImage(2, "integralsearch.png", #PB_ImagePlugin_PNG)
FreeImage(2)
Define Text.s = ""
ForEach FoundEntries()
Text + RSet(Str(FoundEntries()\X), 3, " ") + ", " + RSet(Str(FoundEntries()\Y), 3, " ") + #CRLF$
Next
MessageRequester("Done", "Time needed: " + Str(Time) + "ms" + #CRLF$ + "Found positions: " + #CRLF$ + Text)
Re: fastest way to compare bit maps
Posted: Tue Feb 21, 2012 6:53 am
by alokdube
Just want to compare 2 bit maps, black and white bit maps
Say like a finger print scanner.
@Braden:
CopyStructure(*Image\ValuesPointer + OutputWidth() * OutputHeight() * SizeOf(RGB) - SizeOf(RGB), @Max, RGB)
seems to break, im on an older version of PB
Re: fastest way to compare bit maps
Posted: Tue Feb 21, 2012 1:36 pm
by Ramihyn_
If you want to check if two fingerprints are "the same", then you have to do it very very differently.
Re: fastest way to compare bit maps
Posted: Tue Feb 21, 2012 8:02 pm
by idle
Ramihyn_ wrote:If you want to check if two fingerprints are "the same", then you have to do it very very differently.
That's a bit of an understatement, having a masters in image processing would be a good start for a fingerprint scanner!
Re: fastest way to compare bit maps
Posted: Tue Apr 24, 2012 10:24 am
by alokdube
Not sure what the masters has to do with the algo,
The fastest I can think of is the 10x10 box running superficially over another 10x10 box and somehow finding say max 5x5 or a 6x6 part that is the same in both...even if 60 pixels out of 100 match, in a distributed image map, would it matter (I have seen papers on the normalization approach around a generic curve etc but still the old fashioned way seems the fastest)
A bit map running on top of another bit map is my idea of the fastest approach.
Re: fastest way to compare bit maps
Posted: Tue Apr 24, 2012 9:43 pm
by idle
I suppose you could use correlation but you'd probably need to scale and rotate the image first
Re: fastest way to compare bit maps
Posted: Wed Apr 25, 2012 12:21 am
by electrochrisso
A bit map running on top of another bit map is my idea of the fastest approach
That's what I was thinking, get some kind of average for fingerprint 1, then the average for fingerprint 2, merge them and get the average from that. How to create the formula for the average, well that will take a bit of thinking and testing. Gives me something to think about anyhow.
Re: fastest way to compare bit maps
Posted: Wed May 02, 2012 10:11 am
by alokdube
Dont average out, simply put a range as to "if X percentage dots match, image matches else not" these are all black and white dots.
Re: fastest way to compare bit maps
Posted: Wed May 02, 2012 7:05 pm
by DarkDragon
A common way for this is normalizing the image, gabor enhance it, thin it (not skeletonize!), find endpoints of thinned lines and there you have your feature points which are concatenated to a feature vector. When comparing two sets of feature points they usually just bruteforce the movement heuristically. You can combine it with some other distance measures to get better results.
Re: fastest way to compare bit maps
Posted: Thu May 03, 2012 9:27 am
by alokdube
Thanks Braden!
i would kind of put a coin or some "scale" next to the images and ensure they end up being the same size prior to starting the match
So for example if the scale shows up as 5x5 pixels wide on one , and 4x4 pixels wide on the other, id simply reduce the size to match the smaller one (4x4) as i have that info (enhancing would imply interpolation/ i.e. no genuine data but an approximation) and compare the 2 images
seems nice to me...