Archive for June, 2011

Content aware self-portrait

Thursday, June 30th, 2011

content aware self-portrait

http://alecjacobson.com/art/digital/
http://alecjacobson.com/art/

Ben Hur retargeting challenge

Wednesday, June 29th, 2011

Recently I got the chance to see a friend’s new image retargeting algorithm at work. It was very impressive and the best I’ve seen so far. I particularly liked that uniform scaling was within the set of possible solutions and actually occurred frequently. I like this because often uniform scaling looks way better than fancy retargeting techniques which sprinkle artifacts all over the image.

See the results reminded me again of Ben Hur. This movie was shot at a whopping 2.76:1 aspect ratio. Retargeting it to say, 4:3, would be a mess. All the times when I remember seeing it shown on TV (before widescreens became popular) it was shown with “letter boxes” rather than “pan and scan” or any other attempt to retarget the footage. Not even considering the fact that the original aspect ratio was intentional and that by retargeting it you’d be trivializing the directors’ choices (would a museum crop or stretch a painting to fit the gallery walls better?). Not even considering this, Ben Hur poses a striking challenge for retargeting techniques. To me it represents a real stress test. Much harder than most of the images in the RetargetMe dataset.

Here are some stills I found flipping through the film that I thought would be particularly difficult to retarget:

ben-hur-arab-2
ben-hur-arab-3
ben-hur-arab
ben-hur-drummers
ben-hur-march
ben-hur-parade-close
ben-hur-parade
ben-hur-senate
ben-hur-ship-rowers
ben-hur-trumpets
ben-hur-chariot

I ran some 4 of the easiest methods for retargeting on the last image.

Letter boxing

ben-hur-chariot-letter-box

Uniform scale

ben-hur-chariot-uniform-scale

1/2 Uniform scale, 1/2 letter box

ben-hur-chariot-uniform-scale-and-letter-box

Seam carving

ben-hur-chariot-seam-carving

Personally none of the above options besides Letter boxing are acceptable. Not even close. I would really like to see a retargeting algorithm that not only includes uniform scaling and cropping in the set of possible solutions, but also letter boxing. Do you know of one?

It goes without saying that the problem is much harder when considering not just a single frame but the entire scene or film’s worth of video. Letter boxing may be harder to include as an option when considering temporal coherence, but I still think it must be a possible solution. For films like Ben Hur, which purposefully utilize their entire aspect ratio, squishing a scene or cropping out elements would be far worse than the price of two black bars.

Export from After Effects, resave with QuickTime, import with PowerPoint

Thursday, June 23rd, 2011

My ridiculous regimen for creating small video files that Powerpoint knows how to play:

  1. Render from After Effects using Best Settings, Animation, Loseless: this makes a large .mov file
  2. Open in QuickTime and save as HD 480p, HD 720p, or HD 1080p (the largest available), this makes a new, small .mov file
  3. Drag this new .mov file into PowerPoint: often PowerPoint screws up the right most column of pixels on the preview image so I have to cover that with a small white rectangle

Vi(m) tip #11: remove swap file of current file (e.g. after a recover operation)

Wednesday, June 22nd, 2011

You can remove the swap file (.*.swp) of the current file in vim with a simple command in command mode:


:!rm .%.swp

Minimizing quadratic energies with constant constraints

Tuesday, June 21st, 2011

There are a many different ways to minimize a quadratic energy with constant constraints. I wrote out the exact steps for three such ways:

  • Separate the energy into knowns and unknowns, then solve for the unknowns by setting gradient with respect to those unknowns to zero.
  • Add additional term to energy that punishes not satisfying the known values of your constant constraints in the least squares sense, the solve for all variables by setting gradient with respect to all variables to zero.
  • Add additional variables called lagrange multipliers to energy so that the problem is no longer to find a minimum but a stationary point in the new energy. Such a stationary point guarantees that our constraints are met. Find the stationary point by the usual method of setting the gradient to zero, this time the gradient is with respect to all original variables and these new variables.

The pretty print type-up with MATLAB pseudocode.
A plain text, unicode version:


Quadratic energy
E = ZT * Q * Z + ZT * L + C

We want to fix some of the values of Z, we can rearrange the Z's that are still
free and the ones we want to fix so that Z = [X;Y], where X are the free values
and Y are the fixed values;

