圖像分形維數(shù)的計(jì)盒方法改進(jìn)

呂澤昆

（華北電力大學(xué)（北京）控制與計(jì)算機(jī)工程學(xué)院 北京市 102206）

1 概述

簡(jiǎn)單的對(duì)象可以用理想的形狀來(lái)描述，如立方體、錐和圓柱體。但是，大多數(shù)的自然生物是復(fù)雜和不穩(wěn)定的，不能用簡(jiǎn)單的整數(shù)維度來(lái)描述，于是誕生了分形的概念。分形(fractal)學(xué)是Mandelbrot于1975 年創(chuàng)立的，分形一詞的原意是不規(guī)則的、支離破碎的[1]。Mandelbrot 提出了自然界的分形幾何，并提出了對(duì)復(fù)雜而不規(guī)則的形狀以及這些形狀中部分與整體之間自相似性描述，所以分形幾何學(xué)是一門以非規(guī)則幾何形態(tài)為研究對(duì)象的幾何學(xué)。分形學(xué)的提出為自然界中存在的幾個(gè)明顯復(fù)雜的結(jié)構(gòu)提供了數(shù)學(xué)和描述模型。

分形是指一類混亂但其局部與整體卻具有相似結(jié)構(gòu)的圖案。換言之，分形對(duì)象具有“標(biāo)度不變性”規(guī)律。對(duì)部分與整體自相似性的度量涉及到分形維數(shù)的概念，這是分形學(xué)一個(gè)重要的概念，它反映了復(fù)雜形體占有空間的有效性，它是復(fù)雜形體不規(guī)則性的量度。日常中不規(guī)則形狀：云、山和海岸線等無(wú)法由傳統(tǒng)幾何(歐幾里得幾何)簡(jiǎn)單定義的。它們往往隨放大率的變化而具有顯著的不變性。這種自相似性的本質(zhì)在分形理論中能得到很好的衡量。

在日常的研究過(guò)程中，研究對(duì)象的信息可以通過(guò)多種方法加以記錄，從而得到對(duì)研究對(duì)象的描述。隨著近年來(lái)圖像領(lǐng)域的發(fā)展，人們的手機(jī)像素越來(lái)越高，圖像的清晰度越來(lái)越高，圖像已經(jīng)成為描述研究對(duì)象的一個(gè)優(yōu)秀的載體。隨著信息處理技術(shù)和計(jì)算機(jī)技術(shù)的發(fā)展，無(wú)數(shù)的圖形圖像對(duì)象可以轉(zhuǎn)化為數(shù)字圖像。數(shù)字圖像的本質(zhì)是存儲(chǔ)在計(jì)算機(jī)中的矩陣。對(duì)圖像的處理，歸根到底是對(duì)矩陣的處理。因此我們可以將要研究的對(duì)象拍攝為圖像，對(duì)圖像進(jìn)行操作，方便研究。其中利用分形理論對(duì)圖像進(jìn)行研究已經(jīng)成為一部分重要的內(nèi)容。

分形理論指出大多數(shù)自然物體表面在空間上都是分形的，這為分形模型在圖像分析領(lǐng)域的應(yīng)用提供了理論基礎(chǔ)。自分形維數(shù)提出至今，它在各個(gè)領(lǐng)域都起到了重要的作用。在地理方面，文獻(xiàn)[2]利用分形維數(shù)對(duì)山體遙感圖像進(jìn)行計(jì)算，通過(guò)計(jì)算結(jié)果對(duì)山體植被的覆蓋情況進(jìn)行評(píng)估，并取得良好結(jié)果。在植物學(xué)的圖像方面，文獻(xiàn)[3]通過(guò)計(jì)算植物枝干橫截面的分形維數(shù)，判斷枝干內(nèi)部是否腐朽。在地質(zhì)方面，文獻(xiàn)[4]利用電鏡掃描花崗巖，得到圖像并計(jì)算其分形維數(shù)，揭示出花崗巖在斷裂斷口處復(fù)雜的非線性特性，并做出定量描述。在生物種群研究方面，文獻(xiàn)[5]利用分形維數(shù)計(jì)算興安落葉松種群的格局分布，并取得良好結(jié)果。在圖圖像學(xué)領(lǐng)域，已有學(xué)者利用分形的概念提出了圖像分割的理論[6]。在圖像數(shù)據(jù)壓縮與編碼方面，分形理論也展現(xiàn)出優(yōu)秀的能力[7]。

2 分形維數(shù)計(jì)算方法

目前已經(jīng)有許多關(guān)于分形維數(shù)的計(jì)算方法，主要包括Hasdorff方法、尺碼法、計(jì)盒法等。Hauslorff維數(shù)是分形幾何理論的基礎(chǔ)，但其只適合分形幾何的理論推導(dǎo)。對(duì)于實(shí)際應(yīng)用中的計(jì)算無(wú)能為力。

2.1 尺碼法

圖1：改進(jìn)后的算法原理示例圖

圖2：謝爾賓斯基地毯圖

利用計(jì)盒法進(jìn)行計(jì)算的過(guò)程如下：

