Image segmentation is one of the most important tasks in image processing and pattern recognition. One of the most efficient and popular techniques for image segmentation is image thresholding. Among several thresholding methods, Kapur's (maximum entropy (ME)) and Otsu's methods have been widely adopted for their simplicity and effectiveness. Although efficient in the case of bi-level thresholding, they are very computationally expensive when extended to multilevel thresholding because they employ an exhaustive search for the optimal thresholds. In this paper, a fast scheme based on a modified Bees Algorithm (BA) called the Patch-Levy-based Bees Algorithm (PLBA) is adopted to render Kapur's (ME) and Otsu's methods more practical;​ this is achieved by accelerating the search for the optimal thresholds in multilevel thresholding. The experimental results demonstrate that the proposed PLBA-based thresholding algorithms are able to converge to the optimal multiple thresholds much faster than their corresponding methods based on Basic BA. The experiments also show that the thresholding algorithms based on BA algorithms outperform corresponding state-of-the-art metaheuristic-based methods that employ Bacterial Foraging Optimization (BFO) and quantum mechanism (quantum-inspired algorithms) and perform better than the non-metaheuristic-based Two-Stage Multi-threshold Otsu method (TSMO) in terms of the segmented image quality. In addition, the results show the high degree of stability of the proposed PLBA-based algorithms.