サーフェスポイントのセグメントからサークル中心を見つける

Question

円筒オブジェクトのサーフェス測定の数に基づいてサークルの中心を見つける必要があります。

私は現在、（How to determine the radius and center of a circle when only three noncollinear points are known?から採取された）中心を見つけるために3つの点に基づいて（C＃で書かれた）簡略化されたアルゴリズムを使用する：

private Point CircleCenter(List<Point> points, double p1Skip, double p2Skip, double p3Skip) 
{ 
    var p1 = points.Skip((int)(points.Count * p1Skip)).First(); 
    var p2 = points.Skip((int)(points.Count * p2Skip)).First(); 
    var p3 = points.Skip((int)(points.Count * p3Skip)).First(); 

    double mr = (p2.Y - p1.Y)/(p2.X - p1.X); 
    double mt = (p3.Y - p2.Y)/(p3.X - p2.X); 

    double centerX = (mr * mt * (p3.Y - p1.Y) + mr * (p2.X + p3.X) - mt * (p1.X + p2.X))/(2 * (mr - mt)); 

    double centerY = (-1/mr) * (centerX - ((p1.X + p2.X)/2)) + ((p1.Y + p2.Y)/2); 

    return new Point(centerX, centerY, p1.Z); 
} 

問題は、この方法はノイズに非常に敏感であることです。いずれかのポイントがオフの場合、もちろん、それは中心ポイントに影響します。 私は、各断面積に対して利用可能な640の表面点を有しており、3点以上を使用することができるはずであることを示す。

私は、既存のアルゴリズムがより多くの点で拡張することが可能であると推測していますが、どのように把握できません。

Answer 1

私の数学の同僚の助けを借りて、私は最小二乗行列計算を使って解を得ました。

使用アルゴリズムはhereと記載されています。

public static void FitCircle(IEnumerable<Point> points, out double x0, out double y0, out double r) 
{ 
    setMklProvider(); 
    DenseMatrix A = DenseMatrix.Create(3, 3, (i, j) => 0); 
    DenseMatrix b = DenseMatrix.Create(3, 1, (i, j) => 0); 
    A[0, 0] = points.Sum(point => point.X * point.X); 
    A[0, 1] = points.Sum(point => point.X * point.Y); 
    A[0, 2] = points.Sum(point => point.X); 
    A[1, 0] = A[0, 1]; 
    A[1, 1] = points.Sum(point => point.Y * point.Y); 
    A[1, 2] = points.Sum(point => point.Y); 
    A[2, 0] = A[0, 2]; 
    A[2, 1] = A[1, 2]; 
    A[2, 2] = points.Count(); 
    b[0, 0] = points.Sum(point => point.X * (point.X * point.X + point.Y * point.Y)); 
    b[1, 0] = points.Sum(point => point.Y * (point.X * point.X + point.Y * point.Y)); 
    b[2, 0] = points.Sum(point => point.X * point.X + point.Y * point.Y); 
    var x = A.QR().Solve(b); 
    x0 = x[0, 0]/2; 
    y0 = x[1, 0]/2; 
    r = Math.Sqrt(x[2, 0] + x0 * x0 + y0 * y0); 
} 

private static void setMklProvider() 
{ 
    if (!_mklProviderSet) MathNet.Numerics.Control.LinearAlgebraProvider = new MathNet.Numerics.Algorithms.LinearAlgebra.Mkl.MklLinearAlgebraProvider(); 
} 

このソリューションは、少なくとも自分のデータでは、本当に素晴らしい繰り返し結果を生成します。 DenseMatrixはMathNetライブラリの一部です。ユーザsamgakが示唆されているように、さらに、ノイズを低減する

EDIT

、Iは、精度向上、反復還元アプローチ追加：円を固定... 3点を

double x0, y0, r; 
FitCircle(surfacePoints, out x0, out y0, out r); 
var center = new Point(x0, y0, surfacePoints.First().Z); 

int reductionIterations = 10; 
var reducedSet = surfacePoints; 

for (int i = 1; i < reductionIterations; i++) 
{ 
    var orderedByDistanceToCenter = reducedSet.OrderBy(p => (p-center).GetRho()).ToList(); 

    reducedSet = orderedByDistanceToCenter 
     .Skip((int)(orderedByDistanceToCenter.Count * (i/10f))) 
     .Take((int)(orderedByDistanceToCenter.Count - orderedByDistanceToCenter.Count * (i/10f)*2)) 
     .ToList(); 

    // Reduced to zero, abort 
    if (reducedSet.Count < 3) 
     break; 

    FitCircle(reducedSet, out x0, out y0, out r); 
    center = new Point(x0, y0, reducedSet.First().Z); 
} 

public static double GetRho(this Point p) => Math.Sqrt(p.X * p.X + p.Y * p.Y); 

Answer 2

（コメントとしてこれを残したが、私はできないだろう）

私は、あなたが探している用語は「姿勢推定」だと思います。あなたの観測に最適なフィッティングモデルを見つけるために、RANSACのような反復メソッドを使用することを検討しましたか？

Answer 3

ポイントが均一に分布していることがわかっている場合、解は非常に単純です：平均です。センターの平均をかなり正確にするために多くのポイントがあります。

ポイントがうまく分散されていない場合（つまり、シェイプの片側に多くのポイントがある場合）、それでもやりとりできますが、もう少し複雑です。あなたは二次方程式の系を考えることができ、各点と中心との距離と推測半径の差を最小にする点を探しています。これはかなり難しい数学なので、あなたのためにそれを解決するための図書館を探してみるべきです。