[2기 광주 박이근] Feature Extraction (Canny Edge)

안녕하세요 

광주멤버십 21-2기 박이근 입니다.

특징 추출(Feature Extraction)에 대해서 아는데로 적어보려고 합니다 ^^

오늘 이 시간에는 선분 추출하는 방법 중 하나인 

캐니 에지 (Canny Edge)에 대해서 알아보려고 합니다.

일반적으로 영상처리나 패턴인식에 있어서 어떠한 특징을 설정하는 작업은 항상 중요합니다.

이러한 특징은 점, 선, 면, 객체 등등 기본적으로 많이 사용하게 됩니다.

이 들중 일반적으로 점은 매우 중요한 역할을 하고 있으며 

일반적으로 특징점이라고 불리우고 있습니다. 

이러한 점을 뽑아내기 위해서는 크게 두가지 방법으로 나누어 집니다.

이미지의 밝기의 상태를 가지고 직접 특징점을 추출하는 방법

그리고 특징을 나타내는 선분을 추출하여 

그 선분의 끝점을 두 개를 특징점으로 추출하는 방법이 일반적입니다.

그렇다면 선분을 어떻게 찾아야 하는지도 중요하겠죠?

자 그럼 에지(Edge)란 무엇일가요 ?

에지란 영상에서 밝기가 급격하게 변하는 부분을 일반적으로 말합니다.

우리가 흔히 모서리를 인지할 수 있게 하는 요인이죠

이 에지를 검출 함으로써 우리는 물체의 위치 모양 크기등에 대한 정보를 쉽게 얻을 수 가 있습니다.

아래 그림과 같이 명암의 색이 급격히 변하는 부분이 에지 라는 것을 알 수 가 있습니다.

그렇다면 이 에지는 어떻게 구하죠?

위의 그림을 보면 명암그림 아래는 3개의 그림이 가지고 있습니다.

첫번째 그림은 올래의 데이터를 y축을 명암값으로 표현한 그래프 입니다.

두번째 그림은 명암에 대해서 미분을 한번 한것이고

세번째 그림은 미분을 두 번 한것이겠죠

맞습니다. 일반적으로 우리는 미분을 이용하여 구하게됩니다. 

1차 미분 방법으로는 여러분이 아시는 Sobel, Roberts, Prewitt 방법 들이 있습니다.

2차 미분 방법으로는 라플라시안 방법이 있습니다.  

(이밖에도 LOG, DOG 등등이 있습니다.)

하지만 이들보다 좀더 우월한 알고리즘이 1986년 

 John F. Canny 에 의해 처음 

Canny Edge Detection 이라는 이름으로 나타나게 됩니다.

그렇다면 Canny Edge는 왜 중요한가? (우리가 왜 알아야 하는가)

이제까지 논의된 에지 검출기들 보다 우월하기 때문입니다.

윤곽을 가장 잘 찾아내면서도 원래 영상의 회색물질과 관련된

모든 에지(Edge)들을 제거할 수 있는 유일한 방법이기 때문입니다.

 

뭐가 우월하다는 건가요 ?  어떤 면에서 우월한가요?

1. 낮은 에러율을 가집니다.

   정확한 모든 에지가 검출되어야 하며

   의사반응(Spurious Response)가 없어야 합니다. 

   즉 검출된 에지가 항상 정확한 에지이어야 한다는 것입니다. 

    

2. 에지 점들의 위치가 정확히 측정 되어야 한다. (Well Localized)

   찾아진 에지가 참 에지와 가능한 가까워야 한다는 것이다.

   검출기에 의해 에지라고 표시된 점과 진짜 에지의 중심 간의 거리가

   최소여야 한다는 것입니다. (양자화와 샘플링을 통하면 틀려질 수 있습니다.)

    

3. 단일 에지 점 응답

   검출기가 각 참 에지 점에 대해서 한 점만 반환을 해야 합니다. 

   참 에지 주위의 지역 최대들의 수가 최소여야 한다

   검출기가 에지 점이 하나만 있는 곳에서 여러 개를 식별하지 말아야 한다는 것입니다.

    

    

    

장점만 있나요? 단점도 있을 거 같은데?

구현이 복잡하고 실행 시간이 훨씬 길다는 것입니다. 

즉 실시간 산업 영상처리에서는 비용과 속도의 요구로 인하여

임계 값 처리된 기울기 방법 같은 방법을 이용하기도 한다고 합니다.

 

 

 

음 그럼 어떻게 구현하는지 궁금한데요?

알고리즘은 일반적으로 5단계로 진행이 됩니다.

 1. Smoothing        

        

노이즈 제거를 위한 스무딩(blur) 작업입니다.

아래 그림을 보면

미분을 하게 되면 잡음에 의하여 noise가 많이 생기는 것을 볼 수 가있습니다.

우리는 이러한 잡음을 제거해 줄 필요가 있습니다.

 

일반적으로 Blur를 수행하는 함수는 미디언 필터 등등 다양한 함수들이 있습니다.

하지만 가우시안 함수를 많이 사용합니다.

그 이유는 중요하니 공부하시길 바랍니다.

그래서 본 논문에서는 가우시안(Gaussian) 필터를 이용하게 됩니다.

일반적으로 가우시안 식을 복잡하게 이용하는 게 맞지만

논문에서는 가우시안 필터 마스크를 이용합니다.

아래와 같은 마스크 필터를 이용하여 컨볼루션(Convolution)을 통하여

회선 값을 업데이트 하게 됩니다.

 

 

자 가우시안 필터를 적용하니 아래의 왼쪽 그림은 오리지날 영상

오른쪽은 위 가우시안 필터를 적용한 적용한 영상입니다.

 

 

 

 2. Finding gradients

 

다음 단계로는 경사(미분)값을 통하여 에지(Edge)를찾는 단계 입니다.

우선 아래 그림을 봅시다. 

보는 것과 같이 두 번째 그림은

첫 번째 이미지의 빨간 선 부분을 이미지를 2차원 그래프로 표현을 했습니다.

그리고 미분을 한 그림이 세 번째 그림입니다.

 

눈 여겨 볼 그림은 3번째 그림에서 각각의 극 값입니다.

이 극 값이 우리가 찾으려는 Edge가 되는 것입니다.

 

Edge를 정의 하자면 Image의 강도(Intensity)가 급격하게 변하는 부분으로 봅니다.

여기서 극 값은 Maximum, Minimum 2군대를 찾을 수 있습니다.

많은 논문에서는 일반적으로 이 두 가지를 합쳐서 Extrema 라고 부릅니다.

 

이렇게 Extrema를 찾기 위해서는 아래 그림과 같이

기본적인 Sobel Mask를 이용하여 컨볼루션 합니다.

Sobel의 필터의 인자값이 궁금하면 곤잘레스 책을 찾아보면 이유가 설명되어 있습니다. 

 

이렇게 X 축과 Y축에 대해서 미분을 하면 각각 영상을 얻을 수 있습니다.

근데 여기서 중요한 건 왜 우리가 X축과 Y축에 대해서 미분을 하였느냐 입니다.

  

어떠한 함수 f(x, y)가 존재한다면 그것을 각 variables 로 미분 하면

아래와 같이 인자로 갖는 벡터를 가지게 됩니다.

                

 

이것은 가장 빠르게 증가한 (most rapid increase) 방향(direction)을 나타냄과

그것의 값(norm)은 크기를 나타낼 수 있기 때문입니다.

 

그래서 우리는 이 norm을 통하여 증가 량을 비교할 수 있으며

이 Direction에 대하여 방향을 구할 수 있기 때문입니다.

 

 

 

 

그럼 이 Direction과 Norm은 어떻게 구하나요?

 

먼저 강도(Norm)를 구해야 합니다.

아래 그림과 같이 피타고라스의 정리를 통하여 경사 강도를 얻을 수 있습니다.

 

일반적으로 강도의 크기를 얻는 방법입니다.

 

하지만 다른 방법으로는 아래와 같이 유클리디안 거리를 사용하지 않는

아래와 같이 대각선을 고려하지 않는 맨하탄 거리를 이용하는 방법도 있습니다.

 

 

다음으로 방향 (Direction) 구해야 합니다.

이는 아래 그림과 같이 삼각함수를 이용하여 방향을 구할 수 있습니다.

x축과 y축 방향에 대해서 삼각함수를 이용하면 각도(Angle)를 구하게 됩니다.

                  

우리는 X축의 미분값과 Y축의 미분값을 가지고 있다. 이미 소벨마스크를 통하여

그렇기 때문에 삼각함수인 아크탄젠트를 이용하여

