圖像分形維數的計盒方法改進

呂澤昆

（華北電力大學（北京）控制與計算機工程學院 北京市 102206）

1 概述

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

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

在日常的研究過程中，研究對象的信息可以通過多種方法加以記錄，從而得到對研究對象的描述。隨著近年來圖像領域的發展，人們的手機像素越來越高，圖像的清晰度越來越高，圖像已經成為描述研究對象的一個優秀的載體。隨著信息處理技術和計算機技術的發展，無數的圖形圖像對象可以轉化為數字圖像。數字圖像的本質是存儲在計算機中的矩陣。對圖像的處理，歸根到底是對矩陣的處理。因此我們可以將要研究的對象拍攝為圖像，對圖像進行操作，方便研究。其中利用分形理論對圖像進行研究已經成為一部分重要的內容。

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

2 分形維數計算方法

目前已經有許多關于分形維數的計算方法，主要包括Hasdorff方法、尺碼法、計盒法等。Hauslorff維數是分形幾何理論的基礎，但其只適合分形幾何的理論推導。對于實際應用中的計算無能為力。

2.1 尺碼法

圖1：改進后的算法原理示例圖

圖2：謝爾賓斯基地毯圖

利用計盒法進行計算的過程如下：

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

（2）變化測量尺碼ri的大小，重復步驟（1），得到多組ni，從而計算出多組di。

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

通過對尺碼法的流程分析，可以發現尺碼法存在以下的弊端。第一，尺碼法適合在生活中對分形維數進行粗略的計算，對于特殊的地形或者天空中的云等難以人為接近的對象束手無策。第二，由于每次選定測量尺碼時候，會受到人的主觀因素的影響，因此，利用該方法進行定量的測量會產生較大的誤差。故，尺碼法的應用在許多場景中會受到限制。

2.2 計盒法

為了解決尺碼法的弊端，研究人員提出了計盒法。近年來，計盒法因為計算方法相對簡單，測量誤差小且是對研究對象在圖像角度進行研究。因此，計盒法是目前計算分形維數時應用最為廣泛的方法之一。計盒法計算的分形維數也被稱為計盒維數。

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

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

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

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

（4）對上述數據對在雙對數坐標中進行曲線擬合, 其中lgr～IgN(r)曲線的直線部分的斜率即為所求的計盒維數D。

3 計盒方法的改進

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

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

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

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

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

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

（6）對上述數據對在雙對數坐標中進行曲線擬合, 其中lgr～IgN(r)曲線的直線部分的斜率即為所求的計盒維數D。

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

圖1 模擬了一個具有16×16 個像素點的二值圖像的矩陣，因為是二值圖像，所以矩陣中僅包含0 和1。當盒子邊長r=2 時，此時每個盒子的大小為2×2，如綠色圓圈所示，程序統計并保存此時包含1 的盒子個數N(2)。當r=4 時，此時每個盒子的大小為4×4，如藍色框所示，此時只需要在N(2)的基礎上統計并保存包含1 的盒子個數N(4)即可。同理r=8 時，此時每個盒子的大小為8×8，如紅色框所示，在N(4)基礎上統計并保存包含1 的盒子個數N(8)即可。此時r 已經達到了矩陣長度的1/2，故r 不再繼續增長，對得到的3 組數據對進行最小二乘法的模擬，求得分形維數D。

4 試驗及結果

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

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

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

5 結論

本文通過對分形維數的計盒方法進行研究，針對該方法運行時間方面提出了改進方案，并通過實驗進行了驗證。結果表明，改進后的程序仍能保證計盒維數的計算準確度，且對計算速度有17.42%的提升。這對于計算圖像計盒維數方面的研究有重要意義。