My research interests and accomplishments can be broadly classified into the following categories:

(A) CAD Model based Machine Vision

Summary: My research in CAD Model based Machine Vision has centered around the design and analysis of algorithms for the recognition and localization of three dimensional objects from range and intensity images. I have designed surface matching algorithms [8] and recognition/localization algorithms based on the Generalized Hough Transform (GHT) [7]. I have investigated hypergraph based representation schemes and designed efficient algorithms based on hypergraph monomorphism for three dimensional object recognition and localization [2]. I have investigated means of improving the robustness and accuracy of range image segmentation algorithms by an appropriate combination of edge- and surface based segmentation approaches [6]. I have also explored means by which the various stages of range image understanding viz., segmentation, feature extraction and recognition and localization can be synergistically integrated in a range image understanding system [4,11].
    Along more theoretical lines, I have been interested in analyzing the sensitivity of recognition/localization algorithms to errors in segmentation and feature extraction [9]. In particular, I have studied the impact of qualitative feature labeling on the performance of the GHT [5]. Qualitative feature labeling was shown to result in the formulation of a weighted GHT (WGHT) wherein the weights are looked upon as fuzzy membership values for the fuzzy sets defined by the qualitative feature labels [3]. The WGHT was shown both analytically and experimentally to perform better than the GHT [3]. I have also addressed issues concerning knowledge representation and control in CAD model based machine vision systems.  In particular, the modeling of model based machine vision systems as coupled systems (i.e., knowledge based systems in which symbolic and numerical computing are integrated) in an object oriented representation framework was addressed in  [39,40]. I am currently exploring issues concerning the design of hierarchical indexing/hashing structures for CAD model based vision using object models represented as attributed relational hypergraphs.

(B) Parallel Processing for Computer Vision

Summary: My research in parallel processing for Computer Vision is focused on issues concerning the parallelization of recognition and localization algorithms on prototypical SIMD and MIMD multiprocessor architectures as well as special purpose architectures. I have addressed issues concerning parallelization of three-dimensional object recognition and localization algorithms on a fine-grained SIMD architecture such as the Connection Machine CM-2 [18] and on a coarse grained MIMD architecture such as the Intel iPSC hypercube [16,17]and a PVM based cluster of workstations. I have also investigated special purpose architectures for computer vision and the mapping of computer vision algorithms on these architectures. In collaboration with two colleagues, a novel architecture was proposed and designed, which was termed as the Reconfigurable Multi-Ring Network (RMRN). The RMRN has been shown to be a highly efficient, scalable, cost effective and physically compact multiprocessor system suitable for active robot vision on autonomous or dexterous robotic platforms [24]. The theoretical properties of the RMRN were rigorously proved in [20,21]. Procedural primitives for data broadcast, data circulation, sort, data concentrate, data accumulate and circular shift were designed and analyzed in  [23]. These procedural primitives were used as building blocks for parallel algorithms for low- and intermediate level vision such as the FFT, convolution and template matching [23], stereo correlation [24]and the Hough Transform [19,20,26]. The architecture was shown to be well suited for problems in machine and robot vision [24,27]. On the theoretical side, I am currently investigating quantitative performance criteria for the evaluation of parallel and distributed recognition and localization algorithms on prototypical multiprocessor architectures and special purpose multiprocessor architectures such as the RMRN.

(C) Evolutionary Computation, Stochastic Optimization and Neural Networks for Low level Vision

Summary: My current research interests in low level vision are focused on the design and analysis of stochastic optimization techniques for low level vision problems such as edge detection, Gestalt clustering, image segmentation and surface reconstruction. Evolutionary and stochastic optimization techniques such as genetic algorithms, simulated annealing, microcanonical annealing and the random cost algorithm have been investigated in this context. The research thus far has resulted in the design of an edge detection technique using a genetic algorithm (GA) [33,34] and evolutionary algorithms for image segmentation [35]and figure-ground separation [36,37]. The research in  [35] and  [36] has resulted in the formulation and implementation of novel hybrid stochastic optimization algorithms that combine the positive aspects of stochastic hill climbing and evolutionary computation while alleviating their individual shortcomings.
    I am also investigating neural networks and multiscale stochastic optimization algorithms in the context of low level vision. The neural networks of specific interest are stochastic Hopfield networks, Boltzmann networks and Self Organizing Feature Maps. I am particularly interested in the design of multiscale or hierarchical versions of the aforementioned neural networks. The research thus far has resulted in the design of a Multi-Layer Self-Organizing Feature Map (MLSOFM) for image segmentation [28]-[32]. The MLSOFM combines the ideas of and  with those of image segmentation. It is distinctly different from previous approaches to image segmentation using neural networks in that it naturally alleviates the problems of under segmentation and over segmentation endemic to most image segmentation algorithms. The MLSOFM has proved successful in multiscale segmentation of intensity, range and multispectral magnetic resonance (MR) images. Multiscale versions of stochastic Hopfield networks and Boltzmann networks are also being investigated.

(D) Computer Vision and Parallel Processing Applications

