The nonlinear nature of many vision tasks involves analysis over nonlinear spaces embedded in higher dimensional Euclidean spaces. Such manifolds can be studied using the theory of differential geometry. Here we develop two algorithms which can be applied over manifolds. The nonlinear mean shift algorithm is a generalization of the popular mean shift, a feature space analysis method for vector spaces. Nonlinear mean shift can be applied to any Riemannian manifold and is provably convergent to the local maxima of an appropriate kernel density. This algorithm is used for motion segmentation with different motion models and for the filtering of complex image data. The projection based M-estimator is a robust regression algorithm which does not require a user supplied estimate of the level of noise corrupting the inliers. We build on the connections between kernel density estimation and M-estimators to develop data driven rules for scale estimation. The method can be generalized to handle heteroscedastic data and subspace estimation. The results of using pbM for affine motion estimation, fundamental matrix estimation and multibody factorization are presented.