王江晴,張 軼

(中南民族大學(xué)計算機科學(xué)學(xué)院,武漢430074)

基于像素的少數(shù)民族手寫體文檔傾斜校正算法

王江晴,張 軼

(中南民族大學(xué)計算機科學(xué)學(xué)院,武漢430074)

針對女書等少數(shù)民族手寫體文獻(xiàn)行間距不固定、豎行書寫及存在連筆和粘連等特性,提出了一個能夠?qū)@一類傾斜手寫體文檔進(jìn)行準(zhǔn)確調(diào)整的基于像素的改進(jìn)最小二乘法傾斜校正算法(I L SM P).算法同時考慮橫縱坐標(biāo)的誤差,并對字符粘連等進(jìn)行處理以進(jìn)一步提高校正準(zhǔn)確度.實驗結(jié)果表明:該算法對于手寫體文檔的傾斜校正是有效的.

字符粘連;像素;最小二乘法;傾斜校正

少數(shù)民族文獻(xiàn)記錄著各少數(shù)民族的文化基因及歷史淵源,是我國乃至全世界極其寶貴的非物質(zhì)文化遺產(chǎn).在眾多少數(shù)民族語言文字中,女書是世界上最具性別意識的少數(shù)民族文字,這種由女性創(chuàng)造、女性使用、傳女不傳男的斜體文字,從文化層面上反映了女性的集體智慧.女書沒有統(tǒng)一的規(guī)范化字體,她的傳承主要是通過手寫的方式進(jìn)行.在對這些文獻(xiàn)進(jìn)行信息化時,掃描后的文檔經(jīng)常出現(xiàn)傾斜現(xiàn)象,不利于后續(xù)的文字分割、識別等工作,必須對其進(jìn)行傾斜校正.

常用的傾斜校正方法有以下幾類:基于Hough變換的方法、交叉相關(guān)性算法、水平或垂直投影法、基于傅里葉變換的方法、K-最近鄰簇法[1]和基于最小二乘法的方法.基于Hough變換的方法[2]抗噪聲能力強且不受文檔中直線方向的影響[3],但它的數(shù)據(jù)量大,糾斜準(zhǔn)確度偏低[4];交叉相關(guān)性算法[5]準(zhǔn)確率高但相關(guān)矩陣的計算量較大;投影法[6]不但計算量大,且精度取決于進(jìn)行不同角度投影測試時的單位步長角度值;基于傅里葉變換的方法[7]對文檔中全部的像素點做傅里葉變換來進(jìn)行傾斜校正,這種方法的計算量非常大,目前很少采用.

針對女書等手寫體少數(shù)民族文獻(xiàn)行間距不固定、豎行書寫等問題,本文提出了一種基于像素的改進(jìn)的最小二乘法 (I mproved L east Square M ethod Based on Pixel,I L SM P).算法在對各行的粘連現(xiàn)象進(jìn)行處理以后,利用橫縱坐標(biāo)的誤差對像素點位置進(jìn)行運算,以計算文檔傾斜的角度.實驗結(jié)果表明,對于女書等少數(shù)民族手寫體文獻(xiàn),該算法比其它算法具有更高的準(zhǔn)確度.

1 最小二乘法

最小二乘法選取文本圖像的子區(qū)域中字符連通域的底邊中心點作為特征點[8],利用行基線與特征點的關(guān)系,建立數(shù)學(xué)模型如公式(1).

用最小二乘法計算公式擬合出基線方向[9],從而獲取整個頁面的傾斜角.基線的斜率值k[10,11]可通過公式(2)來求解.

其中,表示待處理圖像中所有離散點橫坐標(biāo)的平均值,表示所有離散點縱坐標(biāo)的平均值,表示所有離散點橫縱坐標(biāo)乘積的平均值,·表示所有離散點橫縱坐標(biāo)平均值的乘積,表示所有離散點橫坐標(biāo)的平方的平均值,表示所有離散點縱坐標(biāo)的平方的平均值,Δy表示縱坐標(biāo)的相對距離,Δx表示橫坐標(biāo)的相對距離.

最小二乘法對傾斜文檔的校正是目前常用的校正方法之一.但該方法易受所選取的區(qū)域影響,不具有整體特征,且要求文檔中的文本行都為水平,行間距離固定.文獻(xiàn)[12]對該方法進(jìn)行了改進(jìn),針對頁面前景點來進(jìn)行計算,選擇文檔中最大矩形和其中的像素點作為傾斜角度的檢測對象.這種方法對于包含圖片的文檔比較有效,但要求文檔書寫規(guī)范,行間距離一致.

2 算法設(shè)計及描述

針對最小二乘法在處理手寫體文檔中連筆和粘連、行間距不固定、豎行排列等現(xiàn)象存在的不足,本文提出了I L SM P算法.算法中引入公式(3)[11]、公式(4).

