# US 7,609,887 B2 · System and method for toboggan-based object segmentation using distance transform > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 7,609,887 B2 - Document ID: US7609887B2 - Status: Granted - Kind: B2 - Application number: 11/145,888 - Filed: 2005-06-06 - Published: 2005-12-08 - Granted: 2009-10-27 - Earliest claimed: 2004-06-07 - Assignees: Siemens Medical Solutions USA, Inc. - Inventors: Jianming Liang; Luca Bogoni - Web page: https://patentgrep.com/patent/US7609887B2 ## CPC - G06T 7/0012: {Biomedical image inspection} - G06T 7/11: Region-based segmentation - G06T 7/155: involving morphological operators - G06V 10/267: {by performing operations on regions, e.g. growing, shrinking or watersheds} - G06T 2207/10081: Computed x-ray tomography [CT] - G06T 2207/20041: Distance transform - G06T 2207/20152: Watershed segmentation - G06T 2207/30028: Colon; Small intestine - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract A method of segmenting an object in a digital image comprising providing a digital image comprising a plurality of intensities corresponding to a domain of points in a N-dimensional space, selecting a region of interest in the image, determining a threshold intensity value for points in said region of interest, wherein an object of interest is defined by points with an intensity above a first pre-determined threshold, computing a distance map for each point in said object of interest, tobogganing each point in said object of interest based on said distance map, and selecting a cluster based on the results of said tobogganing. ## Claims ### Claim 1 A method of segmenting an object in a digital image, comprising the steps of: providing a digital image comprising a plurality of intensities corresponding to a domain of points in a N-dimensional space; computing a distance map for a plurality of points in said image; tobogganing each of said plurality of points in said image based on said distance map; selecting a plurality of clusters, wherein said selected clusters are associated with a set of labels; selecting one of said plurality of clusters; identifying surface points based on said distance map, wherein a surface point is a point on a border of an object of interest; computing a centroid of the surface points; adding to said selected cluster those points corresponding to other labeled clusters within a preset distance from said centroid; and wherein the computing steps, the selecting steps, the identifying step and the adding step are performed by a computer. ### Claim 2 (depends on 1) The method of claim 1, further comprising selecting a region of interest in the image, wherein said distance map is computed for points in said region of interest. ### Claim 3 (depends on 2) The method of claim 2, further comprising imposing a constraint on the intensity values of the points in said region of interest, wherein an object of interest is defined by points that satisfy said constraint. ### Claim 4 (depends on 3) The method of claim 3, further comprising binarizing said region of interest based on said constraint, wherein pixels whose intensity value satisfy said constraint are assigned one binary value, and pixels whose intensity value do not satisfy said constraint are assigned another binary value. ### Claim 5 (depends on 3) The method of claim 3, wherein said constraint takes the form of an inequality relationship between a pixel value and one or more threshold values. ### Claim 6 (depends on 5) The method of claim 5, wherein said inequality includes a first threshold value and a second threshold value greater than said first threshold value, said object of interest is further defined by points with an intensity above said first threshold value and below a second pre-determined threshold, and further comprising forming a ternary map of said image, wherein pixels whose intensity is below said first threshold are assigned a first ternary value, pixels whose intensity is equal to or above said second threshold are assigned a second ternary value, and pixels whose intensity is between said first threshold and said second threshold are assigned a third intensity value, wherein said distance is computed for those pixels corresponding to the third ternary value. ### Claim 7 (depends on 6) The method of claim 6, wherein the distance map for each point in said object of interest is determined by the distance of each point in said object of interest to a nearest point with a first ternary value. ### Claim 8 (depends on 1) The method of claim 1, wherein said distance map for each point is determined by the distance of each point in said an object of interest to a nearest point outside said object of interest. ### Claim 9 (depends on 8) The method of claim 8, wherein said distance map is a Euclidean distance. ### Claim 10 (depends on 1) The method of claim 1, wherein tobogganing each point comprises sliding each point towards a nearest neighbor point with a largest distance magnitude. ### Claim 11 (depends on 10) The method of claim 10, wherein a point whose distance magnitude is greater than that of its nearest neighbors is a concentration location that does not slide. ### Claim 12 (depends on 11) The method of claim 11, wherein a cluster is defined by a group of points that all slide to a same concentration location. ### Claim 13 (depends on 1) The method of claim 1, wherein said steps of identifying surface points, computing a centroid, and adding to said selected cluster are repeated until no new points corresponding to other labeled clusters are added to the selected cluster, and further comprising extracting said object of interest as defined by said surface points. ### Claim 14 (depends on 1) The method of claim 1, further comprising determining a distance threshold, and tobogganing only those pixels in the object of interest whose distance map is less than the distance threshold. ### Claim 15 A program storage device readable by a computer, tangibly embodying a program of instructions executable by the computer to perform method steps for segmenting an object in a digital image, said method comprising the steps of: providing a digital image comprising a plurality of intensities corresponding to a domain of points in a N-dimensional space; computing a distance map for a plurality of points in said image; tobogganing each of said plurality of points in said image based on said distance map; selecting a plurality of clusters, wherein said selected clusters are associated with a set of labels; selecting one of said plurality of clusters; identifying surface points based on said distance map, wherein a surface point is a point on a border of an object of interest; computing a centroid of the surface points; and adding to said selected cluster those points corresponding to other labeled clusters within a preset distance from said centroid. ### Claim 16 (depends on 15) The computer readable program storage device of claim 15, the method further comprising selecting a region of interest in the image, wherein said distance map is computed for points in said region of interest. ### Claim 17 (depends on 16) The computer readable program storage device of claim 16, the method further comprising imposing a constraint on the intensity values of the points in said region of interest, wherein an object of interest is defined by points that satisfy said constraint. ### Claim 18 (depends on 17) The computer readable program storage device of claim 17, the method further comprising binarizing said region of interest based on said constraint, wherein pixels whose intensity value satisfy said constraint are assigned one binary value, and pixels whose intensity value do not satisfy said constraint are assigned another binary value. ### Claim 19 (depends on 17) The computer readable program storage device of claim 17, wherein said constraint takes the form of an inequality relationship between a pixel value and one or more threshold values. ### Claim 20 (depends on 19) The computer readable program storage device of claim 19, wherein said inequality includes a first threshold value and a second threshold value greater than said first threshold value, said object of interest is further defined by points with an intensity above said first threshold value and below a second pre-determined threshold, and further comprising forming a ternary map of said image, wherein pixels whose intensity is below said first threshold are assigned a first ternary value, pixels whose intensity is equal to or above said second threshold are assigned a second ternary value, and pixels whose intensity is between said first threshold and said second threshold are assigned a third intensity value, wherein said distance is computed for those pixels corresponding to the third ternary value. ### Claim 21 (depends on 20) The computer readable program storage device of claim 20, wherein the distance map for each point in said object of interest is determined by the distance of each point in said object of interest to a nearest point with a first ternary value. ### Claim 22 (depends on 15) The computer readable program storage device of claim 15, wherein said distance map for each point is determined by the distance of each point in an object of interest to a nearest point outside said object of interest. ### Claim 23 (depends on 22) The computer readable program storage device of claim 22, wherein said distance map is a Euclidean distance. ### Claim 24 (depends on 15) The computer readable program storage device of claim 15, wherein tobogganing each point comprises sliding each point towards a nearest neighbor point with a largest distance magnitude. ### Claim 25 (depends on 24) The computer readable program storage device of claim 24, wherein a point whose distance magnitude is greater than that of its nearest neighbors is a concentration location that does not slide. ### Claim 26 (depends on 25) The computer readable program storage device of claim 25, wherein a cluster is defined by a group of points that all slide to a same concentration location. ### Claim 27 (depends on 15) The computer readable program storage device of claim 15, wherein said steps of identifying surface points, computing a centroid, and adding to said selected cluster are repeated until no new points corresponding to other labeled clusters are added to the selected cluster, and further comprising extracting said object of interest as defined by said surface points. ### Claim 28 (depends on 15) The computer readable program storage device of claim 15, the method further comprising determining a distance threshold, and tobogganing only those pixels in the object of interest whose distance map is less than the distance threshold.