A Constant-time Algorithm for Erosions/Dilations with Applications to Morphological Texture Feature Computation

A computationally efficient algorithm for computing erosions and dilations by one- dimensional grayscale structuring elements with constant slope is proposed. The computational complexity of this algorithm is independent of the size of the support of the structuring function. This is a generalization of the method proposed by Van Herk for the case of erosion and dilation by flat one-dimensional structuring elements. By appropriate combinations of these structuring elements, it is possible to approximate many useful structuring elements. This enables efficient computation of granulometries where the number of operations depends linearly on the number of openings. Theoretical and experimental results comparing the complexity of this algorithm with other standard techniques is presented. Two memory efficient algorithms are then presented. Several implementation issues in computing a granulometry and moments of the associated morphological pattern spectrum are then addressed. An efficient implementation of granulometries for large images on machines with limited memory, by dividing the image into smaller rectangular patches is then discussed. The optimum size of these patches is a function of the specific hardware and has been obtained experimentally for three different hardware platforms. Finally, parallel implementation of the different algorithms on two multi-processor machines is discussed.     

Decomposition of arbitrarily shaped morphological structuringelements

For image processing systems that have a limited size of region of support, say 3×3, direct implementation of morphological operations by a structuring element larger than the prefixed size is impossible. The decomposition of morphological operations by a large structuring element into a sequence of recursive operations, each using a smaller structuring element, enables the implementation of large morphological operations. In this paper, the authors present the decomposition of arbitrarily shaped (convex or concave) structuring elements into 3×3 elements, optimized with respect to the number of 3×3 elements. The decomposition is based on the concept of factorization of a structuring element into its prime factors. For a given structuring element, all its corresponding 3×3 prime concave factors are first determined. From the set of the prime factors, the decomposability of the structuring element is then established, and subsequently the structuring element is decomposed into a smallest possible set of 3×3 elements. Examples of optimal decomposition and structuring elements that are not decomposable are presented     

形态学结构元的二次分解方法

利用数学形态学方法进行图像处理的过程中,对形态学结构元进行分解,可以达到降低计算复杂度和便于利用通用的简单形态学硬件模块实现复杂的形态学运算的目的．讨论了将复杂结构元分解为简单结构元而不降低结构元维数的传统分解方法,并提出了对结构元进行两次降维分解的结构元分解方法,以达到提高形态学运算效率的目的,将每个像素的计算时间复杂度从O(n^2)降低到O(n),n为结构元的大小．文中方法还具有利于硬件实现和并行实现的特点,为加快形态学变换运算提出了新的实现思路．     

Decomposition of arbitrary gray-scale morphological structuring elements

Mathematical morphology has been widely used for many applications in image processing and analysis. Most image processing architectures adapted to morphological operations use structuring elements of a limited size. Therefore, difficulties arise when we deal with a large-sized structuring element. In this paper, we present algorithms for the decomposition of arbitrary gray-scale structuring elements into combined dilations or maximum operators of smaller structuring components. Our method does not need to perform additional pre-processes, such as checking the type of structuring elements and the decomposition rules. Furthermore, it is suited for a parallel pipelined architecture.     

Connected shape-size pattern spectra for rotation and scale-invariant classification of gray-scale images

In this paper, we describe a multiscale and multishape morphological method for pattern-based analysis and classification of gray-scale images using connected operators. Compared with existing methods, which use structuring elements, our method has three advantages. First, in our method, the time needed for computing pattern spectra does not depend on the number of scales or shapes used, i.e., the computation time is independent of the dimensions of the pattern spectrum. Second, size and strict shape attributes can be computed, which we use for the construction of joint 2D shape-size pattern spectra. Third, our method is significantly less sensitive to noise and is rotation-invariant. Although rotation invariance can also be approximated by methods using structuring elements at different angles, this tends to be computationally intensive. The classification performance of these methods is discussed using four image sets: Brodatz, COIL-20, COIL-100, and diatoms. The new method obtains better or equal classification performance to the best competitor with a 5 to 9-fold speed gain     

