While Graph Cuts are used for image segmentation, there exist two problems: how to get better initial information of
foreground and background and how to improve the executing efficiency of Graph Cuts algorithm. To solve the first
problem, path morphology and line segment matching algorithm are performed to get initial background information at
the same time as getting initial foreground information, so non-road pixels similar with road pixels in gray value or
texture are avoided being segmented as road points. To cope with the second problem, push-relabel strategy is chosen
and its parallelized version based on NVIDIA CUDA platform is performed in this paper. Our strategy is performed on
dense built-up area and suburban district and proved to be effective in both accuracy and efficiency.