A discrete expression of Canny's criteria for step edge detectorperformances evaluation

Optimal filters for edge detection are usually developed in the continuous domain and then transposed by sampling to the discrete domain. Simpler filters are directly defined in the discrete domain. We define criteria to compare filter performances in the discrete domain. Canny has defined (1983, 1986) three criteria to derive the equation of an optimal filter for step edge detection: good detection, good localization, and low-responses multiplicity. These criteria seem to be good candidates for filter comparison. Unfortunately, they have been developed in the continuous domain, and their analytical expressions cannot be used in the discrete domain. We establish three criteria with the same meaning as Canny's. Some comparisons with experimental results confirm the validity of our approach. This study highlights the existence of two classes of derivative operators that are distinguished by whether or not the impulse response of the filter in continuous space domain is continuous on its center. These classes exhibit very different properties for the second and third criteria. We extend the use of the first and third criteria to the smoothing filters. We also define an optimal continuous filter according to the continuous third criterion and an optimal discrete filter according to the discrete third criterion. We compare the performances of the sampled version of the continuous filter to those of the optimal discrete filter     

Robust image corner detection through curvature scale space

This paper describes a novel method for image corner detection based on the curvature scale-space (CSS) representation. The first step is to extract edges from the original image using a Canny detector (1986). The corner points of an image are defined as points where image edges have their maxima of absolute curvature. The corner points are detected at a high scale of the CSS and tracked through multiple lower scales to improve localization. This method is very robust to noise, and we believe that it performs better than the existing corner detectors An improvement to Canny edge detector's response to 45° and 135° edges is also proposed. Furthermore, the CSS detector can provide additional point features (curvature zero-crossings of image edge contours) in addition to the traditional corners     

Orientation-Matching Minimization for Image Denoising and Inpainting

In this paper, we propose an orientation-matching functional minimization for image denoising and image inpainting. Following the two-step TV-Stokes algorithm (Rahman et al. in Scale space and variational methods in computer vision, pp. 473–482, Springer, Heidelberg, 2007; Tai et al. in Image processing based on partial differential equations, pp. 3–22, Springer, Heidelberg, 2006; Bertalmio et al. in Proc. conf. comp. vision pattern rec., pp. 355–362, 2001), a regularized tangential vector field with zero divergence condition is first obtained. Then a novel approach to reconstruct the image is proposed. Instead of finding an image that fits the regularized normal direction from the first step, we propose to minimize an orientation matching cost measuring the alignment between the image gradient and the regularized normal direction. This functional yields a new nonlinear partial differential equation (PDE) for reconstructing denoised and inpainted images. The equation has an adaptive diffusivity depending on the orientation of the regularized normal vector field, providing reconstructed images which have sharp edges and smooth regions. The additive operator splitting (AOS) scheme is used for discretizing Euler-Lagrange equations. We present the results of various numerical experiments that illustrate the improvements obtained with the new functional.     

A Zero-Crossing-Based Optimal Three-Dimensional Edge Detector

Three-dimensional (3D) image processing and interpretation is very important in many medical and industrial applications. Detection of 3D boundaries is an essential step in most of the 3D image analysis tasks. In this paper a new computational approach to 3D edge detection is proposed. Optimality criteria such as signal-to-noise ratio, localization, and spurious response for zero-crossing-based, rotationally invariant 3D step edge detectors are derived. An optimal 3D step edge detector is obtained by optimizing a penalty function which combines all the three criteria. The closed form solution to the optimization problem yields the optimal detector. The detector is the Laplacian of a rotationally invariant function, which has a finite spatial support. The behavior of the proposed detector is theoretically analyzed and compared to that of the 3D Laplacian of Gaussian detector. Experimental results with some synthetic and real images are presented.     

A computational approach to edge detection

This paper describes a computational approach to edge detection. The success of the approach depends on the definition of a comprehensive set of goals for the computation of edge points. These goals must be precise enough to delimit the desired behavior of the detector while making minimal assumptions about the form of the solution. We define detection and localization criteria for a class of edges, and present mathematical forms for these criteria as functionals on the operator impulse response. A third criterion is then added to ensure that the detector has only one response to a single edge. We use the criteria in numerical optimization to derive detectors for several common image features, including step edges. On specializing the analysis to step edges, we find that there is a natural uncertainty principle between detection and localization performance, which are the two main goals. With this principle we derive a single operator shape which is optimal at any scale. The optimal detector has a simple approximate implementation in which edges are marked at maxima in gradient magnitude of a Gaussian-smoothed image. We extend this simple detector using operators of several widths to cope with different signal-to-noise ratios in the image. We present a general method, called feature synthesis, for the fine-to-coarse integration of information from operators at different scales. Finally we show that step edge detector performance improves considerably as the operator point spread function is extended along the edge.     

