A Hough transform based line recognition method utilizing both parameter space and image space

Hough Transform (HT) is recognized as a powerful tool for graphic element extraction from images due to its global vision and robustness in noisy or degraded environment. However, the application of HT has been limited to small-size images for a long time. Besides the well-known heavy computation in the accumulation, the peak detection and the line verification become much more time-consuming for large-size images. Another limitation is that most existing HT-based line recognition methods are not able to detect line thickness, which is essential to large-size images, usually engineering drawings. We believe these limitations arise from that these methods only work on the HT parameter space. This paper therefore proposes a new HT-based line recognition method, which utilizes both the HT parameter space and the image space. The proposed method devises an image-based gradient prediction to accelerate the accumulation, introduces a boundary recorder to eliminate redundant analyses in the line verification, and develops an image-based line verification algorithm to detect line thickness and reduce false detections as well. It also proposes to use pixel removal to avoid overlapping lines instead of rigidly suppressing the N×N neighborhood. We perform experiments on real images with different sizes in terms of speed and detection accuracy. The experimental results demonstrate the significant performance improvement, especially for large-size images.     

Image segmentation by a fuzzy clustering algorithm using adaptivespatially constrained membership functions

We present an adaptive fuzzy clustering scheme for image segmentation, the adaptive fuzzy clustering/segmentation (AFCS) algorithm. In AFCS, the nonstationary nature of images is taken into account by modifying the prototype vectors as functions of the sample location in the image. The inherent high interpixel correlation is modeled using neighborhood information. A multiresolution model is utilized for estimating the spatially varying prototype vectors for different window sizes. The fuzzy segmentations at different resolutions are combined using a data fusion process in order to compute the final fuzzy partition matrix. The results provide segmentations, having lower fuzzy entropy when compared to the possibilistic C-means algorithm, while maintaining the image's main characteristics. In addition, due to the neighborhood model, the effects of noise in the form of single pixel regions are minimized     

Numerical convergence and interpretation of the fuzzy c-shellsclustering algorithm

R. N. Dave's (1990) version of fuzzy c-shells is an iterative clustering algorithm which requires the application of Newton's method or a similar general optimization technique at each half step in any sequence of iterates for minimizing the associated objective function. An important computational question concerns the accuracy of the solution required at each half step within the overall iteration. The general convergence theory for grouped coordination minimization is applied to this question to show that numerically exact solution of the half-step subproblems in Dave's algorithm is not necessary. One iteration of Newton's method in each coordinate minimization half step yields a sequence obtained using the fuzzy c-shells algorithm with numerically exact coordinate minimization at each half step. It is shown that fuzzy c-shells generates hyperspherical prototypes to the clusters it finds for certain special cases of the measure of dissimilarity used.     

Multi-circle detection on images inspired by collective animal behavior

Hough transform (HT) has been the most common method for circle detection that delivers robustness but adversely demands considerable computational efforts and large memory requirements. As an alternative to HT-based techniques, the problem of shape recognition has also been handled through optimization methods. In particular, extracting multiple circle primitives falls into the category of multi-modal optimization as each circle represents an optimum which must be detected within the feasible solution space. However, since all optimization-based circle detectors focus on finding only a single optimal solution, they need to be applied several times in order to extract all the primitives which results on time-consuming algorithms. This paper presents an algorithm for automatic detection of multiple circular shapes that considers the overall process as a multi-modal optimization problem. In the detection, the approach employs an evolutionary algorithm based on the way in which the animals behave collectively. In such an algorithm, searcher agents emulate a group of animals which interact to each other using simple biological rules. These rules are modeled as evolutionary operators. Such operators are applied to each agent considering that the complete group maintains a memory which stores the optimal solutions seen so-far by applying a competition principle. The detector uses a combination of three non-collinear edge points as parameters to determine circle candidates (possible solutions). A matching function determines if such circle candidates are actually present in the image. Guided by the values of such matching functions, the set of encoded candidate circles are evolved through the evolutionary algorithm so that the best candidate (global optimum) can be fitted into an actual circle within the edge-only image. Subsequently, an analysis of the incorporated memory is executed in order to identify potential local optima which represent other circles. Experimental results over several complex synthetic and natural images have validated the efficiency of the proposed technique regarding accuracy, speed and robustness.     