公式(3)計算的是橫坐標(biāo)值存在誤差情況下直線的斜率k1.由于在傾斜的手寫文檔中各個像素點的位置都發(fā)生了偏移,即像素點的橫縱坐標(biāo)值都會產(chǎn)生相應(yīng)的偏差,若僅選擇圖像子區(qū)域且僅考慮其中一類誤差,會對手寫文檔的傾斜校正工作產(chǎn)生影響,使校正后的文檔仍存在傾斜現(xiàn)象.因此需要從整個文檔出發(fā),針對所有像素點進(jìn)行處理,本算法同時考慮橫縱坐標(biāo)的誤差,采用公式(4)對k、k1的值進(jìn)行修正,其中α、β是預(yù)先給定的修正系數(shù).由于k1的值較大,根據(jù)多次實驗得出,在α取1、β取0.001時可以得到理想的校正效果.

I L SM P算法對手寫體文檔進(jìn)行傾斜校正的基本流程如下:

(1)預(yù)處理.讀入圖像,對圖像進(jìn)行二值化操作,將圖像轉(zhuǎn)化為黑白二色;

(2)獲取特征點.查找圖像中字符像素點,并記錄各點所在的位置,對于存在行間粘連現(xiàn)象的水平書寫文檔,通過設(shè)置閾值消除粘連現(xiàn)象;

(3)計算傾斜文檔的傾斜角度.利用公式(4)對圖像中各字符點的位置進(jìn)行計算,獲得斜率值K,將K值轉(zhuǎn)化為對應(yīng)的角度值;

(4)利用校正函數(shù)im rotate將原圖像按照傾斜的角度旋轉(zhuǎn),從而對圖像進(jìn)行校正.

3 算法實現(xiàn)

3.1 預(yù)處理

在對傾斜文檔進(jìn)行校正前,首先要進(jìn)行二值化處理,使文檔圖像變?yōu)楹诎锥?文字部分為黑色像素點(用0表示).本文采用大津法對文檔圖像進(jìn)行二值化處理,根據(jù)圖像的參數(shù)信息自動獲取一個最佳的閾值作為二值化的分界值,小于此閾值的像素值置為0,表示文字,大于此閾值的像素值置為1,表示背景,使文檔圖像清晰明了.

3.2 粘連處理

對于水平書寫的文檔,文檔中可能存在行間粘連現(xiàn)象,會使得文字與背景的區(qū)分界限模糊,影響了傾斜角計算的準(zhǔn)確度.針對此問題,本文通過預(yù)設(shè)的閾值T對整個文檔進(jìn)行逐行掃描:若第i行黑色像素的個數(shù)Hi＜T,則將第i行視為存在行間粘連,在水平方向?qū)i行從左至右的像素值置為背景值1,反之,則保持原數(shù)據(jù)不變,不作處理.這不僅解決了行間粘連的現(xiàn)象,同時也提高了傾斜角計算的準(zhǔn)確度.對于豎行書寫的文檔,則極少存在粘連現(xiàn)象,不需做粘連處理.

3.3 特征點選取

利用查找函數(shù)find,通過循環(huán)條件逐一對文檔中的黑色像素點進(jìn)行掃描,并定義一個二維數(shù)組來存放查找到的字符像素點的行列號,將掃描后查找到為黑色像素點的最小行、最大行和最小列、最大列作為新的待處理矩陣的起始和終止行列,從而僅保留文字部分,剔除多余像素信息,最大限度地記錄文檔中文字像素點位置,去除非文字像素點,以節(jié)省計算的數(shù)據(jù)量,提高運算速度.

3.4 頁面傾斜校正

根據(jù)公式(4)計算整個文檔的傾斜斜率值K,并通過反正切函數(shù)獲得文檔圖像傾斜的弧度θ:

獲得傾斜的弧度值后,將其轉(zhuǎn)換為相應(yīng)的角度值,判斷傾斜角度所在的象限,若在第一三象限,則依據(jù)計算得出的角度對原圖像做順時針旋轉(zhuǎn);若在二四象限,則對原圖像做逆時針旋轉(zhuǎn),通過旋轉(zhuǎn)變換即可對原圖像進(jìn)行校正.校正過程如公式(6).其中,x、y為原圖像的坐標(biāo)位置,x′、y′為校正后的坐標(biāo)位置.

4 實驗結(jié)果及分析

本文對大量有代表性的、不同質(zhì)量的樣本進(jìn)行了實驗,包括以豎行排列的手寫女書文檔和有連筆現(xiàn)象的手寫文檔等,實驗中取α=1,β=0.001,T=15.部分實驗結(jié)果如圖1、2所示.

圖1 初始女書文檔Fig.1 Initial document

圖2 校正后的文檔Fig.2 Adjusted document

