Three Novel Edge Detection Methods for Incomplete and Noisy Spectral Data

We propose three novel methods for recovering edges in piecewise smooth functions from their possibly incomplete and noisy spectral information. The proposed methods utilize three different approaches: #1. The randomly-based sparse Inverse Fast Fourier Transform (sIFT); #2. The Total Variation-based (TV) compressed sensing; and #3. The modified zero crossing. The different approaches share a common feature: edges are identified through separation of scales. To this end, we advocate here the use of concentration kernels (Tadmor, Acta Numer. 16:305–378, 2007), to convert the global spectral data into an approximate jump function which is localized in the immediate neighborhoods of the edges. Building on these concentration kernels, we show that the sIFT method, the TV-based compressed sensing and the zero crossing yield effective edge detectors, where finitely many jump discontinuities are accurately recovered. One- and two-dimensional numerical results are presented.     

Detecting derivative discontinuity locations in piecewise continuous functions from Fourier spectral data

We present a method that uses Fourier spectral data to locate jump discontinuities in the first derivatives of functions that are continuous with piecewise smooth derivatives. Since Fourier spectral methods yield strong oscillations near jump discontinuities, it is often difficult to distinguish true discontinuities from artificial oscillations. In this paper we show that by incorporating a local difference method into the global derivative jump function approximation, we can reduce oscillations near the derivative jump discontinuities without losing the ability to locate them. We also present an algorithm that successfully locates both simple and derivative jump discontinuities. This work was partially supported by NSF grants CNS 0324957 and DMS 0510813, and NIH grant EB 02553301 (AG).     

Edge detection from truncated Fourier data using spectral mollifiers

Edge detection from a finite number of Fourier coefficients is challenging as it requires extracting local information from global data. The problem is exacerbated when the input data is noisy since accurate high frequency information is critical for detecting edges. The noise furthermore increases oscillations in the Fourier reconstruction of piecewise smooth functions, especially near the discontinuities. The edge detection method in Gelb and Tadmor (Appl Comput Harmon Anal 7:101–135, 1999, SIAM J Numer Anal 38(4):1389–1408, 2000) introduced the idea of “concentration kernels” as a way of converging to the singular support of a piecewise smooth function. The kernels used there, however, and subsequent modifications to reduce the impact of noise, were generally oscillatory, and as a result oscillations were always prevalent in the neighborhoods of the jump discontinuities. This paper revisits concentration kernels, but insists on uniform convergence to the “sharp peaks” of the function, that is, the edge detection method converges to zero away from the jumps without introducing new oscillations near them. We show that this is achievable via an admissible class of spectral mollifiers. Our method furthermore suppresses the oscillations caused by added noise.     

A Nonparametric Procedure to Detect Jumps in Regression Surfaces

This article proposes a local smoothing procedure for detecting jump location curves of regression surfaces. This procedure simplifies the computation of some existing jump detectors in the statistical literature. It also generalizes the Sobel edge detector in the image processing literature such that more observations can be used to smooth away random noise in the data. The problem to evaluate the performance of jump detectors is discussed and a new measurement of jump detection performance is suggested.     

Using Conventional Edge Detectors and Postsmoothing for Segmentation of Spotted Microarray Images

Segmentation of spotted microarray images is important in generating gene expression data. It aims to distinguish foreground pixels from background pixels for a given spot of a microarray image. Edge detection in the image processing literature is a closely related research area, because spot boundary curves separating foregrounds from backgrounds in a microarray image can be treated as edges. However, for generating gene expression data, segmentation methods for handling spotted microarray images are required to classify each pixel as either a foreground or a background pixel; most conventional edge detectors in the image processing literature do not have this classification property, because their detected edge pixels are often scattered in the whole design space and consequently the foreground or background pixels are not defined. In this article, we propose a general postsmoothing procedure for estimating spot boundary curves from the detected edge pixels of conventional edge detectors, such that these conventional edge detectors together with the proposed postsmoothing procedure can be used for segmentation of spotted microarray images. Numerical studies show that this proposal works well in applications.

Datasets and computer code are available in the online supplements.     

