Abstract:
Approaches to segmentation or detection of objects and their boundaries in images (or other data sets) do not rely on machine learning approaches that aim to minimize pixel-level agreement between a computer and a human. Optimizing such pixel-level agreement does not, in general, provide the best possible result if boundary detection is a means to the ultimate goal of image segmentation, rather than an end in itself. In some examples, end-to-end learning of image segmentation specifically targets boundary errors with topological consequences, but otherwise does not require the computer to “slavishly” imitate human placement of boundaries. In some examples, this is accomplished by modifying a standard learning procedure such that human boundary tracings are allowed to change during learning, except at locations critical to preserving topology.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
       [0001]    This application claims the benefit of U.S. Provisional Application No. 61/169,550, filed Apr. 15, 2009, and U.S. Provisional Application No. 61/169,602, filed Apr. 15, 2009, which are incorporated herein by reference. 
     
    
     BACKGROUND 
       [0002]    This description relates to image and data segmentation. 
         [0003]    The problem of segmentation or identification of objects or groups in data sets has applications in a wide number of fields. In the field of automated image processing and computer vision, problems including detecting boundaries between objects and detecting the presence of objects can be a difficult problem. For example, the problem of boundary detection has a long history in computer vision. In some approaches in a first era, boundaries were detected using gradient filters. In some approaches in a second era, contextual information was incorporated through optimization of objective functions based on Markov random fields, graph partitioning, and other formalisms. Today a new trend is to use machine learning to improve accuracy by training a computer to emulate human boundary judgments. In a typical approach, a boundary detector is trained by minimizing its pixel-level disagreement with humans. 
         [0004]    One area of image processing in which boundary or object detection is important is in analysis of images of biological tissue. For instance, recent advances in electron microscopy (EM) have enabled the automated collection of nanoscale images of brain tissue. The resulting image datasets have renewed interest in automated computer algorithms for analyzing EM images. From the neuroscience perspective, development of such algorithms is important for the goal of finding connectomes, complete connectivity maps of a brain or piece of brain. To find connectomes, two image analysis problems must be solved. First, each synapse must be identified in the images. Second, the “wires” of the brain, its axons and dendrites, must be traced through the images. If both problems are solved, then it would be possible to trace the wires running from every synapse to the cell bodies of its parent neurons, thereby identifying all pairs of neurons connected by synapses. Other instances in which boundary or object detection in biological tissue is important is in analysis of medical images formed using computed tomography (CT) and magnetic resonance imaging (MRI) techniques, for example, locating and determining the extent of a tumor in the imaged tissue. 
         [0005]    One approach to these problems in image processing makes use of boundary detection based on local image characteristics. For instance, pixels in an image are automatically labeled as boundaries versus object, and based on the labeled pixels, the image is segmented into objects. The automated labeling of boundary pixels can be based on a parametric technique, and the parameters are determined in a training procedure in which a set of training images and their corresponding boundary labeling are used to determine the parameters to be used in processing unknown images. For example, training images are analyzed manually to identify boundary pixels in the images, and the parameters are optimized to minimize the error between predicted and hand labeled boundary pixels (e.g., using a Hamming distance metric). A measure of accuracy of such approaches can use a metric based on the resulting segmentation of the image. For example, the Rand Index provides the average number of pairs of pixels in an image that are correctly identified as belonging to the same versus different segments or objects in the image. 
       SUMMARY 
       [0006]    In a general aspect, certain approaches to segmentation or detection of objects and their boundaries in images (or other data sets) do not rely on machine learning approaches that aim to minimize pixel-level agreement between a computer and a human. Optimizing such pixel-level agreement does not, in general, provide the best possible result if boundary detection is a means to the ultimate goal of image segmentation, rather than an end in itself. In some examples, end-to-end learning of image segmentation specifically targets boundary errors with topological consequences, but otherwise does not require the computer to “slavishly” imitate human placement of boundaries. In some examples, this is accomplished by modifying a standard learning procedure such that human boundary tracings are allowed to change during learning, except at locations critical to preserving topology. 
         [0007]    In another aspect, in general, the approach used for image segmentation is applied to a number of scenarios in which one desires high-throughput and automated analysis of structures within images. For example, such applications may include segmenting and profiling morphological properties of cells, segmenting neurons in light or electron microscopic images, and segmenting structures within MRI or other medical imaging. 
         [0008]    In another aspect, in general, a system is applied to analysis of biological tissue. The system includes a segmentation apparatus configured to accept image data representing a three-dimensional image acquired from a biological sample, wherein the segmentation apparatus includes an input for accepting a data representation of segmentation parameters for controlling operation of the segmentation apparatus according to a segmentation procedure. The system also includes a parameter selection system configured to accept training image data and corresponding training segmentation data for a plurality of training images and produce the data representation of the segmentation parameters. The training segmentation data for a training image characterizes at least one of spatial extent of a plurality of objects in the training image and connectivity through a single object of pairs of locations in the training image. The parameter selection system is configured to select the segmentation parameters according to a parameter selection procedure that includes selecting the parameters according to a criterion based on at least one of (a) path connectivity between pairs of locations including path connectivity between non-adjacent locations and (b) a topology of the objects in the image. 
         [0009]    Aspects may include one or more of the following. 
         [0010]    The segmentation procedure includes determining a connectivity between pairs of locations according to the data representing the image and the segmentation parameters, and forming segments according to the determined connectivities. 
         [0011]    The parameter selection procedure includes determining parameters associated with connectivity between pairs of location, and wherein the parameter selection procedure applies a non-uniform reliance on locations in the training images according to contribution of estimated connectivity at those locations to the estimated segmentation of the images. 
         [0012]    The segmentation procedure determines a weighted connectivity between pairs of adjacent pixels of the training data, and forming the segments includes applying a threshold to the weighted connectivities to form binary connectivities and identifying pixels that are connected via sequences on adjacent pixels. For instance, the non-uniform reliance on pixel locations comprises a non-uniform reliance on pairs of adjacent pixels. 
         [0013]    The parameter selection procedure includes, for each of a plurality of pixel locations in the training images, identifying a pair of adjacent pixels on a path between the pair of pixel locations, and determining the non-uniform reliance on pairs of adjacent pixels according to the identified pairs of adjacent pixels. 
         [0014]    The parameter selection procedure includes iterating over a plurality of pairs of pixel locations in the training images, and for each pair of pixel locations, identifying a pair of adjacent pixels on a path between the pair of pixel locations according to a contribution of estimated connectivity between the pair of adjacent pixels to an estimated segmentation of the images and updating a subset of the segmentation parameters that affect an estimated weighted connectivity between the adjacent pixels. 
         [0015]    The parameter selection procedure includes iterating over a plurality of pairs of pixel locations, including pairs of non-adjacent pixel locations, in the training images and for each pair of pixel locations identifying a link between two pixel locations on a path between the pair of pixel locations, the identified link representing degree of linkage between the pair of pixel locations. In some examples, the degree of linkage comprises a maximum linkage, which may be defined as maximum over paths linking the pair of pixel locations of minimal linkage between adjacent pixel locations the path. 
         [0016]    The segmentation procedure includes determining a labeling as background versus object at locations according to the data representing the image and the segmentation parameters, and forming segments according to the determined labelings. 
         [0017]    The parameter selection procedure includes selecting the parameters according to a criterion based topology of the objects in the images. 
         [0018]    The parameter selection procedure includes jointly determining segmentation parameters and transformations of the training segmentation data associated with warpings of the segmentation data that maintain topology of the objects in the training images. 
         [0019]    The parameter selection procedure comprises alternating between a phase for updating segmentation parameters and a phase for transformation of the training segmentation data. 
         [0020]    Updating the segmentation parameters includes applying a gradient update according to a match between estimated pixel labelings and pixel labelings of the transformed segmentation data. 
         [0021]    The parameter selection procedure comprises alternating between a phase for updating segmentation parameters and a phase for transformation of the training segmentation data. 
         [0022]    The parameter selection procedure comprises jointly determining optimal segmentation parameters and transformation of the training segmentation data that maintains a set of topological properties of the training segmentations. 
         [0023]    In another aspect, in general, a system is applied to forming segments of items represented in a data set. The system includes a segmentation apparatus configured to accept the data set representing a plurality of items, wherein the segmentation apparatus includes an input for accepting a data representation of segmentation parameters for controlling operation of the segmentation apparatus according to a segmentation procedure. The system also includes a parameter selection system configured to accept training data sets and corresponding training segmentation data for a plurality of training data sets and produce the data representation of the segmentation parameters. The training segmentation data for a training data set characterizes connectivity through a single segment of pairs of items in the training data set. The parameter selection system is configured to select the segmentation parameters according to a parameter selection procedure that includes selecting the parameters according to a criterion based on path connectivity through sequences of pairs of items. 
         [0024]    Aspects can include one or more of the following features. 
         [0025]    The parameter selection procedure includes, for each training data set, forming a data representation correspond to a spanning tree in which nodes of the tree are associated with items of the data set. 
         [0026]    The parameter selection procedure includes, for pairs of items in the training data set, identifying a link on a path in the spanning tree between the pair of items, and updating parameters associated with that link according to the training segmentation data for the pair of items. 
         [0027]    In another aspect, in general, software is stored on a computer readable medium. The software comprises instructions for causing a data processing system to implement a segmentation module configured to accept image data representing a three-dimensional image acquired from a biological sample, wherein the segmentation apparatus includes an input for accepting a data representation of segmentation parameters for controlling operation of the segmentation apparatus according to a segmentation procedure. The system also implements a parameter selection module configured to accept training image data and corresponding training segmentation data for a plurality of training images and produce the data representation of the segmentation parameters, the training segmentation data for a training image characterizing at least one of spatial extent of a plurality of objects in the training image and connectivity through a single object of pairs of locations in the training image. The parameter selection system is configured to select the segmentation parameters according to a parameter selection procedure that includes selecting the parameters according to a criterion based on at least one of connectivity between pairs of locations and a topology of the objects in the image. 
         [0028]    Advantages of certain aspects can include or more of the following. 
         [0029]    The approach may be applied to the challenging application of tracing the branches of neurons in three-dimensional images of brain tissue taken by electron microscopy. The empirical results show a dramatic reduction in the number of split and merge errors. 
         [0030]    Other features and advantages of the invention are apparent from the following description, and from the claims. 
     
    
     
       DESCRIPTION OF DRAWINGS 
         [0031]      FIG. 1  is a block diagram of an image processing system. 
           [0032]      FIG. 2A  is a representation of a two-dimensional pixel map showing edge pixels of objects, and  FIG. 2B  is a representation of a corresponding affinity graph; 
           [0033]      FIGS. 3A and 3B  are representations of transformations of the representations shown in  FIGS. 2A and 2B , respectively; 
           [0034]      FIG. 4  is a block diagram of a first example of a segmentation apparatus; 
           [0035]      FIG. 5A  is a representation of a pixel segmentation, and  FIG. 5B  is a representation of weighted affinity between pixels and a corresponding binary affinity graph; 
           [0036]      FIG. 6  is a block diagram of a second example of a segmentation apparatus 
       
    
    
     DESCRIPTION 
     1 Introduction 
       [0037]    Referring to  FIG. 1 , a system  100  processes a biological sample  105 , and provides as output, for instance, a presentation image  155  or processed data  165 , or provides input to further processing  170 . The system  100  is described here in the context of an exemplary application related to analysis of biological tissue, but it should be understood that the techniques described below are applicable to a wider variety of image analysis, and more generally to a variety of data analysis tasks, as is outlined later in this description. 
         [0038]    In the system shown if  FIG. 1 , the biological sample  105  is processed in an imaging apparatus  110  to produce image data  115 . In some examples, the imaging apparatus comprises an electron microscope which processes a sample of brain tissue to produce three dimensional image data, for example, providing an intensity level at each voxel (i.e., three-dimensional pixel) location in a rectilinear (e.g., cubic) arrangement of pixel locations. In an example, one goal is to identify neurons in the image data. 
         [0039]    A segmentation apparatus  120  processes the image data  115  and produces segmentation data  125 . In some examples, the segmentation apparatus is implemented using a computer processor controlled by software instructions as well as segmentation parameters  145  stored on a computer readable media. In some examples, the segmentation data comprises a labeling of pixels according to distinct labels for each separate object, for example, using consecutive positive integers (1, 2, . . . ), or as background, for example, using an index zero. Such a labeling is referred to as a segmentation, S, where the label of a pixel j has value s j . The segmentation apparatus is parametric (or otherwise configurable or trainable) and is configured according to segmentation parameters  145 , which are determined, for instance, during a prior training phase which is described below. The segmentation parameters are stored on computer readable media in a form that controls and/or imparts functionality to the segmentation apparatus. 
         [0040]    In some examples, the segmentation data  125  may be used as an input to a display system  150 , for example, to produce a presentation image  155  that provides am operator (e.g., technician, researcher, physician or other clinician) with a view of the objects detected by the segmentation apparatus. The detected objects may be indicated in the presentation image in various ways, for example, using color, opacity, etc. In some examples, the clinician may be able to provide inputs that affect the segmentation, for example, providing an input (e.g., a threshold) that trades off detection of isolated objects versus merging of objects together. 
         [0041]    Generally, the training process that determines the segmentation parameters  145  makes use training image data  135 , which in general comprises the outputs of the imaging apparatus  110  for a corresponding set of biological samples (not shown). The training image data is labeled, for example in a manual labeling procedure  130 , to produce training segmentation data  137 . Generally, the training segmentation data identifies locations of objects in the training image data, for example, providing segmentation values for some or all of the pixels in the corresponding image data. A parameter selection system  140  processes the training image data  135  and corresponding training segmentation data  137  to produce the segmentation parameters  145  that are used by the segmentation apparatus  120  for the unknown image  105 . In some examples, the parameter selection system  140  is implemented using a computer processor. The parameter selection system  140  is matched to the segmentation apparatus  120  such that the segmentation parameters  145  that are passed between these modules link their functionality. 
         [0042]    Very generally, a number of approaches are described below in which the parameter selection system  140  selects the segmentation parameters  145  to match the overall structure of the objects in the training images, without necessarily attempting to reproduce a pixel-by-pixel match between automatically determined segmentations for the training image data  135  and the training segmentations  137  determined in the labeling process  130 . 
         [0043]    Before discussing the various approaches for implementing the segmentation apparatus and associated parameter selection system, a number of representations and characterizing metrics of image data are outlined. Various approached described below use one or both of the representations shown in  FIGS. 2A-B . First, referring to  FIG. 2A , a two-dimensional image is represented as having object regions A, B, and C, with the remainder of the image forming a background. Three-dimensional data can be similarly represented, however, for the sake of presentation, the examples below focus primarily on two-dimensional situations. A grid of square pixels is illustrated, with the pixel based boundary of the object regions being shown with a bold line. The image data itself is not illustrated. In general, each pixel is associated with a numerical scalar or vector of image features, for example, representing image intensity in one or more spectral bands. The pixels in the object regions at the boundary of the object regions are shown in gray, and are referred to as “boundary pixels.” 
         [0044]    Referring to  FIG. 2B , another representation of the image uses an affinity graph in which each node corresponds to one of the pixels. Edges join certain pairs of nodes such that each connected set of nodes corresponds to one of the object regions. In general, the edges in the representation form a disjoint connected subgraphs of a complete graph. For instance, the complete graph may include all edges between nearest neighbor nodes, for example, with four edges per node in two dimensions and six edges per node in three dimensions, or alternatively, eight edges per node in two dimensions and 26 edges per node in three dimensions. Note that the same connected sets of nodes may be achieved with different subgraphs, for instance, by removing edges that do not divide a connected set of nodes, therefore the binary affinity graph is not necessarily unique for any particular segmentation. 
         [0045]    Referring to  FIGS. 3A-B , minor changes in identification of boundary pixels or corresponding edges in a graph representation do not necessarily change the overall structure of the objects in a segmented image. In particular, certain changes may move the boundaries of objects somewhat, but do not change the overall structure of the segmentation. For example, referring to  FIG. 3A , an identification of the gray pixels as boundary pixels defines regions A′, B′, and C′, which do not exactly match regions A, B, and C, in  FIG. 2A , yet the result generally preserves the overall structure. 
         [0046]    To more precisely define the changes that are sufficiently minor to not affect the structure, a definition of “simple pixels” (also referred to below as “simple points”) is used. A binary image L is formed such that all the pixels in non-background regions (e.g., in regions A, B, and C, in  FIG. 2A ) are given a value 1, and all remaining pixels are given a value 0 to form the binary image L. A simple pixel is then defined as a location in the binary image L at which a pixel can be flipped to its complementary value without changing any topological properties of the image. More specifically, the simple pixels are points in a binary image that can be modified (i.e., flipped from foreground to background or vice versa) without altering topological properties of the image including the numbers of components, cavities, and in the case of 3D images, tunnels. We write simple (L) to denote the set of simple points of L. 
         [0047]    This definition of simple pixels is used to define a “warping” of a digital image. Specifically, given an initial binary image L*, then another binary image L is a warping of L* if a sequence of flips of simple points can yield L. In some examples, the allowable pixel flips are restricted to occur only in certain regions of the image, for example, within a prescribed distance of an edge in the original image L*. Note that given an original segmentation S*, a warping S can be defined to correspond to the warping of the related binary image. The notation L         L* is used to denote that L is an allowable warping of L*. 
         [0048]    Some approaches described below make used of segmentations based on affinity graphs. An affinity graph can be binary, for example, as shown in  FIGS. 2B and 3B , with the connected sets of nodes corresponding to objects. An affinity graph can also be weighted such that a edge joining a node i and a node j has a weight A ij . A binary affinity graph can be formed from a weighted affinity graph by retaining edges whose weights exceed a threshold value. 
         [0049]    It can be useful to introduce the concept of maximin affinity, which is defined for any pair of pixels in an affinity graph. Let           be the set of all paths in the graph that connect pixels i and j. For every path P in           there is an edge (or edges) with minimal affinity. This minimal affinity on a path P is written as 
         [0000]      min &lt;k,lεP A kl    
         [0000]    where          k,l         εP means that the edge between pixels k and/are in the path P. A maximin path P ij * is a path between pixels i and j that maximizes the minimal affinity, 
         [0000]        P   ij *=argmax Pε           min &lt;k,l&gt;εP   A   kl . 
         [0000]    The maximin affinity of pixels i and j is the affinity of the maximin edge, or the minimal affinity of the maximin path, P ij * 
         [0000]        A   ij *=max Pε           min &lt;k,l&gt;εP   A   kl . 
         [0000]    Based on these definitions, a pair of pixels is connected in the thresholded binary affinity graph if and only if their maximin affinity exceeds the threshold value. 
         [0050]    Pixel pairs can be classified as connected or disconnected by thresholding maximin affinities. Let Ŝ be the segmentation produced by thresholding the affinity graph A ij  and then finding connected components. Then the connectivity indicator function between pixel locations i and j is 
         [0000]      H(A ij *−θ) 
         [0000]    where H is the Heaviside step function and θ is the threshold applied to the affinities. 
         [0051]    As introduced above, one measure of a similarity between two segmentations, S and T, is the Rand Index. The Rand Index is a statistical measure of the similarity between two data clusterings, which can be used as a measurement of segmentation quality that can operate directly on a segmentation by interpreting a segmentation as a grouping of pixels into separate clusters. More formally, consider an image space X with N pixels {x 1 , . . . , x N } and two segmentations S and T which assign to each pixel location i an integer label {s i } and {t i } respectively. Then the Rand Index is a [0,1]-valued measure of the number of pairs of points having the same label relationship in S and T: 
         [0000]    
       
         
           
             
               R 
                
               
                 ( 
                 
                   S 
                   , 
                   T 
                 
                 ) 
               
             
             = 
             
               
                 
                   
                     ( 
                     
                       
                         
                           N 
                         
                       
                       
                         
                           2 
                         
                       
                     
                     ) 
                   
                   
                     - 
                     1 
                   
                 
                  
                 
                   
                     ∑ 
                     
                       i 
                       , 
                       
                         j 
                         ≠ 
                         i 
                       
                     
                   
                    
                   
                     δ 
                      
                     
                       ( 
                       
                         
                           
                             s 
                             i 
                           
                           = 
                           
                             s 
                             j 
                           
                         
                         , 
                         
                           
                             t 
                             i 
                           
                           = 
                           
                             t 
                             j 
                           
                         
                       
                       ) 
                     
                   
                 
               
               + 
               
                 δ 
                  
                 
                   ( 
                   
                     
                       
                         s 
                         i 
                       
                       ≠ 
                       
                         s 
                         j 
                       
                     
                     , 
                     
                       
                         t 
                         i 
                       
                       ≠ 
                       
                         t 
                         j 
                       
                     
                   
                   ) 
                 
               
             
           
         
       
     
         [0000]    Therefore, the Rand Index is 1 when the two segmentations perfectly match, and 0 when they completely disagree. 
         [0052]    The Rand Index effectively focuses on whether the overall grouping of points into separate segments is correct; subtle geometric differences between two segmentations will decrease the Rand Index but will be much less numerically significant than, for example, the erroneous merging of two regions. Conceptually the Rand Index focuses on whether a segmentation has achieved the correct connectivity between pixels (i.e., whether two pixels are connected or disconnected correctly). 
       2 First Embodiment 
       [0053]    A first embodiment of a segmentation apparatus  120  shown in  FIG. 1  is the segmentation apparatus  120 A shown in  FIG. 4 . This embodiment uses at its basis a classification approach for edges in an affinity graph. The image data  115  is passed to an edge classifier  212 . The classifier  212  outputs a weighted affinity graph, which provides a numerical degree to which each edge joining neighboring pixels in the image belongs to a same object versus forms a boundary between objects. The classifier  212  makes use of segmentation parameters  145 , which are trained using a procedure described below. The weighted affinity graph  216  is passed through a threshold function  218 , which transforms these numerical degrees into a binary affinity graph  220  (i.e., connectivity), and the component identifier  222  forms the connected components from the binary affinity to produce the segmentation data  125  at the output of the segmentation apparatus. 
         [0054]    A simplified two-dimensional example is illustrated in  FIG. 5A . In this figure, which represents a 6×6 pixel image (with pixels labeled A 1  through F 6  for discussion), a solid line  304  shows a human segmentation of the image into three connected components. A computer segmentation is illustrated by a dashed line  306 . As illustrated, the computer segmentation erroneously merges two of the true components (via pixel C 3 ), and erroneously splits a true component (via pixel F 4 ). Furthermore, the detailed boundaries of components do not match at pixels A 1 , A 6 , and D 6 . 
         [0055]    In this embodiment, very generally, training of the segmentation parameters  145  involves updating of the parameters for the edge classifier  212  to focus on edges in the weighted affinity graph that significantly affect the segmentation result. The computer segmentation is determined according to the edge affinity data associated with each of the links joining adjacent pixels. A portion of the affinity data is illustrated in  FIG. 5B  for a limited number of pixels, with quantities less than 0.5 being associated with boundaries and quantities greater than 0.5 being associated with a link joining two pixels within one component of the segmentation. Based on the thresholding at a value of 0.5, a portion of a resulting binary affinity graph is shown in  FIG. 5B . Note that the binary affinity graph incorrectly links nodes B 3 -C 3  and C 3 -D 3 , and erroneously breaks C 3 -C 4 , and is otherwise correct. 
         [0056]    In order to focus training on links that affect the segmentation, pairs of pixels are considered in the training. For example, a pair of pixels, B 3  and D 4  are considered. According to the manual segmentation as shown in  FIG. 5A , these pixels are truly in separated components. However, referring to  FIG. 5B , weighted link affinity data for links in the vicinity of these pixels, and binary affinity data based on thresholding the values in  FIG. 5B , shows that the computer segmentation links pixels B 3  and D 4  into a common component. The training to correct this error is focused on a particular edge by considering the paths joining the two pixels (e.g., B 3 -C 3 -C 4 -D 4 , or B 3 -C 3 -D 3 -D 4 ). Connectivity along a path is assessed according to the minimum affinity value, and the path with the largest such minimum value is attributed the error. For example, the path B 3 -C 3 -D 3 -D 4  has a minimum affinity value of 0.51 (at link C 3 -D 3 ), which is the maximum over the paths linking pixels B 3  and D 4 . Based on this identification of C 3 -D 3  being the critical link joining B 3  and D 4 , the weights for the classifier are adjusted so that the weighted affinity value for link C 3 -D 3  is driven down from 0.51 toward 0. 
         [0057]    In a similar manner, certain links may be associated with erroneous splitting of a segment. For example, paths from pixel F 1  to F 5  may identify the link F 3 -F 4  as being the link that causes the erroneous separation of pixels F 1  and F 5  into different components. 
         [0058]    Effectively, by considering a large number of pairs of pixels (e.g., all pairs of pixels, pairs of pixels within a fixed distance of one another, pairs of pixels chosen from a subset that are hand labeled), and for each pair of pixels identifying the portion of the image (i.e., the edge) that most contributes to the training data segmentation (merging or segmentation error), the links that contribute to erroneous merging or splitting of components are more highly weighted in the retraining of the classifier weights, thereby focusing the training on the end-to-end accuracy of the overall segmentation that is determined by the weighted affinity data. 
         [0059]    A description of an implementation of the first embodiment is provide below. For reference, notation used in this description is provided for reference. 
       2.1 Notation 
       [0000]    
       
         I The underlying image, or more generally a dataset 
         I n  Individual pixel, or other data element, at coordinate nε           
                   =          Graph, where the image/data is defined at nodes of the graph            
                    The nodes of the graph. In the case of a three (two) dimensional image, the nodes form a regular rectangular lattice. 
                    Edges of the graph. In the case of the three (two) dimensional image, the links join adjacent node in the lattice. 
                    The set of paths from node i to node j in the graph          . 
         * In general, the superscript * represents the “truth,” for example as set by human annotation of images, and no superscript indicates computer generated. 
         s n * The true classification of the image/data at coordinate n. 
         S* The true classification of the entire image. 
         s n  The computer classification of the image at coordinate n. 
         S The computer classification of the entire image. 
         δ(s i ,s j ) Similarity between class s i  and class s j : 0 if s i ≠s j ; 1 if s i =s j . 
         e l  The computer generated classification of edge lin the graph. 
         mm i,j  Maximin distance between nodes i and j, computed as 
       
     
         [0000]      mm i,j =max pε           min lεp e l      Θ(mm i,j ) Thresholding of mm i,j : 0 (disconnected) if less than the threshold and 1 (connected) if greater;   m l  Dissimilarity for edge l in the graph.   m i,j  Minimax ultrametic between nodes i and j          computed as     
         [0000]      m i,j =min pε           max lεp m l      l i,j   (max)  The minimax edge on paths from i to j.     
         [0000]      l i,j   (max) =argmax lεp     i,j       (min)   m l ; p i,j   (min) =argmin pε           max lεp m l ; m ij =m l     i,j       (max)   ;   m l *, m i,j * Define m i,j *=00 if nodes i and j are in a connected component, and 1 otherwise, and define m l *=m i,j * for l=(i,j).   Φ(m i,j ) Thresholding of m i,j : 0 (connected) if less than the threshold and 1 (disconnected) if greater.   M(l; I, W) The computer generated ultrametric for link l given an image (or data set) I and estimated parameters W.   T          Clustered subgraph of          , such as a spanning tree, such that           for example, formed by agglomerative clustering of the nodes according to an ultrametric between nodes.     
       2.2 Initial Estimation of W 
       [0082]    Initial training uses a set of images I and corresponding true pixel classification S*. An error function 
         [0000]    
       
         
           
             E 
             = 
             
               
                 1 
                 2 
               
                
               
                 
                   ∑ 
                   
                     l 
                     ∈ 
                   
                 
                  
                 
                   
                     ( 
                     
                       
                         m 
                         l 
                         * 
                       
                       - 
                       
                         M 
                          
                         
                           ( 
                           
                             
                               l 
                               ; 
                               I 
                             
                             , 
                             W 
                           
                           ) 
                         
                       
                     
                     ) 
                   
                   2 
                 
               
             
           
         
       
     
         [0000]    is minimized by varying W, for example, using gradient-based incremental training 
       2.3 Training on Split and Merge Points 
       [0083]    Consider a choice of pairs of pixels (node of graph) i and j. The minimax edge joining the nodes based on the computer calculation is l i,j   (max) , defined in the Notations section above, and therefore m i,j =m l     i,j       (max)   . The training data specifies that the true metric should be m i,j * (e.g., 0 if the two nodes are in a connected class, and 1 otherwise). 
         [0084]    The contribution of the minimax link corresponding to a pair of nodes i and j to the error function is 
         [0000]    
       
         
           
             
               1 
               2 
             
              
             
               
                 
                   ( 
                   
                     
                       m 
                       
                         i 
                         , 
                         j 
                       
                       * 
                     
                     - 
                     
                       M 
                        
                       
                         ( 
                         
                           
                             
                               l 
                               
                                 i 
                                 , 
                                 j 
                               
                               
                                 ( 
                                 max 
                                 ) 
                               
                             
                             ; 
                             I 
                           
                           , 
                           W 
                         
                         ) 
                       
                     
                   
                   ) 
                 
                 2 
               
               . 
             
           
         
       
     
         [0000]    The derivative with respect to the weights W is 
         [0000]    
       
         
           
             
               - 
               
                 ( 
                 
                   
                     m 
                     
                       i 
                       , 
                       j 
                     
                     * 
                   
                   - 
                   
                     M 
                      
                     
                       ( 
                       
                         
                           
                             l 
                             
                               i 
                               , 
                               j 
                             
                             
                               ( 
                               max 
                               ) 
                             
                           
                           ; 
                           I 
                         
                         , 
                         W 
                       
                       ) 
                     
                   
                 
                 ) 
               
             
              
             
               ∂ 
               
                 ∂ 
                 W 
               
             
              
             
               M 
                
               
                 ( 
                 
                   
                     
                       l 
                       
                         i 
                         , 
                         j 
                       
                       
                         ( 
                         max 
                         ) 
                       
                     
                     ; 
                     I 
                   
                   , 
                   W 
                 
                 ) 
               
             
           
         
       
     
         [0085]    The procedure for training on the splits and merges is to iterate over random pairs of nodes (i, j) and for each pair to update the weights W according to the derivative above. 
         [0086]    In some implementations, the random pairs of points are restricted to be within a predetermined distance of one another. 
         [0087]    2.4 Spanning tree implementation 
         [0088]    In some implementations, given the link dissimilarities m l  determined according to the parameters W, a minimal spanning tree is formed for the nodes of the graph. The) spanning tree forms a subgraph          =          such that           and that for any pair of nodes i and j, the minimax link l i,j   (max)  is on the path from i to j in the spanning tree. 
         [0089]    In an iteration with a random node pair (i j), the minimax link is located in the spanning tree, and the parameters of W are updated as above. 
         [0090]    After updating the parameters, a portion of the spanning tree is recomputed according to the updated parameters and the iteration continues. 
       3 Second Embodiment 
       [0091]    Referring to  FIG. 6 , in second embodiment the segmentation apparatus  120 B makes use of a pixel classifier  312 , which accepts the input image data  115  and produces a weighted map  314 , which provides a value in the range [0,1] for each pixel location. Larger values indicate greater certainty of the pixel being in an object and a lower value indicating a greater certainty of the pixel being in the background. The weighted map  314  is processed in a component identifier  322 , which outputs the segmentation data  125  as output of the segmentation apparatus  120 B. 
         [0092]    The goal of the training procedure for the segmentation parameters  145  that are used by the pixel classifier  312  is to find a function that maps an image patch to an estimate of the probability that the central pixel is labeled “1.” We will call such a function an image patch classifier. If the classifier is applied to patches centered at all locations in an image, it produces an output image that is called in-out map. In some alternative examples, rather than an in-out map, the pixel classifier is formulated to produce a boundary map identifying pixels that are likely to be edge pixels. The analog values in this probability map can be thresholded to produce a binary image labeling. In this example, both the classifier output and ground truth are represented as in-out maps. 
         [0093]    Consider a binary machine labeling T and a human labeling L* of the same image. When optimizing pixel error, we would ideally like to minimize the number of binary disagreements between T and L*: Σ i δ(t i ,l i *) where the machine and human labeling at location i are denoted by t i  and l i *, respectively. 
         [0094]    One way of applying supervised learning to boundary detection is to find an image patch classifier, a function that maps an image patch to an estimate of the probability that the central pixel is a boundary. The output of the pixel classifier  312  is referred to as the boundary map  314  and written as F I ({right arrow over (w)}), where I is the image, and {right arrow over (w)} specifies the adjustable parameters in segmentation parameters  145 . The analog values in the boundary map can be thresholded at scalar value 8 to produce a binary boundary labeling H(F I ({right arrow over (w)})−θ), where image-valued quantity H(M) represents the Heaviside step function applied to each pixel location in a map M. 
       3.1 Learning Pixel Error 
       [0095]    Supervised learning can be formulated as the minimization of the pixel error ∥H(F I ({right arrow over (w)})−θ)−L*∥ 2  with respect to the classifier parameters {right arrow over (w)}, where r is a human boundary labeling of the same image. However, it is often easier to optimize a smooth cost function that depends on the real-valued output of the classifier. One choice is the squared error: d(F I ({right arrow over (w)}), L)=Σ i ∥f i ({right arrow over (w)})−l i , where the boundary map and human boundary labeling at location i is written as f i ({right arrow over (w)}) and, respectively. The dependence of f i ({right arrow over (w)}) on the image I is left implicit for notational convenience. Optimizing the squared error thus serves as an approximation to optimizing the binary classification error. Since the squared error cost function depends smoothly on the analog output of the classifier, gradient descent can be applied to find a local minimum. A “batch” implementation computes the gradient of the cost function for the whole image or set of images. An “online” implementation computes the gradient of the cost function for a single pixel. Since the pixel is chosen at random, the average of the online gradient is equal to the batch gradient, which means that online learning is a form of stochastic gradient descent. Online learning is described in the following algorithm: 
         [0000]                                                            gradient ( I,L,{right arrow over (w)},k )           for iter = 1 to k                i = random location in random image           {right arrow over (w)}:= {right arrow over (w)}−η∇ {right arrow over (w)}d(fi ({right arrow over (w)}),l i )                end           return {right arrow over (w)}                    
