Multiscale Connected Operators

Among the major developments in Mathematical Morphology in the last two decades are the interrelated subjects of connectivity classes and connected operators. Braga-Neto and Goutsias have proposed an extension of the theory of connectivity classes to a multiscale setting, whereby one can assign connectivity to an object observed at different scales. In this paper, we study connected operators in the context of multiscale connectivity. We propose the notion of a -connected operator, that is, an operator connected at scale . We devote some attention to the study of binary -grain operators. In particular, we show that families of -grain openings and -grain closings, indexed by the connectivity scale parameter, are granulometries and anti-granulometries, respectively. We demonstrate the use of multiscale connected operators with image analysis applications. The first is the scale-space representation of grayscale images using multiscale levelings, where the role of scale is played by the connectivity scale. Then we discuss the application of multiscale connected openings in granulometric analysis, where both size and connectivity information are summarized. Finally, we describe an application of multiscale connected operators to an automatic target recognition problem.Ulisses Braga-Neto received the Baccalaureate degree in Electrical Engineering from the Universidade Federal de Pernambuco (UFPE), Brazil, in 1992, the Masters degree in Electrical Engineering from the Universidade Estadual de Campinas, Brazil, in 1994, the M.S.E. degree in Electrical and Computer Engineering and the M.S.E. degree in Mathematical Sciences, both from The Johns Hopkins University, in 1998, and the Ph.D. degree in Electrical and Computer Engineering, from The Johns Hopkins University, in 2001. He was a Post-Doctoral Fellow at the University of Texas MD Anderson Cancer Center and a Visiting Scholar at Texas A&M University, from 2002 to 2004. He is currently an Associate Researcher at the Aggeu Magalhães Research Center of the Osvaldo Cruz Foundation, Brazilian Ministry of Health. His research interests include Bioinformatics, Pattern Recognition, Image Analysis, and Mathematical Morphology.     

Locality and Adjacency Stability Constraints for Morphological Connected Operators

This paper investigates two constraints for the connected operator class. For binary images, connected operators are those that treat grains and pores of the input in an all or nothing way, and therefore they do not introduce discontinuities. The first constraint, called connected-component (c.c.) locality, constrains the part of the input that can be used for computing the output of each grain and pore. The second, called adjacency stability, establishes an adjacency constraint between connected components of the input set and those of the output set. Among increasing operators, usual morphological filters can satisfy both requirements. On the other hand, some (non-idempotent) morphological operators such as the median cannot have the adjacency stability property. When these two requirements are applied to connected and idempotent morphological operators, we are lead to a new approach to the class of filters by reconstruction. The important case of translation invariant operators and the relationships between translation invariance and connectivity are studied in detail. Concepts are developed within the binary (or set) framework; however, conclusions apply as well to flat non-binary (gray-level) operators.     

Object-based image analysis using multiscale connectivity

This paper introduces a novel approach for image analysis based on the notion of multiscale connectivity. We use the proposed approach to design several novel tools for object-based image representation and analysis, which exploit the connectivity structure of images in a multiscale fashion. More specifically, we propose a nonlinear pyramidal image representation scheme, which decomposes an image at different scales by means of multiscale grain filters. These filters gradually remove connected components from an image that fail to satisfy a given criterion. We also use the concept of multiscale connectivity to design a hierarchical data partitioning tool. We employ this tool to construct another image representation scheme, based on the concept of component trees, which organizes partitions of an image in a hierarchical multiscale fashion. In addition, we propose a geometrically-oriented hierarchical clustering algorithm which generalizes the classical single-linkage algorithm. Finally, we propose two object-based multiscale image summaries, reminiscent of the well-known (morphological) pattern spectrum, which can be useful in image analysis and image understanding applications.     

Mask-based second-generation connectivity and attribute filters

