DeveloperStation.ORG

Parameter Selection in Hidden Markov Models

2012-01-29T21:22:00.001-05:00

In this post, I discuss the criterion for selecting parameters of an Hidden Markov Model (HMM) for optimum training. If you still do not properly understand whats an HMM, please refer this article on HMMs. In order to classify data, one HMM is needed per class.

Assume that we want to have a Discrete HMM represented by λ( A, B, π). O be the set of observations and N to be number of states in a HMM and M be the number of unique symbols.

P(O|λ) = P = likelihood that an observation matches the given HMM model.

The following are some of the criteria in selecting parameters in Hidden Markov Models (taken from Bell System Journal):

Initial Estimates of A and B: We know that HMM classifier can be trained using Baum-Welch algorithm. For the given set of observations sequences (O1, O2, ......) in Baum-Welch algorithm, λ is re-estimated iteratively such that P is maximized. This depends on the initial parameters of HMM i.e. λ. Different values of A, B and π gives different likelihoods. Different values of λ give different results. There is no one right way to select initial estimates. Hence, they can be of any random values( however, the matrices A, B and π should sum to 1 along the rows).

HMM structure and number of states: Structure of an HMM has an effect on performance of the HMM. For example in speech recognition, a HMM which is modeled from left to right is preferred. There also is no need for a state to traverse to each and every state in the model. i.e. Few elements of A can be zero. If N is too large reliable determination of A and B can become hard. If N is large, also Viterbi Decoding becomes hard. There is also no right way to choose N as it need not be related to a "observable phenomenon" in the problem.

Multiple Observation sequences: Multiple observation sequences (from different training examples of same class) need to be used. Mixing training samples from different sources is a good idea.

Constraints on A, B matrices during training: The matrices A, B and π can take any values (if they follow the constraints such as along each row of a matrix sum of elements needs to be 1). Its found that a HMM where, a state can traverse to all the states is not so flexible. At the same time, a state transition should also not occur "within" the state or "only" to next state. Such restrictions might constrain the level to which the model can be trained. For example in speech models, the transition is usually from left to right, so the matrix elements are zero below the diagonal. If the matrix B is unconstrained and the data set for training is limited, it is likely that b_j(k)=0. There are some solutions for this problem in the journal.

Multiple estimates of A, B and averaging: It is known that different initial values of λ is likely to give different likelihoods for a testing set. So, different values of λ needs to implemented and averaged (average values of matrix elements of A, B and π). However, it was observed that results of the averaged model was not better than other best solutions computed. So, picking the model that has low memory constraint and gives good results should be picked.

Install Boost Libraries on Ubuntu

2012-01-20T20:33:00.001-05:00

I've heard a lot about Boost Libraries. They are well known in the programming community as one of the most well written, quite handy C++ libraries one can use. You can download them here.

For a quick install of Boost libraries on Ubuntu, use the following command:

To quickly learn about Boost Library, click here for free online accessible book.

Kmeans clustering in OpenCV with C++

2012-01-17T11:32:00.001-05:00

Kmeans clustering is one of the most widely used UnSupervised Learning Algorithms. If you are not sure what Kmeans is, refer this article. Also if you have heard about the term Vector Quantization, Kmeans is closely related to that (refer this article to know more about it). Autonlab has a great ppt on Kmeans Clustering.

First, I'll talk about the kmeans usage in OpenCV with C++ and then I'll explain it with a program. If you are not yet comfortable in OpenCV with C++, please refer to this article and the pretty much everything else is the same as in C API (where you use IplImage*,etc).

Btw, My other programs in OpenCV will be posted here.

Function call in C++ API of OpenCV accepts the input in following format:
double kmeans(const Mat& samples, int clusterCount, Mat& labels, TermCriteria termcrit, int attempts, int flags, Mat* centers);

Parameters explained as follows:

