TODO

a. add option -m . for mathcing images provided as extra arguments rather than using an ID.



You can help the ShapeMatcher project by doing one (or more) of the following things and getting 
in contact with me by sending an email to dmac@cs.toronto.edu


1. Develop a "Free LEDA Lite" library to replace the commercial (but originally free and open)
   LEDA library. It would be "Lite" in the sense that the ShapeMatcher uses only very few functions
   provided in LEDA. The only tricky one to implement is the bipartite graph matching function 
   (although code for it can be found on the web and there are plenty of textbooks and papers 
   on the subject, plus the LEDA book itself "LEDA: A Platform for Combinatorial and Geometric
   Computing"). Most of the graphical LEDA function can be easily implemented in a platform 
   dependent library. The idea would be to write a FreeLEDA with the same structure (ie, function 
   prototypes, directory tree, header file names, etc) so that it can be used instead of LEDA 
   without modifying anything in the actual ShapeMatcher code. One possible
   place to start for implementing the template GRAPH data structure is the in Boost library:
   "How to Convert Existing Graphs to BGL": http://www.boost.org/libs/graph/doc/leda_conversion.html


2. Develop a visual interface as an alternative to the current command-line one. 
   You would probably want to make ShapeMatcher be a WIN32 Windows application rather 
   than a console. See the main(...) function in ShapeMatcher.cpp. There you'll find 
   a sketch code for converting it into a WinMain(...) function. Changing this would 
   allow any visual interface or front-end to call ShapeMatcher as a process without 
   having to deal with a console. You'll have to resolve how to redirect cout, cin 
   and cerr, so that they talk to your interface.


3. Improve performance of Flux Skeleton algorithm

   The Flux Skeleton developed at McGill by Kaleem Siddiqi's group is the
   best skeletonization code in terms of the quality of the skeletons that it
   yields. In this algorithm, not only the x-y coordinates of the skeleton points
   are accurate but more importantly their radii are too. The problem with
   this code is that it is really slow. The good news is that it can be fixed, since
   the main reason why it's so slow it's because no once cared about performance when it
   was written. Here are some thoughts about a possible way to go about improving 
   the code.

   The code is slow simply because the guys that wrote it used a very brute force 
   approach to "thin" a shape. The problematic thinning method iterates through all 
   the pixel in a shape looking for the closest on the shape boundary or something 
   like that. So, the idea would be to have a more efficient data structure to
   quickly find the closest points or some other less brute force
   strategy (e.g., using the ANN library already included and use elsewhere in 
   the project). The time-consuming problem is located in one single function, which 
   can be changed without understanding much about what is going on elsewhere in the code.

   This is what we know about the super slow, brute force function:

   It starts in the method create_shape_DivArr in the file
   DivergenceSkeletonMaker. This function traverses all points in the
   image and takes considerable time for actual object points. It calls
   getValue in the DivergenceMap which in turn calls getGradValue in
   DistanceTransform, which in turn calls getValue in itself which calls
   distToPt in DiscreteSegCurve (... hmmm...) and this function seems to
   be looking for the smallest distance between this curve (all points of
   the curve) and the give point (given in create_shape_DivArr). I guess
   there is always just one curve though; the curve that bounds the
   object.


4. There are a number of subproject to do related to making certain parts of the
   code run in parallel, such as in a graphics card (eg, the thining algorithm in 
   the FLuxSkeleton) and on multicore processors. If you are interested in doing this,
   eg, maybe for a course project, let me know and I'll give you more details about 
   how to proceed.