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, 1815HMMs 방법을 사용하는 텍스트 분리에 기반을 둔 방법과 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.0694 sec