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

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

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


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


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


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



霍夫变换算法思想:


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


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


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


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


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



1341642751_7461.png

然而在实现的图像处理领域,图像的像素坐标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]有如下霍夫参数定义:

 // prepare for hough transform
 int centerX = width / 2;
 int centerY = height / 2;
 double hough_interval = PI_VALUE/(double)hough_space;
      
 int max = Math.max(width, height);
 int max_length = (int)(Math.sqrt(2.0D) * max);
 hough_1d = new int[2 * hough_space * max_length];

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

// start hough transform now....
int[][] image_2d = convert1Dto2D(inPixels);
for (int row = 0; row < height; row++) {
  for (int col = 0; col < width; col++) {
      int p = image_2d[row][col] & 0xff;
      if(p == 0) continue; // which means background color
      
      // since we does not know the theta angle and r value, 
      // we have to calculate all hough space for each pixel point
      // then we got the max possible theta and r pair.
      // r = x * cos(theta) + y * sin(theta)
      for(int cell=0; cell < hough_space; cell++ ) {
        max = (int)((col - centerX) * Math.cos(cell * hough_interval) + (row - centerY) * Math.sin(cell * hough_interval));
        max += max_length; // start from zero, not (-max_length)
        if (max < 0 || (max >= 2 * max_length)) {// make sure r did not out of scope[0, 2*max_lenght]
                continue;
            }
        hough_2d[cell][max] +=1;
      }
    }
}


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

// find the max hough value
int max_hough = 0;
for(int i=0; i<hough_space; i++) {
  for(int j=0; j<2*max_length; j++) {
    hough_1d[(i + j * hough_space)] = hough_2d[i][j];
    if(hough_2d[i][j] > max_hough) {
      max_hough = hough_2d[i][j];
    }
  }
}
System.out.println("MAX HOUGH VALUE = " + max_hough);
 
// transfer back to image pixels space from hough parameter space
int hough_threshold = (int)(threshold * max_hough);

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

      // transfer back to image pixels space from hough parameter space
      int hough_threshold = (int)(threshold * max_hough);
      for(int row = 0; row < hough_space; row++) {
        for(int col = 0; col < 2*max_length; col++) {
          if(hough_2d[row][col] < hough_threshold) // discard it
            continue;
          int hough_value = hough_2d[row][col];
          boolean isLine = true;
          for(int i=-1; i<2; i++) {
            for(int j=-1; j<2; j++) {
              if(i != 0 || j != 0) {
                      int yf = row + i;
                      int xf = col + j;
                      if(xf < 0) continue;
                      if(xf < 2*max_length) {
                        if (yf < 0) {
                          yf += hough_space;
                        }
                          if (yf >= hough_space) {
                            yf -= hough_space;
                          }
                          if(hough_2d[yf][xf] <= hough_value) {
                            continue;
                          }
                          isLine = false;
                          break;
                      }
              }
            }
          }
          if(!isLine) continue;
          
          // transform back to pixel data now...
              double dy = Math.sin(row * hough_interval);
              double dx = Math.cos(row * hough_interval);
              if ((row <= hough_space / 4) || (row >= 3 * hough_space / 4)) {
                  for (int subrow = 0; subrow < height; ++subrow) {
                    int subcol = (int)((col - max_length - ((subrow - centerY) * dy)) / dx) + centerX;
                    if ((subcol < width) && (subcol >= 0)) {
                      image_2d[subrow][subcol] = -16776961;
                    }
                  }
                } else {
                  for (int subcol = 0; subcol < width; ++subcol) {
                    int subrow = (int)((col - max_length - ((subcol - centerX) * dx)) / dy) + centerY;
                    if ((subrow < height) && (subrow >= 0)) {
                      image_2d[subrow][subcol] = -16776961;
                    }
                  }
                }
        }
      }

霍夫变换源图如下:

1341643177_4426.png

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


1341643279_6500.png

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

1341643451_7244.png

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

1341643681_8786.png

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

package com.gloomyfish.image.transform;
 
import java.awt.image.BufferedImage;
 
import com.process.blur.study.AbstractBufferedImageOp;
 
public class HoughLineFilter extends AbstractBufferedImageOp {
  public final static double PI_VALUE = Math.PI;
  private int hough_space = 500;
  private int[] hough_1d;
  private int[][] hough_2d;
  private int width;
  private int height;
  
  private float threshold;
  private float scale;
  private float offset;
  
  public HoughLineFilter() {
    // default hough transform parameters
    //  scale = 1.0f;
    //  offset = 0.0f;
    threshold = 0.5f;
    scale = 1.0f;
    offset = 0.0f;
  }
  
  public void setHoughSpace(int space) {
    this.hough_space = space;
  }
  
  public float getThreshold() {
    return threshold;
  }
 
  public void setThreshold(float threshold) {
    this.threshold = threshold;
  }
 
  public float getScale() {
    return scale;
  }
 
  public void setScale(float scale) {
    this.scale = scale;
  }
 
  public float getOffset() {
    return offset;
  }
 
