공간영역에서의 선형 필터링

1. 영역 연산

영역연산(Area operation) 또는 이웃 연산(Neighborhood operation)이라고 불리는 공간 영역에서의 선형 필터링은 새로운 출력 화소의 값을 결정하는 데, 출력화소에 해당하는 입력화소뿐만아니라, 그 주위의 화소들의 영향도 고려하는 연산을 말한다.
주로 모서리 검출, 잡음 제거, 선명하게 하기, 흐리게 하기 등 여러 곳에서 사용이되는데, 입력 영상으로부터 새로운 출력 영상을 만드는 경우, 출력영상의 화소에 해당하는 입력 영상의 화소값을 써서 새로운 화소 값을 계산하는 점 연산의 경우에는, 입력영상의 공간 정보가 반영되지 못하지만, 영역연산과 이웃연산을 통해 주위 화소를 고렿하여, 화소의 공간상의 변화 정보를 이용할 수 있게 된다.
하지만 관심이 있는 좌표 주변의 화소들을 고려하기 때문에, 점연산에 비해 계산 비용이 많이 들어간다.

2. 선형성

입력과 출력이 영상인 연산자 H를 포함하는 식을 생각해보면
$H(af+bg)=aH(f)+bH(g)$
여기에선 $f$와 $g$는 영상이고 a와 b는 상수일 떄 이를 만족하면 연산자 $H$는 선형이라고 한다.
즉, 선형이란 입력이 2배가 되면 출력도 2배가 되고 입력이 반으로 줄면 출력도 반으로 준다는 의미이다.

3. Convolution

Convolution은 영상처리를 하는 데 기본이 되는 이웃 연산이다. 이 연산은 선형연산이며, "상관"이라는 표현 대신에 컨볼루션을 쓸정도로 상관과 구별을 하지 않는 경우도 종종 있다.
일반적으로 영상의 선형필터링으로 컨볼루션을 사용할 때, 출력 화소의 값은 이웃 화소들의 가중치의 합으로 계산하며 이 가중치 행렬을 필터, 마스크, 형틀, 창, 커널 등으로 부른다.
마스크는 일반적으로 3,5크기의 홀수 정방 행렬을 사용하며, 주어진 마스크가 분리 가능하면, 1차원 마스크의 곱으로 표현하기도 한다. 마스크를 주어진 영상의 왼쪽부터 오른쪽으로, 위쪽에서 아래쪽 방향으로 진행하면서, 입력영상의 모든 화소에 대하여 컨볼루션을 계산하여 출력영상을 생성한다. 마스크는 이웃의 범위와 이웃 화소에 대한 가중치를 결정하는데, 일반적으로 $m \times n$크기의 마스크 $h$를 사용한 경우, 크기가 $M \times N$인 영상 $f$에 대한 컨볼루션은 다음식으로 쓸 수 있다.
$g(x,y)=h(x,y)*f(x,y)=\displaystyle\sum_{s=-a}^{a}\displaystyle\sum_{t=-b}^{b}h(-s,-t)f(x+s,y+t)$
여기서 $a=\frac{m-1}{2}$이고, $b=\frac{n-1}{2}$이다.
이를 공간적으로 생각해보면
1) 마스크의 중심 원소에 대해 마스크를 $180\degree$회전시킨다.
2) 입력 영상의 화소위에 마스크의 중심을 이동시킨다.
3) 서로 겹쳐진 마스크의 요소와 입력 화소의 값을 곱한다.
4) 3단계의 각각의 곱을 모두 더한다.
5) 입력 영상의 모든 화소에 대해 2~4를 반복한다.

한 예시로 영상 $f$와 컨볼루션 마스크 $h$를 예로 들어보면
$f=\begin{bmatrix}17 \ 24\ 1\ 8\ 15\ \\23\ 5\ 7\ 14\ 16\\ 4\ 6\ 13\ 20\ 22\\ 10\ 12\ 19\ 21\ 3\\ 11\ 18\ 25\ 2\ 9\end{bmatrix}$

$h=\begin{bmatrix} -1\ 0\ 1\\ -2\ 0\ 2\\ -1\ 0\ 1\end{bmatrix}$

이라고 하자 이를 먼저 $180\degree$회전 시키면
$h_{180}=\begin{bmatrix} 1\ 0\ -1\\ 2\ 0\ -2\\ 1\ 0\ -1\\\end{bmatrix}$
가 된다. 이를 입력 중앙이 입력 영상 $f$의 (2,2)위치(=5 값)에 오도록 겹친 후 그 값을 모두 더하는 과정을 거친다.
즉 $1\times 17+0\times24+(-1)\times1+2\times23+0\times5+(-2)\times7+1\times4+0\times6+(-1)\times13=39$

해당과정을 (2,2)위치부터 (4,4)위치까지 반복하여 나타내면 출력영상 $g$는

$g=\begin{bmatrix}39\ -16\ -41\\ -11\ -46\ -11\\ -41\ -16\:\:\:\:\ 39\end{bmatrix}$

확인해 보면 입력영상 $f$의 (5,5)크기의 행렬이 아닌, 출력영상 $g$는 (3,3)크기의 행렬이 나온다.
입력 영상의 각 화소에 대해 얻은 값은 새로운 출력 영상에 저장된다. 이 값으로 입력영상의 화소값을 대치하게 되면, 다음 새로운 값을 계산하는 데, 이 값이 쓰이게 되는데, 이는 IIR(Infinite Impulse Response System)에 해당하며, 우리가 원하는 값을 얻을 수 없게 된다.

컨볼루션 마스크의 각 원소의 합은 결과 영상, 혹은 출력영상의 전체 밝기에 영향을 미치기 때문에, 많은 컨볼루션 마스크를 원소의 합이 1이 되도록 가중치를 정하고 있다.이 경우에는 출력 영상과 입력영상이 같은 평균 밝기를 갖게 되고, 모서리 검출에 사용하는 컨볼루션 마스크는 음의 계수를 포함하며, 모든 원소의 합이 0이 되는 경우가 있는데, 이 때 음의 출력 화소값이 나오면, 출력값에 상수를 더해 0 이상으로 조절하는 경우도 있다.

컨볼루션을 할 때 마스크의 일부가 영상을 벗어나면 컨볼루션 계산을 할 수 없기 때문에, (3,3)마스크를 쓰게되면, 입력 영상의 경계에 있는 픽셀들은 처리할 수 없다. 따라서 입력 영상의 크기가 $M\times N$크기의 영상이라면, 출력영상의 크기는 $(M-2)\times (N-2)$크기의 영상이 되며 원점도 바뀌게 된다. 마스크가 커지면 커질수록 처리할 수 있는 영역은 더 줄어들기 때문에, 경계에 대한 중요한 문제가 발생한다.

다음은 MATLAB을 통해 이미지 컨볼루션을 이용하여 Prewitt 모서리 마스크를 적용시켜 본 예시이다.
$Prewitt mask(default)=\begin{bmatrix}1&1&1\\0&0&0\\-1&-1&-1\end{bmatrix}$

% 매트랩 코드
img=magic(125);
h=fspecial("prewitt");
ori_img=mat2gray(img);
%% 컨볼루션
img_conv=imfilter(img,h,"conv");
img_conv=mat2gray(img_conv);
figure;
subplot(1,2,1)
imshow(ori_img)
title("원본 영상")
subplot(1,2,2)
imshow(img_conv)
title("컨볼루션")

3-1 Convolution의 경계

1) 화소 제외

컨볼루션 할 수 없는 화소는 제외하는 방법이다. 출력 영상의 크기는 입력 영상의 크기와 같으나, 출력 영상의 경계가 검은색으로 보이게 된다. 물론 가장 간단한 방법이지만, 출력영상의 회색계조의 통계가 큰 변화를 보이게 되기 때문에, 연산 결과에 영향을 미칠 가능성이 존재한다.
즉, 처리하지 못한 영상의 경계에 해당하는 화소들에 0을 할당하여, 영상 경게의 0은 처리하지 못한 화소의 화솟값이 된다.
$g=\begin{bmatrix} 0&0&0&0&0\\0&39&-16&-41&0\\ 0&-11&-46&-11&0 \\ 0&-41&-16&39&0\\ 0&0&0&0&0\end{bmatrix}$

와 같이 마지막 경계되는 부분만을 0으로 채우는 방식이다. 마스크의 크기에 따라 올바로 처리할 수 있는 영역의 크기가 달라지기 때문에, 특별한 상황 아니면 쓰기 어렵다.

2) 0 덧붙이기(Zero padding)

정상적으로 컨볼루션을 행할 수 없는 입력영상의 경계에 있는 화소들을 정상적으로 처리할 수 있도록 화소의 값이 0인 화소들을 입력영상의 경계에 붙여 입력 영상의 크기를 가상으로 크게 하는 방법으로 이 방법을 보통 영 덧붙이기(Zero padding)이라고 한다. 이방법도 첫 번째 방법처럼 쉽기는 하지만, 출력영상의 경계가 영상의 다른 부분과 마찬가지로 중요하다면 좋은 방법 까지는 아니다.

