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

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

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

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

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

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

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

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