Presentation to VII International Workshop on Advanced Computing

Presentation to VII International Workshop on Advanced Computing

Presentation to VII International Workshop on Advanced Computing and Analysis Techniques in Physics Research October , 2000 Title of the Talk Singular Value Decomposition (SVD) to simplify features recognitions analysis in very large collection of images F.Guillon D.J.C Murray , SourceWorks Consulting Inc and Philip Desautels ,Ereo Inc. 2 3 Introduction

Internet was built for slow speed modems Broadband adoption will cause rapid rich media adoption Ereo is developing the first search engine (for images) that identifies and indexes the content and context of rich media files Goal is to answer : find one or more similar IMAGES Ereo builds the largest most intelligent image database on the web 4

Insatiable Thirst for Bandwidth Bandwidth and content fuel one another Reinvention of Web 28.8 (text) to Broadband More Bandwidth More Rich Media Content Cycle repeats itself Lack of Tools for Broadband Medium 2000 JUPITER COMMUNICATIONS PUB. 2/00 5

Ereo Addresses The Markets Needs Next-Gen Rich Media Search Focus on Image Content and Contextual Analysis Most powerful search tools Most Relevance Biggest Database 6

Ereo Technology Our Competitive Positioning RELEVANCY Ereo WorldWide 1.0 Ereo OnSite V 2.0 Ereo OnSite V 1.0 More Like This Rich Media Database Size 7

Ereo Technology Basic Problem: Problem Simple Image Search in a Database of 1 Million Images based on color only will required searching for similar vectors in a high-dimensional space . Each Image Color Vector represents the Color Histogram representation however the number of possible colors is large (16,777,216 values for the RGB color model ) . At run-time the similarity search cannot afford this highdimensional space cost so SOME DIMENSIONALITY REDUCTION IS NEEDED Solution SVD1 ( Singular Value Decomposition ) Tool targeted to PCA (Principal Component Analysis) Dimensionality Reduction for the Color-Image Vector Space for Color Similarity Application Patent Pending under The United States Patent and Trademark Office 8

SVD Technique : Basic SVD methods deal with solving difficult linear-least squares problems such as the terms in documents case and here colors in images They are based on the theorem of Linear Algebra: Any M x N matrix A whose number of rows M is greater than or equal to its number of columns N can be written as the product of an M x N columnorthogonal matrix U , an N x N diagonal matrix W of singular values and the transpose of an N x N orthogonal matrix V: w1 A

= U w2 WN VT 9 SVD Solution We can envision building a A matrix corresponding to the 16 M Color Histogram of a stack of images upon which we would like to do Image Color Similarity Comparison. In order that the SVD process can be a usefull empirical

type of model,we need to demonstrate that we can build a A matrix that is Sparse 10 SVD Implementation / Expt We use the SVD package (SVDPACKC ) from the Net Lib repository , in particular we used the Lanczos and subspace iteration-based methods for determining several of the largest singular triplets (singular values and corresponding left- and right-singular vectors, the U and V matrix ) for large sparse matrices. Test Run: Stack of 1999 jpeg images ( 133 x 100 pixels) : 6,29 Mb

Use the las2 (Lanczos method) program with modified data requirements Use 16Millions ( RGB color model ) color Histogram as starting point (Note R, G, B : discrete range from 0-255 ) We try to build a sparse matrix A of : Columns identify as image id Rows identify as color C index (combination of R, G, B values ) 11 SVD Run/ Results To be able to run the SVD process we have to obtain a matrix sufficiently sparse which means reducing effectively number of colors 16 M to 65,536

In constructing the SVD Sparse matrix we used: 234 Mb of temporary storage to handle 1999 color histograms of 65536 color bins Final sparse matrix formatted using only non-zero values used about 78 Mb SVD process run on a Digital Alpha Linux Machine (Two Alpha 21264 667 MHz CPUs with 4 MB Cache, 1 GB SDRAM) Run time is about 20 min for 200 eigenvalues 12 SVD Results : 700 eigenvalues 4 1 10

