Multi-level image thresholding by synergetic differential evolution

The multi-level image thresholding is often treated as a problem of optimization. Typically, finding the parameters of these problems leads to a nonlinear optimization problem, for which obtaining the solution is computationally expensive and time-consuming. In this paper a new multi-level image thresholding technique using synergetic differential evolution (SDE), an advanced version of differential evolution (DE), is proposed. SDE is a fusion of three algorithmic concepts proposed in modified versions of DE. It utilizes two criteria (1) entropy and (2) approximation of normalized histogram of an image by a mixture of Gaussian distribution to find the optimal thresholds. The experimental results show that SDE can make optimal thresholding applicable in case of multi-level thresholding and the performance is better than some other multi-level thresholding methods.     

A Local Contrast Fusion Based 3D Otsu Algorithm for Multilevel Image Segmentation

To overcome the shortcomings of 1D and 2D Otsu’s thresholding techniques, the 3D Otsu method has been developed. Among all Otsu’s methods, 3D Otsu technique provides the best threshold values for the multi-level thresholding processes. In this paper, to improve the quality of segmented images, a simple and effective multilevel thresholding method is introduced. The proposed approach focuses on preserving edge detail by computing the 3D Otsu along the fusion phenomena. The advantages of the presented scheme include higher quality outcomes, better preservation of tiny details and boundaries and reduced execution time with rising threshold levels. The fusion approach depends upon the differences between pixel intensity values within a small local space of an image; it aims to improve localized information after the thresholding process. The fusion of images based on local contrast can improve image segmentation performance by minimizing the loss of local contrast, loss of details and gray-level distributions. Results show that the proposed method yields more promising segmentation results when compared to conventional 1D Otsu, 2D Otsu and 3D Otsu methods, as evident from the objective and subjective evaluations.      

The computational power of cell division in P systems: Beating down parallel computers?

We study the computational power of cell division operations in the formalframework of P systems, a mathematical model of cell-like membrane structure with regulated transport of objects (molecules) through membranes. We show that a uniformfamily of P systems with active membranes and2-division is able to solve the well-known PSPACE-complete problem QBF inlinear time. This result implies that such a family of P systems modelling celldivision is at least as powerful as so-called Second Machine Class computers. The Second Machine Class, containing most of the fundamental parallelcomputer models such as parallel RAM machines of types SIMD and MIMD, vector machinesand others, is characterized by using an exponential amount of resources(processing units) with respect to the computing time.     

A new social and momentum component adaptive PSO algorithm for image segmentation

In this paper, we present a new variant of Particle Swarm Optimization (PSO) for image segmentation using optimal multi-level thresholding. Some objective functions which are very efficient for bi-level thresholding purpose are not suitable for multi-level thresholding due to the exponential growth of computational complexity. The present paper also proposes an iterative scheme that is practically more suitable for obtaining initial values of candidate multilevel thresholds. This self iterative scheme is proposed to find the suitable number of thresholds that should be used to segment an image. This iterative scheme is based on the well known Otsu’s method, which shows a linear growth of computational complexity. The thresholds resulting from the iterative scheme are taken as initial thresholds and the particles are created randomly around these thresholds, for the proposed PSO variant. The proposed PSO algorithm makes a new contribution in adapting ‘social’ and ‘momentum’ components of the velocity equation for particle move updates. The proposed segmentation method is employed for four benchmark images and the performances obtained outperform results obtained with well known methods, like Gaussian-smoothing method (Lim, Y. K., & Lee, S. U. (1990). On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques. Pattern Recognition, 23, 935–952; Tsai, D. M. (1995). A fast thresholding selection procedure for multimodal and unimodal histograms. Pattern Recognition Letters, 16, 653–666), Symmetry-duality method (Yin, P. Y., & Chen, L. H. (1993). New method for multilevel thresholding using the symmetry and duality of the histogram. Journal of Electronics and Imaging, 2, 337–344), GA-based algorithm (Yin, P. -Y. (1999). A fast scheme for optimal thresholding using genetic algorithms. Signal Processing, 72, 85–95) and the basic PSO variant employing linearly decreasing inertia weight factor.     

Multi-objective and multi-level image thresholding based on dominance and diversity criteria

