[Gimp-developer] GSoC 2013 - n-point image deformation

[Marek Dvoroznak <dvoromar gmail com>]

Hello again,

if you're still interested in the deformation tool I mentioned earlier,
I would be glad to implement it into GIMP during GSoC 2013.

Since last time I did some background research on another deformation
algorithms and played with their implementation in various software. I
also experimented with performance of my proposed algorithm and a
precision of it.

There exist quite a lot of nice deformation algorithms at present. I
experimented with some of them to find pros and cons of my proposed
deformation algorithm.

I also talked to my former computer graphics teacher about them to gain
some more insight into them.

Deformation tools I experimented with:
- Interactive (Rigid) Moving Least Squares implemented in Fiji (an image
processing package based on ImageJ).
- Free Transform Tool implemented in Krita 2.7 pre-alpha (MLS as well)
- Puppet Warp in Photoshop CS6 trial
- Igarashi's As Rigid As Possible shape manipulation (Java demo)
- Bounded Biharmonic Weights (MATLAB demo)

Deformations of realistic objects should be as rigid as possible
(deformation includes only translation and rotation). All deformation
tools above use that.

All mentioned deformation tools solve some system of equations, hence we
get the result pose immediately. Because of that we must specify some
initial conditions - positions of control points. That could be a
drawback for a user in some situations, because to get desired pose,
many control points have to be added and manipulated.

My proposed deformation algorithm (based on [1]) doesn't need these
conditions, because it's based on different (iterative) approach. With
this algorithm it's really like you're manipulating a real world object.
It feels like there is some physics (springs) involved in it but there
isn't – it's just a geometric method. Thanks to that the deformation is
predictable. I think that from user perspective, intuitiveness, fast and
easy manipulation and predictability of final result is very important.

About precision – previously mentioned deformation algorithms are more
precise than my proposed algorithm, but it depends on lattice element
(square or triangle) size. With decreasing lattice element size
precision of result is increasing, but inefficiency of the iterative
process is increasing as well. There has to be some balance set.

About performance – since I have been eager about the performance in C I
made a pure C version of the computing core of the deformation
algorithm. It seems like it's going to be about 2 times faster than Java
implementation but without any additional optimizations – so there is
still a space for speed-up.

There are a lot of details that will be covered in my proposal.

I know that one video clip is sometimes more than a thousand of words so
I'm attaching a link to it – [2]. An example of deformation using Fiji
is not included in the video clip because it's the same as what Krita
does. Igarashi's ARAP and Bounded Biharmonic Weights demos aren't
included as well because it isn't easy (or possible) to load specified
image into them – they are just demos.

Any suggestions or advices will be appreciated.

Marek

References:
[1] Daniel Sýkora, John Dingliana, Steven Collins, As-rigid-as-possible
image registration for hand-drawn cartoon animations, Proceedings of the
7th International Symposium on Non-Photorealistic Animation and
Rendering, August 01-02, 2009, New Orleans, Louisiana

[2] http://youtu.be/k3gN6aZWc-8