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: