We can use [this](http://math.stackexchange.com/a/274728/380122) answer on math.SE to determine on which side of a line a point lies. Based on this formula, we have that the new gray level is given by

    f[{{x1_, y1_}, {x2_, y2_}}][gl_, {x_, y_}] := gl + 0.1 Sign[(x - x1) (y2 - y1) - (y - y1) (x2 - x1)]

We can apply this to all pixels recursively in the following manner:

    iterate[img_] := Module[{dimx, dimy, pts},
      {dimx, dimy} = ImageDimensions[img];
      pts = {RandomInteger[dimx, 2], RandomInteger[dimy, 2]};
      ImageApplyIndexed[f[pts], img]
      ]

    img = ConstantImage[0.5, {300, 300}];
    Nest[iterate, img, 50]

![Mathematica graphics](https://i.sstatic.net/9lNZV.png)

Below is another test run with more iterations, and I also changed the constant 0.1 in front of `Sign` to 0.02. This constant determines how much each side is raised or lowered, and it has a big influence on the visual effect.

    Nest[iterate, img, 100]

![Mathematica graphics](https://i.sstatic.net/OfeGW.png)

I'm not sure how to prove correctness for this algorithm, so if anyone spots an error please tell me.