# Detector Viola Jones

El detector de Viola-Jones descriu un marc de treball per a la detecció d'objectes en imatges en temps real. El detector va ser proposat l'any 2001 per Paul Viola i Michael Jones.
El detector es basa en tres grans aportacions: la utilització de la imatge integral per obtenir una ràpida avaluació de les característiques, un algorisme que aprendrà les característiques per dur a terme la detecció, i un classificador en cascada que descartarà les parts de la imatge que no siguin l'objecte a estudiar per tal de centrar-se en les candidates a si ser-ho.
La creació del detector va ser motivada per la detecció de cares, sent el primer marc de treball capaç de fer-ho ràpidament. Segons Viola i Jones, el detector és capaç de detectar cares en una imatge de 384x288 píxels a una velocitat de 15 imatges/segon utilitzant un ordinador Pentium III a 700 MHz.

## Components del detector
### Característiques i avaluació de la imatge

El detector de Viola-Jones utilitza grups de característiques simples per tal de dur a terme la detecció. La utilització de característiques simples en comptes d'utilitzar els píxels directament es basa en el fet que això permet al sistema operar molt més ràpidament i beneficiarà la codificació en el domini ad-hoc.
Aquestes característiques es divideixen en 4 tipus: dos basades en dos rectangles, una basada en tres rectangles i un altre basat en quatre rectangles. Cadascun d'aquests proporcionarà una informació diferent.
A partir d'aquests rectangles es poden extreure les característiques de la imatge com a avaluacions de la intensitat del conjunt de píxels. La suma de la luminància dels píxels en la regió blanca es resta a la mateixa suma a la regió obscura. El valor obtingut mitjançant aquesta diferència serà el valor de la característica i es pot combinar amb altres formant hipòtesis de les regions d'una imatge.
Les característiques d'aquests rectangles poden ser ràpidament calculades utilitzant una representació intermèdia de la imatge, anomenada imatge integral. Viola-Jones construeixen aquesta imatge prenent la suma dels valors de luminància dels píxels que es troben per sobre i a l'esquerra d'un punt de la imatge. Per tant, per un punt x,y tenim que:
$ii(x,y)=\sum _{a\leq x\ b\leq y}i(a,b)$
on: $ii(x,y)$ és la imatge integral $i(x,y)$ és el valor de la imatge en unes coordenades específiques
La importància d'aquesta imatge integral es basa en el fet que és capaç de calcular ràpidament la suma dels píxels dins d'una àrea determinada de la imatge. Cada suma d'aquesta àrea s'obtindra a partir de quatre referències:
$\sum _{\begin{smallmatrix}A(x)<x'\leq C(x)\\A(y)<y'\leq C(y)\end{smallmatrix}}i(x',y')={\text{sum}}(A)+{\text{sum}}(C)-{\text{sum}}(B)-{\text{sum}}(D).$
Aquest procés es realitza per tot un conjunt d'imatges d'entrenament que contenen l'objecte a detectar, de forma que es puguin trobar de forma més exacta les característiques.

### Classificador

Un cop trobades les característiques dins d'un conjunt d'imatges d'entrenament, cal trobar les que defineixen millor una cara i ajudin a localitzar-la.
Dins d'una imatge de 24x24 trobem un total de 45.396 possibles característiques i això faria impossible avaluar totes les possibilitats en temps reals. Per tant, cal trobar les característiques que defineixin millor l'objecte mitjançant un classificador que s'encarregarà de trobar-les. El detector de Viola-Jones estableix una variant de l'algorisme AdaBoost de Freund i Shaphire. L'elecció d'aquest algorisme ve donada per la seva velocitat d'aprenentatge, on els pesos s'assignen de manera que afavoreixin la classificació de l'objecte, és a dir, assigna uns pesos a les característiques de forma que les característiques que siguin les més probable per l'objecte, tinguin més pes i, per tant, seran les que es tindran en compte.

### Detector de classificadors en cascada

El detector Viola-Jones consisteix a escanejar molts cops la imatge, en diferents posicions i escales. Se senzill d'intuir que la majoria de sub-finestres escanejades no contindran l'objecte, per tant, en comptes de trobar l'objecte, l'algorisme buscarà el no objecte.
Aquest mètode es basa en una cascada de classificadors que classificaran la sub-finestra com objecte o no objecte. Si no és objecte, simplement es descartarà i es passarà a la següent. En canvi es classificarà com a objecte si pasa per tots els classificadors (és a dir que tots els classificadors la consideraran objecte).
Degut a aquest mètode en cascada per tal de decidir si hi ha l'objecte a la imatge o no, la taxa de positius i falsos positius dependrà del nombre d'etapes al classificador en cascada. La taxa de falsos positius pot ser calculada com:
$F=\prod _{i=1}^{K}f_{i}$
On F és la taxa de falsos positius del detector, K és el nombre de classificadors i fi és la taxa de falsos positius calculada pel classificador i. En contraposició, la taxa de detecció del mètode cascada pot ser calculada com:
$D=\prod _{i=1}^{K}d_{i}$
On D és la taxa de detecció del detector, K és el nombre de classificadors i di és la taxa detecció calculada pel classificador i. Per tant, per a una cascada de 32 etapes, obtindrem una taxa de falsos positius de l'ordre de $10^{-6}$.

## Estructura del detector original de Viola-Jones

El detector original que van proposar Viola i Jones conté una cascada de 38 etapes amb un total de 6060 característiques per la detecció de cares. On el primer classificador en cascada utilitza dos característiques i rebutja aproximadament el 50% de les no-cares, mentre que detecta gairebé el 100% de les cares. La següent etapa té classificadors de 25 característiques i les següents 3 etapes tenen classificadors de 50 característiques i així successivament.
El temps d'entrenament fou en una màquina a 466 MHz Alpha Station XP900 de l'ordre de setmanes.

## Aplicacions

El detector de Viola i Jones s'ha utilitzat majorment a la detecció de cares i persones. Però no només s'ha utilitzat en aquest camp, també s'utilitza per detectar tot tipus d'objectes, com mans, detecció de gestos o per exemple, a la indústria de l'automobilisme on s'utilitza per detectar vianants, altres cotxes o senyals de trànsit.

## Popularitat del detector

Aquest detector s'ha fet molt popular degut a la seva velocitat a l'hora de detectar les cares en imatges i per la seva implementació a la llibreria OpencV, on apareix implementat com a funció: cvHaarDetectObjects

## Demostracions

* «Vídeo». Seguiment de cares frame a frame utilitzant el detector Viola & Jones
* Detecció de pell en temps real
* Replicació de moviments facials en un model 3D
* Demostració Arxivat 2017-06-04 a Wayback Machine.

## Bibliografia

* Richard Szeliski, Computer Vision: Algorithms and Applications, Springer, 2010 (anglès)
* Gary Bradski, Adrian Kaehler, Learning OpenCV, O'Reilly, 2008 (anglès)

## Referències

* ↑ Viola and Jones paper for the Second International Workshop On Statistical And Computational Theories Of Vision (anglès) PDF
* ↑ OpenCV 2.0 Reference

## Enllaços externs

* Detección, localización e identificación biométrica de caras en imágenes: métodos y evaluación en el marco NIST-BG (anglès) PDF
* Robust Real-time Object Detection (anglès) PDF
* Viola and Jones' Detector a SiliconIntelligence (anglès)
* Implementació del detector amb matlab (anglès)