These five posts are one argument in order. The first two build loopy belief propagation on discrete variables and run it on a graph that actually has loops. The third swaps the discrete distributions for Gaussians. The last two change the semiring — max-sum in place of sum-product — and take the result out of the textbook: first to data association for target tracking, then to sparse stereo correspondence, where ground truth exists and the claim can be checked rather than admired.
Read in order if the algorithm is new to you. Each post also stands alone, and every one carries the Python it is describing.
-
Loopy Belief Propagation on Factor Graphs, in Python
The algorithm itself, on a factor graph small enough to check every message by hand, then in Python.
-
Image Denoising with Loopy Belief Propagation in Python
The first graph with real loops in it: a Markov random field over image pixels, run until the noise comes out.
-
Line Fitting with Gaussian Belief Propagation in Python
What changes when the variables are continuous and the distributions Gaussian, worked through on a piecewise line fit.
-
Faster Data Association with Max-Sum Belief Propagation (MASDA)
Max-sum in place of sum-product, derived for data association with clutter and misdetection, and how it relates to SPADA.
-
Sparse Stereo Matching with Max-Sum Belief Propagation (MASDA)
The same algorithm pointed at stereo correspondence, measured against ground truth and against exact linear assignment.
Where this goes next
The stereo work is ongoing: a sparse matcher running on an embedded platform, where the interesting question is no longer whether max-sum finds the right correspondences but what it costs per frame to find them. When there is something measured worth reporting, it will appear here as a sixth part.