課程名稱︰多媒體資訊分析與檢索 課程性質︰選修 課程教師︰徐宏民 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰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