基于最小外接矩形的集料顆粒形狀特征快速評價方法研究

曹源文，楊國林，張瑩瑩，王若俊，程志豪

(1. 重慶交通大學 機電與車輛工程學院，重慶 400074； 2. 云南省交通規劃設計研究院，云南 昆明 650041；3. 云南玉楚高速公路投資開發有限公司，云南 昆明 650041)

0 引 言

集料顆粒是瀝青混合料的主要組成部分，其占比約為95%。工程技術人員對路面早期破壞因素作了相關研究，發現集料級配及形狀特征對瀝青路面的使用性能及耐久性有較大的影響。當混合料中針片狀顆粒數量較多時，瀝青路面的強度和抗車轍性能下降，抗水損害能力降低。同時，針片狀顆粒越多，碾壓作業過程中壓碎、壓潰現象越明顯，對瀝青路面的壓實度以及離析情況均有一定的影響[1]。

針片狀顆粒主要產生于機械設備進行破碎的過程中，其含量受破碎機械設備的型式、性能以及加工母巖的構造特征等因素影響，因此需要對針片狀顆粒含量進行檢測，才能找出破碎機械性能參數及母巖的適配程度。然而傳統人工檢測方法效率很低，目前多采用圖像處理的方法來提高工作效率。圖像處理中集料的平面輪廓近似模型有等效圓、等效橢圓和等效矩形[2]，其中以等效矩形模型的使用較為普遍。

由于集料輪廓的形狀較為復雜，且多為凸邊、凹邊。為了獲得更好的等效矩形，目前一般采用面積最小外接矩形和周長最小外接矩形兩種方法。而最小外接矩形的求解算法以旋轉算法[3-6]、掃描算法[7]、頂點鏈碼算法[8]為主。其中旋轉算法目前有等間隔旋轉算法、形心旋轉算法、主軸旋轉算法和凸殼旋轉法。程鵬飛等在求解多邊形最小面積外接矩形[9]時，利用圖形學知識已經證明多邊形的最小外接矩形必定過該多邊形凸邊的一條邊界。因此筆者采用凸殼邊界旋轉算法，對集料顆粒進行形狀特征研究，并對這種算法進行改進，縮短算法運行時間。最后通過實例分析，可以實現快速計算出集料顆粒的扁平率。

1 邊界旋轉法及改進

1.1 凸殼函數算法

凸殼算法在模式識別、圖像處理、圖形學和人工智能方面有著廣泛的應用，很多問題都可以歸納為凸殼問題求解。計算平面點集凸殼的算法通常有卷包裹法、格雷厄姆法、分治算法、增量算法和近似算法等。其中，格雷厄姆算法是解平面點集凸殼問題中的時間復雜性最小算法[10]。

1.1.1 格雷厄姆算法

格雷厄姆算法基于凸多邊形的各頂點必在該多邊形任意一條邊的同一側的原理。該方法的步驟：①找到S點集中縱坐標最小的點P1，把P1同點集中其它各點用線段連接，并計算這些線段與水平線的夾角，然后按夾角大小及到點的距離進行分類，得到一組序列，然后依次連接這些點，便得到一個多邊形；②從P1開始按順序選取相鄰兩個點組成一條線段，再對其余的點進行判斷是否都在這條線段的同一側，若滿足，則繼續選取下一條線段進行上述判斷，若不滿足其余點在同一側，則將當前線段的末端點刪去，后面的頂點依次補上，再進行循環判斷，最終走完所有的頂點，得到最后的凸殼邊界頂點集。

1.1.2 集料凸殼處理

在工程實際中，集料本身的形狀復雜不規則，加上集料表面存在很多白色斑點、棱角紋路等，導致拍攝的圖片也會存在一些缺陷。因此采用格雷厄姆算法將復雜圖像近似填充為凸多邊形，有利于集料顆粒形狀特征的研究。對集料進行凸殼拉伸處理，處理效果如圖1。

從圖1可以看出，格雷厄姆算法得到的凸殼是包含集料復雜圖像點集的最小凸集。其中凹邊特征被拉伸為凸邊，原有的凸邊則被保存下來，使得不規則的復雜形狀輪廓得到較好的轉換。

圖1 集料的凸殼處理Fig. 1 Convex hull treatment of aggregate

1.2 凸殼邊界旋轉算法

1.2.1 確定邊界值

根據凸殼邊界的頂點坐標，分別找到x軸和y軸方向上最大值和最小值，將其作為邊界旋轉的初始最小外接矩形，記錄下當前的外接矩形的面積及邊界最大、最小坐標。

1.2.2 邊界旋轉

