二值影像距離轉換之平行計算法則與架構：沒有限制條件與有限制條件狀況

Abstract

距離轉換在影像處理上是一個十分重要的函數，其可分成兩類：沒有限制 條件的距離轉換和有限制條件的距離轉換。這兩種距離轉換到目前為止都 尚未有一個有效率的平行演算法則及架構提出，此外所提出的方法中就循 序方法而言，處理時間則無法達到即時要求。本論文的重點在針對沒有限 制條件的距離轉換和有限制條件的距離轉換各提出一個平行計算法則和相 對應的硬體架構。就沒有限制條件距離轉換而言，此法則利用由左上至右 下掃描以及由右下至左上掃描兩個平行步驟將距離值求出，其執行時間能 夠達到即時處理的要求，且執行的時間是固定的，即處理時間和處理的影 像圖形具有資料獨立性。所提出的架構是一以管線﹙ Pipeline ﹚輸 入的心臟壓縮式陣列﹙ Systolic Array ﹚，此一架構的處理單元﹙ PE )個數是 n﹙影像大小為 n*n ﹚，處理單元內部的硬體設計亦十分簡單。 就有限制條件的距離轉換部分，主要是利用沒有限制條件距離轉換的基本 概念及其硬體架構發展出來。經由此方法可使得有限制條件的影像圖形距 離轉換能在即時時間的要求下完成距離值轉換，且對於一般簡單的影像圖 形的執行時間幾乎和沒有限制條件的距離轉換執行時間相去不遠，其硬體 架構內處理單元個數是n ，處理單元內部的硬體設計亦十分簡單。由此方 法的提出，可使得許多建構在距離轉換的應用能夠突破處理時間上的瓶頸 ，且利用本論文所提出的簡單硬體架構設計其所需要的功能。 Distance transformation operation is a very important function in image processing, it can be further divided into two classes: distance transformation without constraints and distance transformation with constraints. The existing algorithms for distance transformation operation without constraints only give approximate results and are not suitable for real time implememtation, since they require N*N PE's( N*N is the total number of pixels) for massive parallelism. There are no existing algorithms for distance transformation operation with constraints. Thus, there are no real time implementation, either. We shall present parallel algorithms and parallel architectures for computing distance transformation with and without constraints. Our methods are based on the well known pass local transformation algorithm. We construct a systolic array architecture in which each row data input has a delay of two clocks with respect to its preceding row. For the type of distance transformation operation without constraints, the computation time is always constant for all input images.For this case, the time complexity is O(n), and the hardware complexity is also O(n). On the other hand, for the cases for distance transformation operation with constrains the average time complexity is O(n).These architecures support the real time operation of distance transformation computation required in real machine vision applications.