快速霍夫变换算法_图文

1、 10 期 孙丰荣等: 快速霍夫变换算法 1107 有效地降低 FH T 中的误差, 改善算法的数值计算 精度特性. . g ( x , y 表示原图像 . N 表示原图像规模 ( x, y 表示扩展图像. g kN 表示扩展图像规模; kN = k N , k 为扩展 倍数, 且 k 为 2 的整数次幂. ( x, 0, a 表示对扩展图像进行 FH T 的最 H logkN 2 = 0, 终计算结果. 其中, x= 0, 1, , 2 kN - 1; a 1, , kN - 1. . 其中, x = 0, H ( x , a 表示 M FH T 的计算结果 1, , 2N - 1; a =

2、 0, 1, , N - 1. 1. Exp and ing x 1 + , k 2 y , k 定理 . 定理 2. 图 6 改 进 的 快 速 霍 夫 变 换 算 法 (M FH T 算法 的计算结果 H ( x , a ( x = 0, 1, , 2N - 1; a = 0, 1, , N - 1 是以下 H T 数值的近似 . 这里, 值 H ( , = x co s( x = 0, 1, , 2N - 1 ; = tan 1 a ( a = 0, 1, , N - 1 . 算法最坏情 N - 1 形下, 上述近似值的水平误差上界为 交误差上界为 a log kN 2 k log kN

3、 2 k + 1 ,正 2 1 . co s 2 ( 证明 . 将扩展图像的 H T 数值 H ( , = + N - 1 tan y 0 (m od k - 1 co s 对应的线段记为 L , 其上 , = x ( x, y = g g 2. FH T 1 by FH T A lg orithm 1 3 To get data set HlogkN ( x, 0, a 2 3. 1Con traction 1 0, o therw ise ( 13 的像素点表示为 ( kx , ky . 由定理 1 知, 在算法最坏 (x, 0, a 计算的扩展图像中的像 情形下, 参与 HlogkN 2

4、 < 1 ( log kN 素偏离 L 的水平误差 2 - 1 . 换言之, 2 , 0, a 是由像素集合 g ( kx + , ky 形成 (x H logkN 2 的 . 据式 ( 13 , 将上述集合映射到原图像中, 则为 kx + 1 g + , y . 从而, 相对于原图像,M FH T k 2 1 计 算结果 H ( x , a 中的水平误差 = + < k 2 kN 1 1 1 log 2 1 ( log kN < + . 即该水平误差的 2 - 1 + k 2 2 k 2 上界为 log kN 2 k 3 H ( x , a = H logkN 2 kx ,

5、 0, k+ k- 1 1 + a N - 1 2 ( 14 图 6改进的快速霍夫变换算法 显然,M FH T 的基本运算次数为 O ( k 2N 2 log kN 2 . 图 7 是 SH T , FH T ,M FH T 三种算法的计算量比较 ( 图中的计算量是已作对数化及归一化处理的基本 运算次数. 从图中看出, 较之 FH T ,M FH T 的计算 量有所增加, 但仍明显小于 SH T. 即在算法复杂性 方 面, 图 6 的 M FH T 仍 然 明 显 优 于 图 2 描 述 的 SH T. 另外,M FH T 在每次迭代中所计算的数据量 始终是 2k 2N 2 个, 而且在某次迭

6、代中各个数据的计 算仍然是彼此独立的. 所以, 图 6 描述的M FH T 算 法同样可以并行实现. 进一步, 若处理器阵列的规模 为O (k 2N 2 , 则 M FH T 并 行 处 理 的 计 算 量 仅 为 kN O ( log 2 . 关于 M FH T 的数值特征, 我们得到如下 + log kN 1 2 1 , 正交误差上界为 . + co s 2 k 2 证毕 . 定理 2 表明, 较之 FH T ,M FH T 能够有效地降 低 FH T 由于近似处理带来的误差 ( 参看图 8 . 从 图 8 中还可以看出, 随着图像扩展倍数 k 的增大, . 总之, FH T M FH T

7、 算法的水平误差上界明显减小 算法具有良好的计算精度, 而M FH T 算法又进一步 改善了算法的数值计算精度特性 . © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 1108 计算机学报 2001 年 5数值算例 标准图像FH T 及 M FH T 计算中处理的标准 图像如图 10 所示, 其规模 N = 512. 图像中的圆域 以 B resenham 圆域填充算法生成 ( 圆心位于图像中 心, 半径为 100. 圆域内部的像素值规定为 100. 模型及其 H

8、T 数值仿真计算如图 9 所示, 模 型为圆心位于坐标原点、 半径 R = 100 的圆域. 规定 圆域内部的密度值 g = 100. 则相应于图中直线ab的 H T 数值为 = H ( , 4 (横轴为 x , 纵轴为 H T 数值 . 下同. 以相同的采样 方式, 对模型进行 H T 数值的仿真计算, 结果如图 11 所示 . 该算例显示, 采用近似处理实现快速计算 的 FH T 具有良好的计算精度 . : x H , g d l ab ( 15 2 进一步分析得到 = 2g H ( , R 2 ( 16 例 1. 利用图 4 所示的 FH T 算法处理标准图 像, 根据定理 1, 其最终

9、的迭代计算结果是以下 H T 数值的近似值 , H ( , , a = 0, 1, , 511; = x co s , 511 x = 0, 1, , 1023 ( 注意, 在不引起混淆的情况下, 我 表示 FH T 的迭代计算结果 , 而 们也使用 H ( , 1 例 2. 首先, 利用图 13 描述的处理过程, 获得 0, 范围内的、 对参数空间进行非均匀采样的 H T 数值 . 然后, 对上述数值进行插值处理 ( 线性插值 , 得到在参数空间内进行均匀采样 ( 参考图 14 所示的 采样模式 的计算结果 H (d , < , 其中, d = 0, 1, , 511, <= 0

10、, , 2 , , - = . 180 0, p rocedu re Com p u ting H T values fo r 其中, = tan - a k = 1; 且, 前文已提及, 对于参数空间而言, 上述计算结果 是对其进行非均匀采样而获得的. 图 12 中, 三条曲 线分别对应 : x H ( , 0 : x H , tan - 1 do by FH T 1. Getting H ( , 2. D iscard ing the last g roup values; 4 3. A pp end ing the values to the com p u ting resu lt a

11、rray; 4. Ro tating the im age w ith ang le k+ + ; k 3 T hat is, d iscarded values is H 4 , 3 ; 256 511 w h ile ( k 4 ; 图 13范围内 H T 数值的计算过程 © 1994-2009 China Academic Journal Electronic Publishing House. All rights reserved. 10 期 孙丰荣等: 快速霍夫变换算法 1109 该算例更加清晰地显示了 FH T 良好的计算精度, 也显示了M FH T 在提高计算精度方面

12、的实际效果 . 6结论 快速霍夫变换算法是模式识别和计算机视觉研 究领域的热点问题 . 基于近似计算和迭代处理的策 略, 本文 FH T ( 及 M FH T 算法实现了二值图像直 线检测过程中 H T 的快速计算 . 而且, 算法的误差分 析及数值算例都表明 FH T ( 及 M FH T 有着良好的 计算精度 . 这无疑将提高实际应用中二值图像直线 检测过程的计算效率和检测精度 . 图 4 和图 6 给出 的是顺序算法, 但理论分析表明, FH T ( 及 M FH T 算法可以并行实现, 这意味着算法更为广阔的应用 前景, 这也是本课题继续深入研究的方向之一 . 参 1 图 16 对应上

13、述全部 180 组 H T 数值. 以相同的采样 方式, 对模型进行 H T 数值仿真计算, 结果如图 15 所示 . 图 17 是采用 M FH T ( 图 6 算法中的图像扩展 系数 k = 2 所获得的相应计算结果. 观察图 1517, 可以发现, 较之FH T ,M FH T 有着更高的计算精度. 考 文 献 2 3 4 5 6 P rincen J , Illingw o rth J , K ittler J. A fo rm al defin ition of the Hough T ran sfo rm p rop erties and relation sh ip s. J M

14、 athem atical I m ag ing and V ision, 1992, 1: 153- 148 Bergen J R , Shvayster H. A p robab ilistic algo rithm fo r com 2 p u ting Hough T ran sfo rm. J A lgo rithm , 1991, 12: 639- 656 H u Z Y, M a S D. T h ree cond ition s of a good line p aram eteriza2 tion. Pattern R ecogn ition L etters, 1995,

15、16: 385- 388 Hough P V C. M ethod and m ean s of recogn izing com p lex p at2 tern s. U. S. Paten t 3069654, 1962 Ballard D H. Generalizing the Hough T ran sfo rm to detect arb i2 trary shap es. Pattern R ecogn ition, 1978, 10: 129- 143 D ual R O , H art P E. U se of the Hough T ran sfo rm to detect

16、 lines and cu rves in p ictu res. Comm un ication s of A CM , 1972, 15: 11- 15 Ho C T , Chen L H. A fast ellip se circle detecto r u sing geom et2 ric symm etry. Pattern R ecogn ition, 1995, 28 (1 : 117- 124 Cheng F H , H su W H , Chen M Y. R ecogn ition of handw ritten Ch inese characters u sing fe

17、atu res by m od ified Hough T ran s2 . IEEE T ran s PAM I, 1989, 11 (4 : 429- 439 fo rm techn iques Iocch i, L uca, N ard i, D an iele. Hough T ran sfo rm 2based local2 ization fo r m ob ile robo ts. A dvances in In telligen t System s and Com p u ter Science, W o rld Scien tific Eng ineering Societ

18、y, 1999. 359- 364 D avise E R. I m age sp ace tran sfo rm fo r detection straigh t in in 2 . Pattern R ecogn ition L etters, 1986, 4: 185 du strial im ages 192 Cyp her R E, Sanz J L C, Snyder L. T he Hough T ran sfo rm has com p lex ity on m esh connected com p u ter. S I AM J Com p u ting, 1990, 19: 805- 820 Guerra C