1、混合系统中直线去除的形态学哈夫变换摘要本文主要描述在新的平行结构系统混合系统（Hybrid System）中实现新 Huogh 变换主线移除算法。混合系统同时联合处理单指令多数据 (SIMD)和多指令多数据 (MIMD)。用于图像检测线的线移除算法用来去除主线，以使次线可检测变得更容易。在混合系统中实现该算法并进行评估。作为新的扩展结构，我们也相信出自混合系统的加速。我们能够获得超越由同样数量 PC 组成的多指令多数据系统的加速。本文还将介绍一个单指令多数据的新概念。关键字：Hough 变换；SIMD；MIMD；混合；加速；膨胀；腐蚀1. 绪论如今，计算机问题不仅逐渐扩大而且日益复杂。之所以其
2、越来复杂是源于我们努力对事实的描述更精确。如今，就发展速度而言，计算机问题复杂化的发展速度可能已经超出了处理机的科技发展速度。因此利用可行的技术去实现更高性能的系统必需实现。高性能系统可以完成并发处理若干程序。并行处理已经成为解决许多技术领域问题中的一个不可缺少的工具。这些应用领域包括医学,金融学在此仅提出一些。随着处理机日益快速和廉价，并行处理变得更加可行和实际。大部分并行处理机发展到可以注明日期都是基于 Von Neumann 原则。弗林延伸出一种并行处理机的分类法被广泛应用，并且依照如何处理程序指令和数据流来分类计算机6 。我们着手于分类法观念的一体化并且发展出一种适应于多数并行应用的体
3、系结构。这种新的体系机构被成为混合系统，也就是有多指令多数据和单指令单数据组成。为了举例说明这种混合系统功能，我们提出适合这种新结构体系应用的哈夫曼变化。哈夫曼变化9是在图象处理中检测直线的标准方法。它通过将边缘的象素转化为转变为参数，并且将符合直线等式的存储在数组中。由于这种转变在计算上的精确性，所以在技术上从最初的顺序方法到并行方法2,4,5,7,10,15的转变的研究是不足为奇的。在本论文中，我们介绍了一种新的以并行为基础的哈夫曼变化在混合系统上的实施。图 1. 混和系统体系结构(4PE Cluster)2. 一种新的并行体系结构混合系统（4PE cluster）基本上，并行的计算机可以
4、分为三种，即单指令单数据,单指令多数据和多指令多数据。很多研究员曾用过这些并行体系结构去改善计算应用的执行如大量的翻译应用3，11，17.许多并行运算法则都是围绕运用众多分类法中的一种而发展的。他们可以有意义的加速应用性能。Amdahl 1提出了预知诸如此类的并行系统的性能的等式。他的观点随后被以古斯塔夫定律8而闻名的古斯塔夫加以评价。我们已将这种并行体系结构的观点扩充，结合了单指令多数据以及多指令多数据的并行体系结构，我们称之为混合系统。本质上，混合系统是一种新形式的并行体系结构，是单指令单数据和多指令多数据系统共同工作的结合。这种混合系统最好的应用在功能并行和数据并行的展示道具上。功能并行
5、的任务包括复杂的需要高级处理机的并行代码的执行，且最好在个人计算机上处理。而数据并行的任务包括简单的可以独立计算的数据的处理且最好在单指令多数据时处理。混合体系结构这种观念可以利用现成的成分和标准的成分，因此很容易主张实现低成本的硬件。混合系统可以有不同的组合和一些节点组成。我们研究一混合系统的原型并且命名为 4PE Cluster。从命名可以表明 4PE Cluster 包括使用 4 台个人计算机通过网络连接一起(如图 1)。每台计算机 Systola1024 芯片为粒度安置14,16 这个会在论文第三章节中做更细致的讨论。这些计算机是在Windows NT 平台上运行的相同的系统，而且它们
6、之间的网络连接是通过高速以太网。交互计算机的通信是通过使用 MPI。我们使用了一个新的 Windows NT 兼容的 MPI 软件 PaTENT MPI，它可以适应 MPI_2 信息传递的标准。信息的传递程序是连续的代码且基本上是一个通信库。它易于网络中平行安放的程序运行于多样的处理器。2.1 设立混合系统的加速象所有的并行体系结构一样，它在建立 SIMD 对混合系统的贡献的连接上是有用的。在投资之前决定混合加速的公式对于预知期望的性能是有帮助的。并行处理的加速通常是应用前和后的方法来决定的。换句话说，加速是实现并行处理前后的处理时间的度量。在 MIMD 体系结构和 Gustadsons la
7、w4中，加速可以表示为(1)TpsNSpedu)(Ts 是指连续的处理时间，Tp 并行的处理时间，N 是指 MIMD 处理机的数目。在混合系统的前后关系中，处理时间 Tp 可以更深的细分为就 SIMD 系统而言连续的和并行处理的组合，假设每个 SIMD 系统对 MIMD 机器而言是同质的，也就是拥有相同的处理速度并且在一关口完成 SIMD 必需的任务。 （1）式可以改写为21)(TPNsSpeduSHytir(2)21s其中，T1 是对 SIMD 而言连续的处理时间，T2 是对 SIMD 而言以 MIMD的速度所用的并行处理时间。P 是 SIMD 处理机的数目。在此，我们在分子中用 T1+PT
8、2 来代替 Tp，分母也就是，混合系统的总的处理时间是有 SIMD 和 MIMD 的连续时间和 SIMD 系统下的并行时间之和（也就是 TsT1+T2） 。然而，加速等式（ 2）已假定 SIMD 和 MIMD 拥有相近的处理性能。这是不太可能实现的。以我们的混合 4PE 模型为例，SIMD 是而 MIMD 是运行在 Windows NT 下的计算机，而且都拥有不同水平的执行效率。SIMD 的执行效率主要有 SIMD 的处理速度也就是代码的简洁。这是因为 SIMD系统，代码设计需要同多数 SIMD 体系结构一样的低级编程语言。差异比例x，是满足 SIMD 和 MIMD 处理速度的差异的条件也就是
9、代码从 MIMD 转化到SIMD 的条件。这种在数个 SIMD 处理机中的差异形成了参数 P，我们可以通过 MIMD 系统和 SIMD 系统运行相同的代码所用时间而得。如果 SIMD 与MIMD 有相同的性能，则这个比率为 1。仔细分析，我们可以确定运行时间 T2 实际上等于 SIMD 运行的总时间和转换速率的乘积。我们可以等同为如下：T2=XTsimd (3)转换比率 X 是 MIMD 运行相同代码的处理时间与 SIMD 处理的时间而得，Tsimd 是 SIMD 的总的处理时间。混合系统中程序所用的总的时间等于 MIMD 系统所用的连续时间和 SIMD 用的并行时间。我们可以的到混合系统的加
10、速公式如下：（4）simdsHybirdTXNPSpeu1)(图 2 The Systola 1024 数组结构3. 数组指令的概念在混合系统中，目前有好的和粗糙的两种粒度的工作方式。SIMD 提供了精细粒度方面的工作。在我们所涉及的问题中，SIMD 就是 Systola 1024，也就是我们所知道的指令驱动数组处理器。这对标准的 PC 而言是的成本的，然而，设计这种并行计算机相对于高级语言而言是个挑战，The Systola 102418是同样处理机的二次 3232 数组且每个都与四个直接相邻的相联系。这些同类数组处理机由 44 的处理机碎片组成如图 2（a）所示。这个数组与球形时钟同步。处
11、理机数组的数据交换时，有成行的智能记忆的单元，它们位于数组的北边和西边的边缘。这些单元称为界面处理机(Ips).这些 Ips 中北边的界面芯片与北边的 RAM 相连，西边的界面芯片与西边的 RAM 相连，北边和西边的 RAM 与PC 通过 PCI 互相通信，每两个存储单元数据的传输都是有一个控制芯片来控制。这个存储器的大小是 32 个内在的寄存器和一个外部寄存器。数据的一个字的长度为 16 比特。指令的设定和内部数据的形式都定义为整数和浮点数来解决算术问题。处理机受指令控制，成行的选择器和输入位于处理机数组的左上角处且它们在水平和垂直方向逐步移动。选择器通过数组来移动，成行的选择器水平的从左移
12、向后边，纵队的选择器从顶部移动倒底部。选择器处理机指令的执行，也就是说当且仅当当前处理器中的两个指定位都等于 1 时指令才执行，否则，执行空操作。这个结论引出一个灵活的结构，它使有效率的解决大量不同的应用问题成为可能，举例来说数字，密码学，图像处理11，14 ，在图 3 中，图像表明两个连续的指令和行列的指令位都已激活。较低的图形描述了指令的执行在开始的前四个周期，每个处理机通过读写访问自己的存储器，除此之外，它还有个通信的寄存器可以被相邻的四个处理机访问。CNORTH,C WEST,CSOUTH,CEAST表明了处理机的通信寄存器的四个相邻的部分如图 2（b） 。两个邻近的处理机可以通过写在
13、自身的通信寄存器交换数据然后可以在随后两个时钟段读取其余通信寄存器的内容。这个协定避免了读写冲突且为通过一个指令或恒定数量的指令来完成总和函数提供了可能，处理机数组上的总和函数是联合的且每个处理机对交换函数提供一争论值。由于它们是可交换的和联合的，总和函数可以以不同的方式来评价。ISA 支持从上而下的纵向操作和从左至右的横向操作，源于指令的流程而定。因此一个总和函数例如 Row Sum 和 Column Sum 操作可以在 ISA 上执行。这在后续会进行讨论。另外一些可以在 ISA 上执行的重要的操作是横传播（左右）和纵传播（上下） 。图 3.ISA 的控制流程行传播：每个处理机从它的左边读得
14、值。通过横向的途径执行操作，在通信寄存器之间传递相同的值，直到它达到最右边的处理机。要注意行传播仅需一个指令。一个纵向的传播也是以同样的方式，除了它是从顶到底之外。行数：在行数操作中，每个处理机计算其本身和左边的相邻的通信寄存器的总数。既然完成指令的操作是通过横向的管道，每个处理机直到集聚了在最右边处理机的总数以后才从左至右的集聚通信寄存器的数目。纵数也是以相同的方式完成，除了它是从顶到底以外。4. 哈夫变换哈夫变换是用来检测直线的。当边探测器发现边时，就将边上的点存储起来，然后在探测所有的和这些已发现的点相邻接的点。直线将用 和 来表示。 是原点到直线的垂线段距离， 是轴到垂线段的角度。如
15、4 图所示：图 4 Hough 变换当 在 0 到根号 S 之间时， 的取值范围在-90 到+90 度之间（S 是图形面积的大小） 。接着我们取得以 为坐标轴的空间，然后将其量化。量化的方法如下：将图形空间划分成带有明确编码的块，每一个块对应 XY 坐标系下的一条直线或一组直线， 是在以块大小为增量的范围内变化。块的大小对应着量化的粗糙程度。例如：大量的块提供较少的。当程序被执行时，每个块的采样数对应着 坐标系中这个块中的直线上的像素点。哈夫变换的简单表示如下：for i=0 to image_heigh-1dofor j=0 to image_width-1do if( imagei,j=1
16、)for k=0 to M-1doincrement count(Mk, nearest_int(j-i*k/M); 对于一条直线，一个像素在（X，Y）处，直线的斜率为 M，截距为 C 那么他就可以量化为 Y=MX+C。哈夫变换包括量化一个范围内的两个参数的值和定义一个存储数组，来对斜率 Mk 和截距 Ck 进行记数。对每一个黑色的像素P（X，Y）和一个斜率 Mk 的对应的 Ck 是可以被计算出来的，Ck 被校正为一个最接近计算值的整数。这个整数的计算机方法可以是对计算值加上 0.5 然后在四舍五入为一个 整数。总之，这个算法搜索出所有可能与此黑色像素点对应的的直线。之后计数数组 countM
17、k,Ck增加。这些数组中最大的那些计数值则是这个被检测图像中的直线的斜率和截距。这个检测出的直线的斜率和截距分别是 Mk,Ck。5.形态学哈夫变换的直线移除我们将图像影射在 P 坐标系下，而不是通常的 坐标系下。P 是假想直线的起点到图像参考点之间的像素距离， 是假想直线与 Y 轴的夹角。如下图所示：图 6. P 和角度 的计算在混合系统上执行快速哈夫变换，是为了使用混合结构的优点。我们已经可以在混合系统上用逼近的方法去搜索直线，这种逼近的方法就称为形态学哈夫变换的直线移除这样，我们可以将原始图像分割成 32*32 的子图像，使其与Systola 1024 的处理器相符合。来自主站的子图像被分
18、配给每一个MIMD 系统，通过MIMD 系统，这些子图像的像素被重新排列，并载入SIMD用来进行计算。 我们计算MLRMHT 空间的运算法则 1 有四个步骤,即:1. 运行图像裁剪；2. 利用膨胀和腐蚀来操作图形框架；3. 完成数组计数；4. 去除框架；载入子图像的像素值到SIMD ；For Angle = 0 to 4 5 degrees/如果角度在 0到 45度之间做一下步骤 For every pixel in the sub-image/对于子图像中的每一个像素执行 Compute pixel angle (pix_angle) for each column from the bot
19、tom row;/为每一组数据计算像素的角度Subtract the Angle from the pix_angle;/从计算值中减去Angle的值；If the result is positive/如果结果是正数； Shift the pixel to left;/像素点向左移动Perform Morphological operation;/执行 Morphologica操作；Perform a column sum checked;If the column sum checked is above threshold value/如果数组中数据的和大于阕值； Take note o
20、f the angle and the number of pixels;/对角度和像素的个数做记号Remove the major vertical line;去处主要的垂直线5.1. 图像裁剪裁剪操作是从左到右或从右到左滑动图像的一个边缘，藉此在程序中创造一个平行四边形。我们的目的是使用裁剪操作把斜线变成垂直的直线。斜线变成垂直线之后，其倾斜度可以通过剪切角测定。藉由移动黑色象素到左边在 Systola 1024 中完成裁剪，也就是在顶部的象素比底部的移动更多。这可以通过将 C 寄存器象素值传递到 CWEST寄存器来完成。在 0 到 /4 弧度范围计算每次裁剪操作。/4 到 则要在图像裁剪前翻转和旋转完成操作（见图7） 。通过翻转和旋转可以得到- 到 弧度的剪切角。对象素矩阵取逆实现翻转而旋转可以通过矩阵转置完成。