Summary: I have also investigated various applications of computer vision algorithms to practical problems. As a co-principal investigator on a USDA funded collaborative project with the School of Forestry at the University of Georgia, I have dealt with the processing and analysis of cross-sectional CT images of log samples using machine vision algorithms [13]-[15]. The goal  is to detect and classify the internal log defects and render a 3-D reconstruction of the log that clearly shows its internal defects. The knowledge of the internal defects is used to formulate an optimal lumber production strategy that maximizes the yield and grade of the resulting lumber while minimizing wastage.
    I have also applied parallel processing, computer vision and image processing techniques to problems in computational biology and biomedicine. As a principal investigator on a USDA funded collaborative project with the Department of Genetics at the University of Georgia, I have examined problems related to chromosome reconstruction or physical mapping from short and possibly noisy (error containing) DNA fragments. The problem was modeled as one of signal/image reconstruction for which a optimization algorithms based on simulated annealing and microcanonical annealing have been designed and implemented on prototypical MIMD and SIMD architectures such as the Intel iPSC hypercube [42] and the MasPar MP-2 [44] and on a PVM based cluster of workstations. As a co-principal investigator on an NSF funded collaborative project with the Applied Genetics Technology Center at the University of Georgia, I am investigating algorithms for analysis of DNA microarray images. The goal of this project is to quantify gene expression, detect and quantify clusters of gene expression values arising from homologous (similar) genes and track the changes in cluster characteristics over time using algorithms from image morphology.
    In collaboration with researchers at the Medical College of Georgia, I have investigated parallel algorithms for entropy computation of experimental heart rate and electrocardiac potential (EKG) data. Heart rate entropy has been shown to be indicative of cardiovascular health but entropy computation has proved computationally intensive even for modest size data sets. Data parallel implementations on the  MasPar MP-2 [48] and a PVM based cluster of workstations [51] has yielded impressive speedups and shown the viability of using parallel computing for real time monitoring of cardiovascular activity, especially during surgery. This research presents a novel and challenging applications area for design and development of parallel algorithms.

(E) Content based Retrieval in Visual Information Systems

Summary: Recently, I have been investigating issues related to organization and content based retrieval of video and image data in visual information systems. The approach taken is one based on extraction of content based metadata from the underlying image/video data. The ultimate goal is to allow the user to pose queries using high level metadata that encapsulates the semantics of the underlying problem/application domain. Current work deals with metadata extraction from image and video data with emphasis on the direct processing of compressed images (JPEG) and compressed video streams (MPEG) [49,50].  In particular, a motion based algorithm for the parsing of compressed video was proposed and implemented in  and an integrated video parsing algorithm that combined motion based, luminance based and chrominance based information was proposed and implemented in  [50]. Both algorithms were capable of processing video data in real time (at rates in excess of 30 frames/sec) with the integrated video parsing exhibiting superior results in terms of miss rate and false alarm rate. Generation of indexing/hashing structures for efficient content based retrieval is also being investigated. The long term goal of this research is to permit integrated access to multimedia data which includes video, image, text and audio data.
 

Each of the aforementioned categories are elaborated upon in the following sections.

(A) CAD Model based Machine Vision

