Most classification rules can be expressed in terms of a distance (or dissimilarity) from the point to be classified to each of the candidate classes. For example, linear discriminant analysis classifies points into the class for which the (sample) Mahalanobis distance is smallest. However, dependence among these point-to-group distance measures is generally ignored. The primary goal of this project is to investigate the properties of a general non-parametric classification rule which takes this dependence structure into account. A review of classification procedures and applications is presented. The distance profile nearest-neighbor classification rule is defined. Properties of the rule are then explored via application to both real and simulated data and comparisons to other classification rules are discussed.

No description available.

No description available.

The nearest neighbour problem is of practical significance in a number of fields. Often we are interested in finding an object near to a given query object. The problem is old, and a large number of solutions have been proposed for it in the literature. However, it remains the case that even the most popular of the techniques proposed for its solution have not been compared against each other. Also, many techniques, including the old and popular ones, can be implemented in a number of ways, and often the different implementations of a technique have not been thoroughly compared either. This research presents a detailed investigation of different implementations of two popular nearest neighbour search data structures, KDTrees and Metric Trees, and compares the different implementations of each of the two structures against each other. The best implementations of these structures are then compared against each other and against two other techniques, Annulus Method and Cover Trees. Annulus Method is an old technique that was rediscovered during the research for this thesis. Cover Trees are one of the most novel and promising data structures for nearest neighbour search that have been proposed in the literature.

Recovering a volumetric model of a person, car, or other object of interest from a single snapshot would be useful for many computer graphics applications. 3D model estimation in general is hard, and currently requires active sensors, multiple views, or integration over time. For a known object class, however, 3D shape can be successfully inferred from a single snapshot. We present a method for generating a ``virtual visual hull''-- an estimate of the 3D shape of an object from a known class, given a single silhouette observed from an unknown viewpoint. For a given class, a large database of multi-view silhouette examples from calibrated, though possibly varied, camera rigs are collected. To infer a novel single view input silhouette's virtual visual hull, we search for 3D shapes in the database which are most consistent with the observed contour. The input is matched to component single views of the multi-view training examples. A set of viewpoint-aligned virtual views are generated from the visual hulls corresponding to these examples. The 3D shape estimate for the input is then found by interpolating between the contours of these aligned views. When the underlying shape is ambiguous given a single view silhouette, we produce multiple visual hull hypotheses; if a sequence of input images is available, a dynamic programming approach is applied to find the maximum likelihood path through the feasible hypotheses over time. We show results of our algorithm on real and synthetic images of people.

