Indexação de imagens utilizando o problema de localização de facilidades

Indexação de imagens utilizando o problema de localização de facilidades A NDERSON ROCHA 1 J ÚLIO C ÉSAR A LVES2 R ICARDO M ARTINS DE A BREU S ILVA 2 Instituto de Computação Universidade Estadual de Campinas (Unicamp) Caixa Postal 6176 – CEP 13084-971, Campinas, SP 1 [email protected]

2

Depto. de Ciência da Computação Universidade Federal de Lavras (UFLA) Caixa Postal 37 – CEP 37200-000, Lavras, MG [email protected] and [email protected]

Resumo. A busca por novos meios eficientes e eficazes de indexação de imagens é um campo de pesquisas fundamentado nos mais variados campos da ciência. Inúmeras técnicas de sucesso já existem tais como o GIF e o JPEG. No entanto, muitas outras continuam sendo estudadas e/ou propostas. Neste artigo, apresenta-se uma nova forma. Propõe-se a indexação de imagens através da utilização do problema de localização de facilidades, muito conhecido na área de Otimização. Palavras-Chave: Indexação de imagens, problema de localização de facilidades, p-medianas

Image indexing using the facility location problem Abstract. The research for new efficient and robustness image indexing approaches is a very wide research field of Computer Science. Approaches such as GIF and JPEG were designed to solve this problem. However, a lot of others keep being studied and proposed. In this paper, we propose to index images using the facility location problem, a very known approach of the Optimization research area. Keywords: Image indexing, facility location problem, p-medians

(Received July 1st, 2005 / Accepted Undefined) 1 Introdução Nos últimos dez anos, o uso de imagens digitais tornouse cada vez mais comum, mesmo entre pessoas que não estão ligadas às artes gráficas. A popularização dos scanners de mesa e o surgimento de câmeras fotográficas digitais cada vez mais poderosas e baratas inundaram os computadores com milhares de arquivos de imagem, tradicionais devoradores de memória e espaço em disco.

No entanto, mesmo para os padrões atuais de armazenamento, as fotografias ainda geram arquivos relativamente pesados. Um arquivo TIFF [5], de uma imagem RGB em formato A4 (com 300 dpi de resolução) tem cerca de 25 MB de informação. Isto é, 28 imagens como essa são suficientes para lotar completamente um CD-R. Por outro lado, em formato compactado JPEG, [7], o mesmo CD-R seria suficiente para armazenar mais de 200 fotos [4].

Neste contexto, apresenta-se neste artigo, uma maneira simples e intuitiva de reduzir imagens digitais em até 75% de seu tamanho original. Ao invés de utilizar complicadas teorias matemáticas como transformações de Fourier, Z ou mesmo de Cosseno, propõe-se a construção de imagens através do problema de localização de facilidades. Os resultados, mesmo incipientes, mostram-se bastante promissores. Futuramente, podese aliar a Matemática à Otimização para a construção de imagens de alta definição e pequenas o suficiente para serem rasterizadas de forma rápida. Os resultados são obtidos através da indexação de imagens multiespectrais de entrada de forma semelhante ao processo de indexação feito pelo GIF, [6]. Obviamente, os autores não esperam que formatos tradicionais e já estabelecidos sejam substituídos. O maior objetivo, no entanto, é a apresentação de que é possível mapear o problema de localização de facilidades à indexação de imagens com resultados satisfatórios. Inicialmente como fim didático, o trabalho pode se tornar de muita valia para melhorias futuras e, quem sabe, como um precursor de um futuro formato de imagens indexadas baseado nas teorias clássicas de Otimização. Para maior entendimento do texto, segue uma descrição das seções posteriores. A seção 2 apresenta um embasamento sobre a representação digital de imagens bem como a definição e funcionamento de imagens indexadas. Em seguida, apresenta-se qual foi o problema abordado neste trabalho e o respectivo modelo de Otimização utilizado para solução do mesmo. A seção 3 apresenta as duas estratégias de solução adotadas para o modelo escolhido e uma comparação dos resultados obtidos. Finalmente, a seção 4 apresenta algumas considerações finais sobre o trabalho.

2.1.1 Imagens multi-espectrais (coloridas)

