This paper presents a combined halftoning and compression approach which achieves high quality halftones and compression ratios comparable to those of JBIG and JBIG2 with much simpler encoding and decoding schemes. We use tone-dependent error diffusion and a tree structure to efficiently develop the halftone texture from a limited set of binary one-dimensional tokens. Local estimation of tone further restricts the candidate set of tokens. In areas of the image containing edges or detail, the token is not constrained. A Huffman code is used to efficiently encode the tokens with minimal complexity. Experimental results show that visual quality is very close to that of regular tone-dependent error diffusion.