公开(公告)号：US07844113B2

公开(公告)日：2010-11-30

申请号：US11685815

申请日：2007-03-14

申请人： Andrew Delong ,  Yuri Boykov ,  Daphne Yu

发明人： Andrew Delong ,  Yuri Boykov ,  Daphne Yu

IPC分类号： G06K9/34

CPC分类号： G06T7/162 ,  G06T7/11 ,  G06T7/12

摘要： A region-based push-relabel formulation is disclosed that removes the requirement that the entire graph should fit into the computer memory and yields an implementation that can reduce the required size and redundancy of accesses to the data memory, thus improving speed performance, while allowing for an efficient parallel processing implementation. The algorithm assigns all vertices that are not part of the sources or sinks with a value of 1. Sinks are assigned with zeros and sources are assigned a label equal to the number of their vertices. The preflow is then pushed from the sources to their neighbors, if any. When the preflow has all reached the boundaries, an adjacent region of the neighboring set is selected and preflow is pushed within this region. When the values of the preflow have been exhausted, region relabeling is done to update the label values. This is repeated within the region until all preflow has exited to the boundary of this region. The operation is then repeated for the neighboring regions that now contain the preflow. Regions which have no preflow may be skipped, thereby realizing a savings in processing resources.

摘要翻译： 公开了一种基于区域的推 - 重新标签公式，其消除了整个图形应该适合于计算机存储器的要求，并且产生可以减少对数据存储器的访问所需的大小和冗余度的实现，从而提高速度性能，同时允许 用于高效的并行处理实现。 算法将不是源或汇的一部分的所有顶点赋值为1。将使用零分配陷阱，并为源分配一个等于其顶点数的标签。 然后将预流从源推送到其邻居（如果有的话）。 当预流全部达到边界时，选择相邻集合的相邻区域，并且在该区域内推进预流。 当预流的值已经耗尽时，进行区域重新标签来更新标签值。 这在区域内重复，直到所有预流已经退出到该区域的边界。 然后对于现在包含预流的相邻区域重复操作。 可以跳过没有预先流动的区域，从而实现了处理资源的节省。

公开(公告)号：US20070286483A1

公开(公告)日：2007-12-13

申请号：US11685815

申请日：2007-03-14

申请人： Andrew Delong ,  Yuri Boykov ,  Daphne Yu

发明人： Andrew Delong ,  Yuri Boykov ,  Daphne Yu

IPC分类号： G06K9/20

CPC分类号： G06T7/162 ,  G06T7/11 ,  G06T7/12

摘要： A region-based push-relabel formulation is disclosed that removes the requirement that the entire graph should fit into the computer memory and yields an implementation that can reduce the required size and redundancy of accesses to the data memory, thus improving speed performance, while allowing for an efficient parallel processing implementation. The algorithm assigns all vertices that are not part of the sources or sinks with a value of 1. Sinks are assigned with zeros and sources are assigned a label equal to the number of their vertices. The preflow is then pushed from the sources to their neighbors, if any. When the preflow has all reached the boundaries, an adjacent region of the neighboring set is selected and preflow is pushed within this region. When the values of the preflow have been exhausted, region relabeling is done to update the label values. This is repeated within the region until all preflow has exited to the boundary of this region. The operation is then repeated for the neighboring regions that now contain the preflow. Regions which have no preflow may be skipped, thereby realizing a savings in processing resources.

摘要翻译： 公开了一种基于区域的推 - 重新标签公式，其消除了整个图形应该适合于计算机存储器的要求，并且产生可以减少对数据存储器的访问所需的大小和冗余度的实现，从而提高速度性能，同时允许 用于高效的并行处理实现。 该算法将不是源或汇的一部分的所有顶点赋值为1. Sinks分配为零，并为源分配一个等于其顶点数的标签。 然后将预流从源推送到其邻居（如果有的话）。 当预流全部达到边界时，选择相邻集合的相邻区域，并且在该区域内推进预流。 当预流的值已经耗尽时，进行区域重新标签来更新标签值。 这在区域内重复，直到所有预流已经退出到该区域的边界。 然后对于现在包含预流的相邻区域重复操作。 可以跳过没有预先流动的区域，从而实现了处理资源的节省。

