MCMC Painter

Algorithm Overview

The MCMC Painter uses a Reversible Jump Markov Chain Monte Carlo (RJMCMC) algorithm to iteratively construct paintings that approximate a target image.

Key Components:

• State Space: Variable number of painting elements with parameters (x₁, y₁, x₂, y₂, color)
• Target Distribution: Posterior probability based on image similarity
• Proposal Moves: Birth, death, and update operations
• Acceptance Rule: Metropolis-Hastings criterion with temperature annealing

Reversible Jump MCMC Framework

RJMCMC extends standard MCMC to handle variable-dimensional parameter spaces, allowing the algorithm to add or remove line segments while maintaining detailed balance.

Mathematical Formulation:

• k: Number of painting elements
• SSE(θ): Sum of squared errors between target and current image
• β: Inverse temperature parameter
• p(θ): Prior distribution over painting element parameters

Proposal Mechanisms

1. Birth Move (k → k+1)

Adds a new painting element with parameters sampled from the prior distribution.

2. Death Move (k → k-1)

Randomly selects and removes an existing painting element.

3. Update Move (k → k)

Modifies parameters of an existing painting element using Gaussian proposals.

Acceptance Probabilities

The Metropolis-Hastings acceptance probability ensures detailed balance and convergence to the target distribution.

General Acceptance Formula:

For Birth Moves:

For Death Moves:

Temperature Annealing:

The inverse temperature β increases over iterations, making the algorithm more selective as it progresses: