霍夫直线检测的论文

霍夫变换（Hough Transform）是图像处理领域中，从图像中识别几何形状的基本方法之一。主要识别具有某些相同特征的几何形状，例如直线，圆形，本篇博客的目标就是从黑白图像中识别出直线。

翻阅霍夫直线变换的原理时候，橡皮擦觉得原理部分需要先略过，否则很容易在这个地方陷进去，但是问题来了，这个原理略过了，直接应用函数，里面有些参数竟然看不懂。例如极坐标，角度扫描范围，这种函数就属于绕不过去的知识点了，所以本文转移方向，死磕原理，下面的博文将语无伦次的为你展示如何学习原理知识。

因为数学知识的贫乏，所以在学习阶段会涉及到很多基础概念的学习，一起来吧。

首先找到相对官方的资料，打开该 地址

下面是一个数学小白对原理的学习经验。

教材说：众所周知，一条直线在图像二维空间可由两个变量表示。

抱歉，小白还真不知道……即使学习过，这些年也早已经还给老师了。

一开始难道要学习笛卡尔坐标系，不，你低估小白的能力了，我第一个查询的是 θ 读作 西塔 ，是一个希腊字母。

什么是笛卡尔坐标系？

这个比较简单，直角坐标系。

斜率和截距

斜率，亦称“角系数”，表示一条直线相对于横坐标轴的倾斜程度。

一条直线与某平面直角坐标系横坐标轴正半轴方向的夹角的正切值即该直线相对于该坐标系的斜率。

如果直线与 x 轴互相垂直，直角的正切直无穷大，故此直线不存在斜率。 对于一次函数 y=kx+b ， k 就是该函数图像的斜率。

在学习的时候，也学到如下内容：

截距：对 x 的截距就是 y=0 时， x 的值，对 y 的截距就是 x=0 时， y 的值， 截距就是直线与坐标轴的交点的横（纵）坐标。 x 截距为 a ， y 截距 b ，截距式就是： x/a+y/b=1（a≠0且b≠0） 。

斜率：对于任意函数上任意一点，其斜率等于其切线与 x 轴正方向所成的角，即 k=tanα 。 ax+by+c=0中，k=-a/b 。

什么是极坐标系？

关于极坐标系，打开 百度百科 学习一下即可。

重点学到下面这个结论就行：

找资料的时候，发现一个解释的比较清楚的 博客 ，后续可以继续学习使用。

继续阅读资料，看到如下所示的图，这个图也出现在了很多解释原理的博客里面，但是图下面写了一句话

在这里直接蒙掉了，怎么就表示成极坐标系了？上面这个公式依旧是笛卡尔坐标系表示直线的方式呀，只是把 k 和 b 的值给替换掉了。

为何是这样的，具体原因可以参照下图。

继续寻找关于霍夫变换的资料，找到一个新的概念 霍夫空间 。

在笛卡尔坐标系中，一条直线可以用公式 表示，其中 k 和 b 是参数，表示的是斜率和截距。

接下来将方程改写为 ，这时就建立了一个基于 k - b 的笛卡尔坐标系。

此时这个新的方程在 k - b 坐标系也有一个新的直线。

你可以在纸上画出这两个方程对应的线和点，如下图所示即可。

新的 k - b 坐标系就叫做霍夫空间，这时得到一个结论，图像空间 x - y 中的点 对应了 霍夫空间 k - b 中的一条直线 ，即图像空间的点与霍夫空间的直线发生了对应关系。

如果在图像空间 x - y 中在增加一个点 ，那相应的该点在霍夫空间也会产生相同的点与线的对应关系，并且 A 点与 B 点产生的直线会在霍夫空间相交于一个点。而这个点的坐标值 就是直线 AB 的参数。

如果到这里你掌握了，这个性质就为我们解决直线检测提供了方法，只需要把图像空间的直线对应到霍夫空间的点，然后统计交点就可以达到目的，例如图像空间中有 3 条直线，那对应到霍夫空间就会有 3 个峰值点。

遍历图像空间中的所有点，将点转换到霍夫空间，形成大量直线，然后统计出直线交会的点，每个点的坐标都是图像空间直线方程参数，这时就能得到图像空间的直线了。

上述的内容没有问题，但是存在一种情况是，当直线趋近于垂直时，斜率 k 会趋近于无穷大，这时就没有办法转换了，解决办法是使用法线来表示直线。

上文提及的斜截式如下：

