Efficient Fractal Method for Texture Classification

Andreea Lavinia Popescu1, Dan Popescu1, Radu Tudor Ionescu2, Nicoleta Angelescu3, Romeo Cojocaru1

Abstract— This paper presents an alternative approach toclassical box counting algorithm for fractal dimension estima-tion. Irrelevant data are eliminated from input sequences ofthe algorithm and a new fractal dimension, called efficientfractal dimension (EFD), which is based on the remainingsequences is calculated. The discriminating capacity and thetime efficiency of EFD are evaluated in comparison with fractaldimension (FD) computed by box counting both theoreticallyand empirically. The results revealed that EFD is better thanFD for texture identification and classification.

I. INTRODUCTION

Fractals are characterized in a special geometry calledfractal geometry which was introduced in [1] to characterizecomplex, irregular or fragmented natural forms like coast-lines and landscapes. One of the most familiar indicatorsto describe fractals is the fractal dimension. Because it canbe computed automatically and saves time and memory, thebox-counting algorithm is widely used to evaluate fractaldimension [2]. On the other hand, complex images suchas textures are characterized by varying spatial intensityand color of pixels and usually have statistic descriptors:characteristics associated with the grey level histogram, thegrey level image difference histogram, the grey level co-occurrence matrices [3] and the features extracted from suchmatrices [4], the auto-correlation based features, the powerspectrum, the edge density per unit of area, and so on.

Some researchers have used fractal techniques to describeimage textures and classify various types of texture-basedimages. The work of [5] showed the correlation betweenfractal dimension and texture coarseness. In a similar fashion,the work of [6] used fractal dimension to effectively classifynatural texture. In [7] a comparative study of fractal approachversus statistic approach, in texture analysis of remotelysensed images, is made. Two differential box counting algo-rithms that reduce the quantization errors when calculatingfractal dimension and give more satisfactory results ontextured images are presented in [8], [9].

Due to the simplicity and less calculus amount, the box-counting algorithm is widely used to estimate the fractaldimensions of textured images with or without self-similarity.

1Faculty of Automatic Control and Computer Science, PolitehnicaUniversity of Bucharest, 313 Splaiul Independentei Street,Bucharest, Romania andreea.lavinia@ymail.com,dan popescu 2002@yahoo.com,romeo.cojocaru@upb.ro

2Faculty of Mathematics and Computer Science, Universityof Bucharest, 14 Academiei Street, Bucharest, Romaniaraducu.ionescu@gmail.com

3Faculty of Electrical Engineering, Valahia Univer-sity of Targoviste, 2 Carol I Blvd, Targoviste, Romanianicoletaangelescu@yahoo.com

Some authors have tried to improve efficiency of the classicalalgorithms for estimating the texture features. To followthis line of research, the purpose of [10] is to increasethe efficiency of box counting method by assigning thesmallest number of boxes to cover the entire image at eachselected scale as required. The result was the improvementof estimation accuracy of fractal dimension in the texturedimage cases.

In a classification application a feature is efficient if rela-tive values for different classes are farther apart. Therefore,the goal of this work is to increase texture classification effi-ciency by adapting to texture specificity of the box countingmethod. A novel estimation procedure, called efficient fractaldimension (EFD), is presented in this paper. Theoreticalresults are presented to support the fact that EFD is moreefficient than the fractal dimension (FD) computed by boxcounting. Theoretical statements are validated by experimen-tal results conducted on the popular Brodatz [11] dataset oftexture images. In the experiments, other statistical featuresare associated with fractal dimension to create feature vectorsfor texture classification. Empirical results show that EFD isbetter than fractal dimension.

The paper is organized as follows. The fractal dimensioncomputed by box counting is described in section II. Thenovel approach and theoretical properties are presented insection III. Experiments are presented in IV. Finally, con-clusions are drawn in section V.

II. FRACTAL DIMENSION

