Untitled Normal Page

The problem of Texture Segmentation involves subdividing an image into differently Textured regions. The robust Texture segmenting capabilities of human beings motivated the Computer Vision Researchers to formulate a Mathematical model for the eye. These efforts of modelling the eye lead to the discovery of the band-pass filterbank characteristics of the eye. These filters have the transfer function given by the Gabor elementary functions. The Gabor filters produce outputs which are significantly distinct for the differently textured regions. Detecting the discontinuties in the filter outputs and their Statistical properties help in segmenting and classifying a given image. Past works have been done on designing Gabor filters for having maximum discrimination of different textures. Most of these works were based on some Decission theoretic framework by minimising the Probability of misclassification for bi-partite images. However, our paper deals a more general problem of classification of multi-textured iamges using Clustering of filter output features. To obtain better classification results one needs to move the clusters far apart from each other. Taking this as our objective function we design the Gabor filter by tuning its parameters using Genetic Algorithms. Genetic Algorithms are found to be very efficient in Optimisation problems with non-differentiable and discontinuous objective functions. This paper describes an implementation of a Filter Bank and Classifier scheme for efficient segmentation and classification of differently textured images.

According to Wilson and Spann a Texture may be defined as "Spatially extended patterns based on the more or less accurate repetition of some unit cell (Texel : TEXture ELement)". The phenomenon of Segmentation denotes the process of partitioning a given image into different sub regions, each such region being different from the others in their Statistical properties. Our project aims at segmentation of differently textured regions in a given image. The process of Texture Segmentation finds immense applications in different fields of Computer Vision. Segmentation of textured images help a lot in the problems of Image Analysis.
The human visual system can pre attentively segment Textures in an efficient manner. This realisation has motivated extensive studies and has lead to a promising theory of human texture perception. This theory supported by much psycho physical and neurophysiological data, holds that the human visual system is performing some form of local spatial frequency analysis on the retinal image and this analysis is done by a bank of tuned band pass filters. The concept of local spatial frequency or local frequency, had been put forth in the context of communication systems, many years earlier by Gabor. Classically, images are viewed as either a collection of pixels (in spatial domain) or the sum of sinusoids of infinite extent (in spatial frequency domain). Gabor, however, observed that the spatial representation and the spatial frequency representation are just opposite extremes of a continuum of possible joint space/spatial frequency representations. In a joint space/spatial frequency representation for images, frequency is viewed as a local phenomena (i.e., as a local frequency) that can vary with position throughout the image. Using this paradigm within the framework of human vision, perceptually significant texture differences presumably correspond to differences in local spatial frequency content. texture segmentation thus involves decomposing a retinal image into a joint space/spatial frequency representation (by using a bank of Band pass filters) and then using this information to locate regions of similar local spatial frequency content. Motivated by the fact that a Gabor filter produces different outputs (called texture signatures) for distinct textured regions in an image, a number of studies has been performed on segmentation capabilities of Gabor filters. A number of papers deal with the performance of Gabor filters [Dunn/Higgins/Wakeley:1994], tuning of Gabor filter parameters in Decision theoretic framework [Dunn/Higgins:1995] and design of band pass filter banks [Bovik/Clark/Geisler:1990]. Current work by [Das/Kumar/Yegnanarayana:1998] suggests the use of 1-D Gabor filter windows instead of 2-D ones for better segmentation. We take up the work done by Das and propose a scheme for designing optimal 1-D Gabor filters using GA for the best performance in texture segmentation.

Recent studies on Mathematical modeling of visual cortical cells [Kulikowski/Marcelja/Bishop:1982] suggest a tuned band pass filter bank structure. These filters are found to have Gaussian transfer functions in the frequency domain. Thus, taking the Inverse Fourier Transform of this transfer function we get a filter characteristics closely resembling to the Gabor filters. The Gabor filter is basically a Gaussian (with variances s_x and s_yalong x and y-axes respectively) modulated by a complex sinusoid (with centre frequencies U and V along x and y-axes respectively) described by the following equation :-

This filter is having a complex characteristics and the plot of the Real and Imaginary parts of g(x,y) is shown below :-

Fig. 1 : Plot of Characteristics of the Real and Imaginary parts of the Gabor Filter

