Sunday, May 26, 2013

Hessian Matrix and Jacobian Matrix

Hessian Matrix
In mathematics, the Hessian matrix or Hessian is a square matrix of second-order partial derivatives of a function. It describes the local curvature of a function of many variables. The Hessian matrix was developed in the 19th century by the German mathematician Ludwig Otto Hesse and later named after him. Hesse originally used the term "functional determinants".
Given the real-valued function
f(x_1, x_2, \dots, x_n),\,\!
if all second partial derivatives of f exist and are continuous over the domain of the function, then the Hessian matrix of f is
H(f)_{ij}(\mathbf x) = D_i D_j f(\mathbf x)\,\!
where x = (x1x2, ..., xn) and Di is the differentiation operator with respect to the ith argument. Thus
H(f) = \begin{bmatrix}
\dfrac{\partial^2 f}{\partial x_1^2} & \dfrac{\partial^2 f}{\partial x_1\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_1\,\partial x_n} \\[2.2ex]
\dfrac{\partial^2 f}{\partial x_2\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_2^2} & \cdots & \dfrac{\partial^2 f}{\partial x_2\,\partial x_n} \\[2.2ex]
\vdots & \vdots & \ddots & \vdots \\[2.2ex]
\dfrac{\partial^2 f}{\partial x_n\,\partial x_1} & \dfrac{\partial^2 f}{\partial x_n\,\partial x_2} & \cdots & \dfrac{\partial^2 f}{\partial x_n^2}
\end{bmatrix}.
Because f is often clear from context, H(f)(\mathbf x) is frequently abbreviated to H(\mathbf x).
The Hessian matrix is related to the Jacobian matrix by H(f)(\mathbf x) = J(\nabla \! f)(\mathbf x).
The determinant of the above matrix is also sometimes referred to as the Hessian.[1]
Hessian matrices are used in large-scale optimization problems within Newton-type methods because they are the coefficient of the quadratic term of a local Taylor expansion of a function. That is,
y=f(\mathbf{x}+\Delta\mathbf{x})\approx f(\mathbf{x}) + J(\mathbf{x})\Delta \mathbf{x} +\frac{1}{2} \Delta\mathbf{x}^\mathrm{T} H(\mathbf{x}) \Delta\mathbf{x}
where J is the Jacobian matrix, which is a vector (the gradient) for scalar-valued functions. The full Hessian matrix can be difficult to compute in practice; in such situations, quasi-Newton algorithms have been developed that use approximations to the Hessian. The best-known quasi-Newton algorithm is the BFGS algorithm
Jacobian Matrix

In vector calculus, the Jacobian matrix is the matrix of all first-order partial derivatives of a vector-valued function. Specifically, suppose F : \mathbb{R}^n \rightarrow \mathbb{R}^m is a function (which takes as input real n-tuples and produces as output real m-tuples). Such a function is given by m real-valued component functions, F_1(x_1,\ldots,x_n),\ldots,F_m(x_1,\ldots,x_n). The partial derivatives of all these functions with respect to the variables x_1,\ldots,x_n (if they exist) can be organized in an m-by-n matrix, the Jacobian matrix J of F, as follows:
J=\begin{bmatrix} \dfrac{\partial F_1}{\partial x_1} & \cdots & \dfrac{\partial F_1}{\partial x_n} \\ \vdots & \ddots & \vdots \\ \dfrac{\partial F_m}{\partial x_1} & \cdots & \dfrac{\partial F_m}{\partial x_n}  \end{bmatrix}.


Friday, May 3, 2013

Implementation of KalmanFilter in Opencv

Two Functions used: gemm , solve
gemm: Performs generalized matrix multiplication.
C++: void gemm(InputArray src1, InputArray src2, double alpha, InputArray src3, double gamma, OutputArray dst, intflags=0 )
The function performs generalized matrix multiplication similar to the gemm functions in BLAS level 3. For example, gemm(src1,src2, alpha, src3, beta, dst, GEMM_1_T + GEMM_3_T) corresponds to
\texttt{dst} =  \texttt{alpha} \cdot \texttt{src1} ^T  \cdot \texttt{src2} +  \texttt{beta} \cdot \texttt{src3} ^T