The Kapur and Otsu methods are widely used image thresholding approaches and they are very efficient in bi-level thresholding applications. Evolutionary algorithms have been developed to extend the Kapur and Otsu methods to the multi-level thresholding case. However, there remains an unsolved argument that neither Kapur nor Otsu objective can optimally fit diverse content contained in different kinds of images. This paper proposes a multi-objective model which seeks to find the Pareto-optimal set with respect to Kapur and Otsu objectives. Based on dominance and diversity criteria, we developed a hybrid multi-objective particle swarm optimization (MOPSO) method by incorporating several intelligent search strategies. The ensemble strategy is also applied to automatically select the best search strategy to perform at various algorithm stages according to its historic performances. The experimental result shows that the solutions to our multi-objective model consistently produce equal or better segmentation results than those by the optimal solutions to the original Kapur and Otsu models, and that the proposed hybrid algorithm with and without the ensemble strategy produces a better approximation to the ideal Pareto front than those obtained by two other MOPSO variants and the MOEA/D. In comparison with the most recent multilevel thresholding methods, our approach also consistently obtains better performance in the segmentation result for several benchmark images.     

Automatic multi-thresholds selection for image segmentation based on evolutionary approach

Automatic thresholding has been widely used in machine vision for automatic image segmentation. Otsu’s method selects an optimum threshold by maximizing the between-class variance in a grayscale image. However, the method becomes time-consuming when extended to multi-level threshold problems, because excessive iterations are required in order to compute the cumulative probability and the mean of class. In this paper, we focus on the issue of automatic selection for multi-level thresholding, and we greatly improve the efficiency of Otsu’s method for image segmentation based on evolutionary approaches. We have investigated and evaluated the performance of the Otsu and Valleyemphasis thresholding methods. Based on our evaluation results, we have developed many different algorithms for automatic threshold selection based on the evolutionary method using the Modified Adaptive Genetic Algorithm and the Hill Climbing Algorithm. The experimental results show that the evolutionary approach achieves a satisfactory segmentation effect and that the processing time can be greatly reduced when the number of thresholds increases.     

A noise attribute thresholding method for document image binarization

A new thresholding method, called the noise attribute thresholding method (NAT), for document image binarization is presented in this paper. This method utilizes the noise attribute features extracted from the images to make the selection of threshold values for image thresholding. These features are based on the properties of noise in the images and are independent of the strength of the signals (objects and background) in the image. A simple noise model is given to explain these noise properties. The NAT method has been applied to the problem of removing text and figures printed on the back of the paper. Conventional global thresholding methods cannot solve this kind of problem satisfactorily. Experimental results show that the NAT method is very effective. Received July 05, 1999 / Revised July 07, 2000     

一种带混合进化机制的膜聚类算法

膜计算(也称为P系统或膜系统)是一种新颖的分布式、并行计算模型.为了处理数据聚类问题,提出了一种采用混合进化机制的膜聚类算法.它使用了一个由3个细胞组成的组织P系统,为一个待聚类的数据集发现最优的簇中心.其对象表示候选的簇中心,并且这3个细胞分别使用了3种不同的进化机制:遗传算子、速度-位移模型和差分进化机制.然而,所使用的速度-位移模型和差分进化机制是结合了这个特殊膜结构和转运机制所提出的改进版本.这种混合进化机制能够增强系统中对象的多样性和改善收敛性能.在混合进化机制和转运机制控制下,这种膜聚类算法能够确定一个数据集的良好划分.所提出的膜聚类算法在3个人工数据集和5个真实数据集上被评估,并与k-means和几种进化聚类算法进行比较.统计显著性测试建立了所提出的膜聚类算法的优势.     

A novel local contrast fusion-based fuzzy model for color image multilevel thresholding using grasshopper optimization

The segmentation process is considered the significant step of an image processing system due to its extreme inspiration on the subsequent image analysis. Out of various approaches, thresholding is one of the most popular schemes for image segmentation. In segmentation, image pixels are arranged in various regions based on their intensity levels. In this paper, a straightforward and efficient fusion-based fuzzy model for multilevel color image segmentation using grasshopper optimization algorithm (GOA) has been proposed. Thresholding based segmentation lacks accuracy in segmenting the ambiguous images due to their complex characteristics, uncertainties and inherent fuzziness. However, the fuzzy entropy resolves these problems, but it is unable for segmenting at higher levels and also the complexity level for selecting suitable thresholds is high. The selection of metaheuristic GOA reduces this problem by selecting optimal threshold values. Therefore, to increase the quality of the segmented image, a simple and effective multilevel thresholding method is exploited by using the concept of fusion which is based on the local contrast. Experimental outputs demonstrate that fusion-based multilevel thresholding is better than most specific segmentation methods and can be validated by comparing the different numerical parameters. Experiments on standard daily-life color and satellite images are conducted to prove the effectiveness of the proposed scheme.     

