U E D R , A S I H C RSS

논문번역/2012년스터디/서민관

제약사항� 없는 off-line 필기 �스트 �� 실험

abstract
off-line 필기 ��� 위한 시스템� 소개한다.
� 시스템� �� 모듈� 전체 �스트 ��� �어서 처리하는 분할� 없는 접근 방법(segmentation-free approach)� 특징�다.
전처리, 특징 ì¶”ìœ, 통계ì � 모ë�¸ë§�ì�„ 위한 방법들ì�„ 소개하고, 작성ìž�ì—� ë�…립ì �ì�¸ 방법, 복수ì�˜ 작성ìž�, 한 명ì�˜ 작성ìž�ì�˜ 필기 ì�¸ì‹� 등ì—� 대한 실험들ë�„ ì�´ë£¨ì–´ì§ˆ 것ì�´ë‹¤.
특히, 선형 �별 해�(linear discriminant analysis)과 allograph 문� 모�, 통계� 언어 지�� 결합한 방법� 살펴볼 것�다.
어휘 제한� 없는(lexicon-off) 필기 ��� 결과는 제안하는 방�� 효율� 입�할 것�다.

1. �입
패턴 ���서 �전할 만한 분야는 필기 �스트� ���다.
아�까지는 대부분� off-line 필기 �� 시스템� 우편 번호를 �거나 �행 수표 등� 모양� 처리하는� 사용�다.
�런 시스템들� 분할� 문�나 단어�만 한정�으로 사용�고 있고, 제약사항� 없는 필기 �� 시스템� 무척 �다.
�것� 방대한 어휘� 대해 글�나 단어� 경계가 존재하지 않기 때문� �러한 작업� 복잡�가 올�가기 때문�다.
하지만 컴퓨터� 계산 능력� �가가 � 복잡한 처리를 가능하게 하였기 때문� 필기 �스트 �� 기술� � 살펴볼 만한 가치는 있다.

� 논문�서는 어휘 제한� 없는 off-line� 필기 ��� 기본으로 한 Hidden-Markov-Model� 소개할 것�다.
그리고 작성�� �립�� 방법과 복수 작성�, 단� 작성�� 대해 완전한 �어 문장 ��터베�스� 기반한 몇몇 실험들� 소개할 것�다.
전처리와 특징 ì¶”ìœì�„ 위한 방법들ì�„ 기술할 것ì�¸ë�°, 추가ì �으로 선형 íŒ�별 í•´ì„�, allograph 문ìž� 모ë�¸, 통계ì � 언어 ì§€ì‹� 등ì�˜ ë�” ì •êµ�한 방법ë�„ 살펴볼 것ì�´ë‹¤.

다� 섹션�서는 필기 ��� 대한 관련 연구를 간단히 살펴볼 것�다.
우리가 사용할 ��터베�스� 대해서는 섹션 3�서 소개한다.
ê·¸ 후ì—� ì�´ì–´ì§€ëŠ” 섹션들ì—�서 전처리 과정, 특징 ì¶”ìœì�„ 위한 방법들, 통계ì � 모ë�¸ë§�ê³¼ ì�¸ì‹�ì—� 사용ë�œ 기술 들ì—� 대해서 서술할 것ì�´ë‹¤.
제안한 방법� 효과를 나타내기 위한 �가 결과는 세션 7�서 소개할 것�다.

2. 관련 연구
지난 여러해 �안 off-line 필기 �� 분야�서 �당한 진전� 있었다.
특히 �� 양� 어휘를 �용하는 분리� 단어를 ��하는 시스템� 우편번호나 legal amount reading� 사용�었고, 높� ��률� 기�하였다. 그래서 처리 ��나 ��� 정확�를 높� 여지가 없었다 2, 8.

