[CV] Canny Edge Detector 직접 구현하기

 

https://github.com/BambooKim/2021-2-Computer-Vision-Project-Color

GitHub - BambooKim/2021-2-Computer-Vision-Project-Color

https://github.com/BambooKim/2021-2-Computer-Vision-Project-Gray

GitHub - BambooKim/2021-2-Computer-Vision-Project-Gray

---

2021년 2학기에 전공선택 중 컴퓨터비젼 과목이 있어 한번 듣게 되었다.

 

기말고사 대신 프로젝트 과제를 내주셨는데,

Edge Detector, Stereo Matching, Panorama 중 하나의 주제를 선택해 자신이 원하는 대로 구현하는 것이었다.

 

대신에 OpenCV같은 라이브러리를 쓰면 프로젝트의 의미가 없어지므로,

이미지 읽기/저장 등 정말 필수적인 라이브러리나 함수를 제외하고 모든 코드를 직접 구현해야 했다.

 

Edge Detector를 구현하였고, 언어는 C++을 사용하였다.

---

Canny Edge Detector는 크게 아래의 4가지 단계를 거쳐 수행된다.

 

1. 모든 픽셀마다 x방향과 y방향의 미분값을 구한다.
2. 구해놓은 x방향과 y방향의 미분값을 통해 모든 픽셀값의 magnitude of gradient를 구한다.
3. 모든 픽셀마다 순회하며, 픽셀의 gradient방향의 양 끝을 살펴보며 local maximum이라면 놔두고, 아니라면 없앤다. (Non Maximum Suppression)
4. Double Thresholding 또는 Triple Thresholding을 통해 강한 엣지와 연속된 중간 엣지, 중간 엣지와 연속된 약한 엣지들을 선택한다.

1번과 2번은 커널을 이용해 픽셀마다 반복하며 Convolution을 하면 되므로 생략한다.

 

---

Non Maximum Suppression

 

아래 그림과 같이, 3 x 3의 9개 픽셀이 있다. 우리는 중앙의 픽셀이 local maximum인지 아닌지 판별해야 한다.

이를 위해서는 gradient 방향에서 양쪽 두개의 픽셀값과 비교를 해야 하는데,

항상 gradient 방향이 45도 간격의 특수각이 나오는 것은 아니므로, 이 경우에는 두 픽셀의 중간 값으로 interpolation해야 한다.

처음에는 각도를 어떻게 알아내야 할까 고민을 했는데, 우리는 x방향과 y방향의 gradient값을 알고 있다.

이를 x_gra, y_gra라고 하고, gradient각도를 theta라고 하자.

x_gra/y_gra는 tan(theta)에 해당하기 때문에, theta = arctan(x_gra/y_gra) 이다.

 

특수각에 대해서는 쉽게 구할 수 있고, 특수각이 아니어도 정확한 값이 필요한 게 아니므로 범위에 따라 방향만 알아낼 수 있다.

이를 코드로 나타내면 아래와 같다.

