Histograma de gradients orientats

Imatge d'un vianant (esquerra) i el seu gradient (dreta)

L'histograma de gradients orientats (HOG) és un descriptor de característiques utilitzat en la visió per computador i el processament d'imatges amb el propòsit de detectar objectes. La tècnica té en compte les aparicions de l'orientació del gradient en porcions localitzades d'una imatge. Aquest mètode és similar a altres descriptors visuals, com ara Edge Orientation Histograms (EOH), Scale-invariant feature transform (SIFT) o Shape context (SC), però es diferencia en el fet que es calcula sobre una densa quadrícula de cel·les uniformement espaiades i s'utilitza la superposició de normalització del contrast local per millorar la precisió.

Navneet Dalal i Bill Triggs, investigadors de l'Institut Francès d'Investigació en Informàtica i Automàtica (INRIA), van descriure per primera vegada el descriptor HOG en un article de la CVPR al juny del 2005. En aquest treball inicial van centrar el seu algorisme en la detecció de vianants en imatges estàtiques, encara que posteriorment també l'utilitzarien per a la detecció d'animals i vehicles en imatges estàtiques, així com per a la detecció humana en vídeos.

Teoria

La idea essencial del descriptor és que l'aparença i forma de l'objecte local dins d'una imatge pot ser descrit per la distribució dels gradients d'intensitat o de les direccions de vores. L'aplicació d'aquests descriptors consisteix a dividir la imatge en petites regions connectades, anomenades cel·les, i per a cada cel·la compilar un histograma de direccions de gradient o orientacions de vores pels píxels dins de la casella. La combinació d'aquests histogrames representa el descriptor. Per a una major precisió, els histogrames locals poden ser normalitzats en contrast mitjançant el càlcul d'una mesura de la intensitat a través d'una regió més gran de la imatge, anomenada bloc, i utilitzar aquest valor per normalitzar totes les caselles dins del bloc. Aquesta normalització es tradueix en una millor invariància als canvis d'il·luminació o ombra.

El descriptor HOG manté alguns avantatges sobre altres mètodes de descriptors visuals. Atès que el descriptor HOG opera sobre caselles localitzades, el mètode es manté invariant a transformacions geomètriques i fotomètriques, a excepció de l'orientació d'objectes. Aquests canvis només es durien a terme en grans regions espacials. D'altra banda, el descriptor permet ignorar el moviment dels vianants sempre que mantinguin una posició més o menys vertical. Així doncs, el descriptor de HOG és particularment adequat per a la detecció humana en imatges.

Implementació de l'algorisme

Càlcul del gradient

El primer pas de càlcul en molts detectors de característiques en pre-processament d'imatge és assegurar valors normalitzats de color i gamma, els quals proporcionen cert impacte al rendiment. Però aquest pas pot ser omès en el descriptor HOG, fent en el seu lloc el càlcul dels valors dels gradients. El mètode més comú és aplicar una màscara derivada en una o ambdues direccions, horitzontal i vertical. Aquest mètode requereix el filtratge de les dades de color o intensitat de la imatge amb els següents filtres kernel: $[-1,0,1]{\text{ i }}[-1,0,1]^{T}.\,$]^T.

Dalal i Triggs van provar altres màscares més complexes, com ara les màscares Sobel 3x3 (Operador Sobel) o màscares diagonals, però aquestes van mostrar pitjor rendiment en els experiments de detecció humana en imatges. També van experimentar amb desenfocament gaussià abans d'aplicar la màscara derivada, però igualment van trobar que amb l'omissió de qualsevol suavització s'obtenien millors resultats en la pràctica.

Orientació binning

El segon pas de càlcul consisteix en la creació dels histogrames de cada cel·la. Cada píxel dins la cel·la representa un cert pes ponderat per a un histograma basat en l'orientació a partir dels valors computats en el càlcul del gradient. Les caselles poden ser de forma rectangular o radial, i els canals d'histograma estan distribuïts de manera uniforme sobre 0-180 graus o 0-360 graus, depenent de si el gradient és "sense signe" o "amb signe", respectivament. Dalal i Triggs van trobar que els gradients sense signe utilitzats en conjunt amb 9 canals d'histograma milloren els resultats en els seus experiments de detecció d'humans. Pel que fa al pes de cada píxel, la contribució d'aquest pot ser o bé la mateixa magnitud del gradient, o bé alguna funció de la magnitud; en proves actuals la magnitud del gradient generalment produeix els millors resultats.

Blocs descriptors