Iterative adaptive RBF methods for detection of edges in two-dimensional functions

Radial basis functions have gained popularity for many applications including numerical solution of partial differential equations, image processing, and machine learning. For these applications it is useful to have an algorithm which detects edges or sharp gradients and is based on the underlying basis functions. In our previous research, we proposed an iterative adaptive multiquadric radial basis function method for the detection of local jump discontinuities in one-dimensional problems. The iterative edge detection method is based on the observation that the absolute values of the expansion coefficients of multiquadric radial basis function approximation grow exponentially in the presence of a local jump discontinuity with fixed shape parameters but grow only linearly with vanishing shape parameters. The different growth rate allows us to accurately detect edges in the radial basis function approximation. In this work, we extend the one-dimensional iterative edge detection method to two-dimensional problems. We consider two approaches: the dimension-by-dimension technique and the global extension approach. In both cases, we use a rescaling method to avoid ill-conditioning of the interpolation matrix. The global extension approach is less efficient than the dimension-by-dimension approach, but is applicable to truly scattered two-dimensional points, whereas the dimension-by-dimension approach requires tensor product grids. Numerical examples using both approaches demonstrate that the two-dimensional iterative adaptive radial basis function method yields accurate results.     

Detection of Edges from Nonuniform Fourier Data

Edge detection is important in a variety of applications. While there are many algorithms available for detecting edges from pixelated images or equispaced Fourier data, much less attention has been given to determining edges from nonuniform Fourier data. There are applications in sensing (e.g. MRI) where the data is given in this way, however. This paper introduces a method for determining the locations of jump discontinuities, or edges, in a one-dimensional periodic piecewise-smooth function from nonuniform Fourier coefficients. The technique employs the use of Fourier frames. Numerical examples are provided.     

A Well-Conditioned,Nonconforming Nitsche's Extended Finite Element Method for Elliptic Interface Problems

In this paper, we introduce a nonconforming Nitsche's extended finite element method (NXFEM) for elliptic interface problems on unfitted triangulation elements. The solution on each side of the interface is separately expanded in the standard nonconforming piecewise linear polynomials with the edge averages as degrees of freedom. The jump conditions on the interface and the discontinuities on the cut edges (the segment of edges cut by the interface) are weakly enforced by the Nitsche's approach. In the method, the harmonic weighted fluxes are used and the extra stabilization terms on the interface edges and cut edges are added to guarantee the stability and the well conditioning. We prove that the convergence order of the errors in energy and $L^2$ norms are optimal. Moreover, the errors are independent of the position of the interface relative to the mesh and the ratio of the discontinuous coefficients. Furthermore, we prove that the condition number of the system matrix is independent of the interface position. Numerical examples are given to confirm the theoretical results.     

Subgraph distances in graphs defined by edge transfers

For two edge-induced subgraphs F and H of the same size in a graph G, the subgraph H can be obtained from F by an edge jump if there exist four distinct vertices u, v, w, and x in G such that uv ε E(F), wx ε E(G) - E(F), and H = F - uv + wx. The subgraph F is j-transformed into H if H can be obtained from F by a sequence of edge jumps. Necessary and sufficient conditions are presented for a graph G to have the property that every edge-induced subgraph of a fixed size in G can be j-transformed into every other edge-induced subgraph of that size. The minimum number of edge jumps required to transform one subgraph into another is called the jump distance. This distance is a metric and can be modeled by a graph. The jump graph J(G) of a graph G is defined as that graph whose vertices are the edges of G and where two vertices of J(G) are adjacent if and only if the corresponding edges of G are independent. For a given graph G, we consider the sequence {{J^k(G)}} of iterated jump graphs and classify each graph as having a convergent, divergent, or terminating sequence.     

Adaptive Mollifiers for High Resolution Recovery of Piecewise Smooth Data from its Spectral Information

