Efficient planar graph cuts with applications in computer vision

We present a fast graph cut algorithm for planar graphs. It is based on the graph theoretical work [2] and leads to an efficient method that we apply on shape matching and im- age segmentation. In contrast to currently used methods in Computer Vision, the presented approach provides an upper bound for its runtime behavior that is almost linear. In par- ticular, we are able to match two different planar shapes of N points in O(N² log N) and segment a given image of N pixels in O(N logN). We present two experimental bench- mark studies which demonstrate that the presented method is also in practice faster than previously proposed graph cut methods: On planar shape matching and image seg- mentation we observe a speed-up of an order of magnitude, depending on resolution.