[Computer Vision] Edge detection

해당 글은 건국대학교 지서원 교수님의 컴퓨터 비전 수업 내용을 정리한 글입니다.

 

Image gradient.

 

ex

 

위 이미지와 같이 이미지 상의 불연속성(edge)이 발생하는 주요 원인은 다음과 같습니다:

• 깊이의 불연속성(depth discontinuity): 물체와 물체, 혹은 물체와 배경 사이의 물리적인 거리 차이로 인해 발생합니다.
• 조명의 불연속성(illumination discountinuity): 빛의 방향에 따른 그림자나 강한 반사 등으로 인해 밝기가 급변하는 곳에서 발생합니다.
• 표면 색상의 불연속성(surface color discontinuity): 물체 표면 자체의 색상이나 패턴, 재질이 바뀌는 경계에서 발생합니다.

 

ex

 

위 그림은, 픽셀의 밝기(intensity)를 3차원 지형도의 높이(z축)로 나타낸 그래프입니다. 이 그래프에서 edge는 밝기가 극단적으로 변하는 절벽과 같은 구간으로 시각화됩니다. 이때 edge의 종류는 다음의 세 종류로 나눌 수 있습니다:

(left) step edge, (middle) ramp edge, (right) roof edge

• step edge: 흑과 백이 뚜렷하게 나뉘는 가장 이상적인 형태의 edge입니다.
• ramp edge: 현실의 카메라 렌즈 블러나 조명 등으로 인해 픽셀 밝기가 점진적으로 서서히 변하는 형태입니다.
• roof edge: 얇은 선이나 빛의 하이라이트처럼 밝기가 올라갔다가 곧바로 다시 떨어지는 형태입니다.

 

How to detect image edge?

 

일반적으로 함수에서 값이 급변하는 불연속적인 부분, 즉 edge를 찾기 위한 수학적인 접근법은 미분(derivative)을 취하는 것입니다. 미분값은 밝기 변화의 기울기를 의미하므로, 불연속적인 지점에서 미분값이 매우 크게 나타나기 때문입니다. 하지만 디지털 이미지는 (domain이) 연속적인 함수가 아니라, 하나하나 끊어져 있는 픽셀(descrite signal)들의 배열입니다. 따라서 연속 함수에서 쓰이는 일반적인 미분 공식을 그대로 쓸 수 없고, 대신 finite difference(유한 차분)이라는 방식을 사용해야 합니다.

 

Finite differences.

 

finite difference는 연속 함수에서의 극한의 개념을 이산적인 픽셀의 간격으로 대체한 방법입니다:

forward difference

 

이는 연속적인 도메인에서의 미분 정의입니다. 이를 중앙을 기준으로 difference를 구하면 다음과 같습니다:

centeral difference

 

이를 이산 신호(디지털 이미지)에 맞게 극한 기호를 제거하고 간격 h를 2로 설정하여 양옆 픽셀 차이를 이용해 미분값을 근사하면 다음과 같습니다:

centeral difference

 

그리고 이를 1d filter를 이용해 convolution 연산을 통해 구할 수 있으며, 이때 filter는 [1, 0, -1]입니다. 하지만 이런 1차원 미분 필터는 노이즈에 취약하므로, 이를 해결하기 위해 sobel filter가 제안되었습니다.

 

The sobel filter.

 

sobel filter는 미분을 수행하는 방향과 직교하는 방향으로 blurring 필터를 결합하여 노이즈를 줄입니다:

sobel filter

 

그리고 가로 방향과 세로 방향의 픽셀 차이를 구하기 위해, 각각 가로, 세로 방향의 sobel filter를 만들어줄 수 있습니다:

sobel filter

 

다음은 예시입니다:

ex

 

예시를 보면 수직과 수평 필터의 특징을 알 수 있습니다. 수직 필터는 건물의 세로 기둥이나 세로 실선들을 선명하게 잡아내고, 수평 필터는 층간 구분선이나 가로 패턴을 잡아내는 것을 시각적으로 확인할 수 있습니다.

 

Several derivative filters.

 

