fastest way to compare bit maps

alokdube · **Posted:** Thu Feb 16, 2012 8:53 am

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?

idle · **Posted:** Thu Feb 16, 2012 10:50 am

Ok but what are you intending to do with the result, it will make a difference.

djes · **Posted:** Thu Feb 16, 2012 12:00 pm

Maybe OpenCV could do the job ? Why always reinvent the wheel ?

DarkDragon · **Posted:** Thu Feb 16, 2012 2:18 pm

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:

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)

alokdube · **Posted:** Tue Feb 21, 2012 6:53 am

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

Ramihyn_ · **Joined:** Fri Feb 24, 2006 9:40 am **Posts:** 290

If you want to check if two fingerprints are "the same", then you have to do it very very differently.

idle · **Posted:** Tue Feb 21, 2012 8:02 pm

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!

alokdube · **Posted:** Tue Apr 24, 2012 10:24 am

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.

idle · **Posted:** Tue Apr 24, 2012 9:43 pm

I suppose you could use correlation but you'd probably need to scale and rotate the image first

electrochrisso · **Posted:** Wed Apr 25, 2012 12:21 am

Quote:

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.

alokdube · **Posted:** Wed May 02, 2012 10:11 am

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.

DarkDragon · **Posted:** Wed May 02, 2012 7:05 pm

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.

alokdube · **Posted:** Thu May 03, 2012 9:27 am

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

PureBasic Forum

fastest way to compare bit maps

Who is online