Abstract
Binary encoding of features has proven to be a versatile tool for optimizing data processing and memory efficiency in various machine learning applications. This includes deep barcoding of images for retrieval of similar cases among millions of indexed images. Despite the recent advancement in barcode generation methods, converting hyperdimensional feature vectors (e.g., deep features) to compact and discriminative binary barcodes is still an urgent necessity and widely an unresolved problem. MinMax barcoding of features is one of the efficient binarization methods, where the accuracy of the generated barcodes is inherently dependent on the feature order due to its computation process. In this paper, we propose a combinatorial evolutionary framework for optimizing barcodes. The primary goal is to determine an optimal permutation of extracted deep features, leading to more accurate barcodes. The performance of the proposed model has been assessed in downstream image retrieval tasks using a variety of datasets. This evaluation includes medical images from The Cancer Genome Atlas (TCGA), a comprehensive publicly available dataset, as well as images from a COVID-19 dataset. In addition, the model's performance was tested on diverse non-medical image collections, such as CIFAR-10 and Fashion-MNIST. Our findings demonstrate that optimizing barcodes significantly enhances retrieval accuracy across a wide range of applications, highlighting the applicability and potential of barcodes in various domains.
Introduction
Modern computer vision relies heavily on deep learning "embeddings"—high-dimensional floating-point vectors that represent image content. While descriptive, these embeddings present significant challenges for large-scale retrieval systems due to their high storage requirements and the computational cost of calculating Euclidean distances across millions of entries.
To address these bottlenecks, researchers employ barcoding (binarization), transforming these vectors into compact binary strings (0s and 1s). This allows for massive compression and enables ultra-fast searching via Hamming distance. However, popular methods like MinMax barcoding are highly sensitive to the order of features within the vector. Because MinMax generates bits by comparing adjacent feature values, a sub-optimal permutation can lead to a loss of critical discriminative information. This research proposes a method to find the optimal feature permutation to maximize barcode quality.
The Combinatorial Evolutionary Framework
The authors introduce a Combinatorial Genetic Algorithm (CGA) designed to treat feature ordering as an optimization problem. The workflow integrates deep feature extraction with an evolutionary loop to refine the binarization process.
Methodology
- Feature Extraction: High-dimensional feature vectors are extracted using pre-trained deep networks (e.g., DenseNet121 or ResNet50).
- MinMax Barcoding: A binary bit $y_i$ is generated by comparing feature $x_i$ with its neighbor $x_{i+1}$. If $x_i < x_{i+1}$, the bit is 1; otherwise, it is 0.
- Evolutionary Optimization:
- Chromosomes: Each individual in the population represents a specific permutation of the feature vector.
- Fitness Function: The quality of an order is evaluated by binarizing a training set using that permutation and performing $k$-Nearest Neighbor ($k$-NN) classification. The resulting F1-score serves as the fitness value.
- Genetic Operators: To explore the permutation space, the algorithm uses "Order Crossover" (OX1) to combine traits from parent permutations and "Swap Mutation" to maintain diversity.
Experimental Validation
The framework was validated across four diverse datasets:
- TCGA (The Cancer Genome Atlas): ~30,000 histopathology images across 32 cancer subtypes.
- COVID-19 Radiography: Chest X-rays categorized into four clinical classes.
- Fashion-MNIST & CIFAR-10: Standard benchmarks for general-purpose image classification.
Success was measured using the Improvement Accuracy Rate (IAR), where an IAR > 1.00 indicates that the optimized order outperformed the original feature sequence.
Key Results
- Medical Imaging: On the TCGA dataset with DenseNet121 features, the average F1-score improved by 5% (IAR 1.05). In specific cases like brain tumor classification, improvements reached 8%.
- Enhanced Discriminative Power: In the brain organ dataset, the proximity between barcodes of the same class increased by 67% post-optimization, effectively reducing noise in retrieval results.
- Generalization: The method consistently improved performance on non-medical data, achieving an IAR of 1.02 on both Fashion-MNIST and the COVID-19 dataset.
Discussion and Conclusion
The study reveals that the sequence of features—often treated as arbitrary in neural network outputs—is a critical hyperparameter for effective binarization. This "plug-and-play" enhancement does not require retraining the underlying deep learning models, making it a versatile post-processing tool.
However, challenges remain. As feature dimensions increase (e.g., to 4096), the factorial growth of the search space may require more computationally efficient optimization strategies. Additionally, the iterative nature of the genetic algorithm with $k$-NN evaluation introduces offline training overhead. Future work may explore multi-objective evolutionary algorithms to further balance barcode compactness, retrieval speed, and accuracy.
Reference: Khosrowshahli, R., et al. "Optimal Deep Barcodes for Fast Image Retrieval." Research Square, 2024. DOI: 10.21203/rs.3.rs-4818178/v1
Summary updated