Visual Form 2001

This short paper surveys methods for planar shape recognition and shape smoothing and processing invariant under viewing distortions and possibly partial occlusions. It is argued that all the results available on these problems implicitly follow from considering two basic topics: invariant location of points with respect to a given shape (i.e. a given collection of points) and invariant displacement of points with regard to the given shape.

Structural pattern recognition is characterized by the representation of patterns in terms of symbolic data structures, such as strings, trees, and graphs. In this paper we review recent developments in this field. The focus of the paper will be on new methods that allow to transfer some well established procedures from statistical pattern recognition to the symbolic domain. Examples from visual form analysis will be given to demonstrate the feasibility of the proposed methods.

In this paper we show how the shape and dynamics of complex actions can be encoded using the intrinsic curvature and torsion signatures of their component actions. We then show how such invariant signatures can be integrated into a Dynamical Bayesian Network which compiles efficient recurrent rules for predicting and recognizing complex actions. An application in skill analysis is used to illustrate our approach.

Visual forms come in countless varieties, from the simpli- city of a sphere, to the geometric complexity of a face, to the fractal complexity of a rugged coast. These varieties have been studied with mathematical tools such as topology, differential geometry and fractal geometry. They have also been examined, largely in the last three decades, in terms of mereology, the study of part-whole relationships. The result is a fascinating body of theoretical and empirical results. In this paper I review these results, and describe a new development that applies them to the problem of learning names for visual forms and their parts.

An experimental comparative study of three matching methods for the recognition of 3D objects from a 2D view is carried out. The methods include graph matching, geometric hashing and the alignment technique. The same source of information is made available to each method to ensure that the comparison is meaningful. The experiments are designed to measure the performance of the methods in different imaging conditions. We show that matching by geometric hashing and alignment is very sensitive to clutter and measurement errors. Thus in realistic scenarios graph matching is superior to the other methods in terms of both recognition accuracy and computational complexity.

Hierarchical image structures are abundant in computer vision, and have been used to encode part structure, scale spaces, and a variety of multiresolution features. In this paper, we describe a unified framework for both indexing and matching such structures. First, we describe an indexing mechanism that maps the topological structure of a directed acyclic graph (DAG) into a low-dimensional vector space. Based on a novel eigenvalue characterization of a DAG, this topological signature allows us to efficiently retrieve a small set of candidates from a database of models. To accommodate occlusion and local deformation, local evidence is accumulated in each of the DAG’s topological subspaces. Given a small set of candidate models, we will next describe a matching algorithm that exploits this same topological signature to compute, in the presence of noise and occlusion, the largest isomorphic subgraph between the image structure and the candidate model structure which, in turn, yields a measure of similarity which can be used to rank the candidates. We demonstrate the approach with a series of indexing and matching experiments in the domains of 2-D and (view-based) 3-D generic object recognition.

The task of visual classification is the recognition of an object in the image as belonging to a general class of similar objects, such as a face, a car, a dog, and the like. This is a fundamental and natural task for biological visual systems, but it has proven difficult to perform visual classification by artificial computer vision systems. The main reason for this difficulty is the variability of shape within a class: different objects vary widely in appearance, and it is difficult to capture the essential shape features that characterize the members of one category and distinguish them from another, such as dogs from cats.In this paper we describe an approach to classification using a fragment-based representation. In this approach, objects within a class are represented in terms of common image fragments that are used as building blocks for representing a large variety of different objects that belong to a common class. The fragments are selected from a training set of images based on a criterion of maximizing the mutual information of the fragments and the class they represent. For the purpose of classification the fragments are also organized into types, where each type is a collection of alternative fragments, such as different hairline or eye regions for face classification. During classification, the algorithm detects fragments of the different types, and then combines the evidence for the detected fragments to reach a final decision. Experiments indicate that it is possible to trade off the complexity of fragments with the complexity of the combination and decision stage, and this tradeoff is discussed.The method is different from previous part-based methods in using class-specific object fragments of varying complexity, the method of selecting fragments, and the organization into fragment types. Experimental results of detecting face and car views show that the fragment-based approach can generalize well to a variety of novel image views within a class while maintaining low mis-classification error rates. We briefly discuss relationships between the proposed method and properties of parts of the primate visual system involved in object perception.

The paper introduces a new approximation scheme for planar digital curves. This scheme defines an approximating sausage ‘around’ the given digital curve, and calculates a minimum-length polygon in this approximating sausage. The length of this polygon is taken as an estimator for the length of the curve being the (unknown) preimage of the given digital curve. Assuming finer and finer grid resolution it is shown that this estimator converges to the true perimeter of an r-compact polygonal convex bounded set. This theorem provides theoretical evidence for practical convergence of the proposed method towards a ‘correct’ estimation of the length of a curve. The validity of the scheme has been verified through experiments on various convex and non-convex curves. Experimental comparisons with two existing schemes have also been made.

