基于改進(jìn)A*算法的不完整輪廓修復(fù)方法

李云青　胡斌梁　彭向前　黃怡靜

摘? 要：在利用機(jī)器視覺(jué)對(duì)一些沖壓、注塑等產(chǎn)品進(jìn)行產(chǎn)品定位或者檢測(cè)時(shí)，由于產(chǎn)品個(gè)體的差異，如模具磨損導(dǎo)致圓角局部過(guò)渡平緩等，往往會(huì)出現(xiàn)局部輪廓缺失而產(chǎn)生不完整輪廓，導(dǎo)致檢測(cè)到的產(chǎn)品位置與實(shí)際位置存在較大偏差。為了解決局部輪廓缺失引起的位置失準(zhǔn)問(wèn)題，對(duì)輪廓修復(fù)進(jìn)行了研究，提出一種極坐標(biāo)下基于改進(jìn)的A*算法不完整輪廓修復(fù)方法。首先，將輪廓目標(biāo)轉(zhuǎn)換到極坐標(biāo)下搜索出斷開(kāi)區(qū)域；其次，將完整的輪廓作為先驗(yàn)輪廓，結(jié)合先驗(yàn)輪廓與圖像灰度特征，改進(jìn)A*算法的代價(jià)函數(shù)；最終，對(duì)斷開(kāi)區(qū)域進(jìn)行最優(yōu)輪廓點(diǎn)的搜索，實(shí)現(xiàn)了不完整輪廓的修復(fù)。實(shí)驗(yàn)結(jié)果表明，該算法對(duì)不完整輪廓修復(fù)差異率均不超過(guò)8.33%，魯棒性強(qiáng)。

關(guān)鍵詞：定位；不完整輪廓；極坐標(biāo)；先驗(yàn)輪廓；A*算法；代價(jià)函數(shù)

中圖分類(lèi)號(hào)：TP391? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? 文章編號(hào)：2096-4706（2023）13-0001-06

Incomplete Contour Repair Method Based on Improved A* Algorithm

LI Yunqing， HU Binliang， PENG Xiangqian， HUANG Yijing

（School of Mechanical Engineering， Hunan University of Science and Technology， Xiangtan? 411201， China）

Abstract： In the use of machine vision for product positioning or detection of some stamping， injection molding and other products， due to the differences of individual products， such as mold wear resulting in a smooth local transition of rounded corners， there will often be local contour loss and produce incomplete contour， resulting in a large deviation between the detected product position and the actual position. In order to solve the problem of position misalignment caused by local contour missing， the contour repair is studied and a new incomplete contour repair method based on improved A* algorithm in polar coordinates is proposed. Firstly， the contour targets are converted to polar coordinates to search the disconnection area. Secondly， the complete contour is taken as the prior contour， and the cost function of A* algorithm is improved by combining the prior contour and the image gray feature. Finally， the optimal contour point is searched in the broken area， and the repair of incomplete contour is realized. Experimental results show that the difference rate of incomplete contour repair is less than 8.33%， and the robustness is strong.

Keywords： position; incomplete contour; polar coordinate; prior contour; A* algorithm; cost function

0? 引? 言

