距離變換圖和骨架圖生成算法

1、距離變換圖和骨架圖生成算法距離變換圖和骨架圖生成算法 6.8 距離變換圖和骨架圖生成算法 1 1、距離變換圖算法、距離變換圖算法 距離變換圖算法是一種針對柵格圖像的特 殊變換，是把二值圖像變換為灰度圖像，其中 每個像素的灰度值等于它到柵格地圖上相鄰物 體的最近距離。 6.8 距離變換圖和骨架圖生成算法 1 1、距離變換圖算法、距離變換圖算法 （1 1）基本思想）基本思想 是把離散分布在空間中的目標根據(jù)一定的 距離定義方式生成距離圖, 其中每一點的距離 值是到所有空間目標距離中最小的一個。 對于距離的量度是通過四方向距離（又稱 “城市塊距離”或“出租車距離”）的運算來 實現(xiàn)的，即只允許沿四個主方

2、向而不允許沿對 角方向進行跨柵格的最小路段的計數(shù)。因此， 每個路段為一個像元邊長。 6.8 距離變換圖和骨架圖生成算法 1 1、距離變換圖算法、距離變換圖算法 （2）基于“歐幾里德距離”公式的距離變換圖算法 在二維平面上定義兩點，那么他們之間的歐氏距離表示為 ： 在二值圖像中，1代表目標點，0代表背景；在灰度圖像中，柵格的灰度值 表示該柵格點到最近目標點的距離值。這樣一張MN的圖像可以表示為 一個二維數(shù)組AMN，其中Aij=1對應的柵格表示目標點，Aij=0對應 的柵格表示背景點。設B=(x,y)|Aij=1為目標點集合，則歐氏距離變換 就是對A中所有的柵格點求： 其中 從而得到二值圖像A的歐

3、氏距離變換圖。 歐氏距離變換1歐氏距離變換2 加權歐氏距離變換 6.8 距離變換圖和骨架圖生成算法 1 1、距離變換圖算法、距離變換圖算法 （2）基于“歐幾里德距離”公式的距離變換圖算 法 22 21 )()(),(),(jnimnmjifPPD 柵格空間中的“歐幾里德距離”距離變換公式： 其中，點P 1 ( i，j )和P 2 (m，n) 的坐標值i, j ,m , n 都是整數(shù)。 只要圖中a、b、c 的取值滿足1 b/a 2， 1c/b 2， 那么 它就是歐幾里德距離的一個在柵格空間中的整數(shù)近似值。 6.8 距離變換圖和骨架圖生成算法 1 1、距離變換圖算法、距離變換圖算法 （3）基于柵格

4、圖像間的運算 獲取距離變換圖的算法 基于柵格圖像間的運算獲取距離變換圖算法的基本方法是：反 復對原圖進行“減細”和將減細結果與中間結果作算術“疊加”兩種基 本運算。其終止條件是：“若對原圖再減細，則將成為全零矩陣” 。 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 骨架圖就是從距離變換圖中提取出具有相對 最大灰度值的那些像元所組成的圖像。 骨架圖算法是一種簡潔、直觀的目標表示 方法，它綜合利用了目標的外部輪廓和內部區(qū) 域信息，在描述目標形狀方面具有傳統(tǒng)表示方 法不可比擬的優(yōu)勢，且骨架圖“山脊線”的連 接關系保留了空間拓撲結構的完整，從而極大 地擴展了骨架圖算法的應用領域。

5、 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 自1967年Blum提出中軸的概念以來，骨架已經成為表示和識別 物體的重要手段之一，骨架組合了目標的輪廓喝中藥區(qū)域信息，反 映了目標的重要視覺線索，因而，寄語骨架的目標表示和識別技術 成為牧師識別和計算機視覺的重要研究內容。 為了準確的對物體進行識別，要求骨架要求具有如下性質： （1 1）保留原物體的拓撲。）保留原物體的拓撲。 （2 2）骨架點的位置精確，要靠近物體的中心。）骨架點的位置精確，要靠近物體的中心。 （3 3）骨架的連通性。）骨架的連通性。 （4 4）獲得骨架的半徑值。）獲得骨架的半徑值。 （5 5）骨架能表達物

6、體在人類視覺中的重要部分。）骨架能表達物體在人類視覺中的重要部分。 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 骨架圖算法實現(xiàn)的途徑主要有兩條，其一是基 于灰度圖像的骨架圖算法，其二是直接從灰度圖像 提取目標骨架的算法。 其中，基于灰度圖像的骨架圖算法主要有3類： (1) 從距離變換中提取骨架,即通過計算灰度圖像 的距離變換，從距離變換圖中檢測并連接骨架點得 到目標的骨架，其缺點是難以設計恰當?shù)泥徲驐l件， 需要較多的后處理。 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 (2) 采用邊界模型提取骨架，即采用離散邊 界模型在逼近真實形狀的同時提取骨架

7、，可 得到在噪聲環(huán)境下穩(wěn)健的骨架。但是，運用 該方法時因構造離散邊界模型比較困難，提 取出的骨架有時可能是不連通的。 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 (3) 基于區(qū)域標記的方法。其典型代表是Liu等人 （2000）提出的基于Arcelli的“非脊點下降”算子 的骨架提取算法。該算法通過并行地對圖像中的所 有非脊點進行下降，將圖像分別標記為骨架點和背 景點，可以獲得單像素寬的、與原始圖像同倫的骨 架。但該算法有時不能提取一些規(guī)則目標的完整骨 架，而且算法對邊界噪聲比較敏感（陳曉飛等， 2003）。 6.8 距離變換圖和骨架圖生成算法 2 2、骨架圖算法、骨架圖算法 基于距離變換的骨架圖生成算法 6.8 距離變換圖和