Transforming Images for Fun: A Local Grid-based Image Warper

• Download source - 41.05 KB

Background

Generally, digital image warping is a process of geometrically transforming digital images, including from simple transformations such as scaling or rotation to complex, irregular warps. This topic drew a lot of attention from the academic field in the 1980s. Nowadays, it is a fundamental topic and often taught in courses about Digital Image Processing/Computer Graphics for undergraduate students, e.g. this, this and this. The application of digital image warping can be found widely in the entertainment industry, especially in computer-based image retouching and plastic surgery.

It has been a long time since I took my undergraduate course in Digital Image Processing at the university (though as I remember, image warping techniques were not included in that course, I did not know why), and perhaps I would have completely forgotten this stuff if I had not accidentally found this page. VPSS is an excellent image warper which is implemented in a genius way such that the quality of the output is simply outstanding. And yes, as you might have already noticed, it is a commercial application with the price of 29.95 US dollars.

Well, I am just wondering if my understanding in this field can help me develop another image warper which gives a (hopefully) competitive result. I therefore "dedicated" my last weekend to developing my own warping engine which has the following functionalities:

• Allows users to translate, grow and shrink images at a specific position, with different brush sizes, i.e., different values of the radius of the effective region. These are also the main functionalities of VPSS.
• Platform-independence. Image processing might depend on the platform and/or the library we use, e.g., BITMAP on Win32 API, Bitmap on .NET, IplImage on OpenCV, or even CGImage on iOS. I expect the warping engine should be platform-independent so that it can be re-used on different platforms without any modifications. To this goal, the engine is built purely in C++ and only works with images in their raw form. This means that we have to deal with char[] arrays and the mess of padding bytes... Other basic structures like Point, Rectangle... are also needed to be defined inside the engine itself.
• A good (and flexible) enough filtering strategy. Warping digital image often involves a resampling process which may introduce aliasing and decrease the image quality. To minimize the loss of quality, filtering is needed. There are many applicable filters, ranging from simple interpolation and decimation to complex ones such as Elliptical Weighted Average Filter (EWA). However, this is the place where the traditional quality-performance tradeoff raises again: the better a filter is, the more processing time it will consume. Assuming that we are developing an interactive image warper for iPhone, the performance criterion might be critical so that using the simple interpolation filter is the only acceptable solution. Therefore the engine should be flexible with different filtering strategies.

To be quite frank, I have to say that I did not achieve all of these goals. Within two days of the last weekend, I only managed to build a platform-independent engine with acceptable quality. On the last goal, I only implemented a simple interpolation filtering. However adding other filtering strategies is pretty straightforward.

The result of my implementation and a comparison with VPSS is demonstrated in Figure 1.

Using the Code

The engine supports (but is not limited to) three types of warping, which are expressed by the following constants:

#define WARPER_TRANSLATE 0
#define WARPER_GROW      1
#define WARPER_SHRINK    2 

In order to use the engine, you have 2 options:

• Integrate the source code to your C++ application. In this way, you can access the engine in an OOP manner, and you will have more chances to alter the way in which the engine works. However, suppose you are working on a .NET project and you want to use the engine. You surely cannot simply “export” these C++ classes and use it directly in .NET due to the way in which unmanaged objects are handled in .NET Framework. In this case, you can use the engine in the next style.
• Compiles the engine into a library and invokes it using some simple subroutines, I called this the non-OOP manner.

This section will show how to use the engine in both options.

Using in the OOP Manner

In a C++ project, you can access the engine in the OOP manner. All of the functionalities of the engine can be accessed through the Warper class, therefore you will need to allocate a new Warper for each image:

// The general idea is to create a new ImageData object,
// and then create a new Warper.
// ImageData is a structure defined inside the engine.

ImageData imgData;
imgData.Resize(bmpData.Width, bmpData.Height, 3, bmpData.Stride);
memcpy(imgData.Data, (char*)(void*)bmpData.Scan0, bmpData.Stride * bmpData.Height);

// Create new Warper.
m_warper = new Warper(imgData); 

In an interactive-based warping system, users expect the application responds at every step of their interactions. Therefore to start, update and finish a "warp", you only need to use three functions of Warper called BeginWarp(), UpdateWarp() and EndWarp():