sobel filter 외에도 가중치나 크기가 조금씩 다른 여러 가지 미분 필터가 존재하며, 각각 노이즈에 대한 민감도나 edge 검출의 날카로움 정도에 차이가 존재합니다:

several derivative filters

 

* prewitt filter는 sobel filter와 매우 유사하지만, 중심 픽셀에 가중치를 주지 않고 모든 픽셀에 동일한 가중치(1)를 부여합니다. 수평/수직 방향으로 균일하게 평균을 내기 때문에 계산이 단순합니다. 하지만 중심 픽셀을 강조하는 sobel filter에 비해 edge의 정확한 위치를 찾는 데는 약간 불리할 수 있습니다.

 

* scharr filter는 sobel filter보다 중심 픽셀에 훨씬 더 큰 가중치(3, 10 등)를 부여합니다. 3x3 크기의 작은 kernel에서는 sobel filter보다 회전 대칭성이 뛰어나서 대각선 방향의 미세한 각도 변화를 훨씬 더 정확하게 계산해 냅니다. edge의 뱡향을 정밀하게 구해야할 때 유리합니다.

 

* roberts filter는 3x3이 아닌 2x2 크기의 아주 작은 kernel을 사용하며, 대각선 방향으로 인접한 픽셀끼리의 차이를 계산합니다. 크기가 작아 연산 속도가 매우 빠르고 얇고 날카로운 edge를 잡는 데 유리합니다. 하지만, blurring 효과가 전혀 없기 때문에 노이즈에 매우 취약하다는 치명적인 단점이 있습니다. 노이즈기 없는 아주 깔끔한 이미지에만 주로 쓰입니다.

 

Image gradient.

 

이미지는 2차원 공간(x,y)의 함수이므로, 각 방향의 편미분 결과를 벡터 형태로 묶은 것을 gradient라고 합니다. 수식으로는 다음과 같이 표현되며, 이는 미분을 다변수로 일반화한 개념입니다:

image gradient

 

gradient vector는 항상 픽셀 밝기가 가장 가파르게 증가하는 방향을 가르키며, 이미지의 gradient를 구하는 과정은 다음과 같습니다:

1.

 

우선 사용할 미분 필터(예: Sx, Sy sobel kernel)를 선택합니다.

2.

 

그 후 원본 이미지 f와 각각 convolution 연산을 수행하여 x축과 y축에 대한 편미분을 구합니다. 이렇게 image gradient를 구하면 다음의 두 가지 정보를 얻을 수 있습니다:

 

image magnitude and direction

• magnitude: edge strength를 나타냅니다. 픽셀 밝기 차이가 클수록 값이 큽니다.
• direction: 밝기가 가장 가파르게 증가하는 방향을 나타냅니다.

 

다음은 예시입니다:

ex

 

다음의 그림은 gradient vector가 가리키는 방향(밝기가 변하는 방향)과 실제 edge의 방향은 서로 수직을 이룬다는 것을 보여줍니다:

using the gradient to determine edge strength and direction at a point. note that the edge direction is perpendicular to the direction of the gradient vector at the point where the gradient is computed. each square represents one pixel.

 

Edge detection.

 

실제 신호(이미지)에는 항상 미세한 노이즈가 존재합니다. 이 상태에서 바로 미분을 해버리면 노이즈가 극단적으로 증폭되어, 진짜 edge가 어디인지 찾을 수 없게 됩니다:

differentiation is very sensitive to noise

 

이 문제를 해결하기 위한 핵심 전략은 미분하기 전에 먼저 blurring을 하는 것입니다. gaussian filter 등을 이용해 signal을 부드럽게 만든 후 미분을 수행하면, 노이즈는 억제되고 진짜 edge 위치에서만 깔끔하게 1차 미분 함수의 peak를 찾을 수 있습니다:

differentiation is very sensitive to noise

 

이를 바탕으로 하는 기본적인 edge detection 전략은 다음과 같습니다:

1. 노이즈 제거를 위한 이미지 smoothing(using gaussian).
2. gradient 계산을 통한 edge 후보군 도출(using sobel).
3. 1차 미분의 꼭짓점을 찾아 edge 위치 특정(localizing).
4. 임계값(thresholding) 처리를 통해 최종 edge 결정.

 

