com rela¸c˜ao aos prot´otipos escolhidos. Desejamos, assim, estimar prot´otipos nas regi˜oes de sobreposi¸c˜ao de instˆancias e nas fronteiras entre as classes, visto que s˜ao regi˜oes muito suscept´ıveis a erros de classifica¸c˜ao.
Computando uma MST no grafo completo (Z1, A), obt´em-se um grafo conexo ac´ıclico
cujos n´os s˜ao todas as instˆancias em Z1, e os arcos s˜ao n˜ao direcionados e ponderados
(Figura 3.1b). Seus pesos s˜ao dados pela distˆancia d entre os vetores de atributos de instˆancias adjacentes. Esta ´arvore de espalhamento ´e ´otima no sentido em que a soma dos pesos de seus arcos ´e m´ınima se comparada a outras ´arvores de espalhamento no grafo completo. Os prot´otipos a serem escolhidos s˜ao os elementos conectados na MST com di-
ferentes r´otulos em Z1, isto ´e, elementos mais pr´oximos de classes diferentes (Figura 3.1c).
Removendo-se os arcos entre classes diferentes, tais instˆancias adjacentes tornam-se pro-
t´otipos em S e o Algoritmo 1 pode computar uma floresta de caminhos ´otimos em Z1
(Figura 3.2a). Note que uma dada classe pode ser representada por m´ultiplos prot´otipos
(isto ´e, ´arvores de caminhos ´otimos) e deve existir pelo menos um prot´otipo por classe.
3.2
Classifica¸c˜ao
Para qualquer instˆancia t ∈ Z2, consideram-se todos os arcos conectando t com instˆancias
s ∈ Z1, tornando t como se fosse parte do grafo original (ver Figura 3.2b, onde a instˆancia
t ´e representada pelo triˆangulo no grafo). Considerando todos os poss´ıveis caminhos entre
S e t, deseja-se encontrar o caminho ´otimo P∗(t) de S at´e t com a classe λ(R(t)) de
seu prot´otipo R(t) ∈ S mais fortemente conexo. Este caminho pode ser identificado incrementalmente, avaliando o valor do custo ´otimo V (t) como segue:
V∗(t) = min{V (t), max{V (s), d(s, t)}}. ∀s ∈ Z1. (3.2)
Seja s∗ ∈ Z
1 o n´o que satisfaz a equa¸c˜ao acima (isto ´e, o predecessor P (t) no caminho
´otimo P∗(t)), ou seja, se o custo ´otimo oferecido por s∗ (V∗(t)) for menor do que o custo
atual de t (V (t)), ent˜ao a classifica¸c˜ao simplesmente associa L(s∗) como sendo a classe de
t (Figura 3.2c). Um erro ocorre quando L(s∗) 6= λ(R(t)), ou seja, a instˆancia t ´e ligada a
Cap´ıtulo 4
Campos Aleat´orios de Markov
Campos Aleat´orios de Markov s˜ao modelos probabil´ısticos que podem ser utilizados para integrar informa¸c˜ao espacial contextual em problemas de classifica¸c˜ao de imagens [43, 11]. Tais modelos s˜ao baseados na premissa de que um pixel pertencente a uma determinada classe possui uma probabilidade maior de ter vizinhos tamb´em dessa classe do que qual- quer outra. Os MRFs representam uma generaliza¸c˜ao para duas ou mais dimens˜oes dos processos de Markov unidimensionais, conhecidos como Cadeias de Markov.
Tradicionalmente, duas abordagens distintas foram desenvolvidas. A primeira delas, conhecida como causal, caracterizada por sistemas de vizinhan¸ca n˜ao param´etricos, ´e uma extens˜ao direta dos modelos ocultos de Markov (Hidden Markov Models - HMM). Nessa abordagem, ´e preciso impor um ordenamento artificial para compensar a falta da no¸c˜ao natural de causalidade dos dados espaciais em rela¸c˜ao a s´eries temporais, o que fre- quentemente ocasiona no aparecimento de artefatos direcionais nos campos aleat´orios [71]. Entretanto, uma vantagem dessa abordagem consiste na grande quantidade de ferramen- tas matem´aticas dispon´ıveis envolvendo cadeias de Markov unidimensionais [72, 73]. Na outra abordagem, o ponto de partida foram as ideias e ferramentas utilizadas na mecˆanica estat´ıstica para caracterizar a energia de sistemas f´ısicos de part´ıculas orgˆanicas em um reticulado bidimensional [74]. Nesses modelos, a contribui¸c˜ao de cada part´ıcula para a energia total do sistema depende da intera¸c˜ao de cada elemento com seus vizinhos. Esse desenvolvimento expressa a natureza Markoviana do campo aleat´orio de maneira n˜ao- causal.
A base te´orica para trabalhos que empregam MRFs em processamento de imagens surgiram, principalmente, a partir da d´ecada de 1970 [75, 14]. A partir da´ı, v´arias ou- tras abordagens foram propostas, principalmente em segmenta¸c˜ao e restaura¸c˜ao de ima- gens [76, 15]. Mais recentemente, alguns trabalhos tˆem utilizado campos aleat´orios no contexto de reconhecimento de padr˜oes com o intuito de aumentar a efic´acia dessas abor- dagens [77, 78, 11]. Wu e Ouyang [78], por exemplo, propuseram um modelo h´ıbrido para
4.1. Fundamenta¸c˜ao Te´orica 21
classifica¸c˜ao de imagens utilizando SVM e campos aleat´orios de Markov. Tal abordagem, chamada SVM-MRF, consiste de duas etapas: (i) classifica¸c˜ao dos dados utilizando SVM e (ii) posterior p´os-processamento da imagem utilizando MRF. A ideia consiste, basica- mente, em modelar a imagem classificada como um campo aleat´orio, e o r´otulo de cada pixel atribu´ıdo pelo classificador ´e analisado em rela¸c˜ao `a sua vizinhan¸ca com o intuito de reclassific´a-lo caso atenda `a alguns crit´erios estabelecidos pela abordagem proposta.
Como pode ser notado, a utiliza¸c˜ao de MRF no contexto de an´alise de imagens e reconhecimento de padr˜oes tem crescido ultimamente, principalmente pelo fato da com- plexidade inerente de determinadas imagens, como cenas naturais, por exemplo. Nesses casos, uma classifica¸c˜ao baseada em pixels, muitas vezes, pode levar-nos a resultados n˜ao muito satisfat´orios, podendo gerar o que ´e chamado de “efeito sal e pimenta” (ru´ıdo ou erros de classifica¸c˜ao) sobre as imagens resultantes, quando n˜ao leva-se em considera¸c˜ao a informa¸c˜ao contextual espacial [79, 18]. Portanto, explorar as correla¸c˜oes entre a instˆan- cia e sua vizinhan¸ca pode melhorar o desempenho das t´ecnicas de classifica¸c˜ao baseadas em pixel, uma vez que os pixels adjacentes provavelmente pertencem `a mesma classe. A pr´oxima se¸c˜ao apresenta uma fundamenta¸c˜ao te´orica acerca de campos aleat´orios de Markov.
4.1
Fundamenta¸c˜ao Te´orica
Tem-se que um campo aleat´orio consiste em um conjunto de vari´aveis aleat´orias Y =
{Y1, Y2, . . . , Yn}, sendo que ys´e dito ser uma realiza¸c˜ao de Yse pode assumir valores dentro
de um alfabeto ΣYs, tal que esse campo pode ser caracterizado por uma distribui¸c˜ao de
probabilidade conjunta PY [15, 80, 81].
Assim sendo, tem-se que uma imagem rotulada pode ser modelada por um campo
aleat´orio Y = {Ys|s ∈ Ω}, onde Ω = {(i, j)|1 ≤ i ≤ l, 1 ≤ j ≤ c} denota o conjunto
de ´ındices de locais de um reticulado bidimensional contendo l × c pontos ou pixels. De
modo geral, em imagens rotuladas, assume-se que o alfabeto ΣYs = {1, 2 . . . , C} ´e discreto,
representando os r´otulos para qualquer s ∈ Ω.
Dado um campo aleat´orio, pode-se ainda definir um sistema de vizinhan¸ca sobre ele.
Assim sendo, um sistema de vizinhan¸ca η com rela¸c˜ao a um local s, isto ´e, ηs, pode ser
definido como um subconjunto de Ω tal que ηs = {t|d(s, t) ≤ φ, onde φ denota um limiar
de distˆancia, e d, s ∈ R}, onde cada local t ∈ ηs ´e denominado vizinho de s. Com base
nessa ideia, uma ordem pode ser dada pelo seu n´umero de vizinhos como, por exemplo,
quatro vizinhos na primeira ordem e oito vizinhos na segunda. As trˆes primeiras ordens s˜ao ilustradas na Figura 4.1, j´a que s˜ao as mais utilizadas. Embora a escolha da ordem seja bastante importante, pois interfere na solu¸c˜ao final e no custo computacional, tal problema n˜ao ser´a abordado. Na pr´oxima se¸c˜ao ser˜ao abordados alguns dos modelos de