In many computer vision tasks, we have to explore a large set of possible patterns to find at least one that conforms to a model. I propose efficient methods to tackle problems in different domains by taking advantage of the special structures of high-order global models. By constructing global methods properly, we can match objects quickly and reliably in cluttered images. Quickly localizing an object in clutter when the imagery of the target may appear scaled, rotated and deformed is a challenging task. Due to the scale and rotation consistency constraint, all the object parts are coupled together. I proposed two efficient approximation methods. The first one assumes convex pairwise term. This method has a unique lower convex hull property that allows us to discard large number of target points without sacrificing the quality of the solution. The second method allows general pairwise metrics on a tree augmented by linear nontree edges. This method enables us to search in the continuous scale and rotation space and in virtually arbitrary scale ranges efficiently.
High-order global methods also enable more reliable multiple object tracking. I proposed a multiple shortest path method that is able to handle occlusion, appearance consistency and group layout consistency in a uniform framework. Human pose estimation also benefits from global approaches. I proposed a consistent max-covering method, in which finding human pose is formulated as assembling body parts to fit a rough object foreground and at the same time maintain a valid body plan. I also proposed an efficient method that is able to detect human poses even when we do not know the target scale and rotation. The global methods yield much better results than traditional tree structure methods. Other problems that I tackled using global models include topology constrained object figure/ground separation, key point localization on fast moving articulated object, and finding cuboids in RGBD images.