In the basic box counting algorithm, the binary image issuccessively divided in finer equivalent sub-regions (4, 16,64 and more), by ratio (r = 2, 4, 8, and so on) on bothhorizontal and vertical axis respectively. If the object pixelvalue is represented by logical 1 and the background pixelvalue is represented by logical 0, then the fractal dimensionis calculated as:

D = limn−→∞

logN(r)

log r, (1)

where N(r) is the number of the same size squared sub-regions containing one or more pixels of value 1. In realrepresentation of digital images, the maximum of value of r(denoted by rmax) is limited by the image resolution.

Real textured images differ from ideal fractals and there-fore the points given by the coordinates logr and logN(r)are not positioned on a line. To address this issue, the fractaldimension D has different approximations: the slope of theline of least squares (LLS) of the set of points given by the

2013 2nd International Conference on Systems and Computer Science (ICSCS)Villeneuve d'Ascq, France, August 26-27, 2013

978-1-4799-2022-8/13/$31.00 ©2013 IEEE 44

plane coordinates logr and logN(r), the most frequent localslope and the last ratio given by:

logN(rmax)

log rmax.

For simplicity of calculation, usually the logarithm to base2 is employed. Because most of information is contained incontrast lines, we can consider the edges as object (logicalvalue 1) and the rest as background (logical value 0).

If xi, yi, i = {1, 2, ..., n}, are the coordinates in thelog-log representation, the LLS slope is calculated as thecoefficient, denoted by a, of the corresponding regressionline:

y = ax+ b

a = FD =

nn∑

i=1

xiyi −(

n∑i=1

xi

)(n∑

i=1

yi

)n

n∑i=1

x2i −(

n∑i=1

xi

)2 .(2)

If the image is represented by a multilevel intensityfunction, then the fractal dimension can be evaluated as theaverage AFD of fractal dimensions FDj of the representativecontour images (binary type) which are extracted from theoriginal image, for specified segmentation thresholds Tj ,where j = {1, 2, ...,m}, as follows [12]:

AFD =1

m

m∑j=i

FDj . (3)

Choice of thresholds for binarization (and hence selectedvalues of fractal dimensions to calculate AFD) is a delicateissue because they influence the average fractal dimension.Choosing Tj for calculating AFD is presented in [13],namely the range [lmax−0.1 · lmax, lmax +0.1 · lmax], wherelmax is the gray level for which the number of edge pointsis maximum.

III. AN EFFICIENT BOX COUNTING ALGORITHM

It is interesting to note the following features of the boxcounting algorithm for textures. First, one can observe thatfor r = {1, 2, ..., k}, all the boxes contain points of the edges.This means that the corresponding slopes have a value of 2.Second, due to finite resolution of images, the limit given in(2) may be approximated by the following equation:

FDl =ynxn. (4)

Let imA be a textured-image and A1, A2, ..., An be thecorresponding points in the log-log representation as pre-sented in Figure 1. Therefore, we have that:

OO1 = O1O2 = ... = On−1On = 1. (5)

Consequently, the textured image imA can be character-ized by a vector (vector of boxes) VA:

[VA] = [a1a2...an]T , (6)

Fig. 1. Log-log representation of the vector [a], corresponding to the imageimA.

where ak = OkAk = logNk and Nk represents thenumber of boxes of division level k which contain at leastone pixel of the contour image.

In the case of logarithm to base 2, the fractal dimension(FD) can be obtained by the following equation which is amore simple equation than (2):

FD =

nn∑

i=1

iai −(

n∑i=1

i

)(n∑

i=1

ai

)n

n∑i=1

i2 −(

n∑i=1

i

)2

=

12n∑

i=1

iai − 6(n+ 1)n∑

i=1

ai

(n− 1)n(n+ 1).

(7)

Proposition 1: Whatever the segment AkAk+1, the slopeis less than or equal to 2.

Proof: The proof is obvious. It begins with the follow-ing equation:

tanαk =AkCk

Ok+1Ok=logNk − logNk−1

1

= logNk − logNk−1.

(8)

Since it obvious that Nk ≤ 4 ·Nk−1, it follows that:

