This paper proposes a method to extract character regions in natural scene images by hierarchical classifiers. The hierarchy consists of two types of classifiers : histogram based classifier and SVM. On the bottom level, fast and reliable histogram based classifier is used to reject apparent non-character regions. On the next level, a non-linear SVM is exploited to make a final decision. One of the drawbacks of non-linear SVMs is its computational cost. To reduce the computational cost, we use sparse wavelet representation. Moreover, to reduce the cost further, we propose a method to approximate a SVM with sparse support vectors. We experimentally show this two-step method can perform very well with respect to both the computational cost and recognition rate.