Ground segmentation is an important preprocessing task for autonomous vehicles (AVs) with 3D LiDARs. However, the existing ground segmentation methods are very difficult to balance accuracy and computational complexity. This paper proposes a fast point cloud ground segmentation approach based on a coarse-to-fine Markov random field (MRF) method. The method uses the coarse segmentation result of an improved local feature extraction algorithm instead of prior knowledge to initialize an MRF model. It provides an initial value for the fine segmentation and dramatically reduces the computational complexity. The graph cut method is then used to minimize the proposed model to achieve fine segmentation. Experiments on two public datasets and field tests show that our approach is more accurate than both methods based on features and MRF and faster than graph-based methods. It can process Velodyne HDL-64E data frames in real-time (24.86 ms, on average) with only one thread of the I7-8700 CPU. Compared with methods based on deep learning, it has better environmental adaptability.