tanαk ≤ 2 + logNk−1 − logNk−1 = 2. (9)

For simplicity, we assumed that the fractal dimension (inthis case defined by FDC) is the slope of the secant lineOAn, given by tanαF (see Figure 1):

FDC = tanαF =AnCn

OOn=AnCn

n. (10)

The points: A1, A2, ..., Ak (for which the slopesOA1, OA2, ..., OAk are equal to 2) can be neglected. LetAk(k, ak) be the last point for which the slope of OAk isequal to 2 (tanαk = 2). Considering Ak and the remaining

45

points Ak+1, Ak+2, ..., An, a shorter vector of boxes, denotedby EVA (efficient vector of boxes), can be taken into account:

[EVA] = [akak+1...an]T , (11)

We can apply the estimation of the fractal dimension forthe curve with the origin in Ak, namely the efficient fractaldimension (EFD), as follows:

EFD =

(n− k)n∑

i=k+1

xiyi −

(n∑

i=k+1

xi

)(n∑

i=k+1

yi

)

(n− k)n∑

i=k+1

x2i −

(n∑

i=k+1

xi

)2

=

(n− k)n∑

i=k+1

iai −

(n∑

i=k+1

i

)(n∑

i=k+1

ai

)

(n− k)n∑

i=k+1

i2 −

(n∑

i=k+1

i

)2 .

(12)

Similar to FDC we can approximate EFD by EFDC ,which is the slope of the secant line AkAn, given by tanαFE

(see Figure 1):

EFDC = tanαFE =AnOn −AkOk

OOn −OOk=AnOn −AkOk

n− k.

(13)

Two properties of EFDC , which are also true for EFD,are presented next.

Proposition 2: Fractal dimension is smaller than efficientfractal dimension:

FDC ≤ EFDC .

Proof: Because AkOk = 2k, we obtain that:

tanαF − tanαFE =AnOn

n− AnOn − 2k

n− k=

=2kn− kAnOn

n(n− k)

=k

