A novel structured dictionary training algorithm is proposed for double sparse image representation. Based on the double sparse image representation model proposed by Rubinstein, the zero-tree structure of wavelet coefficients was introduced, and the new dictionary atoms were constructed by linear combination of wavelet bases in all high-frequency bands of same orientation across different scales. The linear combination coefficients were learned via K-SVD. The image decomposition and reconstruction algorithm was proposed based on the learned dictionary. The M-term approximation and compression of remote sensing images both proved the better effects of the proposed structured dictionary than the existing dictionaries.