알고리즘/ Canny Edge Detector
1. Gaussian Blur 로 이미지를 blur해 주어 노이즈를 없앤다.
OpenCV의 cvCanny() 함수는 이러한 과정 없이 원본 이미지에서 바로 canny edge를 찾는다. OpenCV를 사용할 때 노이즈에 의한 잡음이 많은 경우 Gaussian blur를 적용하고 cvCanny()를 사용해야겠다. 아무래도 OpenCV에서 Gaussian blur를 적용하지 않는것은 연산량이 많기 때문인것 같은데 Separable Kernel을 사용하면 속도 향상에 도움이 된다.Separable Kernel을 이용한 Gaussian blur에 대해서는 아래 주소에 포스팅에 정리해 두었다.
http://trip2ee.tistory.com/entry/Separable-Kernel-Convolution
다음 그림은 blur된 이미지와 원본 이미지이다.
2. Sobel Edge를 찾는다.
Sobel Edge Detector를 이용해 엣지를 찾는다.
3. Non-maxima Suppression
엣지의 magnitude 가 maximum인 경우만 엣지로 사용한다. 이 때 모든 3x3 neighbor에 대해서 maximum인지 판별하는 것이 아닌 edge의 orientaton을 고려해 탐색 방향을 결정한다. 엣지 방향은 아래 그림과 같이 4개로 나누며
maximum인지 판단하는 방향은 방향이 0이면 좌우, 1이면 현재 위치에서 offset이 (-1,-1), (+1,+1)인 점과 비교한다. 방향이 2라면 위, 아래와 비교, 3이면 offset이 (-1,+1), (+1,-1)인 점과 비교한다.
Canny Edge의 특징중 하나는 두개의 threshold를 사용하는 것인데, 이 과정에서 높은 threshold보다 엣지의 magnitude가 크면 엣지 픽셀로 지정하고 낮은 threshold 보다 높은 magnitude를 가지면 나중에 edge들을 연결(hysteresis analysis)할 때 엣지 픽셀과 인접해 있으면 엣지로 지정한다.
다음 그림은 non-maxima suppression을 수행한 결과로 maxima는 흰색으로, non-maxima는 회색으로, 엣지가 아닌 부분은 검은색으로 표시했다. 이 그림은 단지 중간 과정을 보여주기 위한 것으로 non-maxima 픽셀도 역시 엣지픽셀로 사용하지 않는다. 또한 threshold를 적용하지 않고 단지 엣지픽셀들의 orientation에 따라 magnitude가 가장 큰 픽셀들만 보여주는 것이다.
4. 엣지 연결하기
위에서도 말했듯이 Canny edge detector는 두개의 threshold를 사용한다. 그 이유는 큰 threshold 보다 큰 magnitude를 가지는 엣지들만 엣지로 할 경우 영상의 잡음으로 인해 엣지 픽셀이 엣지픽셀로 인식되지 않을 경우가 있어 낮은 threshold 보다 높은 magnitude를 가지고 엣지 픽셀과 인접한 픽셀들을 잇기 위함이다. 편의상 큰 threshold를 T1, 작은 threshold를 T2라고 부르겠다.
다음 그림에서 왼쪽은 non-maximum suppression 후 T1 보다 높은 edge픽셀만을 보여주는 것이고 오른쪽은 T2보다 magnitude가 크고 엣지와 인접한 픽셀들을 연결한 결과이다. 이 때 T1=100, T2=50을 사용했다.
 |
