混合系统中直线去除的形态学哈夫变换

1、混合系统中直线去除的形态学哈夫变摘要本文主要描述在新的平行结构系统混合系统(HybridSystem)中实现新Huogh变换主线移除算法。混合系统同时联合处置单指令多数据(S1MD)和多指令多数据(MIMD)o用于图像检测线的线移除算法用来去除主线，以使次线可检测变得更易。在混合系统中实现该算法并进行评估。作为新的扩展结构，咱们也相信出自混合系统的加速。咱们能够取得超越由一样数量PC组成的多指令多数据系统的加速。本文还将介绍一个单指令多数据的新概念。关键字：Hough变换；SIMD；MIMD;混合；力口速；膨胀；侵蚀1 .结论现在，运算机问题不仅逐渐扩大而且日趋复杂。之所以其越来复杂是源于咱们

2、尽力对事实的描述更精准。现在，就进展速度而言，运算机问题复杂化的进展速度可能已经超出了处置机的科技进展速度。因此利用可行的技术去实现更高性能的系统必需实现。高性能系统能够完成并发处置若干程序。并行处置已经成为解决许多技术领域问题中的一个不可缺少的工具。这些应用领域包括医学，金融学在此仅提出一些。随着处置机日趋快速和廉价，并行处置变得加倍可行和实际。大部份并行处置机进展到能够注明日期都是基于VenNeumann原则。弗林延伸出一种并行处置机的分类法被普遍应用，而且依照如何处置程序指令和数据流来分类运算机同。咱们着手于分类法观念的一体化而且进展出一种适应于多数并行应用的体系结构。这种新的体系机构被

3、成为混合系统，也就是有多指令多数据和单指令单数据组成。为了举例说明这种混合系统功能，咱们提出适合这种新结构体系应用的哈夫曼转变。哈夫曼转变9是在图象处置中检测直线的标准方式。它通过将边缘的象素转化为转变成参数，而且将符合直线等式的存储在数组中。由于这种转变在计算上的精准性，所以在技术上从最初的顺序方式到并行方式2,4,5,7,10,15的转变的研究是不足为奇的。在本论文中，咱们介绍了一种新的以并行为基础的哈夫曼转变在混合系统上的实施。NetworkFig.1.Hybridarchitectui,e(4PECluer).图1.混和系统体系结构(4PECluster)2 .一种新的并行体系结构一混

4、合系统(4PE-cluster)大体上，并行的运算性能够分为三种，即单指令单数据，单指令多数据和多指令多数据。很多研究员曾用过这些并行体系结构去改善计算应用的执行如大量的翻译应用3,11,17.许多并行运算法则都是围绕运用众多分类法中的一种而进展的。他们能够成心义的加速应用性能。Amdahl1提出了预知诸如此类的并行系统的性能的等式。他的观点随后被以古斯塔夫定律网而著名的古斯塔夫加以评价。咱们已将这种并行体系结构的观点扩充，结合了单指令多数据和多指令多数据的并行体系结构，咱们称之为混合系统。本质上，混合系统是一种新形式的并行体系结构，是单指令单数据和多指令多数据系总一路工作的结合。这种混合系统

5、最好的应用在功能并行和数据并行的展示道具上。功能并行的任务包括复杂的需要高级处置机的并行代码的执行，且最好在个人运算机上处置。而数据并行的任务包括简单的能够独立计算的数据的处置且最好在单指令多数据时处置。混合体系结构这种观念能够利用现成的成份和标准的成份，因此很容易主张实现低本钱的硬件。混合系统能够有不同的组合和一些节点组成。XX咱们研究一混合系统的原型而且命名为4PECluster。从命名能够表明4PECluster包括利用4分个人运算机通过网络连接一路(如图1)。每台运算机SystolalO-24芯片为粒度安置14,16那个会在论文第三章节中做更细致的讨论。这些运算机是在WindowsNT

