GIMP GSoC 2011 - Seamless Cloning Project - Technical Overview & Status

Recently, I was asked by email to help with the status of my GSoC (2011!) project. So before I say anything about that, let me explain a few things about my current situation.

For those of you who didn't figure it out already from the lack of activity on this website (and the lack of my activity on the web in general), due to my current real-life situation, I barely have any free time except for those few precious hours in the weekend in which I try to run my own life.

This means that my open-source activity went to a level which is not enough to do anything which requires long sessions (*cough* coding new stuff *cough*), and only translations of open source software are being kept in progress (very slowly, but they are being worked on and I'll commit them when I have enough material).

Now that I said that, and now that you know why I'm rather unresponsive by email/comments to this site, let us begin a technical overview of the project status. Note that this was originally written as an email, so I'll sometimes write as if I'm addressing someone specific in a conversation, and sometimes I talk in general (3rd person). Please ignore this inconsistency...

Technical Overview & Status

Proposal
Unfortunately, I failed to find the original proposal. However, you can find the proposal which I recorded in the GIMP wiki. The proposal is located here.

Papers
I'm listing them here, it will become clearer once you see the modules listing.

• The paper behind the seamless cloning algorithm: Coordinates for Instant Image Cloning
• Unfortunately, due to open source licensing issues and some other reasons, I had to implement myself an algorithm for creating fine triangular meshes.
• The algorithm I used (and implemented!) was the Delaunay Terminator, as described by Jonathan Richard Shewchuk in his paper Delaunay Refinement Algorithms for Triangular Mesh Generation.
• Some of the code was based on an existing library (poly2tri) which is in turn based on it's own papers

Modules
The project is divided into 3 main modules

• A library for creating fine triangular meshes - poly2tri-c
• The first part of this library is a C port of a library for creating Constrained Delaunay Triangulations, which are basically "nice" triangulations of existing outlines with/without holes.
  The original library is poly2tri, and the C port I wrote can be found in poly2tri-c's repository under the poly2tri-c/p2t folder
• The second part of this library is an implementation of the Delaunay Terminator algorithm for what we call a Delaunay Refinement.
• Delaunay Triangulations are triangulations which are considered "nice", meaning that most triangles are more or less of equal size, without too big or too small angles.
• Delaunay refinement is the process of taking a Constrained Delaunay Triangulation (which is not exactly Delaunay due to constraints such as outline that must be respected) and refining it by inserting more and more points. The process terminates when the resulting triangulation is almost Delaunay.
• The implementation of the algorithm above was made from scratch and in fact was the biggest part of the GSoC project (the assumption was that there was an existing open source library to do this. Apparently it wasn't so...)
• My implementation can be found in poly2tri-c's repository under the poly2tri-c/refine folder
• The third and final part of this library is an implementation of a triangular mesh render. The render basically takes a mesh created from the refinement process, a buffer to fill and a vertex-to-color function, and creates an image of the mesh in the specified resolution and size.
• This is another implementation from zero, although quite trivial and could probably be made more efficient
• The original article used OpenGL to do this rendering, resulting an ultra-fast renderer. Since the project was done when GIMP/GEGL were in an unclear state regarding usage of graphics hardware acceleration, it was done on the CPU purely which is much slower (yet still almost interactive - less than a second for rendering regular objects)
• My implementation can be found in poly2tri-c's repository under the poly2tri-c/render folder

• The second part of the project is a GEGL operation for doing the actual seamless-cloning operation.
• In brief, here is a description of the process (needed to understand the state of the code):
• Do a heavy preprocessing step for creating a fine triangular mesh from the outline of the pasted area
• Now, for each render attempt, compute the color differences between the edges of the paste and the background image, and use the previously created mesh to interpolate the differences in the colors along the entire area of the pasted image. Add the interpolated color differences on-top of the paste and you get a seamless pasting!
• The GEGL implementation of the operation can be found under gegl/operations/common/seamless-clone (in the soc-2011-seamless-clone branch):
• Files beginning with sc-* are part of a "shared library" with the code required to do seamless cloning
• This library is used using the GeglScContext object (sc-context.h) which manages a seamless cloning operation for a specified buffer to use as a paste.
• GeglScContext implements smart logic to notice when a paste doesn't change between rendering sessions (i.e. calls to the process function) in order to avoid re-doing the heavy preprocessing step
• Ideally, GIMP would use this "seamless cloning library" to implement seamless cloning with an internal op that does not need to do this check over and over, since the paste can't change when moving it on the canvas in the GIMP UI. However, currently gimp uses the GEGL op which is described below in a rather dumb way...
• This library even exposes a pkg-config file to be easily linked against later...
• seamless-clone.c implements gegl:seamless-clone - A simple seamless cloning operation using the above library.
• seamless-clone-compose.c implements gegl:seamless-clone-compose - A simple meta-op for GEGL that composes the seamless paste above a given background...
• Finally, in order to have the triangulation algorithm included, a copy of poly2tri-c is included under the libs directory of GEGL. This is since poly2tri-c has no package that can be installed and it was asked for so that developers won't need to download additional source code from more locations. This is not a desired situation, yet I'm unaware of any package owners for various Linux distributions which would be willing to help with distributing poly2tri-c as it's own package. If any such developer would be found, send them to me and I'll give them any access/help to the repositories (and I'll do any code modifications needed)

• A GIMP tool using the seamless cloning GEGL op
• The tool is a bit buggy in terms of refreshing the canvas (sometimes, artifacts are left when dragging the paste)
• Additionally, it is inefficient since it doesn't use the library directly and so it does the check of whether the paste buffer changes each time
• I'm not sure whether the errors regarding non-continuous pastes (with holes and/or composed of several unconnected parts) do find themselves into the GIMP UI in a proper way...

GIMP/GEGL TODO

• Make GIMP check for the presence of the seamless cloning operation on the startup of the tool
• Make GIMP use the library directly (and check for it's presence on compilation time)
• Conditional OpenGL for doing the rendering of the triangular mesh!
• Implementing the OpenGL rendering in poly2tri-c should be very easy for anyone knowing OpenGL. I'll do it if GIMP/GEGL accepts OpenGL (not OpenCL! That's different!) into the pipeline
• Fix the described bugs in the GIMP tool UI

Poly2tri-C TODO

• Code cleanup, prepare for distribution (I'll do that - it requires less coding then the GIMP stuff and does not require a long coding session - so I can do it on my short available time periods)

Trying all my GSoC projects (seamless clone, triangulation)

It's about time I post this. My work is actually useable enough (I even received my first bug report by email recently) so it's the time to explain how to use this.

In this post I will explain you how to compile Poly2tri-C (the triangulation and mesh generation library), how to compile GEGL with the seamless cloning operation and GIMP with the seamless clone tool.

Ready? Then let us begin!

Very big steps towards finishing post GSoC (2011) work

It works!

An outline and it's refinement

If you have been tracking my blog, you saw that I was struggling in the last few weeks to implement a constrained delaunay refinement algorithm. It took ages, as I always encountered lack of available materials and/or programming bugs. But I'm here to say that it works now!
This implementation is in C# (easier to prototype algorithms than in C), and I will convert it to C later for usage with GIMP and the rest of the project. It's based on a paper by Jonathan Shewchuk: Delaunay Refinement Algorithms for Triangular Mesh Generation.

Now, what about the GEGL side of the project?
As you may have all heard, GIMP is progressing onwards to use GEGL as it's image processing core. My seamless clone tool is not different - it was written as a GEGL operation (meaning you can use it outside of GIMP, in your own programs!). The GEGL operation has received lots of work this week, including:

• Working in tiles instead of whole at once (reduces memory usage and makes it scalable for images as large as supported by GEGL)
• Bug Fixing and Compiler calming (making the warnings disappear)
• Removing code duplication

The op is pretty much done now! I will need to use the new triangulation algorithm (as mentioned above), but it should be transparent to the rest of the code.

Now, what about the GIMP side of the project?
Other than a bit nicer looking GUI for tuning some settings, it's already done since the summer.

Remaining TODO:

• Make the GEGL operation handle blank images to paste and images with very thin (1 pixel wide) areas. Also make it handle holes (I would probably warn about these and refuse to paste).
• Port the triangulation algorithm to C
• Also finally make it a standalone package...
• Improve a bit the GIMP user interface for the tool
• Bonuses:
• Implement an OpenGL and/or a OpenCL (I'm unfamiliar with openCL, and this op is actually very easy with OpenGL) version of the seamless clone operations, to speed things up even more.
• Code optimizations....

That's it for now. I'm off to bed...

Announcing - Project LibStructureGraphic

Note: This post is targeted mainly at programmers or people interested in visualization of data

As programmers, we often write very complex data structures. The hard part about maintaining complex data structures, is tracing bugs - since let's face it, in many places it's not practical to find which node out of several hundreds is deffected.

That's why I started a new project, called LibStructureGraphic. It's a library in Java, for visualizing data structures while making minimal or even no changes to their code. And since a picture is worth Ackermann(4,3) words (This is a programmers joke), here is an example:

Visualizations of a Binomial Heap (top) and a Red Black Tree (bottom)
Click to view fullsize

The idea is that having a visualization of the graph should help the programmer see more data at once, and speed up the times spent on finding bugs. I personally used custom code for drawing some data structures (for debugging) during my data structure course, and this was the source of this project. The visualization saved me hours of debugging!

The library requires a data structure to have the following properties in order to be visualized:

1. For now (will change in the future), the data structure must be representable as a Tree, which means it's composed of nodes where each node has exactly 1 parent and zero or more children.
   Support for Directed-Acyclic-Graphs (DAGs) will be added in one of the next versions, and support for cyclic graphs is planned for the future
2. Each node of the data structure should be represented by an object, which either implements a given interface (for finding the "children", "value" and "color" of the node), or has annotations on the fields that should be drawn. Ideally, the annotations are the preferred way since they mean you don't need to implement any custom functions; The interface is there only for nodes in which it's not possible.
   The nodes don't have to be of the same type - each node can be a completly different type of object!

The library will be released soon - I'm waiting only to see if one of the professors of my university will be willing to host it on its servers as an official project or not (Since this could be very useful in at least 3 mandatory courses). Non-Java versions (python, C#, C++, and potentially C with GObject) are not currently planned, but if enough people will want it, I will consider it ;)

And, the GIMP connection to this project (you didn't really expect me to write a post without mentioning GIMP, didn't you?) is that I'm working on a node-editor for GEGL. I knew I needed to implement a graph layout algorithm for it, and since I'm prototyping everything in Java, I thought of making a library from it.

New GEGL operation!

Hello,

As I mentioned, I started working on some gegl operations, and I'm glad to announnce my first official gegl operation - whirl and pinch! This operation is a port of the known gimp plugin to gegl (since eventually every gimp plugin will have to be ported).

How to install it (linux users):

1. Copy the file operations/workshop/whirl-pinch.c (from inside gegl's source tree) into ~/.local/gegl-0.1/plug-ins/
2. Make sure your enviroment contains gegl's build dependancies
3. Type 'make' inside ~/.local/gegl-0.1/plug-ins/

Now, you will be able to access the operation inside gimp (using the "GEGL Operation" tool) and get a live on-canvas preview of it!

"Whirl and Pinch" live on canvas!

BTW - last night I closed 6 gimp bugs :)

Fixing errors with NAN (C const) and GCC

Today, I was compiling GEGL on a computer other than my regular one, and I got this wonderful error:

exp-combine.c: In function 'gegl_expcombine_new_exposure':
exp-combine.c:149: error: 'NAN' undeclared (first use in this function)
exp-combine.c:149: error: (Each undeclared identifier is reported only once
exp-combine.c:149: error: for each function it appears in.)

The error happens only on certain machines with some versions of gcc, and I it may happen in the most unexpected times...
So, I thought I'd share the solution for this problem with you since I had it in several more projects which use the NAN constant. Basically, NAN is a constant for a floating point value, which represents value that is Not A Number (not to be confused with the value which represents infinity). This value is usually (see note at the end) returned when dividing zero by zero, and therefore it can be added to gcc's definitions by adding the following argument to the command line:

-DNAN="(0.0/0.0)"

This is equivalent to adding the following line in C

#define NAN (0.0/0.0)

Now, there is only a little problem - what if we are not running GCC ourselves? What if a makefile or some other utility does this? Well, with most configure scripts (These scripts prepare the build environment and generate the makefiles) you can simply set the CFLAGS environment variable (before running the configure script) to fix this - in bash syntax this would be:

export CFLAGS="-DNAN=\"(0.0/0.0)\""

This solved my problems :)
Reference - http://old.nabble.com/Where-is-NAN-Defined--td15398150.html, http://linuxreviews.org/howtos/compiling/
As the original email list say, NAN is defined on some platforms and it's undefined on others, and our definition may not always work. From my experience, in the few cases were NAN wasn't defined, the fix presented here was enough.

Edit: I’d recommend checking the first comment below, from Martin Nordholts – he seems to offer another legitimate (and possibly more elegant) solution by telling GCC to use the gnu99 C standard.

Multithreading in GIMP, Learning to write GEGL operations

As some of you have seen, GIMP is being ported to a new graph-based image core, called GEGL. Those of you who have experimented with GIMP 2.6.X and later, have possibly found the GEGL tool (Under the tools menu) which allows you to see on-canvas preview of some operations such as blur, perlin noise (which some of you know as clouds), and more.

Thanks to the very generous help of Øyvind Kolås (aka pippin), I have started to write a GEGL operation for GIMP. Too practice I decided to write a Pixelize operation (not too complex, but also works on a neighborhood of pixels and not on a single pixel).
This is the first time which I implement an image processing algorithm which is not based on samplings for distortion (like the waves filter), and although I know the theory for a lot of time, it still has some bugs with wrong indexes :P

When I finish this, I'm going to post it here along with a log of my chat with pippin on the IRC (on irc://irc.gimp.org/#gegl) to clear out some of the common questions about GEGL. Hopefully I'll be able to post a mini-guide (or more correctly, what I have learned, since I still have a lot to learn to write a full GEGL guide) to introduce other people to writing GEGL operations.

The discussion originally started because I was disappointed that libgimp (the library for interactions between plugins and GIMP) is not thread-safe, meaning that you can't have two threads modifying the same drawable concurrently (unless of course you want to "Create Modern Random Art" as someone called it). And it's impossible not practical to fix it (due to the amount of time it would take).

Apparently, GEGL is multi-threaded (more on this later, in my next post) and it usually works (but sometimes the threads reach a dead-lock, a situation in which both threads are blocking one another from progress since they are waiting for shared resources/memory). It still requires a bit of fixing (Cheer up for pippin! He needs some more motivation to fix this! ;-) )

So, for those of you who want to try "bleeding edge" and unstable GEGL, set the environment variable GEGL_THREADS to 2 (or whatever amount of threads you want GEGL to use) and expect up to 200% speedup (in ideal world. Practically some parts of the code which are executed sequentially, added to the limitation of the memory access speed, both will cause it to run slower depending on the operation and your system) with GEGL (or 0% if you reach a deadlock).
Be warned: this is supposed to be buggy. Please do not report bugs with this, unless you strictly know what you are doing.

Edit: Made the post more correct about the possible speedup. 200% speedup is a naive optimistic view, which is ain't true (and I forgot to mention this)