  public void setOffset(float offset) {
    this.offset = offset;
  }
 
  @Override
  public BufferedImage filter(BufferedImage src, BufferedImage dest) {
    width = src.getWidth();
        height = src.getHeight();
 
        if ( dest == null )
            dest = createCompatibleDestImage( src, null );
 
        int[] inPixels = new int[width*height];
        int[] outPixels = new int[width*height];
        getRGB( src, 0, 0, width, height, inPixels );
        houghTransform(inPixels, outPixels);
        setRGB( dest, 0, 0, width, height, outPixels );
        return dest;
  }
 
  private void houghTransform(int[] inPixels, int[] outPixels) {
        // prepare for hough transform
      int centerX = width / 2;
      int centerY = height / 2;
      double hough_interval = PI_VALUE/(double)hough_space;
      
      int max = Math.max(width, height);
      int max_length = (int)(Math.sqrt(2.0D) * max);
      hough_1d = new int[2 * hough_space * max_length];
      
      // define temp hough 2D array and initialize the hough 2D
      hough_2d = new int[hough_space][2*max_length];
      for(int i=0; i<hough_space; i++) {
        for(int j=0; j<2*max_length; j++) {
          hough_2d[i][j] = 0;
        }
      }
      
      // start hough transform now....
      int[][] image_2d = convert1Dto2D(inPixels);
      for (int row = 0; row < height; row++) {
        for (int col = 0; col < width; col++) {
            int p = image_2d[row][col] & 0xff;
            if(p == 0) continue; // which means background color
            
            // since we does not know the theta angle and r value, 
            // we have to calculate all hough space for each pixel point
            // then we got the max possible theta and r pair.
            // r = x * cos(theta) + y * sin(theta)
            for(int cell=0; cell < hough_space; cell++ ) {
              max = (int)((col - centerX) * Math.cos(cell * hough_interval) + (row - centerY) * Math.sin(cell * hough_interval));
              max += max_length; // start from zero, not (-max_length)
              if (max < 0 || (max >= 2 * max_length)) {// make sure r did not out of scope[0, 2*max_lenght]
                      continue;
                  }
              hough_2d[cell][max] +=1;
            }
          }
      }
      
    // find the max hough value
    int max_hough = 0;
    for(int i=0; i<hough_space; i++) {
      for(int j=0; j<2*max_length; j++) {
        hough_1d[(i + j * hough_space)] = hough_2d[i][j];
        if(hough_2d[i][j] > max_hough) {
          max_hough = hough_2d[i][j];
        }
      }
    }
    System.out.println("MAX HOUGH VALUE = " + max_hough);
    
    // transfer back to image pixels space from hough parameter space
    int hough_threshold = (int)(threshold * max_hough);
      for(int row = 0; row < hough_space; row++) {
        for(int col = 0; col < 2*max_length; col++) {
          if(hough_2d[row][col] < hough_threshold) // discard it
            continue;
          int hough_value = hough_2d[row][col];
          boolean isLine = true;
          for(int i=-1; i<2; i++) {
            for(int j=-1; j<2; j++) {
              if(i != 0 || j != 0) {
                      int yf = row + i;
                      int xf = col + j;
                      if(xf < 0) continue;
                      if(xf < 2*max_length) {
                        if (yf < 0) {
                          yf += hough_space;
                        }
                          if (yf >= hough_space) {
                            yf -= hough_space;
                          }
                          if(hough_2d[yf][xf] <= hough_value) {
                            continue;
                          }
                          isLine = false;
                          break;
                      }
              }
            }
          }
          if(!isLine) continue;
          
          // transform back to pixel data now...
              double dy = Math.sin(row * hough_interval);
              double dx = Math.cos(row * hough_interval);
              if ((row <= hough_space / 4) || (row >= 3 * hough_space / 4)) {
                  for (int subrow = 0; subrow < height; ++subrow) {
                    int subcol = (int)((col - max_length - ((subrow - centerY) * dy)) / dx) + centerX;
                    if ((subcol < width) && (subcol >= 0)) {
                      image_2d[subrow][subcol] = -16776961;
                    }
                  }
                } else {
                  for (int subcol = 0; subcol < width; ++subcol) {
                    int subrow = (int)((col - max_length - ((subcol - centerX) * dx)) / dy) + centerY;
                    if ((subrow < height) && (subrow >= 0)) {
                      image_2d[subrow][subcol] = -16776961;
                    }
                  }
                }
        }
      }
      
      // convert to hough 1D and return result
      for (int i = 0; i < this.hough_1d.length; i++)
      {
        int value = clamp((int)(scale * this.hough_1d[i] + offset)); // scale always equals 1
        this.hough_1d[i] = (0xFF000000 | value + (value << 16) + (value << 8));
      }
      
      // convert to image 1D and return
      for (int row = 0; row < height; row++) {
        for (int col = 0; col < width; col++) {
            outPixels[(col + row * width)] = image_2d[row][col];
          }
      }
  }
  
