羅 元，蔣秋照，張 毅

(重慶郵電大學(xué)光纖通信技術(shù)重點實驗室，重慶 400065)

0 引言

微機電系統(tǒng)(micro electromechanical system，MEMS)的動態(tài)特性決定了MEMS器件的基本性能，其測試得到了國內(nèi)外的高度重視，在眾多方法中基于微視覺的技術(shù)因能實現(xiàn)高速高精度測量而備受關(guān)注，分形因具有自相似這一重要特征在充分利用圖像相關(guān)性方面獨具潛力。但分形理論在MEMS測試中目前基本都用于表面形貌的分析，獲得的是MEMS表面形貌特征和分形維數(shù)之間的關(guān)系［1-2］，很少有人將分形理論用于MEMS動態(tài)測量中。研究面內(nèi)位移前后采集的數(shù)字散斑圖像的分形性質(zhì)，通過分形相關(guān)法、分形插值法實現(xiàn)位移的測量;分形圖像邊緣和分形特性曲線之間有互映射關(guān)系，通過提取MEMS位移或旋轉(zhuǎn)時動態(tài)圖像序列的邊緣，對圖像邊緣的分形性質(zhì)與旋轉(zhuǎn)角度［3］的關(guān)系進行研究，實現(xiàn)基于分形的角度定位;再對離面位移與角度的關(guān)系進行研究，完成基于分形理論的離面位移測量。所以有效的分形維數(shù)算法是實現(xiàn)采用分形維數(shù)描述分形特征的一個前提條件。而計盒維數(shù)法由于其計算簡單易懂，得到了廣泛的應(yīng)用。在計盒維數(shù)法中差分盒計算(difference box counting，DBC)法又是目前計算維數(shù)的最常用的方法。本文通過對差分盒計數(shù)法存在“空盒子”的缺陷的分析，從而在最小盒計數(shù)法［4］的基礎(chǔ)上提出了一種對“空盒子”不予計數(shù)的最優(yōu)盒計數(shù)分形維數(shù)算法。并用實驗驗證了該算法的有效性，以便于MEMS動態(tài)測量的后續(xù)研究。

1 差分盒計數(shù)法

1.1 分形維數(shù)的一般形式

分形維數(shù)［5］是分形幾何描述分形特征的基本參數(shù)，計算分形維數(shù)的方法有很多，如點像素覆蓋法［6］、毯子法［7］、計盒維數(shù)法［7］等。計算分形維數(shù)的一般形式［5］為

(1)式中:ε是小立方體一邊的長度;N(ε)是覆蓋被測形體所需小立方體的總數(shù)。計盒維數(shù)是一種被廣泛應(yīng)用的分形維數(shù)，在分形理論應(yīng)用研究中提出的許多維數(shù)的概念都是計盒維數(shù)的變形。

1.2 差分盒計數(shù)法

差分盒計數(shù)法［7-8］是計盒維數(shù)方法中較優(yōu)的方法，也是目前廣泛運用的維數(shù)計算法。它將圖像(見圖1)想象成三維空間中的曲面［9］z=f(x，y)，其中x，y表示平面位置，z軸表示該位置對應(yīng)于圖像像素的灰度值。設(shè)圖像大小為M×K，灰度級為H，xy平面被分割成許多大小為r×r的網(wǎng)格，每個網(wǎng)格對應(yīng)于三維空間中的一疊r×r×r大小的盒子;設(shè)在第(i，j)個網(wǎng)格中，圖像灰度的最大值位于第l個盒子內(nèi)，最小值位于第m個盒子內(nèi)，則

(2)式中，nr是覆蓋第(i，j)網(wǎng)格中的圖像所需的盒子數(shù)，而覆蓋整個圖像的盒子數(shù)Nr為

不同的r，Nr也不同，對得到的序列(lnr，lnNr)，在雙對數(shù)坐標中對數(shù)據(jù)點 (lnr，lnNr)進行直線擬合［6-7］，所得直線斜率的絕對值即分形維數(shù)D。

圖1 DBC法示意圖Fig.1 Schematic diagram of DBC

