라인 허프 변환(hough transform for line detection)

이번엔 라인 허프 변환에 대해 알아봅시다.

허프변환(hough transform, 줄여서 HT)은 영상분석, 컴퓨터 비전, 패턴 인식 등 분야에서 사용되는 '특징추출' 방법 중 하나입니다.

직선(lines), 원(circles), 타원(ellipses) 등의 추출 패턴이 있지만

여기서는 직선에 대해서만 보도록 하겠습니다.

 

허프변환의 원리

 

 

 

왼쪽에 있는 좌표계는 줄곧 보아온 영상 공간으로 y-x로 표기된다.

여기에 세 점이 있다고 하자.

이때 알아내야 하는 정보는 이들이 직선을 이루는지 여부와 이룬다면 직선의 방정식이다.

어떤 점 (yi,xi)를 지나는 직선은 yi=axi+b로 표현할 수 있는데 이 식을 만족하는 (b,a) 쌍은 무수히 많다.

예를 들어, (yi,xi)=(2,4)라면

직선의 방정식은 2=4a+b가 되는데, a가 변함에 따라 b가 결정된다. a가 가질 수 있는 값이 무수히많기 때문에 (b,a) 쌍은 무수히 많다.

그런데 2=4a+b를 b=-4a+2로 바꾸어 쓰면,

오른쪽 그림의 b-a 공간에서 기울기가 -4이고 절편이 2인 직선을 이룬다. 그림 3.27의 상황에서는 y-x 공간에 세 개의 점이 같은 직선 위에 놓여있으므로, b-a 공간에서는 이들에 해당하는 세 개의 직선이 한 점에서 만나야 한다.

왜냐하면 y-x 공간에서 세 점이 이루는 직선은 같은 기울기 (a1)와 같은 절편(b1)을 가지기 때문이다.

영상 공간(y-x 공간)에 있는 각각의 에지 점 (yi,xi)에 대해 b=-xia+yi 방정식의 자취를 b-a 공간에 그린다. b-a 공간에서 자취가 짙은 점 (bj,aj)를 추출한다.

이 점은 y-x 공간에서 y=ajx+bj라는 직선이다. 이러한 점은 여러 개 일 수 있다.

 

 

조금 쉽게 설명을 하자면

x,y 평면에서 에지의 점들이 a,b 공간(파라미터 공간)에서는 직선으로 나오는데 그 직선들이 만나는 점을 Q(a,b)라고 할때 Q는 x,y 공간에서의 기울기와 절편값을 의미하게 된다.

그것을 역이용하면 x,y평면에서 에지의 라인을 검출해서 변환할 수 있다!!

 

 

그냥 무작정 추출하는 것이 아니라 에지들을 추출한 후 그 에지들을 가지고 허프변환을 한다.

여기서는 캐니 에지 디텍트를 한 영상을 가지고 살펴보겠다.

 

 

 

#include <math.h>
#include <windows.h>
#include <stdio.h>
using namespace std;

int main()
{
 
 int height= 256;
 int width=256;
 
 unsigned char OrgImg[256][256];
 
 register int i,j,k;

 unsigned char* orgImg = new unsigned char [height*width];
 unsigned char* outImg = new unsigned char [height*width];

 //for(i=0; i<height; i++) for(j=0; j<width; j++) orgImg[i*width+j] = m_InImg[i][j];

 

 

 FILE *infile= fopen("road.raw","rb");
 if(infile==NULL){printf("error!");return 0;}
 fread(orgImg, sizeof(char),256*256,infile);
 fclose(infile);

 
 int d, index;
 float p2d = 3.141592654f/180.0f;

 int H[360][362]={0};
 int thres = 60;

 float *LUT_COS = new float [360];
 float *LUT_SIN = new float [360];
 
 

 for(i=0; i<360; i++)
 {
  LUT_COS[i] = (float)cos(i*p2d);
  LUT_SIN[i] = (float)sin(i*p2d);
 }

 for(i=0; i<height*width; i++) outImg[i] = orgImg[i];

 // For voting
 for(i=0; i<height; i++)
 {
  index = i*width;
  for(j=0; j<width; j++)
  {
   if(orgImg[index+j] == 255)
   {
    for(k=0; k<360; k++)
    {
     d = (int)( i*LUT_COS[k] + j*LUT_SIN[k] );
     if(d >=4 && d<= 360) H[k][d]++;
    }
   }
  }
 }

 // For display
 for(d=4; d<=360; d++)
 {
  for(k=0; k<360; k++)
  {
   if(H[k][d] > thres)
   {
    i = j = 2;

    for(j=2; j<height; j++) // vertical pixel
    {
     i = (int)( (d-j*LUT_SIN[k])/LUT_COS[k] );
     if( i<height && i>0) outImg[i*width+j] = 255;
    }

    for(i=2; i<width; i++) // horizontal pixel
    {
     j = (int)( (d-i*LUT_COS[k])/LUT_SIN[k] );
     if( j<height && j>0) outImg[i*width+j] = 255;
    }
   }
  }
 }

 delete []LUT_COS;
 delete []LUT_SIN;

 

// for(i=0; i<height; i++) for(j=0; j<width; j++) outImg[i][j] = outImg[i*width+j];
  FILE *outfile = fopen("result.raw","wb");
 fwrite(outImg,sizeof(char),256*256,outfile);
 fclose(outfile);

 delete []orgImg;
 delete []outImg;

// UpdateAllViews(NULL); 

 

 return 0;
}

 

 

 

 road.rawresult.raw

 

왼쪽영상이 캐니에지디텍터에 의한 영상이고

이 영상을 허프변환한 영상이 오른쪽 영상이다