무작위 표본 합의: 컴퓨터 비전의 강력한 추정

By Fouad Sabry

무작위 표본 합의란 무엇입니까

RANSAC라고도 알려진 무작위 표본 합의는 컬렉션을 기반으로 수학적 모델의 매개변수를 추정하는 데 사용되는 반복 방법입니다. 이상값을 포함하는 관측 데이터. 이 방법은 이상값이 추정값에 영향을 주지 않는 상황에서 사용됩니다. 결론적으로 이상치를 탐지하는 도구로 보는 것도 가능하다는 것이다. 특정 확률로만 적합한 결과를 생성할 수 있는 알고리즘은 비결정적이라고 간주되며, 이 가능성은 해당 방법을 통해 허용되는 반복 횟수가 증가할수록 증가합니다. 1981년 SRI International에서 근무하던 Fischler와 Bolles가 처음으로 알고리즘을 발표했습니다. 이미지에 투영되는 공간의 지점을 찾은 다음 해당 지점을 위치가 알려진 랜드마크 집합으로 변환하는 것이 목표인 위치 결정 문제(LDP)를 해결하기 위해 RANSAC을 활용했습니다.

혜택

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 무작위 표본 합의

2장: 추정량

3장: 최소 제곱

4장: 이상치

5장: 교차 검증(통계)

6장: 오류 및 잔차

7장: 혼합 모델

8장: 강력한 통계

9장: 이미지 스티칭

10장: 리샘플링(통계)

(II) 무작위 표본 합의에 관한 대중의 주요 질문에 답합니다.

(III) 사용에 대한 실제 사례 다양한 분야의 무작위 표본 합의.

이 책은 누구를 위한 책인가요?

전문가, 학부생 및 대학원생, 열성팬, 취미생활자, 그리고 가고 싶은 사람들 모든 종류의 무작위 표본 합의에 대한 기본 지식이나 정보를 넘어선 것입니다.

 

 

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: Apr 30, 2024

Book preview

1장: 무작위 표본 합의

이상치를 포함하는 관측된 데이터 세트에서 수학적 모델의 매개변수를 추정하기 위해 RANSAC(Random Sample Consensus)로 알려진 반복 프로세스를 사용할 수 있습니다. 따라서 이상값을 식별하는 기술로도 볼 수 있습니다. 이 알고리즘은 주어진 확률로 적절한 결과만 생성하기 때문에 비결정적이며, 이는 허용 가능한 반복 횟수에 따라 증가합니다. 1981년 SRI International의 Fischler와 Bolles는 이 알고리즘을 처음으로 대중에게 공개했습니다. RANSAC을 통해 그들은 고정된 좌표를 가진 랜드마크 모음으로 이미지에 매핑되는 공간의 지점을 찾는 것과 관련된 위치 결정 문제(LDP)를 해결할 수 있었습니다.

RANSAC는 무작위 서브샘플링을 여러 번 사용하는 방법입니다. 이상치는 상당한 잡음이 있더라도 일부 모델 매개변수 집합으로 분포를 설명할 수 있는 데이터인 반면, 이상치는 데이터에 대한 기본 가정에 따라 모델과 일치하지 않는 데이터입니다. 특이치 원인의 예로는 과도한 노이즈 값, 잘못된 측정, 잘못 해석된 데이터 등이 있습니다. 또한 RANSAC는 (종종 제한된) 인라이어 집합이 주어졌을 때 이 데이터를 이상적으로 설명하거나 적합하게 설명하는 모델의 매개변수를 추정할 수 있는 프로세스의 존재를 의미합니다.

2차원 선 맞춤은 이 원리를 간단하게 보여줍니다. 이 컬렉션에 인라이어(선에 대략적으로 적합할 수 있는 점)와 이상치(이 선에 맞출 수 없는 점)가 모두 포함된 경우 선을 피팅하는 최소 제곱법으로 인해 데이터에 적합하지 않은 선이 생성될 수 있습니다. 모델은 극단적인 데이터 포인트를 포함한 모든 데이터 포인트에 최적으로 일치합니다. 그러나 RANSAC는 이상값을 포함하지 않고 대신 계산에 내부값만 사용하는 선형 모델을 찾으려고 합니다. 이를 위해 데이터의 많은 무작위 표본을 사용하여 선형 모델을 피팅한 다음 데이터의 일부에 가장 큰 피팅을 제공하는 모델이 반환됩니다. 완전히 인라이어로만 구성된 랜덤 부분 집합은 인라이어와 아웃라이어의 무작위 혼합보다 인라이어가 선형적으로 연결될 가능성이 더 높기 때문에 가장 적합한 모형 적합도를 갖습니다. 알고리즘의 성공 가능성은 데이터의 인라이어 비율과 수많은 알고리즘 매개변수의 선택에 따라 달라지며, 실제로 인라잇의 하위 집합이 무작위로 선택된다는 보장은 없습니다.

