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!

[GSoC-2011] Final Results and How to Try

I am very glad to announce that I now officially passed the Google-Summer-of-Code 2011 :) The email from Google arrived in the last few days, and the official Google announcements on the GSoC results (of all projects) are supposed to be published tomorrow.

S/He is eyeing you :)
Sources: background, paste

Now, it’s time to publish the instructions on how to get and try it for the people who want to test it. There are some known bugs, and probably some unknown bugs, so be warned.

Compilation and Set-Up Instructions

1. You should know how to build of GIMP and GEGL from Git. A partially outdated guide is available here, and some things are explained in more depth here.
2. Instead of building the GEGL master (main) branch, switch to the soc-2011-seamless-clone branch. You can do this by running git checkout soc-2011-seamless-clone. Compile it with the regular flags – nothing special is needed.
3. After building the updated version of GEGL, it’s time to build the updated version of GIMP. Switch to the soc-2011-seamless-clone2 branch, and build it.
4. Before running GIMP, you must set the environment variable p2t_refine_steps to some number defining the maximal amount of points to be used in the mesh (in plain English, more should theoretically produce better result). I know this is annoying, I will get rid of it as soon as I finish debugging a certain code part. The typical number I use is 500 for pastes of around 200x200 pixels, and you should probably increase it if you wish to work on large pastes. If you are using the bash terminal, do export p2t_refine_steps=500 (and change the number as you wish)
5. Run GIMP.

Usage Instructions

Basically, you can just try copying a part, selecting the Seamless Clone tool (Shift+L) and clicking anywhere on the image to start the tool’s interaction. Click Enter to apply the final result. If this doesn’t work (and/or crash), then the instructions below are for you.

1. Run Gimp :)
2. Open the image that you wish to use as the background, and open the image you wish to paste into the background. Copy the part you want to paste. Note that opacity of that part will be treated as if it was binary – parts under 50% opacity will be removed, parts of more than 50% opacity will be completely opaque. The shape can be any shape, as long as it follows the following rules:
1. It must not have holes (Temporary limitation)
2. It must be continuous, i.e. composed of only one part (Temporary(?) limitation)
3. It must not have any long thin areas (Temporary(!) limitation).
   This means that if you have any area which is 1 pixel wide and is 3 pixels long or more (i.e. a thin spike), it will crash. Solution for this was already devised, I just need to code it. Select the Seamless-Clone Tool (Either by clicking the second tool on the toolbox that has the same icon as the move tool, or by doing Shift+L).
3. Click anywhere on the canvas while the background layer is active. The paste will be centered on the cursor, and so the cursor should be in a place where the entire paste is inside the background boundaries (both inside the rectangle defining the layer, and inside an area where all the background below it is opaque). This limitation will be enforced by the User Interface later.
4. Move the paste by clicking on it, dragging and releasing. If you move it slow enough (which actually shouldn’t be so slow), you’ll see the preview updating while you are moving.
5. Click Enter to Apply the effect.

Known Bugs

• All the above mentioned crashes and bugs :)
• Due to not yet complete memory management, the tool leaks memory from it’s preprocessing.
• Converting to tile-based processing is NOT 100% done, so it may crash on large pastes. Don’t ask me how large since I didn’t try anything more than 300x300 on my machine.

Other TODO’s

• Integrate the tool with the help system
• Test better the interaction when the the active image/display/drawable are switched during the interaction of the tool.
• Get a decent tool icon. Anyone with ideas for the visual metaphor to be used by a seamless paste tool, is more than welcome to leave them here as comments! I do design icons, but I don’t have an idea for this one.

GSoC 2011 - (Almost) Final results and thanks!

The end of Google Summer of Code 2011 is near, and I have failed to post enough updates on my blog. But that does not mean one bit that I failed to make progress. I'm proud to present you with my results:


Result, using my GIMP tool :D

The image to paste (source)

The image to paste into (source)
Licensed under Creative Commons Attribution-Share Alike 3.0 Unported