按照盒維數(shù)估計的定義，不同尺度r下的Nr為覆蓋分形的最少盒子數(shù)，表明的含義［9］是:①完全覆蓋分形的盒子總數(shù)為Nr;②Nr在數(shù)量上最少。③所有的盒子都是非空的。然而，差分盒計數(shù)法在估計圖像的分形維數(shù)時，只能保證Nr個盒子完全覆蓋分形，并不能確保盒子數(shù)Nr是最少的，如果灰度曲面發(fā)生了劇烈變化(見圖2)，第2、第3或第4個盒子都可能是“空盒子”(盒子中沒有包含灰度曲面上的點)。由于“空盒子”出現(xiàn)在2個點的中間位置，這時按差分盒計數(shù)法得到的覆蓋灰度曲面的nr(i，j)盒子中，必然包括“空盒子”。如果圖像灰度曲面變化較劇烈，盒子較小，就很容易出現(xiàn)“空盒子”，因此按差分盒計數(shù)法估計覆蓋圖像灰度曲面的盒子數(shù)是不準確的，導(dǎo)致維數(shù)偏大。為了克服差分盒計數(shù)法的缺點，本文在最小盒計數(shù)的基礎(chǔ)上提出了一種能更好估算圖像分形維數(shù)的算法，最優(yōu)盒計數(shù)法(optimal box counting method，OBC)。

圖2 DBC法中出現(xiàn)“空盒子”示意圖Fig.2 A diagram of DBC which exists empty boxes

2 最優(yōu)盒計數(shù)法

最優(yōu)盒計數(shù)法對平面網(wǎng)格的劃分仍采用差分盒計數(shù)法的劃分方式，只是對那些覆蓋圖像灰度曲面的“空盒子”不予計數(shù)，以便能準確求取覆蓋分形曲面的最少盒子數(shù)。具體實現(xiàn)過程如下。

在圖2中，設(shè)圖像大小為M ×N，將x－y圖像平面分成大小為r×r的網(wǎng)格，每個網(wǎng)格對應(yīng)于三維空間中的一疊r×r×r的正方體盒子，考慮第(i，j)個平面網(wǎng)格，第(i，j)個格子共對應(yīng)圖像灰度曲面上K=(r+1)2個點，設(shè)這些點組成的集合為Zij={f1，f2，f3，…，fK}。對集合 Zij中的每個元素 fi(i=1，2，…，K)，若

(4)式中，fix()是一個函數(shù)，它對一個實數(shù)執(zhí)行舍棄小數(shù)部分取整數(shù)部分的操作，并返回該實數(shù)的整數(shù)部分，則可以確定點fi位于第S個盒子中，從而得到集合S，即

(5)式中，集合S為覆蓋點集Zij的所有盒子的編號集合。對集合S，凡是在集合S中只出現(xiàn)1次的元素，全部保留;凡是在集合S中只出現(xiàn)2次或2次以上的元素，只保留1個。這樣就得到一個新的盒子編號集合S'，即

設(shè)Q為集合S'中的元素個數(shù)，則意味著在第(i，j)個網(wǎng)格中，覆蓋圖像曲面的盒子數(shù)為

對得到的序列(lnr，lnNr)，用最小二乘法計算(lnr，lnNr)的斜率，則斜率的絕對值就是圖像的分形維數(shù)。

3 實驗結(jié)果及分析

本文用Sierpinski三角毯(見圖3)和Sierpinski正方毯(見圖4)圖形進行實驗。首先將圖像進行預(yù)處理，二值化得到M×N的數(shù)據(jù)矩陣，將矩陣劃分為邊長為r(最小為一個像素)的盒子，用DBC和OBC兩種方法計算整個矩陣中所占據(jù)的盒子數(shù)Nr，然后改變盒子的邊長r2，r3，…，計算出相應(yīng)的盒子總數(shù)Nr，并繪制在坐標系中;利用最小二乘法對這些點進行線性擬合，所得的直線斜率的絕對值就是圖像的分形維數(shù)，2種方法的程序流程如圖5所示。

根據(jù)MATLAB圖像處理功能和兩種維數(shù)計算的方法對Sierpinski三角毯和正方毯進行維數(shù)計算，然后編寫程序得到仿真圖，如圖6所示，橫坐標是不同尺度r的負對數(shù)，縱坐標表示對應(yīng)尺度r下的覆蓋分形曲面的總盒子數(shù)的對數(shù)值，用最小二乘法擬合后，直線的斜率就是分形的維數(shù)。

