The thing is, there's no "right format" for sprites, as they're used in the game. See http://benfry.com/deconstructulator/ for an example of how sprites are handled by the NES for Super Mario Bros. Mario is split into 8x8 pieces that are swapped out as needed: how do you determine which pieces are "Mario's sprite" and which are "that coin's sprite"? Remember that some pieces will change while others won't.
yea i dont doubt it would be complex & to build an upsampling sprite rendering engine you'd have to understand all this stuff. With old games like this it would probably involve some manual work cuz you'd have to recompose images, smooth as a unit, then decompose somehow back to the original tiling. I mean.... I'm not gonna do it & wouldn't bother trying
the computational price will be much much cheaper tho. swap in upsampled sprite (36 tiles to every 1 in old format, let's say) rather than post-processing every single frame in real-time with a smoothing/upsampling algorithm.
it would also keep the pieces distinct from each other rather than having objects/characters/backgrounds morph in & out of one another
