Vés al contingut

Reconeixement de patrons

De la Viquipèdia, l'enciclopèdia lliure

El reconeixement de patrons, també anomenat lectura de patrons, identificació de figures o reconeixement de formes, és un procés de classificació per categories de qualsevol tipus de mostres mitjançant dades observades o mesurades.

El reconeixement de patrons en camps com la informàtica, l'enginyeria i les matemàtiques està basat en un procés fonamental que es troba en la majoria d'accions que realitzen els éssers vius.

Sistema bàsic de reconeixement de patrons

[modifica]

Els patrons s'obtenen a partir dels processos de segmentació, extracció de característiques i descripció, on cada objecte queda representat per una col·lecció de descriptors. El sistema de reconeixement assigna cada objecte a la seva categoria o classe (conjunt d'entitats que comparteixen alguna característica que les diferència de les altres). Per tal de reconèixer els patrons se segueixen una sèrie de processos:

  1. Adquisició de dades: Mitjançant un sensor es recullen fidelment els elements de l'univers a ser classificats.
  2. Extracció de característiques: A partir d'un mecanisme que extreu la informació útil, eliminant la informació irrellevant.
  3. Selecció de variables: Estableix les característiques més determinants per poder classificar els patrons.
  4. Classificació: Etapa de presa de decisions, en la qual s'assigna a la categoria apropiada els patrons d'una classe desconeguda a priori. És un punt essencial del reconeixement de patrons on es vol classificar un senyal depenent de les seves característiques.


Esquema bàsic d'un sistema de reconeixement de patrons

Adquisició de dades

[modifica]
Esquema de comparació entre el sistema de reconeixement biològic i el sistema de reconeixement de patrons.

El sensor és el dispositiu encarregat de l'adquisició de dades. Aquest ha de ser capaç de transformar magnituds físiques o químiques, anomenades variables d'instrumentació, en magnituds elèctriques. Les variables d'instrumentació depenen del tipus de sensor i poden ser per exemple: temperatura, intensitat lluminosa, distància, acceleració, inclinació, desplaçament, pressió, força, torsió, humitat, etc.

Extracció de Característiques

[modifica]

És el procés de generar característiques que puguin ser utilitzades en el procés de classificació de dades. Ocasionalment ve donat per un preprocessat del senyal, necessari per corregir possibles deficiències en les dades degut a errors del sensor, o bé per preparar les dades de cara als següents processos en les etapes d'extracció de característiques o classificació.

Hi ha dos tipus de característiques:

  • Les elementals: Estan explícitament presents en les dades adquirides i poden ser passades directament a l'etapa de classificació.
  • Les d'alt ordre: Són derivades de les elementals i són generades per manipulacions i/o transformacions en les dades.


Selecció de Variables

[modifica]
Esquema il·lustratiu dels diferents processos de selecció de variables dins d'un sistema de reconeixement de patrons, en funció d'ambdues filosofies.

Consisteix a seleccionar les característiques o trets més adequats per descriure els objectes, localitzant els que incideixen en el problema de manera determinant. Aquesta etapa també pot ser dissenyada dins de la classificació.

La selecció de variables pot diferenciar-se segons els objectius cercats:

  • Per la classificació: La selecció de característiques rellevants, a partir del conjunt total de característiques que descriuen els objectes, es fa per dos motius fonamentals: Millorar la classificació i/o augmentar la velocitat de preprocessat.
  • Per la representació: Decidir quines característiques representen millor a certs tipus d'objectes.


Les estratègies a seguir per dur a terme la selecció de variables:

  • Wrapper: La selecció de característiques es fa utilitzant la informació del mecanisme de classificació.
  • Filter: La selecció es fa amb un criteri independent del classificador, incloent mètodes com:
    • Taules de decisió: Busca un subconjunt mínim de variables que no introdueixi confusió entre classes.
    • ID3: Crea un arbre de decisió i selecciona un conjunt de variables que permeti discriminar entre classes.
    • Teoria de Testors: Busca tots els subconjunts de variables discriminants minimals, amb aquests s'avalua la rellevància de cada variable i se seleccionen aquelles amb major rellevància.

Classificació

[modifica]

La classificació pretén assignar les diferents parts del vector de característiques a grups o classes, basant-se en les característiques ja extretes. En aquesta etapa s'utilitza el que es coneix com a aprenentatge automàtic, l'objectiu del qual és desenvolupar tècniques que permetin un aprenentatge a les computadores.

Acostuma a utilitzar un dels següents procediments:

  • Procediment Geomètric o Clusterització de dades: Els patrons han de poder-se fer gràficament. S'utilitza el càlcul de distàncies, geometria de formes, vectors numèrics, punts d'atracció....
  • Procediment Estadístic: Basat en la teoria de la probabilitat i l'estadística, utilitza anàlisi de variants, co-variants, dispersió, distribució... Se suposa que es té un conjunt de mides numèriques amb distribucions de probabilitat conegudes i a partir d'elles es fa el reconeixement.
  • Sintàctic-estructural: Basat en la cerca de les relacions estructurals que guarden els objectes d'estudi, utilitzant la teoria de llenguatges formals, teoria d'autòmates... L'objectiu és construir una gramàtica que descrigui l'estructura de l'univers dels objectes.
  • Neuro-reticular: S'utilitzen xarxes neuronals que s'entrenen per donar una certa resposta davant determinats valors.
  • Lògic-combinatori: Basat en el fet que la idea sobre el modelat del problema ha de ser el més proper possible a la realitat d'aquest, sense fer suposicions que no estiguin fonamentades. S'utilitza per conjunts difusos i utilitza la lògica simbòlica, circuits combinacionals i seqüencials.

