{"version":1,"kind":"Article","sha256":"","slug":"306","location":"","dependencies":[],"doi":"10.54294/ypz65j","thumbnail":"https://pub.desci.com/ipfs/bafkreieygydo7lmmbzo5kv653hi54thlcyt5lro4l3t5wdqsnyxy3wciva","frontmatter":{"title":"Graph Cuts, <i>Caveat Utilitor</i>, and Euler's Bridges of Konigsberg","abstract":"Graph-based algorithms have enjoyed renewed interest for solving computer vision problems. These algorithms have been the subject of intense interest and research. In order to maintain the ITK library au courant, we developed a framework for graph-based methods of energy minimization in ITK which employ energy functions derived within a Markov Random Field (MRF) context. This required not only the implementation of the energy minimization methodology but also the more general requirement of introducing graph-related data structures into ITK which can be used for other graph-based algorithms pertinent to future extensions of the ITK library. \r\n\r\nPlease note that some of the algorithms described in this paper may be covered by patents and, as such, it is incumbent upon the user to seek licenses before building the binaries which utilize this code. Also note that “research use” is not exempt from acquiring such licenses. The only exemption from patent restrictions is “. . . amusement, to satisfy idle curiosity, or for strictly philosophical inquiry.”","license":"You are licensing your work to Kitware Inc. under the\nCreative Commons Attribution License Version 3.0.\n\nKitware Inc. agrees to the following:\n\nKitware is free\n * to copy, distribute, display, and perform the work\n * to make derivative works\n * to make commercial use of the work\n\nUnder the following conditions:\n\\\"by Attribution\\\" - Kitware must attribute the work in the manner specified by the author or licensor.\n\n * For any reuse or distribution, they must make clear to others the license terms of this work.\n * Any of these conditions can be waived if they get permission from the copyright holder.\n\nYour fair use and other rights are in no way affected by the above.\n\nThis is a human-readable summary of the Legal Code (the full license) available at\nhttp://creativecommons.org/licenses/by/3.0/legalcode","keywords":["Graphs","Graph Data Structure","Graph Cuts","Max Flow","Min-Cut"],"authors":[{"name":"Tustison, Nicholas","email":"ntustison@gmail.com","affiliations":[],"corresponding":true},{"name":"Yushkevich, Paul","email":"pauly@despammed.com","affiliations":[]},{"name":"Song, Zhuang","affiliations":[]},{"name":"Gee, James","email":"gee@mail.med.upenn.edu","affiliations":[]}],"date_submitted":"2008-11-15 08:00:47","external_publication_id":306,"revision_cids":["bafkreiemv7soopghpdqujnfjynsckcdsyphemmkxgzl2rxscv34jra2wya"],"github":"https://github.com/midas-journal/midas-journal-306.git","thumbnail":"https://pub.desci.com/ipfs/bafkreieygydo7lmmbzo5kv653hi54thlcyt5lro4l3t5wdqsnyxy3wciva"},"mdast":{"type":"root"},"downloads":[{"url":"https://ipfs.desci.com/ipfs/bafkreibix7mkxytzu2gslh7b37ivlhiags5njfzlin7ourepwsz6eey36m","title":"root/insight-journal-metadata.json","filename":"insight-journal-metadata.json","extra":{"size_bytes":5880,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreibyjpovzy2ozbkqueq4hrwxmp6r3ai57gyfwxedh2umbkpmdwtqje","title":"root/code/Source/.DS_Store","filename":".DS_Store","extra":{"size_bytes":6148,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiahsdph65mgihvdkfcg7saisweztajqrva62ztynfayqv7h5riycy","title":"root/code/Source/CMakeLists.txt","filename":"CMakeLists.txt","extra":{"size_bytes":3554,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreicyta3inw6ilixlzxperu5lo2c6act3nlgcar7o55244cq5n4e6li","title":"root/code/Source/CMakeTemplate.txt","filename":"CMakeTemplate.txt","extra":{"size_bytes":1918,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreidsuvum4ihhamba3w5xnnhyu3rhrxzjtzkfggnmwokhpg7ktzqjxa","title":"root/code/Source/IJMacros.txt","filename":"IJMacros.txt","extra":{"size_bytes":3465,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreibkmvwafbdnl5eu3wo3mbsngdakpjngxd44bxtbpeovnvaktafvcu","title":"root/code/Source/ImageCompare.cxx","filename":"ImageCompare.cxx","extra":{"size_bytes":8164,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiejqvdqxtc3rl4zojqb37cgn3nk6i2limk2jsi26d2ijli655hlii","title":"root/code/Source/ct_scan.jpg","filename":"ct_scan.jpg","extra":{"size_bytes":34557,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreifzbrilaxjulopbnfflhf5w46hor54fdaby343swxvolqrhdrfrje","title":"root/code/Source/ct_scan_out.nii.gz","filename":"ct_scan_out.nii.gz","extra":{"size_bytes":16137,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreicmuhtm3yltvsuvsa2wnmhglztlx6lx5jkvqrmbtauec4q334dbze","title":"root/code/Source/itkBoykovAlphaExpansionMRFImageFilter.h","filename":"itkBoykovAlphaExpansionMRFImageFilter.h","extra":{"size_bytes":8220,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreigic745njyj5hdkmwmnqvsxdo57ecy2ypthk7nkmogwatcz5mgaem","title":"root/code/Source/itkBoykovAlphaExpansionMRFImageFilter.txx","filename":"itkBoykovAlphaExpansionMRFImageFilter.txx","extra":{"size_bytes":23478,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreihqfkadxfope2ob3z27p26cpb3i5hx2j3dfm2bqyla7pga2gxaddq","title":"root/code/Source/itkBoykovGraphCutFilterTest.cxx","filename":"itkBoykovGraphCutFilterTest.cxx","extra":{"size_bytes":10202,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreihpkf7zffqg3ovvtkgam2b5il5feddhb3d35awnatroc7uvfo7ppm","title":"root/code/Source/itkBoykovGraphTraits.h","filename":"itkBoykovGraphTraits.h","extra":{"size_bytes":2302,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreih7v7u3nfygwxojjr5hndjslpkztgs36vui6c2it4ru3j42hmxxgm","title":"root/code/Source/itkBoykovImageToGraphFunctor.h","filename":"itkBoykovImageToGraphFunctor.h","extra":{"size_bytes":6015,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreigfem2dkg6cgjc4l2idhk6ggnht2wadwstfuiqkvmoomi5bybkmwi","title":"root/code/Source/itkBoykovImageToGraphFunctor.txx","filename":"itkBoykovImageToGraphFunctor.txx","extra":{"size_bytes":6288,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreig4x43kcb4m247ydlrroomb2limgn6eymiz23yishsrrg53goq3bu","title":"root/code/Source/itkBoykovMinCutGraphFilter.h","filename":"itkBoykovMinCutGraphFilter.h","extra":{"size_bytes":5473,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreibejc4zh2yc7t2dkvydubowfofepknx2p5s7hvqowzm2blwml3ena","title":"root/code/Source/itkBoykovMinCutGraphFilter.txx","filename":"itkBoykovMinCutGraphFilter.txx","extra":{"size_bytes":17027,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreicuwgna6cuswmel5pwukkj5g22h5tzdxi6abh4ms2n7spg4trvo5a","title":"root/code/Source/itkDefaultGraphTraits.h","filename":"itkDefaultGraphTraits.h","extra":{"size_bytes":2192,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreihktjnxrbx7hsu5viqx5svsxamsabxmjozwbzzj4m723q2kvzmzey","title":"root/code/Source/itkDefaultImageToGraphFunctor.h","filename":"itkDefaultImageToGraphFunctor.h","extra":{"size_bytes":9563,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreih73emkdznlgkf2wi2yuxtd4pudslvm3wkcehokbjumglc4jze3mu","title":"root/code/Source/itkDefaultImageToGraphFunctor.txx","filename":"itkDefaultImageToGraphFunctor.txx","extra":{"size_bytes":5608,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreihmofhb7b5seoabdnsr7shcjnm6ocrd45i27liu3e5coj7gft55qe","title":"root/code/Source/itkGraph.h","filename":"itkGraph.h","extra":{"size_bytes":12097,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreicxsenyyjoqoovc2qmoscrgdlxldi5tqcthccy5zgxruafx5bv2ni","title":"root/code/Source/itkGraph.txx","filename":"itkGraph.txx","extra":{"size_bytes":7081,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiaovtl2nf3idyxfs33gogfzhdhiw2zmaxrc6l6ww7z2ga2c64whbe","title":"root/code/Source/itkGraphDuplicator.h","filename":"itkGraphDuplicator.h","extra":{"size_bytes":2375,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreihxslzlxaub6whsc63vvw5d6bhimxkkfptxhvq67iotbk5uv2rfoy","title":"root/code/Source/itkGraphDuplicator.txx","filename":"itkGraphDuplicator.txx","extra":{"size_bytes":2044,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreieoc6j22zdlw6shq6e4m2dpe6kwmbngvzy4xb5vu2o3ntws24ajsy","title":"root/code/Source/itkGraphSource.h","filename":"itkGraphSource.h","extra":{"size_bytes":6062,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreidf7aysp5av3bc4k4qm6uewlcjpdabfjzbiu2ublh4i6h7odq5crq","title":"root/code/Source/itkGraphSource.txx","filename":"itkGraphSource.txx","extra":{"size_bytes":2912,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreif6ahdqg5kjqagrpiqdgzxa72p4tfujcoyqah7eupdagp3mznnndm","title":"root/code/Source/itkGraphTest.cxx","filename":"itkGraphTest.cxx","extra":{"size_bytes":9369,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreigk5y364qq2a4dzdxhnm2x3kd6tgr2rhj2dilhxjfpgtnnkwpf4na","title":"root/code/Source/itkGraphToGraphFilter.h","filename":"itkGraphToGraphFilter.h","extra":{"size_bytes":2582,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreieegutjjgjtkcuhxbbxusurntjw5skc3edocwmgekn3pdvnhouvgm","title":"root/code/Source/itkGraphToGraphFilter.txx","filename":"itkGraphToGraphFilter.txx","extra":{"size_bytes":2142,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiahg2dyzh2n3g5g674l5ygjmwg2bp4tsas7ltlvqltforesbtynji","title":"root/code/Source/itkGraphToImageFilter.h","filename":"itkGraphToImageFilter.h","extra":{"size_bytes":4513,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreienm6hxof7kkz6di2r6pljkajfbba275jde6egpvgcexonahu5kcy","title":"root/code/Source/itkGraphToImageFilter.txx","filename":"itkGraphToImageFilter.txx","extra":{"size_bytes":7511,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiauflwwkwyxzlaslrbsyyh3wblv4a4lbfe7ctjadpwgfe7d6lhfre","title":"root/code/Source/itkImageGraphTraits.h","filename":"itkImageGraphTraits.h","extra":{"size_bytes":2526,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreia4oiubjr7ve3mpocxkxhbjeixkrixzhqcchylcoqgn44yasjbhwi","title":"root/code/Source/itkImageToGraphFilter.h","filename":"itkImageToGraphFilter.h","extra":{"size_bytes":4199,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreiduoit2jc7hg3kca22awx3hca2424h7jxshyfuvhqtyv6eyi3ennu","title":"root/code/Source/itkImageToGraphFilter.txx","filename":"itkImageToGraphFilter.txx","extra":{"size_bytes":5830,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreici2v3h4xtehwuhcva7m77bj643xszunesrshopzf77cabqlnt7ha","title":"root/code/Source/itkInPlaceGraphFilter.h","filename":"itkInPlaceGraphFilter.h","extra":{"size_bytes":6304,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreifgmvifuil2aomegrzmugriwjhmxvwmt4clgwgyzkzdfjxtgtwjoa","title":"root/code/Source/itkInPlaceGraphFilter.txx","filename":"itkInPlaceGraphFilter.txx","extra":{"size_bytes":3705,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreidj7yu32qvwkhmlnmvhshhzrq7ti667oid6foe6w4e7o3eql5bfqa","title":"root/code/Source/lungs.nii.gz","filename":"lungs.nii.gz","extra":{"size_bytes":740712,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreib7kapvw3gbxyvhhpqcsu5h4nkgekxh7tcxdwimeytx47wovyvhzm","title":"root/code/Source/lungs_out.nii.gz","filename":"lungs_out.nii.gz","extra":{"size_bytes":17827,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreicso3ybjk3hsonvmtap5hub3gcwafoykao734p6zxukuud5ibaute","title":"root/code/Source/peppers.jpg","filename":"peppers.jpg","extra":{"size_bytes":37119,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreif6slsvyrsvkw35fkhm4kxsixratj2hbz3m3w7pjshhjczjvbzx6a","title":"root/code/Source/peppers_out.nii.gz","filename":"peppers_out.nii.gz","extra":{"size_bytes":20247,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreifr4tjvdbxikibzwhskzyvhcfl2qcsv2k6d74ctlsmphjot2vibfy","title":"root/code/Source/r85slice.png","filename":"r85slice.png","extra":{"size_bytes":14366,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreibeyy3sk4hhqjjovzspu75tnqii6hf75iuwye3jvv5axvmz67uy5a","title":"root/code/Source/r85slice_out.nii.gz","filename":"r85slice_out.nii.gz","extra":{"size_bytes":3206,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreifjt2t3yuy7q74qz7xxuzmv6bet66ktuggtga5kzclue4fawto7gu","title":"root/code/Source/tools.jpg","filename":"tools.jpg","extra":{"size_bytes":11465,"type":"file"}},{"url":"https://pub.desci.com/ipfs/bafkreibvynpivkk3l2fd7pliv4jjeg6yrdi4etpwoe4twfsquw5gyvq2he","title":"root/code/Source/tools_out.nii.gz","filename":"tools_out.nii.gz","extra":{"size_bytes":8813,"type":"file"}},{"url":"https://ipfs.desci.com/ipfs/bafkreic5vmkn2rrycw3vt6csdaxhlwklchvnohpytwtwgjblskbhbb73hm","title":"root/comments.md","filename":"comments.md","extra":{"size_bytes":1090,"type":"file"}},{"url":"https://dweb.link/ipfs/bafybeidiq5ac5ewabcdyrdgcube6nx4bhoufa3nyxuvl5qjgx4r4jrraam","title":"root/article.pdf","filename":"article.pdf","extra":{"size_bytes":1240900,"type":"file"}}],"references":{"cite":{"order":["ref1","ref2"]},"data":{"ref1":{"label":"ref1","enumerator":"1","url":"https://doi.org/10.4153/cjm-1956-045-5","html":"Maximal flow through a network+Canadian Journal of Mathematics+8+399+404+1956+L. R. Ford+D. R. Fulkerson"},"ref2":{"label":"ref2","enumerator":"2","url":"https://doi.org/10.1111/j.2517-6161.1989.tb01764.x","html":"Exact maximum a posteriori estimation for binary images+J. R. Statist. Soc. B+1+2+1+279+1989+D. M. Greig+B. T. Porteous+A. H. Seheult"}}}}