An interesting problem in Computer Vision is the construction of local image descriptors. It deals with the description of intensity patterns within image patches. Image patches are local image regions centered at feature points. The description of such image patches helps in establishing correspondences between the feature points of two or more images of the same scene under intensity, scale, rotation, and affine changes. Such correspondences are used in a wide range of applications, such as image matching, image retrieval, object tracking, and object recognition. This thesis presents new methods for the construction of local image descriptors in order to establish feature point correspondences under nonlinear intensity changes. Nonlinear intensity changes occur in multispectral imaging or when a scene is acquired under variable lighting conditions. Background noise and degradation in ancient document images also cause nonlinear intensity changes. Nonlinear intensity changes affect the performance of the state-of-the-art local descriptors, such as Scale Invariant Feature Transform (SIFT) and result in a low matching performance in image-to-image and image-to-database matching tasks. To cope with these problems, the new methods proposed in this thesis use novel image features, which are obtained by combining the strengths of image gradients, Local Binary Patterns, and illumination invariant edge detectors. These features are read from image patches by using the SIFT-like feature histogram schemes to construct five new local descriptors, which are: Local Binary Pattern of Gradients, Local Contrast SIFT, Differential Excitation SIFT, Normalized Gradient SIFT, and Modified Normalized Gradient SIFT. To evaluate the performance of new descriptors, experiments on five different image datasets are performed. The performance of new descriptors are compared with that of SIFT and seven other state-of-the-art local descriptors. In the case of image-to-image matching, ground truth homographies between the pairs of images are used and the number of correct descriptor matches is counted for the performance comparison. In the case of image-to-database matching, a nearest neighbor based descriptor matching strategy is used and the recognition rates for two different tasks are computed. These tasks are Scene Category Recognition (SCR) and Optical Character Recognition (OCR). The experimental results show that the new descriptors obtain on average 0.5% to 12.8% better performance than SIFT in image-to-image matching. In the case of SCR, they obtain on average 1% to 5% better scene recognition rates than SIFT, whereas in the case of OCR, they demonstrate on average 1.1% to 6.7% better character recognition rates than SIFT.