Hi,

you can use JPEG itself! Here is my code, but I make no efforts to optimize it thus it can be really slow. First of all, you need define RGB to YCbCr transform. I found very nice code here via Mr.Wizard (up to some small correction):
Inverse transform:Then it is necessary to define the Fourier discrete cosine transform.Please, notice the JPEG uses DCT in slightly different way than Wolfram Mathematica. Next step is to define the quntization tabels for all channels:The last step is the quntization itself:Now, we can start. Import an image and divide it into 8*8 blocks:
Then we need to choose the quality of the output.Notice that the quality should be large than 1 and quality=1 reduces the size of the output file by factor 1.8. Thus we put a really terrible quality. The next step is quantization of each channel:This part works really slow, hence please try to optimize it. The last step is to convert to RGB and save to disk:The size of the output file is 2.2 times smaler then initial one. The Mathematica file is attached to this post.

Hi Grisha, thank you for the code!
I think that it is worth to point out that Export to "JPG" uses lossy compression with "CompressionLevel" -> 0.25 by default. So just Importing and then Exporting the image I get 34% smaller JPG file. It would be very interesting to see the results of your compression algorithm without this additional lossy compression by Export. I have tried to Export with  "CompressionLevel" -> 0 but it gives a file which is larger than the original. It raises the question: it is possible in Mathematica to Import a JPG file as Image object and then re-create original file from this Image object (assuming that original file contains no EXIF information)?

Now I see that correct handling of JPG information is impossible in Mathematica without re-implementing of the built-in Importing and Exporting subroutines for JPG.

When saying "correct" I had in mind making incremental changings in a JPG file. For example, I wish to make a lossy compression for a part of a JPG image without loosing any information in another part. I know that it is theoretically possible only for blocks of pixels in the JPG file, but this possibility is very interesting.