Hello guys,

I'm thinnking about applying as a student to implement an image segmentation plugin using the technique known as the Image Foresting Transform (IFT) [4], but before that I'd like to introduce myself and ask a couple of questions to make sure our interests match. So here goes:

= Introduction =

I'm a Computer Science MSc student at UNICAMP (from Brazil, we've a great history of participations on GSoC), and I have been working with Linux for about 4 years. I've just been admitted to the graduate program but I've been researching image processing algorithms (mostly related to object segmentation on images and videos) for the past 2 years. Before that I have worked with robotics, so I have experience on:

* Building C/C++ modules applied to indoor navigation of robots for about 2 years as a Research Scholarship Holder -- This project was also applied to the mix of robotics and entertainment, and involved a lot of C/Shell Script hacking and kernel adaptation (also some Java coding). * Developing image and video segmentation algorithms [1,2,3] using the Image Foresting Transform (created by my advisor prof. Alexandre X. Falcão [4]) mostly in C/C++ (some Python) -- Also as a Research Scholarship Holder. * Dealing with libraries such as wxWidgets (Gtk) to implement the GUI of a software used in my image processing research. I am currently doing some code scrubbing on that sw to make it available on the Internet (open source, of course =D).

In fact, the last item is where I got the inspiration to develop the GIMP plugin in the first place. IFT is a great alternative to algorithms based on the graph cut technique, and it was proven to provide better results [5]. It is a generalization of the Dijkstra's algorithm, which works quite fast and has served for many purposes in the image processing domain (e.g. image segmentation, CBIR, and morphology). Furthermore, in my research we have been working really hard to make user interaction more effective, faster, and the least as possible.

That's it for my technical profile. As for my personal info, I'm not sure what to write about, so feel free to ask me any questions.

= Questions =

I know there is already a segmentation tool in GIMP, but I feel it could co-exist with this plugin. So, here are my questions:

* I like to use SSE intrinsics to optimize some of my code, is it ok if I use it for the plugin?

* I do plan to keep working on my research during the GSoC period, which takes me around 25~30 hours each week. Will this be a problem?

That's it guys. Sorry for the long e-mail.

Hope to hear from you.

Best regards,

[1] - http://portal.acm.org/citation.cfm?id=1700473 [2] - http://www.springerlink.com/content/7415482725175nm7/ [3] - R. Minetto, J. P. Papa, T. V. Spina, A. X. Falcão, N. J. Leite, and J. Stolfi. Fast and robust object tracking using iimage foresting transform. In 16th International Workshop on Systems, Signals and Image Processing, Chalkida, Greece, Jun 2009. IEEE.
[4] - http://www.ic.unicamp.br/~afalcao/downloads.html [5] - http://portal.acm.org/citation.cfm?id=1574529

(Please let me apologize about referencing our papers, but our software is not yet available. If anyone is interested in reading them please contact me.)

--
Thiago Vallin Spina
MSc Student
Laboratory of Visual Informatics
Institute of Computing -- Unicamp
www.liv.ic.unicamp.br/

Hey Guys,

Sorry about the mistake on the subject, I meant GSoC2010 not 2009. I keep forgetting it's a new year =).

Best regards,

On 19 February 2010 05:20, Martin Nordholts wrote:

I don't think we should have two tools for this, rather one tool that does a great job

Afaik GSoC is supposed to be a full-time undertaking, if you spend 30

ours each week on other stuff it can be hard to be productive. If you think you can solve the task at hand despite this however, it will not be a problem in practice.

I intend to write the plugin as part of my MSc thesis, even if it is not chosen as a GSoC project. In fact, I talked to my advisor and he got very excited about the idea, so I believe that my initial estimate of 25~30h could drop to 10~15h (probably even less during GSoC).

Regarding the quality of our approach, I have made a quick comparison and it outperformed GIMP's tool based on SIOX for quite a few images (required less user interaction for correction and produced equal or better results for different types of images). So, if our method indeed proves to be a good alternative and be accepted by the GIMP community, I would be more than happy to implement it as an integral part of GIMP, even if it means doing it for GSoC.

Our segmentation framework and the plugin idea work as follows:

1) When the plugin is loaded the image is automatically pre-segmented and the result is shown to the user.

2) The user would then draw object markers selecting the regions which compose the object, and inserting background markers when a region contains both object and background pixels (those regions will be split independently as near the object's border as possible).

3) Then, our approach uses the markers to improve the automatic pre-segmentation (by learning the color distribution and texture of the object), to select the regions that compose the object, and to divide the regions that need to be divided.

