【正文】 線的初始位置必須離真實(shí)邊界很近，否則難以得到正確的分割結(jié)果。為了解決這個問題，人們提出了multiresolution方法、增加外部壓力和距離勢能等多種改進(jìn)方法，它們的基本思想都是提高外部力的作用范圍，從而引導(dǎo)輪廓線趨向真實(shí)邊界；② 基本Snakes模型對無法捕獲凹陷邊界，盡管也有很多改進(jìn)方法，但效果都不理想。Xu Chenyang等提出的GVF Snake很好地解決了這些問題。GVF Snake的創(chuàng)新在于將傳統(tǒng)Snakes的圖像力(edge map)用擴(kuò)散方程進(jìn)行處理，得到整個圖像域的梯度向 場(gradient vectorflow filed)作為外部力。經(jīng)過擴(kuò)散方程處理后的GVF比edge map更加有序、更能體現(xiàn)物體邊界的宏觀走勢(如下圖)。 由于GVF不是一個表達(dá)式，無法用能量函數(shù)的形式求解，因此GVF Snake是利用力的平衡條件進(jìn)行優(yōu)化(如下圖)。GVF Snakes具有更大的搜索范圍，對輪廓線初始位置不敏感。可以分割凹陷的邊界，對梯度絕對值的大小乃至噪聲具有更好的魯棒性。而且它還不必預(yù)先知道輪廓線是要膨脹(Balloon Snake)還是收縮(Snake)。 算法改進(jìn)通過求解歐拉方程的數(shù)值算法存在一些難以克服的缺點(diǎn)，比如不易得到全局最優(yōu)解、需要計(jì)算高階導(dǎo)數(shù)、加入硬約束后缺乏穩(wěn)定性。為了極小化Snakes模型的能量函數(shù)， Amini等提出基于動態(tài)規(guī)劃的算法，從而開啟了Snakes模型組合優(yōu)化之先河，也使得Snakes模型在計(jì)弭機(jī)視頻領(lǐng)域得以廣泛應(yīng)用。它對Snakes模型的 個控制點(diǎn)的m鄰域，組合而成的所有備選變形位置，通過動態(tài)規(guī)劃求得其中某個組合的能量函數(shù)相對最小，由此迭代計(jì)算，最終使輪廓線收斂到物體邊界。另一種更加常用的組合優(yōu)化方法是貪婪算法。動態(tài)規(guī)劃的每一步要移動n個節(jié)點(diǎn)，而貪婪算法僅移動一個1了點(diǎn)，通過輪流移動n個節(jié)點(diǎn)最終得到一個解。以上是Snakes模型最常用的3個能量函數(shù)極小化算法。數(shù)值算法形式規(guī)范，每一步迭代步長較大，計(jì)算速度比較快。但對參數(shù)太敏感，且不易增加新約束；動態(tài)規(guī)劃算法不僅容易增加各種約束，而且能夠得到最優(yōu)解。但是計(jì)算速度慢，且最終輪廓會趨向物體的強(qiáng)特征部分，使節(jié)點(diǎn)間距不均勻；貪婪算法實(shí)現(xiàn)簡單，速度快，容易加入新約束，最終結(jié)點(diǎn)分布比較均勻，但無法得到最優(yōu)解。 貪婪算法 算法介紹在 Kass 算法中，需要用變分法來求解該動態(tài)方程，它要求外力必須是可微的，而且這種方法在迭代過程中需要求逆矩陣，同時在進(jìn)化過程中，矩陣會隨著蛇點(diǎn)變化而變化，就需要不斷地執(zhí)行求逆操作，非常費(fèi)時。1988 年，Amini 等人提出了動態(tài)規(guī)劃法（又叫時間延遲法）,雖然引入強(qiáng)制力，放寬外力可微的限制，但運(yùn)算仍緩慢，為 O(nm3)，n、m分別為輪廓線上控制點(diǎn)數(shù)和一個點(diǎn)在一次迭代中可能移動的位置數(shù)。1992 年 Williams 又提出了一種貪婪算法,降低了時間復(fù)雜度，變成了 O(mn)。他認(rèn)為輪廓曲線上的各控制點(diǎn)在計(jì)算能量時，與其它各點(diǎn)均不相關(guān)，也就是說，認(rèn)為此時其它各點(diǎn)均處在最佳位置，以計(jì)算當(dāng)前控制點(diǎn)的可能位置，且計(jì)算每一個控制點(diǎn)就更新其位置，不像 Amini 的動態(tài)規(guī)劃法（也是一種交互獲取邊緣方法，主要通過規(guī)劃能量函數(shù)，而不是通過迭代求取出能量函數(shù)）：需整個 Snake 計(jì)算完畢才更新各控制點(diǎn)的可能位置。由于此算法的簡便性（過于貪婪 Greety） ，叫貪婪算法。 算法過程具體介紹離散的貪婪算法的具體過程如下： 設(shè)蛇點(diǎn)為 ，則能量方程可以離散化為：jV (4—5), , ,0()[()()()]mini contijcurvijimgijjwszeEEVEV??????式（59）中的 winsize 為搜索窗口的大小， 代表第 i 個蛇點(diǎn)或其位置。 為第i ,iji 個蛇點(diǎn)在搜索窗口中 j 處的點(diǎn)， j 的范圍在除去蛇點(diǎn)所在位置搜索窗所有點(diǎn)。、 、 分別對應(yīng)于連續(xù)性能量（continuity） 、彎曲能量,()contijEV,()curvij,()imgijEV(curvature)、圖像能量（image） 。前兩種屬于內(nèi)部能量 ，后一項(xiàng)屬于外部能量int()EXs（有時還包括約束（constraint）能量） 。 、 、 為相應(yīng)的權(quán)值。相應(yīng)的()exts???離散值為： (4—6),1, ,0||(){|}aijicontijjwinszedVE????式（4—7）中的 為蛇點(diǎn)間的平均距離，上式使得接近平均距離的蛇點(diǎn)能量值較小，d這樣蛇點(diǎn)分布較為均勻。 大小為： (4—7)110||NiidV??? (4—8)2,1, 1,0| |(){}maxiijicurvijjwinszeVE???? (4—9), ()()ijigijGryIVa?式（4—8）和（4—9）為圖像的曲線能和圖像能。其中 為第 i 蛇點(diǎn)對應(yīng)窗口中 j 位置的灰,()ijIV度值， 、 為窗口中最小和最大的灰度值。minGrayxry 算法結(jié)果采用矩形框架初始化蛇點(diǎn)，并使用(4—5)，經(jīng)過處理，就可以得到圖像 4—10 和圖像4—11。 圖 4—10 原圖像 圖 4—11 Snake 處理圖從結(jié)果可以看出：傳統(tǒng) Snake 蛇形的蛇點(diǎn)的初始化必須在圖像的邊緣處才可以收縮到真正圖像的邊緣。同時，在凹形框內(nèi)圖像沒有向下的力量，故它收縮不到真正的凹坑內(nèi)。第五章 Greed 蛇形分割算法設(shè)計(jì)snake 算法又稱 Active Contour 算法，廣泛應(yīng)用于圖像分割與計(jì)算機(jī)視覺的邊界檢測。這種算法需要首先給出初始的輪廓，然后進(jìn)行迭代，使輪廓沿能量降低的方向靠近，最后即得到一個優(yōu)化的邊界。這里能量函數(shù)包括內(nèi)外力兩方面，如邊界曲率和梯度。Snake 模型有兩個主要特點(diǎn):一方面，它將目標(biāo)輪廓的初始估計(jì)、曲線性質(zhì)、圖像信息和先驗(yàn)知識融于一個統(tǒng)一的過程。另一方面，它在分割目標(biāo)邊緣的過程中尋找能量泛函的局部極小點(diǎn)，而非全局極小點(diǎn)。當(dāng) snake 的能量最小化后，內(nèi)部和外部能量趨于平衡，系統(tǒng) snake 能量達(dá)到一個穩(wěn)定的狀態(tài)。 整體設(shè)計(jì)在對程序進(jìn)行設(shè)計(jì)之前首先要對設(shè)計(jì)任務(wù)有一個清晰的認(rèn)識，對程序的整體框架有一個藍(lán)圖，才便于我們在對后續(xù)各個程序進(jìn)行分塊設(shè)計(jì)的時候有一個總體的把握和方向，對設(shè)計(jì)所要達(dá)到的設(shè)計(jì)指標(biāo)有更深刻的理解。程序流程圖如圖(5—1) ?？梢钥闯鲈谡麄€程序中有載入圖像部分、灰度處理部分、能量計(jì)算部分、圖像分割部分。這四部分的設(shè)計(jì)是整個程序設(shè)計(jì)的關(guān)鍵。載入圖像和灰度處理是算法設(shè)計(jì)的前提，能量計(jì)算是算法程序設(shè)計(jì)的關(guān)鍵部分。圖像分割主要借助 VC++和 Opencv 來實(shí)現(xiàn)。概括來說就是利用 Greed 蛇形分割算法原理，基于 VC++和 Opencv 實(shí)現(xiàn)對任何圖像的分割處理，使之收斂到圖像的邊緣。 載入圖像載入圖像即讀取圖像，這是對圖像處理的準(zhǔn)備。說到讀取圖像，就應(yīng)該清楚關(guān)于所載入圖像的一系列特征，例如是彩色圖，灰度圖還是二值圖。函數(shù)： cvLoadImage功能：從指定文件讀入圖像，返回讀入圖像的指針程序語句如下：IplImage*cvLoadImage(const char* filename, int flags=CV_LOAD_IMAGE_COLOR )。其中：Filename 是要被讀入的文件的文件名。flags 指定讀入圖像的顏色和深度：指定的顏色可以將輸入的圖片轉(zhuǎn)為 3 信道(CV_LOAD_IMAGE_COLOR), 單信道開 始結(jié) 束載 入 圖 像灰 度 處 理計(jì)算蛇點(diǎn)間的平均距離 d計(jì)算連續(xù)性能量 Econt計(jì)算彎曲性能量 Ecurv 計(jì)算圖像能量 Eimg找出各能量相應(yīng)的權(quán)值計(jì)算蛇點(diǎn)的能量圖 像 分 割圖 5—1 程序流程框圖(CV_LOAD_IMAGE_GRAYSCALE), 或者保持不變(CV_LOAD_IMAGE_ANYCOLOR)。深度指定輸入的圖像是否轉(zhuǎn)為每個顏色信道每象素 8 位， （OpenCV 的早期版本一樣） ，或者同輸入的圖像一樣保持不變。選中 CV_LOAD_IMAGE_ANYDEPTH，則輸入圖像格式可以為 8 位無符號，16 位無符號，32 位有符號或者 32 位浮點(diǎn)型。如果輸入有沖突的標(biāo)志，將采用較小的數(shù)字值。比如 CV_LOAD_IMAGE_COLOR | CV_LOAD_IMAGE_ANYCOLOR 將載入 3 信道圖。CV_LOAD_IMAGE_ANYCOLOR 和CV_LOAD_IMAGE_UNCHANGED 是等值的。但是，CV_LOAD_IMAGE_ANYCOLOR 有著可以和CV_LOAD_IMAGE_ANYDEPTH 同時使用的優(yōu)點(diǎn)，所以 CV_LOAD_IMAGE_UNCHANGED 不再使用了。如果想要載入最真實(shí)的圖像，選擇 CV_LOAD_IMAGE_ANYDEPTH | CV_LOAD_IMAGE_ANYCOLOR。 灰度化處理灰度圖像是由圖像的亮度函數(shù)來描述的，其邊緣可以定義為圖像亮度函數(shù)不連續(xù)的點(diǎn)的集合，描述了灰度函數(shù)的局部突變。既然灰度圖像的邊緣檢測就是要保留圖像灰度值變化劇烈的區(qū)域，從數(shù)學(xué)上，最直觀的方法就是微分(對于數(shù)字圖像來說就是差分)，從信號處理的角度看，可以說是用高通濾波器保留高頻信號。用于圖像識別的邊緣檢測方法輸出的一般是二值圖像，即只有黑白兩個灰度的圖像，其中一個灰度代表邊緣，另一個代表背景。所以灰度處理是邊緣檢測的關(guān)鍵步驟。函數(shù)：iplColorToGray功能：把圖像轉(zhuǎn)化為灰度圖程序語句如下：IplImage* CurMap=cvCreateImage(cvGetSize(imageA), IPL_DEPTH_8U,1)。iplColorToGray(imageA,GrayImage)。 cvCvtColor(imageA, GrayImage,CV_BGR2GRAY)。 蛇點(diǎn)間距離設(shè)蛇點(diǎn)間的平均距離為 ，則—d （5—110||NiiV???2）下面程序中定義為 invn。程序設(shè)計(jì)如下：for( i = 1。 i n。 i++ ) { int diffx = pt[i 1].x pt[i].x。 int diffy = pt[i 1].y pt[i].y。 ave_d += cvSqrt( (float) (diffx * diffx + diffy * diffy) )。 } ave_d += cvSqrt( (float) ((pt[0].x pt[n 1].x) * (pt[0].x pt[n 1].x) + (pt[0].y pt[n 1].y) * (pt[0].y pt[n 1].y)))。 ave_d *= invn。程序流程圖如下：圖 5—2 蛇點(diǎn)間距離程序流程圖N開 始i=1==ave_dave_d+invnin結(jié) 束Yi++ 蛇點(diǎn)能量如果設(shè)蛇點(diǎn)為 ，那么該蛇點(diǎn)的能量方程就為jV （5—, , ,0()[()()()]mini contijcurvijimgijjwszeEEVEV??????3）其中 、 、 分別對應(yīng)于連續(xù)性能量（continuity） 、彎曲能量,()contijV,()curvij,()imgij(curvature)、圖像能量（image） 。前兩種屬于內(nèi)部能量 ，后一項(xiàng)屬于外部能量int()EXs（有時還包括約束（constraint）能量） 。 、 、 為相應(yīng)的權(quán)值。()exts???由式（5—3）知，有 3 種力作用于蛇點(diǎn)，它們對蛇點(diǎn)的運(yùn)動有不同的影響: 使輪curvE廓趨于平滑。 使蛇點(diǎn)分布趨于局部均勻。 使蛇點(diǎn)收斂于真正的目標(biāo)邊緣。在蛇點(diǎn)contEimgE運(yùn)動過程中，如何合理調(diào)整四種力對蛇點(diǎn)作用的大小，對最后的收斂結(jié)果往往具有很大的影響。通過對各種力的分析認(rèn)為:(l)當(dāng)蛇點(diǎn)與目標(biāo)邊緣距離較遠(yuǎn)時， 應(yīng)該起主要作用，其目的就是在運(yùn)動的初始contE階段，使蛇點(diǎn)快速向目標(biāo)收縮，更重要的是要盡量避免背景噪聲對蛇點(diǎn)的影響。(2)當(dāng)蛇點(diǎn)收縮到目標(biāo)邊緣附近時， ， 和 應(yīng)該起主要作用，其目的是更c(diǎn)ontcurvimg好地使蛇點(diǎn)向目標(biāo)邊緣收斂。可以看出，準(zhǔn)確判斷出蛇點(diǎn)與目標(biāo)輪廓邊緣的位置關(guān)系，即蛇點(diǎn)是在目標(biāo)外，或在目標(biāo)邊緣附近還是在目標(biāo)內(nèi)，這是權(quán)值參數(shù)調(diào)整的關(guān)鍵。 Greed 蛇形分割算法的實(shí)現(xiàn)流程建立用于圖像操作的 Image 類和控制 Snake 的 MysnakeList 類。其中 Image 類負(fù)責(zé)圖像的基本操作，包括打開、存儲以及基本的圖像變換，圖像變換包括灰度圖轉(zhuǎn)化，圖像的高斯變換，canny 邊緣算子的運(yùn)算等。而 MysnakeList 是蛇點(diǎn) MysnakePoint 的鏈表，負(fù)責(zé)貪婪算法的運(yùn)作，其實(shí)現(xiàn)的功能包括控制點(diǎn)的移動，Snake 蛇曲線的蠕動，角點(diǎn)參數(shù)的自動設(shè)置等。Greed 蛇形分割算法的