近年來(lái)，隨著機(jī)器視覺(jué)技術(shù)被廣泛地應(yīng)用在工業(yè)檢測(cè)領(lǐng)域[1]，許多沖壓零件、注塑零件也紛紛采用視覺(jué)引導(dǎo)下的自動(dòng)裝配技術(shù)。但由于沖壓件、注塑件的加工精度不一致，導(dǎo)致部分產(chǎn)品的被測(cè)輪廓出現(xiàn)退化（實(shí)際產(chǎn)品仍為合格品），在用視覺(jué)技術(shù)對(duì)這些產(chǎn)品進(jìn)行位置檢測(cè)或定位時(shí)，往往會(huì)出現(xiàn)局部輪廓缺失的現(xiàn)象，從而導(dǎo)致視覺(jué)系統(tǒng)檢測(cè)到的產(chǎn)品位置與實(shí)際產(chǎn)品位置會(huì)存在很大的偏差，繼而導(dǎo)致出現(xiàn)產(chǎn)品錯(cuò)誤裝配問(wèn)題。如圖1為某攝像頭外形輪廓檢測(cè)結(jié)果圖，其中綠色（圖1（a）中環(huán)線(xiàn)及圖2（b）中上方半環(huán)線(xiàn)）為檢測(cè)到的輪廓圖，圖1（a）為完好產(chǎn)品在進(jìn)行預(yù)處理后得到的正常八邊形輪廓檢測(cè)效果，檢測(cè)到了完整的八邊形輪廓；圖1（b）為輪廓退化產(chǎn)品進(jìn)行相同預(yù)處理過(guò)程后得到的不完整八邊形輪廓效果，只檢測(cè)到了上半部分輪廓，由此檢測(cè)到的產(chǎn)品與圖1（a）中檢測(cè)到的中心位置之間出現(xiàn)了很大的偏差。圖1（c）為某一方形墊片的檢測(cè)輪廓，輪廓中心實(shí)際應(yīng)當(dāng)在中心位置，但在出現(xiàn)輪廓缺失之后，所檢測(cè)到的中心位置與實(shí)際中心位置相比也出現(xiàn)了很大偏差。因此，常規(guī)的檢測(cè)算法如比較經(jīng)典的Sobel算子、Canny算子等輪廓提取算法[2-4]都不能解決這種由輪廓缺失造成的檢測(cè)失準(zhǔn)問(wèn)題。

針對(duì)輪廓缺失引起的不完整輪廓檢測(cè)問(wèn)題，蘭傳琳[5]將目標(biāo)輪廓的幾何形狀先驗(yàn)生成輪廓模板，然后匹配初步檢測(cè)到的不完整輪廓和輪廓模板的關(guān)鍵點(diǎn)，最后根據(jù)相應(yīng)的關(guān)鍵點(diǎn)的坐標(biāo)對(duì)輪廓模板進(jìn)行優(yōu)化，得到完整的輪廓，但對(duì)于小面積區(qū)域經(jīng)常檢測(cè)不到輪廓；雷靖[6]利用Y事件生成算法，采用了兩類(lèi)Y事件來(lái)分別修復(fù)輪廓缺失，但是對(duì)于非水平方向上大范圍的輪廓事件缺失的處理結(jié)果還不理想。尹高飛[7]在目標(biāo)識(shí)別后采用加入形狀先驗(yàn)知識(shí)的主動(dòng)輪廓模型對(duì)目標(biāo)進(jìn)行輪廓恢復(fù)，能有效地修正目標(biāo)提取結(jié)果中的輪廓缺失，但是需要足夠的先驗(yàn)形狀庫(kù)來(lái)保證輪廓恢復(fù)的精確性。

為了進(jìn)一步解決輪廓缺失引起的不完整輪廓下檢測(cè)不準(zhǔn)確的問(wèn)題，本文提出一種極坐標(biāo)下的基于改進(jìn)A*算法輪廓修復(fù)方法。首先將圖像輪廓轉(zhuǎn)換到極坐標(biāo)下，檢測(cè)其中的局部輪廓斷開(kāi)位置；其次，建立先驗(yàn)輪廓模型，將完整的輪廓作為先驗(yàn)輪廓，結(jié)合先驗(yàn)輪廓與圖像灰度特征對(duì)A*算法進(jìn)行改進(jìn)；最后，對(duì)斷開(kāi)區(qū)域進(jìn)行最優(yōu)輪廓點(diǎn)的搜索，對(duì)節(jié)點(diǎn)的鄰域點(diǎn)進(jìn)行代價(jià)比較，取代價(jià)最小的鄰域點(diǎn)作為新的節(jié)點(diǎn)，將節(jié)點(diǎn)置為輪廓點(diǎn)，并繼續(xù)對(duì)新節(jié)點(diǎn)的鄰域點(diǎn)進(jìn)行代價(jià)比較，直到搜索完斷開(kāi)區(qū)域；最終，連接所有的輪廓點(diǎn)，實(shí)現(xiàn)了不完整輪廓的修復(fù)。

1? 算法原理