6、平台上运行的相同的系统，而且它们之间的网络连接是通太高速以太网。交互运算机的通信是通过利用MPI。咱们利用了一个新的WindowsNT兼容的MPI软件PaTENTMPL它能够适应MPI_2信息传递的标准。信息的传递程序是持续的代码且大体上是一个通信库。它易于网络中平行安放的程序运行于多样的处置器。设立混合系统的加速象所有的并行体系结构一样，它在成立SIMD对混合系统的奉献的连接上是有效的。在投资之前决定混合加速的公式对于预知期望的性能是有帮忙的。并行处置的加速一般是应用'前和后'的方式来决定的。换句话说，加速是实现并行处置前后的处置时刻的气宇。在MIMD体系结构和Gustads

7、on，slaw4中，加速能够表示为Ts+N(Tp)Speedup=-(1)Ts+TpTs是指持续的处置时.刻,Tp并行的处置时刻，N是指MIMD处置机的数量。在混合系统的前后关系中，处置时刻Tp能够更深的细分为就SIMD系统而言持续的和并行处置的组合，假设每一个SIMD系统对MIMD机械而言是同质的，也就是拥有相同的处置速度而且在一关口完成SIMD必需的任务。(1)式能够改写为Speedupllylird =Ts+N（Z +P）Ts +4 +72Ts+NT、+NPT27+T1+T,其中，T1是对SIMD而言持续的处置时刻，T2是对SIMD而言以MIMD的速度所用的并行处置时刻。P是SIMD处置

8、机的数量。在此，咱们在分子顶用T1+PT2来代替Tp,分母也就是，混合系统的总的处置时刻是有SIMD和MIMD的持续时刻和SIMD系统下的并行时刻之和（也就是Ts+Tl+T2）。但是，加速等式（2）已假定SIMD和MIMD拥有相近的处置性能。这是不太可能实现的。以咱们的混合4PE模型为例，SIMD是XXX而MIMD是运行在WindowsNT下的运算机，而且都拥有不同水平的执行效率。SIMD的执行效率主要有SIMD的处置速度也就是代码的简练。这是因为SIMD系统，代码设计需要同多数SIMD体系结构一样的低级编程语言。不同比例x,是知足SIMD和MIMD处置速度的不同的条件也就是代码从MIMD转化

9、到SIMD的条件。这种在数个SIMD处置机中的不同形成了参数P,咱们能够通过MIMD系统和SIMD系统运行相同的代码所历时刻而得。若是SIMD与MIMD有相同的性能，则那个比率为1。仔细分析，咱们能够肯定运行时刻T2实际上等于SIMD运行的总时刻和转换速度的乘积。咱们能够等同为如下：T2=XTsimd（3）转换比率X是MIMD运行相同代码的处置时刻与SIMD处置的时刻而得，Tsimd是SIMD的总的处置时刻。混合系统中程序所用的总的时刻等于MIMD系统所用的持续时刻和SIMD用的并行时刻。咱们能够的到混合系统的加速公式如下：s.Ts+NT+NPXTq仆Speedupllvbird=亍亍（4）1

10、+1controllerPCI busCNORTHISAboard RAM northFig. 2. The Stoh 1024 stray etnictiu-a.QWEST一QSOUTHCEAST图2TheSystola1024数组结构3 .数组指令的概念在混合系统中，目前有好的和粗糙的两种粒度的工作方式。SIMD提供了精细粒度方面的工作。在咱们所涉及的问题中，SIMD就是Systola1024,也就是咱们所明白的指令驱动数组处置器。这对标准的PC而言是的本钱的，但是，设计这种并行运算机相对于高级语言而言是个挑战，TheSystola102418是一样处置机的二次32X32数组且每一个都与四

11、个直接相邻的相联系。这些同类数组处置机由4X4的处置机碎片组成如图2(a)所示。那个数组与球形时钟同步。处置机数组的数据互换时，有成行的智能记忆的单元，它们位于数组的北边和西边的边缘。这些单元称为界面处置机(Ips).这些Ips中北边的界面芯片与北边的RAM相连，西边的界面芯片与西边的RAM相连，北边和西边的RAM与PC通过PCI彼此通信，每两个存储单元数据的传输都是有一个控制芯片来控制。那个存储器的大小是32个内在的寄放器和一个外部寄放器。数据的一个字的长度为16比特。指令的设定和内部数据的形式都概念为整数和浮点数来解决算术问题。处置机受指令控制，成行的选择器和输入位于处置机数组的左上角处且

