사전학습된 OCR 모델 앱에서 후처리만 잘 하면 종이 표를 파일로 추출할 수 있을까? (feat. real-time OCR)

그림 1-1. 체리피킹된 데모영상	그림 1-2. 약간 문제가 있는 데모영상

실시간 OCR과 규칙기반 표 파싱 알고리즘을 통해 인쇄된 표 문서를 파일(.csv)로 추출하는 iOS POC 앱(Excel Scanner)을 제작하였습니다. OCR은 딥러닝 모델을 사용했을텐데, 애플과 구글의 비전 프레임워크를 활용하여 직접 모델을 학습하지 않고도 좋은 성능의 OCR을 활용할 수 있었고, OCR의 결과를 잘 가공하는 표 파싱 알고리즘을 규칙기반으로 제작하였습니다. 이 글에서는 미리 학습된 온디바이스 머신러닝 모델을 활용하여 구축했던 전반적인 프로세스를 소개, 규칙기반 알고리즘이 동작하는 방식 소개, 각 프레임워크를 비교하기 위해 살펴봤던 관점과 간단한 실험내용을 정리하였습니다.

배경

아직도 많은 사무직 종사자들은 인쇄된 표를 직접 타이핑하여 전산화시키는 작업을 하고 있습니다. 최근 책이나 종이 문서의 글자를 추출하여 PDF로 만들어주는 OCR 활용 앱이 많이 등장했고[1][2][3] 앱스토어상에서 높은 별점으로 생산성 향상을 암묵적으로 인정받을 만큼 발전해왔지만, 표를 자동으로 추출하는 기술은 MS의 엑셀 앱[4]을 제외하면 일반인이 사용하기에 실용적인 앱이 많이 없는 것이 현실입니다.

이러한 배경에서 짧은 시간안에 POC 앱을 만들어보게 되었고[5], 추후 보완해야할 점들을 개선하게되면 사무직 종사자들에게 실질적으로 도움이 될 수 있는 서비스를 제작할 수 있을 것으로 기대합니다.

접근법

그림 2. Excel Scanner v0.2의 전체 흐름

Excel Scanner의 전체적인 데이터 흐름은 [그림 2]과 같습니다. 카메라로부터 매 순간 이미지를 입력으로 받습니다. OCR과 표 파싱 알고리즘을 거쳐 결과를 화면상에 보여줍니다. [그림 2]의 오른쪽 상단의 이미지가 파싱 결과를 시각화하여 보여준 모습입니다. 여기까지의 과정이 카메라로부터 입력받은 매 프레임에대해 추론을 수행하고 알고리즘을 거쳐 실시간으로 시각화된 결과를 보여줍니다. 오른쪽 하단의 이미지는 파싱된 표를 파일로 추출한 모습입니다.

Real-time OCR

그림 3. OCR 추론에 대한 입력과 출력

[그림 3]의 실시간 OCR은 구글의 ML Kit[6]과 애플의 Core ML[7]을 고려했습니다. 두 프레임워크가 출시된지는 5년이 되었고, 처음 출시될 당시에는 서로 장단점이 있었지만 지금은 역할과 장점들이 거의 비슷해졌습니다. 이 프레임워크들의 사용을 고려하고 있다면 개발 시점에서 최신 프레임워크의 성능과 지원 범위를 고려해서 선택하면 됩니다. Core ML 프레임워크는 안드로이드에서는 사용할 수 없으므로 이 점도 함께 고려되어야합니다. Core ML은 텍스트 인식(text recognition)과 텍스트 감지(text detection) 기능을 각각 제공하며, ML Kit은 텍스트 인식만 제공합니다. 또한, ML Kit은 클라우드 기반 텍스트 인식도 제공하는데, 이 경우는 API 사용 건수당 일정 비용을 지불해야합니다. 하지만 서비스 특성상 더 정확한 인식 수준을 요구하는 경우 클라우드 기반 텍스트 인식도 고려할 수 있습니다.

ML Kit과 Core ML의 텍스트 인식 지원 언어는 [표 1]과 같습니다. Vision(Core ML)은 아직 한국어 지원이 안되며, ML Kit은 v2(beta)에서 한국어를 지원하고 있습니다.

Framework	Supporting Languages
ML Kit v1[8]	af, sq, ca, hr, cs, da, nl, en, et, fil, ti, fr, de, hu, is, id, it, lv, lt, ms, no, pl, pt, ro, sr-Latn, sk, sl, es, sv, tr, vi
ML Kit v2(beta)[8]	zh, hi, ja, ko, mr, ne
Vision(Core ML) .accurate	en-US, fr-FR, it-IT, de-DE, es-ES, pt-BR, zh-Hans, zh-Hant
Vision(Core ML) .fast	fr-FR, it-IT, de-DE, es-ES, pt-BR

표 1. ML Kit과 Core ML의 텍스트 인식 지원 언어 비교 (22년3월13일 기준)

