Technical reference

The main part is found in the subdirectory JoshiMain. When compiled and build using the ANT script this will result in a JoshiMain_xxx.jar file. The main part is, as mentioned in the introduction of this chapter, responsible for the actual shape recognition. This process is split into multiple steps as shown in the figure below.

Figure 1.1. An overview off Joshi.

Joshi uses an image to polygon converter which does not support color nor does it support grey scales. Therefor images have to be filtered to black and white. White is assumed to be the background color whereas black is assumed to be the foreground color. This filter is just one of multiple steps before a polygon is parsed from the image. Hereunder is the list of steps that Joshi takes to create the polygons.

The StartStopContext is responsible for feeding the PolygonTracker. It does so by creating StartStopShapes that allow the PolygonTracker to retrieve single circulair paths consisting of points. The StartStopContext starts by scanning each line from the left to the rights searching for variations from white to black and from black to white. Since white is assumed to be the background color it starts with white. Every change from white to black is considered as a start value which is always followed by a change from black to white (after the most right point the background color is expected) which is considered as a stop value. These two values (start and stop) are stored in a StartStop instance which is the stored in the StartStopLine created for the specific line. These StartStopLines are storead in an array of which the length is exactly the height of the provided RGBArea (read image). If all lines of the area are scanned and the StartStopLines are filled with the resulting data then theoratically the image could be recreated using these array of StartStopLines.

Figure 2.1.  An example showing the StartStop values per line for the letter A.

Having these StartStopLines filled with StartStop values we can start to combine them. StartStopValues are combined when they are, either directly or indirectly, connected with eachother. To better understand what is meant by this you should imagine opening your favorite bitmap oriented paint program draw some random stuff on it with black, select the fill option and select the color green. Finaly point the mouse on a black dot and start the fill. All dots that now appear green would be combined to a single StartStopShape. Though I could have build a fill routine this is not how Joshi approaches this problem. Instead it searches for StartStop values that overlap eachother. Two StartStop values overlap if the lines they are on directly follow eachother and if one of the start values lays in between the start and stop value of the other. For each StartStop value it is valid that multiple StartStop values can overlap it on both the preceding line and the succeeding line. Therefor a stack is used to push these overlapping StartStop values that are found. Once a StartStop value is analyzed for overlapping by other StartStop values it is being marked as done and put in the pending StartStopShape. StartStop values being marked will never be pushed on the stack again. If the Stack becomes empty the current pending StartStopShape is finished and the algorithm searches the array of StartStopLines for another unmarked StartStop value which it pushes on the stack and repeats the above procedure. In the end all StartStop values will be marked and a list of StartStopShapes created.

The PolygonTracker provides the method called track that converts a StartStopShape into a Polygon. The PolygonTracker is responsible for converting start-stop-shapes into polygons. The convertions runs in three stages.

The PathIterator provided by the StartStopShape class is a double iterator. The outer iterator iterates over the multiple ciruclair point-lists a StartStopShape can be made up off. I.e. the character 'S' has a single circulair point-list, the character 'e' has two circulair point-lists and the character 'B' has three point-lists. The inner iterator iterates over the points in the StartStopShape that when enlisted result in a single circulair point-list. Thus the StartStopShape itself does not maintain this list, instead the PathIterator calculates the order in realtime using an specific algorithm to extract this info from the start-stop infos stored in the StartStopShape. In order to seperate the lists, those that are provided by the outer iterator, the PathIterator markes every point it passed. The outer iterator will search, from the top-left to the right-bottom, for the first unmarked point in the StartStopShape which will be the first point of the list that follows. If no more unmarked points are left then all work is done for the PathIterator and no more lists will follow. Note that the first unmarked point of a StartStopShape, which is completely at the top-left, is always a point that is on the outer polyline of the polygon. All that follow are inner polylines (or you could say holes) of the polygon.

A Circulair point list provided by the PathIterator could directly be used to create a polyline. This would create a polyline that has lots of points, lots of lines to be drawn and needs a lot more calculations in a later stadium where the polygons are being compared. To improve the quality of the polyline Joshi reduces the number of points by detecting which points lay approximatly on the same line. The pseudo code for reducing the number of points in the point list is listed below

Distortion is calculated by taking the distance of each point to the line and accumalating them into either a left-total or a right-total. The absolute difference between the left-total and the right total is then cosindered to be the distortion.

Below is a small example how to use the PolygonTracker on a BufferedImage.

   // create a BufferedImage
   BufferedImage image = new BufferedImage(100, 100, BufferedImage.TYPE_INT_RGB);
   
   // draw a triangle on it
   Graphics gfx = image.getGraphics();
   gfx.setColor(Color.WHITE);
   gfx.fillRect(0,0, image.getWidth(), image.getHeight());
   gfx.setColor(Color.BLACK);
   int xcoords[] = { 0, 100, 0 };
   int ycoords[] = { 0, 50, 100 };
   gfx.drawPolygon(xcoords, ycoords, 3);
   
   // create a StartStopContext from the image
   BufferedImageArea area = new BufferedImageArea(image);
   StartStopContext startStopContext = new StartStopContext(area, 1f);
   
   // get the first StartStopShape from the context
   StartStopShape shape = startStopContext.iterator().next();
   
   // create a PolygonTracker instance and run the shape trough it.  
   PolygonTracker polygonTracker = new PolygonTracker();
   Polygon polygon = polygonTracker.track(shape, 1f, shape.getLocation());
      

Pseudo units are a combination of units and parts of units. Whereas the unit represents just a single shape the pseudo unit represents complex combination of shapes. The unit is always a copy or an representation of the image a pseudo unit must not be that. A pseudo unit consists of one or more pseudo parts. Each pseudo part holds a reference to at lease one unit. A pseudo unit can be interpreted as a programm describing how a PolygonSet is created. Each PseudoPart is a single programm-command which appends zero, one or more polygons to a PolygonSet. A PolygonSet is a class holding a collection of polygons.

The RectangularAnalyzer tries to detect lines by looking at the distances and angles between the polygons. Scanned text should contain text only otherwise the analyzer gets confused. The RectangulerAnalyzer Creates a UnitNodeMap with for each Unit the relation to the other units