基于機器視覺的最大內接矩形快速檢測算法

鄒哲康，朱錚濤，陳映謙，孟令龍，王瑞豐

(廣東工業(yè)大學 機電工程學院,廣州 510006)

0 引言

不規(guī)則多邊形的最大內接矩形的檢測對于皮革裁切、板材邊角料再利用等工業(yè)場景有著重大的影響。目前，國內許多工廠仍是以純人工的方式進行裁定的，人工裁定通常是根據(jù)工人的經(jīng)驗來確定矩形，這種方式存在很強的主觀性，不僅容易造成資源浪費，而且效率也很低。使用機器視覺技術是生產制造業(yè)邁向高效化、智能化、經(jīng)濟化的一個關鍵途徑，實現(xiàn)自動化生產能在大大節(jié)約人力成本、材料資源的同時還能顯著提高生產的效率，而其中存在的最大難題便是如何快速準確地檢測出目標物體的最大內接矩形。

隨著計算機視覺的振翮和工業(yè)智能化的發(fā)展，圖像處理技術已經(jīng)廣泛應用于工廠的自動化生產當中[1]。趙鳳[2]等人研究了基于灰度和非局部空間灰度特征的二維Otsu曲線閾值分割法。本文團隊[3]于2019年研究了大理石板的圖像分割方法，此方法速度快且精度達到預期要求。吳曉光[4]等人研究了獲取圖像區(qū)域最小外接矩形的算法。這些都為檢測不規(guī)則物體最大內接矩形提供了思路。對于求解最大內接矩形，謝新華[5]等的研究表明目標物體的擺放角度會影響最大內接矩形檢測，其提出的遍歷中心擴散法雖有較高的準確率，但其算法時間復雜度高，耗時巨大，不適合運行在高速運轉的自動化流水作業(yè)當中。袁哲[6]等人提出了基于改進遺傳算法的任意圖形最大內接矩形求解法，該方法的適應變化規(guī)律顯示其需要遺傳60代以上才能獲得較為理想的最大內接矩形，顯然也不符合快速檢測的原則。

針對以上問題，本文在謝新華[5]等人的研究基礎上，提出一種快速高效的最大內接矩形檢測算法：邊界排序生長法。該方法能在極短的時間內有效地檢測出理想的內接矩形，采用該方法結合標定的攝像頭就能實現(xiàn)目標物體最大內接矩形的高速檢測。

1 系統(tǒng)算法實現(xiàn)

目標物體最大內接矩形檢測過程分為圖像預處理和矩形檢測兩個部分。首先，傳入工廠提供的實驗數(shù)據(jù)圖像，對這些數(shù)據(jù)圖像進行處理，得到適合檢測的圖像。然后運用不同的視覺檢測算法找到其最大內接矩形并記錄算法運行時間及內接矩形的面積。像處理的總體流程包括圖像采集、圖像語義分割、圖像幾何變換、邊緣檢測、最大內接矩形檢測，算法總體流程如圖1所示。

圖1 算法流程圖

具體算法步驟如下：

1)首先將工廠提供的大理石板材毛胚圖像進行語義分割，保留圖像中需要的部分；

2)選取分割后的圖像的最大連通域，將其轉換為二值圖像并進行平移變換，使得目標物體坐落于圖片的中央位置；

3)對平移后的圖像進行旋轉變換，使得目標物體與水平方向平行；

4)檢測物體的邊緣，并記錄外邊緣的坐標信息；

5)通過視覺檢測算法，找到目標物體的最大內接矩形。

2 圖像預處理

2.1 提取ROI

提取ROI(region of interest)指的是將圖像中需要的物體從背景中分離出來。相比直接將整個圖像作為算法輸入，提取ROI能排除背景產生的干擾，以供后續(xù)算法檢測出最優(yōu)的最大內接矩形。由于大理石板材紋路的復雜性，利用傳統(tǒng)圖像處理的方法很難將其準確地分割，因此，本文采用深度學習中的語義分割網(wǎng)絡來提取采集好的大理石板圖像的ROI。

本實驗使用孟令龍等[3]于2019年發(fā)布的針對大理石板材分割的高效語義分割網(wǎng)絡，模型結構如圖2所示。該模型在U-Net的基礎上修改卷積層的通道數(shù)以減少運算量，使得模型的推理速度減少到5 ms左右。同時加入含有空洞卷積的RASPP模塊以獲得更大的感受野[7]。最后，輔以Focal Loss來擬合出更準確的結果。Focal Loss定義如式(1)，其中α為平衡因子，用來平衡本身比例不均的正負樣本，γ是調節(jié)損失函數(shù)的一個超參數(shù)，其值通常設置為2，p為模型的預測，是一個概率，其值介于0～1之間。大理石板材圖片的語義分割效果如圖3(b)所示。

