在圖像中查找圖像

Question

我在尋找檢測另一圖像內圖像的最佳方法。我有一個小圖像，並希望找到它出現在較大圖像中的位置 - 這實際上是屏幕截圖。從概念上講，它就像是一個'沃爾多在哪裏'？在較大的圖像中進行搜索。

是否有任何有效/快速的方法來實現這一目標？速度比記憶更重要。

編輯：

「內在」的形象並不總是具有相同的規模，但將具有相同的旋轉。

假設圖像完全包含在另一個像素中是不安全的。

Answer 1

維基百科上有一篇關於Template Matching的文章，附帶示例代碼。

（雖然該網頁不處理變化的尺度，它連接到其他的風格匹配，例如Scale invariant feature transform）

Answer 2

您可以將此視爲子字符串問題，其中字母表中的字符是像素，而您的字符串是圖像。您還需要使用與換行符類似的特殊字符來表示圖像邊界。

你想要的算法是維基百科：http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm

更新：如果你不能假設圖像是完全包含在其他，像素爲像素內，那麼這種做法是行不通的。

還有其他更復雜的算法基於與上述相同的動態編程概念，但除非有必要，否則我不會涉及它們。

Answer 3

如果旋轉也必須照顧的Generalised Hough Transform可以使用。