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:
[Hyperbolic image browser]
[Poisson image editing]
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.
- Image retargetting (semantic-based image rescaling): Given a source image and a target resolution,
produce a target image (with the prescribed dimension) so that the output image preserves as most as possible the
(semantic) of the source image.
For target resolution smaller than the source resolution, the idea is to iteratively remove horizontal/vertical seams
(with respect to 4-connexity). For increasing resolution, we rather duplicate seams. (Each removed hor./ver. seam let decrease the resolution hor./vert.
by exactly one pixel).
Appropriate seams are selected using the optimization technique of dynamic programming on pixels valued by their "interests"
(discrete Sobel gradient, entropic measures, etc.).
By manually painting regions of interest with low/high energy, we can enforce the selection of seams
to remove/pass through the selected regions of interests and therefore either remove objects or necessarily keep some portions of the image unchanged.
- Olivier MANGIN
Application to object removal:
Java application of Olivier MANGIN (download this zip and execute the .bat to go through the sample demos)
- Patrick NOLLET
Java applet of Patric NOLLET
See also http://www.seamcarving.com/
Seam Carving for Content-Aware Image Resizing
ACM Transactions on Graphics, Volume 26, Number 3
Further links On the web:
- Image browser in the Poincare hyperbolic disk:
The layout of images in the Poincare disk is done using the Sammon's algorithm (nonlinear projection) for
(MDS) in hyperbolic space.
One application is to search for images with a keyword (say, Paris or Polytechnique in the screenshots below)
and visualize purposely the image collection results in the hyperbolic Poincare disk representation (that is fully visible in the rectangular screen).
- Cyprien PINDAT (used Yahoo! image search API to collect images from text queries)
Download this zip and execute the .bat to run the program and make your own queries.
- Bodgan PRISACARI
Download this zip and execute the .bat to run the program to interactively navigate inside the Poincare disk with a thousand of boxes.
Interactive hyperbolic image browsing - towards an integrated multimedia navigator.
Jörg Walter, Daniel Wessling, Kai Essig, and Helge Ritter.
In ACM MDM/KDD Multimedia Data Mining and Conf Knowledge Discovery and Data Mining, Philadelphia, USA, August 2006.
Link on the web: Interactive Visualization and Navigation using the Hyperbolic Space
- Locality Sensitive Hashing(LSH):
For performing fast approximate nearest neighbor point queries, hash the high-dimensional points with a family
of hash functions so that collisions are very likely
to occur if colliding points (stored in the same bin) are geometrically close together.
The goal is to compare the LSH method with other tree branch-and-bound nearest neighbor algorithms (kd-trees, metric ball trees, vantage point trees) that we studied in INF555.
Application to texture synthesis using the Efros-Leung raster scan texture synthesis algorithm is presented.
Larger neighborhood (point dimensionality):
Download this zip and run locally so that the applet finds properly the source image
(Note that this demo takes time, so please be patient and follow the processing stage in the java console).
Link on the web: LSH home page
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.
Homography with deviation pair shown in grey:
Kanatani and Ohta
Accuracy Bounds and Optimal Computation of Homography for Image Mosaicing Applications
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)
- Girand NOE
- Arnaud RAMEY
(download, install and run the package Poisson Filler)
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.
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.
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
This set the heap size to 256MB; Fortunately, that should be enough!
(c) 2009 Frank Nielsen, All rights reserved.