Near duplicate image detection

Near duplicate image detection A Degree's Project Submitted to the Faculty of the Escola Tècnica d'Enginyeria de Telecomunicació de Barcelona Universitat Politècnica de Catalunya by Joan Ribera Mas In partial fulfilment of the requirements for the degree in (Audiovisual Systems) ENGINEERING Advisor: Mikołaj Leszczuk Barcelona & Krakow, January 2015 2 Abstract The project presents different approaches about how to solve the near duplicate images problem. MPEG-7 descriptors and SIFT transform have been used in order to solve it. The results have been exposed in two different ways. The first one has been focused in the IMCOP project and more precisely on improving the results of the previous paper done in the AGH University [EGL14]. The second one have a more academic approach and the best solution for a given set of images databases have been searched. This problem doesn’t have a general solution and it is necessary to know which database we are using in order to apply the best option. 3 Resum Aquest projecte presenta diverses aproximacions de com resoldre el problema de la detecció de imatges semblants. Descriptors MPEG-7 i transformada SIFT han sigut utilitzats per tal de resoldre aquest problema. Els resultats han sigut exposats de dues maneres. La primera ha estat centrada en el projecte anomenat IMCOP, més precisament, en la millora dels resultats del article anterior realitzat a la Universitat de la AGH [EGL14]. La segona té un enfocament més acadèmic i s’ha buscat la millor solució per un conjunt de bases de dades d’imatges. Aquest problema no té una solució general i es necessari saber amb quina base de dades estem treballant per tal de poder aplicar la millor opció. 4 Resumen Este proyecto presenta diversas formas de resolver el problema de la detección de imágenes parecidas. Descriptores MPEG-7 y la transformada SIFT han sido utilizados para poder resolver este problema. Los resultados han sido expuestos de dos maneras distintas. La primera se ha centrado en el proyecto IMCOP, más precisamente, en la mejora de los resultados del anterior artículo realizado en la Universidad de la AGH [EGL14]. La segunda manera tiene un enfoque más académico y se ha buscado la mejor solución para un conjunto de bases de datos de imágenes. Este problema no tiene una solución general y se necesita saber con qué base de datos se está trabajando para aplicar la mejor opción. 5 Acknowledgements I would like to thank my supervisor Mikołaj Leszczuk all the help that he has given to me during the project. And I want to especially thank the help of my parents encouraging me constantly. 6 Revision history and approval record Revision Date Purpose 0 20/12/2014 Document creation 1 25/01/2015 Document revision DOCUMENT DISTRIBUTION LIST Name e-mail Joan Ribera Mas [email protected] Mikołaj Leszczuk lesz[email protected] Jorge Mata [email protected] Written by: Reviewed and approved by: Date 20/12/2014 Date 25/01/2015 Name Joan Ribera Mas Name Mikołaj Leszczuk/ Jorge Mata Position Project Author Position Project Supervisor 7 Table of contents Abstract ............................................................................................................................ 2 Resum .............................................................................................................................. 3 Resumen .......................................................................................................................... 4 Acknowledgements .......................................................................................................... 5 Revision history and approval record ................................................................................ 6 Table of contents .............................................................................................................. 7 List of Figures ................................................................................................................... 9 List of Tables .................................................................................................................. 11 1. Introduction .............................................................................................................. 12 1.1. Statement of purpose ....................................................................................... 12 1.2. Requirements and specifications ...................................................................... 12 1.3. Work plan ......................................................................................................... 13 1.3.1. Work structure ........................................................................................... 13 1.3.2. Work packages .......................................................................................... 13 1.3.3. Milestone ................................................................................................... 17 1.3.4. Gantt diagram ............................................................................................ 18 1.3.5. Incidences ................................................................................................. 18 2. State of the art ......................................................................................................... 20 2.1. Review of Literature .......................................................................................... 20 2.2. Our work ........................................................................................................... 21 3. Color Descriptors ..................................................................................................... 22 3.1. Introduction....................................................................................................... 22 3.2. Color spaces .................................................................................................... 22 3.3. Dominant Color Descriptor ............................................................................... 23 3.3.1. Extraction .................................................................................................. 23 3.3.2. Similarity Matching .................................................................................... 23 3.4. Scalable Color Descriptor ................................................................................. 24 3.4.1. Extraction .................................................................................................. 25 3.4.2. Matching .................................................................................................... 25 3.5. Color Structure Descriptor ................................................................................ 25 3.5.1. Extraction .................................................................................................. 26 3.5.2. Matching .................................................................................................... 26 3.6. Color Layout Descriptor .................................................................................... 26 8 3.6.1. Extraction .................................................................................................. 27 3.6.2. Matching .................................................................................................... 28 4. Sift Transform .......................................................................................................... 29 4.1. Introduction....................................................................................................... 29 4.2. Extraction ......................................................................................................... 29 4.3. Matching ........................................................................................................... 30 5. Results .................................................................................................................... 31 5.1. Results with CSD.............................................................................................. 31 5.2. Results with the SCD ........................................................................................ 32 5.3. Results with the CLD ........................................................................................ 32 5.4. Results with DCD ............................................................................................. 33 5.5. Results with SIFT ............................................................................................. 34 6. Results with improvements ...................................................................................... 35 6.1. Improvements ................................................................................................... 35 6.2. Results ............................................................................................................. 38 7. Budget ..................................................................................................................... 40 8. Conclusions and future development ....................................................................... 41 Bibliography .................................................................................................................... 43 Appendixes ..................................................................................................................... 46 A. Color Spaces ........................................................................................................... 46 A.1. RGB Color Space .............................................................................................. 46 A.2. YCbCr Space .................................................................................................... 46 A.3. HSV Color Space .............................................................................................. 47 A.4. HMMD Color Space .......................................................................................... 48 B. Databases ............................................................................................................... 49 B.1. Training set ....................................................................................................... 49 B.2. Test set 1 .......................................................................................................... 49 B.3. Test set 2 .......................................................................................................... 50 Glossary ......................................................................................................................... 51 9 List of Figures 1.1: Example of near duplicate images ........................................................................... 12 1.2: Work structure ......................................................................................................... 13 1.3: Gantt diagram .......................................................................................................... 18 1.4: Image before compressor: 1,16 MB ......................................................................... 18 1.5: Image after compression: 834 KB ............................................................................ 18 1.6: Image before compressor: 3,34 MB ......................................................................... 19 1.7: Image after compression: 1,69 MB .......................................................................... 19 2.1: MyFinder algorithm scheme ..................................................................................... 21 2.2: Visual word model ................................................................................................... 21 3.1: Color spaces supported by standards ...................................................................... 22 3.2: Color distribution in a color image ............................................................................ 24 3.3: Schematic diagram of SCD ...................................................................................... 25 3.4: Two images with different local spatial structure of the color but with the same color histogram .................................................................................................................... 26 3.5: Extraction process of Color Layout Descriptor ......................................................... 27 5.1: Results with CSD ..................................................................................................... 31 5.2: Results with SCD ..................................................................................................... 32 5.3: Results with CLD ..................................................................................................... 33 5.4: Results with DCD ..................................................................................................... 33 5.5: Results with SIFT ..................................................................................................... 34 6.1: Illustration of the image rotation for an image. Image sizes: 640x480 pixels ............ 35 6.1: Results with the Kentucky database ........................................................................ 39 6.2: Illustration of image rotation with replacing pixels for an image. Image sizes: 640x480 pixels........................................................................................................................... 36 6.2: Results with the Red Carpet database ..................................................................... 39 6.3: Illustration of image flip + transpose ......................................................................... 36 6.4: Illustration of image flipping. Image size: 640x480 ................................................... 37 6.5: Illustration of image cropping top and down part ...................................................... 37 6.6: Illustration of image cropping in quarters ................................................................. 38 8.1: CSD results without improvements .......................................................................... 41 8.2: CSD results with image cropping method 1 improvements ...................................... 41 8.3: CSD results without improvements .......................................................................... 42 8.4: CSD results with rotation and flipping improvements ............................................... 42 A.1: RGB cube ................................................................................................................ 46 16 Project: Verification of the results WP ref: WP6 Major constituent: Software Sheet 16 of 51 Short description: Verification of the previous results. Planned start date: 08/12/2014 Planned end date: 15/12/2014 Start event: 08/12/2014 End event: 15/12/2014 Internal task T1: Short summary with the problematic images Deliverables: T1 Dates: 15/12/2014 Project: Improvements of the descriptors performance WP ref: WP7 Major constituent: Software Sheet 16 of 51 Short description: Improvements of the performance of the MPEG-7 descriptors Planned start date: 16/12/2014 Planned end date: 07/01/2015 Start event: 04/12/2014 End event: 07/01/2015 Internal task T1: Code and examples. Deliverables: T1 Dates: 07/01/2015 17 Project: Documentation WP ref: WP8 Major constituent: Documentation Sheet 16 of 51 Short description: Final documentation about the whole project. Planned start date: 07/01/2015 Planned end date: 31/01/2015 Start event: 07/01/2015 End event: 31/01/2015 Internal task T1: Documents Deliverables: T1 Dates: 31/01/2015 1.3.3. Milestone WP# Task# Short title Milestone / deliverable Date (week) 1 1 Reading papers about IMCOP Presentation with the supervisor 08/10/2014 2 Searching for the image database Presentation with the supervisor 2 1 Investigation about compression techniques Summary 17/10/2014 3 1 MPEG-7 descriptors investigation Summary 22/10/2014 4 1 Matlab toolboxes Toolboxes 29/10/2014 5 1 MPEG-7 color descriptors implementation. Summary and code. Critical review 07/12/2014 6 1 Verification of the previous results Short summary 15/12/2014 7 1 Improvements. Final review 07/01/2014 8 1 Documentation Final Report 31/01/2015 18 1.3.4. Gantt diagram Figure 1.3: Gantt diagram 1.3.5. Incidences My first assigned task in the project framework was about trying to implement the optimal compressor for each image. While I was working on that, I found that the technology that JPEGmini offers is almost the same that the one that our project needs. JPEGmini [JPM11] is an image optimization technology that reduces the size of JPEG’s by up to 5 or 6 times their original size, while maintaining resolution and perceived quality. The main idea of the JPEGmini is that it imitates the qualities of the Human Visual System (HVS) very closely. This enables the system to apply the optimal amount of compression to each photo. We needed to verify that all the information was true and the performance of the JPEGmini would suit up our project so I decided to test it in my own photos. Figure 1.4: Image before compressor: 1,16 MB Figure 1.5: Image after compression: 834 KB 19 Figure 1.6: Image before compressor: 3,34 MB Figure 1.7: Image after compression: 1,69 MB As we can see at the pictures any differences are notice between the two images and the rate of compression is quite big for the image size. If we use images of 5 or 6 MB we will have more compression. Observing those results we decide to use JPEGmini [JP15] as our project compression technique. So we decided to change the topic of my research to the near duplicate detection images problem. 20 2. State of the art With the fast development of the Internet, and the availability of image capturing devices such as digital cameras, image scanners, the size of digital image collections is increasing rapidly. Efficient image retrieving, browsing and retrieval tools are required by users from various domains, including remote sensing, fashion, crime prevention, publishing, medicine, architecture and so on. For this reason, near duplicate image detection had become one of the most important problems in image retrieval. As more images are published on the Web, and as image manipulation software becomes more powerful and user-friendly, pirating images is becoming increasingly easy. Although digital watermarking techniques exist, these schemes are very difficult to design and there is an inherent trade-off between the robustness of the watermark and the amount of degradation induced in the image. To circumvent digital watermarking, the pirated images are often altered slightly — for instance, by cropping and rescaling. A background, comprehensive review is required. This is known as the review of literature and should include relevant, recent research that has been done on the subject matter. 2.1. Review of Literature These are brief summaries of previous work done in this area:  MyFinder [YZC09]: MyFinder is a user interface application for near duplicate image detection. For each image they first detect a set of interest points using DOG and then they extract the LDP feature for each detected image. They quantize each LDP feature and construct the database with LSH hashing algorithms. Once they have the database constructed for each query they apply the same process of the database and then they use L2 distance and RANSAC geometric verification in order to minimize false matches. 21 Figure 2.1: MyFinder algorithm scheme  Near Duplicate Image Detecting based on Bag of Visual Word Model [LF13]: In this work instead of using LDP feature extraction they use SIFT transform using the visual word model to represent the feature descriptor for each image. Figure 2.2: Visual word model They construct the database with the LSH hash tables and then they compute the distance between two histograms.  Near Duplicate Image Detection: min-Hash and tf-idf Weighting [CPZ08]: They propose a method that uses a visual vocabulary of vector quantized local feature descriptors (SIFT) and for retrieval they exploit enhanced min-Hash techniques. They use standard min-Hash as a similarity measure. 2.2. Our work In our work we use MPEG-7 descriptors and SIFT transform in order to extract the features of our images. We compute different distances depending on which method we are using. 22 3. Color Descriptors For each descriptor, the AGH work team implemented a library for the MPEG-7 standard with the methodology explained at [MSS02]. 3.1. Introduction Color is an important visual attribute for both human vision and computer processing. This chapter provides an overview of MPEG-7 color descriptors. Various factors influenced the selection of these color descriptors. These include: 1. Their ability to characterize the perceptual color similarity, judged by performance of the descriptors in matching images. 2. Low complexity of the associated extraction and matching techniques, as MPEG-7 systems must be able to handle search and retrieval task over large multimedia databases or may be small, portable devices with limited computational power. 3. The size of the coded descriptions, which play an important role in indexing and in transmission of the descriptors over bandwidth-limited networks. 4. The scalability and interoperability of the descriptors. 3.2. Color spaces The color space [RJ1] is used to specify the color space that a given descriptor refers to. It defines four color spaces: RGB, YCbCr, HVS and HMMD. The HMMD is used only in the color structure descriptor. This provides an interoperability between various color descriptors. The table given below shows the color spaces supported by coding standards. Figure 3.1: Color spaces supported by standards The Monochrome color space uses only the luma component (Y) of the YCbCr color space. The explanation of each color space is in the appendices part. 23 3.3. Dominant Color Descriptor The Dominant Color Descriptor (DCD) is defined as: 𝐹={(𝑐𝑖,𝑝𝑖,𝑣𝑖),𝑠}, (𝑖=1,2,…,𝑁) This descriptor gives a description of the representative colors of an image/image region. It consists of the number of dominant colors (N), and a vector of color components (𝑐𝑖) for each dominant color as well as the percentage of pixels (𝑝𝑖) in the image/image region in the cluster corresponding to 𝑐𝑖. A more precise characterization of the color distribution can be obtained with color variance 𝑣𝑖 (describes the variance of color of the pixels in a cluster around the corresponding representative color) and the spatial coherence s (describes the spatial distribution of pixels associated with each representative color wherein high value would indicate that pixels of similar color are co-located). The main application of this descriptor is similarity retrieval in image databases and browsing of image databases based on single or several color values. 3.3.1. Extraction The extraction procedure for the dominant color descriptor uses Generalized Lloyd Algorithm to cluster the pixel color values. The distortion 𝐷𝑖 in the 𝑖th cluster is given as: 𝐷𝑖= ∑ℎ(𝑛) 𝑛‖𝑥(𝑛)−𝑐𝑖‖2, 𝑥(𝑛)∈𝐶𝑖 Where 𝑐𝑖 is the centroid of the cluster 𝐶𝑖, 𝑥(𝑛) is the color vector at pixel n and ℎ(𝑛) is the perceptual weight for pixel n. The perceptual weights are calculated from local pixel statics to account for the fact that human visual perception is more sensitive to light changes in smooth regions than in texture regions. The update rule for the above distortion metric can be derived to be: 𝑐𝑖=∑ℎ(𝑛)𝑥(𝑛) ∑ℎ(𝑛) , 𝑥(𝑛)∈ 𝐶𝑖 3.3.2. Similarity Matching Considering two DCDs, 𝐹1= {(𝑐1𝑖,𝑝1𝑖,𝑣1𝑖),𝑠1𝑖}, (𝑖=1,2,...,𝑁1) 24 𝐹2= {(𝑐2𝑖,𝑝2𝑖,𝑣2𝑖),𝑠2𝑖}, (𝑖=1,2,...,𝑁2) Ignoring the optional variance parameter and the spatial coherence, the dissimilarity 𝐷(𝐹1,𝐹2) between the two descriptors can be computed as: 𝐷2(𝐹1,𝐹2)= ∑𝑝1𝑖 2 𝑁1 𝑖=1 + ∑𝑝2𝑗 2 𝑁2 𝑗=1 − ∑∑2𝑎1𝑖,2𝑗 𝑁2 𝑗=1 𝑁1 𝑖=1 𝑝1𝑖𝑝2𝑗 Where the subscripts 1 and 2 in all variables stands for descriptions 𝐹1 and 𝐹2, respectively, and 𝑎𝑘,𝑙 is the similarity coefficient between two colors 𝑐𝑘 and 𝑐𝑙(more information at [MSS02]). One variation of the above distance is to use the spatial coherence filed. That is the distance that we use to compute the metrics between two descriptors. Is the following one: 𝐷𝑠= 𝑤1𝑎𝑏𝑠(𝑠1−𝑠2)𝐷 + 𝑤2𝐷 Where 𝑠1 and 𝑠2 are the spatial coherencies of the query and target descriptors and 𝑤1 and 𝑤2 are fixed weights, with recommended settings to 0.3 and 0.7 respectively. 3.4. Scalable Color Descriptor The Scalable Color Descriptor (SCD) is a histogram derived descriptor and can provide the global color features when measured over an entire image. It is encoded by the Haar transform and uses the HSV color space uniformly quantized to 255 bins. The figure below shows the respective color distributions in a color histogram. Based on the color distribution the two left images would be considered as more similar compared to the one on the right. In contrast to this the DCT comes with a much more compact representation but with the expense of lower performance in certain applications. Figure 3.2: Color distribution in a color image 25 3.4.1. Extraction Figure 3.3: Schematic diagram of SCD Figure 3.3 shows the block diagram of the SCD extraction process. The output representation is scalable in terms of number of bins, by varying the number of coefficients used. Interoperability between different resolution levels is retained because of the scaling property of the Haar transform. Thus matching based on the information from subsets of coefficients guarantees an approximation of the similarity in full resolution. Furthermore, the feature extraction operation can be scaled to lower levels(less bins in the source histogram). 3.4.2. Matching 𝑙1-norm based matching (sum of absolute differences) can be applied in the Haar transform domain; however, results are not identical with 𝑙1-norm based matching in the histogram domain. We use the second method in order to calculate distances. In this case in which only the sign bit is used the 𝑙1-norm degenerates to a Hamming distance, allowing very low complexity in the distance calculation. 3.5. Color Structure Descriptor The Color Structure Descriptor (CSD) is the generalization of the color histogram that captures some spatial characteristics of the color distribution in an image. It is defined in the HMMD color space using non uniform quantization, specific to Color Structure, between 32-256 colors. A structuring element is defined and moved across the entire image one or more pixels at a time. At each position the color of each pixel covered by the structuring element is determined. For each color the histogram bin containing its count is incremented. The actual descriptor is obtained by normalization and non linear quantization of the final histogram. 32 threshold set in the previous sets is not enough to detect images of the same set so we obtain a lot of false negative detections. Perhaps we could improve our performance if we would train our algorithm with a dataset with the same characteristics as the Kentucky database. 5.2. Results with the SCD The same as the previous descriptor we set a threshold and we decide if an image is near duplicate or not. This are the results: Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Red carpet SCD Training 68 26 1324 26 0.72 0.72 0.98 0.72 Red carpet SCD Test set 1 51 35 1579 16 0.59 0.76 0.98 0.66 Kentucky SCD Test set 2 84 9 1751 92 0.92 0.48 0.95 0.62 Table 5.2: Results with SCD As we can see the results with the scalable descriptor are worse than the ones with the CSD. This is due to the way that the descriptor analyse each image. In the SCD the image histograms at the HSV color space are taking into account so in a dataset like red carpet that we have a common background is very easy to obtain false positives between images of different sets. Also in the Kentucky dataset the results are not satisfactory and we obtain a lot of false negative samples. 5.3. Results with the CLD As the other descriptors, we compute the distance as it is described before. In this case, the distance need some weights so we give to the Y (luminance) the weight of 0.15 and 0.5 for the two chrominance. 33 This are the results: Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Red carpet CLD Training 64 4 1342 34 0.94 0.65 0.97 0.77 Red carpet CLD Test set 1 49 14 1604 24 0.77 0.67 0.98 0.72 Kentucky CLD Test set 2 92 12 1748 84 0.88 0.52 0.95 0.65 Table 5.3: Results with CLD The results with the CLD are slightly better that the ones that we obtained with the SCD but still worse than the ones with the CSD. The main problem with the CLD is setting the threshold in the training set because the distances between images of different sets are quite close so it is difficult to find the best threshold for the optimal model. Also the problem with the CLD is really similar at the one that we had with the SCD because it detects a lot of images as false positive and it doesn’t model well the differences between the images in the same set with images with other sets. 5.4. Results with DCD The results with the DCD are the following ones: Database Method Set TP FP TN FN Precision Sensitivity Specificity Fmeasure Red carpet DCD Training 61 14 1333 36 0.81 0.63 0.97 0.7 Red carpet DCD Test set 1 53 19 1588 21 0.73 0.71 0.98 0.72 Kentucky DCD Test set 2 75 28 1559 102 0.72 0.42 0.93 0.53 Table 5.4: Results with DCD As the results with the SCD or the CLD the DCD descriptor have a lot of problems with images that have a lot of one color in common. The problem that we have when we are working with the DCD and our databases is that numerous images of our databases have a similar background color so when we extract the descriptor from different images but similar background the system detect them as near duplicate. 34 5.5. Results with SIFT Using the MATLAB toolbox described here [VLF07] we were able to create an algorithm that first of all index all the images in a database (SIFT transform of each image) and then matches one image with all the other images in the dataset by the L2 norm between each keypoint or descriptor of the image. Also with this toolbox we were able to set a threshold for the matching process which could tell us the uniqueness of one point. We set the threshold to the default number and we assumed that 89 or more scores between 2 images were enough to say that those images are near duplicate. Here are the results: Database Method Set TP FP TN FN Precision Sensitivity Specificity Fmeasure Red carpet SIFT Training 92 2 1344 6 0.97 0.93 0.99 0.94 Red carpet SIFT Test set 1 65 64 1542 10 0.5 0.86 0.99 0.63 Kentucky SIFT Test set 2 152 6 1754 24 0.96 0.86 0.98 0.91 Table 5.5: Results with SIFT As we can observe the result with the SIFT transform are really good in the Kentucky database. The SIFT transform is able to identify the images of each set and we don’t have a lot of error. On the other hand, SIFT has a lot of problems with the Red Carpet database. This is due to the lack of robustness at modelling similar backgrounds. Different images have a lot of similar keypoints so the algorithm detect them as near duplicate. So the SIFT descriptor is a good technique but with our goals is not the best algorithm. 35 6. Results with improvements Once we obtained the results with all the descriptors we decided to try to improve the results for the descriptor with the best results, in our case the CSD descriptor. 6.1. Improvements We want to improve the performance for both testing sets. First of all, observing the second testing set, the Kentucky database, we have applied the following improvements taking into account the database characteristics:  Comparison the image with the original and the image rotated 90, 180 and 270 degrees. We have maintained the image size [OC14]. Figure 6.1: Illustration of the image rotation for an image. Image sizes: 640x480 pixels  Comparison the image with the original, and the image rotated 90, 180 and 270 degrees applying a replacing pixels technique in the image borders. We have maintained the image size [SE10]. 36 Figure 6.2: Illustration of image rotation with replacing pixels for an image. Image sizes: 640x480 pixels  Comparison the image with the original and the image transpose and flip 90, 180 and 270 degrees. We haven’t maintained the image size. This method is the same as applying a manual rotation at the image visor. Figure 6.3: Illustration of image flip + transpose Image size: 640x480(original and 180 degrees), 480x640(90 and 270 degrees) 37  Comparison the image with the original and the image flipped vertically, horizontally and both ways. We have maintained the image size. Figure 6.4: Illustration of image flipping. Image size: 640x480 Observing the Red Carpet database we figure it out that we could use image cropping in order to detect images from the same set that we previously didn’t detect. We apply the following cropping [CH14]:  Method one: Comparison the image with the original and the image cropped the upper part and the image cropped from the bottom part. The cropping is done in a way that we divide the image by two parts overlapping the middle part in order to have more relevant information. Figure 6.5: Illustration of image cropping top and down part 38  Method two: Comparison the image with the original and the image with the four quarters with relevant information in each quarter. The cropping is done this way because if we divide the image exactly in four quarters the results are worse than if we overlap them with the relevant information of each quarter. Figure 6.6: Illustration of image cropping in quarters The last improvement technique that we apply is to combine the previous described methods. 6.2. Results Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Kentucky Rot (black margins) Test set 2 120 0 1758 56 1 0.68 0.99 0.81 Kentucky Rot (stretched edges) Test set 2 122 0 1758 54 1 0.69 0.99 0.82 Kentucky Rot (without maintaining size) Test set 2 112 0 1758 64 1 0.63 0.99 0.77 Kentucky Flipping Test set 2 112 0 1758 64 1 0.63 0.99 0.77 Kentucky Cropping method 1 Test set 2 110 0 1758 66 1 0.62 0.99 0.77 Kentucky Cropping method 2 Test set 2 106 0 1758 70 1 0.6 0.99 0.75 39 Kentucky Rot + Flip Test set 2 124 0 1758 52 1 0.7 0.99 0.82 Kentucky Rot + Crop Test set 2 114 0 1758 62 1 0.64 0.99 0.79 Kentucky Crop + Flip Test set 2 114 0 1758 62 1 0.64 0.99 0.79 Table 6.1: Results with the Kentucky database Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Red Carpet Rot(black margins) Test set 1 70 20 1681 6 0.77 0.92 0.99 0.85 Red Carpet Rot(stretche d edges) Test set 1 70 18 1681 6 0.8 0.92 0.99 0.86 Red Carpet Rot(without maintaining size) Test set 1 70 10 1681 6 0.87 0.92 0.99 0.9 Red Carpet Flipping Test set 1 70 10 1681 6 0.87 0.92 0.99 0.9 Red Carpet Cropping method 1 Test set 1 74 16 1681 2 0.82 0.97 0.99 0.89 Red Carpet Cropping method 2 Test set 1 70 22 1681 6 0.76 0.92 0.99 0.83 Red Carpet Rot + Flip Test set 1 70 18 1681 6 0.8 0.92 0.99 0.86 Red Carpet Rot + Crop Test set 1 74 24 1681 2 0.75 0.97 0.99 0.85 Red Carpet Crop + Flip Test set 1 74 34 1681 2 0.68 0.97 0.99 0.8 Table 6.2: Results with the Red Carpet database When we use combined methods the rotation and the cropping that we are applying is the one that gave us better results in the previous steps. 40 7. Budget Software Units Price/Unit Total Price Amortization Period Amortization Matlab Licence 1 2586€ 2586€ 10 233€ Ubuntu + Eclipse 1 0€ 0€ 10 0€ Total 2586€ 233€ Salaries Days Hours/Day Price/Hour Total Technician 140 5 8€ 5600€ Total Project cost: 8186€ 41 8. Conclusions and future development In this project, different ways to detect near duplicate images have been presented. Using three different databases we could see the different performance of the color descriptors and the SIFT transform at this approach. As we can observe in the results this problem is not easy to solve so once we obtain the results for each descriptor we decide to improve the best one. When we obtain the final results we can extract two different conclusions. On the one hand, if we focus our work in the IMCOP project and the best performance in the red carpet database have to be obtained we could say that using the CSD is the best way to solve it. Also if they focus the research on detecting all near duplicate images in the database, the image cropping method one is the best approach because we obtain almost a perfect sensitivity only missing two images. The cost of this method is that increasing the sensitivity we are decreasing the precision of the system so we are detecting more images as they were near duplicate. Without improvements: Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Red carpet CSD Training 90 16 1330 8 0.85 0.91 0.99 0.88 Red carpet CSD Test set 1 70 10 1681 6 0.87 0.94 0.99 0.9 Kentucky CSD Test set 2 106 0 1758 70 1 0.6 0.99 0.75 Table 8.1: CSD results without improvements Testing sets with improvements: Database Method Set TP FP TN FN Precision Sensitivity Specificity F-measure Red Carpet Cropping method 1 Test set 1 74 16 1681 2 0.82 0.97 0.99 0.89 Kentucky Cropping method 1 Test set 2 110 0 1758 66 1 0.62 0.99 0.77 Table 8.2: CSD results with image cropping method 1 improvements 48 A.4. HMMD Color Space The HMMD (Hue-Max-Min-Diff) color space is closer to a perceptually uniform color space. The Hue has the same meaning as in the HSV color space. Max and Min components are the maximum and minimum among the R, G, B values, respectively. The Diff component is defined as the difference between max and min. Even though the four components are identified in the name of the color space, one more component, Sum, can be defined as the average of Min and Max components. Only three of the five components are sufficient to describe the HMMD color space. Figure A.5 HMMD color space 49 B. Databases We use three different databases in order to obtain the performance of each descriptor. B.1. Training set Figure B.1: Training set B.2. Test set 1 Figure B.2: Test set 1 50 B.3. Test set 2 Figure B.3: Test set 2 51 Glossary DOG: Difference of Gaussian LDP: Local Directional Pattern LSH: Local Sensitive Hashing RANSAC: Random Sample Consensus