Reverse Bresenham algorithm? How to convert array of drawn pixels into coordinates

Question

Does there exist an algorithm that can analyze an array of pixel coordinates, and return an array of line coordinates that, when drawn using Bresenham's algorithm, would generate lines that cover the same pixels as the original array?

One use case is to optimize hand-drawn pixel art so it can be stored as lines rather than individual pixels.

Update: Here's a more concrete example: Say someone has drawn something by hand with a pencil tool, like a signature.

The red pixels are all stored in a single array. So, for example it might begin: [ [27,31],[26,31],[25,30],[24,30],[23,29],[22,29],[21,28],[20,27],[19,26],[18,25],[18,24],[18,23],[18,22],[18,21],[18,20],[18,19],[18,18],[18,17],[18,16],[18,15],[18,14],[18,13] ... ]

Is there an algorithm that could iterate through this array of individual pixels and return an array of line coordinates? In my example, it would take the pixels I gave above and return the following line coordinates: [ [[27,31],[22,29]], [[22,29],[18,25]], [[18,25],[18,13]] ... ]

Answer 1

If array contains the only line, just find end pixels and define line equation through two end points

To find end pixels, determine the most left one, the most right one, the most bottom one and the most top one. Choose larger - vertical or horizontal - difference to exclude errors for almost vertical or horizontal lines.

Note that source line drawing might contain some intermediate pixels distinct from Bresenham algo.

Answer 2

I would approach this with a greedy algorithm.

Maintain a 2D grid where each pixel has one of three states: either it is red but not covered yet, red and already covered, or grey (i.e. should not be covered). Then do this repeatedly until there are no uncovered pixels:

• Find the top-left-most red-but-uncovered pixel, call it P.
• Do a breadth-first search starting from P to find all red pixels Q (either covered or uncovered) which satisfy the property that a Bresenham line from P to Q covers only red pixels (either covered or uncovered).
• Choose the line which covers the most red-but-uncovered pixels, add it to the output, and mark its pixels as red-and-covered.

The breadth-first search is a bit tricky to describe and justify. We consider the neighbours of a pixel to be in all 8 directions but only consider the neighbours which are red. When we find a neighbour Q, we are interested in two things:

• Is the line from P to Q all red? (i.e. is this a valid candidate for the output?)
• Is there any all-red line from P which goes through Q?

These two questions do not necessarily have the same answer; we need to keep searching past some pixels Q even if they are not valid candidates for a line. The first question is easy to answer by just running Bresenham's algorithm. The second is harder to answer exactly, but fortunately we don't need an exact answer - a false positive means we will consider more pixels than necessary (i.e. it degrades performance) and a false negative means we may output more lines than necessary (i.e. it degrades output quality).

There are various approaches that can be taken to test for the second property. One option would be to consider the range of angles/gradients of lines that could go through that pixel, so for example if Q is just one pixel to the east of P then the range of possible angles is -45 degrees to 45, or the range of possible gradients is -1 to 1 (since a line at one of these angles or gradients from the centre of P would go through some part of Q's square). Then when we look at Q's neighbours, we can reject a neighbouring pixel if it is entirely outside of the cone associated with Q; when we insert the neighbour into the queue, we also need to insert the range of angles/gradients allowed, which in generally will be smaller than the full range of angles/gradients of lines passing through the pixel. This test would give some false positives but no false negatives.

Since this is a greedy algorithm, it will not generally produce optimally-compressed outputs. However, for compression algorithms you usually don't care about optimality, just whether the result is "good enough". There is probably no efficient algorithm which guarantees optimal outputs, since this is a kind of set cover problem.