Fourier coding of image boundaries

A transform coding scheme for closed image boundaries on a plane is described. The given boundary is approximated by a series of straight line segments. Depending on the shape, the boundary is represented by the (x-y) coordinates of the endpoints of the line segments or by the magnitude of the successive radii vectors that are equispaced in angle around the given boundary. Due to the circularity present in the data, the discrete Fourier transform is used to exactly decorrelate the finite boundary data. By fitting a Gaussian circular autoregressive model to represent the boundary data, estimates of the variances of the Fourier coefficients are obtained. Using the variances of the Fourier coefficients and the MAX quantizer, the coding scheme is implemented. The scheme is illustrated by an example.     

On encoding boundaries with quadtrees

The ``line quadtree' data structure hierarchically represents a region and its boundary. Based on the standard quadtree, each node in this structure stores adjacency information as well. While line quadtrees use the same amount of space as standard qaudtrees, they facilitate several region processing algorithms. In particular, we describe efficient algorithms for boundary and superimposing two maps encoded as line quadtrees.     

Curvature-based blending of closed planar curves

A common way of blending between two planar curves is to linearly interpolate their signed curvature functions and to reconstruct the intermediate curve from the interpolated curvature values. But if both input curves are closed, this strategy can lead to open intermediate curves. We present a new algorithm for solving this problem, which finds the closed curve whose curvature is closest to the interpolated values. Our method relies on the definition of a suitable metric for measuring the distance between two planar curves and an appropriate discretization of the signed curvature functions.     

Analysis of the digitized boundaries of planar objects

The digitized boundary of an object can be expressed as a chain of points or of directions or of curvatures, all of which, however, are subject to contamination by spatial noise. The curvature chain is used to detect indentations in the boundary and it can be freed of noise (smoothed) by convolving it with a rectangular filter, once (the Freeman operation), twice (the Gallus operation) or more times. An analysis is made of the spatial frequencies passed by these operations. The analysis provides criteria for determining the optimal values of the width of the filter and the number of times it should be applied.The smoothing procedure is applied to the boundaries of conjugated objects consisting of two or more juxtaposed elementary objects (muscle fibres seen in transverse section). It is then possible to pick out indentations (nodes) in a boundary. The nodes are classified and matched and lines of segmentation are drawn between matched pairs. Criteria of acceptable matching of node pairs are described and examples of segmentation are illustrated.     

Elliptic Fourier features of a closed contour

A direct procedure for obtaining the Fourier coefficients of a chain-encoded contour is presented. Advantages of the procedure are that it does not require integration or the use of fast Fourier transform techniques, and that bounds on the accuracy of the image contour reconstruction are easy to specify. Elliptic properties of the Fourier coefficients are shown and used for a convenient and intuitively pleasing procedure of normalizing a Fourier contour representation. Extension of the contour representation to arbitrary objects at arbitrary aspect angle is discussed. The procedures have direct application to a variety of pattern recognition problems that involve analysis of well-defined image contours.     

Finding the closed partition of a planar graph

In this paper we consider the problem of finding aclosed partition in a directed graph. This problem has applications in concurrent probabilistic program verification. The best sequential algorithm known for this problem runs inO(mn) time wherem is the number of directed edges andn is the number of vertices in the given digraph. In this paper we present a linear-time sequential algorithm to solve the closed partition problem for planar digraphs that arecompact. We then build on this algorithm to obtain an O(n^1.5)-time sequential algorithm to solve the closed partition problem for a general planar digraph.This work was supported in part by NSF Grant CCR 89-10707.     

Detection and visualization of closed streamlines in planar flows

The analysis and visualization of flows is a central problem in visualization. Topology-based methods have gained increasing interest in recent years. This article describes a method for the detection of closed streamlines in flows. It is based on a special treatment of cases where a streamline reenters a cell to prevent infinite cycling during streamline calculation. The algorithm checks for possible exits of a loop of crossed edges and detects structurally stable closed streamlines. These global features are not detected by conventional topology and feature detection algorithms     

Constructing medial axis transform of planar domains with curved boundaries

The paper describes an algorithm for generating an approximation of the medial axis transform (MAT) for planar objects with free form boundaries. The algorithm generates the MAT by a tracing technique that marches along the object boundary rather than the bisectors of the boundary entities. The level of approximation is controlled by the choice of the step size in the tracing procedure. Criteria based on distance and local curvature of boundary entities are used to identify the junction or branch points and the search for these branch points is more efficient than while tracing the bisectors. The algorithm works for multiply connected objects as well. Results of implementation are provided.     

Fast computation of optimal polygonal approximations of digital planar closed curves

