1. An image data compression apparatus, comprising: a compression circuit, for applying a plurality of compression approaches to a first block, and accordingly generating a plurality of first candidate compression results of the first block; a characteristic value extracting circuit, coupled to the compression circuit, for deriving a plurality of first characteristic values from the first candidate compression results, respectively; and a selecting circuit, coupled to the compression circuit and the characteristic value extracting circuit, for selecting a target compression result of the first block from the first candidate compression results according to the first characteristic values and at least one characteristic value threshold, wherein the compression circuit further applies the compression approaches to each of a plurality of second blocks preceding the first block, and accordingly generates a plurality of second candidate compression results of each of the second blocks, and the image data compression apparatus further comprises: a threshold predicting circuit, for determining the at least one characteristic value threshold according to the second candidate compression results of each of the second blocks.