In this paper, we present a new method for text extraction in real scene images. We propose first a skeleton based descriptor to describe the strokes of the text candidates that compose a spatial relation graph. We then apply the graph cuts algorithm to label the nodes of the graph as text or non-text. We finally refine the resulted text lines candidates by classifying them using a kernel SVM. To validate this approach we perform a set of tests on the public datasets ICDAR 2003 and 2011.