基于改进形态学算子的多尺度边缘检测

图像边缘检测的关键是在尽量多地检测到图像边缘的同时更有效地抑制噪声,为此提出了一种新的基于轮廓结构元素的多尺度形态学边缘检测方法。该方法重新组合了基于轮廓结构元素形态学各种运算的优点,实现了一种改进的形态学算子;在此基础上利用改进形态学算子的多尺度运算定义了一种新的边缘检测算子。与其他形态学方法相比,文中方法不仅具有更好的噪声抑制和边缘细节保护功能,而且对结构元素的形状不敏感。     

Methods for fast morphological image transforms using bitmapped binary images

In this paper we present new implementations for morphological binary image processing on a general-purpose computer, using a bitmap representation of binary images instead of representing binary images as bitplanes inserted in gray value images. The bitmap data representation is a very efficient one, both in terms of memory requirements and in terms of algorithmic efficiency because of the CPU operates on 32 pixels in parallel. The algorithms described in this paper are capable of performing the basic morphological image transforms using structuring elements of arbitrary size and shape. In order to speed up morphological operations with respect to commonly used, large, convex structuring elements, the logarithmic decomposition of structuring elements is used. Experiments indicate that the new algorithms are more than 30 times faster for pixelwise operations and about an order of magnitude faster for the basic morphological transforms than the fastest known software implementations.     

自动检测图像目标的形态滤波遗传算法

提出了一种实现形态滤波器参数优化设计的贵传学习算法（Genetic Training Algorithm for Morphologi-cal Fitters,GTAMF）。采用新的交叉与变异算子－曲面体交叉与主从式变异,通过优化搜索全局以获得滤波性和时效性兼优的形态滤波器参数。实验结果表明该方法设计方便,实用性强且易于推广,对提高形态滤波性能效果明显,分析表明,形态滤波器可分解为形态学运算和结构元选择两个基本问题,形态学运算的规则已由定义本身而确定,于是形态滤波器的最终滤波性能就仅仅取决于结构元的选择。通过自适应优化训练使结构元具有图像目标的形态结构特征,从而赋予结构元特定的知识,使形态滤波过程融入特有的智能,以实现对复杂变化的图像具有良好的滤波性能和稳健的适应能力。     

Automatic target detection by optimal morphological filters

It is widely accepted that the design of morphological filters,which are optimal in some sense,is a difficult task.In this paper a novel method for optimal learning of morphological filtering parameters(Genetic training algorithm for morphological filters,GTAMF)is presented.GTAMF adopts new crossover and mutation operators called the curved cylinder crossover and master-slave mutaition to achieve optimal filtering parameters in a global searching,Experimental results show that this method is practical,easy to extend,and markedly improves the performances of morphoological filters.The operation of a morphological filter can be divided into two basic problems including morphological operation and structuring element (SE)Selection.The rules for morphological operations are predefined so that the filter‘s properties depend merely on the selection of SE.By means of adaptive optimization training,structureing elements possess the shape and structural characteristics of image targets,and give specific information to SE.Morphological filters formed in this way become certainly intelligent and can provide good filtering results and robust adaptability to image targets with clutter background.     

Optimal decomposition of convex morphological structuring elementsfor 4-connected parallel array processors

A morphological operation using a large structuring element can be decomposed equivalently into a sequence of recursive operations, each using a smaller structuring element. However, an optimal decomposition of arbitrarily shaped structuring elements is yet to be found. In this paper, we have derived an optimal decomposition of a specific class of structuring elements-convex sets-for a specific type of machine-4-connected parallel array processors. The cost of morphological operation on 4-connected parallel array processors is the total number of 4-connected shifts required by the set of structuring elements. First, the original structuring element is decomposed into a set of prime factors, and then their locations are determined while minimizing the cost function. Proofs are presented to show the optimality of the decomposition. Examples of optimal decomposition are given and compared to an existing decomposition reported by Xu (1991)     

