link: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.420.7883&rep=rep1&type=pdf
결과 영상:
Abstract:
- adaptive thresholding은 조명에 따른 spatial variation를 고려하는 이진화 기법을 말함.
- 제안한 방법은 입력 영상에 대해 integral image를 이용한 실시간 적응적 이진화 기법을 제안함.
- 제안한 방법은 조명 변화에 강건하며, 단순하고 구현이 쉽고 실시간 처리에 적합함.
1. Introduction
- 고정된 이진화 임계값을 사용하면 비디오 스트림 내에서 조명이 spatial하게 변화하는 경우에 실패하게 됨.
- 조명 변화를 고려하기 위한 일반적인 솔루션은 adaptive thresholding이며, 고정된 임계값을 사용하는 방법과 주된 차이점은 각 픽셀마다 서로 다른 이진화 임계값을 계산한다는 것이고 이러한 기법은 조명 변화에 더욱 강건하다고 알려져 있음.
adaptive thresholding과 관련한 수많은 연구들이 있음.
- [White and Rohrer 1983; Bernsen 1986; Parker 1991; Wellner 1993; Yang et al. 1994; Shen and Ip 1997; Chan et al. 1998; Savakis 1998; Sauvola and Pietikainen 2000; Yang and Yan 2000]
성능 비교에 대한 연구는 아래와 같음.
- [Venkateswarlu and Boyle 1995; Sezgin and Sankur 2004]
본 논문에서는 integral image를 이용하여 매우 clear하며 simple한 방법을 제안함.
- 구현하기 쉬우며, 비디오 스트림 상에서도 실시간의 성능을 보임.
- 제안한 방법이 이전 연구[Wellner 1993]의 연장선이긴 하나 조명 변화에 대한 강건함을 향상시켰으며, 추가로 구현에 대한 복잡도의 증가 없이, clear하며 깔끔한 솔루션을 제시함.
- 제안한 방법이 OCR을 위한 이진화 기법으로 White and Rohrer 가 제안한 방법과 유사하나, 본 논문에서는 실시간 비디오를 초점에 맞춰서 구현이 되었음.
- 제안한 방법은 assumption이 없는 더욱 general한 방법이며, 어떤 application에도 적합하게 사용 가능함.
2. Background
2.1 Real-Time Adaptive Thresholding
본 논문에서는 실시간 비디오 스트림 처리에 대해 초점을 맞추고 있으며, 실시간 성능을 유지하기 위해, 이진화 알고리즘은 iteration 회수가 small한 constant가 되도록 해야 함. 이진화는 전처리로서 많이 사용이 되기 때문에 단순하며, 빠른 적응적 이진화 기법이 중요한 요소가 됨.
2.2 Integral Image
integral image(summed-area table로 알려져 있음)는 우리가 pixel로부터 real number f(x, y)까지의 하나의 function을 가지고 있다면 언제든지 사용될 수 있는 방법이며, 영상의 rectangular region에 대해 이러한 function의 sum을 계산하는 것이 목표임. Integral image는 아래와 같은 다양한 어플리케이션에 적용이 됨.
- Texture mapping [Crow 1984]
- face detection in images [Viola and Jones 2004]
- stereo correspondence [Veksler 2003])
Integral image 없이, sum은 각 rectangle 마다 각 픽셀에 대한 function 값을 개별적으로 계산함으로써 linear time으로 계산이 될 수 있음.
- 하지만 만약 multiple의 overlapping된 rectangular windows에 대한 sum을 계산하려 한다면, integral image를 사용할 수 있으며, 단지 linear amount의 전처리만을 이용하여 rectangle 마다 일정한 회수의 operation을 달성할 수 있음.
integral image를 계산하기 위한 식은 아래와 같음.
그림 2(좌측 및 가운데)는 integral image의 계산에 대해 설명하고 있음. 일단 integral image를 얻으면, 어떤 rectangle에 대한 function의 sum이라도 좌측 상단 코너(x_1, y_1)과 우측 하단 코너(x_2, y_2)을 가지고 아래의 식에 의해 일정한 시간 내에 계산이 될 수 있음.
그림 2(우측)는 위의 식 (2)를 이용하여 rectangle D에 대한 f(x, y)의 sum을 계산하는 것을 나타내며, rectangle (A+B+C+D)-(A+B)-(A+C)+A 에 대한 sum을 계산하는 것과 동일함.
3. Technique
본 논문의 adaptive thresholding 기법은 Wellner의 기법[Wellner 1993]에 대한 단순한 확장 버전임. Wellner 알고리즘의 주된 아이디어는 각 픽셀들은 주변 픽셀들의 평균과 비교되도록 하는 것임.
- 구체적으로, 마지막으로 나타난 pixel s에 대한 approximate moving average가 영상을 순회하면서 계산이 되어짐. 만약 현재 픽셀의 값이 평균 보다 t 퍼센트 낮다면 검은색으로 설정이 되고, 그렇지 않으면 흰색으로 설정이 됨.
- 하나의 픽셀과 근처의 픽셀들의 평균을 비교하는 것은 hard한 contrast line을 보존하며, soft한 gradient의 변화는 무시할 수 있는 방법임.
- 이 방법의 이점은 이미지를 single-pass로만 통과하게 된다는 것임. Wellner는 s 값을 영상 가로 길이의 1/8배로 설정하였으며, t의 값을 15로 설정하였지만, 이 방법의 문제는 pixel의 scanning 순서에 의존적이라는 것임. 추가로, moving average는 이웃 샘플들은 모든 방향으로 균등하게 분포되어 있지 않기 때문에 각 step 상에서 surrounding pixel들에 대한 좋은 표현이 아님.
- Integral image를 사용함으로써(영상을 통과하는 하나의 추가적인 반복을 희생시킴), 위와 같은 문제를 겪지 않는 하나의 solution을 나타낼 수 있음.
- 제안한 방법은 clean하며, 직관적이고, 구현하기 쉬우며, 어떻게 영상이 처리되든지 간에 독립적인 동일한 결과를 보임.
- 마지막으로 나타난 pixel s에 대해 running average를 계산하는 것 대신에, 각 pixel 주변의 중점에 대한 s x s window의 average를 계산함.
- 이것은 모든 측면의 이웃 픽셀들을 고려하기 때문에 비교를 위한 더 좋은 average임.
- Integral image를 사용함으로써 average 계산은 linear time으로 가능하게 됨. 본 논문에서는 입력 영상을 통과하는 first pass 내에서 integral image를 계산함.
- Second pass에서는 각 pixel에 대한 integral image를 이용하여 일정 시간 내에 s x s average를 계산하고, 비교를 수행함. 만약 현재 픽셀의 값이 현재 평균 보다 t percentage 아래라면 검은색으로 설정이 되고, 그렇지 않으면 흰색으로 설정이 됨.
본 논문에서 제안한 방법에 대한 슈도 코드가 아래와 같이 있음.
- in: 입력 영상, out: 이진화된 출력 영상, w: 영상의 가로 길이, h: 영상의 세로 길이
4. Performance and Examples
제안한 방법을 펜티엄 4 3.4Ghz에서 640 x 480 영상에 대해 테스트를 수행함.
- 프레임 마다 15 msec 정도 되며, 초당 65 frame의 frame-rate를 가지게 됨.
- Wellner의 기법이 단지 한번의 iteration을 요구하는 것에 비해 본 논문에서 제안한 방법은 각 이미지에 대해 2번의 iteration을 필요로 하기 때문에, 좀 더 느리게 수행 될 것임.
- Wellner의 방법 보다 실제적으로 약 2.5배 느리지만, 좀 더 우수한 segmentation과 실시간 성능을 달성 할 수 있었음.
Wellner의 기법과의 성능 비교 결과 거의 완벽한 성능을 보이고 있음.
5. Discussion
- global thresholding 기법에서는 다루기 힘든 조명 변화를 자동적으로 다룰 수 있음.
- 영상을 2번 처리해야 한다는 결점이 있으나, 실시간 성능을 보일 수 있으며, 처리량은 pixel (i-s/2, j-s/2) 단계에서 이진화 수행과 동시에 pixel (i, j)에서 integral image를 계산함으로써 최소화 시킬 수 있음.
- 이러한 경우에, 아래 픽셀 개수에 따르는 일정한 처리량을 가지게 됨.
thresholding을 위한 기법은 이미지는 주로 배경 픽셀을 포함하고 있으며, 전경 픽셀은 영상 내에서 상당히 분포되어 있다는 assumption을 만듬. 전경 component의 경우 s x s 픽셀 보다 더 크며, component의 center는 배경으로 부정확하게 분류가 됨. 이러한 문제는 보다 큰 커널을 사용함으로써(s를 증가시킴) 완화시킬 수 있지만, segmentation의 detail은 잃어버리게 됨. 응용 분야에 따라 커널의 크기는 적합하게 설정을 해야 함.