랜덤 표본 컨센서스

Random sample consensus

랜덤 표본 컨센서스(RANSAC)는 특이치가 추정치의 값에 영향을 미치지 않도록 합의되어야 할 때 특이치를 포함하는 관측된 데이터 집합에서 수학 모델의 모수를 추정하는 반복적인 방법이다.따라서 특이치 검출 방법으로도 해석할 수 있다.[1]일정한 확률로만 합리적인 결과를 낸다는 점에서 비결정적 알고리즘으로, 이 확률은 더 많은 반복이 허용될수록 증가한다.이 알고리즘은 1981년 피슐러와 볼레스가 SRI 인터내셔널에서 처음 발표한 것이다.그들은 RANSAC를 사용하여 위치 결정 문제(LDP)를 해결했다. 이 문제의 목적은 이미지로 투영되는 공간의 점을 파악하여 위치를 알 수 있는 랜드마크로 만드는 것이다.

RANSAC는 반복된 무작위 하위 샘플링을 사용한다.[2]기본적인 가정은 데이터가 소음의 영향을 받을 수 있지만 일부 모형 모수 집합에 의해 분포가 설명될 수 있는 데이터와 모델에 맞지 않는 데이터인 "특이치"로 구성되어 있다는 것이다.예를 들어, 특이치는 소음의 극단값이나 잘못된 측정 또는 데이터 해석에 대한 잘못된 가설에서 발생할 수 있다.RANSAC는 또한 (대개 작은) 상수 집합이 주어진 경우, 이 데이터를 최적으로 설명하거나 적합시키는 모형의 모수를 추정할 수 있는 절차가 있다고 가정한다.

간단한 예로는 관측치 집합에 2차원의 선을 적합시키는 것이다.이 집합에 대략적으로 선에 적합할 수 있는 점, 즉 이 선에 적합할 수 없는 점, 특이치가 모두 포함되어 있다고 가정할 때, 라인 적합을 위한 단순 최소 제곱법은 일반적으로 상수와 특이치를 포함하여 데이터에 맞지 않는 선을 생성한다.특이치를 포함한 모든 포인트에 최적으로 적합하기 때문이다.반면 RANSAC는 특이치를 배제하고 계산에 상수만을 사용하는 선형 모델을 찾으려고 한다.이것은 선형 모델을 데이터의 여러 무작위 샘플링에 장착하고 데이터의 하위 집합에 가장 적합한 모델을 반환함으로써 이루어진다.상아들은 상아들과 특이치의 무작위 혼합물보다 더 선형적으로 연관되는 경향이 있기 때문에, 전체적으로 상아들로 구성된 랜덤 부분집합은 최상의 모형 적합성을 가질 것이다.실제로 상어의 부분집합이 무작위로 샘플링된다는 보장은 없으며, 알고리즘이 성공할 확률은 데이터 내 상어의 비율과 여러 알고리즘 파라미터의 선택에 따라 달라진다.

개요

RANSAC 알고리즘은 관측된 데이터를 무작위로 추출하여 모형의 매개변수를 추정하는 학습 기법이다.데이터 요소에 상수와 특이치가 모두 포함된 데이터 집합의 경우, RANSAC는 투표 방식을 사용하여 최적의 적합성 결과를 찾는다.데이터 집합의 데이터 요소는 하나 이상의 모델에 대해 투표하는 데 사용된다.이 투표 방식의 구현은 두 가지 가정을 기반으로 한다: 소음 특성이 단일 모델에 대해 일관성 있게 투표하지 않을 것이며(few outlier) 좋은 모델에 동의할 수 있는 충분한 특징이 있다(fef missed data)RANSAC 알고리즘은 반복적으로 반복되는 두 단계로 구성된다.

  1. 첫 번째 단계에서는 최소 데이터 항목을 포함하는 샘플 하위 집합이 입력 데이터 집합에서 랜덤하게 선택된다.적합 모형과 해당 모형 매개변수는 이 표본 부분 집합의 요소만을 사용하여 계산된다.샘플 서브셋의 카디널리티는 모델 파라미터를 결정하기에 충분한 최소값이다.
  2. 두 번째 단계에서 알고리즘은 전체 데이터 집합의 어떤 요소가 첫 번째 단계에서 얻은 추정 모델 파라미터에 의해 인스턴스화된 모델과 일치하는지 점검한다.데이터 요소가 잡음의 효과로 인한 최대 편차를 정의하는 일부 오차 임계값 내에서 추정 모델 모수 집합에 의해 인스턴스화된 적합 모델에 맞지 않는 경우 특이치로서 간주된다.

