图像处理 霍夫变换

2018-09-18 10:22:46 hanjiangtao1995 阅读数 1431

本文讲述霍夫变换的一些内容,关于霍夫变换的总结参考了浅墨_毛星云-OpenCV霍夫变换YuYunTan-经典霍夫变换痴情一笑恋红颜-霍夫变换-----特征提取zlm丶-霍夫变换及应用yqtaowhu-基于OpenCV实现霍夫变换等文章,希望能对霍夫变换有所了解。博主水平有限、欢迎大家一起讨论学习,如果发现错误还请及时帮忙纠正。

 霍夫变换概述

霍夫变换(Hough Transform)是图像处理中的一种特征提取技术,该过程在一个参数空间中通过计算累计结果的局部最大值得到一个符合该特征的集合作为霍夫变换的结果。

霍夫变换于1962年由PaulHough首次提出,最初的Hough变换是设计用来检测直线和曲线,起初的方法要求知道物体边界线的解析方程,但不需要有关区域位置的先验知识。这种方法的一个突出优点是分割结果的Robustness,即对数据的不完全或噪声不是非常敏感。然而,要获得描述边界的解析表达常常是不可能的。该专利对直线采用斜截距参数化,但由于斜率可能变成无穷大,这有可能导致无限变换空间(unbounded transform space)。 

后于1972年由Richard Duda & Peter Hart推广使用,称为“广义霍夫变换[GHT]”,经典霍夫变换用来检测图像中的直线。后来霍夫变换扩展到任意形状物体的识别,多为圆和椭圆。霍夫变换运用两个坐标空间之间的变换将在一个空间中具有相同形状的曲线或直线映射到另一个坐标空间的一个点上形成峰值,从而把检测任意形状的问题转化为统计峰值问题。

 利用广义霍夫变换(GHT),找到模型位置的问题转换为寻找将模型映射到图像中的变换参数的问题。给定变换参数的值,就可以确定模型在图像中的位置。

霍夫变化原理

众所周知, 一条直线在图像二维空间可由两个变量表示:

  • 笛卡尔坐标系:可以由参数斜率和截距(m,b) 表示:y=mx+b
  • 可由参数极径和极角(r,θ)表示:r=xcos\theta +ysin\theta

在笛卡尔坐标系中会存在参数问题,垂直线的斜率不存在(或无限大),这使得斜率参数$m$的值接近于无限。为此,为了更好的计算,Richard O. Duda和Peter E. Hart在1971年4月,提出了极坐标系。其中r是原点到直线上最近点的距离,\theta是x轴与连接原点和最近点直线之间的夹角。如下图所示:

对于一般的点(x_{0}, y_{0})来说,可以将通过这个点的一族直线统一定义为:$r_{0}=x_{0}\cdot\;cos\theta+y_{0}\cdot\;sin\theta$,这就意味着对于每一对(r_{0}, cos\theta)代表一条通过点(x_{0},y_{0})的直线。如果对于一个给定点(x_{0},y_{0})我们在极坐标对极径极角平面绘出所有通过它的直线,将得到一条正弦曲线。正弦曲线的形状取决于,点到所定义原点的距离r。通常r越大,正弦曲线的振幅越大,反之则会越小。例如, 对于给定点x_{0}=8y_{0}=6我们可以绘出r=8\cdot\;cos\theta+6\cdot\;sin\theta的图像 (满足条件r>0,0<\theta<2\pi):

所以我们可以得到一个结论,给定平面中的单个点,那么通过该点的所有直线的集合对应于(r,θ)平面中的正弦曲线,这对于该点是独特的。一组两个或更多点形成一条直线将产生在该线的(r,θ)处交叉的正弦曲线。因此,检测共线点的问题可以转化为找到并发曲线的问题。

继续添加两个点(9,4)和(12,3)得到如下正弦图像:

这三条曲线在平面\theta-r相交于点 (0.925, 9.6), 坐标表示的是参数对(\theta, r)或者是说点(x_{0}, y_{0}), 点(x_{1}, y_{1})和点(x_{2}, y_{2})组成的平面内的直线。一般来说,一条直线能够通过在平面\theta-r寻找交于一点的曲线数量来检测。而越多曲线交于一点也就意味着这个交点表示的直线由更多的点组成,一般来说我们可以通过设置直线上点的阈值来定义多少条曲线交于一点我们才认为检测到了一条直线。这就是霍夫线变换要做的,它追踪图像中每个点对应曲线间的交点,如果交于一点的曲线的数量超过了阈值,那么可以认为这个交点所代表的参数对\theta-r在原图像中为一条直线。
 

