[Computer Vision] Hough Transform

Overview

• 검출된 엣지를 여러가지 분야에서 활용하는 방법을 배운다.
• 엣지를 간단하게 표현할 수 있는 방법을 배운다.
• 엣지를 통해 선분이나 원을 찾는 방법을 배운다.

---

엣지 연결과 선분 근사

엣지의 표현 방법

• 위 이미지에는 16 x 8 이미지가 있다.
• 영상에서 엣지가 차지하는 영역이 적기 때문에 메모리 사용 측면에서 비효율적이다.
• 메모리를 줄이면서 효율적으로 엣지의 위치를 추적하는 방법들이 있다.
• 첫번째 방법은 체인코드를 사용하는 것이다.

• 영상의 화소를 쭉 훑다가 처음 만나는 점을 기준으로 오른쪽 방향을 0 기준으로 잡아서 8연결성으로 살펴본다.
• 체인코드는 위와 같은 8 연결성에서 어떻게 연결되어 있는지 표현하는 것을 의미한다.
• 영상에서 엣지 성분들은 다음과 같이 분류해볼 수 있다.@ (끝점) : edge가 끝나는 점, edge를 기준으로 8연결성을 살펴보았을 때 한개의 edge 성분만 있음

• + (분기점) : edge가 두가지 방향으로 연결되는 점, edge를 기준으로 8연결성을 살펴보았을 때 최소 3개 이상 연결
• O (통과점) : edge 성분의 8연결성을 살펴보았을 때 2개의 edge 정보가 있는 경우

• 끝점과 분기점, 분기점과 통과점, 분기점과 분기점으로 나뉜 지점을 토막으로 나누어 볼 수 있다.

• 각 토막에 해당되는 영상에서의 좌표값을 사용하면 더 적은 메모리를 사용하여 표현할 수 있다.
• 체인코드는 시작지점 좌표값으로 시작하여 방향만 남겨주어 더 효율적으로도 표현할 수 있다.

선분 근사

• A점과 B점을 이어주는 직선으로부터 가장먼점 h가 있을 때 선분 분할을 재귀적으로 반복해서 엣지 성분을 구해본다.
• 다음과 같은 곡선 모양의 엣지 성분을 근사적으로 표현할 수 있는 방법을 생각해보는 것이다.

• A, B 끝 점을 연결하는 직선의 방정식을 만들어 보았지만 엣지 성분을 대표하기에 거리가 있다.
• 곡선과 직선 사이에 가장 거리가 먼 지점을 A'을 선택하여 재귀적으로 직선을 구해나간다.

• 위에서 언급된 과정을 재귀적으로 계산하여 직선의 방정식을 엣지 성분에 근사시킬 수 있다. 
• 근사된 모양은 다음과 같다.

---

허프 변환

• 엣지를 통해 선분, 원을 검출하는 방법
• Hough Transform : 차원(좌표계)의 변환

• 2차원 영상에서 엣지를 표현할 때 너무 많은 메모리가 요구되었다.
• 아이디어: x, y 좌표계를 변환시키면 x, y를 효율적으로 검출할 수 있지않을까?

• 엣지의 연결 과정 없이 선분을 검출한다.
• 엣지를 구성하는 픽셀값을 갖고 어떤 특성을 갖고 있는지를 나타내본다.
• x, y좌표계에서는 좌표값을 하나 하나 살펴보는데 메모리를 비효율적으로 사용하기 때문에 b-a 좌표계로 변환시킨다.
• 이 때 영상 공간 y-x를 기울기 절편 공간 b-a로 변환시킨다.
• 정리하자면 y-x 공간에서 세 점을 이어주는 직선의 방정식을 계산한 후에 기울기와 절편만 알고 있다면 그 위의 모든 좌표를 설명해낼 수 있다.
• 아주 쉽고 극적인 메모리 효율을 보일 수 있다!!!!

 

• 기울기 값이 무한대인 경우 좌표계 변환에 한계가 있기 때문에 극좌표계를 활용한다.
• 원으로 표현된 것을 각도가 변함에 따른 p값을 보여준다.
• 특정 각도에서 하나의 점에서 만나는 것을 확인할 수 있다.
• 정리하자면 y-x좌표계의 3개의 점을 특정 (p, 각도) 값으로 나타낼 수 있어서 메모리를 효율적으로 사용할 수 있다.
• 반대로 말하자면 (p, 각도)을 알고 있을 때 역으로 y-x 좌표계에서의 직선의 방정식을 구할 수 있다.

 

Voting Scheme

• 영상은 이산적이기 때문에 직선의 방정식을 벗어날 가능성이 존재한다.
• 그나마 가장 많이 지나가는 것처럼 보이는 곳을 극 좌표계의 중심점으로 가정할 필요가 있다.
• 직선과 가까운 위치에 Voting이 되는픽셀을 지나는 극 좌표계에서의 직선의 방정식을 찾아보자!

