################################################################################
Multiple Plane Detection in Image Pairs using J-Linkage
Reference Implementation
David F. Fouhey (dfouhey@cs.cmu.edu)
################################################################################

1. Administrative matters

    This is a reference implementation of Multiple Plane Detection in Image 
    Pairs using J-Linkage [1]. To use this code for research purposes, we ask 
    you to cite [1]. This is licensed under a modified BSD license (see 
    License.txt). We would appreciate it if you let us know that you are using 
    our code to keep track of interest in our work.

    Please note that the last steps in [1] are not called in the code; we found
    that in practice, the robust fitting and stability checks do not aid 
    performance enough to merit inclusion. We have, however, included code to 
    do both of them (RobustFitting.py and StabilityCheck.py).

2. Software matters

    This code is written primarily in Python, with some support code written 
    in C. It was developed on Linux; if you want to run it in a non-Unix 
    environment, you will have to modify it in a number of places (SIFT.py, 
    which interacts with the SIFT keypoint program, and SpatialAnalysis.py,
    which calls a Delaunay triangulator).  

    This code depends on:

        1)  David Lowe's SIFT demo program
                (See: http://www.cs.ubc.ca/~lowe/keypoints/)
            
            YOU WILL NEED TO DOWNLOAD THIS. 
    
            If you wish to use another program or descriptor, you must modify 
            SIFT.py to call it. You will also need to modify the keypoint 
            matcher program in supportCode/ or precisely imitate Lowe's output.

        2)  Numpy for least-squares homography estimation. If you wish to use
            another routine, modify homography.py.

        3)  OpenCV Python bindings for outputting images and converting images
            to pgm for SIFT. If these are not available, the results will not
            be visualized. You can also fall back on imagemagick for converting
            images to pgm (See SIFT.py).

    To compile the support code, just run make the main directory. The support
    code includes a brute-force keypoint matcher and code to compute the 
    Delaunay triangulation of 2D points. 


3. Usage

    Get SIFT and place the executable ``sift'' in this directory.
    
    First, compile the support code
        make 
    Now run it on some test images
        ./mpd.py exampleImages/input1.jpg exampleImages/input2.jpg 
    You should see (exact numbers will vary):
        Finding keypoints...
        4389 keypoints found.
        Finding keypoints...
        3494 keypoints found.
        JLinkage Cluster Count: 6
        Filtered Cluster Count: 3

    All output will be in output/ . If you have OpenCV, you should have images
    visualizing the output of each step. If you do not, you will only have
    output/out.txt. This contains an easily parsable file giving the final 
    output of the method. Each line starts with a number n indicating which 
    plane hypothesis the line belongs to; at the beginning of each section is 
    the homography that describes the planar transformation of the form
        n:H:a b c d e f g h 1.0
    where the entries of the homography are written row-by-row. This is followed
    by lines of the form 
        n:p:X_1 Y_1 X_2 Y_2
    giving the supporting correspondences where (X_1, Y_1) is the location of
    the correspondence in image 1 and (X_2, Y_2) is the location of its 
    corresponding location in image 2.

    An example output is given here:

        1:H:-2.358749 -0.117694 1281.568349 -0.609765 -0.666372 448.424585 -0.002157 -0.000152 1.000000
        1:p:802.560000 291.970000 832.390000 303.640000
        1:p:805.720000 286.170000 834.830000 298.980000
                    ... more lines ...
        1:p:746.960000 261.000000 786.430000 277.510000
        2:H:1.053014 0.134924 91.154959 0.054958 1.031752 13.503754 0.000152 0.000211 1.000000
        2:p:965.580000 277.190000 948.400000 291.890000
        2:p:680.390000 310.340000 726.950000 317.430000
                    ... more lines ...


    Eight images are provided for you to play with in exampleImages; more may 
    be found at:

        http://www.cs.middlebury.edu/~dfouhey/ICPR2010/index.html

4. Listing
    
    The code itself is only 1347 lines, but it is always helpful to have a 
    listing of what is provided and what each file does.

        common.py
            Miscellaneous functions
        exampleImages/
            A directory of example images for you to play with
        GlobalMerging.py  
            The global merging scheme in [1]
        homography.py  
            Code to compute least-squares homography estimates
        JLinkage.py  
            An implementation of J-Linkage
        License.txt  
            The license this software is distributed under.
        Makefile  
            Quick makefile to compile the support code
        mpd.py  
            Main code to perform plane detection
        README.txt  
            This file
        RobustFitting.py  
            An implemtation of the iterative robust-fitting procedure
        SIFT.py  
            Code to interact with SIFT
        SpatialAnalysis.py  
            Code to do the Delaunay-triangulation-based spatial analysis
        StabilityTest.py  
            An implementation of the proposed stability test
        supportCode/
            keypointMatcher.c
                A brute-force keypoint matcher
            triangulate.c
                A program that calculates Delaunay triangulations


References:

[1] D. Fouhey, D. Scharstein, and A. Briggs. Multiple Plane Detection in Image 
    Pairs using J-Linkage. In Proc. 20th International Conference on Pattern
    Recognition. Pages 336-339. 2010.
