Parallel Processing Gigapixel Images

Parallel programming is often used to accelerate image processing methods (e.g. Eklund et al., 2013); however, there doesn't appear to be the same level of discussion about using parallel processing to handle gigapixel images (or images that are too large to load on one machine). Is there a reference that discusses parallel processing techniques for large images?

Follow-up Question: To me, it seems there is only one way to process gigapixel images: break them up into chunks and process each chunk on a different node. The way you split the image could differ, but the basic procedure stays the same. Are there other ways parallel processing can be used to handle gigapixel images?

• SO you are intending to make pattern recognition on the image? or decompressing the image as a whole instead of as chunks? Did you try to apply any simple compressing algorighm? Did you generate this image from a single source, or also as chunks? DId you actually tried something? – Brethlosze Mar 21 '17 at 1:29
• This was more of a conceptual question, but I can give you specifics to my underlying problem. I am trying to register a series of gigapixel images that represent a 3D specimen. Each image in the series was acquired in chunks (i.e. tile scan) and fused together into one large image--too large to load in memory of one machine. I have registered low-resolution versions of the images; however, I'm wondering if there is a way to register the high-resolution version. I can break them into chunks. The problem is that the target image chunks would change after each registration iteration. – user27402 Mar 21 '17 at 12:17

Parallel processing of large images or large quantities of images is no different than parallel processing for other data types. You will come across the same strengths and limitations.

First of all, there are two major paradigms for parallel problems: Those that are obviously parallelisable and those that are not (or inherently serial).

In an obvious parallel algorithm, the result of a computation can be achieved by the repeated application of one or more functions (the function here as an element of computation) to a dataset. But, in a non-obvious parallel algorithm, the result of the computation cannot be "untangled" and has to be carried out as a single function. There are of course intermediate cases with a task being composed of some parts that can be parallelised in a straightforward way and some tasks carried out serially (unavoidably).

If you are looking for an object in an image through cross correlation, you can apply an image pyramid on it and then feed the different scales to different algorithms that slide the template over the image and try to find interesting points.

If you are trying to derive the "map" of a metric, again, this can be obviously parallelised. For instance, generate an image where each pixel is the standard deviation of the 8 surrounding pixels in the original image.

If you are trying to extract SIFT descriptors, again, this can be parallelised, to a certain extent.

If you are trying to stitch images together, what you cannot parallelise easily is the optimisation process of trying to match the locations of the keypoints. This is because, you are trying to minimise an error that is distributed over many different combinations of keypoints. Therefore, inevitably, even if you tried to do it path-by-patch you would still have to tune the error between patches to make sure that the algorithm has converged to a single optimal solution.

Given what is mentioned in the comments of the question, it might be possible to still converge to a solution as far as the keypoints are concerned. But, re-projecting already large images and then putting them together into one ultra huge image, might still be challenging, not because of lack of parallelism but because of lack of memory.

Hope this helps.

EDIT:

In the simplest form, I'm attempting to register two gigapixel images A and B

Gigapixel images will require a huge amount of memory if processed in a "conventional" way. This is more or less a fact. The question now is what do we do about it?

I say "more or less" because there are techniques that rely both on software and hardware that could allow in memory processing of such images in the "conventional" way. These are in-memory computing and Shared (or Distributed) Memory. On the former, I forget the exact term right now, but there is a technique which links the actual physical memory of a number of machines together through network links at a very low level. So, suddenly, an algorithm has huge amounts of memory available as if it was "local".

But short of these little beasts the other thing that one can do is process the images in an "unconventional" way. And in this case it really depends on what you want to achieve.

The trick is similar to Sparse Matrices.

Sparse matrices present an interface to the user that is no different than a conventional matrix. You still say I[1200,1500] but internally, the getitem operation of I's data type, that is implied by the use of indexing, does a bit of "magic" with the indices and returns a value. If a matrix is 100x100 and has at most 45 non zero double precision floating point values in it, there is no reason to waste the rest of the space. So, internally, when I[20,32] = 3.1415928 you might store something like 20, 32, [data value] and then later, when 2 * I[20,32], you look up the indices and if they exist in your lookup table you return the value but if not, then you return a 0.0.

In the case of huge images, we are on the other end of the spectrum but still the solution is kind of similar. You create something like a class MappedImage. Instead of loading the image, you have a constructor like MappedImage(pathToDirectory). The contstructor loads the image tiles and does the cross registration but does NOT! actually cross register the images. In other words, all you are after at that point is the transform that takes you from "image space" to "cross registered space".

Once this MappedImage is constructed, you still access it via I[789,145890987] (I here being an object of MappedImage) but the getitem of MappedImage now takes the desired indices, passes them through the transformation matrix, gets the actual locations, "guesses" which image patch contains the pixel values and reads the actual pixel value from that image only.

In this way, you don't have to be keeping all images in memory all the time and you can still use standard memory mapped I/O through the facilities of your language of choice.

The paper provided is primarily focused on doing a high quality registration not necessarily accessing the cross registered image. In a way it does highlight the same problems highlighted earlier and hints at the "conventional" solution which is "work on many small images".

Now, obviously, the next question is "What do you want to do with this 'image'"?

Because, if you want to visualise it, then you can create a MappedImage_Tiler that accesses some I via the interface mentioned earlier and cuts this huge image that you will never be able to see in its entirety into smaller pieces. These can then be sent to an off the shelf tile image viewer and allow you to browse the image like (for example) Google Earth.

But, if you want to work on it and produce some directional derivative or whatever else, then, yes the I[34,2875623897652398756] interface will still work but you will have to lower your expectations on speed. Especially if the goal is to work on "laptop type" hardware as the constraint was in the paper cited.

I can then map those transformation to higher-resolution levels; however, there is error in this type of mapped registration. I'm hoping to use parallel techniques to register A and B directly at the highest resolution.

This is what I had in mind too: Use the low resolution image derived transform and "project" it to the high resolution images (possibly just through a magnification component (?)).

Hope this helps.

• Thanks A_A. This touches on my question, but I am really most concerned with "lack of memory" situations. I'm wondering what parallel techniques exist for processing images that are too large to load as one piece. In your object recognition example, there will be some point in your image pyramid where you cannot load the entire image. In fact, this is the situation I'm dealing with. I've been able to register low-resolution versions of the images, but the algorithm can only work up the pyramid until it can't load the next higher level in the pyramid. I'm wondering what to do at that point. – user27402 Mar 22 '17 at 15:36
• @Vector Thank you for clarifying, will update response as soon as I can. In a way, the answer is already given in bold letters as I suspected the problem. In the meantime, can I please ask you to share more details about your specific application? For example, are you stitching microscopy images by any chance? – A_A Mar 22 '17 at 16:07
• Certainly. In the simplest form, I'm attempting to register two gigapixel images A and B. Neither A nor B can be loaded into memory of a single machine. I have generated image pyramids of A and B, and used the low-resolution pyramid levels to perform my registration. I can then map those transformation to higher-resolution levels; however, there is error in this type of mapped registration. I'm hoping to use parallel techniques to register A and B directly at the highest resolution. A non-parallel solution is presented by Lotz et al. 2015 – user27402 Mar 22 '17 at 16:50
• @Vector Thank you, please see amended response. – A_A Mar 23 '17 at 8:52