RANSAC 알고리즘 및 오류 제거 응용

다음으로 이동:http://www.jellon.cn/index.php/archives/291
1.RANSAC 알고리즘 소개      모델 매개 변수 평가 방법,예 를 들 어 전형 적 인 최소 이승 법 은 특정한 목표 방정식 에 따라 모델 매개 변 수 를 평가 하고 최적화 시 켜 모든 주어진 데이터 세트 에 최대한 적응 하도록 할 수 있다.이 방법 들 은 이상 데 이 터 를 검사 하고 제거 하 는 방법 을 포함 하지 않 습 니 다.그들 은 모두 부 드 러 운 가설 을 바탕 으로 합 니 다.주어진 데이터 세트 의 크기 를 무시 하고 정확 한 데이터 값 으로 이상 데이터 의 영향 을 제거 할 수 있 습 니 다.그러나 많은 실제 상황 에서 부 드 러 운 가설 이 성립 되 지 않 고 데이터 에 보상 을 받 지 못 하 는 심각 한 오류 데 이 터 를 포함 할 수 있 습 니 다.이 럴 때 이런 모델 매개 변 수 는 평가 방법 을 사용 할 수 없습니다.      예 를 들 어 다음 과 같은 상황:7 개의 점(그림 1 참조)을 정 하고 가장 적합 한 직선 구간 을 어떻게 작성 하여 모든 정확 한 점 에서 직선 까지 의 거 리 를 0.8 을 초과 하지 않도록 합 니까?이 때 는 최소 이승 법 등 방법 으로 적합 할 수 없 음 이 분명 하 다.
그림 1
      RANSAC 는 RANdom SAmple Consensus 의 줄 임 말로 이상 데 이 터 를 포함 한 샘플 데이터 세트 에 따라 데 이 터 를 계산 하 는 수학 모형 매개 변 수 를 계산 하여 효과 적 인 샘플 데 이 터 를 얻 는 알고리즘 입 니 다.그것 은 1981 년 에 Fischler 와 Bolles 가 가장 먼저 제기 했다[1].      RANSAC 알고리즘 의 기본 가설 은 샘플 에 정확 한 데이터(inliers,모델 에 묘 사 될 수 있 는 데이터)가 포함 되 어 있 고 이상 데이터(Outliers,정상 범위 에서 멀 어 수학 모델 에 적응 하지 못 하 는 데이터)도 포함 되 어 있다 는 것 이다.즉,데이터 에 소음 이 집중 되 어 있다 는 것 이다.이러한 이상 데 이 터 는 잘못된 측정,잘못된 가설,잘못된 계산 등 으로 인해 발생 할 수 있다.또한 RANSAC 도 정확 한 데 이 터 를 정 하고 이 데이터 에 부합 되 는 모델 매개 변 수 를 계산 할 수 있 는 방법 이 존재 한다 고 가정 했다.      RANSAC 의 기본 사상 묘 사 는 다음 과 같다.      ① 최소 샘플링 집합 이 n 인 모델(n 은 모델 매개 변 수 를 초기 화 하 는 데 필요 한 최소 샘플 수)과 하나의 샘플 집합 P,집합 P 의 샘플 수\#(P)>n 을 고려 하여 P 에서 n 개의 샘플 을 포함 한 P 의 부분 집합 S 초기 화 모델 M 을 무 작위 로 추출 합 니 다.      ② 여 집 SC=P/S 에서 모델 M 과 의 오 차 는 특정한 한도 값 t 를 설정 한 견본 집 과 S 구성 S*보다 작다.S*는 내 점 집합 이 라 고 생각 하고 S 의 일치 집합(Consensus Set)을 구성한다.      ③ 만약 에\#(S*)≥N 이 정확 한 모델 매개 변 수 를 얻 었 다 고 생각 하고 집합 S*(내 점 inliers)를 이용 하여 최소 2 곱 하기 등 방법 으로 새로운 모델 M*를 다시 계산한다.새로운 S 를 무 작위 로 추출 하여 상기 과정 을 반복 합 니 다.      ④ 일정한 표본 추출 횟수 를 완성 한 후에 일치 집합 을 찾기 위해 알고리즘 이 실 패 했 습 니 다.그렇지 않 으 면 표본 추출 후 얻 은 최대 일치 집합 을 선택 하여 내외 점 을 판단 하고 알고리즘 이 끝 납 니 다.      위 에서 알 수 있 듯 이 두 개의 가능 한 알고리즘 최적화 전략 이 존재 한다.① 부분 집합 S 를 선택 할 때 이미 알 고 있 는 견본 특성 등에 따라 특정한 선택 방안 이나 제약 이 있 는 무 작위 선택 으로 원래 의 완전 무 작위 선택 을 대체 할 수 있다.② 일치 집합 S*를 통 해 모델 M*를 계산 한 후 P 에 있 는 모델 M*과 의 오차 가 t 보다 적은 샘플 을 S*에 추가 한 후 M*를 다시 계산 할 수 있다.      RANSAC 알고리즘 은 3 개의 입력 매개 변 수 를 포함 합 니 다.① 샘플 이 모델 의 오차 용인 도 t 를 만족 시 키 는 지 판단 합 니 다.t.내 점 소음 의 평균 분산 에 대한 가설 로 볼 수 있 고 서로 다른 입력 데이터 에 대해 인공 적 으로 관여 하 는 방식 으로 적당 한 문턱 을 설정 해 야 하 며 이 매개 변 수 는 RANSAC 성능 에 큰 영향 을 미친다.② 표본 집 S 를 무 작위 로 추출 하 는 횟수.이 매개 변 수 는 SC 에서 샘플 이 모델 매개 변수 에 참여 하 는 검사 횟수 에 직접적인 영향 을 주 고 알고리즘 의 효율 에 영향 을 미친다.왜냐하면 대부분 무 작위 표본 추출 은 외부 점 의 영향 을 받 기 때문이다.③ 표징 이 정확 한 모델 을 얻 었 을 때 S*의 크기 N 과 일치 합 니 다.표징 데이터 세트 P 의 정확 한 모델 을 확보 하기 위해 서 는 일치 집합 이 충분 해 야 합 니 다.또한 충분 한 일치 견본 은 재 평가 모델 의 매개 변 수 를 더욱 정확 하 게 한다.      RANSAC 알고리즘 은 컴퓨터 시각 에 자주 사용 된다.예 를 들 어 입체 시각 분야 에서 한 쌍 의 카메라 의 일치 점 문제 와 기본 행렬 의 계산 을 동시에 해결한다.
