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

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

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

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

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

6、2 2、骨架圖算法、骨架圖算法 骨架圖算法實現的途徑主要有兩條，其一是基于灰度圖像的骨架圖算法，其二是直接從灰度圖像提取目標骨架的算法。 其中，基于灰度圖像的骨架圖算法主要有3類：(1) 從距離變換中提取骨架,即通過計算灰度圖像的距離變換，從距離變換圖中檢測并連接骨架點得到目標的骨架，其缺點是難以設計恰當的鄰域條件，需要較多的后處理。 6.8 距離變換圖和骨架圖生成算法2 2、骨架圖算法、骨架圖算法 (2) 采用邊界模型提取骨架，即采用離散邊界模型在逼近真實形狀的同時提取骨架，可得到在噪聲環境下穩健的骨架。但是，運用該方法時因構造離散邊界模型比較困難，提取出的骨架有時可能是不連通的。 6.8 距離變換圖和骨架圖生成算法2 2、骨架圖算法、骨架圖算法 (3) 基于區域標記的方法。其典型代表是Liu等人（2000）提出的基于Arcelli的“非脊點下降”算子的骨架提取算法。該算法通過并行地對圖像中的所有非脊點進行下降，將圖像分別標記為骨架點和背景點，可以獲得單像素寬的、與原始圖像同倫的骨架。但該算法有時不能提取一些規則目標的完整骨架，而且算法對邊界噪聲比較敏感（陳曉飛等，2003）。 6.8 距離變換圖和骨架圖生成算法2 2、骨架圖算法、骨架圖算法 基于距離變換的骨架圖生成算法6.8 距離變換圖和