Transcript Document
Multimedia Indexing and Retrieval Kowshik Shashank Project Advisor: Dr. C.V. Jawahar Problem Statement “Develop efficient algorithms for a real time, private multimedia database” Applications Defense systems Surveillance systems Image/Video collections (under copyright notices) Web 2.0 Web image search Database Feature Extraction Indexing Similarity Measure Query Feature Extraction Result Indexing Schemes Hierarchical Structures Vocabulary Trees Hashing Private Retrieval In Hierarchical Structures Querying in CBIR Feature vector Query Image …….. Private Content Based Image Retrieval 1. The user extracts the feature vector of the query image, say fquery. 2. The user asks for the data stored in the root node of the indexing structure. 3. fquery and the information are used to decide whether to access the left or the right sub-tree. 4. The user frames a Query Qi to access the node at level i. 5. The database replies with Ai for the query Qi . 6. The user performs a function f( Ai ) to obtain the information at the node. Go to step 3. Private Content Based Image Retrieval Feature vector (fquery) fquery, f(A1) fquery, f(A2) Root Info Q1 A1 Q2 A2 …….. Quadratic Residuosity assumption Consider a natural number N = p. q where p, q are large prime numbers. Construct a set z*N Z N* x | 1 x N, gcdN, x 1 . x2 Z N* and x, y `y` is called a Quadratic Residue (QR), if x | y = else `y` is called a Quadratic Non-Residue (QNR). Construct a set YN with equal number of QRs and QNRs Quadratic Residuosity Assumption: Given a number `y` YN, it is predictably hard to decide whether `y` is a QR or a QNR. Basic Rules QNR * QNR = QR QNR * QR = QNR QR * QR = QR Viewing the nodes in a level Querying on a Linear Database Q1 Q2 Q3 Q4 1 0 1 0 ith QR QR User QNR QR Database Q ith 1 QR2 QR QNR2 0 1 0 QR Database User A Q12 Q2 Q32 Q4 A[i] = Q[i] if 0 Now the user decides on the ith element as QR or QNR and decides 2 = in Q[i] 1 upon the data at the ithA[i] index the ifdatabase. Converting to 2D database mxn ….. QNR QR ….. QNR QR …. …. …. …. ….. QR Frame a query of length ‘m’ with a QNR in the position of the row in which the node occurs mxn QR 0 1 ….. 0 QNR ….. 1 1 0 …. 1 …. ….. …. 1 …. 1 QR The database forms a m x n matrix with the first bit of information mxn QR2 QR2 ….. QR2 QR QNR QNR2 ….. QNR QNR Multiply along the columns QNR QR ….. ….. …. …. QR …. …. Ai QR2 QR2 QR QNR Put the square of the number if the bit value is 1 else retain the same number Framing the Query and Reply If the user is interested in the data at node (x,y) Frame a query of length m in which the xth value is a QNR and rest are QR. The database computes the reply Ai of length n and returns to the user. If the value of Ai[y] is a QR then the value is 1 else 0. Complexity of the algorithm The communication complexity is O(m) on the user side and O(n) on the server side. Hence the communication complexity is O(max(m,n)) If m = n = 2i , the communication complexity is Extension to other Hierarchical Structures Hierarchical Structures Number of nodes at each level. Information at a node. Any number of nodes can be converted into a ‘m x n’ matrix. Any information can be represented in binary format. If the user has the data about the indexing structure and the format of the information stored at a node, the algorithm can be simulated for any hierarchical structure. Results KD Tree and Corel Database Corel Database consists of 9907 images. Color feature extracted as color histogram with 768 dimensions. Average Retrieval Time: 0.596 secs Sample Results Results Vocabulary Tree and Nister Dataset Nister Dataset consists of 10,200 images. SIFT features used to obtain visual words. Vocabulary size of 10000 visual words. Average Retrieval Time: 0.320 secs Sample Results Results Vocabulary size was varied to test the scalability of the algorithm. As the size increases, the size of the tree increases causing more data to be exchanged, thus increasing the average retrieval time. Results LSH and Corel Dataset LSH – Locality Sensitive Hashing 90 hash functions each having 450 bins on an average. Two level hierarchy. Average Retrieval Time: 0.221 secs Confusion metric was varied to obtain various levels of privacy. As confusion metric decreases, the data exchanged decreases thus giving faster retrieval times. Results The algorithm was tested for its scalability. Synthetic datasets to the tune of a million images were used to test the practicality of the algorithm. Dataset Size Query Time(in secs) 210 0.005832 212 0.008856 214 0.012004 216 0.037602 218 0.129509 220 0.261255 Conclusion We have addressed the problem of private retrieval in Image databases. The algorithm is shown to be customizable for all hierarchical structures as well as Hash based Indexing. Experimental study shows that the algorithm is accurate, efficient and scalable. Algorithm is fully private and feasible on large image databases using the state of art indexing schemes. Demonstrated a near linear operating region for image databases, where the trade off between privacy and speed is feasible. mxn mxn Qi 0 1 ….. 1 QR 1 0 ….. 1 1 0 ….. 1 QNR …. …. …. ….. 1 1 0 ….. 1 1 0 mxn mxn QR QR2 ….. QR2 QR QR2 ….. QR2 QNR2 QNR ….. QNR2 QNR2 QNR ….. QNR2 Ai …. QR ….. QR2 …. …. …. …. …. QR2 QR2 QR ….. QR2 QR QNR ….. QR …. 1 …. ….. …. 1 …. 0 QR