Methods and apparatus for robust rigid and non-rigid motion tracking. An image, a next image, and a mask corresponding to an area in the image may be obtained. The area includes a plurality of points; each point indicates a location of the point in a position space and a color of the point in a color space. An iterative closest point algorithm may be applied that iteratively computes correspondences from a transformation and computes a new transformation from the correspondences. The algorithm tracks motion of the area in the image between the image and the next image. The algorithm matches points indicated by the mask to points in the next image in both position space and color space. An indication of an area in the next image that corresponds to the area in the image as tracked by the algorithm is generated.