8000 eigenvalue 6000 4000 2000 0 100 trace 1 200

300 400 eigenvalues number 500 600 700 13 PCA Dimensionality Reduction The singular value decomposition of the (65536 x 1999) matrix A yields a new 65536 x N matrix T containing the

left singular vectors (equiv of U matrix ) corresponding to the N largest singular values of A . The N largest values retained as much information about the original histograms of the stack of images. The matrix T is used to project 65,536 dimensional color histograms into an N-dimensional space color histograms : H65536 T = H N 14 SVD Results Impact on Similarity

We can compare the similarity of images based on 512 colors bins Histograms versus the SVD Reduced N-Histograms : It is found that for about N = 50 eigenvalues (the most largest values ) we get the same similarity measure of image comparison using the well known P(10) metric . Therefore SVD Process is an efficient empirical method to reduce size of any function describing image properties for similarity purpose. 15 CONCLUSION Singular Value Decomposition Method can be an extremely valuable and simple method of analyzing

data without the necessity of explicit mathematical model and provides data size reduction as well. The method has been successfully proven on text and now can be considered a power full method of similarity comparison based on image properties such as color and possibly morphology of objects (shapes) and textures contained within the image. 16

Recently Viewed Presentations

  • The Three estates - Winston-Salem/Forsyth County Schools

    The Three estates - Winston-Salem/Forsyth County Schools

    Third estate- the rest of French society-the commoners-this, the poorest group, provided most of the country's taxes-these paid for wars, palaces and supported the nobility's lifestyle Directions Today you are going to analyze some political cartoons drawn to represent the...
  •  Essential Question: What were the key ideas of

    Essential Question: What were the key ideas of

    Five concepts formed the core of their beliefs: Reason. ... Separation of powers or direct democracy? Montesquieu. Take power from one king & divide it among 3 branches of gov't that each can limit other branches . Rousseau.
  • S3 Bronze Duke of Edinburgh Award Parent information

    S3 Bronze Duke of Edinburgh Award Parent information

    edofe login site. Timeframes. In class. Timeframe. DofE is more than an expedition! You achieve an Award by completing your own programme of activities in four sections: Volunteering Physical Skills Expedition.
  • Data Teams: Core Comes First -

    Data Teams: Core Comes First -

    (Unit Plan)- follows district projection map with standards deconstructed into student friendly learning targets, assessments and instructional strategies. INTENDED RI.2 Identify the main topic and retell key details of a text.
  • DNA, Chromosomes & Genes

    DNA, Chromosomes & Genes

    Each DNA molecule contains many genes The basic physical and functional units of heredity What is a GENE? A specific sequence of bases Sequences carry the information needed for constructing proteins Proteins provide the structural components of cells and tissues...
  • Gangguan Disosiatif - Gunadarma

    Gangguan Disosiatif - Gunadarma

    Namundalamkehidupannyata, Chris Costner Sizemore terpecahkembalimenjadi 22 kepribadian Film BelahanJiwa Empat wanita , Cairo seorangpelukis ( Rachel Maryam ), Farlynaseorangdesainerpakaian ( Dinna Olivia ), Baby Blue seorangarsitek ( Nirina Zubir ) danpsikologArimby ( Marcella Zalianty ) denganempatpermasalahan psikologis yang ...
  • Important points to consider when reading the poem

    Important points to consider when reading the poem

    The remainder of the poem reveals the harsh heartfelt implications of Midas' gift, highlighting the damage it has done to the couple's relationship and their future together. The final line . in the poem sums up Mrs Midas' regret at...

    Cormode et al. (2005) Count-min Sketch: Inserting; When inserting an element, the element's primary key is hashed using all . d. ... Cormode, Graham, and Shan Muthukrishnan. "An improved data stream summary: the count-min sketch and its applications."