둥's 이것저것

앞에서 Hough Transform(허프변환)을 이용하여 직선을 검출하게 되는 과정을 나타내었다.

그리고 이번 글에서는 이를 응용하여 직선이 아닌 원을 검출하게 되는 과정을 나타내어 보겠다.

위에 흔하게 볼 수 있는 x-y평면 위에 반지름이 r인 원을 그려보았다.

이 원은 (x-a)^2 + (y-b)^2 = r^2 으로 나타내어 질 수 있다.

그럼 [그림.1]에서 그려진 붉은색 원 위의 임의의 점 P1에 대하여 생각해보자.

P1을 지나는 원은 굉장히 많이 존재할 것이다.

[그림.3]을 통해 볼 수 있듯이 P1을 지나는 원은 무수히 많고 각각의 원은 모두 다른 중심, 다른 반지름을 갖고있다.

즉 (x-a)^2 + (y-b)^2 = r^2 의 식에서 중심을 나타내는 a와 b, 그리고 반지름을 나타내는 r의 값이 모두

다르다는 것이다!

그럼 점 P1을 지나는 원을 타나내는 식을 써보도록 하자.

(x1, y1)의 점은 항상 포함될 것이고 a,b,r은 매개변수가 될 것이다.

앞에서 Hough Transform의 매개변수는 a와 b 로 총 2개였지만 여기서는 r까지 포함되어 3개의 매개변수,

즉 3차원으로 나타내어 지게 된다.

즉 (x-a)^2 + (y-b)^2 = r^2 의 식을 x축, y축이 아닌 a축, b축, r축에 대하여 3차원으로 나타내어 보자!

우선 식을 좀 간단하게 (a-x)^2 + (b-y)^2 = r^2 의 형태로 바꿔보자.

그럼 위와 같이 뒤집어진 원뿔형의 모습으로 그려지게 될 것이다.

원뿔형이 그려진다는 것에 대해 이해가 가지 않는다면

r값에 값을 하나씩 넣어보면서 생각해보자.

우선 r=0 일때 a=x, b=y 가 된다.

따라서 r축의 값은 0이되고 a의 값은 x, b의 값은 y가 되는 한 점을 나타내게 된다.

다음으로 r값에 2를 넣어보자.

(a-x)^2 + (b-y)^2 = 2^2 의 형태로 이는 중심이 (x,y)이고 반지름이 2인 원의 방정식이 된다.

즉 r축의 값이 2일땐 중심은 (x,y), 반지름은 2인 원이 그려지게 된다.

다음으로 r값에 3을 넣어보자.

위와 같은 방식으로 r축의 값이 3일때 중심은 (x,y), 반지름은 3인 원이 그려지게 된다.

이러한 과정의 반복으로 a-b-r 좌표계에는 무한히 큰 뒤집어진 원뿔형의 모습이 그려지게 된다.

그럼 이제 x-y평면상의 다른 점 P2(x2, y2)에 대하여 생각해보자.

점 P2역시 이 점을 지나는 원은 무수히 많이 존재하게 될 것이다.

그리고 위의 과정과 똑같이 점 P2를 지나는 모든 원들을 a-b-r축을 이용하여 표시하여 보자.

위의 [그림.6] 과 같이 나타내어질 수 있을 것이고 여기서 보이는 원뿔은 무한히 큰 원뿔이기 때문에

이때 발생되는 접점의 a,b,r값을 알 수 있고 여기에 해당하는 a,b,r값을 이용하여 x-y 평면에 나타내게 되면

P1과 P2 모두 지나게 되는 원을 그릴 수 있게 된다. ([그림.7] 참고)

따라서 x-y평면 위의 임의의 점들이 a-b-r좌표계에서 동일한 부분에 계속적으로 겹치게 된다면

이 임의의 점들은 모두 동일한 원 위에 나타내어 진다고 볼 수 있다.

그리고 Threshold로 지정된 갯수 이상의 점들이 동일한 원 위에 있게되면 이를 원으로 판단하여 검출하게 된다.

[Hough Transform을 통한 직선 검출]

x-y 평면 위에 임의의 점 P1이 있다고 하자.

이 점 P1을 지나는 직선은 무수히 많이 존재하게 된다.

그럼 이 수많은 직선들 중 하나를 표현해보자.

우리는 흔히 이 직선을 y=ax+b 로 나타낼 수 있을 것이다.

이는 기울기 a와 y절편 b를 이용하여 x값이 변화할 때의 y값을 나타내는 것이다.