samples: It contains the data. Each row represents a Feature Vector. Each co lumn in a row represent a dimension. So, we can have multiple dimensions of data in the feature vector. Example if we have 50, 5 dimensional feature vector, we will have 50 rows, 5 colums of this matrix. One thing interesting which I've noticed is kmeans doesn't work with CV_64F type.
clusterCount: It should be specified beforehand. We need to know how many clusters do we divide the data into. It is an integer.
labels: It is an output Matrix. If we had a Matrix of above specified size (i.e 50 x 5 ), we will have 50 x 1 output Matrix. It determines which cluster the feature vector belongs. It starts with 0, 1, .... (number of clusters-1).
TermCriteria: It determines the criteria in applying the algorithm. Max iterations, accuracy,etc.
attempts: number of attempts made with different initial labelling. Also refer documentation for elaborate information on this parameter.
flags: It can be
KMEANS_RANDOM_CENTERS (for random initialization of cluster centers).
KMEANS_PP_CENTERS (for kmeans++ version of initializing cluster centers)
KMEANS_USE_INITIAL_LABELS (for user defined initialization).
centers: Matrix holding center of each cluster. If we divide the 50 x 5 feature vector into 2 clusters, we will have 2 centers of each in 5 dimensions.

Sample program is explained as follows:

Access Pixels in C++ using OpenCV

2012-01-13T15:56:00.001-05:00

I'm writing this blog post since, I've seen many people while moving from C API to C++ API have faced a lot of confusion in understanding it.

This post explains on how to use cv::Mat datatype in accessing pixels of a Image or elements of a Matrix. An example of cv::Mat_ is also shown.

Btw, My other programs in OpenCV will be posted here.

Many people still write code using IplImage* or CvMat* datatype. The sight of pointers scare a lot of people (except for some). With moving to C++ API, one can make use of C++ references which are more easier to understand and also one can use Object Oriented Programming techniques to bring in more easier to write code and flexibity in programming.

Moving to C++ API hasn't been that tough for me but, it definitely took a while. Now, my code looks more cleaner that before. I recommend everyone to move to C++ API using the cv::Mat type.

Sometimes, when you don't want to deal with the return type of the Matrix while accessing the elements (i.e. without the use of ".at" operator), you can use cv::Mat_ (which is a template sub class of cv::Mat).

Taking care of the data-type of Matrix elements is really important. I didn't care much about it while using the C API. But C++ API makes you more aware of the data-type of elements of the Matrix. This is for good as it encourages efficient usage of memory.

To use C++ API, you need the following headers and namespace.

Fore more faster ways of accessing pixels, refer OpenCV documentation.

The following code is used to:

Declare.
Assign.
Print or Access

values of pixels in Images or elements in Matrices of cv::Mat type in OpenCV:

Declaring Matrices: You have to know the data-type of elements of the Matrix before accessing or printing them.

For assigning values: For printing values (same as above):

Installing GHMM

2012-01-12T11:45:00.004-05:00

There seems to be some dependency issues while installing GHMM in Linux (Ubuntu). The following script installs GHMM (A HMM lib written in C with a python wrapper and a GUI).

I running Ubuntu 10.04 LTS.

Use of Lambda, Map, Reduce and Filter in Python

2011-12-14T08:53:00.001-05:00

I have heard a lot about Lambda on Python.

I was scared in the beginning as I thought the code was very cryptic until very recently explored what it is all about.

Lambda is a anonymous function that one can write for quick operations instead of formally writing a function using def.

It can be used in conjunction with other functionality like Map, Reduce, Filter in Python.

Examples of Lambda are given below.

Map, Reduce and Filter functions in Python make writing code much more easier (less lines of code) and I think they are optimized internally which will make them more faster than writing custom code which will most probably be sub-optimal in terms of performance.

Here is a example of Matrix Multiplication (along with other optimizations) making use of Map along with some.

Now lets see what Map, Reduce, Filter is and how Lambda can be used with them.

Map functionality in Python i.e. with Syntax map(function, sequence) takes a sequence of values and passes it to function and returns a list of items.
Filter functionality in Python i.e. with Syntax filter(function, sequence) takes a sequence of values and passes it to function and returns a list of items for which function(item) is true.
Reduce functionality in Python i.e. with Syntax reduce(function, sequence) takes first 2 items in sequence, processes them and takes result, next item and so on.

KMeans and Vector Quantization

2011-12-11T11:55:00.001-05:00

KMeans clustering is a type of Vector Quantization ("Since vector quantization is a natural application for k-means, information theory terminology is often used."[1] ).

From Machine Learning perspective, feature vectors can be considered as code-word and the table mapping code-word to cluster ids is a codebook.

Each feature vector to be clustered is considered as a code-word and in KMeans clustering, they are assigned to the closest centroid (cluster id).

Pages describing Vector Quantization - KMeans:

Interesting talk on Robotics and Artificial Intelligence

2011-12-08T17:49:00.001-05:00

