The image auto rectification project at Google aims to create a pleasanter version of user photos by correcting the small, involuntary camera rotations (roll / pitch/ yaw) that often occur in non-professional photographs. Our system takes the image closer to the fronto-parallel view by performing an affine rectification on the image that restores parallelism of lines that are parallel in the fronto-parallel image view. This partially corrects perspective distortions, but falls short of full metric rectification which also restores angles between lines. On the other hand the 2D homography for our rectification can be computed from only two (as opposed to three) estimated vanishing points, allowing us to fire upon many more images. A new RANSAC based approach to vanishing point estimation has been developed. The main strength of our vanishing point detector is that it is line-less, thereby avoiding the hard, binary (line/no-line) upstream decisions that cause traditional algorithm to ignore much supporting evidence and/or admit noisy evidence for vanishing points. A robust RANSAC based technique for detecting horizon lines in an image is also proposed for analyzing correctness of the estimated rectification. We post-multiply our affine rectification homography with a 2D rotation which aligns the closer vanishing point with the image Y axis.

The Google newspaper search program was launched on September 8, 2008. In this paper, we outline the technology pieces underlying this large and complex project. We have created a production pipeline which takes newspaper microfilms as input and emits individual news articles as output. These articles are then indexed and added to the content base, so that they turn up in response to Google searches. Thus, in response to a Google query ldquoHitler deathrdquo, we are able to show newspaper articles from the very day it was reported, authentic and unbiased by passage of time. Non-uniform illumination, presence of significant noise, tears and scratches in the microfilm image, all pose special challenges for this project. The significant variation of layouts across newspapers and time eras, the variations in font sizes occurring in a single page (which confuses the OCR engine) compound the difficulties. The project is still going on after the initial launch was made (with about 15 million news articles).

An algorithm for computing three-dimensional (3-D) velocity field and motion parameters from a range image sequence is presented. It is based on a new integral 3-D rigid motion invariant feature-the trace of a 3x3 "feature matrix" related to the moment of inertia tensor. This trace can be computed at every point of a moving surface and provides a quantitative measure of the local shape of the surface. Based on the feature's conservation along the trajectory of every moving point, a 3-D Flow Constraint Equation is formulated and solved for the velocity field. The robustness of the feature in presence of noise and discontinuity is analyzed.

A new computational model for optical flow estimation is proposed. The proposed model utilizes trajectory information present in a multiframe spatio-temporal volume. Optical flow estimation is formulated as an optimization problem. The solution to this optimization problem yields a velocity field corresponding to smoothest and shortest trajectories of constant intensity points within the spatio-temporal volume. The approach is motivated by principles of inertia of motion and least action in physics and vision psychology. An analogy between a trajectory and a "thin wire" is discussed. A simple mechanism for handling trajectory discontinuities is also incorporated. The optimization problem is solved by stochastic relaxation techniques. Some experimental results and performance comparisons with two existing optical flow estimation techniques are presented to demonstrate the effectiveness of the proposed approach.>

An algorithm for computing 3D motion (velocity field and motion parameters) from a sequence of range images is presented. The algorithm is based on a new integral 3D rigid motion invariant feature which can be computed locally at every point of the moving surface. This feature is the trace of a 3/spl times/3 matrix (referred to as "feature matrix" in the paper) which is closely related to the moment of inertia tenser in physics. This trace of the "feature matrix" at any point provides a quantitative measure of the local shape of the surface around that point. Since the trace feature is rigid motion invariant, it remains conserved along the trajectory of every moving point. Based on that, a 3D flow constraint equation is formulated at every point on the surface, which can be solved for the velocity at the point using optical flow techniques. Since the proposed feature is integral in nature, it is robust in terms of noise and discontinuity in the moving surface. Theoretical analysis is provided to justify these claims. Experimental results are also provided to justify the efficacy of the method.>