$f=\begin{bmatrix}0&0&0&0&0&0&0&\\0&17& 24& 1& 8& 15& 0\\0&23& 5& 7& 14& 16&0\\ 0&4& 6&13& 20& 22&0\\ 0&10& 12& 19& 21& 3&0\\0& 11& 18& 25&2&9&0 \\ 0&0&0&0&0&0&0\end{bmatrix}$

3) 미러링: 'replicate'

경계에 있는 화소들에 대하여 정상적인 컨볼루션을 행할 수 있도록 경계에 있는 화소값을 복사하여, 입력영상의 크기를 가상으로 크게 하는 방법이 있다. 이를 미러링(Mirroring)으로 부른다.

$f=\begin{bmatrix}A&B&C\\D&E&F\\G&H&I\end{bmatrix}$

입력 영상 $f$를 미러링 방법으로 처리하면,

$f_{proc}=\begin{bmatrix}A&A&B&C&C\\A&A&B&C&C\\D&D&E&F&F\\G&G&H&I&I\\G&G&H&I&I\end{bmatrix}$

4) 두루마리 방법: 'circular'

미러링과 비슷하게, 영상 자체가 모든 방향으로 반복된다고 가정하며느 경계를 넘어가는 화소의 반대편 화소와 맞대어 있다고 생각하고, 경계에 있는 화소값을 복사하는 대신에, 경계를 넘어가는 화소의 값으로 맞은 편 화소의 값을 취하여 컨볼루션을 행하는 방법이다.

$f=\begin{bmatrix}A&B&C\\D&E&F\\G&H&I\end{bmatrix}$

입력 영상 $f$를 두루마리 방법으로 처리하면,

$f_{proc}=\begin{bmatrix}I&G&H&I&G\\C&A&B&C&A\\F&D&E&F&D\\I&G&H&I&G\\C&A&B&C&A\end{bmatrix}$

컨볼루션을 비롯한 영역 연산은 매우 많은 계산을 필요로 한다.
$m\times n$마스크를 써서 식 연산을 하는 경우에는 화소당 $n^2$의 곱셈과 같은 수의 덧셈이 필요하다. 이 때문에 속도 개선을 위하여 소프트웨어나 하드웨어 기술을 쓸 필요가 있다.
가장 효과적인 기술 중 하나로, 컨볼루션 마스크가 분리가 가능한 경우를 들 수 있다. 분리가 가능한 마스크는 폭이 n이고 서로 직교하는 두 1차원 마스크의 곱으로 표현할 수 있다.
예를 들어,
$\begin{bmatrix}1&2&1\\ 0&0&0\\-1&-2&-1\end{bmatrix}=\begin{bmatrix}1\\0\\-1\end{bmatrix}\begin{bmatrix}1&2&1\end{bmatrix}$

로 왼쪽의 컨볼루션 마스크는 오른쪽 두 벡터의 곱으로 표현할 수 있다.
이는 영상이 A행렬로 주어지면 아래와 같이 열벡터 $\begin{bmatrix}1&0&1\end{bmatrix}$을 이용해 열 방향으로 결과를 먼저 얻은 다음, 이 중간 결과에 행 벡터 $\begin{bmatrix}1&2&1\end{bmatrix}$를 이용해 행 방향으로 적용하면 최종 결과를 얻을 수 있다.
$\begin{bmatrix}1&2&1\\ 0&0&0\\-1&-2&-1\end{bmatrix}*A=\begin{bmatrix}1\\0\\-1\end{bmatrix}\begin{bmatrix}1&2&1\end{bmatrix}*A=(\begin{bmatrix}1\\0\\-1\end{bmatrix}*A)*\begin{bmatrix}1&2&1\end{bmatrix}$

여기서 *는 컨볼루션 연산을 의미하고, 2차원 마스크를 1차원마스크로 분리하는 경우에는 각 열마다 계산한 값을 저장했다 사용하면, 모든 열에 대해서 한번만 계산되고, 두번째 1차원 마스크로 연산하는 경우에도 같은 방법을 사용하게 되면, 총 계산양을 많이 줄일 수 있다.
즉 시간 복잡도에 따르면 1차원 마스크를 통한 연산의 수는 $O(n)$이지만 표준 2차원 마스크의 컨볼루션은 $O(n^2)$이고, 이는 마스크의 크기가 커지면 커질수록 더 두드러진 효과를 얻을 수 있다.

4. 상관

