Tracing a bitmap

I explained in my blog on SVG how I needed to trace a bitmap for a QR code in order to make an SVG version.

To me, this seems very obvious, but it is interesting that people do have different algorithms for doing this. So I thought it worth documenting how I did it.

The objective is to make an SVG, which uses a path to draw around something and fill it with a colour, from a bitmap. A bitmap has each pixel that is a colour on a grid. It is very obvious how a bitmap works when looking at the QR code as it is clearly made of squares of black and white.

Simplistic

This obvious and simplistic approach is make an SVG rectangle for each pixel. That makes for a large SVG file, hence the idea of tracing around multiple pixels of the same colour and using a path.

Not just black and white

The first thing I considered was that this could be more generic than just black and white. We already use an image library to generate a bitmap using indexed colours. This means we have a grid of bytes, each of which has a value 0 to 255, each representing one colour. A separate table says which colour is actually used for each number. It is a paint by numbers system.

I already use this to generate the existing PNG images, including the QR code. But why not make the tracing function a generic SVG output for any indexed bitmap we make.

This basically means tracing each colour, one after the other. However, the principle is just the same for black and white images.

Background colour

Even with an indexed colour bitmap there is often the notion of a background colour. So my code starts by checking if one has been specified and making a simple rectangle of that colour for the whole bitmap.

With the QR code this is simple, it is white. Not a lot of people know that QR codes actually require 3 pixels of white all the way around. You often see them with one pixel, or even in some cases with none (krispy kremes boxes?).

Sometimes the background colour is also transparent in which case you don't plot it at all. Obviously a simple check to see if any pixels are the background colour, and if none, then don't bother either.

In any case, if there is a background, you don't include that colour in the tracing as it is already handled.

Just black

Obviously for the QR code it is simple. The indexed colours are just 0 (white) and 1 (black), with 0 as the background colour. So we do a white rectangle, and then a path for the black. Where there are multiple colours we just trace each (non background) colour one at a time.

Directions

As part of the walking around the image tracing it, we have to consider facing a direction. Imagine you are standing on a square on a chess board, you can be facing one of 4 ways, to consider the 4 sides of the square on which you stand...

When working on a direction, some times we have to add or subtract, and we do so using modulo arithmetic, so adding 1 to 3 becomes 0. As such adding 1 is turning right and subtracting 1 is turning left.

In the code, a simple dx and dy table can be used to hold the offset for each direction.

Repetition

As we scan the image to find areas to trace around, we could easily find we are going over the same thing more than once. To avoid this we also create a byte array, one per pixel, in which we record the edge of that pixel which we have already traced. This is one bit per direction so actually only 4 bits used in each byte. This stops us accidentally trying to trace any edge of any pixel more than once. We only record the edge of the pixel we are in, not the other side, i.e. the opposite edge on the adjacent pixel, as that will be recorded when we trace its colour. Obviously if the other colour is the background, as with out QR codes, then that does not get traced, but if it was in fact another colour to trace, we don't want to record that edge as having been traced yet.

Over the edge

Obviously, as part of this, we need to look at the colour of a pixel, so we make a function that takes an x and y co-ordinate and returns the colour. The indexed colours are 0 to 255. However, we allow full integers for x, y, and the result. This means we can look over the edge of the bitmap, either negative x, or y, or values beyond the width and height of the image, and these can return -1 for the colour which will match no colour actually in the image.

What this means is we can look at the pixel in any direction and see that it is a different colour, so it is the edge of what we are tracing. We do not have to have a special case for looking in direction 3 when on the left of the image, we simply see that as colour -1, so clearly the edge of what we are tracing.

Finding areas to trace

The first thing to do is scan the image for the colour we are tracing. Remember, we are tracing one colour at a time, and not bothering to trace the background colour at all. For QR codes, that means we only trace black.

1. We scan from top to bottom and left to right in a simple loop looking first for a pixel of the colour we are tracing.
2. We then consider what edge of that pixel we want to trace, looking in turn at direction 0, 1, 2, 3 and looking for a pixel in that direction which is not the same colour, so an edge of the block of pixels of this colour. We also disregard any directions where we have already done that edge of this pixel.
3. If we find no directions that match that rule, then this is not a pixel to trace. It is either one we have done already, or one that is surrounded by pixels of the same colour so does not need tracing.
4. If we do find a direction, then that is our starting point for walking around a set of pixels of this colour, doing the trace. 

Two faced

Actually, it is slightly simpler! I said we check 0, 1, 2 and 3 to find an edge to trace, but in practice we can only see 0 or 2.