My research in this area has centered around design and analysis of algorithms for the recognition and localization of three dimensional objects from range and intensity images.
As part of my doctoral research, I developed Hough Transform based algorithms for matching surfaces embedded in 3-D space [8]. Subsequently, I generalized these surface matching algorithms for the purpose of recognition and localization of three dimensional rigid objects composed of curved quadric surfaces from range images [7]. These recognition and localization algorithms were based on the generalized Hough Transform and were found to be robust in that they were capable of recognizing and localizing three dimensional objects in range images that contained multiple objects with instances of partial occlusion [7].
    While on the faculty of the Department of Computer Science at the University of Georgia, I  continued to build on my previous research in the design and analysis of recognition and localization algorithms for model based machine vision. My earlier algorithms based on the generalized Hough Transform [7] were computationally intensive. In an effort to address the combinatorial complexity of object recognition and localization in multiple object scenes with partial occlusion, I investigated hypergraph based representation schemes for rigid 3-D objects composed of curved quadric surfaces and recognition/localization algorithms based on hypergraph monomorphism [2]. The hypergraph representation presented in  [2] was viewpoint independent resulting in  substantial memory savings for the object model database. The resulting hypergraph monomorphism algorithm integrated both relational constraints and the rigid pose constraint and had a low polynomial order complexity (O(n²) where n is the number of scene features) even in multiple object scenes with partial occlusion as compared to the worst case exponential complexity of straightforward graph monomorphism algorithms. I also designed an algorithm for incrementally constructing the hypergraph representation of an object model from range images of the object from different viewpoints. The hypergraph monomorphism and the hypergraph construction algorithms were designed to correct errors in the initial segmentation of the range image [2].
    I have investigated ways of improving the robustness and accuracy of existing range image segmentation techniques. Most conventional range image segmentation algorithms could be classified as either surface based or edge based, depending on whether they extract the parameters of the underlying surface or the surface discontinuities, respectively. The primary drawback of edge based segmentation techniques is the inevitable fragmentation of the edges in the presence of noise. Surface based segmentation techniques, on the other hand, can result in over segmentation or under segmentation of the image. In collaboration with my graduate student, I designed a range image segmentation algorithm that integrated both surface and edge information [6]. In this algorithm, the geometric parameters of the surface regions are used to hypothesize the presence of a surface discontinuity and accurately compute its parametric form. The presence of the surface discontinuity in the image is used to confirm the hypothesis whereas its absence is used as a cue to merge the appropriate regions. Experiments on range images demonstrated that the synergetic integration of surface and edge information results in a robust and accurate segmentation algorithm capable of alleviating the individual shortcomings of edge based and region based segmentation techniques [6].
    I have also investigated means by which the various stages in range image understanding, viz. segmentation, feature extraction, recognition and localization, could be synergistically integrated in a range image understanding system. Conventional approaches to range image understanding have treated these stages in isolation with a largely bottom up flow of control and data through the three stages.  Strictly bottom up approaches are fragile in the face of errors in segmentation due to noise and limitations on sensor resolution and accuracy. Synergetic interaction of these three stages is essential for an image understanding system to exhibit robust behavior [4].  In collaboration with my graduate student, I designed and implemented a range image understanding system that attempts to exploit the synergy between the various stages in the image understanding process [4,11]. The salient features of the range image understanding system were: (i) a synergetic combination of edge- and surface based segmentation processes that results in more accurate segmentation than would have been possible with either of them alone and (ii) the ability to correct errors made during segmentation in the recognition and localization stages. Experimental results on range images demonstrated the validity of our approach. An efficient algorithm for pose verification of hypothesized objects in the range image was also designed [10]. The pose verification algorithm used feature matching and cast the pose verification problem as one of optimal assignment (also known as the  Hungarian marriage problem in combinatorics). The pose verification algorithm was found to be far more robust to small errors in the computed pose when compared with pose verification algorithms  that relied on straightforward depth comparison.
    Along more theoretical lines, I have analyzed the sensitivity of recognition and localization algorithms to errors in segmentation and feature extraction. In  [9], I analyzed  the sensitivity of the generalized Hough Transform (GHT) to errors in segmentation and feature extraction in the context of 3-D object recognition and localization. The 3-D objects under consideration were rigid objects composed of piece wise smooth quadric surfaces. The features were  resulting from extended features such as axes of symmetry, centroids etc. derived from the piece wise smooth quadric surfaces. The sensitivity of the computed pose to errors in the angle of the dihedral feature junctions was analyzed. A redundant representation of the Hough space was seen to reduce the sensitivity of the computed pose to these errors. The effect of qualitative feature labeling (i.e., assigning qualitative attributes to scene features) on the robustness of the GHT was also analyzed [5]. Qualitative feature labeling was seen to result in a reduction in the search space of scene interpretation hypotheses and also the number of spurious interpretations explored by the GHT.
    Grimson and Huttenlocher  [12] have suggested two criteria by which the performance of the GHT can be judged: (i) the redundancy factor of the GHT i.e. the number of Hough buckets into which a computed transform value is fragmented due to the finite resolution of the sensor and  finite quantization of the Hough space and (ii) the probability of occurrence of spurious peaks of significant magnitude due to random accumulation of evidence in the Hough space. It is desirable that both the redundancy factor and the probability of occurrence of random spurious peaks of significant magnitude be as low as possible. The straightforward GHT, however, shows a high probability of spurious peaks of significant magnitude even for small values of the redundancy factor and small magnitude of the search space of scene interpretations. Qualitative labeling of scene features was shown to result in the formulation of a weighted Generalized Hough Transform (WGHT) where each match of a scene feature with a model feature was assigned a weight based on the qualitative attributes assigned to the scene feature. These weights were looked upon as membership function values for the fuzzy sets defined by these qualitative attributes. A fuzzy probabilistic model for the WGHT was formulated in . Analytical expressions for the redundancy factor and the probability of random accumulation of spurious votes  were derived for the WGHT using a statistical occupancy model and compared with the corresponding expressions for the straightforward GHT [3]. Experimental results on intensity and range images showed that the WGHT performed better than the conventional GHT in terms of the aforementioned criteria.
    I have also addressed issues related to knowledge representation and control in CAD model based vision systems. Most problems in CAD model based vision could be looked upon as a trade-off between the complexity of representation and the complexity of control (i.e., the constraint propagation/satisfaction technique used). The choice of representation granularity  (i.e., global features vs. local features) and constraint propagation/satisfaction technique greatly impacts the performance of the vision system.  Typical shortcomings of most CAD model based vision systems are:

1. Restriction to a single level of representation granularity
2. Use of constraint propagation techniques based on matching of features at a single level of representation granularity
3. Inflexible control strategies
4. Inadequate integration of numerical and symbolic processing.

(B) Parallel Processing for Computer Vision

My research interests in parallel processing for computer vision are largely focused on the parallelization of recognition and localization algorithms for 3-D machine vision. I have explored means of parallelizing the recognition and localization algorithms that I designed on prototypical SIMD and MIMD multiprocessor architectures. Recognition and localization algorithms based on the GHT [7] were found to be well suited for parallelization on a fine grained SIMD architecture such as the Connection Machine CM-2. In [18], issues on exploiting fine grained parallelism on the CM-2 at every stage of 3-D object recognition and localization such as segmentation, feature extraction matching, pose determination and pose verification were tackled. Experimental results on the CM-2 brought out the advantages of exploiting fine grained parallelism for 3-D machine vision using recognition and localization techniques based on the GHT. In  [16,17]parallelization of recognition and localization algorithms based on Interpretation Tree (I.T.) search on a coarse grained MIMD hypercube (Intel iPSC/2) was explored. Three strategies for mapping the I.T. search process on the MIMD hypercube were designed. The performance of the parallel I.T. search for each of these mapping strategies was analyzed in terms of parameters such as speed-up, processor utilization, interprocessor communication overhead and load sharing between processors. It was shown how the requirement for uniform load sharing leads to increased interprocessor communication overhead.
    In collaboration with my colleagues Dr. Arabnia and Dr. Smith in the Department of Computer Science at the University of Georgia, I have investigated special purpose architectures for computer vision and the mapping of computer vision algorithms on these architectures. The architecture that we proposed is termed as the Reconfigurable Multi-Ring Network (RMRN). In  [21,23] the properties of the RMRN architecture were investigated and rigorously proved. Briefly, the RMRN_n consists of 2ⁿ processors connected in a ring, but with the capability for reconfiguration, under software control, into R rings of D processors each, with corresponding elements of each ring linked in a pipelined manner, for any R and D whose product is 2ⁿ. The total number of processors could be any composite number, but using the natural choice of a power of 2 maximizes the number of possible configurations and also lends itself to ease of mapping algorithms onto the RMRN. Some of the salient properties of the RMRN are:

