Turns out PNG is very amendable to RDO optimization approaches, but few have really tried.
This is something I've been wanting to try for a while. This experiment only injects 3 pixel matches into the PNG Paeth (#4) predictor bytes. It uses an accurate Deflate bitprice model which is computed by first compressing the image to 24bpp PNG using predictor #4, then the 3 pixel matches are inserted.
Original PNG (oxipng): 16.06bpp