# Descriptor de la Distribució del Color

El Descriptor de la Distribució del Color (DDC) està dissenyat per capturar la distribució espacial del color en una imatge. El procés d'extracció de les característiques es compon de dues parts, en primer lloc es realitza la selecció del color més representatiu mitjançant una quadrícula i després hi apliquem la Transformada Discreta del Cosinus amb la corresponent quantització.
El color és la característica més bàsica dels continguts visuals, per tant, es poden utilitzar colors per descriure i representar una imatge. L'estàndard MPEG-7 ha testejat el procediment més eficaç per a descriure el color i n'ha seleccionat els que han donat els millors resultats. Aquest estàndard proposa diferents mètodes per tal d'obtenir descriptors visuals, i una de les eines definides per descriure el color és el DDC, que permet descriure la relació de color existent entre seqüències o grup d'imatges.
El DDC captura la disposició espacial dels colors més representatius d'una quadrícula superposada en una regió o una imatge. La representació es basa en els coeficients de la DCT. Aquest és un descriptor molt compacte, altament eficient en la navegació i ràpid en aplicacions de cerca. Es pot utilitzar tant en imatges fixes com en fragments de vídeo.

## Definició

El DDC és una representació del color de resolució invariant i molt compacta, que permet la recuperació d'imatges amb alta velocitat i que ha estat dissenyat per representar de manera eficaç la distribució espacial dels colors. Aquesta característica es pot utilitzar en una gran varietat de recuperacions, ja que es basa en la similitud, en el filtratge del contingut i en la seva visualització. És especialment útil per a aplicacions espacials de recuperació basades en estructures. Aquest descriptor s'obté aplicant la transformada discreta del cosinus (DCT) en una matriu 2D on hi trobem la representació local dels colors en Y o Cb, o Cr de l'espai de color. Les funcions del DDC són bàsicament les següents:
          - Comparació imatge a imatge
          - Comparació videoclip a videoclip
El DDC és un dels descriptors de color més ràpid i precís.

## Extracció

El procés d'extracció d'aquest descriptor de color consta de quatre etapes:
* Divisió de la imatge
* Selecció del color més representatiu
* Transformada DCT
* Exploració en zig-zag
L'estàndard MPEG-7 recomana l'ús de l'espai de color YCbCr en el DDC. Si ho necessita, pot intercanviar diferents espais de color mitjançant aquestes fórmules.

### Divisió de la imatge

En la fase de divisió, la imatge d'entrada (en l'espai RGB de color) es divideix en 64 blocs per garantir la invariabilitat de la seva resolució o del seu escalat. Les entrades i sortides d'aquest pas es resumeixen en la següent taula:
| Entrada etapa 1 | Sortida etapa 1 |
| Entrada d'una imatge [M x N] | Imatge d'entrada dividida en 64 blocs [M/8xN/8] |

### Selecció del color més representatiu

Després de l'etapa de divisió de la imatge, se selecciona un únic color com a representant de cada bloc. Es pot utilitzar qualsevol mètode per escollir el color més representatiu, però l'estàndard recomana l'ús de la mitjana dels colors dels píxels en un mateix bloc com a mostra del color més representatiu, ja que és un procés més simple i l'exactitud de la descripció, en general, podem dir que és suficient. Els resultats de la selecció s'emmagatzemen en una petita imatge icona de mida 8x8. La següent figura mostra aquest procés. Fixeu-vos que en la imatge de la figura s'ha mantingut la resolució de la imatge original per tal de facilitar-ne la seva representació. Les entrades i sortides d'aquesta etapa es resumeixen en la següent taula:
| Entrada etapa 2 | Sortida etapa 2 |
| Imatge d'entrada dividida en 64 blocs [M/8xN/8] | Imatge icona [8x8] |
Un cop s'obté la icona de la imatge s'aplica la conversió de l'espai de color entre RGB i YCbCr.
| Entrada etapa 3 | Sortida etapa 3 |
| Imatge icona [8x8] en l'espai de color RGB | Imatge icona [8x8] en l'espai de color YCbCr |

### Transformada DCT

    ${\begin{array}{l}B_{pq}=\alpha _{p}\alpha _{q}\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}A_{mn}\cos {\frac {\pi (2m+1)p}{2M}}\cos {\frac {\pi (2n+1)q}{2N}},\qquad 0\leq p\leq M-1,\;0\leq q\leq N-1\\\alpha _{p}={\begin{cases}{\frac {1}{\sqrt {M}}},&p=0\\{\sqrt {\frac {2}{M}}},&1\leq p\leq M-1\end{cases}}\qquad \alpha _{q}={\begin{cases}{\frac {1}{\sqrt {N}}},&q=0\\{\sqrt {\frac {2}{N}}},&1\leq q\leq N-1\end{cases}}\end{array}}$
    Fórmula per calcular la DCT d'una matriu 2D
