Underwater (UW) imagery presents several challenging problems for the developer of automated target recognition (ATR) algorithms, due to the presence of noise, point-spread function (PSF) effects resulting from camera or media inhomogeneities, and loss of contrast and resolution due to in-water scattering and absorption. Additional problems include the effects of sensor noise upon lossy image compression transformations, which can produce feature aliasing in the reconstructed imagery. Low-distortion, high- compression image transformations have been developed that facilitate transmission along a low-bandwidth uplink of compressed imagery acquired by a UW vehicle to a surface processing or viewing station. In early research that employed visual pattern image coding and the recently- developed BLAST transform, compression ratios ranging from 6,500:1 to 16,500:1 were reported, based on prefiltered six- band multispectral imagery of resolution 720 X 480 pixels. The prefiltering step, which removes unwanted background objects, is key to achieving high compression. This paper contains an analysis of several common compression algorithms, together with BLAST, to determine compression ratio, information loss, and computational efficiency achievable on a database of UW imagery. Information loss is derived rom the modulation transfer function, as well as several measures of spatial complexity that have been reported in the literature. Algorithms are expressed in image algebra, a concise notation that rigorously unifies linear and nonlinear mathematics in the image domain an has ben implemented on a variety of workstations and parallel processors. Thus, our algorithms are feasible, widely portable, and can be implemented on digital signal processors and fast parallel machines.