一种基于遗传算法的最小交叉熵阈值选择方法

最小交叉熵阈值法(MCET) 在二级阈值中是有效的, 但在多极阈值的穷尽搜索中却要付出昂贵的时间代价. 鉴于此, 提出一种基于遗传算法(GA) 的MCET选择方法: 在执行图像分割(IS) 任务之前, 先将IS 转化为在一定约束 条件下待优化的问题; 在寻找待优化问题最优解的计算过程中引入一种回归设计技巧以存储中间结果; 使用这种回 归设计技巧, 在一组标准测试图像上利用GA搜索待优化问题的最优解. 实验结果表明, 利用所提出的方法获得的多 个阈值非常接近于穷尽搜索获得的结果.

     

An enhanced bitstring encoding for exact maximum clique search in sparse graphs

This paper describes BBMCW, a new efficient exact maximum clique algorithm tailored for large sparse graphs which can be bit-encoded directly into memory without a heavy performance penalty. These graphs occur in real-life problems when some form of locality may be exploited to reduce their scale. One such example is correspondence graphs derived from data association problems. The new algorithm is based on the bit-parallel kernel used by the BBMC family of published exact algorithms. BBMCW employs a new bitstring encoding that we denote ‘watched’, because it is reminiscent of the ‘watched literal’ technique used in satisfiability and other constraint problems. The new encoding reduces the number of spurious operations computed by the BBMC bit-parallel kernel in large sparse graphs. Moreover, BBMCW also improves on bound computation proposed in the literature for bit-parallel solvers. Experimental results show that the new algorithm performs better than prior algorithms over data sets of both real and synthetic sparse graphs. In the real data sets, the improvement in performance averages more than two orders of magnitude with respect to the state-of-the-art exact solver IncMaxCLQ.     

An improved scheme for minimum cross entropy threshold selection based on genetic algorithm

Image segmentation is one of the most critical tasks in image analysis. Thresholding is definitely one of the most popular segmentation approaches. Among thresholding methods, minimum cross entropy thresholding (MCET) has been widely adopted for its simplicity and the measurement accuracy of the threshold. Although MCET is efficient in the case of bilevel thresholding, it encounters expensive computation when involving multilevel thresholding for exhaustive search on multiple thresholds. In this paper, an improved scheme based on genetic algorithm is presented for fastening threshold selection in multilevel MCET. This scheme uses a recursive programming technique to reduce computational complexity of objective function in multilevel MCET. Then, a genetic algorithm is proposed to search several near-optimal multilevel thresholds. Empirically, the multiple thresholds obtained by our scheme are very close to the optimal ones via exhaustive search. The proposed method was evaluated on various types of images, and the experimental results show the efficiency and the feasibility of the proposed method on the real images.     

Gesture image segmentation with Otsu’s method based on noise adaptive angle threshold

By analyzing the essence and deficiency of the improved Otsu’s method, this paper proposes a noise adaptive angle threshold based Otsu’s method for gesture image segmentation. It first designs a two-dimensional histogram of gray value-neighborhood truncated gray mean to avoid the interference of extreme noise by discarding the extremes of the neighborhood. Then, the probability that the pixel is noise is calculated according to the actual situation, adaptive filtering is implemented to enhance the algorithm’s universal applicability. It finally converts the threshold space to an angle space from 0° to 90°, and the threshold search range is compressed to improve its efficiency. As the gesture is close to the background and the boundary is blurred, this paper combines the global and local Otsu’s method to segment the gesture images based on the angle space. On the one hand, it uses the global Otsu’s method to obtain the global threshold t₁. On the other hand, it uses the local Otsu’s method to obtain the local threshold t₂, and segments gesture images based on t₂. Experimental results show that the proposed method is effective and can accurately segment gesture images with different noises.

     

Unsupervised multiscale segmentation of color images

