This paper presents a new approach that aims to improve the performance of the intra block coding of H.264/AVC and HEVC by using a finite state machine. Based on the high correlations between a frame’s neighboring blocks, the finite state machine is employed at both the encoder and decoder to reduce the number of bits required for intra encoding, improving the coding performance of videos. With the matching adaptive template, a better prediction block is found. Through the proposed extra intra prediction modes, the number of bits required to encode a block is reduced significantly, and thus a better intra coding performance is achieved. In addition, an early termination is proposed to speed-up the coding performance. Experimental results show that with the proposed method, the bit rate can be reduced 11% on average when compared to H.264/AVC and 4% on average when compared to HEVC.