Arbitrarily shaped coding is an important tool to achieve MPEG-4, which is a object-based coding standard. We proposed an efficient shaped coding method which enhances the coding efficiency of conventional padding techniques in the object-based video coding where the shape information is provided. The boundary block-searching algorithm (BBS) is applied to the boundary blocks of a VOP (video object plane) which consists of both background and object pixels. Actually, boundary blocks have strong correlation even though they are located apart. For an input boundary block, we search the closest block (only object pixels) from the previously encoded data using the BBS algorithm. After searching, the boundary block is represented as a position vector. This process reduces the number of boundary blocks to be DCT and makes the bit rate small. Experimentation has been done on various video sequences under different test conditions and verifies significant coding efficiency improvement.