Higher Order MRF-MAP formulation has been a popular technique for solving many problems in computer vision. Inference in a general MRF-MAP problem is NP Hard, but can be performed in polynomial time for the special case when potential functions are submodular. Two popular combinatorial approaches for solving such formulations are flow based and polyhedral approaches. Flow based approaches work well with small cliques and in that mode can handle problems with millions of variables. Polyhedral approaches can handle large cliques but in small numbers. We show in this paper that the variables in these seemingly disparate techniques can be mapped to each other. This allows us to combine the two styles in a joint framework exploiting the strength of both of them. Using the proposed joint framework, we are able to perform tractable inference in MRF-MAP problems with millions of variables and a mix of small and large cliques, a formulation which can not be solved by either of the two styles individually. We show applicability of this hybrid framework on object segmentation problem as an example of a situation where quality of results is significantly better than systems which are based only on the use of small or large cliques.

Use of higher order clique potentials in MRF-MAP problems has been limited primarily because of the inefficiencies of the existing algorithmic schemes. We propose a new combinatorial algorithm for computing optimal solutions to 2 label MRF-MAP problems with higher order clique potentials. The algorithm runs in time O(2(k)n(3)) in the worst case (k is size of clique and n is the number of pixels). A special gadget is introduced to model flows in a higher order clique and a technique for building a flow graph is specified. Based on the primal dual structure of the optimization problem, the notions of the capacity of an edge and a cut are generalized to define a flow problem. We show that in this flow graph, when the clique potentials are submodular, the max flow is equal to the min cut, which also is the optimal solution to the problem. We show experimentally that our algorithm provides significantly better solutions in practice and is hundreds of times faster than solution schemes like Dual Decomposition [1], TRWS [2] and Reduction [3], [4], [5]. The framework represents a significant advance in handling higher order problems making optimal inference practical for medium sized cliques.

Use of higher order clique potentials for modeling inference problems has exploded in last few years. The algorithmic schemes proposed so far do not scale well with increasing clique size, thus limiting their use to cliques of size at most 4 in practice. Generic Cuts (GC) of Arora et al. [9] shows that when potentials are submodular, inference problems can be solved optimally in polynomial time for fixed size cliques. In this paper we report an algorithm called Approximate Cuts (AC) which uses a generalization of the gadget of GC and provides an approximate solution to inference in 2-label MRF-MAP problems with cliques of size k ≥ 2. The algorithm gives optimal solution for submodular potentials. When potentials are non-submodular, we show that important properties such as weak persistency hold for solution inferred by AC. AC is a polynomial time primal dual approximation algorithm for fixed clique size. We show experimentally that AC not only provides significantly better solutions in practice, it is an order of magnitude faster than message passing schemes like Dual Decomposition [19] and GTRWS [17] or Reduction based techniques like [10, 13, 14].

We propose an algorithm called Multi Label Generic Cuts (MLGC) for computing optimal solutions to MRF-MAP problems with submodular multi label multi-clique potentials. A transformation is introduced to convert a m-label k-clique problem to an equivalent 2-label (mk)-clique problem. We show that if the original multi-label problem is submodular then the transformed 2-label multi-clique problem is also submodular. We exploit sparseness in the feasible configurations of the transformed 2-label problem to suggest an improvement to Generic Cuts [3] to solve the 2-label problems efficiently. The algorithm runs in time O(mk n3) in the worst case (n is the number of pixels) generalizing O(2k n3) running time of Generic Cuts. We show experimentally that MLGC is an order of magnitude faster than the current state of the art [17, 20]. While the result of MLGC is optimal for submodular clique potential it is significantly better than the compared methods even for problems with non-submodular clique potential.

In this paper, we present, formalize and prove the correctness of recovery algorithm for our open and safe nested transaction model using I/O automaton model. Our nested transaction model uses the notion of a recovery point subtransaction in the nested transaction tree. It introduces a prewrite operation before each write operation to increase the potential concurrency. Our transaction model is termed as "open and safe" as prewrites allow early reads (before database writes on disk) without cascading aborts. The systems restart and buffer management operations are modelled as nested transactions to exploit possible concurrency during restart. Each non-access transaction, object, and the scheduler is modeled as I/O automaton. Each of these automata is specified with the help of some pre-and post-conditions. These pre-and post-conditions capture the operational semantics and the behavior of each automaton during recovery operations. Our proof technique makes use of assertional reasoning and provide many interesting invariant, thus gives a better understanding of our recovery algorithm.

This paper describes an output-sensitive scheme to construct the visibility graph of a simple polygon with m obstacles and n vertices in optimal O(|E| +T + m log n ) time where |E| is the size of the visibility graph and T is the time required to triangulate the simple polygon with obstacles. We use a partition of the space into regions called corridors which eases the efforts of the construction. Our algorithms are simple and the data structures used are only linked lists.

The expressibility of bounded-arity query hierarchies resulting from the extension of first-order logic by the least fixed-point, inductive fixed-point and generalized fixed-point operators is studied. In each case, it is shown that increasing the arity of the predicate variable from k to k+1 always allows some more k-ary predicates to be expressed. Further, k-ary inductive fixed-points are shown to be more expressive than k-ary least fixed-points and k-ary generalized fixed-points are shown to be more expressive than k-ary inductive fixed-points.

The class of preflow push algorithms recently introduced by Goldberg and Tarjan for solving the maximum flow problem on a weighted digraph with n vertices and m edges is studied. Goldberg and Tarjan’s $O(n^3 )$ time bound for the highest distance preflow push algorithm is improved to $O(n^2 \sqrt m )$, and it is shown that this bound is tight by constructing a parametrized worst-case network. It is also shown that the $O(n^3 )$ time bound is tight for the FIFO preflow push algorithm, and the $O(n^2 m)$ time bound is tight for the LIFO preflow push algorithm. The maximal excess preflow push algorithm is then developed, and it is shown that it performs $O(n^2 \sqrt m )$ pushes and that this bound is tight. Based on this, the authors develop a maximum flow algorithm for the synchronous distributed model of computation that uses $O(n^2 \sqrt m )$ messages and $O(n^2 )$ time, thereby improving upon the best previously known algorithms for this model.

The problem of determining the Euclidean shortest path between two points in the presence of m simple polygonal obstacles is studied. An O( m2 logn + nlogn ) algorithm is developed, where n is the total number of points in the obstacles. A simple O(E+T) algorithm for determining the visibility graph is also shown, where E is the number of visibility edges and T is the time for triangulating the point set. This is extended to a O(Es + nlogn) algorithm for the shortest path problem where Es is bounded by m2.

In this paper we describe two interconnection networks for parallel processing, namely the orthogonal trees network and the orthogonal tree cycles (OTN and OTC). Both networks are suitable for VISI implementation and have been analyzed using Thompson's model of VLSI. While the OTN and OTC have time performances similar to fast networks such as the perfect shuffle network (PSN), the cube comnected cycles (CCC), etc., they have substantially better area * time2 performances for a number of matrix and graph problems. For instance, the connected components and a minimal spanning tree of an undirected N-vertex graph can be found in 0(log4 N) time on the OTC with an area * time2 performance of 0(N2 log8 N) and 0(N2 log9 N) respectively. This is asymptoticaly much better than the performances of the CCC, PSN and Mesh. The OTC and OTN can be looked upon as general purpose parallel processors since a number of other problems such as sorting and DFT can be solved on them with an area * time2 performance matching that of other networks. Finally, programming the OTN and OTC is simple and they are also amenable to pipelining a series of problems.