# PureBasic Forum

 It is currently Tue May 21, 2013 3:05 pm

 All times are UTC + 1 hour

 Page 1 of 1 [ 13 posts ]
 Print view Previous topic | Next topic
Author Message
 Post subject: fastest way to compare bit mapsPosted: Thu Feb 16, 2012 8:53 am
 Enthusiast

Joined: Fri Nov 02, 2007 10:55 am
Posts: 143
Location: India
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?

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Thu Feb 16, 2012 10:50 am

Joined: Fri Sep 21, 2007 5:52 am
Posts: 2485
Location: New Zealand
Ok but what are you intending to do with the result, it will make a difference.

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Thu Feb 16, 2012 12:00 pm

Joined: Sat Feb 19, 2005 2:46 pm
Posts: 1334
Location: Pas-de-Calais, France
Maybe OpenCV could do the job ? Why always reinvent the wheel ?

_________________
The Shooting Crew ~> http://www.shootingcrew.com/
Bobble Puzzle, Purebreaker 3 ~> http://djes.free.fr

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Thu Feb 16, 2012 2:18 pm

Joined: Mon Jun 02, 2003 9:16 am
Posts: 1917
Location: Germany
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()

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

_________________
bye,
Daniel

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Tue Feb 21, 2012 6:53 am
 Enthusiast

Joined: Fri Nov 02, 2007 10:55 am
Posts: 143
Location: India
Just want to compare 2 bit maps, black and white bit maps
Say like a finger print scanner.
CopyStructure(*Image\ValuesPointer + OutputWidth() * OutputHeight() * SizeOf(RGB) - SizeOf(RGB), @Max, RGB)
seems to break, im on an older version of PB

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Tue Feb 21, 2012 1:36 pm
 Enthusiast

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.

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Tue Feb 21, 2012 8:02 pm

Joined: Fri Sep 21, 2007 5:52 am
Posts: 2485
Location: New Zealand
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!

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Tue Apr 24, 2012 10:24 am
 Enthusiast

Joined: Fri Nov 02, 2007 10:55 am
Posts: 143
Location: India
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.

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Tue Apr 24, 2012 9:43 pm

Joined: Fri Sep 21, 2007 5:52 am
Posts: 2485
Location: New Zealand
I suppose you could use correlation but you'd probably need to scale and rotate the image first

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Wed Apr 25, 2012 12:21 am
 Enthusiast

Joined: Mon May 14, 2007 2:13 am
Posts: 731
Location: Darling River
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.

_________________
PureBasic Rocks! Even More! And More!
PureBasic 5, Now We're Really Rockin!

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Wed May 02, 2012 10:11 am
 Enthusiast

Joined: Fri Nov 02, 2007 10:55 am
Posts: 143
Location: India
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.

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Wed May 02, 2012 7:05 pm

Joined: Mon Jun 02, 2003 9:16 am
Posts: 1917
Location: Germany
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.

_________________
bye,
Daniel

Top

 Post subject: Re: fastest way to compare bit mapsPosted: Thu May 03, 2012 9:27 am
 Enthusiast

Joined: Fri Nov 02, 2007 10:55 am
Posts: 143
Location: India
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...

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 1 of 1 [ 13 posts ]

 All times are UTC + 1 hour

#### Who is online

Users browsing this forum: Exabot [Bot] and 5 guests

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forum

Search for:
 Jump to:  Select a forum ------------------ PureBasic    Coding Questions    Game Programming    3D Programming    Assembly Programming    The PureBasic Editor    The PureBasic Form Designer    General Discussion    Feature Requests and Wishlists    Tricks 'n' Tips Bug Reports    Bugs - Windows    Bugs - Linux    Bugs - Mac OSX    Bugs - Documentation OS Specific    AmigaOS    Linux    Windows    Mac OSX Miscellaneous    Announcement    Off Topic Showcase    Applications - Feedback and Discussion    PureFORM & JaPBe    TailBite