仲崇權　趙亮

摘 要：針對插件機器人的視覺定位系統(tǒng)，提出了一種基于圖像金字塔的霍夫變換算法，目標在于準確識別工位點坐標。改進的霍夫變換算法與傳統(tǒng)的霍夫變換算法相比減少了非零像素點的計算，并且通過限定霍夫變換算法所使用的參數，減少了內存的使用以及計算量；沿著邊緣點的梯度方向進行像素點的累加，通過先確定圓心再確定圓心所對應的半徑的方法，用二維累加器替代復雜的三維累加器，從而降低了時間復雜度和空間復雜度，提高了算法的效率。實驗結果表明，本算法能夠準確的定位PCB板的工位點，可以較好的運用在插件機器人的插件過程中。

關鍵詞：視覺定位；累加器；霍夫變換；圖像金字塔

中圖分類號：TP391.41 文獻標識碼：A 文章編號：2095-1302（2016）08-00-04

0 引 言

插件機利用機器視覺技術將一些有規(guī)則的電子元器件自動標準地插裝在印制電路板導電通孔內的機械設備中[1]。工位點識別算法對工位點的獲取起著至關重要的作用，直接影響到插件的準確度及效率。傳統(tǒng)的霍夫變換方法是一種窮盡式搜索，其時間復雜度和空間復雜度都比較高。為了克服傳統(tǒng)霍夫變換的缺陷，文獻[2]提出了一種廣義霍夫變換方法，理論上可以檢測到任意指定曲線，但在實際應用中，當需要檢測的目標物體發(fā)生旋轉或者縮放時，廣義霍夫變換的時間復雜度和空間復雜度的增長都很快；文獻[3]提出的改進后的霍夫變換算法同時利用邊緣像素的梯度和曲率來加速目標的檢測，該改進算法能夠成功的用二維累加器替代三維累加器，有效降低時間復雜度和空間復雜度，但由于直線的曲率是無窮大，當圖像中存在由許多直線組成的物體時效果很不理想；文獻[4]利用一對邊緣點來建立查找表，這種改進方法也能夠利用二維累加器代替三維累加器，但對于有部分目標物體被遮擋的圖像，檢測結果可能不太理想。

本文提出了一種基于霍夫變換的改進方法，該方法在不影響目標檢測準確度的情況下，利用圖像金字塔在低分辨率的圖像上進行目標檢測，減少了非零像素點，同時利用像素梯度以及對圓的半徑加以限定的方法，先獲取圓心再確定半徑，用二維累加器替代復雜的三維累加器，降低了霍夫變換算法的復雜度，提高了該算法的效率，保證了工位點識別算法的準確性。

1 霍夫變換與圖像金字塔

1.1 霍夫變換

霍夫圓變換是通過三維累加器獲取圓心以及半徑的一種方法[5]，具體如圖1所示，圖像上的點映射為一個三維空間中的圓錐面：（a-x0）2+（b-y0）2=r2，在xy平面，若三個點在同一個圓上，則它們對應的空間曲面相交于一點，這些點構成的邊界接近一個圓形。假設一幅大小為M×N （其中M>N）的圖像，其中非零像素點個數為Z，圖像上的每一個非零像素點所對應的圓錐面可表示為三維累加矩陣G=[ga，b，r]M×N×N/2，將Z個矩陣進行累加則得到三維累加器，0≤j≤Z-1。此累加器空間的最大值對應原始圖像的圓的參數ac，bc，rc：

1.2 圖像金字塔

圖像金字塔是一系列以金字塔形狀排列的分辨率逐漸降低的圖像集合，如圖2所示。最初用于機器視覺和圖像壓縮。金字塔最底部是待處理的原始圖像（高分辨率），頂部則是該原始圖像的低分辨率近似。當金字塔向上移動時，尺寸和分辨率降低。

圖3顯示了一個構建兩個密切聯系的圖像金字塔的簡單系統(tǒng)，第j-1級近似輸出提供建立一個近似值金字塔所需的圖像，第j級預測殘差輸出用于構建一個補充的預測殘差金字塔。在圖3中，近似和預測殘差金字塔都以一種迭代方式進行計算。在第一次迭代前，以金字塔形式描繪的圖像放在這個近似金字塔的第j級中。

（3）將輸入的第j級圖像與（2）得到的預測圖像做差，得到的結果即為第j級預測殘差。由于插件機視覺處理部分的主要目標是獲取mark點及工位點的坐標和半徑，因此在霍夫圓變換算法中，獲取圓的中心及半徑即可，之后通過高層圖像計算原始圖像中的圓心坐標以及半徑值。所以本文提出的霍夫圓獲取方法不需要預測第j級殘差，只需要第j-1級近似。

為了確定在實現過程中所用到的圖像金字塔的層數，獲取原始圖像的第二層以及第三層金字塔的圖像。通過圖4的比較可以看出第三層金字塔圖像的工位點細節(jié)丟失較嚴重，且由于分辨率較低，通過該圖像所確定的工位點坐標會對誤差較為敏感，導致工位點坐標誤差較大，插件失敗。因此選擇原始圖像的第二層金字塔圖像。假設原始圖像中非零像素點的個數為M，則二層金字塔圖像中的非零像素點的個數為M/4。圖4所示是該圖像的金字塔結果。

2 基于圖像金字塔的改進霍夫變換

