Segmentation and classification of range images

The recognition of objects in three-dimensional space is a desirable capability of a computer vision system. Range images, which directly measure 3-D surface coordinates of a scene, are well suited for this task. In this paper we report a procedure to detect connected planar, convex, and concave surfaces of 3-D objects. This is accomplished in three stages. The first stage segments the range image into ``surface patches' by a square error criterion clustering algorithm using surface points and associated surface normals. The second stage classifies these patches as planar, convex, or concave based on a non-parametric statistical test for trend, curvature values, and eigenvalue analysis. In the final stage, boundaries between adjacent surface patches are classified as crease or noncrease edges, and this information is used to merge compatible patches to produce reasonable faces of the object(s). This procedure has been successfully applied to a large number of real and synthetic images, four of which we present in this paper.     

Recovery of parametric models from range images: the case forsuperquadrics with global deformations

A method for recovery of compact volumetric models for shape representation of single-part objects in computer vision is introduced. The models are superquadrics with parametric deformations (bending, tapering, and cavity deformation). The input for the model recovery is three-dimensional range points. Model recovery is formulated as a least-squares minimization of a cost function for all range points belonging to a single part. During an iterative gradient descent minimization process, all model parameters are adjusted simultaneously, recovery position, orientation, size, and shape of the model, such that most of the given range points lie close to the model's surface. A specific solution among several acceptable solutions, where are all minima in the parameter space, can be reached by constraining the search to a part of the parameter space. The many shallow local minima in the parameter space are avoided as a solution by using a stochastic technique during minimization. Results using real range data show that the recovered models are stable and that the recovery procedure is fast     

Segmentation and adaptive assimilation for detail-preserving display of high-dynamic range images

Realistic display of high-dynamic range images is a difficult problem. Previous methods for high-dynamic range image display suffer from halo artifacts or are computationally expensive. We present a novel method for computing local adaptation luminance that can be used with several different visual adaptation-based tone-reproduction operators for displaying visually accurate high-dynamic range images. The method uses fast image segmentation, grouping, and graph operations to generate local adaptation luminance. Results on several images show excellent dynamic range compression, while preserving detail without the presence of halo artifacts. With adaptive assimilation, the method can be configured to bring out a high-dynamic range appearance in the display image. The method is efficient in terms of processor and memory use.     

Efficient search and verification for function based classification from real range images

In this work we propose a probabilistic model for generic object classification from raw range images. Our approach supports a validation process in which classes are verified using a functional class graph in which functional parts and their realization hypotheses are explored. The validation tree is efficiently searched. Some functional requirements are validated in a final procedure for more efficient separation of objects from non-objects. The search employs a knowledge repository mechanism that monotonically adds knowledge during the search and speeds up the classification process. Finally, we describe our implementation and present results of experiments on a database that comprises about 150 real raw range images of object instances from 10 classes.     

Segmentation of volumetric tissue images using constrained active contour models

In this article we describe an application of active contour model for the segmentation of 3D histo-pathological images. The 3D images of a thick tissue specimen are obtained as a stack of optical sections using confocal laser beam scanning microscope (CLSM). We have applied noise reduction and feature enhancement methods so that a smooth and slowly varying potential surface is obtained for proper convergence. To increase the capture range of the potential surface, we use a combination of distance potential and the diffused gradient potential as external forces. It has been shown that the region-based information obtained from low-level segmentation can be applied to reduce the adverse influence of the neighbouring nucleus having a strong boundary feature. We have also shown that, by increasing the axial resolution of the image stack, we can automatically propagate the optimum active contour of one image slice to its neighbouring image slices as an appropriate initial model. Results on images of prostate tissue section are presented.     

Segmentation based compression for graylevel images

