基於fft的碎紙片縱切拼接復原算法
2023-12-01 15:34:31
基於fft的碎紙片縱切拼接復原算法
【專利摘要】本發明公開了一種基於FFT的碎紙片縱切拼接復原算法,通過對圖像碎片進行編碼,將其轉化為灰度矩陣,進行二值化處理,之後對碎片的左右邊緣進行FFT處理,進行頻域分析。然後確定原圖的左右邊沿碎片,利用FFT處理後各邊緣列的歸一化互相關係數對各個圖像的左右邊進行識別,匹配出相鄰的圖片,逐步重複上述過程,完整地復原所有碎片。利用該算法,復原正確率高,復原速度也與直接匹配法相當,是一種高效的算法。
【專利說明】基於FFT的碎紙片縱切拼接復原算法【技術領域】[0001]本發明主要運用於圖像拼接(文字拼接)領域,設計了一種基於FFT的碎紙片縱切 拼接復原算法。【背景技術】[0002]快速傅立葉變換,是離散傅氏變換的快速算法,它是根據離散傅氏變換的奇、偶、 虛、實等特性,對離散傅立葉變換的算法進行改進獲得的。它對傅氏變換的理論並沒有新的 發現,但是對於在計算機系統或者說數字系統中應用離散傅立葉變換,可以說是進了一大止 /J/ O[0003]快速傅氏變換算法可以運用到圖像拼接的領域。
【發明內容】
[0004]將原理圖編碼,編碼後使之轉化為矩陣。其中,為了減少算法的計算量和時間複雜 度,編碼採用的編碼方式為,將所有白色的像素設定為0,其他均為I。編碼後之後,得到矩 陣,便於後續處理。[0005]將編碼後的數據進行識別然後進行FFT處理,對各個碎片進行頻域變化,進行頻 譜分析。求其矩陣邊緣相互之間的自相關性,將自相關性最大的兩張碎片進行拼接。【專利附圖】
【附圖說明】[0006]圖1為算法流程圖。具體實施方案[0007]為了探尋兩個相鄰碎片間的關係,本算法將各個碎片編碼後矩陣的邊緣列進行 FFT快速傅立葉變換,因為最終圖片的最左邊全為白色,所以首先可以得到原圖最左邊一 列,再將該碎片的最右列和其他碎片的最左列逐一進行互相關係數的計算,得出一族互相 關係數,選取其中結果最大的一列的碎片進行匹配,得到最終結果。[0008]傅立葉原理表明:任何連續測量的時序或信號,都可以表示為不同頻率的正弦波 信號的無限疊加。而根據該原理創立的傅立葉變換算法利用直接測量到的原始信號,以累 加方式來計算該信號中不同正弦波信號的頻率、振幅和相位。[0009]對於信號的分析,很多情況下僅依靠時域是遠遠不夠的,很多時域上不好分析的 信號轉入頻域的分析中,立即變得便於分析。本算法依據分析的需要,分別將每個灰度矩陣 的左上角和右上角看作起點,將0-1 二值矩陣一列的取值看作I軸,將離散的點看作t軸, 對其進行FFT處理。得到每個矩陣的邊緣列的頻譜。對它的特徵進行提取,並分別計算它 與其它碎紙片邊緣的互相關係數,進行匹配。筆者認為,頻譜特徵接近,即互相關係數接近 的兩個碎紙片處在相鄰的位置。[0010]該算法的流程圖如圖1所示:圖片編碼矩陣的FFT處理:①FFT快速傅立葉變換與DFT離散傅立葉變換算法的比較:對於任一離散序列X(K)的I點,其DFT計算公式如下所示:
【權利要求】
1.一種基於FFT的碎紙片縱切拼接復原算法,其特徵在於,它包括以下步驟,(1)圖片編碼本算法首先對圖片進行預處理,用MATLAB導入文件並編碼後使之轉化為矩陣;其中, 為了減少算法的計算量和時間複雜度,編碼採用的編碼方式為,將RGB的閾值設為128,對灰度矩陣進行反向處理,小於128的變為1,大於128的變為O ;編碼之後,得到矩陣,便於後續處理;(2)對每張圖片的左右邊進行識別,為了探尋兩個相鄰碎片間的關係,本算法將的各個碎片編碼後矩陣的邊緣列進行FFT 快速傅立葉變換處理,因為圖片由文字組成其的最左邊全為白色,所以首先可以人工得到原圖最左邊一列,再將該碎片的最右列和其他碎片的最左列逐一進行互相關係數的計算, 得出一族互相關係數;本算法採用了基於信號處理從歸一化互相關係數模型去對兩個信號的相關係數進行定量的衡量;不妨設兩個樣本分別為離散信號X (n)、y (η),長度為N同時將其看作兩組同維的向量;定義X (n)、y (η)的互相關係數如下式所示,
【文檔編號】G06T5/50GK103559697SQ201310458539
【公開日】2014年2月5日 申請日期:2013年10月3日 優先權日:2013年10月3日
【發明者】王浩, 曹丹, 鄭智隆, 孫翰斐, 顧也琛, 於思奇, 李子祺, 張旭, 餘冬琪 申請人:王浩