Disclosed are a moving-picture compression encoding apparatus comprising a motion-compensated predicting unit that includes a first cost calculator for generating cost values based upon difference information indicative of differences between prediction signals generated by a prediction signal generator and a moving-picture signal input to the moving-picture compression encoding apparatus; a preliminary selector for preliminarily selecting a plurality of blocks based upon the cost values and outputting the blocks to a second cost calculator; the second cost calculator for generating new cost values by applying a frequency conversion to the difference information regarding the block sizes that have been output from the preliminary selector; and a block size selector for selecting an optimum block size based upon the cost values resulting from the frequency conversion.