The variance terms s_x and s_y dictate the spread of the band pass filter centered at the frequencies U and V in the frequency domain. It is found that as the 2D Gabor filter is applied to the images, the edges are smoothened out in all directions due to the presence of the Gaussian term (having a smoothing effect) in the filter. This smoothing operation leads to loss of important edge informations. The Gabor function being a separable one, it is found that if a 1D Gabor filter is applied on the image along the two different (Horizontal and Vertical) directions, then the edges are smoothed in the direction of application of the filter leaving the edge information intact across the same. The two different filter outputs are then combined to get a better texture signature map. More so, the application of 1D Gabor Filters in place of two reduces the filtering operations from O(M²N²) to O(MN²). The operations thus performed on the image i(x,y) thus yields the output i'(x,y) as :-

By definition, a texture is basically a spatially extended pattern of more or less accurate repetations of some simillar units (called texels). Thus if we look at a particualr texture as simply a grid of texels (such as Bricks, scales of Fishes, etc.), then the texture is basically a 2D signal with some fixed Spatial Frequency. Hence, the Fourier Transform of this texture will be impulses in the Frequency domain located at a specific point corresponding to its spatial frequency. However, the Gabor functions being Gaussians modulated with complex sinusoids will produce impulses in the Gabor domain which die down following a Gaussian characteristics. Thus, we can expect the output of a Gabor Filter to have a Gaussian distribution. However, in natural textures this is not always the case. In natural textures, the texels are arranged in a random manner, with arbitrary orientations and overlaps among themselves.

Thus a natural texture is modelled as a 2D signal consisting of two parts; firstly the unperturbed texture having texels arranged in a perfect manner and secondly, the noise which takes into account the random perturbations like overlap, arbitrary orientations etc. Thus, inspite of having a Gaussian distribution of the Gabor filter output, we obtain a Rician distribution which is "almost a Gaussian" where the deviation is due to the "noise" of the unperturbed texture. The perturbed image shown in the above figure is passed through a Gabor filter of size 11x11 with standard deviations of 5 and centre frequencies of 0.1 along each directions. The pixel value distribution of the Filter output is shown below, which is observed to follow a Rician Distribution.

Fig. 3 : Distribution of the Pixel Values of the Gabor Filter Output for the Perturbed Texture shown in Fig. 2

To smoothen out the noise present in the Gabor Filter output, we further process it by passing it through a Gaussian Post Filter. Using the Separability criteria of the 2D Gaussian Filters, we again go for 1D Gaussian filters and recombine their outputs thereby retaining the edge information and reducing the number of filtering operations. The output of the Gaussian Post Filter (with reduced noise) has a (smoother) distribution which is more close to a Gaussian one and this makes the job of texture classification easier in the feature space formed by the mean and standard deviation (defining parameters of a Gaussian distribution).

The Genetic Algorithms are search algorithms based on the mechanics of Natural Selection and Genetics. Here a number of parameters are encoded into a bitstring called a Genotype. An initial Population is created by taking a number of such genotypes which are basically randomly selected in the search space. This algorithm combines the Survival Of the Fittest strategy with a Structured yet Randomised form of Information Exchange for generating new bitstrings in the Next Generation using some Genetic Operators. In every generation a new craeture (Bit String) is created using bits and pieces of the fittest of the old. Occasionally a new part is tried for good measure. While randomized, genetic algorithms are not simple random walk. They efficiently exploit historical information to speculate on new search points with expected improved performance. A fitness function is used to evaluate individuals, and reproductive success varies with fitness. GAs work with a coding of the parameter set, not the parameters themselves. The natural parameter set of the optimization problem is to be coded as a finite-length string over some finite alphabet. They search from a population of points, not a single point so it approaches parallely towards the optimized value. This algorithm use payoff information (called fitness function or objective function), not derivatives or other auxiliary knowledge. This facillitates GA to be used in Optimisation problems having a non-differentiable or dis-continuous Objective function. Unlike the Deterministic algorithms, GA use probabilistic transition rules, not deterministic rules. A Simple Genetic Algorithm can be listed as follows :-

1. Randomly generate an initial population M(0)
2. Compute and save the fitness u(m) for each individual m in the current population M(t)
3. Define selection probabilities p(m) for each individual m in M(t) so that p(m) is proportional to u(m) thus creating a mating pool
4. Generate M(t+1) by probabilistically selecting individuals from M(t) to produce offspring via genetic operators. In this operation individuals are chosen in groups of two and then mated.
5. Repeat step 2 until satisfying solution is obtained.

The Genetic Operators help in forming the population of the Next Generation following some Probabilistic Transition rules. The Genetic Operators are described as follows :-

Crossover
Takes two individuals and produces two new individuals. A random number is chosen between 1 and length of the string which is called the crossover point. Then the portions previous to and after the crossover points of the two strings selected for mating are interchanged. A Simple Crossover Phenomenon is shown for two bit strings-