피팅 모델에 대해 얻은 상수 집합을 컨센서스 집합이라고 한다.RANSAC 알고리즘은 특정 반복에서 설정한 합의서가 충분한 인라이어를 가질 때까지 위의 두 단계를 반복적으로 반복한다.

RANSAC 알고리즘에 대한 입력은 관측된 데이터 값 집합, 관측치에 어떤 종류의 모형을 적합시키는 방법 및 일부 신뢰 매개변수다.RANSAC는 다음과 같은 단계를 반복하여 목표를 달성한다.

  1. 원본 데이터의 임의 부분 집합을 선택하십시오.이 부분집합을 가상의 상아라고 불러라.
  2. 모형은 가상의 상아 집합에 적합하다.
  3. 그런 다음 다른 모든 데이터를 적합된 모델에 대해 테스트한다.일부 모델별 손실 함수에 따라 추정된 모형에 잘 맞는 점은 합의 집합의 일부로 간주된다.
  4. 충분히 많은 포인트가 합의 집합의 일부로 분류되었다면 추정 모형은 합리적으로 양호하다.
  5. 그 후, 합의된 모든 구성원을 사용하여 재추정함으로써 모델이 개선될 수 있다.

이 절차는 너무 적은 점수가 컨센서스 집합의 일부이기 때문에 기각되는 모델을 생산할 때마다 일정한 횟수를 반복하거나, 컨센서스 집합 크기와 함께 정제된 모델을 만든다.후자의 경우, 정제된 모델의 컨센서스 세트가 이전에 저장한 모델보다 크면 우리는 정제된 모델을 유지한다.

알고리즘.

일반 RANSAC 알고리즘은 다음과 같이 작동한다.

주어진: 데이터 – 관측치의 집합. 모형 – 관측된 데이터 점을 설명하는 모형.n – 모형 모수를 추정하는 데 필요한 최소 데이터 포인트 수. k – 알고리즘에서 허용되는 최대 반복 횟수. t – 모델별로 잘 맞는 데이터 포인트를 결정하는 임계값. d – 모형이 데이터에 잘 적합한다고 주장하기 위해 필요한 근접 데이터 포인트 수.Return: bestFit – 데이터를 가장 잘 적합시키는 모델 매개변수(또는 좋은 모델이 발견되지 않는 경우 null) 반복 = 0 bestFit = null bestEr = 매우 큰 을 반복하는 동안 < k아마도inlier :=n data maybeModel := model에 장착된 model parametersInliers alsoInliers := maybe에 없는 데이터의 모든 점에 대해 빈 집합inlier는 point가 maybeModel에 적합할 경우 t add point보다 작은 오류로 또한 inliers end대한 // 이것은 우리가 좋은 모델을 찾을 수 있음을 의미한다 // 이제 그것이 얼마나 좋은지 시험한다. 더 나은 모델 := model parameters는 아마도 모든 포인트에 적합할 것이다.Inlier 및 Inliers thisErr :=이러한 포인트에 얼마나 잘 맞는지를 나타내는 척도:=이러한 <BestErr> 다음에 bestFit :=betterModel bestEr :=이러한 포인트에 얼마나 잘 맞는지나타내는 척도.

매개변수