Per tal de tenir en compte els canvis en la il·luminació i el contrast, els punts forts del gradient ha de ser normalitzat a nivell local, el que requereix l'agrupació de les caselles més grans, en blocs espacialment connectats. El descriptor de HOG és llavors el vector d'histogrames de caselles normalitzat de totes les regions de bloc. Aquests blocs normalment es superposen, el que significa que cada casella contribueix més d'una vegada al descriptor final. Hi ha dos blocs geometrics existents: blocs rectangulars R- HOG i blocs circulars C - HOG. Els Blocs R- HOG són generalment reixetes quadrades, representats per tres paràmetres : el nombre de caselles per bloc, el nombre de píxels per casella, i el nombre de canals per histograma de casella. En l'experiment de detecció humana Dalal i Triggs, van trobar que els paràmetres òptims eren blocs de caselles de 3x3, caselles de 6x6 amb 9 canals d'histograma. D'altra banda, van trobar que una certa millora en el rendiment podia ser obtinguda mitjançant l'aplicació d'una finestra espacial Gaussiana dins de cada bloc abans de la tabulació de vots dels pixels a cada casella. Els blocs de R- HOG són bastant similars als descriptors Scale-invariant feature transform (SIFT), però, malgrat la seva obtenció similar,els blocs de R- HOG es calculen en quadrícula denses en una escala única sense alineació i orientació, mentre que els descriptors SIFT es calculen en escala invariant en punts de la imatge clau i es fan girar per alinear l'orientació. A més, els blocs de R- HOG s'utilitzen en combinació per codificar la informació de forma espacial, mentre que els descriptors SIFT s'utilitzen sols.

Els blocs de C-HOG es poden trobar en dues variants : els que tenen una casella, casella central única i aquells amb una casella central angularment dividida. A més, aquests blocs de C - HOG poden ser descrits amb quatre paràmetres : el nombre d'intervals angulars i radials, el radi del bin del centre, i el factor d'expansió per al radi de bins radials addicionals. Dalal i Triggs van trobar que les dues variants principals proporcionen un rendiment igual, i que dos bins radials amb quatre cubs angulars, un centre de ràdio de 4 píxels, i un factor d'expansió de 2 proporcionen el millor rendiment en la seva experimentació. La ponderació gaussiana no proporciona cap benefici quan s'usa en conjunció amb els blocs de C - HOG .

Bloc de normalització

Dalal i Triggs van explorar quatre mètodes diferents per a la normalització de blocs. Sigui v el vector no normalitzat que conté tots els histogrames d'un bloc determinat, ||v||_k sigui la seva k-norma, per k=1,2 i $e$ és una petita constant (el valor exacte no és important). A continuació, el factor de normalització pot ser un dels següents:

L2-norm: $f={v \over {\sqrt {\|v\|_{2}^{2}+e^{2}}}}$

L2-hys: L2-norm seguida per la retallada (que limita els valors màxims de v a 0,2) i renormalitzada.

L1-norm: $f={v \over (\|v\|_{1}+e)}$

L1-sqrt: $f={\sqrt {v \over (\|v\|_{1}+e)}}$

A més, l'esquema de L2-Hys es pot calcular prenent en primer lloc L2-norm, retallant el resultat, i després renormalitzant. En els seus experiments, Dalal i Triggs, van trobar que els esquemes L2-Hys, L2-norm, i L1-sqrt ofereixen un rendiment similar, mentre que la L1-norm ofereix un rendiment una mica menys fiable, però, els quatre mètodes mostren una millora molt significativa respecte a les dades no normalitzades.

Classificador SVM

L'últim pas en el reconeixement d'objectes utilitzant el descriptor HOG és alimentar els descriptors en algun sistema de reconeixement basat en l'aprenentatge supervisat. La màquina de vector de suport és un classificador binari que busca un hiperplà òptim com una funció de decisió. Un cop entrenat amb les imatges que contenen algun objecte en particular, el classificador SVM pot prendre decisions pel que fa a la presència d'un objecte, com un ésser humà, en les imatges de prova addicionals. En les proves de reconeixement humà, Dalal i Triggs van utilitzar el paquet de programari SVMLight de lliure disposició conjuntament amb els seus descriptors HOG per trobar figures humanes en imatges de prova.

Proves

En el seu experiment original de detecció humana, Dalal i Triggs comparen el seu el bloc de descriptors C- HOG/ R- HOG amb les ones generalitzades Haar, descriptors PCA - SIFT i Shape Contex. Les ondetes generalitzades de Haar són ondetes orientades de Haar, i van ser utilitzades en 2001 per Mohan, Papageorgiou i Poggio en els seus propis experiments de detecció d'objectes. Descriptors PCA - SIFT són similars als descriptors SIFT, però es diferencien en el fet que l'anàlisi de components principals, s'aplica als pegats gradient normalitzat. Els descriptors PCA - SIFT van ser utilitzats per primera vegada el 2004 per Ke i Sukthankar i van ser guardonats per superar descriptors SIFT regulars. Finalment, Shape Context utilitza contenidors circulars, similars als utilitzats en els blocs C - HOG, però només tabulen vots basant-se en la presència d'una vora, sense fer distinció pel que fa a l'orientació. Shape Context es va utilitzar originalment el 2001 per Belongie, Malik i Puzicha. La prova va començar amb dos conjunts de dades diferents. La base de dades de vianants de l'Institut Tecnològic de Massachusetts conté 509 imatges d'entrenament i 200 imatges de prova dels vianants als carrers de la ciutat. El conjunt només conté imatges que ofereixen la part davantera o posterior de la figura humana i conté poca variança en l'actitud humana. El conjunt és ben conegut i s'ha utilitzat en una varietat d'experiments de detecció d'humans, com ara els realitzats per Papageorgiou i Poggio el 2000. La base de dades MIT està disponible per a la investigació en. El segon conjunt va ser desenvolupat per Dalal i Triggs exclusivament per al seu experiment de detecció humana a causa del fet que els descriptors HOG funcionaven gairebé perfectament en el conjunt del MIT. El seu conjunt, conegut com a INRIA, conté 1805 imatges de fontografies personals d'éssers humans. El joc conté imatges de persones en una àmplia varietat d'actituds i inclou fons difícils, com escenes de masses, la qual cosa el fa més complex que el conjunt del MIT. La base de dades INRIA està disponible per a la investigació en.

