Alternative Memory Models for ITK
An ITK image employs an implicit contiguous memory representation. Implicit means the representation cannot be configured or changed. Contiguous means the pixel elements are stored as a 1D array, where each element is adjacent in memory to the previous element. Unfortunately, in certain situations a contiguous memory representation is not desirable.

This article describes three alternative memory models for ITK images: slice contiguous, sparse, and single-bit. A slice contiguous image is a three-dimensional image whereby each slice is stored in a contiguous 1D array, but the slices are not necessarily adjacent in memory. Slice contiguous images are well suited for interoperability with applications representing images using DICOM. A sparse image is an n-dimensional image in which each pixel is stored in a hash table data structure. This memory model is well suited for images with very large dimensions, but few pixels that are actually relevant. A single-bit binary image is an n-dimensional image that internally stores a boolean as a single-bit, rather than the typical eight-bits. Single-bit images allow very compact representations for on-off binary masks.

ITK images are tightly coupled with their underlying memory representation. Performing a quick "grep" over the code base reveals numerous classes which directly access the image pixel array via itk::Image::GetBufferPointer().

Some of these include:

• Image iterators
• Image adapters
• Image file readers/writers
• VTK image export filter
• Octree
• Watershed segmenter
• BSpline deformable transform
• Optimized Mattes mutual information metric

The existence of these classes, as well as ITK’s strict backward compatibility policy, makes it difficult—but fortunately not impossible — to introduce images with alternative memory models. This article describes three new image memory models which use a similar mechanism to the existing itk::VectorImage. The new image types do not require changes to existing code, and they function with iterators and the majority of existing filters. However they will not function with classes that directly access the pixel array. For example, it is not possible to directly read or write the proposed images to/from disk, export the images to VTK, or use the images with the optimized registration framework.

(a) Contiguous Memory Model

(b) Slice Contiguous Memory Model
Figure 1: Contiguous and slice contiguous memory models.

Slice Contiguous Images
A slice contiguous image is implicitly three-dimensional. Each slice is stored in a contiguous 1D array, but the slices are not necessarily adjacent in memory. This representation is shown in Figure 1. The image can be realized by creating a new image class with custom pixel and neighborhood accessor functions. The pixel and neighborhood accessor functions provide a layer of indirection for iterators to access the image pixel data. Given the incoming offset for a contiguous memory model, the new accessors compute the index of the slice containing the pixel and the offset within that slice. The new image class is templated over the pixel type; it is not templated over the number of dimensions as it is always three.

One important different between itk::Image and itk::SliceContiguousImage is that for the later GetBufferPointer() always returns NULL (i.e., the pixel buffer makes no sense). Ideally this method would not even exist for slice contiguous images, but unfortunately too many other classes assume its existence.

A slice contiguous image is created in a very similar fashion to a “normal” image:

An additional step requires the pixel container to be configured with a list of slice pointers:

The slice contiguous image is now able to be used like any other image:

Sparse Images
A sparse image is an n-dimensional image in which each pixel is stored in a hash table data structure. Each time a pixel is set, a new offset-value pair is added to the hash table. Such a memory model means that little or no memory is allocated when the image is created, but the memory footprint grows as more and more pixels are set. This memory model is well-suited for images with very large dimensions, but few pixels which are actually relevant. It should be noted that (presently) filters using sparse images must be single-threaded.

A sparse image can be created in the typical fashion:

A sparse image requires a “background” value to be specified for undefined pixels:

Pixels can be retrieved or set directly (using Get/SetPixel) or via an iterator:

Single-bit Binary Images It is very common in image processing to create mask images which indicate “on” or “off” regions. Currently, the smallest pixel element available in ITK for representing such images is unsigned char which is stored in a single byte (8-bits). Even though a boolean can only represent 0 or 1, it too is stored in a single byte—check this yourself using std::cout << sizeof(bool) << std::endl.

Single-bit binary images internally represent each pixel as a single-bit. As such, the memory footprint for on-off masks can be lowered by (nearly) a factor of eight. Similar to slice contiguous images, single-bit binary images provide custom pixel accessor functions which convert the incoming offset to the relevant bit mask for the underlying data storage. Unlike slice contiguous images, single-bit binary images fit slightly better within the existing ITK framework so GetBufferPointer() makes sense in this context.

A single-bit binary image can be created as follows:

The bits are stored in blocks of 32, so the above code will actually allocate a buffer with size 96×96. As with all the presented image memory models, the binary image can be used with any iterator and/or filter which does not directly access the pixel buffer via GetBufferPointer().

Performance
Although the memory models presented above may be advantageous for reducing memory usage in certain scenarios, they have a performance penalty. Accessing pixels stored in a contiguous array can be highly efficient, whereas the three new images require additional computation whenever a pixel is accessed. A simple performance test was undertaken to compare the new memory models. The test measured four properties: (1) time to allocate the buffer, (2) time to fill the buffer, (3) time to set all pixels using an iterator, and (4) time to get all pixels using an iterator. Each test was run on a 256×256×256 image, executed on my notebook (Intel Core 2 Duo, T7250 @ 2GHz, 3GB RAM, Windows Vista SP1 32-bit) a total of 5 times with mean times (in seconds) reported in the following table.

All of the images have similar values for buffer allocation and getting pixels using an iterator. The sparse image was the fastest for filling the buffer because no memory is actually set at this moment, only a single “background” value. However, it was also the slowest (by quite a margin) for setting pixels using an iterator, because each pixel being set must be added to the hash table. The single-bit binary image was also fast for filling the buffer because the pixels are set in groups of 32-bits, rather than individual elements.

Performance timings (in seconds) for a 256×256×256 image.

Conclusion
This article discussed three images with alternative memory models: slice contiguous, sparse, and single-bit binary images. The proposed images should work with most of the existing ITK filters—assuming they access the pixel data using iterators rather than GetBufferPointer().

Acknowledgments
Thanks to Karthik Krishnan (Kitware) and Glen Lehmann (Calgary Scientific) for helpful discussions.

  Dan Mueller writes software to analyze and view images. At the moment he’s doing this for digital pathology images at Philips Healthcare in Best, Netherlands. When he’s not working with images, Dan enjoys making them with his camera. This year he’s taken over 6000 photos in 14 different countries.