Conducting identity around product models

O algoritmo para segmentação fuzzy, chamado de MOFS - Multi-Objetct Fuzzy Seg-

mentation, foi proposto por Herman e Carvalho [Herman e Carvalho 2001] e é uma so-

lução gulosa1 para a segmentação fuzzy. Neste algoritmo foi utilizado uma estrutura de dados do tipo Heap Binário [Cormen et al. 2001], na qual todos os spels são inseridos com uma chave associadaσc₀ e uma única vez. Os spels são, então, removidos do heap 1_{Um algoritmo guloso sempre faz a escolha que parece ser a melhor no momento [Cormen et al. 2001]}

em uma ordem decrescente do valor finalσc₀. O problema deste algoritmo é que toda vez que o valorσc₀for alterado essa atualização no heap será da ordem O(log N), com N sendo

o número de spels do heap em determinado instante. A complexidade do algoritmo é da ordem O(N(log N + ML)), com N sendo a quantidade total de spels, M a quantidade de

objetos, geralmente não superior a 10, e L é uma pequena constate que indica a quanti- dade de vizinhos usados no crescimento das regiões, neste trabalho esse valor pode ser 4 ou 6.

Em busca de uma maior eficiência na segmentação fuzzy, foi proposto por Carva- lho et al. [Carvalho et al. 2005] um algoritmo mais eficiente, o qual foi denominado de Fast-MOFS (Algoritmo 2.1). Neste, foi feita uma discretização dos valores gerados pela função de afinidade. Supõe-se que um conjunto não vazio R de possíveis valores de afinidades fuzzy, os quais podem ser atribuídos aos spels de uma classe particular de problema, seja sempre um subconjunto do conjunto A. Sendo K a cardinalidade do conjunto A_{∪ 1, e 1 = a}1 > a2 > ··· > aK > 0 sendo os elementos de A. Por exem-

plo, em muitas aplicações, a qualidade da segmentação fuzzy não é significativamente afetada se cada valor da afinidade for arredondado para três casas decimais. Se for utili- zado este arredondamento para as afinidades dos spels, poderá ser utilizado um conjunto

A_{= {0.001,0.002,··· ,0.999,1.000}, com K = 1000 e a}k= 1.001 − k/1000.

Nesta nova implementação foi utilizada uma matriz de dimensões M_{× K denominada}

U , onde M representa o número de objetos e K são os possíveis valores que a afinidade

pode assumir. Todo spel que pertença ao objeto m com afinidade k estará armazenada em uma lista ligada [Cormen et al. 2001] cujo nó cabeça é U[m][k]. Esta implementação

é mais eficaz, com uma complexidade de espaço na ordem de O(M(K + V )) se todas as

estruturas de dados puderem ser armazenadas na memória principal.