일반적으로 OCR 결과는 바운딩박스와 문자열로 구성되어 있습니다. 바운딩박스는 텍스트가 담겨 있는 영역 정보이고, 문자열은 해당 바운딩박스 안에 들어있는 글자 정보입니다. 영어 기준, 단어 단위까지 바운딩박스를 쪼개어 결과를 받을 수 있습니다. 프레임워크에따라 문단 단위, 줄 단위도 구분된 구조로 인식 결과를 받을 수 있습니다.

이러한 OCR 결과를 가공하여 표 구조로 클러스터링하는 알고리즘은 다음 섹션에서 설명하도록 하겠습니다.

Table Parsing Algorithm

표 파싱 알고리즘은 텍스트 인식된 결과(바운딩박스와 문자열)를 입력으로 받으면 표 형식(행과 열로 묶인)으로 만들어주는 알고리즘입니다. 바운딩박스 집합을 행과 열로 클러스터링하게 됩니다.

그림 4. 표 파싱 알고리즘 세부 흐름도

1 단계: OCR 추론으로부터 받은 결과에대해 각 셀의 바운딩박스에서 왼쪽 상단의 점을 가져옵니다. 이 점들은 각 셀을 대표하는 위치로 가정하여 클러스터링을 수행합니다.

2단계: 클러스터를 대표하는 수식으로 $y = ax + b$ 을 사용할 것이기 때문에 $a$가 infinity가 되지 않도록 행(row)을 찾는 알고리즘만 구현되어 있습니다. 열(column)을 대표하는 수식은 $a$가 infinity가 될 수 있어 $y$가 infinity가 되는 것을 사전에 방지했습니다. 그러므로 열을 찾는 경우에는 모든 셀의 좌표를 90° 회전하여 행을 찾는 알고리즘을 사용하게 됩니다.

3단계: 셀 집합($P \supset {p_1, p_2, p_3, …, p_n }$)에서 원점에서 제일 가까운 셀($p_{criterion}$)을 찾습니다. 원점과 셀의 거리를 계산할 때, 아래 수식과 같이 유클리디언 제곱 거리 수식에서 $y$축에대한 거리를 늘릴 수 있도록 상수를 곱하여 계산하였습니다. 거리는 순서를 세우는데 사용되므로 계산 효율을 얻기 위해 유클리디언 거리에서처럼 제곱근은 사용하지 않았습니다.

\[d_{CSED}^{2}((x_1, y_1), (x_2, y_2)) = (0.1*(x_1 - x_2))^2 + (8*(y_1 - y_2))^2\]

$CSED$: Custom Squared Euclidean Distance

4단계: $p_{criterion}$를 기준으로 같은 방향으로 가까운 두 셀($p_1, p_2$)을 찾습니다. 모든 셀을 순회하진 않으며, $N$개의 셀을 최대로 두고 확인합니다. 여기서도 위 수식을 사용하므로 $y$축은 멀게 만들었으므로 양옆에 가까히 있는 셀들을 먼저 탐색하게 됩니다. $p_{criterion}$와 $p_1, p_2$를 찾으면 하나의 클러스터가 만들어질 준비가 되었습니다.

5단계: 하나의 클러스터는 $p_{criterion}$를 시작점으로하여 나머지 셀들을 이어 만든 각각의 직선이 있습니다. 각각의 직선을 평균내어 현재 클러스터를 대표하는 직선을 만듭니다. 대표 직선과의 거리가 멀지 않은 지점에 후보 셀을 확인합니다. 후보 셀이 대표직선과 일정 범위 이내에 위치한다면 후보셀을 클러스터에 넣고, 대표직선을 업데이트합니다.

다시 3단계: 5단계까지 사용된 모든 셀들은 $P$에서 제거하고, 클러스터내에 셀들의 순서를 정리하고, 다시 3단계로 돌아가 $P$가 빈 집합이 될 때까지 반복합니다.

시각적 디버깅

때로는 사람의 눈으로 실시간 결과를 확인하는 것이 하나로 계산된 숫자보다 더 많은 인사이트를 줄 수 있습니다. 로그상에서는 알기 어려웠던 알고리즘의 문제들을 파악하는데 시각적 디버깅의 도움을 받았습니다. 알고리즘의 각 단계별로 셀들이 정상적으로 할당되는지 빠르게 확인하고, 최종적으로 셀들이 각 클러스터에 잘 담겼는지 확인하는데 [그림 5]와 같은 시각적 디버깅 방법의 도움을 받았습니다.

제가 만들었던 시각적 정보는, 각 행과 열을 대표하는 대표직선, 같은 행은 같은 색으로 칠해진 셀로 표현(혹은 같은 열을 같은 색으로 칠해진 셀로 표현), 화면상에 셀 자체가 정상 인식 되었는지 식별등의 정보를 한눈에 알 수 있었고, 실시간으로 여러 프레임에 걸쳐 어떻게 인식되는지 짧은 시간 안에 알고리즘의 성능을 정성적으로 판단할 수 있었습니다.

그림 5. 표 파싱 알고리즘 결과를 시각적 표현. 같은 행의 셀들은 같은 색으로 표현, 행과 열을 대표하는 직선을 그림

