Parallel processing for distance transforms

A computer-implemented method of processing an image, the method comprising:

• at an input, receiving a seed image the seed image specifying a seed region and a height image;
• storing a distance image in memory and initializing that distance image on the basis of the seed region;
• using at least one processor to execute at least two threads in parallel in order to carry out a raster scan algorithm to assign a geodesic distance value to each image element of the distance image using the height image that distance being a geodesic shortest distance from the image element to the seed region;
• wherein one of the threads executes a raster scan by moving a window over the distance image in a forward raster scan and another of the threads executes a raster scan by moving a second window over the distance image in a backward raster scan;
• and
• synchronizing the two threads when each thread's raster scan meets a cross-over condition to enable each thread to complete processing by processing each image element of the distance image at most a single time, each image element of the distance image being processed twice by the at least two threads combined.

A distance transform engine comprising:

• an input arranged to receive a seed image specifying a seed region and to receive a height image;
• a memory arranged to store a distance image;
• a processor arranged to initialize the distance image on the basis of the seed region;
• the processor being arranged to execute at least two threads in parallel in order to carry out a raster scan algorithm to assign a geodesic distance value to each image element of the distance image using the height image that geodesic distance being a shortest distance from the image element to the seed region;
• the processor being arranged such that one of the threads executes a raster scan by moving a window over the distance image in a forward raster scan and another of the threads executes a raster scan by moving a second window over the distance image in a backward raster scan;
• and wherein the processor is arranged to synchronize the two threads when each thread's raster scan meets a cross-over condition and when each thread's raster scan is completed, synchronizing the two threads when each thread's raster scan is completed indicating the distance image is completed, each image element of the distance image being processed twice by the two threads combined;
• and
• wherein the processor is arranged such that each raster scan comprises a sequence of kernel operations each kernel operation comprising selecting a minimum of a plurality of distances and assigning that minimum distance to an image element location currently in registration with the center of the window.