SIFT 서술자를이용한오프라인필기체문자인식특징추출기법 박정국 김경중 세종대학교 컴퓨터공학과 Email: prfirst@sju.ac.kr, kimkj@sejong.ac.kr Feature Extraction for Off-line Handwritten Character Recognition using SIFT Descriptor Jung-Guk Park Kyung-Joong Kim Department of Computer Engineering, Sejong University 요약본논문에서는 SIFT(Scale Invariant Feature Transform) 기술자를이용하여오프라인필기체문자인식을위한특징추출방법을제안한다. 제안하는방법은문자의획의방향정보를제공하는특징벡터를추출함으로써오프라인문자인식에서성능향상을기대할수있다. 테스트를위해 MNIST 필기체데이터베이스와 UJI Penchar2 필기체데이터베이스를이용하였고, BP(backpropagation) 신경망과 LDA(Linear Discriminant Analysis), SVM(Support Vector Machine) 분류기에서성능테스트를하였다. 본논문의실험결과에서는일반적으로사용되는특징추출로부터얻어진특징에제안된특징추출을정합하여성능항샹을보인다. 1. 서론 오프라인필기체문자인식은지난 50년간패턴인식분야에서중요한연구주제였다 [1]. 실세계에서무인우편번호인식, 수표인식, 문서판별등에서사용되기위한연구사례가있으며 [2][3] 다양한특징추출방법 [4][5] 과전처리 [6] 및분류기성능향상과함께발전되어져왔다. 문자인식에서각문자클래스마다구별력이강한특징을추출하는것은성능향상과이어지므로특징추출은중요한부분이다. 패턴인식문제에서도성능을높이기위해서는특징추출과추출된특징을처리하는분류기의성능이주요관심사이다. 문자인식을위한특징추출방법은여러각도에서연구중이며 S.W.Lee는문자의각획의방향을 Kirssh마스크를이용하여획을 4방향으로나누어특징추출을하였고 [7], Dayahanker는 12방향의특징추출을하였다 [8]. 획의정보를잘반영할수있는특징추출은문자인식문제를보다쉽게풀수있는접근방법이다. 본논문에서는특징추출부분에대한방법을제안하며그림1에제안된방법의개요 를보인다. 제안하는방법은 D.G.Lowe[9] 가소개한 SIFT (Scale Invariant Feature Extraction 이하 SIFT) 기술자를문자의정의된중심모멘트에중심으로하여특징을추출한다. SIFT 서술자는지문인식 [10], 사물인식 [11], 문자인식 [12] 등에서유용하게사용되고있다. 제안하는특징추출은일반적으로사용되는문자인식을위한특징에추가되어구별력을가진특징을생성하게되는데, 이는문자의획의방향에대한정보를제공할수있다. 제안하는방법으로추출된특징은 3가지의다른타입의분류기를사용하여기존의특징과비교하며성능평가를한다. 본연구에서는구별력있는특징추출에중점을두었으며기존의특징추출중일반적으로사용되는방법중문자영상이미지로부터문자의획의정보를충분히반영할수있는 2가지를채택하여제안된방법과의비교를본논문에서보인다. 본논문의구성은다음과같다.2장에서는제안하는특징추출방법을서술하고,3장에서는추출된특징을분류하기위한분류기들을소개한다.4장에서는실험결과를보이고, 5장은본논문의결론을제시한다.
그림 2. 중심모멘트와 4 분할평면의특징히스토그램 그림 1. 문자인식의시스템과본논문의제안한방법 2. 특징추출 3. 분류기 이절에서는오프라인필기체문자인식을위한특징추출방법을소개한다. 제안하는특징추출방법은본연구에서정의된중심모멘트를중심으로 SIFT 서술자를사용하여특징추출을하였다. 중심모멘트는입력된문자영상을 4분할하여 4평면을생성하며다음과같이정의된다 [13]. m (x,y) R x p y p a = m 00 (1) x c = m 10 a y c = m 01 a m은중심모멘트정의이며, a는문자의면적을나타내고, x c,y c 는 x축,y축중심모멘트이다. 중심모멘트를중심으로 SIFT 서술자가특징추출을하게된다. SIFT 서술자는다음과같다. Descriptor (x,y) =[θ (x,y),mag (x,y) ] (2) θ (x,y) = tan 1 (I x,y+1 I x,y 1 )/(I x 1,y I x+1,y ) mag (x,y) = (I x+1,y I x 1,y ) 2 +(I x,y+1 I x,y 1 ) 2 수식 2의 Descriptor (x,y) 는문자영상이미지필셀좌표x,y에서의 SIFT 서술자를나타내고크기가 mag 이고방향이 θ인벡터로나타낼수있다. 구해진벡터의 θ을 8방향으로양자화하며, 각픽셀의벡터방향θ에따라서 mag 크기를정합한히스토그램을특징으로사용한다. 양자화된벡터는중심모멘트를중심으로 4개의특징평면으로나누어서정규화하여, 한평면당 8방향의벡터를가지는 4평면의총 32개의특징벡터를완성한다. 제안하는 SIFT 서술자는각평면의글의획의방향과크기를반영할수있다. 이절에서는특징을사용하여분류를수행할분류기에대해소개를한다. LDA(Linear Discriminant Analysis) 와 MLP(Multi-Layered Perceptron), SVM(Support Vector Machine) 분류기를서술한다. A. LDA LDA는베이지언학습을이용하여패턴분류를한다. 베이지언확률은다음과같으며 P (w i x) = p(x w i)p (w i ) p(x) 분별함수는다음과같다. g(w i, x) =p(x w i )P (w i ) p(x w i ) 는 N(µ, Σ) 인정규분포를따르며 1 p(x w i )= (2π) d 2 Σ i 1 2 exp (x µ i ) T Σ 1(x µi ) 2 분별함수는다음과같이얻을수있다 [14]. B. MLP g(x,w i )=(x µ i ) T Σ 1 (x µ i )+log P (w i ) 본실험에서사용한 Multiple Layer Perceptron 은하나의은닉층을가졌으며델타법칙으로연결강도를학습시킨다. 입력층은특징벡터의차원과같고, 출력층의개수는클래스의개수를따른다. 어떤입력패턴 x =[x 1,x 2,...x d ] 이고 k개의클래스가있을때, 출력값 O k 는 O k (x) =s[ h n j=1 w kj s(v T jix + v j0 )+w k0 ]
= s[ h n j=1 w kj h j + w k0 ] 1 s는시그모이드함수 s(x) = 1+exp 이며, h x n 은은닉층의개수이다. w kj 은출력층과은닉층을연결하는가중치이고, v j i는은닉층과입력층을연결하는가중치값이다. 연결강도학습에는 back-propagation( 오류역전파 ) 알고리즘 [15] 을사용했으며, 온라인모드로연결값을갱신하였다. C. SVM Support Vector Machine[16] 분류기는일반적으로이진분류문제를해결하는데사용하며, 다중분류문제에서는여러개의 SVM이필요하다. 본연구에서는 M 분류문제에대해서 ( ) M 2 문제로나누어서해결을하였다. 어떤특징벡터 x에대해서 SVM은 f(x) = y i α i k(x, x i )+b (3) 로나타내며, l은학습을위한특징패턴의개수이며, y i 는특징x에대한 -1또는 1을갖는목표값이다. b는바이어스이며, k(x, x i ) 은특징벡터의커널함수이며 Φ(x) 는특징벡터를확장시킨특징공간함수이다. 본연구에서는 k(x, x i )=Φ(x) Φ(x i ) (4) k(x, x i,p)=(1+x x i ) p (5) 두가지커널을사용하였다. 수식 (3) 은일반화된선형판별함수로나타낼수있으며 w = y i α i Φ(x i ) α i 는아래의최적화문제를풀면서얻을수있다. 을최소화하며 y i f(x i ) 1 ξ i, J(w) = 1 2 w 2 ξ i 0,,..., l 을만족한다. 이것은 2차계획법문제이며듀얼문제로변환할수있으며 를최대화하고 W (α) = α i 1 2 α iα j y i y j k(x i, x j ) 0 α i C, i =1,..., l, α i y i =0 여기에서 C 는학습하는동안의분류에러임계치이다. 4. 실험결과 본연구를위해문자영상의크기를 28x28 크기로정규화하여 Otsu[17] 방법을이용하여의사-이진영상으로변환하는간단한전처리과정을거치며 MNIST 데이터베이스와 Machine Learining Repository의 UJI penchar2 데이터베이스를사용하였다.( 그림3 참고 ) MNIST 데이터베이스는 60000개의테스트집합과 10000개의테스트집합으로이루어져있으며각클래스간학습집합을균등하게하기위해 5000종류를사용하였다. UJI pencahr2 데이터베이스는필기체영상이미지 52개의영문자대문자소문자를포함하여 14가지스페인문자, 숫자,21가지각종기호문자영상이미지를포함하여, 학습영상이미지 80종류와테스트영상이미지 40종류로이루어져있다. 분류기매개변수설정은 MLP의경우학습률은 0.2로하였으며 MNIST 데이터베이스에대해서는 50 epoch, UJI penchar2 데이터베이스는 100 epoch를학습시켰다. SVM(L) 은수식 (4) 의커널을따르고 SVM(P) 는수식 (5) 의커널을따르며커널의 p의값은2이며두 SVM 모두종료임계치값을 0.01로하였고분류에러임계치는 1로설정하였다. 본연구에서는숫자영상이미지를사용하여기존의필기체숫자의특징추출방법과비교를하였다. D.Trier[4] 는문자영상이미지에서특징을추출하게위해 Zoning technique와 Projection crossing count 방법을소개하였고본실험에서는두가지특징추출을정합하여하나의특징벡터를생성하여특징추출1을만들고, 여기특징벡터에제안하는 SIFT 서술자가포함된특징을포함하여특징추출2을생성하여비교를하였다. 특징추출1에서 projection crossing count 방법으로 22차원의벡터를생성하고특징벡터의차원을낮추고 Zoning technique 에서는영상이미지를 7*7로나누어서단일한부분의화소의평균을특징값으로취해서특징벡터의차원은총 71차원이다. 특징추출2에서는특징추출1에서제안한방법의 SIFT 서술자특징벡터 32차원을포함시킨다. 표1에서는두특징에대해 4가지분류기로테스트된결과를보인다. 표2와표3에서는 MNIST데이터베이스에서특징추출1과특징추출2으로추출된특징을 SVM(L) 분류기로학습된결과를보이며제안한특징추출방법의향상된성능을보여준다.
그림 3. 데이터베이스영상이미지의예 ( 위 UJIPenchar2 데이터베이스아래 MNIST 데이터베이스 ) 표 I 기존의특징추출방법과제안하는특징추출방법을각분류기를이용한테스트결과 MNIST UJI Penchar2 분류기 기존의특징추출 제안된특징추출 기존의특징추출 제안된특징추출 LDA 85.12% 89.00% 87.75% 89.50% MLP 94.83% 95.04% 92.50% 94.25% SVM(L) 92.50% 94.34% 91.75% 93.50% SVM(P) 95.73% 96.07% 93.50% 94.75% 표 II SVM(L) 을사용한 MNIST 데이터베이스 CONFUSION MATRIX( 위. 특징추출1 아래. 특징추출2( 제안한방법 )) 0 962 3 0 2 0 2 4 2 5 0 98.16% 1 1 962 4 3 0 9 5 0 13 0 96.20% 2 4 11 952 9 2 2 7 4 8 1 95.20% 3 2 1 13 936 1 22 0 9 10 6 93.60% 4 1 4 5 0 940 0 9 0 3 20 95.72% 5 3 8 11 26 4 816 8 2 13 1 91.47% 6 7 0 4 0 4 9 931 0 3 0 97.18% 7 0 7 8 2 11 3 0 933 4 32 93.30% 8 8 42 6 16 11 12 2 5 864 8 88.70% 9 1 217 3 14 22 6 0 16 18 917 75.53% total 92.50 0 969 0 0 1 0 1 3 2 4 0 98.87% 1 1 976 7 2 2 1 4 0 6 1 97.60% 2 2 8 969 5 3 0 1 5 7 0 96.90% 3 2 0 6 955 0 21 0 7 5 4 95.50% 4 0 2 4 0 951 1 8 0 1 15 96.84% 5 2 1 4 24 1 843 6 1 9 1 94.50% 6 6 1 6 0 2 10 930 0 3 0 97.07% 7 0 6 7 0 10 1 0 950 2 24 95.00% 8 5 9 8 5 8 9 1 4 918 7 94.25% 9 2 4 2 14 16 4 0 18 221 933 76.85% total 94.34 표 III SVM(L) 을이용한 UJI PENCHAR2 데이터베이스 CONFUSION MATRIX( 위. 특징추출1 아래. 특징추출2( 제안한방법 ) 0 38 0 0 0 0 0 1 0 1 0 95.00% 1 2 36 0 0 2 0 0 0 0 0 90.00% 2 0 1 36 0 0 2 0 1 0 0 90.00% 3 1 0 0 39 0 0 0 0 0 0 97.50% 4 0 3 0 0 36 0 0 0 0 1 90.00% 5 0 1 0 2 0 36 0 0 1 0 90.00% 6 0 0 1 0 0 2 36 0 1 0 90.00% 7 0 0 0 0 0 0 0 38 1 1 95.00% 8 0 0 1 1 0 0 0 0 38 0 95.00% 9 1 1 2 0 0 1 0 0 1 34 85.00% total 91.75 0 40 0 0 0 0 0 0 0 0 0 100% 1 1 38 0 0 0 0 0 0 0 0 95.00% 2 0 3 36 0 0 0 0 1 0 0 90.00% 3 0 0 0 40 0 0 0 0 0 0 100% 4 0 3 0 0 37 0 0 0 0 0 92.50% 5 0 0 0 1 0 36 0 0 3 0 90.00% 6 0 0 1 0 0 1 36 0 2 0 90.00% 7 0 0 0 0 0 0 0 39 0 1 97.50% 8 0 1 0 0 0 0 0 0 39 0 97.50% 9 0 1 1 2 0 2 0 0 1 33 82.50% total 93.50
5. 결론 본논문에서는 SIFT서술자를이용하여획의방향을반영할수있는특징을추출할수있었고, 표1에서보이듯각 4가지의분류기를통해제안하는방법이오프라인필기체문자인식에서성능을향상시키는것을확인할수있었다. 본연구에서는일반적으로높은인식률을위한다양한특징추출방법을연구하지못하였지만, 기존에사용하던특징추출에사용되는방법에제안하는방법을정합하여더나은특징을추출해낼수있었다. 제안하는방법은획의구별력을높혀주어사선이나역사선에대해강한정보를제공하여오인식되는샘플의수를낮출수있었고테스트한두데이터베이스에대해서인식향상을보였으며, 일반적으로오인식될수있는숫자 7과 9의혼동을감소시켰고비슷한위상적정보를가진획에대한문자의구별력을높힐수있었다. 감사의글 이논문은 2010년도정부 ( 교육과학기술부 ) 의재원으로한국연구재단의지원을받아수행된기초연구사업임 (2010-0012876) 참고문헌 Transactions on Pattern Analysis and Machine Intelligence, vol.18, no. 6, pp. 648-652, 1996 [8] Dayashankar Singh, Sanjay Kr.Singh and Dr.Maitreyee Dutta, Hand- Written Character Recognition using twelve Directional feature Input and Neural Network, International Journal of Computer Applications, no. 3 - Article 14, 2010 [9] David G. Lowe, Distinctive Image Features from Scale-Invariant Keypoints, International Journal of Computer Vision, vol. 60, no. 2, pp. 91-110, 2004 [10] Unsang Park, Sharath Pankanti and A.K. Jain, Fingerprint verification using SIFT features, Defense and Security Symposium, Orlando, FL, USA, vol. 6944, 2008 [11] Koen van de Sande, Theo Gevers and Cees Snoek, Evaluating Color Descriptors for Object and Scene Recognition, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 99, no. PrePrints, 2009 [12] Zhiyi Zhang, Lianwen Jin, Kai Ding and Xue Gao, Character-SIFT: A Novel Feature for Offline Handwritten Chinese Character Recognition, icdar, pp.763-767, 2009 10th International Conference on Document Analysis and Recognition, 2009 [13] Sergios Theodoridis and Konstantinos Koutroumbas, Pattern Recognition 3/E, Academic Press, pp. 340-342, 2006. [14] Richard O. Duda, Peter E. Hart, David G. Stork, Pattern lassification 2/E, Wiley-Interscience, pp. 36-41, 2002 [15] D. E. Rumelhart, G. E. Hinton, R. J. Williams, Learning internal representations by error propagation, Neurocomputing: foundations of research, pp. 673-695, 1986 [16] Christopher J.C. Burges, A Tutorial on Support Vector Machines for Pattern Recognition, Data Mining and Knowledge Discovery, vol.2,pp. 121-167, 1998 [17] Nobuyuki Otsu, A threshold selection method from gray-level histograms, IEEE Transactions on Systems, Man and Cybernetics, vol. 9, no. 1, pp. 62-66, 1979 [1] Shunji Mori, Ching Y.Suen, Kazuhiro Yamamoto, Historical Review of OCR Research and Development, Document image analysis, IEEE Computer Society Press, pp. 244-273, 1995 [2] LeCun Y., Boser B., Denker J. S., Henderson D., Howard R. E., Hubbard W. and Jackel L. D., Backpropagation Applied to Handwritten Zip Code Recognition, Neural Computation, vol. 1, no. 4, pp. 541-551, 1989 [3] LeCun Y., Bottou L., Bengio Y. and Haffner P., Gradient-Based Learning Applied to Document Recognition, Intelligent Signal Processing, IEEE, pp. 306-351, 2001 [4] Øivind Due Trier, Anil K Jain and Torfinn Taxt, Feature Extraction Methods For Character Recognition - A Survey, Pattern Recognition, vol. 29, pp. 641-662, 1996 [5] Cheng-Lin Liu, Kazuki Nakashima, Hiroshi Sako, Hiromichi Fujisawa, Handwritten digit recognition: investigation of normalization and feature extraction techniques, Pattern Recognition, vol. 37, no. 2, pp. 265-279, 2004 [6] Chen-Lin Liu, Masashi Koga, Hiroshi Sako, Hiromichi Fujisawa, Aspect Ratio Adaptive Normalization for Handwriiten Character Recognition, Lecture Note in Computer Science, vol. 1948, pp. 418-425, 2000 [7] Seong-Whan Lee, Off-Line Recognition of Totally Unconstrained Handwritten Numerals Using Multilayer Cluster Neural Network, IEEE