首先，將圖像坐標(biāo)轉(zhuǎn)化為極坐標(biāo)[8]，在極坐標(biāo)系下判斷目標(biāo)輪廓有無(wú)斷開(kāi)，搜索出斷開(kāi)區(qū)域；然后，使用完整輪廓建立先驗(yàn)輪廓，由于本文研究的應(yīng)用場(chǎng)景在工業(yè)檢測(cè)中，每類(lèi)產(chǎn)品檢測(cè)中光照環(huán)境基本不變，待檢目標(biāo)放置固定，故不需要太多先驗(yàn)輪廓，只需確定1個(gè)完整輪廓作為先驗(yàn)輪廓即可，這樣也降低了算法復(fù)雜度，提高了檢測(cè)效率；其次，在A*算法[9]的基礎(chǔ)上，結(jié)合圖像灰度信息和先驗(yàn)輪廓改進(jìn)A*算法的代價(jià)函數(shù)，并搜索斷開(kāi)區(qū)域的最優(yōu)輪廓點(diǎn)，將斷開(kāi)區(qū)域的起點(diǎn)作為節(jié)點(diǎn)，對(duì)節(jié)點(diǎn)的5個(gè)鄰域點(diǎn)進(jìn)行代價(jià)比較，取最小代價(jià)的鄰域點(diǎn)作為新的節(jié)點(diǎn)，繼續(xù)對(duì)節(jié)點(diǎn)的鄰域點(diǎn)進(jìn)行代價(jià)比較，更新節(jié)點(diǎn)直到搜索完斷開(kāi)區(qū)域；最后，將節(jié)點(diǎn)作為輪廓點(diǎn)，連接所有的輪廓點(diǎn)，修復(fù)斷開(kāi)區(qū)域的缺失輪廓。

1.1? 極坐標(biāo)轉(zhuǎn)換

極坐標(biāo)系相較于笛卡爾坐標(biāo)系，可以將旋轉(zhuǎn)部分轉(zhuǎn)移為平移部分，如圖2所示，經(jīng)極坐標(biāo)轉(zhuǎn)化[10]之后，圖像輪廓由原來(lái)的環(huán)形轉(zhuǎn)化為一條直線(xiàn)。

笛卡爾坐標(biāo)轉(zhuǎn)化極坐標(biāo)式如下：

式中：PDi（xi，yi）表示以圖像中點(diǎn)為原點(diǎn)的笛卡爾坐標(biāo)系下的輪廓點(diǎn)，Pi（ρi，θi）表示PDi（xi，yi）

轉(zhuǎn)化的極坐標(biāo)，ρi表示極徑，θi表示極角。

輪廓點(diǎn)在笛卡爾坐標(biāo)系下，橫坐標(biāo)與縱坐標(biāo)形成不了單一的映射關(guān)系，而在極坐標(biāo)下將輪廓點(diǎn)映射到[0，2π]上，極徑與極角形成了單一的映射關(guān)系，且灰度值沒(méi)有發(fā)生變化[11]，可實(shí)現(xiàn)從上往下遍歷圖像，簡(jiǎn)化了閉合輪廓的計(jì)算過(guò)程；在笛卡爾坐標(biāo)系下，環(huán)形邊緣的灰度梯度變化以法線(xiàn)方向?yàn)橹?，與

X，Y方向存在角度差，極坐標(biāo)系下環(huán)形邊緣附近的梯度變化可直接以ρ方向?yàn)橹?，減小了計(jì)算量[12]。

如圖3所示，根據(jù)圖像目標(biāo)像素尺寸461×485，目標(biāo)徑向長(zhǎng)度在200像素左右，在轉(zhuǎn)化后的極坐標(biāo)系，以0.5°為一角度單元，對(duì)極坐標(biāo)圖進(jìn)行掃描，如果某個(gè)區(qū)域Jl（ ρ ∈（ρl1，ρl2），θ ∈（θl1，θl2））沒(méi)有搜索到連續(xù)的輪廓點(diǎn)，那么則判定該區(qū)域?yàn)檩喞笔^(qū)域，區(qū)域Jl的兩端點(diǎn)分別為Pl1（ρl1，θl1），Pl2（ρl2，θl2）。

1.2? 基于改進(jìn)的A*算法的輪廓修復(fù)

