Ceres-Solver Tutorial : 최적화 문제를 푸는 라이브러리 (1)

다음은 Ceres-Solver 튜토리얼 사이트 (http://ceres-solver.org/nnls_tutorial.html) 를 번역하고 추가적인 설명을 덧붙인 글입니다. 

---

Ceres Solver는 대규모 비선형 최적화 문제를 푸는 오픈소스 C++ 라이브러리이다. 구글 엔지니어들에 의해 개발되었고, 특히 컴퓨터 비전, 로봇공학 등의 분야에서 자주 사용된다. 이 라이브러리는 Levenberg-Marquardt, Dogleg, 및 이러한 방법을 확장한 Trust Region 방식과 같은 최적화 알고리즘을 제공한다.
Ceres Solver의 주요 특징은 다음과 같다:

1. 자동 미분 지원: 사용자는 비선형 함수의 수식을 제공하면 Ceres가 자동으로 미분을 계산한다. 이는 복잡한 함수에 대한 미분을 직접 계산할 필요가 없어 유용하다.
2. 수치적 안정성: 뉴턴 방식과 비슷한 Trust Region 방식을 사용하여 최적화 과정에서 수치적 안정성을 유지한다.
3. 효율성: sparse matrix를 사용하여 대규모 최적화 문제를 효율적으로 처리할 수 있다.
4. 사용자 정의 가능성: 사용자가 직접 손실 함수, 제약 조건, 파라미터화 방법 등을 정의할 수 있어 유연하다.
5. 병렬 처리: 멀티스레드를 지원하여 컴퓨팅 자원을 효율적으로 사용할 수 있다.

Ceres Solver는 특히 컴퓨터 비전 분야에서 3D 구조 복원, 카메라 캘리브레이션, 이미지 등록 등의 문제에 널리 사용된다. Google의 Street View에서도 사용되는 것으로 알려져 있으며, 실제 상업적 제품이나 연구에서도 많이 활용되고 있다.

Tutorial

예를 들어 이런 종류의 non-linear least squares problem 을 해결하는 것은 다양한 분야에서 널리 사용된다. 예를 들어 Bundle Adjustment 가 있다.

Ceres Solver 에서 이 수식은 Residual Block 이라고 불리고, f 는 Cost Function 이다. 여러 최적화 문제들에서는 스칼라들이 그룹 단위로 나오고는 하는데, Ceres 에서는 그런 소규모의 스칼라 그룹을 ParameterBlock 이라고 부른다. ParameterBlock 은 single parameter 일 수 있다.
해당 수식에서 ρ 는 Loss Function 이다. Loss Function 은 non-linear least squares 문제에서 outlier 의 영향을 줄이는 역할을 한다.

Residual Function

 
Ceres Solver에서 "residual function"은 최적화 문제에서 최소화하고자 하는 핵심 요소이다. 이 함수는 주어진 파라미터에 대해 "잔차(residual)" 값을 계산하며, 최적화 과정은 이 잔차의 제곱합을 최소화하는 것을 목표로 한다.
최적화 문제에서는 일반적으로 관측된 데이터와 모델 예측 간의 차이를 최소화하기 위해 사용된다. 예를 들어, 관측된 데이터 포인트들과 모델 예측 간의 차이를 계산하는 함수가 잔차 함수이다. 이 차이는 잔차라고 불리며, Ceres Solver는 이 잔차들의 제곱합을 최소화하여 최적의 파라미터를 찾는다.

Ceres Solver에서의 구현

 
Ceres Solver를 사용할 때, 사용자는 이 잔차 함수를 구현해야 한다. Ceres는 사용자가 제공한 잔차 함수를 바탕으로 자동 미분(또는 수치 미분, 분석적 미분)을 사용하여 잔차의 자코비안을 계산한다. 이 정보를 사용하여 최적화 문제를 효과적으로 해결한다.
잔차 함수는 Ceres Solver에서 최적화 문제의 "비용 함수(cost function)"의 일부로서, 이 비용 함수가 최소화되는 파라미터 값을 찾는 것이 최적화의 목표이다. 잔차 함수의 구현과 관련하여 Ceres는 다양한 최적화 기법과 도구를 제공하여 사용자가 효과적으로 최적화 문제를 해결할 수 있도록 돕는다.

Hello World!

예를 들어 다음과 같은 수식의 최솟값을 찾는 문제를 생각해 보자.
Ceres Solver 로 다음과 같은 문제를 해결하기 위해서는 첫 번째로 f(x) = 10-x 를 작성하는 것이다.
 

struct CostFunctor {
	template <typename T>
	bool operator()(const T* const x, T* residual) const {
		residual[0] = 10.0 - x[0];
		return true;
	}
}

 
여기서 주목해야 할 것은 operator() 이 templated method 라는 점이다. input 과 output 이 동일한 T 형태로 나온다.
 

int main(int argc, char** argv){
	google::InitGoogleLogging(argv[0]);
	
	double initial_x = 5.0;
	double x = initial_x; //최적화할 변수 x 를 초기화한다.
	
	Problem problem;
	//Ceres Solver의 Problem 객체를 생성한다. 이 객체는 최적화 문제를 정의하고 관리하는 역할을 한다.
	
	CostFunction* cost_function = new AutoDiffCostFunction<CostFunctor,1,1>(); 
	//잔차 함수를 정의하는 CostFunction 객체를 생성한다. AutoDiffCostFunction은 자동 미분 기능을 활용하여 자코비안(미분값)을 계산한다. CostFunctor는 사용자가 정의해야 하는 구조체로, 실제 계산을 수행한다. <1, 1>은 잔차와 독립 변수의 차원을 나타낸다.

	problem.AddResidualBlock(cost_function, nullptr, &x);
	//Residual 블록은 위에서 정의한 cost_function을 사용한다. nullptr은 로스 스케일링을 사용하지 않겠다는 의미입니다.
	
	Solver::Options options; //최적화 solver 의 옵션을 설정하는 객체를 생성한다. 
	options.linear_solver_type = ceres::DENSE_QR; //선형 솔버 유형을 QR 분해를 사용하는 dense 솔버로 설정한다.
	options.minimizer_progress_to_stdout = true; //솔버의 진행 상태를 표준 출력으로 redirect 한다. 이 옵션을 통해 사용자는 최적화 과정을 실시간으로 모니터링할 수 있다.

	Solver::Summary summary; //최적화 작업의 결과를 저장할 객체를 생성한다. 
	Solve(options, &problem, &summary);
	
	std::cout << summary.BriefReport() << "\\n";
	std::cout << "x: " << initial_x << " -> " << x << "\\n";
	return 0;
}

 
AutoDiffCostFunction 은 CostFunctor 를 입력으로 받아 자동으로 미분해주며 이 값을 CostFunction 인터페이스로 넘겨준다.
만약 이 코드를 실행하게 되면 다음과 같은 출력을 얻을 수 있다.
 

iter      cost      cost_change  |gradient|   |step|    tr_ratio  tr_radius  ls_iter  iter_time  total_time
   0  4.512500e+01    0.00e+00    9.50e+00   0.00e+00   0.00e+00  1.00e+04       0    5.33e-04    3.46e-03
   1  4.511598e-07    4.51e+01    9.50e-04   9.50e+00   1.00e+00  3.00e+04       1    5.00e-04    4.05e-03
   2  5.012552e-16    4.51e-07    3.17e-08   9.50e-04   1.00e+00  9.00e+04       1    1.60e-05    4.09e-03
Ceres Solver Report: Iterations: 2, Initial cost: 4.512500e+01, Final cost: 5.012552e-16, Termination: CONVERGENCE
x : 0.5 -> 10

 
x=5 부터 시작해서 solver 는 두 개의 iteration 을 돌아 10으로 가게 된다. 자세히 살펴본다면 이것이 linear problem 이기 때문에 하나의 linear solve 가 최적값임을 알 수 있다. 또한 첫 번째 iteration 에서 최적값에 가까운 해를 얻었다는 점도 주목할 만 하다.