L'enllaç de dalt té una imatge que mostra exemples de la base de dades de detecció humana INRIA . Pel que fa als resultats, el bloc de descriptors C- HOG/ R- HOG treballa comparativament, amb els descriptors C- HOG es manté un lleuger avantatge en la taxa d'errades de detecció amb taxes de falsos positius fixes, i amb els dos conjunts de dades. En el conjunt del MIT,el bloc de descriptors C- HOG/ R- HOG va produir una taxa d'errades de detecció pràcticament igual zero treballant amb una taxa de falsos positius 10e-4. Al set INRIA, el boc de descriptors va produir una taxa d'error de detecció de prop de 0,1 amb una taxa de falsos positius de 10e-4. Les ondetes de Haar generalitzades representen la següent i més alta aproximació de rendiment : les ones produeixen més o menys una taxa d'errada de 0,01 amb una taxa de falsos positius de 10-4 en el set MIT, i aproximadament una fallada taxa de 0,3 en el conjunt de INRIA. Els descriptors PCA- SIFT i Shape context fan una actuació bastant dolenta en els dos conjunts de dades. Tots dos mètodes produeixen una taxa de fallades de 0,1 a una taxa de falsos positius 10-4 en el set MIT i gairebé una taxa de fallades de 0,5 a una taxa de falsos positius 10-4 al set INRIA.

Desenvolupament posterior

Com a part del 'Pascal Visual Object Classes 2006 Workshop', Delal i Triggs van presentar resultats en l'aplicació de descriptors d'Histograma de gradients orientats a imatges d'objectes diferents, de persones, cotxes, autobusos, bicicletes, animals domèstics.

Durant el 2006 en la ‘European Conference on Computer Vision ', Dalan i Triggs van formar equip amb Cordelia Schmid per a aplicar Histogrames de gradients orientats al problema de la detecció de persones en pel·lícules i videos. Essencialment, la seva tècnica implica la combinació del 'regular HOG descriptor' en 'frames' individuals, amb 'new Internal Motion Histograms (IMH)' en parelles de frames subsequents. Aquests 'Internal Motion Histograms' usen les magnituds dels gradients dels camps de flux òptic obtinguts de frames consecutius. Aquestes magnituds dels gradients són usats de la mateixa manera a les produïdes en l'aproximació del HOG descriptor. Al provar el mètode en troços de pel·lícules en DVD, el mètode combinat HOG-IMH donava una taxa d'error aproximat de 0,1x10^(-4) falsos positius.

A la 'IEEE Conference on COmputer Vision and Pattern Recognition in 2006', Qiang Zhu, Shai Avidan, Mei-Chen Yeh, i Kwang-Ting Cheng presenten un algoritme per a accelerar substancialment la detecció de figures humanoides usant 'HOG '. El seu sistema usa 'descriptors HOG' en combinació amb l'algoritme de 'cascade of rejecters', aplicat exitosament al problema de la detecció facial. També, en comptes de dependre de blocs de mida uniforme, usen blocs que varien de grandària, localització i ratio d'aspecte. Per a separar els blocs més útils per a la detecció de persones, fan servir l'algoritme 'AdaBoost' per a seleccionar aquests blocs i inclourels en ’a rejecter cascade’. En les seves proves, l'algoritme va aconseguir rendiment comparable a l'algoritme original de Dalal i Triggs, pero operant a velocitats fins a 70 vegades superiors.

Vegeu també

• Scale-invariant feature transform

Enllaços externs

• Una implementació de Matlab (arxiu mex) (anglès)
• Codi de PCA-SIFT Detecció d'Objectes (anglès)
• Kit d'eines de programari per a la detecció d'objectes HOG (Pàgina web de l'equip de recerca) Arxivat 2009-09-19 a Wayback Machine. (anglès)
• INRIA conjunt d'imatges d'humans Arxivat 2010-05-05 a Wayback Machine. (anglès)
• MIT Conjunt d'imatge de vianants (anglès)