Quasi-Euclidean Uncalibrated Epipolar Rectification

Epipolar rectification transforms a pair of images so that the epipolar lines are parallel and horizontal and matching points have the same vertical coordinate. Euclidean epipolar rectification refers to the rectification of images produced by calibrated cameras, that is, images for which the camera matrix (intrinsic and extrinsic parameters) is known. Quasi-Euclidean epipolar rectification refers to the rectification of images taken by uncalibrated cameras with results comparable to the calibrated case.

Quasi-Euclidean Uncalibrated Epipolar Rectification by A. Fusiello and L. Irsara is a method that gives quite good results but the implementation details are a tad sketchy. Quasi-Euclidean Epipolar Rectification by Pascal Monasse goes into the details of implementation missing from the Fusiello-Irsara method. The following slides go a little bit further.

The input is a pair of images taken by uncalibrated cameras and a set of feature matches between the two images, typically obtained by Scale-invariant feature transform (SIFT) and Random sample consensus (RANSAC). The crux of the method is to find the two rotations to apply to the cameras (around their optical centers) as well as the focal length such that the Sampson error is minimized (by the Levenberg–Marquardt algorithm).

It might be a good idea to delve into inner workings of the Levenberg–Marquardt algorithm, a cross between the Gauss-Newton algorithm and Gradient descent: