距離變換

距離轉換（distance transform），亦稱距離圖（distance map）或距離場（distance field），是數位影像的一種衍生表示法。術語的選擇取決於對所討論物件的觀點：是將原始影像轉換為另一種表示法，還是僅為其賦予一個額外的圖或場。

在需要區分某點位於形狀內部還是外部的情況下，距離場也可以是有向的（signed）。

距離圖會為影像中的每個像素標記其與最近障礙像素的距離。最常見的障礙像素類型是二元影像中的邊界像素。請參見影像中二元影像上切比雪夫距離轉換的範例。

通常，此轉換／圖會以所選的度量來限定。例如，若底層度量為曼哈頓距離，則可稱之為曼哈頓距離轉換。常見的度量有：

• 歐幾里得距離
• 計程車幾何，亦稱城市街區距離或曼哈頓距離。
• 切比雪夫距離

存在數種演算法可用於計算這些不同距離度量的距離轉換，然而，若要在影像網格上計算，精確歐幾里得距離轉換（EEDT）的計算需要特殊處理。

其應用包括數位影像處理（例如，模糊效果、骨架化）、機器人學中的運動規劃、用於產前基因檢測的醫學影像分析，甚至路徑規劃。

均勻採樣的有向距離場已被用於 GPU 加速的字體平滑，例如 Valve 的研究人員便曾採用此技術。

有向距離場也可用於（3D）實體建模。在典型的 GPU 硬體上進行渲染需要將其轉換為多邊形網格，例如透過行進立方體演算法。

參見

• 有向距離函數
• 函數表示法
• 平行曲線
• 用於距離計算的水平集方法。

外部連結

• Fast distance transform in C++ by Felzenszwalb and Huttenlocher
• Distance Transform tutorials in CVonline
• Survey of fast exact Euclidean distance transform algorithms
• Using distance mapping for AI
• Distance Transforms by Henry Kwong and Dynamic Step Distance Transforms by Richard Scott, The Wolfram Demonstrations Project.
• Morphological DistanceTransform function in Mathematica
• Morphological Inverse Distance Transform function in Mathematica
• A general algorithm for computing distance transforms in linear time [1]

Category:影像處理 Category:數位幾何學