U E D R , A S I H C RSS

논문번역/2012년스터디/�민�

�민�

  • LaTeX 수ì‹�ì�´ 안 보여요

용어 사전

see also � 보기
coarse 대략��, 거친

2012/11/16

  • 「Experiments in Unconstrained Offline Handwritten Text Recognitionã€� 번역
  • 다ì�Œ 주까지 1학년 1학기ì—� ë°°ìš´ Linear Algebra and Its Applicationsì�˜ 1.10, 2.1, 2.2ì ˆ 번역하기

2012/11/29



Experiments in Unconstrained Offline Handwritten Text Recognition(제약 없는 오프�� 필기 글� ��� 관한 실험)


초�
오프�� 필기 글� ��� 위한 시스템� 소개한다. � 시스템� 특징� 분할� 없다는 것으로 �� 모듈�서 한 줄� 통째로 처리한다. 전처리, 특징 추출(feature extraction), 통계� 모형화 방법� 서술하고 저� �립, 다저�, 단� 저�� 필기 �� 작업� 관해 실험하였다. 특히 선형 �별 분�(Linear Discriminant Analysis), �서체(allograph) 글� 모형, 통계� 언어 지�� 통합� 조사하였다.

1 서론
필기 글� ��� 패턴 ��� �전�� 분야다. 지금까지� 오프�� 필기 �� 시스템들� 대부분 우편 주소 �기나 �행 수표 같� 형�� 처리하는 � �용�었다. 14 �들 시스템� 개별 글�나 단어 ��� 한정� 반면 제약 없는(unconstrained) 필기 글� ��� 위한 시스템� 거� 없다. 그 �유는 �러한 작업� �게 복잡하기 때문�� 글� �는 단어� 경계� 대한 정보가 없는 �다 헤아릴 수 없� 정�로 어휘가 방대한 것� 특징�다. 그럼�� 필기 글� �� 기법� � 조사하는 것� 가치 있는 �유는, 계산 능력� 향삼함� 따� �욱 복잡한 처리를 할 수 있기 때문�다.
본 논문�서는 �닉 마르코프 모형� 기반한, 어휘(lexicon)-free 오프�� 필기 �� 시스템� 소개하고 완전한 �어 문장 ��터베�스� 관한 몇 가지 실험� 저� �립� 그리고 대조를 위해 다저�, 단� 저��으로 수행했다. 전처리와 특징 추출 방법� 소개하고 �� �해 선형 �별 분�, �서체 글� 모형� 사용, 통계� 언어 모형 같� �욱 정�한 기법들� 조사한다. 그 뒤� 절�서는 오프�� 필기 ��� 대한 관련 작업들� 짧게 검토한다. 우리가 사용한 ��터베�스는 3절�서 소개한다. 그 다� 전처리, 특징 추출 방법, 통계� 모��과 ��� 위한 기법� 설명한다. �가 결과는 제안한 방법� 효율성� 입�하기 위해 7절�서 소개한다.

2 관련 작업
최근 몇 년간 오프�� 필기 �� 분야는 �당히 진전하였다. 특히 우편 주소나 legal amount �기를 위한, �� 어휘를 사용한 개별 단어 �� 시스템� 높� ��률� 달성했고 �� 정확�� 아니� 처리 ��를 고려해�� 개선할 여지가 거� 없다. 2 8
반면� 방대하거나 아예 한계가 없는 어휘를 �용한 제약 없는 필기 글� ��� 훨씬 어렵다. �는 개별 단어 처리 시스템� 본질�으로 있는 문맥 지�과 단어 분할 정보가 없기 때문�다. �런 난조�� 제약 없는 필기 글� �� 시스템� 몇 개 개발�었다. 1, 9, 11, 18, 15, 17 �들 시스템� 주로 추출한 특징� 종류와 한 줄� �� 전� 단어별로 분할�는 지 아닌지� 차�가 있다. �닉 마르코프 모형(HMM) 그리고 순환형 신경�과 HMM� 융합� �용한 분할 기반 방법� 예로 �� 1, 18과 15가 있다. 15� 실험� 단� 저�로부터 얻� ��터베�스를 가지고 수행한 반면 1, 18� 실험� 여러 저�� �료를 가지고 검사하였다. 16�서는 오프�� 필기체 단어 ��� 광범위하게 조사하였다.
한 줄� 초기� 분할하여 발�하는 오류를 피하기 위해 9�서는 분할� 하지 않는, 즉 한 줄 전체를 �� 모듈� 넘기는 방법� 제안한다. � 시스템� 단� 저�� 대해 검사�었고 통계� 언어 지�과 결합하여 유�한 �� 결과를 달성한다. 11� 저� 수백 명으로부터 제작하고 보다 � ��터베�스�서 검사�, 저�� 무관한 제약 없는 글� ��� 위한 발전� 시스템� 서술한다. 앞으로 나올 절�서 설명하는 시스템� 전처리와 특징 추출 방법� 약간 다른 비슷한 접근법� 사용한다. 그� �해 �서체 글� 모형, 즉 글� 종류별 HMM 집합과 통계� 언어 모형� 사용 � 아니� 특징 벡터� 선형 �별 분�(LDA)� �용한 결과� 조사한다.