알고리즘 분석

위 알고리즘은 셀의 개수를 $n$이라 했을때 $O(n^2log(n))$ 시간복잡도를 가집니다. 3단계에서 5단계까지를 셀 개수에 비례하게 반복할 것이며, 각 반복문 안에는 남은 셀들을 원점으로부터 거리 기준으로 정렬을 하거나, $p_{criterion}$로부터 거리 기준 정렬을 하게 됩니다. 반면, 공간복잡도는 $O(n)$ 알고리즘 입니다.

알고리즘의 한계

• $O(n^2log(n))$의 시간복잡도를 가지기 때문에 알고리즘 한계로 인한 셀의 개수 한계점이 있을 수 있습니다. 간단한 표는 처리시간이 짧을 수 있지만, 100개, 1000개가 넘는 셀은 처리시간이 급격히 느려질 수 있습니다. 시간 복잡도를 줄일 방법이 필요합니다.
• 텍스트 인식기의 성능에 의존적입니다. 텍스트 인식기의 성능이 좋지 않은 입력 데이터의 경우 알고리즘의 성능도 함께 급격히 떨어질 수 있습니다.
• 표에서 두 셀이 합쳐진(셀 병합) 케이스는 고려되지 않았습니다.
• 표에서 각 셀들의 글자가 왼쪽 정렬임을 가정합니다. 중앙 정렬이나 오른쪽 정렬의 경우 대표 직선을 만드는 과정에서 문제가 있을수 있습니다.

처리 속도 비교

그림 6. ML Kit과 Core ML의 텍스트 인식 추론속도 비교(디버깅 모드). y축은 ms 단위.

[그림 6]는 프레임워크별 추론 속도와 알고리즘의 처리 속도를 비교한 결과입니다. 세가지 모두 셀의 개수가 많아질수록 시간이 많이 소요되는 양상을 띄었고, 알고리즘의 시간은 아직 추론속도에 비하면 적은 편입니다.

Core ML은 ML Kit에비해 추론 시간이 비교적 천천히 증가하는 모습이었지만, 글자가 많은 이미지의 경우 3년전(2019년)과 비슷하게 ML Kit이 좋은 정확도를 보여주었습니다(정성적 평가).

정리

이번 아티클에서는 추가적인 학습 없이 여러 On-device ML 프레임워크의 제공되는 기능을 활용하여 손쉽게 OCR 활용 앱을 제작해본 경험을 공유드렸습니다. OCR 결과를 후처리하는 알고리즘의 시간복잡도가 다소 크게 측정되었지만, 프로토타입 목적에서는 큰 문제가 되진 않았으며, 추후에 개선을 통해 해결할 수 있을 것으로 생각됩니다. 알고리즘 설명 뿐만 아니라, 외부 프레임워크별 OCR 기능의 추론 속도 비교, 표 파서 알고리즘 속도 비교를 통해 모바일 앱에서 확인할 수 있는 지표를 살펴보았습니다. 마지막으로 시각적 디버깅 방법을 소개하여 실시간 추론 앱에서만 관찰할 수 있는 직관을 정성적으로 평가해보았습니다.

앞으로 할 일

테스트셋 구축. 시각적 디버깅 방법을 통해 정성적인 성능 평가를 할 수 있었지만, 테스트셋을 통한 정량적인 성능 평가가 필요합니다. 테스트셋을 구성하는 데이터는 실제 핸드폰으로 찍은 사진 뿐만 아니라 다양한 크기의 사진과 카메라 각도, 엑셀 파일 형식 등을 포함하고 있어야 합니다. 또한 사용자 데이터를 테스트셋으로 사용할 수 있는 방법도 고민해 볼 수 있습니다.

정량적 평가를 위한 지표 설정. 알고리즘이 개선되었음을 수치상으로 판단할 수 있도록 지표를 설정해야합니다. 하나의 수치로 표현되어 알고리즘이 점점 개선된다는 사실을 평가할 수 있어야 합니다.

표 파싱 딥러닝 모델 제작. 데이터가 충분히 쌓인다면, 표 파싱 알고리즘도 딥러닝을 활용한 시도를 해볼 수 있습니다. 표 파싱 알고리즘만 딥러닝으로 해결할수도 있지만, OCR 모델을 포함한 전체 모델을 딥러닝 모델로 제작해볼 수도 있습니다. 하지만 Core ML이나 ML Kit의 OCR이 가볍고 성능이 꽤 좋은 편이라, 이정도 성능의 라이브러리는 가능한 활용하는 하는 것이 모델을 직접 만들어 내는 것 보다 효율적인 방법이 될 것으로 생각됩니다.

참조

[1] CamScanner
[2] Adobe Scan — Adobe
[3] vFlat Scanner — 보이저액스
[4] MS Lens — Microsoft
[5] 9시간 해커톤 기록 — Facebook 포스팅
[6] ML Kit — Google official documentation
[7] Core ML — Apple official documentation
[8] Supporting languages for ML Kit Text Recognition