DIP10.1~10.2 Edge-based Segmentation (2)

0. 서론

이전 포스트에서는 기본적인 Spatial filter를 적용하여 gradient를 얻고, 그 gradient를 바탕으로 직교하는 edge를 얻는 방법에 대해서 배웠었다. 이번 포스트에서는 기존 방식의 한계를 극복한 edge detector에 대해서 알아보자.

https://do-my-best.tistory.com/entry/DIP10

DIP10.1~10.2 Edge-based Segmentation (1)

 

1. The Marr-Hildreth Edge Detector

먼저 정리하자면 이 방식은 Laplacian of a Gaussian (LoG)를 활용하여 Edge를 추출하는 방식이다.

 

기존 문제점

기존에는 다음과 같은 문제점이 존재했다.

intensity changes는 image scale에 독립적이지 않다 (다양한 크기의 연산을 사용해야 한다.)

급격한 intensity change는 1차 미분값을 튀게하고, 2차 미분 값에 zero crossing 패턴을 야기한다. 

 

해결

따라서 이 알고리즘에선 기존 방식에 필요한 크기에 조정할 수 있는 방식을 채택하여 edge 크기에 알맞은 operator를 채택할 수 있게 하여(예를 들어 blurry edge에선 큰 operator로, sharp edge에서는 작은 operator로), 위와 같은 문제를 해결하고자 하였다.

 

이러한 특징을 갖는 operator는 Laplacian of a Gaussian (LoG)으로, 다음과 같이 정의된다.

이를 가시화 하면 다음과 같다.

위 그림을 본다면 앞서 언급한 크기에 따라 적합한 방식으로 edge를 추출할 수 있음을 알 수 있다. 

 

LoG를 2차 미분 대신 사용 가능한 이유

이를 보면서 가우시안을 2차 미분한 필터를 적용하는 것이 어떻게 가우시안 필터를 먹인 이미지의 2차 미분값(edge)를 근사할 수 있는지에 의문이 생길 수 있다. 이에는 convolution의 특징인 교환법칙과 결합법칙 때문인데,

이에 따라 아래가 성립한다.

 

따라서 LoG필터를 먹인 것이, Gaussian을 먹인 이미지에 2차 미분(Laplacian)한 것과 같으므로, 미분이라는 복잡한 연산 대신 적은 연산량으로도 2차 미분의 효과를 얻을 수 있다. 또한, 라플라시안이 isotropic하므로, 여러개의 커널을 쓸 필요도 없어 효율적이라는 장점도 있다.

 

 

순서

1. 가우시안으로 필터링 한다

2. LoG를 먹인다.

3. zero crossing 포인트를 찾는다.

 + thresholding

 

 

예시

아래는 이에 대한 적용의 예시이다. zero crossing 영역이 너무 많다보니 이에 대한

사진 c는 threshold가 0으로 설정되어 spaghetti effect가 발생한 경우이다. (all the edges form closed loops) 이를 positive threshold를 적용하여 사진 d와 같이 깔끔하게 edge를 뽑아낼 수 있다. (LoG 최댓값의 약 4%) threshold의 효과로 spaghetti effect의 해소 뿐만 아니라 major한 edge만 남고, minor한 edge는 필터링 됨을 확인할 수 있다.

 

이 방식의 추가 장점은 zero-crossing point를 edge로써 판단하기 때문에 edge가 1px이므로, edge를 활용한 이유 문제를 간소화 할 수 있다.

 

 

LoG근사, DoG

LoG대신, 가우시안간의 차를 통하여 LoG를 근사할 수 있다. 

실험적으로 사람의 시각이 방향과 frequency에 대해 일부 범위에 대해서만 수용하므로 1.6:1 비율로 가우시안 필터링 된 결과를 뺀다면 이미지의 기본 특성을 유지하면서 엔지니어링 관점에서 효율적인 근사 LoG효과를 얻을 수 있다고 한다.

 

LoG와 DoG가 같은 값(Zero-crossing 픽셀)을 도출하기 위해서는 LoG의 변수가 반드시 다음과 같은 식을 만족해야한다.

(쨋든 DoG로 LoG를 근사할 수 있고, 이를 일치시키기 위해서는 변수 설정에 특정 조건이 필요하다는 것만 우선 보자)

 

