Packing equal circles into a circle with circular prohibited areas

The paper considers the problem of packing a maximal number of identical circles of a given radius into a multiconnected domain. The domain is a circle with prohibited areas to be finite unions of circles of given radii. We construct a mathematical model of the problem and investigate its characteristics. The starting points are constructed in a random way or on the ground of the hexagonal lattice. To find the local maxima, a modification of the Zoutendijk method of feasible directions and a strategy of active inequalities are applied. We compare our results with the benchmark instances of packing circles into circular and annular containers. A number of numerical examples are given.     

布氏硬度自动测量中多圆检测方法

圆检测应用广泛,是布氏硬度自动测量的关键。针对圆检测中存在圆分裂、多个圆、不完整圆的情况,提出一种基于交叉圆合并、凸包点迭代纯化最小二乘拟合的圆检测方法。首先对图像进行纹理增强并二值化,其次提取有效区域的最小外接矩形,并得到圆弧与最小外接矩形的三个切点,得到初始圆,然后合并有交叉的圆。最后求合并圆的轮廓点与其凸包的交集,进行迭代纯化最小二乘拟合,最终得到亚像素级的圆半径值。最后通过实际应用测试,验证了论文方法的有效性。     

基于Blob算法的标记圆检测技术研究

大型物体的三维测量中,大多采用基于标记圆的拼接,标记圆检测的正确性和定位精度决定了拼接的精度。在二值化图像上运用Blob分析得到标记圆的轮廓信息,综合使用标记圆灰度特性、尺寸特征、圆形度和误差准则来筛选标记圆,圆心定位采用具有亚象素定位精度的最小二乘拟合法。实验表明该方法抗干扰强,标记圆的识别率可达98%。     

Packing unequal circles using formulation space search

In this paper we present a heuristic algorithm for the problem of packing unequal circles in a fixed size container such as the unit circle, the unit square or a rectangle. We view the problem as being one of scaling the radii of the unequal circles so that they can all be packed into the container. Our algorithm is composed of an optimisation phase and an improvement phase. The optimisation phase is based on the formulation space search method whilst the improvement phase creates a perturbation of the current solution by swapping two circles. The instances considered in this work can be categorised into two: instances with large variations in radii and instances with small variations in radii. We consider six different containers: circle, square, rectangle, right-angled isosceles triangle, semicircle and circular quadrant. Computational results show improvements over previous work in the literature.     

圆形标志投影偏心差补偿算法

目的 圆形标志目前正广泛地应用于各类视觉测量系统,其圆心定位精度决定了测量系统的测量精度。当相机主光轴与标志表面不平行时,圆被映射为椭圆,圆心位置计算产生偏差。光轴与标志表面夹角较大或标志较大等情况下会产生较大的偏心差进而严重影响系统测量精度。为此,提出一种基于三同心圆圆形标志的投影偏心差补偿算法。方法 算法基于三同心圆的圆形标志设计,根据3组椭圆拟合中心坐标解算偏心差模型进行计算补偿。结果 针对圆形标志偏心差问题,同心圆补偿算法取得良好效果,有效提升了圆形标志定位精度。仿真结果表明,在拍摄角度、拍摄距离、圆形标志大小不同的情况下,偏心差在像素量级,补偿后偏心差在10^-11像素量级。实物实验结果表明,若设计有直径分别为6 cm,12 cm,18 cm的三同心圆标志,经解算补偿结果较以往两同心圆算法精度提高一倍,偏心差值减小80%,测量误差在0.1 mm左右。结论 本文提出了一种新的偏心差补偿算法,利用三同心圆标志增加约束解算偏心差。与以往偏心差补偿算法相比,此方法精度更高,且无需预先平差解算相机与目标的距离、拍摄角等参数,仅需要知道标志圆形半径比例及椭圆中心坐标即可计算补偿,具有很高的实用性,可用于改善基于非编码标志点的深度像匹配、基于圆形标志点的全自动相机标定方法、视觉导航定位等应用中。     

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.     

Multi-circle detection on images using artificial bee colony (ABC) optimization

Hough transform has been the most common method for circle detection, exhibiting robustness, but adversely demanding considerable computational effort and large memory requirements. Alternative approaches include heuristic methods that employ iterative optimization procedures for detecting multiple circles. Since only one circle can be marked at each optimization cycle, multiple executions ought to be enforced in order to achieve multi-detection. This paper presents an algorithm for automatic detection of multiple circular shapes that considers the overall process as a multi-modal optimization problem. The approach is based on the artificial bee colony (ABC) algorithm, a swarm optimization algorithm inspired by the intelligent foraging behavior of honeybees. Unlike the original ABC algorithm, the proposed approach presents the addition of a memory for discarded solutions. Such memory allows holding important information regarding other local optima, which might have emerged during the optimization process. The detector uses a combination of three non-collinear edge points as parameters to determine circle candidates. A matching function (nectar-amount) determines if such circle candidates (bee-food sources) are actually present in the image. Guided by the values of such matching functions, the set of encoded candidate circles are evolved through the ABC algorithm so that the best candidate (global optimum) can be fitted into an actual circle within the edge-only image. Then, an analysis of the incorporated memory is executed in order to identify potential local optima, i.e., other circles. The proposed method is able to detect single or multiple circles from a digital image through only one optimization pass. Simulation results over several synthetic and natural images, with a varying range of complexity, validate the efficiency of the proposed technique regarding its 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.     

A menagerie of rational B-spline circles