Nearest Neighbor (NN in short) queries are important in emerging applications, such as wireless networks, location-based services, and data stream applications, where the data obtained are often imprecise. The imprecision or imperfection of the data sources is modeled by uncertain data in recent research works. Handling uncertainty is important because this issue affects the quality of query answers. Although queries on uncertain data are useful, evaluating the queries on them can be costly, in terms of I/O or computational efficiency. In this thesis, we study how to efficiently evaluate NN queries on uncertain data. Given a query point q and a set of uncertain objects O, the possible nearest neighbor query returns a set of candidates which have non-zero probabilities to be the query answer. It is also interesting to ask \which region has the same set of possible nearest neighbors", and \which region has one specific object as its possible nearest neighbor". To reveal the relationship between the query space and nearest neighbor answers, we propose the UV-diagram, where the query space is split into disjoint partitions, such that each partition is associated with a set of objects. If a query point is located inside the partition, its possible nearest neighbors could be directly retrieved. However, the number of such partitions is exponential and the construction effort can be expensive. To tackle this problem, we propose an alternative concept, called UV-cell, and efficient algorithms for constructing it. The UV-cell has an irregular shape, which incurs difficulties in storage, maintenance, and query evaluation. We design an index structure, called UV-index, which is an approximated version of the UV-diagram. Extensive experiments show that the UV-index could efficiently answer different variants of NN queries, such as Probabilistic Nearest Neighbor Queries, Continuous Probabilistic Nearest Neighbor Queries. Another problem studied in this thesis is the trajectory nearest neighbor query. Here the query point is restricted to a pre-known trajectory. In applications (e.g. monitoring potential threats along a flight/vessel's trajectory), it is useful to derive nearest neighbors for all points on the query trajectory. Simple solutions, such as sampling or approximating the locations of uncertain objects as points, fails to achieve a good query quality. To handle this problem, we design efficient algorithms and optimization methods for this query. Experiments show that our solution can efficiently and accurately answer this query. Our solution is also scalable to large datasets and long trajectories. / published_or_final_version / Computer Science / Doctoral / Doctor of Philosophy

Video surveillance systems have been popular as a security tool for years, and the technological development helps monitoring accident-prone areas with the help of digital image processing.A thermal and a visual camera are being used in the surveillance project. The thermal camera is sensitive to the heat emitted by objects, and it is essential to employ the thermal camera as the visual camera is only useful in the presence of light. These cameras do not provide images of the same resolution. In order to extract the region of interest (ROI) of the visual camera, the images of these cameras need to have the same resolution; therefore the thermal images are processed in order to have the same size as the visual image.The ROI extraction is needed in order to reduce the data that needs to be transmitted. The region of interest is extracted from the visual image and the required processes are mostly done on the thermal image as it has lower resolution and therefore requires less computational processing. The image taken from the thermal camera is up scaled by using the nearest neighbor algorithm and it is zero-padded to make the resolutions of the two images equal, and then the region of interest is extracted by masking the result with the related converted version of visual image to YCbCr color space.

Recovering a volumetric model of a person, car, or other objectof interest from a single snapshot would be useful for many computergraphics applications. 3D model estimation in general is hard, andcurrently requires active sensors, multiple views, or integration overtime. For a known object class, however, 3D shape can be successfullyinferred from a single snapshot. We present a method for generating a``virtual visual hull''-- an estimate of the 3D shape of an objectfrom a known class, given a single silhouette observed from an unknownviewpoint. For a given class, a large database of multi-viewsilhouette examples from calibrated, though possibly varied, camerarigs are collected. To infer a novel single view input silhouette'svirtual visual hull, we search for 3D shapes in the database which aremost consistent with the observed contour. The input is matched tocomponent single views of the multi-view training examples. A set ofviewpoint-aligned virtual views are generated from the visual hullscorresponding to these examples. The 3D shape estimate for the inputis then found by interpolating between the contours of these alignedviews. When the underlying shape is ambiguous given a single viewsilhouette, we produce multiple visual hull hypotheses; if a sequenceof input images is available, a dynamic programming approach isapplied to find the maximum likelihood path through the feasiblehypotheses over time. We show results of our algorithm on real andsynthetic images of people.

Link travel time plays a significant role in traffic planning, traffic management and Advanced Traveler Information Systems (ATIS). A public probe vehicle dataset is a probe vehicle dataset that is collected from public people or public transport. The appearance of public probe vehicle datasets can support travel time collection at a large temporal and spatial scale but at a relatively low cost. Traditionally, link travel time is the aggregation of travel time by different movements. A recent study proved that link travel time of different movements is significantly different from their aggregation. However, there is still not a complete framework for estimating movement-based link travel time. In addition, probe vehicle datasets usually have a low penetration rate but no previous study has solved this problem. To solve the problems above, this study proposed a detailed framework to estimate movement-based link travel time using a high sampling rate public probe vehicle dataset. Our study proposed a k-Nearest Neighbors (k-NN) regression method to increase travel time samples using incomplete trajectory. An incomplete trajectory was compared with historical complete trajectories and the link travel time of the incomplete trajectory was represented by its similar complete trajectories. The result of our study showed that the method can significantly increase link travel time samples but there are still limitations. In addition, our study investigated the performance of k-NN regression under different parameters and input data. The sensitivity analysis of k-NN algorithm showed that the algorithm performed differently under different parameters and input data. Our study suggests optimal parameters should be selected using a historical dataset before real-world application.

This thesis work presents a non-parametric learning method, the Extended Nearest Neighbor (ENN) algorithm, as a tool for data disaggregation in smart grids. The ENN algorithm makes the prediction according to the maximum gain of intra-class coherence. This algorithm not only considers the K nearest neighbors of the test sample but also considers whether these K data points consider the test sample as their nearest neighbor or not. So far, ENN has shown noticeable improvement in the classification accuracy for various real-life applications. To further enhance its prediction capability, in this thesis we propose to incorporate a metric learning algorithm, namely the Large Margin Nearest Neighbor (LMNN) algorithm, as a training stage in ENN. Our experiments on real-life energy data sets have shown significant performance improvement compared to several other traditional classification algorithms, including the classic KNN method and Support Vector Machines.