The problem of texture recognition is addressed by studying appropriate descriptors in the spatial frequency domain. During a training phase a filter is configured to determine different classes of texture by the response of its correlation with the Fourier spectrum of training-image templates. The technique is tested on standard texture patterns and then applied to magnetic resonance images of the brain to segment the cerebellum from the surrounding white and grey matter. Comparisons with established texture recognition techniques are presented, which show that the proposed method performs as well as, or better than, traditional techniques and has the advantage of not having to decide which texture measure to use for a specific image structure.
The objective of this work is the development of an algorithm which, after training, will be able to discriminate between different textures classes. The system proposed uses the properties of the Fourier spectrum of each pattern to achieve this discrimination.
Several techniques have been employed for texture based segmentation, for which Sonka [1] provides a comprehensive review. Most of them derive categories of texture descriptors and then, during a training phase, cluster these descriptors to achieve discrimination. Traditional methods of texture feature extraction are based either on statistical or structural models [2]. In the statistical model texture is defined by a characteristic set of relationships between image elements, and for most practical purposes these are determined from tonal values. We will be using one or more of these as comparators, namely
In principle the Fourier transform should a provide complete representation
of pixel-to-pixel relationships both in position and amplitude.
Figure 1, showing a Fourier transform
with orthogonal spatial frequency axes and , gives a simple justification
for this. Relatively large spatial frequency magnitudes within
annuli reflect texture scale, the further away from the origin
the finer the texture, and high values grouped within localised
wedges at an angle
represent lines or edges in the image in a direction of .
We will confirm our approach using Brodatz test patterns exhibiting texture at various scales, followed by a medical image segmentation problem.
An approach to the texture recognition problem in the simple case of two different types of texture can be formulated as follows:
Given two patterns p1 and p2 design a mask x that will discriminate between them by means of correlation, by maximising over the set of all possible masks, where the symbol denotes a correlation operator.
The above task is non-trivial since the optimal mask x is not usually either of the patterns. The correlation between domains can be defined using the normalised correlation coefficient:
where fij and gij refer to the ijth components of the each domain.
Consider two simple binary sequences p1 = 11011 and p2 = 11000. Using the normalised correlation equation above replacing components of f , g with those of p1, p2, produces 0.4082. If we attempt to discriminate between them by using either p1 or p2 as the correlating mask x we get an absolute difference in the response as:
Searching exhaustively the set of all possible masks x, reveals that other masks exist that achieve a higher absolute difference when correlated with the two patterns.
Masks can also be revealed which possess the equally useful property of minimising differences. [back]
Our goal is to design a mask which, when correlated with the Fourier spectrum of each of the given patterns, will produce a response such that the inter-class difference will be maximised and the intra-class differences will be minimised.
In previous work we have used GAs to solve large scale optimisation problems of shape matching[3],[4] and stack filter design [5] applied to medical images. We will now use GAs to solve the optimisation over all possible masks, by minimising (or maximising) an objective function based on the correlation.
The steps of the algorithm (Figure 2) can be summarised as:
The application of the Fourier transform to a texture image leads to a choice of whether to examine the magnitude or phase components of the transform. Although a mathematical background to the spectral properties of texture has suggested the use of transform magnitude, phase is an important feature of signals and in computation involving 2D transforms is often overlooked.
To discover which spectral quantity carries most textural information
for our medical images, we applied a forward 2D FFT on a 128 128
pixel central section of the image in figure 5 and formed a reconstruction
with an inverse FFT after encoding the magnitude at different
resolutions (from 2 to 8 bits), whilst keeping the phase component
unchanged and vice-versa. Table 2 shows the Mean Average Error
(MAE) between the original and reconstructed image. Altering the
encoding resolution for the magnitude results in slower rate of
increase in MAE than for phase. MAE is therefore more sensitive
to phase encoding resolution, justifying use of the magnitude
of the spectrum for texture matching at a given resolution.
The aim is to design a filter which when correlated with all the members of class A will produce a high response and when correlated with the members of class B will produce a low response. As a starting point the objective function should incorporate the terms:
where 0 < i < na, nb and na and nb are the number of members in class A and class B respectively. cia denotes the correlation coefficient of eq. (1), between the designed mask and the logarithm of the spectrum of the ith member of class A, arranged such that 0 cia 1. This function maximises the responses with all members of class A. Similarly:
minimises the responses with all members of class B, and:
will minimise all the intra-class distances, achieving uniformity of the response of the correlation within each of the classes. Since discrimination consists of three components: acceptance, rejection and uniformity of response, the objective function adopted is the sum of the three terms. The weighting factor (na + nb)/2 is applied to the first two terms so that their contribution balances that of the final term.
Our application of GA principles has been largely guided by Goldberg [6]. For a GA to be used the problem has to be encoded for genetic search, i.e the parameters have to be mapped to a finite length symbol string, using an appropriate conversion alphabet.
The main new element in the design of the chromosome is that it is two-dimensional. This gives it physical significance and makes the implementation of the genetic operators more meaningful. Being the output of a 2D FFT, the chromosome is a two dimensional matrix with n rows and n columns. Since Fourier spectra normally exhibit a considerable dynamic range in amplitude between basic and higher harmonics the most convenient way to proceed is via a logarithmic transform, quantised to an minimal number of bits. Each gene, representing logarithmic spectral magnitude is encoded in binary.
A significant factor affecting the GA's performance is the number of harmonics used to evaluate the correlation coefficient. Too few result in non-robust filters whilst too many produce over-sensitive filters with a sharp response to a specific image feature rather than mean regional texture. Eight harmonics were used in this work.
Selection is performed in the usual way enhanced by pre-computing
for each generation the number of offspring each chromosome is
allowed to have according to its fitness. The nature of the problem
and the design of the chromosome encouraged the implementation
of crossover by exchanging rectangular segments of chromosome,
with the breakpoints aligned on gene boundaries.
Each bit of each segment is copied perfectly otherwise a mutation occurs which acts as a logical NOT on the value of the bit.
The GA population was limited to 100 and 100 generations of evolution allowed. Crossover probability was typically 0.8 and 2 breakpoints allowed in each dimension. Bit mutation was 0.5%. The quantities correlated were the logarithm of the real part of the spectral magnitude, encoded to 8 bits. Experimental variation of the genetic parameters usually failed to alter the final convergence, although varying the crossover strategy from 1-breakpoint to n-breakpoints resulted in a halving of the number of generations needed to achieve a given convergence.
The result of the application of the GA-designed filter to an image is likely to be an incompletely segmented image, where regions containing texture which belongs to class A have high values and regions similar to members of class B have low values. To improve the segmentation and apply the method to more than two textures, a maximum likelihood decision rule that minimises the probability of false classification was used and a 5 x 5 median filter applied to the segmented image.
The candidate boundary that has been obtained so far may not accurately enclose the region of contrasting texture because of the filter's inherent spatial resolution, but it is likely that it will follow its boundary and have a similar shape. It can be further refined if there is strong edge information to be exploited. The brain image is an example where the distinctly different texture of the cerebellum may be enclosed in part by a strong boundary, information that is not utilised by a texture segmentation technique. We therefore assist the performance of the GA by an active contour model [7]. The snake is initialised with the boundary resulting from the texture segmentation and will migrate, via energy minimisation, towards a boundary suggested by edge-strength evidence in the image. [back]
Our initial objective is to compare the operation of the GA-based texture classification with conventional methods on controlled texture. Figure 4 contains sections of real, but standardised, Brodatz texture and shows the result of the GA based texture filter, using 32 x 32 pixel training segments, compared with the co- histogram method of Unser and the Laws R5R5 matrix.
A more ambitious application was to design a filter able to discriminate
between the characteristic texture of the cerebellum and surrounding
tissue. Although conventional edge based approaches might be used
(since an edge exists separating at least part of the cerebellum
from the rest of the brain), the complexity of grey-scale variation
within the cerebellum itself does not allow successful exploitation
of such methods, and the shape is insufficiently characteristic
for template matching.
We used trans-axial slices from an MRI data set (236 176
pixels at 1 mm resolution). Figure 5 shows the essential nature
of the problem. The lobes containing white and grey matter are
relatively uniform regions with randomly folded outlines, whilst
the brain stem is an enclosed uniform object. The texture of the
cerebellum has a characteristic structure with longitudinal folds
which give rise to a tonal variation having spatially dependent
orientation. albeit in a generally 'arc-like' manner. For the
training, class A consists of four 16 16 pixel patches
marked as black squares within the cerebellum and class B consists
of four external patches, marked, in Figure 6a, as white squares.
The segmented image is shown in Figure 6c.
The effectiveness of our technique needs to be tested against
other well established texture classification methods. We use
three descriptors derived from the GLSD, namely the contrast,
entropy and energy.
The GLSD descriptors (contrast, entropy and energy) are displayed as tonal maps in figure 7 with entropy the most characteristic of the three methods.
Figure 8(a) shows the image after median filtering. The primary contour lies on the cerebellum, albeit with a smaller, but similar, shape. The active contour enhanced segmentation is shown in Figure 8(b). The position of the cerebellum has been located and its shape accurately captured.
We next applied filters derived from one MRI trans-axial section to another taken at a different axial position where the texture may be slightly different due to biological change. The refined boundary is shown in Figure 8(d), indicating that filters derived using one image can detect similar texture in another.
In a final example a digitised hip radiograph (intentionally scanned at low resolution) was sampled in the trabecular patterned and smooth texture bone regions. Figure 9 shows the segmentation labelling and overlayed regions of characteristic texture
A system for texture discrimination, based on the spectral frequency properties is described and results produced using images containing standard textures and magnetic resonance images of the human brain. The system exploits well-established Fourier spectral properties. The difference from other texture classification methods lies in the fact that this approach searches the frequency spectrum of given textures, extracting characteristic relationships which are difficult to discover analytically. [back]
We are grateful for the financial assistance for K.D. from the 'Alexander S Onassis' Public Benefit Foundation.
[1] M. Sonka, V. Hlavac and R. Boyle, Image processing, analysis and machine vision , Chapman and Hall, 1993. [return to text]
[2] R.M. Haralick, "Statistical and structural approaches to texture", Proc. IEEE, 67, 1979, pp. 786 - 804. [return to text]
[3] K. Delibasis and P.E. Undrill, "Anatomical object recognition using deformable geometric models", Image and Vision Computing, 12, 1994, pp. 423-433. [return to text]
[4] K. Delibasis Undrill P.E. and G.G. Cameron, "Genetic Algorithms applied to fourier descriptor based geometric models for anatomical object recognition in medical images", Comp. Vis. and Image Underst., 66 ,3, 1997, pp 286-300. [return to text]
[5] K. Delibasis and P.E. Undrill. Genetic algorithm implementation of stack filter design for image restoration, IEE Proc. Vision, Image and Signal Processing, 143, 1996, pp. 177 - 183. [return to text]
[6] D. Goldberg, Genetic Algorithms in optimisation, search and machine learning, Addison-Wesley, 1989. [return to text]
[7] M. Kass, A. Witkin and D. Terzopoulos, "Snakes: Active contour models", Intl. J. Comp. Vis., Vol. 1,No. 4, 1988, pp. 321-331. [return to text] [back to Contents]
The above is a summary of the following papers:
Delibassis K, Undrill PE and Cameron GG, (1997) Designing Texture Filters with Genetic Algorithms : an application to Medical Images, Signal Processing, 57, 1, 19-33
Undrill PE, Delibassis K and Cameron GG, (1997) Using genetic algorithms to design 2D filters for texture interpretation and image restoration in the presence of noise. In: Proc. IEE Colloquium on 'Pattern Recognition', Digest 1997/018, IEE Press, London, pp 4/1 - 4/6 [back to Contents]
Paper or postcript versions can be despatched upon request to
Peter Undrill at the address given at the beginning of the document.