REASERCH INTERESTS AND CONTRIBUTIONS IN SIGNAL AND IMAGE PROCESSING
During the postgraduate studies, my research was focused on signal representation and analysis and it has been later extended to computer vision and image analysis. After graduation I pursued my research interests in computer vision and texture characterization for biomedical applications at the University of Belgrade, Belgrade, Yugoslavia. Currently, at Bell Labs, Lucent Technologies, Murray Hill, NJ, I am involved in the design, performance analysis and implementation of perceptually based algorithms for web based image searches.
My research contributions are divided into three areas, which are described as follows.
1. General Image Processing algorithms
1.1 Theoretical Analysis of Wavelet Filter Banks and Selection of an Optimal Wavelet Family for Texture Characterization
Wavelet transform has found application in numerous signal and image processing operations. One intensively investigated field is numerical description of texture via discrete wavelet transform (DWT). Following Mallat's initial proposal in 1987, many researchers have examined the utility of various wavelet representations in texture analysis. All these studies revealed that the scale-frequency approach is very suitable for the description and analysis of natural textures. Although all theoretical and implementation aspects of the wavelet based algorithms are very well studied and understood, many issues related to the choice of filter bank in the texture processing remained unresolved untill now. Previous investigations have mostly considered applications of the wavelet transform in image coding. For example, regularity and number of vanishing moments have been used for filter evaluation in image coding, but despite all the efforts their importance is still an open question. Another reliable filter evaluation was obtained by taking into account a shift variance degree of the decomposition filters. However, the utility of all these metrics in prediction of texture characterization performance is not established yet. The impact of the wavelet basis has been only partially addressed in a very few of the recently published papers, where the choice of an optimal wavelet filter bank for texture characterization was identified with the selection of FIR filters with good frequency localization and as shorter impulse response as possible. The scope of this research was to investigate whether the properties of decomposition filters (regularity, vanishing moments, degree of shift variance, linear phase, etc.) play an important role in texture description, and which feature is dominant in the selection of an optimal filter bank. Hence, in this work we have theoretically analyzed main properties of the DWT filter banks: shift variance, regularity and number of vanishing moments, as well as the reported filter design techniques. Our theoretical analysis and the experiments conducted show that the selection of decomposition filters has a significant influence on the results of texture characterization. We present ranking for 20 most often used orthogonal and biorthogonal filters, and establish criteria for LP and HP filters in the wavelet decomposition system for texture description.
1.2 Design and Application of Nonseparable Filter Banks for Texture Characterization
Texture analysis is of the highest importance in computer vision, since many natural scenes can be viewed as a composition of different textures. Therefore, in the past three decades a large number of techniques for calculation of texture features has been proposed. Recently, algorithms based on multichannel and multiresolution analysis have received significant attention. These approaches were inspired by various psychophysical experiments and studies of the human visual system, showing that concepts of frequency and scale are fundamental for texture description. One intensively investigated approach is based on the wavelet transform. However, all the methods presented so far, consider only 2D filter banks with separable filtering and rectangular downsampling. On the other hand, nonseparable systems, although more difficult to design and implement, offer many advantages and greater flexibility. In addition, various decomposition schemes that can be accomplished by choosing lattices of a different structure allow us to observe a signal from many different viewpoints. Therefore, it is interesting to look into the texture from all the aspects offered by diverse nonseparable decompositions. The task is even more attractive, bearing in mind that untill now, nonseparable multidimensional filter banks were applied primarily in image coding. Here, we investigate the design and the application of the quincunx and hexagonal wavelet transforms for the texture characterization, and address several questions of potential importance for this purpose.
A fundamental difference between a separable filter bank and a "true" multidimensional filter bank designed on arbitrary lattice is in the manner in which the filtering and sampling operations are performed. In 1D, downsampling a signal by a factor N is accomplished simply by retaining every Nth sample and discarding the rest. In 2D, the downsampling is performed in accordance with a downsampling matrix D, by retaining only the samples on the sublattice generated by D. Hence by choosing the sampling lattice in a different manner we demonstrate the diversity of possibilities offered by these nonseparable decompositions. Moreover, to choose an optimal nonseparable solution for a particular problem, it is important to analyze all the advantages and disadvantages of different sampling structures in texture analysis. Here we introduce the wavelet transform for arbitrary sampling lattices, analyze spectral properties of quincunx and hexagonal decompositions and connect them with the texture analysis problem. We also address the design of nonseparable filters and construct McClellan transforms for the design of nonseparable filters. Finally, for both separable and nonseparable decompositions, on a set of Brodatz textures, we perform feature extraction with 2D filters derived from the same 1D wavelet family. Our experiments show that: 1) in standard working conditions all decompositions perform equally, 2) quincunx transform is appropriate for analysis of small textures, classification with small number of features, enables rotationally invariant description and represents an optimal choice in a noisy environment, 3) hexagonal transform is optimal for fine structural analysis and performs well in the presence of noise, 4) hexagonal and separable decompositions are suitable for classification of visually similar textures. Finally, both nonseparable decompositions are incorporated in a region growing technique showing their applicability for texture segmentation
1.3 New Separable Wavelet Decomposition for Image Analysis and Compression
Here we propose a new separable extension of the one-dimensional wavelet transform to the two dimensional case and describe its application to the texture analysis and image compression problems. The main difference between this algorithm and the traditional pyramidal decomposition is that the decomposed images are characterized by different resolution levels for different directions. Since the decomposition is performed mainly in the mid frequencies, where the most significant information about natural images is concentrated, this approach has advantages for the purpose of texture description and image coding over the traditional decomposition schemes. For example, the pyramid structured wavelet decomposition (PSWD) of 2-D signals has certain limitations in texture characterization, since the decomposition is carried only in the low frequency channel. Consequently, very important texture information contained in the mid-spectrum is not described well enough. Much more appropriate, but computationally very exhaustive, is the so called tree-structured wavelet decomposition (TSWD), in which the further decomposition is performed in all frequency channels. The common feature of these two algorithms is that the separability is exploited at each stage of the decomposition, so each stage of the decomposition includes both row and column transforms. The basic idea of the proposed algorithm is very simple: instead of separable row/column computation at each stage, all octaves in each dimension are successively computed, so complete 2-D wavelet transform is implemented as separable computation of complete 1-D transforms. As there are N row DWT's and N column DWT's, the new algorithm will be called 2N´ 1-D DWT. Hence this scheme enables more flexible texture energy distribution compared to the standard pyramidal wavelet representation. Because length N/2, length N/4, etc., DWTs are applied only once to all rows and columns, the computational complexity is between the computational complexities of PSWD and TSWD. We also prove that when lowpass and highpass filters are derived from the orthonormal families the perfect reconstruction property is preserved. The new algorithm is applied to various natural and biomedical images with a high classification accuracy, showing its applicability for analyzing a large class of textures. Finally, we also address the applicability of the method in image coding applications.
1.4 Transform Based Method for the Design of Hexagonal FIR Filters
Here we present a transform based solution for the design of multidimensional hexagonal FIR filters. The proposed solution maps the coefficients of a one-dimensional (1D) prototype filter, to a two-dimensional filter (2D), which preserves the perfect reconstruction property as well as zeros at the points of replicated spectra.
In the past decade the wavelet decomposition emerged as a new, powerful tool for signal approximation and modeling. The most often used generalization of the wavelet transform is separable, where a multidimensional scaling function and wavelets are expressed as tensor products of the corresponding 1D families. However in many practical applications better results can be achieved with nonseparable extensions. One nonseparable decomposition scheme having many desirable properties is based on the hexagonal sampling lattice. The hexagonal sampling is an optimal sampling scheme for signals which are bandlimited over a circular region in the spectral domain and the hexagonal subsampling provides the tightest packing of all regular 2D lattices. In addition, the computational savings in the application of the hexagonal sampling are also significant. Finally, the nonseparable decomposition based on hexagonal symmetric QMFs produces much better frequency tuning than other types of decompositions. The main problem in the application of hexagonal systems lays in very difficult filter design, mainly based on the constrained nonlinear cascade structures and optimization techniques. Hexagonal filters can also be constructed by using some of the traditional techniques such as: frequency sampling, window or equiripple designs. However, all these methods are generally unable to construct multidimensional filters with all the desirable properties such as: a certain degree of regularity obtained with maximally short filters, symmetry or orthogonality. The design of 1D filters for the PR banks has been studied extensively and many different filter families have been presented. Therefore, when it is possible, transformations of a one-dimensional design into a multidimensional one is a very desirable approach.
Here we present a transform based solution for the design of multidimensional hexagonal FIR filters, which can be also used for construction of continuous hexagonal wavelet bases. The proposed solution is based on the factorization of the hexagonal decimation matrix followed by the application of the McClellan transform. In our method, the hexagonal sampling matrix is factored so that it becomes a product of two matrices, each having the determinant equal to 2. In this way, we can use already designed 2D filters for the matrices with determinant 2 (which could be only quincunx or separable matrices). There are two main advantages of the proposed solution over the direct application of the McClellan transform. First, as mentioned before, it allows for "shorter" 2D filters. In addition, by direct application of the McClellan transform to 1D biorthogonal filters from a two-channel filter bank, the perfect reconstruction property cannot be achieved. On the other hand, our method preservs the PR property. This can be easily established since the hexagonal system presented can be seen as a cascade of two two-channel PR filter banks. The first one performs 2D quincunx transform and the second one performs 1D decomposition along the y axis. The proposed solution can also be used for the construction of continuos wavelet bases as well as activations in the wavelet neural networks.
2. Image processing for biomedical applications
2.1 Fully Automated Method for Automatic Segmentation of IVUS Images
There are different methods for evaluating coronary artery disease: angiography, magnetic resonance imaging, tomography, echocardiography or intravascular ultrasound. Intravascular ultrasound (IVUS) is a catheter based technique which provides two-dimensional images that accurately demonstrate lumen geometry and structure. Therefore, clinical community expresses great interest in using this imaging method in evaluating coronary artery disease. Unfortunately, untill recently, quantitative IVUS studies of coronary artery sclerosis have been performed mostly by manual measurements and from manually traced wall borders. A method for automatic detection of the boundaries between the structural layers in the arterial wall offers numerous advantages for efficient quantitative assessment of blood vessel shape. Hence, in the past few years several researchers began to develop computer based methods for identifying arterial borders. However, a fully automated method for segmentation of the IVUS images has not been presented yet. Therefore, the major goal of our research was to develop and validate a fully automated, robust and efficient method for determining the arterial lumen and wall contours in the IVUS images. The robustness requirement dictates that the method has to be able to handle a variety of cases with good performance under all working conditions. From the users point of view, the segmentation process has to be fast and reliable to separate different tissue regions. Our segmentation method is based on automatic thresholding in the texture feature space, allowing for partitioning of an IVUS image into different regions. After employing textural operators to separate different tissue regions, we perform morphological processing to refine extracted contours. Moreover, to determine vessel borders accurately, we integrated the knowledge of the vessel anatomy and ultrasound image characteristics in all processing steps. The approach is robust, since it can handle a variety of input images. Most of image degradation factors were incorporated in the morphological model of the vessel contours making the segmentation result insensitive to noise, distortions, or poor image quality. The method is efficient enough for low-cost implementation, due to the selection of simple, yet accurate, texture operators. The processing speed is also increased by applying a concept of hierarchical thresholding. Consequently, all component labeling, object extraction, object filling and morphological opening procedures were performed as binary operations between two regions or on the single contour. Finally, since the accuracy was the most important requirement, the whole procedure was carefully tested. A validation study compared our method with referent manual analysis in two aspects. First, the contour preciseness was expressed through correlation coefficient and the match ratio. Second, the accuracy in determining the relevant vessel shape parameters was expressed as mean and standard deviation of relative error. In both aspects, our method consistently yielded good results.
2.2 Wavelet Image Decomposition for Myocardial Tissue Characterization After Acute Myocardial Infarction: A Novel Approach for the Detection of Successful Reperfusion in the Early Postinfarction Period
Some computer applications for tissue characterization in medicine and biology, such as analysis of the myocardium or cancer recognition, operate with tissue samples taken from very small areas of interest. To perform texture characterization in these applications, only few texture operators can be employed. These operators should be sensitive to noise and image distortion and yet be reliable in estimating the texture quality from a small number of image points. Therefore, in order to describe the quality of infarcted myocardial tissue, we proposed a new wavelet-based approach for analysis and classification of texture samples with small dimensions.
Acute myocardial infarction is caused by the obstruction of a coronary artery by a thrombus, leading to irreversible damage of the heart muscle (myocardium). Two-dimensional (2D) echocardiography is a well-established noninvasive technique for monitoring the effects of various therapeutic interventions after infarction. One possible therapeutic intervention is thrombolitic therapy which results in dissolution of the thrombus and the restoration of normal coronary flow. In order to plan the management strategy in the post-infarction period the most important issue is to detect whether the therapy was successful or not. Since the quality of standard ultrasound images precludes accurate identification of myocardial viability, the search for additional sources of information is still in progress. Image processing, namely texture analysis, provides one possible approach. This is because myocardial infarction produces significant alteration of myocardial acoustic properties, and this can be detected by ultrasound as a textural pattern different from the normal one.
Texture characterization of the myocardial tissue is not an easy task to perform. First, ultrasound images have very poor quality: they are degraded by speckle noise, acoustic shadowing, and system distortions present in all instrumentation. Another disadvantage of 2D echocardiography is caused by the heart muscle anatomy. Compared to the dimensions of the entire heart, the myocardial area has a very small width. For example, with 512´ 512 pixel resolution, tissue samples taken from the myocardium do not exceed 16´ 16 pixels. These dimensions are usually inadequate for reliable estimation of texture quality and separation between tissue classes is extremely difficult to perform. Over the years numerous methods for texture classification have been developed: first-order and second-order statistics of texture, Gaussian Markov random fields, fractal models, multichannel methods and multiresolution analysis. Many of these approaches provide good results in different fields of application; however, a large number of them have showed very low classification rates (or could not be implemented at all) when texture samples are of small dimensions. Therefore, in order to investigate possible differences in myocardial tissue between patients with infarction, we proposed a new wavelet-based filtering technique.
The main idea of the new algorithm lies in the successive decomposition of the input image with wavelet basis functions and the synthesis of new images with higher resolution. First, the input texture image is decomposed with a filter bank derived from an biorthogonal wavelet basis and an image approximation on the higher resolution is formed. From texture characterization perspective, the proposed decomposition scheme performs more efficient energy distribution of an image, and the first-, second- and higher-order statistics calculated on the expanded images can be used as reliable texture descriptors for classification purposes. Hence, texture energy measures calculated at each output of the filter bank as well as energies of synthesized images are used as texture features in the classification. We also proposed a new unsupervised classification technique based on a modified statistical t-test. The method was tested with clinical data and the classification results obtained using this method were shown to be very promising.
2.3 Nonseparable Wavelet Transform for Characterization of Liver Tissue and Detection of Diffuse Diseases
One important application of diagnostic ultrasound is imaging of the liver. Many methods for differentiation between normal and abnormal tissues are based on the examination of B-scan images. However, for characterizing diffuse diseases (such as cirrhosis, steatosis or hepatitis) clinical ultrasound is not reliable and diagnosis is usually performed by biopsy. Therefore, a reliable noninvasive method for early detection and differentiation of diffuse diseases is clearly desirable. Since steatosis and cirrhosis produce different changes in acoustical properties of the liver tissue, which results in different image textures, an alternative approach can be found in computer based texture analysis.
Many researchers have studied the problem of liver tissue classification. However, as to our knowledge, none has ever addressed the question of detecting the cirrhosis and steatosis in the early stages of a disease. We have previously shown that the scale/frequency approach based on the separable wavelet transform is appropriate for the analysis of ultrasound textures. Here we proposed a new approach for liver tissue characterization based on nonseparable wavelet decomposition, and its application for the discrimination of visually similar diffuse diseases of liver. The proposed feature extraction algorithm uses the filter bank performing nonseparable quincunx wavelet transform and characterizes textures by a set of channel variances estimated at the output of each filter. Classification experiments on a set of three different tissue types show that the scale/frequency approach, particularly the one based on the nonseparable wavelet transform, could be a reliable method for texture characterization and analysis of B-scan liver images.
3. Image database retrieval
3.1 Modeling of Color Patterns: The Most Important Perceptual Criteria and Their Relationships in Human Perception of Similarity
Our understanding of color textures and color patterns is very modest compared to our understanding of other visual phenomena such as color, contrast or even gray-level textures or gray-level patterns. This is mainly because the basic dimensions of color patterns have not yet been identified, a standardized vocabulary for addressing their important characteristics does not exist, nor is there a grammar defining how these dimensions are to be combined. Previous investigations in this field concentrated mainly on gray-level natural textures. Particularly interesting is work of Rao and Lohse: their research focused on how people classify textures in meaningful, hierarchically-structured categories, identifying relevant features used in the perception of gray-level textures. Similarly, here we determine the basic categories used by humans in judging similarity of color patterns, their relative importance and relationships, as well as the hierarchy of rules governing the use of these categories in human's perception of similarity. The attributes we extract are applicable to a broad range of textures, starting from simple patterns, all the way up to complex, high-level visual texture phenomena.
To understand and model the human perception of similarity we performed a set of subjective experiments. Experimental data were interpreted with the multidimensional scaling techniques and hierarchical clustering analysis. Multidimensional scaling was applied to determine the most important dimensions of pattern similarity, while hierarchical clustering helped us understand how people combine these dimensions when comparing color patterns. Hence, as a result of the experiments we obtained five perceptual criteria used in comparison between color patterns (vocabulary) as well as a set of rules governing the use of these criteria in similarity judgment (grammar). The perceptual criteria are: 1) overall color, 2) directionality and orientation, 3) regularity and placement, 4) color purity and 5) complexity and heaviness. These five dimensions from the pattern vocabulary are governed by the following grammar rules: 1) rule of equal pattern, 2) rule of overall appearance, 3) rule of similar pattern, 4) rule of dominant color and 5) rule of general impression.
While most of our research has been directed at color patterns, we believe that the underlying methodology has greater significance beyond color and texture. We believe that such a methodology, if applied to other retrieval tasks (such as shape and object understanding), will result in a system that is better matched to human expectations. A major advantage of such an approach is that, unlike in most current systems, it eliminates the need for selecting the visual primitives for image retrieval, and it also does not expect the user to assign weights to them. Moreover, we expect that the color pattern understanding model presented in this work will help researchers in image processing, computer vision and computer graphics to build effective and elegant algorithms for texture analysis, manipulation and display. Finally, this model can be used in the development of more natural, human-like interfaces between users and machine.
3.2 Image database retrieval system
We have designed, implemented and tested an end to end, perceptually based system for retrieval and matching of color patterns. There is a necessity for such an "intelligent" retrieval system in applications such as digital museums and libraries, design, architecture and digital stock photography. The central idea of the work is that similarity judgment has to be modeled along perceptual dimensions. Hence, in our earlier work we conducted an experiment on how people evaluate similarity of color patterns. This data was used to discover the intrinsic dimensions of color pattern matching used by humans. We used multidimensional scaling and hierarchical clustering analysis to discover the perceptual criteria for judging the pattern similarity (vocabulary) and the rules governing their use (grammar). Here we present a new computational model which accepts patterns as input, and depending on the query, produces a set of choices that follow human behavior in pattern matching. The new image feature extraction algorithms, as well as the new distance metrics were designed to correlate with human performance. Finally, the system has been extensively tested on numerous examples from different image databases, verifying the robustness of our approach and algorithms. Given below is a list of the significant novel contributions:
a) Color and texture are used and combined into perceptually based rules of pattern matching Most existing image database retrieval systems that use color and texture as visual primitives, expect the user to attach weights to the features, combining them into a single score. In our system we use a hierarchy of rules to combine color and texture without any human intervention.
b) While multidimensional scaling and clustering techniques have been used before to understand how people judge similarity, we are not aware of any work that uses these algorithms for understanding the perception of color patterns.
c) Further, in our system we go beyond discovering the intrinsic dimensions of pattern matching. We have discovered the perceptual criteria underlying the dimensions and have implemented perceptually based image processing algorithms to accomplish the retrieval along human dimensions.
d) The color codebook design is new. Although we are taking the usual approach based on the quantization of the Lab space, the actual implementation of the color cone with different luminance planes is novel. The color distance metric is also new.
e) We have proposed and implemented a new distance metric for texture matching that is better matched to humans' perception of color patterns.
f) Last but not the least, we have built a real end to end working system that has been tested on many different image databases from different application domains to verify the validity of our approach. These results confirm the robustness of our techniques and algorithms.