童立靖　鄭俊朝

(北方工業(yè)大學計算機學院　北京 100144)

?

基于點云數(shù)據(jù)的扭曲文本圖像傾斜校正方法

童立靖鄭俊朝*

(北方工業(yè)大學計算機學院北京 100144)

摘要針對傳統(tǒng)二維層面的傾斜校正算法難以處理扭曲文本的傾斜，提出一種基于點云數(shù)據(jù)的扭曲文本圖像傾斜校正方法。首先，通過三維掃描儀采集文本的數(shù)據(jù)信息，重建文本的三維點云模型，接著通過檢測文本在空間中的位置，定義為空間傾斜與平面傾斜，最后實現(xiàn)文本的自動傾斜校正。實驗結果表明，基于點云數(shù)據(jù)的傾斜校正算法在處理扭曲文本的傾斜校正正確率達到95%以上。

關鍵詞點云數(shù)據(jù)扭曲文本傾斜檢測空間傾斜平面傾斜傾斜校正

0引言

隨著信息技術快速發(fā)展，信息化成為人們提高辦公效率、生活品質(zhì)的重要途徑。電子文檔具有保存方便，并易于在互聯(lián)網(wǎng)中傳輸?shù)忍攸c，因此將紙質(zhì)文檔轉換為電子文檔的技術越來越重要。目前通過電子設備來進行這種轉換的方法主要是通過攝像頭獲取文本資料數(shù)字圖像，經(jīng)過一系列的圖像預處理、OCR(光學字符識別)等將其轉化為電子文檔。而在這種轉換過程中，文本的傾斜會對整個轉化過程產(chǎn)生不利的影響，因此圖像的傾斜校正在圖像的預處理中始終占據(jù)一個非常重要的地位。實際采集文本數(shù)字圖像時，若整個文本處于一個斜面上時或者拍攝角度不對而出現(xiàn)射影文本情況，導致采集的文本圖像出現(xiàn)像素的堆積，影響OCR識別率。同樣若文本為具有一定厚度的書籍時，采集文本數(shù)字圖像時會由于書籍的厚度出現(xiàn)文本扭曲，無法直接進行傾斜校正處理。

傳統(tǒng)的二維文本圖像傾斜校正算法主要分為以下幾類：基于Hough變換的方法、基于投影的方法、基于K-最近鄰方法以及基于Fourier變換方法。文獻[1,2]中基于Hough變換的方法使用圖像空間目標像素的坐標去計算參數(shù)空間中參考點的可能軌跡，是目前用得較多的一種傾斜角檢測方法，但對扭曲文本圖像因無法準確提取文本線而出現(xiàn)難以處理的情況。文獻[3]以文字行之間存在一固定的行間距為基礎再使用基于投影的方法來確定傾斜角度，同樣無法處理扭曲文本。文獻[4]使用基于投影輪廓的方法來求得傾斜角度，之后對整幅圖片進行等角度旋轉，而非像素的旋轉，經(jīng)此方法校正后的扭曲文本圖像很難再接著進行扭曲恢復等處理，影響最終的OCR識別率。文獻[5]使用近鄰法則是找出所有中心點的K個最鄰近點，計算每對近鄰的矢量方向并統(tǒng)計生成直方圖，直方圖的峰值對應著整幅圖像的傾角，同樣對原始扭曲文本校正效果一般。文獻[6]基于Fourier變換方法則以Fourier空間密度最大的方向?qū)趦A斜方向。雖然該方法傾斜校正較為精確,但由于空間復雜度很高, 計算的時間長, 因此在實際中使用較少。

由以上文獻可知，傳統(tǒng)的二維傾斜校正算法無法有效處理原始扭曲文本的傾斜。而本文將三維處理技術應用于文本圖像傾斜校正領域，提出一種基于點云數(shù)據(jù)的扭曲文檔傾斜校正方法，能有效處理扭曲文本的傾斜狀況，并通過實驗進行了驗證。

1算法思路

圖1　算法流程圖

若文本模型存在噪點，會對后續(xù)的處理產(chǎn)生極大的影響，因此需要先對文本點云模型進行去噪。去噪后將傾斜檢測分為兩步：空間傾斜檢測與平面傾斜檢測?？臻g傾斜檢測通過提取模型邊界特征點，采用魯棒方法求得文本模型邊界所在平面的法向量，最后通過與一平行于Z軸的單位向量之間的叉乘、內(nèi)積等計算出空間傾斜角，并進行判斷，若傾斜則采用空間旋轉算法進行旋轉校正。平面傾斜檢測時，由于文本模型是扭曲、非平面的，因此先對文本模型進行平面投影。接著提取投影的邊界特征點，采用空間最小二乘法對其進行空間線性擬合，計算出其平面傾斜角，進行平面傾斜校正。圖1是本文的算法流程圖。

