He estado jugando un poco con Android Bitmaps y descubrí que la compresión PNG lleva mucho más tiempo que incluso el JPEG de mayor calidad. Mucho mucho mas. En mi dispositivo puede ser aproximadamente de 10 segundos contra 1.

AFAIK, PNG es básicamente cadenas de píxeles filtradas comprimidas con desinflado. Bueno, encontrar el mejor filtro para cada cadena puede llevar mucho tiempo, pero puede haber un compromiso establecido entre la velocidad y la efectividad de la compresión. No debería ser más lento que JPEG. ¿Cómo es eso?

Tal vez sea al revés. ¿Hay alguna implementación ultra rápida de JPEG en Android?

ACTUALIZACIÓN: Realmente solo hago cosas como

mBitmap.compress(CompressFormat.JPEG, 100, stream);

y

mBitmap.compress(CompressFormat.PNG, 100, stream);