1111:
2447:
of the graph in two sub-graphs and two solutions, each one optimal for one of the sub-graphs, then it is possible to combine the two solutions into one solution optimal for the whole graph in polynomial time. However, computing an optimal solution for the subset of undefined variables is still a
607:
in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is
2484:
reduction" (HOCR), and the result of such reduction can be optimized with QPBO. Generic methods for reduction of arbitrary functions rely on specific substitution rules and in the general case they require the introduction of auxiliary variables. In practice most terms can be reduced without
2472:-expansion, a reasonable approach is to leave the value of undefined variables unchanged, since the persistence property guarantees that the target function will have non-increasing value. Different exact and approximate strategies to minimise the number of undefined variables exist.
611:
QPBO builds an extended graph, introducing a set of auxiliary variables ideally equivalent to the negation of the variables in the problem. If the nodes in the graph associated to a variable (representing the variable itself and its negation) are separated by the
616:
of the graph in two different connected components, then the optimal value for such variable is well defined, otherwise it is not possible to infer it. Such method produces results generally superior to submodular approximations of the target function.
197:
2485:
introducing additional variables, resulting in a simpler optimization problem, and the remaining terms can be reduced exactly, with addition of auxiliary variables, or approximately, without addition of any new variable.
2257:. In the general case, the minimum cut is not unique, and each minimum cut correspond to a different partial solution, however it is possible to build a minimum cut such that the number of undefined variables is minimal.
571:
285:
1099:
2761:
2628:
3552:
3055:
3868:
2950:
1858:
1693:
2243:
2078:
1913:
1748:
1583:
1441:
953:
743:
2188:
2157:
2023:
1992:
1537:
1395:
317:
2667:
2618:
2837:
2810:
772:
1042:
872:
837:
1822:
1657:
1506:
1364:
3400:
3317:
40:
3595:
3233:
3131:
2859:
2783:
922:
900:
708:
3799:
3728:
3471:
3356:
3273:
2126:
1961:
1796:
1631:
3195:
3093:
655:
3761:
3690:
3433:
1480:
1338:
3657:
2470:
2438:
2393:
2348:
2303:
1278:
2976:
2480:
It is always possible to reduce a higher-order function to a quadratic function which is equivalent with respect to the optimisation, problem known as "higher-order
430:
3921:
3624:
1166:
1139:
1007:
980:
3154:
2883:
2413:
2368:
2323:
2278:
1298:
1253:
1233:
1213:
1193:
792:
682:
365:
337:
2609:
2600:
745:
of the variables have a non-undefined value. A partial solution is always part of a global solution, i.e. there exists a global minimum point
3156:, it is always possible to find a reparametrisation to normal form with the following algorithm in two steps (Kolmogorov and Rother (2007)):
438:
3916:
208:
367:
contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in
1172:
The algorithm can be divided in three steps: graph construction, max-flow computation, and assignment of values to the variables.
1047:
2690:
2658:
1280:
for each variable. After re-parametrising the function to normal form, a pair of edges is added to the graph for each term
688:, and all variables have a non-undefined value; if submodularity is not satisfied, the result will be a partial solution
608:
generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small.
589:
581:
3480:
2983:
2569:
2443:
The way undefined variables can be handled is dependent upon the context of the problem. In the general case, given a
2260:
Once the minimum cut is known, each variable receives a value depending upon the position of its corresponding nodes
593:
3890:
3808:
2890:
27:
597:
2254:
2193:
2028:
1863:
1698:
379:
2350:
belongs to the connected component containing the sink then the variable will have value of 0. Vice versa, if
1542:
1400:
340:
31:
2861:
and vice versa. In some constructions it is useful to ensure that the function has a specific form, called
927:
713:
685:
577:
344:
290:
2481:
1827:
1662:
748:
192:{\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})}
2162:
2131:
1997:
1966:
1511:
1369:
1012:
842:
797:
1801:
1636:
1485:
1343:
3361:
3278:
2815:
2788:
375:
3562:
3200:
3098:
2842:
2766:
905:
883:
691:
3766:
3695:
3438:
3323:
3240:
2444:
2086:
1921:
1756:
1591:
387:
3162:
3060:
640:
3734:
3663:
3406:
2645:
2626:
Kolmogorov, Vladimir; Rother, Carsten (2007). "Minimizing
Nonsubmodular Functions: A Review".
1449:
1307:
3629:
2455:
2955:
2637:
2578:
2564:
405:
3602:
1144:
1117:
985:
958:
2440:
belong to the same connected component, then the value of the variable will be undefined.
383:
368:
2418:
2395:
to the one containing the source, then the variable will have value of 1. If both nodes
2373:
2328:
2283:
1258:
3139:
2885:
is in normal form if the two following conditions hold (Kolmogorov and Rother (2007)):
2868:
2398:
2353:
2308:
2263:
1283:
1238:
1218:
1198:
1178:
777:
667:
391:
350:
322:
3910:
2591:
2582:
2567:(1989). "A decomposition method for minimizing quadratic pseudo-boolean functions".
625:
QPBO produces a solution where each variable assumes one of three possible values:
2657:
Rother, Carsten; Kolmogorov, Vladimir; Lempitsky, Victor; Szummer, Martin (2007).
3900:
2250:
613:
585:
203:
3886:
2865:, which is always defined for any function, and it is not unique. A function
2641:
3896:
2649:
3235:
such that the second condition of normality is not satisfied, substitute:
684:
is submodular, then QPBO produces a global minimum exactly, equivalent to
584:, and the global minimum can be found in polynomial time by computing a
2449:
604:
2590:
Fix, Alexander; Gruber, Aritanan; Boros, Endre; Zabih, Ramin (2011).
580:. It is indeed possible to represent it with a non-negative weighted
566:{\displaystyle w_{pq}(0,0)+w_{pq}(1,1)\leq w_{pq}(0,1)+w_{pq}(1,0)}
2687:
The representation of a pseudo-Boolean function with coefficients
1109:
1110:
280:{\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}}
2629:
IEEE Transactions on
Pattern Analysis and Machine Intelligence
16:
Combinatorial optimization method for pseudo-Boolean functions
2325:
belongs to the connected component containing the source and
657:
respectively. The solution has the following two properties.
1094:{\displaystyle f({\hat {\mathbf {y} }})\leq f(\mathbf {y} )}
588:
of the graph, which can be computed with algorithms such as
2593:
A graph cut algorithm for higher-order Markov random fields
2370:
belongs to the connected component containing the sink and
432:
of the quadratic terms satisfy the submodularity condition
2611:
Higher-Order Clique
Reduction Without Auxiliary Variables
2756:{\displaystyle \mathbf {w} =(w_{0},w_{1},\dots ,w_{nn})}
2452:
problem. In the context of iterative algorithms such as
902:
generated by QPBO and an arbitrary assignment of values
603:
If the function is not submodular, then the problem is
3811:
3769:
3737:
3698:
3666:
3632:
3605:
3565:
3483:
3441:
3409:
3364:
3326:
3281:
3243:
3203:
3165:
3142:
3101:
3063:
2986:
2958:
2893:
2871:
2845:
2818:
2791:
2769:
2693:
2668:
Conference on
Computer Vision and Pattern Recognition
2619:
Conference on
Computer Vision and Pattern Recognition
2458:
2421:
2401:
2376:
2356:
2331:
2311:
2286:
2266:
2196:
2165:
2134:
2089:
2031:
2000:
1969:
1924:
1866:
1830:
1804:
1759:
1701:
1665:
1639:
1594:
1545:
1514:
1488:
1452:
1403:
1372:
1346:
1310:
1286:
1261:
1241:
1221:
1201:
1181:
1147:
1120:
1050:
1015:
988:
961:
930:
908:
886:
845:
800:
780:
751:
716:
694:
670:
643:
441:
408:
353:
325:
293:
211:
43:
576:
then the function can be efficiently optimised with
343:
then QPBO produces a global optimum equivalently to
3862:
3793:
3755:
3722:
3684:
3651:
3618:
3589:
3546:
3465:
3427:
3394:
3350:
3311:
3267:
3227:
3189:
3148:
3125:
3087:
3049:
2970:
2944:
2877:
2853:
2831:
2804:
2777:
2755:
2464:
2432:
2407:
2387:
2362:
2342:
2317:
2297:
2272:
2237:
2182:
2151:
2120:
2072:
2017:
1986:
1955:
1907:
1852:
1816:
1790:
1742:
1687:
1651:
1625:
1577:
1531:
1500:
1474:
1435:
1389:
1358:
1332:
1292:
1272:
1247:
1227:
1207:
1187:
1160:
1133:
1093:
1036:
1001:
974:
947:
916:
894:
866:
831:
786:
766:
737:
702:
676:
649:
565:
424:
359:
331:
311:
279:
191:
3547:{\displaystyle a=\min\{w_{pq}^{0j},w_{pq}^{1j}\}}
3050:{\displaystyle \min\{w_{pq}^{0j},w_{pq}^{1j}\}=0}
1175:When constructing the graph, the set of vertices
3818:
3490:
2987:
2894:
2660:Optimizing binary MRFs via extended roof duality
1114:Graph representing a function of two variables
2763:is not unique, and if two coefficient vectors
3863:{\displaystyle a=\min\{w_{p}^{0},w_{p}^{1}\}}
2945:{\displaystyle \min\{w_{p}^{0},w_{p}^{1}\}=0}
8:
3857:
3821:
3541:
3493:
3222:
3210:
3120:
3108:
3038:
2990:
2933:
2897:
274:
256:
237:
225:
2601:International Conference on Computer Vision
240:
3851:
3846:
3833:
3828:
3810:
3779:
3774:
3768:
3747:
3742:
3736:
3708:
3703:
3697:
3676:
3671:
3665:
3637:
3631:
3610:
3604:
3564:
3532:
3524:
3508:
3500:
3482:
3451:
3446:
3440:
3419:
3414:
3408:
3377:
3369:
3363:
3339:
3331:
3325:
3294:
3286:
3280:
3256:
3248:
3242:
3202:
3164:
3141:
3100:
3062:
3029:
3021:
3005:
2997:
2985:
2957:
2927:
2922:
2909:
2904:
2892:
2870:
2846:
2844:
2820:
2817:
2793:
2790:
2770:
2768:
2741:
2722:
2709:
2694:
2692:
2457:
2420:
2400:
2375:
2355:
2330:
2310:
2285:
2265:
2238:{\displaystyle {\frac {1}{2}}w_{pq}(1,1)}
2211:
2197:
2195:
2164:
2133:
2094:
2088:
2073:{\displaystyle {\frac {1}{2}}w_{pq}(0,0)}
2046:
2032:
2030:
1999:
1968:
1929:
1923:
1908:{\displaystyle {\frac {1}{2}}w_{pq}(1,0)}
1881:
1867:
1865:
1829:
1803:
1764:
1758:
1743:{\displaystyle {\frac {1}{2}}w_{pq}(0,1)}
1716:
1702:
1700:
1664:
1638:
1599:
1593:
1560:
1546:
1544:
1513:
1487:
1457:
1451:
1418:
1404:
1402:
1371:
1345:
1315:
1309:
1285:
1260:
1240:
1220:
1200:
1180:
1152:
1146:
1125:
1119:
1083:
1060:
1058:
1057:
1049:
1023:
1022:
1014:
993:
987:
966:
960:
934:
932:
931:
929:
909:
907:
887:
885:
853:
852:
844:
823:
818:
805:
799:
779:
757:
752:
750:
718:
717:
715:
695:
693:
669:
642:
539:
508:
477:
446:
440:
413:
407:
352:
324:
292:
216:
210:
180:
167:
151:
123:
107:
94:
78:
65:
50:
42:
2519:
2517:
2515:
2505:
2503:
2501:
2499:
2497:
398:Optimization of non-submodular functions
2680:
2493:
374:QPBO is a useful tool for inference on
3922:Computational problems in graph theory
1578:{\displaystyle {\frac {1}{2}}w_{p}(1)}
1436:{\displaystyle {\frac {1}{2}}w_{p}(0)}
637:, noted in the following as 1, 0, and
2839:is said to be a reparametrisation of
948:{\displaystyle {\hat {\mathbf {y} }}}
738:{\displaystyle {\hat {V}}\subseteq V}
20:Quadratic pseudo-Boolean optimisation
7:
2253:of the graph can be computed with a
924:to the variables, if a new solution
312:{\displaystyle E\subseteq V\times V}
1195:contains the source and sink nodes
644:
241:
14:
2812:represent the same function then
2847:
2821:
2794:
2771:
2695:
1853:{\displaystyle p'\rightarrow q'}
1688:{\displaystyle q'\rightarrow p'}
1084:
1061:
935:
910:
888:
767:{\displaystyle \mathbf {x^{*}} }
758:
754:
696:
51:
30:method for minimizing quadratic
3159:as long as there exist indices
2183:{\displaystyle p'\rightarrow q}
2152:{\displaystyle q'\rightarrow p}
2018:{\displaystyle q\rightarrow p'}
1987:{\displaystyle p\rightarrow q'}
1532:{\displaystyle p'\rightarrow t}
1390:{\displaystyle s\rightarrow p'}
1037:{\displaystyle i\in {\hat {V}}}
867:{\displaystyle i\in {\hat {V}}}
832:{\displaystyle x_{i}=x_{i}^{*}}
3178:
3166:
3076:
3064:
2750:
2702:
2532:Billionnet and Jaumard (1989).
2232:
2220:
2174:
2143:
2115:
2103:
2067:
2055:
2004:
1973:
1950:
1938:
1902:
1890:
1839:
1817:{\displaystyle q\rightarrow p}
1808:
1785:
1773:
1737:
1725:
1674:
1652:{\displaystyle p\rightarrow q}
1643:
1620:
1608:
1572:
1566:
1523:
1501:{\displaystyle s\rightarrow p}
1492:
1469:
1463:
1430:
1424:
1376:
1359:{\displaystyle p\rightarrow t}
1350:
1327:
1321:
1088:
1080:
1071:
1065:
1054:
1028:
939:
858:
723:
560:
548:
529:
517:
498:
486:
467:
455:
186:
160:
136:
124:
113:
100:
55:
47:
1:
3395:{\displaystyle w_{pq}^{1j}-a}
3312:{\displaystyle w_{pq}^{0j}-a}
2832:{\displaystyle \mathbf {w} '}
2805:{\displaystyle \mathbf {w} '}
2509:Kolmogorov and Rother (2007).
3897:Implementation of HOCR (C++)
3887:Implementation of QPBO (C++)
3590:{\displaystyle p=1,\dots ,n}
3228:{\displaystyle j\in \{0,1\}}
3136:Given an arbitrary function
3126:{\displaystyle j\in \{0,1\}}
2854:{\displaystyle \mathbf {w} }
2778:{\displaystyle \mathbf {w} }
2583:10.1016/0167-6377(89)90043-6
955:is constructed by replacing
917:{\displaystyle \mathbf {y} }
895:{\displaystyle \mathbf {x} }
703:{\displaystyle \mathbf {x} }
3794:{\displaystyle w_{p}^{1}-a}
3723:{\displaystyle w_{p}^{0}-a}
3466:{\displaystyle w_{q}^{j}+a}
3351:{\displaystyle w_{pq}^{1j}}
3268:{\displaystyle w_{pq}^{0j}}
2621:. IEEE. pp. 1362–1269.
2570:Operations Research Letters
2121:{\displaystyle w_{pq}(1,1)}
1956:{\displaystyle w_{pq}(0,0)}
1791:{\displaystyle w_{pq}(1,0)}
1626:{\displaystyle w_{pq}(0,1)}
3938:
3917:Combinatorial optimization
3891:GNU General Public License
3190:{\displaystyle (p,q)\in E}
3088:{\displaystyle (p,q)\in E}
2608:Ishikawa, Hiroshi (2014).
650:{\displaystyle \emptyset }
382:, and has applications in
28:combinatorial optimization
3893:, by Vladimir Kolmogorov.
3756:{\displaystyle w_{p}^{1}}
3685:{\displaystyle w_{p}^{0}}
3428:{\displaystyle w_{q}^{j}}
380:conditional random fields
1475:{\displaystyle w_{p}(1)}
1333:{\displaystyle w_{p}(0)}
32:pseudo-Boolean functions
3652:{\displaystyle w_{0}+a}
2642:10.1109/tpami.2007.1031
2465:{\displaystyle \alpha }
3903:, by Hiroshi Ishikawa.
3899:, available under the
3889:, available under the
3864:
3795:
3757:
3724:
3686:
3653:
3620:
3591:
3548:
3467:
3429:
3396:
3352:
3313:
3269:
3229:
3191:
3150:
3127:
3089:
3051:
2972:
2971:{\displaystyle p\in V}
2946:
2879:
2855:
2833:
2806:
2779:
2757:
2636:(7). IEEE: 1274–1279.
2466:
2434:
2409:
2389:
2364:
2344:
2319:
2299:
2274:
2239:
2184:
2153:
2122:
2074:
2019:
1988:
1957:
1909:
1854:
1818:
1792:
1744:
1689:
1653:
1627:
1579:
1533:
1502:
1476:
1437:
1391:
1360:
1334:
1294:
1274:
1249:
1235:, and a pair of nodes
1229:
1209:
1189:
1169:
1162:
1135:
1095:
1038:
1003:
976:
949:
918:
896:
868:
833:
788:
768:
739:
704:
678:
651:
578:graph cut optimization
567:
426:
425:{\displaystyle w_{pq}}
361:
345:graph cut optimization
333:
313:
281:
193:
3865:
3796:
3758:
3725:
3687:
3654:
3621:
3619:{\displaystyle w_{0}}
3592:
3549:
3468:
3430:
3397:
3353:
3314:
3270:
3230:
3192:
3151:
3128:
3090:
3052:
2973:
2947:
2880:
2856:
2834:
2807:
2780:
2758:
2603:. pp. 1020–1027.
2523:Rother et al. (2007).
2467:
2435:
2410:
2390:
2365:
2345:
2320:
2300:
2275:
2240:
2185:
2154:
2123:
2075:
2020:
1989:
1958:
1910:
1855:
1819:
1793:
1745:
1690:
1654:
1628:
1580:
1534:
1503:
1477:
1438:
1392:
1361:
1335:
1295:
1275:
1250:
1230:
1210:
1190:
1163:
1161:{\displaystyle x_{q}}
1136:
1134:{\displaystyle x_{p}}
1113:
1096:
1039:
1004:
1002:{\displaystyle x_{i}}
977:
975:{\displaystyle y_{i}}
950:
919:
897:
869:
834:
789:
769:
740:
705:
679:
652:
568:
427:
362:
334:
314:
282:
194:
3809:
3767:
3735:
3696:
3664:
3630:
3603:
3563:
3481:
3439:
3407:
3362:
3324:
3279:
3241:
3201:
3163:
3140:
3099:
3061:
2984:
2956:
2891:
2869:
2843:
2816:
2789:
2767:
2691:
2456:
2419:
2399:
2374:
2354:
2329:
2309:
2284:
2264:
2194:
2163:
2132:
2087:
2029:
1998:
1967:
1922:
1864:
1828:
1802:
1757:
1699:
1663:
1637:
1592:
1543:
1512:
1486:
1450:
1401:
1370:
1344:
1308:
1284:
1259:
1239:
1219:
1199:
1179:
1145:
1118:
1048:
1013:
986:
959:
928:
906:
884:
843:
798:
778:
749:
714:
692:
668:
641:
439:
406:
402:If the coefficients
376:Markov random fields
351:
323:
291:
209:
41:
3856:
3838:
3784:
3752:
3713:
3681:
3540:
3516:
3456:
3424:
3385:
3347:
3302:
3264:
3037:
3013:
2932:
2914:
2563:Billionnet, Alain;
880:: given a solution
828:
3860:
3842:
3824:
3791:
3770:
3753:
3738:
3720:
3699:
3682:
3667:
3649:
3616:
3587:
3544:
3520:
3496:
3463:
3442:
3425:
3410:
3392:
3365:
3348:
3327:
3309:
3282:
3265:
3244:
3225:
3187:
3146:
3123:
3085:
3047:
3017:
2993:
2968:
2942:
2918:
2900:
2875:
2851:
2829:
2802:
2775:
2753:
2541:Fix et al. (2011).
2476:Higher order terms
2462:
2433:{\displaystyle p'}
2430:
2405:
2388:{\displaystyle p'}
2385:
2360:
2343:{\displaystyle p'}
2340:
2315:
2298:{\displaystyle p'}
2295:
2270:
2255:max-flow algorithm
2235:
2180:
2149:
2118:
2070:
2015:
1984:
1953:
1905:
1850:
1814:
1788:
1740:
1685:
1649:
1623:
1575:
1529:
1498:
1472:
1433:
1387:
1356:
1330:
1290:
1273:{\displaystyle p'}
1270:
1245:
1225:
1205:
1185:
1170:
1158:
1131:
1091:
1034:
999:
972:
945:
914:
892:
864:
829:
814:
784:
764:
735:
700:
674:
662:Partial optimality
647:
563:
422:
388:image segmentation
357:
329:
309:
277:
189:
146:
89:
3149:{\displaystyle f}
2878:{\displaystyle f}
2565:Jaumard, Brigitte
2408:{\displaystyle p}
2363:{\displaystyle p}
2318:{\displaystyle p}
2273:{\displaystyle p}
2205:
2040:
1875:
1710:
1554:
1412:
1293:{\displaystyle w}
1248:{\displaystyle p}
1228:{\displaystyle t}
1208:{\displaystyle s}
1188:{\displaystyle V}
1068:
1031:
942:
861:
787:{\displaystyle f}
726:
677:{\displaystyle f}
598:Boykov–Kolmogorov
386:problems such as
360:{\displaystyle f}
332:{\displaystyle f}
119:
74:
3929:
3875:
3869:
3867:
3866:
3861:
3855:
3850:
3837:
3832:
3800:
3798:
3797:
3792:
3783:
3778:
3762:
3760:
3759:
3754:
3751:
3746:
3729:
3727:
3726:
3721:
3712:
3707:
3691:
3689:
3688:
3683:
3680:
3675:
3658:
3656:
3655:
3650:
3642:
3641:
3625:
3623:
3622:
3617:
3615:
3614:
3596:
3594:
3593:
3588:
3553:
3551:
3550:
3545:
3539:
3531:
3515:
3507:
3472:
3470:
3469:
3464:
3455:
3450:
3434:
3432:
3431:
3426:
3423:
3418:
3401:
3399:
3398:
3393:
3384:
3376:
3357:
3355:
3354:
3349:
3346:
3338:
3318:
3316:
3315:
3310:
3301:
3293:
3274:
3272:
3271:
3266:
3263:
3255:
3234:
3232:
3231:
3226:
3196:
3194:
3193:
3188:
3155:
3153:
3152:
3147:
3132:
3130:
3129:
3124:
3094:
3092:
3091:
3086:
3056:
3054:
3053:
3048:
3036:
3028:
3012:
3004:
2977:
2975:
2974:
2969:
2951:
2949:
2948:
2943:
2931:
2926:
2913:
2908:
2884:
2882:
2881:
2876:
2860:
2858:
2857:
2852:
2850:
2838:
2836:
2835:
2830:
2828:
2824:
2811:
2809:
2808:
2803:
2801:
2797:
2784:
2782:
2781:
2776:
2774:
2762:
2760:
2759:
2754:
2749:
2748:
2727:
2726:
2714:
2713:
2698:
2685:
2671:
2665:
2653:
2622:
2616:
2604:
2598:
2586:
2551:
2550:Ishikawa (2014).
2548:
2542:
2539:
2533:
2530:
2524:
2521:
2510:
2507:
2471:
2469:
2468:
2463:
2439:
2437:
2436:
2431:
2429:
2414:
2412:
2411:
2406:
2394:
2392:
2391:
2386:
2384:
2369:
2367:
2366:
2361:
2349:
2347:
2346:
2341:
2339:
2324:
2322:
2321:
2316:
2304:
2302:
2301:
2296:
2294:
2279:
2277:
2276:
2271:
2244:
2242:
2241:
2236:
2219:
2218:
2206:
2198:
2189:
2187:
2186:
2181:
2173:
2158:
2156:
2155:
2150:
2142:
2127:
2125:
2124:
2119:
2102:
2101:
2079:
2077:
2076:
2071:
2054:
2053:
2041:
2033:
2024:
2022:
2021:
2016:
2014:
1993:
1991:
1990:
1985:
1983:
1962:
1960:
1959:
1954:
1937:
1936:
1914:
1912:
1911:
1906:
1889:
1888:
1876:
1868:
1859:
1857:
1856:
1851:
1849:
1838:
1823:
1821:
1820:
1815:
1797:
1795:
1794:
1789:
1772:
1771:
1749:
1747:
1746:
1741:
1724:
1723:
1711:
1703:
1694:
1692:
1691:
1686:
1684:
1673:
1658:
1656:
1655:
1650:
1632:
1630:
1629:
1624:
1607:
1606:
1584:
1582:
1581:
1576:
1565:
1564:
1555:
1547:
1538:
1536:
1535:
1530:
1522:
1507:
1505:
1504:
1499:
1481:
1479:
1478:
1473:
1462:
1461:
1442:
1440:
1439:
1434:
1423:
1422:
1413:
1405:
1396:
1394:
1393:
1388:
1386:
1365:
1363:
1362:
1357:
1339:
1337:
1336:
1331:
1320:
1319:
1299:
1297:
1296:
1291:
1279:
1277:
1276:
1271:
1269:
1254:
1252:
1251:
1246:
1234:
1232:
1231:
1226:
1214:
1212:
1211:
1206:
1194:
1192:
1191:
1186:
1167:
1165:
1164:
1159:
1157:
1156:
1140:
1138:
1137:
1132:
1130:
1129:
1100:
1098:
1097:
1092:
1087:
1070:
1069:
1064:
1059:
1043:
1041:
1040:
1035:
1033:
1032:
1024:
1008:
1006:
1005:
1000:
998:
997:
981:
979:
978:
973:
971:
970:
954:
952:
951:
946:
944:
943:
938:
933:
923:
921:
920:
915:
913:
901:
899:
898:
893:
891:
873:
871:
870:
865:
863:
862:
854:
838:
836:
835:
830:
827:
822:
810:
809:
793:
791:
790:
785:
773:
771:
770:
765:
763:
762:
761:
744:
742:
741:
736:
728:
727:
719:
709:
707:
706:
701:
699:
683:
681:
680:
675:
656:
654:
653:
648:
572:
570:
569:
564:
547:
546:
516:
515:
485:
484:
454:
453:
431:
429:
428:
423:
421:
420:
366:
364:
363:
358:
338:
336:
335:
330:
318:
316:
315:
310:
286:
284:
283:
278:
221:
220:
204:binary variables
198:
196:
195:
190:
185:
184:
172:
171:
159:
158:
145:
112:
111:
99:
98:
88:
70:
69:
54:
3937:
3936:
3932:
3931:
3930:
3928:
3927:
3926:
3907:
3906:
3883:
3878:
3807:
3806:
3765:
3764:
3733:
3732:
3694:
3693:
3662:
3661:
3633:
3628:
3627:
3606:
3601:
3600:
3561:
3560:
3479:
3478:
3437:
3436:
3405:
3404:
3360:
3359:
3322:
3321:
3277:
3276:
3239:
3238:
3199:
3198:
3161:
3160:
3138:
3137:
3097:
3096:
3059:
3058:
2982:
2981:
2954:
2953:
2889:
2888:
2867:
2866:
2841:
2840:
2819:
2814:
2813:
2792:
2787:
2786:
2765:
2764:
2737:
2718:
2705:
2689:
2688:
2686:
2682:
2678:
2670:. pp. 1–8.
2663:
2656:
2625:
2614:
2607:
2596:
2589:
2562:
2559:
2554:
2549:
2545:
2540:
2536:
2531:
2527:
2522:
2513:
2508:
2495:
2491:
2478:
2454:
2453:
2422:
2417:
2416:
2397:
2396:
2377:
2372:
2371:
2352:
2351:
2332:
2327:
2326:
2307:
2306:
2287:
2282:
2281:
2262:
2261:
2207:
2192:
2191:
2166:
2161:
2160:
2135:
2130:
2129:
2090:
2085:
2084:
2042:
2027:
2026:
2007:
1996:
1995:
1976:
1965:
1964:
1925:
1920:
1919:
1877:
1862:
1861:
1842:
1831:
1826:
1825:
1800:
1799:
1760:
1755:
1754:
1712:
1697:
1696:
1677:
1666:
1661:
1660:
1635:
1634:
1595:
1590:
1589:
1556:
1541:
1540:
1515:
1510:
1509:
1484:
1483:
1453:
1448:
1447:
1414:
1399:
1398:
1379:
1368:
1367:
1342:
1341:
1311:
1306:
1305:
1282:
1281:
1262:
1257:
1256:
1237:
1236:
1217:
1216:
1197:
1196:
1177:
1176:
1148:
1143:
1142:
1121:
1116:
1115:
1108:
1046:
1045:
1011:
1010:
989:
984:
983:
962:
957:
956:
926:
925:
904:
903:
882:
881:
841:
840:
801:
796:
795:
776:
775:
753:
747:
746:
712:
711:
710:where a subset
690:
689:
666:
665:
639:
638:
623:
535:
504:
473:
442:
437:
436:
409:
404:
403:
400:
392:stereo matching
384:computer vision
369:polynomial time
349:
348:
321:
320:
289:
288:
212:
207:
206:
176:
163:
147:
103:
90:
61:
39:
38:
17:
12:
11:
5:
3935:
3933:
3925:
3924:
3919:
3909:
3908:
3905:
3904:
3894:
3882:
3881:External links
3879:
3877:
3876:
3874:
3873:
3872:
3871:
3859:
3854:
3849:
3845:
3841:
3836:
3831:
3827:
3823:
3820:
3817:
3814:
3802:
3801:
3790:
3787:
3782:
3777:
3773:
3750:
3745:
3741:
3730:
3719:
3716:
3711:
3706:
3702:
3679:
3674:
3670:
3659:
3648:
3645:
3640:
3636:
3613:
3609:
3597:, substitute:
3586:
3583:
3580:
3577:
3574:
3571:
3568:
3557:
3556:
3555:
3543:
3538:
3535:
3530:
3527:
3523:
3519:
3514:
3511:
3506:
3503:
3499:
3495:
3492:
3489:
3486:
3474:
3473:
3462:
3459:
3454:
3449:
3445:
3422:
3417:
3413:
3402:
3391:
3388:
3383:
3380:
3375:
3372:
3368:
3345:
3342:
3337:
3334:
3330:
3319:
3308:
3305:
3300:
3297:
3292:
3289:
3285:
3262:
3259:
3254:
3251:
3247:
3224:
3221:
3218:
3215:
3212:
3209:
3206:
3186:
3183:
3180:
3177:
3174:
3171:
3168:
3145:
3135:
3134:
3122:
3119:
3116:
3113:
3110:
3107:
3104:
3084:
3081:
3078:
3075:
3072:
3069:
3066:
3046:
3043:
3040:
3035:
3032:
3027:
3024:
3020:
3016:
3011:
3008:
3003:
3000:
2996:
2992:
2989:
2979:
2967:
2964:
2961:
2941:
2938:
2935:
2930:
2925:
2921:
2917:
2912:
2907:
2903:
2899:
2896:
2874:
2849:
2827:
2823:
2800:
2796:
2773:
2752:
2747:
2744:
2740:
2736:
2733:
2730:
2725:
2721:
2717:
2712:
2708:
2704:
2701:
2697:
2679:
2677:
2674:
2673:
2672:
2654:
2623:
2605:
2587:
2577:(3): 161–163.
2558:
2555:
2553:
2552:
2543:
2534:
2525:
2511:
2492:
2490:
2487:
2477:
2474:
2461:
2428:
2425:
2404:
2383:
2380:
2359:
2338:
2335:
2314:
2293:
2290:
2269:
2247:
2246:
2234:
2231:
2228:
2225:
2222:
2217:
2214:
2210:
2204:
2201:
2190:, with weight
2179:
2176:
2172:
2169:
2148:
2145:
2141:
2138:
2117:
2114:
2111:
2108:
2105:
2100:
2097:
2093:
2083:for each term
2081:
2069:
2066:
2063:
2060:
2057:
2052:
2049:
2045:
2039:
2036:
2025:, with weight
2013:
2010:
2006:
2003:
1982:
1979:
1975:
1972:
1952:
1949:
1946:
1943:
1940:
1935:
1932:
1928:
1918:for each term
1916:
1904:
1901:
1898:
1895:
1892:
1887:
1884:
1880:
1874:
1871:
1860:, with weight
1848:
1845:
1841:
1837:
1834:
1813:
1810:
1807:
1787:
1784:
1781:
1778:
1775:
1770:
1767:
1763:
1753:for each term
1751:
1739:
1736:
1733:
1730:
1727:
1722:
1719:
1715:
1709:
1706:
1695:, with weight
1683:
1680:
1676:
1672:
1669:
1648:
1645:
1642:
1622:
1619:
1616:
1613:
1610:
1605:
1602:
1598:
1588:for each term
1586:
1574:
1571:
1568:
1563:
1559:
1553:
1550:
1539:, with weight
1528:
1525:
1521:
1518:
1497:
1494:
1491:
1471:
1468:
1465:
1460:
1456:
1446:for each term
1444:
1432:
1429:
1426:
1421:
1417:
1411:
1408:
1397:, with weight
1385:
1382:
1378:
1375:
1355:
1352:
1349:
1329:
1326:
1323:
1318:
1314:
1304:for each term
1289:
1268:
1265:
1244:
1224:
1204:
1184:
1155:
1151:
1128:
1124:
1107:
1104:
1103:
1102:
1090:
1086:
1082:
1079:
1076:
1073:
1067:
1063:
1056:
1053:
1030:
1027:
1021:
1018:
996:
992:
969:
965:
941:
937:
912:
890:
875:
860:
857:
851:
848:
826:
821:
817:
813:
808:
804:
783:
760:
756:
734:
731:
725:
722:
698:
673:
646:
622:
619:
590:Ford–Fulkerson
574:
573:
562:
559:
556:
553:
550:
545:
542:
538:
534:
531:
528:
525:
522:
519:
514:
511:
507:
503:
500:
497:
494:
491:
488:
483:
480:
476:
472:
469:
466:
463:
460:
457:
452:
449:
445:
419:
416:
412:
399:
396:
356:
328:
308:
305:
302:
299:
296:
276:
273:
270:
267:
264:
261:
258:
255:
252:
249:
246:
243:
239:
236:
233:
230:
227:
224:
219:
215:
200:
199:
188:
183:
179:
175:
170:
166:
162:
157:
154:
150:
144:
141:
138:
135:
132:
129:
126:
122:
118:
115:
110:
106:
102:
97:
93:
87:
84:
81:
77:
73:
68:
64:
60:
57:
53:
49:
46:
15:
13:
10:
9:
6:
4:
3:
2:
3934:
3923:
3920:
3918:
3915:
3914:
3912:
3902:
3898:
3895:
3892:
3888:
3885:
3884:
3880:
3852:
3847:
3843:
3839:
3834:
3829:
3825:
3815:
3812:
3804:
3803:
3788:
3785:
3780:
3775:
3771:
3748:
3743:
3739:
3731:
3717:
3714:
3709:
3704:
3700:
3677:
3672:
3668:
3660:
3646:
3643:
3638:
3634:
3611:
3607:
3599:
3598:
3584:
3581:
3578:
3575:
3572:
3569:
3566:
3558:
3536:
3533:
3528:
3525:
3521:
3517:
3512:
3509:
3504:
3501:
3497:
3487:
3484:
3476:
3475:
3460:
3457:
3452:
3447:
3443:
3420:
3415:
3411:
3403:
3389:
3386:
3381:
3378:
3373:
3370:
3366:
3343:
3340:
3335:
3332:
3328:
3320:
3306:
3303:
3298:
3295:
3290:
3287:
3283:
3260:
3257:
3252:
3249:
3245:
3237:
3236:
3219:
3216:
3213:
3207:
3204:
3184:
3181:
3175:
3172:
3169:
3158:
3157:
3143:
3117:
3114:
3111:
3105:
3102:
3095:and for each
3082:
3079:
3073:
3070:
3067:
3044:
3041:
3033:
3030:
3025:
3022:
3018:
3014:
3009:
3006:
3001:
2998:
2994:
2980:
2965:
2962:
2959:
2939:
2936:
2928:
2923:
2919:
2915:
2910:
2905:
2901:
2887:
2886:
2872:
2864:
2825:
2798:
2745:
2742:
2738:
2734:
2731:
2728:
2723:
2719:
2715:
2710:
2706:
2699:
2684:
2681:
2675:
2669:
2662:
2661:
2655:
2651:
2647:
2643:
2639:
2635:
2631:
2630:
2624:
2620:
2613:
2612:
2606:
2602:
2595:
2594:
2588:
2584:
2580:
2576:
2572:
2571:
2566:
2561:
2560:
2556:
2547:
2544:
2538:
2535:
2529:
2526:
2520:
2518:
2516:
2512:
2506:
2504:
2502:
2500:
2498:
2494:
2488:
2486:
2483:
2475:
2473:
2459:
2451:
2446:
2441:
2426:
2423:
2402:
2381:
2378:
2357:
2336:
2333:
2312:
2291:
2288:
2267:
2258:
2256:
2252:
2229:
2226:
2223:
2215:
2212:
2208:
2202:
2199:
2177:
2170:
2167:
2146:
2139:
2136:
2112:
2109:
2106:
2098:
2095:
2091:
2082:
2064:
2061:
2058:
2050:
2047:
2043:
2037:
2034:
2011:
2008:
2001:
1980:
1977:
1970:
1947:
1944:
1941:
1933:
1930:
1926:
1917:
1899:
1896:
1893:
1885:
1882:
1878:
1872:
1869:
1846:
1843:
1835:
1832:
1811:
1805:
1782:
1779:
1776:
1768:
1765:
1761:
1752:
1734:
1731:
1728:
1720:
1717:
1713:
1707:
1704:
1681:
1678:
1670:
1667:
1646:
1640:
1617:
1614:
1611:
1603:
1600:
1596:
1587:
1569:
1561:
1557:
1551:
1548:
1526:
1519:
1516:
1495:
1489:
1466:
1458:
1454:
1445:
1427:
1419:
1415:
1409:
1406:
1383:
1380:
1373:
1353:
1347:
1324:
1316:
1312:
1303:
1302:
1301:
1287:
1266:
1263:
1242:
1222:
1202:
1182:
1173:
1153:
1149:
1126:
1122:
1112:
1105:
1077:
1074:
1051:
1025:
1019:
1016:
994:
990:
967:
963:
879:
876:
855:
849:
846:
824:
819:
815:
811:
806:
802:
781:
732:
729:
720:
687:
671:
663:
660:
659:
658:
636:
632:
628:
620:
618:
615:
609:
606:
601:
599:
595:
591:
587:
583:
579:
557:
554:
551:
543:
540:
536:
532:
526:
523:
520:
512:
509:
505:
501:
495:
492:
489:
481:
478:
474:
470:
464:
461:
458:
450:
447:
443:
435:
434:
433:
417:
414:
410:
397:
395:
393:
389:
385:
381:
377:
372:
370:
354:
346:
342:
326:
306:
303:
300:
297:
294:
271:
268:
265:
262:
259:
253:
250:
247:
244:
234:
231:
228:
222:
217:
213:
205:
181:
177:
173:
168:
164:
155:
152:
148:
142:
139:
133:
130:
127:
120:
116:
108:
104:
95:
91:
85:
82:
79:
75:
71:
66:
62:
58:
44:
37:
36:
35:
33:
29:
25:
21:
2862:
2683:
2659:
2633:
2627:
2610:
2592:
2574:
2568:
2546:
2537:
2528:
2479:
2442:
2259:
2248:
1174:
1171:
877:
661:
634:
630:
626:
624:
610:
602:
594:Edmonds–Karp
575:
401:
373:
201:
34:in the form
23:
19:
18:
3901:MIT license
2863:normal form
2251:minimum cut
878:Persistence
614:minimum cut
586:minimum cut
347:, while if
3911:Categories
2557:References
2128:the edges
1963:the edges
1798:the edges
1633:the edges
1482:the edges
1340:the edges
794:such that
621:Properties
341:submodular
3786:−
3715:−
3579:…
3387:−
3304:−
3208:∈
3182:∈
3106:∈
3080:∈
3057:for each
2963:∈
2952:for each
2732:…
2460:α
2445:partition
2175:→
2144:→
2005:→
1974:→
1840:→
1809:→
1675:→
1644:→
1524:→
1493:→
1377:→
1351:→
1106:Algorithm
1075:≤
1066:^
1029:^
1020:∈
1009:for each
940:^
859:^
850:∈
839:for each
825:∗
759:∗
730:⊆
724:^
686:graph cut
645:∅
635:undefined
502:≤
304:×
298:⊆
266:…
248:∈
242:∀
223:∈
140:∈
121:∑
83:∈
76:∑
2826:′
2799:′
2650:17496384
2427:′
2382:′
2337:′
2292:′
2171:′
2140:′
2012:′
1981:′
1847:′
1836:′
1682:′
1671:′
1520:′
1384:′
1267:′
2450:NP-hard
1044:, then
605:NP-hard
287:, with
202:in the
26:) is a
3805:where
3477:where
2648:
2482:clique
633:, and
596:, and
3763:with
3692:with
3626:with
3435:with
3358:with
3275:with
2676:Notes
2664:(PDF)
2615:(PDF)
2597:(PDF)
2489:Notes
2305:: if
982:with
664:: if
631:false
582:graph
319:. If
3559:for
3197:and
2785:and
2646:PMID
2415:and
2280:and
2249:The
2159:and
1994:and
1824:and
1659:and
1508:and
1366:and
1255:and
1215:and
1141:and
774:for
627:true
600:'s.
390:and
378:and
24:QPBO
3819:min
3491:min
2988:min
2895:min
2638:doi
2579:doi
339:is
3913::
2666:.
2644:.
2634:29
2632:.
2617:.
2599:.
2573:.
2514:^
2496:^
1300::
629:,
592:,
394:.
371:.
3870:.
3858:}
3853:1
3848:p
3844:w
3840:,
3835:0
3830:p
3826:w
3822:{
3816:=
3813:a
3789:a
3781:1
3776:p
3772:w
3749:1
3744:p
3740:w
3718:a
3710:0
3705:p
3701:w
3678:0
3673:p
3669:w
3647:a
3644:+
3639:0
3635:w
3612:0
3608:w
3585:n
3582:,
3576:,
3573:1
3570:=
3567:p
3554:;
3542:}
3537:j
3534:1
3529:q
3526:p
3522:w
3518:,
3513:j
3510:0
3505:q
3502:p
3498:w
3494:{
3488:=
3485:a
3461:a
3458:+
3453:j
3448:q
3444:w
3421:j
3416:q
3412:w
3390:a
3382:j
3379:1
3374:q
3371:p
3367:w
3344:j
3341:1
3336:q
3333:p
3329:w
3307:a
3299:j
3296:0
3291:q
3288:p
3284:w
3261:j
3258:0
3253:q
3250:p
3246:w
3223:}
3220:1
3217:,
3214:0
3211:{
3205:j
3185:E
3179:)
3176:q
3173:,
3170:p
3167:(
3144:f
3133:.
3121:}
3118:1
3115:,
3112:0
3109:{
3103:j
3083:E
3077:)
3074:q
3071:,
3068:p
3065:(
3045:0
3042:=
3039:}
3034:j
3031:1
3026:q
3023:p
3019:w
3015:,
3010:j
3007:0
3002:q
2999:p
2995:w
2991:{
2978:;
2966:V
2960:p
2940:0
2937:=
2934:}
2929:1
2924:p
2920:w
2916:,
2911:0
2906:p
2902:w
2898:{
2873:f
2848:w
2822:w
2795:w
2772:w
2751:)
2746:n
2743:n
2739:w
2735:,
2729:,
2724:1
2720:w
2716:,
2711:0
2707:w
2703:(
2700:=
2696:w
2652:.
2640::
2585:.
2581::
2575:8
2424:p
2403:p
2379:p
2358:p
2334:p
2313:p
2289:p
2268:p
2245:.
2233:)
2230:1
2227:,
2224:1
2221:(
2216:q
2213:p
2209:w
2203:2
2200:1
2178:q
2168:p
2147:p
2137:q
2116:)
2113:1
2110:,
2107:1
2104:(
2099:q
2096:p
2092:w
2080:;
2068:)
2065:0
2062:,
2059:0
2056:(
2051:q
2048:p
2044:w
2038:2
2035:1
2009:p
2002:q
1978:q
1971:p
1951:)
1948:0
1945:,
1942:0
1939:(
1934:q
1931:p
1927:w
1915:;
1903:)
1900:0
1897:,
1894:1
1891:(
1886:q
1883:p
1879:w
1873:2
1870:1
1844:q
1833:p
1812:p
1806:q
1786:)
1783:0
1780:,
1777:1
1774:(
1769:q
1766:p
1762:w
1750:;
1738:)
1735:1
1732:,
1729:0
1726:(
1721:q
1718:p
1714:w
1708:2
1705:1
1679:p
1668:q
1647:q
1641:p
1621:)
1618:1
1615:,
1612:0
1609:(
1604:q
1601:p
1597:w
1585:;
1573:)
1570:1
1567:(
1562:p
1558:w
1552:2
1549:1
1527:t
1517:p
1496:p
1490:s
1470:)
1467:1
1464:(
1459:p
1455:w
1443:;
1431:)
1428:0
1425:(
1420:p
1416:w
1410:2
1407:1
1381:p
1374:s
1354:t
1348:p
1328:)
1325:0
1322:(
1317:p
1313:w
1288:w
1264:p
1243:p
1223:t
1203:s
1183:V
1168:.
1154:q
1150:x
1127:p
1123:x
1101:.
1089:)
1085:y
1081:(
1078:f
1072:)
1062:y
1055:(
1052:f
1026:V
1017:i
995:i
991:x
968:i
964:y
936:y
911:y
889:x
874:.
856:V
847:i
820:i
816:x
812:=
807:i
803:x
782:f
755:x
733:V
721:V
697:x
672:f
561:)
558:0
555:,
552:1
549:(
544:q
541:p
537:w
533:+
530:)
527:1
524:,
521:0
518:(
513:q
510:p
506:w
499:)
496:1
493:,
490:1
487:(
482:q
479:p
475:w
471:+
468:)
465:0
462:,
459:0
456:(
451:q
448:p
444:w
418:q
415:p
411:w
355:f
327:f
307:V
301:V
295:E
275:}
272:n
269:,
263:,
260:1
257:{
254:=
251:V
245:p
238:}
235:1
232:,
229:0
226:{
218:p
214:x
187:)
182:q
178:x
174:,
169:p
165:x
161:(
156:q
153:p
149:w
143:E
137:)
134:q
131:,
128:p
125:(
117:+
114:)
109:p
105:x
101:(
96:p
92:w
86:V
80:p
72:+
67:0
63:w
59:=
56:)
52:x
48:(
45:f
22:(
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
