In transmitting compressed video bit-stream over Internet, packet loss causes error propagation in both spatial and temporal domain, which in turn leads to severe degradation in image quality. In this paper, a new error concealment algorithm, called EBMA (Edge Detection based Boundary Matching Algorithm), is proposed to repair damaged portions of the video frames in the receiver. Conventional BMA (Boundary Matching Algorithm) assumes that the pixels on the boundary of the missing block and its neighboring blocks are very similar, but has no consideration of edges across the boundary. In our approach, the edges are detected across the boundary of the lost or erroneous block. Once the orientation of each edge is found, only the pixel difference along the expected edges across the boundary is measured instead of the calculation of differences between all adjacent pixels on the boundary. Therefore, the proposed approach needs very few computations and the experiment shows an improvement of the performance over the conventional BMA in terms of both subjective and objective quality of video sequences.