This paper proposes a new multiresolution technique for color image representation and segmentation, particularly suited for noisy images. A decimated wavelet transform is initially applied to each color channel of the image, and a multiresolution representation is built up to a selected scale 2^J. Color gradient magnitudes are computed at the coarsest scale 2^J, and an adaptive threshold is used to remove spurious responses. An initial segmentation is then computed by applying the watershed transform to thresholded magnitudes, and this initial segmentation is projected to finer resolutions using inverse wavelet transforms and contour refinements, until the full resolution 2⁰ is achieved. Finally, a region merging technique is applied to combine adjacent regions with similar colors. Experimental results show that the proposed technique produces results comparable to other state-of-the-art algorithms for natural images, and performs better for noisy images.     

Transition pixel: A concept for binarization based on edge detection and gray-intensity histograms

This paper introduces a novel binarization method based on the concept of transition pixel, a generalization of edge pixels. Such pixels are characterized by extreme transition values computed using pixel-intensity differences in a small neighborhood. We show how to adjust the threshold of several binary threshold methods which compute gray-intensity thresholds, using the gray-intensity mean and variance of the pixels in the transition set. Our experiments show that the new approach yields segmentation performance superior to several with current state-of-the-art binarization algorithms.     

Spatially Constrained Student’s <Emphasis Type="Italic">t</Emphasis>-Distribution Based Mixture Model for Robust Image Segmentation

The finite Gaussian mixture model is one of the most popular frameworks to model classes for probabilistic model-based image segmentation. However, the tails of the Gaussian distribution are often shorter than that required to model an image class. Also, the estimates of the class parameters in this model are affected by the pixels that are atypical of the components of the fitted Gaussian mixture model. In this regard, the paper presents a novel way to model the image as a mixture of finite number of Student’s t-distributions for image segmentation problem. The Student’s t-distribution provides a longer tailed alternative to the Gaussian distribution and gives reduced weight to the outlier observations during the parameter estimation step in finite mixture model. Incorporating the merits of Student’s t-distribution into the hidden Markov random field framework, a novel image segmentation algorithm is proposed for robust and automatic image segmentation, and the performance is demonstrated on a set of HEp-2 cell and natural images. Integrating the bias field correction step within the proposed framework, a novel simultaneous segmentation and bias field correction algorithm has also been proposed for segmentation of magnetic resonance (MR) images. The efficacy of the proposed approach, along with a comparison with related algorithms, is demonstrated on a set of real and simulated brain MR images both qualitatively and quantitatively.     

基于分解的灰度图像二维阈值选取算法

作为一维Otsu法的推广, 二维Otsu法综合考虑了像素点的灰度信息及其邻域灰度的均值信息, 可以有效地滤除噪声. 其快速算法采用递归的方式构建查找表, 将算法的时间复杂性由OL4降到OL2. 提出基于分解的阈值选取算法, 求解两个一维Otsu法的阈值来替代原始的二维Otsu法的最佳阈值. 指出在原算法的假设成立的条件下, 该方法可以得到与原二维Otsu法相同的分割阈值, 而算法的时间复杂性可以进一步降低到OL. 而在实际中, 原算法的假设一般不成立. 本文的实验结果表明此时该阈值选取方法也可以在保证原二维Otsu算法良好的抗噪性的前提下, 计算阈值所需的时间更短、空间更小, 且阈值化结果也可以达到或优于二维Otsu算法的结果.     

基于2维灰度熵阈值选取快速迭代的图像分割

目的 为了使图像阈值分割的精度和速度进一步提高,提出了一种基于2维灰度熵阈值选取快速迭代的图像分割方法。方法 首先,提出了1维灰度熵阈值选取的快速迭代算法;然后,考虑图像目标和背景的类内灰度均匀性,给出了基于灰度—邻域平均灰度级直方图的灰度熵阈值选取准则;最后,提出了2维灰度熵阈值选取的快速迭代算法,并采用递推方式计算准则函数中的中间变量,避免其重复运算,加快了运算速度,大大减少了运算量。结果 大量实验结果表明,与近年来提出的3种阈值分割法相比,所提出的方法分割性能更优,分割后的图像中目标区域完整,边缘清晰,细节丰富且运行时间短,仅为基于混沌小生境粒子群优化的二维斜分倒数熵分割法运行时间的3%左右。结论 本文方法对不同类型灰度级图像的分割效果及运行速度均有明显优势,是实际系统中可选择的一种快速有效的图像分割方法。     