또한 가우시안 커널이 separable 하므로, 1D로 나타내어 효율적인 연산도 가능하다더라~

 

 

 

2. The Canny Edge Detector (★)

 

목표

1. Low error rate. (All edges should be found, and there should be no spurious responses.)

2. Edge points should be well localized. (Prediction이 GT과 가장 비슷하여, 최적이어야 한다)

3. Single edge point response. (GT당 하나의 Prediction만, 실제 edge당 하나의 예측 edge만)

 

 

자세한 설명

Circular 2D-Gaussian function으로 첫 smoothing하고 gradient를 도출한 이후, gradient magnitude와 direction으로 각 포인트에 대해 edge 강도와 방향을 예측한다.

 

어떻게 gradient magnitude와 direction으로 edge를 예측하는가? -> 방법

1. Gradient의 강도와 방향을 계산한다

2. Nonmaxima suppression으로 이러한 ridges를 얇게하여 겹치는 edge를 제거한다. (문제 3의 해결)

3. threshold(hysteresis thresholding)로 false edge를 삭제한다 (문제 1의 해결)

 

nonmaxima suppression이란?

gradient (edge의 법선)의 방향을 4개의 방향으로 quantize하고, 이를 바탕으로 suppression한다 

 - Gradient quantization 

 

 - Suppression (동일 방향에 대한 통합)

 

hysteresis thresholding

아래 threshold(TL), 위 threshold(TH)로 thresholding하는 것이다.

이렇게 설정된 gNH와 gNL를 바탕으로, gNH ( x,y )에서 방문하지 않은 픽셀을 순회하면서, 방문된 픽셀에 연결된 픽셀 중 gNL(x,y)에 있는 픽셀을 valid edge pixels로 설정한다. 이렇게 gNH(x,y)에 존재하는 모든 픽셀이 방문되지 않았다면 gNH순회부터 다시 시도하고, 다 방문되었다면 gNL에 존재하는 나머지를 invalid edge pixel로 설정한다. 이렇게 만들어진 gNL에 gNH을 뺌으로서 edge를 detection하는 것이다.

 

결과

앞서 제시했던 문제를 해결하여 다른 알고리즘에 비해 주요 edge의 detail이 매우 살아나면서, 관련없는 feature를 없애 깔끔한 edge를 도출함을 확인할 수 있다.

 

 

참고

https://carstart.tistory.com/188

[Corner Detection] #2 캐니 에지(Canny Edge)

 

 

3. LINKING EDGE POINTS (서론)

실제로 edge detection을 한다면 noise때문에 edge가 끊어지거나, 잘못된 edge 연결을 하는 등 오류가 많이 발생한다. 그래서 edge detection이후 linking algorithm을 적용하여 edge pixels을 연결하여 의미있는 edge나 region boundary를 도출한다.  

이번 챕터에서는 이 알고리즘이 어떻게 적용되는지에 대해서 알아보자.

 

4. Local Processing

특정 기준에 따라 특성을 공유하는 edge픽셀 끼리 연결한다. 다음은 그 기준에 대한 서술이다.

 

4-1. 판단 기준 (E는 크기에 대한, A는 방향에 대한 Threshold)

(1) the strength (magnitude)

(2) the direction of the gradient vector.

즉, edge point와 비교 edge point간의 크기와 방향 차가 일정 범위 이하인 것 끼리 유사하다고 판단하고, 연결하는 방식이다. 그렇다면 이러한 비교 edge point를 어떻게 판단할까? 다음은 그에 대한 설명이다.

 

 

4-2. 비교 기준

1. gradient magnitude와 angle arrays를 구한다

2. 다음 조건에 부합한 g( x, y )를 만든다 // (TM : threshold, A : specified angle direction, TA : 방향 범위)

3. g를 X축 방향으로 순회하며 특정 L보다 짧은 놈들이 있다면, 비교한다 

4. 3번의 순회축을 다른 방향으로 설정하고 진행한다

 

다음은 그 예시이다.

 

결과

직선이라는 구조를 알기 때문에 2방향만 해도 됐다~ 하지만 구조를 모른다면?, 혹시 타원이라면, 혹시 각도가 50도인 직선이라면?(뒤의 Hough Transform이 이를 해결)

 

 

5. Global Processing Using the Hough Transform (★)

사용 이유