2點云去噪

在三維掃描儀獲取結構光的投影并進行處理的過程中，不可避免地會產(chǎn)生一些噪點數(shù)據(jù)，這些噪點數(shù)據(jù)將會對后續(xù)的處理產(chǎn)生較大的干擾作用，因此必須先對其進行點云去噪。由于三維掃描儀都有配套的處理軟件，可以對采集的模型數(shù)據(jù)進行初步分割，去除那些不需要的部分。但有時個別單點或者微量點云會由于人眼無法觀察到而導致人工清除失敗，因此進行去噪的主要目的就是去除那些遺漏的離群點。本文采用的方法是基于K-近鄰的散亂點云去噪算法。

2.1K-近鄰搜索

文本模型是由無數(shù)個孤立的點組成的，因此我們讀入到內(nèi)存中的數(shù)據(jù)點都是混亂的、無序的，這和傳統(tǒng)的BMP位圖有著顯著區(qū)別。所以在對模型進行其他處理前，必須先將模型中的散亂點通過某種結構關聯(lián)起來，建立數(shù)據(jù)點之間的空間拓撲關系。本文采用K-近鄰結構[7]。

目前最常用的K-近鄰計算方法有八叉樹法、 空間單元格法和K-d樹法。其中前兩種方法都是基于空間包圍盒的劃分， 后一種方法則用來查找相距最近的兩點。本文采用空間單元格法進行K-近鄰計算。首先設P=Pi(i=0,1,…,n)是文本點云模型S上的一個采樣點集，將S中與當前點Pi距離最近的k個數(shù)據(jù)點稱為點Pi的K-近鄰，記作Nb(p)。接著讀入文本模型數(shù)據(jù)點集，將整個點集的坐標存入三個一維數(shù)組中，得到模型點集在X、Y、Z三個坐標軸方向上的最大值與最小值，然后根據(jù)極值信息，k值及點的總數(shù)n，計算出子立方體邊長L。同時將文本點云模型劃分成m′×n′×l′個子立方體，記錄每個子立方體所包含的數(shù)據(jù)點以及每個點所在的立方體索引號，并刪去不包含任何點的子立方體。最后通過子立方體內(nèi)點的信息遍歷數(shù)據(jù)點進行K-近鄰搜索。

定義三個方向上最小坐標為: Min _x、Min _ y、Min _z；最大坐標為: Max _ x、Max _ y、Max _ z，則式(1)文本點云模型的子立方體的長度L：

(1)

其中β為調(diào)節(jié)立方體編程L大小的比例因子；n為數(shù)據(jù)點的總個數(shù)；k為可調(diào)整的近鄰點的個數(shù)。那么由式(2)可以推導出子立方體在三個坐標上的個數(shù)：

(2)

同樣由式(3)可推導出當前點P(x,y,z)在子立方體中三個坐標方向的索引號：

(3)

在此為每一個立方體子空間建立一鏈表。該表存儲每個子立方體內(nèi)的所有點，并統(tǒng)計該子立方體內(nèi)點的個數(shù)，其結構如下：

typedefstructCubecell

{

LinkedListLink；

//子立方體內(nèi)數(shù)據(jù)點集表的頭指針

intn；

//子立方體中所含數(shù)據(jù)點的個數(shù)

}Cube;

求取當前點的K個近鄰點的步驟為：

1) 根據(jù)當前點的坐標值，確定其所在子立方體的索引號，同時將此子立方體視為初始搜索區(qū)域；

2) 計算當前點到所在立方體六個面的最短距離ds；

3) 計算當前搜索區(qū)域點的總個數(shù)N1，若N1不小于K，則接著計算當前點與搜索區(qū)域內(nèi)其他點的最大距離dmax。若dmax小于ds，取前k個點為當前點的K近鄰點，否則以當前區(qū)域為中心向周圍擴展建立新的搜索區(qū)域;

4) 為每一個數(shù)據(jù)點建立一個k鄰近表。該表保存每個點的k個鄰近點以及它與鄰近點的距離，其結構如下：

typedefstructKpoint

