Sparse Motion Analysis

Motion segmentation is an essential pre-processing task in many computer vision problems. In this dissertation, the motion segmentation problem is studied and analyzed. At first, we establish a framework for the accurate evaluation of the motion field produced by different algorithms. Based on the framework, we introduce a feature tracking algorithm based on RankBoost which automatically prunes bad trajectories. The algorithm is observed to outperform many feature trackers using different measures. Second, we develop three different motion segmentation algorithms. The first algorithm is based on spectral clustering. The affinity matrix is built from the angular information between different trajectories. We also propose a metric to select the best dimension of the lower dimensional space onto which the trajectories are projected. The second algorithm is based on learning. Using training examples, it obtains a ranking function to evaluate and compare a number of motion segmentations generated by different algorithms and pick the best one. The third algorithm is based on energy minimization using the Swendsen-Wang cut algorithm and the simulated annealing. It has a time complexity of $O(N^2)$, comparing to at least $O(N^3)$ for the spectral clustering based algorithms; also it could take generic forms of energy functions. We evaluate all three algorithms as well as several other state-of-the several other state-of-the-art methods on a standard benchmark and show competitive performance.