A method of decoding a bitstream comprising a digital representation of a video includes decoding motion information for a current video block from the bitstream, estimating matching costs of the current video block using one or more templates based on a partial set of pixel locations in each of the one or more templates, where in the each of the one or more templates includes a video block with multiple samples and refining the motion information of the current video block using a template having a minimum matching cost.