This paper proposes a fast motion estimation scheme of arbitrarily shaped video object. The instructive role of the alpha-plane taking part in the motion estimation of video object is discussed, and a weighted binary alpha-plane matching criterion (WBAMC) is proposed by using boundary extension and boundary mask techniques. Based on priority search strategy, this paper proposes a fast binary alpha-plane assisted motion estimation (BAAME) scheme of video object. First, the BAAME uses alpha-plane and the WBAMC criterion to limit the search of boundary macro-blocks (MBs) into small unimodal area of two starting points so that a conventional fast motion estimation algorithm can be employed to search the motion vectors (MVs) of boundary MBs. Second, the BAAME predicts the starting points of opaque MBs by using MVs of neighboring boundary MBs and then employs a fast motion estimation algorithm to compute the MVs of opaque MBs. The proposed scheme can be combined with many spatial domain based and frequency domain based different motion estimation algorithms, and be effectively applied to object-based video codecs. The experimental results show that the BAAME scheme can always reach high motion estimation accuracy and better subjective quality for standard test video sequences which have different characteristics respectively. The proposed scheme can achieve 0.1~0.8dB higher prediction quality on average than DS (diamond search) and PSA (priority search algorithm) (BAAS (binary alpha-plane assisted search)+DS), and a little lower PSNR (peak signal-to-noise ratio) than FS (full search). Moreover, the BAAME scheme can speed up the motion estimation about 20 times in terms of computational complexity when compared with FS.