I need to work with a good amount of 4-bit images. However, it's got to be for J2ME devices, which means great lack of memory. So, could you propose a compression algorithm that could decompress on the fly relatively fast and still have some reasonable degree of compression?
It depends on the nature of your images. Simple run length encoding (RLE) might be enough and it's trivial to implement and very fast.