為了進(jìn)一步驗證算法的有效性,將I L SM P算法與只考慮縱坐標(biāo)誤差的標(biāo)準(zhǔn)最小二乘法、Hough算法[8]、交叉相關(guān)性算法[9]進(jìn)行了比較,比較結(jié)果如表1,表2所示.從表1中可以看出,本文提出的算法與標(biāo)準(zhǔn)最小二乘法相比,在校正效果和準(zhǔn)確率方面都有顯著的提高;從表2中可以看出,本文提出算法的誤差平均值為0.035,誤差標(biāo)準(zhǔn)偏差為0.03279,而Hough算法的誤差平均值為0.15,誤差標(biāo)準(zhǔn)偏差為0.06707,交叉相關(guān)性算法的誤差平均值0.068,誤差標(biāo)準(zhǔn)偏差為0.0416.本算法在對傾斜文本圖像進(jìn)行校正時,校正的精度比較高,且最大絕對誤差和最小絕對誤差也相對較小.

表1 標(biāo)準(zhǔn)最小二乘法與I LSM P比較Tab.1 Comparison about Standard Least SquareM ethod and I LSM P

表2 Hough算法、交叉相關(guān)性算法與I LSM P比較Tab.2 Comparison about Hough A lgorithm、Cross-Correlation A lgorithm and I LSM P

5 結(jié)語

針對少數(shù)民族手寫體文獻(xiàn)中存在的連筆、粘連、行間距不固定和豎行書寫等特點,本文提出了一個改進(jìn)的傾斜校正算法I L SM P.算法在計算斜率值時,以文檔中所有文字像素點的橫縱坐標(biāo)位置為基本計算元素進(jìn)行計算,不僅考慮了縱坐標(biāo)的誤差情況,同時將橫坐標(biāo)的誤差情況也加以利用,以得出文檔傾斜的角度,從而使計算得到的斜率值更為科學(xué)合理.針對水平書寫方式中各行之間存在的粘連現(xiàn)象,本算法也加以處理.實驗表明,對于女書等少數(shù)民族手寫體傾斜文檔,該算法是有效的.

[1] O′Goman L.The document spectrum for page layout analysis[J].IEEE T ransaction on PAM I,1993,15(11):1162-1173.

[2] 李 政,楊 揚,頡 斌,等.一種基于Hough變換的文檔圖像傾斜糾正方法[J].計算機應(yīng)用,2005,25(3):583-585.

[3] Zhang Ruilin,Hu Yan,Fang Zhijian,et al.Skew detection and correction method of fabic images based on hough transform [C]//IC ICTA.Proceedings of the 2009 Second International Conference on Intelligent Computation Technology and A utomation.Zhangjiajie:IC ICTA,2009:340-343.

[4] 周冠瑋,平西建,程 娟.基于改進(jìn)Hough變換的文本圖像傾斜校正方法[J].計算機應(yīng)用,2007,27(7):1813-1816.

[5] 李慶峰,付忠良,劉 琴.一種高效的傾斜圖像校正方法[J].計算機工程,2006,32(21):194-196.

[6] Ciardiello G,Scafur G,DegrandM T,et al.A n experimental system for office document handling and text recognition[C]//ICPR.Proceedingsofthe 9th International Conference on Pattern Recognition.Rome:ICPR,1998:739-743.

[7] PstlW.Detection of linear oblique structure and skew scan in digitized documents[C]//ICPR.Proceedings of the 8th International Conference on Pattern Recognition,Pairs:ICPR,1986:687-689.

[8] 王姝華,李 佐,蔡士杰.基于最小二乘法的文檔圖像傾斜檢測方法[J].計算機應(yīng)用與軟件,2001,13(9):43-46.

[9] 王姝華,李 佐,蔡士杰.基于直線連續(xù)性的頁面傾斜檢測與校正[J].計算機輔助設(shè)計圖形學(xué)學(xué)報,2001(8):736-741.

[10] 王 輝,牟宏鑫,王嘉梅,等.一種文本圖像傾斜校正的方法[J].云南民族大學(xué)學(xué)報:自然科學(xué)版,2010,19(3):232-234.

[11] 王文周.用最小二乘法求直線斜率的新公式[J].四川工業(yè)學(xué)院學(xué)報,2000(1):67-69.

[12] 陳 波,王加俊,吳 陳.基于頁面前景和最小二乘法的傾斜校正[J].計算機工程,2007,33(15):202-204.

Skew Correction Algorithm s Based on Pixel for Handwriting Document of M inority Nationality

W ang J iangqing Zhang Y iy i
(College of Computer Science,South-CentralU niversity for N ationalities,W uhan 430074,China)

A imed to the characteristics,such as conglutinations,unfixed space lines and vertical-w ritten form s in the scripts and documents in m inority nationa lities,a skew correction algorithm based on pixel called improved least square method( IL SM P)is provided.The algorithm not only takes account of the error of the x-coordinate and y-coordinatel,but also processes the touched characters,and in order to improve the accuracy of the correction.Exper imental results show that the algorithm solves the problem of skew ing handw riting document effectively.

touched characters;pixel point;least square method;skew correction

TP391

A

1672-4321(2011)01-0088-04

2010-09-20

王江晴(1964-),女,教授,博士,研究方向:人工智能,E-mail:w jqing2000@yahoo.com.cn

國家自然科學(xué)基金資助項目(60975021)