（1）選用某個(gè)固定尺碼ri沿著曲線的輪廓（如：海岸線）進(jìn)行測(cè)量，并保證尺碼的兩個(gè)端點(diǎn)始終落在測(cè)量曲線的輪廓上。如此測(cè)量完全部的曲線，記錄總測(cè)量次數(shù)ni，完成一遍的測(cè)量之后，利用測(cè)量時(shí)的尺碼與測(cè)量結(jié)果數(shù)目進(jìn)行乘積計(jì)算出曲線的長(zhǎng)度di，即di=ri×ni。

（2）變化測(cè)量尺碼ri的大小，重復(fù)步驟（1），得到多組ni，從而計(jì)算出多組di。

（3）對(duì)于得到的每組數(shù)據(jù)對(duì)[r1，d1]，[r2，d2]，[r3，d3]…，在雙對(duì)數(shù)坐標(biāo)中采用最小二乘法原理對(duì)數(shù)據(jù)進(jìn)行回歸分析，計(jì)算的直線的斜率即為分形維數(shù)的值。

通過(guò)對(duì)尺碼法的流程分析，可以發(fā)現(xiàn)尺碼法存在以下的弊端。第一，尺碼法適合在生活中對(duì)分形維數(shù)進(jìn)行粗略的計(jì)算，對(duì)于特殊的地形或者天空中的云等難以人為接近的對(duì)象束手無(wú)策。第二，由于每次選定測(cè)量尺碼時(shí)候，會(huì)受到人的主觀因素的影響，因此，利用該方法進(jìn)行定量的測(cè)量會(huì)產(chǎn)生較大的誤差。故，尺碼法的應(yīng)用在許多場(chǎng)景中會(huì)受到限制。

2.2 計(jì)盒法

為了解決尺碼法的弊端，研究人員提出了計(jì)盒法。近年來(lái)，計(jì)盒法因?yàn)橛?jì)算方法相對(duì)簡(jiǎn)單，測(cè)量誤差小且是對(duì)研究對(duì)象在圖像角度進(jìn)行研究。因此，計(jì)盒法是目前計(jì)算分形維數(shù)時(shí)應(yīng)用最為廣泛的方法之一。計(jì)盒法計(jì)算的分形維數(shù)也被稱為計(jì)盒維數(shù)。

目前在分形理論的研究中提出的許多維數(shù)的概念都是基于計(jì)盒法。利用計(jì)盒法進(jìn)行計(jì)算的過(guò)程如下：

（1）將彩色圖像轉(zhuǎn)化為灰度圖像并選擇合適的閾值將圖像進(jìn)行二值化操作，得到二值化之后的圖像（圖像矩陣中僅包含0 和1）。

（2）將上述預(yù)處理后的圖像矩陣分為盒子邊長(zhǎng)為 r 的若干個(gè)盒子( r=2i， i=1，2，3 … 2i＜d，其中d 為圖像長(zhǎng)度和寬度的最小值)。

（3）計(jì)算不同r 時(shí)圖像矩陣中包含1(分形圖像塊)的盒子數(shù)目，記作 N(r)，從而得到多組數(shù)據(jù)對(duì)(r, N(r))。

（4）對(duì)上述數(shù)據(jù)對(duì)在雙對(duì)數(shù)坐標(biāo)中進(jìn)行曲線擬合, 其中l(wèi)gr～I(xiàn)gN(r)曲線的直線部分的斜率即為所求的計(jì)盒維數(shù)D。

3 計(jì)盒方法的改進(jìn)

雖然目前計(jì)盒法在分形維數(shù)計(jì)算方面達(dá)到了很高的準(zhǔn)確度以及很快的速度。但是，對(duì)計(jì)盒法的計(jì)算流程進(jìn)行編程實(shí)現(xiàn)的過(guò)程中，我們發(fā)現(xiàn)，在進(jìn)行上述的過(guò)程中存在需要優(yōu)化的部分。優(yōu)化的思路如為：上述過(guò)程中r=2，4，8…。即r 每次的取值為2 的冪次方。如當(dāng)r=2 時(shí)，計(jì)算N(r)的值，記為N(2)，當(dāng)r=4 時(shí)，記為N(4)。我們發(fā)現(xiàn)，對(duì)于r 的每次取值，都需要遍歷一次圖像矩陣以計(jì)算矩陣中包含1 的盒子數(shù)目，因此每次的遍歷計(jì)算過(guò)程中都存在大量的重復(fù)計(jì)算內(nèi)容，這對(duì)于計(jì)算圖像分形維數(shù)是很耗時(shí)的操作。尤其在圖像分辨率較高，從而圖像矩陣較大的情況下，這種耗時(shí)現(xiàn)象更加明顯。為此本文提出了對(duì)于計(jì)盒維數(shù)計(jì)算方法的優(yōu)化算法，具體過(guò)程如下：

（1）將彩色圖像轉(zhuǎn)化為灰度圖像并選擇合適的閾值將圖像進(jìn)行二值化操作，得到二值化之后的圖像。

