In the presence of false matches and moving objects, image registration is challenging, as outlier rejection, matching and registration become interdependent. In this paper, we present an efficient and robust method, 4D tensor voting, to estimate epipolar geometries for non-static scenes, and identify matching points due to salient and independent motions. Unlike other optimization techniques, data communication in 4D tensor voting does not involve any iterative search. Thus, initialization, local optimum, convergence, and dimensionality of parameter space are not problematic. Like the 8D counterpart, the only assumption we make is the pinhole camera model. Two advancements are made in this work. First, we reduce the dimensionality, and the 4D joint image space is an isotropic and orthogonal one, validating the general assumptions of tensor voting. This improvement is evidenced by the facts that only two passes are needed, and that 4D tensor voting can tolerate an even larger noise/signal ratio (up to a ratio of five). Second, instead of discarding motion pixels as outliers, we successively extract the epipolar geometries contributed by the static background and by the matching points due to salient motions. Only two frames are needed, and no simplifying assumption (such as affine camera model or homographic model between images) is made. Our 4D algorithm consists of two stages: local continuity constraint propagation to remove outliers, and global consistency checking to localize a 4D topological point cone. Results on challenging datasets are presented.