Image-based animation of facial expressions

We present a novel technique for creating realistic facial animations given a small number of real images and a few parameters for the in-between images. This scheme can also be used for reconstructing facial movies where the parameters can be automatically extracted from the images. The in-between images are produced without ever generating a three-dimensional model of the face. Since facial motion due to expressions are not well defined mathematically our approach is based on utilizing image patterns in facial motion. These patterns were revealed by an empirical study which analyzed and compared image motion patterns in facial expressions. The major contribution of this work is showing how parameterized “ideal” motion templates can generate facial movies for different people and different expressions, where the parameters are extracted automatically from the image sequence. To test the quality of the algorithm, image sequences (one of which was taken from a TV news broadcast) were reconstructed, yielding movies hardly distinguishable from the originals. Published online: 2 October 2002 Correspondence to: A. Tal Work has been supported in part by the Israeli Ministry of Industry and Trade, The MOST Consortium     

Sequencing counts: A combined approach for sequencing and selecting costly unreliable off-line inspections

We study the case of “inspect-all” policy, using off-line quality inspections to prevent non-conforming items from reaching the final consumer, in domains where an item is rejected upon first “failure” classification. Given a set of inspections with known inspection costs and error probabilities of two types (classifying conforming items as non-conforming and vice versa), the goal is to find a sequenced subset of inspections that maximizes the expected overall profit, taking into account the revenue from delivering conforming items, the penalty of delivering non-conforming ones, and the overall cost of the inspections used. Our model allows an additional degree of freedom, in comparison to prior work in this domain, enabling the selection of inspections sequence along the selection of which inspections to use. We present an efficient branch and bound algorithm for finding the optimal solution, and two types of heuristics: greedy-based and preliminary sort-based, differing in their accuracy and calculation time. The optimal and heuristic methods are extensively evaluated, using a factorial experimental design that includes 65 610 problem instances. For each instance we compared the methods performance in terms of reaching optimality, deviation from the optimal solution and calculation-time. The results reflect a substantial influence of the sequence over the expected profit. An interesting finding is that the suggested preliminary sort-based heuristics achieve a relatively accurate solution in a reasonable calculation-time and outperform the commonly used greedy-based heuristics. The usefulness of the different methods is illustrated using sample problems from the biometric inspection security domain.     

Two-machine flow-shop scheduling with rejection

We study a scheduling problem with rejection on a set of two machines in a flow-shop scheduling system. We evaluate the quality of a solution by two criteria: the first is the makespan and the second is the total rejection cost. We show that the problem of minimizing the makespan plus total rejection cost is NP-hard and for its solution we provide two different approximation algorithms, a pseudo-polynomial time optimization algorithm and a fully polynomial time approximation scheme (FPTAS). We also study the problem of finding the entire set of Pareto-optimal points (this problem is NP-hard due to the NP-hardness of the same problem variation on a single machine [20]). We show that this problem can be solved in pseudo-polynomial time. Moreover, we show how we can provide an FPTAS that, given that there exists a Pareto optimal schedule with a total rejection cost of at most R and a makespan of at most K, finds a solution with a total rejection cost of at most (1+?)R and a makespan value of at most (1+?)K. This is done by defining a set of auxiliary problems and providing an FPTAS algorithm to each one of them.     

Generalizing Inverse Compositional and ESM Image Alignment

Inverse compositional (IC) image alignment (Baker and Matthews in Int. J. Comput. Vis. 56(3):221–255, 2004) uses the symmetry between the roles of the fixed and moving images for faster processing. However, it requires implementation of compositional optimizer update steps. The IC approach can be viewed as an efficient way of computing the similarity measure derivative relative to the fixed image warp parameters. Since the mapping between the fixed and moving warp parameters is continuous and differentiable, this derivative can be converted into the moving warp space using the chain rule. This avoids the need for compositional update steps. Our generalization also allows the efficient second order method (ESM) (Malis in Proceedings of the 2004 IEEE International Conference on Robotics and Automation (ICRA04), pp. 1843–1848, 2004; Benhimane and Malis in IEEE/RSJ International Conference on Intelligent Robots and Systems, 2004; Malis and Benhimane in Robot. Auton. Syst. 52(1):39–52, 2005) to be applied to general parameterizations of the transformation. Experiments using multiple similarity measures and optimizers show that our generalized IC method equals or exceeds the performance of the original IC approach. The generalized ESM approach is more reliable than the classic approach as it increases the capture radius of the optimization.     