通过第二个公式，可以得到下述公式：

此时，我们可以带入一些数值进行转换。

图像空间有如下的几个点：

转换后的函数，都可以在霍夫空间 θ - ρ （横坐标是 θ ，纵坐标是 ρ ）进行表示。

原理这时就比较清晰了：

除了一些数学知识以外，经典的博客我们也有必要记录一下，方便后面学习的时候，进行复盘。

本部分用于记录本文中提及的相关数学原理，后续还要逐步埋坑。

今天涉及了一点点数学知识，能力限制，大家一起学习，有错误的地方，可以在评论区指出，不胜感激。

希望今天的 1 个小时（今天内容有点多，不一定可以看完），你有所收获，我们下篇博客见~

相关阅读

技术专栏

逗趣程序员

对于圆检测，许多研究人员已经运用参数分解和/或圆的一些几何性质，搞出了霍夫变换的变体以减少计算的复杂性。Yuen等人在1990年的论文中已经对圆的识别的集中霍夫变换的技术进行了比较研究。以参数分解为基础的方法通常是先检测圆心，然后确定半径。这样做的特点的其中之一是圆上一点的方向向量经过圆心(Davies, 1987a; Illingworth and Kittler, 1987). 叶等人在1992年的论文中用到一个性质：圆上两点的切线平行，那么这两点就是圆的直径的两个端点。上述方法需要有对干扰因素十分敏感的边缘等级线的梯度的信息(Davies, 1987b). 干扰因素对边的方向的作用通常要比对边的位置的作用大。不使用边缘方向信息的几种途径包括：陈和Siu（1990）提出了基于水平和垂直弦的中分线的快速椭圆检测法。同样，Ho和陈（1995）提出了一种使用全局几何对称性的快速检测圆的算法，通过水平和垂直对称轴计算出圆心。Sheu等人在1997年的论文中，在整个过程中运用了对称轴的信息来计算所有五个参数。 Goneid等人在1997年的论文中使用一维数组创建了弦的中分线法。Davies（1999）研究了一个用于椭圆的快速精确定位的简单的弦的中垂线法。 Ioannou 等人（1999年）的方法是基于垂径定理。Lei和王（1999）发现了对称轴，继而发现了几对交点是圆心的可选值的正交轴。其缺点是图像中的直线会让对称轴的检测更复杂。

随着人工智能的热度上升，图像识别这一分领域也渐渐被人们所关注。图像识别中最贴近我们生活的可能就是 OCR 技术了。可能很多同学还不知道什么是 OCR。我们先来看下 OCR 的定义：

今天就来简单分析下 OCR 技术的原理，不会涉及具体的算法讲解和推导，毕竟每一个算法都能占很长的篇幅，每一个算法都能重新开一篇来写。

从整体上来说，OCR一般分为两个大步骤：图像处理以及文字识别。

识别文字前，我们要对原始图片进行预处理，以便后续的特征提取和学习。这个过程通常包含：灰度化、二值化、降噪、倾斜矫正、文字切分等子步骤。每一个步骤都涉及了不同的算法。我们以下面这张原始图片为例，进行每个步骤的讲解。

灰度化（gray processing），在RGB模型中，如果R=G=B时，则彩色表示一种灰度颜色，其中R=G=B的值叫灰度值，因此，灰度图像每个像素只需一个字节存放灰度值（又称强度值、亮度值），灰度范围为0-255。说通俗一点，就是将一张彩色图片变为黑白图片。

灰度化一般有分量法、最大值法、平均值法、加权平均法四种方法对彩色图像进行灰度化。

一幅图像包括目标物体、背景还有噪声，要想从多值的数字图像中直接提取出目标物体，最常用的方法就是设定一个阈值T，用T将图像的数据分成两部分：大于T的像素群和小于T的像素群。这是研究灰度变换的最特殊的方法，称为图像的二值化（binaryzation）。

二值化的黑白图片不包含灰色，只有纯白和纯黑两种颜色。

二值化里最重要的就是阈值的选取，一般分为固定阈值和自适应阈值。 比较常用的二值化方法则有：双峰法、P参数法、迭代法和OTSU法等。

现实中的数字图像在数字化和传输过程中常受到成像设备与外部环境噪声干扰等影响，称为含噪图像或噪声图像。减少数字图像中噪声的过程称为图像降噪（Image Denoising）。

