Extreme Points
By: Gady Elkarif
Supervisor: Ph.D Ilan Shimshoni
Perspective Projection is a mathematical concept for projecting 3D space to a flat surface.
We know that parallel lines never meet, but they appear to do so: all the parallel lines in the same direction, in the image, meet in one point on the horizon line, called vanishing point.
The pictures we are working with are indoor scenes. They have many lines which are parallel to the x, y and z, directions. Each of them has a vanishing point, for all lines the direction parallel to that coordinate. This project is dealing with finding the Three Vanishing Points automatically by the computer.
Linear Perspective is a mathematical for creating the illusion of space and distance on a flat surfaceLinear Perspective is a mathematical for creating the illusion of space and distance on a flat surface.
THE ALGORITHM IS AS FOLLOWS:

 Finding the lines.
Given an image, we first run an Edge Detector program for finding lines in the program. Those lines represented by their pixels, and their equation founded by Least Squares Method.
EXAMPLES:
Creating the Elements:
Each line given from the edge detector, is represented by an object which includes:
1. Unique id.
2.Set of pixels recovered by the edge detector.
3. Line equation represented by 3 parameters a, b and c.
We compute for each line the real end points, by computing the intersection of two lines:
1. The line we computed for this set of pixels with the least squares method (a,b,c).
2. The orthogonal line to (1) which passes by the end points (first and last points) of the set of pixels.
This may help us to compute the distance from line to point.
The main loop:

 Repeat N times (N = 10000):
 Choose three pairs of lines randomly.
 Compute the three intersection points of the pairs.
 For each of all the lines:
 Compute the distance of all the three intersection points.
 Add to the sum S the minimal distance if it is less than a maximal value M (M = 12).
 End For each
 End Repeat
 Choose the three points which yields the minimal sum S.
 End
Partition the lines into the three points
Now we have from the previous section the three points we found, we want also to see the partitioning of the lines  each line and the point related to it, and also lines which are not related to any point (yellow lines)
For each of all the lines:

 Compute the distance D to each point, and get the minimal of them (the distance and the point).
 If D < MIN_D then: (MIN_D = 20)
 Add the current line to the point which yielded the minimal distance D.
 Else
 Add the current line to set of unrelated lines (the yellow lines).
 End If
 End For each
THE RESULTS:
Batch 1:
Batch 2:
Batch 3:
Batch 4:
Batch 5:
Powell Method (Optional)
The powell method is used for improving the precision of the resulted points.
In general the powell method is given a first estimate for the result we are looking for and a function which we would like to find the value which minimizes it.
The idea is to run the powell optimization function on the following function F(x, y):

 F(x, y)
 MAX_D = 20
 S = 0
 For each line do:
 Compute the distance D to the point (x, y).
 If D > MAX_D
 S = S + MAX_D
 Else
 S = S + D
 End If
 End For each
 Return S
 End F
The powell method is run as follow:

 We start with a point (x, y) and the set of lines we got from the partition method, those lines are the closest lines to this point.
 We run powell_func which operate the function func and which use the function F described above.
This is used for each points and its related closest lines, we use this method combined with the KMeans algorithm, such that in each step we partition the lines into the lines closest to the three points, run the powell function and then partition again ...
The KMean algorithm:

 While change do:
 Make a Partition.
 change = Compute new mean points. (see below)
 End While
 Return the points.
 While change do:
The compute new mean points method:

 For each point apply powell func function.
 If one of the three points has changed
 Return True
 Return False (No changes  Ending the KMean algorithm)
THE RESULTS
Image 5  Image 4  Image 3  Image2  Image 1  
45.1028  117.801  197.829  1057.2  28.704  965.45  97.224  419.736  1.53378  4340.3  Without Powell 
52.9892  7109.2  185.376  921.533  34.117  944.07  9951.54  67.2631  36.829  236.92  
27522  520.45  5453.2  52.154  37903.8  288.26  189.45  3350.8  26857.2  189.61  
38.7192  129.496  199.352  1080.5  31.274  980.86  102  430.148  11.442  4734.1  With Powell 
78.4348  7038  180.707  939.825  32.041  961.134  8284.07  30.068  27.328  236.18  
87134  1374.22  3480.4  2536.49  25778.5  2441.5  2489.47  121.761  25791.1  2426.26 