公开(公告)号：US07444019B2

公开(公告)日：2008-10-28

申请号：US11058336

申请日：2005-02-15

申请人： Yuri Boykov ,  Gianluca Paladini

发明人： Yuri Boykov ,  Gianluca Paladini

IPC分类号： G06K9/00 ,  G06K9/34

CPC分类号： G06T7/162 ,  G06T7/12 ,  G06T2207/10072 ,  G06T2207/30004

摘要： A method of segmenting an image includes representing an image by a grid with a plurality of nodes, terminals, and edges, the terminals including a source and a sink. The edges include n-links and t-links, where each n-link connects a pair of nodes, and the t-links connect a node to a terminal, and each t-link and n-link has an associated cost. The method includes initializing a node height table, a flow excess table, a t-link capacity table, and an n-link capacity table based on the t-link and n-link costs, and updating the node height table, the flow excess table, the t-link capacity table, the said n-link capacity table in parallel for all nodes until the flow excess table is zero for all nodes. The method steps are performed in parallel for all nodes on a graphics processing unit.

摘要翻译： 分割图像的方法包括通过具有多个节点，终端和边缘的网格表示图像，所述终端包括源和宿。 这些边缘包括n链路和t链路，其中每个n链路连接一对节点，并且t链路将节点连接到终端，并且每个t链路和n链路都具有相关联的成本。 该方法包括基于t链路和n链路成本初始化节点高度表，流量过剩表，t链路容量表和n链路容量表，更新节点高度表，流量过剩 表，t链路容量表，所有节点的所述n链路容量表并行，直到所有节点的流量多余表为零。 对图形处理单元上的所有节点并行执行方法步骤。

公开(公告)号：US06744923B1

公开(公告)日：2004-06-01

申请号：US09650592

申请日：2000-08-30

申请人： Ramin D. Zabih ,  Olga Veksler ,  Yuri Boykov

发明人： Ramin D. Zabih ,  Olga Veksler ,  Yuri Boykov

IPC分类号： G06K970

CPC分类号： G06K9/342 ,  G06K9/20 ,  G06K9/6224 ,  G06K2209/40 ,  G06T7/593

摘要： Many tasks in computer vision involve assigning a label, such as disparity for depth of field data to every pixel. Energy minimization may be used to accomplish this labeling. The present invention provides an efficient way of minimizing energy functions in assigning labels to pixels. Two methods of using graph cuts to compute a local minimum are described. The first move is an &agr;&bgr; swap. For a pair of labels, &agr;, &bgr;, this move swaps the labels between an arbitrary set of pixels labeled a and another arbitrary set of pixels labeled &bgr;. The first method generates a labeling such that there is no swap move that decreases the energy. The second move is the &agr;-expansion. For a label &agr;, this move assigns an arbitrary set of pixels with the label &agr;.

摘要翻译： 计算机视觉中的许多任务涉及到为每个像素分配诸如景深数据的差异的标签。 能量最小化可用于完成此标签。 本发明提供了一种在向像素分配标签时最小化能量功能的有效方式。 描述了使用图形切割计算局部最小值的两种方法。 第一个动作是字母交换。 对于一对标签（alpha，beta），此移动将标记为任意一组像素的标记与另一个任意的标记为β的像素组之间的标签进行交换。 第一种方法产生标签，使得不存在降低能量的互换移动。 第二个举动是阿尔法扩张。 对于标签alpha，此移动将使用标签alpha分配任意一组像素。

公开(公告)号：US07634123B2

公开(公告)日：2009-12-15

申请号：US11370302

申请日：2006-03-08

申请人： Charles Florin ,  Romain Moreau-Gobard ,  Yuri Boykov ,  Gareth Funka-Lea

发明人： Charles Florin ,  Romain Moreau-Gobard ,  Yuri Boykov ,  Gareth Funka-Lea

IPC分类号： G06K9/00

CPC分类号： G06K9/38 ,  G06T7/12 ,  G06T7/149 ,  G06T2207/10081 ,  G06T2207/10088 ,  G06T2207/30048