霍夫變換算法是在金字塔高層的低分辨率圖像上完成的，通過確定梯度方向沿著梯度方向對累加器進行累加，提高了獲取霍夫圓的效率[7，8]；環(huán)境允許的范圍內限制半徑參數可以減少內存的使用及計算量，提高算法的運行效率。然而由于三維累加平面復雜度較高，本文提出的霍夫變換方法通過先確定圓心再確定半徑的方法，將三維累加平面變?yōu)槎S累加平面，降低了復雜度。

首先利用圖像金字塔算法得到邊緣二值圖像的二層金字塔圖像，假設圖像大小為M×N（非零像素點個數為Z），此時圖像分辨率降低，邊緣點減少。對邊緣圖像f（x，y）中的非零像素點計算其局部梯度；根據已經限定的圓的半徑范圍，將半徑在限定范圍內的像素點在二維累加器A中進行累加，此累加器用來求圓心。累加的具體方法為：對于圖像的一個非零像素點（a，b），利用Sobel算子，通過掩模來近似一階導數ga和gb，具體如圖5所示。

2.1 獲取圓心

遍歷獲得的A二維累加器對于欲獲取的圓心有三個限定條件：

（1）圓心不能處于圖像的邊緣；

（2）圓心在A二維累加器中的累加值必須大于設定的閾值param；

（3）圓心在A二維累加器中的累加值必須大于其四鄰域的累加值。然后將其按照累加值進行降序排列，則累加值較高的點即為欲獲取的圓心。獲取圓心的流程圖如圖7所示。

2.2 獲取對應圓心的半徑

獲取圓心對應半徑的流程圖如圖8所示，若在獲取候選圓心的過程中，centers中的候選圓心的個數是D，則對于每一個候選圓心（x0，y0），0≤o≤D-1。首先遍歷存儲圓參數的堆棧circle是否有已經確定了的圓的參數，若此時已經有檢測到的圓的參數，則必須當其與已檢測到的圓心點之間的距離大于設定的閾值min_dist（此閾值為欲獲取的兩個圓心之間的最小距離）時方可將該點視為欲獲取圓心，同時遍歷centers中的下一點；對R中的數據進行降序排列，即可得到該候選中心的最大支持半徑。當遍歷了centers中的每一個候選圓心點之后，circle中的值即為原始圖像中通過本論文的改進的霍夫圓獲取方法所得到的所有圓。

3 實驗結果與分析

為了檢驗插件機器人工位點識別算法的準確性，對一個需要插入六個端子的PCB板進行插件測試，本實驗通過Visual C++編程實現了基于霍夫變換的工位點識別軟件。在實際的圖像處理過程中，獲取圖像的視野大小可以設定為40 mm×30 mm，工位點的識別精度為0.01 mm，相機分辨率為40/0.01=4 000 pixcel（像素），另一方向是30/0.01=3 000 pixcel，即相機的分辨率至少需要4 000×3 000 pixcel，通過調研選擇了一款有效像素為4 384×3 288的相機。

圖9所示為實際插件過程中對工位點識別過程的截圖，在實際測試過程中，該算法能夠對工位點進行準確快速的定位，以完成插件功能，且實時性較好，插件的效率較高。

分析實驗結果可知本算法在圖像處理過程中對非零像素點的計算減少，降低了時間復雜度，提高了該算法的效率；同時利用二維累加器替代復雜的三維累加器，減少了處理內存空間的使用、降低了算法的計算量。因此本論文提出的基于霍夫變換的工位點識別算法準確度高，魯棒性好，可以較好地用于插件機器人的插件過程中。

4 結 語

本文提出的基于霍夫變換的工位點識別算法能夠準確高效的識別工位點，確定工位點的坐標。提出的基于圖像金字塔的霍夫變換算法檢測圓，在處理過程中減少了非零像素點的計算，提高了該算法的效率，保證了插件的實時性，避免了復雜的三維累加器的使用，利用二維累加器降低了時間復雜度和空間復雜度。實驗結果表明，本算法能夠準確識別PCB板的工位點，實現插件機器人的插件功能。研究成果已應用于某公司的插件機器人設備，滿足了實際對PCB板進行插件的需求。本文提出的基于霍夫變換的工位點識別算法使得插件機器人的插件過程變得更加準確、穩(wěn)定、高效。

參考文獻

[1]黃震，顧啟民.高精度機器視覺插件系統(tǒng)的研究與應用[J].組合機床與自動化加工技術， 2014（10）：105-108.

[2]張小軍， 胡福喬.基于廣義霍夫變換的芯片檢測[J].計算機工程， 2009，35（23）：252-254.

[3] Yin Yaping， Wang Yanlin， Liu Guili， et al. The Detection of Quartz that Based on the Improved Hough Transform[J].Information Technology Journal， 2012，11（4）：560-562.

[4] Chen A J， Dong G H. Efficient Method for Rapidly Detecting Circles Based on Edge-Tracking[C]. Second International Symposium on Computational Intelligence and Design. Changsha， China. 2009：402-405.

[5]秦開懷， 王海潁， 鄭輯濤.一種基于霍夫變換的圓和矩形的快速檢測方法[J].中國圖像圖形學報， 2010，15（1）：109-115.

[6]許景波， 袁怡寶.圓度測量中的高斯濾波快速算法[J].南京理工大學學報， 2007，31（3）：342-345.

[7]魏鋒， 王小林， 婁元靜.基于圖像處理技術的印刷電路板圓孔檢測方法[J].河南理工大學學報（自然科學版），2013，32（1）：69-72.

[8]肖敏.基于機器視覺的晶圓定位系統(tǒng)研究[D].上海：上海交通大學，2013.