Federico Perazzi

Seam Carving - Content Aware Image Resizing

2010-05-12T20:44:00.000-07:00

Sometimes we have an image too big and we want to re-size it. Until recently we had two ways to handle this problem: scaling or cropping. Both techniques present drawbacks, in particular scaling leads to unnatural distortions, and cropping entails lost of content.

In 2007, Shai Avidan¹ and Ariel Shamir² presented an algorithm, called Seam Carving or Content Aware Image Resizing³, capable or reducing the size of an image, in a content-aware manner, that is without removing important information from the image itself.

Given as input an image and a target size the algorithm proceeds removing connected straight paths of unnoticeable pixel that blend well with their neighbors. The paths selection is based on an energy function, in my case a Sobel Filter, computed over the image. Once it has been given an energy value to each pixel, as the next step, the algorithm uses dynamic programming to find the minimum cost path connecting the image from top to bottom or left to right depending on the dimension we are reducing. This is really similar to what has been done by Alexei Efros⁴ in Image Quilting for Texture Synthesis⁵, where he uses the same dynamic programming algorithm to cut the boundaries of overlapping blocks of textures.

Finally the pixels that are part of the selected path are removed generating the final result.

*Original image by SBA73, http://www.flickriver.com*

*Left: scaled image. Right: seam-carved image.*

*Original image by TJP, http://interfacelift.com*

*Horizontally seam-carved image.*

References:
¹Shai Avidan, Mitsubishi Electric Research Labs (MERL), http://www.shaiavidan.org
²Ariel Shamir, Interdisciplinary Center and MERL, http://www.faculty.idc.ac.il/arik/site/index.asp
³Seam Carving, http://www.shaiavidan.org/papers/imretFinal.pdf
⁴Alexei Efros, Carnegie Mellon University, http://www.cs.cmu.edu/~efros
⁵Image Quilting, http://www.eecs.berkeley.edu/Research/Projects/CS/vision/papers/efros-siggraph01.pdf

PansaSE Project

2010-05-05T12:02:00.000-07:00

PandaSE was my last semester-long project I took part at the Carnegie Mellon Entertainment Technology Center. In this project we had the chance to work in conjunction with Walt Disney Imagineering on the open-source Panda3D Game Engine. In particular I worked on the shader system of the engine, adding support to all the NVIDIA Cg 2.0 inputs.

Here is a couple of posts I wrote on the Panda3D forum to introduce the new features to the commnutity:
1. Shader Inputs
2. Texture Arrays

This demo showcases the use of Hardware Based Instancing in conjunction with Texture Arrays.

More demos are available on the project website.

Stitching Photo Mosaics (including autostitching)

2010-04-18T09:46:00.000-07:00

The described algorithm generates a panorama from a set of adjacent photos and it is based on the paper Multi-Image Matching using Multi-Scale Oriented Patches but with several simplifications. The algorithm consider that the transformations between different images are projective and therefore the photographs should be taken from the same point of view but with different view directions. To align the images, the algorithm needs to recover the parameters of the transformation between each pair of images. In this case the transformation is an homography. This process involves several steps to make sure no outliers are present in the final set of points used to compute the projective transformation.

1. Interest Points Selection

A large set of interest points is initially generated by a Single Scale Harris Corner Detector (code provided by A. Efros), and then sub-sampled by the Adaptive Non-Maximal Suppression Algorithm, that based on the corner strength, retains only the points that are a maximum in a neighbor of a certain radius. In this way the ANMS ensures that the sample points are spatially well distributed over the entire image.

*In green, interest points etained by the ANMS algorithm.*

2. Feature Descriptors Extraction

Pairs of corresponding interest points from the two images, are coupled based on the similarity of the pixels around them. An axis-aligned 40×40 patch, is extracted around the location of each interest point. This feature descriptor, is subsequently blurred and reduced to 8x8 in order to make the feature matching process translation invariant in a range of about five pixels in every direction.

*Set of zero-mean feature descriptors.*

3. Feature Matching Process

