一種用于MEMS 動(dòng)態(tài)測(cè)量的最優(yōu)盒計(jì)數(shù)分形維數(shù)算法

羅 元，蔣秋照，張 毅

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

0 引言

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

1 差分盒計(jì)數(shù)法

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

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

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

1.2 差分盒計(jì)數(shù)法

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

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

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

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

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

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

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

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

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

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

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

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

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

3 實(shí)驗(yàn)結(jié)果及分析

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

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

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

?

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

4 結(jié)束語

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

［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)運(yùn)動(dòng)角度測(cè)量的研究［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］趙玲.基于圖像的多孔材料特征分析與物性測(cè)量研究［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ù)估計(jì)的最小盒計(jì)數(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.