# Unique eye sketch

#### 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 sub-problems,
but these sub-problems are often repeated across many different cases.
the run-time can be vastly decreased.

Algorithm description:

Our input (source image):

1. 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.

2. Then the eye image is recursively divided into sectors to find the optimal eye partition.
each sector is rotated parallel to X axis.

3. Each sector is then recursively divided to find optimal number of segments and their position.

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

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

6. 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.

7. Our output:

Imporvments to the original algorithm:

1. 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.
2. Graph data set was created to support the 3d representation.
3. 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”). 