As‐Killing‐As‐Possible Vector Fields for Planar Deformation

Cartoon animation, image warping, and several other tasks in two‐dimensional computer graphics reduce to the formulation of a reasonable model for planar deformation. A deformation is a map from a given shape to a new one, and its quality is determined by the type of distortion it introduces. In many applications, a desirable map is as isometric as possible. Finding such deformations, however, is a nonlinear problem, and most of the existing solutions approach it by minimizing a nonlinear energy. Such methods are not guaranteed to converge to a global optimum and often suffer from robustness issues. We propose a new approach based on approximate Killing vector fields (AKVFs), first introduced in shape processing. AKVFs generate near‐isometric deformations, which can be motivated as direction fields minimizing an “as‐rigid‐as‐possible” (ARAP) energy to first order. We first solve for an AKVF on the domain given user constraints via a linear optimization problem and then use this AKVF as the initial velocity field of the deformation. In this way, we transfer the inherent nonlinearity of the deformation problem to finding trajectories for each point of the domain having the given initial velocities. We show that a specific class of trajectories — the set of logarithmic spirals — is especially suited for this task both in practice and through its relationship to linear holomorphic vector fields. We demonstrate the effectiveness of our method for planar deformation by comparing it with existing state‐of‐the‐art deformation methods.     

The Virtual Director: a Correlation‐Based Online Viewing of Human Motion

Automatic camera control for scenes depicting human motion is an imperative topic in motion capture base animation, computer games, and other animation based fields. This challenging control problem is complex and combines both geometric constraints, visibility requirements, and aesthetic elements. Therefore, existing optimization‐based approaches for human action overview are often too demanding for online computation. In this paper, we introduce an effective automatic camera control which is extremely efficient and allows online performance. Rather than optimizing a complex quality measurement, at each time it selects one active camera from a multitude of cameras that render the dynamic scene. The selection is based on the correlation between each view stream and the human motion in the scene. Two factors allow for rapid selection among tens of candidate views in real‐time, even for complex multi‐character scenes: the efficient rendering of the multitude of view streams, and optimized calculations of the correlations using modified CCA. In addition to the method's simplicity and speed, it exhibits good agreement with both cinematic idioms and previous human motion camera control work. Our evaluations show that the method is able to cope with the challenges put forth by severe occlusions, multiple characters and complex scenes.     

Multi-Agent Constraint Systems with Preferences: Efficiency, Solution Quality, and Privacy Loss

In this paper, we consider multi-agent constraint systems with preferences, modeled as soft constraint systems in which variables and constraints are distributed among multiple autonomous agents. We assume that each agent can set some preferences over its local data, and we consider two different criteria for finding optimal global solutions: fuzzy and Pareto optimality. We propose a general graph-based framework to describe the problem to be solved in its generic form. As a case study, we consider a distributed meeting scheduling problem where each agent has a pre-existing schedule and the agents must decide on a common meeting that satisfies a given optimality condition. For this scenario we consider the topics of solution quality, search efficiency, and privacy loss, where the latter pertains to information about an agent's pre-existing meetings and available time-slots. We also develop and test strategies that trade efficiency for solution quality and strategies that minimize information exchange, including some that do not require inter-agent comparisons of utilities. Our experimental results demonstrate some of the relations among solution quality, efficiency, and privacy loss, and provide useful hints on how to reach a tradeoff among these three factors. In this work, we show how soft constraint formalisms can be used to incorporate preferences into multi-agent problem solving along with other facets of the problem, such as time and distance constraints. This work also shows that the notion of privacy loss can be made concrete so that it can be treated as a distinct, manipulable factor in the context of distributed decision making.     

Efficient algorithms of video replication and placement on a cluster of streaming servers

A cost-effective approach to building up scalable video streaming servers is to couple a number of streaming servers together in a cluster so as to alleviate the inherent storage and networking constraints of streaming services. In this article, we investigate a crucial problem of video replication and placement on a distributed storage cluster of streaming servers for high quality and high availability services. We formulate it as a combinatorial optimization problem with objectives of maximizing the encoding bit rate and the number of replicas of each video and balancing the workload of the servers. The objectives are subject to the constraints of the storage capacity and the outgoing network-I/O bandwidth of the servers. Under the assumption of single fixed encoding bit rate for all video objects with different popularity values, we give an optimal replication algorithm and a bounded placement algorithm, respectively. We further present an efficient replication algorithm that utilizes the Zipf-like video popularity distributions to approximate the optimal solutions, which can reduce the complexity of the optimal replication algorithm. For video objects with scalable encoding bit rates, we propose a heuristic algorithm based on simulated annealing. We conduct a comprehensive performance evaluation of the algorithms and demonstrate their effectiveness via simulations over a synthetic workload set.     

