鬆弛演算法與其平行計算模式之探討

Abstract

This dissertation is concerned with systematic approach to relaxation algorithms and parallel computation models. In the first part, a new formula to derive the compatibility coefficients and a new updating scheme of the relaxation process are addressed. In the second part, the flexible parallel architectures for computing both probabilistic relaxation operations and discrete relaxation labeling algorithms are studied. In deriving the new set of compatibility coefficients, the fundamental characteristics of coefficients are listed as the guidelines. The new formula is easy to compute and it is unbiased in connection with the minority-dominant problem. Besides, a new modified relaxation updating scheme based on line masks to enhance the line-shaped image thresholding is proposed. A feasibility study of this method is demonstrated on a set of different types of character patterns, along with the evaluation of performance measures to evalutat the results with respective to other existing methods. We conclude that the new approach has good characteristics such as better smoothness in the presence of noise, fast convergence rate and unbiaseness without minority-dominant effect. For the parallel computation model of the relaxation process, the computation is divided into three different parallel operations. i.e. systolic, simultaneous and pipelined. Through proper space-time arrangement of computation steps, these operations are mapped to a new linear systolic array architecture that runs smoothly without any bottleneck in the data flows. Thus a high degree of computation parallelism is attainable. The arrays use one-dimensional, one-way communication lines between adjacent PEs and communicate with the external environment through a single I/O port. The architecture is suitable for VLSI implementation. Because of the hardware simplicity and programmability features of PEs, the architecture is also flexible enough to execute different relaxation algorithms. In this dissertation, the probabilistic relaxation operations on two dimensional images, probabilistic and discrete models of relaxation labeling algorithms are addressed. The performance comparisons between the proposed architecture and the other existing ones are presented in some details. 本論文對鬆弛演算法提出系統性的探討。首先，我們以新的方式推導出一組相容係數 ，並且運用線性方向罩的運算子以改進傳統的鬆弛演算過程。其次，我們設計了一套 具有彈性化的平行架構，適合於機率式及離散式鬆弛法應用時的平行運算。 關於鬆弛演算法方面，所提出的相容函數能簡單精確的統計出具有線性化的一組相容 係數，以改進偏極化的現象。採取線性方向罩為導向的運算式，加強了包含有線條形 狀的影像的處理效果。我們將這兩種新的方法試驗於一組含有字型圖的二值化分割應 用，並且和其他種演算法相互比較，證實新的方法對於線條形狀的影像處理具有均勻 化，快速收斂，同時能保留原有線條特徵的優良性。 關於平行運算架構之研究，我們首先將鬆弛法的運算過程分成韻律式、同步式及導管 式等三部分加以詳細分析。經過適當的位置及時間上的安排，全部的運算過程可以套 入一個新設計的線性陣列式韻律架構中做高速的平行處理，不會有影像資料流通瓶頸 的現象發生。陣列內的運算單元是採取一次元及單向傳輸的方式，同時和外界的界面 僅需一組簡單的輸出╱輸入端，所以設計的結果非常適合超大型積體電路的製作。因 為硬體的單純化及運算單元的可程式化，我們的平行架構可以彈性的運用於不同的鬆 弛演算法。在這篇論文中，我們分別探討在二維影像應用中的機率模式鬆弛法及在標 示應用中的機率和離散模式鬆弛法，並將平行執行的效益和其他現行架構相互比較。