A quantificação das intensidades de mais de uma banda espectral por vez fornecerá uma informação mais completa a respeito da cena adquirida. Este é o caso da obtenção de imagens coloridas, pois estas são obtidas através de sensores específicos para a determinação de cada uma das intensidades de vermelho (Red), verde (Green) e azul (Blue) – RGB. A mistura destas três bandas espectrais ou cores, permite que se tenha a sensação de enxergar imagens coloridas, uma vez que o olho humano possui sensores que atuam justamente nestas três faixas de comprimento de onda. As imagens coloridas são usualmente compostas por um conjunto de 24 bits: 8 bits para representar as intensidades de vermelho, 8 bits para o verde e 8 bits para o azul. Com a composição destas três cores básicas e utilizando 24 bpp (bits/pixel), pode-se chegar a um número de até 16 milhões de cores e tonalidades distintas. Este número é perfeitamente adequado para a representação da realidade, em cenas digitalizadas, sem a menor perda de detalhes e qualidade em relação às cores. Deve-se isto ao fato deste número de cores ser muito superior à capacidade do olho humano em distinguir cores e tonalidades. A figura 1 apresenta uma visualização tridimensional do espectro de cores.

2 Referencial teórico 2.1 Representação de imagens

Matematicamente, pode-se definir uma imagem como uma função i(x, y), bidimensional, definida numa certa região. Para a maioria das imagens, a região é um subconjunto limitado do plano e os valores assumidos pela função são números reais limitados e não-negativos. O objeto de trabalho do processamento de imagens é a imagem digital que pode ser definida como uma matriz de M × N elementos. Cada um destes elementos é denominado pixel (picture element). O pixel é o menor elemento da imagem e possui um valor associado. Este valor contém a informação de luminosidade e de cor correspondentes à imagem naquele ponto. O número de informações armazenadas no pixel irá definir as bandas espectrais relacionadas à imagem.

Figura 1: Cubo espectral

2.2 Imagens indexadas

A obtenção de imagens coloridas não está restrita apenas às imagens com representação multi-espectral para cada ponto. Pode-se gerar uma imagem onde cada pixel é associado a um valor referente a uma tabela (LUT – Look Up Table), que descreve a cor real deste ponto da imagem. Desta forma, não é preciso associar a cada ponto da imagem as informações a respeito das intensidades RGB. Pode-se, por outro lado, armazenar ima-

gens de cenas coloridas sem a necessidade de reservar uma memória de 24 bpp. Para este tipo de imagens, uma cena é composta pelo mapa de pixels, ou seja, a matriz M xN de pontos com os índices de acesso às cores da tabela de cores. A figura 2 mostra como é uma tabela de cores (LUT) e a tabela 1 mostra como são as referências às entradas de uma tabela de cores. Deste modo, para armazenar uma imagem indexada com 256 cores, por exemplo, são necessários apenas 8 bpp ou 1 byte por entrada da tabela. Com isto, conseguese reduzir o tamanho da imagem em 75%.

Por outro lado, o problema de cobertura de conjuntos, [1], consiste em determinar a localização de p facilidades em uma rede, de forma a atender (ou cobrir) toda a parcela de uma determinada população, dada uma distância de serviço. Os vértices da rede que estiverem a uma distância menor ou igual à distância de serviço em relação a algum vértice escolhido para a instalação de uma facilidade são classificados como cobertos, e a população ou demanda associada a esse vértice é considerada atendida. 2.4 O problema abordado

O problema abordado neste trabalho consiste em indexar uma imagem de 16 milhões de cores segundo um número p variável de cores. Deve-se selecionar as cores que melhor representem a imagem de entrada. Para tal, utiliza-se o problema de localização de facilidades. Esta busca é feita de duas formas diferentes: • Abordagem 1: encontra-se um pixel central denominado centro de área de localização em análise. Este centro representa uma área de raio R previamente inicializado. Esta estratégia é baseada no problema de cobertura de conjuntos (Set Covering Problem – SCP) e (p-Center Problem). Figura 2: Look Up Table – Tabela de cores

Pixel (0,0) (0,1) (0,2) (m,n)

Entrada na tabela (0,1) (3,5) (4,8) (0,0)

• Abordagem 2: encontra-se uma área de localização dentro de um raio de cobertura R previamente inicializado. O cálculo do centro a ser utilizado é feito através da mediana entre os pixels dentro dessa região que contribuem efetivamente para a imagem sendo analisada. Esta abordagem é baseada no problema das p-Medianas (p-Median Problem – pMP). 2.5 O modelo de resolução adotado

Tabela 1: Tabela de referências à LUT

2.3 Problema de localização de facilidades

Problemas de localização tratam de decisões sobre a melhor configuração (ou ótima) para instalação de facilidades, de forma a atender a demanda de uma população. Apesar das diferenças entre as aplicações, os modelos de localização e alocação possuem uma estrutura comum [3] e [2]. De acordo com [3], o problema das p-Medianas é um problema clássico de localização de facilidades e consiste em localizar p facilidades (medianas) em uma rede, de modo a minimizar a soma das distâncias de cada nó de demanda à sua mediana mais próxima.

