В спецификациях методов сжатия PNG, JBIG2, JB2 и даже в JPEG-LS, WebP-lossless, PCIF/BCIF и прочих столько идей, аж глаза разбегаются...
Только проблема может быть в том, что распаковщик будет размером в пару десятков килобайт и отрабатывать одну картинку будет за пару минут.