Better nonlinear resampler with built-in antialiasing (GEGL)

Abstract

Port the improvements to Nohalo Level 1 (gegl-sampler-sharp.c) and port Snohalo Level 1 (Nohalo with variable additional antialiasing) from VIPS to GEGL. In collaboration with Nicolas Robidoux, main developer of the Nohalo family of samplers, program Nohalo and Snohalo Levels 2 and 3 in demand-driven mode for GEGL. Carefully test for bugs and optimize for speed. Merge the various methods so that levels are automatically chosen depending on requested image processing quality level, and so that Nohalo is selected instead of Snohalo when additional antialising is set to zero. Put together a gallery of GEGL sampler outputs to be included in the GEGL source distribution.

Even without the improvements already found in VIPS, Nohalo Level 1 is the second fastest GEGL resampler (after bilinear). A gallery comparing enlargements produced by the current GIMP rescale methods and Nohalo and Snohalo Level 1, as well as pretty good approximations of Nohalo and Snohalo Level 5, is found here.

About Me

Name:

Adam Turcotte

School:

Laurentian University

Degrees:

B.Cosc. - Honours Diploma in Computer Science (Oct. 2007)
B.Sc. - 3-year General Mathematics Degree (May 2009) PENDING

Experience:

Research Assistant for Dr. Nicolas Robidoux (part-time) [2006-Present]
Research Assistant for Dr. Julien Dompierre (part-time) [2008-Present]
Learning Objects Programmer (full-time) [2004]
HTML/CSS, PHP, and MySQL (Little Albert Recording Session Repository)

Awards and Achievements:

NSERC Undergraduate Student Research Award (USRA) [2006]
NSERC Alexander Graham Bell Canada Graduate Scholarship (CGS) [2009]

I was recently offered the CGS and intend to use it to start Masters thesis research on image resampling in Fall 2009. We will contribute the results of this research to open source projects.

IRC:

Username an10na on irc.gimp.net and irc.freenode.net

Native Language:

English (also understood: French)

Software Development Skills

Did you develop any software, either individually or in a group? Please describe the software and its purpose.

SmartMesh (C++) [2008-Present]
I am working with Dr. Julien Dompierre to develop an "intelligent" mesh generation program in C++. This is a group project under SVN pertaining to the solution of industrial fluid mechanics problems.
Image Enlargement Test Suite (C/Scilab/BASH/ImageMagick) [2007-2008]
For my senior thesis, subjective comparisons of resized images were used to assess the quality of various resizing methods. However, it was quickly seen that this was inadequate, and so an extensive test suite was developed to quantitatively assess these methods. Originally consisting of 12 test images, the suite reduces these images to various sizes using custom-made box-filtering and decimation C programs, then uses a collection of open source image resizing methods to re-enlarge these reduced images. At this point the enlargements are compared to the originals using five error measures: Root Mean Squared Error (RMSE), Average Absolute Error (AAE), Maximum Absolute Error (MAE), Average Absolute Error (AAVGE), and Mean Structural Similarity Index (MSSIM). All these error measures were carefully programmed from scratch to minimize round off error, as well as overflow and underflow, and are considerably more precise for the suite's image sizes than the ImageMagick and GIMP implementations. The results produced by these measures are then averaged and tables are created of the results. This test suite (with some later modifications) was used in two publications: Fast Exact Area Image Upsampling with Natural Biquadratic Histosplines (ICIAR 2008) and Benchmarked CPU, SMP and GPU Implementations of Nohalo, a Co-Convex Antialiasing Image Resampler (C3S2E 2009). The first article deals with NBQH and the second article deals with Nohalo, which is one of the methods I intend to develop for GSoC. Both articles were group efforts. Note that two of the co-authors of the Nohalo article (John Cupitt and Kirk Martinez) are core developers of the open source project VIPS (Virtual Image Processing System), which is structured somewhat similarly to GEGL.
Publication Downloads:
- ICIAR 2008
- C3S2E 2009
GIMP Plugins - NNH, NBQH, IBFNBQH (C/GTK+) [2006-2008]
I received an Undergraduate Student Research Award from NSERC in 2006 and began my work in image resizing under the guidance of Dr. Minglun Gong and Dr. Nicolas Robidoux. During this time I developed a standalone C program to resize PPM image files using Nearest Neighbour Histopolation (NNH), which is basically a very careful exact area box filtering. For my senior thesis, I continued this work under Dr. Robidoux by developing a similar program for resizing images using Natural Biquadratic Histosplines (NBQH), and by writing a GIMP plugin of this method in order to take advantage of the filetype support. After receiving my Honours Diploma in Computer Science, I continued working with Dr. Robidoux to develop an Interpolatory Box Filtered version of NBQH (IBFNBQH). Upon finding out that the future of GIMP was GEGL, Dr. Robidoux decided not to distribute the NBQH and IBFNBQH plug-ins, especially after discovering better methods more friendly to demand-driven environments. However, a group of GIMP enthusiasts discovered the plug-ins on Dr. Robidoux's web site (following a thread on gimp-developer) and included them in their remix of GIMP for Windows, eventually putting their version in the GIMP plug-in gallery.
Plugin Downloads:
- NNH
- NBQH
- IBFNBQH
Installation example: gimptool-2.0 --install NBQH.c
King's Court {AI (Java) [2006]} {3D (C++/OpenGL) [2007]}
King's Court is an obscure board game similar to Checkers. Working with a friend, Darren Janeczek, we created a Java version of this game, along with an artificial intelligence for users to play against. Games can be played locally or over a network and can be logged, enabling users to watch previously played games within the GUI. Eventually, the rules of this game were translated to C++ and a 3D version was created using OpenGL. The camera can move in a semi-sphere around the board, a shaft of light indicates the selected game piece, and pieces are animated: sliding or jumping when moved and fading away when captured.
The Mind Reader (Java) [2004]
The Mind Reader is a Java applet requested by Dr. Cynthia Whissell from Laurentian University's Psychology department. She provided me with a "dictionary of affect," which contains a long list of words, each assigned three numerical values. This program, created with the assistance of Dr. Barry Adams, asks the user to quicky type the first seven words that come to mind, The relevant variables associated with these words are averaged and a circular graph is displayed, classifying the mood associated with them, and a vector is drawn to indicate the intensity of this mood.
Computer Simulator (Java) [2004]
Computer Simulator is a Java program, originally designed by Dr. Barry Adams, to demonstrate how instructions and values are loaded and stored in memory locations as a computer program is executed. I improved upon the original design by adding a trace of each instruction executed, as well as a collection of sample programs intended to guide the user.

