1 Searching for Sub-images Using Sequence Alignment Tomáš Homola, Vlastislav Dohnal, Pavel Zezula 2 Presentation Outline • Motivation • Current approaches to the sub-image retrieval • Sequence alignment methods • Conclusion Motivation 3 Image & Search engine & Database of images = (query) (technology) Found images (response) & Happy user Motivation 4 Image & Search engine & Database of images = (query) (technology) Found images (response) & Disappointed user 5 Sub-Image Retrieval — Approaches Global descriptors Local descriptors • Image characterization Sub-Image Retrieval — L.F. Approaches Query Image Database Image(s) Sub-Image Retrieval — L.F. Approaches Query Image Database Image(s) Extract local features Suppose our features are scale- and rotation-invariant SIFT and its derivates, MSER, … Sub-Image Retrieval — L.F. Approaches Query Image Database Image(s) Extract local features Transform local features – local features => visual words – image => bag-of-words Sub-Image Retrieval — L.F. Approaches Query Image Database Image(s) Extract local features Transform local features Find correspon- dences Usually inspired by the text retrieval (tf-idf,…) Sub-Image Retrieval — L.F. Approaches Query Image Database Image(s) Extract local features Transform local features Find correspon- dences Geometrical verification RANSAC, Least Medians of Squares, Generalized Hough Transformation, … Sub-Image Retrieval — L.F. Approaches Extract local features Transform local features Find correspon- dences Geometrical verification Query image Rank the answer Ranked answer Sub-Image Retrieval — Our Approach • Bag-of-words methods: – Rely on training data – Lost of information • Local features (High-dimensional vectors) themselves create an alphabet in our approach Extract local features Transform local features Find correspon- dences Geometrical verification Rank the answer Sub-Image Retrieval — Our Approach • Sequence alignment methods used for the geometrical verification Extract local features Transform local features Find correspon- dences Geometrical verification Rank the answer Sequence alignment • Local features are projected into x/y axis => ordered sequence • Sequences are compared using sequencealignment methods Sequence alignment methods • Commonly used in bioinformatics (i.e. protein sequences alignment) • User defined scoring scheme (match, mismatch and gap scores/penalties) • Scoring matrix Sequence-alignment methods – cont. • Needleman-Wunsch (Global alignment) • Smith-Watermann (Local alignment – deals better with starting/ending gaps -> sequences of the non-equal length) –D––CE–– ×|××||×× ADBHCEFG –D––CE–– =|=–||=– ADBHCEFG – Gap × Mismatch | Match = Gap opening – Gap cont. × Mismatch | Match Sliding windows • Small query & large database image (and vice versa) leads to ―noise‖ in projected sequences (letters B and H) • => Split images (queries and database) into the fixed-size windows • Run sequence alignment for each of the window separately Evaluation • BelgaLogos dataset • Queries: 26 logos, database: 10 000 images • Original method Joly&al – Visual words + RANSAC Mean Average Precision: 25.67 • Our method: 30.95 (Smith-Waterman, Window size 128×128 px) Method cons and pros • Scale-change, shear invariant • Flipping, rotation of 90° invariant (with projections re-ordering) • Not fully rotation and camera viewpoint change (tilt) invariant • Method handles with multiple occurrences of the queried sub-image in one DB image • Sequence of letters ≈ time series => indexable (contrary to RANSAC,…) Future work • Performance – Indexing – Features quantization • Quality – Rotation invariance – Lower precision (too many false positives) – Large windows (more than one window) Conclusion • Sub-Image Retrieval – Features forms an alphabet – Geometric consistency validation using sequence alignment methods – (Sliding) windows to avoid the noise