Edge detection of noisy images based on cellular neural networks

This paper studies a technique employing both cellular neural networks (CNNs) and linear matrix inequality (LMI) for edge detection of noisy images. Our main work focuses on training templates of noise reduction and edge detection CNNs. Based on the Lyapunov stability theorem, we derive a criterion for global asymptotical stability of a unique equilibrium of the noise reduction CNN. Then we design an approach to train edge detection templates, and this approach can detect the edge precisely and efficiently, i.e., by only one iteration. Finally, we illustrate performance of the proposed methodology from the aspect of peak signal to noise ratio (PSNR) through computer simulations. Moreover, some comparisons are also given to prove that our method outperforms classical operators in gray image edge detection.     

Fuzzy based directional weighted median filter for impulse noise detection and reduction

The known median-based denoising methods tends to work well for restoring the images corrupted by random-valued impulse noise with low noise level, but it fails in denoising highly corrupted images. In this paper, a new noise reduction method based on directional weighted median based fuzzy impulse noise detection and reduction method (DWMFIDRM) has been proposed, which has been specially developed for denoising all categories of impulse noise. The contribution of this paper is threefold. The main contribution of the novel impulse noise reduction technique lies in the unification of three different methods; the impulse noise detection phase utilizing the concept of fuzzy gradient values, edge-preserving noise reduction phase based on the directional weighted median of the neighboring pixels and a final filtering step in order to deal with noisy pixels of non-zero degree. Such a unique combination has improved the efficiency of this method for high density noise removal. The experimental results of our proposed method have a significant improvement when compared to other existing filters for high density noise removal. This paper utilizes the concept of fuzzy gradient values. The noise reduction phase that preserves edge sharpness is based on the directional weighted median of neighboring pixels. Final filtering phase is performed only when there is non-zero degree of noise pixels. This phase makes our method more efficient in high noise density. Experimental results show that DWMFIDRM provides a significant improvement on other existing filters.     

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.     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

Adaptive Sequential Monte Carlo for Multiple Changepoint Analysis

Process monitoring and control requires the detection of structural changes in a data stream in real time. This article introduces an efficient sequential Monte Carlo algorithm designed for learning unknown changepoints in continuous time. The method is intuitively simple: new changepoints for the latest window of data are proposed by conditioning only on data observed since the most recent estimated changepoint, as these observations carry most of the information about the current state of the process. The proposed method shows improved performance over the current state of the art. Another advantage of the proposed algorithm is that it can be made adaptive, varying the number of particles according to the apparent local complexity of the target changepoint probability distribution. This saves valuable computing time when changes in the changepoint distribution are negligible, and enables rebalancing of the importance weights of existing particles when a significant change in the target distribution is encountered. The plain and adaptive versions of the method are illustrated using the canonical continuous time changepoint problem of inferring the intensity of an inhomogeneous Poisson process, although the method is generally applicable to any changepoint problem. Performance is demonstrated using both conjugate and nonconjugate Bayesian models for the intensity. Appendices to the article are available online, illustrating the method on other models and applications.     

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.     

An algorithm for computing the eigenvalues of block companion matrices

In this paper we propose a method for computing the roots of a monic matrix polynomial. To this end we compute the eigenvalues of the corresponding block companion matrix C. This is done by implementing the QR algorithm in such a way that it exploits the rank structure of the matrix. Because of this structure, we can represent the matrix in Givens-weight representation. A similar method as in Chandrasekaran et al. (Oper Theory Adv Appl 179:111–143, 2007), the bulge chasing, is used during the QR iteration. For practical usage, matrix C has to be brought in Hessenberg form before the QR iteration starts. During the QR iteration and the transformation to Hessenberg form, the property of the matrix being unitary plus low rank numerically deteriorates. A method to restore this property is used.     

An efficient algorithm for sparse null space basis problem using ABS methods

We propose a way to use the Markowitz pivot selection criterion for choosing the parameters of the extended ABS class of algorithms to present an effective algorithm for generating sparse null space bases. We explain in detail an efficient implementation of the algorithm, making use of the special MATLAB 7.0 functions for sparse matrix operations and the inherent efficiency of the ANSI C programming language. We then compare our proposed algorithm with an implementation of an efficient algorithm proposed by Coleman and Pothen with respect to the computing time and the accuracy and the sparsity of the generated null space bases. Our extensive numerical results, using coefficient matrices of linear programming problems from the NETLIB set of test problems show the competitiveness of our implemented algorithm.     

Enumeration of connected invariant graphs

Let h be a finite group acting on unlabeled graphs which does not change connectivity. Examples include edge reversal in directed graphs and permutations of colors in edge and/or vertex colored graphs. The generating functions of h-invariant (directed) graphs and h-invariant (weakly) connected (directed) graphs are discussed. This leads to a recursive formula for calculating the number of connected graphs when the total number of graphs is known. This is then applied to self-dual signed graphs, self-converse digraphs, and color cyclic graphs. Asymptotic expansions are also obtained. As expected, almost all of the above h-invariant graphs are connected and the asymptotic number of disconnected graphs has a simple interpretation.     

