MCMC and Metropolis-Hastings Algorithm to Solve a Combinatorial Optimization Problem

Combinatorial optimization is widely used in various imaging sciences, including image analysis and processing, computer graphics, computer vision, and visualization. On the other hand, the Metropolis-Hastings algorithm is the most common approach to Markov Chain Monte Carlo for sampling. However, this work aims to introduce the Markov Chain Monte Carlo methods' theoretical background and mathematical variation. Besides, develop an algorithm to solve a combinatorial optimization problem. Additionally, it aims to find mathematical results of probabilistic inference values by approximation methods and use the Metropolis-Hastening algorithm to find an approximate solution to the problem. Consequently, we utilize the MCMC for the Markov Chain Monte Carlo and the Metropolis-Hastings Algorithm to build this system. Thus, we applied a combinatorial optimization solution technique to the noise reduction of binary images. Finally, we compare our results using the structural similarity index (SSIM) and other simple metrics such as mean squared error (MSE) and Peak-SNR for perceptual image quality metrics. SSIM has been frequently shown to significantly beat MSE and result in accuracy.