[Computer Vision] Canny edge detector

🧑🏻‍💻용어 정리

Computer vision
Edge
canny
detector
non-maximun suppresion
connected component

 

 

이번엔 edge detector에 대해 알아봅시다.

 

Canny edge detector

 

• The most widely used edge detector
• Theoretical model : step-edges corrupted by additive Gaussian noise
• Canny has shown that the first derivative of the Gaussian closely approximates the operator that optimizes the product of signal-to-noise ratio and localization.

 

 

Lena 원본 사진을 아래와 같이 봅시다.

 

 

아래는 DoG 연산에 대한 결과로 x 방향과 y 방향에 대한 결과값을 더하여 Gradient magnitude를 뽑아낸 결과입니다.

 

 

결국은 우리는 Peak 가 되는, 경계가 되는 값만 뽑아내는 것이 우리가 원하는 것입니다.

 

그러나, 그 경계 중심으로 변하는 값이 크기 때문에 두꺼운 결과가 나오는 것이 문제입니다.

 

그것들을 얇게 만들어줄 필요가 있습니다.

 

그것을 해주는 것이 "Non-max Suppression"이라는 방법입니다.

 

 

하고 나면 아래와 같이 얇게 만들어 줄 수 있습니다.

 

Non-max Suppression

 

 

 

좁은 영역 안에서, 주변이랑 비교했을 때, 신뢰도가 높은 애만 취하겠다는 concept입니다.

 

edge magintude가 높을 수록 신뢰도가 높다는 것입니다.

 

주변 영역간 비교 했을 때, 상대적으로 높은 Magnitude를 갖는 것만 남기고, 주변에 것들을 없애 나가겠다는 것이죠.

 

그래서 더 가늘어진 결과를 얻을 수 있게 됩니다.

 

 

• We wish to mark points along the curve where the magnitude is biggest
• We can do this by looking for the maximum along a slic normal to the curve (non-maximum suppression)

 

 

위 예시 그림을 봅시다.

 

이 그림은 gradient magnitude 값이 좀 두껍게 뽑아져 나온 것이라고 예상할 수 있습니다.

 

조금의 경계를 두고 두껍게 나온 것입니다.

 

그런데 우리가 원하는 것은 얇은 선처럼 얇게 나오는 것이죠.

 

 

그리고, edge의 값이 높으려면 Magintude 값이 높아야합니다.

 

즉, 가느다락 선이 주변과 비교하여 magintude 값이 높아야 한다는 것이지요.

 

그랬을 때, 우리는 저 선을 구하기 위해서 직교하는 모든 지점의 값을 연결하여 선으로 보아서 얇은 선을 얻을 수 있게 됩니다.

 

 

그래서 gradient magnitude 값이 가장 큰 값을 구하기 위해서, 직교되는 선을 따라서 edge가 Peak가 되는 것을 잘 선택을 하고 싶다는 것입니다.

 

 

 

그것들을 잘 이으면 위와 같이 빨간 선이 나오지 않을까 기대하는 것입니다.

 

 

edge와 직교한다는 것이 무엇을 직교한다는 것인지 살펴봅시다.

 

 

위와 같은 예시를 봅시다.

 

pixel의 값이 위는 하얀색으로 가장 밝고, 아래는 상대적으로 덜 밝으니,

 

gradient 값이 존재합니다.

 

이 경우, 좌우로 변화량이 전혀 없으니, 위와 같이 X 축 방향 변화량은 없다고 볼 수 있습니다.

 

 

그래서 위 수식과 같이 gradient 값을 쓸 수 있습니다.

 

지금과 같은 Vertical change, 즉 x축 변화량이 없는 예제에서는 위와 같이 위로 화살표가 그어집니다.

 

반대로 y 축 변화량이 없다면 x축으로만 화살표가 그어질 것입니다.

 

 

그래서 위와 같이 수평선이 있는 예제에서 gradient는 수직으로 서로 직교한다는 것을 알 수 있습니다.

 

 

그렇다면 직교하는 방향으로 어떻게 따라갈지에 대한 의문이 좀 풀립니다.

 

gradient 방향으로 따라가면 되겠구나 !

 

대각선이라고 하더라도 각 pixel에 대해 gradient를 구하면 가능합니다.

 

결국,

 

image 상에서의 edge 선과 Pixel의 gradient 방향은 일반적으로 직교한다는 것입니다.

 

아까 그 두꺼운 선을 얇게 만들고 싶으니,

 

방식 자체는, 선으로 그어놓은 것처럼 직교하는 방향을 따라 관찰해보자는 것입니다.

 

 

직교하는 방향으로 어떻게 갈지에 대한 것은 gradient 대로 쫓아가보자는 것이죠.

 

그래서 이 검은색 점으로 pixel이 존재할 때,

 