(i)   All 2-D mesh topologies of size 2ⁱ x 2^j are subsets of the RMRN_n where i + j = n. This enables algorithms for 2-D mesh/toroidal architectures of various sizes to be mapped onto the RMRN in O(1) time.

(ii)  The n-cube (i.e. a hypercube with N = 2ⁿ processors) can embed all possible configurations of the RMRN_n (though not simultaneously). This enables the hypercube to simulate the behavior and function of the RMRN.

(iii)  Any algorithm which uses the communication links along a single dimension of the  at any given point in time can be mapped to the RMRN_n in O(1) time. This enables an important and fairly wide class of algorithms for the  to be mapped very efficiently onto the RMRN_n.

(iv)  In any configuration the RMRN can be recursively decomposed into sub configurations with the connectivity pattern preserved within each sub configuration. Thus the RMRN_n can be recursively decomposed in a manner similar to the  n-cube.

(v)   The RMRN is highly scalable since the degree of connectivity of each processor is fixed. This ensures that the number of interprocessor communication links  scales as O(N) with network size whereas the diameter of the RMRN scales as O(log₂ N) with network size.

    Procedural primitives for data broadcast, data circulation, sort, data concentrate, data accumulate and circular shift have been designed and analyzed [23]. These procedural primitives have been used as building blocks for parallel algorithms for low- and intermediate level vision such as the FFT, convolution and template matching [23] and the Hough Transform [19,26]. The architecture is well suited for problems in machine and robot vision [24,27]. Efforts are currently underway towards building the hardware for the RMRN using custom VLSI. Complex problems in intermediate- and high level vision such as binocular stereo, surface reconstruction, image segmentation and object recognition are also being considered along with other problems in robotics such as path and trajectory planning and motion control. For the compute bound problems in active robot vision, the RMRN promises  to offer an efficient, inexpensive, scalable and physically compact multiprocessor system that could be used on mobile and dexterous robotic platforms [24].
    On the theoretical side, I am currently investigating quantitative performance criteria for the evaluation of parallel and dist ributed recognition and localization algorithms
on prototypical multiprocessor architectures and special multiprocessor architectures such as the RMRN. A rigorous analysis of the impact of architectural design parameters such as processor bandwidth, memory bandwidth, interprocessor  communication bandwidth, interconnection topology and synchronization bandwidth on the performance of the parallel/distributed recognition and localization algorithms is currently underway. A quantitative analysis of the performance of the parallel/distributed recognition and localization algorithms in terms of parallel processing parameters such as speedup, load distribution and load balancing overhead, search overhead, synchronization overhead, interprocessor communication overhead, efficiency of parallelism and scalability is being attempted. Quantitative relations between these parallel processing parameters and physical, statistical and geometrical scene parameters such as finite image resolution, scene clutter, gray level quantization, quantization geometry, sensor noise and errors introduced by the feature extraction process are being studied.

(C) Evolutionary Computation, Stochastic Optimization and Neural Networks for Low level Vision