霍夫圆变换

霍夫圆变换的基本原理和上面讲的霍夫线变化大体上是很类似的,只是点对应的二维极径极角空间被三维的圆心点x, y还有半径r空间取代。说“大体上类似”的原因是,如果完全用相同的方法的话,累加平面会被三维的累加容器所代替:在这三维中,一维是x,一维是y,另外一维是圆的半径r。这就意味着需要大量的内存而且执行效率会很低,速度会很慢。对直线来说, 一条直线能由参数极径极角(r,\theta )表示. 而对圆来说, 我们需要三个参数来表示一个圆, 也就是:C:(x_{center},y_{center},r)。这里的(x_{center},y_{center})表示圆心的位置,而 r 表示半径, 这样我们就能唯一的定义一个圆 (x-x_{0})^2+(y-y_{0})^2=r^2

过点\bg_white (x_{1},y_{1})的所有圆可以表示为(a_{1}(i), b_{1}(i),r_{1}(i)),过点(x_{2},y_{2})的所有圆可以表示为(a_{2}(i), b_{2}(i),r_{2}(i)),过点(x_{3},y_{3})的所有圆可以表示为(a_{3}(i), b_{3}(i),r_{3}(i)),如果这三个点在同一个圆上,那么存在一个值(a_{0},b_{0},r_{0}),使得a_{0}= a_{1}(k)=a_{2}(k)=a_{3}(k)b_{0} = b_{1}(k)=b_{2}(k)=b_{3}(k)r_{0} = r_{1}(k)=r_{2}(k)=r_{3}(k),即这三个点同时在圆(a_{0},b_{0},r_{0})上。

 

 

首先,分析过点\bg_white (x_{1},y_{1})的所有圆\bg_white (a_{1}(i), b_{1}(i),r_{1}(i)),当确定r_{1}(i)时 ,(a_{1}(i),b_{1}(i))的轨迹是一个以(x_{1},y_{1},r_{1}(i))为中心半径为r_{1}(i)的圆。那么,所有圆(a_{1}(i),b_{1}(i),r_{1}(i))的组成了一个以(x_{1},y_{1},0)为顶点,锥角为90^{\circ}的圆锥面。
三个圆锥面的交点A 既是同时过这三个点的圆。

2017-11-14 09:28:14 u010312937 阅读数 1806

图像处理之霍夫变换(直线检测算法)

霍夫变换是图像变换中的经典手段之一,主要用来从图像中分离出具有某种相同特征的几何

形状(如,直线,圆等)。霍夫变换寻找直线与圆的方法相比与其它方法可以更好的减少噪

声干扰。经典的霍夫变换常用来检测直线,圆,椭圆等。

 

霍夫变换算法思想:

以直线检测为例,每个像素坐标点经过变换都变成都直线特质有贡献的统一度量,一个简单

的例子如下:一条直线在图像中是一系列离散点的集合,通过一个直线的离散极坐标公式,

可以表达出直线的离散点几何等式如下:

X *cos(theta) + y * sin(theta)  = r 其中角度theta指r与X轴之间的夹角,r为到直线几何垂

直距离。任何在直线上点,x, y都可以表达,其中 r, theta是常量。该公式图形表示如下:

然而在实现的图像处理领域,图像的像素坐标P(x, y)是已知的,而r, theta则是我们要寻找

的变量。如果我们能绘制每个(r, theta)值根据像素点坐标P(x, y)值的话,那么就从图像笛卡

尔坐标系统转换到极坐标霍夫空间系统,这种从点到曲线的变换称为直线的霍夫变换。变换

通过量化霍夫参数空间为有限个值间隔等分或者累加格子。当霍夫变换算法开始,每个像素

坐标点P(x, y)被转换到(r, theta)的曲线点上面,累加到对应的格子数据点,当一个波峰出现

时候,说明有直线存在。同样的原理,我们可以用来检测圆,只是对于圆的参数方程变为如

下等式:

(x –a ) ^2 + (y-b) ^ 2 = r^2其中(a, b)为圆的中心点坐标,r圆的半径。这样霍夫的参数空间就

变成一个三维参数空间。给定圆半径转为二维霍夫参数空间,变换相对简单,也比较常用。

 