데이터 점이 모델 t에 적합한 시기를 결정하는 임계값과 모델이 데이터 d에 잘 적합한다고 주장하는 데 필요한 근접 데이터 포인트 수는 애플리케이션과 데이터 세트의 특정 요건에 기초하여 결정되며, 실험적인 평가에 기초할 수 있다.그러나 반복 횟수는 이론적 결과를 이용하여 원하는 성공 확률 p의 함수로 결정할 수 있다.rANSAC 알고리즘이 실행 후 적어도 하나의 유용한 결과를 제공할 수 있는 원하는 확률을 p로 한다.RANSAC는 일부 반복에서 모델 파라미터가 추정된 n개의 점을 선택할 때 입력 데이터 세트에서 인라이어만 선택하는 경우 성공적인 결과를 반환한다. 을(를) 단일 점을 선택할 때마다 inlier를 선택할 확률로 설정(즉,

= 데이터의 Inlier 수/데이터의 점 수

으로 w 은(는) 사전에 잘 알려져 있지 않지만 약간의 대략적인 값이 주어질 수 있다.모델을 추정하는 데 필요의 점을 독립적으로 선택한다고 가정할 w w^{모든 n개의 점이 상각일 확률이고 - n개의 점 중 하나 이상이 특이치가 될 확률로, 불량 모형이 다음과 같이 추정될 가능성을 의미한다.이 점 세트k의 힘에 대한 확률은 알고리즘이 모든 상각인 n개의 점 집합을 선택하지 않을 확률이며, 이는 - 과 동일해야 한다 결과적으로,

양쪽의 로그를 찍은 후

이 결과는 n개의 데이터 점, 즉 한 번 선택한 점이 교체되고 동일한 반복에서 다시 선택될 수 있다고 가정한다.이것은 종종 합리적인 접근법이 아니며, 대체하지 않고 포인트를 선택한 경우에는 k에 대한 파생값을 상한으로 받아들여야 한다.예를 들어, 위의 그림에 설명된 데이터 세트에 맞는 선을 찾는 경우, RANSAC 알고리즘은 일반적으로 각 반복에서 두 점을 선택하고 계산한다.maybe_model점 사이의 선과 두 점이 구별되는 것이 중요하다.

추가 신뢰를 얻기 위해 표준 편차 또는 표준 편차 배수를 k에 추가할 수 있다.k의 표준 편차는 다음과 같이 정의된다.

장단점

RANSAC의 장점은 모델 매개변수의 강력한 추정[3] 수행할 수 있다는 것이다. 즉, 데이터 집합에 상당한 수의 특이치가 있더라도 높은 정확도로 매개변수를 추정할 수 있다.RANSAC의 단점은 이러한 파라미터를 계산하는 데 걸리는 시간에 상한이 없다는 것이다(소진 제외).계산된 반복 횟수가 제한될 때 얻은 솔루션은 최적 상태가 아닐 수 있으며 데이터에 적합한 솔루션도 아닐 수 있다.이러한 방식으로 RANSAC는 절충을 제공한다. 더 많은 수의 반복을 계산함으로써 합리적인 모델이 생산될 확률을 증가시킨다.더욱이 RANSAC은 오염도가 적당히 높은 세트에 대해서도 최적의 세트를 항상 찾을 수 있는 것은 아니며, 일반적으로 상각자 수가 50% 미만일 때 성능이 떨어진다.최적 RANSAC는 이 두 가지 문제를 모두 처리하기 위해 제안되었으며, 5% 미만의 초과 비율에서도 심하게 오염된 세트에 대한 최적 세트를 찾을 수 있다.RANSAC의 또 다른 단점은 문제별 임계값을 설정해야 한다는 것이다.

RANSAC는 특정 데이터 세트에 대해 하나의 모델만 추정할 수 있다.두 개 이상의 모델 인스턴스가 존재하는 경우, RANSAC는 두 가지 모델 중 하나를 찾지 못할 수 있다.Hough 변환은 둘 이상의 모델 인스턴스가 있을 때 유용할 수 있는 하나의 대안적인 강력한 추정 기법이다.다중 모델 피팅을 위한 또 다른 접근방식은 RANSAC에서와 같이 데이터 포인트의 모델 샘플링과 상어의 반복적 재추정을 결합한 PERE로 알려져 있으며,[5] 전체 솔루션의 품질을 설명하는 글로벌 에너지 함수와 함께 최적화 문제로 공식화되는 다중 모델 피팅을 결합한 것이다.

적용들

RANSAC 알고리즘은 통신 문제를 동시에 해결하고 스테레오 카메라 쌍과 관련된 기본 매트릭스를 추정하기 위해 컴퓨터 비전에 종종 사용된다. 또한 다음을 참조하십시오.모션, 스케일 인바리어스 피쳐 변환, 이미지 스티칭, 견고한 모션 분할로부터의 구조.

개발 및 개선

1981년 이래로 RANSAC은 컴퓨터 비전과 이미지 처리 커뮤니티의 기본 도구가 되었다.2006년, 알고리즘 25주년을 맞아, 컴퓨터 비전 및 패턴 인식 국제회의(CVPR)에서 워크샵을 조직하여 원래 알고리즘에 대한 가장 최근의 기여와 변형을 요약하였으며, 주로 알고리즘의 속도, 추정 솔루션의 강건성 및 정확성을 향상시키기 위한 것을 의미하였다.그리고 사용자 정의 상수의 종속성을 감소시킨다.

RANSAC는 특정 매개변수 집합으로 인스턴스화된 모델에 적합한 데이터 점을 정의하는 올바른 소음 임계값 선택에 민감할 수 있다.그러한 문턱이 너무 크면 모든 가설은 동등하게 (좋은) 순위를 매기는 경향이 있다.반면에 소음 임계값이 너무 작을 경우 추정된 모수가 불안정해지는 경향이 있다(즉, 상각선 집합에 기준선을 추가하거나 제거하면 모수의 추정치가 변동할 수 있다).이러한 바람직하지 않은 효과를 부분적으로 보상하기 위해, Torr 외 연구진은 MSAC(M-estimator SAmple and Consensus)와 MLESAC(최대우도 추정 SAmple and Consensus)라는 RANSAC의 두 가지 수정을 제안했다.[6]주요 아이디어는 컨센서스 집합의 품질(즉, 모델에 적합한 데이터와 특정 매개변수 집합)을 평가하는 것이다(Fischler와 Bolles의 원래 공식에서 등급은 그러한 집합의 카디널리티였다).입력 데이터 집합과 관련된 사전 확률을 고려한 MLESAC로의 확장은 Tordoff에 의해 제안된다.[7]결과 알고리즘은 Guided-MLESAC로 불린다.Chum은 유사한 선과 함께 입력 데이터에 대한 일부 사전 정보가 알려진 경우, 즉 기준점이 이상인지 이상인지 여부를 샘플링 절차를 안내할 것을 제안했다.제안된 접근방식은 PROSAC, PROGulative Sample Consensus라고 불린다.[8]

Chum 외 연구진은 또한 RANSAC라는 랜덤화 버전을 제안하여 좋은 컨센서스 집합을 식별하기 위한 계산 부담을 줄였다.기본 아이디어는 전체 데이터 집합 대신 축소된 점 집합만을 사용하여 현재 인스턴스화된 모델의 선도를 초기에 평가하는 것이다.건전한 전략은 전체 데이터 집합의 적합성을 평가하는 경우 또는 모델을 쉽게 폐기할 수 있는 경우를 높은 신뢰도로 알려준다.상각자 비율이 큰 경우에는 이 접근방식의 영향이 더 목적적합하다고 보는 것이 타당하다.Chum 등이 제안한 전략의 유형을 선점제도라고 한다.NISTer는 장면의 구조와 카메라의 움직임을 실시간으로 강력하게 추정할 수 있는 Preference RANSAC라는[10] 패러다임을 제안했다.접근법의 핵심 개념은 일정한 수의 가설을 생성하여 비교가 어떤 절대 품질 지표에 대한 비교가 아니라 생성된 가설에 대한 품질에 관한 비교가 이루어지도록 하는 것이다.

다른 연구자들은 소음 규모를 알 수 없거나 복수의 모델 인스턴스가 존재하는 어려운 상황에 대처하기 위해 노력했다.첫 번째 문제는 왕과 서더에 의해 해결되었다.[11]Tiddo 등.은 점들에 맞는 랜덤 모델 집합의 특성 함수로 각 기준점을 나타낸다.그런 다음 여러 모델이 동일한 모델을 지원하는 점을 그룹화하는 군집으로 표시된다.J-linkage라고 불리는 클러스터링 알고리즘은 모델 수의 사전 사양을 필요로 하지 않으며, 수동 파라미터 튜닝도 필요하지 않다.[12]

RANSAC는 또한 특이치에 의해 입력 측정이 손상되고 측정 오차의 가우스 분포에 의존하는 Kalman 필터 접근은 실패할 운명인 재귀 상태 추정 애플리케이션에 적합하도록 조정되었다.그러한 접근방식은 KALMANSAC이라고 불린다.[13]

관련 방법

참고 항목

메모들

  1. ^ 데이터 피팅 및 불확실성, T. Stradz, Springer Vieweg (제2판, 2016)
  2. ^ 캔츨러, H. "랜덤 샘플 컨센서스 (랜잭)"인식, 행동 및 행동 연구소, 정보학부, 에든버러 대학교 (1981년)http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.106.3035&rep=rep1&type=pdf
  3. ^ 강력한 통계 자료야, 피터.J. Huber, Wiley, 1981년 (paperback, 2004), 1페이지.
  4. ^ 안데르스 헤스트, 요한 니쇼, 안드레아 마르체티(2013년)."Optimal RANSAC – 최적 세트를 찾기 위한 반복 가능한 알고리즘을 지향한다."WSCG 21(1) 저널: 21–30.
  5. ^ 호삼 이사크, 유리 보이코프(2012년)."에너지 기반 기하학적 다중 모델 피팅".컴퓨터 비전 국제 저널 97(2: 1): 23–147. doi:10.1007/s11263-011-0474-7.
  6. ^ P.H.S.토르와 A.Zisserman, MLESAC: 이미지 기하학, 컴퓨터 비전 및 이미지 이해 78(2000), 번호 1, 138–156의 추정에 적용되는 새로운 강력한 추정기.
  7. ^ B. J. Tordoff와 D.W. Murray, Guided-MLESAC: 일치하는 이전 버전, IEEE Transactions on Pattern Analysis and Machine Intelligence 27(2005), 번호 10, 1523–1535를 사용하여 더 빠른 이미지 변환 추정.
  8. ^ POSAC와의 매칭 점진적인 샘플 컨센서스, 컴퓨터 비전 및 패턴 인식에 관한 회의(San Diego), 2005년 6월 1일, 페이지 220–226
  9. ^ O. Chum과 J. Matas, Td,d test, 제13회 British Machine Vision Conference, 2002년 9월.http://www.bmva.org/bmvc/2002/papers/50/
  10. ^ D. NISTer, 라이브 구조모션 추정을 위한 선제적 RANSAC, IEEE 컴퓨터 비전 국제회의(Nice, 프랑스), 2003년 10월, 페이지 199–206.
  11. ^ H. 왕과 D.Suter, 컴퓨터 비전에 대한 강력한 적응형 척도 모수 모델 추정, 패턴 분석 및 기계 인텔리전스에 대한 IEEE 트랜잭션 26(2004), 번호 11, 1459–1474
  12. ^ R. Tiddo와 A.Fusiello, J-linkage를 사용한 견고한 다중 구조 추정, 2008년 10월 유럽 컴퓨터 비전 회의(프랑스 마르세유), 페이지 537–547.
  13. ^ A. 베달디, H. 진, P. 파바로, S.Soatto, KALMANSAC: 컨센서스에 의한 강력한 필터링, ICCV(International Conference on Computer Vision, ICCV), Vol. 1, 2005, 페이지 633–640
  14. ^ Brahmachari, Aveek S.; Sarkar, Sudeep (March 2013). "Hop-Diffusion Monte Carlo for Epipolar Geometry Estimation between Very Wide-Baseline Images". IEEE Transactions on Pattern Analysis and Machine Intelligence. 35 (3): 755–762. doi:10.1109/TPAMI.2012.227.

참조