摘要： A method and related system for automatically and efficiently isolating the heart in Computer Tomography (CT) or Magnetic Resonance Imaging cardiac scans is disclosed. The method involves segmenting a heart within a set of volumetric data. In accordance with one aspect of the present invention, the set of volumetric data is processed to determine the minimum value of an energy function having a first term, a second term and a third term. The heart is segmented based on the processing of the set of volumetric data.

摘要翻译： 公开了一种用于在计算机断层扫描（CT）或磁共振成像心脏扫描中自动和有效隔离心脏的方法和相关系统。 该方法涉及在一组体积数据内分割心脏。 根据本发明的一个方面，处理一组体积数据以确定具有第一项，第二项和第三项的能量函数的最小值。 基于体积数据集合的处理来分割心脏。

公开(公告)号：US07536050B2

公开(公告)日：2009-05-19

申请号：US11772915

申请日：2007-07-03

申请人： Yuri Boykov ,  Marie-Pierre Jolly

发明人： Yuri Boykov ,  Marie-Pierre Jolly

IPC分类号： G06K9/34

CPC分类号： G06K9/342 ,  G06K9/6224 ,  G06T7/11 ,  G06T7/162 ,  G06T2207/20101

摘要： An image editing system comprises an input device for inputting an image, a graphical user interface for selecting background and object seeds for the image, and an image processor for editing the image. The image processor has various editing routines, including a segmentation routine that builds a graph associated with the image and uses a graph cut algorithm to cut the graph into segments. The user marks certain pixels as “object” or “background” to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and regional information. Graph cuts are used to find the globally optimal segementation of the image. The obtained solution gives the best balance of boundary and region properties satisfying the constraints.

摘要翻译： 图像编辑系统包括用于输入图像的输入装置，用于选择图像的背景和对象种子的图形用户界面，以及用于编辑图像的图像处理器。 图像处理器具有各种编辑例程，包括构建与图像相关联的图形的分割例程，并使用图形切割算法将图形切割成段。 用户将某些像素标记为“对象”或“背景”，为分割提供硬约束。 额外的软约束包含边界和区域信息。 图形切割用于查找图像的全局最佳分割。 得到的解得到满足约束条件的边界和区域性质的最佳平衡。

公开(公告)号：US20060239553A1

公开(公告)日：2006-10-26

申请号：US11370302

申请日：2006-03-08

申请人： Charles Florin ,  Romain Moreau-Gobard ,  Yuri Boykov ,  Gareth Funka-Lea

发明人： Charles Florin ,  Romain Moreau-Gobard ,  Yuri Boykov ,  Gareth Funka-Lea

IPC分类号： G06K9/34

CPC分类号： G06K9/38 ,  G06T7/12 ,  G06T7/149 ,  G06T2207/10081 ,  G06T2207/10088 ,  G06T2207/30048

摘要： A method and related system for automatically and efficiently isolating the heart in Computer Tomography (CT) or Magnetic Resonance Imaging cardiac scans is disclosed. The method involves segmenting a heart within a set of volumetric data. In accordance with one aspect of the present invention, the set of volumetric data is processed to determine the minimum value of an energy function having a first term, a second term and a third term. The heart is segmented based on the processing of the set of volumetric data.

公开(公告)号：US20050213837A1

公开(公告)日：2005-09-29

申请号：US11058336

申请日：2005-02-15

申请人： Yuri Boykov ,  Gianluca Paladini

发明人： Yuri Boykov ,  Gianluca Paladini

IPC分类号： G06T5/00 ,  H04L12/26

CPC分类号： G06T7/162 ,  G06T7/12 ,  G06T2207/10072 ,  G06T2207/30004

摘要： A method of segmenting an image includes representing an image by a grid with a plurality of nodes, terminals, and edges, the terminals including a source and a sink. The edges include n-links and t-links, where each n-link connects a pair of nodes, and the t-links connect a node to a terminal, and each t-link and n-link has an associated cost. The method includes initializing a node height table, a flow excess table, a t-link capacity table, and an n-link capacity table based on the t-link and n-link costs, and updating the node height table, the flow excess table, the t-link capacity table, the said n-link capacity table in parallel for all nodes until the flow excess table is zero for all nodes. The method steps are performed in parallel for all nodes on a graphics processing unit.

