Theses and Dissertations from UMD

Permanent URI for this communityhttp://hdl.handle.net/1903/2

New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM

More information is available at Theses and Dissertations at University of Maryland Libraries.

Browse

Filters

2006 - 200912010 - 20121

Settings

Subject: search.filters.subject.matroid

Search Results

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Discrete Optimization Methods for Segmentation and Matching
    (2012) Liu, Ming-Yu; Chellappa, Rama; Electrical Engineering; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This dissertation studies discrete optimization methods for several computer vision problems. In the first part, a new objective function for superpixel segmentation is proposed. This objective function consists of two components: entropy rate of a random walk on a graph and a balancing term. The entropy rate favors formation of compact and homogeneous clusters, while the balancing function encourages clusters with similar sizes. I present a new graph construction for images and show that this construction induces a matroid. The segmentation is then given by the graph topology which maximizes the objective function under the matroid constraint. By exploiting submodular and monotonic properties of the objective function, I develop an efficient algorithm with a worst-case performance bound of $\frac{1}{2}$ for the superpixel segmentation problem. Extensive experiments on the Berkeley segmentation benchmark show the proposed algorithm outperforms the state of the art in all the standard evaluation metrics. Next, I propose a video segmentation algorithm by maximizing a submodular objective function subject to a matroid constraint. This function is similar to the standard energy function in computer vision with unary terms, pairwise terms from the Potts model, and a novel higher-order term based on appearance histograms. I show that the standard Potts model prior, which becomes non-submodular for multi-label problems, still induces a submodular function in a maximization framework. A new higher-order prior further enforces consistency in the appearance histograms both spatially and temporally across the video. The matroid constraint leads to a simple algorithm with a performance bound of $\frac{1}{2}$. A branch and bound procedure is also presented to improve the solution computed by the algorithm. The last part of the dissertation studies the object localization problem in images given a single hand-drawn example or a gallery of shapes as the object model. Although many shape matching algorithms have been proposed for the problem, chamfer matching remains to be the preferred method when speed and robustness are considered. In this dissertation, I significantly improve the accuracy of chamfer matching while reducing the computational time from linear to sublinear (shown empirically). It is achieved by incorporating edge orientation information in the matching algorithm so the resulting cost function is piecewise smooth and the cost variation is tightly bounded. Moreover, I present a sublinear time algorithm for exact computation of the directional chamfer matching score using techniques from 3D distance transforms and directional integral images. In addition, the smooth cost function allows one to bound the cost distribution of large neighborhoods and skip the bad hypotheses. Experiments show that the proposed approach improves the speed of the original chamfer matching up to an order of 45 times, and it is much faster than many state of art techniques while the accuracy is comparable. I further demonstrate the application of the proposed algorithm in providing seamless operation for a robotic bin picking system.
  • Thumbnail Image
    Item
    Matroids and Geometric Invariant Theory of torus actions on flag spaces
    (2006-04-06) Howard, Benjamin James; Millson, John J; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)
    This thesis investigates the structure of the projective coordinate rings of SL(n,C) weight varieties. An SL(n,C) weight variety is a Geometric Invariant Theory quotient of the space of full flags by the maximal torus in SL(n,C). Special cases include configurations of n-tuples of points in projective space modulo automorphisms of projective space. There are three main results. The first is an explicit finite set of generators for the coordinate ring. The second is that the lowest degree elements of the coordinate ring provide a well-defined map from the weight variety to projective space. The third theorem is an explicit presentation for the ring of projective invariants of n ordered points on the Riemann sphere, in the case that each point is weighted by an even integer. The methods applied involve matroid theory and degenerations of the weight varieties to toric varieties attached to Gelfand Tsetlin polytopes.