q라는 Pixel에 대해서 주변에 비해 gradient magnitude 값이 큰지 작은지 관찰해봅니다.

 

non-maximum suppression의 concept은 주변에 비해 Max하다면 남기고 아니라면 버리는 것입니다.

 

 

 

 

그런데, 이 주변이라는 것은 3 x 3 이나 5 x 5 등의 주변의 의미를 갖는 자유도를 갖습니다.

 

위 예제를 통해서 edge의 특성상 gradient를 따라서 관찰하는 게 더 효율적이다라는 것을 알 수가 있었습니다.

 

그러므로,

 

이때, q라는 Pixel의 gradient 값에 대한 방향을 알 수가 있습니다.

 

그래서 위와 같이 x와 y 방향의 gradient 값의 방향을 화살표로 그려볼 수가 있습니다.

 

이 gradient를 따라 쭉 가다보면 위 그림의 r처럼 한 pixel, 즉 한 점에 놓이게 됩니다.

 

이 r은 두 pixel 사이에 놓이게 됩니다. 물론 한 pixel 위에 정확히 놓일 수도 있습니다.

 

 

그렇다면 우리가 r 위치에서의 Image gradient 값을 뽑아내야 하는데,

 

r의 위치가 소수 위치라면, 우리가 이것을 Interpolation을 통해 추정할 수가 있습니다.

 

그래서 주변 pixel을 통해 Linear나 Nearest Interpolation을 통해서 r 위치에서의 gradient magnitude를 추정할 수가 있습니다.

 

 

그리고, 방향의 부호가 중요한 것은 아니니, r이나 p 중에 골라서 gradient magnitude를 추정하면 됩니다.

 

이때, q가 가지고 있는 것이 gradient magnitude 값이, r이나 p가 가지고 있는 gradient magnitude 값 보다 크다면 주변에 비해 튀는 값이라고 판정합니다.

 

그럼 이것은 버리지 않고 남기는 것입니다.

 

 

이러한 것이 canny edge에서의 non-maximum suppression 방식입니다.

 

즉, 직교하는 방향을 따라 보는 것인데, gradient 방향을 따라 보는 것이죠.

 

 

 

edge의 확률이 높으려면 gradient의 크기가 높아야 하는 것입니다.

 

그래서 위와 같은 큰 신뢰도를 가지는 것을 남겨놓는 것입니다.

 

 

 

 

위와 같은 idea를 통해 magnitude와 angel을 얻을 수 있습니다.

 

 

 

Non-maxtimum suppression을 적용한다고 할 때, 아래와 같은 절차를 거칩니다.

 

 

일단 3 x 3으로 잡았지만, 조금 더 넓은 범위에서 관찰하고 싶다고 하면, 5 x 5를 사용해도 상관 없습니다.

 

대신 범위를 몇으로 잡든, 관찰하고자하는 방향은 gradient 방향 대로 관찰해줘야 한다는 것입니다.

 

gradient를 화살표로 표시하고,

 

3  x 3의 경우에는 그림과 같이 저 지점에서 만나는 것입니다.

 

 

그리고 Interpolation은 앞에서 up&down sampling에서 배운 바와 같이 똑같이 진행되는 것입니다.

 

그리고 linear interpolation이라면  거리를 기준으로 더 가까운 것에 더 높은 weight를 주는 방식으로 말입니다.

 

nearest neighbor(quantization)이라면, 가까운 것으로 선택이 됩니다.

 

이전과 다른 것은 그 값이 pixel 값이 아니라 gradient magnitude 값이라는 것입니다.

 

그렇다면,

 

이 gradient magnitude 값보다 위 검은색 값이 더 크다면,non-maximum suppression에 의해 남게 됩니다.

 

더 작으면 버리게 됩니다.

 

반대 방향도 선택사항으로 해도 되고 안 해도 되는 것입니다.

 

 

 

그리고 3 x 3이 아니라 5 x 5라고 생각해봅시다.

 

그래도 gradient direction은 지켜줘야합니다.

 

더 넓어진 범위에서 보는 것이죠.

 

그리고 화살표를 따라 보는 것은 마찬가지라는 것이죠.

 

gradient 방향대로 쭉 따라가서 봤을 때, 만나는 지점과 비교하는 것은 똑같습니다.

 

3 x 3 보다 5 x 5가 조금 더 큰 영역이므로, 

 

3 x 3 보다 만나는 지점이 더 생깁니다.

 

만나는 지점이라는 것은 두 Pixel 사이에 놓이는 지점을 의미합니다.

 

그래서 총 반대방향까지 합치면, 총 4개의 본인 점과 비교하여 nin-maximum suppression을 통해 비교합니다.

 

 

 

이것을 하고 나면, 두꺼웠던 것이 얇아지는 효과를 내게 됩니다.

 