Mutation
Some positions(selected randomly) on the string selected for mutation are changed according to some probability. The Mutation Phenomenon is shown for a bit string-

The output image obtained from the combined operation of the Gabor and the Gaussian Filter is analysed by sampling windows of a certain dimension. The features (Mean and Standard Deviation) of a certain window is calculated and that block is classified to be a certain texture region by using Minimum Distance Classifier. The feature points for a particular texture is known apriori and it is assumed that only textures in the database can appear in the images. The distance of a feature point obtained from a particular block from all the N (N=Number of Textures) feature points in the feature database is calculated and the block is assigned to a particular number corressponding to a texture from which the distance is the minimum. To make the Minimum Distance Classifier work properly, one has to be sure about minimising the overlap of the different clusters corresponding to different textures. For minimising this overlap, the Filters are tuned such that the centroids of the Clusters move far away from each other to get maximum discrimination between the differently textured regions.

The above figure explains the clustering problem. If the clusters overlap, its very difficult to assign a point to some cluster and there lies a high probability of missclassification. However, in the fig. (b), the separate clusters can be identified properly as ther is no overlap. Though its not always possible in practice to have a non-overlapping condition, but one may always minimise the extent of overlap. Thus, if (m_i,s_i) be the feature centroids in the feature space for the i'th Textuer, we calculate the Euclidean distance dij between these feature points (m_i,s_i) and (m_j,s_j) as :-

Our goal is to maximise the distance d_ij for all i and j in order to move the clusters far away from each other. To ensure the minimum overlapping of the clusters, we can only maximise the minimum of all d_ij and that will take care of maximising others. Thus our Objective function (Of) boils down to :-

Our goal is to choose the filter parameters such that the Objective Function Of is maximised. It is clear from the nature of the Objective Function, that it is a non-differentiable and discontinuous one. Thus, for Optimisation of this function, one can't really rely on the deterministic algorithms like Gradient Descent, Newton-Raphson etc. Stochastic programming methods for optimising such functions is found to be highly efficient in many practical cases. Thus, we opt for using Genetic Algorithms in the problem of maximising our Objective Function.

A suitable scale is chosen for the Gabor Filter to be designed according to the size of the Texel of the Texture. The standard deviations are chosen such that :-

The Post Filter scale is chosen to be the same as the Gabor Filter scale. Thus, U and V are the parameters to be optimised with GA for maximising the objective function. We represent the U and Vas a bit string for parameter coding. e.g. if U = 0.1 and V= 0.2 then we code it as 001100100011001000 ( Multiplying both by 1000, taking the binary number representation, and concatenating them). So our bit-strings are of length 18 bits. Initially we take a random population of some 18 bit strings and then apply Genetic Algorithm rules and operators. In this way, the fittest solutions are chosen down the generations and the objective function gets maximised in each generations. The stopping criteria is dictated by the number of generations for which the algorithm will run. Thus, more the number of generations specified, one may expect to get a better solution of the problem.

The implementation of the algorithm for Texture Classification and Segmentation is explained with the help of the block diagram given in fig. 5. The input image is first passed through a bank of Gabor and Gaussian Post Filters. The outputs

of these Filter Banks are then classified in the intermediate Classifier Stages as shown in the figure. These classifier blocks use the minimum distance classification algorithm as explained in section II and assign a particular number to a pixel if it belomgs to a particular textured region. The outputs of the intermediate classifiers comes to the Final Classifier Block where the Output Image is formed. The final classifier block does a pixel wise processing where it takes the (i,j)'th pixel from all the images and classifies it to that texture which is classified a maximum number of times by the filterbank-classifier stage combination. However, if there is no such unique classification for a pixel (which is identified the maximum number of times), then it marks it as unclassified assigns a zero. Finally, it checks for all the unclassified pixels; check their 3x3 neighbourhood and assign it to the region which it most likely belongs to simply by checking the maximum number of classified pixel values in that neighbourhood. Choosing such a small neighbourhood minimises the probability of misclassification. This classified image is then convolved with [-1 0 1] and its transpose for edge detection and the output comes as a completely segmented and classified image.

To evaluate the accuracy of the scheme, we define a metric "A" for classification accuracy. This is simply the ratio (expressed as a percentage measure) of the properly classified pixels to the total number of pixels in the image. This metric is evaluated on a set of test images whose classification results (ground truths) are known apriori.

