After having recalled the definition and some local properties of strong surfaces, we present a related new thinning algorithm with surface skeleton and a specific application of these notions to superimposition of images of brains obtained by Magnetic Resonance Image.
Morgenthaler and Rosenfeld gave the first formal definition of digital surfaces. Kong and Roscoe embedded digital spaces to continuous spaces to show the intuitive meaning of Morgenthaler-Rosenfeld's surfaces. Reed and Rosenfeld discussed the recognition algorithms for digital surface. Chen and Zhang considered an intuitive and simple definition of digital manifolds in case of direct adjacency in digital spaces. This note continues the task. This note will simplify some concepts used and extended some concepts used. First, we continue to study all cases of ((alpha) , (beta) )- surfaces and eliminate some trivial and overlapping cases. Among nine types of digital surfaces, there are only two useful: (6,26)-surfaces and (18,6)-surfaces. We will develop or modify three algorithms for the three definitions. Because some visually true digital surface is not included in any of ((alpha) , (beta) )-surfaces, we will give a more general definition for digital surface in both direct and indirect adjacency. In order to develop a fast algorithm for real surface tracking, a quasi-digital-surface is defined even through sometimes the definition is weak in terms of mathematics.
In this paper, we introduce a new motion of surfaces in Z3, called simplicity surfaces. In the continuous space, a surface is characterized by the fast that the neighborhood of each point of the surface is homomorphic to an Euclidean disc. The chosen approach consists in characterizing a surface in Z3 by the condition that the neighborhood of any point constitutes a simple closed curve. The major problem is than, if we consider only the usual adjacency relations, this condition is not satisfied even for the simplest surfaces, e.g. digital planes. We thus have to consider another relation. We use a relation for points in Z3 which is based on the notion of homotopy. This allows to define a surface as a connected set of points in which the neighborhood of each point constitutes a simples closed curve for this relation; such a surface is called a simplicity surface. We give two different local characterizations of simplicity surfaces. We then show that a simplicity surface may also be seen as a combinatorial manifold, that is, a set of faces which are linked by an adjacency relation. Furthermore, we show that the main existing notions of surfaces, for the 6- and the 26- adjacency, are also simplicity surfaces.
1D and 2D continua belong to the basic notions of set- theoretical topology and represent a subfield of the theory of dimensions developed by P. Urysohn and K. Menger. In this paper basic definitions and properties of grid continua in R2 and R3 are summarized. Particularly, simple 1D gird continua in R2 and in R3, and simple closed 2D grid continua in R3 are emphasized. Concepts for measuring the length of 1D grid continua and the surface area of a 2D grid continuum are introduced and discussed.
In this paper, we employ a polyhedron whose vertices are only lattice points as a discrete representation of any 3D object, in order to treat the shape in a lattice space. We present a method for generating such polyhedra corresponding to the original objects in Euclidean space, and call this process discretization. Moreover, we prove that our polyhedra converge to the original objects when the grid interval is infinitely decreased to zero. The proof implies that our discretization method has the guarantee of the shape approximation for the sufficiently small grid interval. Finally, we investigate the maximum grid interval which guarantees the shape approximation.
In the recently published Ref. 1 the author survey a number of aspects of the geometry of digital spaces. In this article we exemplify the approach of that book, by providing a self-contained proof of one of its final result which is to do with the correctness and the characterization of the output of a general purpose boundary-tracking algorithm.
In this paper we explore the application of several advanced mathematical techniques from algebraic geometry, notably the theory of correspondences and a novel 'equivariant' invariant theory, to the problem of recognizing 3D geometric configurations from a single 2D view. We specifically require the approach to be view independent. This forces us to characterize line configurations by their 3D or 2D geometric invariants. Recent work of R. Huang on 'invariants of sets of lines in projective 3-space' provides a first description of the necessary line invariances in 3D. In this paper, we simplify Huang's results and develop the algebro- geometric machinery needed to understand the relationship that exists between the 3D algebraic geometry. Exploiting this, we compute a set of fundamental equations in the combined set of 3D and 2D invariants, which generate the ideal of the correspondence, and which completely describe the mutual 3D/2D constraints. We have chosen to call these equations 'object/image equations'. They can be exploited in a number of ways. For example, from a given 2D configuration of lines, we can determine a set of non-linear constraints on the geometric invariants of the 3D line configurations capable of producing that given 2D configuration, and thus arrive at a test for determining the object being viewed. Conversely, given a 3D geometric configuration, we can derive a set of equations that constrain the images of that object. Methods to compute a complete set of generating object/image equations that constrain the images of that object. Methods to compute a compete set of generating object/image equations are mentioned. These include advanced geometric techniques like KSY resultants, sparse resultants, and Groebner bases. The calculations have been carried out using a mix of such advanced techniques in the specific case under consideration, namely line features. The resulting object/image equations have been sued in industrial and defense applications.
Almost all people can imagine a process to make a clay cube a clay ball by smoothing every edge and vertex of a cube without knowing any mathematics to describe this procedure theoretically. This is an example which shows that we can infer and obtain new concepts from learned geometrical concepts. This paper proposed a mathematical model to explain a process to obtain an outline of a shape by using the generalized cylinder representation of the 3D shape and Fourier descriptor for boundary curves on each slice. The method yields an outline of changing of the curvature along an orthogonal net drown on the surface of the original shape.
Registration of conventional range images form multiple viewpoints has generally relied on redundant information from 10,000-100,000 points per image. Continuous scanning by laser-camera sensors without viewpoint knowledge requires the ability to register and integrate narrow range views inclose sequence, in order to minimize redundant data acquisition, permit high acquisition speed and reduce viewpoint planning. This paper presents a method of registering and integrating narrow and spatiotemporally- dense range views, which consists of only three profiles each, without sensor pose information.
3D image modeling of volumetric data is highly demanded for automated visual inspection and non-destructive testing. It also can be useful to biomedical research, medical therapy, surgery planning, and simulation of critical surgery. The common problem of volumetric image data is that the amount of data is too much. This paper proposes a method which selects the important data by using wavelet transformation, and refines the constructed tetrahedral domain until the difference between the approximation and the measured value is less than the specified tolerance. The resulting interpolant can be visualized by using iso-surface rendering. We call this new algorithm as marching tetrahedra for the purpose of comparing to marching cubes algorithm. The main difference between two algorithms is tetrahedra are used instead of cubes. Therefore, we can avoid the ambiguity problem of marching cubes algorithm.
We describe a geometric model of high-resolution radar (HRR), where objects being imaged by the sensor are assumed to consists of a collection of isotropic scattering centers distributed in three dimensions. Three, four, five and six point pure HRR invariant quantities for non-coplanar reflecting centers are presented. New work showing invariants combining HRR and SAR measurements are then presented. All these techniques require matching corresponding features in multiple HRR and/or SAR views. These features are represented using analytic scattering models. Multiple features within the same HRR resolution cell can be individually detected and separated using interference-suppression filters. These features can then be individually tracked to maintain correspondence as the object poise changes. We validate our HRR/SAR invariants using the XPATCH simulation system. Finally, a view-based method for 3D model reconstruction is developed and demonstrated.
This paper introduces a new operator called the surface- shape operator for describing image structure. An image function is considered as a bivariate surface, then the surface-shape operators is established for describing shape of each pixel comparing with its neighborhood by utilizing surface curvatures. In the geometry viewpoint, types of surface shape are elliptic, hyperbolic, cylindrical, etc. To give clearer meanings in general, we label them based on the topographic structure such as hill, dale, ridge, valley, etc. By extending from single-scale image analysis, the surface-shape operator is used as a pre-processing for describing multiscale topographic structures in scale-space representation. Surface-shape operator has invariant properties under linear and monotonic gray tone transformations, and is insensitive to additive noises modeled by linear functions, so it has robustness with brightness variations and shading effects. We illustrate usefulness of the surface-shape operator for image analysis with the image classification application, and compare the proposed method with the popular methods used to-date: the spatial gray level dependence method, Laws' method for the single-scale approach, and the multiresolution simultaneous autoregressive method for the multiscale approach. Results show that the proposed method works much better than the other methods. In particular, the proposed method based on multiscale analysis performs best.
In digital geometry and topology, there are two popular kinds of digital spaces: point spaces and raster spaces. In point-spaces, a digital object is presented by a set of elements. In raster spaces as defined in this note, a digital object is a subset of a 'relation' on the space. In an Euclidean space, given a set S of points which are called sites, we can get the Voronoi diagram of S and its Delaunay triangulation. The Voronoi diagram is just a raster space as well as Delaunay simple decomposition is a point space. Thus, a point space is a dual space of a raster space. This note reviews some research results in point spaces and raster spaces and present the author's opinions on the following problems: how to define digital curves, surfaces, and manifolds in point spaces or raster spaces. What are the difference and relationship between them. What are the advantages and/or disadvantages to use point spaces or raster spaces in practical computation. The purpose of the note is to show a global consideration and to unify some basic concepts in digital geometry and topology.
The use of Hough Transform in image processing is generally restricted to alignment detection. This paper presents different links between HT and the study of convex shapes. It uses classical HT, and as well, equivalent transforms. Various applications are given: symmetry functions, perimeter evaluation, etc. Radon Transform is shown to be a convenient generalization framework.
Size functions are a mathematical tool for comparing shapes represented as topological spaces. In this paper we introduce a method for describing a set of size functions corresponding to a given class of objects. An example of the application of this method for signature recognition is presented.
This paper studies approximation properties of set skeletons. The first result is about objects for which image information is given. Namely, we show that the medial axis by an arbitrary disk with a given radius is a one-side Hausdorff approximation of the skeleton. The second result is about boundary - represented objects. It concerns the approximate construction of the skeleton of an object using the Voronoi diagram of a discrete sample set on its boundary. A new non-standard approach for solving this problem is presented. Meanwhile, a non-standard generalization of Delaunay and Voronoi graphs for hyperfinite point sets is introduced.
The factorization method by Tomasi and Kanade gives a stable and an accurate reconstruction. However is difficult to apply their method to real-time applications. Then we present an iterative factorization method for the GAP model with tracking the feature points. In this method, through the fixed size measurement matrix, which is independent of the number of the frames, the motion and the shape are to be reconstructed at every frame. Some experiments are also given to show the performance of our proposed iterative method.
A similarity measure for silhouettes of 2D objects is presented, and its properties are analyzed with respect to retrieval of similar objects in an image database. Our measure profits from a novel approach to subdivision of objects into parts of visual form. To compute our similarity measure, we first establish the best possible correspondence of visual parts, which is based on a correspondence of convex boundary arcs. Then the similarity between correspondence arcs is computed and aggregated. We applied our similarity measure to shape matching of object contours in various image databases and compared it to well-known approaches in the literature. The experimental results justify that our shape matching procedure gives an intuitive shape correspondence and is stable with respect to noise distortions.
Computing discrete 2D convolutions is an important problem in image processing. In mathematical morphology, an important variant is that of computing binary convolutions, where large kernels are involved. In this paper, we present an algorithm for computing convolutions of this form, where the kernel of the binary convolution is derived from a convex polygon. Because the kernel is a geometric object, we allow the algorithm some flexibility in how it elects to digitize the convex kernel at each placement, as long as the digitization satisfies certain reasonable requirements. We say that such a convolution is valid. Given this flexibility we show that it is possible to computer binary convolutions more efficiently than would normally be possible for large kernels, computes a valid convolution in time O(kmn) time. Unlike standard algorithms for computing correlations and convolutions, the running time is independent of the area or perimeter of K, and our technique do not rely on computing fast Fourier transforms. Our algorithm is based on a novel use of Bresenham's line-drawing algorithm and prefix-sums to update the convolution efficiently as the kernel is moved from one position to another across the image.
2D binary image processing algorithms frequency require the computation, for a pixel p, of some Boolean function of the values of a few pixels near p. For any such Boolean function over a given probability distribution on the function that is, in a sense, optimally efficient. We introduce a measure for run-time efficiency as a result of generating the optimized C implementation, which is independent of the development platforms and the programming skills. Thus it can be regarded as a tool to measure the run-time efficiency of 2D binary image algorithms before even conducting actual experimental tests. Using a simple data set comparing with the evenly distributed probability data, we present our experimental results using our measure and analyze a number of thinning algorithms based on our measure to evaluate the run-time performance of these binary image processing algorithms.
On the discrete grid, the alternate use of V4-V8 neighborhoods is known to approximate the Euclidean distance. This problem was analyzed in the continuous setting and, more generally, it was shown that, if a certain inclusion holds for the unit balls of k distances, their alternate use yields a true distance, called sandwich distance. This paper elaborates on this topic. The initial scope is enlarged by defining new families of distances, called mixed distances. They are compositions of linear combinations of distances and of sandwich distances. Two examples of iterations of mixed distances are investigated. Their unit balls are polygons with 2k sides; their convergence towards the Euclidean disk is analyzed.
A new implementation of the Euclidean, ordered propagation distance transform is developed. Unlike traditional approaches, where multiplication operations contribute a significant cost to computation, we suggest to apply the city lock and chessboard distance transform to approximate the Euclidean distances.In fact, the city block transform is just performed, while the chessboard one is simulated based on the iteration number value. Though multiplications are not totally excluded, their amount is greatly reduced because a few pixel values are only corrected at each iteration of the algorithm by using the Euclidean distances as compared to other similar methods, where those distances are determined for each pixel. As a result, we obtain a faster method for generating the Euclidean distance maps, which is still accurate.
A continuous figure may be represented by a binary image on a discrete grid. Continuous figures possess some invariant properties with respect to translation, rotation and symmetry. In the paper we evaluate maximal and relative errors of several invariant features based on central moments calculated for various geometric figures in 1D and 2D digital spaces.
The face recognition, as one of the pattern recognition, includes various essence such as the representation and the extraction of the required features, the classification based on the obtained features and the detecting specified regions etc. Previously, we presented the scale and the rotation invariant face recognition method based on both Higher-Order Local Autocorrelation features of log-polar image and linear discriminant analysis for 'face' and 'not face' classification. In this face recognition method, the searching for the 'face' region was performed randomly or sequentially on the image. Therefore its searching performance was not satisfiable. In this paper, we present a method to narrow down the search space by dynamically using the information obtained at the previous search point through constructing the multilevel dynamic attention map, which is constructed based on the Ising dynamics and the renormalization group method.
Clustering means grouping of similar objects by optimizing a certain criterion. Clustering techniques are very common and useful in image processing and pattern recognition, especially for unsupervised initial segmentation of images. Images always contain some imprecise, uncertain or ambiguous regions and structures. Fuzzy sets constituted a good framework to represent and take into account these imprecisions. Their use leads to image processing methods where binary decision are not taken at intermediate levels, where only partial information is available. As mentioned by Bloch the usage of fuzzy sets in image processing relies on two different approaches - symbolic, where decision rules are derived from fuzzy logic, and numerical, where fuzzy sets directly represent the spatial structure of the image. Our work combines these two approaches.
There are many applications for which there is a strong need to analyze digital terrain elevation data (DTED). However, the availability of DTED is limited. For some areas of the world, DTED is not available at all, and for other areas it may be only partially available. This introduces significant problems if analysis is required for areas of constrained DTED availability. On the other hand, compressed arc digitized raster graphics (CADRG) maps provide a guaranteed source of digital data that contains a limited amount of elevation information, namely elevations that occur along the contours in the maps. Unfortunately, CADRG maps typically contain a significant amount of additional visual information that obscures features of interest, making difficult the automated locations of contours and the subsequent transformation into DTED.
Directional decomposition of maps and line-drawing images has the advantage of stressing directional information, and so may assist in the analysis of such images. In this paper, a method is described for directional decomposition of maps and line-drawing images into an arbitrary number of directional edge planes, where the range of directions that is included in each directional edge plane may be determined individually. The proposed approach is based on self dilated line kernels, which are generated by dilating discrete periodic line segments by themselves. These kernels are then used by regulated morphological operations, that extend the fitting interpretation of the ordinary morphological operations, in order to obtain the required decomposition. The paper describes necessary propositions of the proposed approach, and represents examples of their use for the application of line-drawings analysis.
We present a new algorithm for large deformation image matching via volume data. The image matching problem is stated as a control problem with the optimal diffeomorphic match constructed a minimize a running smoothness cost on a velocity field generating the diffeomorphism wile simultaneously minimizing a matching end point condition of the imagery. The diffeomorphic deformation field on the image space is generated by numerically integrating the velocity field.
Recently, there has been growing interest in data structures in high dimensional pixel spaces. Among these structures are image manifolds. A point on an image manifold is an image; that is, a brightness function of two variables. In any in- depth geometric study of image manifolds,the impact of various sampling resolutions must be taken into account: will a manifold composed of a specific set of images sampled at one resolution differ geometrically from manifolds composed of the same image set sampled at other resolution. The main theorem of this paper states that under a specific Nyquist criterion, two image manifolds generated from the same source, but samples at differing pixel resolutions are not only diffeomorphic but isometric. This surprising new result proves the fundamental notion that geometric properties are invariant under sampling. Loosely speaking, this means that the two manifolds are of the same shape. In addition to proving this isometry theorem, an examination of fundamental image manifold properties such as curvature validates the theorem. Finally, the limitations of the Nyquist criterion are explored.
Hough Transform, an important tool in image processing, does not use the analytical or geometrical properties of its basic objects, sine curves. Their replacement by other curves, namely circles, has led us to the discovery and the autonomous study of two families of transforms, named Circle and Envelope Transforms. These transforms, internal to the plane of study, are divided into three classes: parabolic, elliptic and hyperbolic, in connection with the Euclidean and the two non-Euclidean geometries. They are shown to be equivalent to Hough Transform. Three 'classical geometry' transforms interplay with envelope transforms: reciprocal polar transform, inversion transform and pedal transform. A unified view is brought by the introduction of the 'space of circles' equipped with a special quadratic form. This set of transforms can be applied successfully to conic curves in view of their characterization and detection. Almost every concept in this model is generalizable to 3D in a straightforward manner. Generalization is also promising for gray-level images in the direction of Radon Transform.
Handwritten Chinese character recognition system invariably sue different image processing techniques to preprocess the input image before the main classification and recognition techniques are used. The authors proposed a different approach to the system philosophy of solving the handwritten Chinese character recognition problem for no preprocessing is necessary. The Chinese characters are treat as ideographs. The proposed system comprise of a Rough Classifier which control the different Fine Classifiers. Each classifier is an optimized artificial neural network using genetic algorithms. A reduced system has been implemented. The result shows that the proposed system has higher recognition rate than the similar systems reported and is more efficiency.
In this paper a new method of deriving the trifocal tensor based on fundamental matrix is presented. Given the matching points in the three images of the same scene, we calculate the two fundamental matrixes with the high accuracy, then we construct the three projection matrixes of the images, and the trifocal tensor could be obtained from the three projection matrixes. With the great simplicity of the method, the experiments show that the transfer eros of our method is less than that of the trilinearity estimating method SVD and it has the same result with that of MLE.
An opto-mechanical microprobe system which combines the advantages of optical non-contact method and mechanical contact one is proposed for measuring very small parts on coordinate measuring machines. The principle is based on the evaluation of a central position of stylus ball by an optical system, the stylus ball is illuminated by a cold light source through an optical fiber. The most inventive advantage of the microprobe is that the deformation of its stylus does not influence the measuring results, so the stylus could be extremely thin. Until now an opto-mechanical microprobe with stylus ball of diameter of about 40 micrometers and stylus of diameter of about 20 micrometers is developed. Experiments show that the accuracy of the opto-mechanical microprobe is better than 1 micrometers and the measuring force is less than 10 (mu) N.