Scheduling unit length jobs on parallel machines with lookahead information

This paper studies two closely related online-list scheduling problems of a set of n jobs with unit processing times on a set of m multipurpose machines. It is assumed that there are k different job types, where each job type can be processed on a unique subset of machines. In the classical definition of online-list scheduling, the scheduler has all the information about the next job to be scheduled in the list while there is uncertainty about all the other jobs in the list not yet scheduled. We extend this classical definition to include lookahead abilities, i.e., at each decision point, in addition to the information about the next job in the list, the scheduler has all the information about the next h jobs beyond the current one in the list. We show that for the problem of minimizing the makespan there exists an optimal (1-competitive) algorithm for the online problem when there are two job types. That is, the online algorithm gives the same minimal makespan as the optimal offline algorithm for any instance of the problem. Furthermore, we show that for more than two job types no such online algorithm exists. We also develop several dynamic programming algorithms to solve a stochastic version of the problem, where the probability distribution of the job types is known and the objective is to minimize the expected makespan.     

Private multiparty sampling and approximation of vector combinations

We consider the problem of private efficient data mining of vertically-partitioned databases. Each of several parties holds a column of a data matrix (a vector) and the parties want to investigate the componentwise combination of their vectors. The parties want to minimize communication and local computation while guaranteeing privacy in the sense that no party learns more than necessary. Sublinear-communication private protocols have primarily been studied only in the two-party case. In contrast, this work focuses on multi-party settings.     

Validation of tri-axial accelerometer for the calculation of elevation angles

One of the main issues in occupational studies focusing on musculoskeletal disorders of the upper extremity is how to best quantify workers' exposures to risk factors during a workday. Direct measurement is preferred because it is objective and provides precise measurements. To measure elevation angle exposure of the upper extremity, accelerometers are commonly used. The main problem with the use of accelerometers is the fact that they are sensitive to linear acceleration and can only assess two axes of rotation. In the present study the Virtual Corset, a pager-sized, battery powered, tri-axial linear accelerometer with an integrated data logger, was validated in vitro for the reconstruction of elevation angles under static conditions and angle error prediction under dynamic conditions. For static conditions, the RMS angle error was less than 1°. Under dynamic conditions the elevation angle error was influenced by the radius and angular acceleration. However, the angle error was predicted well with an RMS difference of 3°. It was concluded that the Virtual Corset can be used to accurately predict arm elevation angles under static conditions. Under dynamic conditions, an understanding of the motion being studied and the placement of the Virtual Corset relative to the joint are necessary.

Relevance to industry

A device is tested that could capture posture exposure of the shoulder at the workplace during a workday. Such exposure measurement can be used to test interventions and to develop preventive guidelines to reduce risk factors associated with musculoskeletal injuries of the upper extremity.     

Mesh Segmentation Refinement

This paper proposes a method for refining existing mesh segmentations, employing a novel extension of the active contour approach to meshes. Given a segmentation, produced either by an automatic segmentation method or interactively, our algorithm propagates the segment boundaries to more appropriate locations. In addition, unlike most segmentation algorithms, our method allows the boundaries to pass through the mesh faces, resulting in smoother curves, particularly visible on coarse meshes. The method is also capable of changing the number of segments, by enabling splitting and merging of boundary curves during the process. Finally, by changing the propagation rules, it is possible to segment the mesh by a variety of criteria, for instance geometric‐meaningful segmentations, texture‐based segmentations, or constriction‐based segmentations.     

Multi-level graph layout on the GPU

This paper presents a new algorithm for force directed graph layout on the GPU. The algorithm, whose goal is to compute layouts accurately and quickly, has two contributions. The first contribution is proposing a general multi-level scheme, which is based on spectral partitioning. The second contribution is computing the layout on the GPU. Since the GPU requires a data parallel programming model, the challenge is devising a mapping of a naturally unstructured graph into a well-partitioned structured one. This is done by computing a balanced partitioning of a general graph. This algorithm provides a general multi-level scheme, which has the potential to be used not only for computation on the GPU, but also on emerging multi-core architectures. The algorithm manages to compute high quality layouts of large graphs in a fraction of the time required by existing algorithms of similar quality. An application for visualization of the topologies of ISP (Internet Service Provider) networks is presented.