# US 2008/0187197 A1 · Method and system for segmentation of tubular structures using pearl strings

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2008/0187197 A1
- Document ID: US20080187197A1
- Status: Published application
- Kind: A1
- Application number: 12/012,385
- Filed: 2008-02-01
- Published: 2008-08-07
- Earliest claimed: 2007-02-02
- Assignees: Siemens Aktiengesellschaft
- Inventors: Gregory G. Slabaugh; Gozde Unal; Tong Fang; Brian Whited; Jarek Rossignnac
- Web page: https://patentgrep.com/patent/US20080187197A1

## CPC

- G06T 7/149: involving deformable models, e.g. active contour models
- G06T 7/11: Region-based segmentation
- G06T 2207/30101: Blood vessel; Artery; Vein; Vascular
- G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL

## Abstract

A method and system for segmenting tubular or stroke-like structures in 2D images is disclosed. Examples of such structures include, but are not limited to, blood vessels, bones, roads, rivers, electrical wirings, and brush-strokes. User inputs identifying a first region on the image inside of a tubular structure and a second region of the image outside of the tubular structure are received. Based on this information, an ordered series of pearls are generated along the tubular structure. Pearls are 2D disks, each having a center location and a radius determined based on local pixel intensities in the image. A continuous model of the tubular structure is generated by interpolating the center locations and radii of the ordered series of pearls.

## Claims

### Claim 1

A method for segmenting a tubular structure in a 2D image, comprising:
generating an ordered series of pearls along the tubular structure, wherein each pearl is a 2D disk having a center location and radius determined based on local pixel intensities inside of the pearl.

### Claim 2 (depends on 1)

The method of claim 1, further comprising:
generating a continuous model of the tubular structure using the center locations and the radii of the ordered series of pearls.

### Claim 3 (depends on 2)

The method of claim 2, wherein said step of generating a continuous model of the tubular structure comprises at least one of:
generating a curve in three-dimensional space of x, coordinates, y-coordinates, and radii, using of a subdivision rule that interpolates the center locations and the radii of the ordered series of pearls;
fitting a piecewise polynomial model to the pearl centers and the radii of the ordered series of pearls; and
fitting a tangent curve to consecutive pearls in the ordered series of pearls, on opposite sides of each pearl.

### Claim at position 4 (depends on 1)

4 The method of claim 1, further comprising:
receiving user inputs identifying a first region in said 2D image inside of the tubular structure and a second region in said 2D image outside of the tubular structure; and
estimating a classification function that classifies a pixel in said 2D image as inside or outside of the object being segmented, based on the first and second regions, respectively.

### Claim 5 (depends on 4)

The method of claim 4, wherein said step of estimating a classification function comprises:
estimating first and second probability densities for the first and second regions, respectively, using non-parametric density estimation based on the pixel intensities in the first and second regions, wherein a pixel in said 2D image is determined to be inside or outside of the tubular structure based on the first and second probability densities.

### Claim at position 6 (depends on 1)

6 The method of claim 1, wherein said step of generating an ordered series of pearls comprises, for each pearl:
(a) adjusting the center location of the pearl based on a function of the pixels that are in the pearl and classified as outside of the tubular structure;
(b) adjusting the radius of the pearl based on a function of the pixels in the pearl that are classified as inside of the tubular structure; and
(c) repeating steps (a) and (b) until the center location and the radius of the pearl converge.

### Claim 7 (depends on 6)

The method of claim 6, wherein steps (a) and (b) are performed subject to constraints on a distance between the center of a current pearl and the center of a previous pearl, where the constraints are defined at least in terms of the respective radii of the current and previous pearls.

### Claim 8 (depends on 7)

The method of claim 7, wherein the constraints comprise a minimal constraint dmin(ri−1,ri) and maximal constraint dmax(ri−1,ri) that are linear functions dmin,max(ri−1,ri)=αri−1+bri, with bounds dmin(ri−1,ri)=ri/2 and dmax(ri−1,ri)=ri−1+ri.

### Claim 9 (depends on 6)

The method of claim 6, wherein said step of generating an ordered series of pearls further comprises, for each pearl:
(d) detecting connected components of pixels classified as in the tubular structure in a region surrounding the pearl;
(e) if the number of connected components detected is one, terminating said ordered series of pearls; and
(f) if the number of connected components detected is greater than one, determining at least one direction from the center of the pearl corresponding to at least one of the connected components; and
(g) initializing at least one next pearl in said at least one direction.