Connected filters are edge-preserving morphological operators, which rely on a notion of connectivity. This is usually the standard 4 and 8-connectivity, which is often too rigid since it cannot model generalized groupings such as object clusters or partitions. In the set-theoretical framework of connectivity, these groupings are modeled by the more general second-generation connectivity. In this paper, we present both an extension of this theory, and provide an efficient algorithm based on the max-tree to compute attribute filters based on these connectivities. We first look into the drawbacks of the existing framework that separates clustering and partitioning and is directly dependent on the properties of a preselected operator. We then propose a new type of second-generation connectivity termed mask-based connectivity which eliminates all previous dependencies and extends the ways the image domain can be connected. A previously developed dual-input max-tree algorithm for area openings is adapted for the wider class of attribute filters on images characterized by second-generation connectivity. CPU-times for the new algorithm are comparable to the original algorithm, typically deviating less than 10 percent either way     

Algebraic and PDE Approaches for Lattice Scale-Spaces with Global Constraints

This paper begins with analyzing the theoretical connections between levelings on lattices and scale-space erosions on reference semilattices. They both represent large classes of self-dual morphological operators that exhibit both local computation and global constraints. Such operators are useful in numerous image analysis and vision tasks including edge-preserving multiscale smoothing, image simplification, feature and object detection, segmentation, shape and motion analysis. Previous definitions and constructions of levelings were either discrete or continuous using a PDE. We bridge this gap by introducing generalized levelings based on triphase operators that switch among three phases, one of which is a global constraint. The triphase operators include as special cases useful classes of semilattice erosions. Algebraically, levelings are created as limits of iterated or multiscale triphase operators. The subclass of multiscale geodesic triphase operators obeys a semigroup, which we exploit to find PDEs that can generate geodesic levelings and continuous-scale semilattice erosions. We discuss theoretical aspects of these PDEs, propose discrete algorithms for their numerical solution which converge as iterations of triphase operators, and provide insights via image experiments.     

A Theoretical Tour of Connectivity in Image Processing and Analysis

Connectivity is a concept of great relevance to image processing and analysis. It is extensively used in image filtering and segmentation, image compression and coding, motion analysis, pattern recognition, and other applications. In this paper, we provide a theoretical tour of connectivity, with emphasis on those concepts of connectivity that are relevant to image processing and analysis. We review several notions of connectivity, which include classical topological and graph-theoretic connectivity, fuzzy connectivity, and the theories of connectivity classes and of hyperconnectivity. It becomes clear in this paper that the theories of connectivity classes and of hyperconnectivity unify all relevant notions of connectivity, and provide a solid theoretical foundation for studying classical and fuzzy approaches to connectivity, as well as for constructing new examples of connectivity useful for image processing and analysis applications.     

一种基于灰度级连通性的红外图像分割方法

本文提出一种新的基于灰度级连通性的红外图像分割方法。灰度级连通性认为在某个灰度级以下的所有级集合是连通的,则灰度图像是连通的。提出的图像分割方法使用k级特征开运算将图像中包含目标的k级以上的连通成分保留下来,结合图像弱小目标的特征进行k级连通成分分解运算,提取出包含目标的k级连通成分实现图像简化和目标提取,最后结合简单的二值化处理就能够准确地分割出目标。通过仿真结果的比较,证明在红外图像中这种方法可以实现提高信噪比、提取目标和分割图像的目的。     

The Strong Property of Morphological Connected Alternated Filters

This paper studies connectivity aspects that arise in image operators that process connected components. The focus is on morphological image analysis (i.e., on increasing image operators) and, in particular, on a robustness property satisfied by certain morphological filters that is denominated the strong property. The behavior of alternated compositions of openings and closings is investigated under certain assumptions, particularly connectedness and a connected component preserving condition. It is shown that these conditions cannot in general guarantee the strong property of certain connected alternated filters because of issues related to the locality of the filters. As treated in the paper, there have been a series of misunderstandings in the literature concerning this topic, and it is important to clarify them. The root cause of those problems is discussed, and a solution is indicated. The class of connected openings and closings used to build connected alternated filters should therefore be defined to avoid such situations, since the strong property of alternated filters should be a distinctive characteristic of this class.

Range Image Segmentation through Pattern Analysis of the Multiscale Wavelet Transform

