Hall of Fame: INF555 Projects (2008)

Supervisor: Frank NIELSEN (Ecole Polytechnique, LIX) | Visit the course home page INF555: Fundamentals of 3D

Projects at a glance:
[Image retargetting] [Hyperbolic image browser] [Robust homography] [Compass operator] [Locality-Sensitive hashing] [Poisson image editing] [Grabcut] [Quaternion interpolation]
  • Compass operator: The goal is to trace the contour of an object in a color image, using the following simple compass operator: At a given position and for all possible orientations (choosing circular window centered at that position), we calculate the gray/color pixel neighborhood difference between the two parts of the disk window. We choose the extremum discrepancy as the edge orientation and follow the contour of an object by moving properly according to the picture below. The visual difference between the two half-disk windows at a fixed position and orientation is computed using the Earth mover distance (EMD): A k-means clustering algorithm is run to get a color codebook yielding a histogram distribution on each side of the split disk. The EMD on these histograms are then computed.

    Manon PICARD
    M. Ruzon and C. Tomasi
    Edge, Junction, and Corner Detection Using Color Distributions
    IEEE Transactions on Pattern Analysis and Machine Intelligence, V. 23, No. 11, pp. 1281-1295, November 2001.
    More on the generalized compass operator
  • Robust homography computations: Two pictures taken from the same nodal point by an ideal pinhole camera are related to each other by a projective transformation called an homography. The usual way to stitch pictures is to first extract point of interests (say, Harris-Stephens low-level corners) and then match these features using a RANSAC procedure. Once inliers and outliers are identified, we then seek to estimate the homography related these two noisy point sets. The statistical optimization of Kanatani allows to derive deviation bounds as well.
    Laurent SIFRE

    Homography with deviation pair shown in grey:

    Kanatani and Ohta
    Accuracy Bounds and Optimal Computation of Homography for Image Mosaicing Applications 
    ICCV 1999
  • Poisson image editing with application to seamless closing. Selecting and copy/pasting object of an image to another image is usually done by careful taking the matte of a contoured object that is then pasted on the target image. Another approach consists in roughly enclosing the region of interest in the source image and pasting it onto the target image. Doing so obviously creates visual artefacts. A better method consists in reconstructing the image portion from the mixed source/target ROI gradient with boundary conditions set by the target image.

    Patrick Perez, Michel Gangnet, Andrew Blake: Poisson image editing. ACM Trans. Graph. 22(3):. 313-318 (2003). 
  • Iterated graphcut for object selection in images (also known as Grabcut). First, a trimap is initialized that defines the pixels of the background/foreground and the unkown. Background/foreground Gaussian mixture models (GMMs) are learnt for both background/foreground parts, and a graph cut operation is performed changing the labelling. This operation is repeated until convergence. Users may potentially steer the segmentation by giving foreground/background labels. Grabcut requires carefully implementing kmeans, expectation-maximization, and max flow routines. (The number of components of the foreground/background GMMs can be learnt using G-means, NIPS 2003) Bastien Jacquet

    Download the zip file and run it locally with Eclipse (otherwise there is a memory stack overflow that can be overcome by reducing the image size) See the note at the bottom of this page to increase the Java memory heap.
    (includes the Jama matrix library)
    C. Rother, V. Kolmogorov, A. Blake
    GrabCut: Interactive Foreground Extraction using Iterated Graph Cuts. 
    ACM Transactions on Graphics (SIGGRAPH'04)
  • Click ’n Drop: A convenient system that combines both Grabcut for object selection and Poisson image cloning for pasting.
    (requires Jama)
    Edouard GRAVE

    Download this zip, unzip all files and double click the .bat file.
    Foreground selection is done by mouse dragging (and background with SHIFT+mouse dragging).
  • Quaternion interpolation for animation (requires JOGL, Java for OpenGL)
    Animating (smoothly moving and rotating) a teapot on a smooth curve.

    Demo it using this applet and this applet.
    There is the arcball interface so that you can conveniently rotate in 3D this animation.
    Ken Shoemake
    Animating rotation with quaternion curves
    Computer Graphics, 19, pp. 245-254. SIGGRAPH'85

    By default, applet in browsers have only 2MB memory; that is too short for manipulating large (or many) images. In Eclipse, you can set the size of the Java heap as follows:
     *  run as
     *  open run dialog
     *  onglet argument
     *  VM argument
     *  -Xmx256M
    This set the heap size to 256MB; Fortunately, that should be enough!
    (c) 2009 Frank Nielsen, All rights reserved.