# US 2008/0187199 A1 · Robust Vessel Tree Modeling > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2008/0187199 A1 - Document ID: US20080187199A1 - Status: Published application - Kind: A1 - Application number: 11/838,279 - Filed: 2007-08-14 - Published: 2008-08-07 - Earliest claimed: 2007-02-06 - Assignees: Siemens Corporate Research, Inc. - Inventors: Mehmet Akif Gulsun; Huseyin Tek - Web page: https://patentgrep.com/patent/US20080187199A1 ## CPC - G06T 7/12: Edge-based segmentation - G06T 7/149: involving deformable models, e.g. active contour models - G06T 7/162: involving graph-based methods - G06T 7/181: involving edge growing; involving edge linking - G06T 7/64: of convexity or concavity - G06V 10/457: {by analysing connectivity, e.g. edge linking, connected component analysis or slices} - G06T 2207/10081: Computed x-ray tomography [CT] - G06T 2207/20044: Skeletonization; Medial axis transform - G06T 2207/20101: Interactive definition of point of interest, landmark or seed - G06T 2207/20168: Radial search - G06T 2207/30101: Blood vessel; Artery; Vein; Vascular - G06T 2207/30172: Centreline of tubular or elongated structure - G06V 40/14: Vascular patterns - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract A method for extracting a local center-axis representation of a vessel, includes: placing first and second seed points in an image that includes the vessel, wherein the first and second seed points are placed near a beginning and an end of a centerline of the vessel; representing the image as a discrete graph having nodes and edges, wherein the first seed point is a source node and the second seed point is a goal node; and finding a minimum-cost path between the first and second seed points by computing a cost of edges between the first and second seed points, wherein the cost of each edge is reciprocal to a vesselness measure of the edge. ## Claims ### Claim 1 A method for computing a vesselness measure, comprising: initializing a plurality of rays from a center point of a vessel and collecting an intensity profile of the vessel and a background of the vessel along each ray; modeling each intensity profile by dividing the intensity profile into first, second and third intervals, wherein the first interval represents an intensity value inside the vessel, the second interval represents an intensity value outside the vessel and the third interval represents an intensity value between a boundary of the vessel and the background; for each ray, obtaining a difference between an originally measured intensity profile of the vessel and the background and the originally measured intensity profile's corresponding modeled intensity profile, wherein the difference is a fit measure of the ray; and summing the fit measures for each ray, wherein the total sum is the vesselness measure. ### Claim 2 (depends on 1) The method of claim 1, wherein the vesselness measure along a ray is strong near a center of the ray, drops rapidly near a boundary of the ray and is weak in a non-vascular area between the ray and another ray. ### Claim 3 (depends on 1) The method of claim 1, wherein the vessel is a blood vessel. ### Claim 4 A method for extracting a local center-axis representation of a vessel, comprising: placing first and second seed points in an image that includes a vessel, wherein the first and second seed points are placed near a beginning and an end of a centerline of the vessel; representing the image as a discrete graph having nodes and edges, wherein the first seed point is a source node and the second seed point is a goal node; and finding a minimum-cost path between the first and second seed points by computing a cost of edges between the first and second seed points, wherein the cost of each edge is reciprocal to a vesselness measure of the edge. ### Claim 5 (depends on 4) The method of claim 4, wherein the vesselness measure of an edge is computed orthogonal to the edge. ### Claim 6 (depends on 5) The method of claim 5, wherein fronts propagate fast towards a center of the vessel and slow towards walls of the vessel. ### Claim 7 (depends on 4) The method of claim 4, wherein the vessel is a blood vessel. ### Claim 8 A method for vessel tree modeling, comprising: computing minimum cost paths from a single source located in a vessel of a vessel tree; and computing centerlines of the vessel tree by using an accumulative cost map of the minimum cost paths, wherein the centerlines correspond to respective vessels in the vessel tree. ### Claim 9 (depends on 8) The method of claim 8, wherein computing the minimum cost paths from a single source comprises: placing a seed point in an image that includes the vessel tree; representing the image as a discrete graph having nodes and edges, wherein a cost of each edge is computed from a vesselness measure of the edge; starting a minimum cost propagation from the seed point by first setting an accumulative minimum cost at the seed point to zero and to infinity at every other point in the graph; representing discrete fronts that propagate by minimizing an accumulated vesselness measure, wherein the discrete fronts are pixels that separate pixels that have already been explored from pixels that have not yet been explored; computing the minimum cost propagation from the source for a first number of iterations by computing accumulative minimum costs and setting stop points of the discrete fronts as new sources; and re-computing accumulative minimum costs for each new source by propagating fronts from the new sources for a second number of iterations, wherein if the re-computed accumulative minimum costs are below a first threshold the minimum cost propagation is stopped and pixels that correspond to the discrete fronts that have been stopped are represented as sinks. ### Claim 10 (depends on 9) The method of claim 9, wherein the first number of iterations is greater than the second number of iterations. ### Claim 11 (depends on 10) The method of claim 10, wherein computing centerlines of the vessel tree by using an accumulative cost map of the minimum cost paths comprises: computing a distance from the originally placed seed to the sinks; ordering the sinks based on their corresponding computed distances; selecting a pixel having the largest distance and backtracking until the originally placed seed is reached or until a previously detected path is reached to detect a centerline path; computing a distance of the detected centerline and assigning the detected centerline to its corresponding sink; determining a radius along the detected centerline that corresponds to a maximum vesselness measure along the detected centerline; setting a saliency of the selected pixel by dividing the distance of the centerline by the radius; removing the selected pixel from the ordered list; and when the ordered list is empty, selecting pixels whose saliency is greater than a second threshold, wherein centerlines between the selected pixels and the originally placed seed correspond to respective vessels in the vessel tree. ### Claim 12 (depends on 8) The method of claim 8, wherein the vessel is a blood vessel. ### Claim 13 A system for computing a vesselness measure, comprising: a memory device for storing a program; a processor in communication with the memory device, the processor operative with the program to: initialize a plurality of rays from a center point of a vessel and collect an intensity profile of the vessel and a background of the vessel along each ray; model each intensity profile by dividing the intensity profile into first, second and third intervals, wherein the first interval represents an intensity value inside the vessel, the second interval represents an intensity value outside the vessel and the third interval represents an intensity value between a boundary of the vessel and the background; for each ray, obtain a difference between an originally measured intensity profile of the vessel and the background and the originally measured intensity profile's corresponding modeled intensity profile, wherein the difference is a fit measure of the ray; and sum the fit measures for each ray, wherein the total sum is the vesselness measure. ### Claim 14 (depends on 13) The system of claim 13, wherein the vesselness measure along a ray is strong near a center of the ray, drops rapidly near a boundary of the ray and is weak in a non-vascular area between the ray and another ray. ### Claim 15 A system for extracting a local center-axis representation of a vessel, comprising: a memory device for storing a program; a processor in communication with the memory device, the processor operative with the program to: place first and second seed points in an image that includes a vessel, wherein the first and second seed points are placed near a beginning and an end of a centerline of the vessel; represent the image as a discrete graph having nodes and edges, wherein the first seed point is a source node and the second seed point is a goal node; and find a minimum-cost path between the first and second seed points by computing a cost of edges between the first and second seed points, wherein the cost of each edge is reciprocal to a vesselness measure of the edge. ### Claim 16 (depends on 15) The system of claim 15, wherein the vesselness measure of an edge is computed orthogonal to the edge. ### Claim 17 (depends on 16) The system of claim 16, wherein fronts propagate fast towards a center of the vessel and slow towards walls of the vessel. ### Claim 18 A system for vessel tree modeling, comprising: a memory device for storing a program; a processor in communication with the memory device, the processor operative with the program to: compute minimum cost paths from a single source located in a vessel of a vessel tree; and compute centerlines of the vessel tree by using an accumulative cost map of the minimum cost paths, wherein the centerlines correspond to respective vessels in the vessel tree. ### Claim 19 (depends on 18) The system of claim 18, wherein the processor is further operative with the program when computing the minimum cost paths from a single source to: place a seed point in an image that includes the vessel tree; represent the image as a discrete graph having nodes and edges, wherein a cost of each edge is computed from a vesselness measure of the edge; start a minimum cost propagation from the seed point by first setting an accumulative minimum cost at the seed point to zero and to infinity at every other point in the graph; represent discrete fronts that propagate by minimizing an accumulated vesselness measure, wherein the discrete fronts are pixels that separate pixels that have already been explored from pixels that have not yet been explored; compute the minimum cost propagation from the source for a first number of iterations by computing accumulative minimum costs and setting stop points of the discrete fronts as new sources; and re-compute accumulative minimum costs for each new source by propagating fronts from the new sources for a second number of iterations, wherein if the re-computed accumulative minimum costs are below a first threshold the minimum cost propagation is stopped and pixels that correspond to the discrete fronts that have been stopped are represented as sinks. ### Claim 20 (depends on 19) The system of claim 19, wherein the first number of iterations is greater than the second number of iterations. ### Claim 21 (depends on 20) The system of claim 20, wherein the processor is further operative with the program when computing centerlines of the vessel tree by using an accumulative cost map of the minimum cost paths to: compute a distance from the originally placed seed to the sinks; order the sinks based on their corresponding computed distances; select a pixel having the largest distance and backtrack until the originally placed seed is reached or until a previously detected path is reached to detect a centerline path; compute a distance of the detected centerline and assign the detected centerline to its corresponding sink; determine a radius along the detected centerline that corresponds to a maximum vesselness measure along the detected centerline; set a saliency of the selected pixel by dividing the distance of the centerline by the radius; remove the selected pixel from the ordered list; and when the ordered list is empty, select pixels whose saliency is greater than a second threshold, wherein centerlines between the selected pixels and the originally placed seed correspond to respective vessels in the vessel tree.