確定相似性變換的幾何構造編程

Question

作爲圖像中所示我有「shape1」和「shape2」分開。兩者都有相同的點A，B，C和D.只要看看這些，形狀就不同了。但如果你轉換（旋轉&翻譯）「shape2」，你會得到「shape1」。換句話說，我們可以說「shape2」匹配「shape1」。

我的問題是，給定2個圖像具有相同的點，但座標不同，如何識別「shape2」是否與編程方式匹配「shape1」（或不）？

PS： 「形狀1」和「形狀2」都具有相同的點A，B，C & D，但具有不同的座標。 可能的轉換是旋轉，翻譯或/和鏡像。不適用縮放。

我已經看到有方法來創建具有給定形狀和給定​​集合的轉換形狀。但這恰恰相反。

Answer 1

你沒有顯示任何代碼，所以我也不應該只討論算法。

兩個多邊形之間的相似度的一個定義是對應的角度相等並且相應的邊正比於。因此，從兩個相應的點開始，每個多邊形上一個點。對於每個多邊形，記錄從第一個點到下一個點的線段長度的比例。然後繼續在每個多邊形周圍。比較連續段之間的方向角 - 如果任何不相等（或者在浮點算術中足夠接近），則不存在相似性。還要比較相應段長​​度的比率 - 如果這些比率中的任何一個與第一個不相等/不夠接近，則沒有相似性。如果您回到第一條線段，並且所有內容都已檢查完畢，則多邊形是相似的。

請注意，我假設你知道相應的點和方向是什麼。如果不是這種情況，可以重複上一段中的步驟，對其中一個多邊形上的每個點重複兩次（每次定向一次）。

這就是檢查的相似性，就像在你的標題中一樣。如果你真的想檢查一致，其中「不適用縮放」，如你在問題的主體中所陳述的那樣，線段長度的公共比率必須是1，並且算法更容易一些。

算法是否清晰？您必須能夠找到線段的長度和給定座標的兩條線段之間的方位角，但在開始這種問題之前，您應該知道這種情況。

Answer 2

測量每個點與至少3個其他點之間的距離。對於4分，這意味着衡量所有6個可能的連接。

|A-B|, |A-C|, |A-D|, |B-C|, |B-D|, |C-D| 

如果我沒有弄錯，兩個四邊形匹配，如果所有這6個長度匹配。這是使用你的匹配定義（只有平移，旋轉和鏡像轉換）。

對於N個點，您需要ceil（N * 1.5）連接/測量。例如5分需要8個連接，6分需要9個連接。

要進行優化，因爲您只是比較，您可以計算平方距離並避免許多平方根。

Answer 3

一種方法是計算將一個形狀（下面的P []，其中有N個）的點與另一個形狀（Q []）的點最接近的變換。這被稱爲（正交）Procrustes問題。如果得到的分數「足夠接近」 - 由於浮點運算的精度有限，您可能無法獲得完美的匹配 - 可以說您有匹配。

這裏的演練：的普的

計算平均值，減去從P的，得到了​​普的發言權。同樣，從Q中減去（Q的）平均值。

計算所述p的和q的的 '協方差' 矩陣C，即：

C = Sum{ i | p[i]*q[i]' }/N 

計算C的SVD，即找到正交U，V和對角線S左右即

C = U*S*V' 

變換最能普的映射到Q的是那麼的（正交）地圖

R = V*U' 

和翻譯vecto [R

T = Qbar - R*Pbar 

其中Q吧是的Q的均值，中PBAR在P的

不過，如果你只是想知道是否有轉變，使點匹配，那麼你就不需要計算R和T，所有你需要計算的是殘差，即

E = Sum{ i | |Q[i] - P~[i]|^2 }/N 

其中P〜s是通過上面的變換轉換的Ps，而| x |是向量x的（歐幾里德）範數。

您可以通過

E = Sum{ i | |q[i]|^2 + |p[i]|^2}/N - 2*Tr(S) 

其中tr是跟蹤，即對角線元素之和計算ê。