흩어진 지점에서 타원 평가/피팅

Question

여기 거래가 있습니다. 여러 점 (X, Y)이 '타원형'모양을 이룹니다.

필자는 가능한 '최상의'타원을 평가하고 그 속성 (a, b, F1, F2) 또는 타원의 중심만을 얻고 싶습니다.

모든 아이디어/리드가 인정 될 것입니다.

길래드.

Answer 1

작업을 수행 할 수있는 Matlab 함수 fit_ellipse이 있습니다. 타원의 직각 거리 맞춤 방법에 대해서는 this paper도 있습니다. 직사각형 타원형에 대한 웹 검색은 다른 많은 리소스도 함께 표시합니다.

Answer 2

나는 어떻게 문제에 접근 할 것인가를 설명 할 것이다. 언덕 오르기 법을 제안합니다. 먼저 점의 중력 중심을 시작점으로 계산하고 a와 b에 대해 두 가지 값을 선택합니다 (임의의 양수 값이 가능). 당신은 맞춤 기능이 필요하고 나는 주어진 타원에 누워 (충분히 가까이) 포인트의 수를 반환을 제안 :

int fit(x, y, a, b) 
    int res := 0 
    for point in points 
    if point_almost_on_ellipse(x, y, a, b, point) 
     res = res + 1 
    end_if 
    end_for 
    return res 

지금 일부 step로 시작합니다. 나는 엘리트의 가장 좋은 중심이 첫 번째 점에서 멀리 떨어져 결코 step이 될 수 없을만큼 충분히 큰 값을 선택합니다. 그런 큰 가치를 선택하는 것은 필요하지 않지만 알고리즘의 가장 느린 부분은 최상의 센터에 가까워 질수록 더 큰 가치가 더 좋은 시간입니다.

그래서 지금까지 몇 가지 초기 지점이 ( X, Y)와, B 및 일부 초기 값 및 초기 단계 . 알고리즘은 반복적으로 현재 점의 이웃 중 가장 좋은 점을 선택합니다. 그렇지 않은 경우 두 단계를 줄입니다. 여기서 '최고'는 맞는 함수를 사용하는 것을 의미합니다. 또한 위치는 네 개의 값 (x, y, a, b)에 의해 정의되고 이웃은 8 : (x + -step, y, a, b), (x, y + -step, a, b), (x + - 스텝, y + 스텝, y + 스텝, b + 스텝) (예 : a, b) 등). 여기에 당신이 것을

neighbours = [[-1, 0, 0, 0], [1, 0, 0, 0], [0, -1, 0, 0], [0, 1, 0, 0], 
       [0, 0, -1, 0], [0, 0, 1, 0], [0, 0, 0, -1], [0, 0, 0, 1]] 
iterate (cx, cy, ca, cb, step) 
    current_fit = fit(cx, cy, ca, cb) 
    best_neighbour = [] 
    best_fit = current_fit 
    for neighbour in neighbours 
    tx = cx + neighbour[0]*step 
    ty = cx + neighbour[1]*step 
    ta = ca + neighbour[2]*step 
    tb = cb + neighbour[3]*step 
    tfit = fit(tx, ty, ta, tb) 
    if (tfit > best_fit) 
     best_fit = tfit 
     best_neighbour = [tx,ty,ta,tb] 
    endif 
    end_for 
    if best_neighbour.size == 4 
    cx := best_neighbour[0] 
    cy := best_neighbour[1] 
    ca := best_neighbour[2] 
    cb := best_neighbour[3] 
    else 
    step = step * 0.5 
    end_if 

을 그리고 단계의 값이 (인스턴스 1E-6) 지정된 임계 값보다 작은 될 때까지 반복을 계속하는 방법이다. 어떤 언어를 사용하고 싶은지 모르겠으므로 의사 코드로 모든 것을 작성했습니다.

이 방법으로 찾은 답이 최적이라고 보장 할 수는 없지만 충분히 근사 할 것이라고 확신합니다.

여기에 대한 기사는 hill climbing입니다.

Answer 3

Wild Magic 라이브러리에는 타원 피팅 기능이 포함되어 있다고 생각합니다. 방법 설명이있는 article이 있습니다.

Answer 4

문제는 "최고"를 정의하는 것입니다. 당신의 경우에 무엇이 최선입니까? pointS의 n %를 포함하는 가장 작은 영역을 가진 타원?

"best"를 확률로 정의하면 간단히 점의 공분산 행렬을 사용하고 오차 타원을 계산할 수 있습니다.

"다 변수 가우스 분포"의 오차 타원은 사용자가 결정한 신뢰 구간에 해당하는 점을 포함합니다.

많은 컴퓨팅 패키지가 해당 고유 값 및 고유 벡터와 함께 공분산을 계산할 수 있습니다. 타원의 각도는 x 축과 가장 큰 고유치에 해당하는 고유 벡터 사이의 각도입니다. 반축은 고유치의 역수입니다.

루틴에서 정규화 된 모든 항목을 반환하면 (어떤 방식으로해야합니까) 알파 - 신뢰 구간을 얻기 위해 모든 요소에 어떤 요인을 곱할 것인지 결정할 수 있습니다.

Answer 5

에 의해 제안 된 방법 피팅 타원 :

Z. L. Szpak, W. Chojnacki, 그리고 A. 반 덴 Hengel을. 중심, 축 및 방향에 대한 신뢰 영역 및 불확도 측정 값으로 타원 피팅이 보장됩니다. J. Math. 이미징 비전, 2015.

에 관심이있을 수 있습니다. 대수 및 기하학적 타원형 매개 변수의 추정치를 매개 변수 추정의 불확실성을 나타내는 공분산 행렬과 함께 제공합니다. 그들은 또한 추정과 연관된 평면 95 % 신뢰 영역을 계산하는 수단을 제공하여 타원 적합도의 불확실성을 시각화 할 수 있습니다.

미리 인쇄 된 버전의 문서는 저자 웹 사이트 (http://cs.adelaide.edu.au/~wojtek/publicationsWC.html)에서 볼 수 있습니다. 메서드의 MATLAB 구현도 다운로드 할 수 있습니다. https://sites.google.com/site/szpakz/source-code/guaranteed-ellipse-fitting-with-a-confidence-region-and-an-uncertainty-measure-for-centre-axes-and-orientation