// Non-Maximum을 Suppress하는 함수.
Mat nonMaxSuppress(Mat* mat) {
    Mat src = *mat;
    Mat thin = src.clone();
    
    int width = src.size().width;
    int height = src.size().height;
    
    // 각 픽셀들의 orientation을 담을 배열.
    // 전역 변수이며 2차원 배열로 동적 할당.
    orientation = new double*[height];
    for (int i = 0; i < height; i++) {
        orientation[i] = new double[width];
    }
    
    for (int y = 0; y < height; y++) {
        for (int x = 0; x < width; x++) {
            // 모든 픽셀을 순회하며 orientation을 구한다.
            orientation[y][x] = xConvolvMat[y][x] / yConvolvMat[y][x];
        }
    }

    for (int y = 1; y < height - 1; y++) {
        for (int x = 1; x < width - 1; x++) {
            double orient = orientation[y][x];
            double mag = magnitudes[y][x];
            
            // non-max를 suppress하기 위한 비교 대상.
            double alpha, beta;
            
            if (orient == 0.0) {
                // 0도 / 180도
                alpha = magnitudes[y][x - 1];
                beta = magnitudes[y][x + 1];
            } else if (!isfinite(orient)) {
                // 90도 / 270도
                alpha = magnitudes[y + 1][x];
                beta = magnitudes[y - 1][x];
            } else if (orient == 1.0) {
                // 45도 / 225도
                alpha = magnitudes[y - 1][x - 1];
                beta = magnitudes[y + 1][x + 1];
            } else if (orient == -1.0) {
                // 135도 / 315도
                alpha = magnitudes[y - 1][x + 1];
                beta = magnitudes[y + 1][x - 1];
            } else {
                // 그 외 interpolation
                if (0 < orient && orient < 1) {
                    // 0~45
                    alpha = (magnitudes[y + 1][x + 1] + magnitudes[y][x + 1]) / 2.0;
                    beta = (magnitudes[y - 1][x - 1] + magnitudes[y][x - 1]) / 2.0;
                    
                } else if (-1 < orient && orient < 0) {
                    // 135~180
                    alpha = (magnitudes[y + 1][x - 1] + magnitudes[y][x - 1]) / 2.0;
                    beta = (magnitudes[y - 1][x + 1] + magnitudes[y][x + 1]) / 2.0;
                    
                } else if (1 < orient) {
                    // 45 ~ 90
                    alpha = (magnitudes[y + 1][x] + magnitudes[y + 1][x + 1]) / 2.0;
                    beta = (magnitudes[y - 1][x] + magnitudes[y - 1][x - 1]) / 2.0;
                    
                } else {
                    // 90 ~ 135
                    alpha = (magnitudes[y + 1][x + 1] + magnitudes[y][x + 1]) / 2.0;
                    beta = (magnitudes[y - 1][x - 1] + magnitudes[y][x - 1]) / 2.0;
                }
            }
            
            if (mag >= alpha && mag >= beta) {
                // 만약 local maximum이면 남겨둔다.
                thin.at<uchar>(x, y) = mag;
            } else {
                // local maximum이 아니면 제거한다.
                thin.at<uchar>(x, y) = 0;
            }
        }
    }

    return thin;
}

 

---

Triple Thresholding

 

보통 Canny Edge Detector는 high와 low의 두 개 값을 가지고 thresholding을 한다.

그런데 중간고사 시험문제에 두 개가 아닌 세 개 값을 이용한다면 어떤 식으로 동작할지 묻는 문제가 나왔던 것을 기억해

이를 아이디어 삼아 Triple Thresholding을 구현해봤다.

 