The problem of segmenting and classifying multi-textured images is applied on a set of different images made up of a number of textures. The first step in implementing the Gabor Filter scheme is designing filterbank for efficient segmentation and classification of bi-partite images, i.e. images composed of two different textures. For the task of classifying two differently textured regions only one Gabor filter - Post filter cascade is necessary. Here, our objective is to separate two different clusters as far apart as possible. Thus, the objective function is only the distance between two points which needs to be maximised. This objective function is a differentiable and continuous one and thus one does'nt need Genetic Algorithms for tuning filters in this case. Simple Gradient Descent Algorithm is applied for tuning filter parameters and the resulting filters are applied on a number of bi-partite images. The following table shows the classification and segmentation results so obtained along with the list of filter parameters and classification accuracy.

Result Set - 1 : s_x=10,s_y=10,U=-0.005660,V=-0.005660
Original Image	Classification Ground Truth	Classified Image (89.6%)
Original Image	Classification Ground Truth	Classified Image (86.6%)
Original Image	Classification Ground Truth	Classified Image (91.36%)
Result Set - 2 : s_x=7,s_y=7,U=-0.005182,V=-0.005182
Original Image	Classification Ground Truth	Classified Image (93.08%)
Original Image	Classification Ground Truth	Classified Image (90.05%)
Original Image	Classification Ground Truth	Classified Image (85.29%)
Result Set - 3 : s_x=7,s_y=7,U=6.8663e-010,V=-6.8663e-010
Original Image	Classification Ground Truth	Classified Image (74.59%)
Original Image	Classification Ground Truth	Classified Image (79.25%)

So far we have dealt with bi-textured images. However, in practical situations we generally encounter images consisting of more than two textures. Here, for optimising filter parameters we have to use an objective function which is neither differentiable nor it is continuous. Hence, in this case we go for using Genetic Algorithms. The following table shows some of the results obtained from segmenting and classifying tri-textured images and also some bi-textured images.

This paper provides Mathematical and Experimental evidence suggesting that the application for Gabor Filters to Textured Images produces certain characteristic output signatures that are useful for segmenting the image. It is clear that in a truly autonomous Texture Segmentation Architecture, (such as the Human Visual System) filters can not be customised to individual Textures. In principle, a bank of Filters is required that spans the expected orientation and frequency domain of the textures of interest. Here, we have shown results for classifying and Segmenting bi-partite images. As the Genetic Algorithms provide efficient search in the parameter space, only a few Gabor Filters can be efficiently designed for efficient segmentation and classification of multi-textured images. It may not be always necessary to have the filterbank size same as the number of textures. For a given set of Textures it may also be possible to design smaller filter bank for efficient discrimination.

The final classifier block used above is inherently slow due to pixelwise information processing. This work may be extended to approximate the whole process of classification by an Artificial Neural Network which will take the input from the feature space and will classify the region accordingly. The use of Artificial Neural Network will also facilitate the classification of overlapping clusters in some higher dimension. The Neural Networks, once trained properly, are very efficient and fast in such applications. Using a Neural Network along with a tuned Filter Bank may allow the algorithm to be implemented in some stand alone system for Real Time Processing of Multi-Textured Images.

