This thesis presents a technique to detect copied and/or cloned regions in digital images. We present the algorithm DeReC, based on the Discrete Cosine Transform (DCT). DeReC allows us to detect cloned regions in images with lossless compression (PNG) and lossy compression (specifically JPEG, since this is the image compression format most commonly used today). The algorithm consists in generating a set of feature vectors for each pixel in the image using the DCT, after that, using approximated searches with kd-trees and vp-trees, we find the nearest neighbor for each vector in the set; finally these nearest neighbors are validated to determine if the pixels represent a cloned region. The result of the algorithm is a binary map where the cloned regions are shown in white. We present results of multiple experiments where parameters were setted, execution times were measured and the results obtained for PNG and JPEG images were validated. These experiments allow us to measure the performance of DeReC. Additionally, we present a comparison between our results and results obtained with algorithms found in the literature. The results obtained by DeReC are satisfactory, since it is able to detect cloned regions in the formats for which tests were performed (PNG and JPEG), when measuring the performance of the detection we found that it is on par with other proposals.
En esta tesis se presenta una técnica para detección de regiones copiadas y/o clonadas en imágenes digitales. Con este propósito presentamos el algoritmo DeReC, el cual está basado en la Transformada Coseno Discreta (DCT, de sus siglas en ingles). DeReC permite detectar regiones clonadas en imágenes con compresión sin perdida (PNG) y con compresión con perdida (en específico JPEG, dado que este es el formato de compresión de imágenes m as utilizado en la actualidad). El algoritmo consiste en generar un conjunto de vectores de características para todos los pixeles de la imagen, con la ayuda de la DCT, posteriormente por medio de búsquedas aproximadas, utilizando kd - trees y Vp - trees encontramos al vecino más cercano para cada vector del conjunto; finalmente se validan esos vecinos cercanos para determinar si los pixeles que representan pertenecen a una región clonada o no. Como resultado el algoritmo entrega un mapa binario de la imagen, donde muestra en blanco las regiones clonadas y en negro las regiones no clonadas. Se realizan múltiples experimentos, como son ajustes de parámetros, medición de tiempos de ejecución y validación de resultados obtenidos en imágenes PNG y JPEG. Estos experimentos nos permiten medir la efectividad del algoritmo desarrollado. Adicionalmente se hacen comparaciones contra resultados obtenidos por otros algoritmos encontrados en la literatura. Los resultados obtenidos por DeReC son satisfactorios, ya que logra detectar las regiones clonadas en los formatos para los que se realizaron pruebas (PNG y JPEG), al medir la efectividad de la detección encontramos que está a la par de otras propuestas.
