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.     

Automatic multiple circle detection based on artificial immune systems

Hough transform (HT) has been the most common method for circle detection, exhibiting robustness but adversely demanding a considerable computational load and large storage. Alternative approaches for multiple circle detection include heuristic methods built over iterative optimization procedures which confine the search to only one circle per optimization cycle yielding longer execution times. On the other hand, artificial immune systems (AIS) mimic the behavior of the natural immune system for solving complex optimization problems. The clonal selection algorithm (CSA) is arguably the most widely employed AIS approach. It is an effective search method which optimizes its response according to the relationship between patterns to be identified, i.e. antigens (Ags) and their feasible solutions also known as antibodies (Abs). Although CSA converges to one global optimum, its incorporated CSA-Memory holds valuable information regarding other local minima which have emerged during the optimization process. Accordingly, the detection is considered as a multi-modal optimization problem which supports the detection of multiple circular shapes through only one optimization procedure. The algorithm uses a combination of three non-collinear edge points as parameters to determine circles candidates. A matching function determines if such circle candidates are actually present in the image. Guided by the values of such function, the set of encoded candidate circles are evolved through the CSA so the best candidate (global optimum) can fit into an actual circle within the edge map of the image. Once the optimization process has finished, the CSA-Memory is revisited in order to find other local optima representing potential circle candidates. The overall approach is a fast multiple-circle detector despite considering complicated conditions in the image.     

Multi-ellipses detection on images inspired by collective animal behavior

This paper presents a novel and effective technique for extracting multiple ellipses from an image. The approach employs an evolutionary algorithm to mimic the way animals behave collectively assuming the overall detection process as a multi-modal optimization problem. In the algorithm, searcher agents emulate a group of animals that interact with each other using simple biological rules which are modeled as evolutionary operators. In turn, such operators are applied to each agent considering that the complete group has a memory to store optimal solutions (ellipses) seen so far by applying a competition principle. The detector uses a combination of five edge points as parameters to determine ellipse candidates (possible solutions), while a matching function determines if such ellipse candidates are actually present in the image. Guided by the values of such matching functions, the set of encoded candidate ellipses are evolved through the evolutionary algorithm so that the best candidates can be fitted into the actual ellipses within the image. Just after the optimization process ends, an analysis over the embedded memory is executed in order to find the best obtained solution (the best ellipse) and significant local minima (remaining ellipses). Experimental results over several complex synthetic and natural images have validated the efficiency of the proposed technique regarding accuracy, speed, and robustness.     

Circle Detection by Harmony Search Optimization

Automatic circle detection in digital images has received considerable attention over the last years in computer vision as several novel efforts aim for an optimal circle detector. This paper presents an algorithm for automatic detection of circular shapes considering the overall process as an optimization problem. The approach is based on the Harmony Search Algorithm (HSA), a derivative free meta-heuristic optimization algorithm inspired by musicians improvising new harmonies while playing. The algorithm uses the encoding of three points as candidate circles (harmonies) over the edge-only image. An objective function evaluates (harmony quality) if such candidate circles are actually present in the edge image. Guided by the values of this objective function, the set of encoded candidate circles are evolved using the HSA so that they can fit into the actual circles on the edge map of the image (optimal harmony). Experimental results from several tests on synthetic and natural images with a varying complexity range have been included to validate the efficiency of the proposed technique regarding accuracy, speed and robustness.     

Automatic circle detection on digital images with an adaptive bacterial foraging algorithm

This article presents an algorithm for the automatic detection of circular shapes from complicated and noisy images without using the conventional Hough transform methods. The proposed algorithm is based on a recently developed swarm intelligence technique, known as the bacterial foraging optimization (BFO). A new objective function has been derived to measure the resemblance of a candidate circle with an actual circle on the edge map of a given image based on the difference of their center locations and radii lengths. Guided by the values of this objective function (smaller means better), a set of encoded candidate circles are evolved using the BFO algorithm so that they can fit to the actual circles on the edge map of the image. The proposed method is able to detect single or multiple circles from a digital image through one shot of optimization. Simulation results over several synthetic as well as natural images with varying range of complexity validate the efficacy of the proposed technique in terms of its final accuracy, speed, and robustness.     

一种基于圆的几何特性改进的圆检测随机算法

在模式识别和计算机视觉领域,圆检测的应用十分重要。目前,大部分圆检测算法都把关注点放在精确度和检测效率上,随机算法具有计算效率高和占用内存少的优点,然而,随机算法通过选取大量的候选圆并统计落在候选圆上的像素总数判断圆的存在,在实时检测中并不适用。文章提出了一种基于圆的对称性的改进算法,加速了判断候选圆是否为真实圆的过程,同时在统计候选圆上的像素时没有采集图像中全部的边缘像素,而是采集候选圆的内接正方形和外切正方形范围内的边缘像素。实验表明,这种方法在保持圆检测准确性的条件下减少了运算时间。     

Circle detection using discrete differential evolution optimization

