This paper presents an efficient video coding algorithm: Three-dimensional embedded subband coding with optimized truncation (3-D ESCOT), in which coefficients in different subbands are independently coded using fractional bit-plane coding and candidate truncation points are formed at the end of each fractional bit-plane. A rate-distortion optimized truncation scheme is used to multiplex all subband bitstreams together into a layered one. A novel motion threading technique is proposed to form threads along the motion trajectories in a scene. For efficient coding of motion threads, memory-constrained temporal wavelet transforms are applied along entire motion threads. Block-based motion threading is implemented in conjunction with 3-D ESCOT in a real video coder. Extension of 3-D ESCOT to object-based coding is also addressed. Experiments demonstrate that 3-D ESCOT outperforms MPEG-4 for most test sequences at the same bit rate. 2001 Academic Press.