### Claim 10 (depends on 9)

The method of claim 9, wherein step (f) comprises if the number of connected components is greater than two, determining that a bifurcation exists in said tubular structure and determining multiple directions corresponding to multiple branches of the bifurcation, and step (g) comprises initializing a next pearl in each branch of the bifurcation.

### Claim 11 (depends on 6)

The method of claim 6, wherein said step of generating an ordered series of pearls further comprises, for each pearl:
(d) determining whether the pearl intersects with any previous pearls, excluding a number of pearls immediately preceding the pearl in the ordered series of pearls; and
(e) if the pearl intersects with a previous pearl, linking the pearl to the previous pearl, such that the ordered series of pearls forms a loop, and terminating growth of said ordered series of pearls.

### Claim at position 12 (depends on 1)

12 The method of claim 1, wherein said step of generating an ordered series of pearls comprises:
receiving an initial seed point and direction; and
sequentially generating pearls starting at said initial seed point and moving in said direction along the tubular structure by iteratively estimating the center location and radius for each pearl to fit each pearl to the tubular structure, until a stop condition is met.

### Claim 13 (depends on 2)

The method of claim 2, where said step of generating a continuous model of the tubular structure by interpolating the center locations and the radii of the ordered series of pearls comprises:
interpolating the center locations and the radii of the ordered series of pearls using iterative subdivision, which at each iteration introduces a new pearl between consecutive pearls in the ordered series of pearls.

### Claim 14 (depends on 1)

The method of claim 1, wherein said tubular structure represents a vascular structure.

### Claim 15 (depends on 1)

The method of claim 1, wherein said 2D image is a satellite image.

### Claim 16 (depends on 2)

The method of claim 2, further comprising:
displaying the continuous model of the tubular structure; and
receiving a user input in response to displaying the continuous model of the tubular structure.

### Claim 17 (depends on 16)

The method of claim 16, further comprising at least one of:
deleting a branch of the tubular structure modeled by the ordered series of pearls in response to receiving said user input; and
initiating an ordered series of pearl at a branch of the tubular structure not yet modeled by the ordered series of pearls in response to receiving said user input.

### Claim 18 (depends on 1)

The method of claim 1, wherein said step of generating an ordered series of pearls along the tubular structure comprises:
receiving a user input tracing a path along the tubular structure; and
generating the pearls at samples along the path in real time as the user input is being received.

### Claim 19

An apparatus for segmenting a tubular structure in a 2D image, comprising:
means for generating an ordered series of pearls along the tubular structure, wherein each pearl is a 2D disk having a center location and radius determine based on local pixel intensities inside of the pearl.

### Claim 20 (depends on 19)

The apparatus of claim 19, further comprising:
means for generating a continuous model of the tubular structure using the center locations and the radii of the ordered series of pearls.

### Claim 21 (depends on 19)

The apparatus of claim 19, wherein said means for generating an ordered series of pearls comprises:
means for iteratively adjusting the center location of each pearl based on pixels that are in that pearl and outside of the tubular structure;
means for iteratively adjusting the radius of each pearl based on a function of the pixels in that pearl that are inside of the tubular structure; and
means for determining whether the center location and radius of each pearl have converged.

### Claim 22 (depends on 20)

The apparatus of claim 20, further comprising:
means for displaying the continuous model of the tubular structure; and
means for receiving a user input in response to displaying the continuous model of the tubular structure.

### Claim 23

A computer readable medium encoded with computer executable instructions for segmenting a tubular structure in a 2D image, the computer executable instructions defining a step comprising:
generating an ordered series of pearls along the tubular structure, wherein each pearl is a 2D disk having a center location and radius determine based on local pixel intensities inside of the pearl.

### Claim 24 (depends on 23)

The computer readable medium of claim 23, further comprising computer executable-instructions defining the step of:
generating a continuous model of the tubular structure using the center locations and the radii of the ordered series of pearls.

### Claim 25 (depends on 23)

The computer readable medium of claim 23, wherein the computer executable instructions defining the step of generating an ordered series of pearls comprise computer executable instructions defining the steps of, for each pearl:
(a) adjusting the center location of the pearl based on pixels that are in the pearl and outside of the tubular structure;
(b) adjusting the radius of the pearl based on a function of the pixels in the pearl that are inside of the tubular structure; and
(c) repeating steps (a) and (b) until the center location and the radius of the pearl converge.
