Computer Vision - Edge Detection

- gradient가 변하는 부분은 사실 한 Line이 아니라 영역이다. 그래서 이렇게 굵게 굵게 나온다. 사실상 edge라고 보기에는 좀 부족하다

- 그렇다면 일반적인 edge point를 결정하고 연결해서 curve를 만드는 방법을 알아보자.

- 최적의 edge검출기는 false postive(아닌데 맞다고 찾은 녀석), false negative(진짜 edge를 못찾음)를 줄이고, localization, single response를 조건을 만족해야 한다.

 

1. noise smoothing : 가우시안 활용

2. edge에 반응하는 필터 설계 (matched filter를 만든다고 한다) 라플라시안 처럼 gradient의 극점을 찾을 수 있는 필터를 설계한다.

3. edge의 위치를 결정한다. (threshold를 통해서 판단한다. 혹은 너무 두껍지 않게 thinning한다.)

1. Canny Edge Detector

- (우측)여러 영상에 대해서 (좌측)다양한 종류의 edge가 나올 수 있다.

- 캐니에지 검출기는 각 픽셀에 대해 아래 세가지를 찾는다. (gradient 크기, gradient 방향)

1. edge의 normal : gradient의 방향이다. 에지의 방향과 수직이다.

2. edge의 direction : 에지의 방향이다.

3. edge의 strength : 에지의 크기, gradient 크기(intensity 변화량의 크기)

* 참고로 0부터 180도까지 방향들을 0, 45, 90, 135도 네개의 bin(d1,d2,d3,d4)에 나누어 넣는다. 

Step1. 1차 미분 가우시안 필터 적용

- 1차 미분한 gaussian 마스크로 필터링하여 noise smoothing 과 gradient계산을 수행

- 참고로 미분한 gausian 필터의 표준편차가 커지면 smoothing되는 정도가 커지고 굵은 edge들만 찾게된다.

- 이 단계에서 gradient의 크기, 방향을 구한다.

Step2. Non-maximum suppression

 

- 이렇게 찾은 gradient 방향 , gradient 크기 map에서 local maximal 빼고는 다 gradient value가 0이라고 생각한다 (가장 두드러지는 지점 외에 관심 없음! 이런걸 nonmaximun suppression이라고 한다.)

- non-maximun suppression을 거쳐야 edge가 적절히 얇아지도록 할 수 있다.

- 더 자세히 설명하면 local maximal에서부터 edge방향(gradient에 수직 방향)을 따라서 가면서 (이동방향을 중심으로) 양방향의 작은 gradient는 다 0으로 만든다.

- 위 그림에서는 q를 살펴보자. gradient와 수직인 방향이 edge의 방향이다. edge의 방향을 중심으로 양옆의 gradient값을 비교해서 값이 작으면 p, r을 모두 0으로 만든다.

Step3. threshold (Canny Edge Detector)

- thresholding : 적절한 정도를 설정해서 그 문턱값보다 gradient 크기가 크다면 edge 판단에 활용할 수 있다.

Step4. Edge linking

- threshold와 nonmaximun suppression으로 edge의 후보들을 골랐다.

- 하지만 이제는 찾은 에지들을 연결하는 문제가 남았다.

- 높은 threshold를 넘은 점을 시작점으로 마스크가 따라서 이동한다. 

- 빨간 화살표가 edge의 방향이고 그와 수직인 화살표가 gradient방향이다.

- 에지를 쭉 따라가려는데 어떻게 r,s 중 하나를 edge라고 판단하고 이어야 할까?

 

- 이런 상황을 고려해서 threshold를 high t, low t 두개를 설정해둔다. high t보다 작지만 low t 보다 높으면 edge linking할 점으로 쳐주는 것이다.

- 즉, 밝기 변화가 큰 지점에서 시작해서 에지 방향을 쭉 따라가는데 low threshold를 따로 설정해서 에지로 채택할지 말지 결정한다.

 

- high t는 edge 시작점들이 되고 low t는 linking 할 점들을 선별하는데 추가로 활용된다.

