王秋嬌 秦春桃 帥玉琳

摘要：

為解決工程應(yīng)用中曲邊圖形的最小外接矩形的計(jì)算問題，介紹了現(xiàn)有的幾種算法，分析了其優(yōu)缺點(diǎn)。提出一種時(shí)間復(fù)雜度為O（n）的離散迭代算法，該算法以曲邊圖形輪廓上的一點(diǎn)為基準(zhǔn)，旋轉(zhuǎn)切線獲得切線與曲邊輪廓的交點(diǎn)，以過該交點(diǎn)的切線為一條邊作外接矩形。每次迭代得到局部最小外接矩形，逐次迭代達(dá)到所要求的精度。使用Qt程序框架驗(yàn)證了該算法，分析了該算法的可行性和可靠性。結(jié)果表明，該算法可以快速高效地獲得給定曲邊圖形的最小外接矩形。

關(guān)鍵詞：曲邊圖形；最小外接矩形；離散迭代算法

中圖分類號(hào)：O241；TP391文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：2095-5383（2019）01-0041-04

An Algorithm for Solving the Minimum Circumscribed Rectangle

of Curved Edges Graphs

WANG Qiujiao1， QIN Chuntao1， SHUAI Yulin2

（1. Basic Department， Southwest Jiaotong University Hope College， Chengdu 61

0400， China；2. School of Mathematics， Southwest Jiaotong University， Chengdu 611756， China）

Abstract：

In order to solve the problem of calculating the minimum circumscribed rectangle of curved edge graphs in engineering application， several existing algorithms were introduced， and their advantages and disadvantages were analyzed. A discrete iterative algorithm with time complexity of O（n） was proposed. The algorithm takes the point on the contour of a curved edge graphs as the benchmark and rotates the tangent line to get the intersection point between the tangent line and the curved edge. The tangent line passing through the intersection point was taken as a side of an external rectangle. A local minimum circumscribed rectangle is obtained in every iteration process and the required accuracy is achieved by successive iterations. The Qt program framework was used to verify the algorithm， and the feasibility and reliability of the algorithm were analyzed. The results show that the algorithm can quickly obtain the minimum circumscribed rectangle of the given curved edge graph.

Keywords：

curved edge graph； minimum circumscribed rectangle； discrete iterative algorithm

一個(gè)平面幾何圖形的最小外接矩形是指將該圖形完全包括在內(nèi)并且面積最小的矩形。最小外接矩形計(jì)算被廣泛應(yīng)用于航空航天、數(shù)字圖像顯示、計(jì)算機(jī)圖形圖像、地理信息系統(tǒng)及材料加工等眾多工程領(lǐng)域[1-5]。

文獻(xiàn)[6-7]提出了一種求解多邊形的最小外接矩形的算法，其首先證明多邊形最小外接矩形必然通過該多邊形的一條邊，然后依次遍歷每條邊所在外接矩形，尋找最小外接矩形。文獻(xiàn)[8]將其成功運(yùn)用于二維碼的檢測(cè)中。但該算法的時(shí)間復(fù)雜度為O（n2），并且不適用于平滑幾何圖形，存在較大的局限性。

文獻(xiàn)[9]提出一種利用重心原理尋找圖像的水平主軸與垂直主軸，在兩主軸構(gòu)成的銳角區(qū)域內(nèi)旋轉(zhuǎn)外接矩形，以5%為誤差極限獲取最小外接矩形。該算法在尋優(yōu)過程中的旋轉(zhuǎn)次數(shù)較少，但每次旋轉(zhuǎn)所需的計(jì)算量較大。

文獻(xiàn)[10]提出一種幾何對(duì)象群的最小外接矩形的算法，首先獲取幾何對(duì)象的邊界點(diǎn)集合的凸殼，然后采用幾何計(jì)算方法直接得到矩形的4個(gè)頂點(diǎn)坐標(biāo)，避免了大量旋轉(zhuǎn)角度計(jì)算和坐標(biāo)變換運(yùn)算，從而降低了算法的計(jì)算量。但該算法在幾何對(duì)象群轉(zhuǎn)凸方面復(fù)雜度較高。

上述研究均是在多邊形領(lǐng)域求解最小外接矩形，尚未有學(xué)者公開有關(guān)曲邊圖形的最小外接矩形的算法。本文首先提取曲邊圖形的曲線邊界，提出一種離散迭代算法求解曲邊圖形最小外接矩形的算法；并仿真計(jì)算，驗(yàn)證了該算法的可靠性。

1相關(guān)基礎(chǔ)

11算法約定

