Well-balanced orientations of mixed graphs

We show that deciding if a mixed graph has a well-balanced orientation is NP-complete.     

Procedural Tree Modeling with Guiding Vectors

We propose guiding vectors to augment graph‐based tree synthesis, in which trees are collections of least‐cost paths in a graph. Each node has an associated guiding vector; edges parallel to the guiding vector are cheap, but edges are more expensive when their orientation differs from the guiding vector. We further propose an incremental method for assigning guiding vectors over the graph, in which a node's guiding vector is an incremental rotation of that of its parent. We present a complete procedural system for tree modeling; our use of guiding vectors enables the graph‐based method to produce high‐quality tree models resembling a variety of real‐world tree species.     

Acyclic orientation graph coloring for software-managed memory allocation

This paper presents a novel compiler algorithm,called acyclic orientation graph coloring(AOG coloring),for managing data objects in software-managed memory allocation.The key insight is that softwaremanaged memory allocation could be solved as an interval coloring problem,or equivalently,an acyclic orientation problem.We generalize graph coloring register allocation to interval coloring memory allocation by maintaining an acyclic orientation to the currently colored subgraph.This is achieved with some well-crafted heuristics,including Aggressive Simplify that does not necessarily preserve colorability and Best-Fit Select that assigns intervals(i.e.,colors)to nodes by possibly adjusting the colors already assigned to other nodes earlier.Our algorithm generalizes and subsumes as a special case the classical graph coloring register allocation algorithm without notably increased complexity:it deals with memory allocation while preserving the elegance and practicality of traditional graph coloring register allocation.We have implemented our algorithm and tested it on Appel’s 27921 interference graphs for scalars(augmented with node weights).Our algorithm outperforms Memory Coloring,the best in the literature,for software-managed memory allocation,on 98.64%graphs,in which,the gaps are more than 20%on 68.31%graphs and worse only on 0.29%graphs.We also tested it on all the 73 DIMACS weighted benchmarks(weighted graphs),AOG Coloring outperforms Memory Coloring on all of the benchmarks,in which,the gaps are more than 20%on 83.56%graphs.     

一种基于人员定位的矿井综合通信系统

针对目前矿井井下通信系统功能不完善,技术与实现复杂的现状,提出了一种基于井下人员定位的综合通信监控系统。详细介绍了定位原理与具体实现过程,给出了系统中关键设备基站（BS）与人载通信器的结构原理图,并对综合通信与监控功能的实现进行了分析,最后给出了CMC管理软件的系统功能框图。     

Parallel Globally Consistent Normal Orientation of Raw Unorganized Point Clouds

A mandatory component for many point set algorithms is the availability of consistently oriented vertex‐normals (e.g. for surface reconstruction, feature detection, visualization). Previous orientation methods on meshes or raw point clouds do not consider a global context, are often based on unrealistic assumptions, or have extremely long computation times, making them unusable on real‐world data. We present a novel massively parallelized method to compute globally consistent oriented point normals for raw and unsorted point clouds. Built on the idea of graph‐based energy optimization, we create a complete kNN‐graph over the entire point cloud. A new weighted similarity criterion encodes the graph‐energy. To orient normals in a globally consistent way we perform a highly parallel greedy edge collapse, which merges similar parts of the graph and orients them consistently. We compare our method to current state‐of‐the‐art approaches and achieve speedups of up to two orders of magnitude. The achieved quality of normal orientation is on par or better than existing solutions, especially for real‐world noisy 3D scanned data.     

Logo localization and recognition in natural images using homographic class graphs

We propose a method for localization and classification of brand logos in natural images. The system has to overcome multiple challenges such as perspective deformations, warping, variations of the shape and colors, occlusions, background variations. To deal with perspective variation, we rely on homography matching between the SIFT keypoints of logo instances of the same class. To address the changes in color, we construct a weighted graph of logo interconnections that is further analyzed to extract potentially multiple instances of the class. The main instance is built by grouping the keypoints of the graph connected logos onto the central image. The secondary instance is needed for color inverted logos and is obtained by inverting the orientation of the main instance. The constructed logo recognition system is tested on two databases (FlickrLogos-32 and BelgaLogos), outperforming state of the art with more than 10 % accuracy.     