2. Example (Canny Edge Detector)

- gradient를 구하고 thresholding으로 자잘한 선들을 제거한다. 그리고 non-maximum suppression으로 thinner한 line을 결정한다.

3. Hough transform

- x,y공간에서의 직선은 기울기와 절편으로 이루어진 공간에서 한 점으로 변환이 된다.

- 반면 x,y공간에서의 한 점은 y= mx+b -> m = 1/x(y-b)로 직선으로 변환된다.

- 이미지에 있는 edge를 탐색하고 싶다.

- edge를 구성하는 점들을 hough space로 transform한다.

- hough space를 작은 타일(bin)들로 쪼개서 transform된 직선이 지나가는 지점들에 +1을 해준다.

- 이렇게 총 6개의 점들에 대해서 변환을 수행하고나면 6개 점을 잇는 직선이 hough space에서 한 점으로 가장 많이 체크되었을 것이다.

- 이렇게 투표하는 방식으로 edge를 찾아낸다.

- 두 점들을 Hough transform하면 교차점이 생긴다.

- 저 교차점을 다시 image space로 옮겨오면 두 점을 잇는 직선이 된다.

- 즉 공간상에서 line을 구한 셈이다.

- 총 7개의 점을 hough transform하면 7개의 직선이 생긴다.

- 그 7개의 직선이 교차하는 부분이 hough space에서 가장 많은 투표를 받았을 것이다.

- 가장 많은 투표를 받은 지점을 다시 Image space로 옮겨보면 하나의 직선이 나온다.

 

- 근데 여기 한가지 문제가 있다. 만약 수직선이라면 m이 무한대가 된다. 무한대를 표현할 파라미터 공간이 없기 때문에 새로운 표현법을 사용한다.

- 바로 직선을 세타와 로우로 나타내는 방법이다. 그럼 한정된 매개변수 공간에서 모든 직선을 표현할 수 있다.

- 직선의 점들을 하나씩 변환하여 세타와 로우를 값을 구해서 공간에 투표를 했더니 한 점이 두드러져 보인다.

- 한 점을 허프 공간에 옮겨 놓으면 직선이 나온다 = 이미지의 한 점을 지나는 직선이 로우,세타에 따라 무수히 많다.

- 그 무수히 많은 녀석들중 가장 투표율이 높은 애가 여러 점들을 동시에 지나는 직선이다.

- noise가 껴서 최다 투표 지점이 좀 넓을수도 있다. 이는 hough space의 bin의 크기에 따라서 판단이 달라질 수 있다.

- 그리드가 너무 좁거나 너무 넓어도 정확도가 떨어진다.

- 그리드가 너무 좁아지면 연산량이 많아진다.

*참고로 bin의 값을 증가시킬때(voting할때) smoothing처럼 해당하는 bin만 증가시키는게 아니라 주변 bin도 작은 비율로 증가시키는 방법도 있다.

*edge gradient와 함께 활용하는 방법도 있다. gradient direction 세타를 알고 있기 때문에 점을 허프 공간에서 직선으로 변환할때 세타가 고정될 수 있다.

4. 최종 에지 검출 프로세스

- 일단 케니 에지 검출기로 에지를 추출한다.

- hough transform으로 교차 구간을 잡는다.

- 교차 지점을 다시 에지로 변환하여 매끄럽게 에지들을 이어서 연결한다.

- 이런 랜덤 포인트에 경우 뜬금 없는 에지들이 생길 수도 있다. (허프 변환의 단점이다) 

5. Hough transform for circles

- 원을 찾는 문제의 경우 hough transform이 활용될 수 있다.

- 한 점을 hough space로 옮길때 a,b,r 삼차원 공간으로 옮긴다.

- 제일 투표율이 높은 지점 (x,y,r)을 선택한다.

- 원을 구성하는 네 점이 있을 때, 각 점을 허프 공간으로 옮긴다.

- 거기서 제일 투표율이 높은 (x,y,r)이 원래 이미지 공간에서의 원의 중심, 반지름이 된다.