（2）將上述預(yù)處理后的圖像矩陣分為盒子邊長(zhǎng)為 r 的若干個(gè)盒子( r =2i， i=1，2，3 … 2i＜d，其中d 為圖像長(zhǎng)度和寬度的最小值)。

（3）當(dāng)r 取值為2，4，8…時(shí)，首先以盒子邊長(zhǎng)r=2 對(duì)圖像進(jìn)行劃分，將圖像分為若干塊，統(tǒng)計(jì)此時(shí)圖像矩陣中包含1(分形圖像塊)的盒子數(shù)目，記作N(2)，記錄并保存N(2)。

（4）當(dāng)盒子邊長(zhǎng)r=4 時(shí)，不再遍歷原始圖像的矩陣，而是遍歷上一步N(2)中的值，從中統(tǒng)計(jì)包含1 的盒子數(shù)目，記作N(4)，記錄并保存N(4)。

（5）當(dāng)盒子邊長(zhǎng)繼續(xù)以2 的冪次方增長(zhǎng)時(shí)，依次在上一步保存的記錄中統(tǒng)計(jì)包含1 的盒子數(shù)目，而非每次遍歷原始圖像的矩陣。依次得到多組數(shù)據(jù)對(duì)(r, N(r))。

（6）對(duì)上述數(shù)據(jù)對(duì)在雙對(duì)數(shù)坐標(biāo)中進(jìn)行曲線擬合, 其中l(wèi)gr～I(xiàn)gN(r)曲線的直線部分的斜率即為所求的計(jì)盒維數(shù)D。

上述過(guò)程的核心步驟可以用圖1 表示。

圖1 模擬了一個(gè)具有16×16 個(gè)像素點(diǎn)的二值圖像的矩陣，因?yàn)槭嵌祱D像，所以矩陣中僅包含0 和1。當(dāng)盒子邊長(zhǎng)r=2 時(shí)，此時(shí)每個(gè)盒子的大小為2×2，如綠色圓圈所示，程序統(tǒng)計(jì)并保存此時(shí)包含1 的盒子個(gè)數(shù)N(2)。當(dāng)r=4 時(shí)，此時(shí)每個(gè)盒子的大小為4×4，如藍(lán)色框所示，此時(shí)只需要在N(2)的基礎(chǔ)上統(tǒng)計(jì)并保存包含1 的盒子個(gè)數(shù)N(4)即可。同理r=8 時(shí)，此時(shí)每個(gè)盒子的大小為8×8，如紅色框所示，在N(4)基礎(chǔ)上統(tǒng)計(jì)并保存包含1 的盒子個(gè)數(shù)N(8)即可。此時(shí)r 已經(jīng)達(dá)到了矩陣長(zhǎng)度的1/2，故r 不再繼續(xù)增長(zhǎng)，對(duì)得到的3 組數(shù)據(jù)對(duì)進(jìn)行最小二乘法的模擬，求得分形維數(shù)D。

4 試驗(yàn)及結(jié)果

對(duì)改分形維數(shù)的改進(jìn)進(jìn)行理論的分析后，通過(guò)編寫程序進(jìn)行了驗(yàn)證。本文通過(guò)同一張圖像對(duì)計(jì)盒維數(shù)程序的優(yōu)化前后的進(jìn)行測(cè)試。本文采用1024×1024 像素的謝爾賓斯基地毯圖進(jìn)行測(cè)試。謝爾賓斯基地毯圖是由波蘭數(shù)學(xué)家謝爾賓斯基年提出的，它是自相似集中的一個(gè)典型例子，其分形維數(shù)的理論值為log(8)/log(3)≈1.893。

在計(jì)算準(zhǔn)確度方面，用未改進(jìn)的計(jì)盒方法計(jì)算其計(jì)盒維數(shù)的結(jié)果為1.892，用改進(jìn)后的方法計(jì)算其計(jì)盒維數(shù)的結(jié)果為1.892，改進(jìn)前后的計(jì)算結(jié)果一致且與理論值1.893 之間的誤差為0.1%。這表明本文對(duì)程序的改進(jìn)在計(jì)算結(jié)果的準(zhǔn)確度方面與原有方法一致。

在運(yùn)行時(shí)間方面，未改進(jìn)的計(jì)盒方法計(jì)算其計(jì)盒維數(shù)用時(shí)0.264秒，利用本文改進(jìn)后的程序進(jìn)行計(jì)算，用時(shí)0.218 秒。計(jì)算速度提升了17.42%。

5 結(jié)論

本文通過(guò)對(duì)分形維數(shù)的計(jì)盒方法進(jìn)行研究，針對(duì)該方法運(yùn)行時(shí)間方面提出了改進(jìn)方案，并通過(guò)實(shí)驗(yàn)進(jìn)行了驗(yàn)證。結(jié)果表明，改進(jìn)后的程序仍能保證計(jì)盒維數(shù)的計(jì)算準(zhǔn)確度，且對(duì)計(jì)算速度有17.42%的提升。這對(duì)于計(jì)算圖像計(jì)盒維數(shù)方面的研究有重要意義。