{

doublex,，y，z；

// 鄰近點的坐標信息

doubledistance；

// 數(shù)據(jù)點與鄰近點之間的距離

structKpoint*next；

//下一個鄰近點

}Kpoint, *List；

2.2鄰域平均算法

建立好散亂點之間的空間拓撲關系之后，就可以使用二維圖像處理中的濾波算法對點云模型進行去噪處理。遍歷模型搜索每個數(shù)據(jù)點的K-近鄰，采用鄰域平均法進行去噪。 具體算法描述如下[8]：

1) 讀入三維文本模型點云數(shù)據(jù)；

2) 建立散亂點云之間的空間拓撲關系；

3) 搜索當前點Pi的K-近鄰Nb(p)；

4) 計算當前點Pj與其各K-近鄰點之間的距離，取其平均值Dmid(pi)可由式(4)求出：

(4)

5) 判斷該平均距離Dmid(pi) 是否大于設定的閾值D，若超過，則認為該點是噪點，將其刪除；

6) 重復 3)～5)，直到處理完所有的數(shù)據(jù)點。

3傾斜檢測

首先對文本模型可能發(fā)生的傾斜情況進行分類，在此共分為三大類：空間單傾斜、平面單傾斜、空間平面雙傾斜。以圖2(a)所示圖像為例，文本點云模型在空間上存在傾斜，同時如圖2(b)所示，模型在平面上也存在傾斜，因此模型屬于空間平面雙傾斜類。圖中曲面部分為扭曲文本模型，平面部分為一垂直于Z軸的對照平面，用于觀察文本模型在空間中傾斜狀況。因此結合分類情況以及文本模型本身特點，將對文本點云模型的傾斜檢測分為兩步：空間傾斜檢測與平面傾斜檢測。

圖2　傾斜檢測示意

3.1空間傾斜檢測

由于本文研究的文檔模型是扭曲的，也就是說其所有的點并不落在同一個平面上。因此，需要先選擇某一斜切面為切入點，通過它來研究完整文本模型的特征。結合實際情況，選擇文本模型左右邊界所在的平面為我們所需要的平面。確定平面后，采用曲面邊界提取算法采集模型的邊界特征點。

點云去噪階段已獲得當前點p的K近鄰點集X={x0,x1,…,xk-1}，設X的中心點v，可由式(5)計算[9，10]：

(5)

Ax+By+Cz+D=0

(6)

其中A=xp-xv，B=yp-yv，C=zp-zv，D可由式(7)計算：

(7)

圖3　模型邊界分析圖

得到模型的邊界特征點集之后，通過限制邊界點的X值與Y值得到模型左右邊界特征點，如圖3所示。

通過魯棒的方法求得左右邊界所在平面的法向量[11]。由式(8)計算平面法向量m的分向量(mx,my,mz)：

(8)

這里的N是特征點集中的頂點總數(shù)，(xi,yi,zi)是第i個特征點的位置坐標，next(i)=(i+1)modN是點i的下一個頂點序號。取模運算保證了第(N-1)號頂點的后一個頂點是頂點0。這種方法在計算法向量的每一個分量過程中，只需對每一條邊使用一次乘法運算，而且不需要做共線測試。

得到m向量后先將其單位化，得一單位法向量m′。接著選取一平行于Z軸的單位向量n(0,0,1)，并由式(9)計算向量m′與n的夾角：

(9)

計算出夾角后設一閾值D=0.5°，若夾角位于(-D,D)內(nèi)，則認為模型在空間中無傾斜，否則繼續(xù)對兩個向量進行叉乘運算，得到一新向量即空間旋轉所需要的轉軸，并使用空間旋轉算法對其進行空間旋轉。

圖4(a)中曲面部分為原始模型，平面為一垂直于Z軸的對照平面，圖4(b)為空間校正后模型，黑色線條為上文中所提到的向量m′、n以及它們叉乘后得到的向量。

圖4　空間校正示意

3.2平面傾斜檢測

經(jīng)過空間傾斜檢測及校正，此時整個文本模型垂直于Z軸。先將文檔模型垂直投影到Z=0平面上，投影到此平面上后的模型Z坐標值皆為0，可減少計算量，提高檢測精度。

投影后采集投影四條邊界的特征點，使用基于最小二乘法的空間線性擬合算法，對模型的四條邊界進行線性擬合，分別計算上下兩條直線與左右兩條直線的斜率，并判定兩對傾斜角的差值是否在一個范圍(-1°，1°)內(nèi)。結果可能存在三種情況：

