A more cautious approach than trying to find a box around each character, is to trace the exterior boundary of the black pixels. Then we can work out from the length of the boundary something about the size and shape of the object we have found. This should distinguish noise from characters, given reasonable luck and a good quality image. It also puts a box around the object, although rather an irregularly shaped one. Still, better a weird shaped box than no box at all. At least, we can segment the image into objects.
As we have noted, in the case of handwritten characters it could be a mistake to imagine that the segments we get this way are going to be characters. They could be bits of characters, or more often several characters joined together. For good quality printed text however, border tracing stands a reasonable chance of isolating characters. We therefore discuss the problem of finding the border pixels of a connected block of pixels. We then regard the character as the set of pixels lying inside this rather irregular `box'.
The algorithm described briefly here (and which may be found, with some additional nuances, in some of the references below, particularly Haig, Attikiouzel and Alder) is one which the most innocent would devise unaided.
First we assume that the image has a white border around it, and we have to find the bounding pixels of clumps of black pixels. We therefore start at the top left of the image at a white pixel, and scan horizontally until we encounter the end of the row or a black pixel. In the former case we do a line feed carriage return to start at the left side of the next row down. If we are at the bottom row already and there is no next row, we have scanned the page and stop.
If we have found a black pixel, we draw an imaginary line from the pixel just to the left of it to the black pixel. We note the direction of this line, and the co-ordinates of the black pixel. Then we rotate the line, about the black pixel, in the positive direction (anticlockwise), until it meets another black pixel adjacent to the first black pixel, or returns to its original position. In the latter case the black pixel is isolated; we mark its location, delete it and start again. If we find another black pixel then it is in one of the eight positions adjacent to the first black pixel. Call the black pixel we are currently standing on pixel n. When n= 1 we are at the first black pixel, but this works for all of them. We now move to pixel n+1, note its location, note the direction from pixel n to pixel n+1, and take the line joining pixels n to n+1 and rotate it, about pixel n+1, in the positive direction, until it finds an adjacent black pixel which becomes pixel n+2. This process is repeated until pixel n+1 is a previously listed pixel and the line from pixel n to pixel n+1 is the same previously listed direction. This last condition is very necessary, as it is easy to re-enter a pixel from different directions without circumnavigating the set. The reader should examine carefully the border tracing program and try it out on some sets to see if it locates borders in a sensible way.
Once a black object has been found, the pixel set of its border is determined by this algorithm, and this set of pixels together with every pixel which is inside this border is stored as an object and then deleted from the page, and the scan starts again. Only when the page has been blanked does the procedure terminate.
Deleting the pixels inside the border sounds easy but may not be if the border is not convex. To see if a pixel is inside the border, draw a half ray starting at the pixel and extend to the boundary. Count the number of times this intersects the border. If the number is even, the starting pixel is outside, otherwise it is inside or on the border. This works except in some `bad luck' cases where the half ray hits an extremal point of the boundary. So wobble the line and the starting pixel a little bit and try again. If a pixel is inside the border and not on it, every adjacent pixel is either inside or on the border. A `floodfill' operation stopping at the border and starting inside it can be used to label the points to be removed. Of course, a border may have no interior points.
There are more efficient ways, but it is relatively
easy to prove rigorously that this method will
work. Well, sort of. If the image has a black
border, or a black box around a character,
as in 
, and if the border is broken, then
the algorithm will fail to find the desired set.
Similarly, it will separate out the components of colons, semi-colons and characters such as i and j which are disconnected.
Noise, black lines down the middle where the centre of the book got miscopied, smudges and the like will be picked out and will have anomalous shapes: the single pixel dots can be eliminated at this stage. Knowing the approximate size of a character can help remove the odd spots, although it is easy to get rid of the punctuation as well.
If the input text comes in a wide variety of fonts, as for example the page of a newspaper or magazine, or is mixed with graphic images, then the complications of segmentation can be formidable and go beyond the scope of this book, and, indeed, most others.
