Robust estimation 시리즈 (0) - Outlier란?
Outlier란?
Outlier는 통계 단어로써 ‘이상치‘, 즉 우리가 기대하지 않았떤 잘못된 데이터를 뜻한다. ‘이상치’는 ‘노이즈’와 다른 의미를 가진다. 우리는 보통 어떤 특정 분포의 데이터를 기대하고 알고리즘을 선택하는데, 노이즈는 우리가 기대한 분포 안에서 나타나는 데이터들간의 변화이고, 이상치는 이 분포를 아득히 뛰어넘어 완전히 다른 분포를 가진다. 따라서 Outlier를 제거한다는 것은 우리가 기대했던 올바른 데이터들만으로 계산을 한다는 것이다.
반대로, 이 outlier가 아닌 올바른 데이터는 inlier라고 한다.
많은 컴퓨터 알고리즘에서 황금룰처럼 적용되는 Good data in → Good data out은 비전 알고리즘에도 똑같이 적용된다. 하지만 다른 분야에 비해 유독 컴퓨터 비전에서는 outlier 제거가 더 중요한 것 같다. 왜냐하면 우리가 자주 사용하는 몇개의 컴퓨터 비전 알고리즘들은 outlier가 없는 상황에서만 잘 작동하는 closed-solution인 경우가 많기 때문이다.
Fundamental matrix를 구할때나 homography matrix를 구할 때를 생각해보자. 이 매트릭스 계산을 하기 위해서는 몇개의 image feature pair가 필요하다. 이 계산을 하기 위해 우리가 쓸 수 있는 image feature pair가 몇백개씩 있어도, 우리는 이 중 아무 feature pair나 막 골라서 사용할 수 없다. 그 이유는 fundamental / homography matrix의 계산식에 혹여나 잘못 매칭된 feature pair가 사용될 경우 처참할 정도로 잘못된 결과값이 나오기 때문이다.
그러면 이번에는 우리가 어떠한 방식으로 outlier를 전부 제거해서 좋은 데이터만 남았다고 해보자. Outlier가 없으니 이제 좋은 결과가 나올 것이다. 하지만 컴퓨터 비전 데이터 특성 상 모든 데이터에 noise가 조금씩 끼어있다. 어떤 데이터는 다른 데이터보다 noise가 더 끼어있을 수 있다. 이 때문에 좋은 데이터들 사이에서도 어떤 조합으로 계산하냐에 따라서 정확도가 달라지기도 하는데, 우리는 또 최적의 조합을 찾기 위해 이번에는 ‘가장 적은 노이즈를 가지는 데이터 조합’을 찾는 노력을 들인다.
정확한 결과를 얻기 위해서는 outlier와 noise가 섞인 데이터에서 최적의 데이터를 솎아내야한다. Input 데이터의 양은 유한하기 때문에, 시간만 있다면 모든 경우의 수를 찾아보아 결국에는 최적의 값을 찾아낼 수 있다. 하지만 Real-time 컴퓨터 비전에서는 주어진 시간이 그렇게 많지 않다. 그러면 어떤 방법을 사용해야 빠르게 좋은 데이터만을 솎아낼 수 있을까?
수많은 연구를 통해 발견한 것은, outlier와 noise가 섞인 데이터로부터 곧바로 최적의 데이터를 솎아내는 것보다, outlier의 특성과 noise의 특성을 찾아내 부적절한 데이터를 우선 제거하고난 후 남아있는 데이터로부터 정확한 값을 추론하는 것이 훨씬 빠르다는 것이다. 그렇기 때문에 컴퓨터 비전에서는 수많은 outlier 제거 및 noise 제거 단계를 거친다. Gaussian filter를 사용해서 픽셀 노이즈를 줄여주는 것도, feature matching에 여러가지 threshold를 주는 것도, RANSAC을 통해 올바른 데이터를 골라내는 것도, weighted least squares optimization을 통해서 특정 데이터에 가중치를 주는 것도 모두 outlier 제거 및 noise 제거로 볼 수 있다. 이러한 계산들이 종종 Visual-SLAM에서 전체 계산량의 70~80%를 이루기도 하는데, 이들이 사용되는 이유는 오로지 ‘빠르고 정확한 계산을 위한 outlier 및 noise 제거’ 라고 볼 수 있다.
반대로 생각하면, 더 효율적인 방법으로 outlier와 noise를 제거할 수 있으면 더욱 visual-SLAM의 본질에 다가간다고 생각한다. 그렇기 때문에 이번 포스팅 시리즈에서는 여러가지 outlier 제거 방법에 대해 깊게 알아보기로 한다.
컴퓨터 비전에서의 Outlier 정보 특성
질문: Input data로 수많은 데이터가 들어왔을 때, 우리는 이 중 어떤 데이터가 outlier이고 inlier인지 알 수 있을까?
Naive 답변 1 - 데이터 분포를 분석하기
가장 쉽게 생각할 수 있는 방법은 Raw 데이터의 분포를 보는 것일 것이다.
분포를 보았을 때, 하나의 큰 데이터 분포와 띄엄띄엄 떨어진 데이터들이 있다면, 보통 그 한곳에 모인 큰 데이터 분포를 inlier로 생각하고 띄엄띄엄 떨어진 데이터들이 outlier로 생각될 것이다. 왜냐하면, inlier 데이터는 closed-form에서 잘 작동한다는 전제를 가졌기 때문에 inlier 데이터들은 서로 분포에서 가깝게 나타난다는 특성이 있기 때문이다. 반대로, outlier 데이터는 일정한 분포를 가지지 못한 경우가 많은데, 이는 outlier가 우리가 예상하지 못한 현상에서 오는 경우가 많기 때문이다.
여기까지가 ‘보통의’ 데이터를 받았을 때 우리가 생각하는 방법이다. 통계적으로도 이렇게 생각하는 방식이 일반적이다. 하지만 컴퓨터 비전에서 만큼은 이 방법이 잘 맞지 않는다. 위에서 설명한 방법은 아래와 같은 상황에서 성립하지 않게 되는데, 컴퓨터 비전에서는 이러한 상황이 종종 나타나곤 한다. 즉, 컴퓨터 비전에서는 input 데이터의 분포만 가지고 어떤 데이터가 inlier이고 outlier인지 쉽게 구분할 수가 없다.
- Outlier의 수가 inlier의 수 보다 많은 경우
- Image motion blur
- Outlier들끼리도 분포를 이루는 경우
- 거울에서 반사된 이미지, specular reflection
- Inlier 데이터에 노이즈가 많이 껴있는 경우
- Object motion blur, pixel noise
- Inlier 데이터 자체가 없는 경우
- Occlusion
Naive 답변 2 - Model fitting via least squares
위의 질문에 대해 계속해서 답해보자. 우리는 컴퓨터 비전에서는 input 데이터의 분포만 가지고 inlier와 outlier를 구분할 수 없다는 것을 깨닳았다. 즉, Inlier와 outlier를 구분하기 위해서는 실제로 이 데이터들을 계산식에 넣어보는 방법 (trial-and-error) 밖에 없다는 것을 알았다. 이제 우리가 몇개의 데이터를 샘플링해서 계산식에 넣었다고 해보자. 이 데이터들이 좋은 데이터인지 아닌지 이제 어떻게 알 수 있을까?
가장 쉬운 방법은 (fundamental matrix나 homography matrix와 같은) 모델을 계산해서 샘플링 되지 않은 모든 데이터들이 이 모델과 동의하는지를 보는 것이다. 각각의 데이터와 모델간의 차이 (error, 또는 residual)를 구하고, 이 에러들을 모두 더한다.
두 데이터를 이으면 ‘선’이라는 모델이 나온다.
이 모델에 대해 모든 데이터의 residual 합이 최소가 되는 데이터의 짝을 구하면 된다.
에러의 총합이 내가 ‘에러가 이쯤 안나오면 inlier로 계산한 것이겠다~’ 하고 정한 threshold를 넘지 않으면, 그러면 그 데이터들은 inlier로 고려할 수 있다. 수식으로 표현하면,
하지만 이 방법 역시 극단적인 outlier가 존재하거나, outlier 데이터 사이에도 패턴이 존재하거나, 또는 inlier 패턴이 존재하지 않을경우 작동하지 않는다.
극단적인 outlier가 존재할 경우의 예시.
대다수의 데이터가 M1 모델과 동의함에도 불구하고, outlier의 residual이 너무 크다.
M2 모델은 단 하나의 데이터만 동의하는데도, 전체 residual의 합이 M1 보다 작다.
그러므로 대다수의 데이터가 M1에 동의하는데도, M2가 선택되는 이상한 현상을 볼 수 있다.
M1과 M2 둘 중 하나는 outlier 데이터만으로 만들어진 모델이다.
어떤 모델이 outlier 데이터를 가지고 있는지 모르는 경우, 우리는 어떻게 해야 올바른 모델을 고를 수 있을까?
더 많은 데이터를 포함하는 모델이 항상 inlier는 아니다. Outlier 데이터의 수가 inlier 데이터의 수 보다 많으면 오히려 반대로 고르게 되는 것이다.
여기에 찍힌 데이터가 모두 inlier인 경우에, 우리는 어떤 모델을 골라야하는가?
빨간색과 노란색은 둘 다 데이터를 지나가지만, 전체 비율 50%의 데이터와밖에 동의하지 않는다.
초록색은 residual이 최소화되지만, 단 하나의 데이터도 직접적으로 모델과 동의하지 않는다.
Robust parameter estimation
방금 전 예시에서 본 방법들은 모두 outlier의 영향으로 올바른 모델 선정에 실패했다. 사실 Prior data distribution 분석과 least square model fitting 방법 모두 outlier가 없을때는 잘 작동하는 방법이다. 이 두 방법이 실패한 이유는 순전히 outlier의 영향 때문이다.
그렇다면, outlier가 될만한 요소들을 제거하고 계산해보면 되지 않을까? 이렇게 outlier를 제거하고 모델을 추정하는 기법을 Robust parameter estimation이라고 한다. 여기서 robust-는 outlier가 끼어있어도 강인하게 추정하는- 이라는 뜻을 가지고, parameter는 모델을 구성하는 model parameter를 뜻한다.
방법 1 - Consensus search within a threshold (similar to RANSAC) + least square optimization
이 방법은 RANSAC에서 사용하는 방식에서 조금 더 나아간 방식이 되겠다 (RANSAC을 이해하지 못해도 괜찮다. 이후 포스팅에서 RANSAC 내용을 커버할 것이다). 데이터 샘플링을 통해서 어떠한 모델을 추정해낸다. 그리고 추정된 모델에서 ±로 threshold를 만들어준다.
우리는 이제 다른 데이터는 보지도 않고, 이 threshold
이 inlier들 사이에서 좀 더 좋은 모델을 찾을 수 없을까? 라고 질문이 될 수 있다. 이 방법을 해결하기 위해서는 모든 inlier 데이터들에 대한 residual을 최소화하는 모델 파라미터를 찾으면 된다. 즉, least square optimization을 수행하면 되는 것이다. 이렇게까지하면 outlier 제거 후 noise 제거까지 한 것이 되겠다.
하지만 이 방법도 단점은 있다. Inlier의 데이터 노이즈가 심하다면, threshold
데이터로부터 모델을 추정하고, threshold
그 후 가장 높은 inlier의 수를 가진 모델의 위치에서부터 least squares optimization을 통해 정확한 모델을 추정한다.
방법 2 - Consensus search with weights
또 다른 방법은 방법1과 비슷하지만, threshold를 거는 것 대신에 모델로부터의 residual에 대한 distribution을 그리면 된다. residual이 큰 데이터일 수록 작은 가중치를 가지며 무시되고, residual이 작은 데이터일수록 더 높은 가중치를 가지며 inlier일 확률을 높히는 것이다. 이 방법에서는 실제로 inlier의 노이즈와 outlier 데이터도 계산에 포함되기 때문에, 올바른 distribution만 사용하면 정확한 값을 찾을 수 있다는 점이 장점이다.
하지만 그 올바른 distribution을 어떻게 찾을 것인가? 그 부분이 어렵다.
또, outlier가 강한 패턴을 가지고 있으면 어떻게 할 것인가? 그 부분도 해결되지 않았다.
Residual에 대한 distribution을 그려서 각각의 데이터에 대한 가중치로 이용한다.
높은 residual의 값, 즉 모델이 생각하는 outlier에는 낮은 가중치가,
낮은 residual의 값, 즉 모델이 생각하는 inlier에는 높은 가중치가 부여된다.