A video data compression apparatus with which compressed video data of suitable amounts of data can be produced and the time required for processing is short. The apparatus approximates a real difficulty data Dj indicating the difficulty of the pattern of each picture by the ME residual, flatness, and intra AC and further calculates the target amount of data Tj of the compressed video data from the approximated real difficulty data Dj. An encoder performs compression and coding so that the amount of data of the compressed video data becomes substantially the target amount of data Tj.