Computer Vision Tools

Camera modeling and calibration:

Camera “Optic sensor”: First accurate description was in early 11th century Egypt “Ibn Al-Haitham” Ibn Al-Haitham established that “Light travels in a straight line and when some of the rays reflected from a bright subject pass through the small hole in thin material they do not scatter but cross and reform as an upside down image on a flat white surface held parallel to the hole. The smaller is the hole the clearer is the picture”. First permanent photograph was in Paris 1826 by Niépce using a sliding wooden box camera. The use of photographic film was pioneered by Eastman, his first camera, the “Kodak”.

The image formation process in the ideal pinhole camera system constitutes the basics for the conventional perspective camera model, which is used in computer vision. In this model there are three main components, the camera center, which is the perspective projection center, and the retinal plane (image plane), which is located at a distance equal to the focal length from the camera center. The image of a 3D scene point is the intersection of a line connecting this 3D scene point and the camera center (As shown in the figure.)

The calibration process is to find the model parameters. These parameters mainly consists of two sets: the extrinsic parameter [R|T] (rotation and translation that convert the 3D scene point from an arbitrarily world coordinates system to camera coordinates system.) and the intrinsic parameters K (focal length and viewing angles, pixel size).

Structure from Motion

 It is called also Shape from Motion (SFM). This term refers to extracting the shape of a scene from the spatial and temporal changes occurring in an image sequence. Given a set of image feature trajectories over time, solve for their 3D positions and camera motion. This includes estimation of Camera’s internal geometry “Focal length”, relative 3D motion between the camera and the scene, and the structure “the depth, or 3D Shape.”

Similar to stereo-based technique: SFM finds correspondences from consecutive frames, it reconstruct the scene.

Differences from stereo: it consists of different views from single camera, differences between consecutive frames are smaller than those of stereo pairs, and 3D displacement between the viewing camera and the scene is not necessarily caused by a single 3D transformation. This approach is used in many applications such as Applications: 3D Model Reconstruction, Camera Calibration, Perceptual Computer Interfaces, Robotics, 3D Coding of Image Sequences, and Mosaics and Rectification.

Shape Modeling:

Shape modeling research involves the dissemination of mathematical theories and computational techniques for modeling, simulating and processing digital representations of shapes and their properties. A shape model can be defined as the boundaries of the corresponding object. This boundary can be represented either implicitly or explicitly. Parametric representations are used to represent shape explicitly but have problems with the topology changes of shapes. The implicit representations have a big advantage over explicit methods because they handle the topology changes naturally without any need of parameterization. Implicit shape models include distance and signed distance transforms. This type of scalar functions represents shapes at their zero level points. It is very important in several applications including shape matching, registration, and shape-based segmentation. However, they have some limitation in the shape matching process by restricting the transformation parameters. The implicit vector representation can overcome these restrictions by generalizing the matching process. The vector representations include the vector distance transform as well as the vector level set function proposed in the ICCV2005.

Shapes can be modeled by computing their medial axis or skeletons as well. Representing a 3D shape by a set of 1D curves that are locally symmetric with respect to its boundary (i.e., curve skeletons) is of importance in several machine intelligence tasks. We developed a fast, automatic, and robust variational framework for computing continuous, sub-voxel accurate curve skeletons from volumetric objects. A reference point inside the object is considered a point source that transmits two wave fronts of different energies. The first front converts the object into a graph, from which the object salient topological nodes are determined. Curve skeletons are tracked from these nodes along the cost field constructed by the second front until the point source is reached. The accuracy and robustness of the proposed work are validated against competing techniques as well as a database of 3D objects. Unlike other state-of-the-art techniques, the proposed framework is highly robust because it avoids locating and classifying skeletal junction nodes, employs a new energy that does not form medial surfaces, and finally extracts curve skeletons that correspond to the most prominent parts of the shape and hence are less sensitive to noise.

Kalman Filters:

A Kalman filter is used to estimate the state of a linear system where the state is assumed to be distributed by a Gaussian. Kalman filtering is composed of two steps, prediction and correction. The prediction step uses the state model to predict the new state of the variables:

where      are the state and the covariance predictions at time t. D is the state transition matrix which defines the relation between the state variables at time t and t − 1. Q is the covariance of the noise W. Similarly, the correction step uses the current observations Ztto update the object’s state:

where v is called the innovation, M is the measurement matrix, K is the Kalman gain, which is the Riccati Equation (4) used for propagation of the state models. Note that the updated state, Xtis still distributed by a Gaussian. In case the functions ftand htare nonlinear, they can be linearized using the Taylor series expansion to obtain the extended Kalman filter [Bar-Shalom and Foreman 1988]. Similar to the Kalman filter, the extended Kalman filter assumes that the state is distributed by a Gaussian.