What is your main development platform?

I do most of my development in Linux (Ubuntu and Fedora), but I have also developed in Windows.

What programming languages/tools do you use to develop software?

C
BASH
Java (Eclipse)
HTML/CSS
PHP
MySQL
C++ (Emacs and Microsoft Visual Studio)
SVN
Scheme (GIMP Script-Fu)
Scilab
Maple

Are you familiar with the C programming language, GTK+ and/or Glib?

Most of my university coursework was done in Java, but I have spent the past three years coding projects in C.
I have coded several GIMP plugins, so I am familiar with GTK+ since the graphical interfaces use GIMP Widgets. Specifically, my plugins request a width and height for the output image and a gimp_chain_button allows the user to maintain the aspect ratio of the image. This involves a callback method to ensure that this ratio is maintained as closely as possible.
Since I have coded GIMP plugins, I am moderately familiar with Glib. I have used the basic Glib types and several Glib functions in my code.

Have you been involved in other Free Software projects?

I have written free plugins for image resizing in GIMP and a massive open source image enlargement test suite in C/Scilab/BASH/ImageMagick that will be distributed soon.

Image Manipulation Skills

Do you use any image manipulation software?

I actively use Photoshop and GIMP for digital artwork and photography projects, and I have used Paint Shop Pro in the past. I primarily use Photoshop on my Windows desktop and GIMP on my laptop running Ubuntu.

What's your level of experience?

I consider myself to be an advanced Photoshop and GIMP user, as I have been creating digital artwork for many years. Here are some samples of my work.

Do you know something about common algorithms that are used in image manipulation, or common problems that are encountered in this field?

Yes. My senior thesis was about digital image resampling. I have programmed several image resizing methods, and have used and evaluated about 30 of them. I have studied image resampling artifacts both qualitatively and quantitatively.

GIMP and GEGL Skills

Have you heard about GIMP or GEGL before?

Yes. I have used GIMP for image editing on many occasions, and I am co-author of an article discussing an exact-area image enlargement algorithm implemented as a GIMP plugin. I am also co-author of an article discussing a GEGL implementation of Nohalo, another image resizing algorithm.

Have you used either of them before? Did you know that current versions of GIMP do use GEGL to some extent?

Yes. The GIMP plugins mentioned above were used in the comparative test suite and the upsampled images were created in batch using several Script-fus that I wrote to simplify the process, so I am rather comfortable with GIMP. I am also aware that GEGL is the future of GIMP.

Did you contribute to GIMP or GEGL?

Yes. The plugins mentioned above were repackaged as Windows plugins under the name HQ_Rescale by the user PhotoComiX. The original versions were never added to the repository since we believe that Nohalo and Snohalo are much better candidates for inclusion.

Do you build GIMP or GEGL or both yourself, do you try to keep them more current than your distro's packages?

I built GIMP 2.4 myself before it became the current Ubuntu version, so I could investigate the output produced by enlarging images with Lanczos. Since then, I have simply used the current Ubuntu version.

SoC Project

Have you partcipated in a previous Summer of Code?

No.

Why did you choose this project?

I have been working on image resizing projects since 2006. I am quite fond of this field of research and I consider this project to be completely suited to my abilities. In addition, I would be honoured to have the opportunity to once again work with Dr. Nicolas Robidoux.

What's the goal you want to achieve?

The higher levels of Nohalo and Snohalo produce high-quality output. Programming them so they run fast in demand-driven mode is a definite challenge (unlike with the GPU), and certainly a worthwhile endeavor. If time allows, I intend to help improving abyss policies and/or image size issues within GEGL, and/or help with integrating GEGL resamplers into GIMP, and/or write a GIMP plug-in which uses GEGL resamplers.

Because Nohalo and Snohalo are brand new schemes---and only Nohalo Level 1 is available through GEGL (VIPS svn trunk also has Snohalo Level 1)---Dr. Robidoux put some enlargements on the web (with descriptions) of downsampled images provided by Craig DeForest. I adapted the gallery here and included enlargements produced with the standard GIMP methods. The images given for Nohalo are very good approximations of the results using Nohalo Level 5, but the Snohalo ones are more approximate versions of the true Snohalo level 5, which will be slightly less aliased but more blurry than shown here. GEGL Nohalo Level 1 is already almost as fast as GEGL Bilinear, so we are hoping that Level 3 will not be much slower than GEGL Bicubic.

How much time do you plan to put into the project (hours/week)?

37.5 hours/week.

Are there any exams that will interfere with the project?

No.