1) 若每對傾斜角的差值都在范圍內(nèi)，則對兩對邊界直線的傾斜角取兩輪平均值，這樣可以得到一個高精度的傾斜角；

2) 若其中一對差值在范圍內(nèi)，另一對差值不在范圍內(nèi)，則取差值在范圍內(nèi)的一對的平均值為傾斜角；

3) 若兩對邊界線斜率均不在，則提示模型不合格。

基于初期采集模型時已經(jīng)過選擇與處理，因此后兩種情況較少。

設空間內(nèi)方向向量為s=(m,n,p)且過(x0,y0,z0)點的直線方程由式(10)表示[12,13]：

(10)

當點(xi,yi,zi) 不在直線上時，分別記其在x方向、y方向、z方向的誤差為(εi2,εi2,εi3)。作為最佳擬合直線，必須同時考慮這三個方向的誤差。根據(jù)最佳平方逼近原理，最佳直線應滿足式(11)：

(11)

最小。因為各測量點在x方向、y方向、z方向的誤差(εi2,εi2,εi3)服從正態(tài)分布，所以最佳直線也應滿足式(12)：

(12)

據(jù)此我們在約束條件式(11)式(12)下求由離散點 (xi,yi,zi)，i=1,2,…,N，所確定的最佳直線。

3.3空間旋轉算法

本文使用的是由薛文風[14]提出的空間坐標旋轉算法。設一個點通過軸(x0,y0,z0)，其方向余弦為(nx,ny,nz)。其中θ為坐標點(x,y,z)繞該軸的旋轉角度。則旋轉后的點經(jīng)式(13)計算：

x′ =(x-x0)[nx2(1-cosθ) + cosθ] +(y-y0)[nxny(1-cosθ)-nzsinθ]+ (z-z0)[nxnz(1-cosθ) +nysinθ] +x0y′ =(x-x0)[nxny(1-cosθ) +nzcosθ] +(y-y0)[ny2(1-cosθ)-cosθ]+ (z-z0)[nynz(1-cosθ)-nxsinθ] +y0z′ =(x-x0)[nxnz(1-cosθ)-nycosθ]+(y-y0)[nynz(1-cosθ)-nxcosθ]+(z-z0)[nz2(1-cosθ)-cosθ] +z0

(13)

當(x0,y0,z0)=(0,0,0)時，該軸通過原點繞任意軸旋轉的變換關系表達式比較長，而且需要浮點數(shù)來表示，所以在程序編寫時，最好在計算表達式之前先把sinθ和cosθ算出，以提高程序的執(zhí)行速度。值得注意的是，當進行空間檢測得到所需數(shù)據(jù)后，若存在傾斜需先進行空間傾斜校正，以免干擾平面傾斜角的計算。

4實驗結果

本算法在VisualStudio2005環(huán)境下采用C++語言實現(xiàn)，測試環(huán)境為:Intel?CoreTM7cpu; 內(nèi)存 8GB;操作系統(tǒng)為Windows7的機器上進行。本文先使用三維掃描儀對5本不同厚度的書籍共采集了50個書籍點云模型，其中空間域平面傾斜角皆在(-45°,45°)范圍內(nèi)。所用書籍均為16開普通中文書。接著使用普通攝像頭采集了50幅BMP圖像，拍攝攝像頭像素為500萬，圖像的獲取均在光照均勻的環(huán)境下進行，忽略噪聲的干擾。

表1將傳統(tǒng)的Hough變換法、投影法與本文方法對重度扭曲文本傾斜檢測精度進行了對比分析。傳統(tǒng)的Hough變換法、投影法與K近鄰法總體檢測正確率都低于50%，而本文方法對三種情況的正確率都達到95%以上。此處的正確率是指經(jīng)傾斜校正后視覺上無傾斜的文本圖像個數(shù)與參加測試的樣本個數(shù)之比。由實驗結果可知傳統(tǒng)的二維傾斜校正方法只能對扭曲程度較輕的文本進行有效校正，對于厚度較大、扭曲程度較高的傾斜文本處理能力很差。而本文方法則具有很大的適用范圍，對于以上情況均有很高的校正正確率。

表1　原始扭曲文本總體校正正確率對比分析

用本文算法對選取模型進行傾斜校正，部分實驗效果對比圖如圖5-圖7所示。其中圖5為扭曲文本空間單傾斜對比圖，圖6為扭曲文本空間平面雙傾斜校正效果對比圖，圖7為非扭曲文本傾斜校正效果對比圖。

圖5　單傾斜對比