This process consist of finding couples of feature descriptors that looks similar. This is accomplished through an exhaustive Nearest Neighbor Search where the distance is considered the l2-norm of the difference between pairs of descriptors. Feature descriptors are considered coupled only if their 1-NN/2-NN ratio is within 0.3 otherwise they are discarded. Setting the threshold at 0.3 highly reduce the number of outliers, making the final step almost useless.

4. RANdom SAmple Consensus

The RANSAC algorithm first randomly selects four interest points retained by the Feature Matching Process. Given these four interest points the algorithm computes an exact homography and then counts the number of inliers (couples of interest points) that agree with that particular transformation. This process is repeated until the number of inliers that agree with a particular homography computed through the four randomly selected points, is bigger of a user-defined threshold. In the last step, the RANSAC algorithm calculate a more robust least square homography, using all the inliers that agreed with the selected exact homography.

*Final set of points used to compute the homography.*

5. Image Warping and Blending

The least square homography computed in the previous step is utilized to warp one of the two images, that is subsequently blended together with the other image, giving the final result.

*Panorama of Don's Office made of three adjacent photographs.*

HDR Images

2010-03-21T21:48:00.000-07:00

In photography the dynamic range is the ratio between the maximum and the minimum light intensity measurable by the camera film or the camera digital sensors. Basically we live in a High Dynamic Range world but our cameras can capture only a part of it. In 2004 Paul Debevec presented an algorithm to recover the HDR radiance map of a scene from a set of images taken at different exposures. The pixel values of the HDR radiance map are proportional to the real world radiance values and, once remapped to RBG values through some tone-mapping technique, they represent the image more accurately.

Algorithm Overview

The pixel values of an image are the result of a non linear function f(X) where X is the exposure. This function is a composition of the characteristic curve (the response to the variations in exposure) of the film or, for digital images, of the digital sensors, and of others non linearities introduced by the next processing steps. The problems is that camera sensors record only a low dynamic range of light intensities while the real scenes are made of a much wider range. Debevec solves this problem reconstructing the radiance map from a set of images representing the same scene but recorded at different exposure levels. The algorithm can be splitted into the following steps:

1. Recovering the camera response curve g(Z).

The response curve is recovered solving an over-constrained linear system of equations [(g(Z) - lnE - lnDT)], where g(Z) is the logarithm of the exposure corresponding to the pixel value Z, lnE is the logarithm of the irradiance and lnDT is the logarithm of the exposure time (shutter speed). Once built, the over-constrained linear system is solved in a least square sense.

*In green, interest points etained by the ANMS algorithm.*

2. Reconstructing the HDR radiance map.

Through the camera response function it is possible to construct the HDR radiance map. This is equal to the exponential of the weighted average of the radiance maps of the images taken at different exposures.

*In green, interest points etained by the ANMS algorithm.*

2. Tonemapping.

The image in High Dynamic Range must be re-mapped to a lower dynamic range to be displayed correctly on a monitor. I used the Reinhard Global Tonemapper Operator defined as Ld = L / (L + 1), where L is a scaled luminance value. Here is the final result:

*In green, interest points etained by the ANMS algorithm.*

Deformable Sphere

2010-02-20T22:43:00.000-08:00

A parametric sphere is deformed using Perlin Noise computed directly on the GPU.

Image Morphing

2010-02-18T13:21:00.000-08:00

Morphing is a technique to turn an image into another through a seamless transition and it is mostly used to create a metamorphosis between two person's faces.

To generate this seamless transition, we should know where the pixels of a source image S will end up being in a target image T. To make some calculations simpler, we reverse the problem and instead we find from which position x(S) a pixel of T located at x(T) came from. This sort of inverse warp resembles the semi-lagrangian advection developed by Jos Stam in his famous paper Stable Fluids.

Defined by hand pairs of corresponding points p(S) and p(T), we initially compute a Delaunay Triangulation for the set of points (p(S) + p(T)) / 2. The resulting mesh is displaced to fit into p(S) and p(T) generating a pair of corresponding triangulations t(S) and t(T). Given t(S) and t(T) we proceed computing the set of affine matrices M that maps triangles of t(T) into corresponding triangles of t(S) so that M*t(T) = t(S). Subsequently for each pixel of T located at x(T) = (x,y), contained into a triangle Tr, we compute its corresponding position x(S) through the matrix-vector multiplication M(Tr) * x(T) = x(S). Finally, we warp S into T interpolating the color of the surrounding pixels at x(S) and placing the resulting value in x(T).