The Canny edge detector.

 

Canny edge detector는 컴퓨터 비전에서 가장 유명하고 널리 쓰이는 edge detector입니다. 이는 기본 4단계 전략에 두 가지를 추가했습니다:

1. Smoothing image
2. Computing image gradients
3. Localizing edge(NMS, Non-maximum suppression)
4. Hysteresis thresholding

 

NMS, Non-maximum suppression은 가장 값이 큰(maximum) 값 하나만 남기고 나머지는 지우는 기술입니다. 미분만 한 상태에서는 edge가 여러 픽셀 두께로 뭉특하게 나옵니다. canny detector는 gradient 방향을 따라 픽셀들을 검사하면서, 가장 값이 큰 픽셀 하나만 남기고 나머지는 모두 지워버립니다(suppression):

NMS

 

또한 Hysteresis thresholding은 두 개의 threshold를 사용하는 기술입니다. 단순히 하나의 임계값으로 edge를 자르면 점선처럼 edge가 끊어지는 문제가 발생하기 때문에, 두 개의 임계값(high threshold T, low threshold t)을 사용합니다:

• Strong edge(S > T): 무조건 진짜 edge로 인정합니다.
• Weak edge(S < T but S > t): 기본적으로는 보류하지만, strong edge와 연결되어 있는 경우에만 진짜 edge로 살려줍니다.
• No edge(S < t): 노이즈로 간주하고 완벽히 지웁니다.

A: Strong edge, B: Weak edge but no real edge(연결된 strong edge가 없어서), C: Weak edge but real edge(연결된 strong edge A가 있어서).

 

edge detection 전 노이즈를 제거하기 위해 gaussian blurring을 수행하는데, 이때 gaussian filter의 퍼짐 정도를 결정하는 파라미터가 σ입니다. 만약 작은 σ(예: 1)를 사용한다면, blurring이 약하게 들어가므로, 이미지의 미세한 특징(fine feature)이나 얇은 선들을 edge로 잘 찾아냅니다. 하지만 큰 σ(예: 2)를 사용하면, blurring이 강하게 들어가 자잘한 텍스처나 노이즈를 다 뭉게지고, 물체의 큼직한 윤곽선 등 큰 규모의 edge 만 남게 됩니다. 즉, 내가 찾고자 하는 대상이 무엇인지에 따라 적절한 σ값을 조절해야 합니다:

the choice of σ

 

Derivative of Gaussian.

 

convolution 연산의 결합 법칙을 이용하면, 계산 효율성을 높일 수 있습니다. 기존 방식은 1) 이미지에 gaussian filter를 씌운다. 2) 그 결과에 미분 필터를 씌운다 였습니다. 하지만 convolution의 derivative theorem에 따르면 다음과 같이 정리할 수 있습니다:

derivative theorem of convolution

 

이는 이미지(f)를 매번 blurring하고 미분할 필요 없이, 미리 gaussian filter(h) 자체를 미분해 둔 새로운 필터를 하나 만들어두고, 이를 원본 이미지에 한 번만 convolution 연산하면 결과가 똑같습니다. 이렇게 하면 이미지 전체를 훑는 무거운 연산을 두 번에서 한 번으로 줄여 엄청난 연산량 이득을 얻을 수 있습니다:

derivative of gaussian

 

다음은 원본 gaussian filter의 3D 형태와, 이를 1차 미분하여 만든 Derivative of Gaussian(DoG와는 다름)의 3D 형태를 시각적으로 나타낸 것입니다:

gaussian vs. derivative of gaussian

 

Edge detection with the second-order derivative.

 

지금까지는 1차 미분을 해서 그 값이 최대치(peak)가 되는 곳을 edge로 찾았습니다. 수학적으로 1차 미분이 최대치가 되는 지점은, 한 번 더 미분한 2차 미분 그래프에서는 값이 0을 통과하는 지점(zero-crossing point)이 됩니다.

 

