本論文提出一個適用於個人電腦叢集上，解決二元影像中距離轉換 (distance transformation) 問題的平行演算法。此平行演算法將一張二元影像切割出多個類似平行四邊形之分隔區，利用雙向掃描的方式計算分隔區內各點的距離，於分隔區間則以波形更迭 (wave-front) 的方式，展開平行運算求解距離轉換；以期在電腦叢集中使資料計算與資料傳輸的時間有最好的搭配，使電腦的等待時間盡可能縮短，達到效能最佳化的目的。實驗結果顯示，所提的平行演算法有令人滿意的效能—以一張3840×3840 的二元影像距離轉換而言，在十六台個人電腦構成的電腦叢集中，該平行演算法相對循序演算法之加速比為8.18；若考慮資料讀入的前置時間更可高達13.44。

In this paper, we design and implement an efficient parallel algorithm for computing the distance transformation (DT) of a binary image on a PC cluster. The parallel algorithm decomposes the input image into parallelogram-like areas and computes the distances for all pixels by a 2-pass scanning in all areas among which a wave-front parameterized strategy is adopted to coordinate the computations and communications on the cluster. The experimental results demonstrate the efficiency of the proposed parallel algorithm. In regard to a 3840×3840 binary image, the speed-up ratio of the parallel algorithm over that of the sequential approach is 8.18 by using a cluster of 16 PCs. On the condition that the time for loading the input image was concerned, the speed-up ratio becomes 13.44.