Optimal edge detection using expansion matching and restoration

Discusses the application of a newly developed expansion matching method for edge detection. Expansion matching optimizes a novel matching criterion called the discriminative signal-to-noise ratio (DSNR) and has been shown to robustly recognize templates under conditions of noise, severe occlusion and superposition. The DSNR criterion is better suited to evaluate matching in practical conditions than the traditional SNR since it considers as “noise” even the off-center response of the filter to the template itself. We introduce a family of optimal DSNR edge detectors based on the expansion filter for several edge models. For step edges, the optimal DSNR step expansion filter (SEF) is compared with the widely used Canny edge detector (CED). Experimental comparisons show that our edge detector yields better performance than the CED in terms of DSNR even under very adverse noise conditions. As for boundary detection, the SEF consistently yields higher figures of merit than the CED on a synthetic binary image over a wide range of noise levels. Results also show that the design parameters of size or width of the SEF are less critical than the CED variance. This means that a single scale of the SEF spans a larger range of input noise than a single scale of the CED. Experiments on a noisy image reveal that the SEF yields less noisy edge elements and preserves structural details more accurately. On the other hand, the CED output has better suppression of multiple responses than the corresponding SEF output     

一种基于多小波算子的复合边缘提取方法

由于光照、遮挡以及投影等因素的影响，大量自然场景图像的边缘并不表现为简单的阶跃状边缘，而是几种简单边缘的复合。复合边缘的提取和准确定位是边缘提取中的一个难点。为此，应用图像复合边缘的数学模型，从一对分别为偶对称和奇对称的多小波尺度函数出发，构造出一种对复合边缘具有零系统定位误差的多小波边缘提取算子，相应的小波函数仍然分别为偶对称和奇对称的。理论上，应用这样的多小波边缘提取算子提取图像的复合边缘可以有任意高的边缘定位精度。实验结果表明，和常用的Canny算子相比，应用本文所构造的多小波边缘提取算子提取的图像边缘失真较小，定位更加准确。     

第二小方向导数信息熵的兴趣点检测

目的 为了提高兴趣点检测的定位准确性和对噪声的鲁棒性,提出利用图像轮廓线及其邻域内像素点方向导数信息熵检测兴趣点的方法.方法 首先利用多方向Gabor虚部滤波器提取图像灰度变化信息得到第二小方向导数.然后利用Canny边缘检测器提取边缘映射,并填补断裂边缘映射提取边缘轮廓线.最后求解图像边缘轮廓线及其邻域内像素点对应的第二小方向导数所对应的信息熵归一化值并作为新的兴趣点测度.和直接由灰度变化信息及分析边缘轮廓形状或曲率提取兴趣点的方法相比,本文算法结合了两种算法的思想,利用轮廓线上及其邻域内的像素点梯度方向信息熵值作为兴趣点测度.同时不同于同质及边缘区域的梯度方向变化,兴趣点处的梯度方向变化信息呈现各向异性的特性,利用兴趣点第二小方向导数(第一小方向导数可能为零)对应的信息熵值作为新的兴趣点测度可提高算法的定位准确性.结果 通过对检测图像进行仿射变换和加入高斯噪声处理后,分别利用Harris算子、CSS算子、He&Yung算子和本文算法提取图像兴趣点,并比较各算法在仿射变换和高斯噪声情况下检测到的兴趣点的平均重复率和定位误差两个性能指标的平均值.其中本文算法的性能指标平均值为1.625,远高于Harris(3.25)、He&Yung(2.625)和CSS(2.5)三大兴趣点检测算子.结论 通过与典型的3种算法相对比,本文算法具有较好的平均重复率及噪声鲁棒性,尤其是图像在外界干扰的旋转变换和尺度变换下对兴趣点的定位性有着更好的检测性能.     

Linearly ordered semigroups for fuzzy set theory