�와는 달리 방대한 양� 단어를 사용하는 제한� 없는 필기 �스트� ��� 훨씬 어렵다.
�런 �들� 주로 문맥 정보나 단어 구간� 정보가 없기 때문� �어난다. �러한 어려움� 분리� 단어 처리를 위한 시스템 들� 내재�어 나타난다.
�런 어려움들�� 불구하고 제한� 없는 필기 �스트 ��� 많� 발달해 왔다.
ì�´ 시스템들ì�€ 주로 특징 ì¶”ìœ(feature extract) 타입ì�´ë‚˜ ì�¸ì‹� 단계 ì „ ë˜�는 후ì—� í…�스트 ë�¼ì�¸ì�„ 분리하거나 하는 ì �ì—�서 ì°¨ì�´ê°€ 있다.
1, 18과 15� HMMs 방법� 사용하는 �스트 분리� 기반� 둔 방법과 recurrent neural network와 HMMs를 혼합한 방법� � 예시가 있다.
15�서 한 실험� 단� 작성�� �한 ��터베�스�서 행해진 반면�, 1, 18� 나타난 시스템들� 복수 작성�� ��터를 �용해서 테스트를 했다.
대규모� off-line 필기체 ��� 대한 조사는 16� 보아�.

�른 단계�서 �스트 ��� 분리하는 것� �한 문제�� 회피하기 위해서, 9�서는 전체 �스트 ��� �� 모듈� 입력하는 무분할(segmentation-free) 방법� 소개�어 있다.
� 시스템� 단� 작성�로 테스트 �었고, 통계� 언어 지�과� 결합으로 전�� 있는 �� 결과를 달성하였다.
작성�� �립��고 제약� 없는 �스트 ��� 위한 향�� 시스템� 수백명� 작성�� �해 만들어진 거대한 ��터베�스10�서 실험� 내용� 11� 기술�어 있다.
ì�´ì–´ì§€ëŠ” 섹션들ì—�서 설명할 시스템ì�€ 비슷한 접근법ì�„ 사용하였는ë�°, 전처리와 특징 ì¶”ìœ ë°©ë²•ì�´ 약간 다르다.
추가�으로, � 문� 종류� 따� HMMs나 통계� 언어 모�� 사용하는 등� allograph 문� 모�� 사용하는 것 � 아니� 특징 벡터들� 대해 선형 �별 해�� �용한 효과� 대해서� 살펴보았다.

3. �뭉치
학습과 ��� 위한 입력 ��터는 Lancaster-Oslo/Bergen �뭉치� 기반� 둔 완전한 �어 문장� ��터베�스�서 제공�었다.
작성�� �립� 경우 �만 아니� 복수 작성�� 대한 실험� IAM과 Bern 대학�서 수집한 필기 형태를 �용하여 �루어졌다.
전체 ��터베�스는 다양한 �스트 카테고리들(신문, 종�, 대중 지�, 소설)과 500명 ��� 다른 작성�들� �한 1200종류 ��� 필기 형태를 다루고 있다.
우리는 작성� �립� 경우� 실험� 위해 250명 ��� 작성�가 만든 카테고리 a..f� 형태들� �용했다. 그리고 복수 작성�� 경우� 실험� 위해 6명� 작성�� �해 만들어진 c03� �부를 �용하였다.

우리� 시스템� 단� 작성�� 경우�� �가하기 위해서 노�(Senior)들�게서 수집� ��터베�스�서 제공하는 필기 형태를 �용한 실험� 하였다.
� ��터베�스는 단� 작성�� �한 25페�지� 필기 �스트로 �루어져 있으며, 웹�서 공개�으로 사용할 수 있다.

� ��터베�스� 필기 형태는 해�� 300dpi�서 256� 그레� 레벨로 스캔�었다.
Fig. 1� � ��터베�스� 예시를 보여준다.

4. 전처리
스캔 중�나 필기�서 지��� ��으로 형태� 부정확한 정렬� �는 것으로 발�하는 �러를 보완하기 위해 처�� 주어진 필기 �스트� �미지는 비스듬하게 �어 있다.
따�서 �진화 � �미지� 수� ��� 히스토그램� 최저� 무질서�를 가질 때까지 �미지를 회전시켜야 한다.
주�할 �� � 전처리 단계는 IAM ��터베�스�는 �용할 필요가 없다는 것�다. 작성�들� � 번째 용지� �를 사용하게 �었고 스캔� 하는 �안�� 공�� 통해 정렬� �었기 때문�다.