선형 회귀 분석이 필요한 여러 이상치가 있는 데이터 세트입니다.

RANSAC 회귀; 특이치는 평균에 영향을 미치지 않습니다.

RANSAC 알고리즘은 관측 표본에서 모델 매개변수를 추정하기 위한 데이터 기반 학습 방법입니다. RANSAC는 투표 방법을 사용하여 데이터 요소에 인라이어와 아웃라이어가 모두 포함된 지정된 데이터 세트에 가장 적합한 결과를 얻습니다. 데이터 세트의 데이터 포인트는 하나 이상의 모델에 대한 투표로 사용됩니다. 이 투표 기법은 두 가지 가정 하에 구현됩니다: (a) 괜찮은 모델에 동의할 수 있는 충분한 특징이 있고, (b) 잡음이 있는 특징은 단일 모델(소수의 이상치)에 대해 일관되게 투표하지 않습니다(누락된 데이터가 거의 없음). RANSAC 알고리즘은 대부분 두 단계로 구성되며, 두 단계 모두 반복적인 방식으로 수행됩니다.

입력 데이터 집합의 무작위 하위 집합이 첫 번째 단계에서 샘플로 사용되도록 선택됩니다. 이 하위 표본의 요소는 모형 모수를 사용하여 적합 모형을 계산하는 데 사용됩니다. 모델 매개변수는 하위 샘플의 카디널리티 데이터만 사용하여 계산할 수 있습니다.

프로세스의 두 번째 단계에는 전체 데이터 세트의 어느 부분이 추정된 모델 매개변수로 인스턴스화된 모델과 일치하는지 확인하는 작업이 포함됩니다. 정보가 미리 결정된 오차 범위 내에서 모델을 준수하지 않으면 이상치로 분류됩니다. (이 범위를 벗어난 데이터 포인트는 특이치로 간주됩니다.)

모델을 보정하는 데 사용되는 이상치 그룹을 합의 집합이라고 합니다. 충분한 수의 이상값으로 합의 집합이 형성될 때까지 RANSAC 알고리즘은 앞의 두 단계를 반복적으로 반복합니다.

관측된 데이터 값, 이러한 관측치를 피팅하는 모델 및 이상값을 나타내는 신뢰도 매개변수는 RANSAC 알고리즘에 대한 입력입니다. RANSAC 알고리즘은 아래에 자세히 설명된 다음 단계를 반복적으로 수행하여 목표를 달성합니다.

원본 데이터의 표본을 무작위로 선택합니다. 이 그룹을 가상의 이상값으로 생각할 수 있습니다.

잠재적 이상치 세트는 모델링 프로시저에 대한 입력으로 사용됩니다.

적합 모형에 대한 모든 데이터의 검증은 다음과 같습니다. 합의 집합은 추정된 모델에 대한 손실 함수(즉, 모델에 대한 인라이어 집합)를 최소화하는 원래 데이터 포인트의 하위 집합입니다.

관측치의 비율이 충분히 높으면 합의 집합에 적합하면 추정된 모형의 품질이 적절한 것으로 간주될 수 있습니다.

전체 합의 집합의 데이터로 모델을 재추정하면 더 나은 결과를 얻을 수 있습니다. 시간이 지남에 따라 모델 피팅을 선명하게 하는 것은 모델이 합의 세트에 얼마나 잘 맞는지를 측정하는 피팅 품질의 도움으로 수행됩니다(예: 다음 반복에서 이 측정값을 피팅 품질 기준으로 설정).

이 프로세스를 반복할 때마다 합의 집합의 일부인 점이 너무 적기 때문에 모델이 거부되거나 이전 반복보다 합의 집합 크기가 더 큰 수정된 모델이 거부됩니다. 이 프로세스는 충분히 양호한 모델 매개변수 세트를 찾을 때까지 반복됩니다.

RANSAC의 이상값 및 이상값. 이 점별 선형 피팅의 예에는 7개의 이상값이 포함되어 있습니다(일부 기준에서 모델에 잘 피팅된 데이터 포인트). 대부분의 데이터 점이 선형 선 주위에 모여 있기 때문에 피팅이 불량합니다(즉, 더 많은 인라이어).

