# US 8,786,616 B2 · Parallel processing for distance transforms > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,786,616 B2 - Document ID: US8786616B2 - Status: Granted - Kind: B2 - Application number: 12/635,861 - Filed: 2009-12-11 - Published: 2011-06-16 - Granted: 2014-07-22 - Earliest claimed: 2009-12-11 - Assignees: Microsoft Corporation - Applicants: Toby Sharp; Antonio Criminisi - Inventors: Toby Sharp; Antonio Criminisi - Web page: https://patentgrep.com/patent/US8786616B2 ## CPC - G06T 17/10: Constructive solid geometry [CSG] using solid primitives, e.g. cylinders, cubes - G06F 17/10: Complex mathematical operations {(function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544)} - G06T 5/30: Erosion or dilatation, e.g. thinning - A63F 13/213: comprising photodetecting means, e.g. cameras, photodiodes or infrared cells (A63F13/219 takes precedence) - A63F 2300/1087: comprising photodetecting means, e.g. a camera - G06T 2207/20041: Distance transform - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - A63F: CARD, BOARD, OR ROULETTE GAMES; INDOOR GAMES USING SMALL MOVING PLAYING BODIES; VIDEO GAMES; GAMES NOT OTHERWISE PROVIDED FOR ## Abstract Parallel processing for distance transforms is described. In an embodiment a raster scan algorithm is used to compute a distance transform such that each image element of a distance image is assigned a distance value. This distance value is a shortest distance from the image element to the seed region. In an embodiment two threads execute in parallel with a first thread carrying out a forward raster scan over the distance image and a second thread carrying out a backward raster scan over the image. In an example, a thread pauses when a cross-over condition is met until the other thread meets the condition after which both threads continue. In embodiments distances may be computed in Euclidean space or along geodesics defined on a surface. In an example, four threads execute two passes in parallel with each thread carrying out a raster scan over a different quarter of the image. ## Claims ### Claim 1 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; storing a distance image in memory and initializing that distance image on the basis of the seed image; 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 that distance being a shortest geodesic 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, such that each image element of the distance image is processed at most a single time by the thread executing the forward raster scan and at most a single time by the thread executing the backward raster scan, each image element of the distance image being processed twice by the at least two threads combined. ### Claim 2 (depends on 1) A method as claimed in claim 1 wherein the cross-over condition is that half the image elements of the distance image have been processed. ### Claim 3 (depends on 1) A method as claimed in claim 1 which comprises receiving a height image and using the processor to assign geodesic distance values to the distance image using the height image. ### Claim 4 (depends on 1) A method as claimed in claim 1 wherein the image is selected from any of: a 2 dimensional image, a 3 dimensional image and an image of more than 3 dimensions. ### Claim 5 (depends on 1) A method as claimed in claim 1 wherein the distance image comprises a two dimensional or higher dimensional pixel grid. ### Claim 6 (depends on 1) A method as claimed in claim 1 wherein the step of receiving the seed image comprises obtaining a probability distribution describing belief about whether a given image element is a member of the seed region. ### Claim 7 (depends on 1) A method as claimed in claim 1 wherein the step of synchronizing the two threads comprises: when a first one of the thread's raster scan reaches the middle of the distance image pausing execution of that first thread until the second thread's raster scan reaches the middle of the distance image. ### Claim 8 (depends on 1) A method as claimed in claim 1 wherein the windows are arranged to provide a particular distance metric selected from any of: chamfer 3×3, city block, chessboard, chamfer 5×5 and chamfer 7×7. ### Claim 9 (depends on 1) A method as claimed in claim 1 wherein the windows are arranged to provide a city block metric and wherein the method comprises using the at least one processor to execute four threads in parallel with each thread executing a raster scan over a different quarter of the distance image, waiting to synchronize with the other threads and then continuing its raster scan over another quarter of the distance image. ### Claim 10 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. ### Claim 11 (depends on 10) A method as claimed in claim 10 which is carried out at a gaming apparatus having a hands-free user interface, the method further comprising identifying at least two players based at least in part on the distance image. ### Claim 12 (depends on 10) A method as claimed in claim 10 wherein the cross-over condition is that half the image elements of the distance image have been processed. ### Claim 13 (depends on 10) A method as claimed in claim 10 wherein the step of receiving the seed image comprises obtaining a probability distribution describing belief about whether a given image element is a member of the seed region. ### Claim 14 (depends on 10) A method as claimed in claim 10 wherein the step of synchronizing the two threads comprises: when a first one of the thread's raster scan meets a cross-over condition pausing execution of that first thread until the second thread's raster scan meets the cross-over condition. ### Claim 15 (depends on 10) A method as claimed in claim 10 wherein the windows are arranged to provide a particular distance metric selected from any of: chamfer 3×3, city block, chessboard, chamfer 5×5 and chamfer 7×7. ### Claim 16 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. ### Claim 17 (depends on 16) A distance transform engine as claimed in claim 16 wherein the processor is arranged to synchronize the two threads by: when a first one of the thread's raster scan meets a cross-over condition pausing execution of that first thread until the second thread's raster scan meets the cross-over condition. ### Claim 18 (depends on 16) A distance transform engine as claimed in claim 16 wherein the seed region comprises a probability distribution describing belief about whether a given image element is a member of the seed region. ### Claim 19 (depends on 16) A distance transform engine as claimed in claim 16 wherein the processor is arranged to use windows which provide a particular distance metric selected from any of: chamfer 3×3, city block, chessboard, chamfer 5×5 and chamfer 7×7. ### Claim 20 (depends on 16) A distance transform engine as claimed in claim 16 wherein the processor is arranged to execute four threads in parallel, with each thread executing a raster scan over a different quarter of the distance image, waiting to synchronize with the other threads and then continuing its raster scan over another quarter of the distance image.