This paper presents a segmentation based lossy image compression (SLIC) algorithm. The segmentation scheme (Biswas and Pal, Pattern Recog. Lett. 21 (2000)), entropy based and hierarchical in nature, provides sub-images of homogeneous regions. The compression algorithm encodes a graylevel image through global approximations of sub-images by 2-d Bezier-Bernstein polynomial along with corrections, if needed, over regions in sub-images by local approximation; contours by 1-d Bezier-Bernstein polynomial and texture, if present, by Huffman coding scheme using Hilbert scan on texture blocks. Order of the 2-d polynomials has been computed with the help of an image quality index (IQI). The proposed compression algorithm also examines the compression result by encoding contours through their approximation based on stretching of discrete circular arcs. Stretching is done by affine transformation. Compression results in both the cases have been compared with JPEG results. Attempts have been made to evaluate the quality of reconstructed images through a fidelity vector whose components are different objective measures.     

Theory of contact for geometric continuity of parametric curves

This paper develops a theory of contact for piecewise parametric curves based on the differential geometry of evolutes, polar curves, and binormal indicatrices. This theory is completely geometric, independent of parametrization and generalizes to any order. Two sets of dimensionless, characteristic numbers describing the local geometry of a curve up tonth order are defined. These characteristic numbers can be used to describe conditions for higher order contacts in an algebraic fashion. The same characteristic numbers can also be used to interpret contact conditions of up tonth order in terms of the geometry of higher evolutes and binormal indicatrices. The resulting geometric contact conditions are used to design piecewise parametric curves for Computer Aided Geometric Design (CAGD) applications.     

Segmentation of document images

Several methods for segmentation of document images (maps, drawings, etc.) are explored. The segmentation operation is posed as a statistical classification task with two pattern classes: print and background. A number of classification strategies are available. All require some prior information about the distribution of gray levels for the two classes. Training (either supervised or unsupervised) is employed to form these initial density estimates. Automatic updating of the class-conditional densities is performed within subregions in the image to adapt these global density estimates to the local image area. After local class-conditional densities have been obtained, each pixel is classified within the window using several techniques: a noncontextual Bayes classifier, Besag's classifier, relaxation, Owen and Switzer's classifier, and Haslett's classifier. Four test images were processed. In two of these, the relaxation method performed best, and in the other two, the noncontextual method performed best. Automatic updating improved the results for both classifiers     

Segmentation of chromatic images

When analyzing color pictures one often requires that the image be segmented into meaningful regions based upon the color characteristics of the scene. Such a problem can assume two different forms. The first variation arises when particular color space characteristics are known and the goal is to detect and extract image regions which possess the given color characteristics. The second case arises when there is no a priori knowledge about the color space characteristics of the scene and the goal is to segment the scene into meaningful regions which possess uniform color space characteristics. This paper describes an interactive system which uses a decision surface modeling approach to solve the first case and uses clustering techniques in the three-dimensional color space to solve the second case. A set of examples is presented and the performance of the system is evaluated.     

Segmentation of SAR images

This paper presents a new algorithm for segmentation of SAR images based on threshold estimation using the histogram. The speckle distribution in the SAR image is modeled by a Gamma function. Thus, the SAR image histogram exhibits a combination of Gamma distributions. The maximum likelihood technique is therefore used to estimate the histogram parameters. This technique requires knowledge of the number of modes of the histogram, the number of looks of the SAR image, and the initial parameters of the histogram. The second derivative of the histogram is used to estimate the number of modes. We use two methods to estimate the number of looks. Initial parameters are estimated at the maximum of the Gamma function. Thresholds are selected at the valleys of a multi-modal histogram by minimizing the discrimination error between the classes of pixels in the image. The algorithm is applied to several RADARSAT SAR images with different number of looks. The results obtained are promising.     

On geometric interpolation of parametric surfaces

By exploiting the freedom in the choice of parametrization of a parametric surface, we show that there exist quadratic parametric surfaces that approximate a given parametric surface with the same approximation order as cubics, namely four, in the neighbourhood of a point where the Gaussian curvature of the surface is nonzero. This provides a first generalization to surfaces of earlier work for curves.     

Automatic inspection of mechanical parts using geometric models and laser range finder data

