This article describes and analyzes the new feature extraction technique, Random Local Descriptor (RLD), that is used for the Permutation Coding Neural Classifier (PCNC), and compares it with Local Binary Pattern (LBP-based) feature extraction. The paper presents a model of face feature detection using local descriptors, and describes an improvement on the PCNC for the recognition of plane rotated and small displaced face images, as applied to three databases, i.e., ORL, FRAV3D and FEI. All databases are described along with the recognition results that were obtained. We also include a comparison of our classifier with the Support Vector Machine (SVM) and Iterative Closest Point (ICP). The ORL database was selected to compare our RLDs with LBP-based algorithms. The PCNC with the RLDs demonstrated the best recognition rate, i.e., 97.49%, in comparison with 90.49% for LBPs. For the FEI image database, we obtained the best recognition rate, i.e., 93.57%, in comparison with 66.74% for LBPs. Using the RLDs and rotating the original images for FRAV3D, we improved the recognition rate by decreasing by approximately twice the number of errors. In addition, we analyzed the influence of different RLD parameters on the quality of facial recognition.