Digital distance transforms are useful tools for many image analysis tasks. In the 2D case, the maximum difference from Euclidean distance is considerably smaller when using a 5 × 5 neighbourhood compared to using a 3 × 3 neighbourhood. In the 3D case, weighted distance transforms for neighbourhoods larger than 3 × 3 × 3 has almost not been considered so far. We present optimal local distances for an extended neighbourhood in 3D, where we use the three weights in the 3 × 3 × 3 neighbourhood together with the (2, 1, 1) weight from the 5 × 5 × 5 neighbourhood. A good integer approximation is shown to be 〈3, 4, 5, 7〉.

A Point Distribution Model requires first the choice of an appropriate representation for the data and then the estimation of the density within this representation. Independent Component Analysis is a linear transform that represents the data in a space where statistical dependencies between the components are minimized. In this paper, we propose Independent Component Analysis as a representation for point distributions. We observe that within this representation, the density estimation is greatly simplified and propose solutions to the most common problems concerning shapes. Mainly, testing shape feasibility and finding the nearest feasible shape. We also observe how the description of shape deformations in terms of statistically independent modes provides a more intuitive and manageable framework. We perform experiments to illustrate the results and compare them with existing approaches.

In this paper we propose two techniques to qualitatively estimate distance in monocular vision. Two kinds of approaches are described, the former based on texture analysis and the latter on histogram inspection. Although both the methods allow only to determine whether a point within an image is nearer or farther than another with respect to the observer, they can be usefully exploited in all those cases where precision is not critical or single images are the only source of information available. Moreover, combined with previously studied techniques, they could be used to provide more accurate results. Step by step algorithms will be presented, along with examples illustrating their application to real images.

A common model of second degree variation is an ellipsoid spanned by the magnitudes of the Hessian eigenvalues. We find this model incomplete and often misleading. Here, we present a more complete representation of the information embedded in second degree derivatives. Using spherical harmonics as a basis set, the rotation invariant part of this information is portrayed as an orthonormal shape-space, which is non-redundant in the sense that any local second order variation can be rotated to match one and only one unique prototype in this space. A host of truly rotation invariant and shape discriminative shape factors is readily defined.

The skeleton is an effective tool for shape analysis if its structure can be regarded as a faithful stick-like representation of the pattern. However, contour noise may affect this structure by originating spurious skeleton branches, so that skeletonization algorithms should include a pruning phase devoted to an analysis of the peripheral skeleton branches and, possibly, to their partial or total removal. In this paper, labeled skeletons are considered and the significance of a peripheral branch is evaluated by analyzing the type of interaction between the pattern subset corresponding to the peripheral branch and the pattern subsets corresponding to the skeleton branches adjacent to the peripheral branch. The proposed criteria for skeleton pruning are expressed in terms of four parameters, which as a whole describe the role that the pattern subset corresponding to the peripheral branch plays in the characterization of the shape of the pattern.

The focus of our paper is on the fitting of general curves and surfaces to 3D data. In the past researchers have used approximate distance functions rather than the Euclidean distance because of computational efficiency. We now feel that machine speeds are sufficient to ask whether it is worth considering Euclidean fitting again. Experiments with the real Euclidean distance show the limitations of suggested approximations like the Algebraic distance or Taubin’s approximation. In this paper we present our results improving the known fitting methods by an (iterative) estimation of the real Euclidean distance. The performance of our method is compared with several methods proposed in the literature and we show that the Euclidean fitting guarantees a better accuracy with an acceptable computational cost.

Loss of information in images undergoing fine-to-coarse image transformations is analized by using an approach based on the theory of irreversible transformations. It is shown that entropy variation along scales can be used to characterize basic, low-level information and to gauge essential perceptual components of the image, such as shape and texture. The use of isotropic and anisotropic fine-to-coarse transformations of grey level images is discussed, and an extension of the approach to multi-valued images is proposed, where cross-interactions between the different colour channels are allowed.

Graph pyramids allow to combine pruning of skeletons with a concept known from the representation of line images, i.e. generalization of paths without branchings by single edges. Pruning will enable further generalization of paths and the latter speeds up the former. Within the unified framework of graph pyramids a new hierarchical representation of shape is proposed that comprises the skeleton pyramid, as proposed by Ogniewicz. In particular, the skeleton pyramid can be computed in parallel from any distance map.

A voxel-based method for flattening a surface while best preserving the distances is presented. Triangulation or polyhedral approximation of the voxel data are not required. The problem is divided into two main subproblems: Voxel-based calculation of the minimal geodesic distances between the points on the surface, and finding a configuration of points in 2-D that has Euclidean distances as close as possible to the minimal geodesic distances. The method suggested combines an efficient voxel-based hybrid distance estimation method, that takes the continuity of the underlying surface into account, with classical multi-dimensional scaling (MDS) for finding the 2-D point configuration. The proposed algorithm is efficient, simple, and can be applied to surfaces that are not functions. Experimental results are shown.

In this paper we propose a novel image interpolation algorithm based on the quadratic B-spline basis function. Our interpolation algorithm preserves the original edges while not destroying the smoothness in flat area using the adaptive interpolation method according to the directional edge pattern of input image, significantly improving the overall performance of the interpolation. Our experimental result shows that it can produce higher quality and resolution than the currently existing image interpolation methods.

