An open challenge to the widespread deployment of mobile robots in the real-world is the ability to operate autonomously in dynamic environments. Such autonomous operation requires full utilization of the relevant sensory inputs to adapt to environmental changes. Despite being a rich source of information, vision is however, still under-utilized in robot domains because of the sensitivity to environmental changes and the computational complexity of visual input processing algorithms. This paper enables a mobile robot to better utilize the visual input to navigate safely in dynamic environments – it describes a novel algorithm that: (a) uses local image gradient cues to characterize target objects reliably and efficiently; and (b) uses temporal correspondence of visual cues for robust localization and tracking of environmental obstacles. Furthermore, the information extracted from these visual cues is merged effectively with information obtained from other visual cues and range sensors, using autonomously learned error models of the different information processing schemes. All algorithms are fully implemented and tested on a humanoid robot in dynamic indoor environments.