Early detection of fires is an important aspect of public safety. In the past decades, devices and systems have been developed for volumetric sensing of fires using non-conventional techniques, such as, computer vision based methods and pyro-electric infrared sensors. These systems pose an alternative for more commonly used point detectors, which suffer from transport delay in large and open areas. The ubiquity of computing and recent developments on novel hardware alternatives, like memristor crossbar arrays, promise an increase in the number of deployments of such systems. Existing video-based methods have been developed for the analysis of uncompressed spatio-temporal sequences. In order to respond the growing demand of such systems, techniques specifically aimed at analyzing compressed domain video streams should be developed for early fire detection purposes. In this paper, a Markov model and wavelet transform based technique is proposed to further improve the current state-of-the-art methods for video smoke detection by detecting signs of smoke existence in the MJPEG2000 compressed video.