This is an interesting talk by Dr. Andrew Ng at Stanford University on Future of Robotics and Artificial Intelligence. He talks about present problems in Robotics and Artificial Intelligence.

Action Recognition Survey

2011-11-26T20:17:00.001-05:00

The paper titled "Machine Recognition of Human Activities: A survey" is an interesting Journal Paper I've read recently.

It basically talks about the recent advances, open research problems, future directions of research in Action Recognition and different techniques employed to do Action Recognition.

Image Overlap in Android OpenCV

2011-11-25T00:08:00.001-05:00

Its been recently that I have been playing around with OpenCV on Android.

Btw, My other programs in OpenCV will be posted here.

Basically, I've written a program that overlaps two images. One image exists in the "res" folder in android project and other image is the Image coming from the camera.

Image coming from the camera is available in array of bytes. We convert it into a Bitmap, then into a "Mat". The other image is read as a "Mat" directly using Utils.loadResource method.

Now since both images are in Mat format, I use Mat.getNativeObjAddr() method from android-opencv project to pass the image to JNI code. This is more useful as we can reconstruct cv::Mat in JNI code more easily than passing bytes (lookup samples from android-opencv project) and reconstructing them.

Also, one thing to take care in number of channels in the images/Mat being processed. We need to make sure that all the images being operated on should be of same number of channels. During this process, you might have to convert RGB to Gray or RGB to RGBA, etc.

In the sample program, I've written a code to send RGBA image, RGB image to JNI (OpenCV C++) code and then convert RGB image to RGBA using cvtColor function. Then do a "addweighted" function call on the 2 images and return it to Java code.

I got the following image on my App where I performed merging of two images:

Using C++ (JNI) and Java in combination is more effective as there is more flexibility you can enjoy on Java(Android) and let the complex image processing stuff be done in C++ (faster way).

If you are looking for the program to merge images in OpenCV, take a look at this program. Use the link and the above mentioned tips to create Image Overlapping program for yourself on Android.

Hidden Markov Models for Dummies

2011-11-20T12:10:00.001-05:00

This article is a great collection of the best resources available on the web which explain Hidden Markov Models and their applications.

I think there is never a "best place" to learn all the points of a new concept/idea. But, you need to go through a lot of sources (books, webpages, jounals, etc) to understand something.

If you are done with learning what HMMs can do, you can checkout this post which discusses about selecting optimal parameters for training of a HMM classifier.

Here is a really good explanation of what HMMs are all about. You need some background (Bayesian Networks) with Probability though. The above website Autonlab (from Carnegie Mellon University) has really good explanation/slides for Data Mining, Machine Learning, Pattern Recognition which is helpful to Math, Statistics, Computer Science researchers.
Here is another link (from University of Otago, they make really good tutorials which start from basics) that explains HMMs with basics of Probability and Naive C/C++ implementation.
Here is another link from UC-Berkley which explains Hidden Markov Models (in Practical Machine Learning class). This one clearly states learning, testing/classification without much deep explanation (on how they came up with the equations) and with quick formulae to start with. This is very much unlike other tutorials on the web which seemed to me confusing.
Another tutorial here (Utah State University) describes HMM and also talks about issues in implementing HMM (floating point underflow problem).
Matlab documentation website does a good job in explaining Hidden Markov Models in a basic manner along with the code (to use this code, you need "Statistics" toolbox in Matlab).
This article (University of Cambridge) compares Hidden Markov Models with Dynamic Bayesian Networks. Also covers other stuff on Computer Vision applications using these Stochastic Models.
Most referred tutorial in writing other tutorials is "A tutorial on Hidden Markov Models and selected applications in speech recognition".

Here are set of videos on Youtube that explain Hidden Markov Models in a more mathematical way! Other videos from that guy have excellent Machine Learning examples explained very mathematically and clearly!

There are 3 problems to solve in Hidden Markov Model namely, State Estimation, Decoding or Most Probable Path (MPP) and Training/Learning HMM.

The above 3 problems are solved using the following techniques:

State Estimation: Forward-Backward technique is used for State Estimation (what will be the next state, given set of observations). This step is also known as Classification. This can be used in testing the classifier built.
Decoding or Most Probable Path: Viterbi Decoding technique is used for estimating Most Probable Path (given a set of observations, what is the most probable path that is taken that best explains the observations). This step is also known as Decoding. This can be used in Testing the classifier built.
Training/Learning HMM: Baum-Welch (Expectation Maximization) technique is used for Learning HMM. If we are given a set of observations, we can predict the maximum likelihood HMM that may have produced the observations (adjust the HMM model that fits the data). This is also known as Training.