The usefulness of the 3D Medial Axis (MA)is dependent on both the availability of accurate and stable methods for computing individual MA points and on schemes for deriving the local structure and connectivity among these points. VVc propose a framework which achieves both by combining the advantages of exact bisector computations used in computational geometry: on the one hand, and the local nature of propagation-based algorithms, on the other, but without the computational complexity, connectivity, added dimensionality, and post processing issues commonly found in these approaches. Specifically, the notion of flow of shocks along the MA manifold is used to identify flow along special points and curves which define a shock scaffold. This 1D scaffold is of lower dimensional complexity than the typical geometric locus of medial points which are represented as 2D sheets. The scaffold not only organizes shape information in a hierarchical manner, but is a tool for the efficient recovery of the scaffold itself and can lead to exact reconstruction. VVe present examples of this approach for synthetic data, as well as for sherd data from the domain of digital archaeology.

We present an algorithm that, starting from the surface skeleton of a 3D solid object, computes the curve skeleton. The algorithm is based on the detection of curves and junctions in the surface skeleton. It can be applied to any surface skeleton, including the case in which the surface skeleton is two-voxel thick.

Exact mathematical representations of objects are not suitable for applications where object descriptions are vague or object data is imprecise or inadequate. This paper presents representation schemes for basic inexact geometric entities and their relationships based on fuzzy logic. The aim is to provide a foundation framework for the development of fuzzy geometric modelling which will be useful for both creative design and computer vision applications.

Deformables templates, because they contain a priori knowledge information on searched shapes, can be useful in the segmentation of complex images including partially occluded objects. In this paper, we propose a generic deformable template for shapes that are built around a flexible symmetry axis. The shape model is based on a parametrical skeleton, the distance between this skeleton and the contour points of the shape being determined by a parametrical envelope function. Various examples of skeleton and envelope models are given, and a general scheme for identification and matching suitable for a reusable code implementation is proposed. An application to image segmentation of partially overlapping leaves in natural outdoor conditions is then presented.

This paper presents a geometric measure that can be used to gauge the similarity of 2D shapes by comparing their skeletons. The measure is defined to be the rate of change of boundary length with distance along the skeleton. We demonstrate that this measure varies continuously when the shape undergoes deformations. Moreover, we show that ligatures are associated with low values of the shape-measure. The measure provides a natural way of overcoming a number of problems associated with the structural representation of skeletons. The first of these is that it allows us to distinguish between perceptually distinct shapes whose skeletons are ambiguous. Second, it allows us to distinguish between the main skeletal structure and its ligatures, which may be the result of local shape irregularities or noise.

2D curve representations usually take algebraic forms in ways not related to visual perception. This poses great difficulties in connecting curve representation with object recognition where information computed from raw images must be manipulated in a perceptually meaningful way and compared to the representation. In this paper we show that 2D curves can be represented compactly by imposing shaping constraints in curvature space, which can be readily computed directly from input images. The inverse problem of reconstructing a 2D curve from the shaping constraints is solved by a method using curvature shaping, in which the 2D image space is used in conjunction with its curvature space to generate the curve dynamically. The solution allows curve length to be determined and used subsequently for curve modeling using polynomial basis functions. Polynomial basis functions of high orders are shown to be necessary to incorporate perceptual information commonly available at the biological visual front-end.

In this paper we show that all images are topologically equivalent. Nevertheless, one can define useful pseudo-topological properties that are related to what is usually referred to as topological perception. The computation of such properties involves low-level structures, which correspond to end-stopped and dot-responsive visual neurons. Our results contradict the common belief that the ability for perceiving topological properties must involve higher-order, cognitive processes.

The role of connected components and connected filters is well established. In this paper a new segmentation procedure is presented based on connected components and connected filters. The use of connected components simplified the development of the algorithm. Moreover, if connected components are available as a basic data type, implementation is achievable without resorting to pixel level processing. Using parallel platforms with hardware support for connected components, the algorithm can fully exploit its data parallel implementation. We apply our segmentation procedure to axially oriented magnetic resonance brain images. Novel ideas are presented of how connected components operations (e.g. moments and bounding boxes) and connected filtering (e.g. area close-opening) can be effectively used together.

In this paper, we make an overview of the existing algorithms concerning the discrete curvature estimation. We extend the Worring and Smeulders [WS93] classification to new algorithms and we present a new and purely discrete algorithm based on discrete osculating circle estimation.

This paper describes a method to enhance line structures in a gray level image. For this purpose, we blur the image using anisotropic gaussian filters along the directions of each line structures. In a line structure region the gradients of image gray levels have a uniform direction. To find such line structures, we evaluate the uniformity of the directions of the local gradients. Before this evaluation, we need to smooth out small structures to obtain line directions. We, first, blur the given image by a set of gaussian filters. The variance of the gaussian filter which maximizes the uniformity of the local gradient directions is detected position by position. Then, the line directions in the image are obtained from this blurred image. Finally, we blur the image using anisotropic filter again along the directions, and enhance every line structure.