實驗所得的維數(shù)和與理論維數(shù)的相對誤差見表1和表2，表1是DBC法和像素點覆蓋法的維數(shù)計算結(jié)果，表2是OBC法的維數(shù)計算結(jié)果。

?

圖6a和圖6c圖是DBC法的實驗結(jié)果圖，直線的斜率表示分形維數(shù)，因為沒考慮“空盒子”，所以直線擬合的較好，對應(yīng)尺度下的數(shù)據(jù)點和擬合點相差不大。圖6b和圖6d是采用OBC法的仿真結(jié)果圖，它去除了“空盒子”，并且在不同的尺度下出現(xiàn)“空盒子”數(shù)不同，尺度越小出現(xiàn)“空盒子”越有可能且越多，得到的數(shù)據(jù)點就比較沒規(guī)律，有的偏離擬合點會比較遠，所以直線擬合得不是很好，但直線的斜率更能準確地反映圖像的分形維數(shù)。而表1和表2計算的維數(shù)值和相對誤差也證明了OBC法比較優(yōu)越。對分形圖像分維數(shù)的計算具有普適性。因而將其應(yīng)用在基于分形理論的MEMS動態(tài)測量中會使得測量更加準確。

4 結(jié)束語

本文提出了一種基于最小盒計數(shù)法的最優(yōu)盒計數(shù)分形維數(shù)算法。從理論出發(fā)分析了該算法的優(yōu)點:克服了差分盒計數(shù)法在計算盒子數(shù)時存在“空盒子”的缺陷。并通過用MATLAB軟件進行仿真驗證，結(jié)果表明該算法是有效的。以便將該算法運用在MEMS的動態(tài)測量中，實現(xiàn)基于分形的位移測試和角度定位。

［1］LUO Yuan，ZHANG Yi，XU Xiao-dong.Topography of micromirror for metal MEMS optical switch based on fractal theory［C］//Proceedings-Spie the International Society for Optical Engineering.USA:International Society for Optical Engineering ，2007(6724):672-675.

［2］XIONG Xiang，ZHOU Yan，ZHU Jian-xin.Fractal Analysis of the wear in Micro-electro-mechanical Systems(MEMS)［J］.Lubrication Engineering.2008，33(6):675-679.

［3］胡曉東，李曉俊.微結(jié)構(gòu)平面旋轉(zhuǎn)運動角度測量的研究［D］.天津:天津大學(xué)，2007:49-67.HU Xiao-dong，LI Xiao-jun.Study on Angle Measurement about In-plane Rotation Motion in MEMS［D］.Tianjin:Tianjin Universy，2007:49-67.

［4］WEI Gang，TANG Ju.Study of Minimum Box Counting Method for image fractal dimension estimation［C］//Proc of IEEE International conference on Electricity Distribution.［s.l.］:IEEE Press，2008:1-5.

［5］KHOURY Marc，WENGE Rephael.On the Fractal Dimension of Isosurfaces［J］.IEEE Transactions on Visualization and Computer Graphics，2010，16(6):1198-1205.

［6］林道云.摻用沸石巖礦粉建筑砂漿的力學(xué)性能及其抗壓斷面的分形定量表征［D］.廣州:華南理工大學(xué)，2010.LIN Dao-yun.Rock and Mineral Powder Mixed with Zeolite Building Mortar and Compressive Mechanical Properties of Cross-section of the Quantitative Characteriz-ation of the Fractal［D］.Guangzhou:South China University of Technology，2010.

［7］趙玲.基于圖像的多孔材料特征分析與物性測量研究［D］.武漢:武漢理工大學(xué)，2010.ZHAO Ling.Image-based Porous Materials Characterization and Measurement of Physical Properties［D］.Wuhan:Wuhan University of Technology，2010.

［8］IVANOVICI Mihai，RICHARD No?l.Fractal Dimension of Color Fractal Images［J］.IEEE Transactions on image processing.2011，20(1):227-235.

［9］尹賢龍.基于圖像分形維數(shù)估計的最小盒計數(shù)法的研究［J］.電氣應(yīng)用，2006，25(9):93-97 YIN Xian-long.The Study on the Minimum Box Counting Algorithm Based on Fractal Dimension［J］.Electrotechnical Application，2006，25(9):93-97.