3 �뭉치(corpus)
훈련과 ��� 위한 입력 ��터는 완전한 �어 문장 ��터베�스� �해 제공�고 ��� Lancaster-Oslo/Bergen �뭉치� 기반한다. 7 저� �립� � 아니� 다수 저�� 관한 실험� Bern 대학� IAM�서 수집한 필기 형태 10� ��터베�스를 사용하여 수행하였다. ��터베�스 전체는 다양한 글 범주(출� 글�, 종�, �기 설화, 픽션...)를 �함하고 500명 �� 저�� 1200개 �� 필기 형태로 구성�다. 우리는 250명 ��� 저�가 저� �립� 실험� 위해 제작한 범주 a..f� form과 여섯 저�가 다저��� �용하여 제작한 하위집합 c03� 사용한다.
우리� 시스템� 단� 저���서� �가하기 위해 Senior 15가 수집한 ��터베�스� 필기 서�으로� 실험� 수행했다. � ��터베�스는 한 저�가 쓴 25쪽으로 구성�며 웹�서 공개�으로 얻� 수 있다.1 � ��터베�스� 필기 양�들� 256 그레� 레벨� 사용하여 300dpi 해��로 스캔하였다. 그림 1� � ��터베�스� 예시가 있다.
1 ftp://svr-ftp.eng.cam.ac.uk/pub/data

4 전처리
필기 글�� �미지가 주어진 �태�서 먼저 전체 �미지� 기울임� �정하여 스�� �중 양�� 비정확한 배치나 글� 쓸 때 지��� "밀려남(drift)"� �한 오류를 바로잡는다. 따�서 �미지는 �진화� �미지� 수� 밀� 히스토그램� 최소 엔트로피를 가지기 전까지 회전�다. 4 � 전처리 단계를 IAM ��터베�스� 서��는 �용하지 않았는� 저�들� 양� 아래� � 번째 시트� �를 쓰�� 요청받았고 서� �체는 스��하면서 정확히 정렬�었기 때문�다.
글� 한 걸� � 처리하기 위해 ��� 줄� 추출하여야 한다. 그러기 위해 �미지를 필기 ��� 핵심 �역(core region)들 사�를 분리한다. 핵심 �역, 즉 �스트 ��� 위 베�스��과 아래 베�스�� 사�� �역� threshold를 �용하여 찾는다. threshold는 줄들� 핵심 �역� �하기 위해 필요한 전방foreground 픽셀들� 최소 개수를 나타낸다. � threshold는 �진화한 필기 �역� 수� 밀� 히스토그램� �용하여 Otsu� 방법 12를 �용하면 ��으로 결정�다. 그 다� 수� 투� 히스토그램�서 � 줄� 검� 픽셀� 개수가 축��고 �미지는 � 투� 히스토그램� minima를 따� 핵심 �역별로 나눠진다.
다양한 저�� 글씨체 때문� �� 작업� 단순화하기 위해 필기를 정규화한다. 특히 수� 위치, 기울임, 경사(slant)� �정� 전처리�서 중요함� 드러났다. 그 ��� 정규화는 필기� �기와 그레�레벨� 강�를 고려한다.
가� 글씨체가 한 줄�서� 확 바뀌는 것� �기를 얻어 우리는 � 줄� 수� 위치, 기울임, 경사를 국소�으로 �정한다. 따�서 � 행� 필기 조�segment들 사�� 공백� �색하여 분리�다. 믿� 만한 정규화 계수를 계산하기�는 너무 짧� 조�� 피하기 위해 threshold를 사용한다.
수� 위치와 기울임� 15� 서술� 접근법과 비슷한 선형 회귀(linear regression)를 �용한 베�스�� 측정법� �용하여 �정한 반면�, 경사� 계산� 가장�리edge 방향� 기반한다. 그러므로 �미지는 �진화�고 수� �-백과 백-� 전환� 추출하는� 수� stroke만� 경사 측정� 결정��다. canny edge detector를 �용하여 edge orientation �료를 얻고 �� 히스토그램� 누�한다. 히스토그램� �균� 경사�으로 쓴다.
필기� �기를 정규화하기 위해 � 줄� 극값(local extrema) 개수를 세고 줄� 너비와� 비율� 얻는다. 비례(scaling) 계수는 � 비율� 선형�� 비율� � 수� 글씨체는 � �아지기 때문�다.
마지막 전처리는 그레� 레벨� 정규화하여 다양한 펜과 배경색으로 �한 변화� 대처하는 것�다. �미지� 그레� 레벨 구간� 어�운 강�는 0� �고 �� 쪽� 255가 ��� 조정한다. �뭉치� 통��� 한 줄� �들 전처리를 �용한 결과가 그림 3� 나타나있다.

