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

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

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

中圖分類號：TP391? ? 文獻標(biāo)識碼：A? ? 文章編號：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? 引? 言

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

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

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

1? 算法原理

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2? 實驗效果

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

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

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

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

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

3? 結(jié)? 論

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

參考文獻：

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

[2] 韋德鵬，陳繼清，羅天，等.基于改進八方向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].信號與信息處理：英文，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] 蘭傳琳，方佩章，何楚.基于先驗?zāi)Ｐ蛢?yōu)化的無人機遙感圖像中幾何輪廓目標(biāo)檢測方法 [J].電視技術(shù)，2019，43（1）：5-10+65.

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

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

[8] 張國敏，殷建平，祝恩，等.基于極坐標(biāo)區(qū)間運算的2D形狀匹配 [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] 歐鎖陽，馮琦，張堃.一種融合對數(shù)極坐標(biāo)映射和歸一化割的圖像分割算法 [J].計算機應(yīng)用研究，2012，29（10）：3990-3992.

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

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

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

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

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

收稿日期：2023-02-13

基金項目：國家自然科學(xué)基金（61572185）；湖南省教育廳重點資助項目（19A170）