Game-perfect digraphs

In the A-coloring game, two players, Alice and Bob, color uncolored vertices of a given uncolored digraph D with colors from a given color set C, so that, at any time a vertex is colored, its color has to be different from the colors of its previously colored in-neighbors. Alice begins. The players move alternately, where a move of Bob consists in coloring a vertex, and a move of Alice in coloring a vertex or missing the turn. The game ends when Bob is unable to move. Alice wins if every vertex is colored at the end, otherwise Bob wins. This game is a variant of a graph coloring game proposed by Bodlaender (Int J Found Comput Sci 2:133?C147, 1991). The A-game chromatic number of D is the smallest cardinality of a color set C, so that Alice has a winning strategy for the game played on D with C. A digraph is A-perfect if, for any induced subdigraph H of D, the A-game chromatic number of H equals the size of the largest symmetric clique of H. We characterize some basic classes of A-perfect digraphs, in particular all A-perfect semiorientations of paths and cycles. This gives us, as corollaries, similar results for other games, in particular concerning the digraph version of the usual game chromatic number.     

A faster LU decomposition for parallelC programs

This report introduces a faster parallel LU decomposition algorithm that gives a speedup almost equal to the number of nodes used. The new algorithm takes an advantage of an importantC feature that lays out a matrix using a row major scheme and is based on the currently widely used LU decomposition algorithm with one major modification to eliminate most of the communication overhead. Empirical results are included in this report. For example, solving a dense matrix that contains 100,000,000 elements gives a speedup of 50 when executed on 50 nodes of an Intel Paragon in parallel.     

A Subpixel Image Restoration Algorithm

Abstract

In statistical image reconstruction, data are often recorded on a regular grid of squares, known as pixels, and the reconstructed image is defined on the same pixel grid. Thus, the reconstruction of a continuous planar image is piecewise constant on pixels, and boundaries in the image consist of horizontal and vertical edges lying between pixels. This approximation to the true boundary can result in a loss of information that may be quite noticeable for small objects, only a few pixels in size. Increasing the resolution of the sensor may not be a practical alternative. If some prior assumptions are made about the true image, however, reconstruction to a greater accuracy than that of the recording sensor's pixel grid is possible. We adopt a Bayesian approach, incorporating prior information about the true image in a stochastic model that attaches higher probability to images with shorter total edge length. In reconstructions, pixels may be of a single color or split between two colors. The model is illustrated using both real and simulated data.     

Adaptive extended isogeometric analysis based on PHT-splines for thin cracked plates and shells with Kirchhoff–Love theory

In this paper, a posteriori error estimation and mesh adaptation approach for thin plate and shell structures of through-the-thickness crack is presented. This method uses the extended isogeometric analysis (XIGA) based on PHT-splines (Polynomial splines over Hierarchical T-meshes), which is abbreviated as XIGA-PHT. In XIGA-PHT, the isogeometric displacement approximation is locally enriched with enrichment functions, which efficiently capture the displacement discontinuity across the crack face as well as the stress singularity in the vicinity of the crack tip. On the one hand, the rotational degrees of freedom (RDOFs) are not required in Kirchhoff–Love theory, which drastically reduces the complexity of enrichment mode and computational scale for crack analysis. On the other hand, the PHT-splines basis functions can automatically satisfy the requirement of C¹-continuity for the Kirchhoff–Love theory. Moreover, the PHT-splines facilitate the local refinement, which is the deficiency of NURBS-based isogeometric formulations. The local refinement is highly suitable for adaptive analysis. The stress recovery-based posteriori error estimator combined with the superconvergent patch recovery (SPR) technique is used to evaluate the approximate local discretization error. A new strategy for selecting enriched recovered functions in the enriched areas was proposed. Special functions extracted from the asymptotic stress solutions are applied to obtain the recovered stress field in the enriched area. The results of stress intensity factors or J-integral values obtained by the adaptive XIGA-PHT are compared with reference solutions. Several thin plate and shell illustrative examples demonstrate the effectiveness and accuracy of the proposed adaptive XIGA-PHT.     

A DC optimization-based clustering technique for edge detection

We introduce a method for edge detection which is based on clustering the pixels representing any given digital image into two sets (the edge pixels and the non-edge ones). The process is based on associating to each pixel an appropriate vector representing the differences in brightness w.r.t. the surrounding pixels. Clustering is driven by the norms of such vectors, thus it takes place in \(\mathbb {R}\), which allows us to use a (simple) DC (Difference of Convex) optimization algorithm to get the clusters. A novel thinning technique, based on calculation of the edge phase angles, refines the classification obtained by the clustering algorithm. The results of some numerical experiments are also provided.     

