改進(jìn)的摩爾鄰域圖像邊緣追蹤算法及應(yīng)用

關(guān)鍵詞：摩爾鄰域；邊界追蹤；終止準(zhǔn)則；尺寸標(biāo)注

中圖分類號(hào)：TP391.9 文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2024）28-0034-03

0 引言

隨著計(jì)算機(jī)與人工智能技術(shù)的快速發(fā)展，人們對(duì)圖像處理領(lǐng)域的研究愈發(fā)深入，針對(duì)圖像的噪聲檢測與去除、圖像深度恢復(fù)、圖像增強(qiáng)、圖像輪廓的識(shí)別和追蹤等方面的研究備受關(guān)注。近年來，關(guān)于圖像的自動(dòng)尺寸標(biāo)注在生產(chǎn)與生活中的應(yīng)用也日益增多。例如，宗加飛[1]等提出將尺寸標(biāo)注技術(shù)應(yīng)用于機(jī)械工業(yè)生產(chǎn)中，采用計(jì)算機(jī)視覺進(jìn)行圖像的檢測與尺寸的標(biāo)注，相較單純地采用人工視覺檢測的方法，具有更高的準(zhǔn)確性和檢測速度，從而有效地提高了生產(chǎn)率。

在圖像尺寸標(biāo)注工作中，一個(gè)關(guān)鍵步驟是尋找圖像的輪廓，所涉及的算法稱為邊界追蹤算法。目前，主流智能手機(jī)中的“測距儀”具備對(duì)圖像尺寸進(jìn)行標(biāo)注的功能，其基本原理是攝像頭測量目標(biāo)兩端的距離，手機(jī)內(nèi)置的陀螺儀測量目標(biāo)兩端的角度值，然后運(yùn)用三角函數(shù)計(jì)算出目標(biāo)的長度。然而，這一功能存在兩方面的局限：一是該測距功能僅適用于測量近處的物體，如果目標(biāo)物體距離較遠(yuǎn)，通過“測距儀”測出的長度誤差會(huì)較大；二是測距儀需要人工手動(dòng)校正物體的兩端，因此其準(zhǔn)確性和精確性與手工校正有較大關(guān)聯(lián)，測量的隨機(jī)誤差較大。

Square追蹤算法是近年來備受關(guān)注的邊界追蹤算法之一[2]，它可以實(shí)現(xiàn)對(duì)簡單圖形的邊界追蹤，但其適用范圍有限，不能提取邊緣變化較多的圖形輪廓。本文在分析傳統(tǒng)Square追蹤算法的基礎(chǔ)上，提出了一種改進(jìn)的基于摩爾鄰域的邊界跟蹤算法，可以解決圖像追蹤過程中無法提取復(fù)雜圖案完整外邊界的問題，并將其應(yīng)用于圖像的邊界處理，進(jìn)一步實(shí)現(xiàn)了圖形的自動(dòng)尺寸標(biāo)注功能。

1 問題提出

1.1 物體尺寸標(biāo)注的一般流程

傳統(tǒng)的尺寸標(biāo)注方法采用人工檢測的方式，存在檢測效率低、精度差的缺點(diǎn)，同時(shí)長時(shí)間的測量易導(dǎo)致質(zhì)檢員視覺疲勞，測量誤差增大。因此，采用計(jì)算機(jī)視覺通過圖像處理的方式對(duì)物體尺寸進(jìn)行自動(dòng)標(biāo)注，特別是在大批量物體的尺寸測量中，展現(xiàn)出測量效率高、誤差小、成本低的優(yōu)勢，其應(yīng)用范圍廣泛。

尺寸標(biāo)注的一般流程[3]：

1） 使用攝像頭采集圖像，并通過相應(yīng)的軟件從計(jì)算機(jī)上讀取目標(biāo)圖像。

2） 對(duì)讀取的圖像進(jìn)行預(yù)處理，操作步驟包括：灰度處理、高斯濾波、腐蝕、膨脹、邊緣檢測等。

3） 在提取圖像邊緣的基礎(chǔ)上尋找圖形輪廓。

4） 計(jì)算各個(gè)輪廓的中心點(diǎn)坐標(biāo)。

5） 設(shè)置參照物，計(jì)算實(shí)際尺寸與像素尺寸的比例，據(jù)此求出實(shí)際尺寸，并顯示結(jié)果。

1.2 傳統(tǒng)Square 邊界追蹤算法