Split energy into knowns and unknowns
Z = [X;Y]
or 
Z(unknown) = X and Z(known) = Y
E = [X;Y]T * Q * [X;Y] + [X;Y]T * L + C
E = [X;0]T * Q * [X;Y] + [0;Y]T * Q * [X;Y] + [X;0] * L + [X;Y]T * L + C
E = [X;0]T * Q * [X;0] + 
    [X;0]T * Q * [0;Y] + 
    [0;Y]T * Q * [X;0] + 
    [0;Y]T * Q * [0;Y] + 
    [X;0]T * L + 
    [0;Y]T * L + 
    C
E = [X;0]T * [Q(unknown,unknown) 0; 0 0] * [X;0] + 
    [X;0]T * [0 Q(unknown,known); 0 0] * [0;Y] + 
    [0;Y]T * [0 0; Q(known,unknown) 0] * [X;0] + 
    [0;Y]T * [0 0; 0 Q(known,known)] * [0;Y] + 
    [X;0]T * L + 
    [0;Y]T * L + 
    C
E = XT * Q(unknown,unknown) * X +
  XT * Q(unknown,known) * Y +
  YT * Q(known,unknown) * X +
  YT * Q(known,known) * Y + 
  XT * L(unknown) +
  YT * L(known) +
  C

E = XT * Q(unknown,unknown) * X +
  XT * Q(unknown,known) * Y +
  (YT * Q(known,unknown) * X)T +
  YT * Q(known,known) * Y + 
  XT * L(unknown) +
  YT * L(known) +
  C

E = XT * Q(unknown,unknown) * X +
  XT * Q(unknown,known) * Y +
  XT * Q(known,unknown)T * Y +
  YT * Q(known,known) * Y + 
  XT * L(unknown) +
  YT * L(known) +
  C

E = XT * NQ * X + XT * NL + NC
NQ = Q(unknown,unknown)
NL = Q(unknown,known) * Y + Q(known,unknown)T * Y + L(unknown)
NC = YT * Q(known,known) * Y + YT * L(known) + C

∂E/∂XT = 2 * NQ * X + NL

Solve for X with:
X = (- 2 * NQ)^-1 * NL

Enforce fixed values via soft contraints with high weights
E = ZT * Q * Z + ZT * L + C 
Add new energy term punishing being far from fixed variables
NE = ZT * Q * Z + ZT * L + C + w * (Z(known) - Y)T * I * (Z(known) - Y)
where w is a large number, e.g. 10000
NE = ZT * Q * Z + ZT * L + C + w * (Z - [0;Y])T * [0 0;0 I(known,known)] * (Z - [0;Y])
where W is a diagonal matrix with Wii = 0 if i∈unknown and Wii = wii if j∈known
NE = ZT * Q * Z + ZT * L + C + (Z - [0;Y])T * W * (Z - [0;Y])
NE = ZT * Q * Z + ZT * L + C + ZT * W * Z - 2 * ZT * W * [0;Y] + [0;Y]T * W * [0;Y]
NE = ZT * NQ * Z + ZT * NL + NC
NQ = Q + W
NL = L - 2W * [0;Y]
NC = C + [0;Y]T * W * [0;Y]

Differentiate with respect to ZT
∂E/∂ZT = 2 * NQ * Z + NL

Solve for Z with:
Z = -0.5 * NQ^-1 * NL
or re-expanded
Z = -0.5 * (Q + W)^-1 * (L - 2 * W * [0;Y])

Discard known parts of Z to find X
X = Z(unknown)
But be careful to look at Z(known) - Y to be sure your fixed values are being
met, if not then w is too low. If the X values look like garbage then perhaps
you're getting numerical error because w is too high.

Lagrange multipliers
We want to minimize
E = ZT * Q * Z + ZT * L + C 
subject to the constant constraints:
Z(known) = Y
Find stationary point of new energy:
NE = E + ∑λi *(Zi - Yi)
        i∈known
NE = E + [Z;λ]T * QC * [Z;λ] - [Z;λ]T * [0;Y]
where QC = [0 0 0;0 0 I(known,known);0 I(known,known) 0]
NE = [Z;λ]T * NQ * [Z;λ] + [Z;λ]T * NL + C 
NQ = [Q 0;0 0] + QC =  [         Q        0             ]
                       [                  I(known,known)]
                       [ 0 I(known,known) 0             ]
