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

Abstract

本論文對鬆弛演算法提出系統性的探討。首先，我們以新的方式推導出一組相容係數 ，並且運用線性方向罩的運算子以改進傳統的鬆弛演算過程。其次，我們設計了一套 具有彈性化的平行架構，適合於機率式及離散式鬆弛法應用時的平行運算。 關於鬆弛運算法方面，所提出的相容函數能簡單精確的統計出具有線性化的一組相容 係數，以改進偏極化的現象。採取線性方向罩為導向的運算式，加強了包含有線條形 狀的影像的處理效果。我們將這兩種新的方法試驗於一組含有字型圖的二值化分割應 用，並且和其他種演算法相互比較，證實新的方法對於線條形狀的影像處理具有均勻 化，快速收斂，同時能保留原有線條特徵的優良性。 關於平行運算架構之研究，我們首先將鬆弛法的運算過程分成韻律式、同步式及導管 式等三部分加以詳細分析。經過適當的位置及時間上的安排，全部的運算過程可以套 入一個新設計的線性陣列式韻律架構中做高速的平行處理，不會有影像資料流通瓶頸 的現象發生。陣列內的運算單元是採取一次元及單向傳輸的方式，同時和外界的界面 僅需一組簡單的輸出╱輸入端，所以設計的結果非常適合超大型積體電路的製作。因 為硬體的單純化及運算單元的可程式化，我們的平行架構可以彈性的運用於不同的鬆 弛演算法。在這篇論文中，我們分別探討在二維影像應用中的機率模式鬆弛法及在標 示應用中的機率和離散模式鬆弛法，並將平行執行的效益和其他現行架構相互比較。