FUZZY SHELL-CLUSTERING AND APPLICATIONS TO CIRCLE DETECTION IN DIGITAL IMAGES

A new type of Fuzzy Clustering algorithm called Fuzzy-Shell Clustering (FSC) is introduced, The FSC algorithm seeks cluster prototypes that are p-dimensional hyper-spherical-shells. In two-dimensional data, this amounts to finding cluster prototypes that are circles. Thus the FSC algorithm can be applied for detection of circles in digital images. The algorithm does not require the data-points to be in any particular order, therefore its performance can be compared with the global transformation techniques such as Hough transforms. Several numerical examples are considered and the performance of the FSC algorithm is compared to the performance of the methods based on generalized Hough transform (HT). The FSC is shown to be superior to the HT method with regards to memory requirement and computation time. Like the HT method, the FSC is successful even if only a part of a circular shape is present in the image. Other potential applications of FSC are also considered.     

一种新的不基于Hough变换的随机椭圆检测算法

椭圆检测在模式识别领域中占据着非常重要的位置。常见的基于Hough变换的椭圆检测算法(如RHT算法)存在着占用大量存储空间及计算耗时等缺点。本文提出一种高效随机的椭圆检测算法(RED)。该算法不基于Hough变换,其原理是:首先从一幅图像中随机地挑选出6个点,并定义一个约束距离以确定在此图像中是否存在一个可能的椭圆;当可能椭圆确定之后,引入椭圆点收集过程以进一步确定可能椭圆是否是待检测的真实椭圆。通过对具有不同噪声的合成图像以及真实图像进行测试,结果表明RED算法在低噪声与适度噪声的情况下,速度明显快于RHT算法。     

面向惯性约束聚变实验靶图像的快速椭圆检测

目的：针对惯性约束核聚变实验中靶图像轮廓模糊、亮度不均匀等问题,并从提高图像处理实时性角度出发,提出了一种高可靠性和高精度的快速椭圆检测方法。方法：首先利用椭圆边缘点在它与圆心相连方向上具有较大灰度变化率这一特点,以预估中心点为极点建立极坐标系,通过从极点出发的射线上灰度变化率极值点搜索实现椭圆边缘点检测,极值点搜索在图像局部范围进行保证边缘点检测的有效性和实时性;其次利用基于RANSAC的自适应椭圆参数提取算法得到最终椭圆参数,该方法利用椭圆参数空间聚类分析选取最优椭圆参数,从而实现了一致样本集的自适应选择,保证了椭圆参数拟合精度的同时提高了算法的适应性和鲁棒性。结果：采用本文算法检测一幅图像的平均时间约为110ms,与常用椭圆检测方法相比检测速度有显著提高。结论：对比实验表明,本文提出的椭圆检测方法与其他方法相比具有更高的精度、更快的实时性和更强的鲁棒性。     

模糊c-均值算法改进及其对卫星遥感数据聚类的对比

提出的改进的模糊c-均值聚类方法采用基于标准协方差矩阵的Mahalanobis距离，即椭球体聚类方法，这种聚类算法更接近遥感数据散点图的实际情况，从而可以显著提高聚类效果。对北京卫星ASTER数据的聚类分析实验表明，改进的模糊c-均值聚类方法的聚类效果要优于K-均值聚类方法和常规的模糊c-均值聚类方法。     

Determining membership functions and minimum fuzzy support in finding fuzzy association rules for classification problems

