Topographic mapping in planetary environments relies on accurate 3D scan registration methods. However, most global registration algorithms relying on features such as FPFH and Harris-3D show poor alignment accuracy in these settings due to the poor structure of the Mars-like terrain and variable resolution, occluded, sparse range data that is hard to register without some a-priori knowledge of the environment. In this paper, we propose an alternative approach to 3D scan registration using the curvelet transform that performs multi-resolution geometric analysis to obtain a set of coefficients indexed by scale (coarsest to finest), angle and spatial position. Features are detected in the curvelet domain to take advantage of the directional selectivity of the transform. A descriptor is computed for each feature by calculating the 3D spatial histogram of the image gradients, and nearest neighbor based matching is used to calculate the feature correspondences. Correspondence rejection using Random Sample Consensus identifies inliers, and a locally optimal Singular Value Decomposition-based estimation of the rigid-body transformation aligns the laser scans given the re-projected correspondences in the metric space. Experimental results on a publicly available data-set of planetary analogue indoor facility, as well as simulated and real-world scans from Neptec Design Group's IVIGMS 3D laser rangefinder at the outdoor CSA Mars yard demonstrates improved performance over existing methods in the challenging sparse Mars-like terrain.
Frequency-domain based approaches decouple the problem of finding rotation and translation transformation parameters and attempt to find a suitable registration in the transformed domain @cite_17 @cite_50 @cite_26 . Phase correlation is typically employed for matching which is robust to the effects of noise and occlusions, while fast Fourier transforms (FFT) used to compute cross-correlations makes this approach computationally efficient. However, the Fourier transform can only retrieve the global frequency content of the signal and provides a dense representation of the underlying signal.
@cite_26 @cite_50 @cite_17
2084925837 2163765815 2053725563
This work introduces an original method for registering pairs of 3D views consisting of range data sets which operates in the frequency domain. The Fourier transform allows the decoupling of the estimate of the rotation parameters from the estimate of the translation parameters, our algorithm exploits this well-known property by suggesting a three-step procedure. The rotation parameters are estimated by the first two steps through convenient representations and projections of the Fourier transforms' magnitudes and the translational displacement is recovered by the third step by means of a standard phase correlation technique after compensating one of the two views for rotation. The performance of the algorithm, which is well-suited for unsupervised registration, is clearly assessed through extensive testing with several objects and shows that good and robust estimates of 3D rigid motion are achievable. Our algorithm can be used as a prealignment tool for more accurate space-domain registration techniques, like the ICP algorithm. We present an algorithm that detects rotational and reflectional symmetries of two-dimensional objects. Both symmetry types are effectively detected and analyzed using the angular correlation (AC), which measures the correlation between images in the angular direction. The AC is accurately computed using the pseudopolar Fourier transform, which rapidly computes the Fourier transform of an image on a near-polar grid. We prove that the AC of symmetric images is a periodic signal whose frequency is related to the order of the symmetry. This frequency is recovered via spectrum estimation, which is a proven technique in signal processing with a variety of efficient solutions. We also provide a novel approach for finding the center of symmetry and demonstrate the applicability of our scheme to the analysis of real images We present Spectral Registration with Multilayer Resampling (SRMR) as a 6 Degrees Of Freedom (DOF) registration method for noisy 3D data with partial overlap. The algorithm is based on decoupling 3D rotation from 3D translation by a corresponding resampling process of the spectral magnitude of a 3D Fast Fourier Transform (FFT) calculation on discretized 3D range data. The registration of all 6DOF is then subsequently carried out with spectral registrations using Phase Only Matched Filtering (POMF). There are two main aspects for the fast and robust registration of Euler angles from spherical information in SRMR. First of all, there is the permanent use of phase matching. Second, based on the FFT on a discrete Cartesian grid, not only one spherical layer but also a complete stack of layers are processed in one step. Experiments are presented with challenging datasets with respect to interference and overlap. The results include the fast and robust registration of artificially transformed data for ground-truth comparison, scans from the Stanford Bunny dataset, high end 3D laser range finder (LRF) scans of a city center, and range data from a low-cost actuated LRF in a disaster response scenario. The fast Fourier transform (FFT) is used widely in signal processing for efficient computation of the FT of finite-length signals over a set of uniformly spaced frequency locations. However, in many applications, one requires nonuniform sampling in the frequency domain, i.e., a nonuniform FT. Several papers have described fast approximations for the nonuniform FT based on interpolating an oversampled FFT. This paper presents an interpolation method for the nonuniform FT that is optimal in the min-max sense of minimizing the worst-case approximation error over all signals of unit norm. The proposed method easily generalizes to multidimensional signals. Numerical results show that the min-max approach provides substantially lower approximation errors than conventional interpolation methods. The min-max criterion is also useful for optimizing the parameters of interpolation kernels such as the Kaiser-Bessel function. We consider the problem of phase retrieval, namely, recovery of a signal from the magnitude of its Fourier transform, or of any other linear transform. Due to the loss of Fourier phase information, this problem is ill-posed. Therefore, prior information on the signal is needed in order to enable its recovery. In this work we consider the case in which the signal is known to be sparse, i.e., it consists of a small number of nonzero elements in an appropriate basis. We propose a fast local search method for recovering a sparse signal from measurements of its Fourier transform (or other linear transform) magnitude which we refer to as GESPAR: GrEedy Sparse PhAse Retrieval. Our algorithm does not require matrix lifting, unlike previous approaches, and therefore is potentially suitable for large scale problems such as images. Simulation results indicate that GESPAR is fast and more accurate than existing techniques in a variety of settings. This paper introduces an algorithm for the registration of rotated and translated volumes using the three-dimensional (3-D) pseudopolar Fourier transform, which accurately computes the Fourier transform of the registered volumes on a near-spherical 3-D domain without using interpolation. We propose a three-step procedure. The first step estimates the rotation axis. The second step computes the planar rotation relative to the rotation axis. The third step recovers the translational displacement. The rotation estimation is based on Euler's theorem, which allows one to represent a 3-D rotation as a planar rotation around a 3-D rotation axis. This axis is accurately recovered by the 3-D pseudopolar Fourier transform using radial integrations. The residual planar rotation is computed by an extension of the angular difference function to cylindrical motion. Experimental results show that the algorithm is accurate and robust to noise Abstract Image restoration applications often result in ill-posed least squares problems involving large, structured matrices. One approach used extensively is to restore the image in the frequency domain, thus providing fast algorithms using fast Fourier transforms (FFTs). This is equivalent to using a circulant approximation to a given matrix. Iterative methods may also be used effectively by exploiting the structure of the matrix. While iterative schemes are more expensive than FFT-based methods, it has been demonstrated that they are capable of providing better restorations. As an alternative, we propose an approximate singular value decomposition (SVD), which can be used in a variety of applications. Used as a direct method, the computed restorations are comparable to iterative methods but are computationally less expensive. In addition, the approximate SVD may be used with the generalized cross validation method to choose regularization parameters. It is also demonstrated that the approximate SVD can be an effective preconditioner for iterative methods. We propose a novel technique for the registration of 3D point clouds which makes very few assumptions: we avoid any manual rough alignment or the use of landmarks, displacement can be arbitrarily large, and the two point sets can have very little overlap. Crude alignment is achieved by estimation of the 3D-rotation from two Extended Gaussian Images even when the data sets inducing them have partial overlap. The technique is based on the correlation of the two EGIs in the Fourier domain and makes use of the spherical and rotational harmonic transforms. For pairs with low overlap which fail a critical verification step, the rotational alignment can be obtained by the alignment of constellation images generated from the EGIs. Rotationally aligned sets are matched by correlation using the Fourier transform of volumetric functions. A fine alignment is acquired in the final step by running Iterative Closest Points with just few iterations. A group of algorithms is presented generalizing the fast Fourier transform to the case of noninteger frequencies and nonequispaced nodes on the interval @math . The schemes of this paper are based on a combination of certain analytical considerations with the classical fast Fourier transform and generalize both the forward and backward FFTs. Each of the algorithms requires @math arithmetic operations, where @math is the precision of computations and N is the number of nodes. The efficiency of the approach is illustrated by several numerical examples. Recent compressive sensing results show that it is possible to accurately reconstruct certain compressible signals from relatively few linear measurements via solving nonsmooth convex optimization problems. In this paper, we propose the use of the alternating direction method - a classic approach for optimization problems with separable variables (D. Gabay and B. Mercier, ?A dual algorithm for the solution of nonlinear variational problems via finite-element approximations,? Computer and Mathematics with Applications, vol. 2, pp. 17-40, 1976; R. Glowinski and A. Marrocco, ?Sur lapproximation par elements finis dordre un, et la resolution par penalisation-dualite dune classe de problemes de Dirichlet nonlineaires,? Rev. Francaise dAut. Inf. Rech. Oper., vol. R-2, pp. 41-76, 1975) - for signal reconstruction from partial Fourier (i.e., incomplete frequency) measurements. Signals are reconstructed as minimizers of the sum of three terms corresponding to total variation, ?1-norm of a certain transform, and least squares data fitting. Our algorithm, called RecPF and published online, runs very fast (typically in a few seconds on a laptop) because it requires a small number of iterations, each involving simple shrinkages and two fast Fourier transforms (or alternatively discrete cosine transforms when measurements are in the corresponding domain). RecPF was compared with two state-of-the-art algorithms on recovering magnetic resonance images, and the results show that it is highly efficient, stable, and robust. The nonequispaced Fourier transform arises in a variety of application areas, from medical imaging to radio astronomy to the numerical solution of partial differential equations. In a typical problem, one is given an irregular sampling of N data in the frequency domain and one is interested in reconstructing the corresponding function in the physical domain. When the sampling is uniform, the fast Fourier transform (FFT) allows this calculation to be computed in O(N log N ) operations rather than O(N 2 ) operations. Unfortunately, when the sampling is nonuniform, the FFT does not apply. Over the last few years, a number of algorithms have been developed to overcome this limitation and are often referred to as nonuniform FFTs (NUFFTs). These rely on a mixture of interpolation and the judicious use of the FFT on an oversampled grid (A. Dutt and V. Rokhlin, SIAM J. Sci. Comput., 14 (1993), pp. 1368-1383). In this paper, we observe that one of the standard interpolation or "gridding" schemes, based on Gaussians, can be accelerated by a significant factor without precomputation and storage of the interpolation weights. This is of particular value in two- and three- dimensional settings, saving either 10 d N in storage in d dimensions or a factor of about 5-10 in CPUtime (independent of dimension). The frequencies that have been chosen to make up the scale of Western music are geometrically spaced. Thus the discrete Fourier transform (DFT), although extremely efficient in the fast Fourier transform implementation, yields components which do not map efficiently to musical frequencies. This is because the frequency components calculated with the DFT are separated by a constant frequency difference and with a constant resolution. A calculation similar to a discrete Fourier transform but with a constant ratio of center frequency to resolution has been made; this is a constant Q transform and is equivalent to a 1 24‐oct filter bank. Thus there are two frequency components for each musical note so that two adjacent notes in the musical scale played simultaneously can be resolved anywhere in the musical frequency range. This transform against log (frequency) to obtain a constant pattern in the frequency domain for sounds with harmonic frequency components has been plotted. This is compared to the conventio... Abstract In a wide range of applied problems of 2D and 3D imaging a continuous formulation of the problem places great emphasis on obtaining and manipulating the Fourier transform in Polar coordinates. However, the translation of continuum ideas into practical work with data sampled on a Cartesian grid is problematic. In this article we develop a fast high accuracy Polar FFT. For a given two-dimensional signal of size N × N , the proposed algorithm's complexity is O ( N 2 log N ) , just like in a Cartesian 2D-FFT. A special feature of our approach is that it involves only 1D equispaced FFT's and 1D interpolations. A central tool in our method is the pseudo-Polar FFT, an FFT where the evaluation frequencies lie in an oversampled set of nonangularly equispaced points. We describe the concept of pseudo-Polar domain, including fast forward and inverse transforms. For those interested primarily in Polar FFT's, the pseudo-Polar FFT plays the role of a halfway point—a nearly-Polar system from which conversion to Polar coordinates uses processes relying purely on 1D FFT's and interpolation operations. We describe the conversion process, and give an error analysis of it. We compare accuracy results obtained by a Cartesian-based unequally-sampled FFT method to ours, both algorithms using a small-support interpolation and no pre-compensating, and show marked advantage to the use of the pseudo-Polar initial grid. This correspondence discusses an extension of the well-known phase correlation technique to cover translation, rotation, and scaling. Fourier scaling properties and Fourier rotational properties are used to find scale and rotational movement. The phase correlation technique determines the translational movement. This method shows excellent robustness against random noise. This paper introduces an expectation-maximization (EM) algorithm for image restoration (deconvolution) based on a penalized likelihood formulated in the wavelet domain. Regularization is achieved by promoting a reconstruction with low-complexity, expressed in the wavelet coefficients, taking advantage of the well known sparsity of wavelet representations. Previous works have investigated wavelet-based restoration but, except for certain special cases, the resulting criteria are solved approximately or require demanding optimization methods. The EM algorithm herein proposed combines the efficient image representation offered by the discrete wavelet transform (DWT) with the diagonalization of the convolution operator obtained in the Fourier domain. Thus, it is a general-purpose approach to wavelet-based image restoration with computational complexity comparable to that of standard wavelet denoising schemes or of frequency domain deconvolution methods. The algorithm alternates between an E-step based on the fast Fourier transform (FFT) and a DWT-based M-step, resulting in an efficient iterative process requiring O(NlogN) operations per iteration. The convergence behavior of the algorithm is investigated, and it is shown that under mild conditions the algorithm converges to a globally optimal restoration. Moreover, our new approach performs competitively with, in some cases better than, the best existing methods in benchmark tests. Correlation filters take advantage of specific properties in the Fourier domain allowing them to be estimated efficiently: O(N D log D) in the frequency domain, versus O(D3 + N D2) spatially where D is signal length, and N is the number of signals. Recent extensions to correlation filters, such as MOSSE, have reignited interest of their use in the vision community due to their robustness and attractive computational properties. In this paper we demonstrate, however, that this computational efficiency comes at a cost. Specifically, we demonstrate that only 1 D proportion of shifted examples are unaffected by boundary effects which has a dramatic effect on detection tracking performance. In this paper, we propose a novel approach to correlation filter estimation that: (i) takes advantage of inherent computational redundancies in the frequency domain, (ii) dramatically reduces boundary effects, and (iii) is able to implicitly exploit all possible patches densely extracted from training examples during learning process. Impressive object tracking and detection results are presented in terms of both accuracy and computational efficiency. The theory of compressive sensing enables accurate and robust signal reconstruction from a number of measurements dictated by the signal's structure rather than its Fourier bandwidth. A key element of the theory is the role played by randomization. In particular, signals that are compressible in the time or space domain can be recovered from just a few randomly chosen Fourier coefficients. However, in some scenarios we can only observe the magnitude of the Fourier coefficients and not their phase. In this paper, we study the magnitude-only compressive sensing problem and in parallel with the existing theory derive sufficient conditions for accurate recovery. We also propose a new iterative recovery algorithm and study its performance. In the process, we develop a new algorithm for the phase retrieval problem that exploits a signal's compressibility rather than its support to recover it from Fourier transform magnitude measurements. If only a segment of a function f (t) is given, then its Fourier spectrum F( ) is estimated either as the transform of the product of f(t) with a time-limited window w(t) , or by certain techniques based on various a priori assumptions. In the following, a new algorithm is proposed for computing the transform of a band-limited function. The algorithm is a simple iteration involving only the fast Fourier transform (FFT). The effect of noise and the error due to aliasing are determined and it is shown that they can be controlled by early termination of the iteration. The proposed method can also be used to extrapolate bandlimited functions. We propose a novel discrete signal processing framework for the representation and analysis of datasets with complex structure. Such datasets arise in many social, economic, biological, and physical networks. Our framework extends traditional discrete signal processing theory to structured datasets by viewing them as signals represented by graphs, so that signal coefficients are indexed by graph nodes and relations between them are represented by weighted graph edges. We discuss the notions of signals and filters on graphs, and define the concepts of the spectrum and Fourier transform for graph signals. We demonstrate their relation to the generalized eigenvector basis of the graph adjacency matrix and study their properties. As a potential application of the graph Fourier transform, we consider the efficient representation of structured data that utilizes the sparseness of graph signals in the frequency domain. The Fourier transform of a continuous function, evaluated at frequencies expressed in polar coordinates, is an important conceptual tool for understanding physical continuum phenomena. An analogous tool, suitable for computations on discrete grids, could be very useful; however, no exact analogue exists in the discrete case. In this paper we present the notion of pseudopolar grid (pp grid) and the pseudopolar Fourier transform (ppFT), which evaluates the discrete Fourier transform at points of the pp grid. The pp grid is a type of concentric-squares grid in which the radial density of squares is twice as high as usual. The pp grid consists of equally spaced samples along rays, where different rays are equally spaced in slope rather than angle. We develop a fast algorithm for the ppFT, with the same complexity order as the Cartesian fast Fourier transform; the algorithm is stable, invertible, requires only one-dimensional operations, and uses no approximate interpolations. We prove that the ppFT is invertible and develop two algorithms for its inversion: iterative and direct, both with complexity @math , where @math is the size of the reconstructed image. The iterative algorithm applies conjugate gradients to the Gram operator of the ppFT. Since the transform is ill-conditioned, we introduce a preconditioner, which significantly accelerates the convergence. The direct inversion algorithm utilizes the special frequency domain structure of the transform in two steps. First, it resamples the pp grid to a Cartesian frequency grid and then recovers the image from the Cartesian frequency grid.