Abstract: High Efficiency Video Coding (HEVC) adopts a quadtree-based Coding Unit (CU) block partitioning structure which is flexible to adapt to various texture characteristics of images and can improve the coding efficiency significantly; however, it also introduces a great computation complexity. This paper proposes a fast CU splitting algorithm which can narrow CU depth range and early terminate the CU splitting. Firstly, in learning frame, based on the Sobel edge detection operator, this study obtains edge point threshold at each CU depth level to narrow the CU traversal depth range in the next several frames. Meanwhile, this paper introduces the statistical of Rate-Distortion (RD) cost of CU in the frame and calculates RD threshold of each depth level. Then, in the subsequent video frames, RD threshold is utilized to terminate early the CU splitting in the narrow depth range. The statistical parameters are periodically updated to cope with varying video content characteristics. The experimental results show that the proposed algorithm is able to save 59% encoding time on average with only 1.2% increasing on bit-rate which can observably improve the coding efficiency.