This paper introduces a circle detection method based on differential evolution (DE) optimization. Just as circle detection has been lately considered as a fundamental component for many computer vision algorithms, DE has evolved as a successful heuristic method for solving complex optimization problems, still keeping a simple structure and an easy implementation. It has also shown advantageous convergence properties and remarkable robustness. The detection process is considered similar to a combinational optimization problem. The algorithm uses the combination of three edge points as parameters to determine circle candidates in the scene yielding a reduction of the search space. The objective function determines if some circle candidates are actually present in the image. This paper focuses particularly on one DE-based algorithm known as the discrete differential evolution (DDE), which eventually has shown better results than the original DE in particular for solving combinatorial problems. In the DDE, suitable conversion routines are incorporated into the DE, aiming to operate from integer values to real values and then getting integer values back, following the crossover operation. The final algorithm is a fast circle detector that locates circles with sub-pixel accuracy even considering complicated conditions and noisy images. Experimental results on several synthetic and natural images with varying range of complexity validate the efficiency of the proposed technique considering accuracy, speed, and robustness.     

快速随机Hough变换多圆检测算法

随机Hough变换是检测圆的一种有效方法,但在处理多圆复杂图像时随机采样带来的大量无效累积会导致计算量过大。文中提出一种基于随机Hough变换的快速多圆检测算法,除去三类噪声点,通过随机采样到的一点按照一定规则搜索另外两点来确定候选圆,用原始图像对候选圆进行证据积累以判断是否为真圆。理论分析和实验结果表明：该算法较其他算法能更快地检测出图像中的多个圆,具有较好的应用价值。     

基于切线段匹配的快速圆弧检测算法

针对目前工程图纸矢量化过程中圆弧检测准确率不高、检测时间过长等问题,提出一种基于切线段匹配的快速圆弧检测算法。首先,该方法找出可能位于圆外边界上八方向(0,π/4,π/2,…,7π/4)与圆相切的线段,并记录在切线集合中;然后,对已找到的切线段进行两两配对,估算圆心半径范围,得到候选圆集合;最后,对获取的候选圆集合进行数据合并,对合并后的每一个候选圆进行跟踪检测,最终确定它是一个圆还是一个弧。在切线段寻找过程中进行匹配,对已确定为圆的候选圆,在切线段集合中去除与该圆相对应切线段,有效减少了匹配次数。在对比实验中,所提算法的平均识别率达到了97.250%,平均检测时间为12.290 s, 比随机抽样一致性(RANSAC)算法和有效投票算法(EVM)的平均识别率更高,平均检测时间更短。实验结果表明,所提算法能够有效地对低噪声图像中弧长大于1/8圆周长的圆弧进行检测,同时能提高检测准确率、缩短检测时间。     

Alleviating the computational load of the probabilistic algorithms for circles detection using the connectivity represented by graph

The probabilistic algorithms are effective and widely used to recognize the curves in machine vision and image processing. In this paper, a novel algorithm for detecting circles is presented. It is based on the observation that the connectivity can help to alleviate the computational load of the probabilistic algorithm. A graph model is introduced to express connectivity in the detected edges, and a modified depth-first-search algorithm is developed to segment the whole graph into connected subgraphs and then partition the complex subgraph into simple paths. Then, four pixels are randomly selected from the sampling set, consisting of one proper path or several consecutive paths, to detect circles. The connectivity constraint is further employed to verify the candidates of circles to eliminate the pseudo ones. The experiments, comparing the proposed algorithm with the randomized Hough transform and the efficient randomized circle detection algorithm, show that it has the advantages of computational efficiency and robustness.     

A novel artificial bee colony algorithm with Powell's method

Artificial bee colony (ABC) algorithm is a relatively new optimization technique which has been shown to be competitive to other population-based algorithms. However, there is still an insufficiency in ABC regarding its solution search equation, which is good at exploration but poor at exploitation. To address this concerning issue, we first propose a modified search equation which is applied to generate a candidate solution in the onlookers phase to improve the search ability of ABC. Further, we use the Powell's method as a local search tool to enhance the exploitation of the algorithm. The new algorithm is tested on 22 unconstrained benchmark functions and 13 constrained benchmark functions, and are compared with some other ABCs and several state-of-the-art algorithms. The comparisons show that the proposed algorithm offers the highest solution quality, fastest global convergence, and strongest robustness among all the contenders on almost all test functions.     

结合多阶段优化的圆检测算法

在常规圆检测算法中,Hough变换、随机Hough变换以及随机圆检测算法的检测效率低,导致难以适用于复杂场景或者对检测速度有较高要求的情况。为了提高圆检测的效率,本文从采样点的选取、候选圆的确定以及真圆的确认3个阶段进行分析,结合这3个阶段的优化方法,提出一种结合多阶段优化的圆检测算法。人工图像和实际图像的实验结果表明：该算法较其他算法有效地提高了圆检测的速度,并且具有较好的检测鲁棒性和检测精度。     

基于频谱预处理与改进霍夫变换的离焦模糊盲复原算法

