이 포스트는 2012년에 출판된 'Guide to OCR for Arabic Scripts'라는 책의 4번째 챕터인 'Pre-processing Issues in Arabic OCR'의 내용을 요약한 것입니다. 문자 탐지 및 인식 과정에서 모델에 입력되는 이미지에 불필요한 잡음들을 제거하여 가독성이 좋게 만들어주는 전처리에 대한 내용이라고 할 수 있겠습니다. 제목에는 아랍어(!)가 포함되어 있어서 꼭 아랍어에 최적화된 기법들인 것 같지만, 아랍어의 몇 가지 특징(읽는 순서; 문자들이 이어진 경우가 많음; 점과 같이 작은 획이 단어의 의미에 중요)을 언급한 부분만 제외하면 다른 언어들에도 유용하게 적용될 수 있는 일반적인 문서 이미지 전처리 방법들을 다루고 있어서 소개해보고자 합니다.
Introduction
문서 이미지에서 OCR을 하는 일련의 과정에서, 가장 큰 장애물은 스캐너입니다. 스캔 시 종이를 밀착하지 않아서 생겨나는 clutter noise 및 어두운 배경, 스캐너에 내장된 구닥다리 이진화 알고리즘으로부터 발생하는 salt-and-pepper 등 다양한 잡음들이 스캐너에서 발생합니다. 이외에도 문서에 밑줄(rule-line)이 이미 프린트 되어있는 상태에서 그 위에 손글씨를 쓰는 바람에 획이 겹쳐진 문자, 문서에 포함된 로고, 그래픽 등도 OCR을 어렵게 하는 요인들입니다.
각각의 방법들에 대해서는 어느 정도 필터링을 통해 해결할 수 있지만, 이러한 문제들이 전부 혼재되어 있는 문서는 인식 결과가 만족스럽지 않습니다. 여기서는 이를 해결하기 위해서 인식 이전에 적용할 수 있는 세 가지 전처리 태스크를 다룹니다:
- 흑백 이미지의 가독성 및 이진화 적용을 위한 이미지 처리
- 이진 이미지의 자동 OCR을 위한 이미지 처리
- 손글씨 이진 이미지의 줄 분리
Pre-processing for Grayscale Images
Motivation
그레이스케일 이미지에서 글자를 추출해내기 위해서는 이진화를 하여 배경과 전경을 분리해내야 합니다. 하지만 이 이진화 과정에서 배경 intensity의 변화가 이미지 전체에 걸쳐 심하게 나타나는 경우에는, 각 영역마다 다른 threshold 값을 적용하는 adaptive thresholding을 적용한다 해도 가독성이 좋은 결과를 얻어내기 쉽지 않습니다. 이상적인 결과를 위해서라면 각 영역의 전경과 배경의 intensity 곡선에 따라 threshold 값이 계속해서 달라져야겠지만, 일반적으로 사용하는 adaptive thresholding 알고리즘에서는 이를 고려하는 것이 불가능합니다.
Methodology
위의 문제를 해결하기 위해서 문서의 배경을 상수가 아닌 위치에 따라 변하는 값으로, 즉 위치에 따른 함수로 모델링한 후에 이를 임계치로 하여 이진화합니다. 배경 모델링에는 선형 모델과 비선형 모델을 각각 사용할 수 있습니다.
그레이스케일 이미지 내 각 픽셀의 값을 z 방향 값으로 생각하여 모든 픽셀의 값을 3차원 좌표로 표현하여 흰색이 255, 검정색이 0의 값을 갖도록 합니다. 가장 먼저 배경과 전경을 대충 분리해내기 위해 상수 K를 정해서 thresholding하면, K보다 더 밝기가 낮은 글자 영역이 제거되게 됩니다. 즉, z=K의 평면을 가정하고 그보다 큰 z값을 지닌 픽셀들만을 남기는 것인데, 이렇게 남은 픽셀들을 residual이라고 합시다.
위의 그림은 residual에서 제거된 글자 부분들을 흰색으로 채운 결과입니다. Threshold 값을 넘는 전경이나 넘지 못하는 배경 값이 군데군데 있어서 글씨를 알아볼 수 있는 수준으로 깔끔하게 분리가 되지 않았기 때문에, 추가적인 터치가 필요합니다. 이후의 과정들에서는 residual 이미지를 일차적인 배경의 분포로 보고, residual 이미지를 가장 잘 근사하는 평면, 혹은 곡면을 찾아내게 됩니다.
- Background Separation by Linear Approximation
먼저 배경을 선형함수(평면)로 근사하는 방법을 생각해볼 수 있습니다. 배경을 나타내는 residual 이미지를 m*n의 작은 영역으로 나눈 뒤, 나눠진 각 로컬 영역에서 다음의 목적함수를 최소화시키는 A, B, D를 찾으면, 배경을 가장 잘 근사할 수 있는 배경 평면 Ax+By-z=0을 얻게 됩니다.
- Background Separation by Nonlinear Approximation
두 번째로는 평면 대신 residual의 굴곡을 모두 살린 비선형 함수를 이용해서 배경을 근사하는 방법이 있습니다. 비선형 근사는 평면이 아닌 스캔선(scanline) 단위로 이루어집니다. 아래의 문서 이미지의 붉은 점선인 스캔선을 따라 검정 픽셀의 intensity를 히스토그램으로 표현한 것이 그래프의 회색 막대입니다. 이 회색 막대들을 보면 실제로 글자가 있는 부분들에서는 주변과 확연히 구별될정도의 peak이 나타나며, 큰 분산 값을 갖습니다. 반대로 배경 영역에서는 대체로 분산이 낮은 편입니다.
그래프의 붉은 실선은 스캔선을 따라 측정한 평균입니다. 스캔선을 왼쪽에서 오른쪽으로 옮겨가면서 스캔선 intensity의 평균을 계산하고, 스캔선 위 각 픽셀 위치의 값이 평균보다 낮은 값만을 기록하여 배경의 매우 대략적인 근사치를 얻을 수 있습니다. 이를 selected and estimated background (SEB)라고 부릅시다.
이 SEB에서 더 세밀한 배경을 얻기 위해서 moving window를 이용합니다. 간단하게는 window 내 영역의 SEB 평균 값을 구해서 배경으로 사용할 수도 있고, 혹은 window 내 모든 픽셀의 값을 이용해서 최소자승거리 (min-square distance)를 갖는 line segment를 구한 뒤에 모든 window의 line segment들을 이어서 배경선을 추정할 수 있습니다.
이렇게 계산한 배경 값을 z라고 할 때, 원래의 그레일스케일 이미지는 다음과 같이 표준화될 수 있습니다. c는 255에 가까운 상수입니다. (*히스토그램에서 유추할 때, z를 구할 때 이미 반전된 값을 사용했기 때문인 것으로 보입니다.)
Experiment
상술한 방법을 이용해서 배경을 제거해본 결과는 다음과 같습니다. 아래 이미지 중 왼쪽은 원래의 이미지에서 global threshold를 적용하여 이진화한 이미지, 가운데 이미지는 제시한 방법을 이용하여 전처리한 이미지, 오른쪽은 전처리한 이미지를 왼쪽 이미지와 동일하게 global thresholding한 결과입니다. 균일하지 못한 배경이 잘 제거되어 육안으로 글자 식별이 가능하도록 이진화 처리된 것을 확인할 수 있습니다.
컬러 이미지에서도 동일한 방법으로 배경을 억제할 수 있습니다. 아래 그림에서 결과를 확인해볼 수 있는데요, 왼쪽 위는 원래의 이미지, 왼쪽 아래는 전처리하여 배경이 제거된 이미지, 오른쪽 위는 이를 이진화한 결과입니다.
Pre-processing for Binary Document Images
Clutter Noise
Clutter noise는 보통 스캔 과정에서의 문제로 발생하는 것으로, 문서를 관통하는 검은 줄 혹은 문서 가장자리 영역의 어두운 부분을 뜻합니다. Clutter noise의 제거는 여러 해상도로 다운샘플된 이미지에서 clutter noise에 해당하는 부분을 추출하여 bias 레이어로 만든 뒤, 해당 영역을 원본 이미지에서 제거하는 방식으로 이루어집니다.
Bias는 n*n 크기의 윈도우를 슬라이딩 해가면서 찾아내게 되는데, 해당 윈도우 내의 모든 픽셀이 전부 0이면 윈도우의 중심값도 0, 그렇지 않으면 1의 값을 적용합니다. 이렇게 하면 clutter noise의 영역의 전부 0으로 채워지게 되고, 글자 획이나 전경에 해당하는 bias의 픽셀은 윈도우가 전부 0으로 채워져 있지 않을 것이므로 1이 됩니다.
아래 그림은 clutter noise의 제거 예시입니다. 원본 이미지를 가운데 이미지의 사이즈로 다운샘플한 뒤, 제시한 방법을 이용해서 bias 영역만 추출합니다. 그 후 bias를 원본 이미지로 리사이즈해서 제거하면, 아래 그림과 같이 제거된 결과를 얻을 수 있습니다.
Pepper Noise
Pepper noise는 전경 텍스트에 포함되지 않는데 검정색으로 표시되는 픽셀 부분들을 뜻합니다. 일차적으로 텍스트 영역이 아닌 곳의 pepper noise들은 median filter 등을 이용해서 쉽게 제거할 수 있습니다. 이후 텍스트 영역에 존재하는 pepper noise들을 제거하기 위해서는 먼저 모폴로지 연산(morphology operator)을 이용해 텍스트 마스크를 생성합니다.
이 때 생성된 마스크 이미지에는 없으나 원본 이미지에는 있는 없는 검은 픽셀들은 노이즈 후보로 보고, 마스크 이미지 상에서 노이즈 후보의 local window 영역에 포함된 검은 픽셀의 갯수를 셉니다. 만약 마스크 이미지에 검은 픽셀이 없다면 해당 노이즈 후보는 진짜 잡음인 것으로 보고 제거합니다. 검은 픽셀이 포함되어 있는 경우에는 이 검은 픽셀들의 밀도를 고려해서 0과 255 사이의 어떤 값으로 설정합니다. 이렇게 모든 노이즈 후보에 대해서 연산을 마치면 그레이스케일 이미지를 얻을 수 있는데, 이를 다시 이진화하면 pepper noise가 제거된 형태의 이미지를 얻을 수 있습니다.
아래 그림은 위의 제시한 방법을 이용해서 pepper noise를 제거한 예시입니다. 제일 위의 원본 이미지에서 중간에 있는 텍스트 마스크 이미지를 얻은 뒤, 둘 사이의 픽셀 밀도를 비교해서 잡음을 제거하면 제일 밑에 있는 결과 이미지를 얻을 수 있습니다.
Rule-Lines
대부분 스캔한 이미지들에서는 비스듬히 그어진 rule-line들을 가지게 되기 때문에, 흔히 떠올릴 수 있는 projection profile로부터 위치를 알아내기 쉽지 않습니다. 더군다나 아랍어와 같이 글자 획이 rule-line을 따라 누워있는 경우가 많아 rule-line을 제거했을 때 겹쳐진 영역의 글자 획도 같이 날아갈 확률이 높은 언어들에서는 더 치명적인 문제가 됩니다.
Salt Noise or Holes
Salt noise는 이진화나 여타 잡음 제거 시 발생하는 현상으로, 다른 전처리 후 가장 마지막에 제거합니다. Salt noise 제거시에는 글씨 획의 비어있는 부분을 채우고 얇은 획을 강화하기 위한 region growing approach를 사용합니다.
전경에 속하는 검정 픽셀에 정방형의 deformable filter를 위치시키고, 양옆으로 형태를 변형시켜서 평행사변형 형태의 필터 내부 영역에 검정 픽셀이 가장 많이 포함되도록 합니다. 해당 영역에서는 행이나 열 단위로 흰색으로 비어있는 부분들을 채웁니다. 이 과정은 저자의 다른 논문 'Character image enhancement by selective region-growing' (1996)에서 찾을 수 있습니다.
이렇게 이미지 내 모든 픽셀들이 커버될 때까지 반복하면 다음과 같이 획이 강화된 글자 이미지를 얻을 수 있습니다.
Text Line Separation
Motivation
실질적인 문자 인식 결과는 텍스트의 영역, 특히 줄글을 이미지로부터 얼마나 잘 분리하느냐에 달려 있습니다. 하지만 문서 이미지, 특히 손글씨로 쓰여진 문서 이미지 text line을 추출하는 것은 다음과 같은 요인들 때문에 쉽지 않습니다:
- 각 라인들이 각기 다른 방향성을 지님. 심지어 하나의 라인 내에서도 단어마다 다른 방향으로 진행
- 글자 라인의 간격의 일정하지 않은 편
- 위아래로 인접한 글자 라인들이 서로 접촉하는 경우도 존재
- 작은 symbol들이 존재 (아랍어)
텍스트 라인의 패턴은 해상도가 낮은 이미지에서 더 구별하기 쉽기 때문에, 입력 이미지를 다운샘플하여 시작합니다.
ALCM Using Steerable Filter
ALCM (Adaptive Local Connectivity Map)은 마스크 내의 모든 intensity 값을 합치는 컨볼루션 연산을 적용한 결과로, 다운샘플된 이미지에 steerable directional filter를 적용해 ALCM을 추출하면 ALCM에서는 로컬에서 픽셀들이 해당 필터 방향으로 어떻게 연결되어 있는지 보여줍니다. 아래는 steerable filter가 텍스트 라인에 어떻게 반응하는지를 나타낸 것인데, 오른쪽과 같이 텍스트의 진행 방향으로 장축이 정렬된 필터는 왼쪽과 같이 다른 방향으로 위치한 필터에 비해 더 큰 값을 가지며, 더 연결성 (connectivity)이 강하다는 것을 뜻합니다.
이를 수식으로 표현하면 다음과 같습니다.
이러한 ALCM 변환은 여러 방법을 통해서 할 수 있는데요, 여기서 사용한 방법은 다음과 같습니다. 먼저 전경이 배경보다 높은 값을 갖도록 이미지를 반전한 뒤, 사이즈를 각 방향에 절반으로 다운샘플 합니다. 필터의 장축 a는 옆으로 위치한 단어들을 커버할 수 있도록 충분히 크게 (실험 결과 텍스트 높이의 약 5배), b는 텍스트의 높이보다 약간 작게 설계합니다. 이 실험에서 각도의 범위는 수평, +-1/10, +-1/20의 값을 사용했습니다. 결과로 얻어진 ALCM은 [0, 255]의 범위로 재조정합니다.
Location of Text Lines
여기서는 텍스트 라인의 영역을 파악하기 위한 마스크를 생성합니다. ALCM에서 높은 픽셀 값은 (반전한 상태에서 컨볼루션을 했으므로) 해당 위치에 텍스트가 더 밀집해있다는 것을 뜻합니다. 따라서 ALCM에서 다시 이진화를 통해 텍스트 영역에 속할 확률이 높은 픽셀과, 배경일 확률이 높은 픽셀을 분리해낼 수 있습니다. 이진화에는 Otsu's method를 로컬마다 분리해서 적용합니다. 이 결과로 전경에 해당하는 영역들이 뭉쳐져 있는 결과를 얻을 수 있으나, 완전히 텍스트 라인으로 만들기 위해서는 추가적인 필터링이 필요합니다.
먼저 텍스트가 아닐 확률이 높은 작은 조각 마스크들을 제거합니다. 그리고 텍스트 마스크 영역의 위쪽, 아래쪽 경계 프로파일을 결정한 뒤, 해당 경계 내부에 하얗게 비어있는 픽셀들을 전부 검정색으로 채웁니다. 여기까지 했을 때 대부분의 경우에는 텍스트 라인을 완전히 커버하는 마스크를 얻을 수 있지만, 한 라인이 몇 개의 조각들로 이루어져 추가적인 grouping이 필요한 경우도 있습니다. 이러한 경우에는 horizontal alignment에 기반하여, 인접한 부분들이 하나의 라인을 형성하기에 너무 긴지 아닌지를 판별하여 병합합니다. 최종적으로 각 이어진 부분들은 텍스트 라인을 완전히 커버하는 마스크가 됩니다.
Extraction of Text Lines
마지막으로 텍스트 라인 마스크를 이용해서 실제 텍스트 라인 영역을 검출합니다. 이진화된 ALCM에서 이어진 부분들을 grouping해서 얻은 마스크를 실제 텍스트 라인을 위한 마스크로 사용합니다.
마스크를 원래 이미지의 크기로 upsample한 뒤, 원본 이미지에 중첩해서 마스크와 겹치는 원본 이미지의 글자 영역을 그루핑하고, 마스크와 겹치지 않는 글자 영역들은 가장 가까운 그룹에 편입시킵니다. 만약 텍스트가 하나 이상의 마스크와 접한다면, 이는 여러 라인들에 속한 글자들, 혹은 서로 접한 글자들을 나타내는 것일 수 있습니다. 이러한 글자들을 분리하기 위해서는 별도의 분리 알고리즘 (splitting algorithm)을 적용해야 합니다.
Experiment
아래의 그림은 원래의 문서(왼쪽)에 steerable ALCM을 적용(오른쪽)한 예시입니다. 글씨가 있는 부분은 인접한 글씨와 합쳐지면서 강화되고, 특히 텍스트 라인이 수평 방향으로 정렬되어 있지 않음에도 불구하고 line을 따라서 강화된 특징이 나타나는 것을 확인할 수 있습니다.
이 결과는 동일 저자들의 다른 논문 'Text extraction from grayscale historical documents' (2005)에서 발췌한 결과로, 동일하게 ALCM을 통해 text line을 검출했으나 steerable directional filter 대신 직사각형으로 고정된 필터를 사용했습니다. 더 간단한 버전임에도 불구하고 좋은 결과를 보이는 것을 확인할 수 있습니다.
Conclusions
문서 이미지의 가장 큰 장점은 이미지의 컨텍스트와 관계없이 추출해야 하는 것이 명확하며, 이진화를 잘 할 경우 인식이 훨씬 수월해진다는 점인 것 같습니다. 실제로 문서 이미지를 인식하면서 가장 어려운 것 중 하나가 스캔, 팩스를 거치면서 이미지에 누적된 잡음들이었는데, 이러한 잡음들은 이진화를 했을때 더 두드러지기 때문에 다루기 쉽지 않았습니다. 이 챕터에서는 다양한 heuristic들을 이용해서 이를 제거하는 방법을 보여주고 있기 때문에, 이러한 전처리를 한 이미지에서 문자 인식을 시작한다면 더 좋은 인식 결과를 얻을 수 있을 것입니다.
Share article