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

Abstract

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