<Emphasis Type="Italic">C</Emphasis><Superscript>0</Superscript>IPG adaptive algorithms for the biharmonic eigenvalue problem

This paper focuses on C ⁰IPG adaptive algorithms for the biharmonic eigenvalue problem with the clamped boundary condition. We prove the reliability and efficiency of the a posteriori error indicator of the approximating eigenfunctions and analyze the reliability of the a posteriori error indicator of the approximating eigenvalues. We present two adaptive algorithms, and numerical experiments indicate that both algorithms are efficient.     

Online identification of Takagi–Sugeno fuzzy models based on self-adaptive hierarchical particle swarm optimization algorithm

This paper presents an approach for online learning of Takagi–Sugeno (T-S) fuzzy models. A novel learning algorithm based on a Hierarchical Particle Swarm Optimization (HPSO) is introduced to automatically extract all fuzzy logic system (FLS)’s parameters of a T–S fuzzy model. During online operation, both the consequent parameters of the T–S fuzzy model and the PSO inertia weight are continually updated when new data becomes available. By applying this concept to the learning algorithm, a new type T–S fuzzy modeling approach is constructed where the proposed HPSO algorithm includes an adaptive procedure and becomes a self-adaptive HPSO (S-AHPSO) algorithm usable in real-time processes. To improve the computational time of the proposed HPSO, particles positions are initialized by using an efficient unsupervised fuzzy clustering algorithm (UFCA). The UFCA combines the K-nearest neighbour and fuzzy C-means methods into a fuzzy modeling method for partitioning of the input–output data and identifying the antecedent parameters of the fuzzy system, enhancing the HPSO’s tuning. The approach is applied to identify the dynamical behavior of the dissolved oxygen concentration in an activated sludge reactor within a wastewater treatment plant. The results show that the proposed approach can identify nonlinear systems satisfactorily, and reveal superior performance of the proposed methods when compared with other state of the art methods. Moreover, the methodologies proposed in this paper can be involved in wider applications in a number of fields such as model predictive control, direct controller design, unsupervised clustering, motion detection, and robotics.     

An adaptive <Emphasis Type="Italic">C</Emphasis><Superscript>0</Superscript>IPG method for the Helmholtz transmission eigenvalue problem

The interior penalty methods using C⁰ Lagrange elements (C⁰IPG) developed in the recent decade for the fourth order problems are an interesting topic in academia at present. In this paper, we discuss the adaptive fashion of C⁰IPG method for the Helmholtz transmission eigenvalue problem. We give the a posteriori error indicators for primal and dual eigenfunctions, and prove their reliability and efficiency. We also give the a posteriori error indicator for eigenvalues and design a C⁰IPG adaptive algorithm. Numerical experiments show that this algorithm is efficient and can get the optimal convergence rate.     

Multithread parallelization of Lepp-bisection algorithms

Longest edge (nested) algorithms for triangulation refinement in two dimensions are able to produce hierarchies of quality and nested irregular triangulations as needed both for adaptive finite element methods and for multigrid methods. They can be formulated in terms of the longest edge propagation path (Lepp) and terminal edge concepts, to refine the target triangles and some related neighbors. We discuss a parallel multithread algorithm, where every thread is in charge of refining a triangle t and its associated Lepp neighbors. The thread manages a changing Lepp(t) (ordered set of increasing triangles) both to find a last longest (terminal) edge and to refine the pair of triangles sharing this edge. The process is repeated until triangle t is destroyed. We discuss the algorithm, related synchronization issues, and the properties inherited from the serial algorithm. We present an empirical study that shows that a reasonably efficient parallel method with good scalability was obtained.     

Linear interpolation for image conversion between square structure and hexagonal structure

Spiral Architecture (SA) is a relatively new and powerful image structure consisting of hexagonal pixels arranged in a onedimensional coordinate system. However, all the existing hardware for capturing image and for displaying image are produced based on traditional square image structure. In this paper, we present a software approach to represent an image on SA based on linear interpolation method. We perform edge detection on SA to demonstrate the advantages of image processing on SA. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Efficient edge domination in regular graphs

An induced matching of a graph G is a matching having no two edges joined by an edge. An efficient edge dominating set of G is an induced matching M such that every other edge of G is adjacent to some edge in M. We relate maximum induced matchings and efficient edge dominating sets, showing that efficient edge dominating sets are maximum induced matchings, and that maximum induced matchings on regular graphs with efficient edge dominating sets are efficient edge dominating sets. A necessary condition for the existence of efficient edge dominating sets in terms of spectra of graphs is established. We also prove that, for arbitrary fixed p≥3, deciding on the existence of efficient edge dominating sets on p-regular graphs is NP-complete.