11-th Summer School on Image Processing 3-12 july 2003 Timisoara, Romania
the team formed by the four of us the projects Several solutions for achieving the vectorisation Our achievments future improvments, comment

         1. STEP: SLICING THE IMAGE INTO A SET OF BINARY IMAGES

         MAIN ALGORITHM:
  • select the 1st unprocessed pixel and examine its colour (seed pixel)
  • take all the pixels that have almost the same colour (*)(* means: described later) , and mark them as processed they will have the code 1 in the binary image, and all others are 0
  • vectorize the gained binary image
  • do it until all pixels are processed

         SELECTION OF PIXELS WITH ALMOST THE SAME COLOUR BY GAINING BEST FITTING CLUSTER:
  • create a distance image as follows:
    measure all pixels' distance from the seed pixels as vectorial distances in the RGB cube. The used metric is a parameter, we have L1, L infinite and Euclidian metrics yet. Using different metrics changes the shape of the thresholding object used in the RGB cube
  • get the histogram of the distance image
  • search the minimal threshold value with the help of the histogram (*)
  • threshold the image by letting only survive the pixels that are closer to the seed than the threshold. They'll gain the value 1, and all others gain the value 0.

         SEARCHING FOR THE MINIMAL THRESHOLD VALUE:
  • we use a new parameter, the Vertical Threshold (VTH), which shows what do we call a high difference in the histogram
  • 1. MinThreshold = Threshold (original)
  • 2. search for all local minima and maxima in the range of [0, MinThreshold]
  • 3. If any of the maximas has a minima after them, look for the difference between the minima and the maxima. If it occurs to be larger than the VTH, the minima becomes the minThreshold.
  • 4. repeat it from step 2, until no more maxima occurs in the [0, MinThreshold] interval



         The vectorisation solutions:

         During these 10 days, we came up with several solutions. Forced by the fact, that the actual solutions did not work porperly.

         Idea 1.

         The first idea was to connect all neighbouring pixels with small vectors, and afterwards try to "guess" the shapes. So small vectors should be connected to be lines, if they formed a single long vector (line). This procedure had the leak, that forming long vectors was more difficuly then we tought. The small vectors wich formed the lines required an algorithm which included them into the long vector (line) even if they were not collinear, or even if they were collinear and had some distance between them. This had the consequence that at the intersections have appeared some small vectors, and they made more difficult finding the original crossing vectors. After a few days work we concidered, it was better to find another way to complete the goal.         

         Idea 2.

         The second idea was a lot more easier then the firstone.
         At first, we search the image for a pixel. Go line by line, from up to down, starting from the (0,0) (upper left) corner. When the first point is found, we test, if it has any neighbours, and according to the number of neighbours, we take different actions:
         1. 1 neighbour: the pixel is an end of one line.
         2. 0 or more than 1 neighbours: no action.
         The saved points are line endigs, so the algorithm tries to connect all the points to each other, and in case, he finds a line between them, then saves the line's coordinates, and erases the points from the list, and also removes the line from the original image. This way we'll obtain the list of lines and an image which doesn't contain any lines.
         Afterwards, we search the image for a 90° corner, the same algorithm, as finding the lineendings (90° corner means, the point in the middle has 2 neighbours forming 90° angle). Any corner found will be saved in a separate list.
         As in the case of the line identifying, the algorithm tries if he can close a rectangle, trying to connect each corner with every other. In case of finding a rectangle, the corners will be removed from the list, and the rectangle will be inserted in a separate list, meanwhile it will be removed from the image.
         Afterwards, we search the image for other corners, with the same algorithm written above. Any corner found will be saved in a separate list.
         As in the case of the rectangle identifying, the algorithm tries if he can close a triangle, trying to connect each corner with every other. In case of finding a triangle, the corners will be removed from the list, and the triangle will be inserted in a separate list, meanwhile it will be removed from the image.
         The remaining image will contain the shapes which were not described above: circles, arcs, polylines, polygones and curves. These shapes can concidered as beeing future improvals.