Square追蹤算法是提取二值圖像中邊界信息的基本算法之一[4]，其應(yīng)用涉及像素點(diǎn)的4鄰域，其對(duì)圖形邊界的提取流程如下：對(duì)于給定的數(shù)字圖像（圖像由像素組成，這里用像素說明），即在網(wǎng)格上以白像素為背景的一組像素，需要確定一個(gè)邊界像素起始點(diǎn)（黑色），定位起始像素點(diǎn)有許多方法；在這里，從左下角的像素開始，掃描每行像素，從下往上、從左向右進(jìn)行直到遇到第一個(gè)黑色像素，選定這個(gè)像素為起始點(diǎn)。算法將從該起始點(diǎn)出發(fā)，展開后續(xù)的邊界追蹤工作，其步驟如下：

1） 若搜索時(shí)位于黑色像素點(diǎn)上，則向左進(jìn)入相鄰的像素點(diǎn)。

2） 若搜索時(shí)位于白色像素點(diǎn)上，則右轉(zhuǎn)進(jìn)入相鄰的像素點(diǎn)。

3） 搜索過程直到再次遇到起始點(diǎn)時(shí)終止。

4） 整個(gè)搜索過程中經(jīng)過的黑色像素所連成的邊界即為數(shù)字圖像的邊界。

然而，該追蹤算法存在明顯的缺陷[5]：不能追蹤現(xiàn)實(shí)生活中復(fù)雜圖形的輪廓，其性能存在一定的局限性。原因在于：向左或者向右轉(zhuǎn)時(shí)會(huì)錯(cuò)過當(dāng)前像素點(diǎn)對(duì)角線側(cè)的像素，即性能上具有只對(duì)特殊鄰接性圖形有效的弱點(diǎn)，Square邊界追蹤算法對(duì)具有8鄰域而不是4鄰域模式的圖形邊界無法實(shí)現(xiàn)有效的追蹤。失敗案例如圖1所示。

1.3 邊界追蹤算法步驟

通過對(duì)傳統(tǒng)Square追蹤算法的觀察，發(fā)現(xiàn)圖像尺寸標(biāo)注工作中一個(gè)關(guān)鍵步驟是如何尋找圖形輪廓[6]，其涉及的算法為邊界追蹤算法，首先對(duì)圖像進(jìn)行基本的處理：1） 圖像灰度化以提高運(yùn)算速度。2） 圖像二值化，二值化過程可以大大減少圖形中的數(shù)據(jù)量，使目標(biāo)輪廓更加凸顯。

邊界追蹤算法的一般步驟總結(jié)為：

1） 確定邊界的起始點(diǎn)，并從該點(diǎn)出發(fā)展開搜索，搜索方式可以是從左往右、自下而上等。

2） 確定邊界點(diǎn)的判別方式以及搜索準(zhǔn)則，判別方式用來判斷該點(diǎn)是否為邊界點(diǎn)，搜索準(zhǔn)則用來對(duì)下一個(gè)邊界點(diǎn)展開搜索。

3） 確定終止條件，這將影響邊界追蹤的結(jié)果是否為一個(gè)完整的輪廓。

為了提高邊界追蹤的成功率，在以上下左右四個(gè)方向?yàn)榛A(chǔ)的4鄰域上加入對(duì)角領(lǐng)域拓展至順時(shí)針8 領(lǐng)域，運(yùn)用摩爾鄰域追蹤的思想對(duì)原算法進(jìn)行改進(jìn)。

2 改進(jìn)的摩爾鄰域追蹤算法

對(duì)于給定的像素p，其摩爾鄰域是一組與原像素共享邊或頂點(diǎn)的像素集合，即在原來上、下、左、右的基礎(chǔ)上加上了左上、左下、右上、右下4個(gè)對(duì)角元素，將原來的4鄰域擴(kuò)展至包含對(duì)角鄰域的8鄰域，又被稱為間接鄰域。

該算法對(duì)圖形邊界提取的流程如下：

1） 確定一個(gè)起始像素點(diǎn)，定位起始像素的方式很多，可以從網(wǎng)格的左上角開始，從上而下以及從左往右掃描每一列像素，直到遇到第一個(gè)黑色（邊界）像素點(diǎn)，將該像素點(diǎn)作為起始像素點(diǎn)。

2） 每次遇到黑色像素，將其設(shè)置為邊界點(diǎn)。然后原路返回到先前到達(dá)的白色像素，以順時(shí)針方向搜索摩爾鄰域內(nèi)的每一個(gè)像素，直到遇到下一個(gè)黑色像素。

