幾何圖形的識(shí)別和編輯

類型：課程設(shè)計(jì)題目：幾何圖形的識(shí)別和編輯主要是直線和圓的識(shí)別，這在工程圖的識(shí)別和其他領(lǐng)域中都 4 4第二節(jié)在工程圖的識(shí)別中常用的方法 4第三章論文的工作基礎(chǔ)和工作環(huán)境 6第一節(jié)數(shù)字圖像處理技術(shù) 6 6 6第二節(jié)圖像格式－BMP格式 7第三節(jié)算法及數(shù)學(xué)基礎(chǔ) 8 82.基于單義域的直線及圓識(shí)別算法 第四章直線和圓的識(shí)別和編輯的實(shí)現(xiàn) 第一節(jié)系統(tǒng)的層次結(jié)構(gòu)的圖示 第二節(jié)系統(tǒng)數(shù)據(jù)結(jié)構(gòu)及類的設(shè)計(jì) 第三節(jié)主程序?qū)崿F(xiàn) 第四節(jié)系統(tǒng)功能介紹 第五節(jié)總結(jié)及展望 錯(cuò)誤!未定義書(shū)簽。第一章概述計(jì)算機(jī)技術(shù)的發(fā)展，使人類社會(huì)進(jìn)入了信息化和自動(dòng)化，計(jì)算機(jī)智能識(shí)別也隨著計(jì)算機(jī)的發(fā)展得到了迅速的發(fā)展。特別是圖形圖像的計(jì)算機(jī)處理技術(shù)更是有了前所未有的進(jìn)步和應(yīng)用。計(jì)算機(jī)識(shí)別也逐漸的從圖形圖像處理的大環(huán)境下分離出來(lái)作為一門(mén)新的高科技研究領(lǐng)域出現(xiàn)。圖形圖像的識(shí)別涉及到的學(xué)科很多，包括數(shù)字信號(hào)處理、工程數(shù)學(xué)、信息論、運(yùn)籌學(xué)、等，它與計(jì)算機(jī)、自動(dòng)化、生物學(xué)、關(guān)學(xué)、視覺(jué)心里和生理學(xué)、人工智能、智能信息處理等眾多領(lǐng)域交叉、綜合集成，有廣泛的應(yīng)用。識(shí)別基本的圖元直線和圓。直線和圓是二值圖像中最基本的組成元素，也是最常見(jiàn)的圖形元素。在工程圖的數(shù)字化識(shí)別中有很大的應(yīng)用。2.本論文中圖像中的圖元都是單一的線性，即線寬是一個(gè)象素的情況。第二節(jié)在工程圖的識(shí)別中常用的方法圖形的識(shí)別最主要的是圖形特征的提取，在這個(gè)階段，常用的方法是全局特征方法（包括：不變距，自回歸模型、傅立葉描述符、霍夫變換等），全局特征的特征提取方法是理論比較完善的，計(jì)算過(guò)程比較清楚。針對(duì)不同的特征在二值圖像的處理中，人們常用的數(shù)據(jù)結(jié)果有游程編碼－考慮了掃描行上），在兩個(gè)方向上的推廣。在本論文中就是利用了LAG的數(shù)據(jù)結(jié)構(gòu)思想與c++builder的數(shù)據(jù)結(jié)構(gòu)相結(jié)合的方法即：用下一個(gè)象素點(diǎn)是與鏈表頭相鄰還是和尾本論文中對(duì)交點(diǎn)的處理。目前對(duì)交點(diǎn)的處理有下面幾類算法：1.基于網(wǎng)格算法，該算法是通過(guò)網(wǎng)格加大搜索步長(zhǎng)來(lái)跳過(guò)交點(diǎn)。2.基于圖段合并的算法，是根據(jù)交點(diǎn)處行程段的連通性，以交點(diǎn)為界將圖線分割成圖段，記錄各段之間的連接及從屬關(guān)系，然后連接或延長(zhǎng)各分支圖段，然后得到整條圖線。在本論文中采用了第二種方法，基于圖段合并的算法。第二章論文的工作基礎(chǔ)和工作環(huán)境第一節(jié)數(shù)字圖像處理技術(shù)將客觀世界實(shí)體或圖片等通過(guò)不同的量化(數(shù)字化)手段送入計(jì)算機(jī)，由計(jì)算機(jī)按使用要求進(jìn)行圖像的平滑、增強(qiáng)、復(fù)原、分割、重建、編碼、存儲(chǔ)、傳輸?shù)确N種不同的處理，需要時(shí)把加工處理后的圖像重新輸出，這個(gè)過(guò)程稱為圖像處理。因此，圖像處理的含義是用計(jì)算機(jī)對(duì)圖像進(jìn)行加工處理以得到某種預(yù)期的效果，它本質(zhì)上是一種二維數(shù)字信號(hào)處理技術(shù)。1.圖像處理的基本內(nèi)容以改變或強(qiáng)調(diào)圖像信息的某些特點(diǎn)(增強(qiáng)有用信息，無(wú)用信息)，改善圖2.描述圖像的特征并進(jìn)行特征抽取和分析。用某個(gè)標(biāo)準(zhǔn)衡量并進(jìn)行分類比較，將抽取的特征歸結(jié)為一定的模式，這屬于模式識(shí)別的范圍；對(duì)圖像的某些部分合并或進(jìn)行重新組織，這種技術(shù)是從N—1維的信息用某種算法得到N維的圖像，例如計(jì)算機(jī)視覺(jué)就是這樣的一種技術(shù)。2.主要的圖像處理技術(shù)它不追究圖像客觀質(zhì)量的降低原因。圖像的視覺(jué)質(zhì)量是因人而異的，其質(zhì)量的高低和好壞受觀看者的心理、愛(ài)好和文化素質(zhì)等因素的影響。圖像的恢復(fù)則致力于探索圖像質(zhì)量降低的原因，并盡可能消除圖像質(zhì)量的降低，恢復(fù)圖彩色數(shù)字圖像通常是由三個(gè)二維數(shù)組組成的，其信息量相當(dāng)大，這給圖像的傳輸、處理、存儲(chǔ)和顯示等帶來(lái)很大的負(fù)擔(dān)。但問(wèn)題的另一方面是圖像中又往往存在很多冗余信息，在傳輸和存儲(chǔ)時(shí)可以對(duì)數(shù)字圖像進(jìn)行一定方式的編碼，刪除圖像中的冗余信息，以提高圖像傳輸和存儲(chǔ)的效率。不同角度的投影圖，通過(guò)計(jì)算可得到物缽內(nèi)部的圖像，這種技術(shù)稱為投影重計(jì)算機(jī)按照一定的客觀測(cè)度(例如灰度、顏色和幾何性質(zhì)等)將圖像中包含的物體和區(qū)域從圖像中區(qū)分出來(lái)，稱為圖像的分割。用適當(dāng)?shù)臄?shù)學(xué)語(yǔ)言來(lái)表示被分割出來(lái)的物體或區(qū)域的結(jié)構(gòu)和統(tǒng)計(jì)特性，或用數(shù)學(xué)語(yǔ)言表示區(qū)域問(wèn)的關(guān)系，稱為描述。圖像經(jīng)分別和描述后，可較為容易地分類和識(shí)別。第二節(jié)圖像格式－BMP格式式與顯示設(shè)備有關(guān)，因此把這種BMP圖像文件格式稱為設(shè)備相關(guān)位圖位圖文件的組成位圖文件的組成位圖文件頭BITMAPFILEHEADER位圖信息頭BITMAPINFOHEADERBYTE第三節(jié)算法及數(shù)學(xué)基礎(chǔ)1.霍夫變換（HoughTransform）霍夫變換是圖像處理中從圖像中識(shí)別幾何形狀的基本方法之一。其基本思想就是把圖像平面上的點(diǎn)對(duì)應(yīng)到參數(shù)平面上的曲線，最后通過(guò)統(tǒng)計(jì)特性來(lái)解決分遮蓋的不敏感等特性，霍夫變換在模式識(shí)別領(lǐng)域得到廣泛的應(yīng)用，如直線、下面就于本論文相關(guān)的直線和圓的識(shí)別進(jìn)行簡(jiǎn)單的介紹。圖像空間中同一直線上的點(diǎn)，經(jīng)霍夫變換所形成的直線相交于參數(shù)空間中的一點(diǎn)，該點(diǎn)坐標(biāo)代表圖像空間中直線的斜率及截距。利用累加數(shù)組累計(jì)參數(shù)空間中通過(guò)該點(diǎn)的直線條數(shù)，即代表圖像空間中直線上的點(diǎn)數(shù)。設(shè)已知一黑白圖像上畫(huà)了一條直線，要求出這條直線所在的位置。我們知和截距。過(guò)某一點(diǎn)(x,y)的所有直線的參數(shù)都會(huì)滿足方程y=kxx+b。即圖像空間中的一點(diǎn)(x,y)確定了參數(shù)空間中的一族直線。方程y=kxx+b在參數(shù)k--b平面上是一條直線。這樣，圖像x--y平面上的一個(gè)前景像素點(diǎn)就對(duì)應(yīng)到參數(shù)平面上的一條直線。Step2.對(duì)于圖像上每一前景點(diǎn)，求出參數(shù)平面對(duì)應(yīng)的直線，把這直線上的所有點(diǎn)的值都加1。Step3.找到參數(shù)平面上峰值點(diǎn)的位置，這些位置的坐標(biāo)就是原圖像上直線的參數(shù)，每個(gè)位置對(duì)應(yīng)于原圖像上的一條直線。的直線方程沒(méi)有辦法表示x=c形式的直線（這時(shí)候，直線的斜率為無(wú)窮大）。上。在變換后的空間中這條正弦曲線上的任意一點(diǎn)對(duì)應(yīng)于原始圖像平面(x,y)空過(guò)變換后所對(duì)應(yīng)的各正弦曲線都相交于一點(diǎn)。利用霍夫變換檢測(cè)出半徑已知的圓形，是將圖像平面上的每一點(diǎn)對(duì)應(yīng)到參數(shù)平面上的一個(gè)以已知半徑為半徑的圓。經(jīng)過(guò)霍夫變換，在參數(shù)平面上得到圓相交于一點(diǎn)，這個(gè)點(diǎn)的坐標(biāo)即為原圖形坐標(biāo)平面上待識(shí)別的圓心坐標(biāo)。算法可以簡(jiǎn)單描述為：取和圖像平面一樣的參數(shù)平面，以圖像上每一個(gè)前景點(diǎn)為圓心，以已知的半徑在參數(shù)平面上畫(huà)圓，并把結(jié)果進(jìn)行累加。最后找出參數(shù)平面上的峰值點(diǎn)，這個(gè)位置就對(duì)應(yīng)了圖像上的圓心。應(yīng)圓的圓心和半徑。圖像平面上的每一點(diǎn)就對(duì)應(yīng)于參數(shù)空間中每個(gè)半徑下的一個(gè)圓，在參數(shù)的三維空間中得到一個(gè)圓錐。最后找出參數(shù)空間中的峰值點(diǎn)，即得到待識(shí)別的圓的圓心和半徑。受圖像旋轉(zhuǎn)的影響，在很多領(lǐng)域都有廣泛的應(yīng)用，有關(guān)霍夫變換的研究和改進(jìn)也很多。例如廣義霍夫變換、隨機(jī)霍夫變換、快速霍夫變換等等，就是針對(duì)直線的霍夫變換也有很多改進(jìn)算法。由于時(shí)間的原因，在本軟件中，只是使用了2.基于單義域的直線及圓識(shí)別算法霍夫變換為幾何圖形的識(shí)別的一個(gè)重要算法，但是由于該標(biāo)準(zhǔn)算法的時(shí)間復(fù)雜度和空間復(fù)雜度都是O(Nm),其中m是參數(shù)坐標(biāo)的維數(shù)，雖然有不少針對(duì)具體問(wèn)題（例如直線識(shí)別）的改進(jìn)算法，其在實(shí)際使用中也存在計(jì)算量大的問(wèn)題。針對(duì)本論文的工作的實(shí)際情況，參考文獻(xiàn)【1】，并進(jìn)行了適當(dāng)?shù)暮?jiǎn)化，單義域是指對(duì)待識(shí)別的圖形進(jìn)行分割得到的具有單一的幾何意義（線段或圓?。c(diǎn)的集合。對(duì)圖片進(jìn)行從上往下、從左往右的掃描，根據(jù)交點(diǎn)進(jìn)行分割得到多義域，多義域中的點(diǎn)構(gòu)成一個(gè)連通區(qū)域。對(duì)多義域進(jìn)行識(shí)別并分割得到多義域由鏈表實(shí)現(xiàn)。算法描述如下：尾節(jié)點(diǎn)不是交點(diǎn)）節(jié)點(diǎn)進(jìn)行比較，如果與頭節(jié)點(diǎn)相鄰，將其插入到該多義域的頭節(jié)點(diǎn)之前；如果與尾節(jié)點(diǎn)相鄰，將其插入到該多義域的尾節(jié)點(diǎn)之后。注：交點(diǎn)的判斷。續(xù)的識(shí)別過(guò)程中將把不是單義域的進(jìn)行分裂。2.2最小二乘法擬合直線和圓最小二乘法首先由KarlGauss為進(jìn)行行星最小二乘法已經(jīng)變成從實(shí)驗(yàn)數(shù)據(jù)來(lái)進(jìn)行參數(shù)估計(jì)的主要手段。由最小二乘法獲一個(gè)數(shù)學(xué)程式，通過(guò)它能獲得一個(gè)在最小方差意義上與實(shí)驗(yàn)數(shù)據(jù)最好擬合助模運(yùn)用最小二乘法進(jìn)行圓的擬合公式如下：運(yùn)用最小二乘法進(jìn)行直線擬合的公式如下：2.3多義域分裂和單義域的識(shí)別對(duì)2.1中得到的多義域，運(yùn)用最小二乘法進(jìn)行擬合，對(duì)于擬合不成功的多義域運(yùn)用首尾相連最大距離法進(jìn)行分裂，得到單義域，并記錄下各單義域的擬合結(jié)果，供全局考慮，識(shí)別直線和圓用。2．對(duì)選中的多義域運(yùn)用最小二乘法進(jìn)行圓的擬合；如果得到的平均徑向弧的單義域；記錄擬合的結(jié)果，作為總體識(shí)別的種子圓，轉(zhuǎn)向5執(zhí)行，3．對(duì)選中的多義域運(yùn)用最小二乘法進(jìn)行直線擬合；如果得到的平均距離段的單義域；記錄擬合結(jié)果，作為總體識(shí)別的種子直線，轉(zhuǎn)向5執(zhí)行，4．該多義域?yàn)槎鄠€(gè)線段或圓弧的組合。將該多義域的頭尾節(jié)點(diǎn)連接，計(jì)域進(jìn)行分裂，得到兩個(gè)新的多義域，取代原先的多義域；轉(zhuǎn)向2執(zhí)行。由此，所有的多義域都分裂為單義域，并對(duì)各單義域進(jìn)行了擬合。2.4總體整合，識(shí)別直線和圓對(duì)2.3得到的單義域列表進(jìn)行總體的整合，得到直線和圓。1．選取單義域列表中的第一個(gè)單義域，將其擬合的圖形（直線或圓）作2．將列表中其他單義域的識(shí)別結(jié)果與種子圖形進(jìn)行比較，如果誤差小于指定閾值，則屬于同一直線或同一圓，將其與選定單一域進(jìn)行合并，3.主要技術(shù)3.1BorlandC++Builder＋＋圖形設(shè)備接口(GDI)，使得用戶很方便地在應(yīng)用程序添加圖像或處理圖像。第三章直線和圓的識(shí)別和編輯的實(shí)現(xiàn)第一節(jié)系統(tǒng)的層次結(jié)構(gòu)的圖示第二節(jié)系統(tǒng)數(shù)據(jù)結(jié)構(gòu)及類的設(shè)計(jì)1.主要類的層次結(jié)構(gòu)圖形基類，提供所有圖形的標(biāo)準(zhǔn)屬性和方法。其他圖形類（直線、圓）等都是該類的子類，繼承其所有的public屬性和方法，對(duì)其中的虛方法（virtual）該類為虛類，其成員函數(shù)主要為虛函數(shù)，為其所有子類提供統(tǒng)一的接口，但是沒(méi)有實(shí)現(xiàn)。其他模塊對(duì)圖形進(jìn)行操作時(shí)，除非生成新的實(shí)例（Instance現(xiàn)、擴(kuò)充和維護(hù)提供很大方便。public:/*屬性定義*///前景色（由于時(shí)間等的限制，本系統(tǒng)暫時(shí)只定義該圖形的屬性，其//他如：填充色，線條型，填充型等可擴(kuò)充）/*編輯用屬性*///編輯時(shí)標(biāo)志該圖形是否被選擇//編輯操作所選中的點(diǎn)/*識(shí)別用屬性*///識(shí)別的效果描述，值越小說(shuō)明識(shí)別效果越好//最小二乘法的平均誤差；//霍夫變換：1-參數(shù)空間中該圖形的值/最大值//圖形上點(diǎn)的數(shù)量/*成員函數(shù)定義*//*顯示和描述用方法*///顯示圖形：在指定的位圖上顯示圖形//描述圖形：作為T(mén)treeView的節(jié)點(diǎn)（主窗體使用）/*識(shí)別用*///直線上的兩個(gè)線段；圓上面的兩個(gè)圓弧//合并兩個(gè)圖形//經(jīng)過(guò)判斷為相同的圖形進(jìn)行合并，返回True；否則返回False。//判斷圖形存在的可能性（利用具體圖形的幾何規(guī)則）/*編輯用*///判斷是否點(diǎn)擊該圖形，若選中則當(dāng)前編輯的圖形改為當(dāng)前圖形//取得鼠標(biāo)形狀：鼠標(biāo)移動(dòng)到選中圖形的可操作點(diǎn)上時(shí)，顯示為編輯形狀//更新圖形：將編輯點(diǎn)移動(dòng)到(x,y)點(diǎn)。更新成功返回True，否則False。};3.圖形類（CLine、CCircle）圖形類是幾何圖形的具體實(shí)現(xiàn)，實(shí)現(xiàn)對(duì)應(yīng)幾何圖形的描述和相關(guān)操作。圖根據(jù)要求，本系統(tǒng)中實(shí)現(xiàn)了直線（CLine）和圓（CCircle）兩個(gè)圖形類。其他簡(jiǎn)單的幾何圖形如橢圓、矩形等也可以類似的方法實(shí)現(xiàn)，作為本系統(tǒng)的一斜式不能描述豎直直線，也避免極坐標(biāo)方程轉(zhuǎn)換的問(wèn)題）。因?yàn)槌杀壤膬山M端點(diǎn)為軸進(jìn)行旋轉(zhuǎn)；2）線段的中點(diǎn)，選中中點(diǎn)并移動(dòng)，是平移整個(gè)直線。publicpublic:/*初始化*//*直線的屬性*///線段的兩個(gè)端點(diǎn)/*對(duì)父類虛方法的實(shí)現(xiàn)*///在目標(biāo)位圖上畫(huà)出直線（本系統(tǒng)中的實(shí)現(xiàn)為畫(huà)線段）//在TTreeView中描述//返回描述用字符串//判斷該直線是否與指定圖形相同//將指定圖形強(qiáng)制轉(zhuǎn)化為CLine類型，比較其參數(shù)A,B,C，//若小于指定閾值，則返回Ture，否則返回False。//合并同一直線上的兩個(gè)線段//若目標(biāo)圖形與該圖形屬同一直線，進(jìn)行合并，返回True；//判斷是否選擇該直線進(jìn)行編輯。//判斷指定點(diǎn)(x,y)到該直線的距離，//如果小于指定閾值則返回True，否則False。//取得鼠標(biāo)形狀。//中點(diǎn)時(shí)返回垂直的四個(gè)方向箭頭的形狀表示移動(dòng)//更新直線};public:/*初始化*/CCircle(intargX,intargY,intargR);/*圓的屬性*///圓心//半徑intR;/*對(duì)父類虛方法的實(shí)現(xiàn)*///在目標(biāo)位圖上畫(huà)出圓//在TTreeView中描述//返回描述用字符串////判斷該圓是否與指定圖形相同//將指定圖形強(qiáng)制轉(zhuǎn)化為CCircle類型，比較其參數(shù)圓心坐標(biāo)和半徑，//若小于指定閾值，則返回Ture，否則返回False。//合并同一圓上的兩個(gè)圓弧//若目標(biāo)圖形與該圖形屬同一圓，進(jìn)行合并，返回True；//判斷是否選擇該圓進(jìn)行編輯。//計(jì)算指定點(diǎn)(x,y)到圓心的距離，并與半徑比較，//如果小于指定閾值則返回True，否則False。//取得鼠標(biāo)形狀。//圓上點(diǎn)時(shí)返回水平的雙向箭頭形狀表示改變半徑；//圓心時(shí)返回垂直的四個(gè)方向箭頭的形狀表示移動(dòng)//更新圓};織對(duì)圖像的識(shí)別結(jié)果、組織當(dāng)前編輯工作的圖形對(duì)象集。提供添加圖形、刪除public:/*初始化*///在目標(biāo)位圖上畫(huà)出所有的圖形//描述圖形};5.點(diǎn)類（CPoint）點(diǎn)類對(duì)于與圖像上的前景點(diǎn)。由于識(shí)別時(shí)需要判斷是否為交點(diǎn)，在一般的public:/*初始化*//*屬性：是否為交點(diǎn)*/};在“基于單義域的圖形識(shí)別算法”中，單義域和多義域的唯一區(qū)別就是多義域不是單一的幾何元素，其在存儲(chǔ)結(jié)構(gòu)上是一樣的，在本系統(tǒng)中，都由刪除點(diǎn)、判斷該單義域是否有識(shí)別價(jià)值、識(shí)別該單義域等接口和方法。public:/*初始化*//*識(shí)別該單義域：實(shí)現(xiàn)算法中對(duì)單義域的識(shí)別部分*///如果識(shí)別成功（得到圓或線段）返回True，否則返回False/*嘗試添加新的點(diǎn)到該單義域*///判斷該點(diǎn)是否屬于該單義域并確定是在頭部還是在尾部，并將其插入到適當(dāng)位置；如果該點(diǎn)為交點(diǎn)，則將相應(yīng)的方向關(guān)閉增長(zhǎng)；若加入成功返回True，/*/*判斷該單義域是否有識(shí)別價(jià)值*///如果該單義域含有的點(diǎn)數(shù)太少，則沒(méi)有價(jià)值返回False，否則返回True。/*屬性：識(shí)別出的圖形*/};基于單義域識(shí)別類是實(shí)現(xiàn)“基于單義域的直線和圓識(shí)別算法”的主要類。它實(shí)現(xiàn)了對(duì)目標(biāo)圖像的分割、對(duì)分割結(jié)果的顯示、對(duì)識(shí)別得到的多義域進(jìn)行分割、對(duì)單義域識(shí)別結(jié)果的總體考慮，最終得到識(shí)別結(jié)果集。得到。用來(lái)組織對(duì)圖像的單義域分割后的結(jié)果。。public:/*構(gòu)造和析構(gòu)函數(shù)*//*掃描圖像，得到多義域*///從上往下