编程思路解析:

1.      读取一幅带处理二值图像,最好背景为黑色。

2.      取得源像素数据

3.      根据直线的霍夫变换公式完成霍夫变换,预览霍夫空间结果

4.       寻找最大霍夫值,设置阈值,反变换到图像RGB值空间(程序难点之一)

5.      越界处理,显示霍夫变换处理以后的图像

 

关键代码解析:

直线的变换角度为[0 ~ PI]之间,设置等份为500为PI/500,同时根据参数直线参数方程的取值

范围为[-r, r]有如下霍夫参数定义:

[java] view plain copy
  1. // prepare for hough transform  
  2. int centerX = width / 2;  
  3. int centerY = height / 2;  
  4. double hough_interval = PI_VALUE/(double)hough_space;  
  5.       
  6. int max = Math.max(width, height);  
  7. int max_length = (int)(Math.sqrt(2.0D) * max);  
  8. hough_1d = new int[2 * hough_space * max_length];  

实现从像素RGB空间到霍夫空间变换的代码为:

[java] view plain copy
  1. // start hough transform now....  
  2. int[][] image_2d = convert1Dto2D(inPixels);  
  3. for (int row = 0; row < height; row++) {  
  4.     for (int col = 0; col < width; col++) {  
  5.         int p = image_2d[row][col] & 0xff;  
  6.         if(p == 0continue// which means background color  
  7.           
  8.         // since we does not know the theta angle and r value,   
  9.         // we have to calculate all hough space for each pixel point  
  10.         // then we got the max possible theta and r pair.  
  11.         // r = x * cos(theta) + y * sin(theta)  
  12.         for(int cell=0; cell < hough_space; cell++ ) {  
  13.             max = (int)((col - centerX) * Math.cos(cell * hough_interval) + (row - centerY) * Math.sin(cell * hough_interval));  
  14.             max += max_length; // start from zero, not (-max_length)  
  15.             if (max < 0 || (max >= 2 * max_length)) {// make sure r did not out of scope[0, 2*max_lenght]  
  16.                 continue;  
  17.             }  
  18.             hough_2d[cell][max] +=1;  
  19.         }  
  20.     }  
  21. }  

寻找最大霍夫值计算霍夫阈值的代码如下:

[java] view plain copy
  1. // find the max hough value  
  2. int max_hough = 0;  
  3. for(int i=0; i<hough_space; i++) {  
  4.     for(int j=0; j<2*max_length; j++) {  
  5.         hough_1d[(i + j * hough_space)] = hough_2d[i][j];  
  6.         if(hough_2d[i][j] > max_hough) {  
  7.             max_hough = hough_2d[i][j];  
  8.         }  
  9.     }  
  10. }  
  11. System.out.println("MAX HOUGH VALUE = " + max_hough);  
  12.   
  13. // transfer back to image pixels space from hough parameter space  
  14. int hough_threshold = (int)(threshold * max_hough);  

从霍夫空间反变换回像素数据空间代码如下:

[java] view plain copy
  1. // transfer back to image pixels space from hough parameter space  
  2. int hough_threshold = (int)(threshold * max_hough);  
  3. for(int row = 0; row < hough_space; row++) {  
  4.     for(int col = 0; col < 2*max_length; col++) {  
  5.         if(hough_2d[row][col] < hough_threshold) // discard it  
  6.             continue;  
  7.         int hough_value = hough_2d[row][col];  
  8.         boolean isLine = true;  
  9.         for(int i=-1; i<2; i++) {  
  10.             for(int j=-1; j<2; j++) {  
  11.                 if(i != 0 || j != 0) {  
  12.                   int yf = row + i;  
  13.                   int xf = col + j;  
  14.                   if(xf < 0continue;  
  15.                   if(xf < 2*max_length) {  
  16.                       if (yf < 0) {  
  17.                           yf += hough_space;  
  18.                       }  
  19.                       if (yf >= hough_space) {  
  20.                           yf -= hough_space;  
  21.                       }  
  22.                       if(hough_2d[yf][xf] <= hough_value) {  
  23.                           continue;  
  24.                       }  
  25.                       isLine = false;  
  26.                       break;  
  27.                   }  
  28.                 }  
  29.             }  
  30.         }  
  31.         if(!isLine) continue;  
  32.           
  33.         // transform back to pixel data now...  
  34.         double dy = Math.sin(row * hough_interval);  
  35.         double dx = Math.cos(row * hough_interval);  
  36.         if ((row <= hough_space / 4) || (row >= 3 * hough_space / 4)) {  
  37.             for (int subrow = 0; subrow < height; ++subrow) {  
  38.               int subcol = (int)((col - max_length - ((subrow - centerY) * dy)) / dx) + centerX;  
  39.               if ((subcol < width) && (subcol >= 0)) {  
  40.                   image_2d[subrow][subcol] = -16776961;  
  41.               }  
  42.             }  
  43.           } else {  
  44.             for (int subcol = 0; subcol < width; ++subcol) {  
  45.               int subrow = (int)((col - max_length - ((subcol - centerX) * dx)) / dy) + centerY;  
  46.               if ((subrow < height) && (subrow >= 0)) {  
  47.                   image_2d[subrow][subcol] = -16776961;  
  48.               }  
  49.             }  
  50.           }  
  51.     }  
  52. }  
霍夫变换源图如下:

霍夫变换以后,在霍夫空间显示如下:(白色表示已经找到直线信号)


最终反变换回到像素空间效果如下:


一个更好的运行监测直线的结果(输入为二值图像):


完整的霍夫变换源代码如下:

[java] view plain copy
  1. package com.gloomyfish.image.transform;  
  2.   
  3. import java.awt.image.BufferedImage;  
  4.   
  5. import com.process.blur.study.AbstractBufferedImageOp;  
  6.   
  7. public class HoughLineFilter extends AbstractBufferedImageOp {  
  8.     public final static double PI_VALUE = Math.PI;  
  9.     private int hough_space = 500;  
  10.     private int[] hough_1d;  
  11.     private int[][] hough_2d;  
  12.     private int width;  
  13.     private int height;  
  14.       
  15.     private float threshold;  
  16.     private float scale;  
  17.     private float offset;  
  18.       
  19.     public HoughLineFilter() {  
  20.         // default hough transform parameters  
  21.         //  scale = 1.0f;  
  22.         //  offset = 0.0f;  
  23.         threshold = 0.5f;  
  24.         scale = 1.0f;  
  25.         offset = 0.0f;  
  26.     }  
  27.       
  28.     public void setHoughSpace(int space) {  
  29.         this.hough_space = space;  
  30.     }  
  31.       
  32.     public float getThreshold() {  
  33.         return threshold;  
  34.     }  
  35.   
  36.     public void setThreshold(float threshold) {  
  37.         this.threshold = threshold;  
  38.     }  
  39.   
  40.     public float getScale() {  
  41.         return scale;  
  42.     }  
  43.   
  44.     public void setScale(float scale) {  
  45.         this.scale = scale;  
  46.     }  
  47.   
  48.     public float getOffset() {  
  49.         return offset;  
  50.     }  
  51.   
  52.     public void setOffset(float offset) {  
  53.         this.offset = offset;  
  54.     }  
  55.   
  56.     @Override  
  57.     public BufferedImage filter(BufferedImage src, BufferedImage dest) {  
  58.         width = src.getWidth();  
  59.         height = src.getHeight();  
  60.   
  61.         if ( dest == null )  
  62.             dest = createCompatibleDestImage( src, null );  
  63.   
  64.         int[] inPixels = new int[width*height];  
  65.         int[] outPixels = new int[width*height];  
  66.         getRGB( src, 00, width, height, inPixels );  
  67.         houghTransform(inPixels, outPixels);  
  68.         setRGB( dest, 00, width, height, outPixels );  
  69.         return dest;  
  70.     }  
  71.   
  72.     private void houghTransform(int[] inPixels, int[] outPixels) {  
  73.         // prepare for hough transform  
  74.         int centerX = width / 2;  
  75.         int centerY = height / 2;  
  76.         double hough_interval = PI_VALUE/(double)hough_space;  
  77.           
  78.         int max = Math.max(width, height);  
  79.         int max_length = (int)(Math.sqrt(2.0D) * max);  
  80.         hough_1d = new int[2 * hough_space * max_length];  
  81.           
  82.         // define temp hough 2D array and initialize the hough 2D  
  83.         hough_2d = new int[hough_space][2*max_length];  
  84.         for(int i=0; i<hough_space; i++) {  
  85.             for(int j=0; j<2*max_length; j++) {  
  86.                 hough_2d[i][j] = 0;  
  87.             }  
  88.         }  
  89.           
  90.         // start hough transform now....  
  91.         int[][] image_2d = convert1Dto2D(inPixels);  
  92.         for (int row = 0; row < height; row++) {  
  93.             for (int col = 0; col < width; col++) {  
  94.                 int p = image_2d[row][col] & 0xff;  
  95.                 if(p == 0continue// which means background color  
  96.                   
  97.                 // since we does not know the theta angle and r value,   
  98.                 // we have to calculate all hough space for each pixel point  
  99.                 // then we got the max possible theta and r pair.  
  100.                 // r = x * cos(theta) + y * sin(theta)  
  101.                 for(int cell=0; cell < hough_space; cell++ ) {  
  102.                     max = (int)((col - centerX) * Math.cos(cell * hough_interval) + (row - centerY) * Math.sin(cell * hough_interval));  
  103.                     max += max_length; // start from zero, not (-max_length)  
  104.                     if (max < 0 || (max >= 2 * max_length)) {// make sure r did not out of scope[0, 2*max_lenght]  
  105.                         continue;  
  106.                     }  
  107.                     hough_2d[cell][max] +=1;  
  108.                 }  
  109.             }  
  110.         }  
  111.           
  112.         // find the max hough value  
  113.         int max_hough = 0;  
  114.         for(int i=0; i<hough_space; i++) {  
  115.             for(int j=0; j<2*max_length; j++) {  
  116.                 hough_1d[(i + j * hough_space)] = hough_2d[i][j];  
  117.                 if(hough_2d[i][j] > max_hough) {  
  118.                     max_hough = hough_2d[i][j];  
  119.                 }  
  120.             }  
  121.         }  
  122.         System.out.println("MAX HOUGH VALUE = " + max_hough);  
  123.           
  124.         // transfer back to image pixels space from hough parameter space  
  125.         int hough_threshold = (int)(threshold * max_hough);  
  126.         for(int row = 0; row < hough_space; row++) {  
  127.             for(int col = 0; col < 2*max_length; col++) {  
  128.                 if(hough_2d[row][col] < hough_threshold) // discard it  
  129.                     continue;  
  130.                 int hough_value = hough_2d[row][col];  
  131.                 boolean isLine = true;  
  132.                 for(int i=-1; i<2; i++) {  
  133.                     for(int j=-1; j<2; j++) {  
  134.                         if(i != 0 || j != 0) {  
  135.                           int yf = row + i;  
  136.                           int xf = col + j;  
  137.                           if(xf < 0continue;  
  138.                           if(xf < 2*max_length) {  
  139.                               if (yf < 0) {  
  140.                                   yf += hough_space;  
  141.                               }  
  142.                               if (yf >= hough_space) {  
  143.                                   yf -= hough_space;  
  144.                               }  
  145.                               if(hough_2d[yf][xf] <= hough_value) {  
  146.                                   continue;  
  147.                               }  
  148.                               isLine = false;  
  149.                               break;  
  150.                           }  
  151.                         }  
  152.                     }  
  153.                 }  
  154.                 if(!isLine) continue;  
  155.                   
  156.                 // transform back to pixel data now...  
  157.                 double dy = Math.sin(row * hough_interval);  
  158.                 double dx = Math.cos(row * hough_interval);  
  159.                 if ((row <= hough_space / 4) || (row >= 3 * hough_space / 4)) {  
  160.                     for (int subrow = 0; subrow < height; ++subrow) {  
  161.                       int subcol = (int)((col - max_length - ((subrow - centerY) * dy)) / dx) + centerX;  
  162.                       if ((subcol < width) && (subcol >= 0)) {  
  163.                           image_2d[subrow][subcol] = -16776961;  
  164.                       }  
  165.                     }  
  166.                   } else {  
  167.                     for (int subcol = 0; subcol < width; ++subcol) {  
  168.                       int subrow = (int)((col - max_length - ((subcol - centerX) * dx)) / dy) + centerY;  
  169.                       if ((subrow < height) && (subrow >= 0)) {  
  170.                           image_2d[subrow][subcol] = -16776961;  
  171.                       }  
  172.                     }  
  173.                   }  
  174.             }  
  175.         }  
  176.           
  177.         // convert to hough 1D and return result  
  178.         for (int i = 0; i < this.hough_1d.length; i++)  
  179.         {  
  180.           int value = clamp((int)(scale * this.hough_1d[i] + offset)); // scale always equals 1  
  181.           this.hough_1d[i] = (0xFF000000 | value + (value << 16) + (value << 8));  
  182.         }  
  183.           
  184.         // convert to image 1D and return  
  185.         for (int row = 0; row < height; row++) {  
  186.             for (int col = 0; col < width; col++) {  
  187.                 outPixels[(col + row * width)] = image_2d[row][col];  
  188.             }  
  189.         }  
  190.     }  
  191.       
  192.     public BufferedImage getHoughImage() {  
  193.         BufferedImage houghImage = new BufferedImage(hough_2d[0].length, hough_space, BufferedImage.TYPE_4BYTE_ABGR);  
  194.         setRGB(houghImage, 00, hough_2d[0].length, hough_space, hough_1d);  
  195.         return houghImage;  
  196.     }  
  197.       
  198.     public static int clamp(int value) {  
  199.           if (value < 0)  
  200.               value = 0;  
  201.           else if (value > 255) {  
  202.               value = 255;  
  203.           }  
  204.           return value;  
  205.     }  
  206.       
  207.     private int[][] convert1Dto2D(int[] pixels) {  
  208.         int[][] image_2d = new int[height][width];  
  209.         int index = 0;  
  210.         for(int row = 0; row < height; row++) {  
  211.             for(int col = 0; col < width; col++) {  
  212.                 index = row * width + col;  
  213.                 image_2d[row][col] = pixels[index];  
  214.             }  
  215.         }  
  216.         return image_2d;  
  217.     }  
  218.   
  219. }  
转载文章请务必注明出自本博客!!
2018-09-11 11:00:34 qq_18234121 阅读数 449

原理介绍

霍夫变换在检测各种形状的的技术中非常流行,如果你要检测的形状可以用数学表达式写出,你就可以是使用霍夫变换检测它。及时要检测的形状存在一点破坏或者扭曲也可以使用。我们下面就看看如何使用霍夫变换检测直线。

一条直线可以用数学表达式y = mx + c 或者 = x cos θ + y sinθ 表示。ρ是从原点到直线的垂直距离,θ 是直线的垂线与横轴顺时针方向的夹角(如果你使用的坐标系不同方向也可能不同,我是按OpenCV 使用的坐标系描述的)。如下图所示:

                                                                         

所以如果一条线在原点下方经过,θ的值就应该大于0,角度小于180。但是如果从原点上方经过的话,角度不是大于180,也是小于180,但ρ 的值小于0。垂直的线角度为0 度,水平线的角度为90 度。

       让我们来看看霍夫变换是如何工作的。每一条直线都可以用(ρ; θ) 表示。所以首先创建一个2D 数组(累加器),初始化累加器,所有的值都为0。行表示ρ,列表示θ。这个数组的大小决定了最后结果的准确性。如果你希望角度精确到1 度,你就需要180 列。对于ρ,最大值为图片对角线的距离。所以如果精确度要达到一个像素的级别,行数就应该与图像对角线的距离相等。

        想象一下我们有一个大小为100x100 的直线位于图像的中央。取直线上的第一个点,我们知道此处的(x,y)值。把x 和y 带入上边的方程组,然后遍历θ 的取值:0,1,2,3,...,180。分别求出与其对应的 的值,这样我们就得到一系列(ρ; θ) 的数值对,如果这个数值对在累加器中也存在相应的位置,就在这个位置上加1。所以现在累加器中的(50,90)=1。(一个点可能存在与多条直线中,所以对于直线上的每一个点可能是累加器中的多个值同时加1)。

举例子 :                       

 

编程思路解析:

1.      读取一幅带处理二值图像,最好背景为黑色。

2.      取得源像素数据

3.      根据直线的霍夫变换公式完成霍夫变换,预览霍夫空间结果

4.       寻找最大霍夫值,设置阈值,反变换到图像RGB值空间(程序难点之一)

5.      越界处理,显示霍夫变换处理以后的图像

2017-05-31 19:40:02 coming_is_winter 阅读数 1166

霍夫变换之简单梳理

一、霍夫变换

  霍夫变换(Hough Transform) 是图像处理中从图像中识别几何形状的基本方法之一,应用很广泛,也有很多改进算法。主要用来从图像中分离出具有某种相同特征的几何形状(如,直线,圆等)。最基本的霍夫变换是从黑白图像中检测直线(线段)。以上为百度百科内容。
  霍夫变换另一个思路的理解是把一个空间内难以解决不好解决的问题转移到对应的其他空间寻求解决办法。现在应用到直线检测与圆的检测中。
       先不涉及霍夫变换,先按普通的思路分析,怎样在一幅图片中找到存在其中的直线并把其画出来呢?其实对于人来讲比较简单,人眼搜索图片中所有区域,根据我们脑中直线的概念去找图片中对应的点的集合就对了。但是计算机不能这么做,我们看到的色彩绚烂的图片在计算机的理解中只是数量的矩阵,它能不能找到一条直线取决于根据人的参数设置找出对应的点的集合,而其自身没有对于直线的准确理解。

二、霍夫直线

       在笛卡尔x,y坐标系下,已知一系列离散点,怎样找出一张直线呢?若下图所示:
        
图1

一般思路,假设离散点有n个,随机挑选出两个点c1(x1,y1),c2(x2,y2)就可以确定一条直线,直线方程为kx+y=b,n个点最后可以确定(n-1)!个方程,统计方程的斜率与截距,两个参数都一致的表示离散点存在于一条直线上,这也是一种方法,计算量是多少呢?(n-1)!的计算量就很大了,最后斜率与截距还要两两比较,所以比较繁琐。
       霍夫变换把xy坐标系下的方程转换为kb空间,把x,y当成常数,而k,b为变量,方程变为:b+xk=y,在xy空间的经过一个特定点的所有直线在k,b坐标系下就是一条直线(可以联系一下降维的概念,复杂问题简单化,霍夫变换的工作),举个例子:设特定点ct=(3,4),在xy空间中由于k,b的取值不限,,所以经过特征点的直线集合为一个面。而在k,b空间,把ct带入b+xk=y后方程为b+3k=4,映射为一条直线,如下图所示:


      

      图2 左图为xy坐标系进过特定点ct的所有直线,未画完整      右图为所有直线在kb坐标系的投影,为一条直线


图3 左图为xy坐标系进过特定点1,2的所有直线,未画完整      右图为所有直线在kb坐标系的投影,为两条条直线

       看图2可以明白在xy坐标系下经过一个特征点的所有直线为一个面,映射到k,b空间为一条直线,看图3两个特定点映射到k,b空间为两条直线,两条直线相交确定一个点,这个交点(kt,bt)为在x,y的坐标系下表示经过两个特定点的一条直线(方程为kx+y=b)的kt,bt值。霍夫变换中还涉及到一个叠加原理,在这里表示为经过这个交点的直线越多,说明在xy坐标系下用kt,bt做参数的直线经过的点越多,这条直线越容易被检测出来。(以上图形为了直观展示,画图准确性不足)。现在我们回到计算量的问题上,图像上xy坐标系下的一个点映射到kb坐标系下画一条直线,计算一次,所以n个点对应着n次计算,计算量大幅减少,,霍夫变换的优势体现出来。
        但由xy空间到kb空间有一个问题,看方程:kx+y=b,特定点确定后,当k=0时,b=y,当b=0时,k=y/x,通过这两个点 就可以把直线画出来了,特殊情况是x=0时,也就是有点在y轴上时,k=y/x除数为0,k确定不了,方程也确定不了了。
        除了k,b空间,还有其他的空间吗?

图4
  xy坐标系还可以映射到rθ坐标系,如图4左上图所示:y=(-cosθ/sinθ)x+(r/sinθ),变换一下r=xcosθ+ysinθ。经过上边xy与kb空间变换我们得到的经验在这顺套,xy坐标系下的一条直线对应着rθ坐标系下的一个点,xy空间经过特定点的所有直线映射到到rθ空间为一条曲线(图4右上),多个特征点的所有直线映射到rθ空间为对应的曲线,若有交点,可以确定xy的一条直线(图4右下),同一交点上的曲线越多,说明xy空间一条直线上的已知点越多,直线越容易检测。同样计算量还是n级别的。解决了y轴点不能空间变换的问题。

三、霍夫圆

  大体原理相似,圆在xy空间方程,(x-a)^2+(y-b)^2=r^2,映射到abr三维空间,方程为:(a-x)^2+(b-y)^2=r^2,设特定点为ct(xt,yt),则经过ct的所有圆映射到abr空间为r=sqrt((a-xt)^2+(b-yt)^2)。为一个圆锥面。如下图所示(特定点为(30,30)):


图5
  两个特征点为两个圆锥面相交为一抛物线,三个圆锥面以上相交为一点,回到霍夫变换的叠加问题。
  参考文献:

  浅墨_毛星云:http://blog.csdn.net/poem_qianmo/article/details/26977557/。【OpenCV入门教程之十四】OpenCV霍夫变换:霍夫线变换,霍夫圆变换合辑

        

2018-11-08 20:33:19 Godsolve 阅读数 355

霍夫变换是一种特征检测(feature extraction),被广泛应用在图像分析(image analysis)、电脑视觉(computer vision)以及数位影像处理(digital image processing)。
霍夫变换是用来辨别找出物件中的特征,例如:线条。他的算法流程大致如下,给定一个物件、要辨别的形状的种类,算法会在参数空间(parameter space)中执行投票来决定物体的形状,而这是由累加空间(accumulator space)里的局部最大值(local maximum)来决定。

而本次实验我要做的就是使用霍夫变换进行图像圆的检测。

霍夫变换的过程可以分为以下几步:

  1. 对输入图像进行边缘检测,获取边界点,即前景点。
  2. 假如图像中存在圆形,那么其轮廓必定属于前景点(此时请忽略边缘提取的准确性)。
  3. 同霍夫变换检测直线一样,将圆形的一般性方程换一种方式表示,进行坐标变换。由x-y坐标系转换到a-b坐标系。写成如下形式(a-x)²+(b-y)²=r²。那么x-y坐标系中圆形边界上的一点对应到a-b坐标系中即为一个圆。
  4. 那x-y坐标系中一个圆形边界上有很多个点,对应到a-b坐标系中就会有很多个圆。由于原图像中这些点都在同一个圆形上,那么转换后a,b必定也满足a-b坐标系下的所有圆形的方程式。直观表现为这许多点对应的圆都会相交于一个点,那么这个交点就可能是圆心(a, b)。
  5. 统计局部交点处圆的个数,取每一个局部最大值,就可以获得原图像中对应的圆形的圆心坐标(a,b)。一旦在某一个r下面检测到圆,那么r的值也就随之确定。

在实际实现中,只需要注意输入的是灰度图,以及霍夫变换中的参数问题,就可以较好地实现图像中圆的检测。

结果如下图:
在这里插入图片描述

不过我的实现中还存在一些问题,例如图像如果是不完全连通的,有时候就不能识别。
在这里插入图片描述
在这张图例,第二行第二个圆就没有识别出来,而且第二行第一个图识别出了两个圆。

此外,对于边缘粗细不一样的图形,我的实现中会出现识别出n多个圆的情况。
在这里插入图片描述
可能是因为对于不同像素的位置,而识别出了不同的圆。


同时也欢迎各位关注我的微信公众号 南木的下午茶

在这里插入图片描述


代码自取:

#include "stdafx.h"
#include "opencv2/core/core.hpp"
#include "opencv2/highgui/highgui.hpp"
#include "opencv2/imgproc/imgproc.hpp"
#include <opencv2/opencv.hpp>
#include <iostream>

using namespace std;
using namespace cv;

int main()
{
	//【1】载入原始图和Mat变量定义   
	Mat srcImage = imread("E:/C++/CVE7/1.jpg");  //工程目录下应该有一张名为1.jpg的素材图
	Mat midImage, dstImage;//临时变量和目标图的定义

						   //【2】显示原始图
	imshow("【原始图】", srcImage);

	//【3】转为灰度图,进行图像平滑
	cvtColor(srcImage, midImage, CV_BGR2GRAY);//转化边缘检测后的图为灰度图
	GaussianBlur(midImage, midImage, Size(9, 9), 2, 2);

	//【4】进行霍夫圆变换
	vector<Vec3f> circles;
	HoughCircles(midImage, circles, CV_HOUGH_GRADIENT, 1.5, 10, 200, 100, 0, 0);

	//【5】依次在图中绘制出圆
	for (size_t i = 0; i < circles.size(); i++)
	{
		Point center(cvRound(circles[i][0]), cvRound(circles[i][1]));
		int radius = cvRound(circles[i][2]);
		//绘制圆心
		circle(srcImage, center, 3, Scalar(0, 255, 0), -1, 8, 0);
		//绘制圆轮廓
		circle(srcImage, center, radius, Scalar(155, 50, 255), 3, 8, 0);
	}

	//【6】显示效果图  
	imshow("【效果图】", srcImage);

	waitKey(0);

	return 0;
}