5 특징 추출
필기 줄� 전처리한 �미지는 특징 추출 단계� 입력 �료로 사용�다. sliding window 기법� 11� 설명하는 접근법과 비슷하게 �용한다. 우리� 경우 �미지� 높�와 열 네 개 �기� 창� �미지� 왼쪽�서 오른쪽으로 � 열씩 겹치면서 움��고 기하 추출� �� 추출한다.
sliding window� � 열�서 특징 7개를 추출한다. (1) �-백 변화 개수(windowed text image� �진화 �후), (2) 베�스��� 대한 강� 분�� �균 값 위치, (3) 최�단 글� 픽셀�서 베�스��까지� 거리, (4) 최하단 글� 픽셀�서 베�스��까지� 거리, (5) 최�단과 최하단 �스트 픽셀� 거리, (6) 최�단과 최하단 �스트 픽셀 사�� �균 강�, (7) 그 열� �균 강�. 특징 (2)-(5)는 core size, 즉 하단 베�스��과 �단 베�스��(극대값� 통한 line fitting으로 계산)� 거리� �해 정규화�어, 글씨 �기� 변�� 대해 �욱 굳건해진다. 그 후� 모든 특징� 윈�우� 네 열� 걸� �균화�다.
강� 분�� �균값� 변화 � 아니� 하단 contour와 �단 contour� 방향� 고려하기 위해 추가�으로 세 가지 방향성 특징� 계산한다. �� 즉 우리는 네 lower countour �, upper contour �, sliding window 내 �균값� 통해 줄들� 재고 선 방향들� (8), (9), (10) 특성으로 �� 사용한다. (뭔 소리) � 넓� temporal context를 고려하여 우리는 특징 벡터� � 성분마다 근사�� 수� 미분� 추가로 계산하고 결과로 20 차� 특징 벡터를 얻는다. (윈�우당 특징 10개, �함수 10개)
특징 벡터들� decorrelate하고 종류 분별력� 향�하기 위해 우리는 훈련 단계와 �� 단계�서 LDA를 통합한다. (cf. 6) �래 특징 표현� �차 변환하고 특징 공간� 차�� �차 줄�며 최�화한다. �차 변환 A를 구하기 위해 훈련 �료� �래스내 분산(within class scatter) 행렬 Sw와 �래스간 분산(between class scatter) 행렬 Sb를 �용하여 고유 벡터 문제를 해결한다. � 분산(scatter) 행렬들� 계산하여 � 특징 벡터� HMM �태와 함께 �름표를 붙여야 한다. 우리는 먼저 �반�� 훈련� 수행하고 훈련 �료들� �태를 기준으로 정렬한다. 분산 행렬� 구했으면 LDA 변환� 다� 고유 벡터 문제를 풀어 계산한다.



��와 ����는 ��−1��� 고유값과 고유벡터다. 차� reduction(경�?)� 가장 � m개 고유값� �하는 m개 고유 벡터만� 구하여 얻어진다. 모든 특징 벡터를 LDA 변환한 후�는 완전히 새로운 HMM 훈련� 수행�다.