í…�스트ì—� 추가ì �ì�¸ 처리를 하기 위해서는 ê°�ê°�ì�˜ 필기 ë�¼ì�¸ë“¤ì�„ ì¶”ìœí•´ì•¼ 한다.
�것� 수필 ���서 중요한 부분� �미지를 분할하는 것으로 가능하다.
�스트 ��� �위나 하위� 기준선 같� 종류� 핵심 지역� 기준 선� 나타내기 위해서 핵심 지역� �하는 필수 선들� 픽셀들� 나타내는 임계치를 찾는 것으로 알 수 있다.
�진화 � 수필 지역� 수� 밀� 히스토그램� �용하는 Otsu method를 �용하면 � 임계치를 ��으로 구할 수 있다.
그 후 수� 투사� 히스토그램� � ��들� 검� 픽셀들� 수가 누��다. 그리고 � �미지는 � 투사� 히스토그램� 최소� 지�� 따� 핵심 지역으로 분할�다.

다양한 필기 스타��나 작성� 차� 때문� �� 작업� 간단하게 하기 위해서는 필기들� 정규화 �어야 한다.
특히 필기� 수� 위치, �그러�� 수정하는 것� 전처리�서 중요하다고 �명�었다.
추가�� 정규화는 필기� �기와 그레� 레벨� 강�� 중시한다.

가�� 필기 스타�� 한 �� 안�서� �게 달�질 수 있다는 관찰�서 �향� 받아서 우리는 � 수필 ��� 수� 위치, �그러� 등� 지역�으로 �정하였다.
따�서 � 행� 수필 지역 사�� 공백� �색하는 방법� 통해 나누어진다.
안정�� 정규화 ��를 계산하기� 너무 짧� 지역� 회피하기 위해서 임계치를 사용하였다.

반면� 수� 위치와 �그러�� 15� 나온 것과 비슷한 선형 회귀(linear regression)를 �용한 베�스�� 추정 방법� �용해서 �정하였다. �그러진 ��� 계산� �� 방향� 기반으로 하였다.
ë”°ë�¼ì„œ 해당 ì�´ë¯¸ì§€ëŠ” ì�´ì§„í™”ë�˜ê³ , ì�¼ê·¸ëŸ¬ì§� 추정ì�„ 위해서 수ì§� íš�ì�´ 중요하다는 ê³ ë ¤ 하ì—� 수í�‰ ë°©í–¥ì—�서 ê²€ì�€ìƒ‰-í�°ìƒ‰, í�°ìƒ‰-ê²€ì�€ìƒ‰ 변환들ì�´ ì¶”ìœë�œë‹¤.
ê°�ë�„ 히스토그램ì—�서 누ì �ë�˜ëŠ” 모서리 기반 ë�°ì�´í„°ë¥¼ 얻기 위해서 ì •êµ�한 모서리 ê²€ìœê¸°ê°€ 사용ë�˜ì—ˆë‹¤.
� 히스토그램� �균값� �그러진 ��(slant angle)로서 사용�었다.

필기� �기를 정규화하기 위해서 우리는 � 필기 ��� 지역�� 극값(local extrema)� 세고 � 값� ��� 넓�와 비�하였다.
ì•ì²™ ì�¸ìž�(scaling factor)는 선형ì �으로 ì�´ 관계ì—� 기반한다. ì�´ëŠ” ì�´ 관계가 í�´ìˆ˜ë¡� 필기 스타ì�¼ì�´ ì¢�아지기 때문ì�´ë‹¤.
마지막 전처리 단계는 다른 종류� 펜과 종�� �한 차�를 보완하기 위한 그레� 레벨� 정규화로 �루어져 있다.
따�서 �미지� 그레� 레벨 간격� 가장 어�운 곳� 0� �고 가장 �� 곳� 255가 �다.
� 전처리 단계� 효과는 �뭉치�서 전형�� �스트 ��� �용한 그림 3� 나타나 있다.

