Higher-order inference for vision problems

Many problems of image understanding can be formulated as semantic segmentation, or the assignment of a 'class' label to every pixel in the image. Until recently, for reasons of efficiency, the problem of generating a good labelling of an image has been formulated as the minimisation of a pairwise Markov random field. However, these pairwise fields are unable to capture the higher-order statistics of natural images which can be used to enforce the coherence of regions in the image or to encourage particular regions to belong to a certain class. Despite these limitations, the use of pairwise Markov models is prevalent in vision. This can largely be attributed to the pragmatism of computer vision researchers; although such models do not fully capture image statistics, they service as an effective discriminative model that prevents individual pixels from being mislabelled. Moreover, unlike many optimisation approaches for higher-order models, approximation algorithms exist for pairwise models, that are guaranteed to find a solution whose cost must lie within a fixed bound of the cost of global optima. In this thesis, we show that the optimisation of many higher-order models can also be performed by approximate algorithms which have the same guarantees and effectiveness as those used for the optimisation of pairwise algorithms. We first consider the optimisation of the higher-order Associative Hierarchical Networks, and by transforming them into pairwise models, propose new approximate algorithms for efficiently minimising them. This work is the first to prove approximation bounds, independent of the size of cliques, for the widespread P" and robust P" models. We consider the problem of optimising the set of labels present in an image and the labelling of the image concurrently, and show how they can be optimised simultaneously using a variety of techniques. In the final chapter,EThOS - Electronic Theses Online ServiceGBUnited Kingdo