查找兩個圖像之間的不同區域

Question

我的目的是比較兩個圖像之間的像素，並找出最小（優化的）包含圖像之間所有不同像素的矩形區域。 簡單地說，我比較了兩幅圖像的所有像素（例如1024 * 768像素），發現了不同的部分，但由於速度而不是好主意。 我需要做這個比較每秒至少十五次。 你知道更有效的算法嗎？

Answer 1

如果你的像素值存儲在二維數組中（比如灰度值爲0-255），你可以做的就是像矩陣一樣處理數組，然後減去兩個數組。結果中的條目是零是相同的像素，非零表示它們是不同的。然後，您會發現包含非零條目的頂部行作爲您的y-MAX，您的y-MIN包含非零的最低行，x-MIN包含非零的第一列和非零的最後一列爲x-MAX。然後該矩形具有4個座標：

• （X-MIN，Y-MIN）--lower左角
• （X-MAX，Y-MIN）--lower右上角
• （X- MAX，Y-MAX）--top右上角
• （X-MIN，Y-MAX）--top左側開出角球

如果你碰巧知道所有的條目都至少爲零（可能是通過獲取絕對值來完成，但這會增加成本），那麼你可以通過右邊所有1的列向量乘以矩陣。這會給你一個行數。然後，您會找到第一個和最後一個非零的行數（自上而下搜索，自下而上）。如果你在左邊乘以全1的行向量，你會得到相同的結果，但是列總和。再次尋找那些非零的。

矩陣運算很好，因爲有優化的庫可以幫助加速計算（並且矩陣並不那麼大）......特別是如果您有可用於執行計算的GPU。但即使在串行中，小矩陣向量計算也不是那麼耗時。

Answer 2

從另一個圖像中減去一個圖像。相同的像素將變爲零，即黑色。

找到一個黑色的角落，並使用trim（修剪邊框/邊緣）類型的命令來修剪黑色邊框，這將告訴您區別的區域。

這是很簡單的ImageMagick的兩行做，如果你可以使用 - 它可對C/C多的平臺++，Python和Perl中......

讓我們兩個圖像，a.jpg和b.jpg：

你看到我做了什麼呢？ :-)

現在我們可以使用ImageMagick來查找差異和不同的區域。我正在使用命令行，但正如我所說的，您可以使用C/C++，Perl，Python，.NET或其他任何可以漂浮您的船的設備。

要麼用它來尋找差異：

convert a.jpg b.jpg \ 
     -compose difference \ 
     -composite \ 
     -threshold 0 \ 
     -separate \ 
     -evaluate-sequence Add \ 
     diff.jpg 

其中給出了這樣的：

或者使用：

composite a.jpg b.jpg -compose difference diff.jpg 

其中給出了這樣的：

或者用這個簡單的減法：

convert a.jpg b.jpg -compose minus -composite diff.jpg 

現在你可以使用ImageMagick的邊框裝飾功能來評價，如果你修剪所有的黑色邊框過什麼會留下，像這樣：

convert a.jpg b.jpg \ 
     -compose difference \ 
     -composite \ 
     -threshold 0 \ 
     -separate \ 
     -evaluate-sequence Add \ 
     -format "%w %h %@" \ 
     info: 

它輸出這個：

400 463 264x240+80+176 

告訴你圖像是400x463，如果你裁剪了邊框，你將剩下一個矩形264x240，其左上像素偏移80,176從圖像的左上角。

只是爲了好玩，我會繪製矩形到圖像中的紅色，用這個命令：

convert diff.jpg \ 
     -stroke red \ 
     -fill transparent \ 
     -draw "rectangle 80,176 344,416" \ 
     rect.jpg 

其中給出了這樣的：

從本質上講，你可以做我的全部在這裏用一行或兩行shell解釋，或者8-10行C/C++。請注意，邊界框稍大，因爲我疊加的漫畫具有透明的矩形背景。如果您需要在差分中允許一定程度的「粗糙」，您還可以使用-fuzz 5%來允許圖像中的細微差異。

檢測的邊界框的另一方式是squidge的差分圖像，直到它是一個高大的圖像，只有一個像素寬，這樣的：

convert diff.jpg -scale 1x! -threshold 1% t.jpg 

得到的圖像如下：

現在，如果將輸出轉換爲文本格式，您可以很容易地找到第一個白色像素（在程序中，您不會這樣做 - 您會寫一個循環代替 - 但我是示出的概念在這裏）：

convert diff.jpg -scale 1x! -threshold 1% txt: | grep -m1 white 

0,176: (255,255,255) #FFFFFF white 

的grep -m1 white查找具有在它white第一行，然後停止尋找（匹配被限制爲1）。這表明白色像素的第一行是176 - 與上面的紅色框相比。現在我們可以找到最後一個白色像素，使用：

convert diff.jpg -scale 1x! -threshold 1% txt: | grep white | tail -1 

0,415: (255,255,255) #FFFFFF white 

並且我們知道行415是邊界框的底部。

現在你squidge圖像的寬而扁的版本僅有1個像素高，並找到自己的邊框的左，右極限：

convert diff.jpg -scale x1! -threshold 1% txt: | grep -m1 white 

80,0: (255,255,255) #FFFFFF white 

convert diff.jpg -scale x1! -threshold 1% txt: | grep white | tail -1 

343,0: (255,255,255) #FFFFFF white 

所以您邊框的左右極限是80和343 - 根據紅色矩形。