In video compression, progressive coding plays an important role in terms of coding efficiency and error resilience and has been an attractive research topic since the standardization of H.264/AVC. In this paper, we propose a high-performance progressive coding scheme with the help of bi-level images. Different from progressive H.264/AVC and other video standards, we construct image epitomes as coding priors and use them to generate predictions of intra blocks at the encoder. In addition, we reduce the loss during coding and transmit the compressed images to the decoder. We perform compression-oriented video bi-level image analysis and search for the best bi-level images by using the expectation maximization algorithm. The resulting image bi-level for a video sequence can be viewed as the base layer in spatially scalable video coding. Experiments show that our proposed progressive scheme improves the state of the art by an average of 0.53 dB in PSNR. Simulations under a packet loss environment also demonstrate that intra refresh with bi-level images outperforms random intra refresh by up to 2 dB, leading to better subjective quality.