圖像配准問題…也就是如何用C++編程實現在一個大矩陣里尋找一個與它一個子矩陣最為相似的一個等維小矩陣？

01-07

可供參考：以下是我寫的兩個不同大小的矩陣，b是a的子矩陣，目的是在a里找出b

int a[6][6]={{1,1,2,3,0,1},{0,0,1,1,3,0},{5,0,1,2,1,0},{4,4,3,0,3,4},{1,1,2,2,4,5},{0,2,2,0,6,3}};
int b[3][3]={{1,2,1},{3,0,3},{2,2,4}};

假設A是大矩陣，B是小矩陣

sum((A[i,j] - B[i,j])2)

= sum(A[i,j]2 + B[i,j]2 - 2A[i,j]B[i,j])

= sum(A[i,j]2) + sum(B[i,j]2) - sum(2A[i,j]B[i,j])

其中第一項裡面的平方們可以先保存起來，第二項則是個不會變化的數字，包里計算第三項就可以了。

你這實際上是找平方誤差最小的矩陣。

假設大矩陣為 $n imes m$ ,小矩陣為 $a imes b$ 。

先考慮比較暴力的找的話：枚舉每一個點作為小矩陣的左端點，然後算該小矩陣與大矩陣的誤差即可。複雜度： $O(nmab)$ 。

但是這樣複雜度不優秀，期待更好的複雜度的演算法。

f=Position[#,Min@#][ListConvolve[1+0#2,#1^2,-1]+Total[#2^2,2]- 2ListConvolve[Reverse[#2,{1,2}],#1,-1]];

f[a,b] (* {{3,3}} *)

表示b的第一個元素和a的第3行第3列對齊.

f 的複雜度就是 ListConvolve 的複雜度，是 $mathrm{O}((n log n)^2)$ .

具體演算法上邊給過了，配准推薦看看使用關鍵點的方法，如sift等

你這樣的配準是最簡單的

如果加上旋轉和縮放，直接沒法用

C大學裡沒學好，也都忘記了，更別提C++了，我用Excel幫你搞了個，用的VBA，

代碼如下，水平很爛，請多包涵。

Sub Calc()


Dim widMTX1 As Integer

Dim widMTX2 As Integer

Dim widMTXdelta As Integer

Dim widMTX2InitX As Integer

Dim widMTX2InitY As Integer

Dim Container
widMTX1 = 6 "Size of Large Matrix

widMTX2 = 3 "Size of Small Matrix

widMTXdelta = widMTX1 - widMTX2

widMTX2InitX = 7

widMTX2InitY = 0
ReDim ListSTVDEV(1 To WorksheetFunction.Power(widMTXdelta + 1, 2))

ReDim ListX(1 To WorksheetFunction.Power(widMTXdelta + 1, 2))

ReDim ListY(1 To WorksheetFunction.Power(widMTXdelta + 1, 2))
Container = 0

Starter = 1
Debug.Print "Power Delta"  " Col "  " Row "
For i = 0 To widMTXdelta

    For j = 0 To widMTXdelta

        Container = 0

        For k = 1 To widMTX2 "calculation

            For l = 1 To widMTX2

                "Debug.Print Cells(k + j, l + i)  "-"  Cells(widMTX2InitY + k, widMTX2InitX + l)

               Container = Container + WorksheetFunction.Power(Cells(k + j, l + i) - Cells(widMTX2InitY + k, widMTX2InitX + l), 2)

            Next

        Next

        ListSTVDEV(Starter) = Container

        ListX(Starter) = i + 1

        ListY(Starter) = j + 1
        Debug.Print ListSTVDEV(Starter)  "-"  ListX(Starter)  "-"  ListY(Starter)

        Starter = Starter + 1

    Next

Next