Trajectory data are prevalent in systems that monitor the locations of moving objects. In a location-based service, for instance, the positions of vehicles are continuously monitored through GPS; the trajectory of each vehicle describes its movement history. We study joins on two sets of trajectories, generated by two sets M and R of moving objects. For each entity in M, a join returns its k nearest neighbors from R. We examine how this query can be evaluated in cloud environments. This problem is not trivial, due to the complexity of the trajectory, and the fact that both the spatial and temporal dimensions of the data have to be handled. To facilitate this operation, we propose a parallel solution framework based on MapReduce. We also develop a novel bounding technique, which enables trajectories to be pruned in parallel. Our approach can be used to parallelize existing single-machine trajectory join algorithms. To evaluate the efficiency and the scalability of our solutions, we have performed extensive experiments on a real dataset.

Trajectory data are prevalent in systems that monitor the locations of moving objects. In a location-based service, for instance, the positions of vehicles are continuously monitored through GPS; the trajectory of each vehicle describes its movement history. We study joins on two sets of trajectories, generated by two sets M and R of moving objects. For each entity in M, a join returns its k nearest neighbors from R. We examine how this query can be evaluated in cloud environments. This problem is not trivial, due to the complexity of the trajectory, and the fact that both the spatial and temporal dimensions of the data have to be handled. To facilitate this operation, we propose a parallel solution framework based on MapReduce. We also develop a novel bounding technique, which enables trajectories to be pruned in parallel. Our approach can be used to parallelize existing single-machine trajectory join algorithms. We also study a variant of the join, which can further improve query efficiency. To evaluate the efficiency and the scalability of our solutions, we have performed extensive experiments on large real and synthetic datasets.

In social tagging systems, such as Delicious1and Flickr2, users are allowed to annotate resources (e.g., Web URLs and images) with textual descriptions called tags. Tags have proven to be invaluable building blocks in algorithms for searching, mining and recommending resources. In practice, however, not all resources receive the same attention from users, and as a result, most tags are added to the few highly-popular resources, while most of the resources receive few tags. Crucially, this incomplete tagging on resources can severely affect the effectiveness of all tagging applications. We present iTag, an incentive-based tagging system, which aims at improving tagging quality of resources, by incentivizing taggers under budget constraints. Our system is built upon traditional crowdsourcing systems such as Amazon Mechanical Turk (MTurk). In our demonstration, we will show how our system allows users to use simple but powerful strategies to significantly improve the tagging quality of resources.

Lung motion estimation plays an important role in image-guided radiotherapy. This paper presents an algorithm to estimate lung deformation and motion during respiration using 4D deformable image registration for 4D-CT data. The image intensity of 4D-CT is transformed into vessel feature space, which is used to extract and track bifurcation points of lungs vessel. The spatially mean shift iteration is used to track bifurcation points in all phase images. The initial positions of these bifurcation points in all phase images are provided by the initial transformations between the reference image and all phase images estimated by matching candidate corresponding bifurcation points based on SIFT features. The trajectory of tracked bifurcation points are used to construct lung deformable model by TPS interpolation. We have validated our proposed algorithm on DIR-lab dataset. The results are compared with the results of the previously 4D registration methods, showing improvement of registration error and significant improvement of computation time for 4D deformable image registration.

The robust point matching (RPM) has been applied in image registration. Although the RPM has been extensively used in non-rigid registration of images, it does not solve a consistent correspondence between the two images except at the estimated corresponding points. In this paper, we propose an image registration method based on the consistent robust point matching to solve the forward and reverse transformations between two images. It defines a novel cost function for RPM by introducing the inverse consistency constraint. The fuzzy corresponding relationship between points is estimated based on both the forward and reverse transformations simultaneously. The proposed method also introduces similarity of image content in the procedure of points matching. The performance of our method is demonstrated and validated in synthetic experiments. Moreover, we apply the method to the problem of non-rigid registration of real images and brain images. The results indicate the improvement of the proposed method in the aspect of bi-directional image registration and the decrease of the inverse consistency errors of the forward and the reverse transformations between two images.