二维遗传算法用于图象动态分割

为了有效地对受噪声影响的图象进行分析,提出了两种基于二维遗传算法的图象动 态分割算法.在这些算法中:1)分别采用了以阈值曲面和模糊隶属度曲面为染色体的二维染 色体编码方式;2)采用了全局阈值化算法和模糊集合理论初始化种群;3)采用Hopfield网络 的能量函数形式,结合FCM算法和现有阈值化算法中的一般性分割准则构造适应度函数. 利用实际图象将所提出的算法与一些典型算法进行了分割比较实验,结果表明所提算法有较 好的抗噪效果.     

改进的图谱理论阈值分割方法

针对现有的基于归一化的图谱理论阈值分割算法的权值计算公式没有充分考虑像素点的关联,在图像含有弱边界时很难得到真实解,导致图像细节分割不理想的问题,本算法首先使用高斯混合模型构造新的约束条件引入到权值计算中,使得权值计算充分地考虑像素点之间的关联。在计算图谱划分测度前,本算法通过高斯混合模型的均值参数自适应确定门限值的分布区间,较大地提高了图谱划分测度计算的效率。实验结果表明,相对于现有的基于归一化的图谱理论的阈值分割方法,本文算法具有较好的分割效果,可以保留图像更多细节。     

A joint intensity and edge magnitude-based multilevel thresholding algorithm for the automatic segmentation of pathological MR brain images

Multilevel thresholding is one of the most popular image segmentation techniques due to its simplicity and accuracy. Most of the thresholding approaches use either the histogram of an image or information from the grey-level co-occurrence matrix (GLCM) to compute the threshold. The medical images like MRI usually have vague boundaries and poor contrast. So, segmenting these images using solely histogram or texture attributes of GLCM proves to be insufficient. This paper proposes a novel multilevel thresholding approach for automatic segmentation of tumour lesions from magnetic resonance images. The proposed technique exploits both intensity and edge magnitude information present in image histogram and GLCM to compute the multiple thresholds. Subsequently, using both attributes, a hybrid fitness function has been formulated which can capture the variations in intensity and the edge magnitude present in different tumour groups effectively. Mutation-based particle swarm optimization (MPSO) technique has been used to optimize the fitness function so as to mitigate the problem of high computational complexity existing in the exhaustive search methods. Moreover, MPSO has better exploration capabilities as compared to conventional particle swarm optimization. The performance of the devised technique has been evaluated and compared with two other intensity- and texture-based approaches using three different measures: Jaccard, Dice and misclassification error. To compute these quantitative metrics, experiments were conducted on a series of images, including low-grade glioma tumour volumes taken from brain tumour image segmentation benchmark 2012 and 2015 data sets and real clinical tumour images. Experimental results show that the proposed approach outperforms the other competing algorithms by achieving an average value equal to 0.752, 0.854, 0.0052; 0.648, 0.762, 0.0177; 0.710, 0.813, 0.0148 and 0.886, 0.937, 0.0037 for four different data sets.

     

A heuristic supervised Euclidean data difference dimension reduction for KNN classifier and its application to visual place classification

In this paper, we propose a novel supervised dimension reduction algorithm based on K-nearest neighbor (KNN) classifier. The proposed algorithm reduces the dimension of data in order to improve the accuracy of the KNN classification. This heuristic algorithm proposes independent dimensions which decrease Euclidean distance of a sample data and its K-nearest within-class neighbors and increase Euclidean distance of that sample and its M-nearest between-class neighbors. This algorithm is a linear dimension reduction algorithm which produces a mapping matrix for projecting data into low dimension. The dimension reduction step is followed by a KNN classifier. Therefore, it is applicable for high-dimensional multiclass classification. Experiments with artificial data such as Helix and Twin-peaks show ability of the algorithm for data visualization. This algorithm is compared with state-of-the-art algorithms in classification of eight different multiclass data sets from UCI collection. Simulation results have shown that the proposed algorithm outperforms the existing algorithms. Visual place classification is an important problem for intelligent mobile robots which not only deals with high-dimensional data but also has to solve a multiclass classification problem. A proper dimension reduction method is usually needed to decrease computation and memory complexity of algorithms in large environments. Therefore, our method is very well suited for this problem. We extract color histogram of omnidirectional camera images as primary features, reduce the features into a low-dimensional space and apply a KNN classifier. Results of experiments on five real data sets showed superiority of the proposed algorithm against others.     