For Computer Vision guys, these slides explains how to apply it to action recognition.

Once you are comfortable with basics of HMM, you might want to look into this paper. Here authors describe on how to select initial parameters of HMM.

A background in Statisctical Pattern Recognition, Stochastics will definitely help in understanding Hidden Markov Models. Hidden Markov Models are widely used in Speech Recognition, Computer Vision (Gesture Recognition and Action Recognition).

There are 3rd party libraries available on the web for use in your project. Also, there is a Matlab toolkit available.

Move to the Cloud

2011-11-16T20:35:00.001-05:00

This is an interesting article and video from UC Berkley, concerning Cloud Computing. It discusses about the need for Cloud for building Scalable Services, opportunities for Startups, advantages of Cloud, concerns about Cloud Computing!

It also talks about present concerns about Cloud Computing, possible solutions. Its basically the way UC Berkley would want to see the Cloud Services evolve.

Possibilities with Array Cameras

2011-11-09T07:53:00.000-05:00

This is a interesting video on usage of Array Cameras to avoid Occlusions. Array Cameras are a set of Cameras whose Images are Co-Planar .There are a lot of possibilities with usage of Array Cameras in Surveillance, Occlusion Avoidance.

The link for this research paper from UCSD is here.

Apple's Siri and Android's Voice Control

2011-11-02T10:43:00.002-04:00

Its been a while since Apple's iPhone 4S was released and everyone going GAGA over Siri. It seems very funny looking over claims of Apple fanboi's to be able to talk to their phones and it replying it back. That feature has been in Android for almost an year.

However, Siri is absolutely amazing.. Apple has once again shown us that better implementation always attracts positive attention.

Presently, Android's voice feature is not as extensive as of Siri. For example, I can say "weather in Morgantown" in Android and it will give me a weather prediction on a Google search page. Siri will give me the weather directly by speaking to me (which is really cool).

We need to specify the input properly in Android. For example I can't say "drive to Pittsburgh" in Android (this opens up searching "drive to pittsburgh" in google search) rather, I would have to say "Navigate to Pittsburgh" which is not so natural (to me).

However, translate feature is awesome on Android.

Android 4.0 features updated text to speech feature, making the API more cleaner. I think this move will encourage more developers to bring in more apps to Android market. Previously, I believe developers would have to write it in C++ (unofficial API), now there is no need for that.

No matter, Siri is a great feature but I'm a little skeptical over its success as its not a natural interface to talk to phone. Google voice search, and voice dialer are great features on Android which were present since the days of Gingerbread. But, I see very few people talking about it or using it extensively.

Andy Rubin also claims the same. They want to wait and see how the public reception of this feature will be.

But on the other hand, maybe Apple did the right thing by giving voice control in iPhone 4S a name ("Siri") and calling it an personal assistant or it is an marketing tactic made by Apple.

I guess its time for Google to make the same move.

Object tracking survey

2011-10-31T11:50:00.001-04:00

This is an old Journal Paper I've read (long time back) on Object Tracking during Literature reivew: "Object Tracking: A Survey"

This has a gist of almost all object tracking methods used till 2006.

Kinect Depth and Real-world distance

2011-10-29T20:23:00.000-04:00

Here is an interesting link where the author compares real world distance with the distance measured with Kinect.

My friend and colleague Sriram, is also working in a similar area. I think we can expect important posts regarding that on http://worldofcameras.wordpress.com/

Image Overlap in C++

2011-10-14T09:40:00.000-04:00

In this post we see on how to do Image Overlay/Overlap in C++. It is very simple in OpenCV with the use of addweighted function.

Btw, My other programs in OpenCV will be posted here.

Checkout the program:

Output:

I actually looked at this reference, but realized there is a simpler way to it later instead of playing around with Pixels. So, I'm putting up this post.

Science and Computer Simulation

2011-10-05T15:43:00.001-04:00

Here is an interesting link which tries to describe analogy between Science/Scientific Experiments and Computer Simulation/Programming.

An Introduction to Computer Simulation Methods: Amazon Book
Sample Chapters.
Scientific Programming in Java.

I'm glad, someone author wrote it in form of a book (first.

