Searching for information on the web is cumbersome. Given our experiences today, we may not even want to think about searching for multimedia information on the (multimedia) web.

Nevertheless, in this chapter we will briefly sketch one of the possible scenarios indicating the need for multimedia search. In fact, once we have the ability to search for multimedia information, many scenarios could be thought of.

As a start, we will look at two media types, images and documents. We will study search for images, because it teaches us important lessons about content analysis of media objects and what we may consider as being similar. Perhaps surprisingly, we will study text documents because, due to our familiarity with this media type, text documents allow us to determine what we may understand by effective search.

...

Amsterdam Drugport

information

• video surveillance -- monitoring
• telephone wiretaps -- audio recording
• photography -- archive
• documents -- investigations
• transactions -- structured data
• geographic information -- locations, routes

media types

• images -- photos
• video -- surveillance
• audio -- interviews, phone tracks
• documents -- forensic, reports
• handwriting -- notes
• structured data -- transactions

retrieval

• image query -- all images with this person
• audio query -- identity of speaker
• text query -- all transactions with BANK Inc.
• video query -- all segments with victim
• complex queries -- convicted murderers with BANK transactions
• heterogeneous queries -- photograph + murderer + transaction
• complex heterogeneous queries -- in contact with + murderer + transaction

...

information retrieval

Information retrieval, according to  [IR], deals with the representation, storage, organisation of, and access to information items.

To see what is involved, imagine that we have a (user) query like:

find me the pages containg information on ...

information retrieval models

• boolean or set-theoretic models
• vector or algebraic models
• probabilistic models

vector models

• attribute term weighting scheme improves performance
• partial matching strategy allows retrieval of approximate material
• metric distance allows for sorting according to degree of similarity

image query

• obtaining descriptive information
• establishing similarity

content-based description

• objects in image
• shape descriptor -- shape/region of object
• property description -- cells in image

shape

• bounding box -- (XLB,XUB,YLB,YUB)

property

• property -- name=value

example

  shape descriptor: XLB=10; XUB=60; YLB=3; YUB=50   (rectangle)  
  property descriptor: pixel(14,7): R=5; G=1; B=3 
  

definitions

• image grid: $(m\; *\; n)$ cells of equal size
• cell property: (Name, Value, Method)

example

  property: (bwcolor,{b,w},bwalgo) 
  

...

similarity-based retrieval

solutions

• metric approach -- distance between two image objects
• transformation approach -- relative to specification

metric approach

           d(x,y) = d(y,x)
  	 d(x,y)  d(x,z) + d(z,y)
  	 d(x,x) = 0
  

pixel properties

• objects with pixel properties $p\_1,...,p\_n$
• pixels: $(x,y,v1,...,v\_n)$
• object contains w x h (n+2)-tuples

complexity

a set of points in k-dimensional space for k = n + 2

feature extraction

• maps object into s-dimensional space

...

transformation approach

transformation operators

   $to\_1,...,to\_r$ -- translation, rotation, scaling
  

cost

• $cost(TS)\; =\; \%S\_\{i=1\}^\{r\}\; cost(to\_\{i\})$

distance

• $d(o,o\text{'})\; =\; min\; \{\; cost(TS)\; |\; TS\; in\; TSeq(o,o\text{'})\; \}$

advantages

• user-defined similarity -- choice of transformation operators
• user-defined cost-function

operations

   rotate(image-id,dir,angle)
   segment(image-id, predicate)
   edit(image-id, edit-op)
  

...

image repository

• storage -- unsegmented images
• description -- limited set of features
• index -- feature-based index
• retrieval -- distance between feature vectors

mission

Our goal is to study aspects of the deployment and architecture of virtual environments as an interface to (intelligent) multimedia information systems ...

...

query

• document database + string matching

problems

• synonymy -- topic T does not occur literally in document D
• polysemy -- some words may have many meanings

...

effective search

• precision -- how many answers are correct
• recall -- how many of the right documents are returned

precision and recall

  precision = ( returned and relevant ) / returned  
  recall = ( returned and relevant ) / relevant 
  

anomalies

• return all documents: perfect recall, low precision
• return 'nothing': 'perfect' precision, low recall

example

complextity

reduction

• stop list -- irrelevant words
• word stems -- reduce different words to relevant part

...

...

user-oriented measures

• coverage ratio -- fraction of known documents
• novelty ratio -- fraction of new (relevant) documents
• relative recall -- fraction of expected documents
• recall effort -- fraction of examined documents

...

Aesthetics

• intentions -- motives of the artist
• expression -- where form takes over
• representation -- the relation of art to reality

...

5. information retrieval

• (*) What is meant by the complementarity of authoring and retrieval? Sketch a possible scenario of (multimedia) information retrieval and indicate how this may be implemented. Discuss the issues that arise in accessing multimedia information and how content annotation may be deployed.

concepts

• How would you approach content-based description of images?
• What is the difference between a metric approach and the transformational approach to establishing similarity between images?
• What problems may occur when searching in text or document databases?

technology