NL = [L;0] + [0;Y];
Differentiate with respect to all variables, including lagrange multipliers
∂E/∂[Z;λ]T  = 2 * NQ * Z + NL
Solve with
[Z;λ] = -0.5 * NQ^-1 * NL

Discard fixed values and langrange multipliers.
X = Z(known)
The value of λi is the "force" of the constraint or how hard we had to pull the
energery minimum to meet the constraints. See
http://www.slimy.com/~steuard/teaching/tutorials/Lagrange.html#Meaning

Common mesh energies, sum notation and matrix notation

Monday, June 20th, 2011

I’m always re-deriving the matrix notation of common triangle mesh energies like the Dirichlet energy, Laplacian energy, or local rigidity energy. Here’s my usual strategy. I’ll assume that if your energy came from a continuous integral you can at least get it to a sum over mesh elements. Here I write my sums over vertices and their neighbors, but surely you could also sum over triangles.

mesh energies sum to matrix form
Pretty-printed pdf document

Uglier plain text, unicode version:


∑i∑j∈N(i) vi  = ∑i * #N(i) * v = VT * D * 1, 
  where D is diagonal with Dii = #N(i)
∑i∑j∈N(i) vj  = VT * A * 1, where A is the adjacency matrix
∑i∑j∈N(i) vi - vj = VT * D * 1 - VT * A * 1 = VT * (D-A) * 1

∑i∑j∈N(i) wij  = 1 * Aw * 1, where Aw adjacency with Awij = wij, if j∈N(i)
∑i∑j∈N(i) wij*vi  = ∑i vi * ∑j∈N(i) wij  = VT * Dw * 1, 
  where Dw diagonal with Dwii = ∑j∈N(i) wij
∑i∑j∈N(i) wij*vj  = VT * Aw * 1

∑i mi * ∑j∈N(i) wij vi = ∑i mi * vi * ∑j∈N(i) wij = VT * M * Dw * 1,
  where M is diagonal with Mii = wi
∑i mi * ∑j∈N(i) wij vj = VT * Aw * M * 1

∑i∑j∈N(i) vi² = VT * D * V
∑i∑j∈N(i) vivj = VT * A * V
∑i∑j∈N(i) vj² = VT * RD * V, where RD is diagonal, RDjj = ∑i 1 if j∈N(i)
  if j∈N(i) implies i∈N(j) then
  D = RD
  so ∑i∑j∈N(i) vj² = ∑i∑j∈N(i) vi² = VT * D * V
∑i∑j∈N(i) (vi - vj)² = ∑i∑j∈N(i) vi² - 2 * ∑i∑j∈N(i) vivj + ∑i∑j∈N(i) vj²
                     = 2 * ∑i∑j∈N(i) vi² - 2 * ∑i∑j∈N(i) vivj
                     = 2 * VT * D * V - 2 * VT * A * V
                     = 2 * VT * (D - A) * V
                     = 2 * VT * L * V

∑i∑j∈N(i) wij*vi²  = ∑i vi² * ∑j∈N(i) wij = VT * Dw * V
∑i∑j∈N(i) wij*vivj = VT * Aw * V
∑i∑j∈N(i) wij*vj² = VT * RDw * V, where DW is diagonal, RDwjj = ∑i wij if j∈N(i)
  if j∈N(i) implies i∈N(j) and wij = wji then 
  Dw = RDw
  so ∑i∑j∈N(i) wij*vj² = ∑i∑j∈N(i) wij*vi² = VT * Dw * V
∑i∑j∈N(i) wij(vi - vj)² = 
  = ∑i∑j∈N(i) wij*vi² - 2 * ∑i∑j∈N(i) wij*vivj + ∑i∑j∈N(i) wij*vj²
  = 2 * ∑i∑j∈N(i) wij*vi² - 2 * ∑i∑j∈N(i) wij*vivj
  = 2 * VT * Dw * V - 2 * VT * Aw * V
  = 2 * VT * (Dw - Aw) * V
  = 2 * VT * Lw * V

