fastest way to compare bit maps

[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?

[idle]

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

[djes]

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

[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)

[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

[Ramihyn_]

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

[idle]

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]

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]

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

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

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

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

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