3） 重復(fù)步驟2） 的過程，當(dāng)起始像素被第二次訪問時(shí)，算法終止，在整個(gè)運(yùn)行過程中經(jīng)過的黑色像素即是數(shù)字圖案的邊界。

摩爾鄰域邊界跟蹤算法是8鄰域搜索過程，對(duì)比邊界追蹤算法的一般步驟，其弱點(diǎn)在于停止準(zhǔn)則的選擇。參照?qǐng)D2，如果該停止準(zhǔn)則選取不當(dāng)，算法將無法有效對(duì)圖形的完整輪廓進(jìn)行追蹤。因此，對(duì)停止準(zhǔn)則的優(yōu)化會(huì)有效提升摩爾鄰域邊界跟蹤算法的整體性能。

我們可以采用以下的優(yōu)化方式去改進(jìn)原摩爾鄰域邊界跟蹤算法的停止準(zhǔn)則：第二次搜索至起始像素點(diǎn)時(shí)，進(jìn)入該點(diǎn)的方向與第一次相同時(shí)停止。圖2中的追蹤過程雖然再次回到起始點(diǎn)，但過程中遺漏了大部分的邊界像素點(diǎn)，其原因在于沒有滿足停止準(zhǔn)則。圖3在圖2的追蹤結(jié)果上繼續(xù)展開邊界追蹤，直到滿足停止準(zhǔn)則為止。通過對(duì)比圖2與圖3的結(jié)果，改進(jìn)后的算法有效地提高了摩爾鄰域跟蹤算法的執(zhí)行效果。

分析圖2與圖3區(qū)別的原因：摩爾鄰域追蹤算法在檢查當(dāng)前邊界像素點(diǎn)的摩爾鄰域時(shí)，相比4鄰域搜索方式更加全面且有效，能夠更準(zhǔn)確地找到下一個(gè)邊界像素點(diǎn)。對(duì)于傳統(tǒng)Square跟蹤算法向左右兩邊轉(zhuǎn)時(shí)忽略了對(duì)角側(cè)的像素點(diǎn)問題，摩爾鄰域跟蹤算法提取到的圖案外邊界更加完整。因?yàn)槟栢徲驗(yàn)?鄰域搜索方式，這將導(dǎo)致其搜索的下一個(gè)邊界像素點(diǎn)總是位于當(dāng)前像素點(diǎn)的摩爾鄰域內(nèi)。當(dāng)算法兩次以相同的方向追蹤到起始像素點(diǎn)，這表明算法已追蹤完圖案完整的邊界。如果算法沒有終止，則會(huì)再次重復(fù)追蹤該像素點(diǎn)。

3 基于改進(jìn)摩爾鄰域的邊緣追蹤算法實(shí)驗(yàn)效果與實(shí)際應(yīng)用

3.1 實(shí)驗(yàn)效果

為了進(jìn)一步驗(yàn)證采用基于改進(jìn)摩爾鄰域的邊緣追蹤算法與Square追蹤算法對(duì)不同圖像進(jìn)行輪廓追蹤的效果，在Windows 環(huán)境下，本文采用PyCharmCommunity Edition 2022.2.2 作為軟件工具，選用3 幅圖像圖4（a）、（b）、（c）展開實(shí)驗(yàn)對(duì)比驗(yàn)證。

對(duì)圖4進(jìn)行以下步驟的處理：

1） 讀入彩色圖像，并引入gray_img函數(shù)實(shí)現(xiàn)彩色圖像灰度化。

2） 調(diào)用get_binary_img函數(shù)實(shí)現(xiàn)圖像二值化。

3） 展開邊界追蹤，過程中調(diào)用了canny邊緣檢測函數(shù)、findcontour輪廓提取函數(shù)、drawcontour輪廓繪制函數(shù)等。

在原摩爾鄰域邊界跟蹤算法停止準(zhǔn)則的優(yōu)化方面，調(diào)用Python中math包的sin（）函數(shù)模塊。具體步驟如下：

1） 導(dǎo)入math包，使用math.radians（）方法將邊界起始點(diǎn)與終止點(diǎn)之間的角度轉(zhuǎn)換為弧度。

2） 計(jì)算弧度的正弦值并判斷其值是否等于正負(fù)1。如果是，則終止搜索；反之，則從該邊界點(diǎn)繼續(xù)展開追蹤。

圖5 展示了分別對(duì)圖4 中3 幅不同圖像執(zhí)行Square追蹤算法進(jìn)行輪廓追蹤的效果。明顯地，圖5（e）和（f）的邊界追蹤存在嚴(yán)重缺失。

