Parallel Processing Gigapixel Images
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.

For more information, please see this link and this link

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.