5. 특징 ì¶”ìœ
필기 ë�¼ì�¸ì�˜ 전처리 ë�œ ì�´ë¯¸ì§€ëŠ” 특징 ì¶”ìœ ë‹¨ê³„ì�˜ ìž…ë ¥ ë�°ì�´í„°ë¡œ 들어간다.
11� 기술� 것과 유사한 접근방법� sliding window 기법� �용�었다.
우리ì�˜ 경우ì—�는 ì�´ë¯¸ì§€ì�˜ 높ì�´ì™€ 4ì—´ì�˜ ë„“ì�´ë¥¼ 가진 윈ë�„ìš°ê°€ 2ì—´ë§Œí�¼ ê²¹ì³�지면서 ì�´ë¯¸ì§€ì�˜ 좌측ì—�서 우측으로 ì�´ë�™í•˜ì˜€ë‹¤. 그리고 한ë‘� ê°œì�˜ 기하학ì � 특징들ì�„ ì¶”ìœí–ˆë‹¤.

sliding window� � 열마다 다� 7가지 특징들� 계산�었다.
(1) 검�색-�색 변환� 수(window� 들어간 �스트 �미지를 �진화 한 후�)
(2) 기준선� 고려했� 때� 극값 분산� �균값 위치(position of the mean value of the intensity distribution)
(3) �스트 픽셀� 최�단�서 기준선까지� 거리
(4) �스트 픽셀� 최하단�서 기준선까지� 거리
(5) �스트 픽셀� 최�단과 최하단 사�� 거리
(6) �스트 픽셀� 최�단과 최하단 사�� �균 극값
(7) 열� �균 극값
필기 사�즈� 분산� 대해 견고함� �가시키기 위해서 특징 (2)-(5)는 �단 기준선과 하단 기준선� 거리(지역 최고값� �용한 line fitting으로 계산�)를 �용해서 정규화�었다.
그 후� window� 4열마다 모든 특징들� �균화�었다.

극값 분산� �균값� 경사� �만 아니� �하단 윤곽� 방향� 고려하기 위해서, 우리는 추가�으로 3개� 방향 특징� 계산하였다.
따�서 우리는 window 내부� 있는 4개� 하단 윤곽�과 �단 윤곽�, �균 값� �용해서 ��� 추정하였다. 그리고 ��� 위치를 �� (8), (9), (10)� 특징으로 사용하였다.

� 넓� 임시 문맥� 고려해서, 우리는 � 특징 벡터 요소마다 근사�� 수� 파�물(approximate horizental derivative)� 계산하였다. 따�서 20차�� 특징 벡터를 얻었다.(window당 10개� 특징 + 10개� 파�물)

특징 벡터들� 연관성� 줄�고 �래스(...)� 분리성� �가시키기 위해서 우리는 훈련과 �� 단계� 선형 �별 해�� 통합하였다.(cf. 6)
선형 변환과 특징 공간� 차�� 줄�는 방법� �용하여 �형 특징 표현(........ original feature representation)� 최�화하였다.
선형 변환 A는 훈련 ��터� 있는 class scatter matrix Sw과 scatter matrix Sb 간� 고유값(eigenvalue) 문제를 푸는 것으로 얻어진다.
� scatter matrix들� � 특징 벡터가 HMM�태로 분류�고 우리는 처�� 훈련 ��터� �태� 기반한 정렬� 따�서 �반 훈련� 수행해야 한다. (...........................)
� scatter matirx들� 알고 있� 때 LDA 변환� 다� 고유값 문제를 푸는 것으로 계산할 수 있다.

... �

...와 ...는 S-1wSb� 고유값과 고유벡터�다.
ì°¨ì›�수ì�˜ 수ì•ì�€ mê°œì�˜ 최대 고유값들ì—� ì†�한 mê°œì�˜ 고유벡터를 구하는 것ì�„ 고려하는 것으로 얻는다.
모든 특징 벡터들� LDA 변환 한 후� 완전히 새로운 HMM 학습� 수행�다.

6. 통계� 모��과 ��
필기 �스트 �� 작업� 위한 설정, 학습, HMMs� 해� 작업� ESMERALDA 개발 환경5�서 제공�는 방법들과 �구들� �해 수행�다.
HMMs� �반�� 구성� 위해 우리는 512개� Gaussian mixtures with diagonal covariance matrices를 담고 있는 공유 codebook과 반-연��� 시스템들� �용하였다.
기본 시스템 모�� 위해서 52개� 문�, 10개� 숫�, 12개� 문장부호와 괄호, 하나� 공백 문�가 표준 Baum-Welch 재추정� �용해서 훈련�다.
문� 모�들� 반복으로 구성� 결합 모�� 전체 �스트 ��� ��하기 위해서 사용�다.
가장 유사할 것 같� 문� 배열� 표준 Viterbi beam-search 방법� �용해서 계산�다.

