The goal of this project is to build a system that performs low-level stroke interpretation, smoothing, beautification and, optionally, some low-level recognition.  You will find and implement algorithms in the literature to solve these problems.

The idea behind this assignment is for you to get some experience with low-level stroke processing and the challenges involved.  Exactly what you implement will depend a little on what you decide to implement, so this problem description is pretty general.  It lists a set of high-level guidelines, tasks and expectations, but there is a lot of room for experimentation and creativity.  As always, I list plenty of extensions that I encourage you to play around with.

NOTE: This assignment is currently a "work in progress" so that we can start talking about it in class.  It will be refined over the next week based on our discussions.

Basic Functionality [60 points]

You should implement a WPF application that beautifies the users strokes in the following way:

• Finds corners in the users strokes and approximates the potions of the strokes with lines (you may handle curves for extra-credit)  [20 points]
•  Detects the following constraints between lines in the sketch (note: I added congruence and object alignment to make it feasible to draw things like squares and rectangles easily) [10 points]:
• Two types of connection:
• point to point connection: Two or more stokes share an endpoint, or one stroke forms a closed loop
• point to line or curve connection: A stroke begins or ends on a curve or line
• Parallelism and perpendicularity 
• Vertical and Horizontal alignment
• Congruence (NEW)
• Object Alignment (NEW)
• For extra credit, you may implement any other constraints that you would like
• Cleans up the sketch by adjusting the newly drawn stroke to fit the detected constraints (note: the new line will usually be over constrained: see below).  In the case where the user has drawn a poly-line, the segments in the poly-line may be processed one at a time, in the order in which they were drawn. [25 points] 
• Lets users sketch directly, OR load data in ISF.  In the case where data is loaded in, you can assume that the data will contain timestamp information on each of its points.  Use the GUID 
  "86280C5E-BA45-4faa-D6B6-1279039FC1F4" to get the timestamps out of the points.  The timestamps will be unsigned longs (ulong or UInt64).  I have also provided some test data (see below under testing and writeup). [10 points]
• Allow the user to undo their previous actions and/or delete objects they have drawn. [5 points]

Notes on Basic Functionality

• Because of ambiguity in the sketch, you will almost certainly have an over-constrained situation.  That is, there will be more than one possible set of constraints that might be met.  For the basic system, you can just choose the best one (or one of the best) arbitrarily.  For extra credit, you can build an interactive system that relies on user feedback (see below).
• You will write your own constraint solver.  Don't try to do anything overly complicated.  I recommend following the approach given in Igarashi's "Interactive Beautification" paper.
  
• You should provide feedback by replacing the user's strokes with shapes cleaned up shapes, but these shapes do not have to be interactive and you do not have to support any sort of gestural interface.
• You may choose to consider only a subset of the strokes on the page at any one time for your constraint detection/satisfaction.  Explain how you choose this subset and why in your writeup.
• You may not use any of the built-in gesture recognizers for this assignment.

Note that the points for the above section are given only for correctness.  

Advanced Functionality

For extra credit, implement any or all of the following extensions:

• Go beyond just lines, and detect circular arcs and/or Bezier curves and fit them to the users strokes.  Implement as many constraints as you can for these new shapes (some constraints will be quite difficult to detect and enforce).
• Design an interactive beautification system where the user helps the system resolve ambiguities.  Include a gestural interface of your design for editing the sketch (e.g, resizing and moving pieces of the sketch, deleting lines or parts of lines, etc).
• As a preprocessing step, simplify "messy" drawings into simple line drawings, and then beautify these drawings as above.  By "messy" I mean a sketch with a lot of over-tracing--that is a sketch that "looks sketchy"
• Any other related extension of your choice.

Testing and Writeup [40 points]

A significant part of this assignment is analyzing how well your system works, in addition to implementing the above algorithms. In your writeup, in addition to a basic README, I am looking for two things: a justification of your approach, and an analysis of its strengths and weaknesses.

Readme file

In a file called README.txt describe how to run your program, any missing features or bugs that you are aware of, and any extra credit that you implemented.

Design/approach Justification

In the first part of your writeup, you will analyze your design.  In a file called "Design.txt", write up answers/explanations for the following:

1. How did you approach each of the technical problems above (corner finding and beautification), and why?  What were the most challenging parts of this task and how did you solve these challenges?
2. Give an overview and critique of your design from a software engineering perspective.  How did you organize your data?  What worked well and what would you change if you had to do it over again.
3. What was the most difficult part of this assignment and why?

Testing and Results

In the second part of your writeup, you will report on how well your algorithms perform.  For this assignment we will focus on qualitative results, but for extra credit you have the option of also providing quantitative results.

First, select the data you will test on.  While some of your discussion can be based on your own use of the system, you should also include results on pre-collected data and interactive sessions with someone else.

Pre-collected data
Here are two datasets that you can use in your testing:

• Family tree data set:  Simple drawings of family trees
• Simple shape data set: Single geometric shapes drawn in isolation

The family tree data may contain some ellipses, but you should be able to find data that does not.
Select several sketches from the above datasets OR collect your own data by asking your friends to draw sketches in your ink collection application that you wrote for assignment 1.  5-10 sketches should be enough for this part.

Run the files through your program and note what works well and what doesn't.  How many corners does it miss?  Does it find too many corners?  Can you identify when this happens?  What constraints does it find reliably?  Which ones does it miss?  Etc...

Interactive data
Now, get a friend or two to interact with your application for a few minutes and again note what works well and what doesn't.  Also observe whether your friend is able to adjust to your system to improve the system's performance.

Write up all of your results in a file called Results.txt.  Include your observations of both datasets in your results.  You will probably have 1.5-2 pages of results.

Criteria

Your writeup will be graded on the following criteria:

• Overall completeness: Did you provide all the information requested above?
• Soundness/completeness of your Justification: Is your design justification compelling (both for your algorithms and your code)?  Are there solid reasons for your decisions?  Even if your design is not ideal, do you clearly identify what could be improved?
• Depth and Breadth of results: Do you discuss your results at a non-trivial level in order to illustrate the high-level strengths and weaknesses of your algorithms?  Have you tested your code on a wide variety of real-world examples?
• Clarity of expression: Is your writeup easy to read and grammatically sound?