2.RANSAC 가 잘못된 조합 을 제거 하 는 데 사용 되 는 응용      특징 점 배합 에서 모델 은 한 평면 상의 특징 점 에서 다른 평면 상의 특징 점 까지 의 사영 관계 이 고 사영 행렬 H 로 반응 한다.H 는 8 개의 자유 도 를 포함 하 는 3 이다.×3.행렬 은 최소 두 평면 중의 4 쌍 의 일치 점 으로 계산 할 수 있 지만 같은 평면 상의 3 개 점 은 반드시 공 면 이 아니 어야 한다.      그림 2,그림 3 은 RANSAC 의 잘못된 조합 제거 실험 결과 로 두 그림 의 일치 점 은 인공 적 으로 Harris 각 점 포 지 셔 닝 을 선택 하여 선택 한 것 이다.일치 점 은 선택 이 끝 난 후에 인공 수정 점 이 집 중 된 데 이 터 를 선택 하여 외 점 을 생 성 한다.두 그림 에서 녹색 점 은 RANSAC 가 정확하게 일치 하 는 점 이 맞다 고 생각 하고 빨간색 점 은 잘못된 일치 점 이 맞다.
그림 2 그림 3
참고 문헌:[1]Fischler,M.A.and Bolles,R.C.무 작위 표본 보 정:이미지 분석 및 자동 지도 작성 을 위 한 어 플 리 케 이 션 피 팅 을 위 한 패 러 다 임.ACM 의 커 뮤 니 케 이 션,24(6):381–395,1981.[2]Richard Hartley and Andrew Zisserman.Multiple View Geometry in Computer Vision(2nd ed).Cambridge University Press.[3]정 현,주 염,임 홍 도,반 항 휘.SIFT 특징 을 바탕 으로 원 격 탐지 영상 자동 조준 과 조합,원 격 탐지 기술 과 응용,23(6):721-728,2008 년 12 월
 