图像中噪声的来源有许多种，这些噪声来源于图像采集、传输、压缩等各个方面。噪声的种类也各不相同，比如椒盐噪声，高斯噪声等，针对不同的噪声有不同的处理算法。

在上一步得到的图像中可以看到很多零星的小黑点，这就是图像中的噪声，会极大干扰到我们程序对于图片的切割和识别，因此我们需要降噪处理。降噪在这个阶段非常重要，降噪算法的好坏对特征提取的影响很大。

图像降噪的方法一般有均值滤波器、自适应维纳滤波器、中值滤波器、形态学噪声滤除器、小波去噪等。

对于用户而言，拍照的时候不可能绝对的水平，所以，我们需要通过程序将图像做旋转处理，来找一个认为最可能水平的位置，这样切出来的图，才有可能是最好的一个效果。

倾斜矫正最常用的方法是霍夫变换，其原理是将图片进行膨胀处理，将断续的文字连成一条直线，便于直线检测。计算出直线的角度后就可以利用旋转算法，将倾斜图片矫正到水平位置。

对于一段多行文本来讲，文字切分包含了行切分与字符切分两个步骤， 倾斜矫正 是文字切分的前提。我们将 倾斜矫正 后的文字投影到 Y轴，并将所有值累加，这样就能得到一个在y轴上的直方图。

直方图的谷底就是背景，峰值则是前景（文字）所在的区域。于是我们就将每行文字的位置给识别出来了。

字符切分和行切分类似，只是这次我们要将每行文字投影到 X轴。

但要注意的是，同一行的两个字符往往挨的比较紧，有些时候会出现垂直方向上的重叠，投影的时候将他们认为是一个字符，从而造成切割的时候出错（多出现在英文字符）；也有些时候同一个字符的左右结构在X轴的投影存在一个小间隙，切割的时候误把一个字符切分为两个字符（多出现在中文字符）。所以相较于行切分，字符切分更难。

对于这种情况，我们可以预先设定一个字符宽度的期望值，切出的字符如果投影超出期望值太大，则认为是两个字符；如果远远小于这个期望值，则忽略这个间隙，把间隙左右的“字符”合成一个字符来识别。

预处理完毕后，就到了文字识别的阶段。这个阶段会涉及一些人工智能方面的知识，比较抽象，没法用图片表达，我尽量讲得简单易懂一些。

特征是用来识别文字的关键信息，每个不同的文字都能通过特征来和其他文字进行区分。对于数字和英文字母来说，这个特征提取是比较容易的，总共就 10 + 26 x 2 = 52 个字符，而且都是小字符集。对于汉字来说，特征提取的难度就比较大了，因为首先汉字是大字符集；其次国标中光是最常用的第一级汉字就有3755个；最后汉字结构复杂，形近字多，特征维度就比较大。

在确定了使用何种特征后，还有可能要进行特征降维，这种情况下，如果特征的维数太高，分类器的效率会受到很大的影响，为了提高识别速率，往往就要进行降维，这个过程也很重要，既要降低特征维数，又得使得减少维数后的特征向量还保留了足够的信息量（以区分不同的文字）。

对一个文字图像，提取出特征，丢给分类器，分类器就对其进行分类，告诉你这个特征该识别成哪个文字。分类器的设计就是我们的任务。分类器的设计方法一般有：模板匹配法、判别函数法、神经网络分类法、基于规则推理法等，这里不展开叙述。在进行实际识别前，往往还要对分类器进行训练，这是一个监督学习的过程。成熟的分类器也有很多，有 SVM，CNN 等。

其实就是对于分类器的分类结果进行优化，这一般就要涉及自然语言理解的范畴了。

首先是形近字的处理：举个栗子，“分”和“兮”形近，但是如果遇到“分数”这个词语，就不应该识别为“兮数”，因为“分数”才是一个正常词语。这需要通过语言模型来进行纠正。

其次是对于文字排版的处理：比如一些书籍是分左右两栏的，同一行的左右两栏不属于同一句话，不存在任何语法上的联系。如果按照行切割，就会把左行的末尾和右行的开头连在一起，这是我们不希望看到的，这样的情况需要进行特殊处理。

OCR 的大致原理就是这样。整体上来看，OCR 的步骤繁多，涉及的算法复杂，针对每一个步骤，每一个算法都有许多单独的研究论文，本文无法进行深入探讨。如果从零开始做 OCR，这将是一个浩大的工程。笔者才疏学浅，对于模式识别、机器学习也属于入门阶段，如果有错漏的地方，还请各位斧正。