Designing Texture Filters with Genetic Algorithms : an application to Medical Images

Konstantinos Delibasis, Peter E Undrill and George G Cameron,
Department of Biomedical Physics and Bioengineering,
University of Aberdeen, Foresterhill, Aberdeen, AB9 2ZD,
Scotland, UK.

Abstract

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.

Contents

  1. Introduction
  2. Texture discrimination using genetic algorithms
  3. Results
  4. Conclusions
  5. References
  6. Further Information                                                   [Back to C & IP Online Page]

1. Introduction

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.

1.1. Statistical approaches to texture based segmentation

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

1.2. Spatial frequency approaches to texture classification

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 .

Figure 1 - Texture variation in fourier space

We will confirm our approach using Brodatz test patterns exhibiting texture at various scales, followed by a medical image segmentation problem.

1.3 A correlation approach to pattern classification

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:

……(1)

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:

………….(2)

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.

Table 1 - Power of mask x to discriminate patterns p1 and p2

Masks can also be revealed which possess the equally useful property of minimising differences. [back]

2. Texture discrimination using genetic algorithms

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.

2.1. Correlation based optimisation

The steps of the algorithm (Figure 2) can be summarised as:

Figure 2 - Correlation process
  1. Rectangular patches are selected from a given image as members (training templates) representing each class of texture to be detected.
  2. A Fourier Transform (FT) is performed on each of the patches and the resulting spectra are logarithmically transformed to reduce the range of the values appearing in the patch spectra, simplifying the encoding into binary needed by the GAs.
  3. An objective function involving the responses of the correlation of the mask with the results of step 2 is evaluated over the set of all possible masks.
  4. An optimisation algorithm (in this case a Genetic Algorithm) is applied to the objective function over the set of all possible masks.

2.1.1. Choices for correlation

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.

Table 2 - Relative importance of magnitude and phase

2.2. The objective function

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:

……………………….……(3a)

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:

…… ………………(3b)

minimises the responses with all members of class B, and:

…………...(3c)

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.

2.3. Filter realisation using genetic algorithms

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.

2.3.1. The chromosome

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.

2.3.2. The genetic operators

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.

Figure 3 - Genetic crossover

Each bit of each segment is copied perfectly otherwise a mutation occurs which acts as a logical NOT on the value of the bit.

2.3.3. Choice of GA parameters

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.

2.4. Implementation of the system

  1. The starting point is an image with regions classified into two different classes. One or more training patches (32  32 pixels) are selected as members of each class.
  2. The first generation of the GAs is initialised with random values. The design of a discriminating filter now proceeds by GA optimisation
  3. This filter can be used either to find additional regions of these classes in the same or different image.

2.5. Post-processing the results of texture-based segmentation

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.

2.6. Derivation of an enclosing contour

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]

3 Results

3.1. Standard texture patterns

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.

Figure 4 - A comparison of GA texture analysis

3.2. Magnetic resonance brain images

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.

Figure 5 - Segmenting anatomical texture

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.

[Figure 6 about here]

3.2.1. A comparison of texture segmentation

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.

Figure 7 - GLSD maps (l to r: contrast, entropy, 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.

3.3. Boundary refinement

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.

Figure 8 - Boundary refinement

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

Figure 9 - Labelling characteristic texture in a hip-bone radiograph [back]

4. Conclusion

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]

Acknowledgement

We are grateful for the financial assistance for K.D. from the 'Alexander S Onassis' Public Benefit Foundation.

References

[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]

Further Information

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.