圖2 語義分割模型

(1)

2.2 旋轉擺正

目標物體的擺放方向切中了算法找到最大內接矩形面積的肯綮。為了得到面積最大的內接矩形，需要將目標物體旋轉到與水平方向平行的位置，即使得目標物體水平方向上的最小外接矩形最小。

在旋轉前需要將目標圖像移動到圖片中央位置以最大程度上避免目標物體旋轉后超出圖像邊界。首先求取圖像的中心以及目標物體的中心，圖像中心如式(2)所示，中心點橫坐標記為center_x,縱坐標記為center_y，其中img_w代表圖片的寬度，img_h代表圖片的高度。

(2)

使用OpenCV中的“cv2.moments”函數(shù)求取目標物體的各階矩，并根據(jù)函數(shù)返回的矩值得到目標物體的重心[8]，即該物體的中心，將中心點的橫坐標記為Cx，縱坐標記為Cy，可由公式(3)計算得出:

(3)

其中:M00為目標物體的零階矩；M10和M01均為目標物體的一階矩。

求得圖像中心和目標物體中心后可根據(jù)公式(4)計算出橫坐標需要移動的距離dx與縱坐標需要移動的距離dy，即圖像中心與目標物體中心橫坐標與縱坐標的差值。

(4)

根據(jù)所求得的dx和dy將目標圖像平移變換到圖片中央位置，用空間變換矩陣表示如式(5)，式中M為變換矩陣。平移變換后的結果如圖3(c)所示：

(5)

選取平移變換后的圖像的最大連通域，根據(jù)其標定區(qū)域邊界的像素點集找到目標物體的最小外接矩形[4]，如圖3(d)所示。選取最小外接矩形中橫坐標最小的頂點和縱坐標最小的頂點，分別記為(left_x,left_y)和(top_x,top_y)，根據(jù)如下公式求出最小外接矩形和水平方向的夾角θ。

(6)

利用公式(6)求得的角度θ，對圖像進行旋轉變換。用空間變換矩陣表示為式(7)。

[x′,y′,1]=[[x,y,1]M

(7)

式(7)中的M為變換矩陣，有順時針和逆時針兩種形式：

(順時針)

(逆時針)

旋轉后的圖像如圖3(e)所示。目標圖片旋轉后的最小外接矩形如圖3(f)所示，證明此時的目標物體已經(jīng)擺放水平。

圖3 大理石板材圖像預處理

2.3 邊緣檢測

邊緣指的是圖像中不連續(xù)性的特性，如灰度、紋理結構以及顏色的突變等，是物體與背景之間的重要信息。邊緣檢測[9]是指提取目標圖像的邊緣輪廓信息并丟棄非相關的其他信息。對數(shù)字二值圖像進行拓撲分析[10]來確定圖像的外邊界，以非壓縮的形式記錄所有外邊界的輪廓點并保存于數(shù)組當中，即保存的相鄰的兩個點的像素位置之差不超過1。

3 最大內接矩形檢測

3.1 遍歷法

遍歷法的思想是遍歷所有邊界點，在其中找面積最大的矩形作為結果，其主要原理如下：

1)以邊緣檢測所得數(shù)組中的第一個邊界點作為初始點，記為A1，從A1起向右移動直到到達圖像的邊界，即到達像素值為0的位置，記為A2，再從A2向下移動直到再次到達圖像的邊界，記為A3，再從A3向左移動直到到達圖像邊界，記為A4。若在移動點到達邊界前的x坐標等于A1的x坐標則需要提前停止移動，并在此記為A4。由A2、A3、A4構成矩形1。

2)將過程1選取的初始點A1記為B1，從B1起向下移動直到到達圖像的邊界，即到達像素值為0的位置，記為B2，再從B2向右移動直到再次到達圖像的邊界，記為B3，再從B3向上移動直到到達圖像邊界，記為B4。相應的，在移動點到達邊界前的y坐標等于B1的y坐標時也需要提前停止移動，并在此記為B4。由B2、B3、B4構成矩形2。

選取邊緣檢測所得數(shù)組中的下一個邊界點作為初始點，往復過程1和2，直到遍歷完目標物體所有的邊界點，選擇其中面積最大的矩形為檢測結果，算法原理如圖4所示，該方法檢測效果如圖5(a)所示。

圖4 遍歷法檢測原理

