Local features are widely used in many computer vision tasks such as marker-less augmented reality (AR), object recognition and tracking, and 3D reconstruction. The robustness, distinctiveness and high efficiency of a local feature are critical to the user experience of real-world applications. However, existing local feature algorithms are either too compute-insensitive to achieve real-time performance, especially when running on low power mobile devices, or not sufficiently robust and distinctive to identify correct matches from a large database.

This thesis focuses on designing robust, distinctive and high-speed local features that can run in real-time on mobile devices such as smartphones. Typically, a local feature extraction pipeline includes two components: 1) interest point detector which identifies a set of salient points in an image, and 2) point descriptor which represents each detected point using a feature vector. For the interest point detection, this thesis focuses on accelerating SURF point detector by solving two mismatches between the SURF algorithm and the mobile hardware that cause substantial slow-down of the detection process: 1) mismatch between the data access pattern and the small cache size, and 2) mismatch between the huge amount of branches and high pipeline hazard penalty. To address the mismatches, two techniques: tiled SURF and gradient moment based orientation assignment are proposed. Tiled SURF improves data locality and greatly reduces memory traffic. To avoid the penalties caused by pipeline hazards, the original orientation operator is replaced with branching-free gradient moment computations.

For the point description, this thesis presents a highly efficient and distinctive binary descriptor, called Local Difference Binary (LDB). LDB directly computes a binary string for an image patch using simple intensity and gradient difference tests on pairwise grid cells within the patch. A multiple gridding strategy is applied to capture the distinct patterns of the patch at different spatial granularities. To further enhance the distinctiveness of LDB, a learning-based framework is proposed. In the framework image pixels are densely sampled and represented using Harr-like features, providing a rich source of distinctive binary features. A modified AdaBoost algorithm is leveraged to automatically extract a small set of critical features for any given task with the goal of maximizing the Hamming distance between mismatches while minimizing it between matches. Extensive experiments on real data demonstrate that the proposed point detector and descriptors achieve high robustness, distinctiveness and efficiency on mobile devices.