Interesting Papers in Distributed Camera Networks

2011-10-04T21:07:00.000-04:00

I have read these papers published in the field Camera Networks recently (which I found interesting):

Distributed Coordination for Fast Iterative Optimization in Wireless Sensor/Actuator Networks: Proposed algorithm talks about how wireless sensors come to consensus on an issue in a Fast manner. How does this compare to other methods. (optimzation problem).
Distributed Multi-Target Tracking In A Self-Configuring Camera Network: Talks about a modified Distributed Kalman filter that is used for tracking in Smart Cameras.
Programming Support for Distributed Optimization and Control in Cyber-Physical Systems: Talks about issues regarding programming support for distributed shared memory architecture.
Scalable Target Coverage in Smart Camera Networks: With only Pan changing in a PTZ camera, talks about Camera Coverage problem (which is an optimization problem). Talks about impact of proposed algorithm with changes in density of sensors/cameras, number of targets, etc.

Interesting talk

2011-09-19T06:13:00.000-04:00

Color spaces in Vision

2011-09-05T09:58:00.000-04:00

Here is an interesting article that talks about the pros and cons of using a specific color space for http://chipsight.com/color-space-for-embedded-vision/

It talks about YCrCb, Lab, RGB, Normalized RGB,YUV, HSV, other color spaces and their pros and cons with respect to each other.

Kalman Filter for Dummies

2011-09-01T21:05:00.001-04:00

I've been reading about Kalman filter and its application in Tracking.

For those who are finding Kalman Filter tutorials, even the wikipedia page for Kalman Filter highly confusing might just find these links comparatively easy to understand.

These tutorials help to understand the basic idea of Kalman Filter, why it is applied in Vision problems, etc:

Kalman Filter for dummies
Introduction to Kalman Filter (includes basic probability concepts, etc).
A Study of the Kalman Filter applied to Visual Tracking.

OpenCV performance tests

2011-08-17T02:32:00.000-04:00

This is a good article comparing the performance of common tasks on different versions of OpenCV. Newer version doesn't necessarily mean that it is better in performance.

Here is another link that talks about comparison of OpenCV with other programming frameworks.

A Simple Read/Write Example using Cassandra and Java

2011-08-14T18:58:00.003-04:00

In this post, we take a look at basic CRUD (Create Read Update Delete) operations on Cassandra database using Java JDBC.

We only use Eclipse IDE. This example was tested in Windows 7 Operating System.

To find out more about NoSQL databases, look here.

Cassandra is an open source distributed database management system developed by Apache Software Foundation. It was designed to handle very large amounts of data spread out across many commodity servers while providing a highly available service with no single point of failure.
Popular user of Cassandra is Facebook

To find out more on Cassandra, refer its home site here.

Download and Install Cassandra from here.
Extract the files.
Setup the following Environment Variables.

JAVA_HOME (Give the link to the jre folder where java is installed)
CASSANDRA_HOME (Give the link to the cassandra folder where the files are extracted)

Go to the location where you extracted and then into the "~/apache-cassandra-0.6.6/bin" folder and open 'cassandra-cli.bat' file using any text editor
Replace Line 21 "if NOT DEFINED CASSANDRA_HOME set CASSANDRA_HOME=%CD%" with "if NOT DEFINED CASSANDRA_HOME set CASSANDRA_HOME=%~dp0.."
Now save the file after editing the line.
Now open the command prompt and goto "~/apache-cassandra-0.6.6/bin>" folder and type the following command '.\cassandra.bat'. This starts the server.
Now open another command prompt and goto "~/apache-cassandra-0.6.6/bin>" folder and run '.\cassandra-cli.bat'. This is the UI for the database
Connect to the server by typing the command 'connect localhost/9160'.
Here, type "Create Column Family AuthCollection ;" This creates a column family (i.e., table)
There are certain jar files needed which are available in the Project Dump which is available for download below. It is present in the folder titled 'JarFiles' in the Project Directory.
Be sure to add these jar files to the class path.

The code which performs all the CRUD operations is as follows.

The screen shot of the output is as follows:

This code is available for download along with the entire project directory here.

OpenCV ROS tutorial

2011-08-03T15:17:00.003-04:00

I recently realized that OpenCV tutorials at ROS website is more useful than any others available out there.

Btw, My other programs in OpenCV will be posted here.

You can download it and other related stuff (cheatsheet, etc) at