• 직선의 기울기: C, 직선의 x절편 : a, 직선의 y 절편 : b
• 직선의 방정식 y = -(b/a)x + b
• 직선의 방정식에 대한 극좌표를 구해보면?
• 원점으로부터 직선과 직교하는 선분을 긋는다.
• x축과 이루는 각 (세타), 원점과 직선 사이의 거리 (r)
• 목표: (x-y좌표계) => y = -(b/a)x + b 를 (극 좌표계) => (세타, r)로 나타내어보자!
• 기울기와 세타, y절편과 r값과의 관계를 이용한다.

• 위와 같이 여러개의 삼각형을 찾을 수 있다. 우선 파랑색으로 표시된 큰 삼각형을 기준으로 본다.
• 큰 삼각형을 기준으로 sin, cos값을 계산할 수 있다.
• 기울기 값을 계산하기위해 cos세타 / sin 세타를 계산하면 - (b/a)를 표현할 수 있다.

• y절편은 빨간색으로 표현된 부분 삼각형을 활용하여 계산한다.
• sin 세타 = r / b 를 만족하기 때문에
• y절편 b = r / sin세타로 계산할 수 있다. 정리하면 다음과 같다.

• 위 관계를 사용하여 x-y좌표계에서의 모든 좌표를 극좌표로 표현할 수 있게 된다.

• 위에서 소개한 관계식에 따라 x, y 값을 알고 있을 때 각 세타에 대응되는 p값을 계산할 수 있다.
• x-y좌표값들을 모두 p, 세타로 변환시켜서 가장 많이 선택(Voting)되는 점 p와 세타를 선택한다.
• 무한대인 경우가 있기 때문에 극좌표계를 통한 표현법이 효율적이다.

 

Algorithm outline

• H라는 값을 모두 0으로 초기화한다. H는 세타값에 따른 p 누적값을 기록하는 허프만 공간이다.
• 각 엣지 포인트에 대해 세타값을 0~180까지 변경해가면서 다음을 계산한다.
• p = x * cos세타 + y*sin세타, H(세타, p) += 1
• 가장 많이 Voting된 좌표를 찾는다.
• 극좌표에 대해 실제로 Visualize 하면 다음과 같다.

• Voting되는 점을 통해 직선의 방정식의 개수를 예측하거나 모양 같은 것을 예측할 수 있다.

• 엣지 성분들 중에서 특정 엣지만을 뽑아낼 수 있다.

• 자율 주행 차량에서는 차선을 검출할 때 허프만 변환을 사용한다.

• 영상에 잡음이 끼어있더라도 차선과 같이 직선이 긴 경우에는 직선에 대응되는 극좌표값의 누적값이 다른 잡음보다 월등하게 높기 때문이다.
• 따라서 원하는 도로 차선만 잡을 수 있다.

 

Effect of noise

• 정확하게 직선의 방정식을 이루는 경우 극좌표로 변환하면 한점으로 Voting된다.
• 하지만 noise가 끼어있는 경우 하나의 점으로 Voting이 되지 않는다. 이 때에는 어떻게 직선을 찾아낼 것인가?

• 잡음을 대표하는 직선의 방정식을 찾아볼 수 있을 것이다. 어떻게 표현할 수 있을까?

• 너무 널럴하게 혹은 정교하게 noise를 다루면 원하는 직선의 방정식을 도출하지 못할 수 있다.
• 이 문제에 관하여 솔루션은 RANSAC 알고리즘이다.

 

Hough transform for circles

• 허프 변환을 통해 원을 찾는 응용을 해본다.

• 2차원 영상에서 원 모양의 엣지 성분이 있을때 원의 반지름 r값을 알고있다고 가정한다.
• 원위의 점에 대해 직교하는 방향으로 뽑다보면 원 내부와 외부에서 하나의 점씩 뽑힐 것이다.
• 밖에서 Voting이 되는 점은 Sparse하게 퍼질 것이다.
• 원 내부에서 Voting이 되는 점은 원의 중심이다.

• 주어진 픽셀에 원이 있다고 가정하고 원 내부에 Voting 되는 점을 찾으면 원의 중심을 찾을 수 있을 것이다.

 

Generalized Hough transform

• 허프 변환을 일반화해서 사물을 찾고 검색하는 알고리즘으로 응용할 수 있다.

• 어느 물체에 위와 같은 특징을 세웠다고 가정하자!

• 마름모, 원, 세모 특징에 대해 우측과 같이 Voting된다고 가정하자!
• 물체에서 각 특징이 Voting하는 점 중에서 많이 Votinge 되는 점을 찾으면 물체의 중심을 찾을 수 있을 것이다.
• 위 아이디어로 영상에서 물체를 인식한다.