• Give a definition of: shape descriptor and property descriptor. Give an example of each.
• How would you define edit distance?
• Characterize the notions precision and recall.
• Give an example (with explanation) of a frequency table.

As a project, you may implement simple image analysis algorithms that, for example, extract a color histogram, or detect the presence of a horizon-like edge.

You may further explore scenarios for information retrieval in the cultural heritage domain. and compare this with other applications of multimedia information retrieval, for example monitoring in hospitals.

For further reading I suggest to make yourself familiar with common techniques in information retrieval as described in  [IR], and perhaps devote some time to studying image analisis,  [Image].

1. artworks -- ..., Miro, Dali, photographed from Kunstsammlung Nordrhein-Westfalen, see artwork 2.
2. left Miro from  [Kunst], right: Karel Appel
3. match of the day (1) -- Geert Mul
4. match of the day (2) -- Geert Mul
5. match of the day (3) -- Geert Mul
6. mario ware -- taken from gammo/veronica.
7. baten kaitos -- eternal ways and the lost ocean, taken from gammo/veronica.
8. idem.
9. PANORAMA -- screenshots from field test.
10. signs -- people,  [Signs], p. 252, 253.

6

video annotation requires a logical approach to story telling

content annotation

   singers -- (Opera,Role,Person)
   score -- ...
   transcript -- ...
  

  video v, frame f 
  f has associated objects and activities 
  objects and activities have properties
  

  property: name = value 
  

   (fd,fi) -- frame-dependent and frame-independent properties 
  

   { giver : Person, receiver : Person, item : Object } 
   giver = Jane, receiver = Dennis, object = briefcase 
  

  which videos are in the library 
  what constitutes the content of each video
  what is the location of a particular video
  

  SELECT -- v:[s,e] 
  FROM -- video:<source><V> 
  WHERE -- term IN funcall 
  

  SELECT  vid:[s,e]
  FROM video:VidLib
  WHERE (vid,s,e) IN VideoWithObject(Dennis) AND
  	object IN ObjectsInVideo(vid,s,e) AND
  	object != Dennis AND
  	typeof(object) = Person
  

  
  detector song; ## to get the filename
  detector lyrics; ## extracts lyrics
  detector melody; ## extracts melody
  detector check;  ## to walk the tree
  
  atom str name;
  atom str text;
  atom str note;  
  
  midi: song;
  
  song: file lyrics melody check;
  
  file: name;
  
  lyrics: text*;
  melody: note*;
  
  

  event('twinkle',2,time=384, note_on:[chan=2,pitch=72,vol=111]).
  event('twinkle',2,time=768, note_off:[chan=2,pitch=72,vol=100]).
  

  int melodyDetector(tree *pt, list *tks ){
  char buf[1024]; char* _result;
  void* q = _query;
  int idq = 0; 
  
    idq = query_eval(q,"X:melody(X)");
    while ((_result = query_result(q,idq)) ) {
           putAtom(tks,"note",_result);
           }
    return SUCCESS;
  } 
  

  states: { pic1.gif,...,picn.gif } 
  features: names of people 
  extraction: find people in pictures 
  relations: left-of, ... 
  

  states:  set of frames 
  features:  persons and objects
  extraction:  gives features per frame 
  relations:  frame-dependent and frame-independent information
  inter-state relation:  specifies sequences of frames
  

  Type: object $|->$ type 
  ObjectWithFeatures: $f\; |->\; \{\; o\; |$ object o contains $f\; \}$ 
  ObjectWithFeaturesAndAttributes: $(f,a,v)\; |->\; \{\; o\; |$ o contains f with $a=v\; \}$ 
  FeaturesInObject: $o\; |->\; \{\; f\; |\; o$ contains $f\; \}$ 
  FeaturesAndAttributesInObject: $o\; |->\; \{\; (f,a,v)\; |\; o$ contains $f$ with $a=v\; \}$ 
  

    SELECT M
    FROM   smds source1 M
    WHERE  Type(M) = Image AND
  	 M IN ObjectWithFeature("Dennis") AND
  	 M IN ObjectWithFeature("Jane") AND
  	 left("Jane","Dennis",M)
  

   SELECT M
   FROM smds video1, videodb video2
   WHERE M IN smds:ObjectWithFeature("Dennis") AND
         M IN videodb:VideoWithObject("Dennis")
  

   D-Lib Forum -- www.dlib.org
   Informedia -- www.informedia.cs.cmu.edu
  

  U = user
  I = item
  B = behavior
  R = recommendation
  F = feature
  

  B = [ time = 20sec, rating = r ]
  F = [ artist = rembrandt, topic = portrait ]
  R = [ artist(rembrandt) = r, topic(portrait) = r ]
  

  A = [  p_{1}, p_2 , ... ]
  where p_{k} = [ f_1 = v_1, f_2 = v_2, ... ]
  

   A_{nightwatch} = [ artist=rembrandt, topic=group ]
   A_{guernica} = [ artist=picasso, topic=group ]
  

       d(x,y) = d(y,x)
       d(x,y) <= d(x,z) + d(z,y)
       d(x,x) = 0