碎紙片的拼接復原

admin

       碎紙片的拼接復原
       由于對任意一個字符來講，筆畫是連續(xù)的，所以對于一般情況，即使文字被切開，兩邊的像素還是有聯(lián)系的，是呈現(xiàn)離散性漸變的。針對此特征，建立了文字連續(xù)性模型來求解該問題。而又因為被切開的兩邊碎片邊緣灰度是具有高相關性的，所以，又建立了向量相關模型來求解進行圖片拼接。用兩種模型分別求解，都得到了對附件一和附件二的正確拼接結果。

       由于附件中的碎片分為正反兩面，所以可以建立組合匹配模型將碎片首先將正反面碎片的灰度矩陣上下拼接，每張碎片的拼接方案有兩種（灰度矩陣a放在左右鏡像處理后的b上或灰度矩陣b放在左右鏡像處理后的a上）。拼接過后，邊緣灰度向量信息會增加為原來的兩倍，這時利用問題二中的全局搜索模型用向量相關性的方法進行匹配拼接。拼接出所有行后，將每一行的下半部分矩陣切割放在上半部分的右邊，又可增加橫向拼接時的邊緣信息，然后各行再次利用向量相關性的方法進行橫向拼接，最終得到結果圖，但是仍然存在較多的碎片不能正確匹配，需要人工干預。

碎紙片的拼接復原 基本思路
此題的關鍵是要給出一張紙條和另一張紙條怎么才算是『吻合』，定量的吻合條件是什么？

考慮到一張紙被切成兩部分，切邊兩側邊緣的圖像應該是很接近的，于是就將『邊緣盡可能接近』作為匹配『吻合』的標準。
『邊緣』，那就是1個像素寬度的一條唄。
比如1#紙條的右邊1像素寬度的數(shù)據(jù)，分別去和3#紙條的左邊1像素寬度的數(shù)據(jù)、4#紙條的左邊1像素寬度的數(shù)據(jù)去試驗
1#：0 0 0 1 1 1 1 0 0
3#：0 0 0 1 1 0 1 0 0
4#：0 1 0 1 0 0 0 0 0
顯然是1#和3#之間更接近一些。如何定量呢？
將1#與3#上每一個對應的像素乘起來，再相加，如果是1對著的是1，那么對和有所貢獻，如果1對著是0，則沒有，加起來的和越大說明吻合的程度越高。
這種對應數(shù)相乘，再把每個乘積加起來的操作，叫dot production
比如(x1,x2,x3)和(y1,y2,y3)的dot production=x1y1+x2y2+x3y3
如果寫成矩陣的乘法，x要橫著寫，y要豎著寫：
\left[ \begin{matrix} { x }_{ 1 } & { x }_{ 2 } & { x }_{ 3 } \end{matrix} \right] \quad \left[ \begin{matrix} { y }_{ 1 } \\ { y }_{ 2 } \\ { y }_{ 3 } \end{matrix} \right] ={ x }_{ 1 }{ y }_{ 1 }+{ x }_{ 2 }{ y }_{ 2 }+{ x }_{ 3 }{ y }_{ 3 }

1#和3#計算可以得出=3
1#和4#計算可以得出=1
1#和3#的邊緣更接近。

那么接下來的思路就很清晰了，用1#紙條的右邊1像素寬度的數(shù)據(jù)去分別和2#、3#、4#...18#左邊1像素寬度的數(shù)據(jù)分別去試，找到dot_production最大的那個，就是『邊緣最接近』的了。
不妨把1#紙條的右邊緣1像素寬度數(shù)據(jù)寫成R1，j#紙條的左邊緣1像素寬度數(shù)據(jù)寫成Lj，
用矩陣乘法的方式寫出來就是：
[R1（橫著寫）][L1（豎著寫）,L2（豎著寫）,L3（豎著寫）...L18（豎著寫）] =[u(1,1),u(1,2),u(1,3),..u(1,18)]

找到[u(1,1),u(1,2),...u(1,18)]里面最大的值，就是1#紙條所對應的右邊那一條了。
一個一個的試顯然很麻煩，恰好矩陣的乘法可以很好的解決這個問題，
把所有紙條右邊1像素寬度的數(shù)據(jù)寫作R，第i#紙條的數(shù)據(jù)就是Ri，所以R是一個每行有1980，有19列的矩陣
把所有紙條右邊1像素寬度的數(shù)據(jù)寫作L，第j#紙條的數(shù)據(jù)就是Lj，要把L矩陣豎著寫，所以要做一個transpose操作，就是豎過來。簡單的可以寫成L'。
R*L'就是我們所需要知道每個『右邊』與每個『左邊』的吻合度了，一共有19*19個數(shù)字。不妨寫成U=R*L'
下圖就是這個U矩陣，顏色的深淺表示數(shù)字的大小。碎紙片的拼接復原