Fuzzy entropy based optimal thresholding using bat algorithm

Image segmentation is a very significant process in image analysis. Much effort based on thresholding has been made on this field as it is simple and intuitive, commonly used thresholding approaches are to optimize a criterion such as between-class variance or entropy for seeking appropriate threshold values. However, a mass of computational cost is needed and efficiency is broken down as an exhaustive search is utilized for finding the optimal thresholds, which results in application of evolutionary algorithm and swarm intelligence to obtain the optimal thresholds. This paper considers image thresholding as a constrained optimization problem and optimal thresholds for 1-level or multi-level thresholding in an image are acquired by maximizing the fuzzy entropy via a newly proposed bat algorithm. The optimal thresholding is achieved through the convergence of bat algorithm. The proposed method has been tested on some natural and infrared images. The results are compared with the fuzzy entropy based methods that are optimized by artificial bee colony algorithm (ABC), genetic algorithm (GA), particle swarm optimization (PSO) and ant colony optimization (ACO); moreover, they are also compared with thresholding methods based on criteria of between-class variance and Kapur's entropy optimized by bat algorithm. It is demonstrated that the proposed method is robust, adaptive, encouraging on the score of CPU time and exhibits the better performance than other methods involved in the paper in terms of objective function values.     

目标自适应图像分块与小目标提取

针对传统二维直方图方法的难点,提出了采用基于分水岭变换的图像自适应分块的解决方法,新方法能使得每个小目标都被分割在同一个图像区域内,克服了传统图像分块方法采用固定分块,易造成将同一目标分到多个区域的缺点。方法中首先采用了基于标记点的灰度图像重建方法对图像进行预处理,在自适应增强目标的同时也克服了分水岭变换易造成过度分割的影响,在此基础上进一步地对图像采取了基于分水岭变换的图像分块,接着在每一个分块区域中采用引入目标分布信息阈值选取方法,得到二值化的结果。实验表明该方法目标分割结果稳定,适合于小目标的分割提取。     

Cuckoo search algorithm and wind driven optimization based study of satellite image segmentation for multilevel thresholding using Kapur’s entropy

The objective of image segmentation is to extract meaningful objects. A meaningful segmentation selects the proper threshold values to optimize a criterion using entropy. The conventional multilevel thresholding methods are efficient for bi-level thresholding. However, they are computationally expensive when extended to multilevel thresholding since they exhaustively search the optimal thresholds to optimize the objective functions. To overcome this problem, two successful swarm-intelligence-based global optimization algorithms, cuckoo search (CS) algorithm and wind driven optimization (WDO) for multilevel thresholding using Kapur’s entropy has been employed. For this purpose, best solution as fitness function is achieved through CS and WDO algorithm using Kapur’s entropy for optimal multilevel thresholding. A new approach of CS and WDO algorithm is used for selection of optimal threshold value. This algorithm is used to obtain the best solution or best fitness value from the initial random threshold values, and to evaluate the quality of a solution, correlation function is used. Experimental results have been examined on standard set of satellite images using various numbers of thresholds. The results based on Kapur’s entropy reveal that CS, ELR-CS and WDO method can be accurately and efficiently used in multilevel thresholding problem.     

A multi-level abstraction and modeling in video databases

In this paper, we propose a multi-level abstraction mechanism for capturing the spatial and temporal semantics associated with various objects in an input image or in a sequence of video frames. This abstraction can manifest itself effectively in conceptualizing events and views in multimedia data as perceived by individual users. The objective is to provide an efficient mechanism for handling content-based queries, with the minimum amount of processing performed on raw data during query evaluation. We introduce a multi-level architecture for video data management at different levels of abstraction. The architecture facilitates a multi-level indexing/searching mechanism. At the finest level of granularity, video data can be indexed based on mere appearance of objects and faces. For management of information at higher levels of abstractions, an object-oriented paradigm is proposed which is capable of supporting domain specific views.     

灰度梯度映射函数改进的Otsu阈值法

针对目标与背景灰度分布不均匀的图像,基于集中于目标的图像阈值法思想,引入图像的灰度直方图信息,得到更为细致的阈值化准则。考虑图像的边缘信息,引入灰度梯度映射函数,提出了基于梯度的集中于目标的Otsu阈值法。大量经典图像阈值化结果表明,该方法在目标提取的完整性和边缘保留的清晰性方面,均表现出了更佳的效果。     

Solving the process of hysteresis without determining the optimal thresholds

