Yakov lanczner, Merav Joseph
The goal of the project is to create an eye sketch using a dynamic programing algorithm.
A short clip explaining our project
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.
By using some extra memory to remember the answers to already-seen answers,
the run-time can be vastly decreased.
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):
Imporvments to the original algorithm: