Yakov lanczner, Merav Joseph
The goal of the project is to create an eye sketch using a dynamic programing algorithm.
Demonstration:
A short clip explaining our project
Code:
The algorithm can be found Here.
Our Main code can be found Here.
Workspace:
Dynamic programming:
Applied to algorithms which need to solve a problem by considering smaller subproblems,
but these subproblems are often repeated across many different cases.
By using some extra memory to remember the answers to alreadyseen answers,
the runtime can be vastly decreased.
Algorithm description:

Given an image of an eye, convert its data to a 3d representation:
X and Y axis are the coordinates and Z is the color data. 
Then the eye image is recursively divided into sectors to find the optimal eye partition.
each sector is rotated parallel to X axis. 
Each sector is then recursively divided to find optimal number of segments and their position.

For each sector a plane that minimizes the distances of the (X,Y,Z) points from the plane is computed.

A dynamic programing algorithm is used in order to calculate the optimal partition to k segments.

In order to find the ideal number of partitions for the whole eye and for each sector (slice)
a binary search is used to find the “elbow” point,
the point that is farthest from the line that connects (1,f(1)) with (n,f(n))=(n,0),
where (1,f(1)) is the sum of distances from the ideal plane of partition to 1 segment,
and (n,f(n)) is the sum of distances from the ideal plane of partition to n segments.  The code of the algorithm “the Shortest path with exactly k edges in a directed and weighted graph”,
was modified to python and combined into the project’s code.  Graph data set was created to support the 3d representation.
 The different stages explained in “Algorithm description” section were all implemented,
including: 2d and 3d implemntation, modified binary search, combining algebraic regression,
mathematical calculations(plane, distance from a point to a line, “finding the elbow point”).
Our input (source image):
Our output:
Imporvments to the original algorithm:
Contact us:
Yakov lanczner: yakovlan88@gmail.com
Merav joseph: meravtyt@gmail.com