* 1차 미분을 하면 한 점으로 edge detection을 할 수 있는 것이 아니라, 일정한 threshold를 넘는 구역을 edge로서 탐지하는 것입니다. 그 기준이 되는 threshold를 설정하는 것 또한 어렵습니다(얼마나 커야 edge일까?). 한편 2차 미분을 사용하면 한 점(zero-crossing point)으로 edge를 찾을 수 있기 때문에 유리하며, 절대적인 기준 없이 edge info.를 얻을 수 있습니다.

 

따라서, 2차 미분을 한 뒤 값이 양수에서 음수(또는 그 반대)로 바뀌는 zero-crossing을 찾으면 더 정밀하게 edge의 중심을 잡아낼 수 있습니다:

Edge detection with the second-order derivative

 

1차 미분 때와 마찬가지로, 픽셀로 이루어진 이미지에서 2차 미분을 하려면 finite differences를 사용해야 합니다. 2차 finite differences 공식은 다음과 같습니다:

Edge detection with the second-order derivative

 

1차 미분을 2차원(x, y)으로 확장한 것이 gradient였다면, 2차 미분을 2차원으로 확장한 연산자가 바로 laplacian입니다:

Laplcian kernel

 

이 수식을 행렬(kernel)로 표현하면 아래의 3x3 kernel이 되며, 가장 기본적인 형태는 십자가 모양으로 값이 들어간 [[0,1,0], [1,-4,1], [0,1,0]]이며, 대각선 방향까지 고려하여 가운데가 -8이나 8이 되는 확장된 laplacian kernel들도 존재합니다.

 

* 어짜피 zero crossing point만 찾으면 되기 때문에, kernel 전체의 부호가 바뀌어도 상관없습니다.

 

Laplacian of Gaussian (LoG) filter.

 

LoG

 

1차 미분 때 노이즈 문제를 해결하기 위해 derivative of gaussian filter를 사용했습니다. laplacian filter도 마찬가지로 노이즈에 매우 취약하기 때문에, 똑같은 전략을 사용해줍니다. gaussian filter와 laplacian filter를 하나로 합친 LoG를 사용합니다. 즉, 원본 이미지에 LoG filter를 한 번만 씌우면, 노이즈가 부드럽게 제거됨과 동시에 2차 미분이 수행됩니다. 결과 그래프를 보면, 노이즈가 없는 깔끔한 파동 형태가 나오며, 여기서 값이 0을 가로지르는 지점을 찾으면 그곳이 edge입니다.

 

* output signal에서 0인 부분이 무조건 edge일까요? zero "crossing" point가 edge입니다. 즉, (+)에서 (-)로 가면서 0을 지나거나, (-)에서 (+)로 가면서 0을 지나는 point들이 edge이지, 접선으로 0을 지나는 점들은 edge가 아닙니다.

 

다음은 예시입니다:

(left) LoG, (right) laplacian filtering w/o gaussian. there are a lot of noises.

(left) LoG, (right) Derivative of Gaussian filtering

LoG vs. Derivative of Gaussian.

 

다음은 Gaussian, Derivative of Gaussian and LoG를 3차원으로 시각화 한 결과입니다:

Gaussian vs. Derivative of Gaussian vs. LoG

 

What about DoG?

 

unsharp masking (revisit).

 

한편, 원래의 신호에서 blurred signal을 빼버리면, 이미지의 고주파 성분인 edge 만 남게 되는데, 이를 unsharp mask(DoG, Difference of Gaussian)이라고 부릅니다. 이 마스크를 원본에 다시 더해주면 윤곽선이 뚜렷해지는 sharpening 효과를 얻을 수 있습니다.  한편, 위 그림에서 Unsharp mask를 보면, zero crossing point가 생깁니다. 그리고 그 점은 정확히 original signal에서의 edge입니다. 즉, unsharp mask를 통해서 LoG를 근사할 수 있다는 것입니다.

 

Laplacian of Gaussian은 연산량이 많습니다. 이는 DoG를 통해서 거의 완벽하게 근사할 수 있으며, σ값이 서로 다른 두 개의 gaussian filter를 빼서 만들 수 있습니다.