  Optimization-based 3D object tracking is known to be precise and fast, but
sensitive to large inter-frame displacements. In this paper we propose a fast
and effective non-local 3D tracking method. Based on the observation that
erroneous local minimum are mostly due to the out-of-plane rotation, we propose
a hybrid approach combining non-local and local optimizations for different
parameters, resulting in efficient non-local search in the 6D pose space. In
addition, a precomputed robust contour-based tracking method is proposed for
the pose optimization. By using long search lines with multiple candidate
correspondences, it can adapt to different frame displacements without the need
of coarse-to-fine search. After the pre-computation, pose updates can be
conducted very fast, enabling the non-local optimization to run in real time.
Our method outperforms all previous methods for both small and large
displacements. For large displacements, the accuracy is greatly improved
($81.7\% \;\text{v.s.}\; 19.4\%$). At the same time, real-time speed ($>$50fps)
can be achieved with only CPU. The source code is available at
\url{https://github.com/cvbubbles/nonlocal-3dtracking}.