4) Finally, the user may add/remove object and background markers to finalize the segmentation by selecting/splitting the regions. This step does not need to learn the object's properties.

* Optional * 5) I am currently working to improve a tool for soft segmentation which is applied automatically to the border of the segmentation mask, and which may be interactively used on fine features such as hair.

There are only three parameters that may be changed by the user: 1) The number of regions which should be pre-segmented (usually a slider to select between "less" and "more" regions) 2) The percentage of the object's information that should be used (we actually combine information learned from the object markers with color and texture information from the image to achieve better results). 3) Marker size and type (object/background).

Certain aspects of the framework may be changed or simplified to make it even more user-friendly, such as the automatic pre-segmentation step and the combination percentage parameter (50% usually yields good results).

* Note: I can demonstrate our method if necessary *

I'd rather prefer that you used the GCC vector extensions:

http://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html

Actually, that is what I currently use so there will be no problem.

Hey guys, sorry about the delay. It's been a bit of a busy week.

On 21 February 2010 14:05, Sven Neumann wrote:

Did you compare against SIOX as in the master branch or against the improved version that resulted from last year's GSoC ? It would also be interesting if you could benchmark your algorithm using the benchmark proposed in "GrabCut": interactive foreground extraction using iterated graph cuts" published in the Proceedings of the 2004 SIGGRAPH Conference. There's a Python script shipped with the GIMP source code that does this with the SIOX tool.

I compared against both branches and the results were about the same. Regarding the benchmark, on the papers that I mentioned in my first email [1,2] we used the whole GrabCut segmentation dataset considering the F-measure over the groundtruths (because our approach does not use trimaps). The accuracy result was of over 98% on every paper. In fact, on another work [3] seven users segmented a subset with 20 images from the GrabCut dataset, using different pattern classifiers for one stage of our framework, and the results were still above 97.7%. Also, we used the average number of drawn markers as an indication of user interaction, and part of our current approach (described in [2]) required about 5 markers in average (foreground + background). We are currently working on a paper to detail our final framework, because what was proposed on [2] was further improved to make user interaction even more effective and simple, while maintaining the segmentation quality.

I made a video comparing what I am going to implement for GIMP (currently on our research software) and the soc-2009-siox-drb branch, which can be seen here: http://vimeo.com/9803589. In my comparison, I used two images from the GrabCut dataset and one from the Berkeley dataset [4] that present increasing degree of difficulty. I believe that the foreground selection tool requires a lot more user interaction for most common images, because it usually does not handle well cases where foreground and background have similar texture/color (as pointed out on the SIOX paper).

In my opinion we should at this point concentrate on merging last year's work on the SIOX tool. If we start to add other segmentation methods before this work is merged, then it will become very difficult to ever get the soc-2009-siox-drb branch merged.

I agree that it should be a concern to merge that branch, but I think my framework could be released as a minor version in the future. So, it would be nice to have GSoC support for that.

[1] - http://portal.acm.org/citation.cfm?id=1700473 [2] - http://www.springerlink.com/content/7415482725175nm7/ [3] - Spina, T. V.; Montoya-Zegarra, J. A.; Andrijauskas, F.; Faria, F. A.; Zampieri, C. E. A.; Pinto-Cáceres, S. M.; Carvalho, T. J. and Falcão, A. X. "A comparative study among pattern classi?ers in interactive image segmentation". Brazilian Symposium on Computer Graphics and Image Processing, 22 (SIBGRAPI), Oct 2009, IEEE. To appear in IEEE Xplore. [4] - http://www.eecs.berkeley.edu/Research/Projects/CS/vision/bsds/

Hello, Gerald.

On 1 March 2010 19:57, Gerald Friedland wrote:

Hi all,

I agree that we should first merge the GSOC code from this year before we start thinking of a new segmenter. Let me know if you need any help. However, I think both a graph-cut-based segmenter and SIOX could have a place in GIMP side-by-side. Graphcut-based segmenters and SIOX have different complementary properties. It is going to be a GUI challenge though because it requires expert knowledge to know when to use which.

I do believe that using both algorithms could be a nice solution. In fact, it was my original proposal and I am willing to try to merge both methods.

Thiago: I can give you a couple of pictures that you should try with your segmenter and then compare against SIOX... especially those with a lot of texture and semi-transparent layers. The new version of SIOX can cope with them very well. Graph-based segmentation algorithms can't because they look for a minimum cut, which is a problem because especially those highly complicated pictures require a lot of time to do manually.