圖6展示了分別對(duì)圖4中3幅不同圖像執(zhí)行本文提出的基于改進(jìn)摩爾鄰域的邊緣追蹤算法進(jìn)行輪廓追蹤的效果。圖6中的3幅子圖完美保留了原圖4中圖像的完整外邊界輪廓。

3.2 實(shí)驗(yàn)結(jié)果分析

對(duì)比圖5和圖6的執(zhí)行結(jié)果可以得出：

1） 對(duì)于如圖4（a）所示的邊界清晰、變化簡單的圖形，Square追蹤算法的輪廓提取效果較為理想。

2） 對(duì)于輪廓邊界變化復(fù)雜的圖形，如圖4（b）、（c），Square追蹤算法只能追蹤到圖形的局部外邊界。

3） 本文提出的改進(jìn)摩爾鄰域追蹤算法可以提取邊界變化復(fù)雜圖形的完整輪廓。

3.3 算法的實(shí)際應(yīng)用

進(jìn)一步將改進(jìn)的摩爾鄰域追蹤算法運(yùn)用于實(shí)際圖片的邊界追蹤，并進(jìn)一步實(shí)現(xiàn)自動(dòng)尺寸標(biāo)注，具體操作步驟如下：

1） 運(yùn)用基于改進(jìn)摩爾鄰域的邊緣追蹤算法提取目標(biāo)圖像的邊界輪廓。

2） 定義圖像中物體所占的像素?cái)?shù)與物體實(shí)際比例的關(guān)系，根據(jù)參照物的實(shí)際長度與寬度，調(diào)用pixel_per_cm函數(shù)計(jì)算單位長度中的像素個(gè)數(shù)。

3） 計(jì)算被測物體輪廓的最小外接矩形。如果等輪廓是圓，找出與輪廓擬合的中心和最小半徑來計(jì)算最小外接矩形；如果等輪廓不是圓，在輪廓的頂點(diǎn)上循環(huán)，獲取當(dāng)前和前一個(gè)頂點(diǎn)的坐標(biāo)，求這兩個(gè)頂點(diǎn)的中點(diǎn)，重復(fù)此過程將輪廓擬合成圓以計(jì)算最小外接矩形，循環(huán)過程中調(diào)用minAreaRect（）與boxPoints（）函數(shù)，并獲取4個(gè)頂點(diǎn)的坐標(biāo)。

4） 調(diào)用Width與Height函數(shù)，根據(jù)4個(gè)頂點(diǎn)與單位長度中像素的個(gè)數(shù)，計(jì)算測量物體的長度與寬度。圖7（a）和（b）是物品原圖和運(yùn)用改進(jìn)的摩爾鄰域追蹤算法進(jìn)一步進(jìn)行圖像自動(dòng)尺寸標(biāo)注的結(jié)果圖。

表1列出了圖7（a）中展示的5種物品的真實(shí)尺寸與利用本文提出的基于改進(jìn)的摩爾鄰域追蹤算法進(jìn)行邊界自動(dòng)檢測并完成尺寸標(biāo)注的結(jié)果，其中相對(duì)誤差是真實(shí)值和測量值的誤差與真實(shí)值的比值。

分析表1中的尺寸標(biāo)注結(jié)果和相對(duì)誤差，可以發(fā)現(xiàn)自動(dòng)尺寸標(biāo)注的結(jié)果比較接近真實(shí)值，算法有效。個(gè)別物品的測量相對(duì)誤差較大，這與原始圖片的清晰度與像素也有關(guān)聯(lián)。

4 結(jié)束語

本文提出的改進(jìn)摩爾鄰域邊界追蹤算法適應(yīng)當(dāng)下關(guān)于尺寸標(biāo)注越來越廣泛的技術(shù)應(yīng)用現(xiàn)狀，針對(duì)傳統(tǒng)的Square追蹤算法在提取復(fù)雜圖形輪廓方面的局限性，提出由傳統(tǒng)以上、下、左、右4個(gè)方向?yàn)榛A(chǔ)的4 鄰域拓展至加入對(duì)角鄰域后的8鄰域追蹤方式。在此基礎(chǔ)上，從優(yōu)化終止準(zhǔn)則入手，著重解決了圖像追蹤過程中無法提取復(fù)雜圖形完整外邊界的問題，并進(jìn)一步將算法運(yùn)用于實(shí)際物品的自動(dòng)尺寸標(biāo)注中。實(shí)驗(yàn)結(jié)果表明，本文提出的摩爾鄰域改進(jìn)算法對(duì)實(shí)際物體圖形尺寸能夠進(jìn)行有效的標(biāo)注。