RANSAC 오류 제거 matlab 코드(matchransac.m）：

function correctPoints = match_ransac(P1,P2, it, N, t)
% MATCH_RANSAC:RANSAC outliner detector for matched point-pairs
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Input:
%       P1        - coordinates of points in the 1st image, [pointnum x 2]
%       P2        - coordinates of points in the 2nd image, [pointnum x 2]
%       it        - iterations (the number of subset to try)
%       N         - number of points in a consensus set to determine a correct model has been found
%       t         - error tolerance to determine whether a point is compatible for the model
% 
% Output:
%       correctPoints - indexes of point-pairs corrected matched determined by RANSAC
% 
% Author: 
% Jiaolong Yang
% Beijing Laboratory of Intelligent Information Technology,
% School of Computer Science,
% Beijing Institute of Technology
% [email protected]
% 
% Reference:
% Fishler M A, Bolles R C. Random sample concensus:A paradigm for model fitting
% with applications to image analysis and automated cartography[J]. Communications
% of ACM, 1981, 24(6):381—395.
% 
% $Revision: 1.0 $  $Date: 2010.03.17 21:44:20 $ Original version
% $Revision: 1.1 $  $Date: 2010.03.19 16:04:50
% $Revision: 2.0 $  $Date: 2010.03.23 13:17:39
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
    switch nargin
        case 2
            it = size(P1,1);
            N = fix(0.4*size(P1,1));
            t = 3;
        case 3
            N = fix(0.4*size(P1,1));
            t = 3;
        case 4
            t = 3;
    end
 
    correctPoints = [];
    pointNum = size(P1, 1);
    history = [];
 
    for i = 1:it
        %initialize consensus set with 4 points randomly selected 
        S = randperm(pointNum);
        S = S(1:4);
        %check whether every 3 points are noncollinear
        if check_collineation(P1(S, :))
            it = it+1;
            continue;
        end
 
        %check whether the selected group haven't been used before
        historyNum = size(history,1);
        exist = 0;
        for j = 1:historyNum
            equal = 1;
            for k = 1:4
                if history(j,k) ~= S(k)
                    equal = 0;
                    break;
                end
            end
            if equal
                exist = 1;
                break;
            end
        end
        if exist
            %reject used group
            it = it+1;
            continue;
        else
            history(end+1, :) = S;
        end
 
        %compute projective transformation matrix
        H = projectivematrix(P2(S,:)', P1(S,:)');
        %get full consensus set
        S =  get_consensus_set(P1, P2, S, H, t); 
        %check if the model(namely the matrix) is correct or better than that we've found
        if size(S,2) > N 
            N = size(S,2);
            correctPoints = S;
        end
    end
 
    %update projective transformation matrix
    H = projectivematrix(P2(correctPoints,:)',P1(correctPoints,:)');
    %get all points compatible with the best model
    correctPoints =  get_consensus_set(P1, P2, correctPoints, H, t);
end
 
function S = get_consensus_set(P1, P2, S, H, t)
 
    dataNum = size(P1,1);
    %traverse all the points
    for i = 1:dataNum
        if size(find(S == i), 2) ~= 0
            continue;
        end
 
        %project p1 to p1_h using the given transformation matrix
        p1 = P1(i,:);
        tmp = H*[p1,1]';
        p1_h = tmp(1:2)' / tmp(3);
 
        p2 = P2(i,:);
 
        %compute the error(euclidian distance betwween p1_h and p2)
        dis = sqrt((p1_h(1)-p2(1))*(p1_h(1)-p2(1)) + (p1_h(2)-p2(2))*(p1_h(2)-p2(2)));
 
        %check error tolerance
        if dis < t
            S(end+1) = i;
        end
    end
end
 
function re = check_collineation(P)
 
    num = size(P,1);
    if num > 2
        for i = 1:num-2
            for j = i+1:num-1
                for k =j+1:num
                    a = [P(i,:)-P(j,:), 0];
                    b = [P(i,:)-P(k,:), 0];
                    %determine collineation of 3 points by "corss(p1p2,p1p3)==0"
                    if cross(a,b) == 0
                        re = 1;
                        return;
                    end
                end
            end
        end
    end
 
    re = 0;
end