In a crowdsourcing system, Human Intelligence Tasks (HITs) (e.g., translating sentences, matching photos, tagging videos with keywords) can be conveniently specified. HITs are made available to a large pool of workers, who are paid upon completing the HITs they have selected. Since workers may have different capabilities, some difficult HITs may not be satisfactorily performed by a single worker. If more workers are employed to perform a HIT, the quality of the HIT's answer could be statistically improved. Given a set of HITs and a fixed "budget", we address the important problem of determining the number of workers (or plurality) of each HIT so that the overall answer quality is optimized. We propose a dynamic programming (DP) algorithm for solving the plurality assignment problem (PAP). We identify two interesting properties, namely, monotonicity and diminishing return, which are satisfied by a HIT if the quality of the HIT's answer increases monotonically at a decreasing rate with its plurality. We show for HITs that satisfy the two properties (e.g., multiple-choice-question HITs), the PAP is approximable. We propose an efficient greedy algorithm for such case. We conduct extensive experiments on synthetic and real datasets to evaluate our algorithms. Our experiments show that our greedy algorithm provides close-to-optimal solutions in practice.

The information managed in emerging applications, such as sensor networks, location-based services, and data integration, is inherently imprecise. To handle data uncertainty, probabilistic databases have been recently developed. In this paper, we study how to quantify the ambiguity of answers returned by a probabilistic top-k query. We develop efficient algorithms to compute the quality of this query under the possible world semantics. We further address the cleaning of a probabilistic database, in order to improve top-k query quality. Cleaning involves the reduction of ambiguity associated with the database entities. For example, the uncertainty of a temperature value acquired from a sensor can be reduced, or cleaned, by requesting its newest value from the sensor. While this “cleaning operation” may produce a better query result, it may involve a cost and fail. We investigate the problem of selecting entities to be cleaned under a limited budget. Particularly, we propose an optimal solution and several heuristics. Experiments show that the greedy algorithm is efficient and close to optimal.

A social tagging system, such as del.icio.us and Flickr, allows users to annotate resources (e.g., web pages and photos) with text descriptions called tags. Tags have proven to be invaluable information for searching, mining, and recommending resources. In practice, however, not all resources receive the same attention from users. As a result, while some highly-popular resources are over-tagged, most of the resources are under-tagged. Incomplete tagging on resources severely affects the effectiveness of all tag-based techniques and applications. We address an interesting question: if users are paid to tag specific resources, how can we allocate incentives to resources in a crowd-sourcing environment so as to maximize the tagging quality of resources? We address this question by observing that the tagging quality of a resource becomes stable after it has been tagged a sufficient number of times. We formalize the concepts of tagging quality (TQ) and tagging stability (TS) in measuring the quality of a resource's tag description. We propose a theoretically optimal algorithm given a fixed “budget” (i.e., the amount of money paid for tagging resources). This solution decides the amount of rewards that should be invested on each resource in order to maximize tagging stability. We further propose a few simple, practical, and efficient incentive allocation strategies. On a dataset from del.icio.us, our best strategy provides resources with a close-to-optimal gain in tagging stability.

While hand-drawn cel animation is a world-wide popular form of art and entertainment, introducing stereoscopic effect into it remains difficult and costly, due to the lack of physical clues. In this paper, we propose a method to synthesize convincing stereoscopic cel animations from ordinary 2D inputs, without labor-intensive manual depth assignment nor 3D geometry reconstruction. It is mainly automatic due to the need of producing lengthy animation sequences, but with the option of allowing users to adjust or constrain all intermediate results. The system fits nicely into the existing production flow of cel animation. By utilizing the T-junction cue available in cartoons, we first infer the initial, but not reliable, ordering of regions. One of our major contributions is to resolve the temporal inconsistency of ordering by formulating it as a graph-cut problem. However, the resultant ordering remains insufficient for generating convincing stereoscopic effect, as ordering cannot be directly used for depth assignment due to its discontinuous nature. We further propose to synthesize the depth through an optimization process with the ordering formulated as constraints. This is our second major contribution. The optimized result is the spatiotemporally smooth depth for synthesizing stereoscopic effect. Our method has been evaluated on a wide range of cel animations and convincing stereoscopic effect is obtained in all cases.