首先求出凸殼邊界上每條線段相對水平方向的夾角。假設凸殼邊界上第i個點的坐標為(xi,yi)，第i條線段的水平夾角為θi，則計算公式為：

(1)

(2)

確定旋轉后的凸殼邊界在x軸和y軸方向上最大值和最小值，將其作為旋轉后的最小外接矩形，計算并記錄下當前的外接矩形的面積和旋轉的角度及邊界最大、最小坐標。

(3)

旋轉演示過程如圖2。

圖2 旋轉過程示意Fig. 2 Rotation process indication

將旋轉回原圖像區域上的坐標記錄并保存，然后根據此坐標便可計算出外接矩形面積。

1.2.3 確定最小外接矩形

重復進行邊界旋轉，將旋轉次數記為m，凸殼邊界頂點個數記為n。如果第m+1次旋轉獲得的最小外接矩形比第m次要小，則保留第m+1次的最小外接矩形，且將其顯示到圖像中，否則將繼續進行邊界旋轉，直到所有的邊界旋轉完成。至此需要的最小外接矩形已經確定，選擇其中面積最小的一個外接矩形作為集料的近似最小外接矩形，如圖3。

圖3 最小外接矩形Fig. 3 Minimum outer rectangle

1.3 算法改進

由于集料圖形輪廓凸邊較多且復雜，可能存在相同水平夾角，導致邊界旋轉次數增加。因此需將這些夾角統一化到第一象限內，可以減少旋轉次數，提高算法運行效率。假設統一化后的水平夾角為θ，則統一化公式為：

θ=mod[θi/(kπ+π/2)] (i≤n且k∈Z)

(4)

然后取出θ中相同的角度，將其他重復的水平夾角刪除，然后把最新的θ帶入邊界旋轉算法進行求解。

2 實例分析

2.1 算法求解對比

利用圖像處理技術，將集料標記序號，然后采用最小面積外接矩形的邊界旋轉算法進行求解，為了便于圖像觀察，只把求過程中小于當前外接矩形的矩形圖像進行顯示。其運行過程及結果如圖4。

從試驗圖像中可以得出，兩種算法結果一致，且改進后的凸殼邊界旋轉算法在求解集料輪廓最小面積外接矩形具有更好的時效性。

2.2 可行性分析

由圖4可以看出，采用邊界旋轉算法和改進后的算法結果相同，說明了改進算法的可靠性。根據多次求取原始算法和改進算法的運行時間及旋轉次數，得到算法及改進前后的平均旋轉次數與耗時。

圖4 邊界旋轉算法運算過程及結果Fig. 4 Operation process and results of boundary rotation algorithm

采用改進后的凸殼邊界旋轉算法、運行過程及結果如圖5。在旋轉次數和耗時上的提高效率如表1。

圖5 算法改進后的運算過程及結果Fig. 5 Operation process and results of the improved algorithm

//s/s/%/%11110.470350.39768.47%15.60%21820.490570.39068.6820.4843410.5971200.45364.8124.1198050.9272570.59568.0735.80

由表1可以得出：采用改進后旋轉算法，平均旋轉次數減少67.5%。隨著求解集料個數的增加，算法運行耗時縮短率也隨著提高，圖像中集料個數較少時耗時縮短率增加并不明顯。而隨著集料個數大量的增加，算法耗時大幅度的降低。

2.3 誤差分析

對于任意一個集料顆粒，扁平比等于該集料最大長度與最大寬度的比值：

(5)

式中：lmax、bmax分別為最小外接矩形的較長邊和較短邊。

扁平比μ(μ≥1)的值越大，則該集料顆粒形狀就越趨向于片狀。而當扁平比μ的值越接近1時，集料形狀越接近于方形。經圖像處理和人工測量得到集料多次測量的尺寸參數平均值如表2。

表2 圖像處理和人工測量得到的集料顆粒尺寸參數Table 2 Size parameters of aggregate particle obtained byimage processing and artificial measurement

(6)

(7)

圖6 相對誤差散點圖Fig. 6 Relative error scatter plot

3 結 論

1)針對集料顆粒本身形狀復雜，棱角紋路多等問題，提出了應用格雷厄姆算法將復雜圖像進行凸殼處理，降低了圖像的來源誤差。

2)對凸殼邊界旋轉算法進行了改進，并得到改進前后的時間縮短率曲線。結果表明：處理的集料顆粒數越多，耗時縮短率越明顯。改進后的算法可應用于批量集料顆粒的形狀特征評價。

3)通過實例分析，得到了圖像測量與傳統游標卡尺測量扁平比的最大相對誤差為4.35%，平均相對誤差為2.40%，表明了筆者算法具有較好的準確性。