From: ted.dunning@gmail.com   
      
   No, it doesn't come with source.  Running it or its cousins is   
   instructive, however.   
      
   If you want to detect lines in a raster image, then a good place to   
   start is with the Hough transform.   
      
   The way that this works is that each lit pixel can be part of any line   
   that goes through that point.  If you express these lines as a linear   
   expression,   
      
       y = a + b * x   
      
   then each point can belong to a set of lines which are described by the   
   two parameters that are solutions of y_0 = a + b * x_0.  You might   
   prefer to use theta = tan^-1 b, but the game is the same.  Each point   
   contributes some mass to all of the lines that it might be part of and   
   those lines are represented either as lines in (a,b) or curved figures   
   in (a, theta) space.   
      
   If take all of the pixels in your original image and convert them to   
   pixels in Hough space, then the brightest points in Hough space   
   represent linear features in the original image.  Pick one or more, use   
   those lines to describe the original image (or segments of those lines)   
   and repeat until you have a good approximation of the image.   
      
   The result is an image composed of lots of nearly parallel features   
   clustered around linear features of the image.  These linear features   
   are points in Hough space that can be clustered (or you can define a   
   simple metric and cluster directly).  Now you have a representation   
   with a decreased number of line segments.   
      
   The final step in a simple version of a line finder is to group   
   neighboring but non-parallel segments to build splined representations   
   of curvilinear segments.   
      
   Getting to this simplest state isn't all that hard, but it does take a   
   fair bit of grunt work to get it all just right.   
      
   The next level of theoretical interest is to think of the thing that   
   originally caused the drawing you are trying to digitize.  That   
   original thing had a probability distribution and that distribution and   
   the cultural conventions used to produce drawings give very strongly   
   peaked distributions over the space of all possible images.  For   
   instance, an drawing that is mostly white paper is much more likely   
   than one that is mostly black (I am talking line drawings here, not   
   general images).  Likewise, it is highly probable that there is a   
   considerable peaking of line orientations around something that is   
   nearly horizontal and something that is at right angles to this.   
   Again, circles and ellipses are more common than other curved shapes   
   and lines normally have fairly constant width.   
      
   All of these probabilistic considerations allow you to work in the   
   space of abstract drawings and build an algorithm that finds something   
   like an MAP estimator of the original drawing.  This sort of noisy   
   channel drawing extraction is /much/ harder to build, but has   
   potentially much higher performance.   
      
      
      
   Oh.... you should also look at spectral clustering.  It can be very,   
   very helpful as a pre-processing step.   
      
      
   Good luck.  Share your results.   
      
   [ comp.ai is moderated.  To submit, just post and be patient, or if ]   
   [ that fails mail your article to , and ]   
   [ ask your news administrator to fix the problems with your system. ]   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)