Arbitrary shaped coding is an important issue of MPEG-4. In this study, an efficient shaped coding method, called the boundary block-searching (BBS) algorithm, which can enhance the coding efficiency of conventional padding schemes, is proposed. The proposed BBS algorithm assumes that boundary blocks have strong correlation even though they are not connected. For an input boundary block, the most similar block (only object pixels are considered) is sought from the previously coded data. Instead of being encoded by the use of discrete cosine transform, the boundary block is encoded by a position vector, which indicates the relative position of the most similar block. Therefore, the number of bits required to denote the boundary block is greatly reduced and low bit rate can be achieved. For two video sequences under different test conditions, simulation results show that the proposed BBS algorithm can greatly improve coding efficiency.