My current research interests in low level vision are focused on the design and analysis of evolutionary and stochastic optimization algorithms for low level vision problems such as edge detection, Gestalt clustering, image segmentation and surface reconstruction. The evolutionary algorithms under investigation include the various variants of the genetic algorithm (GA) whereas the stochastic optimization algorithms under investigation include simulated annealing, microcanonical annealing and the random cost algorithm. The research thus far has resulted in GA based techniques for edge detection [33,34], image segmentation [35]and figure-ground separation [36].
    The GA is an evolutionary search/optimization technique, the conceptual basis of which lies in Darwin's , better known as . The GA repres ents each candidate solution as a chromosome and traverses the search space by constructing better chromosomes (solutions) from an existing population of chromosomes using operators such as selection, crossover and mutation that mimic the process of natural evolution. Although GA's have found successful applications in a variety of problem domains, their application to vision problems has been somewhat limited.
    The GA based edge detection algorithm in [33] treats candidate edge configurations as two-dimensional chromosomes with assigned fitness values. In [34]crossover, mutation and meta-level operators for the GA are designed which enable exploration of better edge configurations using a population of existing edge configurations. The GA with various combinations of meta-level operators was tested on synthetic and real intensity images. The performance of the GA was compared both qualitatively and quantitatively with hill climbing based and simulated annealing based edge detection approaches. The GA based edge detection technique was shown to perform very well in terms of robustness to noise, rate of convergence and quality of the final edge image [33]. The GA produced edge images comparable in quality to those produced by simulated annealing but exhibited a faster rate of convergence. Although hill climbing was seen to exhibit a faster rate of convergence than the GA or simulated annealing, it did not exhibit the same robustness to noise, resulting in a greater degradation of the final edge image with increased noise levels.
    In [35] the GA based edge detection approach was extended to the problem of image segmentation. A suitable fitness function to quantify the quality of the segmented image and the corresponding GA operators were designed and implemented. In  [36]the GA was investigated in the context of figure-ground separation. The figure-ground separation problem was modeled as an Ising system from quantum physics and the fitness function for the GA was derived from the Ising energy function. Although GA's are inherently parallel, premature convergence to local minima and the need to maintain large population sizes were seen to present significant problems. Stochastic annealing techniques, on the other hand, are computationally intensive and not as easily parallelizable. But they guarantee asymptotic convergence to a global minimum if certain conditions on the annealing schedule are satisfied. In  [35,36]evolutionary stochastic optimization algorithms that combine the positive aspects of stochastic annealing and evolutionary computation while alleviating the individual shortcomings of both were proposed and implemented. The evolutionary stochastic optimization algorithms were seen to outperform their pure evolutionary and pure stochastic annealing counterparts. Hierarchical or multiscale evolutionary and stochastic optimization techniques in the context of low level vision problems are currently being investigated.
    I have also investigated neural implementations of low level vision algorithms. The neural networks of specific interest are stochastic Hopfield networks, Boltzmann networks and Self Organizing Feature Maps. I am particularly interested in the design of multiscale or hierarchical versions of the aforementioned neural networks. The research thus far has resulted in the design of a Multi-Layer Self-Organizing Feature Map (MLSOFM) for image segmentation [28]-[32]. One of the shortcomings of the conventional single layer Self-Organizing Feature Map (SOFM) is that the number of neural units in the feature map has to be close to the number of regions in the final segmentation. Since, one typically does not know the number of regions in the final segmentation  a priori, the SOFM often yields an under segmented or over segmented image. The MLSOFM consists of multiple SOFM layers organized in a pyramidal fashion. The problem of image segmentation is formulated as one of vector quantization and mapped onto the MLSOFM. The MLSOFM combines the ideas of and  with those of image segmentation. It is distinctly different from previous approaches to image segmentation using neural networks. The MLSOFM generates an  which represents the segmentation of the image at multiple scales of abstraction. Traversal of the abstraction tree results in the desired segmented image. Since the neural units in each layer of the MLSOFM do not have to be specified a priori, the MLSOFM can be seen to alleviate a major shortcoming of the SOFM in the context of image segmentation. The MLSOFM has been successfully applied to the segmentation of intensity, range and multi-spectral magnetic resonance (MR) images. The MLSOFM is currently being extended for use in hierarchical image coding and semantics preserving compression of images [29,32]. Also, multiscale versions of stochastic Hopfield networks and Boltzmann networks are being explored for the purpose of Gestalt clustering and image segmentation.

(D) Computer Vision and Parallel Processing Applications

I have also explored practical applications of computer vision and parallel processing. As a co-principal investigator on a USDA funded collaborative project with the School of Forestry at the University of Georgia, I have dealt with the processing and analysis of cross-sectional CT images of log samples using machine vision techniques [13,14,15]. These CT images are analyzed for the detection and localization of defects such as holes, knots, cracks, wood decay, bark and pitch pockets etc. The nature of the defects and the ring structure deduced from each CT image are used to construct a 3-D model of the log sample. The 3-D model is used to simulate various sawing patterns and to determine the optimal lumber processing strategy that would maximize the resulting lumber yield. This would enable the saw mill to maximize the grade and yield of the produced lumber, minimize wood wastage and conserve valuable forest resources. The research in this project thus far has resulted in the internal defect classification and 3-D reconstruction of logs of premium hardwood species [13,15]. Initial simulations of algorithms for optimal lumber processing strategy determination have yielded very encouraging results [14]. Current research is aimed at further refinement of algorithms for internal defect detection and localization and for optimal lumber processing strategy determination.  The role of parallel computing in real time CT scanning of logs and for subsequent image analysis and optimal lumber processing strategy determination is also being investigated.
    I have also investigated applications of computer vision and parallel computing to problems in computational biology and biomedicine. As the principal investigator on a USDA funded collaborative project with the Department of Genetics at the University of Georgia, I have investigated algorithms for reconstruction of chromosomes from short and possibly noisy (i.e., error containing) DNA fragments. The problem is modeled as one of image/signal reconstruction in the presence of noise. A likelihood function is defined for the relative ordering of the DNA fragments and their pair wise spacing in the presence of noise. A maximum likelihood estimation (MLE) procedure that recovers the relative ordering of the DNA fragments and their pair wise spacing is then defined. The MLE procedure is shown to be computationally intensive and intractable involving both, combinatorial and continuous optimization, thus calling for the use of parallel computing. An earlier (and simpler) version of the chromosome reconstruction problem was modeled along the classical Traveling Salesman Problem (TSP) which is known to be intractable. Parallel implementations of chromosome reconstruction algorithms based on the MLE approach and the TSP approach on an SIMD architecture (MasPar MP-2), MIMD architecture (Intel iPSC/860) and a PVM based cluster of workstations was seen to yield very good speedups. As co-principal investigator on an NSF funded collaborative project with the Applied Genetics Technology Center at the University of Georgia, I am currently investigating algorithms for the analysis of DNA microarray images used for the measurement of gene expression. The goals of this project are to detect and characterize clusters of gene expression patterns when multiple genes are jointly expressed in response to a stimulus, detect differential gene expression patterns using morphological operators, detect and track temporal patterns in gene expression values and characterize background noise due to cross-hybridizations.
     In collaboration with researchers at the Medical College of Georgia, I have investigated parallel algorithms for entropy computation of heart rate and electrocardiac potential (EKG) data. The short term goal of the research is to use the computed entropy as a retrospective diagnostic tool whereas the long term goal is on-line entropy computation during surgery and recovery. A wide variety of dynamic systems such as the human heart, which were earlier considered stochastic or periodic have been re-classified as chaotic. Chaotic systems are deterministic, not stochastic. Entropy is a diagnostic statistic that characterizes the level of chaos within a dynamic system. Zero entropy indicates a periodic system, very high positive values of entropy (approaching infinity) indicates a random system and finite positive values of entropy indicates a chaotic system. The research focused on the parallel computation of Kolmogorov entropy using the algorithm of Grassberger and Procaccia. Entropy computation has proved computationally intensive even for modest size data sets. Data parallel implementations on an SIMD machine (MasPar MP-2) [47,48] and control parallel implementations [51]on a PVM based cluster of workstations gave impressive speedups. The current implementations, though suitable for off-line analysis of electrocardiac data, fall short of the requirements for real time cardiovascular monitoring. This research presents a novel and challenging applications area for design and development of parallel algorithms. An immediate application of the research is to aid the anesthesiologist in assessing risk associated with recovery of ambulatory surgery patients using EKG data. The proper analysis of heart rate and EKG data would greatly reduce unnecessary hospitalization costs and also potential risks arising from imprudent patient discharges. Future research will look into design of special purpose hardware in the form of application specific integrated circuits (ASICs) for the real time computation of heart rate entropy.
 

