ICM is very fast but I could not find any references that contain a detailed analysis on its convergence (e.g. rate of convergence).
Any suggestions please? Thanks a lot for your help!
The speed and accuracy of convergence does depend on the source signal to noise ratio. I would relate convergence to stability and think about "time to converge" as just "time to propagate".
Have you looked at the Viterbi algorithm? In the case of a 2-d image, an MRF prior is potentially a very strong constraint on individual pixels - so iid per-pixel noise is not such a hard problem.
Conditional mode is a Bayesian concept and is often non-convex such as Ising, convergence to a local maximum is unlikely a global maximum, the Maximum A-posteriori Probability MAP is what links neighbours. Updates are only stable if they are performed sequentially. Updating both neighbours allows oscillations.
The weight function reflects the assumed noise-level, given a well behaved noise distribution (convex log-probabilities) the local-maxima.
In practice I gather a smoothing function or less granular model is used to prime the estimate - this is equivalent to simulated annealing. It deliberately slows down convergence to have a better chance of ending up at good local maximimum .. i.e. close to the global maximum.
I apologise if my comments are naive, I'm no expert and just flicked through these papers.