Hysteresis is an important edge detection technique, but the unsupervised determination of hysteresis thresholds is a difficult problem. Thus, hysteresis has limited practical applicability. Unimodal thresholding techniques are another edge detection method. They are useful, because the histogram of a feature image (usually the feature image is an approximation of the gradient image) is unimodal, and there are many unsupervised methods to solve this problem. But such techniques do not use spatial information to detect edge points, so their performance is worse than that of the hysteresis.In this paper, we show how to formulate the hysteresis process as a unimodal thresholding problem without determining the optimal hysteresis thresholds. Using similar steps of the Canny edge detector to obtain an approximation of the gradient image we compare the performance of our method against that of a method that determines the best parameters of an edge detector and show that our method performs relatively well. Additionally, our method can adjust its sensitivity by using different unimodal thresholding techniques.     

一种改进的二维最小误差闭值分割方法

二维最小误差(TME)阈值法是一种有效的图像分割方法,但该方法计算复杂度高,难以实时处理,且该算法受噪声影响较大.针对此问题,提出了一种改进的TME阈值分割方法.首先,将传统的3×3模板分成互补的两个模板:十字模板和4-角域模板,并用这两个模板分别对原图像进行中值滤波得到两幅图像;然后,用两幅图像创建二维直方图并对其进行分割,以获得更好的分割性能;最后,对TME阈值选取公式进行简化得到最简公式,并利用此最简公式和其在二维直方图上的计算特性构建新型的快速算法,以便降低计算复杂度.仿真实验结果表明,与当前TME 阈值分割方法相比,所提方法不仅分割效果更好、稳定性更强,而且运行速度更快,占用的存储空间更少.     

Grey level reduction for segmentation, threshholding and binarisation of images based on optimal partitioning on an interval

Optimal reduction of the number of grey levels present in an image is a fundamental problem in segmentation, classification, lossy compression, quantisation, inspection and computer vision. We present a new algorithm based on dynamic programming and optimal partitioning of the image data space, or its histogram representation. The algorithm allows the reduction of the number of grey levels for an image in a fine to coarse fashion, starting with the original grey levels present in the image and all the way down to two grey levels that simply create a binarised version of the original image. The algorithm can also be used to find a reduced number of grey levels in a natural way without forcing a specific number ahead of time. Application of the algorithm is demonstrated in image segmentation, multi-level thresholding and binarisation, and is shown to give very good results compared to many of the existing methods.     

Phase-based optimal image thresholding

The automatic binarization of gray-level images or the automatic determination of an optimum threshold value that separates objects from their background is still a difficult and challenging problem in many image processing applications. The difficulty may arise due to a number of factors, including, poor contrast, high noise to signal ratio, complex patterns, and/or variable modalities in the gray-scale histograms. In this paper an algorithm for determining an optimum image thresholding value is proposed. Phase correlation between the gray-level image and its binary counterpart is defined as a function of the thresholding parameter. The optimum thresholding problem is then constructed as a problem of optimization where the objective is to find a threshold value that maximizes the phase correlation between the two images. Experimental results to compare the proposed algorithm to the various thresholding techniques are also presented.     

自然计算的新分支——膜计算

作为自然计算的新分支,膜计算是当前计算机科学、数学、生物学和人工智能等多学科交叉的研究热点.概述膜计算的最新动态,以一个简单膜系统为例介绍膜计算的基本概念和基本原理,从细胞型、组织型和神经型三类膜系统以及它们的计算能力和计算效率方面介绍膜计算理论研究进展,通过概括膜计算国内外应用研究成果讨论其应用前景和方向,并从软硬件发展历程分析膜系统软硬实现研究现状.最后给出有关膜计算研究的重要网络资源、热点研究领域和重点关注的问题.     

Efficiently extracting and classifying objects for analyzing color documents

Conventional objects extraction method are not efficient for color document image with large graphics. For example, the projection profile and connected component based methods scanning the large graphics many times. To display the large graphics are extracted, conventional methods use rectangle to represent it. Thus, scanning into the large graphics is time-consuming. In this paper, a novel system for efficiently analyzing color documents is proposed to solve above mentioned problem. The proposed system includes color transformation, background color determination, objects extraction by top-down method, and objects classification without parameters. The proposed color document analysis system is efficient because it scans only background pixels such that the temporal complexity is O (NB), where NB is the total number of background color pixels. Results of this study demonstrate that this system is more effective and efficient than other methods. Moreover, the proposed algorithm can be run in an embedded environment (such as a mobile device) and processed in real-time system due to its simplicity and efficiency.