둥's 이것저것

[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 을 이용한 원 검출 방법에 대해 써보겠다.