A*算法是啟發(fā)式算法中的一種，主要由實(shí)際代價(jià)和估計(jì)代價(jià)兩部分構(gòu)成，通過(guò)總代價(jià)最低在兩點(diǎn)之間選擇一個(gè)最優(yōu)路線(xiàn)[13，14]。如圖4所示，檢測(cè)對(duì)象雖然存在輪廓缺失，但是在邊緣附近的灰度變化明顯且圖像具有網(wǎng)格化，將缺失區(qū)域的兩個(gè)端點(diǎn)作為起點(diǎn)和終點(diǎn)，在先驗(yàn)輪廓和缺失區(qū)域的灰度特征的基礎(chǔ)上改進(jìn)A*算法的代價(jià)函數(shù)。

首先，構(gòu)造A*算法在本文輪廓修復(fù)中的代價(jià)函數(shù)：

式中：F表示估價(jià)函數(shù)；點(diǎn)Kb （，）表示K（ρk，θk）的5個(gè)鄰域點(diǎn)之一；G（Kb）表示起點(diǎn)Pl1到Kb的實(shí)際代價(jià)函數(shù)；H（Kb）表示Kb到終點(diǎn)Pl2的估計(jì)代價(jià)函數(shù)，Pi（ρi，θi）為先驗(yàn)輪廓曲線(xiàn)C上的點(diǎn)；gray（K）表示節(jié)點(diǎn)K的灰度值，gray（Kb）表示節(jié)點(diǎn)K的鄰域點(diǎn)Kb的灰度值；設(shè)定一條直線(xiàn)L經(jīng)過(guò)Kb與終點(diǎn)Pl2，P0表示過(guò)Kb垂直于直線(xiàn)L與先驗(yàn)輪廓曲線(xiàn)C的交點(diǎn)。

式（2）為估價(jià)函數(shù)，需要將實(shí)際代價(jià)G（Kb）（即起點(diǎn)Pl1到點(diǎn)Kb的代價(jià)）和估計(jì)代價(jià)H（Kb）（即點(diǎn)Kb到終點(diǎn)Pl2的代價(jià)）相加作為估價(jià)F，對(duì)節(jié)點(diǎn)K的5個(gè)鄰域點(diǎn)Kb計(jì)算估價(jià)F并取最小值作為最終的估價(jià)F。

式（3）為實(shí)際代價(jià)函數(shù)，邊緣處往往灰度值變化較大[15]，為了使找到的輪廓點(diǎn)更符合目標(biāo)實(shí)際輪廓，引入灰度梯度，梯度越小表示越接近邊緣即實(shí)際代價(jià)趨近最優(yōu)。

式（4）為估計(jì)代價(jià)函數(shù)，傳統(tǒng)的A*算法采用曼哈頓距離作為估計(jì)代價(jià)，為了使修復(fù)的輪廓點(diǎn)變化更符合先驗(yàn)輪廓的曲率，如圖5所示，以點(diǎn)Kb表示垂足，作垂直于直線(xiàn)L的垂線(xiàn)交于先驗(yàn)輪廓上的P0，為了盡可能利用先驗(yàn)輪廓的特征，故設(shè)步距為1對(duì)先驗(yàn)輪廓取點(diǎn)，將P0與Pl2范圍內(nèi)的先驗(yàn)輪廓點(diǎn)Pi到直線(xiàn)L的距離和作為估計(jì)代價(jià)，距離和越小表示點(diǎn)Kb越接近先驗(yàn)輪廓，即估計(jì)代價(jià)最小。

由圖3中完整輪廓極坐標(biāo)圖和不完整輪廓極坐標(biāo)圖可知，極徑和極角屬于單一映射關(guān)系，從斷開(kāi)區(qū)域的起點(diǎn)到終點(diǎn)的搜索方向?yàn)閺淖笙蛴遥瑢?duì)節(jié)點(diǎn)K周?chē)?鄰域點(diǎn)中左上、左、左下三個(gè)方向的搜索屬于無(wú)效搜索，故只取圖6中的5個(gè)方向進(jìn)行搜索。將斷開(kāi)區(qū)域的起點(diǎn)Pl1作為算法搜索的第一個(gè)節(jié)點(diǎn)K，取其中估價(jià)值最小的鄰域點(diǎn)Kb作為新的節(jié)點(diǎn)K，繼續(xù)計(jì)算節(jié)點(diǎn)K的5個(gè)鄰域點(diǎn)并取估價(jià)F最小的鄰域點(diǎn)Kb作為新的節(jié)點(diǎn)K，繼續(xù)計(jì)算節(jié)點(diǎn)K的5個(gè)鄰域點(diǎn)并取估價(jià)F最小的鄰域點(diǎn)Kb作為新的節(jié)點(diǎn)K，直到斷開(kāi)區(qū)域的終點(diǎn)Pl2作為新的節(jié)點(diǎn)K。搜索完斷開(kāi)區(qū)域后，將節(jié)點(diǎn)作為最優(yōu)輪廓點(diǎn)并連接所有的節(jié)點(diǎn)，最終修復(fù)整個(gè)目標(biāo)的輪廓。

