Advanced
A Restoration Method for Geometric Distortions to Improve Scanned Books Identification
A Restoration Method for Geometric Distortions to Improve Scanned Books Identification
Journal of Broadcast Engineering. 2015. May, 20(3): 379-387
Copyright © 2015, The Korean Society of Broadcast Engineers
  • Received : March 09, 2015
  • Accepted : May 19, 2015
  • Published : May 30, 2015
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
도영 김
상훈 이
Sagar Jadhav
상훈 이
slee@yonsei.ac.kr

Abstract
최근 몇 년 간, 만화 콘텐츠의 불법 복제 및 배포로 인한 저작권 침해가 중요한 이슈로 떠오르고 있다. 만화의 불법적인 사용을 방지하기 위해 활용되는 핑거프린트 기법은 불법 만화 콘텐츠를 빠르고 정확하게 식별하는 것이 가능하다. 하지만 불법 유통되는 만화는 스캔 혹은 촬영 과정에서 왜곡이 생기고, 이로 인해 원본으로부터 추출된 핑거프린트와 다른 형태를 가지게 된다. 핑거프린트 비교 과정에서 만화 콘텐츠가 정확히 식별되지 않는다. 본 논문은 스캔 또는 촬영 중 발생하는 기하학적 왜곡 방법에 대한 보정 방법을 제시하고 이에 따른 핑거프린트 식별을 개선하고자 한다.
Keywords
Ⅰ. 서 론
최근 들어 스마트폰, 태블릿과 같은 휴대용 디바이스의 발달에 따라, 사용자들이 인터넷 상의 e-book, 만화, 동영상과 같은 콘텐츠를 손쉽게 저장하여 유통할 수 있다. 디지털 콘텐츠에 대한 수요가 급증하여 이를 제공하는 미디어 서비스도 증가 추세에 있다. 하지만 이러한 미디어 서비스는 디지털 콘텐츠를 용이하게 불법 복제 및 배포할 수 있어 해당 저작권자들의 저작권을 침해할 수 있다는 부작용이 생겨나고 있다.
이러한 문제를 해결하기 위해 디지털 콘텐츠의 불법 복제 및 배포를 막을 수 있는 수많은 연구가 진행되고 있다 [1] [2] [3] . 핑거프린트 추출 기법은 불법 배포된 디지털 콘텐츠를 식별하고 보호할 수 있는 효과적인 방법으로 [4] 에서는 만화 핑거프린트 추출에 관한 한 가지 방법이 소개되어 있다. 2개의 소구역으로 나누어진 38가지 종류의 마스크를 이미지에 적용하여, 각 소구역에 해당하는 픽셀 값의 평균을 비교하여 38비트의 핑거프린트를 추출해낸다. 하지만 불법 복제된 만화의 경우 광학적, 기하학적 왜곡에 의해 픽셀 값혹은 위치가 변하기 때문에, 마스크의 평균 픽셀 값이 원본과는 다르게 추출 될 수 있다. 따라서 왜곡을 보정하여 핑거 프린트를 추출하거나, 왜곡에 강인한 핑거프린트를 찾는것이 매우 중요하다.
만화 스캔 과정에서 발생하는 왜곡은 두 가지 종류가 있다. 출판물을 올바르지 않은 위치에서 스캔하여 발생하는 기하학적 왜곡과 스캐너 혹은 조명으로 인해 생기는 광학적 왜곡이 존재하는데, 이에 대해 많은 사람들이 연구를 진행해왔다 [5] [6] [7] [8] . 스캔 혹은 촬영 시 생기는 기하학적 왜곡 보정은 보통 OCR (Optical character recognition)의 정확도를 높이기 위한 전처리 과정으로 수행된다. 그림 1 과 같이 모든 문자가 일직선으로 정렬되도록 만들어 OCR의 정확도를 높인다.
PPT Slide
Lager Image
구겨진 이미지를 펴는 과정 Fig. 1. Dewarping process of warped image
만화 이미지는 다양한 연필 스케치와 몇 줄의 텍스트로 표현된다. 만화 핑거프린트 추출의 경우 다양한 왜곡에 대하여 강인해야 한다. 그 중 기하학적 왜곡은 4개의 모서리 위치와 2차원 원근 변환을 통해 보정된다. [9] 는 휴 선 변환 (Hough line transform) 후 평면 호모그래피 (plane homography), 교차선 (cross line) 등을 이용하여 기하학적 왜곡을 보정하였다. 하지만 이 방법은 해당 문서가 높은 대비의 경계선을 가지고 있어야 하며, 교차선과 모서리의 위치를 구하는데 매우 많은 계산량을 필요로 한다. 한편 [10] 에서는 소벨 필터를 이용해 이미지를 이분화한 후 확장 (dilation)과 침식 (erosion)을 활용하여 이미지를 분할하였다. 모서리의 위치를 추출하기 위해 해리스 코너 감지 (Harris corner detection) 기법을 이용하였다. 하지만 스캔 이미지는 일반적으로 낮은 대비를 갖지고 있어, 코너 감지 (corner detection)와 확장 (dilation)을 적용하기 어렵게 만든다.
스캔된 문서의 광학 보정을 위해 기존에는 간단한 이분화 기법을 사용했으나 [11] , 비교적 복잡한 광원에 의한 왜곡에 대해서는 좋지 않은 성능을 보였다. [12] 가 제안한 표면 알베도 (albedo) 기법은 광학적 보정에 적용될 수 있지만, 해당 스캐너 내부 알고리즘에 대하여 알고 있어야 하는 단점이 있다. [13] 의 경우에는 스캔된 도서의 3차원 표면 방정식을 계산하여 이미지를 직사각형 형태로 변환하여 가독성을 높였지만, 도서의 3차원 방정식을 계산해야 하므로 알고리즘의 계산량이 많아 이미지를 복원하는데 많은 시간이 걸린다.
본 논문은 만화 이미지의 왜곡을 제거하고 만화 식별 시스템에서 핑거프린트의 매칭 정확도를 높이는 것이다. 스캔 혹은 촬영된 만화의 기하학적 (geometric) 왜곡과 광학적 (photometric) 왜곡 중 기하학적 왜곡을 보정할 수 있는 매우 빠른 방법을 제시한다.
Ⅱ. 기하학적 왜곡 복원의 필요성
만화 스캔 시 사용자의 조작으로 기하학적 왜곡이 생기는데, 이로 인해 스캔 이미지는 원본 이미지와 다르게 표현 될 수도 있다. 핑거프린트가 원본과는 다르게 추출되어, 원본 이미지의 핑거프린트와 일치하지 않아 식별 가능성이 낮아지므로 스캔 이미지를 원본 이미지와 비슷하게 보정하여 기하학적 왜곡을 바로 잡아 핑거프린트 식별 가능성을 향상시켜야 한다. 또한 실시간으로 업로드되는 만화 콘텐츠를 처리하기 위해서는 매우 빠른 보정 알고리즘이 필요하다.
PPT Slide
Lager Image
[4]의 핑거프린트의 마스크 하나를 원본, 왜곡, 복원 이미지에 적용한 예시 Fig. 2. Examples of applying the mask of fingerprints in [4] to the original, distorted and restored images
본 논문에서는 기하학적 왜곡 보정의 성능을 테스트하기 위해 [4] 의 핑거프린트를 사용하였다. 그림 3 [4] 의 핑거프린트 마스크 중 하나를 이미지에 적용한 그림이다. 파랑 색 구역 픽셀 값의 평균과 빨간 색 구역 픽셀값의 평균을 비교하여 핑거프린트 값을 결정한다. 왜곡 이미지를 보면 파랑 색 구역에는 하얀 색 배경이 추가되어 원본 이미지와는 다른 픽셀 분포를 갖게 된다. 기하학적 왜곡으로 인해 원본 이미지의 핑거프린트와 왜곡 이미지의 핑거프린트가 다르게 추출될 수 있다. 그림 3 의 복원 이미지에서처럼 기하학적 왜곡을 보정한다면 픽셀의 분포가 원본과 비슷해져 핑거프린트 또한 비슷한 값을 얻을 수 있다.
PPT Slide
Lager Image
만화 식별 시스템 구성도 Fig. 3. Comic identification system diagram
Ⅲ. 기하학적 왜곡 복원 방법
- 1. 전체 시스템
제안된 만화 식별 시스템은 그림 3 에 나와 있다. 이 시스템은 양면 페이지 분할 모듈, 왜곡 보정 모듈, 핑거프린트 추출 모듈, 핑거프린트 매칭 모듈 4단계로 이루어져 있다. 양면 페이지 분할 모듈이 포함된 이유는 핑거프린트 추출시 한 페이지에 대해서만 핑거프린트를 추출하여, 더욱 많은 핑거프린트를 추출함으로써 핑거프린트를 활용한 식별 정확도를 향상하였다. 보통 시스템에 만화가 두 페이지씩 스캔되어 업로드되면 기하학적 왜곡을 먼저 보정한다. 기하학적 왜곡은 그림 4 와 같이 이미지 전체에 대해서 나타나기 때문에 이미지 전체에 대하여 기하학적 왜곡을 보정하고 페이지를 분할한다. 기하학적 왜곡을 보정하지 않고 양면 페이지를 분할하면 그림 4 의 왜곡 이미지와 같이 잘못된 부분을 분할하게 된다. 기하학적 왜곡을 보정한 후 페이지를 분할하면 그림 4 의 복원 이미지에서 보이는 것처럼 좀더 정확한 부분을 분할하게 된다.
PPT Slide
Lager Image
만화의 가하학적 왜곡 예시; 왼쪽: 왜곡 이미지, 오른쪽: 복원 이미지 Fig. 4. The example of the geometric distortion of comic; left: distorted image, right: restored image
- 2. 기하학적 왜곡 보정
본 논문에서는 여러 종류의 기하학적 왜곡을 보정할 수 있는 한 가지 방법을 제시한다. 보정 알고리즘은 캐니 엣지감지 (Canny edge detection), 코너 감지 (corner detection), 퍼스펙티브 변환 (perspective transformation) 3단계로 진행된다.
  • 1) 캐니 엣지 감지: 캐니 엣지 감지는 이미지의 그라디언트를 계산하여 임계값을 통해 엣지의 이분화 맵을 획득한다[14]. 이력 (Hysteresis) 임계값 기법을 사용함으로써 잡음이 존재하는 환경에서도 좋은 엣지 이분화 이미지를 얻을 수 있다. 이력 임계값 기법에서는 두 가지 임계값,Thigh와Tlow이 사용되는데,Thigh와Tlow는 픽셀 최댓값의 80%와 40%로 실험적으로 결정하였다.
  • 2) 모서리 감지: 퍼스펙티브 보정을 위해 4개의 모서리를 찾아야하는데, 앞에서 구한 엣지 이미지가 사용된다. 본 논문에서는 왼쪽 위 모서리의 위치를 구하기 위한 방법을 제시하였는데, 이는그림 5에 나와 있다. 모서리의 위치를 결정하기 위해, 각 열에 대하여 맨 위 픽셀부터 맨 아래 픽셀까지 픽셀 값이 0이 아닌 픽셀을 처음으로 나오는 행 인덱스를 검색한다. 각 열에 대하여 0이 아닌 픽셀이 나오면 그 픽셀의 행 인덱스를 저장하고, 나오지 않으면 인덱스의 최댓값을 저장한다. 모든 열에 대해서 행 인덱스를 저장한 후, 인덱스의 변화가 일정 임계값보다 크게 일어나는 지점을 모서리로 판단한다.그림 5에서는i- 1에서i로 넘어갈 때 행인덱스 변화가 크게 일어나므로 (10,i)가 왼쪽 위 모서리가 되는 것을 확인할 수 있다. 이러한 방법을 다른 3개의 모서리에도 적용하여 찾을 수 있다.
  • 3) 퍼스펙티브 변환: 퍼스펙티브 변환은 변환 행렬을 이용하여 4개 모서리의 위치를 이동시켜 이미지를 변환하는 과정이다. 모서리 감지에서 찾은 4개의 모서리를 직사각형의 4개 모서리 좌표로 대응시켜 변환하면 직사각형의 이미지를 얻을 수 있다. 이는 식 (1)과 같이 행렬식으로 나타낼 수 있다.
