In this paper, we propose a novel dictionary based video coding technique with adaptive construction of overcomplete dictionaries and advanced coding methods tailored to sparse signal representations. A set of dictionaries is trained off-line using inter or intra predicted residual samples and is applied for encoding. New coding tools are developed so that the encoder can more compactly represent the residual signal. The same set of dictionary elements can be reused for neighboring blocks, and the optimal number of dictionary elements can be decided using rate-distortion optimization. Experimental results demonstrate that the proposed algorithm yields both improved coding performance and improved perceptual quality at low bit rates.