solve: Solves one or more linear systems or least-squares problems.
C++: bool solve(InputArray src1, InputArray src2, OutputArray dst, int flags=DECOMP_LU)
  • solution (matrix inversion) method.
    • DECOMP_LU Gaussian elimination with optimal pivot element chosen.
    • DECOMP_CHOLESKY Cholesky LL^T factorization; the matrix src1 must be symmetrical and positively defined.
    • DECOMP_EIG eigenvalue decomposition; the matrix src1 must be symmetrical.
    • DECOMP_SVD singular value decomposition (SVD) method; the system can be over-defined and/or the matrix src1 can be singular.
    • DECOMP_QR QR factorization; the system can be over-defined and/or the matrix src1 can be singular.
    • DECOMP_NORMAL while all the previous flags are mutually exclusive, this flag can be used together with any of the previous; it means that the normal equations\texttt{src1}^T\cdot\texttt{src1}\cdot\texttt{dst}=\texttt{src1}^T\texttt{src2} are solved instead of the original system \texttt{src1}\cdot\texttt{dst}=\texttt{src2} .
The function solve solves a linear system or least-squares problem (the latter is possible with SVD or QR methods, or by specifying the flag DECOMP_NORMAL ):
\texttt{dst} =  \arg \min _X \| \texttt{src1} \cdot \texttt{X} -  \texttt{src2} \|
namespace cv
{
KalmanFilter::KalmanFilter() {}
KalmanFilter::KalmanFilter(int dynamParams, int measureParams, int controlParams, int type)
{
init(dynamParams, measureParams, controlParams, type);
}
void KalmanFilter::init(int DP, int MP, int CP, int type)
{
CV_Assert( DP > 0 && MP > 0 );
CV_Assert( type == CV_32F || type == CV_64F );
CP = std::max(CP, 0);
statePre = Mat::zeros(DP, 1, type);
statePost = Mat::zeros(DP, 1, type);
transitionMatrix = Mat::eye(DP, DP, type);
processNoiseCov = Mat::eye(DP, DP, type);
measurementMatrix = Mat::zeros(MP, DP, type);
measurementNoiseCov = Mat::eye(MP, MP, type);
errorCovPre = Mat::zeros(DP, DP, type);
errorCovPost = Mat::zeros(DP, DP, type);
gain = Mat::zeros(DP, MP, type);
if( CP > 0 )
controlMatrix = Mat::zeros(DP, CP, type);
else
controlMatrix.release();
temp1.create(DP, DP, type);
temp2.create(MP, DP, type);
temp3.create(MP, MP, type);
temp4.create(MP, DP, type);
temp5.create(MP, 1, type);
}
const Mat& KalmanFilter::predict(const Mat& control)
{
// update the state: x'(k) = A*x(k)
statePre = transitionMatrix*statePost;
if( control.data )
// x'(k) = x'(k) + B*u(k)
statePre += controlMatrix*control;
// update error covariance matrices: temp1 = A*P(k)
temp1 = transitionMatrix*errorCovPost;
// P'(k) = temp1*At + Q
gemm(temp1, transitionMatrix, 1, processNoiseCov, 1, errorCovPre, GEMM_2_T);
return statePre;
}
const Mat& KalmanFilter::correct(const Mat& measurement)
{
// temp2 = H*P'(k)
temp2 = measurementMatrix * errorCovPre;
// temp3 = temp2*Ht + R
gemm(temp2, measurementMatrix, 1, measurementNoiseCov, 1, temp3, GEMM_2_T);
// temp4 = inv(temp3)*temp2 = Kt(k)
solve(temp3, temp2, temp4, DECOMP_SVD);
// K(k)
gain = temp4.t();
// temp5 = z(k) - H*x'(k)
temp5 = measurement - measurementMatrix*statePre;
// x(k) = x'(k) + K(k)*temp5
statePost = statePre + gain*temp5;
// P(k) = P'(k) - K(k)*temp2
errorCovPost = errorCovPre - gain*temp2;
return statePost;
}
};
view raw gistfile1.cpp hosted with ❤ by GitHub

