[發(fā)明專(zhuān)利]一種并行快速符號(hào)距離函數(shù)計(jì)算方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201710323415.6
• 申請(qǐng)日: 2017-05-09
• 公開(kāi)（公告）號(hào): CN107330896B
• 公開(kāi)（公告）日: 2020-07-03
• 發(fā)明（設(shè)計(jì)）人: 江少鋒;艾信友;張聰炫;陳震
• 申請(qǐng)（專(zhuān)利權(quán)）人: 南昌航空大學(xué)
• 主分類(lèi)號(hào): G06T7/11
• 分類(lèi)號(hào): G06T7/11;G06T7/155;G06K9/62;G06K9/34
• 代理公司: 南昌洪達(dá)專(zhuān)利事務(wù)所 36111
• 代理人: 劉凌峰

本發(fā)明公開(kāi)了一種并行的快速符號(hào)距離函數(shù)計(jì)算方法，1）本方法先通過(guò)區(qū)域生長(zhǎng)法得到封閉曲線的內(nèi)部和外部，內(nèi)部距離符號(hào)置負(fù)，外部距離符號(hào)置正來(lái)計(jì)算符號(hào)值，再通過(guò)并行降維法來(lái)計(jì)算距離值；2)并行降維法將二維圖像的符號(hào)距離計(jì)算變成兩個(gè)1維并行符號(hào)距離的計(jì)算；3）1維并行符號(hào)距離的計(jì)算采用了并行拋物線下界法，僅通過(guò)3次迭代就能得到所有點(diǎn)的距離值，計(jì)算復(fù)雜度只有O(3)。本發(fā)明的優(yōu)點(diǎn)是：符號(hào)距離函數(shù)計(jì)算是水平集圖像分割技術(shù)中的關(guān)鍵步驟，常規(guī)計(jì)算方法非常耗時(shí)，影響圖像分割效率。本發(fā)明采用并行計(jì)算實(shí)現(xiàn)符號(hào)距離函數(shù)的快速計(jì)算，進(jìn)而大大提高分割速度。

技術(shù)領(lǐng)域

本發(fā)明涉及一種圖像處理領(lǐng)域，具體為一種用于水平集圖像分割的快速符號(hào)距離函數(shù)計(jì)算方法。

背景技術(shù)

圖像分割是圖像處理領(lǐng)域中的一個(gè)關(guān)鍵技術(shù)，主要用于目標(biāo)識(shí)別和理解，在基于圖像的人工智能領(lǐng)域中起到非常重要的作用，同時(shí)圖像分割也是一經(jīng)典難題，發(fā)展至今仍沒(méi)有找到一個(gè)通用的方法。常用的分割技術(shù)有基于閾值的分割方法、基于邊界的分割方法、基于區(qū)域的分割方法。Osher和Sethian提出的基于水平集的分割方法是一種基于邊界的分割方法，由于能夠很好地處理拓?fù)浣Y(jié)構(gòu)發(fā)生變化時(shí)產(chǎn)生的問(wèn)題近年來(lái)成為圖像分割中最大的研究熱點(diǎn)。一般在水平集計(jì)算的初始化及更新過(guò)程中，都需要計(jì)算符號(hào)距離函數(shù)(SDF)。符號(hào)距離函數(shù)如下定義：

其中d[(x,y),C]表示點(diǎn)(x,y)與閉合曲線C之間的距離。

這一選擇的優(yōu)點(diǎn)是：由于距離函數(shù)具有如下基本性質(zhì)：|▽u|≡1這意味著u(x,y)的變化率處處都是均勻的，沒(méi)有太多的坡地，也沒(méi)有平原。這樣將有利于數(shù)值計(jì)算的穩(wěn)定性。

由于給定的曲線運(yùn)動(dòng)方程只是對(duì)于嵌入函數(shù)的零水平集成立，而不是對(duì)函數(shù)的所有水平集成立，所以隨著演化的進(jìn)行，u逐漸偏離了距離函數(shù)的性質(zhì)，|▽u|遠(yuǎn)大于1的某些局部就會(huì)出現(xiàn)尖峰或者深谷，|▽u|遠(yuǎn)小于1的局部就會(huì)出現(xiàn)平坦區(qū)。以致計(jì)算結(jié)果發(fā)生誤差，如果不加以糾正，這種誤差就會(huì)逐漸增大，最終導(dǎo)致計(jì)算結(jié)果嚴(yán)重錯(cuò)誤。為了讓水平集函數(shù)始終保持為符號(hào)距離函數(shù)，有必要在進(jìn)行若干次u的更迭后，進(jìn)行重新初始化。為此符號(hào)距離函數(shù)在水平集初始化及演化過(guò)程中都需要計(jì)算。

對(duì)于任意閉合曲線，直接計(jì)算符號(hào)距離函數(shù)的計(jì)算量較大。特別是對(duì)于大幅圖像來(lái)說(shuō)，計(jì)算量更大。因此，如何快速準(zhǔn)確地計(jì)算任意閉合曲線地符號(hào)距離函數(shù)，對(duì)于提高水平集方法地效率和穩(wěn)定性至關(guān)重要。

符號(hào)距離函數(shù)不僅用于水平集分割還大量直接用于計(jì)算機(jī)視覺(jué)中的三維視覺(jué)特征提取，模式識(shí)別等領(lǐng)域。而計(jì)算符號(hào)距離函數(shù)的計(jì)算量較大，時(shí)間復(fù)雜度為O(N*M)，N為圖像點(diǎn)數(shù)，M為閉合曲線點(diǎn)數(shù)。尤其對(duì)于大幅圖像，計(jì)算量更大。故快速準(zhǔn)確地計(jì)算符號(hào)距離函數(shù)對(duì)提高水平集方法的效率和穩(wěn)定性至關(guān)重要。

上世紀(jì)90年代開(kāi)始研究人員提出了源點(diǎn)掃描法，快速步進(jìn)法和降維法。源點(diǎn)掃描法確認(rèn)與每個(gè)網(wǎng)格點(diǎn)同處一條特性線(輪廓線C的法線)上的輪廓線點(diǎn)(源點(diǎn))，基于源點(diǎn)來(lái)計(jì)算符號(hào)距離，其計(jì)算復(fù)雜度為O(K*N)，其中K為迭代次數(shù)，N為圖像點(diǎn)數(shù)。快速步進(jìn)法以封閉曲線為起點(diǎn)，從法線方向進(jìn)行放射，采用快速匹配法計(jì)算符號(hào)距離，該方法的計(jì)算復(fù)雜度為O(NlnM)。降維法將2維或更高維符號(hào)距離計(jì)算轉(zhuǎn)換為兩次1維符號(hào)距離計(jì)算(見(jiàn)公式(2))，其中D_f|x'(y)為沿Y方向每列1維符號(hào)距離計(jì)算結(jié)果，再沿X方向做一次1維符號(hào)距離計(jì)算即得到D_f(x,y)。每次1維符號(hào)距離計(jì)算(式3)可等效為求一系列圖像點(diǎn)對(duì)應(yīng)的拋物線組的下邊界得到(附圖1)，其計(jì)算復(fù)雜度為O(2N)。雖然理論上在降維法計(jì)算中圖像的每行和每列的計(jì)算是獨(dú)立的，可以并行計(jì)算完成，計(jì)算復(fù)雜度為O(W+H)，其中W為圖像寬度，H為圖像高度，但是所采用的拋物線下邊界法仍然是串行的。

其中

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