2012/11/16 ¶
- 「Experiments in Unconstrained Offline Handwritten Text Recognition」 번역
- 다음 주까지 1학년 1학기에 배운 Linear Algebra and Its Applications의 1.10, 2.1, 2.2절 번역하기
Experiments in Unconstrained Offline Handwritten Text Recognition(제약 없는 오프라인 필기 글자 인식에 관한 실험) ¶
초록
오프라인 필기 글자 인식을 위한 시스템을 소개한다. 이 시스템의 특징은 분할이 없다는 것으로 인식 모듈에서 한 줄을 통째로 처리한다. 전처리, 특징 추출(feature extraction), 통계적 모형화 방법을 서술하고 저자 독립, 다저자, 단일 저자식 필기 인식 작업에 관해 실험하였다. 특히 선형 판별 분석(Linear Discriminant Analysis), 이서체(allograph) 글자 모형, 통계적 언어 지식의 통합을 조사하였다.
오프라인 필기 글자 인식을 위한 시스템을 소개한다. 이 시스템의 특징은 분할이 없다는 것으로 인식 모듈에서 한 줄을 통째로 처리한다. 전처리, 특징 추출(feature extraction), 통계적 모형화 방법을 서술하고 저자 독립, 다저자, 단일 저자식 필기 인식 작업에 관해 실험하였다. 특히 선형 판별 분석(Linear Discriminant Analysis), 이서체(allograph) 글자 모형, 통계적 언어 지식의 통합을 조사하였다.
1 서론
필기 글자 인식은 패턴 인식의 도전적인 분야다. 지금까지의 오프라인 필기 인식 시스템들은 대부분 우편 주소 읽기나 은행 수표 같은 형식을 처리하는 데 적용되었다. 14 이들 시스템이 개별 글자나 단어 인식에 한정된 반면 제약 없는(unconstrained) 필기 글자 인식을 위한 시스템은 거의 없다. 그 이유는 이러한 작업이 크게 복잡하기 때문인데 글자 또는 단어의 경계에 대한 정보가 없는 데다 헤아릴 수 없을 정도로 어휘가 방대한 것이 특징이다. 그럼에도 필기 글자 인식 기법을 더 조사하는 것이 가치 있는 이유는, 계산 능력이 향삼함에 따라 더욱 복잡한 처리를 할 수 있기 때문이다.
본 논문에서는 은닉 마르코프 모형에 기반한, 어휘(lexicon)-free 오프라인 필기 인식 시스템을 소개하고 완전한 영어 문장 데이터베이스에 관한 몇 가지 실험을 저자 독립식 그리고 대조를 위해 다저자, 단일 저자식으로 수행했다. 전처리와 특징 추출 방법을 소개하고 이에 더해 선형 판별 분석, 이서체 글자 모형의 사용, 통계적 언어 모형 같은 더욱 정교한 기법들을 조사한다. 그 뒤의 절에서는 오프라인 필기 인식에 대한 관련 작업들을 짧게 검토한다. 우리가 사용한 데이터베이스는 3절에서 소개한다. 그 다음 전처리, 특징 추출 방법, 통계적 모델링과 인식을 위한 기법을 설명한다. 평가 결과는 제안한 방법의 효율성을 입증하기 위해 7절에서 소개한다.
필기 글자 인식은 패턴 인식의 도전적인 분야다. 지금까지의 오프라인 필기 인식 시스템들은 대부분 우편 주소 읽기나 은행 수표 같은 형식을 처리하는 데 적용되었다. 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)을 적용한 결과도 조사한다.
최근 몇 년간 오프라인 필기 인식 분야는 상당히 진전하였다. 특히 우편 주소나 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에 각 데이터베이스의 예시가 있다.
1ftp://svr-ftp.eng.cam.ac.uk/pub/data
훈련과 인식을 위한 입력 데이터는 완전한 영어 문장 데이터베이스에 의해 제공되고 각각은 Lancaster-Oslo/Bergen 말뭉치에 기반한다. 7 저자 독립식 뿐 아니라 다수 저자에 관한 실험을 Bern 대학의 IAM에서 수집한 필기 형태 10의 데이터베이스를 사용하여 수행하였다. 데이터베이스 전체는 다양한 글 범주(출판 글자, 종교, 인기 설화, 픽션...)를 포함하고 500명 이상 저자의 1200개 이상 필기 형태로 구성된다. 우리는 250명 이상의 저자가 저자 독립식 실험을 위해 제작한 범주 a..f의 form과 여섯 저자가 다저자식을 적용하여 제작한 하위집합 c03을 사용한다.
우리의 시스템을 단일 저자식에서도 평가하기 위해 Senior 15가 수집한 데이터베이스의 필기 서식으로도 실험을 수행했다. 이 데이터베이스는 한 저자가 쓴 25쪽으로 구성되며 웹에서 공개적으로 얻을 수 있다.1 두 데이터베이스의 필기 양식들은 256 그레이 레벨을 사용하여 300dpi 해상도로 스캔하였다. 그림 1에 각 데이터베이스의 예시가 있다.
1ftp://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에 나타나있다.
필기 글자의 이미지가 주어진 상태에서 먼저 전체 이미지의 기울임을 교정하여 스캐닝 도중 양식의 비정확한 배치나 글을 쓸 때 지속적인 "밀려남(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 변환은 다음 고유 벡터 문제를 풀어 계산한다.
필기 줄을 전처리한 이미지는 특징 추출 단계의 입력 자료로 사용된다. 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𝑆𝑏𝐴𝑇𝜓𝑖(𝑖=1,2,...,𝑚)
𝜇𝑖와 𝐴𝑇𝜓𝑖는 𝑆𝑤−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에 대하여 통합 통계 모형의 확률을 최대화하는 글자 시퀀스 𝑤̂ 를 찾는 것이다.
필기 글자 인식을 위한 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%와 대응된다.
우리의 필기 인식 시스템을 평가하기 위해 단일 저자식, 다저자식, 저자 독립식 인식 이렇게 세 가지 실험을 수행했다. 표 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를 수행한 결과다.
인식 정확도의 추가 개선, 특히 다저자 인식에서의 개선을 이서체 글자 모형을 적용하여 얻었다.
우리는 분할 없는 오프라인 필기 글자 인식을 위한 시스템을 소개하고 단일 저자, 다저자, 저자 독립식에 관해 실험을 몇 개 수행해다. 어휘를 쓰지 않는 단어 기반 뿐 아니라 글자 수준에서도 유망한 인식 결과를 이루었다. 인식 정확도는 베이스라인 시스템과 비교해 상당히 개선되었는데, 글자 수준에서 통계적 언어 모형을 적용하고 다저자/저자 독립식 인식에서 특징 공간의 LDA를 수행한 결과다.
인식 정확도의 추가 개선, 특히 다저자 인식에서의 개선을 이서체 글자 모형을 적용하여 얻었다.
9 감사의 말
이 연구는 프로젝트 Fi799/1에서 German Research Foundation(DFG)가 제안하였다.
추가로 Bern 대학의 Institute of Informatics and Applied Mathematics, 즉 Horst Bunke와 Urs-Viktor Marti에게 감사한다. 이들은 우리가 필기 양식 데이터베이스인 IAM10을 인식 실험에 쓰는 것을 허락하였다.
이 연구는 프로젝트 Fi799/1에서 German Research Foundation(DFG)가 제안하였다.
추가로 Bern 대학의 Institute of Informatics and Applied Mathematics, 즉 Horst Bunke와 Urs-Viktor Marti에게 감사한다. 이들은 우리가 필기 양식 데이터베이스인 IAM10을 인식 실험에 쓰는 것을 허락하였다.
Linear Algebra and Its Applications by David C. Lay ¶
제 2장 서론 ~ 2.3절
- 보잉사의 공돌이들은 3D 모델링과 계산유체역학을 사용하여 차세대 상업 및 군사용 비행기를 설계한다. 이들은 비행기 주변의 기류를 시뮬레이션하고자 방정식과 변수를 대략 200만개 포함하는 일차 방정식을 반복하여 푼다. 이러한 거대한 방정식계를 현실적인 시간 내에 풀려면 분할 행렬(partitioned matrix)과 행렬 인수분해(matrix factorization)라는 개념을 도입해야 한다.
- 가우스 소거법을 이용한 역행렬 구하기: A I -> I A-¹
- 힐버트 행렬: 계산으로는 역행렬을 구하기 어렵다. 행렬의 차수가 높아지면 행렬식이 급격히 작아진다.
- 이렇게 별로하면 돼. -김태진
