엣지와 그래디언트 (Edge and Gradient)

영상의 모서리(edge)는 다음과 같은 불연속점에서 발생한다.

• Depth, Distance의 불연속점
• Surface Orientation의 불연속점 (예를 들어, 책상 모서리처럼 평면의 각도가 변하는 부분)
• Surface Color의 불연속점
• Illumination의 불연속점 (그림자 등)

이러한 모서리들을 검출하려면 어떻게 해야 할까?

Calculating Gradient by Convolution

어떤 이미지를 좌표를 입력하면 해당 픽셀의 밝기값을 출력하는 $f(x, y)$ 형태의 함수라 생각해 보자.
밝기값의 변화가 적은 영역은 평면, 밝기값이 불연속적인 영역은 모서리이기 때문에, 이미지를 미분하여 모서리를 찾아낼 수 있다.

예를 들어, 어떤 픽셀의 밝기값이 100인데, 한 픽셀 오른쪽으로 이동하니 밝기값이 200이 되었다 하면, gradient가 100이라는 높은 값을 갖고, 해당 영역에 모서리가 있다고 할 수 있다.

이런 연산을 합성곱 필터를 통해 수행할 수 있다.

$$ f = \begin{bmatrix} 1 & 0 & -1 \\ 1 & 0 & -1 \\ 1 & 0 & -1\end{bmatrix} $$

위와 같은 필터로 합성곱을 진행한다고 생각해 보자.
이미지에 수직 방향 모서리가 있으면(예를 들어, [255 ? 100]) 높은 값이 나올 것이고, 모서리가 없다면([255 ? 230]) 낮은 값이 나올 것이다!

한편, 그래디언트의 크기(magnitude) 또한 구할 수 있다. $x$방향 그래디언트 $l_x$와 $y$방향 $l_y$에 대해 다음 식을 통해 한 픽셀이 얼마나 큰 그래디언트를 갖고 있는지 알 수 있다.

$$ \text{magnitude of pixel} =  \sqrt{l_x^2 + l_y^2} $$

그래디언트의 방향(direction) 역시 다음과 같이 구할 수 있다.

$$\text{direction of pixel} \arctan2(l_x, l_y) $$

Noise가 있는 이미지의 Edge Detection

위에서 합성곱을 이용해 모서리를 찾아내는 방법을 다뤘다.
그런데 이미지에 Noise가 있다면, Edge Detection이 제대로 이루어지지 않을 것이다.

그렇기 때문에 Edge를 찾기 전에 먼저 Filtering을 이용해 Noise를 제거하고 진행해야 한다.
이미지 $f$에 필터 $g$로 필터링을 진행하고, 미분을 수행하는($\frac{d}{dx}$) 것이다.

$$ \frac{d}{dx}(f * g)$$

그런데, 이 모든 걸 한 번의 합성곱으로 수행할 수 있다.
위 식을 교환법칙으로 아래와 같이 변환해 보자.

$$ f * \frac{d}{dx}g $$

위 식에서, 미분된 필터 $\frac{d}{dx}g$는 미리 계산해 놓을 수 있다.
그러면, 이미지에 한 번의 합성곱만 수행하여 모든 과정을 한 번에 수행할 수 있다!

Canny Edge Detector

위에서 배운 방식으로 Edge Detection을 수행하면 온갖 모서리들이 다 검출된다.
이미지에서 중요하고 큰 모서리만 검출하기 위한 Canny Edge Detector를 사용해 보자.

https://en.wikipedia.org/wiki/Canny_edge_detector

1. 먼저 이미지의 magnitude를 계산한다.
2. magnitude가 작은 edge들을 적절히 thresholding 한다.
3. Edge들 간에 두께 차이를 줄이기 위해 Non-max suppression을 적용한다.
4. 임계치로 인해 작은 edge들은 사라진다.

그런데 이런 방법을 사용하면, NMS로 인하여 모서리가 중간중간 끊어지기도 한다.
이를 개선하기 위해 Hysteresis Thresholding 방법이 생겼다.

• Threshold 값을 두 개 만든다. (High T and Low T)
• 먼저 Low T 보다 낮은 edge들은 모두 제거한다.
• High T 보다 높은 edge들은 모두 살린다.
• Low T와 High T 사이에 남은 edge들 중, High T와 연결되어 있는 Edge는 모두 살리고 나머지는 모두 버린다.

템플릿 매칭

Convolution을 이용한 Filtering을 어떤 의미에서 Filter와 유사한 구조를 찾는 것으로 볼 수 있다.
Normalized Cross Correlation(NCC)를 사용하여 Template Matching을 수행한다.

$$ s = \frac{\sum_{(u, v) \in I} I_1[u, v] \cdot I_2[u,v]}{\sqrt{\sum_{(u, v)\in I} I_1^2[u,v]\cdot \sum_{(u,v)\in I} I_2^2[u,v]}} $$

분모는 두 이미지(이미지와 필터)의 내적을 수행한다. (즉, 코사인 유사도를 구한다.)
그리고, 분자에 있는 두 이미지의 각 픽셀의 magnitude의 상대적 밝기를 이용해 위 값을 normalize 한다.

그렇게 되면 두 이미지가 유사할수록 1, 유사하지 않을수록 0의 값이 나오게 된다.

느낀 점

대학교 1학년 때 코사인 유사도를 배우고 너무 재밌고 신기해서 수첩에 적어두고 다녔던 것이 생각났다.
이미지 처리 참 재밌는 듯.