이 과정에서는 모든 엣지에 대해서 주변에 인접하고 magnitude가 T2보다 높은 픽셀들을 엣지로 지정하고 또 새롭게 엣지로 지정된 픽셀 주변에서 magnitude가 T2보다 높은 인접한 픽셀을 엣지로 지정하는 식으로 반복적으로 수행한다. OpenCV의 구현에서는 이 부분에 stack을 사용했다. 이 stack의 pop은 말 그대로 pop인데 push는 push할 픽셀을 엣지로 지정하고 난 후 stack에 저장한다. 내가 구현한 코드에서도 이 부분을 따라했다.
상세한 설명을 하자면 위 3번 단계에서 T1보다 큰 픽셀은 픽셀로 지정하고 이 픽셀의 주소를 stack에 push한다. 그리고 T1보다 작고 T2보다 큰 픽셀은 그냥 엣지가 될 수 있는 것임을 지정한다. 이 과정이 모두 끝나면 stack에서 엣지 픽셀을 꺼내고 해당 엣지 픽셀의 3x3 neighbor에 T2보다 큰 픽셀이 있을 경우 이 픽셀을 엣지로 지정하고 stack에 push한다. 이 과정을 stack이 비게 될 때 까지 반복하면 엣지가 모두 연결이 된다.
그리고 gaussian blur 를 적용한 것과 그렇지 않은 것의 차이를 비교하기 위해 gaussian blur를 적용하지 않고 canny edge를 찾은 결과를 보면 다음과 같다.
다음은 내가 C로 구현한 canny edge detector source code이다. 함수 인자 중 이미지와 결과 이미지는 BYTE* 로 주고받는데 OpenCV를 사용하는 경우라면 IplImage의 imageData 를 사용하면 된다.
그런데 어디에서 속도차이가 나는지는 모르겠지만 OpenCV의 코드가 내 코드보다 0.5ms 정도 더 빠르다. 내 코드는 320x240크기의 이미지에서 대략 2.5ms 정도 걸리지만 OpenCV는 2ms 정도 걸리는데 아무리 찾아봐도 무엇때문에 이런 속도 차이가 나는지 모르겠다. 분명 Intel 의 CPU 구조를 잘 아는 사람들이 만든거니 더 최적화된 코드를 짰을텐데 말이다. 그래서 그런지 Intel의 C 컴파일러와 MS의 C컴파일러로 같은 코드를 컴파일해도 Intel의 C컴파일러가 훨씬 더 빠른 최적화된 코드를 만든다고 하는데 Intel C 컴파일러는 무료로 제공되지 않아 사용해보질 못해 아쉽다. MS의 dreamspark같이 학생들에게 무료로 컴파일러를 제공하면 좋을텐데...
void CannyEdge(BYTE *pImage, int width, int height, int th_high, int th_low, BYTE *pEdge)
{
int i, j;
int dx, dy, mag, slope, direction;
int index, index2;
const int fbit = 10;
const int tan225 = 424; // tan25.5 << fbit, 0.4142
const int tan675 = 2472; // tan67.5 << fbit, 2.4142
const int CERTAIN_EDGE = 255;
const int PROBABLE_EDGE = 100;
bool bMaxima;
int *mag_tbl = new int[width*height];
int *dx_tbl = new int[width*height];
int *dy_tbl = new int[width*height];
BYTE **stack_top, **stack_bottom;
stack_top = new BYTE*[width*height];
stack_bottom = stack_top;
#define CANNY_PUSH(p) *(p) = CERTAIN_EDGE, *(stack_top++) = (p)
#define CANNY_POP() *(--stack_top)
for(i=0; i<width*height; i++) {
mag_tbl[i] = 0;
pEdge[i] = 0;
}
// Sobel Edge Detection
for(i=1; i<height-1; i++) {
index = i*width;
for(j=1; j<width-1; j++) {
index2 = index+j;
// -1 0 1
// -2 0 2
// -1 0 1
dx = pImage[index2-width+1] + (pImage[index2+1]<<1) + pImage[index2+width+1]
-pImage[index2-width-1] - (pImage[index2-1]<<1) - pImage[index2+width-1];
// -1 -2 -1
// 0 0 0
// 1 2 1
dy = -pImage[index2-width-1] - (pImage[index2-width]<<1) - pImage[index2-width+1]
+pImage[index2+width-1] + (pImage[index2+width]<<1) + pImage[index2+width+1];
mag = abs(dx)+abs(dy); // magnitude
//mag = sqrtf(dx*dx + dy*dy);
dx_tbl[index2] = dx;
dy_tbl[index2] = dy;
mag_tbl[index2] = mag; // store the magnitude in the table
} // for(j)
} // for(i)
for(i=1; i<height-1; i++) {
index = i*width;
for(j=1; j<width-1; j++) {
index2 = index+j;
mag = mag_tbl[index2]; // retrieve the magnitude from the table
// if the magnitude is greater than the lower threshold
if(mag > th_low) {
// determine the orientation of the edge
dx = dx_tbl[index2];
dy = dy_tbl[index2];
if(dx != 0) {
slope = (dy<<fbit)/dx;
if(slope > 0) {
if(slope < tan225)
direction = 0;
else if(slope < tan675)
direction = 1;
else
direction = 2;
}
else {
if(-slope > tan675)
direction = 2;
else if(-slope > tan225)
direction = 3;
else
direction = 0;
}
}
else
direction = 2;
bMaxima = true;
// perform non-maxima suppression
if(direction == 0) {
if(mag < mag_tbl[index2-1] || mag < mag_tbl[index2+1])
bMaxima = false;
}
else if(direction == 1) {
if(mag < mag_tbl[index2+width+1] || mag < mag_tbl[index2-width-1])
bMaxima = false;
}
else if(direction == 2){
if(mag < mag_tbl[index2+width] || mag < mag_tbl[index2-width])
bMaxima = false;
}
else { // if(direction == 3)
if(mag < mag_tbl[index2+width-1] || mag < mag_tbl[index2-width+1])
bMaxima = false;
}
if(bMaxima) {
if(mag > th_high) {
pEdge[index2] = CERTAIN_EDGE; // the pixel does belong to an edge
*(stack_top++) = (BYTE*)(pEdge+index2);
}
else
pEdge[index2] = PROBABLE_EDGE; // the pixel might belong to an edge
}
}
} // for(j)
} // for(i)
while(stack_top != stack_bottom) {
BYTE* p = CANNY_POP();
if(*(p+1) == PROBABLE_EDGE)
CANNY_PUSH(p+1);
if(*(p-1) == PROBABLE_EDGE)
CANNY_PUSH(p-1);
if(*(p+width) == PROBABLE_EDGE)
CANNY_PUSH(p+width);
if(*(p-width) == PROBABLE_EDGE)
CANNY_PUSH(p-width);
if(*(p-width-1) == PROBABLE_EDGE)
CANNY_PUSH(p-width-1);
if(*(p-width+1) == PROBABLE_EDGE)
CANNY_PUSH(p-width+1);
if(*(p+width-1) == PROBABLE_EDGE)
CANNY_PUSH(p+width-1);
if(*(p+width+1) == PROBABLE_EDGE)
CANNY_PUSH(p+width+1);
}
for(i=0; i<width*height; i++)
if(pEdge[i]!=CERTAIN_EDGE)
pEdge[i] = 0;
delete [] mag_tbl;
delete [] dx_tbl;
delete [] dy_tbl;
delete [] stack_bottom;
}
출처: https://trip2ee.tistory.com/75 [지적(知的) 탐험]
Canny Edge Detector
Canny Edge Detector 는 매우 유명한 edge detector 이고 많이 쓰이는 것이지만 직접 구현할 일이 없었다. 그런데 어제 잠깐 시간이 되서 OpenCV 에 구현된 cvCanny() 함수를 분석해 보고 따라서 구현해 보았다...
trip2ee.tistory.com