為更詳細(xì)地?cái)⑹龊诵乃惴?，本文給出以下約定：

1）若一段曲線的曲率線在其包圍圖形的內(nèi)部，則其曲率為負(fù)，如圖1的曲線的S段；若曲率線在其包圍圖形的外部，則其曲率為正；正負(fù)曲率交接點(diǎn)的曲率為零。

2）若閉合樣條曲線的任意一段曲率均不為負(fù)，則稱其為凸樣條線，如圓及橢圓；否則稱其為凹樣條線，如梭形圖輪廓線。

3）該算法主體將迭代n（n≥2）次以得到較精確的結(jié)果，每次迭代將產(chǎn)生多個(gè)外接矩形，其中面積最小的外接矩形為局部最小外接矩形Smin（n）。

12B樣條線

樣條線是指近似地表示一組離散點(diǎn)坐標(biāo)之間函數(shù)關(guān)系的一條或一組曲線。B樣條曲線是樣條線的一種，曲線經(jīng)過每個(gè)型值點(diǎn)，但不經(jīng)過控制點(diǎn)，其具有多項(xiàng)式的次數(shù)可獨(dú)立于控制點(diǎn)數(shù)目并且允許局部控制等優(yōu)點(diǎn)。本文采用二次B樣條擬合曲邊圖形的邊界。

2算法設(shè)計(jì)

21算法流程

步驟1：得到一條閉合樣條線后，檢測(cè)其曲率。凸樣條線邊界曲線的凸殼就是其本身。對(duì)于凹樣條線，做切線包圍所有凹陷部分（本文稱這些切線為“包裹切線”），將其轉(zhuǎn)為凸殼，如圖1所示。設(shè)定精確度σ及初始角θ，執(zhí)行步驟2。

步驟2：得到圖像的凸殼后，過凸殼上任意一點(diǎn)做該點(diǎn)的切線l11，以其中一條包裹切線的切點(diǎn)為起始點(diǎn)，如圖2的點(diǎn)A；作凸殼的另外3條切線l12、l13及l(fā)14，使切線l13與切線l11平行、切線l12及l(fā)14與切線l11垂直；求取切線l11、l12、l13及l(fā)14的交點(diǎn)后即獲得了過切點(diǎn)A的外接矩形S11，如圖2中的虛線框矩形。

步驟3：以切點(diǎn)A為基準(zhǔn)，將切線l11沿順時(shí)針或逆時(shí)針旋轉(zhuǎn)角度θ1作凸殼的割線，交樣條線于另一點(diǎn)B，如圖2所示，其中圖2沿逆時(shí)針旋轉(zhuǎn)，并且θ1=30°。以點(diǎn)B為基準(zhǔn)點(diǎn)作凸殼的4條切線l21、l22、l23及l(fā)24，從而求取過點(diǎn)B的外接矩形S12，如圖2中的實(shí)線框矩形。在獲取割線交點(diǎn)時(shí)，作以下判斷：若割線交于包裹切線，并且該切線不是該循環(huán)中已得到的所有外接矩形的任意一條邊，則以該切線作為外接矩形的一條邊。

步驟4：以切點(diǎn)B為基準(zhǔn)，將切線l21旋轉(zhuǎn)角度θ1交凸殼于點(diǎn)C，進(jìn)而獲取過點(diǎn)C的外接矩形S13，如圖2中的點(diǎn)畫線框矩形。

步驟5：重復(fù)步驟2—4，當(dāng)割線的交點(diǎn)越過起始點(diǎn)，即對(duì)凸殼遍歷了一周時(shí)，停止上述步驟。假設(shè)此時(shí)共有n1個(gè)外接矩形S11、S12、S13…、S1（n1），從中選擇該次循環(huán)的最小的外接矩形Smin（1）。

步驟6：減小θ1為θ2，重復(fù)步驟2—5，得到第2次遍歷的n2個(gè)外接矩形S21、S22、S23…、S2（n2）以及局部最小外接矩形Smin（2），若此時(shí)精度在誤差范圍之內(nèi)，即存在

Smin（2）-Smin（1）Smin（1）<σ，

則Smin（2）即為誤差為σ的閉合樣線條的最小外接矩形。若不滿足精度σ，則執(zhí)行步驟7。

步驟7：重復(fù)步驟6，得到第i+1次遍歷的局部最小外接矩形Smin（i+1），其中i≥1。若存在

Smin（i+1）-Smin（i）Smin（i）<σ，

則Smin（i）為誤差為σ的閉合樣線條的最小外接矩形。

22算法流程圖