We discuss the reconstruction of piecewise smooth data from its (pseudo-) spectral information. Spectral projections enjoy superior resolution provided the data is globally smooth, while the presence of jump discontinuities is responsible for spurious O (1) Gibbs oscillations in the neighborhood of edges and an overall deterioration of the unacceptable first-order convergence in rate. The purpose is to regain the superior accuracy in the piecewise smooth case, and this is achieved by mollification. Here we utilize a modified version of the two-parameter family of spectral mollifiers introduced by Gottlieb and Tadmor [GoTa85]. The ubiquitous one-parameter, finite-order mollifiers are based on dilation . In contrast, our mollifiers achieve their high resolution by an intricate process of high-order cancellation . To this end, we first implement a localization step using an edge detection procedure [GeTa00a, b]. The accurate recovery of piecewise smooth data is then carried out in the direction of smoothness away from the edges, and adaptivity is responsible for the high resolution. The resulting adaptive mollifier greatly accelerates the convergence rate, recovering piecewise analytic data within exponential accuracy while removing the spurious oscillations that remained in [GoTa85]. Thus, these adaptive mollifiers offer a robust, general-purpose ``black box' procedure for accurate post-processing of piecewise smooth data. March 29, 2001. Final version received: August 31, 2001.     

Viscosity solutions with shocks

A solution of single nonlinear first order equations may develop jump discontinuities even if initial data is smooth. Typical examples include a crude model equation describing some bunching phenomena observed in epitaxial growth of crystals as well as conservation laws where jump discontinuities are called shocks. Conventional theory of viscosity solutions does not apply. We introduce a notion of proper (viscosity) solutions to track whole evolutions for such equations in multi‐dimensional spaces. We establish several versions of comparison principles. We also study the vanishing viscosity method to construct a unique global proper solution at least when the evolution is monotone in time or the initial data is monotone in some sense under additional technical assumptions. In fact, we prove that the graph of approximate solutions converges to that of a proper solution in the Hausdorff distance topology. Such a convergence is also established for conservation laws with monotone data. In particular, local uniform convergence outside shocks is proved. © 2001 John Wiley & Sons, Inc.     

Wavelet transforms and edge detectors on digital images

The paper investigates the problem of locating edges on digital images. The process is completed through various mathematical transforms. The edges are found by implementing mathematical algorithms for convolutions that are adapted to locate the edges and highlights the technique on using wavelet transforms. We are especially addressing the problem of edge detection, because it has far reaching applications to all fields and especially within medicine. A patient can be diagnosed as having an aneurysm by studying an angiogram. An angiogram is the visual view of the blood vessels whereby the edges are highlighted through the implementation of edge detectors. This process can be completed through wavelet transforms and other convolution techniques.     

Mixed boundary value problems and parametrices in the edge calculus

Mixed elliptic boundary value problems are characterised by conditions which have a jump along an interface of codimension 1 on the boundary. We study such problems in weighted edge spaces and show the Fredholm property and the existence of parametrices under additional conditions of trace and potential type on the interface. We develop a new method for computing the interface conditions in terms of the index of boundary value problems in weighted spaces on infinite cones, combined with structures from the calculus of boundary value problems on a manifold with edges. This will be illustrated by the Zaremba problem and other mixed problems for the Laplace operator. The approach itself is completely general.     

On a nonlinear mean and its application to image compression using multiresolution schemes

This paper is devoted to the compression of colour images using a new nonlinear cell-average multiresolution scheme. The aim is to obtain similar compression properties as linear multiresolution schemes but eliminating the classical Gibbs phenomenon of this type of reconstructions near the edges. The algorithm is based on a nonlinear reconstruction operator (using a nonlinear trigonometric mean). The new reconstruction is third-order accurate in smooth regions and adapted to the presence of discontinuities. The data used are always centred with optimal support. Some theoretical properties of this scheme are analysed (order of approximation, convergence, elimination of Gibbs effect and stability).     

Detection of edges from spectral data: New results

We are concerned with the problem of recovering edges of piecewise smooth functions with finitely many jump discontinuities. In a series of papers, Gelb and Tadmor presented computationally simple methods for this task that are based on the conjugate Fourier series with different concentration kernels. In this article we present experimental results comparing conjugate series based methods with a new approach based on polynomial filters and suitable approximations. This new approach proves to be more accurate and stable.     

Painlevé XXXIV Asymptotics of Orthogonal Polynomials for the Gaussian Weight with a Jump at the Edge

