融入fft的綜合評價法的碎紙片縱橫切拼接復原算法
2023-10-28 04:48:42
融入fft的綜合評價法的碎紙片縱橫切拼接復原算法
【專利摘要】本發明公開了一種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。首先通過對圖像碎片進行編碼，將其轉化為灰度矩陣並對其進行二值化處理。利用FFT快速傅立葉變化，進行頻域轉化，進行頻域分析。之後分成兩種情況，對於中文，行的劃分依據是漢字的中心縱坐標；對於英文，行的劃分依據是字母的下端基線。然後，利用行匹配將所有的碎片行分類。利用FFT處理後邊緣矩陣的互相關係數大小和直接匹配法的匹配成功率進行綜合評價，用每個碎片的左右兩個邊分別與左右邊緣的兩邊進行匹配，選取其中匹配度最高的完成匹配，重複直至完成行匹配。對其結果進行人工幹預。之後進行間排序，此處依舊利用上述的綜合評價法實現，之後對結果再進行一次人工檢查與幹預，完成碎片的復原。
【專利說明】融入FFT的綜合評價法的碎紙片縱橫切拼接復原算法
【技術領域】
[0001]本發明主要運用於中英文圖像拼接(文字拼接)領域，設計了一種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
【背景技術】
[0002]快速傅立葉變換，是離散傅氏變換的快速算法，它是根據離散傅氏變換的奇、偶、虛、實等特性，對離散傅立葉變換的算法進行改進獲得的。它對傅氏變換的理論並沒有新的
發現，但是對於在計算機系統或者說數字系統中應用離散傅立葉變換，可以說是進了一大步。快速傅氏變換算法可以運用到圖像拼接的領域。
【發明內容】
[0003]單面印刷文字文件橫縱切碎片的復原
為了探尋兩個相鄰碎片間的關係，本算法將各個碎片編碼後矩陣的邊緣列進行FFT快速傅立葉變換，因為最終圖片的最左邊全為白色，所以首先可以得到原圖最左邊一列，再將該碎片的最右列和其他碎片的最左列逐一進行互相關係數的計算，得出一族互相關係數，選取其中結果最大的一列的碎片進行匹配，得到最終結果。
[0004]傅立葉原理表明:任何連續測量的時序或信號，都可以表示為不同頻率的正弦波信號的無限疊加。而根據該原理創立的傅立葉變換算法利用直接測量到的原始信號，以累加方式來計算該信號中不同正弦波信號的頻率、振幅和相位。
[0005]對於信號的分析，很多情況下僅依靠時域是遠遠不夠的，很多時域上不好分析的信號轉入頻域的分析中，立即變得便於分析。本算法依據分析的需要，分別將每個灰度矩陣的左上角和右上角看作起點，將0-1 二值矩陣一列的取值看作y軸，將離散的點看作t軸，對其進行FFT處理。得到每個矩陣的邊緣列的頻譜。對它的特徵進行提取，並分別計算它與其它碎紙片邊緣的互相關係數，進行匹配。筆者認為，頻譜特徵接近，即互相關係數接近的兩個碎紙片處在相鄰的位置。
[0006]單面印刷文字橫縱切片的復原難度比僅有縱向切片文件的復原大很多，一方面在於碎紙片變多使得編程變得困難和程序運行速度變慢，另一方面在於紙片變小導致的信息變少從而使得匹配更易於發生錯誤。本算法闡述了研究過程中方案的探索和最終使用的方案的改進。本算法分別對中文和英文的處理方法進行了分析。
[0007]本算法對於這種方案進行了分步處理。最後進行了一次人工幹預，得到正確的結果。
[0008]本算法在此對中英文兩種情況進行分別討論，不同特徵。
[0009]一、中文文件的復原
本算法對於中文文件的復原主要經過行分類、綜合評價體系的建立以及人工幹預組成。其算法流程圖如圖1所示:
(1)行分類①分類方案的選取
首先，筆者經過觀察發現，不是所有的標點都是全形的，所以不同行上面的字位置並不處在完全一樣的列上。所以對於碎片的處理不能通過列分類而實現。之後，筆者經過觀察發現，除去空行後，所有的碎片只有11種行的分布位置，所以可以先對它們進行行分類，之後再對於每一行類別的碎片進行相對位置的排序，即可恢復原文。
[0010]觀察事例圖片，本算法發現文字的漢字大小几乎一致，對所有碎片中漢字的縱向高度進行統計，本算法發現漢字的縱向高度為38-41個像素，但是漢字的上下卻往往並不對齊，所以本算法對於所有漢字縱向的中心點縱坐標進行了記錄，根據這些縱坐標的位置，並設定一個像素的閾值，對所有碎紙片進行行分類。
[0011]觀察到事例圖片中的行間距一致，而且大多數正規文件的行間距幾乎一樣寬，所以本算法首先假定圖片中漢字的行間距一致，但是英文的行間距卻並不完全一致，因此，本算法改變思路，轉而去分析漢字高度。
[0012]因為每個漢字的高度有一定的出入，而且漢字的底也不太相同，再加上部分形如「一」的文字存在，所以本算法的分析思路基於漢字的中心點。為了證明這種想法的合理性，本算法對所有漢字縱向坐標進行分析，發現同一行的漢字中心縱坐標處在閾值為1的區間內，所以用這種方法對漢字進行行分類可以得到較好的結果。
[0013]②灰度矩陣的預處理
每個漢字的大小不完全一樣，一方面為了便於觀察，另一方面為了減少部分形如「翁」之類的漢字中間空白部分的幹擾。本算法首先對灰度矩陣進行預處理。因為本體首先，將灰度矩陣以RGB值128作為閾值，轉化為0-1 二值矩陣。
[0014]之後，對生成的矩陣進行掃描，從上到下並且橫向進行，一旦在某一行中遇到有一個像素為黑色，便將整行變成黑色，直到結束為止。為了防止形如「翁」的字幹擾後續檢驗。此時，再對矩陣進行檢驗，將寬度小於20像素的白線全部變成黑色。
[0015]因為圖片中的文本碎片均不含有噪音，所以噪音中黑點與白點的影響可以忽略不計。
[0016]為了顯示上述方法的處理效果，本算法選取一張原圖與一張處理後的圖片進行對t匕，為了使這種事例具有普遍性，本算法選取兩個典型圖進行師範，如圖2、圖3所示，其處理結果分別如圖4，圖5所示。
[0017]經過對上述效果的觀察，本預處理的效果十分明顯，結果也很成功。
[0018]③行分類的實施與結果
本算法先確定兩個邊緣列的碎片項。之後，本算法對於預處理後的矩陣進行分析，統計出所有黑色部分的中心縱坐標大小，對其進行記錄，並設定閾值為1，對其進行分類。
[0019]對於結果分析可得，該分類與其差別較小，可以對其進行人工幹預，將每行之間的先後順序進行排列，本部分的任務完成。
[0020](2)基於FFT信號處理的互相關係數模型
一種普遍的方法為:利用(1)中的圖片編碼方式，得出二值矩陣，首先利用碎片左側的邊緣找出最左邊的一個碎片，之後將灰度矩陣它最右邊一列分別與其他碎片最左邊一列進行分別邏輯異或運算，並將所有結果進行求和，選取結果最大的一個碎片與其相連，但是這種方法的匹配成功率較低，所以本文採取了其他的方法。[0021]為了探尋兩個相鄰碎片間的關係，本算法將各個碎片編碼後矩陣的邊緣列進行FFT快速傅立葉變換，因為最終圖片的最左邊全為白色，所以首先可以得到原圖最左邊一列，再將該碎片的最右列和其他碎片的最左列逐一進行互相關係數的計算，得出一族互相關係數，選取其中結果最大的一列的碎片進行匹配，得到最終結果。
[0022]傅立葉原理表明:任何連續測量的時序或信號，都可以表示為不同頻率的正弦波信號的無限疊加。而根據該原理創立的傅立葉變換算法利用直接測量到的原始信號，以累加方式來計算該信號中不同正弦波信號的頻率、振幅和相位。
[0023]對於信號的分析，很多情況下僅依靠時域是遠遠不夠的，很多時域上不好分析的信號轉入頻域的分析中，立即變得便於分析。本算法依據分析的需要，分別將每個灰度矩陣的左上角和右上角看作起點，將0-1 二值矩陣一列的取值看作y軸，將離散的點看作t軸，對其進行FFT處理。得到每個矩陣的邊緣列的頻譜。對它的特徵進行提取，並分別計算它與其它碎紙片邊緣的互相關係數，進行匹配。筆者認為，頻譜特徵接近，即互相關係數接近的兩個碎紙片處在相鄰的位置。
[0024](1)圖片編碼矩陣的FFT處理:
①FFT快速傅立葉變換與DFT離散傅立葉變換算法的比較:
對於任一離散序列χ(--)的父點，其DFT計算公式如下所示:
【權利要求】
1.一種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
2.其特徵在於能夠進行中英文單面橫縱切片的恢復。
3.如權利要求1一種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
4.其特徵在於它可以進行中文和英文文件的復原。
5.如權利要求2—種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
6.其特徵在於，本算法對於中英文文件的復原主要經過行分類、綜合評價匹配法、行排序和人工幹預組成。
7.中文的行分類依靠行中心線，英文依靠行基線。
8.如權利要求2—種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
9.其特徵在於，每個漢字的大小不完全一樣，一方面為了便於觀察，另一方面為了減少部分形如「翁」之類的漢字中間空白部分的幹擾。
10.本算法首先對灰度矩陣進行預處理。
11.如權利要求2—種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
12.其特徵在於，本算法將各個碎片編碼後矩陣的邊緣列進行FFT快速傅立葉變換，因為最終圖片的最左邊全為白色，所以首先可以得到原圖最左邊一列，再將該碎片的最右列和其他碎片的最左列逐一進行互相關係數和綜合評價值的計算，得出一族互相關係數，選取其中結果最大的一列的碎片進行匹配，得到最終結果。
13.如權利要求2—種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
14.其特徵在於，本發明認為兩個相鄰的矩陣如果綜合評價值越高，則兩圖片的匹配度越好，選取匹配度最高的圖片進行匹配。
15.因為互協方差函數不能進行歸一化處理，從而用量化的指標來清楚地反映出兩個信號的相關係數，所以本算法採用了基於信號處理從歸一化互相關係數模型去對兩個信號的相關係數進行定量的衡量。
16.行匹配與列排序的方法一致，均靠綜合評價值去進行匹配。
17.如權利要求2—種融入FFT的綜合評價的碎紙片縱橫切拼接復原算法。
18.其特徵在於，英文文件的行分類要更難。
19.一方面每個英文字母的縱向高度不同，而且有的整體位置較高，有的整體位置較低，所以難以定位其每一行的位置，對字母進行篩選；另一方面，因為英文字母很多都有弧度，而且信息較少，所以英文文件經過縱橫切片後更加難以復原。
20.其算法流程圖如圖6所示。
21.本算法中文文件和英文文件的區別主要在於數據的預處理和行分類上面。
【文檔編號】G06T3/40GK103679671SQ201310458541
【公開日】2014年3月26日 申請日期:2014年1月12日 優先權日:2014年1月12日
【發明者】王浩, 鄭智隆, 曹丹, 鄒孟霖, 於思奇, 孫翰斐, 李子祺, 張旭, 餘冬琪 申請人:王浩