It may seem obvious actually that you should only ever see 0. After all, the pixel above must be a different colour. If it is the same colour then we already did it, and so the whole block of pixels we are in has already been traced, and so if direction 0 is the same colour, any edge on 1, 2, or 3 must have been traced as part of that block, surely.

Well, actually no, there is an edge case (:-) if the block of pixels we have already traced, i.e. direction 0 is the same colour, but it fully encompasses pixels of a different colour.

Whilst the outside of this black block has been traced, this is an edge to an interior area, and so has not been, and it is direction 2.

So why could we not have direction 1 or 3? Well if it was 1, that means the interior area in question would have been found one row further up already with a black pixel facing down (direction 2) already. Similarly, if the interior pixel was on the left (direction 3) it would have been seen facing down (direction 2) from a previous row.

So actually there are only two possible ways would could be facing to start, 0 and 2. Not that it matters, but 0 is exterior and 2 is interior.

Doing the trace

Having found a starting point, you then do the trace. The direction you are facing is the edge you are going to draw, for each edge you only need to plot one point, and you make up a set of points that are going to be a closed filled area. In SVG you use M x y for the start and L x y for a line, so you need a flag to know you are doing the first point and use the M.

But which point is it? You are looking at an edge, and it does not really matter if you pick the left or right point on that edge in the direction you are facing, as long as you are consistent. In this example I pick the one on the right (considering the direction I am facing).

You mark this edge has having been done in your byte array of edges. And you add this point to the list of points for this trace.

You then move on, and this is where you have to walk around the area you are tracing. So we have to make a decision.

There are three possible choices of how you move...

Firstly, can you turn left around a corner? This means moving to a pixel that is one space right from the direction you are facing (d+1), and then one place left of that (d). To decide if you can move there you simple check if that pixel is the same colour. If so, then move there, and also turn left (d-1). This leaves you facing the same pixel you started facing, so you know it is a different colour already and so don't have to check.

If you can't do that, you may be able to move right. This is only if you cannot do the above move. To do this you simply check if the pixel to your right (d+1) is the same colour. If it is, you move there, but do not change your direction (d). You end up facing the pixel you could not move to in the above case, so again, you know you are facing a pixel of a different colour still.

Finally, if that does not work, you simply turn right, this means staying in the same place by changing to (d+1) direction. Again, this leaves you facing the pixel you could not move to in the above case, so again, you know you are facing a pixel of a different colour still.

When to stop

You keep going, adding a new point, and marking an edge as done, until you find you are facing an edge that is already done. That means you have got back to the start. Then you move on to the next pixel in your scanning to find the next area to trace.

Closing the path

This does not actually result in plotting the end point, as you stop when you get back to the start, but that is fine as the SVG full does not expect the path to be closed for a fill. If you need to, because you want to also trace the outline, for colour bleed or some such, then you can used the close path command (z).

Enclosed areas

The good news is that this approach does not have to consider enclosed areas. We actually know if it is an enclosed area by the starting direction being 2 and not 0, but that does not actually matter. This tracing will always create a clockwise trace for an exterior path and a counter clockwise path for an interior path. The fill logic used by SVG means the inner path cancels our the outer path and creates exactly the effect you want.

Colours butting up

There is one possible issue when tracing multiple colours. The above will create the traces for each colour, but the areas of one colour will touch the areas of another. This should not be a problem in SVG or other contexts, but could be - i.e. depending on how things are rendered it could lead to an infinitesimally small gap between them - perhaps if the result is rotated or manipulated in some way.

To avoid this, we could change the trace logic to consider any colour of a higher number to be the same colour, and we know that the higher colour will be traced on top of this colour. If we do this we will have to clear the byte array of edges before each colour as we'll use the same edges.

Sadly this creates the same issue where we have the edge of two colours on top of each other, and any misalignment due to processing could leak one colour overlapping the other by an infinitesimally small amount.

So maybe not an issue worth bothering about.

Optimising the result

Another important point is not simply to use M and L for SVG. Doing so means absolute co-ordinates and a point for each end of each edge.

Instead, I simply made some functions that use M at the start and then relative co-ordinates using l, h, and v. The numbers are smaller, and using h (horizontal) and v (vertical) means only one value. In practice l is not used, but they are generic SVG path functions that could be used in other places.

The optimisation obviously has to consider that we have multiple points in a row and reduce to a simple line. In this case it was only necessary to consider multiple points either horizontally or vertically which reduce to a single h or v command.

The other optimisation is to use the point on the left of the edge you are facing when doing an exterior path, but the point on the right when doing an interior path. This means you always start and end on a corner, making the optimisation slightly easier.

Obviously if you want an SVG where the QR code pixels are bigger, as is often the case, then simply enclosing the entire thing in a g (group) with a scale is simplest and keeps the numbers in the paths smaller.