Restricted-orientation convexity, also called O-convexity, is the study of geometric objects whose intersection with lines from some fixed set is empty or connected. We introduce restricted-orientation halfspaces, which are an O- convexity analog of halfspaces, explore their properties, and demonstrate their relationship to restricted-orientation convex sets.

Some properties of digital surfaces, such as straightness or flatness can be detected by the combined action of a large set of simple local feature detectors. Our goal is to examine how we can use feature detectors to improve the computation of tangents, curvature, surface normals for digitized curves and surfaces. For continuous surfaces these standard functions can be computed by differential operators. We propose to replace the differential operators by sets of difference operators and feature detectors. For each part of the surface the feature detectors determine which difference operator yields the best approximation for the differential. We show that both the set of feature detectors and the set of difference operators have a rigid mathematical structure. To examine this structure, i.e. the functional decomposition and combination of multiple feature detectors, we use Groebner bases.

This paper presents a new approach, called Gaussian segmentation, to extract regions containing locally concentrated stimuli. We describe two kinds of searching methods, local search and dynamic search, to link local solutions of the estimating function in parameter space in the same and different visual fields, respectively. In the local search, we propose an iterative technique which can find a local solution from any initial state of parameters by means of searching the parametric space locally. The dynamic search is provided to move from one of the local search results as the initial state to the other local search results. Finally, the availability of the technique is shown by experiments for estimating using functional images and real images.

The purpose of this note is to investigate the genericity and stability of shading patterns in the images of scenes. These notions are defined in terms of the gradient dynamical system of image intensity. The main results are: (1) For a surface of revolution, the generic light source directions are stable. (2) For a surface of revolution, the set of connected components of the set of generic directions refines the set of equivalence classes of stable light source directions, each equivalence being the union of one or more components.

We consider a cross-section topology which is defined on grayscale images. The main interest of this topology is that it keeps track of the grayscale information of an image. We define some basic notions relative to that topology. Furthermore, we indicate how to get an homotopic kernel. Such a kernel may be seen as an `ultimate' topological simplification of an image. A kernel of a real image, though simplified, is still an intricated image from a topological point of view. We introduce the notion of irregular region. The iterative method of irregular regions in a kernel allows to selectively simplify the topology. Through an example, we show that this notion leads to a method for segmenting some grayscale images without the need of defining and tuning parameters.

Optimization processes based on `active models' have been used to solve many problems in computer vision. This paper describes a simple class of discrete active models, called migration processes, which can be defined without the use of sophisticated mathematical machinery. The processes are based on iterated averaging over neighborhoods defined by constant geodesic distance. They can be applied to derive natural solutions to a variety of optimization problems, including defining (minimal) surface patches given their boundary curves; and finding shortest paths joining set of points.

The numerous applications of surface interpolation include the modeling and visualization of physical phenomena. A tetrahedrization is the one of pre-processing steps for 4D surface interpolation. The quality of a piecewise linear interpolation in 4D space depends not only on the distribution of the data points in R³, but also on the data values. One can improve the quality of an approximation by using data dependent criteria. This paper discusses Delaunay tetrahedrization method (sphere criterion) and one of the data dependent tetrahedrization methods (least squares fitting criterion). This paper also discusses new data dependent criteria: (1) gradient difference, and (2) jump in normal direction derivatives.