This paper propose a new method, that employs the genetic algorithm, to find fuzzy association rules for classification problems based on an effective method for discovering the fuzzy association rules, namely the fuzzy grids based rules mining algorithm (FGBRMA). It is considered that some important parameters, including the number and shapes of membership functions in each quantitative attribute and the minimum fuzzy support, are not easily user-specified. Thus, the above-mentioned parameters are automatically determined by a binary string or chromosome is composed of two substrings: one for each quantitative attribute by the coding method proposed by Ishibuchi and Murata, and the other for the minimum fuzzy support. In each generation, the fitness value, which maximizes the classification accuracy rate and minimizes the number of fuzzy rules, of each chromosome can be obtained. When reaching the termination condition, a chromosome with maximum fitness value is then used to test its performance. For classification generalization ability, the simulation results from the iris data and the appendicitis data demonstrate that proposed method performs well in comparison with other classification methods.     

Implementation of evolutionary fuzzy systems

Evolutionary fuzzy systems are discussed in which the membership function shapes and types and the fuzzy rule set including the number of rules inside it are evolved using a genetic (evolutionary) algorithm. In addition, the genetic parameters (operators) of the evolutionary algorithm are adapted via a fuzzy system. Benefits of the methodology are illustrated in the process of classifying the iris data set. Possible extensions of the methods are summarized     

Fuzzy risk analysis based on fuzzy numbers with different shapes and different deviations

In this paper, we present a new method for fuzzy risk analysis based on fuzzy numbers with different shapes and different deviations. First, we present a new method for ranking trapezoidal fuzzy numbers based on their shapes and deviations. Then, we use some examples to compare the proposed method with the existing methods for ranking fuzzy numbers. Finally, we use the proposed fuzzy ranking method to present a new fuzzy risk analysis algorithm to deal with fuzzy risk analysis problems. The proposed fuzzy risk analysis algorithm is more flexible and simpler than the existing methods due to the fact that it allows the evaluating values to be represented by trapezoidal fuzzy numbers with different shapes and different deviations.     

基于中心提取的RHT在椭圆检测中的应用

充分利用椭圆的几何性质,借助椭圆的形状控制点约束和弦端点法向约束,大幅降低随机Hough变换(RHT)的无效采样和累积次数,并采用基于视觉感知聚类的模糊置信度对由同一个形变椭圆引入的多个虚假候选椭圆进行有效去除.实验结果表明:该算法与基于RHT的其他椭圆检测方法相比,具有检测速度快、精度高、抵抗椭圆的部分缺失和形变能力强等优点.     

Outlier Detection Algorithms in Data Mining Systems

The paper discusses outlier detection algorithms used in data mining systems. Basic approaches currently used for solving this problem are considered, and their advantages and disadvantages are discussed. A new outlier detection algorithm is suggested. It is based on methods of fuzzy set theory and the use of kernel functions and possesses a number of advantages compared to the existing methods. The performance of the algorithm suggested is studied by the example of the applied problem of anomaly detection arising in computer protection systems, the so-called intrusion detection systems.     

A reasoning algorithm for high-level fuzzy Petri nets

We introduce an automated procedure for extracting information from knowledge bases that contain fuzzy production rules. The knowledge bases considered here are modeled using the high-level fuzzy Petri nets proposed by the authors in the past. Extensions to the high-level fuzzy Petri net model are given to include the representation of partial sources of information. The case of rules with more than one variable in the consequent is also discussed. A reasoning algorithm based on the high-level fuzzy Petri net model is presented. The algorithm consists of the extraction of a subnet and an evaluation process. In the evaluation process, several fuzzy inference methods can be applied. The proposed algorithm is similar to another procedure suggested by Yager (1983), with advantages concerning the knowledge-base searching when gathering the relevant information to answer a particular kind of query     

A fast Hough Transform algorithm for straight lines detection in an image using GPU parallel computing with CUDA-C