n(n− k)(2n−AnOn.

(14)

It follows that:AnOn = (AnOn −An−1On−1)+

+ (An−1On−1 −An−2On−2)+

+ ...+ (A2O2 −A1O1) +A1O1 ≤ 2n.

(15)

Therefore, tanαF − tanαFE ≤ 0 or equivalentlytanαF ≤ tanαFE .

Regarding the discrimination power, the following propo-sition establishes that EFDC has a better discriminationpower than FDC .

Proposition 3: The relative difference of fractal dimen-sion FDC is less than that of EFDC :

FDC(imB)− FDC(imA)

FDC(imB)≤

≤ EFDC(imB)− EFDC(imA)

EFDC(imB).

(16)

Proof: Let [VB ] = [b1b2...bn]T be the vector (ofboxes) for the textured-image imB (reference) and [VA] =[a1a2...an]T be the vector for the textured-image imA.Suppose that the corresponding efficient vectors EVB andEVA have the same size. In other words they can be definedas [EVB ] = [bkbk+1...bn]T and [EVA] = [akak+1...an]T .

The fractal dimensions FDC of the images imA andimB are FDC(imB) = tanβF and FDC(imA) = tanαF ,respectively (see Figure 2). Similarly, the dimensions EFDC

of the two images are EFDC(imB) = tanβFE andEFDC(imA) = tanαFE , respectively (see Figure 3).

Fig. 2. Estimation of fractal dimension (FD) for two images imA andimB .

Fig. 3. Estimation of efficient fractal dimension (EFD) for two imagesimA and imB .

Then, taking into account the relative differences, it fol-

46

lows that:

FDC(imB)− FDC(imA)

FDC(imB)−

− EFDC(imB)− EFDC(imA)

EFDC(imB)

=tanβF − tanαF

tanβF− tanβFE − tanαFE

tanβFE

=BnOn

n − AnOn

nBnOn

n

−BnOn−BkOk

n−k − AnOn−AkOk

n−kBnOn−BkOk

n−k

=BnAn

BnOn(BnOn −BkOk)(−BkOk) < 0.

To evaluate the effectiveness of the proposed algorithms,the relative difference between a reference imA and anotherimage imX can be computed as follows:

∆(X) =F (imA)− F (imX)

F (imA), (17)

where F can be replaced with either the FD or the EFDof the input image.

IV. EXPERIMENTS

The dataset used for testing the EFD approach presented inthis paper is the Brodatz dataset [11]. This dataset is probablythe best known benchmark used for texture classification, butalso one of the most difficult, since it contains 111 classeswith only 9 samples per class.

Experiments are conducted to asses the discriminatorypower of EFD by comparing it with compare FD. Preliminaryexperiments are performed on a few sample images from theBrodatz dataset. In the next experiment, EFD and FD areevaluated in a texture classification context. They are usedin combination with other features in a classification taskperformed on the full Brodatz dataset.

A. Learning Method for Classification

For the classification task, texture specific features areextracted from each image. An image is then be representedby a feature vector. The simplest statistical features extractedare the mean and the standard deviation. Relevant statisticalfeatures for texture classification can be computed fromthe Grey-Level Co-Occurrence Matrix (GLCM). Among thefeatures that show a good discriminating power proposedby [4], we use only four of them, namely the contrast, theenergy, the homogeneity, and the correlation. Gabor features,such as the mean-squared energy and the mean amplitude,can be computed through the phase symmetry measure(LIPSyM) presented in [14], for a bank of Gabor filterswith various scales and rotations. These features are relevantbecause Gabor filters have been found to be particularlyappropriate for texture representation and discrimination.

Three variants of feature vectors are used. The first variantincludes the 8 features described above. The second one, in-cludes the fractal dimension besides the 8 features describedabove. For the third variant, FD is replaced with EFD. The

goal of the classification task is to compare the accuracylevels obtain with these three type of feature vectors.

The classifier that is used in the experiments is the LinearDiscriminant Analysis (LDA). For a particular classificationproblem, some methods may be more suitable than others.The accuracy level depends on many aspects such as classdistribution, the number of classes, data noise, size of thetraining data, and so on. In some particular cases, whenthe number of classes is greater than 2, there is a seriousproblem with the regression methods. More precisely, someclasses can be masked by others. The LDA classifier is ableto improve accuracy by avoiding the masking problem [15].

B. Brodatz Preliminary Test

For preliminary experimental validation we used fourmonochrome images from three classes presented in Fig-ure 4. The first two images (imA1 and imA2) are of thesame class, while imB and imC are of different classes.First, selected test images have been resized to 512 × 512pixels with intensity levels of 8 bits. Next, images have beenconverted to binary format using the threshold Tj . If a pixelhad a gray value greater than Tj , then the pixel is assignedthe value of 0 (black), otherwise the pixel is assigned thevalue of 1 (white). Contour images are obtained from binaryimages by edge extraction using a local algorithm. Finally,the vector of boxes and the efficient vector of boxes canbe extracted from this representation. The resulted vectorscomputed from images imA1, imA2, imB and imC arepresented in Table I.

Observe that the box counts obtained for r ≤ 32 areequal for all images in Table I. Thus, k can be selectedto be log32 = 5 for the EFD computation. To evaluatethe effectiveness of the proposed approach by comparingit with FD, the relative difference between the referenceimA1 and the other images can be calculated using (17).Both EFD and EFDC are evaluated and compared withFD and FDC , respectively. Obtained results are presented inTable II. Empirical results confirm that the relative differencefor different classes is higher in the case of EFD thanin the case of FD. In conclusion, EFD can be usedas good feature for texture classification, showing a highdiscriminatory power.

C. Brodatz Classification Test

In this experiment, images are represented by normalizedfeature vectors. The baseline feature set includes the fol-lowing 8 features: the mean and the standard deviation ofthe patch, the contrast, the energy, the homogeneity, and thecorrelation extracted from the GLCM, and the mean-squaredenergy and the mean amplitude extracted by using Gaborfilters. The FD is added to the baseline feature set to obtainthe second feature vector. Finally, the EFD is added to thebaseline feature set to obtain the third feature vector. Thesethree different variants of feature vectors are used to performthe classification task. The goal of this experiment is to assessthe discriminatory power of FD and EFD. Table III comparesaccuracy rates of the LDA classifier based on the proposed

47

Fig. 4. Images selected for preliminary test from Brodatz database.

variants of feature vectors. The accuracy rates presented inTable III are actually averages of accuracy rates obtained over100 runs for each feature set. There are 3 random samplesper class for training, while the other 6 images from eachclass are left for testing.

TABLE IIIACCURACY RATES ON THE ENTIRE BRODATZ DATASET USING 3

RANDOM SAMPLES PER CLASS FOR TRAINING. RESULTS OBTAINED

WITH SEVERAL VARIANTS OF FEATURE VECTORS ARE PRESENTED.

Feature set Accuracybaseline (8 features) 78.92%

FD + baseline (9 features) 79.52%EFD + baseline (9 features) 79.84%

Empirical results show that both FD and EFD improveaccuracy when they are added to the baseline feature set.However, the LDA classifier based on the feature set thatinculdes EFD has an accuracy rate with 0.32% higher thanthe one based on the feature set that inculdes FD. Thus,the discriminatory power of EFD is greater than that of FD.But, another advantage of EFD is that it takes less timeto be computed. To compute EFD for the entire Brodatzdatabase, it takes 5.07 seconds on a computer with 2.3GHz Intel Core i7 processor and 8 GB of RAM memoryusing a single Core. On the same machine, FD needs 5.28seconds. In conclusion, EFD is better than FD in terms ofaccuracy and time efficiency. This experiment was designedto show the discriminatory power of EFD. The classifierpresented here uses a small feature set which doesn’t giveimpressive results. However, this classifier serves its purposeto show the difference between EFD and FD. State of artclassifiers obtain accuracy levels up to 90% on this dataset.For example, in [16] the accuracy rate reported on theBrodatz dataset using 3 training samples per class is 88, 15%.

V. CONCLUSIONS

In the textured image cases, efficient fractal dimensioncan be considered as an additional and cost efficient featureto improve texture characterization and classification. Theproposed algorithm derives directly from box counting byeliminating insignificant terms from the beginning of thecomputation. The results confirm that efficient fractal dimen-sion offers better results in texture classification than boxcounting estimation of fractal dimension.

ACKNOWLEDGEMENT

The work has been funded by FP7-REGPOT,ERRIC:Empowering Romanian Research on IntelligentInformation.

REFERENCES

[1] B. B. Mandelbrot, The fractal geometry of nature,1st ed. W.H. Freeman, Aug. 1982. [Online]. Available:http://www.worldcat.org/isbn/0716711869

[2] H. O. Peitgen, H. Jurgens, and D. Saupe, “Chaos and fractals: newfrontiers of science,” 1992.

[3] L. G. Shapiro and G. Stockman, Computer Vision, 1st ed. UpperSaddle River, NJ, USA: Prentice Hall PTR, 2001.

[4] R. M. Haralick, K. Shanmugam, and I. Dinstein, “Textural Featuresfor Image Classification,” IEEE Transactions on Systems, Man andCybernetics, vol. 3, no. 6, pp. 610–621, Nov. 1973.

[5] A. P. Pentland, “Fractal-Based Description of Natural Scenes,”IEEE Transactions on Pattern Analysis and Machine Intelligence,vol. 6, no. 6, pp. 661–674, Nov. 1984. [Online]. Available:http://dx.doi.org/10.1109/TPAMI.1984.4767591

[6] J. M. Keller, S. Chen, and R. M. Crownover, “Texture description andsegmentation through fractal geometry,” Computer Vision, Graphicsand Image Processing, vol. 45, no. 2, pp. 150–166, Feb. 1989.

[7] S. W. Myint, “Fractal approaches in texture analysis and classificationof remotely sensed data: Comparisons with spatial autocorrelationtechniques and simple descriptive statistics,” International Journal ofRemote Sensing, vol. 24, no. 9, pp. 1925–1947, 2003.

[8] N. Sarkar and B. Chaudhuri, “An efficient differential box-countingapproach to compute fractal dimension of image,” IEEE Transactionson Systems, Man and Cybernetics, vol. 24, no. 1, pp. 115–120, 1994.

[9] W.-S. Chen, S.-Y. Yuan, H. Hsiao, and C.-M. Hsieh, “Algorithms toestimating fractal dimension of textured images,” Proceedings of IEEEInternational Conference on Acoustics, Speech, and Signal Processing,vol. 3, pp. 1541–1544, 2001.

[10] J. Li, Q. Du, and C. Sun, “An improved box-counting methodfor image fractal dimension estimation,” Pattern Recognition,vol. 42, no. 11, pp. 2460–2469, Nov. 2009. [Online]. Available:http://dx.doi.org/10.1016/j.patcog.2009.03.001

[11] P. Brodatz, Textures: a photographic album for artists and designers,ser. Dover pictorial archives. New York, USA: Dover Publications,1966.

[12] D. Popescu and R. Dobrescu, “Carriage road pursuit based on sta-tistical and fractal analysis of the texture,” International Journal ofEducation and Information Technologies, vol. 2, no. 11, pp. 62–70,2008.

[13] R. Dobrescu and D. Popescu, “Image processing applications basedon texture and fractal analysis,” Applied Signal and Image Processing:Multidisciplinary Advancements, pp. 226–250, 2011.

[14] M. Kuse, Y.-F. Wang, V. Kalasannavar, M. Khan, and N. Rajpoot,“Local isotropic phase symmetry measure for detection of beta cellsand lymphocytes,” Journal of Pathology Informatics, vol. 2, no. 2,p. 2, 2011.

[15] T. Hastie, R. Tibshirani, and J. Friedman, The Elements of StatisticalLearning, corrected ed. Springer, July 2003.

[16] S. Lazebnik, C. Schmid, and J. Ponce, “A Sparse Texture Represen-tation Using Local Affine Regions,” PAMI, vol. 27, no. 8, pp. 1265–1278, Aug. 2005.

48

TABLE IVALUES OBTAINED FOR VECTORS OF BOXES CORRESPONDING TO THE FOUR TEST IMAGES. THE FOLLOWING NOTATIONS ARE USED r – THE NUMBER

OF SUB-REGIONS FOR EACH OF THE AXES, NX(r) – NUMBER OF BOXES THAT CONTAIN AT LEAST A SINGLE 1 IN IMAGE imX . EFD IS COMPUTED

FROM r = 32 TO r = 512.

r 2 4 8 16 32 64 128 256 512log r 1 2 3 4 5 6 7 8 9

logNA1(r) 2 4 6 8 10 11.82 13.39 14.76 15.59logNA2(r) 2 4 6 8 10 11.84 13.44 14.77 15.59logNB(r) 2 4 6 8 10 11.99 13.83 15.22 16.06logNC(r) 2 4 6 8 10 12 13.96 15.33 16.17

TABLE IIVALUES OBTAINED BY EFD, EFDC , FD AND FDC WHEN APPLIED ON THE TEST IMAGES. RELATIVE DIFFERENCES FROM THE REFERENCE IMAGE

imA1 TO THE OTHER IMAGES COMPUTED WITH (17) ARE ALSO SHOWN.

Image imA1 imA2 ∆(A2) imB ∆(B) imC ∆(C)FD 1.794 1.796 0.11% 1.856 3.46% 1.871 4.29%

EFD 1.412 1.411 0.07% 1.534 8.64% 1.567 10.98%FDC 1.732 1.732 0% 1.784 3.00% 1.797 3.75%EFDC 1.398 1.398 0% 1.515 8.37% 1.543 10.37%

49