In High Efficiency Video Coding (HEVC), a quad-tree based Coding Unit (CU) partitioning scheme is employed, achieving a substantial improvement in coding efficiency compared with previous standards. The superior coding efficiency of HEVC is achieved at the expense of greatly increased complexity. A fast intra coding scheme consisting of fast CU depth decision and fast prediction mode decision is proposed to reduce the computational requirement. Classification of the homogeneity of video content using an adaptive double thresholds scheme is employed to reduce the number of Rate Distortion (RD) evaluations. The partition information of spatially neighbouring CUs is utilised to further narrow the depth range. The construction of the initial candidate list is improved for each Prediction Unit (PU). Then the prediction mode correlation between neighbouring quad-tree coding levels is considered to predict the most likely coding mode. The Hadamard cost of prediction modes is examined to further reduce the candidate modes. The computational complexity of HEVC intra coding is therefore reduced. Simulation results show that the proposed algorithm reduces encoding time by up to 71% compared with the HM 13.0 implementation, while having a negligible impact on rate distortion, with increases in bit-rate of 1.82%.