俞新凱

(廣州南方學(xué)院電氣與計算機(jī)工程學(xué)院，廣東 廣州 510970)

0 引言

用料裁切是生產(chǎn)實踐中經(jīng)常遇到的問題，例如在皮革產(chǎn)業(yè)原材料裁切、建筑用地規(guī)劃、板材邊角料循環(huán)利用等領(lǐng)域，都期望實現(xiàn)裁切利用率最大化。

計算機(jī)圖像處理技術(shù)在眾多方向上的發(fā)展已經(jīng)比較成熟。目標(biāo)區(qū)域的輪廓線提取、二值化與卷積處理、任意曲線路徑擬合等相關(guān)技術(shù)為本課題研究提供了基礎(chǔ)條件。目前在同類問題的研究方向上，謝新華等人提出了基于遍歷目標(biāo)物體的中心擴(kuò)散法[1]，袁哲等人提出了基于改進(jìn)遺傳算法[2]、鄒哲康等人提出基于機(jī)器視覺的邊界排序生長法[3]等研究成果，在提取不規(guī)則圖形的最大內(nèi)接矩形的技術(shù)實現(xiàn)上，都已獲得不錯的效果，而關(guān)鍵差異主要還是在算法處理的時間效率上。

本文提出一種基于等效采樣與均勻擴(kuò)散、旋轉(zhuǎn)變換等方法相結(jié)合的平面任意圖形最大內(nèi)接矩形算法，力求壓縮檢測點位的采樣空間，又確保不遺失真實、有效的目標(biāo)結(jié)果。

1 問題定義

1.1 圖形定義

本文所述平面內(nèi)任意不規(guī)則圖形屬于拓?fù)淅碚撝械亩噙B通區(qū)域，定義如下[4]：

平面內(nèi)，區(qū)域D 的邊界中是由一條或幾條曲線所圍成，單條曲線必須為閉環(huán)，即邊界不能有“缺口”，所圍區(qū)域內(nèi)可以存在“空洞”，如圖1所示。

附加約束：

⑴邊界線條由單像素點組成，邊界內(nèi)外沒有多余的附著點（毛刺），相關(guān)技術(shù)實現(xiàn)可以參考圖像邊界分析或路徑擬合等方面的文獻(xiàn)[5]；

⑵若在初始圖像輸入時，存在兩個或以上分離的區(qū)域，則按不同的對象分別計算各自最大內(nèi)接矩形。

1.2 問題求解

在區(qū)域D（下簡稱D）內(nèi)，找出面積最大的矩形R（以下簡稱R），R 不能超出D 的邊界，兩者邊界可以重合。如圖1所示，陰影部分為R。

圖1 不規(guī)則區(qū)域內(nèi)找出最大內(nèi)接矩形

D 的邊界信息為已知條件，即邊界點的像素位置坐標(biāo)是已知的，本文稱其為邊界點組（下稱Boundary點組）。本文所述面積以像素點為單位，對象區(qū)域所覆蓋的像素點個數(shù)為其面積大小。

2 采樣處理

2.1 等效采樣分析

這里提出一種等效采樣的思路。由于本算法在處理矩形擴(kuò)散時，采用的策略是四條邊等速增長，因此在最大矩形R 內(nèi)部，是存在一部分等效樣本點能擴(kuò)散成R 的，本文將這些點歸為OS 點組，即最優(yōu)解（Optimal Solution）點組。

在圖2 中，OS 點組分兩種情形，一是對于R 的角位接觸D 的內(nèi)凹處，此時OS 點聚集于角平分線上且不能離角位太遠(yuǎn)；二是對于R的邊位接觸D的內(nèi)凸處，此時OS 點聚集于該處附近。因此，只要能確保采樣空間能覆蓋到OS 點組中的任意一個，即可最終求得R，從而壓縮樣本空間的大小。

圖2 最優(yōu)解OS點組

2.2 劃定圖形內(nèi)部

劃定區(qū)域D的內(nèi)部空間，并求出其整體面積，是本算法設(shè)計要先行解決的問題。輸入圖形的邊界要求是閉合的，且內(nèi)部必須存在空隙。本文以此為前提條件，采用“注水”法求得D的面積。

⑴構(gòu)建一個用于保存平面像素點狀態(tài)的二維數(shù)組Matrix（下稱Matrix 狀態(tài)矩陣），該二維數(shù)組平面剛好覆蓋D區(qū)域。

⑵約定Matrix的元素為像素點的狀態(tài)，值與狀態(tài)的對應(yīng)關(guān)系為：0-未檢測、1-注水點、2-邊界點、3-邊界外；狀態(tài)默認(rèn)初值為0。

⑶檢索一輪Boundary 點組，將其對應(yīng)到Matrix狀態(tài)矩陣的元素狀態(tài)值均設(shè)為2。

