對數(shù)字圖像快速有效的圓檢測方法

對數(shù)字圖像快速有效的圓檢測方法摘要：本文提出了兩種新的和有效的源于灰度圖像的圓檢測方法。作為一種工具，我們已經(jīng)使用了在一個方案中的蟻群算法。在其它方案中，我們使用蟻群再生和重組系統(tǒng)〔ARRS〕，自主研發(fā)的一種全新的方法。在這里提出的方案，有三個常見的步驟。首先，MATLAB邊緣檢測算子將灰度圖像轉(zhuǎn)換成一個二進制的1；然后我們應(yīng)用此二進制圖像檢測閉合回路；最后，這些閉合回路用來測試圓。方案的主要特點之一是，他們可以檢測相交和不想交的圓圈組成的不同形狀的圖像。第一個方案是傳統(tǒng)的蟻群算法修改之后的應(yīng)用程序，在計算結(jié)果方面有很準確的結(jié)果。因此，我們構(gòu)建一個新的蟻群系統(tǒng)〔ARRS〕，可以在令人難以置信的時間和內(nèi)存效率檢測出圓，使其適用于實時應(yīng)用。關(guān)鍵詞：循環(huán)檢測，圓檢測，螞蟻系統(tǒng)算法，蟻群再生和重組系統(tǒng)。1.引言從拍攝的圖像的檢測規(guī)那么幾何形狀的各種方法已經(jīng)被研究。其中Hough變換〔HT〕是最流行的一種，已被用于提取分析功能，如直線，圓，橢圓，因為它抗噪聲好。這種技術(shù)的一個嚴重的缺點是它巨大的時間和空間復(fù)雜度，時間復(fù)雜度與用于表征該形狀的參數(shù)的數(shù)目呈指數(shù)增長。本文中，我們提出了全新的方案來有效地進行圓檢測，從現(xiàn)實生活中的圖像，同時使用蟻群算法和螞蟻再生和重組系統(tǒng)〔ARRS〕，這是一種全新的算法。據(jù)我們所知，我們無法從有效的灰度圖像準確、快速地提取有關(guān)相交或者是非相交的圓的任何工作，這一點是我們論文所主要研究的。本文已被細分為8個局部。第二節(jié)將介紹我們的第一個基于蟻群算法的圓檢測方案，我們將其叫做方案I。在第三節(jié)，我們介紹了我們的方案II螞蟻再生和重組系統(tǒng)。在第四節(jié)提出了一種基于探索方案II圖形根底上改良的閉環(huán)檢測方法。第五節(jié)中提供了根本算法，用于從閉環(huán)中檢測圓。第六節(jié)為方案I和方案II提供了仿真結(jié)果，文章最后的結(jié)論和今后的工作范圍在第七局部。由于空間的稀缺性，我們無法提供預(yù)覽的蟻群算法。詳細討論這算法可在[3],[4]。2.方案I：閉環(huán)檢測中的蟻群算法基于蟻群算法的方案I由三個步驟組成：1.根據(jù)螞蟻像素強度和信息素濃度產(chǎn)生解決2.在他們的路徑封閉循環(huán)檢測和測試這些循環(huán)的圓形和橢圓形；3.信息素信息的更新。這三個執(zhí)行步驟在下面描述。首先，使用MATLAB的邊緣檢測算子〔如sobel和canny〕將現(xiàn)實生活中的灰度級圖像轉(zhuǎn)換成一個二進制1.它們將高強度梯度地區(qū)轉(zhuǎn)換到邊緣。因此，在二進制圖像中，每一個像素相關(guān)聯(lián)的強度值是0或1。這些強度值被儲存在一個二維結(jié)構(gòu)P中。Pij中P的每一個元素有四個信息字段。它們是四〔代表強度值〕，ant_token(將在后面解釋)，Phr〔存儲信息素的各像素的濃度〕和圓〔將在后面解釋〕。在成立之初，大量的螞蟻被隨機放置在邊緣像素，每一只螞蟻具有一定的記憶。它們存儲被訪問的像素，而像素是閉合回路的一局部。它們行進通過了邊緣像素同時也記下了經(jīng)歷過的數(shù)目。每當一只螞蟻試圖移動到一個新的像素，首先搜索在其附近的邊緣像素。附近居住的螞蟻〔I,J〕個像素Nij={(m,n):i-1≤m≤i+1,j-1≤n≤j+1,(m,n)變成一個邊緣像素}。搜索的方法是如果螞蟻已檢測到一個閉環(huán)是不同的，當它沒有發(fā)現(xiàn)任何的閉環(huán)時。每個像素具有ant_token的字段。螞蟻，通過一個像素移動的同時，離開它在該像素ant_token字段上的識別號。當螞蟻遇到一個像素進行識別號碼，它便會得到一個二進制的循環(huán)檢測器。這意味著，螞蟻已經(jīng)檢測到一個封閉環(huán)。循環(huán)檢測域設(shè)定在0處。循環(huán)檢測域已經(jīng)設(shè)好，螞蟻就會向仍未訪問過的邊緣像素移動。這樣做是為了防止通過相同的穿越路徑，否那么，螞蟻可以移動到它們的鄰居，那些它們訪問過的或者未訪問的至少三步驟前的邊緣像素。以防有多重選擇，對于上述的任何情況下，它會根據(jù)偽隨機分布選擇下一個像素。其中，P(M.N)是第〔M,N〕像素下一個選擇一和τmn的〔m,n〕個像素的信息素濃度的概率。一旦螞蟻檢測到一個閉合回路，它儲存在其儲存器中的像素使其閉環(huán)。這些封閉的環(huán)會根據(jù)第5節(jié)中所描述的算法檢測圓。在螞蟻算法中，螞蟻對于較重的信息素濃度路徑選擇的概率較大。在這種情況下信息素作為一個正反應(yīng)。但是，為以更好的方法探索整體圖像，在方案I中，螞蟻是基于信息素的水平較大的概率選擇路徑。因此，螞蟻被啟發(fā)探索以前任何其他螞蟻沒有訪問過的邊緣。隨著新方法，信息素的沉積規(guī)那么也改變了。當螞蟻從多個分支的起源到達一個點，它選擇的路徑僅依賴于路徑的信息素的水平。每只螞蟻也在計算它在旅行中作出決定的數(shù)量?，F(xiàn)在，一只螞蟻信息素的沉積量與必須進行決策的數(shù)量成反比。因此，如果螞蟻在其路徑中遇到許多分支，不能探索，然后就存儲信息素，是螞蟻啟發(fā)通過這條道路，去探索那些沒有訪問過的分支。此域Pij的信息被存儲在信息素。“圓〞域只有當對應(yīng)像素是一個圓的一局部時是一個特殊的標識符。因此，用統(tǒng)一的圓的像素的現(xiàn)場檢測符合我們的目的。方案I的偽代碼：主程序：initializepheromoneconcentrationoneachpixelinitializeants’memorywhile(alliterationsarenotover)placeantsrandomlyonedgepixelsallowantstoconstructtheirsolutionpathevaporatepheromonefromtheentiregraphallowantstodepositpheromonetrailontheirsolutionpathaccordingtotherulesalreadydescribeddeleteants’currentmemoryendidentifythepixelswithunity‘circle’fieldConstructionofSolutionPath:fori=1toMAXANTwhile(anthassomeedgepixelsinitsneighbortomoveinto&ithasnotreturnedtothestartingpixel)if(anthasalreadydetectedaloop)if(q>q0)searchforunvisitededgepixelwithminimumpheromoneconcentrationelsechooseanunvisitededgepixelprobabilisticallyendelseif(q<q0)searchforedgepixelwithminimumpheromoneconcentrationelsechooseanedgepixelprobabilisticallyendif(antdetectsaloop)antsetsitsloopdetectorfieldantuploadsallthepixelsinitsmemorythatconstructthelooptheloopistestedforcircleif(theloopisacircle)set‘circle’fieldsofthepixelsendendendend3．方案II螞蟻再生和重組系統(tǒng)〔ARRS〕方案I的主要缺點是，它是不確定性的方法。圖像增加的復(fù)雜性使得該算法需要更長的時間和更大數(shù)量的螞蟻。因此，我們不得不尋找一個新的基于人工螞蟻的方法，該方法將是確定性的探索邊緣像素，無論是多么復(fù)雜的圖像。本節(jié)介紹我們下面的方案II，以及它如何躲避方案I的缺點。一個字符串的邊緣像素，其中每個像素只能連接到兩個相鄰的像素，被稱為一個分支。兩個以上的分支集合的地方，我們稱之為像素的節(jié)點。一個分支采取以坐標完全描述像素的一個分支。因此，每個分支，可以表示為一個結(jié)構(gòu)，其中有兩個字段：雙向〕index：存儲識別的分支數(shù)；branch_arr[]：包含的像素的坐標的分支；每個分支被建模為一個單一的塊的鏈表當發(fā)現(xiàn)一個新的分支，一塊塊被添加到列表。每個節(jié)點還表示為一個結(jié)構(gòu)，以下字段：n.i)index：該指數(shù)為n，我們把它的第N個節(jié)點或節(jié)點nn.ii的〕〔X,Y〕坐標的節(jié)點。n.iii)連接[]：每個節(jié)點又是另一個鏈表的方框圖。一旦發(fā)現(xiàn)一個新的節(jié)點，一個新的塊便被添加到列表中。正如方案A所描述的，每只螞蟻都有一定的內(nèi)存，記錄旅行和探索的圖形。一個單一的螞蟻被表示為以下域結(jié)構(gòu)a.i)(X,Y):當前的坐標，是螞蟻移動不斷更新的。a.ii)(Xn,Yn),其原節(jié)點的坐標索引)路徑[]:這個數(shù)組存儲著它沿著分支的像素坐標。在行動前一只螞蟻發(fā)現(xiàn)邊緣像素的像素在周圍的數(shù)量，不包括它剛過來的像素〔即螞蟻不能搬回〕。對于一個分支，這個數(shù)量是1.對于一個節(jié)點，它至少有兩個〔其中跟隨定義〕，當一只螞蟻發(fā)現(xiàn)這樣一個像素，我們說它發(fā)現(xiàn)了一個節(jié)點。如果一只螞蟻移動到分支上的像素，然后更新自己的坐標和存儲的坐標上的像素的陣列，對螞蟻相鄰像素的集合是，ijth像素被定義為Nij={(p,q):i-1≤p≤i+1,j-1≤q≤j+1,(p,q)作為一個邊緣像素，類似的定義給了第三局部。如果一只螞蟻發(fā)現(xiàn)了一個節(jié)點，它意識到自己已經(jīng)過的節(jié)點和新發(fā)現(xiàn)的節(jié)點是由它所走過通過分支相互連接的節(jié)點。在這一點上，螞蟻的路徑[][]branch_arr陣列成為新發(fā)現(xiàn)的分支，這只螞蟻變?yōu)榉腔顒訝顟B(tài)〔即停止旅行〕，再現(xiàn)新的螞蟻放置他們在每一個新的分支的開始，起源于特定節(jié)點的像素。我們稱這個過程為螞蟻的再生。每只螞蟻也是一個鏈表的一塊，當一個螞蟻變得不活潑，塊對應(yīng)于螞蟻從列表中刪除。當螞蟻重生，塊被附加到鏈表。因此這個過程無論圖像是如何復(fù)雜都能進行完整的探索。事實上，放置螞蟻開始搜索的進程〔我們稱之為“媽媽〞的螞蟻〕在一個隨機選擇的邊緣像素上的。圖像的強度信息和平常一樣保存在二維數(shù)組中。媽媽螞蟻移動到一個節(jié)點〔這是第一個發(fā)現(xiàn)的節(jié)點〕和新產(chǎn)生的螞蟻從該節(jié)點沿著分支移動。到目前為止，我們觀察到螞蟻的三個特性：特性I：所有螞蟻都以相同的速度移動，即一個像素一步。特性II：螞蟻在節(jié)點產(chǎn)生的。特性III：螞蟻記得它來源于并穿過像素的節(jié)點。螞蟻這些屬性有一個有趣的結(jié)果，假設(shè)兩個節(jié)點A和B之間，有一條較短的路徑S和較長的路徑L。螞蟻是在A生成然后向B移動，沿著S更快地到達B，然后將一個新的螞蟻的像素連接L到B。因此這個新的螞蟻會沿L走向A，兩只螞蟻相向一段時間后，相遇重組。重組的螞蟻可以如下利用：i)由于每個發(fā)現(xiàn)有局部相同的分支，其路徑[]陣列可以參加后得到一個包含數(shù)組分支的像素坐標。ii)關(guān)聯(lián)矩陣，用來存儲連接圖中的節(jié)點之間的信息，可更新。這樣的重組和交換信息保障，每一個邊緣像素只被一只螞蟻訪問一次，因此，我們得到另一個特性。特性IV：一只螞蟻最終到達了死胡同，或者是節(jié)點或者是與另一只螞蟻相遇，而變得不活潑。每當ith節(jié)點和jth節(jié)點之間的聯(lián)系是通過分支K發(fā)現(xiàn)，就會進行以下操作：節(jié)點i.connectivity[K]=+1和節(jié)點j.connectivity[K]=-1否那么，這些陣列的條目被設(shè)置為零。變量B跟蹤分支的數(shù)量檢測。從分指標的陣列位置連接[]連接陣列，這些陣列探索完成后，將有長度對應(yīng)于最大的分支指數(shù)，即B。節(jié)點總數(shù)為N，現(xiàn)在我們堆棧與陣列下方的一個節(jié)點連接，從頂部的節(jié)點1開始，然后是節(jié)點2，之后節(jié)點3等等。因此，N*B矩陣形成根本而的圖的關(guān)聯(lián)矩陣。如果I=J，即來自同一節(jié)點的螞蟻的一個分支存在，檢測到它本來就是一個閉環(huán)。在這種情況下我們參加螞蟻的路徑[]陣列到像素坐標的這個分支環(huán)，然后測試它的圓形或橢圓形。ARRS的偽代碼：假設(shè)，在任何時刻的活潑的螞蟻的數(shù)量是M，檢測分支數(shù)是B，搜索結(jié)束時M=0.whileM>0i=1;whilei<=Mfindd,thenumberofedgepixelsaroundthepixeloccupiedbytheithant;if(d>1)addablocktothelistofnodes;B=B+1;addablocktothelistofbranchesandmakethepath[]arrayofthisantthebranch_arr[]ofthenewbranch;theindexofthisbranchisB;if(theantwascomingfromnodepandhasreachednodeq)nodep.connectivity[B]=+1;nodeq.connectivit[B]=-1;enddeletetheblockofthisithantfromthelistofants;placed-1newantsatthestartingpixelsofthed-1newbranchesoriginatingfromthisnodebyaddingd-1newblockstothelistofants;M=M+d-2;elseif(d=1)if(theonlypixelavailabletomoveintoisoccupiedbysomeotherant//i.e.twoantsmeet//letoneantbefromnodepandtheotherfromnodeq)deletetheblockofthetwoantsfromtheantlist;M=M-2;ifp≠qthenB=B+1;addanewblocktothelistofbranches;jointhepath[]arraysoftheantsbacktobackandmakethisthebranch_arr[]ofthenewbranch;nodep.connectivity[B]=+1;nodeq.connectivity[B]=-1;elsejointhepath[]arraysofthetwoantsandtestforcircleendelseupdatetheco-ordinatesoftheithantaccordingtotheadjacentpixelitmoves;recordtheco-ordinatesofthispixelinthepath[]array;endendi=i+1endend4發(fā)現(xiàn)閉合回路的改良算法假設(shè)一組分支K是Bk={b1，b2，…，bk}，選擇所有B分支數(shù)集，這里有兩點要注意，I.各分支與它連接的兩個節(jié)點是相關(guān)聯(lián)的。分支Bi終端節(jié)點ni1和ni2，如果Bi是一個閉環(huán)回路，那么閉環(huán)必須通過ni1和ni2。那么很明顯，如果選定的分支構(gòu)成一個閉合回路，回路必須通過那個屬于它集節(jié)點的所有節(jié)點。在一個封閉的循環(huán)，分支的數(shù)量形成回路，在回路的節(jié)點數(shù)目必須相等，即Nk的基數(shù)必須等于K。集合Nk中的每個節(jié)點都必須恰好連接到Bk兩個分支中。條件I和II是必要的和足夠的任何選定的組構(gòu)成閉合回路?，F(xiàn)在，我們的關(guān)聯(lián)矩陣，對應(yīng)于選定的分支，是增強形成一個新的N*K的矩陣，我們稱之為IK。IK是只有1，-1,0項組成的關(guān)聯(lián)矩陣。從一個分支可以連接兩個節(jié)點，一列中有兩個非零元素。Ik的每一行對應(yīng)一個節(jié)點和非零的數(shù)，在一行中的條目給出連接到的節(jié)點的分支數(shù)目。如果在Bk的分支形成一個循環(huán)，然后在C中的行對應(yīng)于屬于Nk的節(jié)點必須具有兩個非零項的每一個和所有其他行〔即不屬于集合Nk的行〕應(yīng)具有為零的條目，即如果一個行有一個非零的條目，那么它應(yīng)該正好有兩個這樣的條目，否那么其所有條目都為零。我們在一個Ik的一個細胞〔r,c〕開始，包含一個非零的條目。現(xiàn)在行r中一個非零的條目意味著另一個r中非零項的存在。我們更新行數(shù)r進入到c中的其他非零細胞。這是相當于從分支的一段移動到另一端。這個新的行也有一個非零的條目〔這個細胞〕，那么我們檢查其他非零項〔如果不存在，那么我們拒絕〕，并更新相應(yīng)的列號移動到該單元格。修改c意味著我們在其它分支，是連接到同一個節(jié)點和我們要去的這個分支的另一端〔修改r〕再到其他分支連接到端〔修改c〕等，每次檢測每個節(jié)點用條件II。我們保持一個變量P，最初設(shè)置為零。我們每一次修改，覆蓋一個分支和增量P。當P為K，即所有的分支被覆蓋，我們檢查是否已經(jīng)回到起始節(jié)點；如果是，那么條件被滿足〔條件II已經(jīng)滿足，因為我們來到這點對每個節(jié)點用條件II檢測〕，因此，形成一個封閉的循環(huán)，反之那么不行。如果我們回到起始節(jié)點P=K，那么在Bk閉環(huán)分支，否那么那么不每一次我們修改C，也會記錄在一個數(shù)組的列數(shù)。因此，該陣列將有順序，分支再形成回路。由于非零項意味著只有+1和-1，如果在一行中有兩個非零項，在該行中的所有條目的模數(shù)的總和必須是兩個。一個分支可以是一個獨特的圓圈的一局部。所以，如果我們發(fā)現(xiàn)一組分支確實形成了一個圓，假設(shè)是我們刪除所有這些分支那么不影響發(fā)現(xiàn)其他界的可能性。一旦它被發(fā)現(xiàn)，一些K個分支形成一個封閉的循環(huán)，這是一個圓圈，我們刪除的塊，分別對應(yīng)到這些分支的分支列表，兵降低總分值數(shù)B為k。我們從K=2開始，檢查所有的分支與當前的K值后，我們增加K值。每一次我們找了一組新的分支，我們檢查是否B>=K,因為B在這個過程中變化，當B小于K是，我們從圖中搜索所有可能的完整的界。5.圓檢測算法用于圓檢測的算法，從閉環(huán)的幾何屬性，通過3個非共線點可以得出一個獨特的圓圈。步驟描述如下：1.選擇三個等距點上的閉環(huán)隨機找到獨特的通過這三個點的圓的方程。2.比擬每一個回路中的其他店的圓與圓的半徑和中心之間的距離。3.如果偏差δ>ε〔閾值，這是一個函數(shù)的半徑〕，環(huán)是不被考慮為一個圓。4即使條件III滿足，如果超過四分之一上的點的環(huán)路δ>ε/2，那么放棄該環(huán)路。5.一個閉環(huán)已經(jīng)通過上述所有的四個測試被認為是一個圓。被取為可能的圓的半徑的函數(shù)的閾值ε為更大范圍的圓中，我們可以得到更大的偏差。我們選擇了ε正比于半徑，偏差常數(shù)λ，在這樣一個從或多或少的所有可見的實驗范圍從或多或少的所有可見的來確定圓圈方式。6.模擬結(jié)果方案二的結(jié)果：我們測試我們的兩套不同的圖像上的算法，在逐漸增加的復(fù)雜性，以表格的形式提供的圖像的系統(tǒng)性能的比擬研究。定時信息的結(jié)果是平均超過10運行。圖5：不同的封閉循環(huán)檢測到的原始圖像在最后一組，考慮圖像具有不同的形狀。圖像大小為300*300像素的邊緣像素的總數(shù)是1160.探索時間為0.532秒，回路測試時間是0.703秒。方案二的時間效率從上面的結(jié)果是顯而易見的。但是，該方案是內(nèi)存使用效率。存儲器被用來存儲i)二維矩陣，對應(yīng)于圖像的像素的強度信息〔ii〕該坐標像素相對應(yīng)于每個發(fā)現(xiàn)的分支〔iii〕關(guān)聯(lián)矩陣通過分支結(jié)構(gòu)存儲不同節(jié)點間的連接信息。因此，內(nèi)存的使用率最高只有在勘探結(jié)束時。7.結(jié)論和未來的工作這里介紹的兩種方法是完全新穎的。I方案的缺點促使我們尋找更好的方法，我們找到了方案II。因為我們已經(jīng)能夠探測到閉合回路，我們可以從圖像中檢測到任何類型的封閉輪廓。我們的下一個嘗試將是從不同形狀圖像中找出橢圓形和平行四邊形。此外，我們的方案的時間復(fù)雜度和內(nèi)存的要求沒有，，與其他現(xiàn)有的方法比擬，如Hough變換和基于遺傳算法的方法。工程上的進步，我們試圖比擬我們的算法與計算時間參數(shù)的根底上，提出了內(nèi)存的使用