I've played around a bit and thought that using something like the KMP algorithm (that's an easy one to implement I guess -> wikipedia has a nice pseudocode) might be helpfull too:
Imports System.Drawing.Imaging
Imports System.Runtime.InteropServices
Public Class ImageFinder
Public Shared Function Contains(Parent As Bitmap, Child As Bitmap) As Point
If Parent Is Nothing OrElse Child Is Nothing Then Throw New ArgumentException("Narf!")
If Parent.PixelFormat <> Imaging.PixelFormat.Format32bppArgb OrElse Child.PixelFormat <> Imaging.PixelFormat.Format32bppArgb Then Throw New ArgumentException("Narf again!")
If Parent.Width = Child.Width AndAlso Parent.Height = Child.Height AndAlso Parent.GetPixel(0, 0) <> Child.GetPixel(0, 0) Then Return Nothing
If Child.Width > Parent.Width OrElse Child.Height > Parent.Height Then Return Nothing
Dim bmdParent, bmdChild As BitmapData
Try
' Get bitmap data into array of int
bmdParent = Parent.LockBits(New Rectangle(0, 0, Parent.Width, Parent.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb)
bmdChild = Child.LockBits(New Rectangle(0, 0, Child.Width, Child.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb)
Dim ParentValuesPerLine As Integer = bmdParent.Stride \ 4
Dim ChildValuesPerLine As Integer = bmdChild.Stride \ 4
Dim ParentData((bmdParent.Stride \ 4) * bmdParent.Height - 1) As Integer
Dim ChildData((bmdChild.Stride \ 4) * bmdChild.Height - 1) As Integer
Marshal.Copy(bmdParent.Scan0, ParentData, 0, ParentData.Length)
Marshal.Copy(bmdChild.Scan0, ChildData, 0, ChildData.Length)
If bmdParent IsNot Nothing Then Parent.UnlockBits(bmdParent)
bmdParent = Nothing
If bmdChild IsNot Nothing Then Child.UnlockBits(bmdChild)
bmdChild = Nothing
' Create KMP-Table:
Dim T(Child.Height - 1)() As Integer
For i = 0 To Child.Height - 1
T(i) = KMP_Table(ChildData, i * ChildValuesPerLine, ChildValuesPerLine)
Next
Dim line_c As Integer = 0
Dim line_p As Integer = 0
Dim found As Boolean
While line_p <= Parent.Height - Child.Height
line_c = 0
Dim childoffset As Integer = line_c * ChildValuesPerLine
Dim parentoffset As Integer = line_p * ParentValuesPerLine
Dim m As Integer = -1
While True
m = KMP_Search(ParentData, parentoffset, ParentValuesPerLine, m + 1, ChildData, 0, ChildValuesPerLine, T(0))
If m > -1 Then
' first line found
Debug.Print("Possible match at {0},{1}", m, line_p)
found = True
Dim p = parentoffset + ParentValuesPerLine
Dim c = childoffset + ChildValuesPerLine
For i = 1 To Child.Height - 1
If KMP_Search(ParentData, p, ParentValuesPerLine, m, ChildData, childoffset, ChildValuesPerLine, T(i)) <> m Then
' this line doesnt match
found = False
Exit For
End If
p += ParentValuesPerLine
c += ChildValuesPerLine
Next
If found Then
Debug.Print("Found match at {0},{1}", m, line_p)
Return New Point(m, line_p)
End If
Else
Exit While
End If
End While
line_p += 1
End While
'Catch ex As Exception
'Throw
Finally
If bmdParent IsNot Nothing Then Parent.UnlockBits(bmdParent)
If bmdChild IsNot Nothing Then Child.UnlockBits(bmdChild)
End Try
End Function
Private Shared Function KMP_Search(ByVal S As Integer(), s0 As Integer, slen As Integer, m As Integer,
ByVal W As Integer(), w0 As Integer, wlen As Integer,
tbl() As Integer) As Integer
Dim i As Integer = 0
While m + i < slen
If W(w0 + i) = S(s0 + m + i) Then
If i = wlen - 1 Then Return m
i += 1
Else
m = m + i - tbl(i)
If tbl(i) > -1 Then
i = tbl(i)
Else
i = 0
End If
End If
End While
Return -1
End Function
Private Shared Function KMP_Table(ByRef arr() As Integer, start As Integer, count As Integer) As Integer()
Dim table(count - 1) As Integer
table(0) = -1
table(1) = 0
Dim pos As Integer = 2
Dim cnd As Integer = 0
While pos < count - 1
If arr(start + pos - 1) = arr(start + cnd) Then
cnd += 1
table(pos) = cnd
pos += 1
ElseIf cnd > 0 Then
cnd = table(cnd)
Else
table(pos) = 0
pos += 1
End If
End While
Return table
End Function
End Class
I used the following "benchmark" function to compare against the code from Abdias Software :
Private Sub Button1_Click_1(sender As Object, e As EventArgs) Handles Button1.Click
Dim ofd As New OpenFileDialog
If ofd.ShowDialog = Windows.Forms.DialogResult.OK Then
Dim bm As Bitmap = Bitmap.FromStream(New MemoryStream(File.ReadAllBytes(ofd.FileName)))
Dim bm2 As New Bitmap(bm.Width, bm.Height, PixelFormat.Format32bppArgb)
Dim gr = Graphics.FromImage(bm2)
gr.DrawImageUnscaled(bm, New Point(0, 0))
Dim bm3 As New Bitmap(100, 100, PixelFormat.Format32bppArgb)
gr = Graphics.FromImage(bm3)
gr.DrawImage(bm2, New Rectangle(0, 0, 100, 100), New Rectangle(bm2.Width - 110, bm2.Height - 110, 100, 100), GraphicsUnit.Pixel)
PictureBox1.Image = bm3
Dim res As New List(Of Integer)
For i = 1 To 10
Dim stp = Stopwatch.StartNew
Dim k = ImageFinder.Contains(bm2, bm3)
stp.Stop()
res.Add(stp.ElapsedMilliseconds)
Next
ListBox1.Items.Add(String.Format("KMP: Image = {3}x{4}, Min = {0}, Max = {1}, Avg = {2}", res.Min, res.Max, res.Average, bm2.Width, bm2.Height))
res.Clear()
For i = 1 To 10
Dim stp = Stopwatch.StartNew
Dim k = bm2.ContainsSO(bm3)
stp.Stop()
res.Add(stp.ElapsedMilliseconds)
Next
ListBox1.Items.Add(String.Format("SO: Image = {3}x{4}, Min = {0}, Max = {1}, Avg = {2}", res.Min, res.Max, res.Average, bm2.Width, bm2.Height))
End If
End Sub
I tested with large (8MP) and small (1MP) photos (no drawings, icons, etc) and found the kmp version roughly 2 times faster than the other approach. In absoulute numbers 40ms vs 75ms for an 8MP image tested on i7-2600. The result might depend on the types of images, because KMP (and others) win, when they can skip larger areas.
