Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2013-03-03

AUTHORS

Noha Youssry El-Zehiry, Leo Grady

ABSTRACT

The Mumford–Shah model has been one of the most influential models in image segmentation and denoising. The optimization of the multiphase Mumford–Shah energy functional has been performed using level sets methods that optimize the Mumford–Shah energy by evolving the level sets via the gradient descent. These methods are very slow and prone to getting stuck in local optima due to the use of gradient descent. After the reformulation of the 2-phase Mumford–Shah functional on a graph, several groups investigated the hierarchical extension of the graph representation to multi class. The discrete hierarchical approaches are more effective than hierarchical (or direct) multiphase formulation using level sets. However, they provide approximate solutions and can diverge away from the optimal solution. In this paper, we present a discrete alternating optimization for the discretized Vese–Chan approximation of the piecewise constant multiphase Mumford–Shah functional that directly minimizes the multiphase functional without recursive bisection on the labels. Our approach handles the nonsubmodularity of the multiphase energy function and provides a global optimum if the image estimation data term is known apriori. More... »

PAGES

270-285

References to SciGraph publications

  • 2002-12. A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model in INTERNATIONAL JOURNAL OF COMPUTER VISION
  • 2005. Energy Minimization Based Segmentation and Denoising Using a Multilayer Level Set Approach in ENERGY MINIMIZATION METHODS IN COMPUTER VISION AND PATTERN RECOGNITION
  • 2010-12-11. Global Minimization for Continuous Multiphase Partitioning Problems Using a Dual Approach in INTERNATIONAL JOURNAL OF COMPUTER VISION
  • 2009. Graph Cut Optimization for the Piecewise Constant Level Set Method Applied to Multiphase Image Segmentation in SCALE SPACE AND VARIATIONAL METHODS IN COMPUTER VISION
  • 2009. Efficient Global Minimization for the Multiphase Chan-Vese Model of Image Segmentation in ENERGY MINIMIZATION METHODS IN COMPUTER VISION AND PATTERN RECOGNITION
  • 2010. Discrete Calculus, Applied Analysis on Graphs for Computational Science in NONE
  • 1984-02. Roof duality, complementation and persistency in quadratic 0–1 optimization in MATHEMATICAL PROGRAMMING
  • 2007-06. Fast Global Minimization of the Active Contour/Snake Model in JOURNAL OF MATHEMATICAL IMAGING AND VISION
  • 2005. A Fast and Exact Algorithm for Total Variation Minimization in PATTERN RECOGNITION AND IMAGE ANALYSIS
  • 2012. A Continuous Max-Flow Approach to Minimal Partitions with Label Cost Prior in SCALE SPACE AND VARIATIONAL METHODS IN COMPUTER VISION
  • 2008. A Convex Formulation of Continuous Multi-label Problems in COMPUTER VISION – ECCV 2008
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s11263-013-0617-0

    DOI

    http://dx.doi.org/10.1007/s11263-013-0617-0

    DIMENSIONS

    https://app.dimensions.ai/details/publication/pub.1045055569


    Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
    Incoming Citations Browse incoming citations for this publication using opencitations.net

    JSON-LD is the canonical representation for SciGraph data.

    TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Imaging and Computer Vision, Siemens Corporation, Corporate Technology, Princeton, NJ, USA", 
              "id": "http://www.grid.ac/institutes/grid.419233.e", 
              "name": [
                "Imaging and Computer Vision, Siemens Corporation, Corporate Technology, Princeton, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "El-Zehiry", 
            "givenName": "Noha Youssry", 
            "id": "sg:person.07657676251.51", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07657676251.51"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "HeartFlow Inc., Redwood city, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.509381.6", 
              "name": [
                "HeartFlow Inc., Redwood city, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Grady", 
            "givenName": "Leo", 
            "id": "sg:person.0617232252.77", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0617232252.77"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11585978_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029397323", 
              "https://doi.org/10.1007/11585978_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s10851-007-0002-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1007015061", 
              "https://doi.org/10.1007/s10851-007-0002-0"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03641-5_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012650891", 
              "https://doi.org/10.1007/978-3-642-03641-5_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02612354", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1045174000", 
              "https://doi.org/10.1007/bf02612354"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-1-84996-290-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026629478", 
              "https://doi.org/10.1007/978-1-84996-290-2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-24785-9_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1018639988", 
              "https://doi.org/10.1007/978-3-642-24785-9_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11492429_43", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039483424", 
              "https://doi.org/10.1007/11492429_43"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1023/a:1020874308076", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035462968", 
              "https://doi.org/10.1023/a:1020874308076"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-88690-7_59", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033809104", 
              "https://doi.org/10.1007/978-3-540-88690-7_59"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-02256-2_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027022699", 
              "https://doi.org/10.1007/978-3-642-02256-2_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s11263-010-0406-y", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026209771", 
              "https://doi.org/10.1007/s11263-010-0406-y"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2013-03-03", 
        "datePublishedReg": "2013-03-03", 
        "description": "The Mumford\u2013Shah model has been one of the most influential models in image segmentation and denoising. The optimization of the multiphase Mumford\u2013Shah energy functional has been performed using level sets methods that optimize the Mumford\u2013Shah energy by evolving the level sets via the gradient descent. These methods are very slow and prone to getting stuck in local optima due to the use of gradient descent. After the reformulation of the 2-phase Mumford\u2013Shah functional on a graph, several groups investigated the hierarchical extension of the graph representation to multi class. The discrete hierarchical approaches are more effective than hierarchical (or direct) multiphase formulation using level sets. However, they provide approximate solutions and can diverge away from the optimal solution. In this paper, we present a discrete alternating optimization for the discretized Vese\u2013Chan approximation of the piecewise constant multiphase Mumford\u2013Shah functional that directly minimizes the multiphase functional without recursive bisection on the labels. Our approach handles the nonsubmodularity of the multiphase energy function and provides a global optimum if the image estimation data term is known apriori.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s11263-013-0617-0", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1032807", 
            "issn": [
              "0920-5691", 
              "1573-1405"
            ], 
            "name": "International Journal of Computer Vision", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "3", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "104"
          }
        ], 
        "keywords": [
          "Mumford-Shah", 
          "Mumford-Shah energy", 
          "level sets", 
          "gradient descent", 
          "Mumford-Shah model", 
          "combinatorial optimization", 
          "approximate solution", 
          "optimal solution", 
          "level set method", 
          "global optimum", 
          "hierarchical extension", 
          "set method", 
          "optimization", 
          "hierarchical approach", 
          "recursive bisection", 
          "data term", 
          "multiphase formulation", 
          "graph representation", 
          "energy function", 
          "solution", 
          "set", 
          "approximation", 
          "nonsubmodularity", 
          "reformulation", 
          "image segmentation", 
          "model", 
          "approach", 
          "optimum", 
          "graph", 
          "formulation", 
          "class", 
          "representation", 
          "denoising", 
          "descent", 
          "multiphase", 
          "bisection", 
          "energy", 
          "extension", 
          "multi class", 
          "Apriori", 
          "terms", 
          "function", 
          "method", 
          "segmentation", 
          "influential model", 
          "use", 
          "labels", 
          "group", 
          "paper", 
          "multiphase Mumford\u2013Shah energy", 
          "discrete hierarchical approaches", 
          "hierarchical (or direct) multiphase formulation", 
          "Vese\u2013Chan approximation", 
          "piecewise constant multiphase Mumford\u2013Shah", 
          "constant multiphase Mumford\u2013Shah", 
          "multiphase Mumford\u2013Shah", 
          "multiphase energy function", 
          "image estimation data term", 
          "estimation data term"
        ], 
        "name": "Combinatorial Optimization of the Discretized Multiphase Mumford\u2013Shah Functional", 
        "pagination": "270-285", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1045055569"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s11263-013-0617-0"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s11263-013-0617-0", 
          "https://app.dimensions.ai/details/publication/pub.1045055569"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:30", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_609.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s11263-013-0617-0"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    HOW TO GET THIS DATA PROGRAMMATICALLY:

    JSON-LD is a popular format for linked data which is fully compatible with JSON.

    curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s11263-013-0617-0'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s11263-013-0617-0'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s11263-013-0617-0'

    RDF/XML is a standard XML format for linked data.

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s11263-013-0617-0'


     

    This table displays all metadata directly associated to this object as RDF triples.

    171 TRIPLES      22 PREDICATES      95 URIs      76 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s11263-013-0617-0 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 schema:author N7eeaa6ac62a645d3983fa553c6787729
    4 schema:citation sg:pub.10.1007/11492429_43
    5 sg:pub.10.1007/11585978_29
    6 sg:pub.10.1007/978-1-84996-290-2
    7 sg:pub.10.1007/978-3-540-88690-7_59
    8 sg:pub.10.1007/978-3-642-02256-2_1
    9 sg:pub.10.1007/978-3-642-03641-5_3
    10 sg:pub.10.1007/978-3-642-24785-9_24
    11 sg:pub.10.1007/bf02612354
    12 sg:pub.10.1007/s10851-007-0002-0
    13 sg:pub.10.1007/s11263-010-0406-y
    14 sg:pub.10.1023/a:1020874308076
    15 schema:datePublished 2013-03-03
    16 schema:datePublishedReg 2013-03-03
    17 schema:description The Mumford–Shah model has been one of the most influential models in image segmentation and denoising. The optimization of the multiphase Mumford–Shah energy functional has been performed using level sets methods that optimize the Mumford–Shah energy by evolving the level sets via the gradient descent. These methods are very slow and prone to getting stuck in local optima due to the use of gradient descent. After the reformulation of the 2-phase Mumford–Shah functional on a graph, several groups investigated the hierarchical extension of the graph representation to multi class. The discrete hierarchical approaches are more effective than hierarchical (or direct) multiphase formulation using level sets. However, they provide approximate solutions and can diverge away from the optimal solution. In this paper, we present a discrete alternating optimization for the discretized Vese–Chan approximation of the piecewise constant multiphase Mumford–Shah functional that directly minimizes the multiphase functional without recursive bisection on the labels. Our approach handles the nonsubmodularity of the multiphase energy function and provides a global optimum if the image estimation data term is known apriori.
    18 schema:genre article
    19 schema:inLanguage en
    20 schema:isAccessibleForFree false
    21 schema:isPartOf N7ef24e80286a4d04911e9e77befc2253
    22 Nd9fdb8b7490a4a509512ec3e03c420a1
    23 sg:journal.1032807
    24 schema:keywords Apriori
    25 Mumford-Shah
    26 Mumford-Shah energy
    27 Mumford-Shah model
    28 Vese–Chan approximation
    29 approach
    30 approximate solution
    31 approximation
    32 bisection
    33 class
    34 combinatorial optimization
    35 constant multiphase Mumford–Shah
    36 data term
    37 denoising
    38 descent
    39 discrete hierarchical approaches
    40 energy
    41 energy function
    42 estimation data term
    43 extension
    44 formulation
    45 function
    46 global optimum
    47 gradient descent
    48 graph
    49 graph representation
    50 group
    51 hierarchical (or direct) multiphase formulation
    52 hierarchical approach
    53 hierarchical extension
    54 image estimation data term
    55 image segmentation
    56 influential model
    57 labels
    58 level set method
    59 level sets
    60 method
    61 model
    62 multi class
    63 multiphase
    64 multiphase Mumford–Shah
    65 multiphase Mumford–Shah energy
    66 multiphase energy function
    67 multiphase formulation
    68 nonsubmodularity
    69 optimal solution
    70 optimization
    71 optimum
    72 paper
    73 piecewise constant multiphase Mumford–Shah
    74 recursive bisection
    75 reformulation
    76 representation
    77 segmentation
    78 set
    79 set method
    80 solution
    81 terms
    82 use
    83 schema:name Combinatorial Optimization of the Discretized Multiphase Mumford–Shah Functional
    84 schema:pagination 270-285
    85 schema:productId N1893d96a1f7f4c6ea5f6249538fabfcc
    86 Ncc25ec089a734cd9854880f1fb488863
    87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045055569
    88 https://doi.org/10.1007/s11263-013-0617-0
    89 schema:sdDatePublished 2022-01-01T18:30
    90 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    91 schema:sdPublisher N1ba50a8dc2c141b3a4b9e33c2682953c
    92 schema:url https://doi.org/10.1007/s11263-013-0617-0
    93 sgo:license sg:explorer/license/
    94 sgo:sdDataset articles
    95 rdf:type schema:ScholarlyArticle
    96 N1893d96a1f7f4c6ea5f6249538fabfcc schema:name doi
    97 schema:value 10.1007/s11263-013-0617-0
    98 rdf:type schema:PropertyValue
    99 N1ba50a8dc2c141b3a4b9e33c2682953c schema:name Springer Nature - SN SciGraph project
    100 rdf:type schema:Organization
    101 N7eeaa6ac62a645d3983fa553c6787729 rdf:first sg:person.07657676251.51
    102 rdf:rest Na5681448a3ef481a954d588608439620
    103 N7ef24e80286a4d04911e9e77befc2253 schema:volumeNumber 104
    104 rdf:type schema:PublicationVolume
    105 Na5681448a3ef481a954d588608439620 rdf:first sg:person.0617232252.77
    106 rdf:rest rdf:nil
    107 Ncc25ec089a734cd9854880f1fb488863 schema:name dimensions_id
    108 schema:value pub.1045055569
    109 rdf:type schema:PropertyValue
    110 Nd9fdb8b7490a4a509512ec3e03c420a1 schema:issueNumber 3
    111 rdf:type schema:PublicationIssue
    112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    113 schema:name Information and Computing Sciences
    114 rdf:type schema:DefinedTerm
    115 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    116 schema:name Artificial Intelligence and Image Processing
    117 rdf:type schema:DefinedTerm
    118 sg:journal.1032807 schema:issn 0920-5691
    119 1573-1405
    120 schema:name International Journal of Computer Vision
    121 schema:publisher Springer Nature
    122 rdf:type schema:Periodical
    123 sg:person.0617232252.77 schema:affiliation grid-institutes:grid.509381.6
    124 schema:familyName Grady
    125 schema:givenName Leo
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0617232252.77
    127 rdf:type schema:Person
    128 sg:person.07657676251.51 schema:affiliation grid-institutes:grid.419233.e
    129 schema:familyName El-Zehiry
    130 schema:givenName Noha Youssry
    131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07657676251.51
    132 rdf:type schema:Person
    133 sg:pub.10.1007/11492429_43 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039483424
    134 https://doi.org/10.1007/11492429_43
    135 rdf:type schema:CreativeWork
    136 sg:pub.10.1007/11585978_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029397323
    137 https://doi.org/10.1007/11585978_29
    138 rdf:type schema:CreativeWork
    139 sg:pub.10.1007/978-1-84996-290-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026629478
    140 https://doi.org/10.1007/978-1-84996-290-2
    141 rdf:type schema:CreativeWork
    142 sg:pub.10.1007/978-3-540-88690-7_59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033809104
    143 https://doi.org/10.1007/978-3-540-88690-7_59
    144 rdf:type schema:CreativeWork
    145 sg:pub.10.1007/978-3-642-02256-2_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027022699
    146 https://doi.org/10.1007/978-3-642-02256-2_1
    147 rdf:type schema:CreativeWork
    148 sg:pub.10.1007/978-3-642-03641-5_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012650891
    149 https://doi.org/10.1007/978-3-642-03641-5_3
    150 rdf:type schema:CreativeWork
    151 sg:pub.10.1007/978-3-642-24785-9_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1018639988
    152 https://doi.org/10.1007/978-3-642-24785-9_24
    153 rdf:type schema:CreativeWork
    154 sg:pub.10.1007/bf02612354 schema:sameAs https://app.dimensions.ai/details/publication/pub.1045174000
    155 https://doi.org/10.1007/bf02612354
    156 rdf:type schema:CreativeWork
    157 sg:pub.10.1007/s10851-007-0002-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007015061
    158 https://doi.org/10.1007/s10851-007-0002-0
    159 rdf:type schema:CreativeWork
    160 sg:pub.10.1007/s11263-010-0406-y schema:sameAs https://app.dimensions.ai/details/publication/pub.1026209771
    161 https://doi.org/10.1007/s11263-010-0406-y
    162 rdf:type schema:CreativeWork
    163 sg:pub.10.1023/a:1020874308076 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035462968
    164 https://doi.org/10.1023/a:1020874308076
    165 rdf:type schema:CreativeWork
    166 grid-institutes:grid.419233.e schema:alternateName Imaging and Computer Vision, Siemens Corporation, Corporate Technology, Princeton, NJ, USA
    167 schema:name Imaging and Computer Vision, Siemens Corporation, Corporate Technology, Princeton, NJ, USA
    168 rdf:type schema:Organization
    169 grid-institutes:grid.509381.6 schema:alternateName HeartFlow Inc., Redwood city, CA, USA
    170 schema:name HeartFlow Inc., Redwood city, CA, USA
    171 rdf:type schema:Organization
     




    Preview window. Press ESC to close (or click here)


    ...