PPT Slide
Lager Image
PPT Slide
Lager Image
위-왼쪽 모서리 검색 Fig. 5. Top-Left corner searching
( x,y )는 왜곡 이미지의 모서리 좌표이고, ( x′,y′ )는 보정된 이미지의 모서리 좌표이다. 왜곡 이미지의 모서리는 위의 모서리 감지 과정에서 찾을 수 있으며, 보정된 이미지의 모서리 좌표는 단순히 핑거프린트 추출을 위해 원하는 이미지 크기로 설정하면 된다. 본 논문에서는 핑거프린트의 정확도와 계산량을 둘 다 고려하여 복원 이미지의 크기를 256x256으로 설정하였다. 따라서 복원 이미지의 4개 모서리의 위치는 (0,0), (0,255), (255,0), (255,255)이 된다. 왜곡 이미지와 복원 이미지의 4개 모서리의 위치를 알고 있으므로 특별한 분류 과정 없이 간단한 연립 방정식을 통해 변환 행렬을 계산할 수 있다.
- 3. 양면 페이지 분할
이미지가 양면으로 스캔될 경우 이미지 너비가 높이보다 크다. 반대로 단면일 경우에는 이미지 높이가 너비보다 크다. 이와 같은 단순한 성질을 활용하여 양면이 스캔되었다고 판단하면 이미지 너비의 반을 갈라서 2개의 단면으로 나눈다.
- 4. 핑거프린트 추출
핑거프린트는 [4] 를 이용하여 추출되었다. [4] 에서는 이미지에 2개의 소구역을 가진 마스크를 씌워 각 소구역에 해당되는 픽셀 값의 평균을 비교하여 0 또는 1의 2진수로 표현한다. 그림 6 에 나온 총 38가지 마스크를 씌워 38 비트의 핑거프린트를 얻게 된다.
PPT Slide
Lager Image
핑거프린트 추출을 위해 사용된 [4]에서 사용한 38개의 마스크 Fig. 6. 38 masks used in [4] for the fingerprint extraction
- 5. 핑거프린트 매칭
핑거프린트 매칭의 정확성과 계산량을 고려하여 원본 만화와 업로드된 만화의 첫 10페이지의 핑거프린트의 해밍거리를 계산하였다. 원본 만화의 첫 10페이지 핑거프린트는 그림 3 의 데이터베이스에 380비트씩 저장되어 있으며, 왜곡 이미지의 핑거프린트가 시스템에 유입되면 그림 3 의 과정을 거쳐 380비트의 핑거프린트를 추출한 후, 시스템에 존재하는 모든 원본 만화의 핑거프린트와 비교하여 최소 해밍 거리를 가진 원본 만화와 매칭된다. 해밍 거리를 구하는 방법은 식 (2)과 같다.
PPT Slide
Lager Image
하지만 데이터베이스에 존재하지 않는 만화가 시스템에 유입될 경우 잘못된 만화로 식별될 수 있다. 오식별이 발생하지 않도록 해밍 거리에 임계값을 설정하였다. 본 논문에서 사용한 임계값은 380비트의 20%로 76비트이다. 가장 작은 해밍 거리를 가진 만화일지라도 해밍 거리가 76비트를 넘는다면 다른 만화라고 판단하여 오식별 가능성을 제거하였다.
Ⅳ. 실험
- 1. 실험 환경
실험에 사용된 컴퓨터의 사양은 Intel i5-3570 CPU, 8GB RAM이고, 해당 실험은 Visual studio 2013에서 C언어를 통해 구현되었다.
- 2. 실험 결과
실험에는 그림 6 [4] 의 38가지 패턴의 핑거프린트가 만화 식별을 위해 사용되었다. 왜곡에 대한 성능을 측정하기 위해 표 1 과 같이 기하학적 왜곡 종류를 정의하였다.
기하학적 왜곡의 종류Table 1. Various Types of geometric distortion
PPT Slide
Lager Image
기하학적 왜곡의 종류 Table 1. Various Types of geometric distortion
기하학적 왜곡은 스캔 시 발생할 수 있는 가능한 왜곡에 대하여 인위적으로 스캔하여 생성하였으며, 광학적 특성을 유지하기 위해 오식별 또는 미식별이 일어나지 않도록 같은 스캐너를 이용하여 스캔하였다.
만화를 식별하기 위해 해밍 거리의 임계값을 20%로 설정하였다. 총 126권의 만화에 대하여 각각 표 1 의 11가지 왜곡을 적용한 만화를 [13] 과 제안한 알고리즘을 통하여 보정 작업을 거친다. 보정된 이미지로부터 핑거프린트를 추출한 후 데이터베이스에 존재하는 모든 원본 만화의 핑거프린트와 비교하여 매칭 정확도를 측정하였다. 매칭 정확도는 표 1 의 각 왜곡에 대하여 얼마나 보정이 가능한지를 평가하는 것으로, 두 알고리즘의 성능을 알아볼 수 있다.
실험 결과 두 알고리즘 거의 비슷한 성능을 보였다. 회전 왜곡이 심각하게 들어간 D4와 여러 가지 복합적인 왜곡이 가해진 D11의 경우에는 두 알고리즘 모두 좋지 않은 성능을 보였다. 인위적으로 회전을 가하여 왜곡 이미지를 생성하여 이미지 일부가 잘려 두 알고리즘 모두 좋지 않은 성능을 보였고, 복합적인 왜곡에 대해서도 심하게 이미지가 왜곡되었을 경우에도 10% 정도는 완벽하게 복원되지 못하였다.
기하학적 왜곡 보정 전후의 매칭 정확도 (%)Table 2. The matching accuracy before and after restoration of geometric distortion (%)
PPT Slide
Lager Image
기하학적 왜곡 보정 전후의 매칭 정확도 (%) Table 2. The matching accuracy before and after restoration of geometric distortion (%)
알고리즘 처리 시간 또한 매우 중요한 요소인데, 표 3 은 현격한 계산량의 차이를 보여준다. [13] 의 경우 굉장히 정교하게 이미지를 복원하여 매칭 정확도를 높였으나 1권 당처리 시간이 28.36초로 실시간으로 사용하기는 어려운 수준이다. 반면, 제안 알고리즘은 1권 당 불과 0.54초의 처리시간을 가지고 있다. 핑거프린트 추출 및 매칭 시간이 약 0.3초라는 것을 생각해 보았을 때, 불과 1초 이내에 만화의 왜곡을 보정하고 식별할 수 있는 매우 빠른 방법이다. 업로드 되는 만화를 실시간으로 처리하기 위해서는 [13] 보다는 제안 알고리즘이 훨씬 뛰어난 속도를 보인다. 1권 당 10장의 이미지를 처리하므로 [13] 은 한 장의 이미지를 처리하는 데도 2.836초의 좋지 않은 성능을 보인다. 실시간으로 계속 업로드 되는 만화를 식별하기 위해서는 [13] 보다는 제안 알고리즘이 처리 시간 면에서 우위를 보이고 있다.
기하학적 왜곡 보정 처리 시간 (초/1권)Table 3. Processing time for restoration of geometric distortion (second/a book)
PPT Slide
Lager Image
기하학적 왜곡 보정 처리 시간 (초/1권) Table 3. Processing time for restoration of geometric distortion (second/a book)
Ⅴ. 결 론
핑거프린트 식별의 성능을 향상시키기 위해 기하학적 왜곡을 보정하는 효과적인 방법을 제안하였다. 엣지 이미지를 활용하여 만화의 4개 모서리를 탐지하였고, 단순하고 효과적인 선형 변환 행렬을 이용하여 이미지의 기하학적 왜곡을 해결하였다. 왜곡 보정을 적용하기 전 시스템보다 더욱 정확한 결과를 얻었다. 게다가 알고리즘이 매우 간단하여 불과 1초 이내에 보정 및 식별이 이루어져 매우 많은 양의 만화가 업로드 되는 웹하드 환경에서 충분히 사용할 수 있는 수준의 속도를 보이고 있다. 이 논문에서는 기하학적 왜곡에 대해서만 다루었지만, 서론에서도 언급하였듯이 기하하적 왜곡뿐만 아니라 스캐너 및 조명으로 인해 발생하는 광학적 왜곡도 만화식별에 있어서 심각한 영향을 끼친다. 광학적 왜곡 또한 실시간으로 불법 업로드 되는 환경에서도 충분히 작동할 수 있는 빠르고 정교한 방법을 제시할 필요가 있다.
BIO
김 도 영
- 2014년 : 연세대학교 학사 졸업
- 2014년 ~ 현재 : 연세대학교 전기전자공학과 석박사통합과정
- ORCID : http://orcid.org/0000-0002-8156-9738
- 주관심분야 : 의료영상처리
이 상 훈
- 2007년 : 연세대학교 학사 졸업
- 2007년 ~ 현재 : 연세대학교 전기전자공학과 석박사통합과정
- ORCID : http://orcid.org/0000-0001-7535-5349
- 주관심분야 : 의료영상처리, GPU프로그래밍
Sagar Jadhav
- 2012년 : Maharashtra Academy of Engineering, Electronics and telecommunication 학사 졸업
- 2012년 ~ 현재 : 연세대학교 전기전자공학과 석사과정
- ORCID : http://orcid.org/0000-0002-8569-0500
- 주관심분야 : 영상처리
이 상 훈
- 1989년 : 연세대학교 전기공학과 학사 졸업
- 1991년 : 한국과학기술원(KAIST) 전기공학과 석사 졸업
- 2000년 : Univ. of Texas at Austin 전기공학과 박사 졸업
- 2003년 ~ 현재 : 연세대학교 전기전자공학부 교수
- ORCID : http://orcid.org/0000-0001-9895-5347
- 주관심분야 : 3D영상화질평가, 기계학습, 프로그래밍
References
D´ıaz-Sa´nchez D. , Sanvido F. , Proserpio D. , Mar´ın A. 2010 “Dlna, dvb-ca and dvb-cpcm integration for commercial content management.” Consumer Electronics, IEEE Transactions on 56 (1) 79 - 87    DOI : 10.1109/TCE.2010.5439129
Lin S. D. , Chen C.-F. 2000 “A robust dct-based watermarking for copyright protection.” Consumer Electronics, IEEE Transactions on 46 (3) 415 - 421    DOI : 10.1109/30.883387
Oostveen J. , Kalker T. , Haitsma J. 2002 “Feature extraction and a database strategy for video fingerprinting.” Recent Advances in Visual Information Systems Springer 117 - 128
Lee J. , Lee S. , Seo Y. , Yoo W. “Robust video fingerprinting based on hierarchical symmetric difference feature.” Proceedings of the 20th ACM international conference on Information and knowledge management. ACM 2011 2089 - 2092
Zhang L. , Yip A. M. , Tan C. L. “A restoration framework for correcting photometric and geometric distortions in camera-based document images.” Computer Vision, 2007. ICCV 2007. IEEE 11th International Conference on. IEEE 2007 1 - 8
Suzuki Y. , Yamashita A. , Kaneko T. 2007 “Correction of geometric and photometric distortion of document images using a stereo camera system.” MVA 215 - 218
Nikolaos Stamatopoulos "A two-step dewarping of camera document images." Document Analysis Systems, 2008. DAS'08. The Eighth IAPR International Workshop on. IEEE 2008 209 - 216
Jian Liang , DeMenthon Daniel , Doermann David 2008 "Geometric rectification of camera-captured document images." Pattern Analysis and Machine Intelligence, IEEE Transactions on, 30.4 591 - 605
Robin Tommy , Mohan S. "An approach for fully automating perspective images based on symmetry and line intersection." Image Information Processing (ICIIP), 2011 International Conference on. IEEE 2011 1 - 5
Geetha Kiran A. , Murali S. “Automatic rectification of perspective distortion from a single image using plane homography.”
Zheng Zhang , Tan Chew Lim "Correcting document image warping based on regression of curved text lines." Document Analysis and Recognition, 2003. Proceedings. Seventh International Conference on. IEEE 2003 589 - 593
Li Zhang "3D geometric and optical modeling of warped document images from scanners." Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on. Vol. 1. IEEE 2005 337 - 342
Hiroki Shibayama , Watanabe Yoshihiro , Ishikawa Masatoshi 2013 "Reconstruction of 3D surface and restoration of flat document image from monocular image sequence." Computer Vision–ACCV 2012 Springer Berlin Heidelberg 350 - 364
Canny J. 1986 “A computational approach to edge detection,” Pattern Analysis and Machine Intelligence, IEEE Transactions on, no. 6 679 - 698