In this paper a new sign coding approximation method for the wavelet coefficients in a 2D image codec based on a simulated annealing metaheuristic is presented. The efficiency of the proposed algorithm versus a genetic algorithm using benchmarks of Kodak is compared and showing that the proposed sign prediction algorithm is efficient and provides a significant reduction of wavelet coefficients sign information in the final bit-stream. The results show that, by including sign coding capabilities to a nonembedded encoder, the sign compression gain is up to 17.35%, being the rate-distortion (R/D) performance improvement up to 0.25 dB.