[發明專利]一種基于動態規劃的距離變換計算方法

有效

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

1.一種對二值圖像像素進行距離變換處理的方法，其特征在于，所述方法包括：

步驟1：輸入二值圖像創建數組，將目標像素的8個鄰域劃分為上鄰域和下鄰域，其中，上鄰域和下鄰域分別包括4個鄰域；

步驟2：在目標像素的上鄰域內計算目標像素與背景像素的偽距離變換，獲得第一偽距離變換結果；

步驟3：在目標像素的下鄰域內計算目標像素與背景像素的偽距離變換，獲得第二偽距離變換結果；

步驟4：比較所述第一偽距離變換結果和所述第二偽距離變換結果，獲得二者的較小值，則二者的較小值作為最終距離變換計算的結果；

所述方法具體包括：

首先，針對m*n大小的圖像，將目標像素I(x,y)＝1的八鄰域分為上鄰域Un、下鄰域Dn，I(x,y)＝1代表圖像的目標像素；

Un＝{(x-1,y-1)，(x,y-1),(x+1,y-1),(x-1,y)}

Dn＝{(x+1,y),(x-1,y+1),(x,y+1),(x+1,y+1)}

然后，設置偽距離記錄數組：第一偽距離記錄數組LD[m,n]，第二偽距離記錄數組RU[m,n]，并將二者初始化為0；

然后，從上到下，從左到右，光柵掃描圖像，若一個目標像素的上鄰域內存在一像素點p，若p為背景像素，則這一目標點的距離變換值為1，即LD[x,y]＝1；反之，即若一個目標像素的上鄰域內沒有背景像素點，則該目標點的距離變換值是上鄰域中相應點的距離變換值與該目標點距離之和的最小值；

然后，從下到上，從右到左，光柵掃描圖像，若一個目標像素的下鄰域內存在一像素點p，若p為背景像素，則這一目標點的距離變換值為1，即LD[x,y]＝1；反之，即若一個目標像素的下鄰域內沒有背景像素點，則該目標像素點的距離變換值是下鄰域中相應點的距離變換值與該目標點距離之和的最小值；

最后，取LD[x,y]和RU[x,y]相應點的較小值為最終距離變換計算的結果值：

RET[x,y]＝min(LD[x,y],RU[x,y])。

2.根據權利要求1所述的對二值圖像像素進行距離變換處理的方法，其特征在于，所述計算方法的空間復雜度需求為O(n)。

3.根據權利要求1所述的對二值圖像像素進行距離變換處理的方法，其特征在于，所述方法具體應用于城市街區距離計算中，最短城市街區距離CBDT(x,y)＝RET[x,y]。