We study the uniform asymptotics of the polynomials orthogonal with respect to analytic weights with jump discontinuities on the real axis, and the influence of the discontinuities on the asymptotic behavior of the recurrence coefficients. The Riemann–Hilbert approach, also termed the Deift–Zhou steepest descent method, is used to derive the asymptotic results. We take as an example the perturbed Gaussian weight , where θ(x) takes the value of 1 for x < 0 , and a nonnegative complex constant ω elsewhere, and as . That is, the jump occurs at the edge of the support of the equilibrium measure. The derivation is carried out in the sense of a double scaling limit, namely, and . A crucial local parametrix at the edge point where the jump occurs is constructed out of a special solution of the Painlevé XXXIV equation. As a main result, we prove asymptotic formulas of the recurrence coefficients in terms of a special Painlevé XXXIV transcendent under the double scaling limit. The special thirty‐fourth Painlevé transcendent is shown free of poles on the real axis. A consistency check is made with the reduced case when ω= 1 , namely the Gaussian weight: the polynomials in this case are the classical Hermite polynomials. A comparison is also made of the asymptotic results for the recurrence coefficients between the case when the jump happens at the edge and the case with jump inside the support of the equilibrium measure. The comparison provides a formal asymptotic approximation of the Painlevé XXXIV transcendent at positive infinity.     

Vertical and oblique fault detection in explicit surfaces

The purpose of this paper is to study the problem of detection of vertical and oblique faults in explicit surfaces. First, we characterize the finite jump discontinuities of a univariate function in terms of the divergence of sequences related to the slopes of least-squares polynomial approximations of the function. Then, we propose an algorithm to locate the finite jump discontinuities of a univariate function and its first derivative from a finite set of scattered data values of the function. As a consequence, we derive a method to detect vertical and oblique faults in explicit surfaces when the data sets are distributed along lines. We finally present some numerical and graphical examples.     

Evaluation of mixed mode stress intensity factors for interface cracks using EFGM

This paper presents the implementation of element free Galerkin method for the stress analysis of structures having cracks at the interface of two dissimilar materials. The material discontinuity at the interface has been modeled using a jump function with a jump parameter that governs its strength. The jump function enriches the approximation by the addition of special shape function that contains discontinuities in the derivative. The trial and test functions of the weak form are constructed using moving least-square interpolants in each material domain. An intrinsic enrichment criterion with enriched basis has been used to model the crack tip stress fields. The mixed mode (complex) stress intensity factors for bi-material interface cracks are numerically evaluated using the modified domain form of interaction integral. The numerical results are obtained for edge and center cracks lying at the bi-material interface, and are found to be in good agreement with the reference solutions for the interfacial crack problems.     

Boundary integral method for thermoelastic screen scattering problem in ℝ3

We investigate a three‐dimensional mathematical thermoelastic scattering problem from an open surface which will be referred to as a screen. Under the assumption of the local finite energy of the unified thermoelastic scattered field, we give a weak model on the appropriate Sobolev spaces and derive equivalent integral equations of the first kind for the jump of some trace operators on the open surface. Uniqueness and existence theorems are proved, the regularity and the singular behaviour of the solution near the edge are established with the help of the Wiener–Hopf method in the halfspace, the calculus of pseudodifferential operators on the basis of the strong ellipticity property and Gårding's inequality. An improved Galerkin scheme is provided by simulating the singular behaviour of the exact solution at the edge of the screen. Copyright © 2000 John Wiley & Sons, Ltd.     

On Local Smoothness Classes of Periodic Functions

We obtain a characterization of local Besov spaces of periodic functions in terms of trigonometric polynomial operators. We construct a sequence of operators whose values are (global) trigonometric polynomials, and yet their behavior at different points reflects the behavior of the target function near each of these points. In addition to being localized, our operators preserve trigonometric polynomials of degree commensurate with the degree of polynomials given by the operators. Our constructions are “universal;” i.e., they do not require an a priori knowledge about the smoothness of the target functions. Several numerical examples are discussed, including applications to the problem of direction finding in phased array antennas and finding the location of jump discontinuities of derivatives of different order.