논문

하루에도 수만개의 글자를 읽고 있습니다. 하루에도 수백장의 종이를 들춰 읽습니다.
이것은 그 읽기에 대한 일기입니다.

Fast mean filtering technique (FMFT)

[cite]0.1016/j.patcog.2006.02.008[/cite]

1. Introduction

이미지 프로세싱에서 자주 쓰이는 기법 중 하나는 어떠한 마스크에 의한 컨볼루션일 것입니다. 블러링이나 샤프닝, 노이즈 제거, 에지 검출 등 지역적인 특징을 내기 위해서 사용되곤 합니다. 그 중에서도 mean 또는 averaging 필터는 이미지 프로세싱에서는 물론이거니와 다른 작업의 전처리 작업으로 너무나 많이 쓰이는 기법입니다.

하지만 단순하게 있는 그대로 이를 구현한다면 그 계산에 걸리는 시간이 만만치 않습니다. 예를 들어 1024 * 1024 크기의 이미지를 7 * 7 크기로 mean filtering을 한다면 모두 50 * 10^6 번 만큼의 덧셈과 10^6 번 만큼의 나눗셈이 필요합니다. 하지만 인접한 마스크는 많은 영역을 서로 중첩하고 있기 때문에 중복된 연산을 하고 있습니다. 이러한 부분을 이용하여 어떻게 계산을 빠르게 할 수 있는지 이제 알아보겠습니다.

2. Mean filtering

Mean filtering 이 어떤 것이고 어디에 쓰이는지 간단히 언급하고 있으나 생략하도록 하겠습니다.

3. The basic method

크기 P * Q 를 갖는 이미지 F를 m * n 크기의 마스크를 이용하여 필터링하는 경우를 생각해봅시다. 어떠한 기교를 부리지 않고 있는 그대로 계산을 하면 알고리즘은 다음과 같습니다.

이렇게 계산을 하고 나면 P Q m n 번의 덧셈이 필요하게 됩니다. 여기에 P Q 번의 나눗셈이 필요하게 되죠. 하지만 논문에 나온 그림과 같이 (row, col) 위치와 (row, col+1) 위치와의 사실 1개 컬럼만큼의 차이만 있을 뿐 나머지 영역은 공유하고 있어 중복된 더하기 연산을 하고 있습니다. 이러한 속성을 이용하여 개선된 계산법을 살펴봅시다.

앞에서 계산된 결과에서 이번 계산에 포함되지 않는 픽셀을 빼고 새로 포함되는 픽셀을 더하였습니다. 이와 같이 하면 거의 P * Q * m * 2 정도로 계산량을 줄일 수 있습니다.

4. Proposed methods

여기서 약간 더 나아가 보겠습니다. 먼저 덧셈에 대한 최적화입니다.

앞에서 계산에서 제외되는 부분을 빼고 새로 추가되는 부분을 더하였지만, 대상 위치가 이동할 수록 추가된 부분 또한 언젠가 빼야할 것입니다. 따라서 컬럼단위로 미리 계산을 모두 해놓는다면 더했던 부분을 나중에 다시 빼게 될 경우에 중복으로 계산하게 되는 부분을 줄일 수 있습니다.

이제 나눗셈에 대한 최적화도 해보겠습니다. 이 방법은 최종 결과물이 greylevel인 경우에만 해당되는 방법입니다. 사실 나눗셈까지 한 결과물은 실수이지만 이미지로 출력할 경우 결국 256단계의 greylevel을 사용하여야 합니다. 따라서 실수를 0 ~ 255 사이의 수로 바꾸는 작업이 필요한데, 단간단하게 반올림하지 않고 소수점 이하를 버림으로써 변환한다고 가정합니다.

만약 3 * 3 크기의 마스크를 사용하였다고 하고, 나눗셈 하기 직전의 Sum 값은 0 ~ 2295 (255 * 9) 사이의 값을 가집니다. 이를 나눗셈 연산을 통해 9로 나누게 되면 0 ~ 8 까지의 값은 나눗셈 후에 0으로, 9 ~ 17 까지는 1로, 2286 ~ 2294 까지는 254 값으로 변환됩니다. 이것을 미리 계산을 해둔다면 따로 픽셀 수 만큼의 나눗셈은 필요없게 됩니다.

이제 완성된 계산법을 살펴봅시다.

5. Implementation and results

당연하겠지만 기존의 방법 대비 계산 시간이 짧다고 이야기합니다. 3 * 3 크기에서는 2.5배 정도, 11 * 11 에서는 10.8배 정도 빨랐다고 합니다.

하지만 이 방법과 Integral image를 이용한 방법과의 비교가 필요하다고 생각됩니다. Intergral image를 생성하는데 시간이 걸리긴 하지만, 일단 생성하고 난 뒤에는 크기가 어떻든 간에 단 4번의 계산으로 그 영역의 합을 구할 수 있습니다. 나눗셈에 관한 최적화는 이용될 수 있을 것으로 생각됩니다.


Add a Comment Trackback