Visibility-driven mesh analysis and visualization through graph cuts

In this paper we present an algorithm that operates on a triangular mesh and classifies each face of a triangle as either inside or outside. We present three example applications of this core algorithm: normal orientation, inside removal, and layer-based visualization. The distinguishing feature of our algorithm is its robustness even if a difficult input model that includes holes, coplanar triangles, intersecting triangles, and lost connectivity is given. Our algorithm works with the original triangles of the input model and uses sampling to construct a visibility graph that is then segmented using graph cut.     

On deriving explicit formulas of the surface areas for the arrangement graphs and some of the related graphs

We derive an explicit formula for the surface area of the arrangement graph, i.e. the number of vertices at a certain distance from the identity vertex in such a graph. We also present such formulas for the star graph, the alternating group graph, and the split-star graph, via their respective structural relationship to the arrangement graph.     

A Direct Manipulation Interface for 3D Computer Animation

We present a new set of interface techniques for visualizing and editing animation directly in a single three-dimensional scene. Motion is edited using direct-manipulation tools which satisfy high-level goals such as “reach this point at this time” or “go faster at this moment”. These tools can be applied over an arbitrary temporal range and maintain arbitrary degrees of spatial and temporal continuity. We separate spatial and temporal control of position by using two curves for each animated object: the motion path which describes the 3D spatial path along which an object travels, and the motion graph, a function describing the distance traveled along this curve over time. Our direct-manipulation tools are implemented using displacement functions, a straightforward and scalable technique for satisfying motion constraints by composition of the displacement function with the motion graph or motion path. This paper will focus on applying displacement functions to positional change. However, the techniques presented are applicable to the animation of orientation, color, or any other attribute that varies over time.     

Stereo correspondence through feature grouping and maximal cliques

The authors propose a method for solving the stereo correspondence problem. The method consists of extracting local image structures and matching similar such structures between two images. Linear edge segments are extracted from both the left and right images. Each segment is characterized by its position and orientation in the image as well as its relationships with the nearby segments. A relational graph is thus built from each image. For each segment in one image as set of potential assignments is represented as a set of nodes in a correspondence graph. Arcs in the graph represent compatible assignments established on the basis of segment relationships. Stereo matching becomes equivalent to searching for sets of mutually compatible nodes in this graph. Sets are found by looking for maximal cliques. The maximal clique best suited to represent a stereo correspondence is selected using a benefit function. Numerous results obtained with this method are shown     

What energy functions can be minimized via graph cuts?

In the last few years, several new algorithms based on graph cuts have been developed to solve energy minimization problems in computer vision. Each of these techniques constructs a graph such that the minimum cut on the graph also minimizes the energy. Yet, because these graph constructions are complex and highly specific to a particular energy function, graph cuts have seen limited application to date. In this paper, we give a characterization of the energy functions that can be minimized by graph cuts. Our results are restricted to functions of binary variables. However, our work generalizes many previous constructions and is easily applicable to vision problems that involve large numbers of labels, such as stereo, motion, image restoration, and scene reconstruction. We give a precise characterization of what energy functions can be minimized using graph cuts, among the energy functions that can be written as a sum of terms containing three or fewer binary variables. We also provide a general-purpose construction to minimize such an energy function. Finally, we give a necessary condition for any energy function of binary variables to be minimized by graph cuts. Researchers who are considering the use of graph cuts to optimize a particular energy function can use our results to determine if this is possible and then follow our construction to create the appropriate graph. A software implementation is freely available.     

A generative sketch model for human hair analysis and synthesis