The Kalman filter has been extensively used in the vision community for tracking. Broida and Chellappa [1986] used the Kalman filter to track points in noisy images. In stereo camera-based object tracking, Beymer and Konolige [1999] use the Kalman filter for predicting the object’s position and speed in x − z dimensions. Rosales and Sclaroff [1999] use the extended Kalman filter to estimate 3D trajectory of an object from 2D motion.

Kalman Filter Algorithm

Particle Filters:

One limitation of the Kalman filter is the assumption that the state variables are normally distributed (Gaussian). Thus, the Kalman filter will give poor estimations of state variables that do not follow Gaussian distribution. This limitation can be overcome by using particle filtering [Tanizaki 1987]. In particle filtering, the conditional state density p(Xt|Zt) at time t is represented by a set of samples {s(n)t : n = 1, . . . , N} (particles) with weights π(n)t (sampling probability). The weights define the importance of a sample, that is, its observation frequency [Isard and Blake 1998]. To decrease computational complexity, for each tuple (s(n), π(n)), a cumulative weight c(n) is also stored, where c(N) = 1.

The new samples at time t are drawn from  St−1 = {(s(n)t−1, π(n)t−1, c(n)t−1) : n = 1, . . . , N} at the previous time t − 1 step based on different sampling schemes [MacKay 1998].

Using the new samples St, one can estimate the new object position by

Particle filter-based trackers can be initialized by either using the first measurements, s(n)0 ∼ X0, with weight π(n)0= 1/N or by training the system using sample sequences. In addition to keeping track of the best particles, an additional resampling is usually employed to eliminate samples with very low weights. Note that the posterior density does not have to be a Gaussian. Particle filters recently became popular in computer vision. They are especially used for object detection and tracking.

Particle Filter Algorithm

Shape from Shading

Important references:

• M.T. Ahmed El-Melegy and Aly A. Farag, “Nonmetric Calibration of Camera Lens Distortion: Differential Methods and Robust Estimation,” IEEE Transactions on Image Processing, vol. 43, no. 7, pp. 1215-1230, August 2005.

• M. T. Ahmed and A. A.  Farag,  ”Differential Methods for Non-metric Calibration of Camera Lens Distortion,” IEEE International Conference on Computer Vision and Pattern Recognition (CVPR’2001), Hawaii, Vol. 2, pp. 477-482, December 2001

• M. Sabry Hassouna and A. A. Farag, TPAMI-0845-1206 – Variational Curve Skeletons Using Gradient Vector Flow,” IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 31,  No.12, pp. 2257 – 2274, Dec. 2009.

• H. E. Abd El Munim and A. A. Farag, ”Curve/Surface Representation and Evolution using Vector Level Sets with Application to the Shape based Segmentation Problem,” IEEE Transaction on Pattern Analysis and Machine Intelligence (PAMI), Vol. 29, No. 6, pp. 945-958, June 2007.

• H. E. Abd El Munim and A.A. Farag, ”Shape Representation and Registration using Vector Distance Functions,” IEEE Conference on Computer Vision and Pattern Recognition (CVPR07), Minnesota, USA, June 20

• Kalman, R.E., “A New Approach to Linear Prediction Problems”, Transactions of the ASME–Journal of Basic Engineering, pp. 35-45, March 1960.

• Sorenson, H.W., “Least Squares Estimation: from Gauss Kalman”, IEEE Spectrum, vol. 7, pp. 63-68, July 1970.

• Grewal M., Andrew A,. ‘Kalman Filter theory and practice’ 2nd edition,2002.

• B. Mohafza, “Radar system analysis and design using MATLAB” ,2005

• N. J. Gordon, D. J. Salmond, and A. F. M. Smith, “Novel approach to nonlinear/non-Gaussian Bayesian state estimation,” IEE Proceedings-F, vol. 140, no. 2, pp. 107–113, 1993.

• M. S. Arulampalam, S. Maskell, N. Gordon, and T. Clapp, “A tutorial on particle filters for online nonlinear/non-gaussian Bayesian tracking,” IEEE Transactions on Signal Processing, vol. 50, no. 2, pp. 174–188, 2002.

• B. Ristic, S. Arulampalam, N. Gordon, Beyond the Kalman Filter: Particle Filters for Tracking Applications, Artech House Publishers, 2004.

•  A.Yilmaz, O. Javed and M. Shah,” Object Tracking: A Survey”, ACM Computing Surveys, Vol. 38, No. 4, Article 13, Publication date: December 2006.

Copyright © 2011, All rights reserved to CVIP Laboratory, Computer Vision & Image Processing Laboratory, University of Louisville,Kentucky, USA.
Designed & Maintained by webmasters team