We consider the interactions between edges and intensity distributions in semi-open image neighborhoods surrounding them. Locally this amounts to a kind of figure-ground problem, and we analyze the case of smooth figures occluding arbitrary backgrounds. Techniques from differential topology permit a classiffication into what we call folds (the side of an edge from a smooth object) and cuts (the background). Intuitively, cuts arise when an arbitrary scene is “cut” from view by an occluder. The condition takes the form of transversality between an edge tangent map and a shading flow field, and examples are included.

In this paper, we present an incremental algorithm to efficiently extract topological features of deformable objects from a given sequential volume data. Even though these features are global shape information, we show that there are possibilities that we can extract them by local operations avoiding global operations.

This paper addresses the problem of enhancement of noisy scalar and vector fields, when they are known to be constrained to a manifold. As an example, we address selective smoothing of orientation using the geometric Beltrami framework. The orientation vector field is represented accordingly as the embedding of a two dimensional surface in the spatial-feature manifold. Orientation diffusion is treated as a canonical example where the feature (orientation in this case) space is the unit circle S1. Applications to color analysis are discussed and numerical experiments demonstrate again the power of this framework for non-trivial geometries in image processing.

Techniques to estimate the surface area of regular solids based on polyhedrization are classified to be either local or global. Surface area calculated by local techniques generally fails to be multigrid convergent. One of the global techniques which is based on calculating the convex hull shows a tendency to be multigrid convergent. However this algorithm only deals with convex sets. The paper estimates the surface area using another global technique called DPS (Digital Planar Segment) algorithm. The projection of these DPSes into Euclidean planes is used to estimate the surface area. Multigrid convergence experiments of the estimated surface area value are used to evaluate the performance of this new method for surface area measurement.

A method for deformable shape-based image segmentation is described. Regions in an image are merged together and/or split apart, based on their agreement with an a priori distribution on the global deformation parameters for a shape template. Perceptually-motivated criteria are used to determine where and how to split regions, based on the local shape properties of the region group’s bounding contour. In general, finding the globally optimal region partition for an image is an NP hard problem; therefore, two approximation strategies are employed: the highest confidence first algorithm and shape indexing trees. Experiments show that the speedup obtained through use of the approximation strategies is significant, while accuracy of segmentation remains high. Once trained, the system autonomously segments shapes from the background, while not merging them with adjacent objects or shadows.

In this paper we propose a series of novel morphological operators that are anisotropic, and adapt themselves to the local orientation in the image. This new morphology is therefore rotation invariant; i.e. rotation of the image before or after the operation yields the same result.We present relevant properties required by morphology, as well as other properties shared with common morphological operators. Two of these new operators are increasing, idempotent and absorbing, which are required properties for a morphological operator to be used as a sieve. A sieve is a sequence of filters of increasing size parameter, that can be used to construct size distributions.As an example of the usefulness of these newoperators, we show how a sieve can be build to estimate a particle or pore length distribution, as well as the elongation of those features.

This paper presents a visual architecture able to identify salient regions in a visual scene and to use them to focus on interesting locations. It is inspired by the ability of natural vision systems to perform a differential processing of spatial frequencies in both time and space and to focus their attention on a local part of the visual scene. The present paper analyzes how this differential processing of spatial frequencies is able to provide an artificial system with the information required to perform an exploration of its visual world based on a center-surround distinction of the external scene. It shows how the salient locations can be gathered on the basis of their similarities to form a high level representation of the visual scene.

We propose a method to generate component-based shape descriptions by the application of a perceptual grouping approach known as tensor voting. Based on previously described results on the generation of region, curve and junction saliencies and motivated by psychological findings about shape perception, we introduce extensions by a voting between junctions to create amodal completions, by a labeling of the junctions according to a catalog of junction types, and by a traversal algorithm to collect the local information into globally consistent part decompositions. In contrast to commonly used partitioning schemes, our method is able to create layered representations of overlapping parts. We consider this a major advantage together with the use of local operations and low computational costs whereas other approaches are based on highly iterative processes.

In this paper we present a new class of algorithms for detecting lines in digital images. The approach is based on a general formulation of a combinatorial optimization problem. It aims at estimating piecewise linear models. A linear system is constructed with the coordinates of all contour points in the image as coefficients and the line parameters as unknowns. The resulting linear system is then partitioned into a close-to-minimum number of consistent subsystems using a greedy strategy based on a thermal variant of the perceptron algorithm. While the partition into consistent subsystems yields the classification of the corresponding image points into a close-to-minimum number of lines. A comparison with the standard Hough Transform and the Randomized Hough Transform shows the considerable advantages of our combinatorial optimization approach in terms of memory requirements, time complexity, robustness with respect to noise, possibility of introducing “a priori” knowledge, and quality of the solutions regardless of the algorithm parameter settings.

Koenderink characterizes the local shape of 2D surfaces in 3D in terms of the shape index and the local curvedness. The index characterizes the local type of surface point: concave, hyperbolic, or convex. The curvedness expresses how articulated the local shape is, from flat towards very peaked. In this paper we define corner points as point on a shape of locally maximal Koenderink curvedness. These points can be detected very robustly based on integration indices. This is not the case for other natural corner points like extremal points. Umbilici can likewise be detected robustly by integral expressions, but does not correspond to intuitive corners of a shape. Furthermore, we show that Koenderink corner points do not generically coincide with other well-known shape features such as umbilici, ridges, parabolic lines, sub-parabolic lines, or extremal points. This is formalized through the co-dimension of intersection of the different structures.

In this paper, a dynamic model for contours using wavelets is presented. First it is shown how to construct probabilistic shape priors for modeling contour deformation using wavelets. Then a dynamic model for shape evolution in time is presented. This allows this formulation to be applied to the problem of tracking a contour using the stochastic model to predict contour location and appearance in successive image frames. Computational results for two real image problems are given for the Condensation (Conditional Density Propagation) tracking algorithm. It is shown that this formulation successfully tracks the objects in the image sequences.

A method for partitioning shapes is described based on a global convexity measure. Its advantages are that its global nature makes it robust to noise, and apart from the number of partitioning cuts no parameters are required. In order to ensure that the method operates correctly on bent or undulating shapes a process is developed that identifies the underlying bending and removes it, straightening out the shape. Results are shown on a large range of shapes.

In this paper we propose to use invariant signatures of polygonal approximations of smooth curves for projective object recognition. The proposed algorithm is not sensitive to the curve sampling scheme or density, due to a novel re-sampling scheme for arbitrary polygonal approximations of smooth curves. The proposed re-sampling provides for weak-affine invariant parameterization and signature. Curve templates characterized by a scale space of these weak-affine invariant signatures together with a metric based on a modified Dynamic Programming algorithm can accommodate projective invariant object recognition.

We introduce a rule-based approach for the learning and recognition of complex movement sequences in terms of spatio-temporal attributes of primitive event sequences. During learning, spatio-temporal decision trees are generated that satisfy relational constraints of the training data. The resulting rules are used to classify new movement sequences, and general heuristic rules are used to combine classiffication evidences of different movement fragments. We show that this approach can successfully learn how people construct objects, and can be used to classify and diagnose unseen movement sequences.

This article proposes to use both theories of possibility and rough histograms to deal with estimation of the movement between two images in a video sequence. A fuzzy modeling of data and a reasoning based on imprecise statistics allow us to partly cope with the constraints associated to classical movement estimation methods such as correlation or optical flow based-methods. The theoretical aspect of our method will be explained in details, and its properties will be shown. An illustrative example will also be presented.

In this paper, a novel algorithm for learning structured descriptions, ascribable to the category of symbolic techniques, is proposed. It faces the problem directly in the space of the graphs, by defining the proper inference operators, as graph generalization and graph specialization, and obtains general and coherent prototypes with a low computational cost with respect to other symbolic learning systems. The proposed algorithm is tested with reference to a problem of handwritten character recognition from a standard database.

We report on a method for achieving a significant truncation of the training space necessary for recognizing rigid 3D objects from perspective images. Considering objects lying on a table, the configuration space of continuous coordinates is three-dimensional. In addition the objects have a few distinct support modes. We show that recognition using a stationary camera can be carried out by training each object class and support mode in a two-dimensional configuration space. We have developed a transformation used during recognition for projecting the image information into the truncated configuration space of the training. The new concept gives full flexibility concerning the position of the camera since perspective effects are treated exactly. The concept has been tested using 2D object silhouettes as image property and central moments as image descriptors. High recognition speed and robust performance are obtained.

In the framework of an evolutionary approach to machine learning, this paper presents the preliminary version of a learning system that uses Genetic Programming as a tool for automatically inferring the set of classification rules to be used by a hierarchical handwritten character recognition system. In this context, the aim of the learning system is that of producing a set of rules able to group character shapes, described by using structural features, into super-classes, each corresponding to one or more actual classes. In particular, the paper illustrates the structure of the classification rules and the grammar used to generate them, the genetic operators devised to manipulate the set of rules and the fitness function used to match the current set of rules against the sample of the training set. The experimental results obtained by using a set of 5,000 digits randomly extracted from the NIST database are eventually reported and discussed.

In this paper we propose a new classifier - the Maximal Rejection Classifier (MRC) - for target detection. Unlike pattern recognition, pattern detection problems require a separation between two classes, Target and Clutter, where the probability of the former is substantially smaller, compared to that of the latter. The MRC is a linear classifier, based on successive rejection operations. Each rejection is performed using a projection followed by thresholding. The projection vector is designed to maximize the number of rejected Clutter inputs. It is shown that it also minimizes the expected number of operations until detection. An application of detecting frontal faces in images is demonstrated using the MRC with encouraging results.

