第七屆認(rèn)證杯〞數(shù)學(xué)中國 數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽

...wd......wd......wd...第七屆“認(rèn)證杯〞數(shù)學(xué)中國數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽承諾書我們仔細(xì)閱讀了第七屆“認(rèn)證杯〞數(shù)學(xué)中國數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽的競賽規(guī)則。我們完全明白，在競賽開場后參賽隊員不能以任何方式〔包括、電子郵件、網(wǎng)上咨詢等〕與隊外的任何人〔包括指導(dǎo)教師〕研究、討論與賽題有關(guān)的問題。我們知道，抄襲別人的成果是違反競賽規(guī)則的,如果引用別人的成果或其他公開的資料〔包括網(wǎng)上查到的資料〕，必須按照規(guī)定的參考文獻(xiàn)的表述方式在正文引用處和參考文獻(xiàn)中明確列出。我們鄭重承諾，嚴(yán)格遵守競賽規(guī)則，以保證競賽的公正、公平性。如有違反競賽規(guī)則的行為，我們承受相應(yīng)處理結(jié)果。我們允許數(shù)學(xué)中國網(wǎng)站()公布論文，以供網(wǎng)友之間學(xué)習(xí)交流，數(shù)學(xué)中國網(wǎng)站以非商業(yè)目的的論文交流不需要提前取得我們的同意。我們的參賽隊號為：#1777參賽隊員(簽名)： 隊員1：王立志隊員2：張國營隊員3：曹媛莉參賽隊教練員(簽名)：參賽隊伍組別：研究生組第七屆“認(rèn)證杯〞數(shù)學(xué)中國數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽編號專用頁參賽隊伍的參賽隊號：〔請各個參賽隊提前填寫好〕：#1777競賽統(tǒng)一編號〔由競賽組委會送至評委團(tuán)前編號〕：競賽評閱編號〔由競賽評委團(tuán)評閱前進(jìn)展編號〕：2014年第七屆“認(rèn)證杯〞數(shù)學(xué)中國數(shù)學(xué)建模網(wǎng)絡(luò)挑戰(zhàn)賽第一階段論文題目關(guān)于矢量化過程中邊界提取問題的模型關(guān)鍵詞矢量化；邊緣跟蹤與擬合；梯度檢測法；參數(shù)方程摘要：摘要：矢量圖，作為圖像的一種表示方法，以其縮放不失真、存儲空間小等特性，越來越受到人們的青睞，廣泛應(yīng)用于電影、醫(yī)療等重要領(lǐng)域。本文針對由位圖到矢量圖這一柵格化的逆過程，簡單分析了其去噪，二值化，等問題，重點依據(jù)題目提出的尋找邊緣方程的問題進(jìn)展詳盡的描述?，F(xiàn)按照次重點簡單表達(dá)如下：首先，本文在綜合了多種矢量圖提取算法的根基上，結(jié)合圖像矢量化編輯的特點，提出了一種用于快速提取邊緣曲線的方法—基于參數(shù)方程法，基于該方法實現(xiàn)了對輪廓信息的快速提取。通過聚類的方法將檢測出的輪廓信息〔像素〕進(jìn)展分類，并對聚類后的曲線信息進(jìn)展擬合，使之成為便于操作管理的B-樣條曲線。其次，在完成題目要求的前提下，對獲取矢量圖過程中的主要步驟簡單介紹，對矢量化涉及的消燥、二值化等問題進(jìn)展解釋，以加深對模型應(yīng)用的理解。并對矢量化過程中的某些特定名詞進(jìn)展解釋，以便于更好的了解和理解復(fù)雜的過程。最后，對模型的優(yōu)缺點加以總結(jié)，展望模型的應(yīng)用領(lǐng)域。關(guān)鍵詞：矢量化；邊緣跟蹤與擬合；梯度檢測法；參數(shù)方程參賽密碼〔由組委會填寫〕參賽密碼〔由組委會填寫〕所選題目:B題英文摘要〔選填〕Abstract:vector,asarepresentationofimage,withitsscalingdistortion,suchassmallstoragespacecharacteristics,moreandmorepeopleofallages,widelyusedintheimportantfieldoffilm,medicaletc..Thispaperbythebitmaptovectorinverseprocessdiagramofthisgrid,asimpleanalysisofthedenoisingproblem,twovalues,andsoon,focusonthedetaileddescriptionofthefoundationforedgeequationthequestionsproposed.Inaccordancewiththefocusonsimplenarrativetime:Aboveall,thispaperbasedonsynthesizingavarietyofvectorextractionalgorithm,combinedwiththecharacteristicsoftheimagevectorediting,amethodforrapidextraction-characteristiccurveedgecurvemethodispresented,themethodtorealizethefastextractionofcontourinformationbasedon.Contourinformationthroughclusteringmethodwillbedetected(pixel)classification,andtofitthecurveinformationafterclustering,makeitconvenientforoperationandmanagementoftheB-splinecurve.Secondly,onthepremisetocompletetherequirementsofthesubject,themainstepsforobtainingvectorgraphintheprocessofsimpleintroduction,thevectortoeliminatedryness,twovaluesareexplained,inordertodeepentheunderstandingofthemodelapplication.Andthespecifictermvectorintheprocessofinterpretation,intheprocessinordertobetterunderstandandunderstandcomplex.Lastbutnotleast,theadvantagesanddisadvantagesofthemodelaresummarized,applicationprospectmodel.目錄目錄1.簡介11.1背景介紹11.2本文的目的和意義12.矢量化過程中存在的問題13.模型的建設(shè)23.1模型中涉及的字母23.2灰度圖像的二值化23.2.1閾值分割法簡介23.2.2計算閾值的方法33.2.3最正確閾值的選擇43.2.4二值化結(jié)果53.3二值圖像的消噪63.3.1二值圖像的消噪63.3.2孤立點消除73.3.3空穴的消除83.3.4小面積顆粒的去除83.3.5.自動去除斑點噪聲的方法93.4邊緣檢測93.5邊緣跟蹤103.6邊緣曲線的分段擬合113.6.1尖點提取113.6.2算法思想123.6.3算法設(shè)計123.6.4實驗結(jié)果及分析133.6.5曲線擬合144.總結(jié)及展望174.1總結(jié)174.2展望17參考文獻(xiàn)181.簡介1.1背景介紹隨著信息技術(shù)的開展，圖像越來越成為人們獲取和感知信息的主要來源。特別是數(shù)字圖像技術(shù)的開展，己廣泛應(yīng)用于電影、醫(yī)療、工業(yè)和航空航天等重要領(lǐng)域，在經(jīng)濟(jì)的開展中起到了相當(dāng)重要的作用。常見的計算機平面圖形的表示方法有位圖和矢量圖。位圖是基于像素點的圖,由一系列像素點組成的。常見的位圖有點陣圖、光柵圖以及像素圖等，其存儲格式有jpg，gif，bmp等。矢量圖則是由一系列曲線信息和顏色信息組成的抽象圖,通常被壓縮存儲為XML文件。矢量圖從本質(zhì)上只是使用曲線方程對圖形進(jìn)展的準(zhǔn)確描述，在以像素為根本顯示單元的顯示器或打印機上是無法直接表現(xiàn)的。將矢量圖轉(zhuǎn)換成以像素點陣來表示的信息，再加以顯示或打印，這個過程稱之為柵格化〔Rasterization〕，而柵格化的逆過程相比照擬困難。1.2本文的目的和意義本文的研究目的與矢量化的過程密切相關(guān)，針對矢量化處理過程中所包含的圖象前處理、矢量跟蹤、圖形識別、圖形后處理以及圖形格式轉(zhuǎn)換輸出這五個環(huán)節(jié)，本文主要對圖象的去噪、二值化、細(xì)化特別是我們想要建設(shè)合理的數(shù)學(xué)模型，盡量準(zhǔn)確地提取出圖案的邊界限條，并將其用方程表示出來。應(yīng)用本文所設(shè)計的模型，可以最快速的準(zhǔn)確提取圖像的邊緣曲線，并對其進(jìn)展擬合，方便地進(jìn)展矢量化，對于工程制圖及提高圖像的質(zhì)量有明顯的意義。2.矢量化過程中存在的問題目前，光柵圖象輸入識別與矢量化系統(tǒng)的研究與開發(fā)是工程及制圖領(lǐng)域內(nèi)的一個研究方向，屬于一個較新的課題，這個方向在我國的研究還處于一個開場階段。該課題的研究具有重要的實際意義和理論價值，同時又具有較大的難度，理論上的研究成果與實際的需求還有比擬大的距離。光柵圖象輸入識別與矢量化系統(tǒng)的研究與開發(fā)，需要花費一定的時間去進(jìn)展編寫調(diào)試，由于時間和個人能力的限制，我們的模型不可能在短時間內(nèi)完成整個矢量化系統(tǒng)的工作，只能就課題所涉及的幾個主要方面加以研究。對于文中已得出的結(jié)論，目前也只適用于理論階段，方程的準(zhǔn)確性及應(yīng)用領(lǐng)域還有待考察。3.模型的建設(shè)3.1模型中涉及的字母字母意義T閾值A(chǔ)ve灰度均值Q(k)別離指標(biāo)hk灰度為k的像素個數(shù)Phs〔i〕灰度級的概率函數(shù)〔i，j〕像素Gray灰度Sx，Sy梯度3.2灰度圖像的二值化灰度圖像中目標(biāo)圖像與背景的分割即圖像二值化。掃描圖主要是由目標(biāo)和背景組成，當(dāng)然可能還有一些掃描圖紙時所摻雜的噪聲。一般人們所關(guān)心的那局部圖像物體為目標(biāo)，而把物體之外的區(qū)域稱為背景，在人類視覺中目標(biāo)與背景有著明顯不同的界限，人們可以很容易的將其別離，而計算機則必須通過一定的判定規(guī)則才能將其別離。掃描圖像大多數(shù)為256級灰度圖像，像素的灰度值是從0~255之間，灰度值0表示黑色像素，為目標(biāo)像素，灰度值255表示白色像素，為背景像素，灰度值在0一255之間的像素可能屬于目標(biāo)像素，也可能屬于背景像素。一般采用閾值分割法對目標(biāo)和背景進(jìn)展分割，把目標(biāo)像素標(biāo)記為1，把背景像素標(biāo)記為0。3.2.1閾值分割法簡介閾值分割法是一種區(qū)域分割技術(shù)，使用該方法分割灰度圖像時一般對圖像有一定的假設(shè)。換句話說，是基于一定的圖像模型的。最常用的模型可描述如下：假設(shè)圖像由具有單峰灰度分布的目標(biāo)和背景組成，在目標(biāo)或背景內(nèi)部的相鄰像素間的灰度值是高度相關(guān)的，但在目標(biāo)和背景交界處兩邊的像素在灰度值上有很大的差異。如果一副圖像滿足這些條件，它的灰度直方圖根本上可看作是由分別對應(yīng)目標(biāo)和背景的兩個單峰直方圖混合而成。此時如果這兩個分布大小(數(shù)量)接近且均值相距足夠遠(yuǎn)，而且均方差也足夠小，則直方圖應(yīng)是雙峰的。此類圖像的灰度直方圖曲線如圖3.1，其中橫坐標(biāo)軸表示圖像中出現(xiàn)的灰度值，縱坐標(biāo)軸表示圖像中取某一灰度值出現(xiàn)的概率，即取該灰度值的像素占圖像總像素的比例。當(dāng)使用閾值方法來分割灰度圖像時，首先確定一個灰度閾值T，然后將圖像中每個像素的灰度值與閾值T相比擬，所有灰度值小于或者等于閾值T的像素都被判屬于目標(biāo)，所有灰度值大于該閾值T的像素都被判斷為背景。即〔3-1〕由上式可見，要從復(fù)雜的背景下把目標(biāo)像素提取出來，閾值正確選取是關(guān)鍵。如果閾值選得過大，一些目標(biāo)物將被誤分為背景；如果取得太小，則會將一些背景轉(zhuǎn)換成目標(biāo)物，造成目標(biāo)區(qū)的特征失真，形成錯誤分割。3.2.2計算閾值的方法閾值計算的方法很多，常用的有整體閾值法、類判別分析法、迭代閾值法等。1.整體閾值法整體閾值分割的具體方法是：首先計算整個圖像的灰度直方圖，然后獲得整個圖像的最正確分割閾值。整體閾值分割適合圖紙質(zhì)量比擬好，整幅圖像背景均勻，圖線質(zhì)量較好的情況。對于背景不均勻，背景與圖線比照不一致的圖像，不適合使用整體閾值分割的，可采用二次處理技術(shù)實現(xiàn)。首先，計算整圖的灰度直方圖，獲得全局最正確閾值，進(jìn)展第一次分割。然后將圖像劃分成l00100的像素塊(根據(jù)圖紙具體情況，可以調(diào)整分塊大小)，在每一個塊內(nèi)部，按照整體閉值分割的方法獲得最正確閾值。2.類判別分析法該方法根據(jù)Otsu提出的類判別分析法尋找閾值[1]。計算閾值的具體步驟如下：l)計算輸入圖像的灰度級直方圖(用灰度級的概率函數(shù)Phs(i)來表示)。計算灰度均值(Ave)〔3-2〕計算灰度均值A(chǔ)ver(k)以及直方圖的和w(k)〔3-3〕〔3-4〕計算類別離指標(biāo)〔3-5〕求使Q最大的k值。要計算的最正確閾值為：。用該閾值得到的二值圖像有較好的別離特性，并能盡可能多的圖像的有用特征提取出來。迭代閾值閾值也可以通過迭代計算得到，首先取圖像灰度范圍的中值作為初始閾值(設(shè)共有L個灰度)，然后按下式進(jìn)展迭代：〔3-6〕其中是灰度為k的像素個數(shù)，迭代一直進(jìn)展到完畢，取完畢時的為分割閾值。迭代法不僅思路簡單，實現(xiàn)容易，而且運行速度快。這種方法對于具有雙峰直方圖的圖像效果很好，即使在多峰直方圖的情況下也能獲得適宜的閾值。3.2.3最正確閾值的選擇目標(biāo)像素與背景比照明顯的圖象，由于圖線在圖象整體中所占面積比擬小，圖線對應(yīng)的峰面積較小，像素數(shù)量也較少；白色背景占據(jù)了圖象中的絕大局部內(nèi)容，面積較大。兩個峰尖對應(yīng)于目標(biāo)及背景上的灰度值數(shù)量最多的點，兩峰之間的谷對應(yīng)于物體圖線邊緣附近相對較少數(shù)量的點。對于這種灰度變化均勻直方圖曲線，一般采用整體閾值法。最簡單做法就是在整個圖象中將閾值設(shè)置為常數(shù)。只要選擇了正確的閾值，使用一個固定的全局閾值一般會有較好的分割效果。某些情況下，比方圖象質(zhì)量比擬差，特別是噪聲大，背景的灰度值并不恒定，而且圖線和背景的比照度在圖象中變化比擬大時，閾值就難以直接選取。因此，對于各種不同質(zhì)量的圖象，應(yīng)有針對性地采用不同的處理方法，使二值化到達(dá)最理想的效果。根據(jù)圖象的質(zhì)量，一般可分為四類：(1)清晰，即圖形與背景分界明顯且噪聲小〔圖3.2(a)〕(2)較為清晰，即圖形與背景分界明顯，但存在一定的噪聲〔圖3.2(b)〕(3)較為模糊，即圖形與背景分界不很明顯，也無較多的噪聲〔圖3.2(c)〕(4)模糊，即圖形與背景分界不明顯，且存在大量噪聲數(shù)據(jù)〔圖3.2(d)〕圖3.2圖像的分類由于本文所處理的圖像的噪聲不多，屬于圖3.2(a)的情況，因此采用整體閾值法進(jìn)展處理。這種方法算法簡單，運行速度快，也不會在圖像的某些部位產(chǎn)生偽影現(xiàn)象。具體方法是：首先考察整個圖像的灰度直方圖，尋找目標(biāo)和背景的最頂峰值，然后以兩局部中的最頂峰值的平均值對應(yīng)的灰度值，作為整個圖像的最正確分割閾值，對灰度圖像進(jìn)展分割，獲得二值化圖像。由于白描圖像中圖線面積比擬小，圖線對應(yīng)的波峰不明顯。采用上述的整體閾值分割方法進(jìn)展二值化處理，使用的閾值為180，分割結(jié)果如圖3.4所示?？梢钥闯?，絕大局部圖線內(nèi)容都得到了比擬好的分割，背景區(qū)域比擬干凈，沒有明顯的噪聲。3.2.4二值化結(jié)果以下是實現(xiàn)灰度圖像二值化的局部代碼和結(jié)果：VoidCDfView::OnDraw(CDC*pDC){mybmp.Display2(pDC,0,0,widths,heights);color*pic=mybmp.BmpToPixel(mybmp.m-hBmP);if(pic)for(inti=0;i<heights;i++)for(intj=0;j<widths;j++){if(!(pic[i*widths+j].Bb>180&&pic[i*widths+j].Bg>180&&pic「i*widths+j].Br>180))PDC一>SetPixel(j+500,i,00000000):}}}圖3.3灰度圖像圖3.4二值化圖像3.3二值圖像的消噪光柵圖形一般是以像素或壓縮的像素塊為單位來表示圖像，可以認(rèn)為這種圖形是由一個個的像素組成，彼此之間沒有任何關(guān)系，也不考慮圖像的內(nèi)容，簡單的說光柵圖像就是一個點陣的概念。矢量圖采用的是完全不同的存儲方式，它的存儲單位不是單個像素或像素塊，而是人們感興趣的圖像內(nèi)容的特征。如在矢量圖中要表示一個圓，只須存儲圓的圓心、半徑和顏色即可：對于一條直線，只須用直線的兩端點坐標(biāo)表示即可。對于用矢量表示的圖形而言，如果需要轉(zhuǎn)化成光柵點陣的形式，由給出的圖形參數(shù)描述，利用計算機圖形學(xué)的根本方法，可以很方便的進(jìn)展轉(zhuǎn)化。但其逆過程，即從圖形的光柵點陣形式轉(zhuǎn)化成其參數(shù)的描述也就是采用矢量來表示的形式,就相當(dāng)困難了。本文的目的,就在于對這一逆過程進(jìn)展探索，分析比擬現(xiàn)有的幾種矢量化算法，提出一種更實用、更高效的矢量化算法，將點陣圖像轉(zhuǎn)化為矢量圖形。其大致流程如以下列圖所示：圖3.5矢量化流程圖3.3.1二值圖像的消噪噪聲消除是矢量化預(yù)處理的一個重要環(huán)節(jié)。在二值化的過程中，由于所采用的整體閾值算法無法充分考慮圖像的構(gòu)造特征，二值化后的圖像仍然會包括局部噪聲，這些噪聲會對后續(xù)的細(xì)化、矢量化等過程產(chǎn)生嚴(yán)重的影響，必須盡可能消除。二值化后的圖像中包含的主要噪聲類型有[2]：〔1〕孤立噪聲：圖紙背景中的孤立點、斑點、污點或者麻點。〔2〕毛刺噪聲：圖紙中圖線邊緣不應(yīng)該有的小毛刺。〔3〕空洞、缺隙噪聲：圖紙中圖線上出現(xiàn)的小洞或者邊沿出現(xiàn)的缺口?！?〕斷裂噪聲：圖紙中個別圖線出現(xiàn)的輕微斷裂。下面將針對不同的噪聲采用不同的方法消除[3]：在介紹二值圖消噪的方法之前,首先介紹一下二值圖像的幾個重要的定義?！?〕4-鄰域和8-鄰域?qū)τ谌我幌袼?i，j)，把包含該像素在內(nèi)的一個集合稱為像素(i，j)的鄰域[4]。在柵格平面表示的數(shù)字圖像中，最常用的是“像素的4-鄰域〞和“像素的8-鄰域〞。像素的4-鄰域(4-Neighbor)：對像素(i，j)，將它以及其上(i-1，j)，下(i+1，j)，左(i，J-1)，右(i，j+1)4點構(gòu)成的集合，稱為像素(i，j)的4-鄰域，有時也稱4-近鄰。像素的8-鄰域(8-Neighbor)：對像素(i，j)，將它和其上(i-1，j)，下(i+1，j)，左(i，J-1)，右(i，j+1)4個像素以及對角線的右上(i-1，j+1)，左上(i-1，j-1)，左下(i+1，j-1)，右下(i+1，j+1)4個像素構(gòu)成的集合，稱為像素(i，j)的8-鄰域(圖3.2)，有時也稱8-近鄰。圖3.6鄰域圖〔2〕連接數(shù)：在某個“1〞像素區(qū)中的連接數(shù)，可以以這個像素的8-鄰域值f(x0)至f(x7)(參照圖3.6)按下式進(jìn)展計算：〔3-7〕如果xk=x8，則令x8=x0通過對X像素8-鄰域內(nèi)一切可能存在的值，按公式(3-1)進(jìn)展計算，其連接數(shù)總是取0~4之間的值?！?〕像素間的距離本次設(shè)計中，像素間的距離采用阿基米德表示方法：設(shè)像素A，B兩點的坐標(biāo)分別(xa，ya)和(xb，yb)，則其間的距離d可表示為：〔3-8〕下面開場介紹具體的噪聲的消除方法。3.3.2孤立點消除目前，孤立點的消除一般是采用4-鄰域去除方法或8-鄰域去除方法。如圖3.7所示，如果當(dāng)前處理像素f(i，j)為1，而其4-鄰域像素(i-1，j)、(i+1，j)、(i，j-1)、(i，j+1)均為0時。則將當(dāng)前處理像素置為0，X為0或1。在處理過程中發(fā)現(xiàn)，4-鄰域去除法雖然可以將孤立點去除，但也有可能將穿插點、分支點或連接點一塊除去。因此，本文采用8-鄰域去除孤立點的方法。方法同4-鄰域去除方法類似，如果當(dāng)前處理像素f(i，j)為1，判斷它的8-鄰域像素上(i-1，j)，下(i+1，j)，左(i，J-1)，右(i，j+1)，右上(i-1，j+1)，左上(i-1，j-1)，左下(i+1，j-1)，右下(i+1，j+1)。如果均為0，則將當(dāng)前處理像素f(i，j)置為0。如圖3.8所示。圖3.74-鄰域去除孤立點圖3.88-鄰域去除孤立點3.3.3空穴的消除空穴的消除與孤立點的消除正好相反，對應(yīng)的消除方法也有4-鄰域和8-鄰域兩種方法。如果當(dāng)前處理像素f(i，j)為0，在4-鄰域消除空穴的算法中，只需判斷f(i，j)的四個鄰點，而在8-鄰域消除空穴的算法中，則需要判斷f(i，j)的八個鄰點。因此4-鄰域消除空穴的算法相對于8-鄰域算法的速度要快，所以本文采用了4-鄰域消除空穴的算法。3.3.4小面積顆粒的去除利用4-鄰域法和8-鄰域法可以去除孤立像素點和空穴，但對于一些有假設(shè)干個像素組成的孤立的小面積顆粒，則不能用這兩種方法去除，可以用標(biāo)記法求面積的方法除去。這里，面積指的是某一黑色區(qū)域中所有像素值為1的點的個數(shù)。首先，對二值圖按行、列進(jìn)展掃描，將第一個掃描到的像素值為1的點進(jìn)展標(biāo)記。并且從標(biāo)記的點開場，依次將與標(biāo)記點相鄰的像素值為1的點都作同樣的標(biāo)記，直到標(biāo)記完所有與標(biāo)記相連的為1的像素點。然后，計算出所有標(biāo)記過的像素值為1的點的總數(shù)，即為該黑色塊的面積。將該面積與預(yù)先設(shè)定的面積值相比擬，如果大于給定面積值，則保存該塊面積內(nèi)的像素點。否則，就刪除該塊面積內(nèi)的像素點。對整幅二值圖作同樣的處理，最后輸出的二值圖就是去除小面積顆粒后的圖像，給定面積值可根據(jù)需要以及二值圖中顆粒和目標(biāo)的大小來設(shè)定。其具體操作可使用如下方式：在一次掃描圖像的過程中即完成圖像中連通區(qū)域的判定、區(qū)域像素點坐標(biāo)的記錄以及區(qū)域面積的計算。然后依據(jù)噪聲面積閾值遍歷圖像中連通區(qū)域鏈表，將區(qū)域面積小于閾值的區(qū)域的像素點去除(置為背風(fēng)光)。在表達(dá)圖像中連通區(qū)域提取及面積計算算法之前說明一下定義的數(shù)據(jù)構(gòu)造：定義了一個區(qū)域點坐標(biāo)鏈表，表頭結(jié)點記錄區(qū)域標(biāo)記號及區(qū)域面積值，其它結(jié)點記錄區(qū)域內(nèi)的點坐標(biāo)值，再定義一個區(qū)域表頭結(jié)點指針數(shù)組，用于記錄圖像中所有的連通區(qū)域信息。C語言描述如下：TypedefStructRegionPointNode{//區(qū)域點坐標(biāo)結(jié)點POINTpoint;//點坐標(biāo)StruetRegionPointNode*Nextpoint;//指向下一結(jié)點的指針}*LPRegionPointNode,*RegionPointList;TyPedefstruet{intRegionNo;//區(qū)域編號intRegionArea;//區(qū)域面積COLORREFRegionColor;//區(qū)域顏色LPRegionPointNodenext;}*Region;RegionAllRegion[MAX];假定二值圖像目標(biāo)像素為黑(下同)，且為了算法表達(dá)的簡潔，未考慮圖像的邊界問題，依據(jù)各邊界特點作相應(yīng)判斷。算法的主要步驟如下：STEP1：初始化AllRegion[MAX]，區(qū)域個數(shù)為0；STEP2：從上到下，從左到右掃描圖像中的每個像素：如果找到一個像素為黑且其左前!右上!正上!左上的點都不為黑，則{新建一區(qū)域鏈表RegionPointList并初始化；區(qū)域個數(shù)增1；新建一坐標(biāo)值結(jié)點PointNode，賦值當(dāng)前像素點坐標(biāo)；當(dāng)前坐標(biāo)值結(jié)點PointNode參加當(dāng)前區(qū)域鏈表中；修改區(qū)域鏈表頭信息，區(qū)域編號為當(dāng)前區(qū)域個數(shù)號，該區(qū)域面積置1；將區(qū)域表頭指針參加圖像區(qū)域數(shù)組中；}否則{根據(jù)其左前、右上、正上、左上的點的狀態(tài)確定的巧種情況，決定當(dāng)前點應(yīng)該參加的區(qū)域鏈表或者還需將兩個鏈表合并；同時修改相應(yīng)區(qū)域鏈表信息及圖像區(qū)域數(shù)組信息。}以上算法即可求得圖像中目標(biāo)連通區(qū)域的個數(shù)，每一區(qū)域的面積以及該區(qū)域的像素點坐標(biāo)。然后依據(jù)噪聲面積閾值，遍歷圖像中的區(qū)域信息數(shù)組，將小于面積閾值的連通區(qū)域的像素點去除，即可到達(dá)去除噪聲的目的。3.3.5.自動去除斑點噪聲的方法自動去除噪聲斑點的算法的根本思想是：先計算出圖像中所有目標(biāo)連通區(qū)域的面積，然后對區(qū)域面積進(jìn)展排序,找出區(qū)域面積值出現(xiàn)突變的點,即可確定為噪聲面積閾值。然后即可按上述方法進(jìn)展去噪處理。例如，對一幅含有較多斑點噪聲的線劃圖像進(jìn)展了根據(jù)區(qū)域面積的去噪實驗，通過交互式指定的某一較大斑點噪聲面積為37個像素，系統(tǒng)自動確定的噪聲面積閉值為37個像素，其區(qū)域面積及閾值如確定方法如圖3-5所示，按此閾值對原始圖像進(jìn)展去斑點噪聲后，可見在噪聲面積與目標(biāo)區(qū)域面積相差很大的情況下，本文采用的自動確定斑點噪聲閾值的方法可行，可快速準(zhǔn)確地消除輸入圖像的斑點噪聲。而在噪聲面積與局部目標(biāo)線劃面積一樣的情況下，可適當(dāng)減小噪聲面積閾值，然后通過擦除工具擦除其它斑點噪聲。圖3-9自動確定閾值示意圖3.4邊緣檢測邊緣檢測算法[5]作為圖像處理領(lǐng)域和計算機視覺方面的一大重要技術(shù)，被廣泛用來圖像的識別，跟蹤等。邊緣檢測的目的是標(biāo)識數(shù)字圖像中亮度變化明顯的點，通過邊緣檢測可以大幅度的減少數(shù)據(jù)量，去除圖像中可以認(rèn)為不相關(guān)的信息,保存圖像重要的構(gòu)造屬性。依據(jù)檢測算法的原理，邊緣檢測的方法可以分為一階梯度檢測和二階梯度檢測，常見的一階檢測算子有Canny算子、Sobel算子、羅盤算子、Prewitt算子及Roberts算子等，常見的二階梯度檢測算子有LOG、Marr-Hildreth等。由于Canny算子較好的兼容了圖像的平滑操作，對平滑后的圖像進(jìn)展邊緣檢測時有較好的效果，因此，本文基于Canny邊緣檢測算法的原理，提出了一種新的邊緣檢測的方法，該方法簡單有效的提取出了圖像的紋理信息。首先，為了方便梯度信息的計算和使用，我們對圖像進(jìn)展灰度處理，考慮到實際應(yīng)用，根據(jù)人眼的實際特點，我們選?。骸?-9〕接著，分別計算沿著x、y方向的梯度信息,梯度信息的計算使用一階有限差分來進(jìn)展近似，我們采用Sobel算子來進(jìn)展梯度信息的計算，有卷積模板：〔3-10〕然后，對圖像的梯度幅值進(jìn)展非極大值抑制，圖像梯度幅值矩陣中的元素值越大，說明圖像中該點的梯度值越大，但這并不能說明該點就是邊緣。在Canny算法中，非極大值抑制是進(jìn)展邊緣檢測的重要步驟，通俗意義上是指尋找像素點局部最大值，將非極大值點所對應(yīng)的灰度值置為0，我們這里沿用了借鑒了Canny算法的思想，對灰度圖進(jìn)展了一個簡單的非極大抑制中間處理。完成非極大抑制后，會得到一個二值圖像，非邊緣的點灰度值均為0，可能為邊的局部灰度極大值點可設(shè)置其灰度為128。最后，采用閾值法對圖像的邊緣信息進(jìn)展連接，設(shè)定上下兩個閾值，分別處理圖像，這樣就形成了一些邊緣輪廓曲線。整個過程借鑒了Canny檢測算法的優(yōu)點，結(jié)合我們實際應(yīng)用，相比canny檢測，我們的方法一方面速度上更快，另一方面，由于采用較為準(zhǔn)確的卷積模板進(jìn)展梯度信息的計算，檢測效果有較為明顯的提高。3.5邊緣跟蹤目標(biāo)檢測別離出來以后，就可以進(jìn)展邊緣跟蹤。本設(shè)計中介紹用8方向FREEMAN鏈碼對圖像中的目標(biāo)局部進(jìn)展邊緣跟蹤。鏈碼是對邊界點的一種編碼表示方法，其特點是利用一系列具有特定長度和方向的相連的直線段來表示目標(biāo)的邊界。因為每個線段的長度固定而且方向數(shù)目有限，所以只有邊界的起點需要用(絕對)坐標(biāo)表示，其余點都可只用接續(xù)方向來代表偏移量，最后通過起點的絕對坐標(biāo)與各個偏移量計算出邊緣中各點的絕對坐標(biāo)。光柵圖像一般是按固定間距的網(wǎng)格采集的，所以最簡單的鏈碼是跟蹤邊界并賦給每2個相鄰像素的連線1個方向值。最常見的是4方向和8方向鏈碼。它們的共同特點是線段的長度固定，方向數(shù)有限。對于一個八連通的圖像區(qū)域來說，由以上定義可知，區(qū)域中的每個像素，它的周圍總存在8個像素與它連接，可以為這八個像素設(shè)定從0到7的方向編號，如圖3.10所示。這樣一旦確定了像素P的位置，以及某個鄰接像素的編碼，就可以知道鄰接像素的位置。鏈碼實質(zhì)上一串指向符的序列。鏈碼表示就是從某點開場觀察領(lǐng)域的指向來表示，結(jié)果形成一個序列，因此可以用鏈碼來描述任意曲線或閉合的邊界。圖3.10鏈碼的8鄰域方向用鏈碼對圖像中的目標(biāo)進(jìn)展跟蹤的過程如下[6]：對于整個圖像進(jìn)展從上到下、從左到右的掃描，如果發(fā)現(xiàn)了一個作為前景顏色的像素(黑點)，則對和這一點相關(guān)的圖形進(jìn)展外邊緣的跟蹤，跟蹤完畢后擦除掉跟蹤得到的外邊緣內(nèi)部的所有黑像素，再對圖像進(jìn)展掃描跟蹤，直到整個圖像中已經(jīng)不再有黑色像素。對于每個特定目標(biāo)進(jìn)展外邊緣跟蹤的過程如下：從第一個邊界點開場，定義起始點的初始搜索方向為左上方；如果左上方的點是黑點，則為邊界點，否則搜索方向順時針旋轉(zhuǎn)45度。直到找到第一個黑點為止，這個黑點就是新的邊界點。新邊界點的初始搜索方向為前一邊界點到該點方向的反方向并順時針旋轉(zhuǎn)45度，用同樣的方法搜索下一點，直到返回最初的邊界點為止[7]。其算法實現(xiàn)如下：Do{n=(n+4)%8;//回到起始方向do{n=(n+7)%8;//turnarounds順時針旋轉(zhuǎn)45度NewPoint=CutPoint點在n方向上的點;}while(NewPoint不為目標(biāo)點)if(NewPoint=二StartPoint)}本次跟蹤完畢;}else{CutP0iflt=NGwPoint}while(l)其中：n表示當(dāng)前方向數(shù)，CutPoint表示當(dāng)前點，NewPofni表示在當(dāng)前點的n方向上的點，StartPoint表示起始點。3.6邊緣曲線的分段擬合圖像分割以后，鞋樣的邊緣輪廓被表示成一個個分散的像素點，數(shù)據(jù)量非常大，離需要的圖元對象還差很遠(yuǎn)，不利于進(jìn)展存儲和圖形編輯。因此，通常的處理方式是用一系列首尾相連的曲線來擬合這些點序列，以到達(dá)最終矢量化的目的。輪廓曲線通常都采用內(nèi)插曲線或者逼近曲線來實現(xiàn)擬合。在本系統(tǒng)里，一個數(shù)字化的鞋樣邊緣除了數(shù)據(jù)量大和存在毛刺以外，還具有以下三個特征：(1)存在曲率變化較緩慢的曲線段；(2)存在尖點；(3)鞋樣邊緣是閉合的；綜合以上特點，本文提出了一種分段擬合的方法對鞋樣邊緣進(jìn)展矢量化。該方法主要分為兩大步驟：步驟一：尖點提取，即通過曲率方法提取出輪廓中的尖點，防止在下一步的擬合中將尖點平滑掉，曲線特征喪失。步驟二：曲線擬合，即以尖點為分段點，對每兩個尖點之間的曲線段采用樣條曲線進(jìn)展遞歸擬合，直到精度滿足一定條件為止。以下兩節(jié)對這兩個步驟分別進(jìn)展詳細(xì)介紹[8]。3.6.1尖點提取尖點對應(yīng)曲線中具有局部曲率極大值的點，即曲線的斜率變化發(fā)生突變的點。如圖3.11中的以‘*’標(biāo)示的點即為一個尖點。尖點一般位于兩段光滑曲線的分段處，在擬合時無法用光滑的曲線表示出來，因此通常先提取出邊緣中的尖點，然后把兩個尖點之間的曲線作為一個擬合段。圖3.11尖點示意圖在數(shù)字曲線中估算曲率中余弦法和弦長比方法都是直接利用曲線上點的坐標(biāo)來計算曲率，計算比擬復(fù)雜。本文針對鞋樣邊緣閉合的特點，提出了一種間接的算法，該算法相對以上提到的各種算法計算量要小、算法簡單，并且適合任意形狀的曲線，能快速準(zhǔn)確的提取出復(fù)雜輪廓上的尖點。3.6.2算法思想設(shè)為一閉合的圖像邊緣輪廓點序列(見圖3.12)，用‘*’標(biāo)示的P(0)點為該序列的起始點，隨著i的增大，P(i)沿逆時針方向行進(jìn)一周后又回到P(0)點。由于在閉合曲線上，x和Y之間是非函數(shù)關(guān)系，因此，函數(shù)中曲率的計算公式不能直接用在此處。圖3.12閉合圖形輪廓點序列P(i)在圖3.12上可以看到，P(i)點的坐標(biāo)由X(i)和Y(i)共同決定，因此，可將P(i)分解為兩條一維離散曲線X(i)，Y(i)，(如圖3.13)，X(i)隨i的變化過程即為p(i)在水平方向上的變化，Y(i)則為P(i)在豎直方向上的變化，因此，只要分別找出曲線X(i)，Y(i)上的尖點，綜合起來，就能得到P(i)上的尖點集合。例如在圖3.12、圖3.13中，由點坐標(biāo)的變化趨勢可以看出，曲線X(i)上的尖點Px和曲線Y(i)上的尖點PY(‘*’標(biāo)示)，分別對應(yīng)曲線P(i)上的尖點PX和PY(‘*’標(biāo)示)。由于X(i)，Y(i)都是關(guān)于i的一元離散函數(shù)，因此曲率的估算簡單明了。3.6.3算法設(shè)計根據(jù)以上的曲率近似值即q值求曲線尖點的算法思想如下：以相鄰且其q值全大于0的點序列作為一個局部曲線段，找出該段曲線中q值最大的點，假設(shè)該點的q值大于某一閾值T，則將該點標(biāo)記為一個尖點，否則則為非尖點。具體設(shè)計如下，其中max用來記錄當(dāng)前段中的最大q值，k用來記錄當(dāng)前段中具有最大q值的點的序列號，T為閾值：〔1〕求曲線X(i)上的尖點計算X(i)上某一點對應(yīng)的q(i)值并進(jìn)展判斷；ifq(i)>0{ifq(i)>=max{max=q(i)；k=i；計算q(i+l)并重新開場判斷；}else{計算q(i+l)并重新開場判斷；}else{ifmax>T{將第k點標(biāo)記為尖點；mxa=0；計算〔q+1)并重新開場判斷；}else{max=0；計算〔q+1)并重新開場判斷；}}(2)求曲線Y(i)上的尖點具體過程與求X(i)上的尖點一樣。(3)綜合X(i)與Y(i)上的尖點，求原曲線P(i)上的尖點集。對于X(i)上的任意特征點PX和Y(i)上的任意尖點PY，設(shè)其點的序列號分別為j，k,假設(shè)}，則Px和Py對應(yīng)P(i)上的同一個尖點。假設(shè)}，則Px和Py對應(yīng)P(i)上兩個不同的尖點。3.6.4實驗結(jié)果及分析以以下列圖是用MATLAB[9]語言實現(xiàn)該算法并對圖3.12中的邊緣提取尖點得到的結(jié)果，(圖中‘*’代表尖點)。圖3.14(a)是在曲線X(i)上提取的尖點的情況，圖3.14(b)是X(i)中的尖點在原圖中的對應(yīng)，其中原圖中的Px(1)點對應(yīng)于X(i)中的第一個尖點，其后的以逆時針方向與X(i)中的尖點一一對應(yīng)。圖3.15(a)與圖3.15(b)則是Y(i)中的尖點提取及其在原圖中的對應(yīng)情況。圖3.14曲線X(i)上的尖點及其在原理中的應(yīng)用圖3.15曲線Y(i)上的尖點及其原理圖圖3.16綜合兩個方向上的尖點后的結(jié)果從以上結(jié)果可以看出該算法對尖點的定位是比擬準(zhǔn)確的，且適合各種形狀。在算法效率上，本算法在兩個方向上點的曲率時，分別只用到了三次加減法運算，與其他方法比擬，計算量大大減小，效率高，以下是該算法在計算某點的曲率時其計算量與余弦法和弦長比法的一個比擬：表3.1各種曲率算方法計算量的比擬本節(jié)中提出的間接方法實際上是一種基于參數(shù)方程的方法，在該方法中我們引人了一個新的參數(shù)，即點序列號i，利用該參數(shù)將點序列P(i)的坐標(biāo)變?yōu)閰?shù)方程X(i)，Y(i)的方法來表示〔3-11〕其中X(i)和Y(i)是關(guān)于i的一維離散函數(shù)，因此可以對其用函數(shù)的方法來處理。3.6.5曲線擬合1.拋物樣條曲線通過不在同一直線上的三點：，定義一條拋物樣條曲線的表達(dá)形式如下：〔3-12〕該拋物樣條曲線過三個點，并且有：(1)拋物線段以為起始點。即當(dāng)參變量t=0時，曲線過點。(2)拋物線段以點為終點，即當(dāng)參變量t=1時，曲線過點。(3)當(dāng)參變量t=0.5時，曲線過點,且切矢量等于。由以上三個條件得到方程組如下：〔3-13〕解得：

