Using Expectation Maximization (EM), also called Mean-Shift in the computer vision literature, I developed a decently working blob finder last night.
At Berkeley, I took a computer vision (CV) class with a horrible professor. He tried to have us learn from his home-made book and we didn't learn a darn thing from it. However, he did introduce the concept of "Expectation Maximization" to us. I was really interested in background subtraction and other CV tasks at the time, so I thought that it was really neat. However, I didn't have a chance to use it back then. (Because the class was so horrible)
But now I'm working on a blob tracker for my project and realized that EM was exactly the right concept for tracker initialization. So I crafted a EM code with settling and estimate pruning. It works pretty well with the occasional failure.
The code is here.
It's all python 2.7 code and requires numpy and matplotlib to run.
There are a couple concepts to note:
It uses the regular EM algorithm but I added the concepts of greedy maximization, settling, and estimate pruning to converge faster and reduce the number of iterations. The maximum number of iterations is 20.
Settling (main uses on lines 113-115, 125-128, and 184-185) causes the algorithm to ignore estimates which don't change much. They are still part of the pruning process (see below) but are not recalculated once they are determined to be settled.
Greedy maximization (on line 119) calculates the new radius estimate using the fixed RADIUS_SQ value instead of the previous radius estimate. In practice, this seemed to settle faster (in 8-9 iterations instead of all 20 iterations) and yield results almost as accurate as the exact result.
Estimate pruning (lines 149-179) is used to eliminate overlapping estimates. The idea is that if two estimates are within each other's radii (lines 159-169), then they are trying to estimate the same blob. Therefore, one of the estimates is eliminated. With the initialization (see below) using a large sample, this is important to reduce the runtime.
The algorithm is initialized by randomly choosing 10% of the input points as starting estimates and run through the EM algorithm. This number is then reduced to a few estimates in the pruning phase. After a couple of iterations, all of the estimates will have been settled and the algorithm is complete.
To test, a random number of blobs are generated with random parameters. Then numpy.random.standard_normal() is used to generate the points for each blob. Then the samples are randomly chosen using numpy.random.choice().
All of the points, the samples, the blobs and the estimates are graphed using matplotlib. An example is below:
Benjamin Schleimer