An experiment was conducted to explore the transfer of training between visual lobe measurement tasks and visual search tasks. The study demonstrated that lobe practice improved the visual lobe, which in turn resulted in improved visual search performance. The implication is that visual lobe practice on carefully chosen targets can provide an effective training strategy in visual search and inspection. Results obtained from this research will help us in devising superior strategies for a whole range of tasks that have a visual search component (e.g., industrial inspection, military target acquisition). Use of these strategies, will ultimately lead to superior search performance.

We consider the problem of recognizing an object from its silhouette. We focus on the case in which the camera translates, and rotates about a known axis parallel to the image, such as when a mobile robot explores an environment. In this case we present an algorithm for determining whether a new silhouette could come from the same object that produced two previously seen silhouettes. In a basic case, when cross-sections of each silhouette are single line segments, we can check for consistency between three silhouettes using linear programming. This provides the basis for methods that handle more complex cases. We show many experiments that demonstrate the performance of these methods when there is noise, some deviation from the assumptions of the algorithms, and partial occlusion. Previous work has addressed the problem of precisely reconstructing an object using many silhouettes taken under controlled conditions. Our work shows that recognition can be performed without complete reconstruction, so that a small number of images can be used, with viewpoints that are only partly constrained.

Energy-minimizing techniques are an interesting approach to the segmentation problem. They extract image components by deforming a geometric model according to energy constraints. This paper proposes an extension to these works, which can segment arbitrarily complex image components in any dimension. The geometric model is a digital surface with which an energy is associated. The model grows inside the component to segment by following minimal energy paths. The segmentation result is obtained a posteriori by examining the energies of the successive model shapes. We validate our approach on several 2D images.

This paper considers camera motion extraction with application to automatic video classification. Video motion is subdivided into 3 components, one of which, camera motion, is considered here. The extraction of the camera motion is based on correlation. Both subjective and objective measures of the performance of the camera motion extraction are presented. This approach is shown to be simple but efficient and effective. This form is separated and extracted as a discriminant for video classification. In a simple classification experiment it is shown that sport and non-sport videos can be classified with an identification rate of 80%. The system is shown to be able to verify the genre of a short sequence (only 12 seconds), for sport and non-sport, with a false acceptance rate of 10% on arbitrarily chosen test sequences.

Object identification by matching is a central problem in computer vision. A major problem that any object matching method must address is the ability to correctly match an object to its model when parts of the object is missing due to occlusion, shadows, ... etc. In this paper we introduce boundary signatures as an extension to our surface signature formulation. Boundary signatures are surface feature vectors that reflect the probability of occurrence of a feature of a surface boundary. We introduce four types of surface boundary signatures that are constructed based on local and global geometric shape attributes of the boundary. Tests conducted on incomplete object shapes have shown that the Distance Boundary Signature produced excellent results when the object retains at least 70% of its original shape.

In this paper we propose a method for measuring the simi- larity between two images inspired by the notion of Hausdorff distance. Given two images, the method checks pixelwise if the grey values of one are contained in an appropriate interval around the corresponding grey values of the other. Under certain assumptions, this provides a tight bound on the directed Hausdorff distance of the two grey-level surfaces. The proposed technique can be seen as an equivalent in the grey level case of a matching method developed for the binary case by Hutten- locher et al. [2]. The method fits naturally an implementation based on comparison of data structures and requires no numerical computations whatsoever. Moreover, it is able to match images successfully in the presence of severe occlusions. The range of possible applications is vast; we present preliminary, very good results on stereo and motion correspondence and iconic indexing in real images, with and without occlusion.

The matching of hierarchical relational structures is of significant interest in computer vision and pattern recognition. We have recently introduced a new solution to this problem, based on a maximum clique formulation in a (derived) “association graph.” This allows us to exploit the full arsenal of clique finding algorithms developed in the algorithms community. However, thus far we have focussed on one-to-one correspondences (isomorphisms), and many-to-one correspondences (homomorphisms). In this paper we present a a general solution for the case of many-to-many correspondences (morphisms) which is of particular interest when the underlying trees reflect real-world data and are likely to contain structural alterations. We define a notion of an ε-morphism between attributed trees, and provide a method of constructing a weighted association graph where maximal weight cliques are in one-to-one correspondence with maximal similarity subtree morphisms.We then solve the problem by using replicator dynamical systems from evolutionary game theory. We illustrate the power of the approach by matching articulated and deformed shapes described by shock trees.

This paper casts the problem of perceptual grouping into an evidence combining setting using the apparatus of the EM algorithm. We are concerned with recovering a perceptual arrangement graph for line- segments using evidence provided by a raw perceptual grouping field. The perceptual grouping process is posed as one of pairwise relational clustering. The task is to assign line-segments (or other image tokens) to clusters in which there is strong relational affinity between token pairs. The parameters of our model are the cluster memberships and the pair- wise affinities or link-weights for the nodes of a perceptual relation graph. Commencing from a simple probability distribution for these parameters, we show how they may be estimated using the apparatus of the EM algorithm. The new method is demonstrated on line-segment grouping problems where it is shown to outperform a non-iterative eigenclustering method.