The article was motivated by J. Blinn's column on the many ways to draw a circle (see ibid., vol.7, no.8, p.39-44, 1987). The authors have found several other ways to represent the circle as a nonuniform rational B-spline curve, which they present. Square-based methods, infinite control points, triangle-based methods, general circular arcs and rational cubic circles are some of the methods and types of circle discussed     

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.     

改进的Kasa算法及其在圆拟合中的精度分析

Kasa算法是应用最为广泛的代数圆拟合方法之一,但在短圆弧采样条件下拟合结果不够理想,且拟合精度随圆半径的减小而变差.在Kasa代数算法的基础上,提出RS约束算法.通过坐标旋转使采样点具有对称性,以横坐标最大值作为半径约束条件修正拟合算法.仿真测试验证了RS约束算法具备更强的鲁棒性,能够消除半径变化对拟合精度的影响,在短圆弧情况下该算法的拟合精度远优于Ka-sa算法.     

New heuristics for packing unequal circles into a circular container

We propose two new heuristics to pack unequal circles into a two-dimensional circular container. The first one, denoted by A1.0, is a basic heuristic which selects the next circle to place according to the maximal hole degree rule. The second one, denoted by A1.5, uses a self look-ahead strategy to improve A1.0. We evaluate A1.0 and A1.5 on a series of instances up to 100 circles from the literature and compare them with existing approaches. We also study the behaviour of our approach for packing equal circles comparing with a specified approach in the literature. Experimental results show that our approach has a good performance in terms of solution quality and computational time for packing unequal circles.     

Reconstruction of a digital circle

Since digitization always causes some loss of information, reconstruction of the original figure from a given digitization is a challenging task. Reconstruction of digital circles has already been addressed in the literature. However, an in-depth analysis of an OBQ image of a continuous circle as well as a solution to its domain construction problem is still lacking. In this paper a detailed analysis of digital circles has been carried out. A modified I_R method is formulated to numerically compute the domain of each digital quarter circle for a given radius. Several properties of the OBQ image of a circle reveal that in many cases it is possible to split a digital circle into four digital quarter circles, such that the domains of the individual quarter circles can be combined to obtain the domain of the full circle. Moreover, the domain of a quarter circle is geometrically characterized.     

Constrained circles packing test problems: all the optimal solutions known

Taking a satellite module layout design as engineering background, this paper gives constrained test problems for an unequal circle packing whose optimal solutions are all given. Given a circular container D with radius R, the test problem can be constructed in the following steps. First, M=217 circles are packed into D without overlaps by ‘packing with a tangent circle’ to get the values of radii and centroid coordinates of the circles, which are expressed by R. Then the 217 circles are arranged in descending sequence of radius and are divided into 23 groups according to the radius. Finally, seven test problems are constructed according to the circles of q=1, 2, …, 7 groups. The optimal solution to the test problems as well as its optimality and uniqueness proof are also presented. The experimental results show that the test problems can effectively evaluate performances of different evolutionary algorithms.     

Simple and branched skins of systems of circles and convex shapes

Recently, there has been considerable interest in skinning circles and spheres. In this paper we present a simple algorithm for skinning circles in the plane. Our novel approach allows the skin to touch a particular circle not only at a point, but also along a whole circular arc. This results in naturally looking skins. Due to the simplicity of our algorithm, it can be generalised to branched skins, to skinning simple convex shapes in the plane, and to sphere skinning in 3D. The functionality of the designed algorithm is presented and discussed on several examples.     

有限包络圆族的快速生成方法及其在二维布局优化中的应用

为了有效地实施有限包络圆族方法(FCM),大幅度减少包络圆数目,达到一圆多用、圆尽其用的目的,提出3种FCM自动化建模方法:二分法、三步划分法和带间隙的改进三步划分法.二分法利用组件各边长度和设置的容差大小得到该边的候选包络圆,若该圆不满足组件所有边的容差要求,则将该边不断地对分,直至所得到的包络圆满足各边的容差要求;三步划分法和带间隙的改进三步划分法则以组件区域为划分对象,依次对组件多边形凸顶角、凸扇形区和多边形各边剩余线段划分包络圆,且带间隙的改进三步划分法则允许包络圆在组件边界上以适当的间隙分布.最后通过算例表明,三步划分法和带间隙的改进三步划分法能用尽量少的包络圆逼近二维组件,在组件装填布局优化设计中明显提高了组件装填布局优化效率.     

Finding circular shapes in an image on a pyramid architecture

The problem of finding circular shapes in an image using a pyramid architecture is considered. In this paper we have defined a new transformation that converts circles in an image to a family of straight lines allowing the problem to be converted to line detection which can be solved by Hough transform algorithms. Also, based on this new transformation we have developed two algorithms for circle detection using a pyramid architecture.     

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.     

基于RSSI的无线传感器网络圆环质心定位算法

针对无线传感器网络质心算法受节点分布均匀程度的影响, 少数锚节点增大定位误差, 提出了一种圆环质心算法. 该算法以未知节点为圆心, 将未知节点通信区域划分成半径由大到小的圆环, 通过圆环剔除容易增大定位误差的锚节点, 筛选出合适的锚节点, 并在圆环上寻找近似等边三角形来进一步减小定位误差. 同时提出了利用RSSI值来形成圆环的方法. 仿真结果表明, 在100m×100m的区域中, 随机投放100个节点, 通信半径为20m, 锚节点数为20时, 圆环质心算法与质心算法相比, 定位精度提高了11%.