Low-rate image retrieval with tree histogram coding

To perform image retrieval using a mobile device equipped with a camera, the mobile captures an image, transmits data wirelessly to a server, and the server replies with the associated database image information. Query data compression is crucial for low-latency retrieval over a wireless network. For fast retrieval from large databases, Scalable Vocabulary Trees (SVT) are commonly employed. In this work, we propose using distributed image matching where corresponding Tree-Structured Vector Quantizers (TSVQ) are stored on both the mobile device and the server. By quantizing feature descriptors using an optimally pruned TSVQ on the mobile device and transmitting just a tree histogram, we achieve very low bitrates without sacrificing recognition accuracy. We carry out tree pruning optimally using the BFOS algorithm and design criteria for trading off classification-error-rate and bitrate effectively. For the well known ZuBuD database, we achieve 96% accuracy with only ∼1000 bits per image. By extending accurate image recognition to such extremely low bitrates, we can open the door to new applications on mobile networked devices.