（系统分析与集成专业论文）并行计算在hough变换中的应用.pdf

学位论文独创性声明 本人所里交的学位论文是我在导师的指导下进行的研究工作及取得的研究 成果。据我所知，除文中已经注明引用的内容外，本论文不包含其他个人已经 发表或撰写过的研究成果。对本文的研究做出重要贡献的个人和集体。均已在 文中作了明确说明并表示谢意。 作者签名：盐董：日期；2 翌生厶9 学位论文使用授权声明 本人完全了解华东师范大学有关保留、使用学位论文的规定，学校有权保 留学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版。有权 将学位论文用于非赢利目的的少量复制并允许论文进入学校圈书馆被查阅。有 权将学位论文的内容编入有关数据库进行检索。有权将学位论文的标题和摘要 汇编出版。保密的学位论文在解密后适用本规定。 学位论文作者签名；体慧 日期：2 盟幺臼 导师签名：阮和于牛 日期：坦垒! q 。扛东帅范人学计算机系硕卜学位论文 摘要 人多数蚓像处理任务都是计算密集型的问题数据量和运算量大，给实时应用带来困难， 而剀像) ：行处理技术是提高图像处理速度的最有效技术。 在幽像处理技术中，h o u g h 变换在形状分析方面被公认为是一种强有力的工具，即使枉： 徊噤卢的情况r ，它仍能给小比较c i f l , j 结果。但它有既个主要的缺点，一是运算量人，运算 时问k ，小能满足某些实叫性要求；一硅耗费内存空间多。因此，它也需要并行技术。本文 对它的并仃化披术进行j ，深入的时论。其主婴作如f ： 1 蚓像并行处理技术的l 。多基本概念，都米白计算机并行处理的概念。因此我们首先对f 汁算机的发艇及其体系结构进行j 7 同顾。另外，在并行算法方觚，对其定义和分类作了 介纠， 刈 仃算法的砹订法柑睢能评价进行了阐述。 2 接着本义介 “f j ，h o u g h 变换，行川二二种不| 司的体系结构和方法米实现它的升j j ：化。 3 尚先住删孔连接纳i r 算机f 实现l o u g h 变换。由，维网孔计算机的结构比较简单 而且比较规范，使得它成为觯决汁算机图像处理问题首选的并行体系结构。本文针对传统 i i o u g h 变换只能统计直线t 嶷包魏豢个数，不能记录线段的两端点坐标艘跃度的缺点，介 纠j 7 冲f l 改进t l o u g h 变换弹法并扫r 网孔处理机阵列中实现，还给山r 能够识别并消除重 复线段的j l 行算法，这些m 实际问趔。i i 是很有j _ 的。 4 j 0 管刚孔类j 铂体系结构i t 4 通合蚓像处理算法但网孔本身通信直径人，当处理艮距离 的数据传递搬f 1 州，速度比较慢，l 硝此人们提出j 由连续的尺寸递层减小的网孔绸成的金 字塔体系结构，它结台r 刚4 l i i 树类，体系结构的特征。本文提出了一种有效的多分辨率 1 4 0 u g h 变抉扫二金字塔机器。 ，的流水线实现。多分辨率h o u g h 变换使州一系列的多分辨率 划像午f f 祟加器数组的特性，i 柏敬地把它映射到金字塔不同层人小可变的处理器阵列中。 这种力法充分地利川了处理器，1 ：l - i 流水线这种实现方式可适i h 丁连续图像的有效分析。 5 计 ? 计弹机体系结卡勾包括单指令流多数据流( s i m d ) 和多指令流多数据流( m i m d ) 曲种绌构。f i l l 撕_ f l 法都址丝 j s i m d 结构。本文介纠了一种新的包含了m i m d 币s i m d 肌种结构的系统结构，我们称这种新的结构为混台系统。而且，我们介纠了一种适用于此 性台系统的新的h o u g h 变换定义方法，并在此混合系统中实现，取得了较好的效粜。 戈键酬：l t o u g h 变换 j r 行计算网孔i ：r 算机金字塔处理机s i m dm i m d 堂蔓塑垫叁兰 ! ：簦! ! 墨 蟹土兰垡堡兰 一一一 a b s t r a c t m o s ti m a g ep r o c e s s i n gt a s k sa r ev e r ye o m p u t a t i o n a l l yi n t e n s i v e t h ea m o u n to fd a t a i n v o l v e da n dc o m p u t i n gp o w e rr e q u i r e da r ev e r yl a r g e ，w h i c hb r i n gg r e a td i f f i c u l t i e si nr e a l _ t i m e a p p l i c a l i o n s ，w h i l ei m a g ep a r a l l e lp r o c e s s i n gt e c h n o l o g y i st h em o s te f f i c i e n tt e c h n o l o g yt o i m p r o v ei n a a g ep r o c e s s i n gs p e e d h 1t h ei m a g ep r o c e s s i n gl e c h n o l o g y ，h o u g ht r a n s f o r mi sc o n s i d e r e da s ap o w e r f u lt o o li n s h a p ea n a l y s i sw h i c hg i v e sg o o dr e s u l t se v e ni nt h ep r e s e n c eo fn o i s e b u ti t h a st w om a j o r s h o r t c o m i n g s o n ei sl a r g ec o m p u t i n gp o w e ra n dl o n gc o m p u t i n gt i m e ，w h i c hc a n ts a t i s f ys o m e l e a l t i m e r e q t d r e m e n t s ，t h eo t h e ri s e x c e s s i v es t o r a g er e q u i r e m e n t t h e r e f o r e ，i tn e e d sp a r a l l e l t e c h n o l o g y i nt h i sp a p e rw eg i v eaf u r 、t b e , c o n s i d e r a t i o na b o u ti t sp a r a l l e le x e c u t i o n ，a n dt h ew o r k o f t h ep a p e ri si n c l u d e da sf o l l o w i n g m a n yb a s i cc o n c e p t si nt h ei m a g ep a r a l l e lp r o c e s s i n ga r ef i o mc o m p u t e rp a r a l l e lp r o c e s s i n g ， s ow ef i r s tl o o kb a c ko f tt h ed e v e l o p m e n to fp a r a l l e lc o m p u t e ra n di t sa r c h i t e c t u r e so t h e r w i s e ，i n t h ep a r a l l e la l g o li t h m ，w ci n t r o d u c ei t sd e f i n i t i o na n dc l a s s i f i c a t i o n a n do i lt h eb a s eo ft h i s ，t h e d e s i g nm e t h o do fp a r a l l e la l g o r i t h ma n di t sp e r f o r m a n c ee v a l u a t i o na r ed e s c r i b e d a f t e rp i e s e n t i n gt h ed e f i n i t i o no f t h eh o u g ht r a n s f o r m ，w ea p p l yt h r e ed i l f c r c n ta r c h i t e c t u r e s a n dm e t h o d st oi n r p l e m e n tp a r a l l e le x e c u t i o no f t h eh o u g ht r a n s f o r r n f i r s tw ei m p l e m e n th o u g ht r a n s f o r mo nt h em e s h - c o n n e c t e dc o m p u t e r ( m c c ) b e c a u s eo f i t ss i m p l i c i t ya n dr e g u l a r i t y ，t h e2 - d i m e n s i o nm c ci sap r e f e r r e dp a r a l l e la r c b i t e c t u r ef o rs o l v i n g t h ec m l l p u t e l li m a g ep l o c e s s i n gp r o b l e m f h ec o n v e n t i o n a lh o u g ht r a n s f o r mc a no n l yc o u n tt h e n u m b e , o ff e a t u r ep o i n t sw h i c ha l ec o l l i n e a r , a n dc a l l tr e c o r dt h ee n dp o i n t so f al i n es e g m e n ta n d i t s l e n g t h h e r e b y ，t h i sp a p e rp r e s e n t a ni m p r o v e dh o u g ht r a n s f o r mt oo v e r c o m et h e s et w o s h o r t c o m i n g st h ea l g o r i t h mi sp a r a l l e l i z e da n di m p l e m e n t e di nm c c w h a t sm o r e ，w eg i v ea p a r a l l e la l g o r i t h mt oi d e n t i f ya n de l i m i n a t eo v e r l a p p i n gl i n es e g m e n t st h e s ea d v a n t a g e sa r ev e r y u s c “jj i nt h er e aj a p p l i c a t i o n s a l t h o u g hm e s ht y p ea r c h i t e c t u r ei sv e r ys u i t a b l ef o r t h ei m a g ep r o c e s s i n g ，i t sc o m m u n i c a t i o n d i a m e t e ri sv e r yl a r g ei tt e n d st ob es l o ww h e ni tc o m e st oh a n d l i n gd a t at r a n s f e ro p e r a t i o n so v e r l o n gd i s t a n c e s s op y r a m i da r c h i t e c t u r e s ，c o n s i s t i n go fa s t a c ko fs u c c e s s i v e l ys m a l l e rs i z e d 5 华东师范、学计算机系硕士学位论文 m e s h e s ，h a v eb e e ns u g g e s t e d p yr a m i da r c h i t e c t u r e sc o m b i n et h ef e a t u r e so fm e s ha n dt r e et y p e a r c h i t e c t u r e s l h i sp a p e rp l e s e n t sa ne f f i c i e n tp i p e l i n e di m p l e m e n t a t i o no ft h em u l t i r e s o l u t i o n h o u g ht r a n s f o r m ( m h t ) o nap y r a m i dm a c h i n e ，t h em h t u s e sas e to fm u l t i r e s o l m i o ni m a g e s a n da c c u n r n l a t o ra r r a y sa tt h ed i f f e r e n tl a y e r so ft h ep y r a m i d ，w h i c hc a nb ee f f i c i e n t l ym a p p e d i n t ot h ev a ti a b l es i z e dp r o c e s s o ra r r a y sa tt h ed i f f e r e n tl a y e r so ft h ep y r a m i d d u et ot h i s ，t h e m e t h o di e s u l t si l la h i g hu t i l i z a t i o no ft i l ep r o c e s s o r sb e s i d e s ，t h ep i p e l i n e di m p l e m e n t a t i o n i h s h i o ni ss u i t a b l ef o rr e a l - t i m ea n a l y s i so tac o n t i n o o u ss e q u e n c eo fi m a g e s p a r a l l e l c o m p u t e r a r c h i t e c t u r ec o n s i s t so ft w o c l a s s i f i c a t i o n s ：s i m p l ei n s t r u c t i o n s lr e a m t n u l l i p l ed a t as t r e a m ( s i m d ) a n dn m l l i p l ei n s t r u c t i o ns t r e a m m u l t i p l ed a t as t r e a m ( m i m d ) t h ea b o v et w om e t h o d sa r eb o t hb a s e d0 1 1t h es i m ds t r u c t u r e i nt h i sp a p e gw ei n t r o d u c ea n a r c h i t e c t u r e 。r e f c r r e da sh y b r i ds y s t e m ，c o m b i n e sb o t hs i m da n dm i m ds y s t e mf u r t h e r m o r e ， w ep r e s e n tan e wp a la i m b a s e dii o n g hl r a n s t b li l lf o ri m p l e m e n t a t i o no nt h eh y b r i ds y s t e ma n d g i v eab e t t e ri e s u l t k e y w a r d s ：h o u g ht r a n s f b ln 1 p y r a m i dp r o c e s s o r p a ) a l l e lc o m p u t i n g s i m d 6 m e s h c o n n e c t e dc o m p u t e r m i m d 华来帅她人学讨。算机系坝上学位论立 第一章绪论 耐至今日，幽像处理已经发展成为。应用广泛、内容丰富的综合性学科，也是诸多计 算机应i l j 领域中一个最为活跃的领域。它的发展已有4 0 余年的历史，在此期间，随着汁算 机、集j j 芟i u 路等技术的e 速发腱，i 璺| 像处理无论在算法上、系统结构上，还魁在应刚上以及 博段f | 勺程度l 都j 】c 得丁长足| ! f ( 】进展。但培，幽像处理依然面l 临着许多挑战性的问题，其中艘 1 要的问题就足如f u j 提高解扶实际复杂问题的综台能力。就当前的技术水平米说，这种综合 能力色土括i f - l 像处理的删络化、复杂问题的求解与处理速度的高速化。 蚓像j i ： 处删技术是l 利像处理中的一个重要方面，是提高图像处理速度的最有效技术。 1 i图像处理目前面临的挑战1 1 】 现在的幽像处理，已经取得_ r 理论l i 、应用上的突出成果，并进入了人发展时期，但也 瓶临着i i 多挑战。诸如于写体文字的识别技术、癌细胞的识5 ；l 技术、复杂应蹦的实时系统技 术等臀，门纳起来这些挑战集中在以r 三个方面： i )幽像处理的网络化 2 )复杂问题的求解 3 )处删速膻的高速化 1 1 1 图像处理的网络化 蚓像处理系统的发展人致分为3 个阶段。早期的图像处理系统比较昂贵，多以小型机为 ：机，h 多人轮流使川一台殴备，这个阶段为第一阶段。这一阶段的图像处理系统具有以图 像帧存为中心的系统结构。随着微机性能的提高私j 价格的火幅度降低，在幽像处理实验室里， 人s j l d p ，| j ! i j 称该条件f ，该算法具有超线性加速比。 2 4 4 。5 并行算法的可扩展性分析 可扩胜性灶改“高性能并行机年j f ：行算法所追求的一个重要目标。它呵分为资源可扩展 p i - 、鹰川t 扩展性t f l | 技术可扩艘性二种。由于本文的主要研究对象是并行算法，为此本节主要 羽其中的应, q l 可j j l 展性，也即并行算法的可扩展性进行讨论。 并行算法的可 ：f i 展性”1 1 “是对并行算法有效利用增加的处理机数目能力的一种度量， 与算泫没计内在”行性和通信需求钉芙。1 9 9 3 年a y g r a m a 等提山了度量并行算法可扩 展性的恒等效率方法【”i 。 似l 殳某斤行弹法往南p 台同构处理机组成的并行机上的执行时问为l 。它对应的最优 i # 行掉法的执行1 1 1 问为z ，则根据外行算法的效率定义有 r 、s r 乜p2 孑一 丑：卫：! 乃蚶兀叮 n r 兀为并行算法在尸台处理机上执行时的通信、同步等时间开销。 华东师范人学计算机系碗：l 学位论文 硅然式中的z 足问题规模的增函数。对脚定问题规模，随着处理机数p 的增加。f 不变，t o 将增t j j l j ，因此根据公式可知算法的效率将。f 降：对固定的处理机数_ p ，随着问题规 模的增人，、正都将增大，但由下增加的速度小于五，因此算法的效率将增大。结台 这两种情况可知，对某些并行算法而言，在p 增加的情况f ，只要适当地增加问题规模 可以保持算法的效率不变，此即j f 行算法可扩展性的恒等效率度量方法。由于并行算法的通 信开销瓦的增k 速率囚体系结构而异，冈此这里所说的并行算法的可扩展性指的是基于给 定体系坌吉构的并彳丁算法的可扩展性，也即并行算法一体系结构组合的可扩展性。 进一步根据上式叫知，为保持效率i 刮定， 五必须正比于t o 。换言之，r 列等式应被满 足 丁。2 足7 1 。 由，一? l 、“为户雨j 的函数，因此由式，可推得正心j d 表示的函数式丁= 厂。( 尸) ， 刚为并行算法对r 效率e 的恒等效率幽数。 若j ( p ) 为p 的线性函数，则称浚并行算法是强可扩展的。 2 4 5 并行加速比模型 ， ：行加速比是一个度鼙r 扑处理性能的参数它刻画并行求解一个实际问题所获得的性 能， ! | j 柏对单机l i 的串行处理m r 高使 j 并行处理所获得的性能。从问题规模角度出发可将并 行加速比分为矧定规模问题的，【j 速比模型和可变规模问题( 扩充问题规模) 的加速比模型。 2 4 5 1a m d a h l 加速比模型 a m d a l l i 加速比模型指出：对于个给定的并行系统雨j 一个崮定规模的问题如果该 蝴题的串行部分所l ! ，比例为厂，并行部分所占比例为n ，且厂+ n = l ，并行系统的规模为 尸，昔我们忽略通信同步等由 ：并行化所引起的额外开销，则有 研2 蔗2 志 华东师范人学 计算机系硕士学位论文 从式中可以香i l j ，无论使h j 多少台处理机，它的加速比都不会超过肜，也就是说应 用问题串行部分的瓶颈无法川增加处理机台数来解决。由于该模型假设了问题规模阉定，故 它也称为吲定规模问题的加速比模型。 2 4 5 2g u s t a f s o n 加速比模型 按m a m d a h l 定律，由1 二只i i0i 的审行操作的存在，用1 0 0 0 个处理器的最大加速比也不 会超过1 ( ) 。然而1 9 8 8 年2 f l 美国s a n d i a 国家实验室的g u s t a f s o n 等三人在含1 0 2 4 个处理器的 n c u b e 系统上进行了非稳定流修止、曲面波模拟以及薄膜应力分析等3 个应用问题的试算， 史陶、m i 述比分别达到- r 1 0 1 6 ，1 0 2 0 l j l 0 2 1 。依据这些实验结果，他们指出经熟a m d a h l 定律 蕴含着问题规模1 i 变的假定，即掉法中的可并行成分不随处理器个数变化的假定是不符合实 际的，通过适当增加问题的规模川以哒到线性加速比。若，、n 定义如前，且 = 1 ， | j ! i l ) j i ：i 迷比为 2 糍+ p 此| ：i | j 吼- s t a f s o n 血i 述比模型。它指山婴获得较高的加迷比，应随处理机数目的增加而增加 刚题的枷模，衙小足吲定问题j ；5 l ! 模。 娃然，a m d a h l ) j l l 速比模j 弘! j g u s t a f s o n j j h 速比模型从不同的角度看待并行处理，前者强 渊的是通过并 i 处理米缩短求解题的刚阃，后者强调的是在同样的时问里，通过并行处理 能运行多人的运算量，即通过运行时阔米限制问题规棋的增长程度。 2 5 小结 本章刚唢了并行汁算机的发展过样，井介绷了它们的分类及其体系结构。在阐述硬件方 面的i 司时，对并行算法的软什环境，特别是消息传递并行环境p v m 做了介绍。然后详细描 述了并行算法方面的基础知识。住并行算法的定义和分类的基础上对并行算法的殴计方法、 性锖评价进行rl 喇述。 奉章对丁后i 自i j l 章刚刨的j f 行计算机体系结构、并行算法的提出与评价标准，起着理论 1 的指导f l ：, l t j 。本章是厉面儿章的理论基础。 兰查些型查堂 盐苎塑墨 塑! ：兰垡丝兰一 第三章h o u g h 变换的基本原理 在形状分析方面，h o u g h 变换被公认为是一种强有力的工具，即使在有噪声的情况f ， 它仍能给川比较女f 的结果。它有舾个i 要的缺点：一一是运算量大，运算时间长不能满足某 些实时性娑求：，足耗赞的内存空间多。但它适合并行处理，因此被，“泛地应用于图像处理 和计算机视觉的领域中，而且这种方法也越米越受到了人们的重视。 由 一在h o u g h 变换中，我们考虑的图像是二值边缘图像。因此，在进行h o u g h 变换之 酊，酋先业对幽像进行边缘检测并? 值化。r 面就先l l 我们回顾一下边缘检测方面的内容。 3 1 边缘检测 刚像的边缘娃幽像的最基本特祉。所谓边缘是指其周围像素灰度有阶跃变化或屋顶变化 的那些像素的集台。边缘j 泛地存在r 物体与背景之间、物体与物体之间、基元与基元之间， 它是羟 像分制的重要特征。 边缘检测可以借助空域微分算于( 住数字阁像巾，都j ； j 差分运算来代替) 模板，利用卷 积晌方法米实现。常川的边缘检测算j 有以f ) l 种： r o b e r t s 算子 对j ：数字幽像f ( x ，y ) ，它的每个像素的梯度值为 g m ( i ，) = ( 。，( f ，) ) 2 十( y f ( i ，) ) 2 。厂( f ，l ，) = f ( i ， ，) ( f i ，)，f ( i ，) = f ( i ，) 一f ( i ，1 ) 接中、( t ) ，a ，( - ) 分：l j i j 为x 、，方向的差分a r o b e r t s 算f 是对g m ( i ，j ) 的近似，其模板为 s o b e i 算子 一 华东帅范人学计算机系 硕一学位论文 s o b e l 算子采h j 3x3 邻域，它的检测效果比r o b e r s 算子好。其摸板为 一101 20 2 1ol 拉普拉斯( l a p l a c i a n ) 算子 12l 000 一l一2一l l , a p l a c i a n 算于是一种阶导数算子，其二阶导数在边缘点处出现零交叉。因此找到了 零交义点，就能找到边缘点。其摸板为： 高斯拉普拉斯算子 o一10 1 4 一l 010 一lll l8一l lll 由j jl a p l a c i a n 算子边缘检测办法常常产生双像素边界，另外还对噪卢比较敏感。因此， 把l a p l a c i a n 锐化滤波器平高斯平滑滤波器结合起米，先平滑掉噪声，再进行边缘检测，效 求史蚶。这就是高斯拉普拉斯弹子( l a p l a c i a no f g a u s s i a n ，l o g ) 常朋的模扳如下： 2 4 4 4 2 4080 4 。482 48 4 4080 4 2 4 4 4 2 3 2 h o u g h 变换的背景 h o u g l l 变换i ”】( i t o u g h f r a n s f o r m ，h t ) 是由p a u lh o u g h 在1 9 6 2 年首次提i _ l j 的。他根据 数学对偶性原则提山了检j 9 | | j 幽像直线的l i o u g h 变换，起先是作为一项电子设备方面的专利， 川1 ：从气泡室的规洲区域中探测高速粒子轨迹的。最米，h o u g h 变换引起了r o s e n f e l d i ”1 领 导的性i 像处理协会的注意，该力法被不断地研究和发展。d u d a 和h a r t 口u i 将极坐标引入了 t o u g h 变抉，使i l o u g h 变化更加有效的川丁直线探测。1 9 8 1 年，d h b a l l a r d p q 提出了检测 非解析任意形状的r 一投法，有效的将h o u g h 变换推广到对任意方向和范围的非解析的任意 形状的识别这方法称为j 。义t l o u g h 变换法( g e n e r a l i z e d h o u g h t r a n s f o r m ，g h t ) 。 华东师范人学计算机系 碗士学位论文 由 。h o u g h 变换对随机噪卢和部分遮盖现象不敏感，而且适合并行处理，因此被广泛 地应川于计算机幽像处理利汁算机视觉领域中，如直线检测、圆的检测、一般边界的检测、 。维和三维运动参数的估计，这种方法也越来越受到人们的重视。 3 3 h o u g h 变换的定义 3 3 1 斜率一截距参数化表示法 直线的方拌为 其中羽 f 足参数分别表示斜率羊截距。 ( 3 1 ) 述方样中，x 和y 提脱测变量，卅利c 是参数。如果已知参数值珊和c 则该点坐 柏、之问的关系剐列确定。把上述方捌巫新表示为 ( 。= v m x ( 3 2 ) 假定和c 是我制感兴趣的变鲑而x 和l y 是常数，则上述方程表示的是m c 空间中 的一条首线，斜率和截距山x 利y 抉定。点0 ，y ) 对应于m c 空间的一条直线。x y 空 间的条龃线对廊m c 空问的一个点，如圈3 - 1 ( a ) 所示。如果育线上有n 个点，那么这些 点对应参数字问一cl 的一个卣线族，且所有直线都经过( m ，c ) 这一点，该点的坐标正好 反映rx y 空f ；i i ：的龃线参数，如吲3 - l ( b ) 所示。 c 2 1 2 34 o 1 2 m x y 空间的一条真线对应m c 空间的一个点 o 一 计算机系硕上学位论文 1 2 3 4 ” c 2 2 m ( b ) x y 空间的一条直线上的多个点对应棚一e 空问多条交于一点的值线 蚓3 一l i l o u g h 变换的斜率一截距参数化表示 然而如果使j j 上述( 3i ) 的南线方程式，将产生如_ f 的两个问题 若输入陶像为垂直卣线，斜率将趋于无限火 若输入图像为水平直线，截距将趋于无限大 针对这两个刚题提出了所旧的法线参数化( n o r m a lp a r a m e t e r i z a t i o n ) 表示法，它使用 r 冉线的檄坐标形式，非常适合实际席j _ j 。 3 3 2 法线参数化表示法 d 线的极坐标形式刊袅小如p p = x c o s o + y s i n t 9 其中p 表示从原点到盲线的法线距离，口为从x 算起的角度。 ( 3 ，3 ) 从卜式可以看出，x y 平阿内的条直线对应于p 一0 空间中的一点，如图3 - 2 ( a ) 所 1 i 。如果直线上有月个点，那么这些点对应空间p 一目空间上的厅条止弦曲线，且所有的正 坛曲线相交1 j p 一目空间中的一点这个点就是该直线的参数如图3 - 2 ( b ) 所示。根据这个 原理，l ，j 以刖h o u g h 变换抽取商线。 华东师范人学计算机系 硕士学位论文 通常将x y 称为幽像空间，p 一0 为参数空l n j 。 y 2 y 2 2 x y 玎 o ( a ) x y 空问的条直线l 对应p 一0 空问的个点 2 x y 氕 0 2 ( b ) 一条龃线i 多个点对应多条交于一点的止弦曲线 酬3 - 2h o u g h 变换的法线参数化表示法示意图 2 法线参数化表示的h o u g h 变换，义称为经典的h o u g h 变换，或者称为标准的h o u g h 变 3 3 3 h o u g h 变换的离散化表示 在计算机内，处理的幽像都是数字幽像。上述( 3 3 ) 的h o u g h 变换表示法中图像空 间和参数空间都是离散化的，f 面我们介窖f ! l 一下标准的h o u g h 变换的离散化表示。 j 5 1 酬像卒间，的人小为n m ( 即m 行”列，原点在图像的左f 角) 。l ( i ，j ) 表示幽 华东帅范人学计算机系硕士学位论文 像在【f ，) 处的像素值。d | 于我仃j 考虑的是二值图像，因此如果( j ，) 处的像素点是边缘点( 这 些点义称为特征点) ，则l ( i ，j ) = 1 ：否则tl ( i ，j ) = o 。 改参数空间的范闭为【一。，n 。 ，陋。，氏。】，假设设定p 个0 值，可个p 值。则 臼= ( 只。一只。) p ，p = ( p 。一p 。) q 圳么参数空间就形成了一个p oq 网格。其中 第卅个护值为 p 。= p 。+ m a o( 0 m p ) 第九个p 值为p 。= p m m + n a p ( o 门 g ) 则式( 3 3 ) 的彤式政为：p 。= l i c o s o m + j s i n o m j 3 4 应用h o u g h 变换检测直线的算法步骤 ( 3 4 ) 抽取商线的h o u g h 变换的通常步骤，山概括如h 1 对幽像进行边缘检测井：值化。 2 在参数字间选择合适的p 。，p 。，只。，只。 3 台理地量化参数空问，t ：【p 。，p 。丑x 】，阢。氏。】间建立一个累加器4 ( 肛臼) ， 肝管每个元素为0 。 4 埘一给定的0 值对x y 平面的每一个边缘像素点应用h o u g h 变换，利t 【：i j 公式( 3 4 ) ， 计算相应的p 值，行任相应的累加器l ，a ( p ，0 ) = 爿( p ，0 ) + l 。 5 重复步骤4 ，售剑汁葬完所有的臼值。 6 统汁得剑的累加表，找山剥应蚓像平面欺线点的累加器中的局部极大值或摄大值，这 个值就是检测到的直线参数。 从上述算法步骤中，我们i 叮以清楚地看到h o u g h 变换实质上娃一个“投票”过程。累 加表中的每一i l 都是一个候选，累加表相当于一个投票统计。每个特征点对通过此点的所有 卅能的由线进行投祟。得票多的项所对应的参数就是实际图像空间中检测到的直线的参数 3 9 华东! j r b - 7 0 ；凡学计算机系硕士学位论文 值；而得票少的项丢弃不要。“投祟”止体现了h o u g h 变换的全局性和抗干扰的鲁棒性。 3 5 h o u g h 变换的并行化 从上面的定义中，我们看 i jh o u g h 变换存在着两个主要的缺点：一是运算量人，运算 h f 间长，小能满足某些实时性较强的应刖场合；二是耗费i 存空间人。对此，人们提出了许 多解珧方法，大致分为两种： 设讨高效的h o u g h 变换算法； 在多处理机系统中通过使j 多个处理单元获得大量的计算能力来实现h o u i g h 变换。 第种力法已经在多分辨牢h o u g h 变换1 2 2 1 ( m u l t i r e s o l u t i o nh o u g ht r a n s t b r m 。m t t t ) 口适、th o u g h 变换1 2 3 1 ( a d a p t i v eh o u g ht r a n s f o r m ，a h t ) 以及快速h o u g h 变换1 2 4 1 ( f a s th o u g h t r a n s l b l m ，f h t ) 中得到实现。为了减少计算，这些算法都是基于迭代的由粗到精的搜索策 蜡。 第一种实现方法也已经在汁y - l l 荚文献中描述。例如，在h o u g h 变换映射到网孔体系 结构中的实现川1 2 7 j ；柏线性阵列中的实现f 2 8 】，搏动性阵列的实现1 2 ”，分布式存储机器的 实现i ”i | 3 “，兆享存储机器的实i 皑【”i ，号体系结构中的实现m 】。 任第种解决方法中，虽经过1 ；断的努力，已提出了上述等多种改进的方法，但h o u g h 变 奂奉身是汁算密集犁的问题传统的单机系统不能提供足够的处理能力。因此，由丁h o u g h 变换本身特点干l | 汁算t l l f l 方面的限制，在计算时间的方面，还是存在着很大的问题。特别 是在j 。业环境中，对实时性的婴求越米越高。在这种情况f ，并行计算的应川就成为了一种 必然结果。 此，本义1 i j f 究的重点就竹第一种实现方法方呵，也就是把并行计算麻用到h o u g h 变 换米。住f 面儿章中，我们将刈具体的行行算法及其在并行计算机上的实现做详细的讨论。 3 6 小结 本章介 “j h o u g h 变换检测直线的两种定义：一种是斜率一截距参数化表示法，另 种足法线参数化表示法。由r 在第种定义中，当输入图像为垂直宜线和水平直线时，将 出现参数空间无煨人的问题。冈此，提出了第二种定义井被广泛地用于研究平实践中。由 j h o u g h 变换存住运算量人，运算时问长以及耗费内存空间人的问题，传统的单机系统不 4 0 华东师范人学计算机系硕士学位论文 能提供足够的处理能力。吲此我们把并行计算应用到其中来。在之后的儿章中我们将对此 做深入的讨论。 4 l 华东师范人学汁算机系硕士学位论文 第四章 h o u g h 变换在网孔计算机中的实现 由i 二维网孔计算机( m e s h + c o n n e c t e d c o m p u t er m c c ) 的结构比较简单，而且比较规 把，使得它成为解抉_ i ；f 算机视觉问题的怍常有力的并行体系结构。随着v l s i 技术的高速发 艘，它非常适台通过网络互连丽实现。 4 1阵列处理机3 4 1 4 1 1阵列处理机的操作模型 步的并行处理机阵列称为阵列处理机，它州一个控制部件同时管理多个处理单元。 所有处理单元均收到从控制郜仆j 播来的同一条指令，但是操作的对象却是；同的数据。由 j i 阵列处理机能处理单指令多数据流( s i m d ) ，所以阵列处理机也成为s i m d 计算机。 s i m d 计算机的操作摸耻参见幽4 1 ，其中p e 为处理单元，它包括运算处理器p m c 和存储器m e n 两部分。 劁4 is i m d 计算机的模型 s i m d 讨。算机的操作模型叫h j1 i 元组表示：s i m d = ( n ，c ，i ，m ，r ) n 为机器的处理单元数。例如l l l i a e i v 训算机有6 4 个p e ，而m p 1 计算机有1 6 3 8 4 个p e 。 c 为控制部件c u 南接执行的指令集，即标最指令和程序流控制指令。 华东! f | i 范大学计算机系碗二l 学位论文 i 为由c u 广播垒所有p e 进行并行执行的指令集，包括：算术运算、逻辑运算、数据寻径、 屏蔽以及其他由每个p e 对它的数据所执行的局部操作。 m 为屏敝方案集，其中每种屏蔽将所有p e 划分成允许操作和禁止操作两种： 作模式。 r 是数据寻径功能集，说明互连网络中p e 间通信所需要的各种没置模式。 4 1 2 阵列处理机的特点 阵列处理机自以f 特点： 1 阵列机是以单指令流多数据流方式i ：作的。 2 阵州机采州资源重复方法引入空问i 习素，即在系统中设置多个相同的处理单元来开发并 行性，这与利川时间重叠的向量流水线处理机是不一样的。此外它是利崩并行性中的 i 司时性，所何处理单元必须同时进行相同操作。 3 阵列机是以某一类算法为背景的专用汁算机。这是由于阵列机中通常都采用简单、规整 的! j2 连网络求实现处理单7 c 问的近接操作，从而限定了它所适用的求解算法类别。因此 对垃连例络波计的”究就成为阵列机研究的重点之一。 4 阵列 l 的研究必颁与并”算法的研究密切结合，以使它的求解算法的适应性更强一些， 应州面更j 1 。一些。 5 从处理单元来看，由了- 结构都相副，幽而可将阵列机看成是一个同构型并行机。但它的 控制器实质1 是一个标赫处理机，而为了完成i 0 操作以及操作系统的管理，尚需一个 前端机i 川此实际的阵列机系统是由上述三部分构成的一个异构型多处理机系统。 4 1 3 阵列处理机的基本结构 阵别处理机按其雌置u r 分为两类 分布式存储器的阵列机 分布式存储器的s i m d 阵列处理机结构参见图4 - 2 。 它舍青多个司样结构的处理单元j d e ，通过数据寻径网络以一定方式互相连接。每个 p e 有备自的本地存储器l m 。在阵列控制部件的统一指挥下，实现并行操作。程序利数据 毕东师范人学计算机系颧j 学位论文 通过主机装入控制存储器。由1 ：通过控制部件的是单指令流所以指令的执行顺序还是和单 处理机样，基本上是串行处理。 幽4 - 2分布式存储器的s i m d 阵列处理机结构 指令送到控制部件进行洋码。如果趋标量指令，则直接由标量处理机执行。如果是向量 指令，则阵列控制部件通过广播总线将它广播到所有尸_ e 并行执行。 划分| 舌的数据集合通过向量数据总线分布到所有p e 的本地存储器l m 。p e 通过数据 寻往网络且连。数据寻彳寻= 删络执行尸间的通信。控制部件通过执行程序米控制数据寻径刚 络。 p e 的同步由控制部件的顺件实现。也就是说。所有p e 在同一个周期执行同一条指令。 但是i j 以h j 屏敞逻辑来决定任何一个尸e 在给定的指令周期执行或不执行指令。i l l i a ci v 是 这种结构的s i m d 阵列处理机，它由6 4 个带本地存储器的p e 组成j p e 间通过8 8 环绕 连接嘲格实现且连。 e i 猗生产的s i m d 机器儿乎都是基1 二分布式存储器模型的系统。各种s i m d 机器主要差 别在t ：进行尸之问相通信的数据寻径网络各不相同。 1 l i a c i v 中的4 - $ g 连接网格结构 住过土是最常州的种。本章中州到的阵列处理机就是基于此模型。 共享存储器的阵列机 共享存储器的s i m d 阵列处理机结构参见圈4 3 。 华东师范人学计髯：机系城上学位论文 这是集中设置存