Target appearance change during tracking is always a challenging problem for visual object tracking. In this paper, we present a novel visual object tracking algorithm based on Structure Complexity Coefficients (SCC) in addressing the motion related appearance change problem fundamentally. Based on our careful analysis, we found that the motion related appearance change is quite related to the SCC of target surface, where the appearance of complex structural regions is easier to change comparing with that of smooth structural regions with target motion. With the proposed SCC, a SCC-GL distance is defined in addressing both the appearance change and occlusion related problems during tracking. Moreover, an Observation Dependent Hidden Markov Model (OD-HMM) framework is designed where the observation dependency between neighboring frames is considered comparing with the standard HMM based tracking framework. The observation dependency is computed with the proposed SCC. We also present a novel outlier removing method in appearance model updating to avoid error accumulation. Experimental results on various challenging video sequences demonstrate that the proposed observation dependent tracker (
) achieves better performance than existing related tracking algorithms.