Mining top-k regular-frequent itemsets using database partitioning and support estimation

Temporal regularity of itemset appearance can be regarded as an important criterion for measuring the interestingness of itemsets in several applications. A frequent itemset can be said to be regular-frequent in a database if it appears at a regular period. Therefore, the problem of mining a complete set of regular-frequent itemsets requires the specification of a support and a regularity threshold. However, in practice, it is often difficult for users to provide an appropriate support threshold. In addition, the use of a support threshold tends to produce a large number of regular-frequent itemsets and it might be better to ask for the number of desired results. We thus propose an efficient algorithm for mining top-k regular-frequent itemsets without setting a support threshold. Based on database partitioning and support estimation techniques, the proposed algorithm also uses a best-first search strategy with only one database scan. We then compare our algorithm with the state-of-the-art algorithms for mining top-k regular-frequent itemsets. Our experimental studies on both synthetic and real data show that our proposal achieves high performance for small and large values of k.     

K步稳定的鞋印花纹图像自动聚类

目的 鞋印是刑事侦查的重要物证之一,如何对积累的大量鞋印花纹图像进行自动归类管理是刑事技术迫切需要解决的问题之一。与其他类图像不同,鞋印花纹图像具有种类多但数目未知、同类花纹分布不均匀且同类花纹数目少的特点。基于鞋印花纹图像的这些特点,用目前典型的聚类算法对鞋印花纹图像集进行聚类,并不能取得很好的效果。在对鞋印花纹图像进行分析的基础上,提出一种K步稳定的鞋印花纹图像自动聚类算法。方法 对已标记的鞋印花纹图像进行统计发现,各类鞋印花纹之间在特征空间上存在互不相交的区域(本文称为隔离带)。算法的核心思想是寻找各类鞋印花纹之间的隔离带,来将各类分开。过程为:以单调递增或递减的方式调整特征空间中判定两点为一类的阈值,得到数据集的多次划分;若在连续K次划分的过程中,某一类的成员不发生变化,则说明这K次调整是在隔离带中进行的,即聚出一类,并从数据集中删除已标记的数据;选择下一个阈值对剩余的数据集进行划分,输出K步不变的类;依此类推,直到剩余数据集为空,聚类完成。结果 在两类公开测试数据集和实际鞋印花纹数据集上进行实验,本文算法的主要性能指标都超过典型算法,其中在包含5792枚实际鞋印花纹数据集上的聚类准确率和F-Measure值分别达到了99.68%和95.99%。结论 针对鞋印花纹图像特点,提出了一种通过寻找各类之间的隔离带进行自动聚类的算法,并在实际应用中取得了很好的效果。且算法性能受参数的变化以及类的形状影响较小。本文算法同样适用于具有类似特点的其他数据集的自动聚类。     

鲁棒空间约束的模糊聚类图像分割

目的 为进一步提高分割精度,在模糊聚类的基础上引入统计信息,提出一种鲁棒型空间约束的模糊聚类分割算法。方法 基于局部空间信息的先验概率与后验概率,提出一种新型空间约束项,并通过卷积操作提高运行效率;进而引入负对数联合概率作为测度函数,进一步提高算法对于各像素点所属类别的甄别能力;同时将测度函数与空间约束项整合至目标函数中,通过迭代更新各参数达到最小化目标函数的目的。结果 对于合成图像的实验结果表明,本文算法对于噪声类型和噪声强度具有较强的鲁棒性;对于彩色图像的实验结果表明,在适当的特征描述符的辅助下,本文算法也能够获得令人满意的分割结果和较高的分割精度。结论 本文算法克服了现有算法的缺陷,进一步提升了图像的分割精度。其适用于分割带噪声图像,且在适当纹理特征的辅助下分割彩色图像,与同类算法的比较实验结果验证了本文算法的有效性。     