The Hough Transform (HT) is a digital image processing method for the detection of shapes which has multiple uses today. A disadvantage of this method is its sequential computational complexity, particularly when a single processor is used. An optimized algorithm of HT for straight lines detection in an image is presented in this article. Optimization is realized by using a decomposition of the input image recently proposed via central processing unit (CPU), and the technique known as segment decomposition. Optimized algorithms improve execution times significantly. In this paper, the optimization is implemented in parallel using graphics processing unit (GPU) programming, allowing a reduction of total run time and achieving a performance more than 20 times better than the sequential method and up to 10 times better than the implementation recently proposed. Additionally, we introduce the concept of Performance Ratio, to emphasize the outperforming of the GPU over the CPUs.     

A novel Hough transform based on eliminating particle swarm optimization and its applications

Hough transform (HT) is a well established method for curve detection and recognition due to its robustness and parallel processing capability. However, HT is quite time-consuming. In this paper, an eliminating particle swarm optimization (EPSO) algorithm is employed to improve the speed of a HT. The parameters of the solution after Hough transformation are considered as the particle positions, and the EPSO algorithm searches the optimum solution by eliminating the “weakest” particles to speed up the computation. An accumulation array in Hough transformation is utilized as a fitness function of the EPSO algorithm. The experiments on numerous images show that the proposed approach can detect curves or contours of both noise-free and noisy images with much better performance. Especially, for noisy images, it can archive much better results than that obtained by using the existing HT algorithms.     

广义模糊Gibbs随机场与MR图像分割算法研究

为了对图像进行准确、可靠的分割,提出了一种基于广义模糊集的软分割算法,并将广义模糊集和G ibbs场结合起来,提出了广义模糊G ibbs随机场模型,同时建立了广义模糊G ibbs分割(GFGS)算法。该算法是首先把每一个分割类看作是广义模糊类,并以最大后验概率(MAP)为判别准则来决定每一个像素值的归类以及它属于该类的隶属度;然后用广义隶属度函数中负的部分来刻划数据中的异常值,使得该算法能有效地处理异常值;最后用该模糊类的质心来更新类的中心,并以人脑的仿真图像和临床MR图像进行了实验。实验结果表明,该算法能有效地滤除噪声和处理部分容积效应,是一个分割能力强、稳健性好的算法。     

基于计算机视觉的公交系统人流量检测算法

提出了一种基于计算机视觉的公交系统人流量检测方法。通过分析现场行人视频数据，运用图像处理的方法提取图像中通行的行人以及通过视场内的人流量，阐述了复杂背景、低分辨率和特殊拍摄角度条件下的人头特征曲线提取算法和基于部分椭圆弧的椭圆模板参数估算法，试验结果表明了该算法的正确性和有效性。     

Projectively invariant decomposition and recognition of planar shapes

An algorithm is presented for computing a decomposition of planar shapes into convex subparts represented. by ellipses. The method is invariant to projective transformations of the shape, and thus the conic primitives can be used for matching and definition of invariants in the same way as points and lines. The method works for arbitrary planar shapes admitting at least four distinct tangents and it is based on finding ellipses with four points of contact to the given shape. The cross ratio computed from the four points on the ellipse can then be used as a projectively invariant index. It is demonstrated that a given shape has a unique parameter-free decomposition into a finite set of ellipses with unit cross ratio. For a given shape, each pair of ellipses can be used to compute two independent projective invariants. The set of invariants computed for each ellipse pair can be used as indexes to a hash table from which model hypothesis can be generated Examples of shape decomposition and recognition are given for synthetic shapes and shapes extracted from grey level images of real objects using edge detection.     

基于密度峰值的加权犹豫模糊聚类算法

由于人们对事物认知的局限性和信息的不确定性,在对决策问题进行聚类分析时,传统的模糊聚类不能有效解决实际场景中的决策问题,因此有学者提出了有关犹豫模糊集的聚类算法.现有的层次犹豫模糊K均值聚类算法没有利用数据集本身的信息来确定距离函数的权值,且簇中心的计算复杂度和空间复杂度都是指数级的,不适用于大数据环境.针对上述问题,...