Decomposition of arbitrarily shaped binary morphologicalstructuring elements using genetic algorithms

A number of different algorithms have been described in the literature for the decomposition of both convex binary morphological structuring elements and a specific subset of nonconvex ones. Nevertheless, up to now no deterministic solutions have been found to the problem of decomposing arbitrarily shaped structuring elements. This work presents a new stochastic approach based on genetic algorithms, in which no constraints are imposed on the shape of the initial structuring element nor assumptions are made on the elementary factors, which are selected within a given set     

Optimal implementation of morphological operations on neighborhood-connected parallel computers

To efficiently perform morphological operations on neighborhood-processing-based parallel image computers, we need to decompose structuring elements larger than the neighborhood that can be directly handled into neighborhood subsets. In the special case that the structuring element is a convex polygon, there are known decomposition algorithms in the literature. In this paper, we give an algorithm for the optimal decomposition of arbitrarily shaped structuring elements, enabling an optimal implementation of morphological operations on neighborhood-connected parallel computers in the general case.     

Adaptive Unsymmetrical Trim-Based Morphological Filter for High-Density Impulse Noise Removal

The modified decision-based unsymmetrical trimmed median filter (MDBUTMF), which is an efficient tool for restoring images corrupted with high-density impulse noise, is only effective for certain types of images. This is because the size of the selected window is fixed and some of the center pixels are replaced by a mean value of pixels in the window. To address these issues, this paper proposes an adaptive unsymmetrical trim-based morphological filter. Firstly, a strict extremum estimation approach is used, in order to decide whether the pixel to be processed belongs to a monochrome or non-monochrome area. Then, the center pixel is replaced by a median value of pixels in a window for the monochrome area. Secondly, a relaxed extremum estimation approach is used to control the size of structuring elements. Then an adaptive structuring element is obtained and the center pixel is replaced by the output of constrained morphological operators, i.e., the minimum or maximum of pixels in a trimmed structuring element. Our experimental results show that the proposed filter is more robust and practical than the MDBUTMF. Moreover, the proposed filter provides a preferable performance compared to the existing median filters and vector median filters for high-density impulse noise removal.

     

FPGA-based fast computation of gray-level morphological granulometries

Morphological granulometries constitute one of the most useful and versatile image analysis techniques applied to a wide range of tasks, from size distribution of objects, to feature extraction and to texture characterization in industrial and research applications where high-performance instrumentation and online signal processing are required. Since granulometries are based on sequences of openings with structuring elements (SEs) of increasing size, they are computational demanding on non-specialized hardware. In this paper, a pipelined hardware architecture for fast computation of gray-level morphological granulometries is presented, centered around two systolic-like processing arrays able to process with flat SEs of different shapes and sizes. To validate the proposed scheme, the architecture was modeled, simulated and implemented into a field programmable gate array. Implementation results show that the architecture is able to compute particle size distribution on 512 × 512 sized images with flat non-rectangular SEs of up to 51 × 51, in around 60 ms at a clock frequency of 260 MHz. It is shown that a speed up over two orders of magnitude is obtained compared to a naive software implementation. The architecture performance compares favorably to similar hardware architectural schemes and to optimized high-performance graphical processing units-based implementations.     

Highly Accurate Schemes for PDE-Based Morphology with General Convex Structuring Elements

The two fundamental operations in morphological image processing are dilation and erosion. These processes are defined via structuring elements. It is of practical interest to consider a variety of structuring element shapes. The realisation of dilation/erosion for convex structuring elements by use of partial differential equations (PDEs) allows for digital scalability and subpixel accuracy. However, numerical schemes suffer from blur by dissipative artifacts. In our paper we present a family of so-called flux-corrected transport (FCT) schemes that addresses this problem for arbitrary convex structuring elements. The main characteristics of the FCT-schemes are: (i) They keep edges very sharp during the morphological evolution process, and (ii) they feature a high degree of rotational invariance. We validate the FCT-scheme theoretically by proving consistency and stability. Numerical experiments with diamonds and ellipses as structuring elements show that FCT-schemes are superior to standard schemes in the field of PDE-based morphology.     

