碎紙片的拼接復(fù)原

admin

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

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

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

考慮到一張紙被切成兩部分，切邊兩側(cè)邊緣的圖像應(yīng)該是很接近的，于是就將『邊緣盡可能接近』作為匹配『吻合』的標(biāo)準(zhǔn)。
『邊緣』，那就是1個(gè)像素寬度的一條唄。
比如1#紙條的右邊1像素寬度的數(shù)據(jù)，分別去和3#紙條的左邊1像素寬度的數(shù)據(jù)、4#紙條的左邊1像素寬度的數(shù)據(jù)去試驗(yàn)
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#上每一個(gè)對(duì)應(yīng)的像素乘起來(lái)，再相加，如果是1對(duì)著的是1，那么對(duì)和有所貢獻(xiàn)，如果1對(duì)著是0，則沒(méi)有，加起來(lái)的和越大說(shuō)明吻合的程度越高。
這種對(duì)應(yīng)數(shù)相乘，再把每個(gè)乘積加起來(lái)的操作，叫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#計(jì)算可以得出=3
1#和4#計(jì)算可以得出=1
1#和3#的邊緣更接近。

那么接下來(lái)的思路就很清晰了，用1#紙條的右邊1像素寬度的數(shù)據(jù)去分別和2#、3#、4#...18#左邊1像素寬度的數(shù)據(jù)分別去試，找到dot_production最大的那個(gè)，就是『邊緣最接近』的了。
不妨把1#紙條的右邊緣1像素寬度數(shù)據(jù)寫成R1，j#紙條的左邊緣1像素寬度數(shù)據(jù)寫成Lj，
用矩陣乘法的方式寫出來(lái)就是：
[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#紙條所對(duì)應(yīng)的右邊那一條了。
一個(gè)一個(gè)的試顯然很麻煩，恰好矩陣的乘法可以很好的解決這個(gè)問(wèn)題，
把所有紙條右邊1像素寬度的數(shù)據(jù)寫作R，第i#紙條的數(shù)據(jù)就是Ri，所以R是一個(gè)每行有1980，有19列的矩陣
把所有紙條右邊1像素寬度的數(shù)據(jù)寫作L，第j#紙條的數(shù)據(jù)就是Lj，要把L矩陣豎著寫，所以要做一個(gè)transpose操作，就是豎過(guò)來(lái)。簡(jiǎn)單的可以寫成L'。
R*L'就是我們所需要知道每個(gè)『右邊』與每個(gè)『左邊』的吻合度了，一共有19*19個(gè)數(shù)字。不妨寫成U=R*L'
下圖就是這個(gè)U矩陣，顏色的深淺表示數(shù)字的大小。碎紙片的拼接復(fù)原