⑷掃描Matrix矩陣，按“邊界→空白→邊界”的順序記錄行進(jìn)路線上的節(jié)點，當(dāng)找到這種關(guān)系時（狀態(tài)值變化為2→0+→2），判定中間一連串空白為D的內(nèi)部點。

⑸以D 中任意一個內(nèi)部點作為中心的“九宮格”邊界有8個點。令九宮中心為P0，其余8個點從左上角開始，按順時針方向順序編號，分別為：P1、P2、P3、P4、P5、P6、P7、P8。用傳遞關(guān)系定義所有九宮格，則D 的全體內(nèi)部點可以構(gòu)成連通圖。

⑹ 構(gòu)建一個用于按順序存儲注水點的隊列Queue（先進(jìn)先出，下稱Q隊列）。

⑺以第一個P0作為根節(jié)點，按“廣度優(yōu)先”遍歷連通圖的所有節(jié)點[6]，每輪迭代都以當(dāng)前節(jié)點為“九宮中心”，順序訪問其周圍的8 個點（從P1到P8），并記錄其狀態(tài)值到Matrix 矩陣中。邊界內(nèi)的點記為注水點⑴；邊界外的點記為邊界外⑶。每標(biāo)記一個注水點都將其加入隊列Q中。

⑻當(dāng)前輪檢測完畢后，便消去了九宮內(nèi)的未檢測(0)點。下輪迭代則從Q 中出隊一個注水點，將P0的游標(biāo)（九宮中心）移交給它，重復(fù)迭代過程。

⑼直至Q隊列為空時，迭代結(jié)束。此時遍歷一輪Matrix狀態(tài)矩陣，累計邊界點和注水點的合計數(shù)，便得到區(qū)域D的面積，記為Sd。

2.3 均勻布點

由于R 是待求解，無法事前就得知該從哪兒出發(fā)才能找到R。這里采用均勻分布的方法，以避開連續(xù)走點遍歷，達(dá)到壓縮樣本空間效果[7]。

對于以怎樣的稀疏度來采樣，遵從以下原則：

⑴面積較大的區(qū)域D，布點傾向于稀疏；反之則傾向于稠密；

⑵避免在邊界鄰近處采樣，因為內(nèi)接矩形對邊界鄰近點的覆蓋率低。

對于⑴，使用布點間隔span 來確定稀疏度，span的計算公式如下：

Sd為圖形區(qū)域D的面積。

圖3是按該方法得到對應(yīng)圖形的采樣點及相關(guān)數(shù)據(jù)。

圖3 采樣點分布

對比邊界點數(shù)、內(nèi)部點數(shù)和采樣點數(shù)，可見檢測點的樣本空間已大為減小。這里將采樣點集合稱為Sample點組。

3 矩形計算

大體上按照“擴(kuò)散→旋轉(zhuǎn)→觸停檢測→計算面積→比較大小”的步驟，若中間檢測環(huán)節(jié)發(fā)生了“觸停”，則對應(yīng)邊停止擴(kuò)散，否則繼續(xù)擴(kuò)散；如果四條邊均發(fā)生觸停，則計算所得矩形面積。

“觸?！钡亩x：當(dāng)某條邊在擴(kuò)散過程中一旦發(fā)生了該邊的點集（包括兩端點）與圖形邊界Boundary 點組有交集的事實，則該邊停止擴(kuò)散。

3.1 四邊擴(kuò)散

遍歷Sample 點組中的全部樣本點，分別從每個樣本點P出發(fā)，通過四邊逐步擴(kuò)散的求得對應(yīng)的矩形Rp，再通過比較得到最大R。算法步驟大致如下（以水平擺置為例，在旋轉(zhuǎn)變換后，矩形內(nèi)部各點保持位置對應(yīng)關(guān)系）。

⑴在像素網(wǎng)格中，以樣本點作為中心的九宮方陣為初始矩形原型，擴(kuò)散過程中成為動態(tài)增長的Rp。

⑵定義四角點位數(shù)組Corners，初值為九宮方陣的四個角位。

⑶定義四條邊的是否可繼續(xù)擴(kuò)散（該邊遠(yuǎn)離中心向外移動）的布爾型數(shù)組Extensible，初值為true。

⑷定義擴(kuò)散速度v，為每次擴(kuò)散所增加的步長，即像素個數(shù)，先約定為1。

⑸迭代過程：

①按擴(kuò)散速度v，更新四角點位的坐標(biāo)。水平擺置時可以在更新后直接檢測觸停事件；旋轉(zhuǎn)方向時需要先實施旋轉(zhuǎn)變換后再檢測“觸?！?。