摘要翻译： 分割图像的方法包括通过具有多个节点，终端和边缘的网格表示图像，所述终端包括源和宿。 这些边缘包括n链路和t链路，其中每个n链路连接一对节点，并且t链路将节点连接到终端，并且每个t链路和n链路都具有相关联的成本。 该方法包括基于t链路和n链路成本初始化节点高度表，流量过剩表，t链路容量表和n链路容量表，更新节点高度表，流量过剩 表，t链路容量表，所有节点的所述n链路容量表并行，直到所有节点的流量多余表为零。 对图形处理单元上的所有节点并行执行方法步骤。

公开(公告)号：US20070292025A1

公开(公告)日：2007-12-20

申请号：US11772915

申请日：2007-07-03

申请人： Yuri Boykov ,  Marie-Pierre Jolly

发明人： Yuri Boykov ,  Marie-Pierre Jolly

IPC分类号： G06K9/34

CPC分类号： G06K9/342 ,  G06K9/6224 ,  G06T7/11 ,  G06T7/162 ,  G06T2207/20101

摘要： An image editing system comprises an input device for inputting an image, a graphical user interface for selecting background and object seeds for the image, and an image processor for editing the image. The image processor has various editing routines, including a segmentation routine that builds a graph associated with the image and uses a graph cut algorithm to cut the graph into segments. The user marks certain pixels as “object” or “background” to provide hard constraints for segmentation. Additional soft constraints incorporate both boundary and regional information. Graph cuts are used to find the globally optimal segementation of the image. The obtained solution gives the best balance of boundary and region properties satisfying the constraints.

摘要翻译： 图像编辑系统包括用于输入图像的输入装置，用于选择图像的背景和对象种子的图形用户界面，以及用于编辑图像的图像处理器。 图像处理器具有各种编辑例程，包括构建与图像相关联的图形的分割例程，并使用图形切割算法将图形切割成段。 用户将某些像素标记为“对象”或“背景”，为分割提供硬约束。 额外的软约束包含边界和区域信息。 图形切割用于查找图像的全局最佳分割。 得到的解得到满足约束条件的边界和区域性质的最佳平衡。

公开(公告)号：US06973212B2

公开(公告)日：2005-12-06

申请号：US09943035

申请日：2001-08-30

申请人： Yuri Boykov ,  Marie-Pierre Jolly

发明人： Yuri Boykov ,  Marie-Pierre Jolly

IPC分类号： G06T5/00 ,  G06K9/34

CPC分类号： G06K9/342 ,  G06K9/6224 ,  G06T7/11 ,  G06T7/162 ,  G06T2207/10072 ,  G06T2207/20101

摘要： Disclosed is a method of segmenting one or more objects from one or more backgrounds in an image, the method comprising defining a plurality of image nodes, each said image node corresponding to one or more pixels of said image, connecting pairs of adjacent nodes with n-links, each said n-link weighted with an n-link cost, defining a source node, defining a sink node, defining one or more object seeds, said object seeds corresponding to image nodes within said objects, defining one or more background seeds, said background seeds corresponding to image nodes within said backgrounds, connecting said source node with each said object seed with a plurality of t-links, connecting said sink node with each said background seed with a plurality of t-links, wherein each said t-links is weighted with a t-link cost, and calculating a segmentation cut having the smallest total cost of all cuts separating said source from said sink, wherein said total cost of each said cut is defined as the sum of the costs of all said n-links and t-links that each said cut severs.

摘要翻译： 公开了一种从图像中的一个或多个背景分割一个或多个对象的方法，所述方法包括定义多个图像节点，每个所述图像节点对应于所述图像的一个或多个像素，将相邻节点对与n 链接，每个所述n链路以n链路成本加权，定义源节点，定义汇聚节点，定义一个或多个对象种子，所述对象种子对应于所述对象内的图像节点，定义一个或多个背景种子 所述背景种子对应于所述背景内的图像节点，将所述源节点与每个所述对象种子连接多个t链路，将所述宿节点与每个所述背景种子连接多个t链路，其中每个所述t链路 链接以t链接成本加权，并且计算具有将所述源与所述宿分开的所有切割的总成本最小的分割切割，其中每个所述切割的总成本被定义为 所有这些切断的所有n链路和t链路的成本。