12、它们在水平和垂直方向慢慢移动。选择器通过数组来移动，成行的选择器水平的从左移向后边，纵队的选择器从顶部移动倒底部。选择器处置机指令的执行，也就是说当且仅铛铛前处置器中的两个指定位都等于1时指令才执行，不然，执行空操作。那个结论引出一个灵活的结构，它使有效率的解决大量不同的应用问题成为可能，举例来讲数字，密码学，图像处置11,14,在图3中，图像表明两个持续的指令和行列的指令位都已激活。较低的图形描述了指令的执行在开始的前四个周期，每一个处置机通过读写访问自己的存储器，除此之外，它还有个通信的寄放器能够被相邻的四个处置机访问。CNORTH,CWEST,CSOUTH,CEAST表明了处置机的通信寄

13、放器的四个相邻的部份如图2（b）。两个临近的处置性能够通过写在自身的通信寄放器互换数据然后能够在随后两个时钟段读取其余通信寄放器的内容。那个协定避免了读写冲突且为通过一个指令或恒定数量的指令来完成总和函数提供了可能，处置机数组上的总和函数是联合的且每一个处置机对互换函数提供一争辩值。由于它们是可互换的和联合的，总和函数能够以不同的方式来评价。ISA支持从上而下的纵向操作和从左至右的横向操作，源于指令的流程而定。因此一个总和函数例如RowSum和ColumnSum操作能够在ISA上执行。这在后续会进行讨论。另外一些能够在ISA上执行的重要的操作是横传播（左右）和纵传播（上下）。L.C.Simer

