Graph regularized nonnegative sparse coding using incoherent dictionary for approximate nearest neighbor search. (October 2017)

• Record Type: Journal Article
• Authors: Zhang, Yupei; Xiang, Ming; Yang, Bo
• Is Part Of: Pattern recognition. Volume 70(2017:Oct.)
• Page Start: 75
• Page End: 88
• Publication Date: 2017-10
• Subjects: Nonnegative sparse coding -- Incoherent dictionary learning -- Laplacian regularization -- Approximate nearest neighbor searching -- Image retrieval; Pattern perception -- Periodicals; Perception des structures -- Périodiques; Patroonherkenning; 006.4
• DOI: 10.1016/j.patcog.2017.04.030
• Languages: English
• ISSNs: 0031-3203

Abstract

Highlights: Graph Laplacian regularization is considered for improvement. Non-negativity constraints are adopted for enriching sparse codes. An iterative algorithm is proposed to learn incoherent dictionary. Interesting improvement is reaped without sacrificing query time. Abstract: In this paper, we consider the problem of approximate nearest neighbor (ANN) retrieval with the method of sparse coding, which is a promising tool of discovering compact representation of high-dimensional data. A new study, exploiting the indices of the active set of sparse coded data as retrieval code, exhibits an appealing ANN route. Here our work aims to enhance the method via considering its shortages of the local structure of the data. Our primary innovation is two-fold: We introduce the graph Laplacian regularization to preserve the local structure of the original data into reduced space, which is indeed beneficial to ANN. And we impose non-negativity constraints such that the retrieval code can more effectively reflect the neighborhood relation, thereby cutting down on unnecessary hash collision. To this end, we learn an incoherent dictionary with both rules via a novel formulation of sparse coding. The resulting optimization problem can be provided with an available solution by the widely used iterative scheme, where we resort to the feature-sign search algorithm in the sparse coding step and exploit the method that uses a Lagrange dual for dictionary learning step. Experimental results on publicly available image data sets manifest that the rules are positive to promote the classification and ANN accuracies. Compared with several state-of-the-art ANN techniques, our methods can achieve an interesting improvement in retrieval accuracy.