My tool allows you to move the paste on the image and see it update according to it's environment, so that it will paste seamlessly. It's not real-time yet, since I recompute some values that should be cached everytime, but most work to enable caching is done, and I hope to reach that before the final deadline. (Even if it won't be before the deadline, I will do it even after GSoC ends).

This is also the time to thanks all the people who made this possible:

• The authors of the Coordinates for Seamless Cloning article, who developed this algorithm.
• Prof. Daniel Cohen-Or, the professor who taught me computer graphics at the university, and helped me understanding the article (he is also one of the article authors).
• My GSoC mentor, Michael Natterer (aka mitch), who agreed to mentor me and assisted me when I was stuck.
• Mason Green, the original author of the poly2tri library, which was heavily used in the project for computing interpolation meshes. I would have never reached the project deadline without his amazing library.
• Prof. Jonathan Richard Shewchuk, who developed some of the geometrical algorithms that were used in this project.
• Finally, special thanks to all the great guys on the GIMP and GEGL irc who helped a lot - mitch, Bat`O, pippin, Alexia_Death, Mikachu, and more.

The end is near, and so is the beginning

Pictures from Yehuda Poliker's Concert on the
Student-Day, and a picture of my GSoC kit. Cellphone
pictures, so low quality :P

There is a feeling of an end in the air. The end of university, another chapter in my life. Yesterday I took part in the Student Day party at our university - there were amazing concerts by fantastic artists, including Yehuda Poliker, Monica Sex, Hadag Nachash and more. The Student Day is a known symbol of the end of the year, which happens 2-3 weeks before the end of the semester. The fact that is practically my last year as a student (I will have one last course left for the next semester, but that doesn't really count) does start to get in, and I am gradually getting used to this.

This week was also the official beginning of the Google Summer of Code coding period! After getting my cool GSoC kit (see the picture) 2 days ago I really felt that I'm a part of this great project - many thanks to google for organizing this! Anyway, I almost finished porting poly2tri to C. Once this is done, I can start coding my project. The milestones for my project are:

1. Port poly2tri to C (from C++), a library for generating Constrained Delaunay triangulations for given polygons.
2. Implement Chew's Second Algorithm to create adaptive meshes from CDT's*
3. Implement code to create polygons from Black/White (1-bit) channels (The edges where the color differs should be described by polygons)*
4. Combine all these to create an adaptive mesh from a Black/White channel (which symbolizes a selection area)
5. Create a triangle mesh renderer with color interpolation between vertices (actually, Cairo may be able to do this!)*
6. Implement the Mean-Value-Coordinate cloning, using these above, as a GEGL operation*
7. Add some GUI and put it as a GIMP tool

Marked with * are the steps that would require the actual work, most other steps should hopefully be trivial. But again, hopes and reallity don't necessarily agree :) When I applied for this GSoC I knew there was code to do adaptive mesh generation from polygon outlines. It's only too bad that none of the code to do this is small and in a GPL compatiable license :(

I hope to finish everything untill step 4 (and parts of 5 if I'll be able to use Cairo) untill the midterm, but I can't really set the midterm goals yet since I haven't started to seriously code yet because there is still a university semester going on for the next week or two.

To all students out there, good luck in the exam period! And for the GSoC students, good luck with the projects! :D

I’m doing a Google Summer of Code!

My application for a Google Summer of Code project for GIMP was accepted! =D
After being around the development team for a year or so (and hanging around the IRC even more), and after I couldn’t apply last year for technical reasons, this year I will get my chance.

Here is the initial description of the project, taken from my project page:

The project I intend to implement is something called Adaptive Cloning (aka Seamless cloning). Basically, the idea is that cloning parts from one image to another usually does not end well. This is because of different exposure/white-balance settings, or simply because of different lighting conditions.

The idea is to implement an algorithm which would allow to copy a part from one image, and paste it seamlessly into the other; the pasted area will be blended to fit the destination image locally. There are several techniques to do that, and the most known one is called poisson image cloning. The problem with most of these algorithms is that they are expensive (computation-wise) and are not suitable for interactive editing and previewing, unless you use hardware acceleration.

The suggested technique for my project is based on an article from Siggraph 2009 (includes demos and videos), which shows realtime performance (both on the GPU and the CPU*). The user would paste a some area from the clipboard and will then be able to "blend it in" according to it's environment.

I'm open for any suggestions regarding usability, ui integration, or anything which relates to the project. Feedback will be more than welcome!

* Note that I'm not sure for which sizes on the CPU it preforms on realtime, but it's still much more cheap computation-wise than most other techniques and a small lag of few seconds is something which should be acceptable for this sort of workflow.

GIMP has 5 projects for this GSoC – if all these projects succeed, GIMP will gain a major boost in it’s capabilities. This year’s projects are:

• Adaptive Cloning (aka Seamless cloning)
  • Student: Barak Itkin (IRC nick: LightningIsMyName)
  • Mentor: Michael Natterer (IRC nick: mitch)
• Replace GimpSizeEntry widget
  • Student: Enrico Schröder (IRC nick: enrico(?))
  • Mentor: Martin Nordholts (IRC nick: Enselic)
• iWarp like tool for Gimp
  • Student: Michael Muré (IRC nick: Bat`O) – the same guy who did the GSoC of the cage tool last year!
  • Mentor: Alexia Death (IRC nick: Alexia_Death)
• Porting GIMP plugins to GEGL operations
  • Student: Robert Sasu (IRC nick: robert)
  • Mentor: Mukund Sivaraman (IRC nick: muks)
• OpenCL in GEGL
  • Student: Victor Oliveira (IRC nick: victorm)
  • Mentor: João S. O. Bueno (IRC nick: gwidion)

I would also like to congratulate Blender (formally, The Blender Foundation) for an astonishing amount of 17 GSoC projects! If there is any project who can do anything with 17 students, it’s Blender. Congrats also for Inkscape for 4 GSoC projects.

Good luck to my fellow GSoC students, especially the GIMP (and Blender) students. I hope I will finish my project – I already learned from Bat`O last year that it is feasible to code something like this ;)

The list of all accepted projects for all organizations for this year’s GSoC can be found here.

Small Help Wanted

I searched without success for a small GPL compatible library for generating quality triangular meshes (example) from a given outline (probably a quality constrained Delaunay triangulations / conforming Delaunay triangulation) - I need this for my project. I haven’t found any library that is both small and GPL compatible. If anyone knows any such library, please tell me - it will save me lots of work and guarantee less bugs in the final result.

Edit: It seems as if poly2tri may do the job of creating a CDT (Constrained Delaunay Triangulation), and on that I can apply Chew's second algorithm. This is not optimal, but it is feasible since creating the CDT was probably the hard pard. If anyone finds something better, I will still be glad to knkow!