@Article{ Dunn/Higgins/Wakeley:1994,
author = { Dunn, Dennis and Higgins, William E. and Wakeley, Joseph }
year =       { 1994 },
keywords =    { texture segmentation, texture discrimination, computer vision, Gabor functions, image segmentation },
institution= { Department of Computer Science and Engineering, The Pennsylvania State University and Department of Electrical and Computer Engineering, The Pennsylvania State University and Applied Research Laboratory},
title = { Texture Segmentation Using 2-D Gabor Elementary Functions },
   journal = { IEEE Transactions on Pattern Analysis and Machine Intelligence },
   number = { 2 },
volume = { 16 },
month = { February },
pages = { 130- 149 },
annote = { Many texture-segmentation schemes use an elaborate bank of filters to decompose a textured image into a joint space/spatial-frequency representation. Although these schemes show promise, and although some analytical work has been done, the relationship between texture differences and the filter configurations required to distinguish them largely unknown. This paper examines the issue of designing individual filters. Using a 2-D texture model, it shows analytically that applying a properly configured band pass filter to a textured image produces distinct output discontinuities at the texture boundaries; the analysis is based on Gabor elementary functions, but it is the band pass nature of the filter that is essential. Depending on the type of texture differences, these discontinuities form one of four characteristics signatures : a step, ridge, valley, or a step change in average local output variation. Accompanying experimental evidence indicates that these signatures are useful for segmenting an image. The analysis indicates those texture characteristics that are responsible for each signature type. Detailed criteria are provided for designing filters that can provide quality output signatures. The paper also illustrates occasions when asymmetric filters are beneficial, an issue not previously addressed.
                        - Rajrup Banerjee (12'th February/2000) }
}

@Article{ Dunn/Higgins:1995,
author = { Dunn, Dennis and Higgins, William E. }
year =       { 1995},
keywords =    { texture segmentation, computer vision, Gabor Filters, image segmentation },
institution= { Department of Computer Science and Engineering, The Pennsylvania State University and Department of Electrical and Computer Engineering },
title = { Optimal Gabor Filters for Texture Segmentation },
   journal = { IEEE Transactions on Image Processing },
number = { 7 },
volume = { 4 },
month = { July},
pages = { 947-964 },
annote = {
                       Texture segmentation involves subdividing an image into differently textured regions. Many texture-segmentation schemes are based on a filter-bank model, where the filters, called Gabor Filters are derived from Gabor elementary functions. The goal is to transform texture differences into detectable filter output discontinuities at texture boundaries. By locating these discontinuities, one can segment an image into differently textured regions. Distinct discontinuities occur, however, only if the Gabor filter parameters are suitably chosen. Some previous analysis hs shown how to design filters for discriminating simple textures. Designing filters for more general natural textures, though, has largely been done ad hoc. This paper proposes a scheme for devising a more rigorously based method for designing Gabor Filters. It assumes that an image contains two different textures and that prototype samples of the textures are given a priori. It is argued that Gabor filter outputs can be modeled as Rician random variables and a Decision theoretic algorithm for selecting optimal filter parameters has been developed. To improve segmentation for different texture pairs a multiple-filter segmentation scheme, motivated by the Rician model has also been proposed. Experimental results indicate that the method is superior to previous methods in providing useful Gabor filters for a wide range of texture pairs.
                        This work can be extended to texture segmentation for multiple textured images by considering a multiple hypothesis testing problem for the texture classification. Further works can also be done for the implementation of the filter bank, thus obtained after optimisation.
                                     - Prithwijit Guha (13/2/2000)
}

@Article{Bovik/Clark/Geisler:1990,
author= { Bovik, Alan Conrad and Clark, Marianna and Geisler, Wilson S.},
year = { 1990},
keywords = { Amplitude demodulation, complex modulation, computer vision, Gabor function, multiple channel, phase demodulation, texture analysis, texture segmentation },
institution= { UTA - EECS and LMSC - Austin Division and UT - Dept. Psychology},
title = { Multichannel Texture Analysis using localised spatial filters },
journal = { IEEE Transactions on Pattern Analysis and Machine Intelligence },
number = { 1 },
volume = { 12 },
month = { January },
pages = { 55 - 73 },
}

@InProceedings{Das/Kumar/Yegnanarayana:1998,
author= { Das, S. and Kumar, G.P. and Yegnanarayana, B. },
year = { 1998},
keywords = { Gabor filter, texture segmentation, edge detection },
institution= { IIT Madras - CSE },
title = { One Dimensional Gabor Filtering for Texture Edge Detection },
booktitle = { Computer Vision, Graphics and Image Processing - Recent Advances },
pages = { 231 - 237 },
}

@Article{ Gabor:1946,
author = { Gabor, D },
year = { 1946 },
title = { Theory of Communication },
journal = { J. Inst. Elec. Eng. (London) },
volume = { 93 },
pages = { 429-457 },
}

@Article{ Kulikowski/Marcelja/Bishop:1982,
author = { Kulikowski, J. J. and Marcelja, S. and Bishop P.},
year = { 1982 },
title = { Theory of spatial position and spatial frequency relations in the receptive fields of simple cells in the visual cortex },
journal = { Biol. Cybern },
volume = { 43 },
pages = { 187-198 },
}

@Article{ Marcelja:1980,
author = { Marcelja, S. },
year = { 1980 },
title = { Mathematical description of the responses of simple cortical cells },
journal = { J. Opt. Soc. Amer },
volume = { 70 },
number = { 11 },
pages = { 1297-1300 },
}

Filter-1 : sigmax=10;sigmay=10;u=0.02381;v=0.02381 Filter-2 : sigmax=7;sigmay=7;u=0.033333;v=0.033333 Filter-3 : sigmax=11;sigmay=11;u=0.021739;v=0.021739
Original Image	Classification Ground Truth	Classified Image (75.73%)
sigmax = 10; sigmay = 10; u = 0.002; v = 0.997
Original Image	Classification Ground Truth	Classified Image (91.6%)
Original Image	Classification Ground Truth	Classified Image (92.6%)
Original Image	Classification Ground Truth	Classified Image (96.36%)