We present a 2D shape recognition and classification method based on matching shape outlines. The correspondence between outlines (curves) is based on a notion of an alignment curve and on a measure of similarity between the intrinsic properties of the curve, namely, length and curvature, and is found by an efficient dynamic-programming method. The correspondence is used to find a similarity measure which is used in a recognition system. We explore the strengths and weaknesses of the outline-based representation by examining the effectiveness of the recognition system on a variety of examples.

The paper describes a method for analysing a sequence of images by building static images, representing the environment on which shapes move. From the background and moving objects it is possible to reconstruct the original image sequence as well as to generate new ones. The analysis uses a linguistic interface that allows to express the semantics of video's. Both background and movement analysis allows to extract the shapes contained in a video. The description of video shapes and of their spatiotemporal properties is performed by a Prolog program; so the program using facts describes the Syntax of the video’s, while the layout of predicates contains the description of the semantics. Then the content of a ‘video-base’ may be extracted: the approach uses a prototype film, whose description is used as a dynamic query for automatic extraction of other film semantics.

A major concern in practical vision systems is how to retrieve the best matched models without exploring all possible object matches. This research presents probabilistic hypothesis generation based on indexing approach for the rapid recognition of three dimensional objects. We have defined the discriminatory power of a feature for a model object is defined in terms of a posteriori probability. This measure displays belief that a model appears in the scene after a feature is observed. We compute off-line the discriminatory power of features for model objects from CAD model data using computer graphic techniques. In order to speed up the indexing or selection of correct objects, we generate and verify the object hypotheses for features detected in a scene in the order of the discriminatory power of these features for model objects. Experimental results on synthetic and real range images show the effectiveness of our probabilistic method for hypothesis generation.

In this paper we present an efficient method for smooth surface generation from unorganised points using NURBS. This is a preferred alternative to using triangular meshes, which are expensive to store, transmit, render and are difficult to manipulate. The proposed method does not require triangulation prior to surface fitting because it generates NURBS directly. Two fundamental problems must be addressed to accomplish this task: parameterisation of measured data and overcoming ill-conditioning of the least squares surface fitting. We propose to solve the parameterisation problem by employing a suitable base surface, automatically generated from the data points, or provided as a CAD model if available. Ill-conditioning was solved by introducing additional fitting criteria in the minimisation functional, which constrain the fitted surface in the regions with insuficient number of data points. Surface fitting is performed by treating the surface as a whole without the need to either identify or re-measure the regions with insuficient data. The accuracy of fitting is dictated by the number of control points. The improvements in data compression, shape analysis and rendering are presented. The realised computational speed and the quality of the results were found to be highly encouraging.

This paper describes preliminary research work aimed at obtaining a multi-level iconic representation of 3D objects from geometric meshes. A single-level iconic model describes an object through parts of different dimensions connected to form a hypergraph. The multi-level iconic model, called Non-manifold Multi-Tessellation, incorporates decompositions of an object into parts at different levels of abstraction, and permits to refine an iconic representation selectively.

This paper describes three systems for image indexing and retrieval based on contour analysis. The systems compared are F-Index for Contours (fic), Hierarchical Entropy-based Representation (her) and Sketch-based query by Dialogue (sqd). The first system has been modified for contour-matching, since it was originally designed for a different purpose. The choice of these specifical systems has been made because of their similar conception, aim and computational complexity. An experimental and conceptual comparison has been carried out in order to assess retrieval precision, efficiency and usability. The results show that fic and her have similar performance in the high end of the spectrum, while sqd has less precise retrieval and less efficient search.

This paper clarifies a suficient condition for the reconstruction of an object from its shadows. The objects considered are finite closed convex regions in three-dimensional Euclidean space. First we show a negative result that a series of shadows measured using a camera moving along a circle on a plane is insuficient for the full reconstruction of an object even if the object is convex. Then, we show a positive result that a series of pairs of shadows measured using a general stereo system with some geometrical assumptions is suficient for full reconstruction of a convex object.

In this report, we present a 3D shape modeling method using the shape’s silhouettes from multiple views to determine the model (polyhedron) parameters. The polyhedron parameters are determined by neural networks, each of which represents the model’s silhouette observed from a view point, and determines the polyhedron parameters by the back propagation algorithm so that the model’s silhouette from each view approximates the corresponding silhouette of the target shape. By conducting basic experiments, we verified the effectiveness of the method.

A robust method is presented for retrieval of model shapes that have parts similar to the query shape presented to the image database. Structural feature indexing is a potential approach to efficient shape retrieval from large databases, but it is sensitive to noise, scales of observation, and local shape deformations. To improve the robustness, shape feature generation techniques are incorporated into structural indexing based on quasi-invariant shape signatures. The feature transformation rules obtained by an analysis of some particular types of shape deformations are exploited to generate features that can be extracted from deformed patterns. Effectiveness is confirmed through experimental trials with databases of boundary contours, and is validated by systematically designed experiments with a large number of synthetic data.