〔3-14〕將式(3-14)代入式(3-12)得：由式(3-14)可得，當(dāng)在同一條直線上時，即時，，曲線方程變成一條直線。因此在本文中的擬合基元實際上是直線和拋物樣條曲線。是一個點向量，在二維平面上它包含了兩個坐標(biāo)值[x(t),y(t)]。對該條拋物線進(jìn)展存儲和編輯時，只需對、和進(jìn)展操作。無需像數(shù)字曲線那樣對每一個點都進(jìn)展操作。在屏幕上顯示該條曲線時，可以根據(jù)參變量t的取值，計算出位于曲線上的數(shù)據(jù)點，然后順次連線繪出圖形。2.擬合算法--遞歸算法本文提出了一種遞歸的擬合方法對各個尖點之間的曲線段分別進(jìn)展擬合。該算法思想如下：以當(dāng)前離散曲線段的起點、中點和末點構(gòu)造一條拋物樣條曲線對當(dāng)前曲線段進(jìn)展擬合并進(jìn)展誤差計算，假設(shè)本段擬合的誤差小于給定的閾值，則返回；否則以當(dāng)前曲線段的中點將曲線分為兩局部再用同樣的方法分別進(jìn)展擬合，算法設(shè)計如下，其中：first表示當(dāng)前曲線段的起始點。last表示當(dāng)前曲線段的終點。T為誤差閾值，單位為像素，可以根據(jù)不同需要進(jìn)展設(shè)定Reeursive(intfirst,intlast)bew=first和last的中點；構(gòu)造依次過fisrt,bwe和last三點的拋物樣條曲線；Len=當(dāng)前段的擬合誤差；if(Len>=T){

Reeursive(first,bew);Recursive(bew,last);}else{返回;}}用這種方法依次擬合各尖點之間的曲線段，就能得到總的擬合結(jié)果。可以看出該算法對每段曲線只需用兩個簡單的遞歸語句就能實現(xiàn)擬合；相對于遺傳算法中各種復(fù)雜的遺傳、變異及穿插等操作，非常簡單且易于實現(xiàn)。3.算法分析及試驗結(jié)果由前面的分析可知，評價一個矢量化算法的根本標(biāo)準(zhǔn)是其準(zhǔn)確性和其數(shù)據(jù)壓縮率。以下就從這兩個方面對遞歸算法進(jìn)展分析：〔1〕.準(zhǔn)確性遞歸算法中遞歸的中止條件是某段曲線的擬合誤差小于誤差閾值T，假設(shè)條件不滿足，則可以對曲線進(jìn)展進(jìn)一步的細(xì)分，以進(jìn)展更準(zhǔn)確的擬合，直到滿足精度條件為止。由于T可以根據(jù)實際需要進(jìn)展設(shè)定，因此理論上遞歸算法能到達(dá)任意大小的擬合精度。但精度越大，遞歸次數(shù)越多，計算量也越大?！?〕.數(shù)據(jù)壓縮率擬合后的鞋樣邊緣可以表示為一系列首尾相連的拋物樣條曲線。由前面的分析可知一條拋物樣條曲線可以由不在同一直線上的三個點決定，因此對它們進(jìn)展存儲和編輯時無需直接操作曲線，只需存儲或編輯各段曲線的分界點及其在原始曲線上的中點，在最后顯示或切割時再用這些分界點及中點作為參數(shù)恢復(fù)出各條曲線。因此本算法的壓縮率就是原始點序列個數(shù)與分界點及中點個數(shù)的比。比率越大，則算法的壓縮效率越大。在遞歸算法中,最后得到的分界點的數(shù)量也與誤差閾值T的選取有關(guān)，T越小，擬合的精度越高，則對原曲線的分段就越細(xì)，分界點數(shù)量越多，壓縮率就越小。同樣，T越大，則壓縮率也越大。因此實際應(yīng)用中我們應(yīng)當(dāng)根據(jù)需要選擇適宜的閾值，這樣可在滿足精度的條件下減小遞歸次數(shù)，防止不必要的計算，同時還可以提高數(shù)據(jù)壓縮率。圖3.17擬合后的圖像以下各組圖片顯示了用該算法對各種形狀進(jìn)展擬合，在誤差閾值T分別取5和12的時候