OpenCV 4로 배우는 컴퓨터 비전과 머신 러닝/ 에지 검출과 응용

에지 검출

미분과 그래디언트

  • 영상에서 에지(edge)란 한쪽 방향으로 픽셀 값이 급격하게 바뀌는 부분을 의미
    • 일반적으로 객체와 배경의 경계, 객체와 다른 객체의 경계에서 에지가 발생한다.
    • 그러므로 영상에서 에지를 찾아내는 작업은 객체의 윤곽을 알아낼 수 있는 방법이며, 다양한 컴퓨터 비전 시스템에서 객체 판별을 위한 전처리로 에지 검출이 사용됨.
  • 영상에서 에지를 찾아내려면 픽셀 값의 변화율을 측정하여 변화율이 큰 픽셀을 선택한다.
    • 수학에서 함수 또는 데이터의 변화율을 미분(derivative)라고 한다.

f' = {df \over dx} = lim_{\Delta x \to 0} {f(x + \Delta x) - f(x) \over \Delta x}

  • 1차원 연속 함수 f(x) 의 값 변화에 따른 미분 f'(x) 는 아래 그림과 같다.
    • (미분 내용 설명 생략)

  • 영상은 2차원 평면 위에 픽셀 값이 정형화 되지 않은 상태로 나열되어 있는 형태이므로 미분 공식을 사용할 수 없다.
    • 영상으로부터 미분을 계산하려면 두 가지 특징을 고려해야 하는데, 하나는 영상이 2차원 평면에서 정의된 함수라는 점이고, 두 번째는 영상이 정수 단위 좌표에 픽셀이 나열되어 있는 이산함수라는 점이다.
  • 영상과 같이 일련의 데이터가 순서대로 나열되어 있는 경우에는 미분 근사화 방법을 이용하여 변화량을 측정할 수 있다. 미분 근사는 다음 세 가지 방법을 주로 사용한다.
    • 전진 차분 (forward difference)
      • {dI \over dx} \cong {I(x + h) - I(x) \over h}
    • 후진 차분 (backward difference)
      • {dI \over dx} \cong {I(x) - I(x - h) \over h}
    • 중앙 차분 (centered difference)
      • {dI \over dx} \cong {I(x + h) - I(x - h) \over h}
  • 위 수식에서 I(x) 는 1차원 이산함수이고, h 는 이산 값의 간격을 의미한다.
    • 미분 근사 방법을 영상에 적용할 경우, h 는 픽셀의 간격이라 생각할 수 있으며 보통 픽셀 간격의 최소단위인 1을 h 값으로 사용한다.
    • 즉, 전진 차분 수식은 I(x + 1) - I(x) 로 정리되며, 이는 자기 자신 바로 앞에 있는 픽셀에서 자기 자신 픽셀 값을 뺀 형태이다.
    • 후진 차분은 I(x) - I(x - 1) 로 정리되며, 이는 자기 자신 픽셀에서 바로 뒤에 있는 픽셀 값을 뺀 형태이다.
    • 마지막으로 중앙 차분은 {I(x + 1) - I(x - 1) \over 2} 로 정리되며,로 정리되며 자기 자신을 제외하고 바로 앞과 뒤의 픽셀값을 이용하는 미분 근사 방법이다.
    • 세 가지 방법 중 중간값 차이를 이용하는 방법이 이론적으로 근사화 오류가 가장 적으며, 실제 영상에서 미분을 계산할 때도 널리 쓰이고 있다.
  • 영상은 2차원 평면에서 정의된 함수이기 때문에 영상에서 에지를 찾기 위해서는 영상을 가로 방향과 세로 방향으로 각각 미분해야 한다.
    • 2차원 영상 I(x, y) 를 가로 방향으로 미분한다는 것은 y좌표는 고정한 상태에서 x축 방향으로만 미분 근사를 계산하는 것을 의미하며, 이러한 연산을 x축 방향으로의 편미분(partial derivative)라고 한다.
    • x축 방향의 편미분은 I_{x} 또는 {\partial I \over \partial x} 로 표기한다.
    • 이와 유사하게 y축 방향으로의 편미분은 I_{y} 또는 {\partial I \over \partial y} 라고 표기하고, x 좌표를 고정한 상태에서 y축 방향으로 미분 근사를 수행하여 구할 수 있다.
  • 2차원 영상 I(x, y) 에 대하여 x축과 y축 방향에 대한 각각의 편미분을 중앙 차분 방법으로 근사화하면 다음과 같다.

