Abstract

In this paper, we aim to learn a mapping (or embedding) from images to a compact binary space in which Hammingdistances correspond to a ranking measure for the imageretrieval task. We make use of a triplet loss because this has been shown to be most effective for ranking problems. How-ever, training in previous works can be prohibitively expen-sive due to the fact that optimization is directly performed on the triplet space, where the number of possible tripletsfor training is cubic in the number of training examples.To address this issue, we propose to formulate high-orderbinary codes learning as a multi-label classification problem by explicitly separating learning into two interleaved stages. To solve the first stage, we design a large-scale high-order binary codes inference algorithm to reduce the high-order objective to a standard binary quadratic problem such that graph cuts can be used to efficiently inferthe binary codes which serve as the labels of each trainingdatum. In the second stage we propose to map the original image to compact binary codes via carefully designed deep convolutional neural networks (CNNs) and the hashing function fitting can be solved by training binary CNN classifiers. An incremental/interleaved optimization strategy is proffered to ensure that these two steps are interactive with each other during training for better accuracy. We conduct experiments on several benchmark datasets, which demonstrate both improved training time (by as much as two orders of magnitude) as well as producing state-of-theart hashing for various retrieval tasks.