This thesis presents the theoretical and experimental development of progressive image transmission techniques involving fractals and wavelets, with emphasis on progressive image complexity measures to evaluate and guide the image decomposition. A new and novel progressive image transmission technique is presented where textures are synthesized to recreate an image. The textures are synthesized by generating fractal surfaces such that they interpolate control points, resulting in a higher level representation of an image. From this work, it was conjectured that fractal and multifractal complexity measures can serve as quantitative quality measures, since these dimensions characterize object complexity. The framework and experimentation for a complexity measure is developed based on the Renyi generalized entropy, the Renyi dimension spectrum, and the Mandelbrot spectrum. This framework is extended to the newly introduced relative Renyi dimension spectrum, which forms a new class of measures referred to as relative multifractal dimensions. Experimental results show that these multifractal dimensions, and in particular the relative Renyi dimension spectrum, has properties consistent with an image quality measure and correlate well with psychovisual characteristics. It is shown that the relative Renyi dimension spectrum is more resilient to calculation errors as compared to the other image quality measures. These image complexity measures are used to analyze and identify of regions of complexity disparity in an image for wavelet based progressive image transmission. Finally, the theoretical framework is developed to extend the idea of additive information cost functions in wavelet packet best basis searches such that the Renyi generalized entropy can serve as an entropy based information cost function.