효과적인 도서 목록 검색을 위한 개선된 OCR 알고리즘에 관한 연구
2011-06-03 CCTV뉴스
또한 인식부에서는 문자의 크기와 경사도, 부분 손실 등의 영상에 강인성을 갖는 바이큐빅 보간법을 적용하여 데이터 손실 복원과, 반자동 기울기를 갖는 입력 영상의 보정을 하였다. 모의실험 결과 기존 알고리즘 보다 인식률에서는 6%, 검색시간에서는 1.077초 더 우수함을 확인하였다.
최근 정보화 산업과 반도체 산업의 발전에 따라 초고속 통신기술, 컴퓨터를 기반으로 하는 멀티미디어 기술 등이 급속도로 발전함으로 인하여 정보의 콘텐츠(contents) 이용이 다양화되고 있다. 또한 사회 곳곳에서 인식의 변화로 과거에는 생각할 수 없었던 새로운 아이디어로 다방면에 걸쳐서 정보를 활용한 자동화 기능이 요구되어지고 있으며, 부분적으로 자동화 기능이 점점 늘어가는 추세이다.
인간의 생활과 업무를 편리하게 하기 위하여 인간과 컴퓨터가 정보를 주고받는 방법이 주로 컴퓨터 단말기와 키보드에 의존하고 있다. 이에 대표적으로 도서정보 검색기술은 아직까지도 키보드(keyboard)를 기반으로 하는 정보 검색으로 이루어지기 때문에 많은 시간을 투자하여 필요한 정보를 찾는다. 따라서 컴퓨터와 인간, 컴퓨터와 주변장치간의 정보전달을 손쉽게 하려는 노력의 일환으로 정지영상 및 동영상, 음성과 같은 멀티미디어 객체에 대한 자동인식 연구가 진행되고 있으며, 최근 비치된 도서들을 자동적으로 분류하고 관리하고자 하는 시스템의 개발은 사회적 요구 사항이 되고 있다. 그 중에서 가장 적합하고 올바른 접근 방법은 도서들의 제목 영역을 자동으로 추출하여 인식하는 방법이다.
2003년에 영상처리와 패턴인식을 이용하여 도서 영역 추출, 도서들 간의 제목 영역 추출, 도서들의 제목 영역 인식 순으로 통하여 도서 자동 위치 파악 시스템에 대해 논문을 기술하였다. 그러나 본격적인 실험이 수행되지 않아서 시스템 유용성을 입증하지 못하고, 특히 다양한 제목 정보에 대한 파악과 인식의 어려운 문제점이 존재하고 있다. 기존 문자 인식은 단순 조건에서 문자를 인식하였으며, 외부 잡음, 데이터 손실로 인한 낮은 화질, 기울어진 문자, 다양한 크기와 글씨체의 경우 인식률이 많이 떨어지는 단점을 가지고 있다.
이에 본 고에서는 기울어진 문자, 다양한 크기, 글씨체, 흐린 영상 등의 입력 영상에 대하여 문자 복원과 인식, 효율적이고 정확한 도서 검색을 하기 위하여 바이큐빅 보간법(bicubic interpolation)을 적용한 광학문자 인식 알고리즘을 제한하고자 한다.
본 고에서 적용한 광학문자 인식 알고리즘은 검출부와 인식부로 구성하고, 검출부에서는 복잡한 배경에서 정확한 도서 영역 검출을 위하여 로버츠 에지 연산자와 허도로프 거리 알고리즘을 적용하여 필요한 영역을 검출한다. 또한 인식부는 문자의 크기와 경사도, 부분 손실 등의 영상에 강인성을 갖는 바이큐빅 보간법을 적용하여 데이터 손실 복원과 반자동 기울기를 갖는 입력 영상의 보정을 통하여 인식률과 검색시간을 단축하는 도서 목록 인식 시스템을 구현한 후 모의실험을 통하여 성능을 비교분석하고자 한다.
도서 인식 시스템
도서 제목 영역 검출 알고리즘
가. 에지 연산자
에지 검출은 영상 인식의 기본적인 첫 단계로서 영상의 구성을 결정하기 위해 화소들을 하나의 영역으로 만들기 위해 사용한다. 본 고에서 도서의 특징을 정확하게 유지하고 검출 속도를 향상시키기 위하여 로버츠 연산자를 사용하였다.
도서 입력 영상을 이용하여 로버츠, 소벨, 프리윗, 캐니 에지 연산자의 연산속도는 표 1과 같고, 검출된 에지는 그림 1과 같다. 표 1은 10개 도서 입력 영상에 대상으로 각각 소벨, 로버츠, 프리윗, 캐니 연산자를 적용하였으며, 비교분석을 통해 로버츠 에지 연산자가 속도 측면에서 우수함을 확인할 수 있다.
허도로프 거리는 2차원 영상의 비교에 널리 사용되어진 거리 매칭 방법이며, 1993년 Huttenlocher 등에 의해서 이진 영상을 비교하기 위해서 제안되었다. 기본적으로 허도로프 거리 알고리즘은 기존 영상이 입력 영상에 존재하는지, 입력 영상의 어느 부분에 가장 잘 부합되는지를 검색하는데 사용되며, 매칭 거리가 작을수록 더 유사한 위치로 판단할 수 있다. 이러한 접근 방법은 계산량 측면에서 효율적이고, 잡음과 물체의 형태 변화에 강한 특성을 갖는다.
허도로프 거리 측정법은 큰 영상 내에 작은 영상이 존재하는지, 그리고 어디에 있는지 알아내고자 할 때, 첫 번째 단계는 두 영상으로부터 에지 점들을 찾아내는 것이다. 그렇게 함으로써 점, 선 또는 다각형들의 이진화된 에지 영상을 이용해서 작업할 수 있다.
본 고에서 에지 정보는 앞에서 논한 로버츠 연산자를 사용하여 얻는다.
두 점 a와 b사이의 거리를 d(a,b)=|| a-b|| 라고 할 때, 점 a와 유한 점 집합 B={b1,.....,bNb} 사이의 거리는 식 (1)과 같이 정의된다.
주어진 두 개의 유한 점 집합 A={a1,.....,aNb}와 B={b1,.....,bNb}에 대한 허도로프 거리는 식 (2)과 같다.
여기서 ||·||는 2차원 영상의 유클리안 놈(norm)이고 , h(A,B), h(B,A)는 두 집합 A와 B사이의 직접 거리를 나타낸다.
그림 2는 허도로프 거리 매칭 알고리즘의 적용 예로 (a)는 기존 영상, (b)은 입력 영상, (c)은 매칭 결과 영상이다. 즉, (a) 기존 영상이 (b) 입력 영상의 어느 부분에 가장 유사하게 매칭 되는지를 보여주는 그림으로 (c) 영상이 매칭 결과 영상이다.
도서 제목 인식 알고리즘
가. 바이큐빅 보간법
디지털 영상에서의 보간법은 화소 값을 보간하는 것을 뜻하며 주변의 화소들을 분석함으로써 새로운 화소를 생성한 것을 말한다. 이러한 방법은 영상처리와 컴퓨터 시각, 디지털 시스템의 포맷 변환 등의 여러 응용 분야에서 사용된다.
특히 원영상의 해상도와 사용되는 영상의 해상도가 틀릴 때 영상의 해상도를 원하는 대로 맞추어 주는 영상 확대 및 축소와 같은 응용분야에서 많이 활용되고 있다.
양선형 보간법은 대표적인 선형 보간법으로써 이러한 선형 보간법들은 거리에 반비례하는 선형적 가중치를 사용하여 뭉그러짐 현상을 일으킨다. 이 문제점을 개선하기 위해서 가중치를 단지 선형적으로 적용하는 것이 아니라 거리에 대한 3차 컨볼루션(convolution) 함수를 이용한다. 이러한 3차 컨볼루션 함수는 Rifman에 의해 처음 소개 되었으며 Simon과 Bernstein 등에 의해 개선되었다. 바이큐빅 보간법은 주변 값들과의 연관성을 고려한 방법으로 보간법 중에 매우 정확한 방법이다.
인접한 16개의 화소를 이용하며 모든 보간 함수들과 같은 원리에 의해 작업이 이루어진다. 계산해야 할 한 점은 중앙에 놓아지고 샘플 점들의 값들은 샘플들에 의해 곱해진 후에 모든 결과들의 합은 새롭게 형성되는 화소 값이 만든다.
1차원 바이큐빅 보간 커널(kernel) 함수는 식(3)으로 표현된다.
여기서 a=-0.5, -0.75, -1.0은 a를 위해 제안된 값들이고 그림 3은 a값에 따라 1차원 3차 컨볼루션 함수 곡선의 변화이다.
세 개 a값 중에서 시각적인 결과들에 대하여 보간 커널을 평가한다면 a=1.0,일 때 가장 좋은 선택이며 Bernstein은 a에 대한 준 강조 제약조건이다.
1981년 Keys은 Taylor 급수의 차수를 사용하여 정확히 하기 위해서 a가 -0.5이어야 한다고 수학적으로 증명하며 수식 (3)을 식 (4)로 제시하였다.
그림 4는 식 (4)에 의한 바이큐빅 보간함수이며, 그림 5는 2차원 영상의 바이큐빅 보간함수이다.
따라서 원 화소에 대한 보간 위치 s라면 4개 화소를 기준으로 각각 3차 방정식을 세워 구간 방정식을 구하고, 이를 이용하여 구간사이의 원하는 값을 찾아내는 방법으로 밑에 식 (5)를 수평, 수직 방향에 대하여 각각 적용한다.
그림 6은 식(5)을 이용하여 새로운 화소 값을 보간하는 과정을 설명한 것이다
본 고에서는 영상의 확대를 위해 바이큐빅 보간법을 사용하였다. 그림 7은 바이큐빅 보간법 영상에 적용한 결과를 보인 것이다.
그림 8은 원 영상을 4배 인수로 확대된 결과 영상의 히스토그램을 비교할 수 있으며, 그 중에서 원 영상 히스토그램과 제일 유사한 결과는 바이큐빅 보간법을 적용한 결과 영상의 히스토그램이다.
바이큐빅 보간법은 최소 거리 이웃 보간법과 쌍선형 보간법보다 더 좋은 화질을 얻으며 특히 연속적인 톤 영상의 크기를 조절할 때 가장 뛰어난 화질을 제공한다.
나. OCR 알고리즘
과거 광학문자 인식 알고리즘과 같은 오프라인 문자 인식에 있어 인식 과정에 비해 전처리 과정에 대한 연구가 비중 있게 다루어지지 못하였다. 하지만 전처리 과정 또한 인식단계와 같이 그 비중 또한 쉽게 간과해서는 안 된다. 문서 영상에서의 전처리는 문서 영상의 잡음과 왜곡 등을 제거하고, 인식의 대상이 되는 문자를 추출하는 과정으로 일정한 순서에 따라 진행되어야 한다.
보통 광학문자 인식 알고리즘을 이용한 문서 영상은 인식단계 이전에 이진화, 잡음제거, 문자분할, 정규화 등의 전처리 과정을 거친다.
문서 영상의 이진화는 입력 영상내의 문자 영역은 강조시키고 배경이나 음영은 비교적 포함되지 않도록 하는 것과 문서 영상의 해석이 빠른 속도로 이루어질 수 있게 하는데 목적을 두고 있다. 이진화는 그레이(gray) 영상을 0 또는 1의 이진 영상으로 변환하는 과정으로 인식을 하기 위하여 먼저 식 (6)을 이용하여 컬러(RGB)영상을 그레이 영상으로 변환하고, 이를 다시 0~255 단계로 구성된 그레이 영상을 이진(binary)영상으로 변환하여야 한다.
이진 영상으로 변환하는 방법은 문서 영상 전체에 대하여 전역적 임계값을 이용한 전역적 이진화 방법과 영상의 각 부분마다 임계값을 이용한 지역적 이진화 방법이 있다. 기본적으로 영상 전체의 평균을 임계값(threshold)으로 사용하는 전역적 이진화(global binarization) 방법에서 화소들의 밝기 분포 히스토그램에서 전경과 배경에는 큰 피크가 존재하는데, 이 두 피크 사이의 중간 값을 임계값으로 하여 식 (7)과 같은 이진화를 수행한다.
여기서 G(x,y), B(x,y)는 그레이 영상과 이진 영상을 의미하며, 임계값은 (첫 번째 피크+두 번째 피크)/2 이다. 문서 영상의 글자에 잡음이 섞이면 전혀 다른 글자로 인식되는 경우가 발생한다. 이러한 잡음이 글자의 한 부분인지 판단하여 글자부분이 아니라면 잡음을 제거해야 한다. 잡음제거를 위해서 기본적으로 평활화, 선형화, 저주파 통과 필터(low pass filter), 미디언 필터(median filter)등이 사용된다. 이들 잡음제거 방법 중 원영상의 강한 에지와 상세 한 부분을 보존하기 위해서는 미디언 필터가 효과적이다.
문서 구조 분석은 일반적인 문서나 특정한 형식의 문서에서 지식을 사용하여 문서 영상으로부터 문서의 기하학적인 구조를 추출하는 것이다. 즉, 문서를 단위 블럭의 집합으로 분할한 후, 각 블럭의 특성을 조사하여 문자 영역과 비문자 영역으로 분리하는 작업이다. 이러한 문서 구조 분석을 위하여 사용되는 방법은 일반적으로 투영 프로파일(projection profile)방법을 적용하거나 연결요소 분석(connected component analysis)방법 등을 적용한다. 연결요소 분석 방법은 임의의 흑(black) 화소 또는 백(white) 화소에 대하여 8방향 또는 4방향의 인접화소가 같을 경우 이 화소를 모두 연결하여 화소의 집합을 얻는다. 그림 영역은 연결 요소의 부피가 큰 반면에 문자 영역은 작고 일정한 크기의 연결 요소를 갖는다. 이 방법은 유사한 특성을 갖는 연결 요소를 만들기 위해 각 요소를 병합하는데, 연결 요소의 종, 횡비 등의 특징을 분석하여 음영을 제거하거나 필요한 영역을 추출할 수 있으며, 활자체나 문자 크기의 변화에 무관하게 임의의 방향에 위치한 문자 행을 분리할 수 있다. 그러나 계산량이 많이 필요하고 경험적 지식이 많이 사용되는 단점이 있다.
투영 프로파일은 투영축상의 흑색화소의 수를 계산함으로써 얻어지는 물결 모양의 윤곽으로 문서의 전역적인 특성을 나타내어 기울어진 문서의 교정이나 요소 추출, 그리고 문자 추출에 중요한 역할을 한다. 투영 윤곽의 값이 부분적으로 최소가 되는 지점을 문서 영역 분할의 기준으로 결정하는데, 대부분의 문서가 수직 또는 수평 방향의 블럭으로 구성되므로 반복적으로 적용할 경우 매우 효율적으로 각 영역을 분리할 수 있다.
마지막으로 문서 구조 분석을 통해 추출된 텍스트 영역은 인식 대상인 문자 단위로 분할하게 되는데, 분할된 문자의 가로, 세로의 크기는 일정하지 않으며, 분할된 문자를 일정한 형태로 만들기 위해 정규화 과정을 수행한다.
그림 9는 본 고에서 제안한 도서 제목 인식 시스템을 위한 전체 시스템 블록도이다. 본 고의 전체 구성은 그림 9와 같이 먼저 도서 목록 영상 데이터베이스 안에는 입력 영상과 기존 영상에 대한 로버츠 연산자를 적용하여 에지 특징 점들을 검출하였다. 다음은 이 특징 점들을 갖는 두 에지 영상에 대한 허도로프 거리 알고리즘을 이용하여 매칭 시켜 도서 목록 영역을 정확하게 검출하였다. 검출한 결과 영상에 대한 확대된 영상을 보간하기 위해서 바이큐빅 보간 알고리즘과 기울기 교정하기 위한 로테이션 적용하였고 이진화, 잡음 제거, 문자 분할, 정규화 순서로 도서 목록을 정확하게 인식하였으며, 인식한 결과는 마지막으로 메모장에 출력된다.
실험
제안된 도서 제목 인식 시스템은 성능 평가를 위해 원광대학교 도서관에서 영상의 크기나 해상도 등에 상관없이 자연스럽게 도서제목이 첨가된 임의의 100개 도서영상을 대상으로 하였으며, 모의실험은 Matlab 7.0을 이용하여 수행하였다.
그림 10은 로버츠 에지 연산자와 허도로프 거리 알고리즘을 적용하여 도서 영역을 검출한 결과 영상이다.
실험을 통해 표 2의 결과를 나타내었다. 표 2의 결과에서 보이듯 제안한 도서 제목 검출 및 인식 알고리즘을 적용한 시스템이 기존의 인식률에서 6% 우수함과 처리 시간에서도 평균 1.077초 향상됨을 보였다.
최종적으로 제안된 알고리즘은 MATLAB GUI를 이용하여 도서 제목 인식 시스템을 구현하였다. 그림 11은 구현된 도서 문자 인식 시스템의 GUI 영상으로 템플릿 영상 버튼을 누르면 로버츠 에지 연산, 허도로프 거리, 바이큐빅 보간, 문자 분할 영상과정을 단계별로 확인할 수 있다.
그림 11의 (a)는 도서 제목 인식과 다시 한 번 텍스트 워드 창을 통해 확인할 수 있는 초기 화면이고, (b)는 원 영상, (c)은 바이큐빅 보간, 기울기 교정과 이진화 (d)는 최종 문자 인식 결과 영상이다.
제안한 시스템은 복잡한 배경에서도 정확한 도서 영역 검출과 처리 속도를 향상시키기 위해 로버츠 연산자와 허도로프 거리 알고리즘을 적용하였고, 인식단계에서는 잡음, 문자 복원, 흐림 영상을 복원하기 위해 바이큐빅 보간법을 제시하였다.
또한 기울어진 글자 영상을 수평으로 반자동 교정 후 정확한 인식을 위한 OCR 알고리즘을 적용한 결과 그림10과 같이 정확히 인식함을 확인하였으며, 표 2의 결과와 같이 기존 알고리즘보다 인식률 면에서 6%, 속도 면에서 1.077초 향상되었음을 확인하였다.
향후 연구에서는 실시간 도서 검색, 자동 기울기 교정, 다중문자 인식이 가능하도록 하기위한 지능로봇에 대한 연구가 필요할 것으로 사료된다.