// Triple Thresholding을 통해 Canny Edge Detection 수행.
Mat cannyEdgeTriple(Mat* mat, double threshold_high, double threshold_mid, double threshold_low) {
    Mat canny = (*mat).clone();
    canny = nonMaxSuppress(&canny);
    Mat thin = canny.clone();

    stack<pair<int, int>> Stack;
    stack<pair<int, int>> _Stack;
    
    int width = canny.size().width;
    int height = canny.size().height;
    
    // 중간 edge와 약한 edge를 조사할 때 중복을 방지하기 위해.
    bool** check = new bool*[height];
    bool** _check = new bool*[height];
    for (int i = 0; i < height; i++) {
        check[i] = new bool[width];
        _check[i] = new bool[width];
    }
    
    // 중앙 픽셀의 주변 8개 픽셀을 조사하기 위해
    int dx[8] = { 1, 1, 0, -1, -1, -1, 0, 1 };
    int dy[8] = { 0, 1, 1, 1, 0, -1, -1, -1 };
    
    for (int y = 1; y < height - 1; y++) {
        for (int x = 1; x < width - 1; x++) {
            // Non-Max Suppress에서 살아남은 값들.
            if (thin.at<uchar>(x, y) >= threshold_high) {
                canny.at<uchar>(x, y) = 255;
                
                // 중간 edge 조사시 중복 방지용.
                check[y][x] = true;
                
                // 약한 edge 조사시 중복 방지용.
                _check[y][x] = true;
                
                // 중간 edge들을 조사하기 위해 강한 edge를 Stack에 넣는다.
                Stack.push(make_pair(x, y));
            } else {
                canny.at<uchar>(x, y) = 0;
            }
        }
    }
    
    while (!Stack.empty()) {
        int x = Stack.top().first;
        int y = Stack.top().second;
        Stack.pop();
        check[y][x] = true;
        _check[y][x] = true;
        
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // nx, ny는 조사할 8개 픽셀의 좌표. 해당 좌표가 인덱스 범위에 해당하는지 확인.
            if (0 <= nx && nx < width && 0 <= ny && ny < height) {
                if (!check[ny][nx]) {
                    double nMag = magnitudes[ny][nx];
                    
                    // 조사할 픽셀이 mid와 high 사이라면
                    if (threshold_mid <= nMag && nMag <= threshold_high) {
                        // 중간edge와 연속인 중간 edge 조사용.
                        Stack.push(make_pair(nx, ny));
                        // 중간edge와 연속인 약한 edge 조사용.
                        _Stack.push(make_pair(nx, ny));
                        canny.at<uchar>(nx, ny) = 255;
                    }
                }
            }
        }
    }
    
    while (!_Stack.empty()) {
        int x = _Stack.top().first;
        int y = _Stack.top().second;
        _Stack.pop();
        _check[y][x] = true;
        
        for (int i = 0; i < 8; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            // nx, ny는 조사할 8개 픽셀의 좌표. 해당 좌표가 인덱스 범위에 해당하는지 확인.
            if (0 <= nx && nx < width && 0 <= ny && ny < height) {
                if (!_check[ny][nx]) {
                    double nMag = magnitudes[ny][nx];
                    
                    // 조사할 픽셀이 low와 mid 사이라면
                    if (threshold_low <= nMag && nMag <= threshold_mid) {
                        // 약한 edge와 연속인 약한 edge를 조사하기 위해.
                        _Stack.push(make_pair(nx, ny));
                        canny.at<uchar>(nx, ny) = 255;
                    }
                }
            }
        }
    }
    
    for (int i = 0; i < height; i++) {
        delete[] check[i];
        delete[] _check[i];
    }
    delete[] check;
    delete[] _check;
    
    return canny;
}

강한 엣지와 연속된 중간 엣지, 중간 엣지와 연결된 약한 엣지들만 살리고 나머지는 없애는 것은 말로 하면 쉽다.

하지만 코드로 구현하려고 하니 픽셀들과의 연관성, 연속성을 어떻게 나타내야 할지 고민을 했다.

처음에는 dfs로 구현해보려 했으나, 이미지 사이즈가 크다면 메모리 사이즈가 매우 커져 중간에 뻗어버린다.

 

그래서 스택을 이용하였다.

강한 엣지들을 판별하면서 스택에 넣고, 나중에 스택에서 하나씩 꺼내며 주변 8개 픽셀 중에 중간 엣지가 있는지 확인하면서 스택에 넣고, 또 중간 엣지랑 연속된 중간 엣지가 있는지 확인한다.

또 다른 스택에서 하나씩 꺼내며 중간 엣지 주변 8개 픽셀들을 확인하며 약한 엣지가 있는지 확인하고, 또 약한 엣지 주변에 약한 엣지가 있는지 확인하며 hysteresis thresholding을 구현하였다.

Canny - Gray

잘 동작하는 것을 확인하였다.

 

아래는 RGB 버전인데, Double Thresholding과 Triple Thresholding 두 가지의 차이를 보여준다.

Canny Double - RGB

Canny Triple - RGB

 

Triple thresholding이 double thresholding보다 더 미세한 엣지들을 보여주는 것을 확인했다.