No description available.

Geometric computations are essential in many real-world problems. One important issue in geometric computations is that the geometric models in these problems can be so large that computations on them have infeasible storage or computation time requirements. Decomposition is a technique commonly used to partition complex models into simpler components. Whereas decomposition into convex components results in pieces that are easy to process, such decompositions can be costly to construct and can result in representations with an unmanageable number of components. In this work, we have developed an approximate technique, called Approximate Convex Decomposition (ACD), which decomposes a given polygon or polyhedron into "approximately convex" pieces that may provide similar benefits as convex components, while the resulting decomposition is both significantly smaller (typically by orders of magnitude) and can be computed more efficently. Indeed, for many applications, an ACD can represent the important structural features of the model more accurately by providing a mechanism for ignoring less significant features, such as wrinkles and surface texture. Our study of a wide range of applications shows that in addition to providing computational efficiency, ACD also provides natural multi-resolution or hierarchical representations. In this dissertation, we provide some examples of ACD's many potential applications, such as particle simulation, mesh generation, motion planning, and skeleton extraction.

The shapes of naturally occurring objects characteristically involve spatial events occurring at many scales. This paper offers a symbolic approach to constructing a primitive shape description across scales for 2D binary (silhouette) shape images: grouping operations are performed over collections of tokens residing on a Scale-Space Blackboard. Two types of grouping operations are identified that, respectively: (1) aggregate edge primitives at one scale into edge primitives at a coarser scale and (2) group edge primitives into partial-region assertions, including curved- contours, primitive-corners, and bars. This approach avoids several drawbacks of numerical smoothing methods.

This report shows how knowledge about the visual world can be built into a shape representation in the form of a descriptive vocabulary making explicit the important geometrical relationships comprising objects' shapes. Two computational tools are offered: (1) Shapestokens are placed on a Scale-Space Blackboard, (2) Dimensionality-reduction captures deformation classes in configurations of tokens. Knowledge lies in the token types and deformation classes tailored to the constraints and regularities ofparticular shape worlds. A hierarchical shape vocabulary has been implemented supporting several later visual tasks in the two-dimensional shape domain of the dorsal fins of fishes.

This study presents a new shape representation scheme based on disconnected symmetry axes along with a matching framework to address the problem of generic shape recognition. The main idea is to define the relative spatial arrangement of local symmetry axes in a shape centered coordinate frame. The resulting descriptions are invariant to scale, rotation, small changes in viewpoint and articulations. Symmetry points are extracted from a surface whose level curves roughly mimic the motion by curvature. By increasing the amount of smoothing on the evolving curve, only those symmetry axes that correspond to the most prominent parts of a shape are extracted. The representation does not suffer from the common instability problems of the traditional connected skeletons. It captures the perceptual properties of shapes well. Therefore, finding the similarities and the differences among shapes becomes easier. The matching process is able to find the correct correspondence of parts under various visual transformations. Highly successful classification results are obtained on a moderate sized 2D shape database.

We present an efficient method for reconstructing complex geometry using an elliptic Partial Differential Equation (PDE) formulation. The integral part of this work is the use of three-dimensional curves within the physical space which act as boundary conditions to solve the PDE. The chosen PDE is solved explicitly for a given general set of curves representing the original shape and thus making the method very efficient. In order to improve the quality of results for shape representation we utilize an automatic parameterization scheme on the chosen curves. With this formulation we discuss our methodology for shape representation using a series of practical examples.

One of the remaining obstacles to the widespread application of industrial robots is their inability to deal with parts that are not precisely positioned. In the case of manual assembly, components are often presented in bins. Current automated systems, on the other hand, require separate feeders which present the parts with carefully controlled position and attitude. Here we show how results in machine vision provide techniques for automatically directing a mechanical manipulator to pick one object at a time out of a pile. The attitude of the object to be picked up is determined using a histogram of the orientations of visible surface patches. Surface orientation, in turn, is determined using photometric stereo applied to multiple images. These images are taken with the same camera but differing lighting. The resulting needle map, giving the orientations of surface patches, is used to create an orientation histogram which is a discrete approximation to the extended Gaussian image. This can be matched against a synthetic orientation histogram obtained from prototypical models of the objects to be manipulated. Such models may be obtained from computer aided design (CAD) databases. The method thus requires that the shape of the objects be described, but it is not restricted to particular types of objects.

The question of how shape is represented is of central interest to understanding visual processing in cortex. While tuning properties of the cells in early part of the ventral visual stream, thought to be responsible for object recognition in the primate, are comparatively well understood, several different theories have been proposed regarding tuning in higher visual areas, such as V4. We used the model of object recognition in cortex presented by Riesenhuber and Poggio (1999), where more complex shape tuning in higher layers is the result of combining afferent inputs tuned to simpler features, and compared the tuning properties of model units in intermediate layers to those of V4 neurons from the literature. In particular, we investigated the issue of shape representation in visual area V1 and V4 using oriented bars and various types of gratings (polar, hyperbolic, and Cartesian), as used in several physiology experiments. Our computational model was able to reproduce several physiological findings, such as the broadening distribution of the orientation bandwidths and the emergence of a bias toward non-Cartesian stimuli. Interestingly, the simulation results suggest that some V4 neurons receive input from afferents with spatially separated receptive fields, leading to experimentally testable predictions. However, the simulations also show that the stimulus set of Cartesian and non-Cartesian gratings is not sufficiently complex to probe shape tuning in higher areas, necessitating the use of more complex stimulus sets.

People began to interact with their own environment since their birth. Their main organs to sense their surroundings are their hands, and this is the most natural way of interaction in human-human interactions. The goal of this dissertation is to enable users to employ their hands in interaction with computers similar to human-human interaction. Using hands in the computer interaction increases both the naturalness of computer usage and the speed of interaction. One way of accomplishing this goal is to utilize computer vision methods to develop hand interfaces. In this study, a regular, low-cost camera is used for image acquisition, and the images from camera are processed by our novel vision system to detect user intention. The contributions are (i) a method for interacting with a screen without touching in a distributed computer system is proposed, (ii) a benchmark of four hand shape representation methods is performed using a comprehensive hand shape video database, and (iii) a vison-based hand interface is designed for an application that queries a video database system, and its usability and performances are also assessed by a group of test users to determine its suitability for the application.

A novel and unconventional shape description scheme is proposed which captures the hierarchy of parts and medial descriptors. Both the parts and the medial descriptors are extracted simultaneously, in a complementary fashion, using a real valued function defined over the shape domain. The function arises out of both global and local interactions within the shape domain and it is related to an extension of a linear elliptic PDE with an integral term. The part hierarchies, extracted via level sets and watersheds of the function, are organized into proper binary trees, and the medial descriptors, extracted via ridges and watersheds of the function, are organized as rooted depth-1 trees. The medial descriptors (we named global skeleton) consist of two distinct medial abstractions. The limbs and prominent boundary features are captured in the form of conventional skeletons. Secondly, the coarse structure of the shape is captured in the form of a watershed region, which is a powerful tool in respect to both stability and representation of prominent shape properties. Additionally, as an important technical contribution that addresses part matching, the randomized hierarchy tree is introduced that endows the part hierarchy tree with a probabilistic structure.