OpenCV: Surf Matching in Video Sequence

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "opencv2\opencv.hpp"
#include <opencv2\nonfree\features2d.hpp>
using namespace std;
using namespace cv;
int main()
{
Mat img_1, img_2;
//image = imread("lena.jpg",1);
//img_1= imread("C:/Users/JimWei/Documents/Visual Studio 2010/Projects/FeatureExtractionOpenCV/FeatureExtractionOpenCV/PCB.jpg", CV_LOAD_IMAGE_GRAYSCALE );
img_1= imread("PCB.jpg", CV_LOAD_IMAGE_GRAYSCALE );
if(img_1.empty())
{
cout << "Could not open or find the first image" << std::endl ;
return -1;
}
resize(img_1,img_1,Size(0,0),0.15,0.15,INTER_LINEAR);
imshow("Image 1", img_1);
VideoCapture capture(0);
if (!capture.isOpened())
{
cerr<<" Could not create capture";
return -1;
}
while(true)
{
capture>>img_2;
cvtColor(img_2,img_2,CV_RGB2GRAY);
resize(img_2,img_2,Size(0,0),0.5,0.5,INTER_LINEAR);
imshow("VideoSequence",img_2);
//resize(img_2,img_2,Size(0,0),0.2,0.2,INTER_LINEAR);
// Step -1, Detect keypoints using SURF detector
int minHessian = 100;
SurfFeatureDetector detector(minHessian);
vector<KeyPoint> keypoints_1, keypoints_2;
detector.detect(img_1, keypoints_1);
detector.detect(img_2, keypoints_2);
// Step -2, Calculate descriptors (feature vector)
SurfDescriptorExtractor extractor;
Mat descriptor_1, descriptor_2;
extractor.compute(img_1,keypoints_1,descriptor_1);
extractor.compute(img_2,keypoints_2,descriptor_2);
// maches with Flann Based Matching.
double t = (double)getTickCount();
FlannBasedMatcher matcher2;
vector<DMatch> matches2;
matcher2.match(descriptor_1,descriptor_2,matches2);
t = ((double)getTickCount() - t)/getTickFrequency();
cout << " Flann Based Matching Time (senconds): " << t<<endl;
// quick calcualation of max and min distances between keypoints
double max_dist=0; double min_dist = 100;
for (int i =0; i < descriptor_1.rows;i++)
{
double dist = matches2[i].distance;
if(max_dist<dist) max_dist = dist;
if(min_dist>dist) min_dist = dist;
}
vector< DMatch> good_matches;
for (int i=0;i<descriptor_1.rows;i++)
{
if( matches2[i].distance<2*min_dist)
good_matches.push_back(matches2[i]);
}
// Draw Good Matches
Mat img_goodmatches;
drawMatches(img_1,keypoints_1,img_2,keypoints_2,good_matches,img_goodmatches,Scalar::all(-1),Scalar::all(-1),vector<char>(),DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);
vector<Point2f> obj;
vector<Point2f> scene;
for( int i = 0; i < good_matches.size(); i++ )
{
obj.push_back(keypoints_1[good_matches[i].queryIdx].pt);
scene.push_back(keypoints_2[good_matches[i].trainIdx].pt);
}
Mat H = findHomography( obj,scene,CV_RANSAC);
vector<Point2f> obj_corners(4);
obj_corners[0] = cvPoint(0,0);
obj_corners[1] = cvPoint(img_1.cols,0);
obj_corners[2] = cvPoint(img_1.cols,img_1.rows);
obj_corners[3] = cvPoint(0,img_1.rows);
std::vector<Point2f> scene_corners(4);
Mat img_object = img_1.clone();
perspectiveTransform( obj_corners, scene_corners, H);
Mat img_matches = img_goodmatches;
//-- Draw lines between the corners (the mapped object in the scene - image_2 )
line( img_matches, scene_corners[0] + Point2f( img_object.cols, 0), scene_corners[1] + Point2f( img_object.cols, 0), Scalar(0, 255, 0), 4 );
line( img_matches, scene_corners[1] + Point2f( img_object.cols, 0), scene_corners[2] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[2] + Point2f( img_object.cols, 0), scene_corners[3] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[3] + Point2f( img_object.cols, 0), scene_corners[0] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
//-- Show detected matches
imshow( "Good Matches & Object detection", img_matches );
if(waitKey(1) == 27) break;
}
waitKey(0);
return 0;
}
view raw gistfile1.cpp hosted with ❤ by GitHub

OpenCV: SURF Feature matching

  1. Load two images
  2. do SURF feature extraction
  3. Using Flann matching to match the keypoints
  4. Identify good matches
  5. find the object in the scene image

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "opencv2\opencv.hpp"
#include <opencv2\nonfree\features2d.hpp>
using namespace std;
using namespace cv;
int main()
{
Mat img_1, img_2;
//image = imread("lena.jpg",1);
img_1= imread("Matrix1_small.jpg", CV_LOAD_IMAGE_GRAYSCALE );
img_2= imread("RoboticsMatrix.jpg", CV_LOAD_IMAGE_GRAYSCALE );
if(img_1.empty()||img_2.empty())
{
cout << "Could not open or find the image" << std::endl ;
return -1;
}
/// Resize
resize(img_1,img_1,Size(0,0),0.15,0.15,INTER_LINEAR);
resize(img_2,img_2,Size(0,0),0.2,0.2,INTER_LINEAR);
imshow("Image 1", img_1);
imshow("Image 2", img_2);
// Step -1, Detect keypoints using SURF detector
int minHessian = 400;
SurfFeatureDetector detector(minHessian);
vector<KeyPoint> keypoints_1, keypoints_2;
detector.detect(img_1, keypoints_1);
detector.detect(img_2, keypoints_2);
Mat img_keypoints_1;
drawKeypoints( img_1, keypoints_1, img_keypoints_1, Scalar::all(-1), DrawMatchesFlags::DEFAULT );
imshow("Image1 KeyPoints", img_keypoints_1);
//imwrite("Lena Keypoints.jpg",img_keypoints_1);
// Step -2, Calculate descriptors (feature vector)
SurfDescriptorExtractor extractor;
Mat descriptor_1, descriptor_2;
extractor.compute(img_1,keypoints_1,descriptor_1);
extractor.compute(img_2,keypoints_2,descriptor_2);
//step - 3, Matching descriptor vectors with a brute force mathcher
double t = (double)getTickCount();
BFMatcher matcher(NORM_L2);
vector<DMatch> matches;
matcher.match(descriptor_1, descriptor_2,matches);
t = ((double)getTickCount() - t)/getTickFrequency();
cout << " Brute Force Matching Time (senconds): " << t<<endl;
// maches with Flann Based Matching.
t = (double)getTickCount();
FlannBasedMatcher matcher2;
vector<DMatch> matches2;
matcher2.match(descriptor_1,descriptor_2,matches2);
t = ((double)getTickCount() - t)/getTickFrequency();
cout << " Flann Based Matching Time (senconds): " << t<<endl;
//--Draw Matches
Mat img_matches;
drawMatches(img_1,keypoints_1,img_2,keypoints_2,matches,img_matches);
//-- Show Detected Matches
imshow("Matches Brute",img_matches);
//--Draw Matches
Mat img_matches2;
drawMatches(img_1,keypoints_1,img_2,keypoints_2,matches2,img_matches2);
//-- Show Detected Matches
imshow("Matches Flann",img_matches2);
// quick calcualation of max and min distances between keypoints
double max_dist=0; double min_dist = 100;
for (int i =0; i < descriptor_1.rows;i++)
{
double dist = matches2[i].distance;
if(max_dist<dist) max_dist = dist;
if(min_dist>dist) min_dist = dist;
}
vector< DMatch> good_matches;
for (int i=0;i<descriptor_1.rows;i++)
{
if( matches2[i].distance<3*min_dist)
good_matches.push_back(matches2[i]);
}
// Draw Good Matches
Mat img_goodmatches;
drawMatches(img_1,keypoints_1,img_2,keypoints_2,good_matches,img_goodmatches,Scalar::all(-1),Scalar::all(-1),vector<char>(),DrawMatchesFlags::NOT_DRAW_SINGLE_POINTS);
imshow( "Good Matches", img_goodmatches );
for( int i = 0; i < good_matches.size(); i++ )
{
printf( "-- Good Match [%d] Keypoint 1: %d -- Keypoint 2: %d \n", i, good_matches[i].queryIdx, good_matches[i].trainIdx );
}
// Localize the object
vector<Point2f> obj;
vector<Point2f> scene;
for( int i = 0; i < good_matches.size(); i++ )
{
obj.push_back(keypoints_1[good_matches[i].queryIdx].pt);
scene.push_back(keypoints_2[good_matches[i].trainIdx].pt);
}
Mat H = findHomography( obj,scene,CV_RANSAC);
vector<Point2f> obj_corners(4);
obj_corners[0] = cvPoint(0,0);
obj_corners[1] = cvPoint(img_1.cols,0);
obj_corners[2] = cvPoint(img_1.cols,img_1.rows);
obj_corners[3] = cvPoint(0,img_1.rows);
std::vector<Point2f> scene_corners(4);
Mat img_object = img_1.clone();
perspectiveTransform( obj_corners, scene_corners, H);
img_matches = img_goodmatches;
//-- Draw lines between the corners (the mapped object in the scene - image_2 )
line( img_matches, scene_corners[0] + Point2f( img_object.cols, 0), scene_corners[1] + Point2f( img_object.cols, 0), Scalar(0, 255, 0), 4 );
line( img_matches, scene_corners[1] + Point2f( img_object.cols, 0), scene_corners[2] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[2] + Point2f( img_object.cols, 0), scene_corners[3] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
line( img_matches, scene_corners[3] + Point2f( img_object.cols, 0), scene_corners[0] + Point2f( img_object.cols, 0), Scalar( 0, 255, 0), 4 );
//-- Show detected matches
imshow( "Good Matches & Object detection", img_matches );
// imwrite("Lena SURF Matches.jpg",img_matches);
waitKey(0);
return 0;
}
view raw gistfile1.cpp hosted with ❤ by GitHub

Wednesday, May 1, 2013

OpenCV: SURF Feature extractor

Main steps:
  1. Read Two Images
  2. Resize to half of its size
  3. Detectect Keypoints  using SURF
  4. Calculate Feature Descriptor
  5. Matching Descriptor using Brute Force Matcher
Original Image
 SURF Keypoints
SURF Matches
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include "opencv2\opencv.hpp"
#include <opencv2\nonfree\features2d.hpp>
using namespace std;
using namespace cv;
int main()
{
Mat img_1, img_2;
img_1= imread("lena.jpg", CV_LOAD_IMAGE_GRAYSCALE );
img_2= imread("lena.jpg", CV_LOAD_IMAGE_GRAYSCALE );
if(img_1.empty()||img_2.empty())
{
cout << "Could not open or find the image" << std::endl ;
return -1;
}
/// Resize
resize(img_1,img_1,Size(0,0),0.5,0.5,INTER_LINEAR);
resize(img_2,img_2,Size(0,0),0.5,0.5,INTER_LINEAR);
imshow("Image 1", img_1);
imshow("Image 2", img_2);
// Step -1, Detect keypoints using SURF detector
int minHessian = 400;
SurfFeatureDetector detector(minHessian);
vector<KeyPoint> keypoints_1, keypoints_2;
detector.detect(img_1, keypoints_1);
detector.detect(img_2, keypoints_2);
// Step -2, Calculate descriptors (feature vector)
SurfDescriptorExtractor extractor;
Mat descriptor_1, descriptor_2;
extractor.compute(img_1,keypoints_1,descriptor_1);
extractor.compute(img_2,keypoints_2,descriptor_2);
//step - 3, Matching descriptor vectors with a brute force mathcher
BFMatcher matcher(NORM_L2);
vector<DMatch> matches;
matcher.match(descriptor_1, descriptor_2,matches);
//--Draw Matches
Mat img_matches;
drawMatches(img_1,keypoints_1,img_2,keypoints_2,matches,img_matches);
//-- Show Detected Matches
imshow("Matches",img_matches);
waitKey(0);
return 0;
}
view raw gistfile1.cpp hosted with ❤ by GitHub