Sequential Monte Carlo for Maximum Weight Subgraphs with Application to Solving Image Jigsaw Puzzles.

Area of Science:

• Computer Science
• Artificial Intelligence
• Graph Theory

Background:

• Maximum weight subgraph (MWS) problems involve finding optimal subgraphs under specific constraints.
• Sequential Monte Carlo (SMC) methods are often used for inference but typically require ordered observations.
• Image jigsaw puzzle assembly is a complex problem that can be framed as an MWS problem with hard constraints.

Purpose of the Study:

• To develop a novel inference approach for solving MWS problems with hard constraints within an SMC framework.
• To address the challenge of undefined state ordering in SMC when observations are provided simultaneously, such as in image jigsaw puzzles.
• To propose a new SMC algorithm capable of estimating high-dimensional posterior distributions by exploring state permutations.

Main Methods:

• A novel Sequential Monte Carlo (SMC) sampling framework is proposed.
• The method relaxes the assumption of ordered observations, allowing for simultaneous data input.
• It incorporates a strategy for exploring different state orders and selecting informative permutations at each sampling step to achieve maximum a posteriori estimation.

Main Results:

• The proposed SMC inference framework significantly outperforms loopy belief propagation.
• Experimental results show a quadrupled accuracy in image jigsaw puzzle assembly compared to loopy belief propagation.
• The novel approach effectively handles hard constraints, including node inclusion and mutual exclusion.

Conclusions:

• The developed SMC inference approach provides a powerful new tool for solving constrained maximum weight subgraph problems.
• This method offers a significant advancement for applications like image jigsaw puzzle assembly where natural state ordering is absent.
• The ability to explore state permutations enhances the estimation of high-dimensional posterior distributions.