A new underwater video compression technique based on adaptive hybrid wavelets and directional filter banks is proposed to achieve both high coding efficiency and good reconstruction quality at very low-bit rates. A key application is the real-time transmission of video through acoustic channels with limited bandwidth, from an autonomous underwater vehicle to a surface station, e.g., for man-in-the-loop monitoring and inspection operations. For intra-frame coding, the method maintains details in texture regions at relatively low bit rates, and overcomes the ringing artifacts within smooth regions. For inter-frame coding, improved efficiency is achieved by making use of: (1) a new spatio-temporal just-noticeable-distortion model to remove perceptual redundancy; (2) motion interpolation to reduce bit rate; and (3) variable-precision in quantizing the residual error. Experiments with underwater video sequences are presented to assess the effectiveness of the proposed approach, in comparison to traditional wavelet-based techniques.