Segons la constància d'un conjunt previ, que permet al sistema aprendre, la classificació pot ser: supervisada, parcialment supervisada o no supervisada.

a) Classificació supervisada o classificació amb aprenentatge:
Esquema sobre la classificació supervisada aplicada dins d'un reconeixement de patrons.
Treballa amb la disponibilitat d'àrees d'entrenament, basant-se en les àrees que coneix a priori i la classe a la qual pertanyen. Aquestes serviran per generar una signatura espectral característica de cada una de les classes. Es denominen classes informacionals en contraposició a les classes espectrals que genera la classificació no supervisada.

Hi ha diversos mètodes de la classificació supervisada com ara:
  • Funcions discriminants: Si són dos classes, es busca obtindre una funció g tal que per un nou objecte O, si g(O) ≥ 0 s'assigna a la classe 1, en cas contrari s'assignarà a la classe 2. Si són múltiples classes es busca un conjunt de funcions g i el nou objecte s'ubica a la classe on la funció pren el valor més gran.
  • Veí més proper: Un nou objecte s'ubica a la classe on està l'objecte de la mostra original que més se li assembla.
  • Xarxes neuronals artificials: Denominades habitualment RNA. Imiten a les xarxes neuronals reals en el desenvolupament de tasques d'aprenentatge.


b) Classificació parcialment supervisada o aprenentatge parcial: En aquest cas només existeix una mostra d'objectes en alguna de les classes definides.


c) Classificació no supervisada o classificació sense aprenentatge:
Esquema sobre la classificació no supervisada aplicada dins d'un reconeixement de patrons.
Utilitza algoritmes de classificació automàtica multivariant en els que els individus més pròxims es van agrupant formant classes. Existeixen dos tipus:
  • Restringida: El nombre de classes en les que s'estructurarà la mostra està prèviament definit.
  • Lliure: El nombre de classes en les que s'estructurarà la mostra depèn exclusivament de les dades.
Hi ha diversos mètodes de la classificació supervisada com ara:
  • Simple Link i Complete Link: Parteixen de grups unitaris d'objectes i van formant unions dels grups més semblants a cada etapa fins complir alguna condició.
  • ISODATA: Es van formant grups que s'ajusten iterativament utilitzant la teoria de probabilitats. En algunes versions es pot fer la unió o divisió d'algun grup.
  • C-means: Es defineix un grup de llavors més semblants, prenent els centroides de cada grup com a noves llavors i s'itera fins que s'estabilitza.
  • Criteris lògic-combinatoris: Els criteris que s'imposen als grups són tals com ser connexes, complets maxims, compactes, etc.


El reconeixement de patrons és més complex quan s'utilitzen plantilles per generar variants. Per exemple, a la gramàtica les frases sovint segueixen el patró "subjecte-predicat", però es requereix cert coneixement de la llengua per detectar el patró. El reconeixement de patrons s'estudia en molts camps, incloent psicologia, etologia, informàtica i processament de senyals digitals.

Aplicacions

[modifica]

Les aplicacions dels sistemes de reconeixement de patrons són infinites, tot i això, algunes de les més rellevants i que s'utilitzen actualment són:

  • Previsió meteorològica: Per classificar totes les dades meteorològiques segons diferents patrons. Amb el coneixement a priori de les diferents situacions que es poden donar, ens permet crear mapes de predicció automàtics.
  • Reconeixement òptic de caràcters: És una de les aplicacions més populars dels sistemes de reconeixement de patrons, ja que els símbols d'escriptura són sovint fàcilment identificables. S'utilitza independentment de si són escrits a mà o a màquina.
  • Reconeixement de la parla: L'anàlisi del senyal de veu s'utilitza actualment en moltes aplicacions, un exemple clar són els teleoperadors informàtics.
  • Aplicacions en medicina: Anàlisis de bioritmes, detecció d'irregularitats en imatges de rajos-x, detecció de cèl·lules infectades, taques a la pell, etc.
  • Reconeixement d'empremtes dactilars: Utilitza les empremtes dactilars, fàcilment identificables, i seguidament detecta i classifica les coincidències de manera que trobar correspondències resulta més senzill.
  • Reconeixement de cares: Utilitzat tant per contar el nombre d'assistents en una manifestació com per detectar un somriure. Actualment hi ha diferents càmeres al mercat amb aquesta opció.
  • Interpretació de fotos (aèries i de satèl·lit): Útil per a propostes militars o civils, com en l'agricultura, la geologia, la geografia, la planificació de ciutats, etc.
  • Predicció de magnituds màximes de terratrèmols.
  • Reconeixement d'objectes: Com aplicacions importants per persones amb discapacitats visuals.
  • Reconeixement de música: Identifica el tipus de música o la cançó concreta que s'està escoltant.

Vegeu també

[modifica]

Bibliografia

[modifica]
  • Richard O. Duda, Peter E. Hart, David G. Stork (2001) Pattern classification (2a edició), Wiley, Nova York, ISBN 0471056693.
  • Dietrich Paulus and Joachim Hornegger (1998) Applied Pattern Recognition (2a edició), Vieweg. ISBN 3-528-15558-2
  • J. Schuermann: Pattern Classification: A Unified View of Statistical and Neural Approaches, Wiley&Sons, 1996, ISBN 0471135348
  • Sholom Weiss and Casimir Kulikowski (1991) Computer Systems That Learn, Morgan Kaufmann. ISBN 1-55860-065-5

Enllaços externs

[modifica]