*Left: source image; Right: target image. http://www2.imm.dtu.dk/~aam/datasets/datasets.html*

*Pairs of correspondent points defined over the two images.*

*Delaunay Triangulations.*

*Face morphing.*

Fluid Simulation

2009-11-09T14:30:00.000-08:00

The fluid simulation is based on the paper "Stable Fluids" by Jos Stam.

Inverse Kinematics

2009-10-11T22:46:00.000-07:00

Inverse Kinematics entails finding a set of joint angles necessary for the end effector to reach the desired position. In the video the desired position is defined with the wireframe cubes, while the end-effectors are represented by the hands of the model.I used the Pseudo-Inverse of the Jacobian Matrix method to approximate the final solution.

Least Square Meshes

2009-08-10T11:40:00.000-07:00

This is an implementation of the paper "Least-squares Meshes" by Olga Sorkine.

Given a set of random control points and the mesh connectivity, the geometry is reconstructed solving an over-constrained sparse linear system. Vertices lie as close as possible to the center of their ring, making the generated mesh “As smooth as possible”.

Cloth Simulation

2009-07-03T21:42:00.000-07:00

The implementation of the simulation is based on this article appeared on Gamasutra in 2003.

A common model for simulating Real-Time Cloths consists of a system of interconnected springs and particles. The corresponding system of ODE suffers of instability in presence of stiff springs (especially when solved with an explicit integrator). On the other hand weak springs lead to elastically looking, bouncy cloths.

The alternative proposed in the article consists of modeling the cloth over a set of constrained particles, where the constraint is the distance between adjacent particles. The corresponding over-constrained linear system of linear equations is solved through a Gauss-Siedel Relaxation. The absence of the spring equations in the model leads to a quite stable simulation.

Collisions are handled projecting the particles out of the external bodies, perpendicularly to the contact direction.

Texture Synthesis by Non-parametric Sampling

2009-05-31T11:47:00.000-07:00

The algorithm is based on the paper: "Texture Synthesis by Non-parametric Sampling" by A. Efros

Texture Synthesis is the process of generating an arbitrarily big texture consistent with the pattern of a smaller sample given as input. Assumed a Random Markov Field model, the probability of a pixel belonging to the new texture to have a certain value depends on its spatial neighborhood. That is, the color of a pixel X with an l-shaped neighborhood nX, will be the color of the pixel Y that has the most similar neighborhood nY to nX.

Image Quilting

2009-05-20T15:54:00.000-07:00

This project is based on the paper: "Image Quilting for Texture Synthesis and Transfer" by Alexei A. Efros.
Prior to this paper Texture Synthesis, that is the process of generating an arbitrarily big texture consistent with the pattern of a smaller sample given as input, was performed sampling and transferring one pixel at the time. The process, besides being deterministic, was also really slow.

In this paper Texture Synthesis is performed sampling and transferring entire tiles (or patches), that once stiched together generate the new image. Basically the new image is a collage made of sub-tiles taken from a smaller existing image.

To avoid noticeable artifacts samples are selected based on the similarity of their border with the border of their neighbors. This region (the border of the sub-tiles) will eventually overlap and will be cut, to further reduce the non-similarities between adjacent patches.

Catmull-Clark Subdivision Surface

2009-05-20T14:27:00.000-07:00

The algorithm that generates smooth surfaces is performed in two steps: Subdivision and Averaging.

During the Subdivision step a new vertex is added at the midpoint of each edge and at the centroid of each face. Given a face with n vertices {v1, v2, v3, v4} the centroid is given as (v1 + v2 + ... + vn) / n. Subsequently the vertices are connected to form m quads out of each m-sided polygon.

In the Averaging step the position of each vertex is set to be the sum of the centroids of the faces incident to it divided by the vertex valence, that is the number of edges connected to it.

Maya Animation - Playboy

2008-12-10T20:45:00.000-08:00

This animation is part of the final project, me and my three teammates did for the Building Virtual Worlds course. I textured, lighted and rendered the scene.