[發(fā)明專利]一種基于動態(tài)規(guī)劃的距離變換計算方法

有效

• 申請?zhí)枺?/td>: 201610080714.7
• 申請日: 2016-02-03
• 公開（公告）號: CN105528759B
• 公開（公告）日: 2018-11-09
• 發(fā)明（設計）人: 李均利;趙繼帆;孫宇紅;魏平
• 申請（專利權）人: 四川師范大學
• 主分類號: G06T3/00
• 分類號: G06T3/00
• 代理公司: 成都行之專利代理事務所(普通合伙) 51220
• 代理人: 郭受剛

本發(fā)明公開了一種基于動態(tài)規(guī)劃的距離變換計算方法，所述方法包括：步驟1：輸入二值圖像創(chuàng)建數(shù)組，將目標像素的8個鄰域劃分為上鄰域和下鄰域，其中，上鄰域和下鄰域分別包括4個鄰域；步驟2：在目標像素的上鄰域內(nèi)計算目標像素與背景像素的偽距離變換，獲得第一偽距離變換結果；步驟3：在目標像素的下鄰域內(nèi)計算目標像素與背景像素的偽距離變換，獲得第二偽距離變換結果；步驟4：比較所述第一偽距離變換結果和所述第二偽距離變換結果，獲得二者的較小值，則二者的較小值作為最終距離變換計算的結果，實現(xiàn)了減少了計算的復雜度，保障了計算的一定精確度，運算時間較短，處理效率較高的技術效果。

技術領域

本發(fā)明涉及圖像分析與模式識別領域，尤其是涉及圖像處理過程中一種近似的距離變換方法。

背景技術

對于一幅二值圖像，圖像中的像素可分為背景像素(像素值為0)和目標像素(像素值為1)兩類，而距離變換就是指把二值圖像每一像素的像素值0、1變換成由到其最近背景像素間的距離值的過程。經(jīng)距離變換后的圖像更能突出展現(xiàn)圖像的邊緣、幾何骨架等信息，進而有助于進行圖像形態(tài)處理(如細化、粗化、骨架化)，模式匹配(如物體檢測和stereofeature匹配)，目標重建、圖像分割、機器人碰撞檢測等方面的研究應用，因此距離變換一直是圖像處理領域的研究熱點。

現(xiàn)在的對距離變換計算方法的研究可分為兩個方向：

一、近似歐氏距離變換計算方法

這類計算方法的基本思想是利用圖像處理里常用到的一個近似模板運算，計算從圖形外移動到圖形內(nèi)某點的最短距離，模板內(nèi)標識的距離值通常是歐式距離的取整近似值，同時模板也不可能始終沿著邊界輪廓的法向方向移動，因此這類方法一定是有誤差，如城市街區(qū)距離、棋盤距離、倒角距離等。盡管此類計算方法實現(xiàn)簡單，且速度較快，但由于存在誤差而不適用于對精度高度嚴格要求的一些圖像處理過程中，如醫(yī)學圖像。

二、完全歐氏距離變換計算方法

隨著硬件技術的不斷提高及對距離變換的廣泛應用，人們也開始致力于完全歐氏距離變換計算方法的研究，并提出了許多相對高效的計算方法，如行列交叉法、邊界追蹤法及基于Voronoi的方法等。雖然上述計算方法可以獲得精確的距離變換，但其中的大部分方法的復雜度較高，運行時間較長，同時隨著社會的發(fā)展，所需處理的圖像的數(shù)據(jù)量也越來越大，此類計算方法的運行時間會更長，這將給實際應用帶來一定困難。

綜上所述，本申請發(fā)明人在實現(xiàn)本申請實施例中發(fā)明技術方案的過程中，發(fā)現(xiàn)上述技術至少存在如下技術問題：

在現(xiàn)有技術中，現(xiàn)有的距離變換計算方法存存在誤差，導致精度較差，或存在運算時間較長，處理效率較低的技術問題。

發(fā)明內(nèi)容

本發(fā)明提供了一種基于動態(tài)規(guī)劃的距離變換計算方法，解決了現(xiàn)有的距離變換計算方法存存在誤差，導致精度較差，或存在運算時間較長，處理效率較低的技術問題，實現(xiàn)了減少了計算的復雜度，保障了計算的一定精確度，運算時間較短，處理效率較高的技術效果。

距離變換是針對二值圖像的一種變換。對于一幅m×n的二值圖像I(x,y)，其中，(x,y)∈(0≤x≤m-1,0≤y≤n-1),(x,y)代表像素在圖像中的位置，I(x,y)代表該位置的像素值，若I(x,y)＝1代表圖像的目標像素；I(x,y)＝0代表圖像的背景像素，所以根據(jù)圖像值，可以將二值圖像分為目標O_b和背景B_g,O_b＝{(x,y)|I(x,y)＝1}為目標像素集合，B_g＝{(x,y)|I(x,y)＝0}為背景像素集合。