Approximate Nearest Neighbors (ANN) in high dimensional vector spaces is a fundamental, yet challenging
problem in many areas of computer science, including computer vision, data mining and robotics. In this work,
we investigate this problem from the perspective of compressive sensing, especially the dictionary learning aspect.
High dimensional feature vectors are seldom seen to be sparse in the feature domain; examples include, but not
limited to Scale Invariant Feature Transform (SIFT) descriptors, Histogram Of Gradients, Shape Contexts, etc.
Compressive sensing advocates that if a given vector has a dense support in a feature space, then there should
exist an alternative high dimensional subspace where the features are sparse. This idea is leveraged by dictionary
learning techniques through learning an overcomplete projection from the feature space so that the vectors are
sparse in the new space. The learned dictionary aids in refining the search for the nearest neighbors to a query
feature vector into the most likely subspace combination indexed by its non-zero active basis elements. Since
the size of the dictionary is generally very large, distinct feature vectors are most likely to have distinct non-zero
basis. Utilizing this observation, we propose a novel representation of the feature vectors as tuples of non-zero
dictionary indices, which then reduces the ANN search problem into hashing the tuples to an index table; thereby
dramatically improving the speed of the search. A drawback of this naive approach is that it is very sensitive
to feature perturbations. This can be due to two possibilities: (i) the feature vectors are corrupted by noise,
(ii) the true data vectors undergo perturbations themselves. Existing dictionary learning methods address the
first possibility. In this work we investigate the second possibility and approach it from a robust optimization
perspective. This boils down to the problem of learning a dictionary robust to feature perturbations, viz. paving
the way for a novel Robust Dictionary Learning (RDL) framework. In addition to the above model, we also
propose a novel LASSO based multi-regularization hashing algorithm which utilizes the consistency properties of
the non-zero active basis for increasing values of the regularization weights. Even though our algorithm is generic
and has wide coverage in different areas of scientific computing, the experiments in the current work are mainly
focused towards improving the speed and accuracy of ANN for SIFT descriptors, which are high-dimensional
(128D) and are one of the most widely used interest point detectors in computer vision. Preliminary results from
SIFT datasets show that our algorithm is far superior to the state-of-the-art techniques in ANN.
Thermal imaging is rightfully a real-world technology proven to bring confidence to daytime, nighttime and all weather security surveillance. Automatic image processing intrusion detection algorithms are also a real world technology proven to bring confidence to system surveillance security solutions. Together, day, night and all weather video imagery sensors and automated intrusion detection software systems create the real power to protect early against crime, providing real-time global homeland protection, rather than simply being able to monitor and record activities for post event analysis. These solutions, whether providing automatic security system surveillance at airports (to automatically detect unauthorized aircraft takeoff and landing activities) or at high risk private, public or government facilities (to automatically detect unauthorized people or vehicle intrusion activities) are on the move to provide end users the power to protect people, capital equipment and intellectual property against acts of vandalism and terrorism. As with any technology, infrared sensors and automatic image intrusion detection systems for global homeland security protection have clear technological strengths and limitations compared to other more common day and night vision technologies or more traditional manual man-in-the-loop intrusion detection security systems. This paper addresses these strength and limitation capabilities. False Alarm (FAR) and False Positive Rate (FPR) is an example of some of the key customer system acceptability metrics and Noise Equivalent Temperature Difference (NETD) and Minimum Resolvable Temperature are examples of some of the sensor level performance acceptability metrics.