This paper addresses the problems associated in processing arrays of depth data in order to achieve the goal of automatic inspection of mechanical parts, i. e. developing general model-based inspection strategies that can be applied to a range of objects. The main problems in processing this data are segmenting out reliable primitives from the data and matching these primitives to those in a stored geometric model of an object. The ability of a 3D vision system to provide depth data accurate enough to perform automatic inspection tasks was until recently only possible at a short range from an object, typically a few centimetres. However it is now possible to produce dense data from a vision system situated further from the object, typically half a metre to a metre. Such a system is outlined. Some current model-based matching techniques are assessed for their suitability for employment in inspection type tasks. One approach is adopted and modifications that improve the efficiency and accuracy of the method for inspection purposes are presented. Finally, an inspection strategy is outlined and its performance assessed. Results are presented on both artificial and real depth data.     

Parallel search for the interpretation of aerial images

In this paper, we present a parallel search scheme for model-based interpretation of aerial images, following a focus-of-attention paradigm. Interpretation is performed using the gray level image of an aerial scene and its segmentation into connected components of almost constant gray level. Candidate objects are generated from the window as connected combinations of its components. Each candidate is matched against the model by checking if the model constraints are satisfied by the parameters computed from the region. The problem of candidate generation and matching is posed as searching in the space of combinations of connected components in the image, with finding an (optimally) successful region as the goal. Our implementation exploits parallelism at multiple levels by parallelizing the management of the open list and other control tasks as well as the task of model matching. We discuss and present the implementation of the interpretation system on a Connection Machine CM-2. The implementation reported a successful match in a few hundred milliseconds whenever they existed.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem () = min{c ^t x¦Ax =b + ¯b,x 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function (). As a consequence, the optimality intervals form a partition of the closed interval {; ¦()¦ < }. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of () is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.This research was partially funded by the United States Navy-Office of Naval Research under Contract N00014-87-K-0202. Its financial support is gratefully acknowledged.     

A geometric view of parametric linear programming

We present a new definition of optimality intervals for the parametric right-hand side linear programming (parametric RHS LP) Problem ?(λ) = min{c ^t x¦Ax =b + λ¯b,x ≥ 0}. We then show that an optimality interval consists either of a breakpoint or the open interval between two consecutive breakpoints of the continuous piecewise linear convex function ?(λ). As a consequence, the optimality intervals form a partition of the closed interval {λ; ¦?(λ)¦ < ∞}. Based on these optimality intervals, we also introduce an algorithm for solving the parametric RHS LP problem which requires an LP solver as a subroutine. If a polynomial-time LP solver is used to implement this subroutine, we obtain a substantial improvement on the complexity of those parametric RHS LP instances which exhibit degeneracy. When the number of breakpoints of ?(λ) is polynomial in terms of the size of the parametric problem, we show that the latter can be solved in polynomial time.     

Detecting objects in images in real-time computer vision systems using structured geometric models

Methods for designing high-level image processing algorithms for real-time computer vision systems (VS) in which images of objects or their parts can be represented using structured geometric models that have step-like edge features as their primitive elements.     

Probabilistic reachability for parametric Markov models

Given a parametric Markov model, we consider the problem of computing the rational function expressing the probability of reaching a given set of states. To attack this principal problem, Daws has suggested to first convert the Markov chain into a finite automaton, from which a regular expression is computed. Afterwards, this expression is evaluated to a closed form function representing the reachability probability. This paper investigates how this idea can be turned into an effective procedure. It turns out that the bottleneck lies in the growth of the regular expression relative to the number of states (n ^{Θ(log n)}). We therefore proceed differently, by tightly intertwining the regular expression computation with its evaluation. This allows us to arrive at an effective method that avoids this blow up in most practical cases. We give a detailed account of the approach, also extending to parametric models with rewards and with non-determinism. Experimental evidence is provided, illustrating that our implementation provides meaningful insights on non-trivial models.     

Strategies for designing geometric transformations on quantum images

Three design strategies for constructing new geometric transformations on quantum images from other transformations are proposed. The strategies focus on the affected areas in the images, the separability, and smoothness of the transformations by exploiting a representation of images on quantum computers extensively. The complexity in terms of the number of basic gates and the depth of the corresponding circuits are analyzed to understand the advantages and disadvantages of each strategy. Examples to demonstrate the applicability of the proposed strategies are presented. The strategies provide high level tools to explore and analyze transformations which are necessary to build practical image processing applications on quantum computers.