where η is a rate parameter, which is a positive and generally small number.
 
       3.2 Warping Error 
       [0096]    A preferred approach to supervised learning of the parameters does not necessarily attempt to exactly match the training segmentation data  137 . Rather, for any choice of segmentation parameters, a best warping to the training segmentation is found to match the boundary map output from the pixel classifier. Specifically, we define the warping error as 
         [0000]    
       
         
           
             
               D 
                
               
                 ( 
                 
                   T 
                   || 
                   
                     L 
                     * 
                   
                 
                 ) 
               
             
             = 
             
               
                 min 
                 
                   L 
                   ⊲ 
                   
                     L 
                     * 
                   
                 
               
                
               
                 
                    
                   
                     T 
                     - 
                     L 
                   
                    
                 
                 2 
               
             
           
         
       
     
         [0097]    One approach to finding the best warping in the above minimization is to use a descent algorithm for finding local minima During warping, we are allowed to flip simple points of L that lie inside the mask M, i.e., points in the set simple (L)∩M. Flipping any such pixel j of L satisfying |t j −l j |0.5 produces a new warping with smaller error. A descent algorithm greedily picks the pixel for which this error reduction is the largest, breaking ties randomly as follows: 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                   
                 warp( L*,T,M ) 
               
               
                   
                 L := L* 
               
               
                   
                 do 
               
             
          
           
               
                   
                 S := simple(L)∩M 
               
               
                   
                 i := argmax jεS  |t j −l j | , breaking ties randomly 
               
             
          
           
               
                   
                 if |t i −l i | &gt; 0.5 
               
             
          
           
               
                   
                 l i  := 1−l i   
               
             
          
           
               
                   
                 else 
               
             
          
           
               
                   
                 return L 
               
             
          
           
               
                   
                 end 
               
               
                   
               
             
          
         
       
     
         [0098]    Since ∥T−L∥ 2  is decreasing, the algorithm is guaranteed to converge to a local minimum of the warping error. How problematic is the lack of an efficient algorithm for finding a global minimum? This does not appear to be a problem in practice. 
       3.3 Learning Warping Error 
       [0099]    In this preferred approach, warping error is used to optimize the classifier weights rather than pixel error, formulating the weight selection as an optimization of D(F 1 ({right arrow over (w)})∥L*) with respect to {right arrow over (w)}, 
         [0000]      min {right arrow over (w)} D(H(F I ({right arrow over (w)})−θ∥L*, 
         [0000]    which can be represented using the definition of D(T∥L*) above as the nested optimization: 
         [0000]    
       
         
           
             
               min 
               
                 w 
                 → 
               
             
              
             
               
                 min 
                 
                   L 
                   ⊲ 
                   
                     L 
                     * 
                   
                 
               
                
               
                 
                   
                      
                     
                       
                         H 
                          
                         
                           ( 
                           
                             
                               
                                 F 
                                 I 
                               
                                
                               
                                 ( 
                                 
                                   x 
                                   → 
                                 
                                 ) 
                               
                             
                             - 
                             θ 
                           
                           ) 
                         
                       
                       - 
                       L 
                     
                      
                   
                   2 
                 
                 . 
               
             
           
         
       
     
         [0100]    We call this method Boundary Learning by Optimization with Topological Constraints, or BLOTC. Note that standard training is the case where no warping of L* is allowed, i.e., the geometric constraint becomes completely tight. In order to make this cost function easier to optimize, we again use a smooth approximation of the binary error. 
         [0101]    The preferred approach makes use of an algorithm that alternates between gradient descent for {right arrow over (w)} and descent for the warped image L as follows: 
         [0000]    
       
         
               
               
             
               
               
             
               
               
             
           
               
                   
               
             
             
               
                   
                 blotc ( I,L*,M,k 1 ,k 2  ) 
               
               
                   
                 L := L* 
               
               
                   
                 {right arrow over (w)} := random initialization 
               
               
                   
                 {right arrow over (w)} := gradient (L, {right arrow over (w)}, k 1 ) 
               
               
                   
                 repeat 
               
             
          
           
               
                   
                 L := warp ( L,F I ({right arrow over (w)}),M ) 
               
               
                   
                 {right arrow over (w)} := gradient ( I,L,{right arrow over (w)},k 2  ) 
               
             
          
           
               
                   
                 until convergence 
               
               
                   
                 return {right arrow over (w)} 
               
               
                   
               
             
          
         
       
     
       Classifiers 
       [0102]    The approaches can be applied with a variety of parametric pixel or edge classifiers. One choice is a convolutional network. One examples of such a network that has been evaluated containing 6 hidden layers, 24 feature maps in each hidden layer, and full connectivity between feature maps in adjacent layers. Each individual filter has 5×5 pixels, but the multiple-layers yield an effective field of view of the classifier of 28×28 pixels. In an example with the BLOTC approach examples, such a network was trained for 1,000,000 updates using the traditional optimization with the labels fixed. The BLOTC network was initialized with the weights from a standard network after 500,000 gradient updates and then further trained for 500,000 additional updates using BLOTC optimization. Each network was trained in roughly 18 hours, using a layer-wise procedure that iteratively adds hidden layers to the network architecture. The training used a fast shared-memory GPU implementation that provides between a 50-100×increase in training speed as compared to CPU implementations. 
       5 Other Embodiments 
       [0103]    In other embodiments, one or both of two general approaches, of which the description above provides specific examples, generally focus the training of the classifier on significant edges or pixels. Other approaches also permit certain discrepancies between the manual segmentation and the computer segmentation if the discrepancies are not significant in that they do not affect the segmentation. 
         [0104]    For example, the specific example in which a nested optimization considers both warping of the training segmentation as well as parameter optimization of the classifier is an example of modification of the training data to better match the automated prediction to the extent that the modification is not significant. In the example above, maintaining the digital topology in permissible warpings is the example of an insignifican modification. In other examples, modifications of the training data can include other types of changes. For example, rather than warping by flipping pixels, other forms of warping may be used (e.g., continuous warping or deformations of the image space). 
         [0105]    A specific example presented above focuses parameter updating on maximin edges in an affinity graph addresses edges that may affect the segmentation more than others. Other focusing on significant edge or pixel classification parameters may be used in other embodiments. For example, in a pixel classification rather than an edge classification approach, the importance of correct classification of certain pixels may vary by pixel, and therefore a weighting to the important pixels may be used. Furthermore, the approach to updating parameters of maximin edges may alternatively focus on all edges weighting their contribution according to the degree to which they are close to a maximin value. 
         [0106]    Examples presented above use training image data  135  that is separate from the image data  115  of an unknown sample. In some examples, an operator can provide some partial labeling of the data for the unknown image, for example, by indicating a small number of pairs of pixels that are in same versus different object. Such labeling can occur prior to applying the segmentation procedure to the unknown data, or as a correction phase after an initial segmentation. When such partial labeling of the unknown data is available, the parameter selection system  140  can adapts the segmentation parameters  145  to better match the unknown sample. 
       6 Applications 
       [0107]    As introduced above, examples of the approaches described above address segmentation of two- (e.g., image slices) and three-dimensional (e.g., volume) images of biological or other physical objects. In some examples, the segmentation  130  determined by the system is used to form data representing an output image, for example, for presentation to a user on an image output device (e.g., a graphical computer display). Examples of such output images include enhancements showing the segmentation of the image in conjunction with the original image. In some examples, segmented components are further classified (e.g., according to image properties within the segments) and the segments are enhanced with color, intensity, or other visual attributes. In some examples, automatic segmentation of an image is used for further computation, and the result of the computation is stored, further processed, or presented to a user. For example, the segmentation may be used for counting components (e.g., cells, neurons), or determining physical characteristics (e.g., average size, area, cross-section). 
         [0108]    In another example, techniques described above are applied to a task of tumor detection and/or localization. As a specific example, tumors are detected and/or localized in two-dimension mammography images (e.g., X-ray images of projections through breast tissue) or in three dimensional images of breast tissue (e.g., using Computed Tomography (CT), Magnetic Resonance (MR), or ultrasound techniques). In some examples, the techniques are based on training a classifier to classify each image location (e.g., pixel) as tumor versus non-tumor, or for classifying adjacent locations as same versus different object (e.g., both tumor or both normal versus transition/edge between normal and tumor). In training, each abnormality has some geometry which will be subjected to warping, but the number of independent abnormalities in each image (which may be zero) is a topological feature that is preserved. The approach may be applied to a variety of abnormalities or objects in the image, which typically include (micro)califications, masses, and architectural distortions, not all of which are necessarily malignant. 
       7 Non-Image Data Sets 
       [0109]    For a data set I of size N, a fully linked graph with N nodes is formed. An initial estimate of W that parameterizes the link metric is formed as above. Note that in the image segmentation approach above, the graph with nodes corresponding to pixels is not fully connected, but rather has links forming a rectangular lattice. 
         [0110]    As above, a minimum spanning tree of the graph is formed using the computer predicted metrics m l =M(l;l,W). For example, the nodes are agglomeratively clustered to form the spanning tree. 
         [0111]    For a fixed tree, a series of iterations are performed. At each iteration a pair of data points is selected, and W is incremented according to the derivative above. 
         [0112]    After a number of iterations, the agglomerative clustering tree is recomputed, and a further set of iterations is performed. 
         [0113]    To classify a new data point, the trained ultrametric is used to identify the nearest training data point to the new data point to classify the new data point according to one of the classes found in the training data. 
         [0114]    As introduced above, the parameter estimation approach can include adaptation of the parameters based on partial labeling or correction of the unknown data set. 
         [0115]    Applications to such non-image data can include forming groups or clusters of items according to trainable similarity metrics between pairs of items (e.g., for computer implemented advertising or product recommendation systems), and forming groups or clusters of individuals based on trainable similarity metrics between pairs of individuals. 
       8 Implementations 
       [0116]    The approach can be implemented in the form of a computer program (e.g., software instructions stored on a computer readable medium for controlling a data processing system) which would be tailored to accept three-dimensional data, for example, from current available cross-sectional imaging datasets that are output by imaging units. In some implementations, the approach is incorporated into a system that acquires a three-dimensional image of a patient and provides a representation of the image to an operator of the system, typically a clinician. In some implementations, the approach is hosted separately from the system that acquires the image, for example in a separate image processing module or server that provides image analysis services. In some implementations, the approach is combined with a system that performs volume segmentation, which may combined with or separate from the image acquisition and/or image display systems. 
         [0117]    It is to be understood that the foregoing description is intended to illustrate and not to limit the scope of the invention, which is defined by the scope of the appended claims. Other embodiments are within the scope of the following claims.