아래와 같이 식을 이용하면 각도 세타를 얻을 수 있습니다.

 

 

 

이 각도를 구하게 된 다음 각각의

방향성에 있어서는 다음 단계에서 사용하기 위하여 각도를 그룹화 시켜 줍니다.

아래 그림과 같이 5개의 구역 ( 0, 45, 90, 135, 180)으로 구분하게 됩니다.

 

                

 

즉 논문에서는 일반적으로 -22.5 에서 22.5도를 기준으로 이를 0도(상방향)로 구분하고 있습니다.

총 그러니 8방향으로 구분 됩니다. (상하좌우 4개방향과 대각선 4개 방향)

이해가 안 가면 아래에서 그림 예시가 있는데 그걸 보면 쉽게 이해가 갈것입니다.

 

        아래 오른쪽 그림은 Gradient magnitudes의 그림입니다.

        즉 소벨 마스크를 통하여 얻은 이미지 이다. (왼쪽은 아까 위에서 Blur 한 영상)

 

3. Non-maximum suppression

 

Local maxima 선택하는 단계입니다. 매우 중요합니다.

극 값을 선택하는데 있어서 잘못된 영역이 나올 수 있습니다.

즉 진짜 Edge가 아님에도 불구하고 검출이 된 영역이 있다는 것입니다.

그래서 우리는 이들(Non-Maximum)을 제거 해야 합니다.

 

그래서 Blur를 통하여 흐려진 Edge에서 잘못된 검출이 발생한다는 것입니다.

그래서 다시 Sharp한 edge로 다시 변환해야 합니다.

그래서 local Maxima는 남기고 나머지는 모두 제거하는 작업을 진행하는 것입니다.

 

 

이는 먼저 경사 방향을 45도 간격으로 라운딩 하면서8방향의 이웃을 설정하게 됩니다.

우리는 이전에서 작업을 하였습니다.

우리는 Norm과 Direction을 가지고 있지 않는가?

하지만 본 논문에서는 상하좌우만 판단하는 것 같습니다.

 

그리고선 양 방향과 음 방향으로 에지 강도와

현재 픽셀의 에지 강도를 비교판단을 하는 것입니다

 

 

예를 들면 아래 그림과 같이

현재 픽셀의 에지 강도가 가장 크다면 그 값을 보존하고 아니면 삭제 하는 것입니다.

그러면 Local Maxima 만 하얀색으로 설정 됨을 알 수 가 있습니다.

 

왼쪽 아래를 보면 4방향만 고려하기 때문에 6이 최대이기 때문에 넌 Maximum

오른쪽은 4방향 고려하기 때문에 넌 4인데 최대는 7이기 때문에 넌 Non-Maximum 이 된다.

4 5 7    5 7 6

5 6 4    6 4 3

3 4 3    4 3 1

 

 

이렇게 Local Maxima 를 선택하게 되면 아래와 같은 결과를 얻을 수 있습니다.

오른쪽 그림이 Non-Maximum Suppression을 진행한 이미지

  

 

 

4. Double thresholding

위에서 non-maximum suppression을 거친 이미지에 나타나는 에지들 중에는

실제 에지(Edge)와 약간의 노이즈(Noise) 등 즉 잡음에 의해 검출된 것들이 존재 합니다.

그래서 이들을 구별해 내어야 합니다.

 

가장 구별하기 쉬운 방법으로는 임계 값을 사용하는 것입니다.

여기서 임계 값은 2개를 이용하게 되는데

 

위 그림과 같이 low와 high를 기준으로

파랑색 영역은 제거 하고

주황색 영역과 빨간색 영역을 각각 구분하게 됩니다.

 

아래 그림은 임계 값 20과 80을 설정한 경우를 나타냅니다.

 

왼쪽 이미지는 아까 Non-Maxinum Surression 했던 이미지이고

오른쪽 이미지는 이를 토대로 2개의 임계값에 대하여

 

진한 하얀 영역은 빨간색 영역 (High 이상 값)    강한 에지라 부르겠음

옅은 회색 영역은 주황색 영역 (Low 와 High 사이 값)    약한 에지라 부르겠음

 

 

이렇게 나누게 되면 진한 하얀 영역은 진짜 Edge가 되고

옅은 회색 영역은 이제 연관성을 판별해야 합니다.

    

 

 5. Edge tracking by hysteresis

 