(E) Content based Retrieval in Visual Information Systems

Some of my more recent research deals with various issues related to the organization and content based retrieval of video and image data in visual information systems. This research is a crucial component in providing integrated high level access to multimedia information. The current research has focused on automatic parsing of video data for extraction of content based metadata. The content based metadata represents the image/video contents at a higher level of abstraction and can be used to provide an indexing mechanism into an image/video database.
    The video parsing algorithms developed in [49,50]detect shot boundaries, special cinematographic effects such as fades, dissolves and image morphs, predominant camera motion such as zoom and pan, and predominant object motion such as translation and rotation. Both pixel based and feature based approaches have been investigated with an emphasis on direct analysis of compressed video data (MPEG). In [49] a motion based video parsing algorithm was proposed and implemented. The algorithm was shown to be fairly robust in its detection of shot boundaries, fades and dissolves. On a 200MHz SUN UltraSparc-1 workstation, a C++ implementation of the video parsing algorithm was shown to be capable of processing video streams at a rate of 60 frames/sec, making it suitable for real time (30 frames/sec) video parsing applications. In  [50] a video parsing algorithm that integrated luminance based, chrominance based and motion based information was proposed and implemented. In addition to shot boundaries, fades  and dissolves, the algorithm was also capable of detecting pans, zooms and predominant object motion. The algorithm was seen to be more robust than those that used luminance, chrominance or motion information in isolation. In a quantitative study, the integrated video parsing algorithm was shown to outperform strict luminance based, chrominance based and motion based  video parsing algorithms in terms of percentage of misses and percentage of false alarms. The processing rate of the integrated video parsing algorithm was 48 frames/sec on a 200MHz SUN UltraSparc-1 workstation (20% slower than the strict motion based algorithm) but still suitable for real time applications. The immediate goal of this project is to formulate and implement representation schemes (in the form of key frames and mosaics) for distinct video shots detected by the video parsing process. These representations will be used to provide an indexing mechanism to an image/video database. The long term goal is to support high level integrated access to multimedia data which may include text, video, images and audio data.
 

References

[1]    M. Suk and S.M. Bhandarkar, Three-Dimenstional Object Recognition from Range images , Springer-Verlag Inc., Tokyo, Japan, 1992.

[2]    S.M. Bhandarkar, A Surface Feature Attributed Hypergraph Representation for 3-D Object Recognition, Intl. Journal of Pattern Recognition and Artificial Intelligence , Vol. 9, No. 6,  pp. 869-909.

[3]    S.M. Bhandarkar, A Fuzzy Probabilistic Model for the Generalized Hough Transform, IEEE Trans. Systems, Man and Cybernetics , Vol. 24, No. 5, May 1994, pp. 745-759.

[4]    S.M. Bhandarkar and A. Siebert, INTEGRA - An Integrated Approach to Range Image Understanding, Intl. Journal of Pattern Recognition and Artificial Intelligence, Vol. 6. No. 5, Dec. 1992, pp. 913-954.

[5]    S.M. Bhandarkar and M. Suk, Qualitative Features and the Generalized Hough Transform, Pattern Recognition,  Vol. 25, No. 9, 1992, pp. 987-1006.

[6]    S.M. Bhandarkar and A. Siebert, Integrating Edge and Surface Information for Range Image Segmentation, Pattern Recognition, Vol. 25, No. 9, 1992, 947-962.

[7]    S.M. Bhandarkar and M. Suk, Recognition and Localization of Curved Objects,  Machine Vision and Applications Vol. 4, 1991, pp. 15-31.

[8]    S.M. Bhandarkar and M. Suk, Hough Clustering Technique for Surface Matching, in  Proc. IAPR Intl. Workshop on Computer Vision, Oct. 1988, Tokyo, Japan, pp. 82-85.

