Thumbnail
Access Restriction
Open

Author Kumar, M. Pawan ♦ Veksler, Olga ♦ Torr, Philip H. S.
Source CiteSeerX
Content type Text
File Format PDF
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Truncated Convex Model ♦ Pairwise Potential ♦ Range Expansion ♦ Range Swap ♦ Posteriori Estimate ♦ Standard Real Data Problem ♦ Polynomial Time ♦ Standard Linear Programming ♦ Consecutive Label ♦ Multiplicative Bound ♦ Approximate Maximum ♦ Example Interiorpoint Algorithm ♦ Large Search Space ♦ Previous Approach ♦ Lp Relaxation ♦ Efficient St-mincut Algorithm ♦ Tree-reweighted Message Passing ♦ Discrete Random Field
Abstract We consider the problem of obtaining an approximate maximum a posteriori estimate of a discrete random field characterized by pairwise potentials that form a truncated convex model. For this problem, we propose two st-mincut based move making algorithms that we call Range Swap and Range Expansion. Our algorithms can be thought of as extensions of αβ-Swap and α-Expansion respectively that fully exploit the form of the pairwise potentials. Specifically, instead of dealing with one or two labels at each iteration, our methods explore a large search space by considering a range of labels (that is, an interval of consecutive labels). Furthermore, we show that Range Expansion provides the same multiplicative bounds as the standard linear programming (lp) relaxation in polynomial time. Compared to previous approaches based on the lp relaxation, for example interiorpoint algorithms or tree-reweighted message passing (trw), our methods are faster as they use only the efficient st-mincut algorithm in their design. We demonstrate the usefulness of the proposed approaches on both synthetic and standard real data problems.
Educational Role Student ♦ Teacher
Age Range above 22 year
Educational Use Research
Education Level UG and PG ♦ Career/Technical Study
Publisher Date 2011-01-01