I would be very glad if you could provide me some of these examples, because it would really help me with my research. Also, I would like to state that our approach is *not* based on the min-cut/max-flow algorithm, so it does not suffer with many of its drawbacks. Right now my current job is to deal with soft segmentation in an attempt to cope with the transparency issue, and we already have some good solutions.

Thiago

On 2 March 2010 04:56, Sven Neumann wrote:

The current code is prepared for multiple algorithms as backend for the segmentation tool. It's not foreseen that you switch between algorithms, but that you pick one, but even that could probably be changed. As there is currently only the SIOX backend, there's no choice of algorithm exposed in the user interface. But it wouldn't be too difficult to add a toggle or combo-box for that. The question is how much does the user interaction depend on the chosen algorithm?

My algorithm is quite flexible about that. For instance, the lasso + markers used for SIOX could be the form of interaction chosen for IFT (I would only need to select a set of foreground and background pixels as initial markers), although I think that showing the pre-segmentation and selecting markers is helpful and more simple. Then, maybe both algorithms could run in parallel and the results would be somehow merged.

For most cases (highly textured images, similar foreground and background, variation in illumination, multiple objects, etc.) our algorithm works fine. However, to solve the transparency issue I am doing some experiments on a solution which is similar to SIOX. We currently use a pattern classifier to fuzzy classify all the pixels in order to estimate the arc-weights of the IFT graph. Thus, we form a fuzzy map with values between 0 and 1. This map can be straightforwardly used as an alpha channel, but I'm working on a piece of code which will allow the user to select, after the hard segmentation, markers where the fuzzy map values should be considered. Also, those markers would be used to refine the local fuzzy classification in order to obtain better values, because our current fuzzy classification considers global information (the foreground and background markers on the first iteration).

In a nutshell, first the user would do the binary segmentation and then s/he would select where soft values should be computed. Therefore, what I mean is that there will be a nice solution for the transparency problem soon.

Thiago

Hi Gerald,

I believe we were writing emails at the same time, and you didn't get to read my last one.

On 2 March 2010 21:49, Gerald Friedland wrote:

First: Try any image that works well and add 80% noise. SIOX is pretty good with noise.
Last time I tried Grabcut with such an image, I got a segmentation fault...

Here is an example with heavy noise to show that we can cope with it: http://www.liv.ic.unicamp.br/~tvspina/images/flower_noisy_result.png(original: http://www.liv.ic.unicamp.br/~tvspina/images/flower_original.png).

Once again, I must say that *we do not use GrabCut nor any graph-cut-based method. *That's why you cannot assume that we have the same weaknesses. In a way we do perform a cut in our graph, but we *do not use the min-cut/max-flow algorithm*. In fact, a paper by a coleague of mine and my advisor [1] proved that the best result graph-cut can achieve is the one IFT already provides.

Furthermore, although I do believe that being noise resistant is very important, and SIOX does a very good job at it, I do not think that regular GIMP users would want to segment an image with 80% noise.

Then: Try images like this one:

http://www.bigfoto.com/themes/nature/winter/tree-winter-village.jpg and try to extract the tree. The current GIMP version in the main branch cannot do it, the version from last Google Summer of Code can do it. Graph-based algorithms usually have problems but I think this is an important feature
because it saves HOURS of work to be able to do it semi-automatically!

Given that you probably did not see my previous email, because we exchanged them almost at the same time, you missed the fact that I am working to solve that problem and that I already have a good solution for semi-transparent images. Please refer to my last email for more information. Working with such images is paramount to my research and that problem will not remain unsolved for long. In fact, I believe that within the month or less I should have a good solution ready.

Thiago

[1] - http://portal.acm.org/citation.cfm?id=1574529

Hey guys,

I have been waiting for GSoC to begin in order to present a more concrete proposal.

So, I have discussed my idea with João S. Bueno and he agreed to being my mentor for GSoC. We live nearby and have the same Alma Mater (UNICAMP), so it was easy to get in touch.

Basically, I have proposed to first merge the soc-2009-siox-drb branch with the main branch and then implement my algorithm as another backend for the foreground selection tool. For the first part, it would be nice if I could get some advice from Gerald if possible.

In my proposal I have stated everything that I told you guys on this thread, so there are not many surprises. Also, João and I did some brainstorming and came up with a few ideas which are not described on the attached file, but that I'll try to implement if there's time.

Best regards,

Thiago