我已经玩了一点，并认为使用类似 KMP 算法的东西（我猜这是一个容易实现的算法 -> wikipedia 有一个很好的伪代码）也可能会有所帮助：
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
我使用以下“基准”函数与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
我用大 (8MP) 和小 (1MP) 照片（没有图纸、图标等）进行了测试，发现 kmp 版本比其他方法快大约 2 倍。在 i7-2600 上测试的 8MP 图像的绝对数字为 40 毫秒与 75 毫秒。结果可能取决于图像的类型，因为 KMP（和其他）赢了，当他们可以跳过更大的区域时。
