用于圆检测的最小二乘法

Question

我试图用最小二乘法对数据点的子集进行激光扫描的圆检测。由于测量只得到一个圆的一部分，最小二乘法返回错误的结果，报告一个圆比实际更接近激光。

算法的结果显示在图片中。散点点表示激光测量，圆周以算法返回的点为中心。灰色半透明形状表示机器人进行扫描(在这个形状的左边和右边的激光)。

我只对圆的局部坐标感兴趣，它知道半径RR。

PS。我假设扫描被分割成簇(self.clustersi是一个集群)，这是x，y激光点的列表。

def circle(x, scan):
    xc, yc = x
    f = sqrt((scan[:,0] - xc)**2 + (scan[:,1] - yc)**2) - RR
    return f


def optimize_detect_circles(self):

    centre = [1,1]

    for i in range(0, self.number_of_clusters):
        range_points = np.array(self.clusters[i])

        sol = optimize.root(circle, centre, args=(range_points), method='lm')
        self.circle_candidates.append(sol.x)
        print sol.x

这张照片是：

​

​

Answer 1

1,1离正确的值太远了；您很可能陷入某种局部最优状态。

试着从一个离真正的中心更近的地方开始。首先将一条直线拟合到集群中，然后将点分成两半，根据它们投射到的线的一半；然后将两条线拟合成新的两个子簇中的一条；在中间点为这两个垂直点找到一个交点。

这是基于你的星系团是跨度不超过180度的弧线，它们看起来就是这样。如果没有，只需重复细分，得到四个和弦而不是两个和弦。

Answer 2

你可以用圆Hough变换找到圆圈--如果你事先知道圆圈的半径，这就特别容易了。

我从短距图像的这个过程的文档中自由地借用，我将运行的以下代码组合在一起，但可能需要进行一些调整才能找到圆圈：

import numpy as np
import matplotlib.pyplot as plt

import skimage
from skimage import data, filter, io
from skimage.transform import hough_circle
from skimage.feature import peak_local_max
from skimage import data, color
from skimage.draw import circle_perimeter

theImage = np.sum(io.imread("w1s31.png"),2)/4 # Image to greyscale

hough_radii = np.arange(61, 69, 2) # These are the radii to search for
hough_res = hough_circle(theImage, hough_radii)
centers = []
accums = []
radii = []

for radius, h in zip(hough_radii, hough_res):
    # For each radius, extract two circles
    num_peaks = 2
    peaks = peak_local_max(h, num_peaks=num_peaks)
    centers.extend(peaks)
    accums.extend(h[peaks[:, 0], peaks[:, 1]])
    radii.extend([radius] * num_peaks)

# Draw the most prominent 5 circles
image = color.gray2rgb(theImage)
for idx in np.argsort(accums)[::-1][:5]:
    center_x, center_y = centers[idx]
    radius = radii[idx]
    cx, cy = circle_perimeter(center_y, center_x, radius)
    theImage[cy, cx] = (1)

plt.imshow(theImage, cmap=plt.cm.gray)
plt.show()

Answer 3

下面是从这文件中实现的圆圈检测的一个小片段。

该算法总是有效的，且不具有线性复杂度。

​

var add = function(a,b){ return a+b; };
var add_uu = function(a,b){ return a+b[0]*b[0]; };
var add_uv = function(a,b){ return a+b[0]*b[1]; };
var add_vv = function(a,b){ return a+b[1]*b[1]; };
var add_uuu = function(a,b){ return a+b[0]*b[0]*b[0]; };
var add_vvv = function(a,b){ return a+b[1]*b[1]*b[1]; };
var add_uvv = function(a,b){ return a+b[0]*b[1]*b[1]; };
var add_uuv = function(a,b){ return a+b[0]*b[0]*b[1]; };
var getx = function(e){ return e[0]; };
var gety = function(e){ return e[1]; };

$(document).ready(function () {
  var paper = Raphael("canvas");
  var points=[];
    
  $("#canvas").mousedown(function (e) {
    var x = e.offsetX;
    var y = e.offsetY;
    points.push([x,y]);
    paper.circle(x, y, 1);
 });
    
 $("#clear").click(function(){
   paper.clear();
   points = [];
 });
    
 $("#go").click(function(){
     var N = points.length;

     var xb = points.map(getx).reduce(add,0) / N;
     var yb = points.map(gety).reduce(add,0) / N;
     
     var u = points.map(function(e){return [e[0]-xb,e[1]-yb];});
     
     var a1 = u.reduce(add_uu,0);
     var b1 = u.reduce(add_uv,0);
     var c1 = 0.5*(u.reduce(add_uuu,0) + u.reduce(add_uvv,0));
     var a2 = u.reduce(add_uv,0);
     var b2 = u.reduce(add_vv,0);
     var c2 = 0.5*(u.reduce(add_vvv,0) + u.reduce(add_uuv,0));
     
     var q = a2/a1;
     var vc = (c2-q*c1)/(b2-q*b1);
     var uc = (c1-b1*vc)/a1;
     
     var r = Math.sqrt(uc*uc+vc*vc+(a1+b2)/N);
     var x = uc+xb;
     var y = vc+yb;
     
     paper.circle(x, y, r).attr({"stroke":"#f00","stroke-width":2});
     
     var e = points.reduce(function(p,c) {
       var t = r*r - (c[0]-x)*(c[0]-x) - (c[1]-y)*(c[1]-y);
       return p+t*t;
     },0);
     
     console.log("Residue = " + e);
 });
});

#canvas {
  width: 600px;
  height: 400px;
  border: 2px dotted #ccc;
  cursor: crosshair;
}

<script src="http://cdnjs.cloudflare.com/ajax/libs/raphael/2.1.0/raphael-min.js"></script>
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
<button id="clear">Clear</button>
<button id="go">Compute circle</button>
<div id="canvas"></div>

​