[9]    S.M. Bhandarkar and M. Suk, Sensitivity Analysis for Matching and Pose Computation Using Dihedral Junctions, Pattern Recognition, Vol. 24, No. 6, 1991, pp. 505-513.

[10]  S.M. Bhandarkar and M. Suk, Pose Verification as an Optimal Assignment Problem,  Pattern Recognition Letters, Vol. 12, 1991, pp. 45-53.

[11]  S. M. Bhandarkar and A. Siebert, INTEGRA - An Integrated Approach to Range Image Understanding, Proc. Intl. Conference on Pattern Recognition, The Hague, Netherlands, August, 31 - September 4, 1992, Vol. A, pp. 624-627.

[12]  W.E.L. Grimson and D. P. Huttenlocher, On the Sensitivity of the Hough Transform for Object Recognition, IEEE Trans. Pattern Recognition and Machine Intelligence, Vol. 12, No. 3, March 1990, pp.  255-274.

[13]   S.M. Bhandarkar, T. Faust and M. Tang, A System for Detection of Internal Log Defects by Computer Analysis of Axial CT Images, Proc. IEEE Intl. Wkshp. Appl. Computer Vision,  Sarasota, FL, Dec. 2-4, 1996, pp. 258-263.

[14]   S.M. Bhandarkar, T.D. Faust and M. Tang, A Computer Vision System for Lumber Production Planning, Proc. IEEE Intl. Wkshp. Appl. Computer Vision, Princeton, NJ, October 19-21, 1998, pp. 134-139.

[15]   S.M. Bhandarkar, T.D. Faust and M. Tang, CATALOG: A System for Detection and Rendering of Internal Log Defects Using Computer Tomography, Machine Vision and Applications, to appear.

[16]   S. M. Bhandarkar, Parallelizing Object Recognition on the Hypercube, Pattern Recognition Letters, Vol. 13, 1992, pp. 433-441.

[17]   S.M. Bhandarkar and L.C. Sung, Object Recognition on the Hypercube, Proc. IEEE Intl. Conf. on Systems, Man and Cybernetics, Charlottesville, VA, October 1991, pp. 625-630.

[18]   S.M. Bhandarkar, R. Shankar and M. Suk, Exploiting Parallelism in 3-D Object Recognition using the Connection Machine, Robotics and Autonomous Systems ,Vol. 8, 1991, pp. 291-309.

[19]   S.M. Bhandarkar and H.R. Arabnia, The Hough Transform on a Multi-Ring Reconfigurable Network, Journal of Parallel and Distributed Computing, Vol. 24, No. 1,  January 1995, pp. 107-114.

[20]   S.M. Bhandarkar and H.R. Arabnia, Parallel Computer Vision on a  Reconfigurable Multiprocessor Network, IEEE Trans. on Parallel and Distributed Systems,Vol. 8, No. 3, March, 1997, pp. 292-309.

[21]   S.M. Bhandarkar and H.R. Arabnia, A Reconfigurable 1-Factor Hypercubic Embedding Network - Theoretical Properties and Algorithms , Parallel Computing, Vol. 21, No. 11, Nov. 1995, pp.  1783-1806.

[22]   H.R. Arabnia and S.M. Bhandarkar, Parallel Stereocorrelation on a Reconfigurable Multi-Ring Network, Intl. Journal  Supercomputing, Vol. 10, 1996, pp. 243-269.

[23]   S.M. Bhandarkar, H.R. Arabnia and J.W. Smith, A Novel Reconfigurable Architecture for Image Processing and Computer Vision, Intl. Journal of Pattern Recognition and Artificial Intelligence,  Vol. 9, No. 2, 1995, pp. 201-229.

[24]   S.M. Bhandarkar and H.R. Arabnia, A Novel Reconfigurable Multiprocessor for Robot Vision, Proc. IEEE Intl. Conf. Robotics and Automation , San Diego, CA, May 1994, pp. 2857- 2862.

[25]   S.M. Bhandarkar and H.R. Arabnia, Parallelization of Computer Vision Algorithms on a Novel Reconfigurable Multiprocessor Network ,Proc. of 12th Intl. Conf. on Pattern Recognition , Oct. 1994, Jerusalem, Israel, Vol. 3, pp. 240-244.

[26]   S.M. Bhandarkar and H.R. Arabnia, A Multi-Ring Reconfigurable Multiprocessor Network for Computer Vision, Proc. Intl. Workshop on Computer Architectures for Machine Perception, New Orleans, LA, December 1993, pp.  180-190.

[27]   S.M. Bhandarkar and H.R. Arabnia, Parallel 3-D Object Recognition, Proc. IEEE Intl. Conf. on Signal Processing ,Beijing, China, October 1993, Vol. II, pp.  1022-1026.

[28]   J. Koh, M. Suk and S.M. Bhandarkar, A Multi-layer Self-Organizing Feature Map For Range Image Segmentation, Neural Networks , Vol. 8, No. 1, 1995, pp. 67-86.

[29]   J. Koh, M. Suk and S.M. Bhandarkar, A Multi-layer Kohonen's Self-Organizing Feature Map For Range Image Segmentation, Proc. Intl. Conf. on Neural Networks,San Francisco, CA, April 1993, pp. 1270-1275.

[30]   J. Koh, M. Suk and S.M. Bhandarkar, A Self-Organizing Neural Network for Hierarchical Range Image Segmentation, Proc. IEEE Intl. Conf. on Robotics and Automation,Atlanta, GA, May 1993, pp. 758-763.

