Frames of a video data stream can be encoded using statistically-based spatially differentiated partitioning. Statistically-based spatially differentiated partitioning involves forming a difference frame between a current video frame and a temporally nearby video frame and then calculating the variance of the difference frame on a block-by-block basis. A histogram can be formed from the calculated variances and a threshold determined on the histogram. The determined threshold can be used to select parameters for the encoding process that will more efficiently encode static or slow-motion areas without a significant loss in resulting quality.