Thresholding is a fundamental operation in image processing. Based on the pairwise nearest neighbor technique and the variance criterion, this theme presents two fast adaptive thresholding algorithms. The proposed ΓΏrst algorithm takes O((m -k)m ) time where k denotes the number of thresholds speciΓΏed by the user; m denotes the size of the compact image histogram, and the parameter has the constraint 1 6 6 m. On a set of di erent real images, experimental results reveal that the proposed ΓΏrst algorithm is faster than the previous three algorithms considerably while having a good feature-preserving capability. The previous three mentioned algorithms need O(m k ) time. Given a speciΓΏc peak-signal-to-noise ratio (PSNR), we further present the second thresholding algorithm to determine the number of thresholds as few as possible in order to obtain a thresholded image satisfying the given PSNR. The proposed second algorithm takes O((m -k)m + N ) time where N and denote the image size and the fewest number of thresholds required, respectively. Some experiments are carried out to demonstrate the thresholded images that are encouraging. Since the time complexities required in our proposed two thresholding algorithms are polynomial, they could meet the real-time demand in image preprocessing.