霍夫变换是怎么发明的？
点击我爱计算机视觉标星，更快获取CVML新技术
本文由纯真学者出神入化编译自：
https://ieeexplore.ieee.org/document/5230799/references#references
讲述霍夫（Hough）变换如何被发明的故事。
Hough变换用于检测数字图像中的直线等几何特征，可能是计算机视觉中使用最广泛的程序之一[1-3]。虽然没有人列出计算机视觉中使用任何特定算法或技术的频率，但我们可以通过注意在Google Scholar搜索术语“Hough变换”中返回超过22,000次引用, 来了解其受欢迎程度。这是好几倍于其他经典计算机视觉算子的引用次数，如Sobel算子[3]或Canny边缘检测器[4]。
这种变换来自哪里？你可能会模糊地回忆起它可以追溯到P.V.C的1962年专利，虽然我怀疑很少有读者真正看过这个专利，其标题页如图1所示。如果你这样做，你可能会惊讶地发现今天使用的变换其实并没有在那里描述。实际上，今天的变换不是一下子就被发明的，而是采取了几个步骤。Hough的初步想法与19世纪末数学中一个不起眼的分支的想法相结合，才产生了我们现在所熟悉的正弦变换。
图 1
以前无人知晓的这一历史说明了有时候将非显而易见的相关想法结合起来有多重要。正说明路易斯巴斯德的观察，“机会有利于准备好的思想”，在20世纪和21世纪仍然像19世纪一样恰当
霍夫的定义
1962年的Hough专利是一个简洁的奇迹，只有五页长，包括数字和索赔。更值得注意的是，没有定义任何变换的代数方程。此外，本发明的大多数公开内容，包括三个图中的两个并不是专用于变换，而是专用于使用诸如差分放大器和锯齿波发生器之类的部件来实现本发明的模拟电路的描述。
图 2
该专利描述变换的唯一图形如图2所示，图2显示了三角形中的共线点如何映射到变换平面中的相交线的三个示例。这些交叉点并非偶然：Hough明显地理解了他的几何结构的理论属性，他指出，“如果一个图形中的一系列点位于一条直线上，那么平面中的相应直线变换就会有一个相交。 “
对于Hough本人来说，如何看待点到线变换的想法是一个谜。他一直在寻求，没有成功。但一天晚上下班回家时，他有一个莫名其妙但真正的“aha！”见解：将零维点映射到一维直线 ，通过增加维度似乎使问题更复杂 ，但实际上导致了一个简单的解决方案，可以使用当时的模拟电子元件[6]实现。
无论这个想法如何产生，Hough的1962年专利清楚地揭示了一个关键思想，它是当今使用的变换的基础：图像平面中的共线点可以通过将它们映射到在变换中相交的几何结构（对于Hough，直线）来识别。但同样清楚的是，Hough所描述的几何变换和现在为计算机视觉界已经使用了几十年的几何变换差别很大。其实，想真正达到目标还需要几个步骤。
罗森菲尔德的定义
1969年，阿兹里尔·罗森菲尔德（Azriel Rosenfeld）发表了他的计算机视觉基础书籍“计算机图像处理”。在几乎是某章节末尾，他提出了一个“有趣的替代方案，利用点线变换检测直线”[7]。他引用了Hough专利，并且据我所知，第一次以（1）给出的形式定义变换代数，其中（xi，yi）是图像平面中的点，x和y是变换平面的轴：
Y=yi*x+xi (1)
他指出，如果一组点（xi，yi），i = 1，...，n是共线的，那么很容易证明变换平面中的相应线将全部通过单个点。他还用括号表示，如果点（xi，yi）位于几乎与x轴平行的直线上，那么这些直线几乎是平行的，因此它们的交点移动到无穷大的位置。也许从Hough的建议 “以正确的角度扫描每张图片两次” 中得到暗示，罗森菲尔德建议通过在（1）中交换xi和yi来克服这个困难。罗森菲尔德提出了另外一项建议。他再次注意到，存在许多共线这一现象将在变换空间中产生高值。
罗森菲尔德是如何发现Hough专利的，现在已经无法确定。众所周知，Hough和罗森菲尔德并不熟悉[6]。罗森菲尔德当然是一位了不起的学者，也许他只是自己找到了这项专利。但无论他如何找到它，我们都可以说罗森菲尔德沿着从霍夫的专利到今天使用的变换的路径迈出了一大步：他给出了变换的第一个显式代数形式，他向计算机科学和计算机视觉社区介绍了一个最初呈现为模糊的想法. 阿兹里尔·罗森菲尔德（Azriel Rosenfeld）是计算机图像处理史上的一位高瞻远瞩的人物，他的想法遍及600多篇论文和数十本书。但我怀疑很少有人知道他在将计算机视觉中最重要的算法之一带到现在的形式中所扮演的角色。
图 3
迂回
在模式识别研究的早期阶段，提出了许多替代的数学方法，这些方法早已被遗忘。其中一种方法是基于积分几何[8]，这是纯数学的一个分支，研究随机几何事件的概率。首先在18世纪提出的整体几何中的典型问题是布冯的针问题：将针放在由木板制成的地板上并计算针将穿过裂缝的概率。其他经典问题是计算线截取图形的概率并计算圆的随机弦的预期长度。这些学科中的一些研究引起了我的注意。对于积分几何学，现在已经很好地定义了“随意”抛出一条线的概念。这意味着在ρ-θ空间中的矩形上采样均匀分布，该矩形ρ在0-ρmax之间，θ在0和2π之间。对我来说，它可以用来解决斜率和截距的无界值问题。
发明霍夫变换
在20世纪60年代后期，我与我的同事Richard O. Duda和其他人一起为Shakey开发了一个视觉系统，这是一个由SRI International的人工智能中心创建的移动智能机器人。 Shakey生活在一个室内世界，房间里有几乎像楔子和立方体一样的几何实体。当今的视觉系统提供了噪声边缘检测作为起点，我们试图利用这种噪声输出来建立局部环境模型，并从已知地标的识别中更新机器人的位置。
我正在研究整体几何方法是否可以帮助解决这个问题，同时研究罗森菲尔德的计算机图像处理，看看我是否可以从这个开创性的书中获取任何想法。我对罗森菲尔德对“点线变换”的简要描述很感兴趣，但却被变换空间在理论上无界的尴尬事实所困扰，需要用到前面提到的不优雅的轴反转技巧。
然而最终通过考虑直线的正规形式的ρ和θ的有界值，以及由积分几何学建立的不变性，我提出了一个新的，我认为更令人满意的变换：
ρ=xicosθ+yisinθ (2)
ρ
从（2）我们可以将图像平面中的点（xi，yi）映射到曲线
图 4
图4示出了x-y图像平面中的三个点，并指示每个点具有通过它的任意大量的线。所有这些都有一条共同的线路吗？在水平截获接近无穷大的过程中，隐含地意识到在变形空间中出现的问题。图5显示了ρ-θ变换空间中的三个正弦曲线，每个正弦曲线对应于图像平面中的单个点。交点处的ρ和θ值定义了穿过三个点的x-y平面中的线。
图 5
这种新变换不会受到与将点映射到直线相关的理论和计算问题的影响。有限图像平面中的点映射到有限变换空间中的正弦曲线，并沿着线图指向相交的正弦曲线，而与线的方向或坐标轴的选择无关。
Duda和我在1972年向研究界介绍了新的变换[11]。在那篇论文中，我们将变换方法的计算复杂度与图像平面中所有点对的详尽分析的复杂性进行了比较，获得了简单的结果，我们还引入了变换的扩展，以解决检测高阶分析形状（如圆）的问题。今天教科书和大学课程普遍教授的变革是1972年杜达和我论文中描述的变换。
尾声
可是，我很惊讶那时研究界似乎对我认为的好主意没有反响，但我的注意力已经开始从计算机视觉转移到其他人工智能领域。许多年后，当我注意到1988年的一篇调查文章[12]引用了136篇参考文献时，我又感到惊讶。关于霍夫变换及其变化的研究一直持续到今天，偶尔还出现专门针对霍夫变换的特刊，例如[13]。
最近两个非常不同的例子说明了变换的广泛应用。第一个是粒子追踪（激发了霍夫的专利), 应用程序使用变换版本来检测大型强子对撞机中的μ子轨迹[14]。第二个应用与汽车安全有关：变换用于基于视觉的系统，该系统检测车辆何时离开车道
自引入Hough变换的现代形式以来已经超过35年了，它仍然是计算机视觉工具包中的标准项目。但它的早期历史表明，今天的变化几乎是由“偶然”从几何洞察演变为理论上优雅且计算上有效的程序。
[1] R. O. Duda and P. E. Hart, Pattern Classification and Scene Analysis. New York: Wiley-Interscience, 1973, pp. 335–337.
[2] R. Bradski and A. Kaehler, Learning OpenCV. Sebastopol, CA: O’Reilly, 2008, pp. 153–160.
[3] E. R. Davies, Machine Vision: Theory, Algorithms, Practicalities. San Francisco, CA: Elsevier, 2005, pp. 265–269.
[4] J. A. Canny, “A computational approach to edge detection,” IEEE Trans. Pattern Anal. Machine Intell., vol. 8, no. 6, pp. 679–714, 1986. [5] P. V. C. Hough, “Method and means for recognizing complex patterns,” U.S. Patent 3 069 654, Dec. 18, 1962.
[6] P. V. C. Hough, private communication, Mar. 13, 2009.
[7] A. Rosenfeld, Picture Processing by Computer. New York: Academic, 1969, pp. 335–336.
[8] H. Solomon, Geometric Probability. Philadelphia, PA: Society of Industrial Mathematics, 1987.
[9] A. B. J. Novikoff, “Integral geometry as a tool in pattern recognition,” in Principles of SelfOrganization, Von Foerster and Zopf, Eds. New York, NY: Pergamon, 1962, pp. 347–368.
[10] N. J. Nilsson, The Quest for Artificial Intelligence: A History of Ideas and Achievements. New York: Cambridge Univ. Press, 2010. [11] R. O. Duda and P. E. Hart, “Use of the Hough transformation to detect lines and curves in pictures,” Commun. ACM, vol. 15, no. 1, pp. 11–15, June 1972.
[12] J. Illingworth and J. Kitler, “A survey of the Hough transform,” Comput. Vis., Graph., Image Process. Arch., vol. 44, no. 1, pp. 87–116, 1988.
[13] Real-Time Imaging, vol. 6, no. 2, pp. 77–173, Apr. 2000.
[14] N. Amran and E. Etzion, “Hough transform track reconstruction in the cathode strip chambers in ATLAS,” CERN-THESIS-2008-062, 2008.
[15] K. Mineta, K. Unoura, and T. Ikeda, “Development of a lane mark recognition system for lane keeping assist system,” Honda R & D Rev., vol. 12, no. 1, pp. 101–108, 2000.
加群交流
关注计算机视觉与机器学习技术，欢迎加入52CV群，扫码添加52CV君拉你入群，
（请务必注明:52CV）
喜欢在QQ交流的童鞋，可以加52CV官方QQ群：702781905。
（不会时时在线，如果没能及时通过验证还请见谅）
长按关注我爱计算机视觉