Camera handoff and placement for automated tracking systems with multiple omnidirectional cameras

In a multi-camera surveillance system, both camera handoff and placement play an important role in generating an automated and persistent object tracking, typical of most surveillance requirements. Camera handoff should comprise three fundamental components, time to trigger handoff process, the execution of consistent labeling, and the selection of the next optimal camera. In this paper, we design an observation measure to quantitatively formulate the effectiveness of object tracking so that we can trigger camera handoff timely and select the next camera appropriately before the tracked object falls out of the field of view (FOV) of the currently observing camera. In the meantime, we present a novel solution to the consistent labeling problem in omnidirectional cameras. A spatial mapping procedure is proposed to consider both the noise inherent to the tracking algorithms used by the system and the lens distortion introduced by omnidirectional cameras. This does not only avoid the tedious process, but also increases the accuracy, to obtain the correspondence between omnidirectional cameras without human interventions. We also propose to use the Wilcoxon Signed-Rank Test to improve the accuracy of trajectory association between pairs of objects. In addition, since we need a certain amount of time to successfully carry out the camera handoff procedure, we introduce an additional constraint to optimally reserve sufficient cameras’ overlapped FOVs for the camera placement. Experiments show that our proposed observation measure can quantitatively formulate the effectiveness of tracking, so that camera handoff can smoothly transfer objects of interest. Meanwhile, our proposed consistent labeling approach can perform as accurately as the geometry-based approach without tedious calibration processes and outperform Calderara’s homography-based approach. Our proposed camera placement method exhibits a significant increase in the camera handoff success rate at the cost of slightly decreased coverage, as compared to Erdem and Sclaroff’s method without considering the requirement on overlapped FOVs.     

Approximation algorithms and heuristics for task scheduling in data‐intensive distributed systems

In this work, we are interested in the problem of task scheduling on large‐scale data‐intensive computing systems. In order to achieve good performance, one must construct not only good task schedules but also good data allocation across nodes on the system, since before a task can be executed, it must have access to data distributed on the system. In this article, we present a general formulation of a static problem that combines both scheduling and replication problems in data‐intensive distributed systems. We show that this problem does not admit an approximation algorithm. However, considering a restricted version of the problem that considers some practical constraints, an approximation algorithm can be designed. From a practical perspective, we introduce a novel heuristic for the problem that is based on nodes clustering. We compare the heuristic with two adapted approaches from other works in the literature by computational simulations using an extensive set of instances based on real computer grids. We show that our heuristic often obtains the best solutions and also runs faster than other approaches.     

A Mixed Closure-CSP Method for Solving Scheduling Problems

Scheduling problems can be viewed as a set of temporal metric and disjunctive constraints and so they can be formulated in terms of CSP techniques. In the literature, there are CSP-based methods which sequentially interleave search efforts with the application of consistency enforcing mechanisms and variable/ordering heuristics. Therefore, the number of backtrackings needed to obtain a solution is reduced. In this paper, we propose a new method that effectively integrates the CSP process into a limited closure process: not by interleaving them but rather as a part of the same process. Such an integration allows us to define more informed heuristics. These heuristics are used to limit the complete closure process to a maximum number of disjunctions, thereby reducing its complexity while at the same time reducing the search space. Some open disjunctive solutions can be maintained in the CSP process, limiting the number of backtrackings necessary, and avoiding having to know all the problem constraints in advance. Our experiments with flow-shop and job-shop instances show that this approach obtains a feasible solution/optimal solution without having to use backtracking in most cases. We also analyze the behaviour of our algorithm when some constraints are known dynamically and we demonstrate that it can provide better results than a pure CSP process.     

Optimal capacity allocation for Web systems with end-to-end delay guarantees

Providing quality of service guarantees have become a critical issue during the rapid expansion of the e-Commerce area. We consider the problem of finding the optimal capacity allocation in a clustered Web system environment so as to minimize the cost while providing the end-to-end performance guarantees. In particular, we consider constraints on both the average and the tail distribution of the end-to-end response times. We formulate the problem as a nonlinear program to minimize a convex separable function of the capacity assignment vector. We show that under the mean response time guarantees alone, the solution has a nice geometric interpretation. Various methods to solve the problem are presented in detail. For the problem with tail distribution guarantees, we develop an approximation method to solve the problem. We also derive bounds and show that the solution is asymptotically optimal when the service requirement becomes stringent. Numerical results are presented to further demonstrate the robustness of our solutions under data uncertainty.     

Consistency techniques for continuous constraints

