An improved stereo algorithm based on graph cuts is developed. Firstly, a robust and adaptive energy function is defined and its graph-representability is proved. The function employs rank transform to reduce noises of data term and utilizes adaptive truncated liner model based on color similarity to preserve the discontinuities of disparity. Secondly, the complexity of the existing graph cuts based stereo algorithms is analyzed, and an α-expansion operation based on segment-constraint is presented. According to disparity smoothness in color connectivity regions, the search range for every pixel is reduced and distance transform is introduced to get candidate correspondences of the disparity α as vertices of the constructed graph in each expansion, thus the computation cost of the maximum flow on graphs is reduced. Finally, α-expansion is operated in descending sequence of the disparity distribution to reduce the total number of iteration. The experimental results show that the improved algorithm can effectively raise the computation efficiency and matching accuracy of stereo ones based on graph cuts.