The current definition of 3D digital lines, which uses the 2D digital lines of closest integer points (Bresenham's lines) of two projections, has several drawbacks: the discrete topology of this 3D digital line notion is not clear; its third projection is, generally, not the closest set of points of the third euclidean projection; if we consider a family of parallel euclidean lines, we do not know how many combinatorially distinct digital structures will be built by this process; and mainly the set of voxels defined in this way is not the set of closest points of the given euclidean line. And these questions are the simplest ones; many others could be asked: dependence on the choice of the projection, intersections with digital planes, intersections between 3D digital lines,... This paper gives a new definition of 3D digital lines relying on subgroups of Z³, whose main advantage over the former one is its ability to convert any practical question into rigorous algebraic terms. It follows previously developed ideas but with a much simpler treatment and new results. In particular, we obtain a complete description of the topology of these lines and a condition for the third projection being a 2D digital line as well as a classification of digital lines of the same direction into classes of equivalent combinatorial structure.

The following problem is considered: given three image intensities (photographs) of an opaque object surface, reconstruct the shape of the surface and the surface local reflecting properties. This problem is formalized on the basis of rigorous description of object photoimage formation (in the framework of geometrical optics and photometry) and resulted in three concepts: an optical surface (the mathematical description of an opaque object surface), a projection schema (the mathematical description of an image- formatting optical apparatus as a (photo)camera), a projection-schema image (the mathematical description of an image intensity). The usage of these concepts allows one to formulate the opaque object surface reconstruction problem as the mathematical problem of reconstructing an optical surface from its three projection-schema images. It is shown that the optical surface reconstruction (OSR) problem takes the form of a Cauchy problem for the system of three first- order, non-linear, partial differential equations. A general uniqueness theorem for the OSR problem is proven. Also, the OSR problem for a specific class (`diffuse-speculum' surfaces) of optical surfaces is investigated. The conditions providing the unique reconstruction of a diffuse- speculum optical surface have been found in the form of `pure' geometric conditions (the restrictions on the relative positions in the space of the source of illumination and cameras) as well as in the form of some restrictions on image intensity distributions which to be used if the geometric conditions are not fulfilled.

We study various algorithmic tasks related to the inverse problem for discrete Radon transforms. These questions are motivated by demands from tomography, material sciences, data compression, image processing, and data security.

In this note, we discuss various kinds of 2D unit cells, or surface-unit cells, made by regular polygons (simplexes) in the plane R X R. Mathematically, the plane can be divided by simplexes or regular polygons (decomposition). If we only allow one kind of surface-unit in the plane, there are only three possible choices: regular triangle (3-regular- polygon), square (4-regular-polygon), or 6-regular-polygon. Using Euler's formula for planar graphs, we give a type of topological proofs to that a closed digital curve has at least 6 points in a 3-regular-polygon decomposition plane, has at least 8 points in a 4-regular-polygon decomposition plane, and has at least 12 points in a 6-regular-polygon decomposition plane, respectively. On the other hand, a plane can also be divided by combinations of two kinds of regular polygons. We have obtained two types of {3,6}-regular-polygon combinations, two types of {4,8}-regular-polygon combinations, and one type of {3,12}-regular-polygon combination. We also discuss the application of polygons or closed paths to digital surfaces in 3D digital spaces.

Let a 26-connected, bounded subset of Z³, such that the projection in the plane Oxy is one to one. We present an incremental algorithm which determines if this subset is or is not a piece of digital plane. This problem is solved thanks to the diophantine definition of digital planes and by using only 2D geometrical constructions.

A new spatial relation called arrangements has been previously proposed to describe how embedded parts in an image are surrounded by their neighbors. Arrangements can be derived directly from the sequence of Voronoi cells bordering an embedded part of an image. It has been shown that it is possible to compare any two arrangements, caused by the embedding of the same parts, by use of the Diagonal Exchange Operator and the Voronoi Flower diagram. However, the algorithms previously proposed is practical only for very small sets of embedded parts because of both the expensive operation of computing the prerequisite area Voronoi tessellation and the exponential search complexity (in terms of the number of edges in the Voronoi tessellation) required to compute the distance metric. We present a new algorithm for computing arrangements efficiently for complex images containing a large number of embedded parts. Motivated by the new algorithm, we propose the use of arrangements for the indexing and retrieval of complex technical diagrams which may contain many similar parts.

The analysis of simple elliptical image structures is accomplished by casting the image as a 3D surface so that the mathematics of surface analysis can be explained. Segmentation is performed by computing surface characteristics using differential geometry and classifying image regions based on local surface measures. The segmented image regions are classified by fitting a generalized conic section to the region boundary. A least squares method minimizes the total error between the segmented image and the ideal conic. Further image manipulations force this conic to be an ellipse for this application. The image analysis paradigm is tested with bubble images where each bubble region is assumed to have an elliptical shape.

The invariance and covariance of extracted features from an object under certain transformation play quite important roles in the fields of pattern recognition and image understanding. For instance, in order to recognize a 3D object, we need specific feature extracted from a given object. These features should be independent of the pose and the location of an object. In this paper, as one of the feature extracting methods, we present 3D autoregressive model and its higher dimensional extensions. 1D and 2D autoregressive model has been considered as one of the feature extracting methods.

I demonstrate how local coordinate transformations can be performed optically and how local planar representation of 3D figures allows one to initiate development of 3D optical computational geometry.

This paper deals with a hierarchical description of grayscale images based on image dipoles. An image dipole is a region whose lines of slope emanate from the maximum, and reach the same minimum. Incorporating an image dipole based representation of an image into a scale-space filtering, we proposed here a hierarchical image dipole description of the image. The proposed description consists of image dipole networks of selected scales, and linking of image dipoles across the scales such that it contains all transformations of the image dipole network in the scale-space.

In this paper we define a property applied to contours and 2D shapes we call `shape equivalence', or more strictly, `virtual shape equivalence'. The intuitive idea is that two contours or 2D shapes are `virtually equivalent' (at a given scale of resolution) if they can possibly give rise to identical area sampled images (at the given scale) with respect to a given sampling regime. The word `virtual' is used because the relationship is not a true equivalence relation--in particular it is not strictly transitive. The idea is similar to the psychological notion of `just noticeable difference' (JND). Two stimuli are within a JND threshold if a subject cannot perceptually distinguish them, even though they may in fact be different. Similarly our notion of virtual equivalence of contours corresponds to there being no noticeable difference between them with respect to a certain class of sampling regimes at a particular scale of resolution. The usefulness of the concept is that it can be used to built a formal theory of shape and contour simplification (at various scales) to assist object recognition.

Edges of general images are generally made of the noise (or singular) points of images. Some purely discrete and very simple algorithms, like Sobel one, are able to approximate these edges, but, unhappily, they lack accuracy. Using the restriction of gray level images to 3 X 3 masks interpreted as 3D digital surfaces, we give a new way of computing exactly the normal vector, or gradient, at regular points. We derive from this study a new discrete algorithm, based on Max Area Triangles contained in 3 X 3 masks, able to make a finer distinction between regular and singular point on any image and giving softer boundaries.

Dual graph contraction reduces the number of vertices and of edges of a pair of dual image graphs while at the same time, the topological relations among the `surviving' components are preserved. Repeated application produces a stack of successively smaller graphs: a pair of dual irregular pyramids. The process is controlled by selected decimation parameters which consist of a subset of surviving vertices and associated contraction kernels. Equivalent contraction kernels combine two or more contraction kernels into one single contraction kernel which generates the same result in one single dual contraction. This is the basis to the proof that any segmentation can be represented in one single level of such a pyramid. Experimental results demonstrate the applicability on synthetic and real images respectively.

Using the theory of correspondences from algebraic geometry, we have developed methods for relating 3D objects to 2D images and vice versa. This provides a very general framework for the use of geometric invariants in image recognition. At a concrete level, our techniques yield a system of polynomial equations in variables which represent both the 3D invariants of the features on an object and the 2D invariants of the features in an image. These equations will be satisfied if and only if the object can produce the image up to projective transformations of both the object and the image. The case of affine invariants was dealt with in previous work. The applications considered are to single view recognition and to indexing image databases for content based retrieval.

A new Euclidean distance transformation (EDT) for binary images in Zⁿ is introduced. We sequentialize the parallel method of Huang and Mitchell by restricting the propagation to sufficient propagation paths. Tests in Z² and in Z³ show that the algorithm is significantly faster than other well known signed and unsigned EDTs. Combined with the method of Saito and Toriwaki, it also yields a fast parallel EDT.

There is an application G^Aff which sends an admissible subset M of Pn+1 to an admissible subset G^Aff(M) of Pⁿ⁺¹. The application G^Aff is an involution, but the most useful property of GAff is to transform the profile of M in the direction (nu) (epsilon) Pn into an intersection of G^Aff(M) with an affine hyperplane of Pⁿ⁺¹. We denote by i:Pⁿ yields Pⁿ⁺¹ the application defined by i([x₁,...,x_n+1]) equals [x₁,...,x_n+1,0], and C_(nu)M the profile in the direction (nu) (epsilon) Pⁿ. We can generalize the application G^Aff to convex n-polytopes, written GP^Aff, and it gives a dual application from n-polytopes to n-polytopes which reverses inclusion of faces. The main property of GP^Aff is that if A is a polytope close to an analytic convex hypersurface M, then GP^Aff (A) is close to G^Aff(M). We can deduce an algorithm of reconstruction of convex sets using this map.

In the area of robotic vision we are interested in developing algorithms for the control of a robot manipulator by means of visual feedback. Image analysis and exploitation of the image features are therefore steps of importance. This paper deals with the problem of 3D localization of objects representing circular patterns. The first part of the paper is concerned with the parametrization of elliptic curves and a second part is dedicated to the estimation of an object's position and orientation.

In this paper, we propose a randomized algorithm to estimate the planar motion parameters of a finite closed set. By randomly searching points on two shapes measured at different times, we determine the centroids and translation of the planar shapes. Taking these centroids as reference points, the algorithm proceeds to determine the point-to- point correspondences by randomly searching three points on each shape that form congruent triangles. After the point correspondences have been determined, the rotation is estimated by solving the rigid motion equation.

A binary image contains object points and background points. Many operations on 2D and 3D images are required to preserve connectivity, that is, every object of the resulting image after the application of the operation preserves the same connectivity of the corresponding object in the original image. Normally, such operations can only delete `simple' object points. The simplicity of an object point can be determined by verifying its immediate neighborhood, i.e., a 3 X 3 neighborhood for the 2D case, or a 3 X 3 X 3 neighborhood for the 3D case, respectively. This verification for the 2D case is not difficult. However, it is not very easy for the 3D case since the number of different configurations of the 3D immediate neighborhood of a point is rather large. This paper studies some properties of this 3D problem and reduce it to a 2D problem.

In this paper, a 2D image, stored as a 2D array of pixels, is represented as a function f: Z² yields Z such that f(x) is the gray scale value of the image function f at the point x (epsilon) Z². The set of points (x,f(x)) where x (epsilon) Z² can be considered as a topographical surface S. We formally define `blob-like' features on this surface S as regions associated with extrema of f. We associate a blob-like feature to each extremum of the surface S. The blob-like regions have spatial as well as gray level extent. These features are the connected components of the surface S. Features associated with minima correspond to darker objects on brighter background whereas those associated with maxima correspond to brighter objects on darker background. It is well known, that not all image features can be detected at any one scale. We therefore propose a multi- scale scenario wherein the complete information about all the image features is contained in the gaussian scale space representation of that image. We detect the formalized `blob-like' features at each scale of the scale space and translate the problem of representation of these features across the scales to a tree representation G. The nodes of G correspond to the blob like features and the relative positioning of the gray level blobs in the tree is decided by the topographical surface S. These blobs are grouped into a higher order image structure, called the (sigma) -blob which is a family of blobs over an interval of scale. The detection of the prominent image features is translated to the problem of the traversal of the (sigma) -blob tree which is the representation of the (sigma) -blobs as nodes and the relative positioning in this tree representation is decided by the scale at which these (sigma) -blobs would be detected. Additional properties of the blob-like features are established both at single scale and across the scales. The detection algorithm proposed in the work is presented with test runs on both synthetic and real images.

A new class of functions is studied. They are generalizations of the little-known `flower-shop distance'. We call them touching functions. Some of them are metrics, i.e. touching metrics (TM). Disks, circles and digital paths based on these metrics are also studied. The distance transform based on TMs is introduced and a scheme for the algorithm is given.

Classic colorimetry and the traditionally used color space do not represent all perceived colors (for example, browns look dark yellow in colorimetric conditions of observation) so, the specific goal of this work is to suggest another concept of color and to prove that the corresponding set of colors is complete. The idea of our approach attributing color to surface patches (not to the light) immediately ties all the problems of color perception and vision geometry. The equivalence relation in the linear space of light fluxes F established by a procedure of colorimetry gives us a 3D color space H. By definition we introduce a sample (sigma) (surface patch) as a linear mapping (sigma) : L yields H, where L is a subspace of F called the illumination space. A Dedekind structure of partial order can be defined in the set of the samples: two samples (alpha) and (Beta) belong to one chromatic class if ker(alpha) equals ker(Beta) and (alpha) > (Beta) if ker(alpha) ker(Beta) . The maximal elements of this chain create the chromatic class BLACK. There can be given geometrical arguments for L to be 3D and it can be proved that in this case the minimal element of the above Dedekind structure is unique and the corresponding chromatic class is called WHITE containing the samples (omega) such that ker(omega) equals {0} L. Color is defined as mapping C: H yields H and assuming color constancy the complete set of perceived colors is proved to be isomorphic to a subset C of 3 X 3 matrices. This subset is convex, limited and symmetrical with E/2 as the center of symmetry. The problem of metrization of the color space C is discussed and a color metric related to shape, i.e., to vision geometry, is suggested.

A new algorithm of the non-Euclidean distance transform with raster scanning value propagation is developed. In this algorithm, a single access to some analyzed pixels is sufficient to obtain their final values, while double processing of every pixel is necessary in other algorithms, of this type. In addition to a raster image, interval coding is used to speed up a processing. This representation does not take much memory space. An application of the proposed distance transform algorithm for object shape reconstruction from disconnected blobs (text symbols are chosen as an example) is given. As compared to the standard raster scanning algorithm, a speed-up factor of 1.3 - 1.4 is obtained, while reconstruction results are the same in both cases.

Delaunay triangulation is the dual of Dirichlet tessellation is not affine invariant. In other words, the triangulation is dependent upon the choice of the coordinate axes used to represent the vertices. In the same reason, Delaunay tetrahedrization does not have an affine invariant transformation property. In this paper, we present a new type of tetrahedrization of spacial points sets which is unaffected by translations, scalings, shearings and rotations. An affine invariant tetrahedrization is discussed as a means of affine invariant 2D triangulation extended to 3D tetrahedrization. A new associate norm between two points in 3D space is defined. The visualization of tetrahedrization (i.e. tetrahedral domain, representative data points and transformed data points) can discriminate between Delaunay tetrahedrization and affine invariant tetrahedrization.

In this paper, we propose a new operator called the Surface- Shape operator (SS-operator) for determining local surface shape, and use it for analyzing image structure. We consider an image function as a bivariate surface, then describe a shape of each pixel comparing with its neighborhood. In a geometry viewpoint, types of surface shapes are elliptic, hyperbolic, parabolic, etc. Here, we label them based on topographical structure and used a statistic approach to measure spatial distribution of these shapes overall the surface. The Surface-Shape operator is established by utilizing the eigenvalues of Hessian of an image function. We show how to derive this operator and its interesting properties, and give examples to demonstrate its usefulness in practical uses. Finally, we illustrate its roles for describing texture images by using co-occurrence matrices, a statistical measure, to represent its numerical description, and show its good performance for suppressing shading effects as well.

A new method is developed to estimate fundamental matrix (F matrix). We first find two parameters in the 8-parameter F model by the new constraint developed in this paper, the two parameters are the affine coordinates of an epipole. Then we obtain the rest 6 parameters by solving a set of linear equations. Finally, our method is tested with many real images and compared with the 8-point method and some iterative algorithms, the results show that our method has many advantages, such as the obvious geometrical meaning, the fewer matching pairs needed for calculation and high accuracy F matrice.

This paper introduces a combinatoric approach in digital geometry. This mathematical tool allows to establish a connection between algebra and geometry in digital geometry. Some development in hypergraphs, matroid and antimatroid are presented. Such concepts provide a sound mathematical basis for digital geometry objects such as graphs, convexity and algebra. Some applications in image processing are included in this paper.