We develop a new image representation which combines support for coding and content-based retrieval. The algorithm minimizes a weighted sum of the expected compressed file size and query response time. Our approach leads to a progressive refinement retrieval by successively reducing the number of searched files as more bits are read. Furthermore, no distance computations are required during a query. Only simple bit pattern comparisons are required. In our experimental results based on a 1.4 Mbyte image database, the number of bits read during a typical retrieval was less than 1000 bytes (less than 0.08% of the database). The approach supports compressed data modification and low-bit-rate high quality browsing.