다음은 기본 RANSAC 알고리즘을 구현하는 몇 가지 의사 코드입니다.

주어진:

data – 관측값 집합입니다.

model – 관측된 데이터 포인트를 설명하는 모델입니다.

n – 모델 파라미터를 추정하는 데 필요한 최소 데이터 포인트 수입니다.

k – 알고리즘에서 허용되는 최대 반복 횟수입니다.

t – 모델에 잘 맞는 데이터 포인트를 결정하기 위한 임계값입니다(inlier).

d – 모델이 데이터에 잘 맞는다고 주장하는 데 필요한 가까운 데이터 점(인라이어)의 수입니다.

돌아오다:

bestFit – 데이터에 가장 적합할 수 있는 모델 파라미터입니다(또는 좋은 모델을 찾을 수 없는 경우 null).

반복 = 0

bestFit = 널

bestErr = something really large // 이 매개변수는 반복이 진행됨에 따라 모델 매개변수를 최상의 데이터 피팅으로 선명하게 하는 데 사용됩니다.

반복이 k를 수행하는 동안 <

maybeInliers : = 데이터에서 무작위로 선택된 n 값

maybeModel := maybeInliers에 맞는 모델 매개 변수

confirmedInliers : = 빈 집합

데이터의 모든 포인트에 대해

point가 t보다 작은 오차로 maybeModel에 맞으면

confirmedInliers에 점 추가

다음과 같은 경우 종료

에 대한 끝

confirmedInliers의 요소 개수가 d> 이면

이것은 우리가 좋은 모델을 찾았을 수 있음을 의미합니다.

이제 얼마나 좋은지 테스트하십시오.

betterModel := confirmedInliers의 모든 점에 맞는 모델 매개 변수

thisErr := betterModel이 이러한 점에 얼마나 잘 맞는지에 대한 측정값입니다.

thisErr < bestErr 이면

bestFit : = 더 나은 모델

bestErr := thisErr

다음과 같은 경우 종료

다음과 같은 경우 종료

반복 증가

다음 시간 동안 종료

bestFit 반환

Python에서 미러링된 의사 코드입니다. 또한 이 최소제곱 기반 LinearRegressor 정의, RANSAC 응용 프로그램 및 결과 그래픽 표현은 2D 회귀 문제를 해결합니다.

복사에서 가져오기 복사본

가져오기 numpy를 np로

numpy.random 가져 오기 default_rng

rng = default_rng()

클래스 RANSAC :

def __init__(self, n=10, k=100, t=0.05, d=10, model=없음, 손실=없음, 메트릭=없음):

self입니다.n = n # 'n': 모수를 추정할 최소 데이터 포인트 수

self입니다.k = k # 'k': 허용되는 최대 반복 횟수

self입니다.t = t # 't': 점이 잘 맞는지 확인하기 위한 임계값

self입니다.d = d # 'd': 모델이 잘 맞는다고 주장하는 데 필요한 가까운 데이터 포인트의 수

self입니다.model = model # 'model': 'fit' 및 'predict'를 구현하는 클래스

self입니다.loss = loss # 'loss': 벡터를 반환하는 'y_true'와 'y_pred'의 함수

self입니다.metric = metric # 'metric': 'y_true'와 'y_pred'의 함수이며 float를 반환합니다.

self입니다.best_fit = 없음

self입니다.best_error = np입니다.인프

def 적합 (self, X, y) :

for _ in range(self.k)를 사용합니다.

ids = rng입니다.순열(X.모양0])

maybe_inliers = ids[: self.n

maybe_model = copy(self.모델).fit(Xmaybe_inliers], ymaybe_inliers])를 사용합니다.

임계값 = (

self입니다.loss(yids][self.n :], maybe_model.predict(Xids][self.n :]))

< 자아.티

)

inlier_ids = idsself입니다.n :][np.flatnonzero(thresholded)입니다.flatten()]

inlier_ids 경우.크기 > 각자.디:

inlier_points = np입니다.hstack([maybe_inliers, inlier_ids])

better_model = 복사(self.모델).fit(Xinlier_points], yinlier_points])를 사용합니다.

this_error = self입니다.메트릭(

yinlier_points], better_model.예측(Xinlier_points])

)

this_error < 자신이라면.best_error:

self입니다.best_error = this_error

self입니다.best_fit = maybe_model

자기 자신을 반환합니다.