One of the new features of iTunes 7.0 is cover flow, the ability to navigate albums by their covers using either a list view, or a nifty rolodex-like effect. This and the fact that my iPod nano display the cover art for albums as pushed me to add cover art to my music collection. The problem of adding a cover image to the music, in particular with a reasonable resolution means the files will become significantly larger. The good news is that iTunes alleviates the problem by consolidating the artwork for albums, i.e. if one song of the album has a cover, it is used for all songs in the album. While this scheme is nice from a disk usage point of view, it is not very robust: if the song with the cover is deleted, the whole album looses its cover.
I don’t know if cover album data is compressed within mp3 files, but if there are not, one elegant solution would be to split the cover art of an album among the files of the songs that form the album. Consider an album with four songs with a cover album of 200×200 pixels. The idea is to store odd lines on songs 1 and 2, and even lines on songs 3 and 4. We distribute columns in a similar fashion: even columns on songs 1 and 3 and odd columns on songs 2 and 4. The result is that each song contains a subsample of the cover at 100×100 pixels and with four song’s sub images, the high-resolution version can be reconstructed. While the quality of the subimages will not be as good as if they were resampled at a lower resolution, each subimage should still be usable. If one of the songs of the album is missing the high-resolution version can still be extrapolated by averaging the pixels arounds the missing pixel. Of course this idea can be adapted for albums with any number of songs. Each sub-sampled image could be compressed independently, but compressing n images independently will certainly not achieve the same compression ration as compressing the whole image once.