window size를 키우게 되면 더 굵기가 얇아지게 되는 것입니다.

 

 

결국, 두꺼운 것이 Edge로 봤을 때 불필요한 정보들이 많은데,

 

그것들을 쳐내는 과정이 필요합니다.

 

그래서 잉여 정보들을 쳐내는 방법 중에서 Non maximum suppression이 대표적인 방법입니다.

 

 

그래서, 기존 pixel 이 있고, 주변이랑 비교하는데, 선택 기준이 gradient magnitude가 주변에서 큰가 작은가에 의해, 직교하는 것들에 대해서 값을 추출하는 것이죠.

 

직교해야 우리가 원하는 선을 도출해낼 수 있기 때문이죠.

 

 

 

Before Non-maximun suppression

 

 

 

After Non-maximun suppression

 

 

그래서 위와 같은 결과를 얻습니다.

 

 

결국, 우리는 edge에 해당되는 것만 남기고 나머지는 다 버리겠다는 것입니다.

 

그래서 이것을 Binary image로 만들겠다는 것이죠.

 

 

edge에 해당하는 부분만 1의 값을 갖는 것이고, 나머지는 0의 값을 갖는 것입니다.

 

1 또는 0 아니면 255 또는 0이라고 생각하시면 됩니다.

 

 

지금 우리가 non-maximum suppression으로,

 

두꺼운 것들 얇게 만들어줬지만, 아직 0 또는 1의 값이 아닙니다.

 

gradient 크기에 따라서 밝고 어두움이 아직 존재합니다.

 

 

그래서 gradient의 크기를 보고 어떤 것은 취하고 어떤 것은 취하지 않을 지를 선택하는 과정을 거쳐야합니다.

 

 

Hysteresis thresholding (Double thresholding)

 

기준을 세워서 더 높으면 1 낮으면 0과 같이 값을 부여하는 것입니다.

 

그 높은 애들을 edge라고 판정하겠다는 것입니다.

 

 

그래서 threshold를 2개를 씁니다.

 

M은 magnitude에 해당하고 x, y는 좌표입니다.

 

모든 pixel에 대해 T H 보다 큰 것은, 높은 threshold 보다 큰 gradient magnitude를 갖는 것은 무조건 edge로 하겠다는 것입니다.

 

T L 보다 낮은 것은 무조건 edge가 아니라고 하는 것입니다.

 

 

그런데 우리가 하려고 하는 것은 0 또는 1로, binary classification, 즉 2개의 class를 만드는 것입니다.

 

그러나, T L 과 T H 사이의 값들이 존재하여, 3가지 classification이 됩니다.

 

 

그래서 우리는 T H 보다 큰 edge인 애들을 strong edge, T L 보다 작은 애들은 Edge가 아닌 것입니다.

 

그리고 T L 과 T H 사이의 것을은 Weak Edge라고 합시다.

 

 

그것을 non-maximum suppresion을 통해 그려보면 아래와 같습니다.

 



 

아래와 같은 Pixel 값을 가집니다.

 

• string - 255
• weak - 128
• not a edge - 0

 

non-maximum suppresion을 거친 값에다가 double thresholding을 통해 class 3개로 나눈 것을 그린 것입니다.

 

 

이 지져분한 결과를 다시 선택을 해야합니다.

 

 

 

 

 

이것을 하는 과정이 wark edge를 기준으로 하여 쭉 연결해 나가는 것입니다.

 

찐한 선이 strong edge, 얇은 선이 weak edge라고 생각해봅시다.

 

 

 

그랬을 때,

 

weak edge의 한 지점부터 시작해서 쭉 연결을 합니다.

 

한 pixel이라도 strong edge와 만나는 부분이 있다면, 그 edge는 다 strong edge로 하는 것입니다.

 

weak edge들도 다 strong edge들로 만드는 것입니다.

 

계속해서 적어도 Weak edge 또는 Strong edge가 있다면 계속해서 연결해 나가는 것입니다.

 

멈출 때까지, edge가 아닌 부분이 나올 때까지 멈추지 않고 계속 이어나갑니다.

 

이 이어진 것을  connected component라고 합니다. (연결 된 것 중 가장 큰 집합)

 

그리고 strong edge를 만나지 못하고, weak edge만 있다면, 이것은 edge가 아닌 것으로 끝나는 것입니다.

 

 

결국, Strong edge가 하나라도 있는 edge는 strong edge가 되고,

 

Strong edge가 없다면 edge가 아니게 되는 것입니다.

 

 

그래서 이 과정을 통해 0 또는 1의 값으로 나오게 되는 것입니다.

 

 

 

이렇게 Double thresholding을 통해서 edge detection을 해보았습니다.

 

 

그래서 위와 같은 Lena image에서 edge 를 뽑아내었습니다.