2? 實(shí)驗(yàn)效果

通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證本文算法效果，本文算法采用C++語(yǔ)言編程，Visual Studio 2017編譯器編譯，基于運(yùn)行內(nèi)存12 GB，Windows 10 X64平臺(tái)下運(yùn)行。對(duì)不同角度輪廓缺失的攝像頭模組外殼的沖壓件進(jìn)行檢測(cè)，結(jié)果如圖7所示。

從修復(fù)不同角度區(qū)域不完整輪廓的實(shí)驗(yàn)結(jié)果看，如表1所示，本文算法能修復(fù)缺失的輪廓，對(duì)各個(gè)角度區(qū)域具有較強(qiáng)的適應(yīng)性，修復(fù)輪廓與先驗(yàn)輪廓相比曲率差異率最大不超過(guò)8.33%，表明修復(fù)的輪廓接近先驗(yàn)輪廓，由于在估計(jì)代價(jià)部分結(jié)合了先驗(yàn)輪廓信息，輪廓較平滑，節(jié)點(diǎn)突出較少，估計(jì)代價(jià)函數(shù)設(shè)計(jì)效果較好。

對(duì)方形墊片（圖8（a））進(jìn)行外圍輪廓檢測(cè)，方形墊片左下部分較亮而右上部分較暗，從墊片的二值圖（圖8（b））可看出，最外圍輪廓缺失了大部分，無(wú)法檢測(cè)到完整的輪廓；在使用本文算法之后，從效果圖（圖8（c））可看出，修復(fù)的輪廓貼近其真實(shí)輪廓，曲線(xiàn)無(wú)突出節(jié)點(diǎn)，效果較好。

對(duì)三角形的目標(biāo)（圖9（a））進(jìn)行檢測(cè)，直接進(jìn)行輪廓提取之后，檢測(cè)出的三角形中心位置出現(xiàn)了較大偏差（圖9（b））；使用本文算法之后，即使在斷開(kāi)區(qū)域角度范圍較大的情況下也能較好的修復(fù)輪廓（圖9（c））。

綜合以上實(shí)驗(yàn)結(jié)果，在檢測(cè)不完整輪廓的目標(biāo)時(shí)，本文算法能較好地修復(fù)目標(biāo)完整輪廓，能適應(yīng)不同斷開(kāi)區(qū)域的角度范圍，即使斷開(kāi)區(qū)域較小也能修復(fù)成功，魯棒性較強(qiáng)，能修復(fù)不同形狀的目標(biāo)輪廓。

3? 結(jié)? 論

為了解決局部輪廓缺失引起的位置失準(zhǔn)問(wèn)題，本文提出一種極坐標(biāo)下基于改進(jìn)的A*算法不完整輪廓修復(fù)方法，該方法先將目標(biāo)輪廓轉(zhuǎn)化到極坐標(biāo)下并搜索斷開(kāi)區(qū)域，將完整輪廓作為先驗(yàn)輪廓，利用先驗(yàn)輪廓與斷開(kāi)區(qū)域的灰度特征改進(jìn)A*算法，在斷開(kāi)區(qū)域中搜索節(jié)點(diǎn)并將節(jié)點(diǎn)作為輪廓點(diǎn)，搜索完成之后連接所有輪廓點(diǎn)，最終修復(fù)斷開(kāi)區(qū)域的輪廓。實(shí)驗(yàn)結(jié)果表明，該算法能修復(fù)不同角度缺失的目標(biāo)輪廓，對(duì)不同形狀的目標(biāo)輪廓也有較好的修復(fù)效果，但本文算法針對(duì)邊緣外凸的環(huán)形目標(biāo)輪廓修復(fù)，只對(duì)5個(gè)方向進(jìn)行輪廓點(diǎn)的尋優(yōu)，雖然節(jié)省了計(jì)算量，但是有些角度范圍會(huì)出現(xiàn)盲區(qū)，后續(xù)在研究中會(huì)進(jìn)一步完善。