圖5 不同方法檢測效果對比

3.2 中心擴散法

3.2.1 確定擴散中心

經(jīng)過預處理中的平移變換后，整幅圖像的中心就是目標物體的中心點，因此，可由公式(2)確定目標物體的中心點，中心點橫坐標記為center_x，縱坐標記為center_y。

定義left、right、top、bottom四個初始變量，變量的初始值與中心點的對應關系分別由公式(8)所示的關系確定：

(8)

3.2.2 向外擴散

1)以(left,top)和(right,top)兩點確定一條直線，判斷該直線是否在目標圖像區(qū)域內，即該線段內所有的點的像素值都不為0，若該線段在目標圖像區(qū)域內，則向上擴展，即變量top減去1，若該直線已經(jīng)到達了目標物體的邊界，則停止向上擴展。

2)以(left,top)和(left,bottom)兩點確定一條直線，判斷該直線是否在目標圖像區(qū)域內，即該線段內所有的點的像素值都不為0，若該線段在目標圖像區(qū)域內，則向左擴展，即變量left減去1，若該直線已經(jīng)到達了目標物體的邊界，則停止向左擴展。

3)以(left,bottom)和(right,bottom)兩點確定一條直線，判斷該直線是否在目標圖像區(qū)域內，即該線段內所有的點的像素值都不為0，若該線段在目標圖像區(qū)域內，則向上擴展，即變量bottom加1，若該直線已經(jīng)到達了目標物體的邊界，則停止向下擴展。

4)以(right,bottom)和(right,top)兩點確定一條直線，判斷該直線是否在目標圖像區(qū)域內，即該線段內所有的點的像素值都不為0，若該線段在目標圖像區(qū)域內，則向上擴展，即變量right加1，若該直線已經(jīng)到達了目標物體的邊界，則停止向右擴展。

依次往復1～4過程，直到四條直線都到達物體的邊界，此時這四條直線構成的矩形便是中心擴散法的檢測結果。其檢測效果如圖5(b)所示。

3.3 遍歷中心擴散法

該方法的作者認為其同時具有遍歷法的準確性和中心擴散法的適用性。原理是首先計算由(2)式確定的目標圖像中心點的位置，然后對該點向上、下、左、右移動一些位置來改變中心點的坐標，利用中心擴散法以這些點為中心點檢測內接矩形并記錄，直到遍歷完所有的“中心點”，選取所找到的內接矩形中面積最大的一個作為該方法的檢測結果。以向上、下、左、右增加或減少1至3個像素為例，共使用了49個點，其檢測效果如圖5(c)所示。

3.4 邊界排序生長法

邊界排序生長法的思想是以最快的速度選定一個最有可能成為最大內接矩形的初始矩形，對其超出的部分進行收縮，不足的部分進行擴張，從而達到又快又準的效果。主要分為選擇初始矩形、逆生長和生長三個步驟。

3.4.1 選擇初始矩形

搜尋目標物體邊界點中橫坐標與縱坐標之和最大的點和最小的點，以及橫坐標與縱坐標之差最大的點與最小的點。將以上四個點的橫坐標與縱坐標分別按從小到大排序，取其中排第二的橫坐標和縱坐標記為(x1,y1)，排第三的橫坐標和縱坐標記為(x2,y2)，以(x1,y1)為左上角(x2,y2)為右下角確定初始矩形。

3.4.2 逆生長

對于不同形狀的目標物體，其選擇出的初始矩形不一定會完全落在目標圖像區(qū)域內。因此，對于初始矩形超出的部分要進行一系列收縮操作，該過程類似于中心擴散法的逆過程。

判定(x1,y1)和(x2,y1)兩點確定的直線是否在目標圖像區(qū)域內，即該線段內所有的點的像素值都不為0，若已經(jīng)超出目標圖像區(qū)域，則x1加上1；判定(x1,y1)和(x1,y2)兩點確定的直線是否在目標圖像區(qū)域內，若已經(jīng)超出目標圖像區(qū)域，則y1加上1；判定(x1,y2)和(x2,y2)兩點確定的直線是否在目標圖像區(qū)域內，若已經(jīng)超出目標圖像區(qū)域，則x2減去1；判定(x2,y1)和(x2,y2)兩點確定的直線是否在目標圖像區(qū)域內，若已經(jīng)超出目標圖像區(qū)域，則y2減去1，依次重復以上4個步驟，直到該矩形完全進入到目標圖像內，即完成了“逆生長”。

3.4.3 生長

