The authore of the depixelising algorithm actually also did something like that:

"Content-Adaptive Image Downscaling" http://johanneskopf.de/publications/downscaling/

I always thought it was sad that it didn't get as much attention. I think it could also interesting to use in thumbnail generation based on regular photos, for example.

Going to ask in that reddit thread if the author is already aware of this algorithm. Might be able to take some cool new ideas from it if they don't! :)