У меня есть мысль разбить картинку на тайлы. Тайлы проанализировать на схожесть и реиспользовать тайлы которые похожи.
Векторное кодирование. Пробовал для однобитных (двухцветных) картинок, в принципе приемлемо. Сжатие с потерями, а дальше можно пробовать дожимать обычными упаковщиками.