We face the problem of obtaining the optimal polygonal approximation of a digital planar curve. Given an ordered set of points on the Euclidean plane, an efficient method to obtain a polygonal approximation with the minimum number of segments, such that, the distortion error does not excess a threshold, is proposed. We present a novel algorithm to determine the optimal solution for the min-# polygonal approximation problem using the sum of square deviations criterion on closed curves.Our proposal, which is based on Mixed Integer Programming, has been tested using a set of contours of real images, obtaining significant differences in the computation time needed in comparison to the state-of-the-art methods.     

Fourier domain representation of planar curves for recognition in multiple views

Recognition of planar shapes is an important problem in computer vision and pattern recognition. The same planar object contour imaged from different cameras or from different viewpoints looks different and their recognition is non-trivial. Traditional shape recognition deals with views of the shapes that differ only by simple rotations, translations, and scaling. However, shapes suffer more serious deformation between two general views and hence recognition approaches designed to handle translations, rotations, and/or scaling would prove to be insufficient. Many algebraic relations between matching primitives in multiple views have been identified recently. In this paper, we explore how shape properties and multiview relations can be combined to recognize planar shapes across multiple views. We propose novel recognition constraints that a planar shape boundary must satisfy in multiple views. The constraints are on the rank of a Fourier-domain measurement matrix computed from the points on the shape boundary. Our method can additionally compute the correspondence between the curve points after a match is established. We demonstrate the applications of these constraints experimentally on a number of synthetic and real images.     

Computation of medial axis and offset curves of curved boundaries in planar domain

In this paper, we begin our research from the generating theory of the medial axis. The normal equidistant mapping relationships between two boundaries and its medial axis have been proposed based on the moving Frenet frames and Cesaro’s approach of the differential geometry. Two pairs of adjoint curves have been formed and the geometrical model of the medial axis transform of the planar domains with curved boundaries has been established. The relations of position mapping, scale transform and differential invariants between the curved boundaries and the medial axis have been investigated. Based on this model, a tracing algorithm for the computation of the medial axis has been generated. In order to get the accurate medial axis and branch points, a Two_Tangent_Points_Circle algorithm and a Three_Tangent_Points_Circle algorithm have been generated, which use the results of the tracing algorithm as the initial values to make the iterative process effective. These algorithms can be used for the computation of the medial axis effectively and accurately. Based on the medial axis transform and the envelope theory, the trimmed offset curves of curved boundaries have been investigated. Several numerical examples are given at the end of the paper.     

The kinematic design of spatial,hybrid closed chains including planar parallelograms

It is presented an integral approach for the kinematic design of spatial, hybrid closed chains which include planar parallelograms into their kinematic structure. It is based on a systematic application of recursive formulae intended for describing the evolution of screws through time. Due to the particular nature of the proposed approach, it can be closely related with Lie algebras and allows to overcome the lacking of group structure offered by a parallelogram when it is going to be considered as a component of a hybrid closed chain. Several application examples are presented in order to show the potential of the proposed approach.     

Fast Fourier transform-based correlation of DNA sequences using complex plane encoding

The detection of similarities between DNA sequences can be accomplished using the signal-processing technique of cross-correlation. An early method used the fast Fourier transform (FFT) to perform correlations on DNA sequences in O(n log n) time for any length sequence. However, this method requires many FFTs (nine), runs no faster if one sequence is much shorter than the other, and measures only global similarity, so that significant short local matches may be missed. We report that, through the use of alternative encodings of the DNA sequence in the complex plane, the number of FFTs performed can be traded off against (i) signal-to-noise ratio, and (ii) a certain degree of filtering for local similarity via k-tuple correlation. Also, when comparing probe sequences against much longer targets, the algorithm can be sped up by decomposing the target and performing multiple small FFTs in an overlap-save arrangement. Finally, by decomposing the probe sequence as well, the detection of local similarities can be further enhanced. With current advances in extremely fast hardware implementations of signal-processing operations, this approach may prove more practical than heretofore.     

Detecting the image boundaries between optical flow fields from several moving planar facets

A novel method of image and scene segmentation is presented which detects boundaries in the image between optical flow fields from different moving planar facets in the scene. It is based on parts of recent structure-from-motion algorithm and with simple quasi image processing provides a stable segmentation with intrinsic noise of several per cent in the optical flow. The method is suitable for implementation on parallel architectures.     

Globally optimal grouping for symmetric closed boundaries by combining boundary and region information