The data handled in emerging applications like location-based services, sensor monitoring systems, and data integration, are often inexact in nature. In this paper, we study the important problem of extracting frequent item sets from a large uncertain database, interpreted under the Possible World Semantics (PWS). This issue is technically challenging, since an uncertain database contains an exponential number of possible worlds. By observing that the mining process can be modeled as a Poisson binomial distribution, we develop an approximate algorithm, which can efficiently and accurately discover frequent item sets in a large uncertain database. We also study the important issue of maintaining the mining result for a database that is evolving (e.g., by inserting a tuple). Specifically, we propose incremental mining algorithms, which enable Probabilistic Frequent Item set (PFI) results to be refreshed. This reduces the need of re-executing the whole mining algorithm on the new database, which is often more expensive and unnecessary. We examine how an existing algorithm that extracts exact item sets, as well as our approximate algorithm, can support incremental mining. All our approaches support both tuple and attribute uncertainty, which are two common uncertain database models. We also perform extensive evaluation on real and synthetic data sets to validate our approaches.

By extending from monocular displays to binocular displays, one additional image domain is introduced. Existing binocular display systems only utilize this additional image domain for stereopsis. Our human vision is not only able to fuse two displaced images, but also two images with difference in detail, contrast and luminance, up to a certain limit. This phenomenon is known as binocular single vision . Humans can perceive more visual content via binocular fusion than just a linear blending of two views. In this paper, we make a first attempt in computer graphics to utilize this human vision phenomenon, and propose a binocular tone mapping framework. The proposed framework generates a binocular low-dynamic range (LDR) image pair that preserves more human-perceivable visual content than a single LDR image using the additional image domain. Given a tone-mapped LDR image (left, without loss of generality), our framework optimally synthesizes its counterpart (right) in the image pair from the same source HDR image. The two LDR images are different, so that they can aggregately present more human-perceivable visual richness than a single arbitrary LDR image, without triggering visual discomfort . To achieve this goal, a novel binocular viewing comfort predictor (BVCP) is also proposed to prevent such visual discomfort. The design of BVCP is based on the findings in vision science. Through our user studies, we demonstrate the increase of human-perceivable visual richness and the effectiveness of the proposed BVCP in conservatively predicting the visual discomfort threshold of human observers.

Data ambiguity is inherent in applications such as data integration, location-based services, and sensor monitoring. In many situations, it is possible to "clean", or remove, ambiguities from these databases. For example, the GPS location of a user is inexact due to measurement errors, but context information (e.g., what a user is doing) can be used to reduce the imprecision of the location value. In order to obtain a database with a higher quality, we study how to disambiguate a database by appropriately selecting candidates to clean. This problem is challenging because cleaning involves a cost, is limited by a budget, may fail, and may not remove all ambiguities. Moreover, the statistical information about how likely database objects can be cleaned may not be precisely known. We tackle these challenges by proposing two types of algorithms. The first type makes use of greedy heuristics to make sensible decisions; however, these algorithms do not make use of cleaning information and require user input for parameters to achieve high cleaning effectiveness. We propose the Explore-Exploit (or EE ) algorithm, which gathers valuable information during the cleaning process to determine how the remaining cleaning budget should be invested. We also study how to fine-tune the parameters of EE in order to achieve optimal cleaning effectiveness. Experimental evaluations on real and synthetic datasets validate the effectiveness and efficiency of our approaches.

We propose a new method for detecting and approximating the boundary surfaces in three-dimensional (3-D) biomedical images. Using this method, each boundary surface in the original 3-D image is normalized as a zero-value isosurface of a new 3-D image transformed from the original 3-D image. A novel computational framework is proposed to perform such an image transformation. According to this framework, we first detect boundary surfaces from the original 3-D image and compute discrete samplings of the boundary surfaces. Based on these discrete samplings, a new 3-D image is constructed for each boundary surface such that the boundary surface can be well approximated by a zero-value isosurface in the new 3-D image. In this way, the complex problem of reconstructing boundary surfaces in the original 3-D image is converted into a task to extract a zero-value isosurface from the new 3-D image. The proposed technique is not only capable of adequately reconstructing complex boundary surfaces in 3-D biomedical images, but it also overcomes vital limitations encountered by the isosurface-extracting method when the method is used to reconstruct boundary surfaces from 3-D images. The performances and advantages of the proposed computational framework are illustrated by many examples from different 3-D biomedical images.