14、al./JRirallclDisnib.Cwrrpui.64(2G04lIQoQ-iOoSFig.3.Controlflowm.anISA.图的控制流程行传播：每一个处置机从它的左侧读得值。通过横向的途径执行操作，在通信寄放器之间传递相同的值，直到它达到最右边的处置机。要注意行传播仅需一个指令。一个纵向的传播也是以一样的方式，除它是从顶到底之外。行数：在行数操作中，每一个处置机计算其本身和左侧的相邻的通信寄放器的总数。既然完成指令的操作是通过横向的管道，每一个处置机直到集聚了在最右边处置机的总数以后才从左至右的集聚通信寄放器的数量。纵数也是以相同的方式完成，除它是从顶到底之外。4 .哈夫变换哈

15、夫变换是用来检测直线的。当边探测器发觉边时，就将边上的点存储起来,然后在探测所有的和这些已发觉的点相邻接的点。直线将用p和o来表示。p是原点到直线的垂线段距离，0是轴到垂线段的角度。如4图所示：Fig.4.Houghtransform.图4Hough变换当P在0到根号S之间时，0的取值范围在-90到+90度之间(S是图形面积的大小)。接着咱们取得以P0为坐标轴的空间，然后将其量化。量化的方式如下:将图形空间划分成带有明确编码的块，每一个块对应XY坐标系下的一条直线或一组直线，P0是在以块大小为增量的范围内转变。块的大小对应着量化的粗糙程度。例如：大量的块提供较少的。当程序被执行时，每一个块的采

16、样数对应着P。坐标系中那个块中的直线上的像素点。哈夫变换的简单表示如下：fori=0toimage_heigh-ldoforj=0toimage_width-ldoif(imagei,j=l)fork=0toM-ldoincrementcount(Mk,nearest_int(j-i*k/M);对于一条直线，一个像素在(X,Y)处，直线的斜率为M,截距为C那么他就可以够量化为Y=MX+C。哈夫变换包括量化一个范围内的两个参数的值和概念一个存储数组，来对斜率Mk和截距Ck进行记数。对每一个黑色的像素P(X,Y)和一个斜率Mk的对应的Ck是能够被计算出来的，Ck被校正为一个最接近计算值的整数。那个

17、整数的运算机方式能够是对计算值加上然后在四舍五入为一个整数。总之，那个算法搜索出所有可能与此黑色像素点对应的的直线。以后计数数组countMk,Ck增加。这些数组中最大的那些计数值则是那个被检测图像中的直线的斜率和截距。那个检测出的直线的斜率和截距别离是Mk,Cko5.形态学哈夫变换的直线移除咱们将图像影射在P坐标系下，而不是通常的p。坐标系下。P是假想直线的起点到图像参考点之间的像素距离，中是假想直线与Y轴的夹角。如下图所示：Fig.6.Computingpandanal-e图6.P和角度中的计算在混合系统上执行快速哈夫变换，是为了利用混合结构的长处。咱们已经能够在混合系统上用逼近的方式去搜

18、索直线，这种逼近的方式就称为形态学哈夫变换的直线移除如此，咱们能够将原始图像分割成32*32的子图像，使其与Systola1024的处置器相符合。来自主站的子图像被分派给每一个MIMD系统,通过MIMD系统，这些子图像的像素被从头排列，并教入SIMD用来进行计算。我们计算MLRMHT空间的运算法则1有四个步骤，即：1 .运行图像裁剪；2 .利用膨胀和侵蚀来操作图形框架；3 .完成数组计数；4 .去除框架；载入子图像的像素值到S/MO；ForAngle=0to45degrees图像裁剪裁剪操作是从左到右或从右到左滑动图像的一个边缘，藉此在程序中创造一个平行四边形。咱们的目的是利用裁剪操作把斜线变

19、成垂直的直线。斜线变成垂直线以后，其倾斜度能够通过剪切角测定。希山移动黑色象素到左侧在Systola1024中完成裁剪，也就是在顶部的象素比底部的移动更多。这能够通过将C寄放器象素值传递到QWEST寄放器来完成。在0到八/4人弧度范围计算每次裁剪操作。冗/4到五则要在图像裁剪前翻转和旋转完成操作（见图7）。通过翻转和旋转能够取得-五到n弧度的剪切角。对象素矩阵取逆实现翻转而旋转能够通过矩阵转置完成。(b)Flip ImageverticallyRotate linas-e by 倡 2 CCWSheared Imagefig.7.Shearingofanglesfrom0tojc/2:(a)S

20、lieariitgfbiangles0to丸/4;(b)Shearingforanglestox«4to欣2.After ErosionFig.S.Moiphologicaloperarioiis,dilationanderosion.形态学运算在主线上的应用膨胀和侵蚀是两种最普通的形态学运算。形态学在图像处置和图像分析上的应用很多2。通过裁剪以后，常常观测到并非所有象素排列在一条垂直线上。当某些象素改变超过其他象素时，垂直线上就会缺少一些象素。现在，就可以够就可以利用膨胀和侵蚀操作来减少这种现象。在图像处置全进程，咱们通过利用一种固定的结构元素实现那个一匚作。在膨胀（见到图8）处置

21、进程中，用一种结构元素来匹配图像的式样。这种结构元素只是简单的形状小组。咱们仅仅把元素用来表示主线不可信的列。主线就是象素从边缘的一边向另一边的延伸。列总数测试能通过检查每次裁剪后列的总数值是不是大于阀值来肯定一条主线存在的可能性。膨胀和侵蚀的形态学运算只对主线不可信的列起作用。在膨胀处置时，若是参考象素是白色，就要对毗连象素进行测试。万一它也是相同于结构的元素，然后将参考象素设成黑色。另外它的左侧是不变的。侵蚀处置III经裁剪的图像匹配结构元素开始。若是结构元素的所有象素和图像一样，就将它的毗连象素设成白色。.主线移除主线一旦被定位，就将其从经裁剪的图像中删除掉。主线记录在Hough空间只有

22、当它们抵达Y轴位置时才被删除。主线移除的作历时预防做进一步裁剪时这些主线弄乱已裁剪图像中的次线。通过不可信主线的列的“与”操作能够删除这些线。主线移除对这些线在裁剪时弄乱次要线的预防效果如图9所示。Before line remoral. Both major and minor line exists.After line removaL only minor line rematnFig.9.Majorlineremoval.列总数列总数运算与第3节的行总数运算相似。它大体上是由图像网格每一列的黑色象素的数量取得。那个运算就是将本次自身值加上之前所有处置器取得的总数累加值传递到下一处置器。

23、在列的所有处置器的总数都被计算过之前这一进程将反复进行6.实验结果图io解释了一张图象中一些线的检测。左侧的图显示的是图象中将要被检测的一些线,而右边的图显示/thecolumnsumofthetakenatvariousangles.（实在不明白是什么意思）。当剪切的角接近线的正确的角时，更多的像素排列成线而且这说明了积累器中有更大的数。在图10（b）中，积累器的值相对地转换成从白到黑的灰度值范围。越黑的点说明那个角积累的像素点越多。当一条主要的线被检测出来，它将从正在修剪的图象中被删除，以避免它对次要的线造成干扰。在图中线a-e是主要线因为它们从一个边缘跨越到另一个。主要线之下的区域通常超

24、级清楚（凫色），因为它们被检测后当即被删除。像f和g（被圈住的）如此的次要的线是抛物线收缩检测出的，如图所示。从g能够看出，检测次要线的特性是它在展开成为较克灰度（像素点队列的散布）前逐渐变细成为一个较深色的点（像素点队列）。主要线移除算法的主要长处是它使得主要线能够容易检测的同时一些较长的次要线也能够容易地检测。Fig.10.ofspace3Pmajor：5morphologicalHougktraziixbnx;(a)Originalimagecoutaimagseveral,iziajoranduuuoilines;(b)TheHoughspacemapofangleandp.图11（a

25、）是一个64X64像素的图，显示了印制电路板的一部份；图11（b）显示了对该图进行边检测操作的结果；图11（c）显示了对0。到45°角，positiveP应用形态哈夫变换主要线去除方式后的线。那个算法能够提掏出所有主要线和大部份较长次要线。但是，检测出很短的次要线仍是很困难的。处置短的倾斜的次要线的方式的改良还有专门大余地。Fig11.RjeaultofmajorlineremovalmaipholosicalHoughtiansibimalsoiLtlim:(a)oriEinalimage;(b)edeumse;(c)resultofourmajorline起aova工orphob

26、鼠calHT.表1显示了64X64像素图象的标准哈夫变换（HT）算法和MLRMHT算法的申行处置时刻。虽然标准的哈夫变换处置略微快一些，它的执行却是不稳固的。标准的哈夫变换依赖于图象中的黑色像素的数量。图象中的黑像素越多，所需的计算越多。这意味着处置时刻是转变的而且依赖于图象的复杂度和大小。MLRMHT方式有如此的长处：它不依赖于黑像素的数量，所以产生了稳固的多的处置时刻。表2显示了用不同的PC执行MLRMHT方式的结果。在4PC（4PE串行）的混合系统中，64X64像素图象被分成32X32像素的4张图象。处置时刻包括从PC到Systola1024和viceversa的数据传输时刻。FC运行在

27、333MHz频率下而Systola1024的时钟频率是50MHZ。1PC上的串行运行是在没有任何Systola1024卡的PC上的算法串行处置时刻而相邻列显示了带有Systola卡的一个PC并行系统上的处置和带有Systola卡的四个PC并行系统上的处置结果。由于相对较短的处置时刻，时刻是通过运用很多循环取得的。基于Gustafson定律，表2所示的从混合系统（4PE串）中取得的加速能够超过从相应的MIMD系统中取得的加速，这归因于SIMD因素的奉献。运用从SIMD取得的增强的执行能力，如处置器数量的增加或更高的时钟频率，更显著增加的执行加速是值得期待的13o虽然咱们此刻的SIMD卡还处于它的原型阶段，咱们已经有计划来进一步增强它的性能。表3显示了当运用4PE用时处置时刻的缩短。替换了（4）中来源于混合系统中的新的加速方程的参数，咱们取得了预想的加速。相较较下，那个预想的加速相对接近于气宇的加速。Table1ProcwiwizzgTimefbra54x64inagwkuig口口ndxd五TQidXELRLtHTMLRMHTStandardHTSeqg疝alpiece:】i皿庶Q11s0075Table2Speedupcompaiioaionprocesin?tunefbr6+x64imageusingML-RMHTMLIET1PC1PCwi+4PCswxtk