Image Searches Abstraction Invariance 36 350 Data Mining 2 September 2009 1 Medical x rays brain imaging histology do these look like cancerous cells Satellite imagery Fingerprints Finding illustrations for lectures 2 Searching for Images by Searching for Text Assume there s text accompanying the images annotation tags Search those text records with the query phrase Take images which appear close to the query phrase on highly ranked records This how Google does it 3 Sometimes this works perfectly 4 and sometimes it doesn t depends on the text 5 Searching for images by representing images For text we only cared about features and only worked with feature vectors Define numerical features for images and everything carries over Abstraction 6 Abstraction Remove some of the details but keep others Kept details features Then act on abstracta Hopes Simplifies problem Lets you treat many problems similarly 7 Abstract level feature vectors Similarity matching BoW v6 BoW v5 BoW v4 BoW v3 BoW v2 BoW v1 Dimensionality Classification Clustering etc Reduction Text 1 Text 2 Text 3 Text 4 Text 5 Text 6 Concrete level meaningful objects 8 Abstract level feature vectors Similarity matching Topics v6 Topics v5 Topics v4 Topics v3 Topics v2 Topics v1 Dimensionality Classification Clustering etc Reduction Text 1 Text 2 Text 3 Text 4 Text 5 Text 6 Concrete level meaningful objects 9 Abstract level feature vectors Similarity matching Bitmap v6 Bitmap v5 Bitmap v4 Bitmap v3 Bitmap v2 Bitmap v1 Dimensionality Classification Clustering etc Reduction Pic 1 Pic 2 Pic 3 Pic 4 Pic 5 Pic 6 Concrete level meaningful objects 10 Abstract level feature vectors Pic 1 Pic 2 Pic 3 Pic 4 v5 Pic 5 v6 Bag of colors Bag of colors v4 Bag of colors v3 Bag of colors v2 Bag of colors v1 Dimensionality Classification Clustering etc Reduction Bag of colors Similarity matching Pic 6 Concrete level meaningful objects 11 Abstract level feature vectors v5 Network 3 Network 4 Network 5 v6 Motifs Network 2 v4 Motifs Network 1 v3 Motifs Motifs v2 Motifs v1 Dimensionality Classification Clustering etc Reduction Motifs Similarity matching Network 6 Concrete level meaningful objects 12 Need to find right relevant representation Representation concrete abstract interface Go read The Sciences of the Artificial Great methods at the abstract level generally fail if the representation is bad missing what s relevant including what s irrelevant comparing apples to kangaroos A lot of your work will be designing both multicellular sexually reproducing carbon based lifeforms representations 13 Abstract level feature vectors v2 v3 v4 v5 Topics Bitmap Bag of colors Text 1 Text 2 v6 Motifs v1 BoW Dimensionality Classification Clustering etc Reduction BoW Similarity matching Social Network Text 3 Pic 1 Pic 2 Concrete level meaningful objects 14 flower1 flower2 flower3 tiger1 tiger2 tiger3 ocean1 ocean2 ocean3 15 Euclidean Distance of Images Image is MxN pixels each with 3 color components so a 3MN vector Euclidean distance possible and OK for some kinds of noise removal but hopeless even at grouping flower1 with flower2 or slight changes in perspective lighting 16 Bag of Colors If it works try it some more For each possible color count how many pixels there are of that color Use Euclidean distance on color count vectors Too many colors so quantize them down to a manageable number like stemming or combining synonyms 17 flower1 flower2 flower3 flower4 flower5 flower6 flower7 flower8 flower9 tiger1 tiger2 tiger3 tiger4 tiger5 tiger6 tiger7 tiger8 tiger9 ocean1 ocean2 ocean3 ocean4 ocean5 ocean6 ocean7 Multidimensional scaling flower ocean tiger 1 0 ocean5 ocean6 ocean1 flower4 flower9 ocean4 0 5 ocean3 ocean7 0 0 V2 flower7 flower2 flower6 flower8 tiger4 0 5 tiger2 flower1 1 0 flower5 flower1 flower2 flower3 flower4 flower5 flower6 flower7 flower8 flower9 tiger1 tiger2 tiger3 tiger4 tiger5 tiger6 tiger7 tiger8 tiger9 ocean1 ocean2 ocean3 ocean4 ocean5 ocean6 ocean7 1 0 Distances between images 0 5 ocean2 tiger6 flower3 tiger1 tiger8 tiger9 tiger5 tiger7 tiger3 0 0 0 5 1 0 V1 MDS plot of images 18 Representation and Invariance Invariances of a representation how can we change the underlying object without changing the representation What differences does the representation ignore 19 Invariants of bags of words Punctuation and word order Universal words exact count of the of to if using inverse document frequency Word endings if using stemming Grammar context word proximity Send lawyers guns and money vs Sending the Guns lawyers for the money 20 Invariants of bags of colors Small changes in orientation pose some rotations Small amounts of color noise or weird colors Texture 21 Same color counts different textures 22 Non invariants Lighting shadows Occlusion 3D effects Blurring There are good ways to deal with blur from astronomy but full vision is very very hard 23 Breaking an invariance is easy e g add features for textures or sub divide the image and do colorcounts on each part Adding invariances is hard often need to go back to scratch and chose a different representation 24 Similarity search with real images from the web retrievr see notes 25 26 Typically works better with more restricted domains actually pretty good for medical images 27