基于多尺度数学形态学的边缘检测

提出了一种基于多尺度数学形态学的图像边缘检测方法,利用数学形态学在描述灰度图像方面的优势,分析了在不同尺度下边缘提取的特点,采用非极大值运算方法提取边缘点,并与其他形态学边缘检测法进行了比较,给出了在含噪条件下边缘提取的实验结果。     

Speeding-up successive Minkowski operations with bit-plane computers

Performing successive Minkowski operations on binary images is a well known and widely used task in image processing. In bit-serial parallel computers (so called bit-plane computers) the time necessary to perform such operations depends to a great extent on the complexity of the particular structuring element T. As it is well known, this computation time can be reduced if T is decomposed into the (set theoretical) sum of simpler structuring elements. Such decompositions, however, are known only for a very narrow class of structuring elements. In this paper, a modification of that decomposition method is presented which results in speeding up the Minkowski operations for a broader class. It is shown that, after a certain number of steps, just the ‘extreme points’ of the structuring element are important. So, unlike the convenient methods, it is successfully applied only if sequences of Minkowski operations are applied. This is the case in particular in mathematical morphology when erosion, dilatation, opening (ouverture), and closing (fermeture) are performed repeatedly.     

一种灰度形态算子的构造方法

提出了采用灰度结构元图像的灰度形态算子的构造方法。所构造的形态算子采用了适合灰度结构元图像与灰度图像间操作的结构，其相应的操作具有较明确的物理解释，从而适合招待灰度图像处理任务。     

一种基于数学形态学的分形维数估计方法

对于分形维数的估计是基于分形理论的纹理图像分割算法中最重要的环节。由于使用固定划分的规则网格，常用的基于盒计数的分形维数估计算法及其各种改进方法的误差较大；而传统的形态学维数估计算法虽然在准确性上有一定提高．但其时间复杂度偏高。为此提出了一种基于可变结构元的数学形态学分形维数估计方法(VSEM)。该方法将灰度图像视为一个三维空间中的曲面，使用一组不同尺度的结构元分别度量该曲面．根据度量结果与尺度之间满足的指数率来估计图像表面的分形维数。通过恰当的选择结构元和使用递推技术得到不同尺度下的膨胀结果，新方法成功地弥补了现有算法的不足。本文使用了一组合成纹理和一组自然纹理来评估几种常见的分形维数估计算法。结果显示，本文提出的新方法能够在较小的时间复杂度下，得到更为精确的估计结果。最后，将该方法应用于遥感图像的分割。与其他常用的分形分割算法相比，使用该方法估计的分形维数和图像的临域均值作为特征能够得到更好的分割结果。在对比分析和分割实验中表现出的良好性能说明本文提出的分形维数估计算法可以有效地应用于纹理图像分割。     

Parallel implementation of sequential morphological filters

Many useful morphological filters are built as more or less long concatenations of erosions and dilations: openings, closings, size distributions, sequential filters, etc. An efficient implementation of these concatenations would allow all the sequentially concatenated operators run simultaneously, on the time-delayed data. A recent algorithm (see below) for the morphological dilation/erosion allows such inter-operator parallelism. This paper introduces an additional, intra-operator level of parallelism in this dilation/erosion algorithm. Realized in a dedicated hardware, for rectangular structuring elements with programmable size, such an implementation allows obtaining previously unachievable, real-time performances for these traditionally costly operators. Low latency and memory requirements are the main benefits when the performance is not deteriorated even for long concatenations or high-resolution images.