圖6　雙傾斜對比

圖7　校正效果對比

5結語

本文結合當前快速發(fā)展的三維處理技術，將三維點云處理技術應用到文本圖像傾斜校正領域，克服了傳統(tǒng)二維傾斜校正方法對原始扭曲文本、射影文本傾斜校正效果不佳的缺點。提出的基于點云數(shù)據(jù)的扭曲文本傾斜校正方法，對于復雜文本如扭曲文本、射影文本可以直接進行傾斜校正處理。經(jīng)試驗表明，本文方法對于扭曲文本傾斜校正正確率能達到95%。本方法已試用于本實驗室開發(fā)的輔助閱讀器改進項目，實現(xiàn)了對于市面上大部分不同厚度的書籍的自動傾斜校正處理，擴大了閱讀器使用范圍，提高了用戶操作容錯率。

參考文獻

[1] 周冠瑋,平西建,程娟. 基于改進Hough變換的文本圖像傾斜校正方法[J].計算機應用,2007,27(7):52-57.

[2] 段汝嬌,趙偉,黃松嶺. 一種基于改進Hough變換的直線快速檢測算法[J]. 儀器儀表學報, 2012, 31(12):2774-2780.

[3] 張順利,李衛(wèi)斌,吉軍. 基于投影的文檔圖像傾斜校正方法[J].計算機工程與應用,2010,46(3): 166-168.

[4] 程立,姚為,李波. 基于投影輪廓的文本圖像傾斜檢測[J]. 中國圖象圖形學報,2015,20(1):29-38.

[5]DeyP,NoushathS.Arobustskewdetectionmethodforscanneddocumentimages[J].PatternRecognition, 2010, 43(3):937-948.

[6]PSTLW.Detectionoflinearobliquestructureandskewscanindigitizeddocuments[C]//Proceedingsofthe8thInternationalConferenceonPatternRecognition.Paris,France:[s.n.],1986:687- 689.

[7] 謝方方,徐連誠,牛冰茹. 一種基于反向K近鄰的孤立點檢測改進算法[J].計算機應用與軟件,2014,31(6),267-270.

[8] 曹爽,岳建平,馬文. 基于特征選擇的雙邊濾波點云去噪算法[J]. 東南大學學報(自然科學版),2013,43(S2):351-354.

[9] 陳義仁,王一賓,彭張節(jié)，等．一種改進的散亂點云邊界特征點提取算法[J]. 計算機工程與應用,2012,48(23):177-180.

[10] 吳祿慎,晏海平,陳華偉，等. 一種基于散亂點云的邊界提取算法[J]. 計算機應用與軟件，2014,31(11):264-268.

[11] 李寶,程志全,黨崗,等. 三維點云法向量估計綜述[J]. 計算機工程與應用,2010,46(23):1-7.

[12] 姚宜斌,黃書華,孔建,等. 空間直線擬合的整體最小二乘算法[J]. 武漢大學學報(信息科學版),2014,39(5):571-574.

[13] 王繼剛,周立,蔣廷臣，等. 一種簡單的加權整體最小二乘直線擬合方法[J]．測繪通報,2014(4):33-35.

[14] 薛文風. 三維空間坐標的旋轉算法[J].電腦編程技巧與維護,1995(6):59-60.

A TILT CORRECTION METHOD FOR DISTORTED TEXT ANDIMAGEBASEDONPOINTCLOUDDATA

Tong LijingZheng Junchao*

(College of Computer, North China University of Technology, Beijing 100144, China)

AbstractIn view of that traditional two-dimensional tilt correction algorithm is difficult to deal with the tilts of distorted text, we put forward a point cloud data-based tilt correction method for distortion text and image. First, it collects data information of text by a 3D scanner, and reconstructs the 3D point cloud model of text. Then according to the examined text position in space, it defines the tilt as either the space tilt or plane tilt. Finally it realises automatic tilt correction of the text. Experimental results show that the correction rate of tilt correction algorithm based on point cloud data reaches over 95% in dealing with the distorted text.

KeywordsPoint cloud dataDistorted textSkew detectionSpace tiltPlane tiltTilt correction

收稿日期：2015-06-10。國家自然科學基金項目(61371142)；北京市教委專項(PXM2013_014212_000026)。童立靖，副教授，主研領域：圖像處理，智能控制，系統(tǒng)辨識等。鄭俊朝，碩士生。

中圖分類號TP3

文獻標識碼A

DOI:10.3969/j.issn.1000-386x.2016.06.043