상관은 컨볼루션과 거의 똑같은 방법으로 계산을 진행한다. 크기가 $m\times n$ 마스크를 사용하여 $M \times N$인 영상 $f$에 대한 상관은
$g(x,y)=\displaystyle\sum_{s=-a}^{a}\displaystyle\sum_{t=-b}^{b}h(s,t)f(x+s,y+t)=h(s,t)\cdot f(x,y)$

여기서 컨볼루션의 연산과 다른 부분은 $h(-s,-t)$가 아닌 $h(s,t)$를 사용한다는 것으로 마스크를 회전하지 않고, 서로 겹치는 마스크의 요소와 화소 값을 곱하고 더하는 과정을 사용한다는 것이다.
즉 컨볼루션과 상관은 마스크를 $180\degree$회전 하느냐 하지 않느냐의 차이기 때문에, 컨볼루션에 사용한 소프트웨어나 하드웨어를 써서 비정규화된 상관을 계산할 수 있다.

상관은 주로 두 영상 사이에서 유사성을 찾아내는 데 사용한다. 모르는 영상과 아는 영상 사이의 가장 근접한 정합을 찾아낼 필요가 있는 경우에 주로 이용하는데, 이 아는 사진(미리 준비한 사진)을 모델 혹은 형틀이라고 하며, 해당 모델들과의 상관을 적용하면, 유사성을 계산하여 유사성이 가장 높은 모델을 찾아내면 부품 번호나 병변 등 을 알아낼 수 있다.

$h(s,t)$를 상관 마스크로 부르기도 하지만, 형틀 또는 모델이라는 이름을 더 사용한다. 왜냐하면 보통 컨볼루션 마스크보다 훨씬 크기도 크고 형틀의 요소는 영상의 화소값과 같은 형을 가질 뿐만 아니라 값의 범위도 같기 때문이다. 영상의 밝은 부분은 좀 더 큰 값을 주기 때문에 최대한 유사성이 어느점에서 일어났는 지 확인하기 어렵기 때문에, $g(x,y)$를 규정화하는 것이 관례로 사용된다.
보통 규정화하는 방법 중 하나는 입력 영상의 이웃 화소들의 합으로 나누는 것이다.

$g'(x,y)=\frac{g(x,y)}{\displaystyle\sum_{s}\displaystyle\sum_{t}f(x+s,y+t)}$

보통 상관은 찾고자 하는 특징의 방향과 크기를 알면 큰 위력을 발휘하며, 알맞은 형틀을 설계하는 것도 가능하다. 그러나 특징의 방향과 크기의 형틀이 다른 경우에는 유사성을 제대로 계산하기 어렵다는 문제를 안고있다.

다음은 MATLAB을 통해 이미지 상관 이용하여 Prewitt 모서리 마스크를 적용시켜 본 예시이다.
상관은 Convolution과 마스크가 원점에 대해 대칭이면 동일한 결과를 얻을 수 있다는 점에 주목하자.
$Prewitt mask(default)=\begin{bmatrix}1&1&1\\0&0&0\\-1&-1&-1\end{bmatrix}$

%% 매트랩 코드
img=magic(125);
h=fspecial("prewitt");
ori_img=mat2gray(img);
%% 상관
img_corr=imfilter(img,h,"corr");
img_corr=mat2gray(img_corr);
figure;
subplot(1,2,1)
imshow(ori_img)
title("원본 영상")
subplot(1,2,2)
imshow(img_corr)
title("상관")

5. 매트랩 실습

매개변수를 motion으로 선택하여 카메라가 선형으로 흔들림을 주는 마스크를 생성하고, convolution을 진행하여, 입력 영상을 흐리게 만들어주는 예시.

%% 컨볼루션 2
img=imread("lena512.bmp");
img=rgb2gray(img);
% 카메라가 선형으로 흔들리는 효과를 주는 마스크 생성
moving_effect=fspecial("motion",21,11);
% 이미지와 Convolution을 통해 흔들리는 효과를 이미지에 적용시킴
eff_img=imfilter(img,moving_effect,"conv","circular");
eff_img=mat2gray(eff_img);
figure;
subplot(1,2,1)
imshow(img)
title("원본 영상")
subplot(1,2,2)
imshow(eff_img)
title("효과 적용 영상")

h = fspecial('motion',len,theta)는 영상에 컨벌루션을 수행한 후 카메라의 선형 움직임을 근사하는 필터를 반환합니다. len은 움직임의 길이를 지정하고, theta는 움직임의 각도를 반시계 방향의 도 단위로 지정합니다. 이 필터는 가로 방향 움직임과 세로 방향 움직임에 대한 벡터가 됩니다. 디폴트 len은 9이고 디폴트 theta는 0입니다. 이는 9픽셀의 가로 방향 움직임에 해당합니다.