同樣地，“逆生長”后的矩形有時也含有一定的生長空間，既該矩形四條邊不一定都能達到目標圖像的邊界，因此，要對該矩形進行相應的擴散操作，以獲得最大的內接矩形。

首先，將“逆生長”后矩形的左上角的坐標(x1,y1)與右下角的坐標(x2,y2)分別對應中心擴散法的四個初始數(shù)值left、top、right、bottom，然后使用中心擴散法對逆生長后的矩形繼續(xù)擴散，直到該矩形的四個邊都抵達目標物體的邊界，即進行所謂的“生長”。將擴散后的矩形作為邊界排序生長法的檢測結果。

邊界排序生長法的檢測過程可由圖6表示，圖中的不規(guī)則五邊形代表待檢測的目標物體，左側矩形區(qū)域代表選定的初始矩形，箭頭代表該矩形需要“逆生長”的方向，中間圖片的矩形區(qū)域表示初始矩形“逆生長”后的矩形，周邊的箭頭表示該矩形需要“生長”的方向，右側矩形為左側矩形沿箭頭方向“生長”后的矩形，即邊界排序生長法的檢測結果。邊界排序生長法的檢測效果如圖5(d)所示。

圖6 生長示意圖

4 實驗結果與分析

本文實驗設備為AMD R31200@3.4 GHz CPU，32 GB 2 933 MHz內存，NVIDIA GTX 1660 6 GB顯卡，64位Windows10操作系統(tǒng)。實驗使用python3.6語言在jupyter notebook編譯環(huán)境下結合OpenCV、time及Numpy模塊編程實現(xiàn)。其中使用“cv2.threshold”函數(shù)將灰度圖轉換為二值圖，使用“cv2.findContours”函數(shù)獲取目標圖像的輪廓，使用“cv2.minAreaRect”函數(shù)確定目標圖像的最小外接矩形，使用“cv2.moments”函數(shù)計算目標圖像的各階矩并由此推導出目標圖像的中心，使用“cv2.getRotationMatrix2D”函數(shù)和“cv2.warpAffine”函數(shù)對圖像進行平移、旋轉變換等[11]操作。

為了研究遍歷中心擴散法的不同遍歷量對檢測面積及速度的影響，本文采用了以目標物體中心點為中心的3×3、7×7、11×11、15×15方格內的所有點作為“中心點”的遍歷中心擴散法對4種不同形狀的板材進行驗證，以矩形包含的像素點數(shù)表示檢測面積的大小，檢測面積與耗時如表1所示。為了研究4種方法的檢測效果及運行速率，本文使用4種方法分別對8種不同形狀的板材進行驗證，其中遍歷中心擴散法的遍歷量為225個點，以矩形包含的像素點數(shù)表示檢測面積的大小，檢測面積與耗時如表2所示。

表1 不同遍歷量的遍歷中心擴散法檢測結果對比

表2 4種方法的檢測結果對比

本文通過控制變量法，研究同一石板在不同算法下的檢測面積及計算耗時。表1結果顯示遍歷中心擴散法的檢測結果與選取的“中心點”數(shù)呈正線性相關，隨著選取的“中心點”數(shù)的增多，該方法的檢測結果越接近完美，但其相應的檢測耗時也會成倍增長。由圖7第三行子圖和表2可知，遍歷法有很好的魯棒性，但在應用于凹多邊形時有一定的機率出現(xiàn)錯誤，分析其原理不難得出遍歷法在運用于凹多邊形時，矩形的最后一條邊有可能因超出目標圖像邊界而導致出錯。并且該算法時間復雜度高，不適合應用與對速度有高需求的場景中。由圖7第三行結果可以看出，中心擴散法在每個方向上的擴散速度都是相同的，因此在處理長條狀的多邊形時效果極為不理想。由表2和圖7可以得出，邊界排序生長法不僅檢測效果好，適用性廣，而且檢測速度大大領先其他三種方法，能在5 ms的時間內完成檢測，因此更適合應用于對速度有高要求的不規(guī)則多邊形最大內接矩形檢測場景。

圖7 不同形狀石板四種方法檢測結果

5 結束語

本文通過分析其它方法發(fā)不足之處，思考并設計出了邊界排序生長法。該方法不僅檢測效果好，而且在計算速度上大大領先文中另外三種方法，值得在高速運行的流水線中推廣和應用。此外本文也存在著一定的問題。經(jīng)分析，本文的不足之處主要體現(xiàn)在邊界排序生長法的檢測結果仍有一部分提升空間，以及對于遍歷中心擴散法是否存在某種中心點的選取規(guī)則能使得該算法的檢測效果又快又好，將有待未來進行深入的研究。