하지만 우리는 특정한 점 P1(x1, y1)을 지나는 직선들을 표시하고 싶다.

즉 a와 b의 값을 정해놓고 x를 변화시키며 y값을 찾고싶은 것이 아닌

x와 y를 (x1,y1)으로 그 점을 지나는 모든 직선들을 식으로 나타내고자 한다.

따라서 임의의 직선에서 원점으로 수직한 선을 그리고 그 선의 길이 r와 그때의 선과 x축과의

각도 theta를 이용하여 P1을 지나는 무수한 직선들을 표현하여 보자. 

위의 그림을 통해 알 수 있듯이 r=x1Cos(theta)+y1Sin(theta) 로 표현될 수 있다.

이 부분에 대해서도 이해가 되지 않을 수 있으니 간단하게 설명하고 넘어가도록 하겠다.

[그림.3]에서 붉은 선은 임의의 직선 y=ax+b와 수직이면서 x축과의 각도가 theta이다.

이를 이용하여 r을 구해보자.

위와 같이 나타낼 수 있을 것이고 여기서

r=x1Cos(theta)+y1Sin(theta) 가 성립됨을 확인할 수 있다.

이제 위의 식을 x와 y에 대하여 나타내는 것이 아닌 r과 theta의 값에 대하여 나타내어 보자.

즉 기존의 x축, y축을 r축과 theta축으로 바꾸는 것이다!

x축을 theta축으로 놓고 y축을 r축으로 놓으면

r=x1Cos(theta)+y1Sin(theta) 의 식을 통해 r값이 삼각함수의 합성된 sin파 형태가 나올 것임을 예측할 수 있다.

즉 그림.5와 비슷한 형태의 그래프를 나타내게 된다.

그럼 다시 처음으로 돌아가보자.

우리는 x-y 좌표 위의 임의의 점 P1에 대하여 그 지점을 지나는 무수한 직선들을 r과 theta를 이용하여 나타내었다.

그럼 x-y좌표계 위에 있는 또 다른 점 P2에 대하여 생각해보자.

점 P2 역시 이 점을 지나는 직선은 무수히도 많을 것이고 P2(x2, y2)의 점을 지나는 그 무수한 직선들은

위와 같은 방법으로

r=x2Cos(theta)+y2Sin(theta)  로 나타낼 수 있다.

즉 위의 그림의 빨간색 선은

r=x1Cos(theta)+y1Sin(theta) 의 그래프와

r=x2Cos(theta)+y2Sin(theta) 의 그래프를 나타낸 것으로 볼 수 있고 여기서 x축은 theta, y축은 r값임을

알 수 있다.

그럼 여기서 두 그래프가 만나는 교차점은 무엇을 의미할까?

여기서 두 그래프의 교차점은 r값과 theta값이 서로 같나는 것을 의미하고 이는 x-y평면 위의 두 점

P1(x1, y1) 과 P2(x2, y2) 가 한 직선 위에 있다는 것으로 해석할 수 있다.

(두 그래프가 아예 같아 겹치게 되면 P1과 P2는 같은 점이 될 것이다)

그리고 위의 그래프는 2*(pi) 를 주기로 반복될 것이고 따라서 2*(pi)를 주기로 교차점의 위치는 반복될 것이다.

따라서 우리는 뒤에 이어지는 주기는 신경쓰지 말고 0~2*(pi)까지의 범위 안에서만 보도록 하자.

0~2*(pi) 안에서 총 2번 접점이 생기는 것을 확인할 수 있다

이는 P1에서 P2로의 직선을 나타내는 교점 1개와 P2에서 P1으로의 직선을 나타내는 교점 1개 이므로

0~2*(pi) 사이에 총 2개의 접점이 생기는 것이고 각각의 접점은 pi 주기로 생기게 될 것이다.

그럼 r-theta 평면의 그래프에서 한 접점에 굉장히 많은 삼각함수 곡선들이 겹치게 되면 어떨까?

이는 많은 점들이 한 직선 위에 있다는 것으로 해석할 수 있고 몇개의 곡선들이 한 접점에 모였을때 그 선을 직선인지

판단할지는 opencv 함수 중 HoughLinesP() 함수의 Threshold 값으로 지정해주게 된다.

즉 Threshold값을 100으로 지정하였다면 100개의 점이 한 직선위에 있을 때 그 직선을 검출하겠다는 의미가 된다.

바로 다음 게시물로 Hough Transform 을 이용한 원 검출 방법에 대해 써보겠다.