抽象的算法流程圖如圖3所示，其中圖3a為總流程圖，圖3b為子流程“獲取第i次迭代的最小外接矩形Smin（i）”的流程圖。

3算法實(shí)驗(yàn)與分析

31實(shí)驗(yàn)

在Qt程序框架下實(shí)現(xiàn)了該算法，隨機(jī)取3幅平面圖形，使用該算法求解圖形的最小外接矩形，效果如圖4所示。

更一般地，隨機(jī)繪制曲線后，迭代次數(shù)與精度及初始角的關(guān)系如表1所示。由表可知，該算法一般迭代2～5次即可達(dá)到所需精度范圍內(nèi)的最小外接矩形。

32算法分析

根據(jù)極限思想，當(dāng)旋轉(zhuǎn)角θ取極小值時(shí)，割線與對(duì)應(yīng)弧線近似等價(jià)，即滿足

lim θ→0 lAB=AB。

因此，當(dāng)取旋轉(zhuǎn)角θ取較小值時(shí)，每次循環(huán)得到的局部最小外接矩形接近于實(shí)際

最小外接矩形，之后的數(shù)次迭代則保證了上一次得到的局部最小外接矩形與實(shí)際最小外接矩形之間不會(huì)有太大的偏差。而輸入?yún)?shù)“精度”既保證了結(jié)果的精度在工程所需范圍，又保證了算法主體的迭代次數(shù)在可控范圍內(nèi)。以旋轉(zhuǎn)角θ=5°為例，最壞情況是循環(huán)360°/5°=72次。

考慮到曲邊圖形的不規(guī)則性以及凹樣條線的存在，循環(huán)體一般循環(huán)20次左右即完成一次迭代，故該算法執(zhí)行速度較快。

本算法既適用于曲邊圖形，也適用于不規(guī)則多邊形，即把多邊形所有的邊當(dāng)作包裹切線來處理，即適用于除單個(gè)點(diǎn)和單條直線外的所有平面圖形。

4結(jié)論

提出一種算法復(fù)雜度為O（n）的曲邊圖形的最小外接矩形算法，通過逐次迭代達(dá)到工程所需精度，該算法同時(shí)適用于所有具有包圍面積的平面圖形。使用Qt程序框架實(shí)現(xiàn)了該算法，經(jīng)實(shí)驗(yàn)驗(yàn)證，該算法可快速準(zhǔn)確地求解工程所需參數(shù)的最小外接矩形。參考文獻(xiàn)：

[1]吳舟舟， 李樹廣. 基于分級(jí)邊緣間距的實(shí)時(shí)車牌檢測(cè)[J]. 中國圖象圖形學(xué)報(bào)， 2007，12（2）：315321.

[2]劉志超. 基于像素累加值比較和最小外接矩形的車牌識(shí)別研究[D]. 太原：太原理工大學(xué)， 2015.

[3]BAO Q， LI Z， TONG X， et al. The transform of the national geographic grids for China based on the axial minimum enclosing rectangle[M]// Knowledge Discovery and Data Mining. Springer Berlin Heidelberg， 2012：8591.

[4]KWAK E， HABIB A. Automatic representation and reconstruction of DBM from LiDAR data using Recursive Minimum Bounding Rectangle[J]. ISPRS Journal of Photogrammetry and Remote Sensing， 2014， 93：171191.

[5]KWAK E， ALDURGHAM M， HABIB A. Automatic 3d building model generation from LIDAR and image data using sequential minimum bounding rectangle[J]. ISPRSInternational Archives of the Photogrammetry， Remote Sensing and Spatial Information Sciences， 2012，XXXIXB3：285290.

[6]程鵬飛， 閆浩文， 韓振輝. 一個(gè)求解多邊形最小面積外接矩形的算法[J]. 圖學(xué)學(xué)報(bào)， 2008，29（1）：122126.

[7]YANG W. On automatic computation of minimumarea encasing rectangles of arbitrary polygons[C]// International Congress on Image & Signal Processing， 2009.

[8]張勇， 楊傲雷. 基于凸包及最小面積外接矩形的QR碼定位[J]. 電子測(cè)量技術(shù)， 2017，40（4）：152156.

[9]張法全， 王國富， 曾慶寧， 等. 利用重心原理的圖像目標(biāo)最小外接矩形快速算法[J]. 紅外與激光工程， 2013，42（5）：13821387.

[10]郭慶勝， 馮代鵬， 劉遠(yuǎn)剛， 等. 一種解算空間幾何對(duì)象的最小外接矩形算法[J]. 武漢大學(xué)學(xué)報(bào)（信息科學(xué)版）， 2014，39（2）：177180.