We consider constraint satisfaction problems with variables in continuous, numerical domains. Contrary to most existing techniques, which focus on computing one single optimal solution, we address the problem of computing a compact representation of the space of all solutions admitted by the constraints. In particular, we show how globally consistent (also called decomposable) labelings of a constraint satisfaction problem can be computed.Our approach is based on approximating regions of feasible solutions by 2 ^k -trees, a representation commonly used in computer vision and image processing. We give simple and stable algorithms for computing labelings with arbitrary degrees of consistency. The algorithms can process constraints and solution spaces of arbitrary complexity, but with a fixed maximal resolution.Previous work has shown that when constraints are convex and binary, path-consistency is sufficient to ensure global consistency. We show that for continuous domains, this result can be generalized to ternary and in fact arbitrary n-ary constraints using the concept of (3,2)-relational consistency. This leads to polynomial-time algorithms for computing globally consistent labelings for a large class of constraint satisfaction problems with continuous variables.     

A branch and price approach for deployment of multi-tier software services in clouds

This paper considers a service deployment problem that combines service placement and replication level decisions in a cloud computing context. The services are composed of multiple components that are to be placed on nodes in the private cloud of the service provider or, if the private cloud has limited capacity, partly in a public cloud. In the service delivery, the provider has to take into account the quality of service guarantees offered to his end-users. To solve the problem, we develop a branch and price algorithm, where the subproblems both are formulated as a linear mixed integer program and a shortest path problem with resource constraints (SPPRC) on a network with a special structure. The SPPRC can be solved by an exact label-setting algorithm, but to speed up the solution process, we develop a heuristic label-setting algorithm based on a reduced network and simplified dominance rule. Our results show that using the heuristic subproblem solver is efficient. Furthermore, the branch and price algorithm performs better than a previously developed pre-generation algorithm for the same problem. In addition, we analyze and discuss the differences in solutions that utilize resources in a public cloud to different degrees. By conducting this analysis we are able to identify some essential characteristics of good solutions.     

An evolutionary approach for configuring economical packet switched computer networks

The topological design of computer networks essentially consists in finding a network topology which minimizes the communication costs, taking into account some constraints such as performance and quality of service. This optimization problem is well known as difficult to solve, such that only heuristic methods are usually recommended and used. These methods are incremental in the sense that they take a starting topology as input solution and perturb it in order to produce a better solution. In this paper, we propose an evolutionary approach, based on the genetic algorithm paradigm, for solving this problem. Simulation results confirm the appropriateness and efficiency of this approach which yields solutions of very good quality for moderate size networks.     

Models for the two‐dimensional rectangular single large placement problem with guillotine cuts and constrained pattern

In this paper, we address the constrained two‐dimensional rectangular guillotine single large placement problem (2D_R_CG_SLOPP). This problem involves cutting a rectangular object to produce smaller rectangular items from orthogonal guillotine cuts. In addition, there is an upper limit on the number of copies that can be produced of each item type. To model this problem, we propose a new pseudopolynomial integer nonlinear programming (INLP) formulation and obtain an equivalent integer linear programming (ILP) formulation from it. Additionally, we developed a procedure to reduce the numbers of variables and constraints of the integer linear programming (ILP) formulation, without loss of optimality. From the ILP formulation, we derive two new pseudopolynomial models for particular cases of the 2D_R_CG_SLOPP, which consider only two‐staged or one‐group patterns. Finally, as a specific solution method for the 2D_R_CG_SLOPP, we apply Benders decomposition to the proposed ILP formulation and develop a branch‐and‐Benders‐cut algorithm. All proposed approaches are evaluated through computational experiments using benchmark instances and compared with other formulations available in the literature. The results show that the new formulations are appropriate in scenarios characterized by few item types that are large with respect to the object's dimensions.     

Using pedestrians walking on uneven terrains for camera calibration

A calibrated camera is essential for computer vision systems: the prime reason being that such a camera acts as an angle measuring device. Once the camera is calibrated, applications like three-dimensional reconstruction or metrology or other applications requiring real world information from the video sequences can be envisioned. Motivated by this, we address the problem of calibrating multiple cameras, with an overlapping field of view observing pedestrians in a scene walking on an uneven terrain. This problem of calibration on an uneven terrain has so far not been addressed in the vision community. We automatically estimate vertical and horizontal vanishing points by observing pedestrians in each camera and use the corresponding vanishing points to estimate the infinite homography existing between the different cameras. This homography provides constraints on intrinsic (or interior) camera parameters while also enabling us to estimate the extrinsic (or exterior) camera parameters. We test the proposed method on real as well as synthetic data, in addition to motion capture dataset and compare our results with the state of the art.     

Visualizing multiple error-sensitivity fields for single camera positioning