No algoritmo fast-MOFS, quando o valor de qualquer componenteσc₀é trocado, basta atualizar as listas em U a qual o spel deve agora pertencer, com o custo de tempo na ordem de O_{(max(1, |{m ≥ 1|}σc_{m> 0}|). A cardinalidade do conjunto {m ≥ 1|}σc_{m> 0} é} no máximo M, o qual é um pequeno valor e normalmente menor que 10 nas aplicações deste trabalho. Com isso, a complexidade do algoritmo é da ordem O(NML), e como M

Algoritmo 2.1: Fast MOFS 1 f o r c_{∈ V do} 2 f o r m_{← 0 t o M do} 3 σc_{m← 0} 4 end- f o r 5 end- f o r 6 f o r m_{← 1 t o M do} 7 f o r c_{∈ V}m do 8 σc_0←σc_{m← 1} 9 end- f o r 10 U_{[m][1] ← V}m 11 f o r k_{← 2 t o K do} 12 U_{[m][k] ← ∅} 13 end- f o r 14 end- f o r 15 f o r k_{← 1 t o K do} 16 f o r m_{← 1 t o M do} 17 w h i l e U_{[m][k] 6= ∅ do}

18 remove um spel d do conjunto U[m][k]

19 C_{← {c ∈ V |}σc_m< min(ak,ψm(d, c)) and σc0≤ min(ak,ψm(d, c))}

20 w h i l e C_{6= ∅ do}

21 remove um spel c do conjunto C

22 t_{← min(a}k,ψm(d, c)) 23 i f σc₀< t t h e n 24 remove c do conjunto U[m][k] 25 f o r n_{← 1 t o M do} 26 σc_{n← 0} 27 end- f o r 28 end- i f 29 σc_0←σc_{m← 1} 30 i n s e r e c no c o n j u n t o U[m][l] onde l é o i n t e i r o al = t 31 end- w h i l e 32 end- w h i l e 33 end- f o r 34 end- f o r

Segmentação Fuzzy de Vídeos

Chung et al. [Chung et al. 2008] propõe um método automático para segmentação de objetos de seu background em vídeos. Estes objetos devem ser aproximadamente estáticos porém rodeados por regiões em movimento. Já Byun et al. [Byun et al. 2003] propôs uma abordagem para detecção automática de faces em vídeos coloridos usando um algoritmo de decisão fuzzy. Este algoritmo detecta as faces usando a distribuição espacial das cores no modelo YCbCr. Estes dois métodos se mostram bastante limitados,

o primeiro pelo tipo de movimento presente nos objetos do vídeos, enquanto o segundo se restringe a segmentar faces detectando regiões que contenham cores semelhantes à peles faciais.

Neste trabalho, o algoritmo de segmentação Fuzzy descrito por Herman e Carvalho [Herman e Carvalho 2001] foi estendido para segmentar vídeos coloridos. Um vídeo é formado por uma sequência de uma ou mais imagens (também chamadas de quadros ou

frames) de uma cena, capturadas ao longo do tempo. Este vídeo pode ser tratado como

um volume, como podemos ver na Figura 3.1. Este volume terá largura e altura (eixos x e y respectivamente) iguais as do vídeo de entrada, e a profundidade (eixo z) será igual a quantidade de frames do vídeo.

O algoritmo de segmentação implementado neste trabalho usa os vizinhos adjacentes de face para expandir as regiões a serem segmentadas (Figura 3.2). Caso a segmentação seja de uma imagem, os vizinhos de um pixel_{(x, y) serão: (x + 1, y), (x − 1,y),(x,y + 1) e}

(x, y − 1) (Figura 3.2-a). Já se a segmentação for de um vídeo, caso em que este é tratado

como um volume 3D, os vizinhos de um pixel_{(x, y, z) serão: (x+1, y, z), (x−1,y,z),(x,y+} 1_{, z), (x, y − 1,z),(x,y,z + 1) e (x,y,z − 1) (Figura 3.2-b). Assim, usando-se este tipo de} vizinhança as sementes selecionadas para um objeto em um determinado frame de um vídeo também servirão para os demais frames que também contenham o mesmo objeto, pois as regiões irão crescer tanto no frame no qual foram inseridas as sementes quanto nos que o sucedem e o antecedem.

Figura 3.1: Conjunto de Frames de um vídeo formando um volume.

Na Figura 3.3 podemos observar o primeiro e o septuagésimo frames de um vídeo sintético. Uma vez que todos os objetos em que deseja-se segmentar o vídeo encontram- se visíveis no primeiro frame, Figura 3.3-(a), pode-se escolher as semente necessárias para cada objeto neste frame. Porém, no septuagésimo frame o avião vem de uma oclusão total causada pela pilha de toros. Isso impossibilita que a região que compreende o avião cresça corretamente para os frames situados após a oclusão, sendo necessária a adição de mais pontos sementes em algum dos frames que sucedam a oclusão.

O aplicativo FuSe Tool (Fuzzy Segmentation Tool) foi desenvolvido para auxiliar a segmentação de imagens e vídeos. Nela o usuário pode navegar entre os frames de um vídeo e adicionar ou remover sementes nestes, fazendo uso de uma interface gráfica de fácil interação.

3.1

Segmentação com Múltiplos Canais

Devido a capacidade do sistema visual humano em diferenciar milhares de tons e intensidades de cores ao contrário das poucas dezenas de níveis de cinza [Pedrini e Schwartz 2008], o processo de identificação de objetos em uma cena ou a interpretação desta, pode ser mais preciso se forem utilizadas informações de cores. Desta forma, neste trabalho, os algoritmos de segmentação de vídeos foram implementados para aplicação em vídeos coloridos.

Figura 3.2: Vizinhanças usadas no algoritmo de segmentação. Em (a), vinhança de 4 usada em segmentações de apenas uma imagem; Em (b), vizinhança de 6 usada na seg- mentação de volumes.

(a) (b)

Figura 3.3: Exemplo de oclusão em um vídeo. Em (a), temos o primeiro frame, onde serão inseridas as sementes. Em (b), tem-se o septuagésimo frame, no qual o avião vem de uma oclusão causada pela pilha de torus.