Inserting lines of pixels into an image quickly

Question

My current dilemma is as follows:

I have a 2550x3300 tiff. At certain (variable) points in my tiff I need to insert a line of pixels from elsewhere in the tiff. e.g. I need to insert 12 copies in a row of line 100 between lines 500 and 501.

I've been looking up different image processing techniques for a few days now and can't find anyone else doing this kind of thing leading me to believe that I'm probably going about this the wrong way.

Alternatively, if what I'm doing is just very slow and there is no better way to do it, what's the fastest way to do it? Using GDI+ it takes me about 12 seconds to add 1330 lines, 7.7 seconds if I use "unsafe" (I'm doing all this in C# right now) and if I use the FreeImage dll I can get it down to around 2.5 seconds.

Thanks in advance.

Answer 1

Unless this is a performance issue for uses, I'd stick with GDI+ simply because it is baked into the framework and keeps dependencies down. If you really need the performance use the FreeImage library.

Answer 2

Perhaps you would be better off looking at data structures. If you were dealing only with one dimension, a B-tree would be a very efficient way to insert as often as you liked with logarithmic cost. If you need to insert columns as well as rows, you'll need something much more sophisticated, but if you insert and delete rows only your life can be relatively simple.

It would help if you could give a description of the image as an abstract data type with all the operations you want to perform and some idea of what you want the costs to be.

If you want an off-the-shelf solution you might try representing the rows of the image as entries in a database table. Or another alternative would be to treat your rows of pixels as strings and you could then try the "C cords" library described in an article by Boehm, Atkinson, and Plass. It describes a data structure for manipulating very large strings efficiently.

Answer 3

It seems to me you have probably leveraged FreeImage as far as it can go.

The FreeImage source (http://freeimage.sourceforge.net/download.html, BitmapAccess.cpp::FreeImage_AllocateT) seems to malloc image storage as a one-dimensional array:

unsigned dib_size = FreeImage_GetImageSize(width, height, bpp); 

bitmap->data = (BYTE *)FreeImage_Aligned_Malloc(dib_size * sizeof(BYTE), FIBITMAP_ALIGNMENT);

Here, dib_size is "device independent bitmap size", and bpp is "bits per pixel".

I assume you use PixelAccess.cpp::FreeImage_GetScanLine() to get the line to copy:

BYTE * DLL_CALLCONV
FreeImage_GetScanLine(FIBITMAP *dib, int scanline) {
 return (dib) ? CalculateScanLine(FreeImage_GetBits(dib), FreeImage_GetPitch(dib), scanline) : NULL;
}

which calls

inline unsigned char *
CalculateScanLine(unsigned char *bits, unsigned pitch, int scanline) {
 return (bits + (pitch * scanline));
}

which seems to be O(1) for array-based lookup.

Since FreeImage internally uses static one-dimensional array storage, it does not seem readily apparent how you will achieve better than O(n) performance when growing the image (for example, when inserting copies of rows). It seems to me the best FreeImage can do is internally malloc new storage sufficient to grow the image, then copy the image data from the source to the new image. This would seem to be O(n).

Using a new data structure (such as B-tree) would take some effort but would give you better insertion-time characteristics (O(log(n)). However, the trade-off for speedup is increased storage space--you would be storing each pixel in a larger amount of space.

Since GDI+ seems closed-source, I am not sure how it implements bitmaps, but given the performance characteristics, it seems worse than FreeImage.