1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132

use serde::{Deserialize, Serialize};
use smallvec::SmallVec;
use thiserror::Error;

/// Implementation of a visual bag-of-words vocabulary,
/// which provides the main functionality of this create.
pub mod vocab;
pub use vocab::Vocabulary;

/// Utilities for extracting feature descriptors using opencv.
pub mod opencv_utils;
#[cfg(feature = "opencv")]
pub use opencv_utils::*;

/// Supported descriptor type is 256-bit array.
pub type Desc = [u8; 32];

/// Bag-of-Words representation of an image or descriptor set.
///
/// Index: word/leaf id in the vocabulary.
///
/// Value: total weight of that word in provided features.
#[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
pub struct BoW(pub Vec<f32>);

/// A map from features to their corresponding nodes in the Vocabulary tree.
/// Each feature maps to several nodes, up to one for each level of the tree.
///
/// The direct index for `feature[i]` is `di = DirectIdx[i]` where
/// `di.len() <= l` (number of levels).
/// `di[j]` is the id of the node matching `feature[i]`
/// at level `j` in the Vocabulary tree.
pub type DirectIdx = Vec<IdPath>;

/// The path from the root to the leaf for a given feature.
// Only 5 entries are stack allocated, so level > 5 would have poor performance.
pub type IdPath = SmallVec<[usize; 5]>;

impl BoW {
    /// Compute L1 norm between two BoW. (Used in Galvez (Eq 2)).
    pub fn l1(&self, other: &Self) -> f32 {
        let values = self.0.iter().zip(&other.0);
        1. - 0.5 * (values.fold(0., |a, (b, c)| a + (b - c).abs()))
    }
}

type BowResult<T> = std::result::Result<T, BowErr>;
#[derive(Error, Debug)]
pub enum BowErr {
    #[error("No Features Provided")]
    NoFeatures,
    #[error("Io Error")]
    Io(#[from] std::io::Error),
    #[cfg(feature = "bincode")]
    #[error("Vocabulary Serialization Error")]
    Bincode(#[from] bincode::Error),
    #[cfg(feature = "opencv")]
    #[error("Opencv Error")]
    OpenCvInternal(#[from] opencv::Error),
    #[cfg(feature = "opencv")]
    #[error("Opencv Descriptor decode error")]
    OpenCvDecode,
}

#[cfg(test)]
#[cfg(feature = "opencv")]
mod test {
    use super::*;
    use std::path::{Path, PathBuf};
    #[test]
    /// Performs a somewhat ad-hoc parameter search for the highest recall as a function
    /// of `l` and `k`. l=4 and k=10 is apparently best.
    fn test_recall() {
        // Load existing vocabulary
        let features = all_kps_from_dir("data/train").unwrap();
        println!("Detected {} ORB features.", features.len());

        for &k in &[6_usize, 8_usize, 10_usize] {
            for &l in &[3_usize, 4_usize, 5_usize] {
                for _ in 0..2 {
                    // Create vocabulary from features
                    let voc = Vocabulary::create(&features, k, l);
                    println!("Vocabulary: {:#?}", voc);

                    // Create BoW vectors from the test data. Save file name for demonstration.
                    let mut bows: Vec<(PathBuf, BoW)> = Vec::new();
                    for entry in Path::new("data/test").read_dir().expect("Error").flatten() {
                        let new_feat = load_img_get_kps(&entry.path()).unwrap();
                        bows.push((entry.path(), voc.transform(&new_feat).unwrap()));
                    }

                    // sort the files just for nicer output
                    let num = |s: &str| -> usize {
                        let s = s.strip_suffix(".jpg").unwrap();
                        s.parse().unwrap()
                    };
                    bows.sort_by(|a, b| {
                        num(a.0.file_name().unwrap().to_str().unwrap())
                            .partial_cmp(&num(b.0.file_name().unwrap().to_str().unwrap()))
                            .unwrap()
                    });

                    let mut cost = 0;

                    // Compare a few images to the the whole collection using L1 norm
                    for (f1, bow1) in bows.iter().skip(12).take(158) {
                        let mut scores: Vec<(f32, usize, i32)> = Vec::new();
                        let reference = num(f1.file_name().unwrap().to_str().unwrap());

                        for (f2, bow2) in bows.iter() {
                            let d = bow1.l1(bow2);
                            let matched = num(f2.file_name().unwrap().to_str().unwrap());
                            let cost = i32::abs(matched as i32 - reference as i32);
                            scores.push((d, matched, cost));
                        }

                        // Print out the top 5 matches for each image
                        let base_cost = 36; // 0 + 1 + 1 + 2 + 2 + 3 + 3 + 4 + 4 + 5 + 5 + 6

                        scores.sort_by(|a, b| b.0.partial_cmp(&a.0).unwrap());
                        for m in scores[..12].iter() {
                            cost += m.2;
                        }
                        cost -= base_cost;
                    }

                    println!("k: {}, l: {}. Total Cost: {}", k, l, cost);
                }
            }
        }
    }
}