基于最小外接矩形的集料顆粒形狀特征快速評(píng)價(jià)方法研究

曹源文，楊國(guó)林，張瑩瑩，王若俊，程志豪

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

0 引 言

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

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

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

1 邊界旋轉(zhuǎn)法及改進(jìn)

1.1 凸殼函數(shù)算法

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

1.1.1 格雷厄姆算法

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

1.1.2 集料凸殼處理

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

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

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

1.2 凸殼邊界旋轉(zhuǎn)算法

1.2.1 確定邊界值

根據(jù)凸殼邊界的頂點(diǎn)坐標(biāo)，分別找到x軸和y軸方向上最大值和最小值，將其作為邊界旋轉(zhuǎn)的初始最小外接矩形，記錄下當(dāng)前的外接矩形的面積及邊界最大、最小坐標(biāo)。

1.2.2 邊界旋轉(zhuǎn)

首先求出凸殼邊界上每條線段相對(duì)水平方向的夾角。假設(shè)凸殼邊界上第i個(gè)點(diǎn)的坐標(biāo)為(xi,yi)，第i條線段的水平夾角為θi，則計(jì)算公式為：

(1)

(2)

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

(3)

旋轉(zhuǎn)演示過(guò)程如圖2。

圖2 旋轉(zhuǎn)過(guò)程示意Fig. 2 Rotation process indication

將旋轉(zhuǎn)回原圖像區(qū)域上的坐標(biāo)記錄并保存，然后根據(jù)此坐標(biāo)便可計(jì)算出外接矩形面積。

1.2.3 確定最小外接矩形

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

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

1.3 算法改進(jìn)

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

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

(4)

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

2 實(shí)例分析

2.1 算法求解對(duì)比

利用圖像處理技術(shù)，將集料標(biāo)記序號(hào)，然后采用最小面積外接矩形的邊界旋轉(zhuǎn)算法進(jìn)行求解，為了便于圖像觀察，只把求過(guò)程中小于當(dāng)前外接矩形的矩形圖像進(jìn)行顯示。其運(yùn)行過(guò)程及結(jié)果如圖4。

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

2.2 可行性分析

由圖4可以看出，采用邊界旋轉(zhuǎn)算法和改進(jìn)后的算法結(jié)果相同，說(shuō)明了改進(jìn)算法的可靠性。根據(jù)多次求取原始算法和改進(jìn)算法的運(yùn)行時(shí)間及旋轉(zhuǎn)次數(shù)，得到算法及改進(jìn)前后的平均旋轉(zhuǎn)次數(shù)與耗時(shí)。

圖4 邊界旋轉(zhuǎn)算法運(yùn)算過(guò)程及結(jié)果Fig. 4 Operation process and results of boundary rotation algorithm

采用改進(jìn)后的凸殼邊界旋轉(zhuǎn)算法、運(yùn)行過(guò)程及結(jié)果如圖5。在旋轉(zhuǎn)次數(shù)和耗時(shí)上的提高效率如表1。

圖5 算法改進(jìn)后的運(yùn)算過(guò)程及結(jié)果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可以得出：采用改進(jìn)后旋轉(zhuǎn)算法，平均旋轉(zhuǎn)次數(shù)減少67.5%。隨著求解集料個(gè)數(shù)的增加，算法運(yùn)行耗時(shí)縮短率也隨著提高，圖像中集料個(gè)數(shù)較少時(shí)耗時(shí)縮短率增加并不明顯。而隨著集料個(gè)數(shù)大量的增加，算法耗時(shí)大幅度的降低。

2.3 誤差分析

對(duì)于任意一個(gè)集料顆粒，扁平比等于該集料最大長(zhǎng)度與最大寬度的比值：

(5)

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

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

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

(6)

(7)

圖6 相對(duì)誤差散點(diǎn)圖Fig. 6 Relative error scatter plot

3 結(jié) 論

1)針對(duì)集料顆粒本身形狀復(fù)雜，棱角紋路多等問(wèn)題，提出了應(yīng)用格雷厄姆算法將復(fù)雜圖像進(jìn)行凸殼處理，降低了圖像的來(lái)源誤差。

2)對(duì)凸殼邊界旋轉(zhuǎn)算法進(jìn)行了改進(jìn)，并得到改進(jìn)前后的時(shí)間縮短率曲線。結(jié)果表明：處理的集料顆粒數(shù)越多，耗時(shí)縮短率越明顯。改進(jìn)后的算法可應(yīng)用于批量集料顆粒的形狀特征評(píng)價(jià)。

3)通過(guò)實(shí)例分析，得到了圖像測(cè)量與傳統(tǒng)游標(biāo)卡尺測(cè)量扁平比的最大相對(duì)誤差為4.35%，平均相對(duì)誤差為2.40%，表明了筆者算法具有較好的準(zhǔn)確性。