Para resolver o problema, utilizou-se o modelo de localização de facilidades. 2.5.1 Dimensões do problema

• Facilidades j: cores do espectro; • Localidades i: cores da imagem. 2.5.2 Atributos

• Zi ∈ {0, 1}: localidade i foi coberta; • hi : demanda na localidade i; • Xj : facilidades; • p: quantidade de facilidades;

• aij : 1 se a facilidade j atende a localidade i e 0, caso contrário. 2.5.3 Função objetivo

max

nR = r(1 + (nroRegioes − p)/(10 ∗ p)) m X

Z i hi

(1)

i=1

2.5.4 Restrições m X

Xj ≤ p

(2)

aij Xj ≥ Zi ∀ i = {1, . . . , m}

(3)

j=1 n X

o processo. Decidiu-se que o novo raio seria dado pela equação abaixo:

j=1

3 Resultados 3.1 Implementação

Em uma imagem qualquer de tamanho M x N pixels, na qual cada pixel é formado por valores R, G e B, deve-se representá-la utilizando no máximo p cores. A idéia é encontrar em um universo de 224 cores, chamado espectro, as, no máximo, p cores que melhor representem esta imagem. Estas cores podem ser escolhidas de várias maneiras, obtendo diferentes resultados. Como apresentado na seção 2.4, foram adotadas duas abordagens. A primeira abordagem será chamada pCentro e a segunda pMediana. As duas abordagens utilizam a idéia de regiões de cobertura e para tanto, a idéia de raio. Na abordagem pCentro, sendo r o raio de cobertura, suponha que uma cor C, com componentes RGB (Cr , Cg , Cb ), do espectro de cores tenha sido escolhida para representar outras cores, passando a se chamar cor de cobertura de uma região. Isto quer dizer que, os pixels da imagem que possuam os valores de suas componentes RGB entre (Cr − r, Cg − r, Cb − r) e (Cr + r, Cg + r, Cb + r), passarão a ser representados pela cor escolhida. No entanto, têm-se várias maneiras de escolher a cor C. Foi utilizada a seguinte idéia: considerando que a imagem seja formada por uma matriz de pixels, formadas por linhas e colunas, os pixels da imagem são percorridos em cada linha do menor para o maior valor. Para cada pixel, se ele ainda não foi coberto, a sua cor é escolhida como a cor de cobertura, e assim, é definida uma região. Caso contrário, o pixel já foi coberto e não é preciso fazer mais nada. O problema é que, dependendo do raio inicial, o número de cores de cobertura, e conseqüentemente de regiões, pode ser maior que o número máximo p de cores. Se isso acontecer é necessário aumentar o raio e repetir

(4)

Deste modo, enquanto o número de regiões for maior que p, o processo de percorrer a imagem e definir regiões é repetido, com um raio cada vez maior. A abordagem pMediana é muito parecida com a anterior. As regiões são escolhidas da mesma forma, contudo, ao invés de utilizar a cor do centro da região como cor de cobertura, utiliza-se a mediana de todas as cores da imagem que pertencem àquela região. Esperando-se que com isso a imagem seja melhor representada. A mediana de uma amostra ordenada é o elemento central, caso a cardinalidade da amostra seja ímpar. Por outro lado, caso a cardinalidade seja par, a mediana é dada pela média aritmética dos dois elementos centrais. O detalhe é que para calcular a cor mediana é preciso definir como ordenar as cores de uma determinada região. Para isso, definiu-se que para duas cores c1 e c2 : c1 < c 2

⇔

c1r − c2r + c1g − c2g + c1b − c2b < 0 (5)

3.2 O Software Desenvolvido

Para implementar-se as idéias apresentadas na seção anterior, desenvolveu-se o wxOtimagem. Este é um programa que permite indexar imagens multi-espectrais. A figura 3 mostra o software em execução.

Figura 3: wxOtimagem em execução

O aplicativo foi desenvolvido utilizando a linguagem de programação C++ e a biblioteca gráfica wxWindows (www.wxwindows.org).

3.3 Comparação dos resultados

