羅 元，蔣秋照，張 毅

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

0 引言

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

1.2 差分盒計數(shù)法

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

(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ù)是不準確的，導致維數(shù)偏大。為了克服差分盒計數(shù)法的缺點，本文在最小盒計數(shù)的基礎上提出了一種能更好估算圖像分形維數(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中，設圖像大小為M ×N，將x－y圖像平面分成大小為r×r的網(wǎng)格，每個網(wǎng)格對應于三維空間中的一疊r×r×r的正方體盒子，考慮第(i，j)個平面網(wǎng)格，第(i，j)個格子共對應圖像灰度曲面上K=(r+1)2個點，設這些點組成的集合為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'，即

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

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

3 實驗結果及分析

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

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

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

?

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

4 結束語

本文提出了一種基于最小盒計數(shù)法的最優(yōu)盒計數(shù)分形維數(shù)算法。從理論出發(fā)分析了該算法的優(yōu)點:克服了差分盒計數(shù)法在計算盒子數(shù)時存在“空盒子”的缺陷。并通過用MATLAB軟件進行仿真驗證，結果表明該算法是有效的。以便將該算法運用在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］胡曉東，李曉俊.微結構平面旋轉運動角度測量的研究［D］.天津:天津大學，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］林道云.摻用沸石巖礦粉建筑砂漿的力學性能及其抗壓斷面的分形定量表征［D］.廣州:華南理工大學，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］.武漢:武漢理工大學，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］.電氣應用，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.