Memoria PIV I (2015)

Trabajo Español
Universidad Universidad Politécnica de Cataluña (UPC)
Grado Ingeniería de Sistemas Audiovisuales - 3º curso
Asignatura (PIV) Procesado de Imagen y Video
Año del apunte 2015
Páginas 6
Fecha de subida 13/03/2016
Descargas 10

Vista previa del texto

 ​ Oriol Bernal Poch  Eduard Torres Romero    Memoria PIV:​  Ejercicio de programación I    1. Presentación del problema  El  problema  que  se  nos  presenta  es  la  recuperación  de  un  conjunto  de  imágenes  a  partir  de  otra,  previamente,  dada  siguiendo  el  criterio  de  similitud  dentro  de  una  base  de  datos.  Para  ello  contamos  con  ciertas  limitaciones,  debemos  reducir  el  tiempo  de  trabajo  al  máximo  y,  únicamente, podemos utilizar el histograma en escala de grises de la imagen.    2. Razonamiento y justificación de las elecciones hechas  El  primer  problema  que  se  nos  plantea  es  el  cálculo  de  los  histogramas  de  una   serie  de  imágenes  pertenecientes  a  una  base  de  datos.  Es  importante  indexar  estos  histogramas  y  guardar  el  resultado  ya  que  su  cálculo  es  muy  costoso.  De  esta  forma  el  algoritmo  solo  se  ejecutará cada vez que se actualice la base de datos.  El  segundo problema es poder encontrar un criterio para decidir qué imágenes se parecen más  entre  ellas.  Para  ello  podemos  usar  el  criterio  de  la  búsqueda  del   error  cuadrático  medio  (MSE)  inferior  o  por  el  contrario,  calcular  la  correlación  y  buscar  el  valor  más alto. Además  también  probaremos  la  eficiencia  con  el  uso  de  la  desviación  absoluta  media  (MAD)  para  intentar conseguir mejores resultados.  Una  vez  realizados  los  algoritmos,  debemos  encontrar  la  forma  de  evaluarlo.  Para  ello  se  usarán  las  curvas  de  “Precision  &  Recall”,  una  métrica  típicamente  empleada  en  el  rendimiento de los sistemas de reconocimiento de patrones.    2.1 ­ Cálculo de los histogramas.  La  solución  al  primer  problema  es  un  simple  algoritmo  que  calcula  los  histogramas  de  cada  imagen  de  la  base  de  datos  con  una  cantidad  específica  de   bins (niveles de gris) y los guarda  en  una  matriz.  Des  esta  forma  obtenemos  como  resultado  una  matriz   de  NxM  dónde   N es el  número  de  bins  y  M  es  el  número  de  imágenes.  Finalmente,  se  exporta  esta  matriz  a  un  fichero  que  podrán  cargar  los  algoritmos  posteriores  para  así  evitar  el  coste  que  supone  la  búsqueda de los histogramas.  El algoritmo propuesto es el siguiente:    clear;  histo_levels=150;  directorio='C:\Users\Edu\Documents\MATLAB\3A\Prog1\BD\';  HISTOS=Histo_BD(histo_levels, directorio);  save('Histogramas','HISTOS');    function [HISTOS] = Histo_BD(num_niv, directorio)  lee_archivos = dir(strcat(directorio,'*.jpg'));   HISTOS = zeros(num_niv,1);  disp('Analizando base de datos:');  for k = 1:length(lee_archivos) %Recorre número de archivos guardados en el directorio  disp(k);  [counts,binLocations]=imhist(rgb2gray(imread(strcat(directorio,lee_archivos(k).name)) ),num_niv);      HISTOS=[HISTOS,counts];  end  HISTOS(:,1)=binLocations;  end    2.2 ­ Comparación de los histogramas.  Para  realizar  la  comparación  usaremos  tres  algoritmos  distintos  y,  posteriormente,  se  analizará cual es el mejor.   ● MSE  En  estadística​ ,  el  error  cuadrático  medio  (ECM)  de  un  estimador  mide  el  promedio  de  los  errores  al  cuadrado,  es  decir,  la  diferencia  entre  el  estimador  y  lo  que  se  estima.    Éste se define como:      donde   es un vector de n predicciones y   es el vector de los verdaderos valores.    ● MAD  Es  un  estimador  parecido  al  MSE  pero  sin  elevar  al  cuadrado  la  diferencia  de  muestras.  Como  consecuencia,  los  casos  aislados  donde  los  valores  son  muy  diferentes  no  tienen  tanto  peso  como  en  el  método  anterior,  que  al  realizar  el  cuadrado amplificaría los errores locales.    El código que implementa estos dos métodos es el siguiente:    function [ res ] = dif_Histos( hist1, hist2, cuadrado )  %Esta función realiza la resta de dos histogramas y suma el valor absoluto  %de dichos valores para calcular la diferencia entre las imágenes.   %La variable “cuadrado” permite cambiar de método.   switch cuadrado              case 1                  dif_cuadrado= ((hist1­hist2).^2)/length(hist1);                  otherwise                 dif_cuadrado= abs(hist1­hist2)/length(hist1);          end    res=sum(dif_cuadrado);    end      ● Correlation  En  nuestro  programa  se   calcula  la  correlación  mediante  los  coeficientes  lineales  de  Pearson,  que  es  una  medida  de  la  relación  lineal  entre  dos  variables  aleatorias  cuantitativas.  A  diferencia  de  la  covarianza,  la  correlación  de  Pearson  es  independiente  de  la  escala  de  medida de las variables. Para su cálculo se hace uso de  la  función  ​ “corr(x,y)”  de  ​ Matlab​ ,  donde  x  e  y​ i  son  los  vectores  resultado   del  histograma  de  la  imagen  a comparar y de la imagen “i” comparada. El coeficiente de  correlación  de  Pearson  retorna  un  índice  que  puede  utilizarse para medir el grado de  relación de dos variables siempre y cuando ambas sean cuantitativas.  El código del algoritmo es el siguiente:    function​  ​ [​  imagenes ​ ]​  ​ =​  AlgoCorr​ (​  histograma​ ,​  num_imagenes​ )  load​ (​ 'Histogramas.mat'​ );​  %Carga los histogramas como matriz HISTOS.  rix​ =[];​  %Crea la matriz de correlación  for​  i ​ =​ 1​ :​ length​ (​ HISTOS​ (​ 1​ ,:))­​ 1 %Recorre el número de imágenes.  rix​ (​ i​ ,:)=​ corr​ (​ histograma​ ,​ HISTOS​ (:,​ i​ ));  %Calcula la  el  máximo de  la correlación  entre histos.  end  ordenados​ =​ sort​ (​ rix​ );​  %Ordena los resultados de mayor a menor.  for​  i​ =​ 1​ :​ num_imagenes %Recorre las "x" imágenes más parecidas.  imag​ (​ i​ )=​ find​ (​ difs​ ==​ ordenados​ (​ i​ ),​ 1​ )­​ 1​ ; %Encuentra la posicion de las "x" imágenes  más parecidas.  end  imagenes​ =​ imag​ ;​  %Devuelve el vector con las "x" imágenes más parecidas.  end    2.3 ­ Gráfica ​ Precision & Recall  Para  poder  evaluar  nuestro  algoritmo  y  dibujar  las  curvas,  es  necesario  conocer  la  base  de  datos  y  saber  cuales   deberían  ser  las  imágenes  más  parecidas.  Para  ello  usamos  una  base  de  datos  de  2000  imágenes  donde encontramos cuatro fotografías, con diferentes puntos de vista  y  pequeñas  variaciones,  de  cada  objeto  diferente.  En  total  tenemos  500  objetos  diferentes en  nuestra base de datos. Esto facilita el estudio de la precisión de nuestro algoritmo.   El código básico quedaría así:     aux=0;  imagenesDevueltas=10;  load('Histogramas.mat');  matrixPrecision=zeros(imagenesDevueltas,1);  matrixRecall=zeros(imagenesDevueltas,1);         imagenReferencia=0;          for i=0:length(HISTOS(1,:))­2          aux=aux+1;              if aux==4                  aux=0;                  imagenReferencia=imagenReferencia+4;              end              if nombreImagen==archivos(i+1).name;                  ref=[imagenReferencia, imagenReferencia+1, imagenReferencia+2,  imagenReferencia+3];                  count=0;                  for j=1:imagenesDevueltas;                      if  listaImagenes(j)==ref(1)||listaImagenes(j)==ref(2)||listaImagenes(j)==ref(3)||listaIm agenes(j)==ref(4)                          count=count+1;                      end                      precision(j)=count/j;                      recall(j)=count/4;                  end                  matrixPrecision=[matrixPrecision, precision'];                  matrixRecall=[matrixRecall,recall'];              end              end   matrixPrecision(:,1)=[];   matrixRecall(:,1)=[];   meanPrecision=(sum(matrixPrecision')/length(matrixPrecision(1,:)))';   meanRecall=(sum(matrixRecall')/length(matrixRecall(1,:)))';      3. Resultados obtenidos    3.1. Curva Precision & Recall     3.2. Tiempo de cálculo en obtener resultados para una imagen query   MAD: Elapsed time is 0.077578 seconds.  MSE: Elapsed time is 0.074379 seconds.  Correlation: Elapsed time is 0.624349 seconds.  3.3 Volumen (MB) de todos los descriptores de la base de datos   El  volumen  de  descriptores  usados  es   muy  similar  en  los  tres  métodos  testeados,  puede variar en dos o tres descriptores.    4. Análisis de los resultados  Los  resultados  han  sido  satisfactorios  al  obtener  una  precisión  y  una  exhaustividad  (recall)  muy  cercanas   al  punto   (0,5,  0,5).  No  obstante,  aún  nos  situamos  muy  lejos  del  ideal  (1,1).  Esto  se  debe  a  la  limitación   impuesta  de,  únicamente  usar  el  histograma  en   escala  de  grises,  omitiendo  la  información  de  color.  Además  el  uso  de  algoritmos  de  reconocimiento  de  formas  y  métodos  que  trabajan  con  árboles  de  decisión  pueden  aumentar  notablemente  la  eficiencia del programa.   Pero  aún  así,  para  analizar  la  eficiencia  de  nuestro  algoritmo  buscaremos  las  curvas  de  Precision  and  Recall   para  histogramas  que  usen  diferentes  números  de bins. El objetivo es la  reducción del tiempo de cálculo sin perder información (o la efectividad del algoritmo).  Los resultados obtenidos son los siguientes:      Como  podemos  observar,  al  reducir  el  número  de  bins  de  150  a 100 se produce una pequeña  mejora  del  algoritmo.  Obtenemos  mejores  resultados  con  un  tiempo de ejecución  menor, por  lo  tanto  elegimos  el  valor  de  100  niveles  para  el cálculo de histogramas de las imágenes y su  posterior  comparación.   Para  valores  menores  de  ​ bins  podemos  observar  que  los  datos   obtenidos  son,  ligeramente,  inferiores.  Gracias  a  esto  podemos  ratificar  que   la  mejor  opción  ronda los 100 ​ bins​ .  5. Posibles mejoras  Una  posible  mejora  para  reducir  el  tiempo  de  ejecución   podría  ser  indexar,  junto  a  los  histogramas  de  las  imágenes,  información  sobre  el  parecido  entre  ellas,  de  forma  que  a  la  hora  de  comparar  imágenes  no  lo  hiciéramos  con  todas  ellas,  que  puede   llegar  a  ser  un  cálculo muy costoso, sino que se realizaría con solo una parte de la base de datos.  Al  realizar  el   cálculo  de  los  histogramas  en  escala  de  grises  se  produce  una  considerable  pérdida  de  información,  por  lo  tanto  si  se  realizara  un  algoritmo  de  comparación  con  tres  histogramas  (R,G,B)  los  resultados  serían  más  fiables,  aunque,  por  contra,  el  tiempo  de  ejecución aumentaría.  Además,  quizás  un  estudio  preliminar  del  fondo  de  la  imagen  o  de  ciertas  características,  como,  por  ejemplo,  las  formas  que  aparecen  podrían  simplificar los cálculos de comparación  (cargando  más  trabajo  a  ​ Algo1​ ).  Así,  podríamos  crear pequeñas subsecciones o subgrupos de  imagen para evitar la comparación con cada una de ellas.   Otro  método  que  podría  mejorar  el  sistema  es  el  uso  de  algoritmos  con  árboles  de  decisión  que  simplificaría  la   búsqueda  a  simples  “preguntas”.  Aún  así,  todo  esto  supondrá  un notable  aumento del tiempo de cálculo, por eso es necesario conocer a  priori qué precisión le pedimos  al algoritmo.      ...