• 영상으로부터 바퀴를 찾았을 때 바퀴로부터 중심 부분이 어디에 맵핑이되는지 생각해볼 수 있을 것이다.
• 뒷바퀴와 앞바퀴를 통해 많이 Voting되는 지점을 찾아서 물체를 검출할 수 있다.

• 주어진 영상으로부터 여러가지 바퀴 영상을 찾아서 평균을 구한다.
• 각 평균 이미지에 대해서 중심 위치가 어떻게 구성되어있을지 mapping해보자!

• 위와 같은 논리로 바퀴도 바퀴도 찾고 특징을 찾아서 중심을 찾도록 mapping을 해보면

• 자동차의 중심위치로 많이 Voting되는 지점으로 자동차를 검출해낼 수 있다.
• 정리하자면 허프변환을 통해 원의 중심을 찾는 아이디어를 확장하고 영상의 특징 영역을 모아서 가장 많이 Voting되는 지점을 찾으면 물체를 검출해낼 수 있다.

• 주어진 영상에서 특징을 찾는다.
• 특징을 중심으로 영역을 모아서 어디에 중심이 있는지 Voting 한다.
• Voting이 가장 많이 되는 점은 물체의 가상의 중심이라고 가정한다.
• 따라서 물체를 검출하는 모델로 만들 수 있다.

• 오토바이, 사람, 소와 같이 특정 기준으로 Voting을 하면 물체가 잘 검출되고 있다.
• 부분적으로 가려진 이미지에 있어서는 단점이 존재할 수 있다.
• 허프 변환의 장점 : 
  가려짐, 잡음이 있어도 잘 검출할 수 있다.
• 허프 변환의 단점 :
  처리시간이 많이 걸리고 모델이 많이 변하는 경우에 잘 검출하지 못한다. 즉, 자동차 오토바이와 같은 모양이 한정되어있는 경우에는 잘 찾지만 모델을 보는 방향에 따라 잘 검출하지 못할 수 있다.

---

RANSAC

• 주어진 영상에 잡음이 있을때 효율적으로 직선의 방정식을 구하는 방법이다.

• 선형 회기 방법을 통해 주어진 데이터에 대한 직선의 방정식을 계산할 수 있다.
• 최소제곱법을 사용하는 것도 일반적이지만 시간이 오래 걸린다.
• 시간을 줄이면서 주어진 데이터에서 직선의 방정식을 구하는 방법을 알아볼 것이다.

• 직선을 검출하는데 잡음을 제외하고 임의의 선택된 점들이 가장 많이 Voting하는 점들을 통해 직선의 방정식을 구한다.

• 위와 같은 영상이 주어졌을 때 빨간색으로 표시된 직선 모양으로 모여있는 점을 제외한 나머지를 잡음으로 생각한다.
• 모여있는 점을 RANSAC을 통해 직선의 방정식을 도출하는 것이다.
• 최소제곱법은 모여있는 점에 대해 모두 거리를 계산하여 직선의 방정식을 구하기 때문에 시간이 오래걸린다.
• 잡음도 직선을 찾는데 영향을 주기 때문에 정확한 직선 계산이 어려워질 수 밖에 없다.

Step by step

• 랜덤하게 두점을 선택하여 두 점의 직선의 방정식을 구한다.

• 특정 범위 안에 전체 데이터가 몇개가 들어오는지 세어본다.

• 거리를 모두 측정했을 때 특정 범위안의 데이터가 전체의 몇퍼센트인지 세어본다.

• 위 데이터가 전체의 80%가 되지 않는다면 전체 데이터를 설명할 수 없다고 가정한 후 버린다.

• 랜덤하게 선택한 다른 두 점에 대하여 위와 같은 과정을 반복한다.

• 80% 이상이 된다면 근사적으로 전체 데이터를 대표할 수 있는 직선의 방정식을 도출한다.
• 잡음, outlier가 있어도 빠르게 구할 수 있다.
• 컴퓨터 비젼이나 데이터 마이닝에서도 랜색 알고리즘이 많이 사용된다.

 

이번 장에서 배운 것은 앞장에서 엣지를 뽑았을 때 엣지가 어떤 특성을 갖고 있는지를 영상을 통해 갖고 있으면 매우 비효율적이기 때문에 엣지 성분을 근사적으로 효율적으로 표현하는 방법을 배워보았다. 

대표적으로 엣지 토막, 체인코드, 랜색이 될 수 있으며 극좌표계로 변환시켜서 표현해도 쉽고 빠르게 엣지 성분을 효율적으로 표현할 수 있기에 허프 변환을 배웠다.

다양한 분야에 응용할 수 있다. 자율주행자동차 분야에서는 선분, 차선을 찾는용도, 주어진 영상에서 패턴과 특징을 찾아 물체를 검출하고 인식하는 등의 용도로 활용될 수 있다.