This work presents an image segmentation method for range data that uses multiscale wavelet analysis in combination with statistical pattern recognition. A feature-detection framework based on multiscale analysis and pattern recognition has several potential advantages over other feature detection systems. These advantages are detection of features at different scales (i.e., features of all sizes), robustness, and few or no free parameters. Our system creates a fuzzy edge map and derives a segmentation from this edge detection. A scale-space signature is the vector of measurements at different scales taken at a single point in an image. We analyze these 1-D signatures with traditional pattern-recognition methods. We train a pattern-recognition system with scale-space signatures from the edge points of a training image. Once trained, the system determines the degree ofedgenessof points in a new image. The goal is to create a system that exploits the advantages of a multiscale, pattern-recognition framework.     

基于形态学尺度空间的多尺度图像分割研究

给出了图像层次分割的新架构，阐述了基于重构形态学操作的尺度空间产生方法，提出了基于形态学尺度空间和形态学分水岭的多尺度分割策略，其目的是生成图像的分割堆栈，并通过链接技术获得有意义的对象分割。该文给出了对各种图像的分割的实验结果，验证了分割策略的有效性。     

Connectivity on Complete Lattices: New Results

The notion of connectivity is very important in image processing and analysis, and particularly in problems related to image segmentation. It is well understood, however, that classical notions of connectivity, including topological and graph-theoretic notions, are not compatible with each other. This motivated G. Matheron and J. Serra to develop a general framework of connectivity, which unifies most classical notions, circumvents incompatibility issues, and allows the construction of new types of connectivity for binary and grayscale images. In this paper, we enrich this theory of connectivity by providing several new theoretical results and examples that are useful in image processing and analysis. In particular, we provide new results on the semi-continuity behavior of connectivity openings, we study the reconstruction operator in a complete lattice framework, and we extend some known binary results regarding reconstruction to this framework. Moreover, we study connectivities constructed by expanding given connectivities by means of clustering operators and connectivities constructed by restricting given connectivities by means of contraction operators.     

Fast Algorithms for Area Morphology

Acton, S. T., Fast Algorithms for Area Morphology, Digital Signal Processing11 (2001) 187–203Efficient algorithms are developed for area morphology. As opposed to traditional morphological operations that alter grayscale images via a concatenation of order statistic filters, the area morphological operators manipulate connected components within the image level sets. Essentially, the area morphology filters are capable of removing objects based on the object area solely. These operators can then be effectively used in important multiscale and scale space tasks such as object-based coding and hierarchical image searches. Unfortunately, the traditional implementation of these filters based on level set theory precludes real-time implementation. This paper reviews previous fast algorithms and introduces a pyramidal approach. The full pyramidal algorithm is over 1000 times faster than the standard algorithm for typical image sizes. The paper provides supporting simulation results in terms of computational complexity and solution quality.     

图像边缘检测效果的边缘连续性评价算法

边缘检测是图像处理的一个重要环节,边缘检测效果的好坏直接决定图像处理结果的好坏,但对于边缘检测结果缺乏一个标准的数值化的评价方式,因此提出了一种对边缘检测结果的边缘连续性量化评价方法。以边缘的连续性作为图片边缘提取效果的评价指标,并且使用边缘段凸包面积与边缘段长度的乘积的平均值来数值化评价边缘连续性。设计了多种实验对同一图片采用不同的边缘检测算法在不同边缘检测参数下进行检测,并与所提算法进行评价对比。实验证明该算法能数值化地快速、有效地评价图片边缘检测的效果好坏,评价结果符合人的视觉感知特征,对于高层次的图像处理与自动化图像处理环节具有较好的应用价值。     

A novel approach to fuzzy rough sets based on a fuzzy covering