Automatic boosted flood mapping from satellite data

Numerous algorithms have been proposed to map floods from Moderate Resolution Imaging Spectroradiometer (MODIS) imagery. However, most require human input to succeed, either to specify a threshold value or to manually annotate training data. We introduce a new algorithm based on Adaboost which effectively maps floods without any human input, allowing for a truly rapid and automatic response. The Adaboost algorithm combines multiple thresholds to achieve results comparable to state-of-the-art algorithms which do require human input. We evaluate Adaboost, as well as numerous previously proposed flood mapping algorithms, on multiple MODIS flood images, as well as on hundreds of non-flood MODIS lake images, demonstrating its effectiveness across a wide variety of conditions.     

一种新的字符图像倾斜矫正与分割算法

针对传统的倾斜矫正与分割算法对不同类型的字符图像处理效果各异的问题,本文提出了一种改进的算法,加入了新的倾斜角度确定准则、阈值动态调整以及区域后处理,不仅解决了传统方法易受噪声和复杂背景干扰、可操作性差的问题,而且也有效地实现了字符图像的倾斜矫正与分割.实验结果表明,尽管新算法在像素点判断次数上多于最大类间方差算法,但...     

A fast technique for image segmentation based on two Meta-heuristic algorithms

Image segmentation is a primary task in image processing which is widely used in object detection and recognition. Multilevel thresholding is one of the prominent technique in the field of image segmentation. However, the computational cost of multilevel thresholding increases exponentially as the number of threshold value increases, which leads to use of meta-heuristic optimization to find the optimal number of threshold. To overcome this problem, this paper investigates the ability of two nature-inspired algorithms namely: antlion optimisation (ALO) and multiverse optimization (MVO). ALO is a population-based method and mimics the hunting behaviour of antlions in nature. Whereas, MVO is based on the multiverse theory which depicts that there is over one universe exist. These two metaheuristic algorithms are used to find the optimal threshold values using Kapur’s entropy and Otsu’s between class variance function. They examine the outcomes of the proposed algorithm with other evolutionary algorithms based on cost value, stability analysis, feature similarity index (FSIM), structural similarity index (SSIM), peak signal to noise ratio (PSNR), computational time. We also provide Wilcoxon test which justify the response of these parameters. The experimental results showed that the proposed algorithm gives better results than other existing methods. It is noticed that MVO is faster than other algorithms. The proposed method is also tested on medical images to detect the tumor from MRI T1-weighted contrast-enhanced brain images.

     

A hybrid differential evolution for optimal multilevel image thresholding

Image thresholding is a process for separating interesting objects within an image from their background. An optimal threshold’s selection can be regarded as a single objective optimization problem, where obtaining a solution can be computationally expensive and time-consuming, especially when the number of thresholds increases greatly. This paper proposes a novel hybrid differential evolution algorithm for selecting the optimal threshold values for a given gray-level input image, using the criterion defined by Otsu. The hybridization is done by adding a reset strategy, adopted from the Cuckoo Search, within the evolutionary loop of differential evolution. Additionally a study of different evolutionary or swarm-based intelligence algorithms for the purpose of thresholding, with a higher number of thresholds was performed, since many real-world applications require more than just a few thresholds for further processing. Experiments were performed on eleven real world images. The efficiency of the hybrid was compared to the cuckoo search and self-adaptive differential evolution, the original differential evolution, particle swarm optimization, and artificial bee colony where the results showed the superiority of the hybrid in terms of better segmentation results with the increased number of thresholds. Since the proposed method needs only two parameters adjusted, it is by far a better choice for real-life applications.