Local binary patterns (LBP) have powerful discriminative capabilities. However, traditional methods with LBP histograms cannot capture spatial structures of LBP codes. To extract the spatial structures of an LBP code map, we compute and encode the Hamming distances between LBP codes of a center point and its neighbors on the LBP code map to generate a new code, which is called Hamming-distance-based local binary patterns (HDLBP). Then, we calculate a joint histogram of LBP and HDLBP to represent the LBP co-occurrence with HDLBP (LBPCoHDLBP). Circular bit-wise shift techniques are used to align HDLBP with LBP for rotation invariance. To achieve scale invariance, we extract the feature of LBPCoHDLBP from each scale and concatenate all features of different scales. Finally, we use the sum of absolute differences (SAD) between the intensities of the center point and its neighbors to weight LBPCoHDLBP for further improvement. Extensive experiments show that our method achieves better performance for smoke detection, texture classification and material recognition than most existing methods and is more computationally efficient.