Many natural and man-made structures have a boundary that shows a certain level of bilateral symmetry, a property that plays an important role in both human and computer vision. In this paper, we present a new grouping method for detecting closed boundaries with symmetry. We first construct a new type of grouping token in the form of symmetric trapezoids by pairing line segments detected from the image. A closed boundary can then be achieved by connecting some trapezoids with a sequence of gap-filling quadrilaterals. For such a closed boundary, we define a unified grouping cost function in a ratio form: the numerator reflects the boundary information of proximity and symmetry and the denominator reflects the region information of the enclosed area. The introduction of the region-area information in the denominator is able to avoid a bias toward shorter boundaries. We then develop a new graph model to represent the grouping tokens. In this new graph model, the grouping cost function can be encoded by carefully designed edge weights and the desired optimal boundary corresponds to a special cycle with a minimum ratio-form cost. We finally show that such a cycle can be found in polynomial time using a previous graph algorithm. We implement this symmetry-grouping method and test it on a set of synthetic data and real images. The performance is compared to two previous grouping methods that do not consider symmetry in their grouping cost functions.     

A hybrid computer-aided linkage design system for tracing open and closed planar curves

This paper presents a computer-aided linkage design system for tracing prescribed open or closed planar curves. The mechanism design is considered a mixture of science and art. The former is about utilizing computers to rigorously size a mechanism in meeting a set of design requirements and the latter is about taking advantage of designers’ experience to narrow down the design domain and speed up the design process. The ultimate goal of the presented design system is to incorporate both science and art into the linkage design process by (1) developing an automatic design framework that is based on library searching and optimization techniques and (2) developing an interactive design framework that is based on advanced human–computer interfaces. To enable the design automation framework, we first pre-built a library of open and closed planar curves generated by commonly used planar linkages. We then turned the classical linkage path generation problem into a library searching problem together with a local optimization problem. To enable the interactive design framework, we developed a set of design interfaces that facilitate designers to intervene and steer the design process. This hybrid design system was developed based on our existing VRMDS (Virtual Reality Mechanism Design Studio) framework. To demonstrate its functionalities, we provided four representative design cases of 4-bar and crank-slider linkages. The result shows that the system returned a desired solution in seconds. We also demonstrate the extensibility of the system by implementing designs of planar 4-bar and crank-slider linkages.     

A new instantaneous center analysis methodology for planar closed chains via graphical representation

Instantaneous center (IC) analysis of a mechanism is very important in mechanism analysis, since the analysis gives intuition about the global movement of the mechanism, and the analysis also makes the numerical analysis of velocities faster. Previous IC analysis methods have used geometrical information from the mechanism configuration. Such methods have disadvantages of complexity in calculation and difficulty determining the direction of linkage movement due to geometric complexity. This research suggests a new IC analysis method for planar closed chains. The proposed method determines the IC simply from the relation between joint velocities based on graphical representation. Twists in screw theory are used to define the joint velocities in a closed chain and also to calculate the IC. Three different kinds of mechanisms are analyzed by the method: a four-bar mechanism, slidercrank mechanism, and a multiple closed-chain mechanism composed of four-bar and slider-crank mechanisms. The analysis methodology can be applied to calculate the ICs of various planar closed chains.     

An efficient, accurate approach to medial axis transforms of pockets with closed free-form boundaries

Medial axis transform of a pocket with free-form closed boundaries is a completed, compact representation of the pocket geometric shape and topology. It is very useful to multiple cutters selection and their tool paths generation for CNC machining of complex pockets. In the past decades, much research has been successfully conducted on the topic of finding the medial axis of a shape domain bounded with a polygon or simple geometries, e.g., lines and circles. Currently, more pockets with free-form boundaries are adopted in mechanical parts; however, the prior medial axis generation methods cannot handle this type of pockets well, resulting in long computation time and low medial axis accuracy. To address this problem, an efficient, accurate approach to calculating the medial axis transforms of these pockets is proposed in this work. An original optimization model of bisectors is established, and a new optimization method—the hybrid global optimization method—is developed to efficiently and accurately solve the optimization model of bisectors. The new optimization model and solver have been applied to many examples, and the testing results have demonstrated the advantages of this innovative approach over the prior medial axis methods. It can be an effective solution to the medial axis transforms of complex pockets.     

Novel image encryption/decryption based on quantum Fourier transform and double phase encoding

A novel gray-level image encryption/decryption scheme is proposed, which is based on quantum Fourier transform and double random-phase encoding technique. The biggest contribution of our work lies in that it is the first time that the double random-phase encoding technique is generalized to quantum scenarios. As the encryption keys, two phase coding operations are applied in the quantum image spatial domain and the Fourier transform domain respectively. Only applying the correct keys, the original image can be retrieved successfully. Because all operations in quantum computation must be invertible, decryption is the inverse of the encryption process. A detailed theoretical analysis is given to clarify its robustness, computational complexity and advantages over its classical counterparts. It paves the way for introducing more optical information processing techniques into quantum scenarios.