기하학적 비전 문제들의 파라미터 추정을 위한 고속의 L-infinity 최적화 기법과 Outlier 제거
Fast L1 Optimization and Outlier Removal for Estimating Parameters of Geometric Vision Problems
- 발행기관 서강대학교 영상대학원
- 지도교수 서용덕
- 발행년도 2013
- 학위수여년월 2013. 2
- 학위명 박사
- 학과 및 전공 영상대학원 미디어공학
- 실제URI http://www.dcollection.net/handler/sogang/000000049635
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작권 보호를 받습니다.
초록/요약
컴퓨터 비전의 기하학적 문제를 풀기 위해 잘 알려진 방법들 중 최근 많이 다뤄지고 있는 기술이 볼록 최적화(convex optimization) 기법이다. 이전에는 제곱합 오차 노름인 L2 오차 노름(error norm)을 최소화하여 특정 파라미터들을 계산했다고 하면 볼록 최적화는 오차들 중 최대값을 나타내는 L-infinity 오차 노름를 최소화하는 방식이다. 두 방식에 차이가 있다면 L2노름 최적화와 달리 L-infinity노름 최적화는 2차원뿔 프로그래밍 (SOCP:second order cone programming) 알고리즘을 이용하여 전역 최적점(global optimum)이 계산 된다는 것이다. L-infinity 오차가 준볼록(quasi-convex) 함수이기 때문에 전역 최적점에 도달하기 위하여 이분법(bisection method)을 사용한다. 이분법 알고리즘은 측정 데이터를 의미하는 2차원뿔(second order cone)들이 만나는 교점(intersection)에 대한 실행가능성(feasibility)을 테스트하고, 반복적으로 전역 오차 수준(global error level)을 조절하는 방법이다. 이것이 L-infinity 최적화의 기본 과정이다. 본 논문에서는 L-infinity 최적화를 이용한 세 가지 종류의 문제에 대해서 언급하고 있다. 첫 번째 문제는 연속적인 시간에 대한 동일한 3차원 포인트 값을 계산하는 삼각법(triangulation) 방법을 소개하고, 두 번째로는 SOI(the sum of infeasibilities)를 최소화하여 outlier들을 제거하는 문제에 대해 다룰 것이다. 마지막으로 SOI를 반복 수행하여 inlier 수를 최대로 하는 알고리즘을 제안하고자 한다. 연속적으로 입력 받는 이미지 측정 데이터에 대한 삼각법은 수행 시간을 줄여 3차원 포인트 값을 업데이트 해 나가는 방법이다. 시간을 줄이기 위한 가장 중요한 방법은 효율적인 최적화 수행을 위한 측정 데이터 수를 유지하는 것이다. 뿐만 아니라, 상계(upper bound)와 하계(lower bound) 사이의 차이를 가능한 작게 유지 시켜 준다. 마지막 단계로 새로 입력된 측정 데이터의 재투영 오차(reprojection error)가 이전에 평가된 오차값 보다 작으면 파라미터를 다시 계산하지 않는다. 이 세 가지 과정을 통해 빠르게 최적화 결과를 얻는다. SOI 최소화는 잠재하는 outlier를 효과적으로 분류해 내기 위한 방법이다. 최근 SOI 최소화는 L-infinity 노름 최소화 (norm minimization) 체계에 바탕을 두고 강건한 오차 함수 (robust error function)를 최소화하는 근사화 방법으로 사용되고 있다. SOI 최소화 방법은 사실 기하학적 비전 문제들에 있어서 outlier를 구별해 내는데 효율적이다. 특히, RANSAC이 적용되지 못하는 카메라 회전값을 알 때의 카메라 움직임과 물체의 3차원 정보값 계산 (motion and structure with known rotation) 문제에 있어 매우 유용하게 사용된다. 마지막 문제는 outlier를 제거 하면서 강건한 파라미터를 추정 하기 위한 연구로 SOI 반복 수행을 통해 최대 inlier 수를 획득하여 계산 된 파라미터의 강건성을 보장해 준다. L-infinity minimization 알고리즘을 이용한 몇몇 outlier 제거 방법들은 최대 inlier 수를 보장하지 못한다. 다시 말해, 이 방법들은 outlier를 제거 하는 동안 inlier도 같이 버려진다는 의미이다. 최대 inlier 수는 SOI 최소화를 반복 수행하여 얻게 된다. 합성 데이터와 실제 데이터를 이용한 실험들은 제안하는 세 가지 방법들의 효율성과 향상된 결과를 보여 주었다.
more초록/요약
The convex programming techniques have been introduced and widely studied in the area of computer vision based geometric reconstruction. While the sum-of-squared (L2) errors is minimized for estimating the set of parameters in a traditional way, convex optimization in this paper L1 error, that is, the maximum among the errors. The difference between L2 errors and L1 error is that L1 error is able to find the global optimum of the error function using the well developed algorithm called SOCP (second order cone programming). Because L1 error belongs to quasi-convex functions, bisection method is utilized to attain the global optimum. It tests the feasibility of the intersection of all the second order cones due to measurements, repeatedly adjusting the global error level. This is the basis of L1 optimization. This dissertation addresses three kinds of problems using L1 optimization. The first problem is about the sequential triangulation. The second problem is for removing outliers by minimizing the sum of infeasibilities(SOI). And, the last problem is to obtain the maximum number of inliers using SOI iteration method with a surrogate function. Sequential triangulation proposes a method to update the coordinates of a 3D point whose image location measurements are provided through a time sequence by reducing computation time. The key idea to reduce the computation time is to keep the number of measurements that are effectively used for the optimization. In addition, the gap of the upper and lower bounds is always kept as small as possible. The third strategy is that the parameters are not re-estimated when the reprojection error of the newly arrived measurement is smaller than the estimation error. These provide a fast optimization. The process of minimizing the sum of infeasibilities (SOI) is for classifying latent outliers efficiently. The SOI minimization was adopted recently as an approximation method to minimize a robust error function under the framework of the L1 norm minimization. The SOI minimization approach is practically effective in collecting outliers when it is applied to geometric vision problems. In particular, this method is useful in structure and motion reconstruction where methods such as RANSAC are not applicable. The third problem is about an efficient method of removing outliers to obtain the maximum number of inliers using SOI(the sum of infeasibilities) iteration method. Some existing L1 minimization methods for removing outliers can not guarantee the maximum number of inliers. In other word, when these methods remove outliers, some inliers are also discarded. Through this algorithm, the maximum number of inliers can be obtained by iterating the minimization of the sum of infeasibilities. Experiments with synthetic and real data demonstrate the efficiency and significant improvements of these three methods.
more