課程名稱︰多媒體資訊分析與檢索
課程性質︰選修
課程教師︰徐宏民
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2007/5/16
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
Multimedia Analysis and Indexing - Spring 2007
Name:_____________________________ School ID:_______________________________
Midterm(2:30 pm, Wednesday, May 16, 2007)
Note:
(1) Wtite down your NAME and School ID in the booklet and the test
problem set(this paper). You have to submit them BOTH to TA after
the midterm.
(2) Best luck to you!
I. Co-occurrence texture: (20%)
Please show the three co-occurrence matrices Cd(i,j), specified by different
displacement vectors d((c)-(e)), for a gray image I, which has the gray value
in each pixel.
(1)What are the dimensions of the co-occurrence matrices?
(2)Please show the three co-occurrence matrices with d = (0,1),
d = (1,0), and d = (1,1).
┌─┬─┬─┬─┐
│0 │0 │2 │3 │ ...j... d = (0,1)
├─┼─┼─┼─┤ .┌───────┐
│1 │0 │3 │2 │ .│ │ d = (1,0)
├─┼─┼─┼─┤ i│ │
│2 │1 │0 │0 │ .│ │ d = (1,1)
├─┼─┼─┼─┤ .└───────┘
│1 │2 │1 │0 │
└─┴─┴─┴─┘
(a)Image I (b)Cd(i,j) (c)-(e)
II. Image Similarity and Near-Duplicate Detection (30%)
We are to design a system to efficiently and effectively discover the
near-duplicates (pecture pairs taken at the same site or with a very
similar scene. See the following two example images.) from a very
LARGE databases(i.e., Flickr) with around N user-contributed images.
(N ~= 250 millions). Given an image in the database, the system needs
to show the top K near-duplicate images in the database and their
corresponding near-duplicate scores. You are allowed to compute the
near-duplicate similarities offline.
((1)What might be good candidates for feature representations of
images and their corresponding distance (or similarity) measures? Why?
(2)What is the time complexity to compute all the pair-wise
similarities in the image database? Any algorithms to speed up the
near-duplicate detection (e.g., filtering out irrelevant images
first with low-cost image similarity measures)? What might be the
impact of your proposed approach in reducing the time complexity?
Any tradeoff for accuracy?
(3)With your proposed algorithm, what might be the estimated time
complexity if a new image is inserted into the database (N images)?
Near-duplicates from the images taken by different persons in front of the
Low library of Columbia University, New York.
III. Precision and Recall (25%)
In the retrieved image list of depth 15, we had inspected the retrieved
images and marked the hit (+) at different depths. there are totally
10 ground-truth images. Please
(1)Complete the "recall" at different depths. Note that at depth i,
we are to cvaluate the retrieved results of the first i images
(ranked 1 to i).
(2)Complete the "precesion" at different depths
(3)Please draw the precesion and recall curve of the retrieved results
(at depth 15).
Please use ONLY the recall and precision values where a "hit" occurs.
# 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Hit - + + - + + - - + + + + - + +
Recall
Precision
VI. Quad-tree and KD-tree (25%)
We have 16 points in a 2-dimensional space. Please organize these
points by space decomposition and their corresponding tree structures
in the following two methods:
(1)Quad-tree, which splits the space into 4 equal subspaces and
continues until each leaf node has a single point.
(2)KD-tree, which recursively subdivides points into two halves
(median values are used) using vertical and horizontal lines till
one point left in each leaf.
(1)-a:space decomposition
(1)-b:tree representation in Quad-tree
(2)-a:space decomposition
(2)-b:tree representation in KD-tree
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.98