The fuzzy set theory initiated by Zadeh (Information Control 8:338–353, 1965) was based on the real unit interval [0,1] for support of membership functions with the natural product for intersection operation. This paper proposes to extend this definition by using the more general linearly ordered semigroup structure. As Moisil (Essais sur les Logiques non Chrysippiennes. Académie des Sciences de Roumanie, Bucarest, 1972, p. 162) proposed to define Lukasiewicz logics on an abelian ordered group for truth values set, we give a simple negative answer to the question on the possibility to build a Many-valued logic on a finite abelian ordered group. In a constructive way characteristic properties are step by step deduced from the corresponding set theory to the semigroup order structure. Some results of Clifford on topological semigroups (Clifford, A.H., Proc. Amer. Math. Soc. 9:682–687, 1958; Clifford, A.H., Trans. Amer. Math. Soc. 88:80–98, 1958), Paalman de Miranda work on I-semigroups (Paalman de Miranda, A.B., Topological Semigroups. Mathematical Centre Tracts, Amsterdam, 1964) and Schweitzer, Sklar on T-norms (Schweizer, B., Sklar, A., Publ. Math. Debrecen 10:69–81, 1963; Schweizer, B., Sklar, A., Pacific J. Math. 10:313–334, 1960; Schweizer, B., Sklar, A., Publ. Math. Debrecen 8:169–186, 1961) are revisited in this framework. As a simple consequence of Faucett theorems (Proc. Amer. Math. Soc. 6:741–747, 1955), we prove how canonical properties from the fuzzy set theory point of view lead to the Zadeh choice thus giving another proof of the representation theorem of T-norms. This structural approach shall give a new perspective to tackle the question of G. Moisil about the definition of discrete Many-valued logics as approximation of fuzzy continuous ones.      

中心B样条二进小波多尺度边缘提取

分析了截尾的Canny算子在多尺度边缘提取时对运算速度造成的影响,提出了中心B样条二进小波多尺度边缘提取,详尽地研究了Canny算子与中心B样条函数的若干性质,中心B样条函数具有紧支集,以极快的速度逼近高斯函数,四阶中心B样条函数的导数比Canny算子更接近最佳边缘检测滤波器.四阶中心B样条函数是二阶平滑问题的唯一最优解,并且它的时频测不准关系值非常接近时频测不准关系下界.从对计算结果的讨论中也得出中心B样条二进小波优于Canny算子的结论.     

The Steiner Ratio Conjecture of Gilbert-Pollak May Still Be Open

We offer evidence in the disproof of the continuity of the length of minimum inner spanning trees with respect to a parameter vector having a zero component. The continuity property is the key step of the proof of the conjecture in Du and Hwang (Proc. Nat. Acad. Sci. U.S.A. 87:9464–9466, 1990; Algorithmica 7(1):121–135, 1992). Therefore the Steiner ratio conjecture proposed by Gilbert-Pollak (SIAM J. Appl. Math. 16(1):1–29, 1968) has not been proved yet. The Steiner ratio of a round sphere has been discussed in Rubinstein and Weng (J. Comb. Optim. 1:67–78, 1997) by assuming the validity of the conjecture on a Euclidean plane in Du and Hwang (Proc. Nat. Acad. Sci. U.S.A. 87:9464–9466, 1990; Algorithmica 7(1):121–135, 1992). Hence the results in Rubinstein and Weng (J. Comb. Optim. 1:67–78, 1997) have not been proved yet.     

Canny edge detection enhancement by scale multiplication

The technique of scale multiplication is analyzed in the framework of Canny edge detection. A scale multiplication function is defined as the product of the responses of the detection filter at two scales. Edge maps are constructed as the local maxima by thresholding the scale multiplication results. The detection and localization criteria of the scale multiplication are derived. At a small loss in the detection criterion, the localization criterion can be much improved by scale multiplication. The product of the two criteria for scale multiplication is greater than that for a single scale, which leads to better edge detection performance. Experimental results are presented.     

基于尺度相乘的Canny改进算法

在Canny算法框架下,对图像进行多尺度滤波分析。定义尺度乘积函数为2个不同尺度滤波器的响应乘积,由相邻尺度近似性确定乘积后的幅值和相角,再选择阈值剔除伪边缘,由非极大值抑制得到图像边缘。实验结果表明,算法比传统Canny算子在噪声抑制和边缘定位方面具有更优的性能。     

Optimal ramp edge detection using expansion matching

In practical images, ideal step edges are actually transformed into ramp edges, due to the general low pass filtering nature of imaging systems. This paper discusses the application of the expansion matching (EXM) method for optimal ramp edge detection. EXM optimizes a novel matching criterion called discriminative signal-to-noise ratio (DSNR) and has been shown to robustly recognize templates under conditions of noise, severe occlusion, and superposition. We show that our ramp edge detector performs better than the ramp detector obtained from Canny's criteria in terms of DSNR and is relatively easier to derive for various noise levels and slopes     

Simultaneous unidirectional and bidirectional chaos-based optical communication using hybrid coupling semiconductor lasers

