We start with a $50 \times 100$ binary image with noise.

It is convenient to encode the image as a sequence of pixels $x_i\in\{-1,1\}$. Then we can write (see eg. here) a simple binary quadratic denoising model

$$\mathrm{maximize} \sum_{i\sim j}z_iz_j+\gamma\sum_i x_iz_i,\quad z_i\in\{-1,1\}$$

which favors similarity between neighboring ($i\sim j$) pixels in $z$ and the similarity between $z$ and the original $x$, with tradeoff between the two measures provided by $\gamma$.

Binary quadratic problems have a natural SDP relaxation, in this case

$$ \begin{array}{ll} \mathrm{mazimize} & \sum_{i\sim j} Z_{ij} +\gamma x^Tz \\ \mathrm{s.t.} & \left[ \begin{array}{cc}Z&z\\z^T&1\end{array} \right] \succeq 0, \\ & \mathrm{diag}(Z)=1.\end{array} $$

We solve the SDP for various $\gamma$ ($Z$ has dimension $5000$; this is not the most efficient image processing algorithm ever invented). To further simplify we don't round but let the raw $z$ interpolate between shades of green.

Merry Christmas from the MOSEK team.