In many data acquisition tasks, the placement of a real camera can vary significantly in complexity from one scene to another. Optimal camera positioning should be governed not only by least error sensitivity, but in addition to real-world practicalities given by various physical, financial and other types of constraints. It would be a laborious and costly task to model all these constraints if one were to rely solely on fully automatic algorithms to make the decision. In this work, we present a study using 2D and 3D visualization methods to assist in single camera positioning based on error sensitivity of reconstruction and other physical and financial constraints. We develop a collection of visual mappings that depict the composition of multiple error sensitivity fields that occur for a given camera position. Each camera position is then mapped to a 3D visualization that enables visual assessment of the camera configuration. We find that the combined 2D and 3D visualization effectively aids the estimation of camera placement without the need for extensive manual configuration through trial and error. Importantly, it still provides the user with sufficient flexibility to make dynamic decisions based on physical and financial constraints that can not be encoded easily in an algorithm. We demonstrate the utility of our system on two real-world applications namely snooker analysis and camera surveillance.     

A simulated annealing approach to integrated production scheduling

This paper describes an approach to manufacturing planning that seeks to integrate both process planning and scheduling. We show that separating these two related tasks, as is the common practice, can impose constraints that substantially reduce the quality of the final schedule. These constraints arise from premature decisions regarding operation sequence and allocation of manufacturing resources. Having formulated an integrated process planning and scheduling problem, we describe a solution technique based on simulated annealing. We compare this approach with others reported in the literature, considering both their generality and performance. In particular, we perform a detailed empirical comparison between simulated annealing and the popular technique of dispatching rules. Our results, achieved with two distinct sets of example problems, show that simulated annealing can produce solutions of significantly higher quality than those achieved through a published dispatching rule approach.     

A Bayesian approach to simultaneously recover camera pose and non-rigid shape from monocular images

In this paper we bring the tools of the Simultaneous Localization and Map Building (SLAM) problem from a rigid to a deformable domain and use them to simultaneously recover the 3D shape of non-rigid surfaces and the sequence of poses of a moving camera. Under the assumption that the surface shape may be represented as a weighted sum of deformation modes, we show that the problem of estimating the modal weights along with the camera poses, can be probabilistically formulated as a maximum a posteriori estimate and solved using an iterative least squares optimization. In addition, the probabilistic formulation we propose is very general and allows introducing different constraints without requiring any extra complexity. As a proof of concept, we show that local inextensibility constraints that prevent the surface from stretching can be easily integrated.An extensive evaluation on synthetic and real data, demonstrates that our method has several advantages over current non-rigid shape from motion approaches. In particular, we show that our solution is robust to large amounts of noise and outliers and that it does not need to track points over the whole sequence nor to use an initialization close from the ground truth.     

Hybrid methods for lot sizing on parallel machines

We consider the capacitated lot sizing problem with multiple items, setup time and unrelated parallel machines, and apply Dantzig–Wolfe decomposition to a strong reformulation of the problem. Unlike in the traditional approach where the linking constraints are the capacity constraints, we use the flow constraints, i.e. the demand constraints, as linking constraints. The aim of this approach is to obtain high quality lower bounds. We solve the master problem applying two solution methods that combine Lagrangian relaxation and Dantzig–Wolfe decomposition in a hybrid form. A primal heuristic, based on transfers of production quantities, is used to generate feasible solutions. Computational experiments using data sets from the literature are presented and show that the hybrid methods produce lower bounds of excellent quality and competitive upper bounds, when compared with the bounds produced by other methods from the literature and by a high-performance MIP software.     

Optimum Fiducials Under Weak Perspective Projection

We investigate how a given fixed number of points should be located in space so that the pose of a camera viewing them from unknown locations can be estimated with the greatest accuracy. We show that optimum solutions are obtained when the points form concentric complete regular polyhedra. For the case of optimal configurations we provide a worst-case error analysis and use it to analyze the effects of weak perspective approximation to true perspective viewing. Comprehensive computer simulations validate the theoretical results.     

Stream Surface Parametrization by Flow‐Orthogonal Front Lines

The generation of discrete stream surfaces is an important and challenging task in scientific visualization, which can be considered a particular instance of geometric modeling. The quality of numerically integrated stream surfaces depends on a number of parameters that can be controlled locally, such as time step or distance of adjacent vertices on the front line. In addition there is a parameter that cannot be controlled locally: stream surface meshes tend to show high quality, well‐shaped elements only if the current front line is “globally” approximately perpendicular to the flow direction. We analyze the impact of this geometric property and present a novel solution – a stream surface integrator that forces the front line to be perpendicular to the flow and that generates quad‐dominant meshes with well‐shaped and well‐aligned elements. It is based on the integration of a scaled version of the flow field, and requires repeated minimization of an error functional along the current front line. We show that this leads to computing the 1‐dimensional kernel of a bidiagonal matrix: a linear problem that can be solved efficiently. We compare our method with existing stream surface integrators and apply it to a number of synthetic and real world data sets.