전처리 �안 보완할 수 없었� 다양한 필기 방�� 차�를 고려해서 우리는 13� 기술� 접근방�과 유사하게 복수 작성�와 작성�� �립�� ��� 위한 문� allograph 모�� �용하였다.
Allograph는 특정 문�� 다른 샘플(realization)과 같� 문�� 하위 항목� 나타낸다.
�것� 기준선 시스템과 반대로 HMMs가 사로 다른 문�� 하위 항목� 모��하기 위해서 사용�다는 것� 뜻한다.
따�서 문� 당 하위 항목� 수와 allograph HMMs� 수는 발견�으로(heuristically) 결정�다. 예를 들어 복수 작성� 시스템� 경우 allograph� 수가 주어진 작성�� 수와 같�� 추정할 수 있다.
초기화를 위해서, 훈련 ��터는 무작위로 선�� allograph HMMs로 분류�다.
모든 문� 샘플� 훈련하는 �안, 병렬�으로 모든 해당하는 allograph 모�들�게 매개변수 재추정� �용�다.
�치 확률� 특정 모�� 매개변수가 현재 샘플� 얼마나 �향� 받았는지를 결정한다.
따�서 allograph 분류는 고유하게 결정�는 것� 아니� 단지 � 과정� soft vector 양�화와 유사한지� 따� 확률�으로 결정�다.

추가�으로, 문� 배열� 대한 추정� 제공할 것 같� �� 과정� 통계� 언어 모�� 통합�었다.
�지 처리� 목표는 ... �� 따르는 관측� ��터 x� 대해 결합� 통계 모�� 확률� 극대화 하는 문� 배열 W^를 찾는 것�다.
위 방정� P(w)는 문� 배열 w와 입력 ��터 x가 문� 모�� 따를 때 � 문� 배열� 관측할 확률 P(x|w)� 대한 문� 모� 확률� 나타낸다.
우리� 경우�는 absolute discounting � �용한 bi-gram언어 모�과 backing-off for smoothing of probability distributions가 �용�었다.

7. ê²°ê³¼
우리는 우리� 필기 �� 시스템� �가하기 위해 세 종류� 실험� 했다. 단� 작성�, 복수 작성�, 작성�와 �립� 경우.
� 실험들� 문� 오류율� table 1� 나타나있다. 실험� 타입� 첫 � 열� 나와 있고, 언어 모�� �용하지 않� �러율� 세 번째 열�, bi-gram 언어 모�� 문� 수준�서 사용한 결과는 네 번째 열�서 찾� 수 있다.
언어 모�� IAM ��터베�스� a..d 카테고리� 모든 �스트를 �용하여 �성�었고, 나머지 실험들�서� ��하다.
어휘 제한� 없는(lexicon-free ....) 단어 ��과 어휘� 기반한 단어 ��� 결과는 table 2� 나타나 있다.
단� 작성�� 경우� 실험� 노�(Senior) ��터베�스�서 학습� 위해 282줄� �스트를 사용했고 테스트를 위해 141줄� �스트를 사용했다. 문� 수준� bi-gram perplexity는 15.3�었다.
bi-gram 언어 모�� �입하는 것으로 13.3%� 기준선 시스템� 오류율� 12.1%까지 �소하는 결과를 �루었다.
LDA 변환� 특징� �용하는 것으로 오류율� �게 �가하지 않게 �다. 심지어 LDA 변환� 특징 공간� 12까지 줄어들어� 그렇다.
단� 작성� 시스템�서� 단어 오류율(table 2)� 어휘가 없는 �황�서 28.5%, 특히 1.5k 어휘�서는 10.5%�다.
� 결과들� 우리가 찾아낸 같� ��터베�스를 쓰는 결과(literature ......)와 비�했� 때 쓸만하다. 훈련용과 테스트용 셋� �기가 다르기 때문� 비�하기는 어렵지만.
17�서 � 글�� 오류율� 28.3%로 측정�었다. 어휘가 없는 경우� 84.1%였고, 특히 1.3k 어휘�서는 16.5%였다.
15는 어휘가 있는 �황�서 6.6%� 단어 오류율과 어휘가 없는 �황�서 41.1%� 단어 오류율� 보고하였다.
9�서 보고� 어휘� 기반한 단어 오류율� 최고치는 15.0%였다.

