10025. Fast Image Match (OpenMP)

I'm a slow walker, but I never walk backwards.

背景

圖片匹配和字串匹配有一點不同,字串匹配通常要求其子字串與搜尋字串完全相符,而圖片匹配則用相似度為依據,當圖片大、複雜且具有干擾,或者需要匹配數量非常多,更先進的領域會利用特徵擷取,用機率統計的方式來篩選可能的匹配數量,篩選過後才進行圖片的細節匹配。

題目描述

給予兩個圖片 $A, B$,圖片格式為灰階影像,每個像素 $\mathit{pixel}(x, y)$ 採用 8-bits 表示,範圍為 $\mathit{pixel}(x, y) \in \lbrack 0, 255]$。

舉一個例子,有一個 $3 \times 3$ 的圖片 $A$ 和一個 $2 \times 2$ 的圖片 $B$,用矩陣表示如下:

$$ A := \begin{bmatrix} a1 & a2 & a3 \\ a4 & a5 & a6 \\ a7 & a8 & a9 \end{bmatrix} ,\; B := \begin{bmatrix} b1 & b2\\ b3 & b4\\ \end{bmatrix}$$

假設左上角座標 $(1, 1)$ 即 $a1$ 的位置、$(1, 2)$ 即 $a2$ 的位置。

  • 若把影像 $B$ 左上角對齊 $A$ 的 $(1, 1)$ 位置,其差異程度 $\mathit{diff}(A, B) = (a1 - b1)^2 + (a2 - b2)^2 + (a4 - b3)^2 + (a5 - b4)^2$
  • 相同地,對齊 $(2, 1)$ 位置,其差異程度 $\mathit{diff}(A, B) = (a4 - b1)^2 + (a5 - b2)^2 + (a7 - b3)^2 + (a8 - b4)^2$

比較時,整張 $B$ 都要落在 $A$ 中。現在要找到一個對齊位置 $(x, y)$,使得 $\mathit{diff}(A, B)$ 最小。

輸入格式

多組測資,每一組第一行有四個整數 $A_H, A_W, B_H, B_W$,分別表示圖片 $A$ 的高寬、$B$ 的高寬。

接下來會有 $A_H$ 行,每一行上會有 $A_W$ 個整數,第 $i$ 行上的第 $j$ 個整數 $x$ 表示 $A(i, j)$ 的灰階像素值。同樣地,接下來會有 $B_H$ 行,每一行上會有 $B_W$ 個整數,第 $i$ 行上的第 $j$ 個整數 $x$ 表示 $B(i, j)$ 的灰階像素值。

  • $ 1\le A_H, A_W, B_H, B_W \le 500$
  • $ B_H \le A_H, B_W \le A_W$
  • $ 0 \le x \le 255$

輸出格式

對於每一組測資輸出一行,兩個整數 $x, y$,滿足 $\mathit{diff}(A, B)$ 最小。若有相同情況滿足,則優先挑選 $x$ 最小,若 $x$ 仍相同,則挑選 $y$ 最小。

範例輸入

4 4 2 2
0 3 3 0
0 3 3 0
0 0 5 5
0 0 5 5
5 5
5 5
3 5 1 2
2 3 0 4 5
0 0 7 0 0
0 0 7 0 0
3 4

範例輸出

3 3
1 1

Discussion