Transcript Slide 1
Private Content Based Image Retrieval Shashank J, Kowshik P, Kannan Srinathan and C.V. Jawahar Is it possible for an image database to respond accurately without any knowledge of the query image. Objective: Quadratic Residuosity Assumption Retrieve results from an image database, while maintaining complete privacy of the query image from the database. • Consider a natural number N = p. q where p, q are large prime numbers. Applications: • Construct a set Z N* : Z • Medical Image Databases • Surveillance Systems • Logo Patent Search • Defense Systems • Web 2.0 • Image based query retrieval * N x | 1 x N, gcdN, x 1 . • `y` is called a Quadratic Residue (QR), if x | y = x2 and x, y else `y` is called a Quadratic NonResidue (QNR). • Construct a set YN with equal number of QRs and QNRs Quadratic Residuosity Assumption: Extension to other Hierarchical Structures • Hierarchical Structures vary in: – Number of nodes at each level. – Information at a node. Results and Discussions • KD Tree and Corel Dataset – Color Histogram (768 dimensions) – Retrieval Time: 0.596 secs • 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. • Vocabulary Tree and Nister Dataset – SIFT features – Vocabulary of 10000 visual words. – Retrieval Time: 0.320 secs Given a number `y` YN, it is predictably hard to decide whether `y` is a QR or a QNR. Basic Properties: PCBIR Algorithm • KD Tree – Similar to binary tree – Each node contains split dimension and split value. QNR x QNR = QR QNR x QR = QNR QR x QR = QR 2. The user first asks the database to send the information at the root node. Q1 fquery, f(A1) A1 3. Using fquery and the information received, the user decides whether to access the left subtree or the right subtree. Q2 …….. fquery, f(A2) A2 Related Work • Blind Vision by S. Avidan and M. Butman • Apply secure multi-party techniques to vision algorithms. PCBIR on a Binary Search Tree 1 ….. 1 QR 1 0 ….. 1 1 0 ….. 1 QNR 1 0 ….. 1 1 0 ….. 1 QR QR mxn QR2 ….. QR2 QNR2 QR2 …. mxn QNR2 QNR2 QNR ….. QNR2 QR ….. QR2 QR2 QR ….. QR2 QR QNR ….. QR …. Ai …. ….. …. QNR …. QR QR2 …. …. ….. QR2 • Multi-party protocols are inefficient compared to our tailor made solution. …. 0 …. 1 …. ….. …. 1 …. 0 …. 6. The user using the data obtained from Ai and fquery decides which subtree to move next to. – Branch factor depends on vocabulary size. – Each node contains representative visual words of its children. Root Info Feature vector (fquery) 5. The database returns a reply Ai for the query Qi. – Used to achieve partial privacy. – 90 Hash functions with 450 bins each. – Retrieval Time: 0.221 secs • Vocabulary Tree 1. Extract feature vector of the query image say fquery. 4. In order to get the data at the node to be accessed, the user frames a query Qi where i indicates the level in which the node occurs. • LSH and Corel Database Formulation of Qi and Ai Center for Visual Information Technology International Institute of Information Technology, Hyderabad, INDIA http://cvit.iiit.ac.in • They need privacy in both directions while PCBIR demands in one direction only.