∑i mi * ∑j∈N(i) wij vi² = ∑i mi * vi² * ∑j∈N(i) wij = VT * M * Dw * V
∑i mi * ∑j∈N(i) wij vj² = VT * RDw * M * V
∑i mi * ∑j∈N(i) wij vivj = VT * Aw * M * V
∑i mi * ∑j∈N(i) wij(vi - vj)² = 
  = ∑i mi * ∑j∈N(i) wij*vi² 
    - 2 * ∑i mi * ∑j∈N(i) wij*vivj 
    + ∑i mi *∑j∈N(i) wij*vj²
  = 2 * ∑i mi * ∑j∈N(i) wij*vi² - 2 * ∑i mi * ∑j∈N(i) wij*vivj
  = 2 * VT * M * Dw * V - 2 * VT * Aw * M * V
  = 2 * VT * M * (Dw - Aw) * V
  = 2 * VT * M * Lw * V
  Note: let wij = cwij = cot(αij) + cot(βij) / mi and let mi = voronoi area at 
  vi, then the familar cotangent form of the discrete Dirichlet energy is
  EDirichlet = 2 * VT * M * Lcw * V

Matlab fprintf function returning cell array of strings

Monday, June 20th, 2011

I always forget how to fprintf the output of a function return a cell array. For example:


fprintf('**%s\n',depfun('magic','-quiet'));

Produces the error:


??? Error using ==> fprintf
Function is not defined for 'cell' inputs.

The solution for passing each string in the cell array to fprintf is simple if you can first save the output to a variable:


A = depfun('magic','-quiet');
fprintf('**%s\n',A{:});

Correctly produces


**/Applications/MATLAB_R2010b.app/toolbox/matlab/elmat/magic.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/datatypes/@opaque/char.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/datatypes/@opaque/double.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/datatypes/@opaque/toChar.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/elmat/meshgrid.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/ops/@opaque/eq.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/strfun/@opaque/findstr.m
**/Applications/MATLAB_R2010b.app/toolbox/matlab/strfun/@opaque/private/fromOpaque.m

New ETHZ masters thesis project available: Design of a modular character animation tool

Monday, June 20th, 2011

Design of a modular character animation tool

Daniele Panozzo, Olga Sorkine, and I are beginning a new collaboration with Cédric Pradalier of the Autonomous Systems Lab here at ETH Zurich. We’re hosting a masters thesis project.

The project, entitled Design of a modular character animation tool is now available, and we are eagerly awaiting applications. In this thesis you will design and produce an innovative input device for interactive animation of virtual 3D characters. The device will consist of a skeleton that will imitate the structure of the character the user wants to animate. The device will be constructed of modular bones and joints which may be rearranged and repositioned on the fly. Movements of the device will be registered with the animation system and will result in corresponding movements of the virtual character. The project will present novel mechanical and electronic challenges, and will be developed in collaboration with the Interactive Geometry Lab. We will provide the required mesh processing software components. This innovative interface will improve the animation workflow used in the videogame and film industry, which by and large relies solely on keyboard and mouse interaction. A fully modular puppet, which could take the form of any character or shape, would not only present a novel interface but also provide a research instrument for evaluating human perception of 3D and 2D poses.
Please don’t hesitate to contact me for extra details.

Loop this video

Friday, June 17th, 2011


I was taking a look at these shockingly smooth, handmade video-loop textures and started thinking about how to make these automatically. A problem statement could be: take as input a video and an interval that should be repeated, try to produce a loop-able video texture. The goal is to maximize smoothness and proximity to the original interval. Each frame of the output might be composed of different pieces (in time) from the input video, and might barrow from frames outside the input interval, and different parts of the texture might loop at different frequencies. There are quite a few academic papers that present what could be the seeds of this technology, a good place to start is Video Textures. Their page annoyingly doesn’t loop their output videos for you, so I made this simple Loop this video! utility.
The examples shown in this and following works are relatively “easy” compared to the handmade video-loop textures, but I think they provide promising first attempts.

Horizontal and vertical centering using html, css without knowing container size

Friday, June 17th, 2011

This is an especially elusive problem when designing a simple webpage in html. There are many non solutions on the web that require knowing the size of the container element. The solution I found was straight forward and did not require knowing anything about the container. It does not require javascript (though the original code uses javascript to show off the fact that it stays centered).

A page with horizontal and vertical centering

Original source