A simultaneous unidirectional and bidirectional chaos-based optical communication scheme based on a hybrid coupling semiconductor laser system that consists of one center semiconductor laser(CSL)and multiple side semiconductor lasers(SSLs)is proposed numerically.In this scheme,the SSLs oriented in a linear chain mutually couple with the adjacent SSLs and they are subjected to identical unidirectional injections from the CSL which is a chaotic external cavity semiconductor laser.We theoretically analyze the conditions for diferent types of chaos synchronization based on the symmetry operation mechanism and injection-locking mechanism,and numerically investigate the influences of operation parameters,parameter mismatch robustness,chaos pass filtering efects and communication performance of the hybrid coupling semiconductor laser system.The simulation results demonstrate that with proper selection of the unidirectional and mutual coupling conditions,the SSLs can synchronize with each other isochronally and simultaneously synchronize to the CSL completely or laggardly,which enables the proposed system to achieve a unidirectional broadcasting communication from the CSL to the SSLs and a bidirectional communication among the SSLs simultaneously.The proposed scheme is beneficial to the implementation of optical chaos communication networks.     

Contour detection improved by frequency domain filtering of gradient image

We propose an intermediate computational step,frequency domain filtering of gradient image,to improve contour detection performance of gradient-based edge detectors.This step is inspired by analyzing the spectrum distribution of object contours and texture edges in the frequency domain of gradient image.We illustrate the principle and efect of this step by adding it to the Canny edge detector.The resulting operator can selectively retain object contours and region boundaries,and meanwhile can dramatically reduce non-meaningful elements caused by textured background.We use several types of images to compare the proposed method and other related methods qualitatively and quantitatively.Experimental results show that the proposed method can efectively enhance the contour detection of Canny edge detector and achieves similar detection performance to two other related methods but runs faster.     

All-Pairs Shortest Paths with Real Weights in <Emphasis Type="Italic">O</Emphasis>(<Emphasis Type="Italic">n</Emphasis><Superscript>3</Superscript>/log <Emphasis Type="Italic">n</Emphasis>) Time

We describe an O(n ³/log n)-time algorithm for the all-pairs-shortest-paths problem for a real-weighted directed graph with n vertices. This slightly improves a series of previous, slightly subcubic algorithms by Fredman (SIAM J. Comput. 5:49–60, 1976), Takaoka (Inform. Process. Lett. 43:195–199, 1992), Dobosiewicz (Int. J. Comput. Math. 32:49–60, 1990), Han (Inform. Process. Lett. 91:245–250, 2004), Takaoka (Proc. 10th Int. Conf. Comput. Comb., Lect. Notes Comput. Sci., vol. 3106, pp. 278–289, Springer, 2004), and Zwick (Proc. 15th Int. Sympos. Algorithms and Computation, Lect. Notes Comput. Sci., vol. 3341, pp. 921–932, Springer, 2004). The new algorithm is surprisingly simple and different from previous ones. A preliminary version of this paper appeared in Proc. 9th Workshop Algorithms Data Struct. (WADS), Lect. Notes Comput. Sci., vol. 3608, pp. 318–324, Springer, 2005.     

The canny detector with edge region focusing using an anisotropic diffusion process

This paper proposes a methodology for edge detection in digital images using the Canny detector, but associated with a priori edge structure focusing by a nonlinear anisotropic diffusion via the partial differential equation (PDE). This strategy aims at minimizing the effect of the well-known duality of the Canny detector, under which is not possible to simultaneously enhance the insensitivity to image noise and the localization precision of detected edges. The process of anisotropic diffusion via thePDE is used to a priori focus the edge structure due to its notable characteristic in selectively smoothing the image, leaving the homogeneous regions strongly smoothed and mainly preserving the physical edges, i.e., those that are actually related to objects presented in the image. The solution for the mentioned duality consists in applying the Canny detector to a fine gaussian scale but only along the edge regions focused by the process of anisotropic diffusion via the PDE. The results have shown that the method is appropriate for applications involving automatic feature extraction, since it allowed the high-precision localization of thinned edges, which are usually related to objects present in the image.     

A high performance edge detector based on fuzzy inference rules

Edge detection is an important topic in computer vision and image processing. In this paper, a novel edge detector based on fuzzy If-Then inference rules and edge continuity is proposed. The fuzzy If-Then rule system is designed to model edge continuity criteria. The maximum entropy principle is used in the parameter adjusting process. We also discuss the related issues in designing fuzzy edge detectors. We compare it with the popular edge detectors: Sobel and Canny edge detectors. The proposed fuzzy edge detector does not need parameter setting as Canny edge detector does, and it can preserve an appropriate detection in details. It is very robust to noise and can work well under high level noise situations, while other edge detectors cannot. The detector efficiently extracts edges in images corrupted by noise without requiring the filtering process. The experimental results demonstrate the superiority of the proposed method to existing ones.