An apparatus and method for coding block boundary detection using interpolated autocorrelation is disclosed. Input video frames are processed to obtain a binary map of possible block boundary pixels including original and rescaled block boundaries. The boundary pixel map is converted to a boundary histogram. Then interpolated autocorrelation is applied to the boundary histogram to detect the block size and block size offset. The interpolated autocorrelation handles both integer sizes and non-integer sizes. A confidence measure is also determined that reflects the accuracy of the detection result. The output for the current video frame is also post processed with information from previous frames to provide better temporal stability.