void form1_MouseDown(...)
{
  if (e.Button == MouseButtons.Left)
  {
    Point pt;
    //...
    m_warper.BeginWarp(pt, m_iRadius, m_iWarperType);
    //...
}

void form1_MouseMove(...)
{
  // ....
  // Get the result in warpedImg by calling UpdateWarp()
  WarpedImage* warpedImg = m_warper->UpdateWarp(pt); 
  
  // show the result on UI
  if(warpedImg)
    DrawImage(m_bmpImage, warpedImg);
}

void form1_MouseUp(...)
{
  //......
  // first, calling UpdateWarp() function
  WarpedImage* warpedImg = m_warper->UpdateWarp(pt);  

  // then call EndWarp()
  if(warpedImg)
  {
    warpedImg = m_warper->EndWarp(warpedImg);
    DrawImage(m_bmpImage, warpedImg, false);
  }
}

Usually, the translating warper can be started and ended right in the MouseUp() and MouseDown() events. However the shrink and grow warper will need a timer to update continuously, providing users with a good experience. You can look into the demo application for more details. That’s all. Your application is now ready to rock!

Using in the Non-OOP Manner

If you are working in a .NET application, you cannot use the exported classes from a C++ DLL directly. The reason is the CLR in .NET Framework is not able to handle C/C++ unmanaged objects. However, we can think about these workarounds:

1. Wrap the C++ DLL in another C++/CLI managed project. The C++/CLI project will act as an intermediate coordinator which has the responsibility to manage the unmanaged objects of the C++ DLL. This can provide the ability of using OOP features from .NET applications.
2. This way, though I prefer not to do so.
3. Create C-style wrapper functions inside the C++ DLL so that it exposes its APIs just by subroutines. These subroutines are responsible for allocating and freeing C++ objects. The application in .NET only needs to call these subroutines. This will break the OOP implementation into some functions that .NET application can call through its P/Invoke mechanism.

I am not going to give a detailed cons. vs. pros. discussion of these approaches here. Roughly speaking, you can see that the first method is more scalable, but may affect the performance of the engine, since C++/CLI is generally slower than unmanaged C++. On the other hand, the last method is fast but not scalable: if you have more objects in the DLL, you will have more work to do with the functions of the API. I choose the last approach, just because I think it is easier to implement in this case.

This is the declaration in C# of the 6 functions of the engine:

[DllImport("ImageWarper.dll", EntryPoint="CreateWarper")]
private static extern int CreateWarper(int width, int height, 
    int scanWidth, int bpp, IntPtr rawData); 

[DllImport("ImageWarper.dll", EntryPoint="ReleaseWarper")]
private static extern int ReleaseWarper(int warperId);

[DllImport("ImageWarper.dll", EntryPoint="BeginWarp")]
private static extern void BeginWarp(int warperId, 
    int centerX, int centerY, int brushSize, int warperType);

[DllImport("ImageWarper.dll", EntryPoint="UpdateWarp")]
private static extern IntPtr UpdateWarp(int warperId, int x, int y, 
    ref int xRet, ref int yRet, ref int width, ref int height, ref int scanWidth);

[DllImport("ImageWarper.dll", EntryPoint = "EndWarp")]
private static extern IntPtr EndWarp(int warperId,
    ref int xRet, ref int yRet, ref int width, ref int height, ref int scanWidth);

They are totally self-explanatory, so I will not go into more details. In the attached source code, the engine is implemented as a library called ImageWarper. I have included a C++/CLI project called ImageWarperTest, and another C# project called WarperTestManaged, which both reference to ImageWarper. ImageWarperTest calls the engine in the OOP manner, and WarperTestManaged uses the engine in the non-OOP manner. You can dive into the source code for more details.

Implementation

This section roughly describes how the engine is designed and how/why it actually works.
As a generalization of this article, the warping engine works in two steps:

1. Creates and maintains a grid surrounding the initial cursor position. The grid only covers a small region, and its size can be changed dynamically and automatically when the user moves the cursor out of the initial grid. When the cursor is moving inside the grid, it is deformed based on the current warping style (translating, growing or shrinking). The intersection points on the grid act as the guider for the next step.
2. The values of pixels inside the grid are calculated based on the new configuration of the grid. This step can involve some filtering techniques which can improve the overall quality of the final image.

These two steps make the name of this article: local grid-based image warper. Local means the warper only changes a region surrounding the cursor, while grid-based indicates that the deformation process uses grid as the guider. This distinction also helps to make the warper more flexible, because we can employ any warping style by applying a new suitable strategy for the first step, and we also can implement any filtering techniques for the second step. These steps are illustrated in Figure 2.

(a)	(b)
(c)	(d)

All functionalities of the engine are implemented in the Warper class.

class DLLEXPORTED Warper
{
public:

  // ....

  // Begin the warping interaction. Called when the interaction begins.
  // ptCenterPos: Location (in pixels) of the mouse click, in regard of the image.
  // iBrushSize: The radius of the effective window, in pixels. 
  // This should not be too large (<= 50).
  // iWarpType: WARPER_TRANSLATE, WARPER_GROW or WARPER_SHRINK
  void BeginWarp(Point &ptCenterPos, int iBrushSize, int iWarperType);

  // Called at every moving step of the interaction.
  // ptMouse: Location (in pixels) of the current interaction, in regard of the image
  // Returns: a WarpedImage, contains the location and the image data
  // of the warped image patch.
  // Please DO NOT modify/delete the returned pointer!
  WarpedImage *UpdateWarp(Point &ptMouse);

  // Called when the interaction finished.
  // Should be call right after a call to UpdateWarp().
  WarpedImage *EndWarp(WarpedImage *warpedImg);

  // ....
};

The first step is performed by derived classes of WarperCanvas. In the engine, we have TranslateCanvas and GrowCanvas, which will deform the grid depending on its own warping strategy (TranslateCanvas for translating, GrowCanvas for growing and shrinking). This can be seen in Warper::UpdateWarp():

WarpedImage* Warper::UpdateWarp(Point &ptMouse)
{
  // ...
  // deforms the grid
  m_canvas->Force(m_ptCenterPos, ptMouse);  

  // interpolating the pixel values based on the grid
  // (which is stored in m_canvas->GetOffsetPoints())   
  Warper::OffsetFilter(m_imgOriginal, m_canvas->GetOffsetPoints(),
        *(m_canvas->GetBoundary()), &(m_warpedImage->Image));

  return m_warpedImage;
}

In the translate warper, an intersection point on the grid will be moved to a new position by applying the following formula:

where c and s are the current and starting position of the cursor, d is the distance reflecting the radius of the effective region.

For the growing and shrinking warper, the formula even looks simpler:

where r is the growing factor. r is greater than 0 for growing case and less than 0 for shrinking case.

The second step is to inference the new values for pixels within the grid. This is done by a simple interpolation filtering which is described in Tolga Birdal's article. You can see the source code in Warper::EndWarp() function.

Future Work

There are so many things to do with this project to make it better.

• The first idea I want to apply is improving the generic strategy, so that the quality of the final image can be better. Look at these two image sequences. The second row is from my warper, the bottom row is from VPSS. I currently have no idea how they implemented this functionality. As my best guess, I think they somehow “remember” the moving trajectory of each pixel, and then reconstruct them when needed. This makes sense since when you are “growing” an image patch, you are going to distribute the information in that patch to the neighbor positions, and the blurring occurred due to the lack of information for the centre position. I am still considering the possibilities of implementing this techniques, and any suggestions are greatly welcome!

(a)
(b)	(c)
(d)	(e)

• Look at the following images. What we want is to augment the body, however since the background nearby that position is not homogeneous, it is also “warped” as well. The solution for this issue is simple. The engine should provide some ways for the user to define what should be deformed, and what shouldn’t. This is a famous problem in Image processing called Interactive-based Image segmentation. After the segmentation is done, the engine will warp the foreground pixels only. (For those readers who are not familiar with Interactive Image segmentation, you can try the built-in functionality in Microsoft Office 2010 called Background Removal. In case you do not have Office 2010, there are tons of research papers about this topic, this and this are some well-known methods).

(a)
(b)	(c)

• Other filtering strategies are also required to get better quality for the final image.

Conclusions

In this article, I have presented a platform-independent generic image warping engine. The result is not really competitive with current state-of-the-art on-shelf commercial applications, however there are a lot of rooms for improvements which makes I believe that the engine is able to be upgraded somehow, and can provide much better final images. In fact, I will implement these ideas when I have free time for it, and in the mean time, suggestions are greatly appreciated.

History

• April 15, 2011: First submission
• April 18, 2011: Updated the source code package to fix the bug when translating near the border
• May 27, 2011: Updated the source code package to fix the bug of drawing in the test projects (mentioned here)