私は少し遊んだことがあり、KMPアルゴリズム（実装は簡単だと思います->ウィキペディアには素晴らしい擬似コードがあります）のようなものを使用することも役立つかもしれないと思いました：
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
次の「ベンチマーク」関数を使用して、AbdiasSoftwareのコードと比較しました。
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
大きい（8MP）と小さい（1MP）の写真（図面やアイコンなどなし）でテストしたところ、kmpバージョンは他のアプローチよりも約2倍高速であることがわかりました。絶対数では、i7-2600でテストされた8MPイメージの75msに対して40msです。KMP（およびその他）がより大きな領域をスキップできる場合に勝つため、結果は画像のタイプによって異なる場合があります。