②Corners 數(shù)組里角點前后相連可得到四條邊，通過斜率關(guān)系依次遍歷每條邊上的所有點。以某條邊例，設(shè)端點p1為(x1,y1)，端點p2為(xz,yz)；Δx=xz-x1，Δy=yz-y1；k=Δy/Δx，為斜率（浮點型），當(dāng)Δx=0，時k=999999.0；設(shè)Ux 為遞增或遞減的單位量，按Δx＜0、=0、＞0 分別取-1、0、1，同理設(shè)Uy；點(xi,yi)為邊線上從p1到p2遍歷過程的點，i 為循環(huán)增量，從1 到|Δx|。則(xi,yi)可以通過以下公式獲得：

③在上一步遍歷每條邊上點時，若發(fā)生觸停事件，則設(shè)置Extensible 數(shù)組中該邊對應(yīng)的值為false，即停止擴(kuò)散，Corners 數(shù)組中對應(yīng)角點坐標(biāo)的x 或y 值不再更新。

④當(dāng)Extensible 數(shù)組中四個方向的值全為false時，迭代結(jié)束。

⑹根據(jù)此時Corners 數(shù)組角點坐標(biāo)，計算得到基于該樣本點擴(kuò)散得到的最大面積矩形maxSp，對應(yīng)于第p個樣本點。

比較所有maxSp，從中找出最大者，即為區(qū)域D 的最大矩形R，目前為水平方向上的，見圖4(a)。

圖4 水平方向與旋轉(zhuǎn)方向上得到的最大矩形

圖4中，矩形內(nèi)部的小黑點為最優(yōu)解樣本點，從該點出發(fā)找到最大矩形?？梢妼嶒灲Y(jié)果符合2.1 小節(jié)中關(guān)于“等效采樣”O(jiān)S點組的定義。

3.2 旋轉(zhuǎn)變換

前面只考察了水平擺置方向上的最大R，為了考察任何方向上擺置的矩形，需要實施旋轉(zhuǎn)變換，逐個角度旋轉(zhuǎn)，分別考察不同方向上的最大值。例如在考察逆時針旋轉(zhuǎn)θ 角度方向時，每次基于水平方向上擴(kuò)散得到的Corners角點數(shù)組，都要先經(jīng)旋轉(zhuǎn)變換后再檢測觸停事件。對于角點原坐標(biāo)(x,y)，可以按以下公式進(jìn)行旋轉(zhuǎn)[8]，變換到像坐標(biāo)(x’,y’)。

這里角點坐標(biāo)是相對于樣本點的，即以樣本點為原點的位移量，在進(jìn)行觸停檢測前，需要將(x’,y’)平移回圖形平面的實際坐標(biāo)去，才能與Boundary 點組的坐標(biāo)統(tǒng)一。

經(jīng)過旋轉(zhuǎn)變換后，最終得到區(qū)域D在任意方向上的最大矩形R，見圖4(b)，可見所得結(jié)果優(yōu)于水平方向的矩形面積。

3.3 擴(kuò)散提速

擴(kuò)散速度v 可以引入動態(tài)設(shè)定機(jī)制，檔位為1-5。例如當(dāng)設(shè)定v=4 時，即每次增長步長為4，則可能會出現(xiàn)某條邊跨越或觸碰了Boundary，此時需要進(jìn)行回滾處理。擴(kuò)散提速在理想的情形下效果比較明顯，例如在初始階段，四周較為空蕩時。此外，具體到某條邊而言，“提速失敗”只會發(fā)生一次，而且回滾再計算的代價也很小。

4 結(jié)束語

本文通過分析研究一種基于等效采樣原理的最大內(nèi)接矩形提取算法，并實現(xiàn)了算法設(shè)計的程序代碼全過程，測試了各種形狀復(fù)雜的平面圖形，對于區(qū)域大小在600×600像素以內(nèi)的普通圖形，程序運行耗時基本上可以控制在2s 以內(nèi)。與暴力破解法找到的結(jié)果相對比，基本上可以保持在99%以上的準(zhǔn)確率。

圖5 展示了針對地圖形狀的圖形輸入運行效果。對于輸入對象為多區(qū)域分離的圖形，程序還實現(xiàn)了批量計算處理。

圖5 批量計算多區(qū)域分離的圖形

該算法經(jīng)應(yīng)用化設(shè)計后可以進(jìn)一步推廣到相應(yīng)的需求場景中。不足之處在于，通過均勻分布的方法來采樣，只是在概率上盡可能覆蓋最優(yōu)解，極端差情況下的計算結(jié)果可能會出現(xiàn)比較大的誤差。此外，在算法改良方面，還可以運用放縮變換加以優(yōu)化，這還需要在后續(xù)的相關(guān)課題研究中，做進(jìn)一步的分析與設(shè)計完善。