6 통계� 모��과 ��
필기 글� ��� 위한 HMM� 구성, 훈련, 해�� ESMERALDA 개발 환경5� 제공하는 방법과 �구� 틀 안�서 수행�다. HMM� �반�� 설정으로서 우리는 512개� Gaussian mixtures with diagonal covariance matrice(� � 저� �립 시스템�서는 2048개)를 �함하는 공유 코드�� 있는 semi-continuous 시스템� 사용한다. 52개 글�, 10개 숫�, 12개 구�� 기호와 괄호, 공백 하나를 위한 기본 시스템 모형� 표준 Baum-Welch 재측정� 사용하여 훈련�다. 그 다� 한 줄 전체를 ��하기 위해 글� 모형� 대한 루프로 구성� conbined model� 사용�다. 가장 가능성 높� 글� 시퀀스가 표준 Viterbi beam- search를 �용하여 계산�다.
전처리�서 벌충할 수 없는 서로 다른 글씨체 사�� 변�� 고려하기 위해 우리는 13� 서술� 접근법과 비슷한, 다저�/저� �립� ��� 위한 글� �서체 모형� �용한다. �서체는 글� 하위 분류, 즉 특정 글�� 서로 다른 실현�다. �는 베�스�� 시스템과달리HMM��제서로다른글� 하위 분류를 모��하는 � 쓰임� 뜻한다. 글�별 하위 분류 개수와 �서체 HMM 개수는 휴리스틱으로 결정하는�, 가령 다저��� �용� 시스템�서 우리는 �서체 개수가 저� 수만� 있다고 가정한다. 초기화�서 훈련 �료는 �서체 HMM들� 임�로 선�하여 �름표를 붙�다. 훈련 �중 모든 글� 표본� 대해 해당하는 모든 �서체� 매개변수 재추정� 병렬 �용한다. 정합 가능성� 특정 모형� 매개변수가 현재 표본� 얼마나 강하게 �향받는 지를 결정한다. �서체 �름표가 유�하게 결정�지는 않기� � 절차는 soft vector quantization과 비슷하다.
부수�으로, 통계� 언어 모형� �� 과정� 통합�어 글� 시퀀스가 발�할 것 같� 정�� 추정� 제공한다. �� 작업� 목표는 주어진 ��터 x� 대하여 통합 통계 모형� 확률� 최대화하는 글� 시퀀스 �̂ 를 찾는 것�다.

�̂ = ��������(�)�(�|�)

위 ��서 P(W)는 글� 시퀀스 w� 언어 모형 확률�고 P(X|W)는 � 글� 시퀀스를 그 글� 모형� 따� 입력 ��터 x로서 관찰한 확률�다. 우리� 경우 absolute discounting과 backing-off for smoothing of probability distribution� �용한 바�그램 언어 모형� �용하였다. (cf. e.g. 3)