  public BufferedImage getHoughImage() {
    BufferedImage houghImage = new BufferedImage(hough_2d[0].length, hough_space, BufferedImage.TYPE_4BYTE_ABGR);
    setRGB(houghImage, 0, 0, hough_2d[0].length, hough_space, hough_1d);
    return houghImage;
  }
  
  public static int clamp(int value) {
        if (value < 0)
          value = 0;
        else if (value > 255) {
          value = 255;
        }
        return value;
  }
  
  private int[][] convert1Dto2D(int[] pixels) {
    int[][] image_2d = new int[height][width];
    int index = 0;
    for(int row = 0; row < height; row++) {
      for(int col = 0; col < width; col++) {
        index = row * width + col;
        image_2d[row][col] = pixels[index];
      }
    }
    return image_2d;
  }
 
}

转载文章请务必注明出自本博客!!

学习图像处理,点击视频教程《数字图像处理-基础入门》

相关文章
|
5天前
|
机器学习/深度学习 人工智能 算法
计算机视觉:目标检测算法综述
【7月更文挑战第13天】目标检测作为计算机视觉领域的重要研究方向,近年来在深度学习技术的推动下取得了显著进展。然而,面对复杂多变的实际应用场景,仍需不断研究和探索更加高效、鲁棒的目标检测算法。随着技术的不断发展和应用场景的不断拓展,相信目标检测算法将在更多领域发挥重要作用。
|
8天前
|
机器学习/深度学习 数据采集 算法
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
Python实现Prophet时间序列数据建模与异常值检测(Prophet算法)项目实战
|
8天前
|
机器学习/深度学习 算法 计算机视觉
|
10天前
|
机器学习/深度学习 运维 算法
Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
Python基于局部离群因子LOF算法(LocalOutlierFactor)实现信用卡数据异常值检测项目实战
|
10天前
|
机器学习/深度学习 数据采集 运维
Python基于孤立森林算法(IsolationForest)实现数据异常值检测项目实战
Python基于孤立森林算法(IsolationForest)实现数据异常值检测项目实战
|
23小时前
|
传感器 算法
基于无线传感器网络的MCKP-MMF算法matlab仿真
MCKP-MMF算法是一种启发式流量估计方法,用于寻找无线传感器网络的局部最优解。它从最小配置开始,逐步优化部分解,调整访问点的状态。算法处理访问点的动态影响半径,根据带宽需求调整,以避免拥塞。在MATLAB 2022a中进行了仿真,显示了访问点半径请求变化和代价函数随时间的演变。算法分两阶段:慢启动阶段识别瓶颈并重设半径,随后进入周期性调整阶段,追求最大最小公平性。
基于无线传感器网络的MCKP-MMF算法matlab仿真
|
3天前
|
机器学习/深度学习 算法 数据挖掘
基于改进K-means的网络数据聚类算法matlab仿真
**摘要:** K-means聚类算法分析,利用MATLAB2022a进行实现。算法基于最小化误差平方和,优点在于简单快速,适合大数据集,但易受初始值影响。文中探讨了该依赖性并通过实验展示了随机初始值对结果的敏感性。针对传统算法的局限,提出改进版解决孤点影响和K值选择问题。代码中遍历不同K值,计算距离代价,寻找最优聚类数。最终应用改进后的K-means进行聚类分析。
|
5天前
|
算法 数据安全/隐私保护
基于GA遗传优化算法的Okumura-Hata信道参数估计算法matlab仿真
在MATLAB 2022a中应用遗传算法进行无线通信优化,无水印仿真展示了算法性能。遗传算法源于Holland的理论,用于全局优化,常见于参数估计,如Okumura-Hata模型的传播损耗参数。该模型适用于150 MHz至1500 MHz的频段。算法流程包括选择、交叉、变异等步骤。MATLAB代码执行迭代,计算目标值,更新种群,并计算均方根误差(RMSE)以评估拟合质量。最终结果比较了优化前后的RMSE并显示了SNR估计值。
20 7
|
2天前
|
算法
基于粒子群优化的图像融合算法matlab仿真
这是一个基于粒子群优化(PSO)的图像融合算法,旨在将彩色模糊图像与清晰灰度图像融合成彩色清晰图像。在MATLAB2022a中测试,算法通过PSO求解最优融合权值参数,经过多次迭代更新粒子速度和位置,以优化融合效果。核心代码展示了PSO的迭代过程及融合策略。最终,使用加权平均法融合图像,其中权重由PSO计算得出。该算法体现了PSO在图像融合领域的高效性和融合质量。
|
2天前
|
传感器 算法 数据安全/隐私保护
基于鲸鱼优化的DSN弱栅栏覆盖算法matlab仿真
```markdown 探索MATLAB2022a中WOA与DSN弱栅栏覆盖的创新融合,模拟鲸鱼捕食策略解决传感器部署问题。算法结合“搜索”、“包围”、“泡沫网”策略,优化节点位置以最大化复杂环境下的区域覆盖。目标函数涉及能量效率、网络寿命、激活节点数、通信质量及覆盖率。覆盖评估基于覆盖半径比例,旨在最小化未覆盖区域。 ```