Copyright © 2014 by Intelligent Systems Laboratory, Computer Science Department, Technion - Israel Institute of Technology, Haifa 3200003, Israel. All rights reserved

Extreme Points

Extreme PointsBy: 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.


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


Extreme Points  Extreme Points 
 Extreme Points  Extreme Points
 Extreme Points  


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

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 K-Means 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 K-Mean algorithm:

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

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 K-Mean algorithm)



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