Recently developed video coding schemes such as MPEG-4 permit arbitrarily-shaped objects to be encoded as separate entities. We describe a shape coding algorithm that adapts the MPEG-4 arbitrary shape coding strategies to a variable block size framework. The new technique, when used in conjunction with motion compensation schemes employing quad-trees as a coding mechanism, successfully integrates the shape and quad-tree coding in a unified structure that minimises temporal correlation. Performance evaluation using MPEG-4 test sequences shows a reduction of up to 16\% in the combined motion and shape coding cost.