Robust Model Fitting Based On Graph Clustering

Robust model fitting is a fundamental and critical research topic in computer vision.The task of robust model fitting aims to extract the parametric models from multistructure data contaminated with outliers and noises.It has widespread applications,such as image registration,3D reconstruction and motion segmentation.During the past few decades,a lot of robust model fitting methods have been proposed to deal with the main challenge,which is to simultaneously estimate both the number and the parameters of model instances in data.However,current model fitting methods are still far from being satisfactory in real-world applications due to the limitations of fitting accuracy and computational speed.To overcome the aforementioned problems,this thesis aims to research graph based robust model fitting methods,which mainly include graph construction,graph reduction and graph clustering.To this end,two graph clustering based robust model fitting methods are proposed to address the multi-structure model fitting problem.The main works and contributions of this thesis are as follows:(1)A simple iterative clustering on graphs based model fitting method is proposed.Most data point clustering based model fitting methods are usually time-consuming when input data include more data points.Moreover,they usually can not deal with the intersection of inliers effectively.Therefore,the proposed fitting method clusters model hypotheses to deal with the multi-structure model fitting problem.Specifically,the proposed fitting method starts from graph construction,where each vertex denotes a model hypothesis and each edge represents the similarity between two model hypotheses.The similarity is computed by the preference of the data points to the generated model hypotheses.Then,a simple iterative clustering algorithm is developed,which adapts the k-medoids clustering algorithm,to intuitively and efficiently estimate model instances in data.In order to speed up,the proposed simple iterative clustering algorithm only considers the vertices within a limited region around each cluster center.However,the proposed clustering algorithm is easy to trap in the local optimum.To solve this problem,two strategies are developed to improve the performance of the clustering algorithm,i.e.,conditional initialization of cluster centers and several conditional initial proposals.The proposed fitting method is able to effectively fit and segment multiple-structure data contaminated with a large number of outliers and noises.Experimental results show that the proposed method achieves superior fitting results over several state-of-the-art model fitting methods on both synthetic data and real images.(2)A co-clustering on bipartite graphs based model fitting method is proposed.Recently,the graph based methods have been widely applied to model fitting.However,these methods are inevitable to lose some useful information when they map data points or model hypotheses to the graph domain.The proposed method first employs a bipartite graph to express the relationships between data points and model hypotheses.Then,a bipartite graph reduction technique based on statistical testing is exploited to remove "insignificant" vertices on the graph.Moreover,the proposed method formulates the model fitting problem as a bipartite graph partitioning problem.Specifically,the proposed fitting method exploits a co-clustering algorithm to learn a structured optimal bipartite graph with exact connected components for graph partitioning.The model instances can directly be estimated from the structured bipartite graph without relying on any post-processing steps.Moreover,a model validation technique is employed to further improve the fitting results.The proposed method makes full use of the duality between data points and model hypotheses on a bipartite graph,leading to superior fitting performance.Experimental results on both synthetic data and real images show that the proposed method performs favourably against several state-of-the-art model fitting methods.