基于等效采樣的最大內接矩形提取算法

俞新凱

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

0 引言

用料裁切是生產實踐中經常遇到的問題，例如在皮革產業原材料裁切、建筑用地規劃、板材邊角料循環利用等領域，都期望實現裁切利用率最大化。

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

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

1 問題定義

1.1 圖形定義

本文所述平面內任意不規則圖形屬于拓撲理論中的多連通區域，定義如下[4]：

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

附加約束：

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

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

1.2 問題求解

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

圖1 不規則區域內找出最大內接矩形

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

2 采樣處理

2.1 等效采樣分析

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

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

圖2 最優解OS點組

2.2 劃定圖形內部

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

⑴構建一個用于保存平面像素點狀態的二維數組Matrix（下稱Matrix 狀態矩陣），該二維數組平面剛好覆蓋D區域。

⑵約定Matrix的元素為像素點的狀態，值與狀態的對應關系為：0-未檢測、1-注水點、2-邊界點、3-邊界外；狀態默認初值為0。

⑶檢索一輪Boundary 點組，將其對應到Matrix狀態矩陣的元素狀態值均設為2。

⑷掃描Matrix矩陣，按“邊界→空白→邊界”的順序記錄行進路線上的節點，當找到這種關系時（狀態值變化為2→0+→2），判定中間一連串空白為D的內部點。

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

⑹ 構建一個用于按順序存儲注水點的隊列Queue（先進先出，下稱Q隊列）。

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

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

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

2.3 均勻布點

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

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

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

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

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

Sd為圖形區域D的面積。

圖3是按該方法得到對應圖形的采樣點及相關數據。

圖3 采樣點分布

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

3 矩形計算

大體上按照“擴散→旋轉→觸停檢測→計算面積→比較大小”的步驟，若中間檢測環節發生了“觸停”，則對應邊停止擴散，否則繼續擴散；如果四條邊均發生觸停，則計算所得矩形面積。

“觸停”的定義：當某條邊在擴散過程中一旦發生了該邊的點集（包括兩端點）與圖形邊界Boundary 點組有交集的事實，則該邊停止擴散。

3.1 四邊擴散

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

⑴在像素網格中，以樣本點作為中心的九宮方陣為初始矩形原型，擴散過程中成為動態增長的Rp。

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

⑶定義四條邊的是否可繼續擴散（該邊遠離中心向外移動）的布爾型數組Extensible，初值為true。

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

⑸迭代過程：

①按擴散速度v，更新四角點位的坐標。水平擺置時可以在更新后直接檢測觸停事件；旋轉方向時需要先實施旋轉變換后再檢測“觸停”。

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

③在上一步遍歷每條邊上點時，若發生觸停事件，則設置Extensible 數組中該邊對應的值為false，即停止擴散，Corners 數組中對應角點坐標的x 或y 值不再更新。

④當Extensible 數組中四個方向的值全為false時，迭代結束。

⑹根據此時Corners 數組角點坐標，計算得到基于該樣本點擴散得到的最大面積矩形maxSp，對應于第p個樣本點。

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

圖4 水平方向與旋轉方向上得到的最大矩形

圖4中，矩形內部的小黑點為最優解樣本點，從該點出發找到最大矩形。可見實驗結果符合2.1 小節中關于“等效采樣”OS點組的定義。

3.2 旋轉變換

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

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

經過旋轉變換后，最終得到區域D在任意方向上的最大矩形R，見圖4(b)，可見所得結果優于水平方向的矩形面積。

3.3 擴散提速

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

4 結束語

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

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

圖5 批量計算多區域分離的圖形

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