I_{x} = {\partial I \over \partial x} \cong {((x+1, y) - I(x-1, y) \over 2}

I_{y} = {\partial I \over \partial y} \cong {((x, y+1) - I(x, y-1) \over 2}

  • 중앙 차분을 이용한 영상의 미분 근사는 마스크 연산을 이용하여 쉽게 구현할 수 있다.
    • 2차원 영상을 x축과 y축 방향에 대해 편미분을 수행하는 필터 마스크를 아래 그림에 나타냈다.
    • 왼쪽 그림은 x축 방향으로 편미분하는 필터 마스크이고, 오른쪽 그림은 y축 방향으로 편미분하는 필터 마스크이다.
    • 앞서 설명한 편미분 근사 수식을 그대로 적용하려면 필터 마스크 값에 1/2을 곱해야 하지만, 보통 미분 값의 상대적 크기를 중요시 하기 때문에 단순화 시킨 마스크를 주로 사용한다.
    • 아래 마스크를 이용하여 영상을 각각 필터링하면 영상을 가로 방향과 세로 방향으로 편미분한 정보를 담고 있는 행렬을 얻을 수 있다.

  • 실제 영상에 대해 x축 방향과 y축 방향으로 편미분한 결과는 아래 이미지와 같다.
    • 원래 영상의 미분은 부호가 있는 실수로 계산되지만, 아래 그림은 미분 결과를 시각적으로 분석하기 위해 128을 더한 후 0-255 사이의 정수로 변환하여 그레이스케일 영상 형태로 나타낸 것이다.

  • 2차원 공간에서 정의된 영상에서 에지를 찾으려면 x축 방향과 y축 방향의 편미분을 모두 사용해야 한다.
    • 2차원 공간에서 정의된 함수 f(x, y) 가 있을 때, 이 함수의 x축 방향 미분과 y축 방향 미분을 한꺼번에 벡터로 표현한 것을 그래디언트(gradient)라고 하고 다음과 같이 표기한다.

\nabla f = \left[ \begin{array}{rr} f_{x} \\ f_{y} \end{array} \right] = f_{x}i + f_{y}j

  • 그래디언트는 벡터이기 때문에 크기(magnitude)와 방향(phase) 성분으로 표현할 수 있다.
    • 그래디언트 벡터의 방향은 변화 정도가 가장 큰 방향을 나타내고, 그래디언트 벡터의 크기는 변화율 세기를 나타내는 척도로 생각할 수 있다.
    • 그래디언트 크기는 보통 \| \nabla f \| 로 표기하고 다음과 같이 구한다.

\| \nabla f \| = \sqrt{f_{x}^{2} + f_{y}^{2}}

  • 그래디언트 방향 \theta 는 다음 수식으로 구할 수 있다.

\theta = tan^{-1}({f_{y} \over f_{x}})

  • 그래디언트 벡터의 크기와 방향을 제대로 이해하기 위해 실제 영상에서 그래디언트를 구한 예를 아래 그림에 나타냈다.
    • 아래 그림에 나타난 영상은 어두운 배경에 밝기가 다른 두 개의 객체가 있는 영상이다.
    • 이 영상에서 객체와 배경 경계상의 세 점 a, b, c를 선택하고, 각 점에서의 그래디언트 벡터를 빨간색 화살표로 나타냈다.
    • 빨간색 화살표의 길이는 그래디언트 크기를 나타내고, 화살표 방향은 그래디언트 벡터의 방향을 나타낸다.
    • 그래디언트 벡터의 크기는 밝기 차이가 클수록 크게 나타나므로 점 a, b의 화살표보다 점 c에서 화살표 길이가 더 길게 나타난다.
    • 그래디언트 벡터의 방향은 해당 위치에서 밝기가 가장 밝아지는 방향을 가리킨다.
    • 점 c에 대해서는 특별히 x축 방향으로의 편미분 f_{x} 와 y축 방향으로의 편미분 f_{y} 성분을 함께 표시하였으며, 이 두 성분을 이용하여 빨간색 화살표를 그릴 수 있다.
    • 참고로 아래 그림에서 노란색으로 표시된 화살표는 그래디언트 벡터와 수직인 방향을 표시한 것이며, 이를 에지의 방향이라고 부른다.

  • 2차원 영상에서 에지를 찾는 기본적인 방법은 그래디언트 크기가 특정 값보다 큰 위치를 찾는 것이다.
    • 여기서 에지 여부를 판단하기 위해 기준이 되는 값을 임계값(threshold) 또는 문턱치라고 한다.
    • 임계값은 영상의 특성에 따라 다르게 설정해야 하며, 보통 사용자의 경험에 의해 결정된다.
    • 일반적으로 임계값을 높게 설정하면 밝기 차이가 급격하게 변하는 에지 픽셀만 검출되고, 낮게 설정하면 약한 에지 성분도 검출된다.

마스크 기반 에지 검출

  • 앞서 영상을 x축 방향과 y축 방향으로 편미분 하는 1×3, 3×1 크기의 마스크에 대해 알아봤는데, 대부분의 영상에는 잡음이 포함되어 있어서 1×3 또는 3×1 마스크를 이용하여 미분을 구할 경우 다소 부정확한 결과가 생성될 수 있다.
    • 그러므로 실제 영상에 미분을 구할 때는 잡음의 영향을 줄일 수 있도록 좀 더 큰 크기의 마스크를 이용한다.
    • 여러 방법의 미분 근사 마스크가 개발되었지만, 가장 널리 사용되는 것은 소벨 필터(Sobel filter) 마스크이다.
  • 영상을 가로 방향과 세로 방향으로 미분하는 3×3 크기의 소벨 필터 마스크를 아래 그림에 나타냈다.
    • 아래 그림의 (a)는 x축 방향으로 편미분을 구하는 소벨 마스크이고, (b)는 y축 방향으로 편미분을 구하는 소벨 마스크이다.
    • (a)에 나타난 x축 방향 미분 마스크는 현재 행에 대한 중앙 차분 연산을 2회 수행하고, 이전 행과 다음 행에 대해서도 중앙 차분 연산을 1회씩 수행한다.
    • 이러한 연산은 현재 행과 이웃 행에서의 픽셀 값 변화가 유사하다는 점을 이용하여 잡음의 영향을 줄이기 위함이며, 특히 현재 행에서 두 번의 중앙 차분 연산을 수행하는 것은 현재 행의 중앙 차분 근사에 더 큰 가중치를 주기 위함이다. y축 방향 미분도 같은 방식으로 설계 되었다.

  • OpenCV는 소벨 마스크를 이용하여 영상을 미분하는 Sobel() 함수를 제공한다. Sobel() 함수는 3×3 소벨 마스크 또는 확장된 형태의 큰 마스크를 이용하여 영상을 미분한다.
  • Sobel() 함수는 입력 영상 src를 편미분한 결과를 dst에 저장한다.
    • 결과 영상의 자료형은 ddepth 인자를 통해 명시적으로 지정해야 하고, ddepth에 -1을 지정하면 src와 같은 타입을 사용하는 dst 영상을 생성한다.
    • dx와 dy 인자는 각각 x 방향과 y 방향으로의 편미분 차수를 의미하며, Sobel() 함수에 의해 계산되는 결과 행렬 dst는 다음 수식과 같은 의미를 갖는다.

dst = {\partial^{xorder + yorder} src \over \partial^{xorder} \partial^{xorder}}

  • ksize 이후의 인자는 모두 기본값을 가지고 있으므로 실제 함수 호출시에는 생략할 수 있다.
    • ksize 인자에 1을 지정하면 3×1 또는 1×3 커널을 사용하고, 기본값인 3을 지정하면 3×3 소벨 마스크를 사용한다.
  • Sobel() 함수는 x방향과 y방향으로의 고차 미분을 계산할 수 있지만 대부분의 경우 x방향 또는 y 방향으로의 1차 미분을 구하는 용도로 사용된다.
    • 예컨대 그레이스케일 레나 영상을 x방향으로 편미분한 결과를 dx 행렬에, y방향으로 편미분한 결과를 dy 행렬에 저장하려면 다음과 같이 코드를 작성하면 된다.
Mat src = imread("lenna.bmp", IMREAD_GRAYSCALE);

Mat dx, dy;
Sobel(src, dx, CV_32FC1, 1, 0);
Sobel(src, dy, CV_32FC1, 0, 1);
  • OpenCV는 소벨 마스크 외에도 샤르 필터(Scharr filter) 마스크를 이용한 미분 연산도 지원한다.
    • 샤르 필터는 3×3 소벨 마스크보다 정확한 미분 계산을 수행하는 것으로 알려져 있다.
    • 샤르 필터 마스크는 아래 그림과 같다.

  • 샤르 필터 마스크를 이용하여 영상을 미분하려면 Scharr() 함수를 사용하면 된다.
    • 샤르 필터를 이용한 영상의 미분은 Sobel() 함수를 이용하여 구할 수도 있다. Sobel() 함수의 ksize 인자에 FILTER_SCHARR 또는 -1을 지정하면 3×3 샤르 마스크를 사용하여 영상을 미분한다.
  • Sobel() 또는 Scharr() 함수를 이용하여 x 방향으로 미분과 y 방향으로 미분을 각각 계산하여 행렬에 저장한 후, 두 미분 행렬을 이용하여 그래디언트 크기를 계산할 수 있다.
    • OpenCV는 2차원 벡터의 x 방향 좌표와 y 방향 좌표를 이용하여 벡터의 크기를 계산하는 magnitude() 함수를 제공한다.
    • magnitude() 함수의 입력으로 사용되는 x와 y는 CV_32F 또는 CV_64F 깊이를 사용하는 행렬 또는 벡터여야 한다. magnitude() 함수의 출력 magnitude를 구성하는 원소 값은 다음 수식에 의해 계산된다.

magnitude(I) = \sqrt{x(I)^{2} + y(I)^{2}}

  • 만약 x 방향으로 미분과 y 방향으로 미분이 저장된 두 개의 행렬이 있을 때, 그래디언트의 방향을 계산하고 싶다면 phase() 함수를 사용할 수 있다.
    • phase() 함수에서 x, y는 입력이고 angle은 출력이다. angle의 각 원소는 다음 수식에 의해 계산된다.

angle(I) = atan2({y(I) \over x(I)})

  • Sobel() 함수를 이용하여 영상으로부터 그래디언트를 계산하고, 그래디언트 크기를 이용하여 에지를 검출하는 예제 코드는 아래와 같다.
void sobel_edge()
{
Mat src = imread("lenna.bmp", IMREAD_GRAYSCALE);

if (src.empty())
{
cerr << "Image load failed!" << endl;
return;
}

Mat dx, dy;
Sobel(src, dx, CV_32FC1, 1, 0);
Sobel(src, dy, CV_32FC1, 0, 1);

Mat fmag, mag;
magnitude(dx, dy, fmag);
fmag.convertTo(mag, CV_8UC1);

Mat edge = mag > 150;

imshow("src", src);
imshow("mag", mag);
imshow("edge", edge);

waitKey();
destroyAllWindows();
}
  • 아래 이미지는 위 예제 코드를 이용한 결과이다.

캐니 에지 검출기

  • 소벨 마스크 기반 에지 검출은 구현이 간단하고 빠르기 때문에 아직도 많은 컴퓨터 비전 시스템에서 사용되고 있으나, 그래디언트 크기만을 기준으로 에지 픽셀을 검출하기 때문에 임계값에 민감하고 에지 픽셀이 두껍게 표현되는 문제점이 있다.
  • 1986년 캐니(J. Canny)는 에지 검출을 최적화 문제 관점으로 접근함으로써 소벨 에지 검출 방법의 단점을 해결할 수 있는 방법을 제시하였다. 캐니는 자신의 논문에서 다음 세 가지 항목을 좋은 에지 검출기의 조건으로 제시하였다.
    • 정확한 검출(good detection): 에지를 검출하지 못하거나 에지가 아닌데 에지로 검출하는 확률을 최소화해야 한다.
    • 정확한 위치(good localization): 실제 에지의 중심을 찾아야 한다.
    • 단일 에지(single edge): 하나의 에지는 하나의 점으로 표현되어야 한다.
  • 캐니는 이러한 조건을 만족하는 새로운 형태의 에지 검출방법을 제시하였으며 이를 캐니 에지 검출기(canny edge detector)라고 한다.
    • 소벨 에지 검출 방법이 단순히 그래디언트 크기만을 이용하여 에지를 찾는 방법이라면, 캐니 에지 검출기는 그래디언트의 크기와 방향을 모두 고려하여 좀 더 정확한 에지 위치를 찾을 수 있다.
    • 또한 에지는 서로 연결되어 있는 가능성이 높다는 점을 고려하여 그래디언트 크기가 다소 약하게 나타나는 에지도 놓치지 않고 찾을 수 있다.
    • 캐니 에지 검출기는 내부적으로 네 개의 연산 과정을 포함한다. 이 네 가지 연산 과정은 아래 이미지에 정리되어 있다.

가우시안 필터링

  • 캐니 에지 검출기의 첫 번째 과정은 가우시안 필터링이다.
    • 캐니 에지 검출기의 첫 번째 단계에서 가우시안 필터를 적용하는 이유는 영상에 포함된 잡음을 제거하기 위함이다.
    • 가우시안 필터링에 의해 영상이 부드러워지면서 에지의 세기도 함께 감소할 수 있기 때문에 적절한 표준편차를 선택하여 가우시안 필터링을 수행해야 한다.
    • 영상에 포함된 잡음이 심하지 않다면 가우시안 필터링은 생략할 수 있다.

그래디언트 계산

  • 캐니 에지 검출기의 두 번째 과정은 영상의 그래디언트를 구하는 작업이다. 캐니 에지 검출기에서 그래디언트 계산은 보통 3×3 소벨 마스크를 사용한다.
    • 다만 앞서 설명한 소벨 마스크가 그래디언트 크기만 고려했다면 캐니 에지 검출기는 그래디언트 방향도 함께 고려한다.
    • 그러므로 가로 방향과 세로 방향으로 각각 소벨 마스크 필터링을 수행한 후, 그래디언트 크기와 방향을 모두 계산해야 한다.
  • 2차원 공간에서 정의된 함수 f(x, y) 의 그래디언트를 \| \nabla f \| = f_{x}i + f_{y}j 라고 할 경우,
    • 그래디언트 크기는 \| \nabla f \| = \sqrt{f_{x}^{2} + f_{y}^{2}} 로 정의되고 이를 벡터 \nabla f 의 L2 노름(L2 norm)이라고 한다.
    • 그러나 그래디언트 크기를 실제로 계산할 때는 연산 속도 향상을 위해 그래디언트 크기를 \| \nabla f \| \approx |f_{x}| + |f_{y}| 형태로 계산하기도 하며, 이를 벡터 \nabla f 의 L1 노름(L1 norm)이라고 한다.
    • 실제로 OpenCV 에 구현되어 있는 캐니 에지 검출기에서도 그래디언트 크기 계산시 기본적으로 L1 노름을 사용한다.

비최대 억제

  • 에지 검출을 위해 단순히 그래디언트 크기가 특정 임계값보다 큰 픽셀을 선택할 경우, 에지 근방의 여러 픽셀이 한꺼번에 에지로 선택될 수 있다. 에지가 두껍게 표현되는 현상을 방지하기 위해 캐니 에지 검출기에서는 비최대 억제(non-maximum suppression) 과정을 사용한다.
    • 비최대 억제는 그래디언트 크기가 국지적 최대(local maximum)인 픽셀만을 에지 픽셀로 설정하는 기법이다. 상대적으로 국지적 최대가 아닌 픽셀은 에지 픽셀에서 제외하기 때문에 비최대 억제라는 용어를 사용한다.
  • 일반적인 2차원 영상에서 국지적 최대를 찾으려면 특정 픽셀을 둘러싸고 있는 모든 픽셀 값을 검사하여 국지적 최대인지 판별해야 한다.
    • 그러나 캐니 에지 검출기의 비최대 억제 과정에서는 그래디언트 벡터의 방향과 같은 방향에 있는 인접 픽셀끼리만 국지적 최대 검사를 수행한다. 결과적으로 비최대 억제를 수행함으로써 가장 변화율이 큰 위치의 픽셀만 에지로 검색된다.

이중 임계값을 이용한 히스테리시스 에지 트래킹

  • 소벨 에지 검출 방법에서는 그래디언트 크기가 특정 임계값보다 크면 에지 픽셀로, 작으면 에지가 아닌 픽셀로 판단했다. 이 경우 조명이 조금 바뀌거나 임계값을 조금만 조절해도 에지 픽셀 판단 결과가 크게 달라질 수 있다.
    • 즉, 하나의 임계값을 사용할 경우 이분법으로 결과가 판단되기 때문에 환경 변화에 민감해질 수 있다. 이러한 문제를 보완하기 위해 캐니 에지 검출기에서는 두 개의 임계값을 사용한다.
  • 캐니 에지 검출기에서 사용하는 두 개의 임계값 중에서 높은 임계값을 T_{High} , 낮은 임계값을 T_{Low} 라고 할 때,
    • 만약 그래디언트 크기가 T_{High} 보다 크면 이 픽셀은 최종적으로 에지로 판단하고 그래디언트 크기가 T_{Low} 보다 작으면 에지 픽셀이 아니라고 판단한다.
    • 그래디언트 크기가 T_{High} T_{Low} 사이인 픽셀은 에지일 수도 있고 에지가 아닐 수도 있다고 판단하며, 이런 픽셀에 대해서는 추가적인 검사를 수행한다.
  • 그래디언트 크기가 T_{High} 보다 큰 픽셀을 강한 에지(strong edge)라고 표현하고, T_{High} T_{Low} 사이인 픽셀을 약한 에지(weak edge) 라고 할 때,
    • 캐니 에지 검출기의 마지막 단계에서는 히스테리시스 에지 트래킹(hysteresis edge tracking) 방법을 사용하여 약한 에지 중에서 최종적으로 에지로 판별할 픽셀을 선택한다.
    • 히스테리시스 에지 트래킹 방법은 에지 픽셀이 대체로 상호 연결되어 있다는 점을 이용한다.
    • 만약 약한 에지 픽셀이 강한 에지 픽셀과 서로 연결되어 있다면 이 픽셀은 최종적으로 에지로 판단하고, 강한 에지와 연결되어 있지 않은 픽셀은 최종적으로 에지가 아니라고 판단한다.
    • 아래 그림에서 세 가지 형태의 에지 후보 중 (a)는 강한 에지와 연결되어 있으므로 모든 픽셀이 에지로 판별되고, (b)는 강한 에지와 연결이 없으므로 에지로 판별하지 않는다. (c)는 강한 에지와 연결되어 있으므로 에지로 판별하지만 T_{Low} 보다 작은 픽셀은 에지로 판별하지 않는다.

  • OpenCV에서 캐니 알고리즘 검출은 Canny() 함수에 구현되어 있다.
    • Canny() 함수는 두 가지 형태로 정의되어 있는데, 하나는 일반 영상을 입력으로 전달하여 에지를 검출할 때 사용하고, 다른 하나는 이미 x 방향과 y 방향의 미분 영상을 가지고 있을 때 사용한다.
    • Canny() 함수를 사용할 때는 두 개의 임계값을 적절하게 지정하는 것이 중요하다.
    • threshold1과 threshold2 인자에 지정하는 두 개의 임계값은 캐니 에지 검출기의 히스테리시스 에지 트래킹 단계에서 사용된다.
    • 보통 threshold1 인자에는 낮은 임계값을 지정하고 threshold2 인자에는 높은 임계값을 지정한다. 낮은 임계값과 높은 임계값은 보통 1:2 또는 1:3의 비율로 지정한다.
  • Canny() 함수를 사용하여 에지를 검출하는 예제는 아래와 같다.
void canny_edge()
{
Mat src = imread("lenna.bmp", IMREAD_GRAYSCALE);

if (src.empty())
{
cerr << "Image load failed!" << endl;
return;
}

Mat dst1, dst2;
Canny(src, dst1, 50, 100);
Canny(src, dst2, 50, 150);

imshow("src", src);
imshow("dst1", dst1);
imshow("dst2", dst2);

waitKey();
destroyAllWindows();
}

직선 검출과 원 검출

허프 변환 직선 검출

  • 직선은 영상에서 찾을 수 있는 많은 특징 중 하나이며 영상을 분석함에 있어 중요한 정보를 제공한다. 
    • 영상에서 직선 성분을 찾기 위해서는 우선 에지를 찾아내고, 에지 픽셀들이 일직선 상에 배열되어 있는지를 확인해야 한다.
  • 영상에서 직선을 찾기 위한 용도로 허프 변환(hough transform) 기법이 널리 사용된다.
    • 허프 변환은 2차원 xy 좌표에서 직선의 방정식을 파라미터(parameter) 공간으로 변환하여 직선을 찾는 알고리즘이다.
  • 일반적인 2차원 평면에서 직선의 방정식은 다음과 같이 나타낼 수 있다.

y = ax + b

  • 이 수식에서 a는 기울기(slope)이고, b는 y 절편(y intersection)이다. 이 직선의 방정식은 다음과 같이 바꿔 쓸 수 있다.

b = -xa + y

  • 방정식을 위와 같이 변경하면 마치 ab 좌표 공간에서 기울기가 -x이고 b절편이 y인 직선의 방정식처럼 보인다.
    • 이처럼 xy 공간에서 직선의 방정식을 ab 공간으로 변경하면 재미있는 현상을 발견할 수 있는데, xy 공간에서 직선은 ab 공간에서 한 점으로 표현되고, 반대로 xy 공간에서 한 점은 ab 공간에서 직선의 형태로 나타난다는 점이다.
  • 아래 이미지에서 (a)의 파란색 실선은 xy 공간에 정의된 직선 y = a_{0}x + b_{0} 이다.
    • 이 수식에서 a_{0} b_{0} 는 직선의 모양을 결정하는 상수이다.
    • xy 공간에서 직선상의 한 점 (x_{0}, y_{0}) 를 선택하고 이 점의 좌표를 이용하면 ab 공간에서 빨간색 직선 b = -x_{0}a + y_{0} 를 정의할 수 있다.
    • 마찬가지로 xy 공간에서 직선상의 다른 한 점 (x_{1}, y_{1}) 를 이용하면 ab 공간에서 보라색 직선 b = -x_{1}a + y_{1} 를 표현할 수 있다.
    • 이 경우 ab 공간에서 빨간색 직선과 보라색 직선이 서로 교차하는 점의 좌표는 (a_{0}, b_{0}) 이며 이는 xy 공간에서 직선의 방정식 y = a_{0}x + b_{0} 를 정의하는 두 개의 파라미터로 구성된 좌표이다.
    • 즉, xy 공간에서 파란색 직선상의 점을 이용하여 생성한 ab 공간상의 직선들은 모두 (a_{0}, b_{0}) 점을 지나간다.

  • 허프 변환을 이용해서 직선의 방정식을 찾으려면 xy 공간에서 에지로 판별된 모든 점을 이용하여 ab 파라미터 공간에 직선을 표현하고, 직선이 많이 교차되는 좌표를 모두 찾아야 한다.
    • 이때 직선이 많이 교차하는 점을 찾기 위해 보통 축적 배열(accumulation array)를 사용한다.
    • 축적 배열은 0으로 초기화된 2차원 배열에서 직선이 지나가는 위치의 배열 원소 값을 1씩 증가시켜 생성한다.
  • 아래 그림은 허프 변환에서 축적 배열을 구축하는 방법을 보여준다.
    • 그림의 왼쪽 xy 영상 좌표계에서 직선 위 세 개의 점을 선택하였고, 각 점에 대응되는 ab 파라미터 공간에서의 직선을 오른쪽 배열 위에 나타냈다. 그리고 배열 위에서 직선이 지나가는 위치의 원소 값을 1씩 증가시킨 결과를 숫자로 나타냈다.
    • 그림의 오른쪽에 나타난 배열이 축적 배열이며, 축적 배열에서 최댓값을 갖는 위치에 해당하는 ab와 b 값이 xy 공간에 있는 파란색 직선의 방정식 파라미터이다.
    • 아래 그림은 하나의 직선에 대해 허프 변환의 예를 설명하였으며, 여러 개의 직선이 존재하는 영상이라면 축적 배열에서 여러 개의 국지적 최댓값을 찾아서 직선의 방정식 파라미터를 결정할 수 있다.

  • 그러나 y = ax + b 형태의 직선의 방정식을 사용할 경우 모든 형태의 직선을 표현하기 어렵다는 잔덤이 있다.
    • 대표적으로 y = ax + b 수식은 y축과 평행한 수직선을 표현할 수 없다. 수직선을 표현하려면 기울기가 무한대가 되어야 하기 때문이다.
    • 그러므로 실제 허프 변환을 구할 때는 다음과 같이 극좌표계 형식의 직선의 방정식을 사용한다.

x cos \theta + y sin \theta = \rho

  • 이 수식에서 \rho 는 원점에서 직선까지의 수직 거리를 나타내고 \theta 는 원점에서 직선에 수직선을 내렸을 때 x축과 이루는 각도를 의미한다. 
    • 이 경우 xy 공간에서 한 점은 \rho \theta 공간에서는 삼각함수 그래프 형태의 곡선으로 표현되고 \rho \theta 공간에서 한 점은 xy 공간에서 직선으로 나타나게 된다.
    • 극좌표계 형식의 직선의 방정식을 사용하여 허프 변환을 수행할 경우에도 축적 배열을 사용하고, 축적 배열에서 국지적 최댓값이 발생하는 위치에서의 \rho \theta 값을 찾아 직선의 방정식을 구할 수 있다.
  • 극좌표계 직선의 방정식을 이용한 허프 변환 직선 검출 과정은 아래 그림과 같다.
    • (a)는 입력 영상이 사용하는 2차원 xy 좌표계이며, 파란색 직선은 x cos \theta_{0} + y sin \theta_{0} = \rho_{0} 이다.
    • 이 직선 위의 세 점을 선택하고 각 점에 대응하는 \rho \theta 공간에서의 곡선을 (b)에 나타냈다.
    • \rho \theta 공간에서 세곡선은 모두 하나의 점에서 교차하며, 이 점의 좌표 (\rho_{0}, \theta_{0}) 가 (a)의 파란색 직선을 나타내는 파라미터가 된다.

  • \rho \theta 는 실수 값을 가지기 때문에 C/C++ 코드로 축적 배열을 구현하려면, \rho \theta 가 가질 수 있는 값의 범위를 적당한 크기로 나눠서 저장하는 양자화 (quantization) 과정을 거쳐야 한다.
    • 예컨대 \theta 는 0에서 \pi 사이의 실수를 가질 수 있는데, 이 구간을 180단계나 360단계로 나눌 수 있다. 구간을 촘촘하게 나눌 경우 정밀한 직선 검출이 가능하지만 연산 시간이 늘어날 수 있다.
  • OpenCV에서는 HoughLines() 함수를 사용하여 허프 변환 직선 검출을 수행할 수 있다.
    • HoughLines() 함수의 첫 번째 인자 image에는 보통 Canny() 함수 등을 이용하여 구한 에지 영상을 지정한다.
    • HoughLines() 함수는 image 영상에서 0이 아닌 픽셀을 이용하여 축적 배열을 구성한다.
    • 직선 파라미터 정보를 받아 올 lines 인자에는 보통 vector<Vec2f> 또는 vector<Vec3f> 자료형의 변수를 지정한다. vector<Vec2f> 자료형을 사용할 경우 \rho \theta 값이 저장되고, vector<Vec3f> 자료형을 사용할 경우 \rho \theta 값 외에 축적 배열에서의 누적 값을 함께 얻어 올 수 있다.
    • rho와 theta 인자는 \rho \theta 값의 해상도를 조정하는 용도로 사용된다. 예컨대 rho에 1을 지정하면 \rho 값을 1픽셀 단위로 설정하며, theta에 CV_PI / 180 을 지정하면 \theta 를 1도 단위로 구분한다. 결국 rho와 theta는 HoughLines() 함수 내부에서 사용할 축적 배열의 크기를 결정하는 역할을 한다.
    • threshold 인자에는 축적 배열에서 직선으로 판단할 임계값을 지정하며, 이 값이 작으면 더 많은 직선이 검출된다.
void hough_lines()
{
Mat src = imread("building.jpg", IMREAD_GRAYSCALE);

if (src.empty())
{
cerr << "Image load failed!" << endl;
return;
}

Mat edge;
Canny(src, edge, 50, 150);

vector<Vec2f> lines;
HoughLines(edge, lines, 1, CV_PI / 180, 250);

// 이하 결과를 화면에 출력하는 코드 생략
}

  • OpenCV는 기본적인 허프 변환 직선 검출 방법 외에 확률적 허프 변환(probabilistic Hough transform)에 의한 직선 검출 방법도 제공한다.
    • 확률적 허프 변환 방법은 직선의 방정식 파라미터 \rho \theta 를 반환하는 것이 아니라 직선의 시작점과 끝점 좌표를 반환한다.
    • 즉, 확률적 허프 변환 방법은 선분을 찾는 방법이다.
  • OpenCV에서 확률적 허프 변환 방법은 HoughLinesP() 함수에 구현되어 있다.
    • HoughLinesP() 함수에서 검출된 선분 정보가 저장되는 lines 인자에는 보통 vector<Vec4i> 자료형의 변수를 지정한다. 각각의 선분 정보는 Vec4i 자료형으로 저장되고 하나의 Vec4i 객체에는 선분의 시작 x, y, 끝 x, y 점이 저장된다.
    • rho, theta, threshold 인자의 의미는 HoughLines()와 동일하다.
    • maxLineGap 인자는 일직선상의 직선이 잡암 등 영향으로 끊어져 있을 때 두 직선을 하나의 직선으로 간주하고자 할 때 사용한다.
void hough_lines_segments()
{
Mat src = imread("building.jpg", IMREAD_GRAYSCALE);

if (src.empty())
{
cerr << "Image load failed!" << endl;
return;
}

Mat edge;
Canny(src, edge, 50, 150);

vector<Vec4i> lines;
HoughLinesP(edge, lines, 1, CV_PI / 180, 160, 50, 5);

// 이하 결과를 화면에 출력하는 코드 생략
}

허프 변환 원 검출

  • 중심 좌표가 (a, b)이고 반지름이 r인 원의 방정식은 다음과 같다.

(x - a)^{2} + (y - b)^{2} = r^{2}

  • 원의 방정식은 세 개의 파라미터를 가지고 있으므로 허프 변환을 그대로 적용하려면 3차원 파라미터 공간에서 축적 배열을 정의하고 가장 누적이 많은 위치를 찾아야 하는데, 이는 너무 많은 메모리와 연산 시간이 필요로 되므로 OpenCV에서는 일반적인 허프 변환 대신 허프 그래디언트 방법(Hough gradient method)을 사용하여 원을 검출한다.
  • 허프 그래디언트 방법은 두 가지로 구성된다.
    • 첫 번째 단계에서는 영상에 존재하는 모든 원의 중심 좌표를 찾고, 두 번째 단계에서는 검출된 원의 중심으로부터 원에 적합한 반지름을 구한다.
    • 원의 중심 좌표를 찾는 과정에서 축적 배열이 사용된다. 다만 허프 그래디언트 방법에서 사용하는 축적 배열은 파라미터 공간에서 만드는 것이 아니라 입력 영상과 동일한 xy 좌표 공간에서 2차원 배열로 만든다.
    • 원의 중심을 찾기 위해 허프 그래디언트 방법은 입력 영상의 모든 에지 픽셀에서 그래디언트를 구하고, 그래디언트 방향을 따르는 직선상의 축적 배열 값을 1씩 증가 시킨다.
  • 허프 그래디언트 방법을 이용하여 원의 중심을 검출하는 과정은 아래 그림과 같다.
    • 원주 상의 모든 점에 대해 그래디언트 방향의 직선을 그리고, 직선 상의 축적 배열 값을 증가 시키면 결과적으로 원의 중심 위치에서 축적 배열 값이 크게 나타나게 된다.
    • 일단 원의 중심을 찾은 후에는 다양한 반지름의 원에 대해 원주 상에 충분히 많은 에지 픽셀이 존재하는지 확인하여 적절한 반지름을 선택한다.

  • OpenCV에서는 HoughCircles() 함수를 사용하여 원을 검출할 수 있다.
    • HoughCircles() 함수의 첫 번째 인자에는 원본 그레이스케일 입력 영상을 전달한다.
    • 직선을 검출하는 HoughLines()와 HoughLinesP() 함수에서는 입력 영상으로 에지 영상을 전달하였지만, HoughCircles() 함수의 입력 영상에는 에지 영상이 아닌 원본 그레이스케일 영상을 전달하면 함수 내부에서 Sobel() 함수와 Canny() 함수를 이용하여 그레디언트와 에지 영상을 계산한 후 허프 그래디언트 방법으로 원을 검출한다.
    • HoughCircles() 함수의 circles 인자에는 vector<Vec3f> 또는 vector<Vec4f> 자료형의 변수를 지정하는데, vector<Vec3f> 자료형을 사용하면 원의 중심 좌표가 (a, b)와 반지름 r이 차례대로 저장되고, vector<Vec4f> 자료형을 사용할 경우 추가적으로 축적 배열 누적 값이 저장된다.
    • dp 인자는 사용할 축적 배열의 크기를 결정하는 용도로 사용된다. 만약 dp 인자를 1로 지정하면 입력 영상과 같은 크기의 축적 배열을 사용하고, 2를 지정하면 입력 영상의 가로와 세로 크기를 2로 나눈 크기의 축적 배열을 사용한다.
    • minDist 인자에는 인접한 원의 최소 거리를 지정한다. 즉, 두 원의 중심점 사이 거리가 minDist 보다 작으면 두 원 중 하나는 검출하지 않는다.
    • param1 인자는 HoughCircles() 함수 내부에서 캐니 에지 검출기를 이용할 때 높은 임계값으로 사용된다. 캐니 에지 검출기의 낮은 임계값은 param1의 절반으로 설정한다. param2는 축적 배열에서 원의 중심을 찾을 때 사용하는 임계값이다.
    • minRadius와 maxRadius 인자에는 검출할 원의 최소 반지름과 최대 반지름을 지정한다. 만약 영상에서 검출할 원의 대략적인 크기를 알고 있다면 minRadius와 maxRadius 를 지정하여 연산 속도를 향상시킬 수 있다.
void hough_circles()
{
Mat src = imread("coins.png", IMREAD_GRAYSCALE);

if (src.empty())
{
cerr << "Image load failed!" << endl;
return;
}

Mat blurred;
blur(src, blurred, Size(3, 3));

vector<Vec3f> circles;
HoughCircles(blurred, circles, HOUGH_GRADIENT, 1, 50, 150, 30);

// 이하 결과를 화면에 출력하는 코드 생략
}

[ssba]

The author

지성을 추구하는 사람/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.