We present a technique for lossy image compression based on the joint-adaptive space and frequency decomposition of images. The algorithm adapts to image content by both developing wavelet packet bases for separate areas of the image and by segmenting image subbands as needed. The elements of the expansion are a two-channel filter bank and a complete and disjoint binary segmentation system. We construct the joint space and frequency library by cascading permutations of these elements. We also formulate the space and frequency operations to be commutative, which allows for the full cascade system to be organized into a graph. After the full expansion, a coding cost is assigned to all elements in the library. The best joint space and frequency basis is found by pruning the graph which indexes the library such that the embedded graph with least cost is found. Its terminal nodes correspond to the best complete basis. We show that encoding the image in its best joint space and frequency basis improves compression performance.