Text binarization is a part of the system of natural scene text extraction. Owing to the effect of uneven light, complex background, low contrast etc., the problem of complex scene text binarization is very challenging. Consequently, a new scheme of scene text binarization is proposed in this paper adopting a two-step strategy. Firstly, K-Means cluster algorithm is employed in color space of RGB by using of two different distance metrics, and the better result is selected as the initial binarization result. Secondly, graph cut is employed for re-labeling verification in the minimum energy framework. Experimental results show the satisfactory performance of the proposed method.