Abstract:
The fast marching algorithm, and its variants, solves numerically the generalized eikonal equation associated to an underlying riemannian metric. A major challenge for these algorithms is the non-isotropy of the riemannian metric. Applications of the eikonal equation to image processing often involve pronounced anisotropies, which motivated the design of new algorithms. A recently introduced variant of the fast marching algorithm addresses the problem of large anisotropies using an algebraic tool named lattice basis reduction. The numerical complexity of this algorithm is insensitive to anisotropy, under weak assumptions. We establish in this paper, in the simplified setting of a constant riemannian metric, that the accuracy of this algorithm is also extremely robust to anisotropy : in an average sense, it is independent of the anisotropy ratio. We also extend this algorithm to higher dimension.

Abstract:
"Marching of freely falling plates" is a fluid dynamics video for the Gallery of Fluid Motion submitted to APS-DFD 2011 at Baltimore Maryland. The problem of a freely falling plate is of interest in both fluid mechanics and nonlinear dynamics. The trajectory of the plate can be regular (Willmarth et al., 1964) or chaotic (Aref and Jones, 1993). As long as Reynolds number is high enough, regular flutter and tumble motion can be obtained for plates with small and large Froude numbers respectively. Belmonte et al. (1998) conducted experimental study on thin flat strips falling in a vertical cell. They categorized the Froude number at which the transition from fluttering to tumbling occurs. Andersen et al. (2005) analyzed the transitions between fluttering and tumbling using vorticity-stream function formulation and ODE dynamic equations based on quasi-steady models. They also found that the fluid circulation is mainly generated by the plate rotation and its angular velocity. However, the correlation among the plate motion, generated vortices, and aerodynamic forces is still not fully understood yet, especially in the case of multiple bodies. The DNS (Direct Numerical Simulation, Dong et al., 2006) of freely falling plates is conducted using our in-house CFD (Computational Fluid Dynamics) solver. Showcased examples in this video are a part of DNS results in the attempt to answer the above question.

Abstract:
We study the discretization of the Escape Time problem: find the length of the shortest path joining an arbitrary point of a domain, to the domain's boundary. Path length is measured locally via a Finsler metric, potentially asymmetric and strongly anisotropic. This Optimal Control problem can be reformulated as a static Hamilton Jacobi, or Anisotropic Eikonal, Partial Differential Equation, as well as a front propagation model. It has numerous applications, ranging from motion planning to image segmentation. We introduce a new algorithm, Fast Marching using Anisotropic Stencil Refinement (FM-ASR), which addresses this problem on a two dimensional domain discretized on a cartesian grid. The local stencils used in our discretization are produced by arithmetic means. The complexity of the FM-ASR, in an average sense over all grid orientations, only depends (poly-)logarithmically on the anisotropy ratio of the metric, while most alternative approaches have a polynomial dependence. Numerical experiments show, in several occasions, that the accuracy/complexity compromise is improved by an order of magnitude or more.

Abstract:
Including derivative information in the modelling of moving interfaces has been proposed as one method to increase the accuracy of numerical schemes with minimal additional cost. Here a new level set reinitialization technique using the fast marching method is presented. This augmented fast marching method will calculate the signed distance function and up to the second-order derivatives of the signed distance function for arbitrary interfaces. In addition to enforcing the condition $|\nabla\phi|^2=1$, where $\phi$ is the level set function, the method ensures that $\nabla(|\nabla\phi|)^2=0$ and $\nabla\nabla(|\nabla\phi|)^2=0$ are also satisfied. Results indicate that for both two- and three-dimensional interfaces the resulting level set and curvature field are smooth even for coarse grids. Convergence results show that using first-order upwind derivatives and the augmented fast marching method result in a second-order accurate level set and gradient field and a first-order accurate curvature field.

Abstract:
One of the most popular methods to solve a time-domain integral equation (TDIE) is the marching-on in time (MOT) method. Recently, a new method called marching-on in degree (MOD) that uses Laguerre polynomials as temporal basis functions has been developed to eliminate the late time instability of the MOT method. The use of an entire domain basis for the time variable eliminates the requirement of a Courant condition, as there is no time variable involved in the field calculation. This is possible as in the procedure the time and the space variables can be separated analytically. A comparison is presented between these two methods from the standpoint of formulation, stability, cost, and accuracy. Numerical results are presented to illustrate these features in the comparison.

Abstract:
We propose a Fast Marching based implementation for computing sub-Riemanninan (SR) geodesics in the roto-translation group SE(2), with a metric depending on a cost induced by the image data. The key ingredient is a Riemannian approximation of the SR-metric. Then, a state of the art Fast Marching solver that is able to deal with extreme anisotropies is used to compute a SR-distance map as the solution of a corresponding eikonal equation. Subsequent backtracking on the distance map gives the geodesics. To validate the method, we consider the uniform cost case in which exact formulas for SR-geodesics are known and we show remarkable accuracy of the numerically computed SR-spheres. We also show a dramatic decrease in computational time with respect to a previous PDE-based iterative approach. Regarding image analysis applications, we show the potential of considering these data adaptive geodesics for a fully automated retinal vessel tree segmentation.

Abstract:
In this paper we give the first method for constructing n-multimagic squares (and hypercubes) for any n. We give an explicit formula in the case of squares and an effective existence proof in the higher dimensional case. Finally we prove that n-multimagic squares do not exist for certain orders.

Abstract:
The fast marching algorithm computes an approximate solution to the eikonal equation in O(N log N) time, where the factor log N is due to the administration of a priority queue. Recently, Yatziv, Bartesaghi and Sapiro have suggested to use an untidy priority queue, reducing the overall complexity to O(N) at the price of a small error in the computed solution. In this paper, we give an explicit estimate of the error introduced, which is based on a discrete comparison principle. This estimates implies in particular that the choice of an accuracy level that is independent of the speed function F results in the complexity bound O(Fmax /Fmin N). A numerical experiment illustrates this robustness problem for large ratios Fmax /Fmin .

Abstract:
Marching Cubes(MC) algorithm is modified and improved in several aspects. The asymptotic decider algorithm is employed to solve the ambiguity problem and octree structure is used to reduce the number of polygons generated and increases the efficiency of the algorithm. The improved algorithm is applied to real geological data obtained from an iron mine in China. Experimental results demonstrate the effectiveness and efficiency of the improved algorithm in the modeling of mineral deposits.

Abstract:
Image processing in machine vision is a challenging task because often real-time requirements have to bemet in these systems. To accelerate the processing tasks in machine vision and to reduce data transferlatencies, new architectures for embedded systems in intelligent cameras are required. Furthermore,innovative processing approaches are necessary to realize these architectures efficiently. Marching Pixelsare such a processing scheme, based on Organic Computing principles, and can be applied for example todetermine object centroids in binary or gray-scale images. In this paper, we present a processing pipelinefor smart camera systems utilizing such Marching Pixel algorithms. It consists of a buffering template forimage pre-processing tasks in a FPGA to enhance captured images and an ASIC for the efficientrealization of Marching Pixel approaches. The ASIC achieves a speedup of eight for the realization ofMarching Pixel algorithms, compared to a common medium performance DSP platform.