Como apresentado na seção 3.1, num primeiro momento, pode-se pensar que a abordagem pMediana represente melhor a imagem. Uma vez que a cor de cobertura tende a estar nas regiões de maior concentração de cores. Entretanto, é necessário uma comparação quantitativa entre as duas abordagens. Para tanto, calculou-se o gap das componentes RGB entre a imagem original e a imagem gerada por cada abordagem. O gap de uma imagem é dado pela soma das distâncias euclidianas de cada componente RGB, de cada pixel da mesma em relação à imagem original. Espera-se com este cálculo que, quanto menor o gap entre a imagem original e a imagem gerada, menor a distorção provocada pela última. Deste modo, foram utilizadas algumas imagens de teste para comparar as duas abordagens. A tabela 2 traz os gaps encontrados para cada imagem de teste, nas duas abordagens. A tabela traz ainda, as dimensões da imagem, o raio inicial, o valor de p e o número de regiões encontradas. 3.3.1 Análise quantitativa

Ri denota o raio inicial, Rc denota o número de regiões de cobertura encontradas I é a imagem analisada e D as suas dimensões. Finalmente, A é a abordagem de indexação utilizada. 3.3.2 Análise visual

A figura 4 mostra uma imagem multi-espectral. A figura 5 mostra a mesma imagem após a indexação com p = 100 pela abordagem 1 (p-Centro). Finalmente, a figura 6 apresenta o resultado da indexação segundo a abordagem 2 (p-Mediana).

I 01

D 270x204

Ri 5

p 25

02

214x454

5

256

03

288x193

10

100

04

288x188

10

50

05

288x204

5

100

06

229x326

5

120

07

300x369

5

256

08

277x187

10

200

09

300x295

10

256

10

300x197

15

180

11

200x200

15

100

12

288x177

5

80

13

330x237

5

256

A pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana pCentro pMediana

gap 9.244.880 9.663.194 2.723.449 2.962.529 1.791.959 1.651.840 2.272.635 1.831.381 1.809.694 1.675.418 1.548.612 1.495.188 2.725.000 3.038.608 1.501.058 1.339.592 1.726.486 1.684.615 1.237.719 1.426.972 1.477.740 1.206.218 2.753.456 1.492.937 2.117.088 2.268.443

Rc 6 6 248 213 95 88 47 42 99 94 112 117 243 184 157 173 188 213 128 150 96 81 74 70 249 198

Tabela 2: Comparação entre as abordagens pCentro e pMediana

3.3.3 Observações

Analisando os dados encontrados nos testes, não é possível chegar a uma resposta conclusiva sobre qual abordagem, pCentro ou pMediana, é a que melhor representa uma imagem com p cores. Entretano, recomedarse-ia, na prática, a utilização da abordagem pCentro uma vez que o tempo necessário para a geração da imagem indexada é consideravelmente menor. 4 Considerações finais

Figura 4: Imagem multi-espectral

O campo da Otimização tem diversas aplicações na ciência. A indexação de imagens é apenas um deles. Este artigo mostrou como utilizar o problema de localização de facilidades, muito conhecido na área de Otimização para indexar imagens e, conseqüentemente, diminuir seus tamanhos em 75%. Obviamente, este trabalho está aquem de competir com formatos já consagrados como o GIF ou mesmo o JPEG. No entanto, com algumas modificações de robustez e de cálculo de regiões esta abordagem pode ser muito bem aplicada. O objetivo, por outro lado, foi de mostrar que a Otimização é um campo meio e não fim. Ela pode ser aplicada aos mais diversos problemas produzindo soluções robustas e satisfatórias.

[6] The Compuserve Group. Specification of the gif image format. In Compuserve. The Compuserve Group, Nov. 2003. Último acesso em 04 de julho de 2005. [7] The JPEG Group. Specification of the jpeg image format. In The Joint Expert Photographic Group. The JPEG Group, Nov. 2003. Último acesso em 04 de julho de 2005.

Figura 5: Imagem indexada p-Centro

Figura 6: Imagem indexada p-Mediana

Referências [1] Church, R. L. and ReVelle, C. S. The maximal covering problem. papers of the regional science association. In Papers of the Regional Science Association. Regional Science Association, 1974. [2] Hakimi, S. L. Optimum distribuition of switching centers in a communication network and some related graph theoretic problems. In Operations Research. Operations Research, 1965. [3] Hillsman, E. L. The p-median structure as a unified linear model for location-allocation analysis. In Environmental and Planning. Environmental and Planning, 1984. [4] Martins, N. R., Reiney, A., and Pires, R. Digitalização de documentos. In SIARQ / Unicamp, June 2001. [5] The Adobe Inc. Specification of the tiff image format. In Adobe Inc. The Adobe Associates Partners, Nov. 2003. Último acesso em 29 de julho de 2005.