为了提高离焦模糊图像复原清晰度,提出一种基于频谱预处理与改进霍夫变换的 离焦模糊盲复原算法。首先改进模糊图像频谱预处理策略,降低了噪声对零点暗圆检测的影响。 然后改进霍夫变换圆检测算法,在降低算法复杂度的同时,增强了模糊半径估计的准确性。最 后利用混合特性正则化复原图像模型对模糊图像进行迭代复原,使复原图像的边缘细节更加清 晰。实验结果表明,提出的模糊半径估计方法较其他方法平均误差更小,改进的频谱预处理策 略更有利于零点暗圆检测,改进的霍夫变换圆检测算法模糊半径估计精度更高,所提算法对已 知相机失焦的小型无人机拍摄的离焦模糊图像具有更好的复原效果。针对离焦模糊图像复原, 通过理论分析和实验验证了改进的模糊半径估计方法的鲁棒性强,所提算法的复原效果较好。     

A feedback combination of global optimization and local optimization for robust template-based visual tracking

This paper proposes a robust template-based visual tracking algorithm. The proposed algorithm combines global optimization and local optimization. The global optimization is performed in translational matching, and the local optimization is implemented by gradient descent in homography-based matching. Translational matching is robust to large translation of the reference image, although it is not robust to rotation, or scaling. In contrast, homography-based matching is robust to rotation, and scaling, although it is not robust to large translation. The proposed algorithm is a feedback combination of the two matching algorithms. Translational matching modifies the initial value for gradient descent in homography-based matching. Homography-based matching updates the reference image for translational matching. The proposed feedback combination inherits advantages from both translational matching and homography-based matching. Robot experiments demonstrate the robustness of the proposed feedback combination to composite transformations of translation, rotation, and scaling.     

Connectivity-based multiple-circle fitting

This paper proposes a connectivity-based method for circle fitting. The use of pixel connectivity effectively avoids false circle detection, improves the robustness against noise and significantly reduces the computational load. The desired circular models are extracted by searching for meaningful circular arcs. The algorithm does not require a good initial guess, and is effective for extracting an a priori unknown number of circles even when the number of outliers exceeds 50%. The experimental results demonstrate that the proposed method performs well in detecting multiple intersecting or occluded circles.     

A graph-based optimization algorithm for fragmented image reassembly

We propose a graph-based optimization framework for automatic 2D image fragment reassembly. First, we compute the potential matching between each pair of the image fragments based on their geometry and color. After that, a novel multi-piece matching algorithm is proposed to reassemble the overall image fragments. Finally, the reassembly result is refined by applying the graph optimization algorithm. We perform experiments to evaluate our algorithm on multiple torn real-world images, and demonstrate the robustness of this new assembly framework outperforms the existing algorithms in both reassembly accuracy (in handling accumulated pairwise matching error) and robustness (in handling small image fragments).     

A multi-threshold segmentation approach based on Artificial Bee Colony optimization

This paper explores the use of the Artificial Bee Colony (ABC) algorithm to compute threshold selection for image segmentation. ABC is an evolutionary algorithm inspired by the intelligent behavior of honey-bees which has been successfully employed to solve complex optimization problems. In this approach, an image 1-D histogram is approximated through a Gaussian mixture model whose parameters are calculated by the ABC algorithm. In the model, each Gaussian function represents a pixel class and therefore a threshold point. Unlike the Expectation-Maximization (EM) algorithm, the ABC method shows fast convergence and low sensitivity to initial conditions. Remarkably, it also improves complex time-consuming computations commonly required by gradient-based methods. Experimental results over multiple images with different range of complexity validate the efficiency of the proposed technique with regard to segmentation accuracy, speed, and robustness. The paper also includes an experimental comparison to the EM and to one gradient-based method which ultimately demonstrates a better performance from the proposed algorithm.     

自适应搜索空间的混沌蜂群算法

针对人工蜂群（ABC）算法的不足,以种群收敛程度为依据,结合混沌优化的思想,提出一种改进的人工蜂群算法—自适应搜索空间的混沌蜂群算法（SA-CABC）。其基本思想是在原搜索区域的基础上,根据每次寻优的结果自适应地调整搜索空间,逐步缩小搜索区域,并利用混沌变量的内在随机性和遍历性跳出局部最优点,最终获得最优解。基于六个标准测试函数的仿真结果表明, 本算法能有效地加快收敛速度,提高最优解的精度, 其性能明显优于基本ABC算法,尤其适合高维的复杂函数的寻优。     

云变异人工蜂群算法

针对传统人工蜂群算法存在收敛速度慢和易陷入局部最优的问题,提出一种基于云模型的改进人工蜂群算法。通过正态云算子计算候选位置,自适应调整算法的局部搜索范围,以提高算法的收敛速度和勘探能力。为保持种群多样性,引入一个新的概率选择策略,使较差的个体具有较大的选择概率,并且利用历史最优解探索新的位置。标准复合函数测试表明,改进算法的收敛速度和求解精度得到提升,优于一些新近提出的改进人工蜂群算法。