This paper proposes tailoring image encoding for an approximate storage substrate, developing an approximation-aware encoding algorithm. We develop a methodology to determine relative importance of encoded bits and store them in an approximate storage substrate that we tune to match their error tolerance. We present a case study with the progressive transform codec (PTC), a precursor to JPEG XR, and a phase-change memory (PCM) storage substrate that is optimized to minimize errors via biasing and tuned via selective error correction to different error rate levels. This enables effective use of approximate storage for images, resulting in over 2.7x increase in density of pixels per silicon volume that is additive to PTC storage savings.