Content-based indexing and retrieval of video have a great role in many applications, and scene change detection plays an essential role in these tasks. In this paper, we introduce an algorithm for sudden and gradual scene change detection in MPEG video in faster than real-time. First, we use the number of bi-directional predicted macroblocks (bi-MBs) within a B frame and their mean to define an adaptive threshold to identify abrupt scene changes. Then, a selected frame consisting of MBs is divided into several sub-MB images to detect gradual scene changes, such as dissolves and fades. This algorithm can be applied to any type of MPEG sequence. Experimental results show that this algorithm is fast and robust to detect most abrupt and gradual scene changes in compressed sequences. This method can be used as pre-processing for indexing and retrieval.