복수 작성�� 수필 �� 작업� 위해 IAM ��터베�스�서 c03� 하위집합� 있는 440줄� �스트 ��들� 학습� 위해 사용�었고, 109줄� 테스트를 위해 사용�었다.
� �스트 ��들� 6명� 다른 작성�� �해 �당히 다른 필기 스타�로 작성�었다.
ì�´ 작업ì�„ 위해서 LDA(수ì•ë�œ ì°¨ì›�수 12)를 ì�´ìš©í•œ 14.2%ì�˜ 오류율ì�„ 가진 문ìž�들ì�´ 얻어졌다. ì—�러율ì�€ allograph 모ë�¸(ê°� 소문ìž�마다 6ê°œì�˜ allograph)ì�„ ì�´ìš©í•˜ëŠ” 것으로 13.3%까지 ê°�소한다.
bi-gram 언어 모�� �용� 추가�으로 오류율� 11.1%(테스트 셋 perplexity 12.0)까지 � 낮춰준다.
어휘를 사용하지 않는 경우ì—� 단어 오류율ì�´ 39.0%, 421ê°œì�˜ 단어(문장부호 í�¬í•¨)를 í�¬í•¨í•˜ëŠ” 어휘를 ì �용하는 것으로 13.9%까지 떨어진다. ì�´ê²ƒì�€ 11ì—� ìœíŒ�ë�œ 단어 오류율 20.5%와 잘 비êµ�ë�œë‹¤.

�러한 결과들� 우리가 훨씬 � 어려운 작성�� �립�� ��� 수행하는� 힘� 주었다.
IAM ��터베�스� 있는 a-f(약 250명� 작성�)� 하위집합� 입력 ��터로 사용�었는�, 4321��� �스트(a-d�서 나옴)는 훈련용으로 사용�었고, 1097��� �스트(e-f�서 나옴)는 테스트� 사용�었다.
� 기준선 시스템� 단어 �러율 31.3%를 달성하였다.
작성� �립�� 경우� allograph 모�� �용하는 것� 복수 작성� 실험과 비�해서 뚜렷한 향�� 나타내지는 않았다.
문� 하나당 3개� allograph를 사용하는 것� 31.1%� 오류율� 달성했고, 우리가 단어당 10개� allograph 모�� 사용한 실험� 했� 때는 오류율(34.8%)과 �� ��가 둘 다 나빠졌다.
하지만 LDA변환� 특징� 사용했� 때�는 오류율� 29.1%로 �미가 있게 �소하였다.
추가�으로 언어 모�� �함시키� 문� 오류율� 훨씬 향��어 22.2%가 �었다.(테스트 셋 perplexity 12.0)
�와 같� 경우�서 어휘를 사용하지 않았� 때 단어 오류율� 60.6%였다.

8. ê²°ë¡ .
우리는 분할� 없는 off-line 수필 �스트 ��� 위한 시스템� 소개하였다. 그리고 단� 작성�, 복수 작성�, 작성�� �립�� 경우� 대한 몇몇 실험� 행하였다.
어휘를 사용하지 않� 경우 단어 기반� 때 � 아니� 문� 수준�서� 유�한 �� 결과가 얻어졌다.
� �� 정확�는 문� 수준�서 통계�� 문� 모�� �용한 기준선 시스템� 비해서 �당히 향��었다. 그리고 특징 공간� 선형 �별 해�� 행하는 것으로 복수 작성�와 작성�� �립�� 경우� 대해 �� 정확�가 향��었다.
allograph 문� 모�� 사용하는 것으로 �� 정확� 측면�서, 복수 작성�� 경우� 특히, � 많� 향�� �루어질 것�다.

9. acknowledgement
� 작업� German Research Foundation(DFG)� 프로�트 Fi799/1�서 �조를 받았다.
추가�으로 수필 형태� DB를 제공한 대학들�게 �사 �사를 드린다.
Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:54
Processing time 0.0134 sec