En la quarta etapa, la luminància (Y) i la crominància blau i vermell (Cb i Cr) són transformats en 8x8 DCT, de manera que s'obtenen tres grups de 64 coeficients DCT. Per calcular la DCT d'una matriu 2D utilitzem la fórmula que s'observa a la imatge.
Les entrades i sortides d'aquesta fase es resumeixen en la següent taula:
| Entrada etapa 4 | Sortida etapa 4 |
| Imatge icona [8x8] en l'espai de color YCbCr | 3 matrius [8x8] de 64 coeficients (DCTY, DCTCb, DCTCr) |

### Exploració en zig-zag

L'exploració en zig-zag es realitza amb els tres grups de 64 coeficients DCT, seguint l'esquema presentat a la figura. L'objectiu de l'exploració en zig-zag són els coeficients de baixa freqüència de la matriu de 8x8. Les entrades i sortides d'aquesta fase es resumeixen en la següent taula:
| Entrada etapa 5 | Sortida etapa 5 |
| 3 matrius [8x8] de 64 coeficients (DCTY, DCTCb, DCTCr) | 3 exploracions en zig-zag de la matriu (DY, DCB, DCR) |
Finalment, obtenim aquest conjunt de tres matrius que corresponen als DDC de la imatge d'entrada.

## Comparació

Aquest procés ajuda a avaluar si dos elements són iguals entre ells, i comparant-los, també podem calcular-ne la seva distància. En el cas dels descriptors de color el procés de correspondència ajuda a avaluar si dues imatges són similars. El seu procediment és el següent:
          - Donada una imatge d'entrada l'aplicació intenta trobar una altra imatge amb un descriptor similar en una base de dades.
Si es consideren dos DDC:
          {DY, DCB, DCR}
          {DY ", DCB", DCR "},
La distància entre els dos descriptors es pot calcular com:
          $D={\sqrt {\sum _{i}w_{yi}(DY_{i}-DY_{i}')^{2}}}+{\sqrt {\sum _{i}w_{bi}(DCb_{i}-DCb_{i}')^{2}}}+{\sqrt {\sum _{i}w_{ri}(DCr_{i}-DCr_{i}')^{2}}}$
El subíndex i representa l'ordre de detecció del zig-zag dels coeficients. A més, fixeu-vos que es pot utilitzar el pes dels coeficients (w) per tal d'ajustar el rendiment del procés de l'aparellament. Aquests pesos donen més importància a uns components del descriptor en més que d'altres. Observant la fórmula, es pot extreure que:
          - 2 imatges són idèntiques si la distància és 0
          - 2 imatges són similars si la distància és propera a 0
Per tant, aquest procés d'aparellament permetrà identificar imatges similars mitjançant els descriptors de color. La complexitat del procés per trobar coincidències és baixamb aquest mètode es poden arribar a cerques d'alta velocitat.

## Aplicació

El nostre objectiu és trobar imatges amb colors similars, per tant, hem d'extreure el DDC d'aquestes imatges i després comparar aquestes dades descriptives amb la tècnica de l'aparellament. En conseqüència, podem definir dues parts principals en l'aplicació d'aquest mètode:
          - Generar una base de dades d'imatges per obtenir els seus DDC
          - Cercar similituds entre una imatge d'entrada donada i la base de dades processada
La següent figura mostra el procés d'anàlisi d'una base de dades:
En aquest procés s'analitza una base de dades d'imatges per tal d'obtenir els DDC que les representen. Aquest procés consisteix a carregar una imatge en memòria i calcular-ne el seu descriptor DDC tal com s'explica a la secció anterior. El resultat final és una base de dades dels DDC vinculats a les imatges que es volen representar.
Una vegada que la base de dades d'imatges s'ha analitzat, es porta a terme la comparació entre una imatge d'entrada i la base de dades dels DDC. Amb aquest procés s'obtenen imatges amb colors similars ordenades de major a menor similitud.

## Vegeu també

* MPEG-7
* Descriptors visuals
* Indexació audiovisual
* Transformada discreta del cosinus (DCT)

## Enllaços externs

* Projecte de Fi de Carrera - Descripció i classificació d'imatges a partir del seu color (Sergi Laencina Verdaguer) PDF (anglès)
* J. Stauden i Sirota J. «Relació de descriptors de la imatge visual i semàntica». Arxivat de l'original el 2012-02-07. [Consulta: 15 desembre 2010]. PDF (anglès)
* «Classificació d'imatges mitjançant l'ús de descriptors visuals del MPEG-7.». Arxivat de l'original el 2011-10-01. [Consulta: 15 desembre 2010]. PDF (anglès)
* MPEG-7 Overview Arxivat 2010-02-14 a Wayback Machine. (Color Layout) (anglès)