霍夫變換是圖像進行中從圖像中識别幾何形狀的基本方法之一，應用很廣泛，也有很多改 進算法。最基本的霍夫變換是從黑白圖像中檢測直線(線段)。廣義的Hough變換已經不僅僅局限于提取直線，二值任意可以用表達式表達的曲線，比如圓，橢圓，正弦餘弦曲線，等等，但是曲線越是複雜，所需參數越多，運算的時間也就越多。歸根結底，Hough變換的精髓在于投票機理，将圖像空間轉換到參數空間進行求解。我們先看這樣一個問題：設已知一黑白圖像上畫了一條直線，要求出這條直線所在的位置 。我們知道，直線的方程可以用y=k*x+b 來表示，其中k和b是參數，分别是斜率和截距。過某一點 (x0,y0)的所有直線的參數都會滿足方程y0=kx0+b。即點(x0,y0)确定了一族直線。方程y0=kx0+b在 參數k–b平面上是一條直線，(你也可以是方程b=-x0*k+y0對應的直線)。這樣，圖像x–y平面上的 一個前景像素點就對應到參數平面上的一條直線。我們舉個例子說明解決前面那個問題的原理。設 圖像上的直線是y=x, 我們先取上面的三個點：A(0,0), B(1,1), C(22)。可以求出，過A點的直線 的參數要滿足方程b=0, 過B點的直線的參數要滿足方程1=k+b, 過C點的直線的參數要滿足方程 2=2k+b, 這三個方程就對應着參數平面上的三條直線，而這三條直線會相交于一點(k=1,b=0)。 同 理，原圖像上直線y=x上的其它點(如(3,3),(4,4)等) 對應參數平面上的直線也會通過點(k=1,b=0) 。這個性質就為我們解決問題提供了方法：首先，我們初始化一塊緩沖區，對應于參數平面，将其所有資料置為0.對于圖像上每一前景點，求出參數平面對應的直線，把這直線上的所有點的值都加１。最後，找到參數平面上最大點的位置，這個位置就是原圖像上直線的參數。上面就是霍夫變換的基本思想。就是把圖像平面上的點對應到參數平面上的線，最後通過 統計特性來解決問題。假如圖像平面上有兩條直線，那麼最終在參數平面上就會看到兩個峰值點， 依此類推。在實際應用中，y=k*x+b形式的直線方程沒有辦法表示x=c形式的直線(這時候，直線的斜 率為無窮大)。是以實際應用中，是采用參數方程p=x*cos(theta)+y*sin(theta)。這樣，圖像平面 上的一個點就對應到參數p—theta平面上的一條曲線上。其它的還是一樣。Hough變換求取直線的源碼：
Hough變換求取直線的源碼：
//提取直線 能夠在二值圖像中提取場地中的白線，并進行重建
//采用Hough變換
#include <iostream>
#include<cv.h>
#include <highgui.h>
#include <math.h>
#define PI 3.1415926
using namespace std;
int main(){
IplImage * image,*image2;
image = cvLoadImage("E:\\image\\game\\board.bmp",0);
cvNamedWindow("image",1);
cvShowImage("image",image);
//Hough變換
//用Hough提取出所有的直線，并在一張新圖中進行繪制
image2 = cvCreateImage(cvSize(image->width,image->height),image->depth,1);
int i,j;
unsigned char *ptr,* dst;
//參數空間的參數 角度0~度 每格2度 distance = fabs(x*cosA + y *sinA)
double angle;
int distance;
int PerAngle = 2;
int m,n;
int AngleNum = 90; //角度範圍0~360度
int maxDistance = (int)(sqrt(pow((double)image->width,2)+ pow((double)image->height,2)) + 2 );
//cout<<maxDistance<<endl;
//參數空間各個點的統計值，使用一維數組，排序友善
//申請一塊記憶體，存放各個直線的出現次數
int * number = new int [AngleNum * maxDistance];
double Hsin,Hcot;
int count = 0;
int max ,lineAngle, rol;
//number指派0
for (i= 0; i< AngleNum * maxDistance; i++)
{
number[i] = 0;
}
for (i = 0 ; i< image->height; i++)
{
for (j = 0 ; j < image->width ; j++)
{
ptr = (unsigned char *)image->imageData + i*image->widthStep +j;
//統計每個直線出現的機率
if ( *ptr != 0)
{
//count++;
//cout<<count<<endl;
for (m = 0 ; m < AngleNum; m++ )
{
angle = (double)m*PerAngle*PI/180.0;
distance = (int)(fabs(j*cos(angle)+ i*sin(angle)));
//cout<<"distance: "<< distance<<endl;
//*(number+ AngleNum* (int)(distance + 0.5) + m) = (*(number+ AngleNum* (int)(distance + 0.5) + m)) +1;
number[AngleNum * distance + m]++;
}
}
}
}
//列印各個方格的統計個數
for (m = 0 ; m <maxDistance; m++)
{
for (n = 0 ; n < AngleNum; n++ )
{
if (number[AngleNum * m + n] > 100)
{
printf("angle %d distance : %d number %d\n",n*2 , m , number[AngleNum* m + n] );
}
}
}
//首先将image2 的所有值指派為0
for (i = 0 ; i< image2->height; i++)
{
for (j = 0 ; j< image2->width; j++)
{
dst =(unsigned char *) image2->imageData + i*image->widthStep + j;
*dst =0;
}
}
//尋找變換域中的直線 假設一條直線上有20個點以上，則認為是一條直線 那麼就在新的圖檔中畫出該直線
//尋找機率最大的直線
/* 添加直線
lineAngle = 0;
rol = 0;
max = number[0];
for (m = 0 ;m< maxDistance ;m++ )
{
for (n = 0 ; n< AngleNum; n++)
{
if (number[AngleNum * m + n] > max)
{
max =number[AngleNum * m + n];
rol = m;
lineAngle = n;
}
}
}
cout<<"m :" <<rol<<" n:"<<lineAngle<<" max" << max<<endl;
//根據角度和距離在image2中添加該圖檔
angle = lineAngle*PerAngle*PI/180;
Hcot = cos(angle)/sin(angle);
Hsin = sin(angle);
for (j = 0;j< image2->width;j++ )
{
i = (int)(rol/Hsin - j*Hcot);
dst = (unsigned char*)image2->imageData + i*image->widthStep + j;
*dst = 255;
}
//添加第二條直線
//最大值鄰域處指派為0
number[rol*AngleNum+ lineAngle] = 0;
for (m = rol-1 ; m<= rol+1; m++)
{
for (n = lineAngle -1 ; n<= lineAngle +1 ; n++)
{
number[m*AngleNum + n] = 0;
}
}
max = number[0];
lineAngle = 0;
rol = 0;
for (m = 0 ;m < maxDistance ;m++ )
{
for (n = 0 ; n < AngleNum; n++)
{
if (number[AngleNum * m + n] > max)
{
max =number[AngleNum * m + n];
rol = m;
lineAngle = n;
}
}
}
cout<<"m :" <<rol<<" n:"<<lineAngle<<" max" << max<<endl;
//根據角度和距離在image2中添加該圖檔
angle = lineAngle*PerAngle*PI/180;
Hcot = cos(angle)/sin(angle);
Hsin = sin(angle);
for (j = 0;j< image2->width;j++ )
{
i = (int)(rol/Hsin - j*Hcot);
if (i< 0 ){i = 0;}
if(i>= image2->height){i = image2->height -1;}
dst = (unsigned char*)image2->imageData + i*image->widthStep + j;
*dst = 255;
}
*/
//畫出所有可能的直線
for (m = 0 ;m< maxDistance ; m++)
{
for (n = 0 ; n< AngleNum ;n++)
{
if (number[m*AngleNum + n] > 110)
{
rol = m;
lineAngle = n;
//根據角度和距離在image2中添加該圖檔
angle = lineAngle*PerAngle*PI/180;
Hcot = cos(angle)/sin(angle);
Hsin = sin(angle);
for (j = 0;j< image2->width;j++ )
{
i = (int)(rol/Hsin - j*Hcot);
if (i< 0 ){i = 0;}
if(i>= image2->height){i = image2->height -1;}
dst = (unsigned char*)image2->imageData + i*image->widthStep + j;
*dst = 255;
}
}
}
}
cvNamedWindow("image2",1);
cvShowImage("image2",image2);
//cvSaveImage("E:\\image\\game\\changjian.bmp",image2);
delete [] number;
cvWaitKey(0);
return 0;
}
在看下面一個問題：我們要從一副圖像中檢測出半徑以知的圓形來。這個問題比前一個還 要直覺。我們可以取和圖像平面一樣的參數平面，以圖像上每一個前景點為圓心，以已知的半徑在 參數平面上畫圓，并把結果進行累加。最後找出參數平面上的峰值點，這個位置就對應了圖像上的 圓心。在這個問題裡，圖像平面上的每一點對應到參數平面上的一個圓。
把上面的問題改一下，假如我們不知道半徑的值，而要找出圖像上的圓來。這樣，一個辦 法是把參數平面擴大稱為三維空間。就是說，參數空間變為x–y–R三維，對應圓的圓心和半徑。 圖像平面上的每一點就對應于參數空間中每個半徑下的一個圓，這實際上是一個圓錐。最後當然還 是找參數空間中的峰值點。不過，這個方法顯然需要大量的記憶體，運作速度也會是很大問題。
有什麼更好的方法麼?我們前面假定的圖像都是黑白圖像(2值圖像)，實際上這些2值圖像 多是彩色或灰階圖像通過邊緣提取來的。我們前面提到過，圖像邊緣除了位置資訊，還有方向資訊 也很重要，這裡就用上了。根據圓的性質，圓的半徑一定在垂直于圓的切線的直線上，也就是說， 在圓上任意一點的法線上。這樣，解決上面的問題，我們仍采用2維的參數空間，對于圖像上的每 一前景點，加上它的方向資訊，都可以确定出一條直線，圓的圓心就在這條直線上。這樣一來，問 題就會簡單了許多。
Hougu變換求取圓源碼：
/************************************************************************/
/* Hough圓變換 */
/************************************************************************/
//白紙上的黑圓圈
#include<cv.h>
#include <highgui.h>
#include <math.h>
#include <iostream>
using namespace std;
int main(){
IplImage * image, *image2;
image = cvLoadImage("E:\\image\\circle2.bmp",0);
cvNamedWindow("image",1);
cvShowImage("image",image);
image2 = cvCreateImage(cvSize(image->width,image->height),image->depth,1);
int i ,j;
int temp = 0;
unsigned char *ptr, *dst;
//參數空間的參數 圓心O（a,b） 半徑radius
int a = 0,b = 0,radius = 0;
//累加器
int A0 = image->height;
int B0 = image->width;
int R0 = (image->width > image->height)? 2*image->width : 2*image->height;//R0取長寬的最大值的2倍
int countLength = A0*B0*R0;
int * count = new int[countLength];
//偏移
int index = A0 * B0 *radius + A0*b + a;
//為累加器指派0
for (i= 0;i<countLength;i++)
{
count[i]=0;
}
//printf("%d",R0);
for (i = 0 ; i< image->height; i++)
{
for (j = 0 ; j< image->width ; j++)
{
ptr = (unsigned char *)image->imageData + i*image->widthStep + j;
//檢測黑線
if (*ptr == 0 )
{
//周遊a ,b 為;累加器指派
for (a = 0 ; a< A0;a++)
{
for (b = 0; b< B0;b++)
{
radius = (int)(sqrt(pow((double)(i-a),2) + pow((double)(j - b),2)));
index = A0 * B0 *radius + A0*b + a;
count[index]++;
temp = count[index];
// printf("%d\n",count[index]);
}
}
}
}
printf("%d\n",i);
}
//image2全部指派為0
for (i= 0; i<image2->height; i++)
{
for (j = 0 ; j< image2->width;j++)
{
dst = (unsigned char *)image2->imageData + i*image2->widthStep + j;
*dst = 0;
}
}
//周遊累加器數組，找出所有的圓
for (a = 0 ; a < A0 ; a++)
{
for (b = 0 ; b< B0; b++)
{
for (radius = 0 ; radius < R0; radius++)
{
index = A0 * B0 *radius + A0*b + a;
if (count[index] > 100)
{
printf("a: %d b: %d r: %d num: %d\n",a,b,radius,count[index]);
//在image2中繪制該圓
for (j = 0 ; j< image->width;j++)
{
i = (int)(sqrt(pow((double)radius,2)- pow((double)(j-b),2)) + a);
if ((i< image2->height) && (i >= 0))
{
dst = (unsigned char*)(image2->imageData + i * image2->widthStep + j);
*dst = 255;
}
//i有兩個值
i = a -(int)(sqrt(pow((double)radius,2)- pow((double)(j-b),2)));
if ((i< image2->height) && (i >= 0))
{
dst = (unsigned char*)(image2->imageData + i * image2->widthStep + j);
*dst = 255;
}
}
}
}
}
}
cvNamedWindow("image2",1);
cvShowImage("image2",image2);
cvSaveImage("E:\\image\\circleHough2.bmp",image2);
cvWaitKey(0);
return 0 ;
}
接下來還有許多類似的問題，如檢測出橢圓，正方形，長方形，圓弧等等。這些方法大都 類似，關鍵就是需要熟悉這些幾何形狀的數學性質。霍夫變換的應用是很廣泛的，比如我們要做一 個支票識别的任務，假設支票上肯定有一個紅顔色的方形印章，我們可以通過霍夫變換來對這個印 章進行快速定位，在配合其它手段進行其它處理。霍夫變換由于不受圖像旋轉的影響，是以很容易 的可以用來進行定位。
霍夫變換有許多改進方法，一個比較重要的概念是廣義霍夫變換，它是針對所有曲線的， 用處也很大。就是針對直線的霍夫變換也有很多改進算法，比如前面的方法我們沒有考慮圖像上的 這一直線上的點是否連續的問題，這些都要随着應用的不同而有優化的方法。
順便說一句，搞圖像處理這一行，在理論方面，有幾本雜志是要看的，自然是英文雜志， 中文期刊好象沒有專門的圖像處理期刊，當然也有不少涉及這方面的期刊，但事實求是來說，的确 比英文雜志水準差很多。
‘IEEE Transactions on Pattern And Machine Intelligence’
‘IEEE Transactions on Image Processing’
是最重要的兩本，其它的如ICIP等的會議文章也非常好。不過，要不想很偏理論， 這些玩藝兒也沒什麼要看的。
2.簡單點概括就是：Hough變換的基本原理在于利用點與線的對偶性，将原始圖像空間的給定的曲線通過曲線表達形式變為參數空間的一個點。這樣就把原始圖像中給定曲線的檢測問題轉化為尋找參數空間中的峰值問題。也即把檢測整體特性轉化為檢測局部特性。比如直線、橢圓、圓、弧線等。
算法如下：
（1）初始化一個變換域空間的數組，r方向上的量化數目圖像對角線方向像素，O方向上的量化數目為180。
（2）順序搜尋圖像的所有黑點。對每一個黑點，在變換域的對應個點加一。
（3）求出變換域最大值點并記錄。最大值點就是直線的所在了。
或者說：hough變換利用圖像空間和hough參數空間的點－線對偶性，把圖像空間中的檢測問題轉換到參數空間。通過在參數空間裡進行簡單的累加統計，然後在hough參數空間尋找累加器峰值的方法檢測直線。例如，圖1(a)中的九條線段對應于如圖1(b)所示的其hough參數空間的九個累加器峰值。圖1(b)中，hough參數空間的橫縱坐标分别為直線極坐标方程:ρ＝x×cos(θ) + y×sin(θ) 的兩個參數ρ和θ。九個峰值的ρ和θ值唯一的确定其對應線段所在直線的兩個參數。并且線段的長度決定坐标(ρ,θ)處的累加值的大小。