In this paper, we propose a realtime face detection approach based on local structure and texture of the objects in gray-level images. Our strategy is to map the local spatial structures and image textures of face class into binary patterns, and use these binary patterns as local descriptors. Boosting based face detector is constructed using these local descriptors, and cascade scheme is employed to further improve the efficiency of the face detector. Compared to the existing face detection approaches, our proposed method has two advantages: (1) it is robust to illumination changes to some extend, for the features use the information of local relationship instead of the original gray values; (2) the computational cost is very low, both in training procedure and evaluation step. The experimental results show that the proposed method can meet the demand of realtime applications with a satisfied detection performance.