參考文獻(xiàn)：

[1] 劉明.基于機(jī)器視覺(jué)的漆包線(xiàn)點(diǎn)焊定位及焊點(diǎn)質(zhì)量檢測(cè)研究 [D].廣州：華南理工大學(xué)，2021.

[2] 韋德鵬，陳繼清，羅天，等.基于改進(jìn)八方向Sobel算子的圖像輪廓提取方法 [J].現(xiàn)代電子技術(shù)，2022，45（19）：54-58.

[3] YANG Y，WEI L. Grey Relevancy Degree and Improved Eight-Direction Sobel Operator Edge Detection [J].信號(hào)與信息處理：英文，2021（2）：012.

[4] RONG W，LI Z，WEI Z，et al. An improved Canny edge detection algorithm [C]// IEEE International Conference on Mechatronics & Automation. IEEE，2014.

[5] 蘭傳琳，方佩章，何楚.基于先驗(yàn)?zāi)Ｐ蛢?yōu)化的無(wú)人機(jī)遙感圖像中幾何輪廓目標(biāo)檢測(cè)方法 [J].電視技術(shù)，2019，43（1）：5-10+65.

[6] 雷靖，張平，徐江濤，等.一種基于AER圖像傳感器的目標(biāo)完整輪廓提取方法 [J].南開(kāi)大學(xué)學(xué)報(bào)：自然科學(xué)版，2020，53（2）：62-67.

[7] 尹高飛，肖鵬峰，吳桂平，等.基于先驗(yàn)形狀的人工目標(biāo)識(shí)別與輪廓恢復(fù) [J].遙感信息，2011（6）：8-12.

[8] 張國(guó)敏，殷建平，祝恩，等.基于極坐標(biāo)區(qū)間運(yùn)算的2D形狀匹配 [J].計(jì)算機(jī)研究與發(fā)展，2008（S1）：286-290.

[9] WANG R L，LU Z Z，JIN Y F. Application of A* algorithm in intelligent vehicle path planning [J]. Mathematical Models in Engineering，2022，8（3）：82-90.

[10] XIE E，WANG W，DING M，et al. PolarMask++： Enhanced Polar Representation for Single-Shot Instance Segmentation and Beyond [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，2022，44（9）：5385-5400.

[11] 歐鎖陽(yáng)，馮琦，張堃.一種融合對(duì)數(shù)極坐標(biāo)映射和歸一化割的圖像分割算法 [J].計(jì)算機(jī)應(yīng)用研究，2012，29（10）：3990-3992.

[12] 叢軍，張輝宇，謝建，等.基于對(duì)數(shù)極坐標(biāo)變換的X射線(xiàn)焊縫缺陷圖像識(shí)別算法 [J]焊管，2022，45（2）：39-43.

[13] 陳曉宏，儲(chǔ)飛黃，方勝良，等.基于剖分網(wǎng)格改進(jìn)A*算法的航跡規(guī)劃研究 [J].電光與控制，2022，29（7）：17-21.

[14] 王衛(wèi)翼，張秋菊，陳中杰.基于圖像處理和改進(jìn)A*算法的激光切割路徑生成方法[J].現(xiàn)代制造工程，2014（10）：95-99.

[15] 張金波.灰度圖像的邊緣檢測(cè)算法研究 [D].南京：東南大學(xué)，2019.

作者簡(jiǎn)介：李云青（1998—），男，漢族，安徽宣城人，碩士研究生在讀，研究方向：圖像處理與視覺(jué)定位；通訊作者：彭向前（1980—），男，漢族，湖南雙峰人，講師，博士，主要研究方向：機(jī)器視覺(jué)和圖像處理。

收稿日期：2023-02-13

基金項(xiàng)目：國(guó)家自然科學(xué)基金（61572185）；湖南省教育廳重點(diǎn)資助項(xiàng)目（19A170）