이전에 나온 방식은 복잡도를 줄이기 위해 사전에 정의된 방향에 대해 순회하며 엣지를 연결하는 방식이었다. 하지만, 연결하고자 하는 엣지가 어떠한 방향성에도 포함되지 못하는 경우는 어떻게 처리할까? 이를 위해, 모든 edge point가 candidate이 되어, 적절한 edge를 연결하는 방식의 필요성이 대두되었다.

 

아이디어

모든 가능한 연결을 고려하며, 그 라인에 포함되는 edge point를 구하는 것은 너무나도 복잡하다. 그렇기 때문에,  xy plane에서 고정된 직선(a,b -> y = ax + b)위의 edge point점(x,y)를 찾는 문제에서, ab plane에서 선(x,y -> b = -xa + y)끼리 만나는 점(a,b)를 찾는 문제로 치환하면 문제의 복잡도가 확 줄어든다. (왜냐하면, xy plane에서는 선을 따라서 모든 edge point의 조합으로 선을 만들고, 그 선 위에 몇개의 edge point가 포함되는지 판단해야 하지만, / ab plane에서는 edge point를 상수로 여겨, x,y로 직선을 만들고, (a,b)를 지나는 선분의 갯수만 카운팅 하면 그 a,b가 만드는 직선 위를 지나는 edge point 갯수를 쉽게 구할 수 있기 때문이다. )

간단하게 복잡도로 나타내보자면, 이전 방식은 N개의 점이 있을 때, 가능한 직선의 갯수는 N^2개, 하나의 선분에 대해 N개의 점이 그 선 위에 있는지를 판단하는 복잡도는 O(N)이다. 따라서 총 복잡도는 O(N^3)이다. 하지만 허프 변환은 N개의 점에 대하여, 최대 M개의 a,b cell을 체크한다고 할 때, 복잡도는 O(NM)이다.  

 

 

 

하지만 ab plane으로 끌어온것은 좋았으나, 문제는 a,b 너무나도 많은 경우의 수를 갖고 있다는 것이다. (ex : 직교하는 라인을 만드려면 a가 무한대로 커저야 한다) 따라서 이를 아래와 같은 문제로 치환하여, 더 제한된 범위로 효율적인 문제로 표현하여 풀 수 있다. 

이를 이용하여 ab plane과 같이 점의 공간에서 파라미터 공간으로 가져온다면, 다음처럼 표현된다

이제 가능한 경우의 수인 모든 theta와 p의 조합에 대해서, 몇개의 직선이 그 점을 지났는지 기록해야 한다. 이를 Accumulator cells 위에서 한다

 

Accumulator cells

이렇게 생긴 공간에 카운팅이 끝난다면 가장 큰 갯수를 가진 cell을 찾을 수 있을 것이고, 그 cell 좌표가 가장 많은 edge point를 관통하는 직선을 나타내는 파라미터일 것이다.

 

여기서 가장 많이 겹치는 선을 보자면 A와 B일 것이다. B를 예로 보자면 p = 50 / theta = 45이다. 즉, 45도로 50만큼 떨어진 곳에서 부터 시작하는 직선이다. 즉, 2,3,4를 지나는 직선을 의미한다.

 

 

 

다른 형상의 Hough transformation

xy plane에서 많은 조합의 파라미터에 모든 포인트를 넣으면서 몇개나 선분 위에 존재하는지를 일일히 새는 것에서 파라미터 plane에서 모든 포인트에 대해 어떤 파라미터 위에 올라갈 수 있는지 체크하는 방식으로 바꾸는 기본 아이디어를 채택하면, 직선 뿐만이 아니라 우리가 원하는 형태의 edge linking을 할 수 있다. 만약 가장 많은 edge point를 지나는 원을 찾고 싶다면 아래와 같이 표현할 수 있다.

여기서 xy plane문제를 c1,c2,c3 plane으로 가져오면 문제를 쉽게 해결할 수 있다.

 

 

예시

활주로를 찾는 예시이다. Canny's algorithm으로 Edge map찾고, Hough transformation으로 가장 긴 (즉, 가장 많은 edge point가 한 선으로 연결 될 수 있는 ) parameter를 Hough parameter space에서 찾은 이후, 일정 크기 내의 빈 공간을 채움으로서 활주로를 강조한다.

 

참조

https://blog.daum.net/swrush/588

IDL에서 허프 변환 (Hough Transform) 사용법