In this paper, we present a generative sketch model for human hair analysis and synthesis. We treat hair images as 2D piecewise smooth vector (flow) fields and, thus, our representation is view-based in contrast to the physically-based 3D hair models in graphics. The generative model has three levels. The bottom level is the high-frequency band of the hair image. The middle level is a piecewise smooth vector field for the hair orientation, gradient strength, and growth directions. The top level is an attribute sketch graph for representing the discontinuities in the vector field. A sketch graph typically has a number of sketch curves which are divided into 11 types of directed primitives. Each primitive is a small window (say 5 /spl times/ 7 pixels) where the orientations and growth directions are defined in parametric forms, for example, hair boundaries, occluding lines between hair strands, dividing lines on top of the hair, etc. In addition to the three level representation, we model the shading effects, i.e., the low-frequency band of the hair image, by a linear superposition of some Gaussian image bases and we encode the hair color by a color map. The inference algorithm is divided into two stages: 1) We compute the undirected orientation field and sketch graph from an input image and 2) we compute the hair growth direction for the sketch curves and the orientation field using a Swendsen-Wang cut algorithm. Both steps maximize a joint Bayesian posterior probability. The generative model provides a straightforward way for synthesizing realistic hair images and stylistic drawings (rendering) from a sketch graph and a few Gaussian bases. The latter can be either inferred from a real hair image or input (edited) manually using a simple sketching interface. We test our algorithm on a large data set of hair images with diverse hair styles. Analysis, synthesis, and rendering results are reported in the experiments.     

Creating MPU implicit surfaces from unoriented point sets with orientation inference

In this paper, we extend the MPU implicits algorithm to deal with unoriented point sets while preserving its desirable properties, such as sharp feature preservation. An orientation inference algorithm is introduced to orientate the local implicit patches by solving a graph labeling problem through energy minimization. Sign consistency between local functions is exploited to infer the globally consistent orientation. To precisely model the features, we employ the affinity propagation clustering algorithm to identify the local surface patches composing the features by considering orientation consistency between data points. Sharp features can then be accurately reconstructed by performing piecewise smooth surface fitting. Experimental results are shown to demonstrate the performance of the proposed algorithm.     

Anonymizing bipartite graph data using safe groupings

Private data often come in the form of associations between entities, such as customers and products bought from a pharmacy, which are naturally represented in the form of a large, sparse bipartite graph. As with tabular data, it is desirable to be able to publish anonymized versions of such data, to allow others to perform ad hoc analysis of aggregate graph properties. However, existing tabular anonymization techniques do not give useful or meaningful results when applied to graphs: small changes or masking of the edge structure can radically change aggregate graph properties. We introduce a new family of anonymizations for bipartite graph data, called (k, ℓ)-groupings. These groupings preserve the underlying graph structure perfectly, and instead anonymize the mapping from entities to nodes of the graph. We identify a class of “safe” (k, ℓ)-groupings that have provable guarantees to resist a variety of attacks, and show how to find such safe groupings. We perform experiments on real bipartite graph data to study the utility of the anonymized version, and the impact of publishing alternate groupings of the same graph data. Our experiments demonstrate that (k, ℓ)-groupings offer strong tradeoffs between privacy and utility.     

Generalizing Swendsen-Wang to sampling arbitrary posterior probabilities

Many vision tasks can be formulated as graph partition problems that minimize energy functions. For such problems, the Gibbs sampler provides a general solution but is very slow, while other methods, such as Ncut and graph cuts are computationally effective but only work for specific energy forms and are not generally applicable. In this paper, we present a new inference algorithm that generalizes the Swendsen-Wang method to arbitrary probabilities defined on graph partitions. We begin by computing graph edge weights, based on local image features. Then, the algorithm iterates two steps: (1) graph clustering - it forms connected components by cutting the edges probabilistically based on their weights; (2) graph relabeling - it selects one connected component and flips probabilistically, the coloring of all vertices in the component simultaneously. Thus, it realizes the split, merge, and regrouping of a "chunk" of the graph, in contrast to Gibbs sampler that flips a single vertex. We prove that this algorithm simulates ergodic and reversible Markov chain jumps in the space of graph partitions and is applicable to arbitrary posterior probabilities or energy functions defined on graphs. We demonstrate the algorithm on two typical problems in computer vision-image segmentation and stereo vision. Experimentally, we show that it is 100-400 times faster in CPU time than the classical Gibbs sampler and 20-40 times faster then the DDMCMC segmentation algorithm. For stereo, we compare performance with graph cuts and belief propagation. We also show that our algorithm can automatically infer generative models and obtain satisfactory results (better than the graphic cuts or belief propagation) in the same amount of time.     

Landmark Selection for Vision-Based Navigation

Recent work in the object recognition community has yielded a class of interest-point-based features that are stable under significant changes in scale, viewpoint, and illumination, making them ideally suited to landmark-based navigation. Although many such features may be visible in a given view of the robot's environment, only a few such features are necessary to estimate the robot's position and orientation. In this paper, we address the problem of automatically selecting, from the entire set of features visible in the robot's environment, the minimum (optimal) set by which the robot can navigate its environment. Specifically, we decompose the world into a small number of maximally sized regions, such that at each position in a given region, the same small set of features is visible. We introduce a novel graph theoretic formulation of the problem, and prove that it is NP-complete. Next, we introduce a number of approximation algorithms and evaluate them on both synthetic and real data. Finally, we use the decompositions from the real image data to measure the localization performance versus the undecomposed map.     

Towards Globally Optimal Normal Orientations for Large Point Clouds

Various processing algorithms on point set surfaces rely on consistently oriented normals (e.g. Poisson surface reconstruction). While several approaches exist for the calculation of normal directions, in most cases, their orientation has to be determined in a subsequent step. This paper generalizes propagation‐based approaches by reformulating the task as a graph‐based energy minimization problem. By applying global solvers, we can achieve more consistent orientations than simple greedy optimizations. Furthermore, we present a streaming‐based framework for orienting large point clouds. This framework orients patches locally and generates a globally consistent patch orientation on a reduced neighbour graph, which achieves similar quality to orienting the full graph.     

The strong network orientation problem

This study presents models and heuristics for solving the strong network orientation problem (SNOP), which can model several tactical optimization problems of setting directions in urban networks. The objective is to set an orientation for each edge in an undirected graph such that the resulting digraph is strongly connected and the total travel distance between any pair of nodes is minimized (or maximized). Investigating tactical optimization problems such as SNOP is motivated by several challenges in urban networks due to the growth of population in urban areas, large number of daily trips, increasing price of maintaining urban networks, and the need to reduce air pollution and passive noise. Thus, a new trend is to utilize the urban networks better. In this context, we first use a multicommodity flow formulation to model the minimization problem. The maximization version is modeled by using the dual formulation of the shortest path problem. Then, scalable heuristic strategies for solving SNOP are investigated. For such purpose, we first propose basic components such as constructive heuristics, perturbations and local searches. They are combined into several metaheuristics based on local searches, multi-start and evolutionary schemes, i.e. Multistart Local Search, Iterated Local Search (ILS), Relaxed ILS, Evolutionary Local Search (ELS), Relaxed ELS, and Variable Neighborhood Search. Computational experiments have been performed to analyze the proposed methods in terms of efficiency and quality of solutions, using grid instances and a graph from downtown Clermont-Ferrand in France.     

Algorithms for P<Subscript>4</Subscript>-Comparability Graph Recognition and Acyclic P<Subscript>4</Subscript>-Transitive Orientation

We consider two problems pertaining to P₄-comparability graphs, namely, the problem of recognizing whether a simple undirected graph is a P₄-comparability graph and the problem of producing an acyclic P₄-transitive orientation of a P₄-comparability graph. These problems have been considered by Hoàng and Reed who described O(n⁴)- and O(n⁵)-time algorithms for their solution, respectively, where n is the number of vertices of the input graph. Faster algorithms have recently been presented by Raschle and Simon, and by Nikolopoulos and Palios; the time complexity of these algorithms for either problem is O(n + m²), where m is the number of edges of the graph. In this paper we describe O(n m)-time and O(n + m)-space algorithms for the recognition and the acyclic P₄-transitive orientation problems on P₄-comparability graphs. The algorithms rely on properties of the P₄-components of a graph, which we establish, and on the efficient construction of the P₄-components by means of the BFS-trees of the complement of the graph rooted at each of its vertices, without however explicitly computing the complement. Both algorithms are simple and use simple data structures.