descriptor and was utilized by Peleg et 
al. /PeNaHa84/ in the context of texture 
classification. Peleg et al. called this 
descriptor the factal signature. They 
demonstrated the power of the method in 
the context of some Brodatz textures. 
The technical problem of measuring the 
fractal dimension of surfaces is quite 
difficult. Recently, Roy et al. showed 
empirically that dramatically different 
dimensions (2.01-2.33) can be achieved by 
applying different algorithms to the same 
data /RoGrGa87/. Most of the methods uti 
lized are based on the so-called variogram 
approach, which can be performed both in 
the spatial and frequence domains (see 
e.g. /Pentla83/). This shows that the 
fractal descriptor indeed has some simila 
rities with the other two methods presented 
above (using Fourier spectra or second 
order statistics). Other methods utilize 
e.g. the number of cubes that are necessary 
to estimate the volume /NaSoTa87/, the 
surface area covered by a blanket /PeNa- 
Ha84/ etc. 
The approach we have used originates from 
the classical problem of measuring the 
length of a coastline. In a texture win 
dow, the length of specific profiles are 
computed at each scale. According to the 
self-similar properties of fractals, 
[N(e)*e D = C] should hold at each scale. 
Here e is the scale, N(e) the number of 
units needed and C is a constant. By ta 
king the logarithm over this equation, 
parameters C and D can be estimated with 
a least-squares procedure. The estima 
tion is done separately in each of the 
four main directions at 10 successive sca 
les. This produces either 4- (fractal 
dimension) or 32 descriptors (in case of 
fractal signatures). In each direction, 
three profiles are used and the final value 
is an average of these three profiles. 
The fractal signatures are always computed 
with the help of three successive scales, 
similarly to the works of /PeNaHa84/ and 
/NaSoTa87/. 
2.4 The amplitude varying rate approach 
Very recently, Zhuang and Dunn reported 
for a new texture measure, which they cal 
led the amplitude varying rate approach 
/ZhuDun90/. In their method the Amplitu 
de Varying Rate Matrix (AVRM) is computed 
through examining the profile of each scan 
line in a fixed direction and recording 
frequencies of distances between pixels 
with the same gray level. From this matrix 
they are able to estimate the sizes of 
the primitives and the periodicity and 
contrast of textures. Zhuang and Dunn 
strongly argued that their method is better 
than the cooccurrence matrix method, be 
cause it can describe some physical inter 
pretations. They also showed empirically 
that their algorithm works better than 
the second order statistics. The result 
can be made questionable, because only 
the Haralick's five most popular features 
where used. 
Because of these promising results we wan 
ted to include this descriptor to the test. 
Again the AVRM-method was utilized in the 
same framework as the first two methods 
reported. 
3. CLASSIFIERS 
Because the usual assumption of multi-nor 
mal probability density functions in the 
context of parametric classifiers does 
not hold in texture classification, the 
Bayesian optimality of such a classifica 
tion system is brutally violated. That is 
why, the maximum likelihood (ML) classi 
fier serves here just as a reference. The 
other two classifiers (k-NN and ALSM) app 
lied are both non-parametric and can better 
adopt themselves to the non-linear decision 
boundaries. 
3.1 The k-NN classifier 
The k-NN classifier (see e.g. /DevKit82/) 
can be regarded as the most important clas 
sifier with respect to practical applica 
tions. It has been proven in /CovHar67/ 
that the (large sample) error rate of the 
k-NN classifier monotonically decreases 
towards the optimal error bound of a 
Bayesian classifier as k goes towards in 
finity. When sample size is finite, this 
is not anymore valid /Devivj80/. 
The proper choice of k is of course a dif 
ficult problem. In principle, one should 
choose k as big as possible, but practical 
problems will occur, because of the fini 
te sample sizes (k does not monotonically 
decrease the classification accuracy). A 
useful guideline given in literature sug 
gests to select k proportional to the squa 
re root of the sample size. 
The k-NN classifier has not been too widely 
used in practical applications, because of 
the storage and computational complexity 
it imposes. However, techniques have been 
presented for competing with traditional 
techniques in this respect. The solution 
is to use two preprocessing techniques, 
namely, Editing and Condensing (see /Dev- 
Kit80/). The idea is to select a small 
subset from the training set such that 
the 1-NN classification with the reduced 
dataset achieves a performance, which is 
close to or better than the performance 
of 1-NN classification with the complete 
set. The editing procedure is based on 
the holdout technique and can be summarized 
as follows /DevKit80/: 
(1) Make a random partition of the 
available training data into N 
subsets (diffusion). 
(2) Classify the samples in subset i 
using the k-NN of subset 
M0D((i+1),N) (classification). 
(3) Discard all the samples that were 
misclassified at step 2 (editing). 
(4) Pool the remaining data to consti 
tute a new data set (confusion). 
336