7 ê²°ê³¼
우리� 필기 �� 시스템� �가하기 위해 단� 저��, 다저��, 저� �립� �� �렇게 세 가지 실험� 수행했다. 표 1� �들 실험� 글� 오류율� 있다. 처� � 열� 실험 종류, 3열� 언어 모형� �용하지 않� 오류율, 4열� 바�그램 언어 모형� 글� 수준�서 �용한 결과다. 언어 모형� IAM ��터베�스� a..d 범주� 모든 글� 사용하여 �성하였고 실험 내내 �정하다. 표 2�는 어휘-free 단어 ��과 어휘 기반 단어 ��� 나타나있다.
단� 저�� 실험� Senior ��터베�스�서 훈련� 282줄, 검정� 141줄� �서 수행했는�, 글� 수준�서 검정 집합� 바�그램 perplexity는 15.3�다. 베�스�� 시스템� 오류율 13.3%는 바�그램 언어 모형� 채�하여 12.1%로 �소했다. LDA 변환한 특징 공간� 차�� 12로 내려갔지만 오류율� 그다지 커지지 않았다. 단� 저� 시스템� 단어 오류율(표 2)� 어휘 없� 28.5%, 1.5k 어휘가 있으면 10.5%다. � 결과들� 우리가 같� ��터베�스를 �용하여 literature(문학 작품� 아닌 것 같다)�서 얻� 오류율과 비��긴 하지만, 훈련 집합과 검정 집합� �기가 달� 비�하긴 어렵다. 17�서 오류율� 글�� 경우 28.3%, 어휘 없는 단어� 경우 84.1%, 1.3k 어휘가 있는 단어� 경우 16.5%다. 15� 보고�서 단어 오류율� 어휘가 있는 경우 6.6%, 어휘 free� 경우 41.1%다. 9�서 최고� 어휘 기반 단어 오류율� 15.0%다.
다저� 필기 �� 작업� 경우 IAM ��터베�스� 하위집합 c03�서 훈련� 440줄, 검정� 109줄� 사용하였다. � 줄들� 글씨체가 확연히 다른 저� 여섯�서 작성하였다. � 작업�서 LDA(12차�으로 경�)를 쓴 글� 오류율 14.2%는 �서체 모형(� 소문�� �서체 6개)� 추가로 사용하여 13.3%로 � �게 �소했다. 바�그램 언어 모형� 채�한 결과 오류율� 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%다. 저� �립� 경우 �서체 모형� 다저� 실험� 비해 별다른 향�� �루지 못했다. 오류율 31.3%는 글�당 �서체 3개를 �서 얻� 것�며 글�당 �서체 10개를 �서 실험했� 때 오류율(34.8%)과 �� �� 모� 하�하였다. 하지만 오류율� LDA 변환한 특징� �� 때 29.1%로 �게 �소했다. 언어 모형� 추가로 통합하여 글� 오류율� 22.2%로 �욱 개선�었다(검정 집합� perplexity는 12.0). �는 어휘를 쓰지 않았� 때 단어 오류율 60.6%와 대��다.

8 ê²°ë¡ 
우리는 분할 없는 오프�� 필기 글� ��� 위한 시스템� 소개하고 단� 저�, 다저�, 저� �립�� 관해 실험� 몇 개 수행해다. 어휘를 쓰지 않는 단어 기반 � 아니� 글� 수준�서� 유�한 �� 결과를 �루었다. �� 정확�는 베�스�� 시스템과 비�해 �당히 개선�었는�, 글� 수준�서 통계� 언어 모형� �용하고 다저�/저� �립� ���서 특징 공간� LDA를 수행한 결과다.
�� 정확�� 추가 개선, 특히 다저� ���서� 개선� �서체 글� 모형� �용하여 얻었다.

9 �사� �
� 연구는 프로�트 Fi799/1�서 German Research Foundation(DFG)가 제안하였다.
추가로 Bern 대학� Institute of Informatics and Applied Mathematics, 즉 Horst Bunke와 Urs-Viktor Marti�게 �사한다. �들� 우리가 필기 양� ��터베�스� IAM10� �� 실험� 쓰는 것� 허�하였다.

참고 문헌
1
2
...
18

Linear Algebra and Its Applications (4th ed.) by David C. Lay

제 2장 서론 ~ 2.3절
  • 보잉사ì�˜ ê³µë�Œì�´ë“¤ì�€ 3D 모ë�¸ë§�ê³¼ 계산유체역학ì�„ 사용하여 차세대 ìƒ�ì—… ë°� 군사용 비행기를 설계한다. ì�´ë“¤ì�€ 비행기 주변ì�˜ 기류를 시뮬레ì�´ì…˜í•˜ê³ ìž� ë°©ì •ì‹�ê³¼ 변수를 대략 200만개 í�¬í•¨í•˜ëŠ” ì�¼ì°¨ ë°©ì •ì‹�ì�„ 반복하여 푼다. ì�´ëŸ¬í•œ 거대한 ë°©ì •ì‹�계를 현실ì �ì�¸ 시간 ë‚´ì—� 풀려면 ë¶„í•  행렬(partitioned matrix)ê³¼ 행렬 ì�¸ìˆ˜ë¶„í•´(matrix factorization)ë�¼ëŠ” ê°œë…�ì�„ ë�„입해야 한다.
  • 가우스 소거법ì�„ ì�´ìš©í•œ 역행렬 구하기: [A I] -> [I A-¹]
  • íž�버트 행렬: 계산으로는 역행렬ì�„ 구하기 어렵다. 행렬ì�˜ 차수가 높아지면 행렬ì‹�ì�´ 급격히 작아진다.

Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:28:55
Processing time 0.0232 sec