Edge Detection

Edge Detector

이전에 라플라시안 커널 에서 다뤘던 내용의 연장입니다.

값은 상관없지만, 방향성이 있어야 하며, 합이 0인 커널을 구현하면 해당 방향으로의 line edge를 검출할 수 있습니다.

하지만, 위 영상 I 처럼 극명하게 경계가 정해지는 영상은 드뭅니다.
대부분의 영상은 아래의 가운데 영상처럼 경계가 명확하게 구분되는 편은 아닙니다.

따라서 이런 경우까지 고려하기 위해 2중 미분을 통해 edge를 검출하는 것이 좋습니다.

하지만, 영상에 노이즈가 낀 경우에는 2중 미분을 한다고 해서 edge를 검출할 수 없습니다.

따라서 우선 미분을 하기 전에 smoothing filter를 적용해서 노이즈를 줄인 후 edge를 검출하면 검출 성능이 올라갈 수 있습니다.

물론, smoothing filter를 적용하면 경계 역시 블러될 수 있습니다.
그럼에도 불구하고, 경계는 찾을 수 있습니다.

참고로 미분 역시 컨볼루전으로 간단하게 처리될 수 있기 때문에 아래와 같이 연산 과정을 간략하게 할 수 있습니다.
(e.g. [1, 0]을 컨볼루전 하면 미분된 효과를 얻을 수 있습니다.)

이런식으로 경계를 강조한 뒤에 threshold를 하면 edge를 검출할 수 있습니다.

---

Canny edge detector

Canny edge detector은 위에서 살펴본 기본적인 edge 검출 방식을 개선시킨 방식입니다.

Edge detector	Canny edge detector
1. smoothing filter (가우시안의 미분) 적용	1. smoothing filter (가우시안의 미분) 적용
2. gradient의 크기만 구함	2. gradient의 크기와 뱡향을 구함
	3. Non-maximum suppression
	4. Hysteresis thresholding

1, 2번 까지 진행하고 threshold 하는 경우에는 차이가 없습니다.
하지만 3, 4 번의 과정을 추가로 진행하여 더 나은 edge를 검출할 수 있습니다.

Non-maximum suppression

기존의 방식대로 검출할 경우 gradient의 크기만을 구하기 때문에 검출하는 edge의 두께가 두꺼워지는 문제가 발생합니다.

하지만, Canny 방식은 방향 역시 구하기 때문에 선의 두께를 얇게 만들어주면서 edge를 결정할 수 있습니다.

그러나, 여전히 약한 edge가 존재하는 문제가 있습니다.

Hysteresis thresholding

약한 edge는 주면의 edge와 linking 하는 방식으로 해결하게 됩니다.

그렇게 하기 위해 일단 Low, High threshold를 우선 정합니다.
이후에 threshold시 아래와 같은 판단을 거쳐 edge를 확정합니다.

• threshold 값이 Low 보다 낮다?
  edge가 아님.

• threshold 값이 high 보다 크다?
  edge임.

• threshold 값이 Low, High 사이이다?
  약한 edge임. 따라서 양 쪽에 edge가 있을 경우에만 edge로 판단.

이렇게 진행된 Canny 방식은 확실히 이전보다 나은 성능을 보입니다.

참고로, 처음의 가우시안 필터의 세기를 크게 한다면 강한 에지만 살아남게 됩니다.

---

Hough transform

Hough transform은 line detector 중 하나인데, 그 방식이 피팅(투표)하는 방식으로 좀 특이하다.

우선 영상에서 edge points를 찾아내고, 이후에는 무수히 많은 직선을 그었을 때,
가장 많은 edge points를 지나는 직선이 선택되는 방식이다.

이 때 드는 의문점이 있다.
무수히 많은 직선을 긋는다는게 시간복잡도 상으로 간단하게 구현 가능한걸까?
일반적인 방식으로 영상에 긋는 방식으로는 불가능 할것이다.
하지만, 영상을 변환하는 과정을 거치면 가능해지는데, 그 방식을 살펴보자.

Hough space

Hough space는 직선의 방정식의 파라미터를 축으로 하는 공간이다.
따라서 영상 공간에서의 직선은 Hough 공간에서는 점으로 표시된다.

반대로 영상 공간에서의 점은?
해당 점을 지나는 직선은 무수히 많을 것이다.
따라서 그 무수히 많은 직선을 Hough 공간상에서 무수히 많은 점으로 찍으면 하나의 직선 형태로 표현될 것이다.

이를 응용해서 무수히 많은 점을 지나는 직선을 찾는 방식은 위 그림과 같다.

영상 공간의 점은 Hough 공간에서 직선으로 표현되기 때문에,
Hough 공간에서의 교점은 영상 공간에서의 모든 점을 지나는 직선이 된다.

하지만, Hough 공간을 확대해보면 실제로 한 점에서 만나는 경우는 드물기 때문에 약간의 근사를 해야하며 거기서 약간의 오차가 발생할 수 있다.