Coordinate Discrete Optimization for Efficient Cross-View Image Retrieval

Yadong Mu, Wei Liu, Cheng Deng, Zongting Lv, Xinbo Gao

Abstract

Cross-view image retrieval is a critical task in multi-modal data analysis, yet traditional hashing methods often suffer from accuracy loss due to continuous relaxation of binary constraints. This paper presents Coordinate Discrete Hashing (CDH), a framework that directly optimizes discrete binary codes using a block coordinate descent approach. By incorporating an active set reduction method and transforming the discrete sub-problem into a quadratic form, CDH achieves significant performance improvements—ranging from 5% to 20% in Mean Average Precision (mAP)—over state-of-the-art methods on standard benchmarks like Wiki, NUS-WIDE, and MIRFlickr.

Introduction

In the era of multi-modal data, cross-view retrieval—such as using a text query to find an image—is essential. To make this search fast and storage-efficient, researchers use "hashing" to compress high-dimensional data into short binary codes. However, the discrete nature of binary codes makes the optimization problem NP-hard. Most existing methods circumvent this by "relaxing" binary constraints to continuous values during optimization and rounding them back at the end. This rounding process introduces significant errors and degrades retrieval precision. CDH addresses this by treating binary constraints as fundamental, employing direct discrete optimization.

Methodology

CDH utilizes an alternating maximization strategy to optimize a dual-objective function focused on semantic preservation and generative probability. Semantic preservation ensures similar items across views have similar hash codes, while generative probability ensures codes can be predicted from raw features of a single view.

Coordinate Discrete Optimization

Instead of simultaneous updates, CDH employs block coordinate descent, updating one bit (one column of the hash matrix) at a time. This approach ensures that each bit is optimized to complement the existing hash code structure. The authors mathematically prove that the discrete sub-problem can be efficiently solved by transforming it into a more tractable quadratic form.

Active Set Reduction

To maintain computational efficiency on large datasets, an active set method identifies a subset of data points most likely to require bit-flips. This drastically reduces the number of updates needed per iteration without compromising the rigorous convergence of the algorithm.

Comparison of bit-flip percentages between the original and reduced active sets, demonstrating the efficiency of the proposed reduction method.

Experimental Evaluation

The performance of CDH was evaluated on three major image-text benchmarks: Wiki (2,866 pairs), NUS-WIDE (~186,000 images), and MIRFlickr (25,000 pairs).

Results and Discussion

CDH consistently outperformed baseline methods such as SCM and SePH. On the Wiki dataset, CDH achieved an mAP of approximately 0.36 for image queries, a substantial improvement over SCM's 0.24. The method demonstrates rapid convergence, typically within just two passes over the total number of bits ($K$).

Convergence of mAP scores across training and testing phases, highlighting the rapid optimization and stability of the CDH framework.

Sensitivity analysis indicates that the model is robust to variations in the hyperparameter $\gamma$, which balances the semantic and generative components of the objective function. This stability suggests that the learned codes are both mathematically optimal and generalizable to new queries.

Conclusion

Coordinate Discrete Hashing demonstrates that direct discrete optimization is not only feasible but superior for large-scale cross-view retrieval. By avoiding relaxation-induced errors and leveraging coordinate descent with active set reduction, CDH provides a scalable and highly accurate solution for multi-modal hashing. Future work may explore non-linear generative models, such as deep neural networks, and unsupervised extensions to the framework.

Summary updated

BibTeX
@inproceedings{mu2016coordinate,
  author = {Yadong Mu and Wei Liu and Cheng Deng and Zongting Lv and Xinbo Gao},
  title = {{Coordinate Discrete Optimization for Efficient Cross-View Image Retrieval}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2016},
}
Figure