Predicting image data with the SRS-12 algorithm. Applying random projection-based c-approximate nearest-neighbor queries to image data

Bachelor Thesis , 2015 , 41 Pages , Grade: 1.0

Computer Science - Applied

Determining point similarity is a cornerstone for a wide variety of applications. Whenever data is being compared, the problem can be stated as a matter of comparing vectors. Due
to this fundamental importance, research has been conducted in this area for decades. For a long time, even for relatively low dimensions such as for example d = 10, complexity was far beyond of what was considered to be feasible in practice. A common approach is to soften the requirements for the accuracy of the neighbor search and look for points within a certain proximity to the query point instead of searching for exact neighbors.

In this thesis we evaluate how well the SRS-12 algorithm works on real-world image data in order to lay the ground for future work such as image prediction. The SRS-12 algorithm is an approach to c-approximate nearest-neighbors and claims to have a tiny index and arbitrary approximation ratio while maintaining good theoretical guarantees.

We first implement and verify the algorithm and subsequently examine the quality of its outputs when it is applied to image data by performing block matching. We find that the SRS-12
algorithm is indeed very suitable for processing image data as long as the input images are cut into patches that are sufficiently large. However the parameters of the algorithm have to be tuned carefully because they significantly affect not only the quality of the results, but also the computation time which can easily exceed an exact nearest-neighbor query if the parameters are not set properly. We conclude our experiment with a recommendation for well-working parameter settings and propose approaches to enhance the quality and speed of approximate nearest-neighbor queries on image data made with the SRS-12 algorithm such that it can be used in real-time.

Contents

1 Introduction
1.1 Motivation
1.2 Problem Statement
1.3 Objectives
1.4 Structure of this Thesis

2 A brief history and overview of Approximate Nearest-Neighbor Queries
2.1 Improving Index Structures
2.2 Softening Requirements for Accuracy
2.3 Further Related Work

3 An Introduction to SRS-12
3.1 Why SRS-12 is worth a consideration
3.2 SRS-12 in a Nutshell
3.3 Variants of SRS-12
3.4 Indexing
3.5 Normal Stopping Condition of the SRS-12 Algorithm

4 Implementation & Experimental Evaluation
4.1 Implementation Details for the Computation of Parameter Values .
4.2 Datasets
4.3 Veri cation on SIFT1M Dataset
4.4 Block Matching
4.4.1 A Brief Introduction to Block Matching
4.4.2 Methodology
4.4.3 Parameter Settings
4.4.4 Computation Time
4.4.5 Conclusions
4.4.6 Summary - Recommended Parameter Settings
4.5 Computation Time of SRS-12 vs Exact Nearest-Neighbor Search
4.5.1 Possible Optimizations

5 Future Work
5.1 Image Prediction
5.2 Reducing Data through Rapid Object Detection and Background Removal . . .
5.3 Optical Flow
5.4 Increasing the Accuracy of the SRS-12 Algorithm

6 Discussion

Bibliography

• College: University of Heidelberg (Computer Science)
• Grade: 1.0
• Author: Philipp Güth (Author)
• Publication Year: 2015
• Pages: 41
• Catalog Number: V305214
• ISBN (eBook): 9783668033542
• ISBN (Book): 9783668033559
• Language: English
• Tags: Machine Learning, Big Data, Image Prediction, Predictive Analytics, Nearest Neighbors, Image Recognition, SRS-12