[31]   S.M. Bhandarkar, J. Koh and M. Suk, Multi-scale Image Segmentation using a Hierarchical Self-Organizing Feature Map, Neurocomputing, Vol. 14, No. 3, 1997, pp. 241-272.

[32]   S.M. Bhandarkar, J. Koh and M. Suk, A Hierarchical Neural Network and Its Application to Image Segmentation, invited paper in Intl. Journal on Mathematics and Computers in Simulation  , Vol. 41, Nos. 3-4, 1996, pp. 337--355.

[33]   S.M. Bhandarkar, Y. Zhang and W.D. Potter, An Edge Detection Technique Using Genetic Algorithm based Optimization, Pattern Recognition , Vol. 27, No. 9, Sept. 1994, pp. 1159-1180.

[34]   S.M. Bhandarkar, Y. Zhang and W.D. Potter, A Genetic Algorithm based Edge Detection Technique, Proc. Intl. Joint Conf. on Neural Networks, Nagoya, Japan, October 1993, pp. 2995-2999.

[35]   S.M. Bhandarkar and H. Zhang, Image Segmentation Using Evolutionary Computation, IEEE Trans. Evolutionary Computation, Vol. 3, No. 1, April 1999, pp. 1--21.

[36]   S.M. Bhandarkar and X. Zeng, Evolutionary Approaches to Figure-Ground Separation, Journal of Applied Intelligence, Vol. 11, No. 2, 1999, in press.

[37]   S.M. Bhandarkar and X. Zeng,  Figure-Ground Separation: A Case Study in Energy Minimization via Evolutionary Computing Proc. IAPR Intl. Workshop Energy Minimization Methods in Computer Vision, Venice, Italy, May 21-23, 1997, pp. 375-390.

[38]   S.M. Bhandarkar and X. Zeng, Evolutionary Computation for Figure-Ground Separation, Proc. Intl. Conf. on Neural Networks , June 9-12, 1997, Houston, TX, Vol. 3, pp. 1673-16 78.

[39]   S.M. Bhandarkar and M. Suk, Coupling Symbolic and Numerical Computing in Knowledge based Systems, Proc. Intl. World Congress on Expert Systems ,Orlando, FL, December, 1991, pp. 1483-1490.

[40]   S.M. Bhandarkar and M. Suk, Computer Vision Systems as Coupled Systems, Proc. SPIE Conf. Applications of Artificial Intelligence VIII , Orlando, FL, April 1990, Vol. 1293, pp.  45-54.

[41]   S.M. Bhandarkar, S. Chirravuri, S. Machaka and J. Arnold, Parallel Computing for Chromosome Reconstruction via Ordering of DNA Sequences, Parallel Computing, Vol. 24, No. 8, 1998, pp. 1177-1204..

[42]   S.M. Bhandarkar, Parallel Processing for Chromosome Reconstruction from Physical Maps-A Case Study of MIMD Parallelism on the Hypercube ,Parallel Algorithms and Applications,  Vol. 12, 1997, pp. 231--252.

[43]   S.M. Bhandarkar and S. Machaka, Chromosome Reconstruction from Physical Maps Using a Cluster of Workstations, Journal of Supercomputing, Vol. 11, No. 1, 1997, pp. 61-86.

[44]   S.M. Bhandarkar and S. Chirravuri, A Study of Massively Parallel Simulated Annealing Algorithms for Chromosome Reconstruction via Clone Ordering, Parallel Algorithms and Applications ,Vol. 1996, pp. 67-89.

[45]   S.M. Bhandarkar, S. Machaka, S.S. Shete and J. Arnold, Parallel Computation of a Maximum Likelihood Estimator for Physical Mapping of Chromosomes, Journal of Parallel and Distributed Computing, under review.

[46]   P. Grassberger and I. Procaccia, Estimation of the Kolmogorov Entropy from a Chaotic Signal, Physical Review, Vol. 28, 1983, pp. 2591-2593.

[47]   S. Chirravuri, S.M. Bhandarkar and D. Whitmire, A Massively Parallel Algorithm for K2 Entropy Computation: Case Studies of Model Systems and  Data, Intl. Journal of Supercomputing Appl. and High Perf. Computing , Vol. 9, No. 4, 1995, pp. 296-311.

[48]   S.M. Bhandarkar, S. Chirravuri, and D. Whitmire, Analysis of Heart Rate Variability on a Massively Parallel Processor, Proc. Intl. Conf. Parallel Processing, Bloomingdale, IL, Aug. 12-16, 1996, Vol. 2, pp. 166-169.

[49]   S.M. Bhandarkar and A.A. Khombadia, Motion based Parsing of Compressed Video, Proc. IEEE Intl. Wkshp. Multimedia Database Mgmt. Systems , Dayton, Ohio, August 5-7, 1998, pp. 80-87.

[50]   S.M. Bhandarkar, Y.S. Warke and A. A. Khombadia, Integrated Parsing of Compressed Video, Proc. Intl. Conf. Visual Inf. Mgmt. Sys., Amsterdam, The Netherlands, June 2-4, 1999, pp. 269-276.

[51]   S.M. Bhandarkar, S. Chirravuri and S. Machaka, Cluster Computing for Biomedical Applications, in Cluster Computing: Theory and Applications, Prentice-Hall Inc., Upper Saddle River, NJ, June 1999, Chapter 29, pp. 604-624.