A rotation and scale invariant face detection algorithm based on the texture of a human face is proposed in the paper. Wavelet packet analysis is performed on the test image to get the coefficients. It is observed that wavelet packet decomposition until third level is sufficient enough to get the necessary frequencial components essential for classifying faces and non-faces. Rotation invariant textural features are extracted from the wavelet coefficients. A scale invariant distance measure between the feature vectors of each of the candidate faces and the prototype face image is proposed to classify the candidate faces into faces and non-faces. The detection process implements a non-linear luminance based lighting compensation method, which is very efficient in enhancing and restoring the natural colors into the images taken in darker and varying lighting environments. The novel detection process proposed is highly efficient in terms of speed and accuracy in detecting frontal view faces in a complex background. The face detection performance of the proposed system is comparable to other reported leading systems.