This paper proposes an efficient algorithm that not only can narrow down the search domain of face identification but also can reconstruct various 3D objects from a single free-hand line drawing. The algorithm is executed in two stages. In the face identification stage, we generate and classify potential faces into implausible, basis and minimal faces by using geometrical and topological constraints to reduce search space. The proposed algorithm searches the space of minimal faces only to identify actual faces of an object fast. In the object reconstruction stage, we introduce 3D regularities and quadric face regularities to reconstruct 3D object accurately. Furthermore, the proposed method can be applied to a wide scope of general objects containing flat and quadric faces. The experimental results show that the proposed method identifies faces much faster than previous ones and efficiently reconstructs various objects from a single free-hand line drawing.

Most CBIR systems use low-level visual features for representation and retrieval of images. Generally such methods suffer from the problems of high-dimensionality leading to more computational time and inefficient indexing and retrieval performance. This paper focuses on a low-dimensional color and shape based indexing technique for achieving efficient and effective retrieval performance. We propose a combined index using color and shape features. A new shape similarity measure is proposed which is shown to be more effective. Images are indexed by dominant color regions and similar images form an image cluster stored in a hash structure. Each region within an image is further indexed by a region-based shape index. The shape index is invariant to translation, rotation and scaling. A JAVA based query engine supporting query-by- example is built to retrieve images by color and shape. The retrieval performance is studied and compared with a region-based shape indexing scheme.

In this paper we propose a virtual drilling algorithm which is applied on 3-D objects. We consider that initial we are provided with a sparse set of parallel and equi-distant slices of a 3-D object. We propose a volumetric interpolation algorithm for recovering the 3-D shape from the given set of slices. This algorithm employs a morphology morphing transform. Drilling is simulated on the resulting volume as a 3-D erosion operation. The proposed technique is applied for virtual drilling of teeth considering various burr shapes as erosion elements.

This work describes a system for detecting and classifying malaria parasites in images of Giemsa stained blood slides in order to evaluate the parasitaemia of the blood. The first aim of our system is to detect the parasites by means of an automatic thresholding based on a morphological approach. Then we propose a morphological method to cell image segmentation based on grey scale granulometries and openings with disk-shaped elements, flat and hemispherical, that is more accurate than the classical watershed-based algorithm. The last step of the system is classifying the parasites by morphological skeleton.

The paper describes a vision processing system for traffic speed computation. Vehicle tracking is performed by using high-level features, that are clusters of license plate characters to achieve increased robustness of the system. By using a binocular arrangement of the Computer Vision system, the spatial and temporal range of image capture between consecutive views is extended, which leads to an improved accuracy in speed computation. Multiple views can be collected, from the same vehicle in transit, depending on the amount of speed. The effectiveness of the proposed solution is demonstrated through a geometric simulation model, where almost all operating conditions and constraints are fully exploited and tested. An error sensitivity analysis is carried out, to identify the most critical components of the system and the possible sources of errors in speed computation. This simulation approach is proved quite useful in this complex scenario, where it is commonly very difficult to collect true speed measures from the vehicles in transit. Beside the simulation analysis, a series of experimental results have been collected by a first prototype that is available since the end of year 2000.

Volumetric images of small mortar samples under load are acquired by X-ray microtomography. The images are binarized at many different threshold values, and over a million connected components are extracted at each threshold with a new, space and time efficient program. The rapid increase in the volume and surface area of the foreground components (cracks and air holes) is explained in terms of a simple model of digitization. Analysis of the data indicates that the foreground consists of thin, convoluted manifolds with a complex network topology, and that the crack surface area, whose increase with strain must correspond to the external work, is higher than expected.

A comparison is made of global and local methods for the shape analysis of logos in an image database. The qualities of the methods are judged by using the shape signatures to define a similarity metric on the logos. As representatives for the two classes of methods, we use the negative shape method which is based on local shape information and a wavelet-based method which makes use of global information. We apply both methods to images with different kinds of degradations and examine how a given degradation highlights the strengths and shortcomings of each method. Finally, we use these results to combine information from both methods and develop a new method which is based on the relative performances of the two methods.

In this paper, we are presenting our results for motion tracking animals in stabling. This system was used in order to record the behavior of pigs in stabling. We used an object-oriented method for our application instead of a block-oriented method. First of all, we calculated a reference image. This image was used in order to separate the objects from the background. Then, object pixels were grouped into an object by the line-coincidence method. Movement parameters are calculated for each object. Finally, an object correction is done for those objects that were occluded by the boundary of the stabling. The resulting tracking path and the movement parameters are displayed on screen for the user.

This paper describes a practical system developed for generating 3D models of human heads from silhouettes alone. The input to the system is an image sequence acquired from circular motion. Both the camera motion and the 3D structure of the head are estimated using silhouettes which are tracked throughout the sequence. Special properties of the camera motion and their relationships with the intrinsic parameters of the camera are exploited to provide a simple parameterization of the fundamental matrix relating any pair of views in the sequence. Such a parameterization greatly reduces the dimension of the search space for the optimization problem. In contrast to previous methods, this work can cope with incomplete circular motion and more widely spaced images. Experiments on real image sequences are carried out, showing accurate recovery of 3D shapes.