다음단계가 연관성의 판별 단계입니다.

빨간색 영역의 에지(High 보다 더 큰 )는 강한 에지로 설정하고

최종 에지 영상에 추가하게 됩니다.

 

주황색 영역의 에지(Low 와 High 사이)는 약한 에지로 설정하게 되고

강한 에지들과 연결될 경우에만 추가 하게 됩니다.

 

왜냐하면 노이즈나 다른 작은 변화량들은 강한 에지들과 연관성이 떨어지기 때문입니다.

그렇기 때문에 사실 강한 에지 들이 거의 실제에지로 나타나는 현상이 발생합니다.

 

에지 트래킹은 BLOB-analysis(binary Large Object)를 통하여 구현하게 된다.

강한 에지를 포함하는 Blob은 보존되고 그 이외는 제거하게 되는 것이다.

 

한마디로 약한 에지에 대해서만 8방향으로 검색하여 연결성 여부를 판단하는 것

만약 강한에지가 연결되어 있음 에지 등록

만약 약한 에지가 연결되어 있음 스택에 넣고 연결 전체를 따라다니며 강한 에지가 연결되어 있나 확인

없으면 넌 에지가 아니다. 하고 판결 내립니다.

 

아래 그림은

첫번째 이미지는 회색영역만 판별합니다.

그래서 이를 토대로 약한 에지를 판별해본 결과

 

두번째 이미지에서

파랑색은 강한 에지와 연관성을 가지고 있는 약한 에지를 나타냄

빨간색은 강한 에지와 연관성을 가지고 있지 않는 약한 에지를 나타냄

 

그래서 마지막 이미지는 강한 에지와 연관성있는 약한 에지만 합친 영상

이게 최종 Canny Edge 영상의 결과물

 

 

아하! 

이제 이해가 가십니까?

최근에도 Canny Edge알고리즘을 사용합니까?

최근 Canny Edge는유용하게 사용되고 있다.

OpenCV 2.4 버전부터는 Gray 영상이 아닌

Color 영상에서도 Canny Edge를 지원한다고 합니다.

 

 

이를 직접 구현하고 싶은데 어떻게 구현하는 소스는 없나요?

http://www.pages.drexel.edu/~nk752/Research/cannyTut2.html

여기 참고 하면 그냥 구현해놓은 소스가 잘 나와 있습니다 ^^

 

 

에이 이를 언제 다 구현하고 앉아 있어요, 좀더 편하게 OpenCV로 구현하고 싶어요!

VS2010을 키고 환경 설정

내 컴에는 2.3.1 버전이 깔려 있기에 2.3.1로 하겠습니다.

우리는 일반적으로 opencv함수를 사용하기 위하여

opencv_core231, opencv_highgui231를 추가해주고

 

    간단하게 영상을 하나 뛰웁시다.

 

 cvCanny 함수를 사용합니다.

Canny함수를 사용하려면 Imgproc231.lib 있어야 합니다. 추가하세요

그리고 인자값은 SrcImage 원본 영상, DstImage 반환 영상

임계값 2개 설정 해주면 끝입니다.

 

별거 아니네,,,, ㅡ,.ㅡ

 

그 결과 다음과 같은 결과를 얻을 수 있습니다.

 

그림을 1 2 3 4 라고 했을 때

4번 사진 100 100 설정은 강한 에지만 구하려고 설정

2번 사진과 4번을 비교 하였을 때

50~ 100 사이의 연결 에지 들이 많다는 것을 알았습니다.

그래서 강도를 50 ~ 200으로 설정하니 좀더 깔끔한 에지를 구할 수 있었음

 

결론은

2개의 임계 값을 어떻게 설정하느냐 ??????

이에 대한 것은 논문을 추후 찾아 봐야겠습니다.

참고 문헌

[1] John Canny. A computational approach to edge detection. Pattern Analysis and Machine

Intelligence, IEEE Transactions on, PAMI-8(6):679–698, Nov. 1986.

[2] F. Mai, Y. Hung, H. Zhong, and W. Sze. A hierarchical approach for fast and robust ellipse

extraction. Pattern Recognition, 41(8):2512–2524, August 2008.

[3] Thomas B. Moeslund. Image and Video Processing. August 2008.

[4] Sergei Azernikov. Sweeping solids on manifolds. In Symposium on Solid and Physical Modeling,

pages 249–255, 2008.