This paper proposes an approach to fuzzy rough sets in the framework of lattice theory. The new model for fuzzy rough sets is based on the concepts of both fuzzy covering and binary fuzzy logical operators (fuzzy conjunction and fuzzy implication). The conjunction and implication are connected by using the complete lattice-based adjunction theory. With this theory, fuzzy rough approximation operators are generalized and fundamental properties of these operators are investigated. Particularly, comparative studies of the generalized fuzzy rough sets to the classical fuzzy rough sets and Pawlak rough set are carried out. It is shown that the generalized fuzzy rough sets are an extension of the classical fuzzy rough sets as well as a fuzzification of the Pawlak rough set within the framework of complete lattices. A link between the generalized fuzzy rough approximation operators and fundamental morphological operators is presented in a translation-invariant additive group.     

Inf-Semilattice Approach to Self-Dual Morphology

Today, the theoretical framework of mathematical morphology is phrased in terms of complete lattices and operators defined on them. The characterization of a particular class of operators, such as erosions or openings, depends almost entirely upon the choice of the underlying partial ordering. This is not so strange if one realizes that the partial ordering formalizes the notions of foreground and background of an image. The duality principle for partially ordered sets, which says that the opposite of a partial ordering is also a partial ordering, gives rise to the fact that all morphological operators occur in pairs, e.g., dilation and erosion, opening and closing, etc. This phenomenon often prohibits the construction of tools that treat foreground and background of signals in exactly the same way. In this paper we discuss an alternative framework for morphological image processing that gives rise to image operators which are intrinsically self-dual. As one might expect, this alternative framework is entirely based upon the definition of a new self-dual partial ordering.     

Multiscale skeletons by image foresting transform and its application to neuromorphometry

The image foresting transform (IFT) reduces optimal image partition problems based on seed pixels to a shortest-path forest problem in a graph, whose solution can be obtained in linear time. Such a strategy has allowed a unified and efficient approach to the design of image processing operators, such as edge tracking, region growing, watershed transforms, distance transforms, and connected filters. This paper presents a fast and simple method based on the IFT to compute multiscale skeletons and shape reconstructions without border shifting. The method also generates one-pixel-wide connected skeletons and the skeleton by influence zones, simultaneously, for objects of arbitrary topologies. The results of the work are illustrated with respect to skeleton quality, execution time, and its application to neuromorphometry.     

蜂巢基底纳米颗粒SEM图像分析方法研究

分析了蜂巢形基底上纳米颗粒SEM图像的特征,阐明了纳米颗粒特征值提取所遇到的问题。借助形态学滤波、直方图均衡、颗粒分析等图像处理方法,解决了图像二值化处理后纳米颗粒图像上的大孔洞、粘连颗粒影响粒径提取等问题。给出了蜂巢形基底上纳米颗粒SEM图像处理算法,实现了占空比、粒径分布等纳米颗粒特征值提取的目标,为进一步对纳米器件的参数进行定量评价和改进奠定了基础。     

A general framework for tree-based morphology and its applications to self-dual filtering

This paper presents a tree-based framework for producing self-dual morphological operators, based on a tree-representation complete inf-semilattice (CISL). The idea is to use a self-dual tree transform to map a given image into the above CISL, perform one or more morphological operations there, and map the result back to the image domain using the inverse tree transform. We also present a particular case of this general framework, involving a new tree transform, the Extrema-Watershed Tree (EWT). The operators obtained by using the EWT in the above framework behave like classical morphological operators, but in addition are self-dual. Some application examples are provided: pre-processing for OCR and dust and scratch removal algorithms, and image denoising. We also explore first steps towards obtaining tree transforms that induce a CISL on the image domain as well.     

Set-Theoretical Algebraic Approaches to Connectivity in Continuous or Digital Spaces

Connectivity has been defined in the framework of topological spaces, but also in graphs; the two types of definitions do not always coincide. Serra gave a set of formal axioms for connectivity, which consists in a list of properties of the family of all connected subsets of a space; this definition includes as particular case connected sets in a topological space or in a graph. He gave an equivalent characterization of connectivity in terms of the properties of the operator associating to a subset and a point of that space, the connected component of that subset containing that point. In this paper we give another family of axioms, equivalent to those of Serra, where connectivity is characterized in terms of separating pairs of sets. In the case of graphs, where connected sets are generated by pairs of end-vertices of edges, this new set of axioms is equivalent to the separation axioms given by Haralick.