Programação Genérica Aplicada a Algoritmos Geográficos (página 2)

Por isso, o desenvolvimento de GIS pode ser aperfeiçoado através da combinação da idéia das técnicas de orientação a objeto com o paradigma emergente de programação genérica (Austern, 1999). Essa idéia levou a ferramentas de programação como a STL (Standard Template Library), que é parte do padrão ISO C++ (Stroustrup 1997), e que fornece um grande número de contêineres genéricos (tais como list, set e map) assim como algoritmos (tais como sort e search) cujo comportamento independe de contêiner. A chave para separação entre contêineres e algoritmos é o uso de iteradores, que são ponteiros generalizados que fornecem a ligação entre algoritmos e estruturas de dados. A aplicação do paradigma de programação genérica para GIS é um processo de quatro passos: (a) encontre padrões na manipulação de dados espaciais pelos algoritmos e nas estruturas; (b) generalize as estruturas de dados em tipos abstratos (contêineres); (c) forneça iteradores que permitam o acesso aos contêineres; (d) projete algoritmos que usem estes iteradores.

Este trabalho tem como objetivo aplicar o paradigma de programação genérica na implementação de algoritmos de agrupamento de dados geográficos. Mostra-se que esse paradigma pode ser útil para que uma mesma implementação de um algoritmo se aplique a diferentes estruturas de dados. Os algoritmos de agrupamento particionam os objetos em conjuntos (clusters) onde os elementos de um conjunto são mais semelhantes, segundo algum critério, do que de elementos de outros conjuntos.

Um agrupamento pode ser visto como uma partição sobre um espaço de atributos, definidos sobre algum critério (Bailey, 1995). Os algoritmos de agrupamento podem ser aplicados, por exemplo, tanto a uma imagem de sensor remoto quanto a um conjunto de objetos geográficos vetoriais com base em um de seus atributos, pois são procedimentos bem definidos que independem de uma estrutura de dados em particular.

A seção 2 aborda a programação genérica, a seção 3 mostra como a programação genérica pode ser ap licada a algoritmos de agrupamento e a seção 4 apresenta o ambiente de trabalho e os resultados obtidos com a implementação dos algoritmos genéricos de agrupamento.

Por último, é apresentada a conclusão.

Programação genérica refere-se a um tipo de abstração no processo de desenvolvimento de software, voltado para a construção de algoritmos que independem de um determinado tipo ou estrutura de dados e que, no entanto, sejam tão eficientes quanto se construídos acoplados a uma determinada estrutura. Os algoritmos genéricos são escritos com base em um conjunto de requisitos sobre as estruturas que manipulam, sem explicitamente especificálas.

Estas estruturas podem ser tipos simples, compostos ou definidos pelo usuário; desde que atendam aos requisitos especificados, podem ser tratadas pelo algoritmo sem a necessidade de sua replicação para cada um deles (Austern, 1999).

Como exemplo, suponha um algoritmo para determinar o valor mínimo dentre os pixels de uma imagem, armazenada segundo uma certa estrutura de dados, e dentre um conjunto de objetos, representados em uma outra estrutura. Os pixels são comparados com base em seu valor de intensidades, e objetos são comparados com base em um de seus atributos. Uma abordagem dependente de tipos para o algoritmo de valor mínimo, iria escrever um algoritmo para cada estrutura de dados, em um mecanismo representado na Figura 2-1.

Figura 2-1
Representação de algoritmo acoplado a estrutura de dados

Segundo a abordagem de programação genérica, o algoritmo de valor mínimo seria definido em termos do conjunto de passos que o descrevem:

percorra toda a estrutura para cada elemento, compare com o valor mínimo atual substitua o valor mínimo atual pelo valor do elemento caso esses seja menor que valor mínimo.

Com base na definição de passos do algoritmo, é feito um levantamento dos requisitos que uma estrutura de dados deve atender a fim de poder ser manipulada por esse algoritmo (o resultado dessa abordagem é ilustrado na Figura 2-2). Nesse caso, observa-se a seguinte lista de requisitos:

• a estrutura deve oferecer algum mecanismo de percorrimento de seus elementos um a um, do primeiro ao último;
• os elementos devem ser capazes de serem comparados entre si.

Figura 2-2.
Representação de algoritmo desacoplado de estrutra de dados

De maneira geral, o conceito de programação genérica consiste, portanto, em se encontrar abstrações em dois passos (Austern, 1999):

1. as instruções que representam o algoritmo e

2. o conjunto de requisitos que devem ser atendidos pelas estruturas de dados e tipos aos quais se aplica.

Os algoritmos de agrupamento particionam os objetos em conjuntos (clusters) onde os elementos de um conjunto são mais semelhantes, segundo algum critério, do que de elementos de outros conjuntos. Um agrupamento pode ser visto como uma partição sobre um espaço de atributos, definidos sobre algum critério (Bailey,1995).

Como exemplos, apresenta-se os algoritmos de agrupamento k-médias e passo igual, descritos a seguir em termos dos passos de cada um.

Informalmente, o agrupamento por k-médias irá encontrar k grupos (k é escolhido a priori) onde a variância dos objetos dentro de cada grupo é mínima.

Cada grupo é identificado por um valor chamado de centróide do grupo. Abaixo são apresentados os passos envolvidos no algoritmo K-Médias:

• Determinar os k centróides iniciais dos grupos, segundo algum critério, por exemplo, aleatoriamente dentro do espaço dos objetos ou de acordo com alguma heurística;
• Calcular a distância entre cada objeto e o centróide de cada grupo já definido;
• Alocar o objeto ao grupo cuja distância ao seu centróide seja a menor;
• Recalcular os centróides dos grupos a partir dos objetos realocados;
• Repetir os passos de 2 a 4 até que algum critério de convergência seja atingido.

O processo de agrupamento de um conjunto de valores em k grupos por passos iguais consiste em dividir o intervalo do menor até o maior valor em k fatias de mesmo comprimento. Cada fatia é identificada pelo seu limite inferior e limite superior. Cada elemento é atribuído à fatia cujo intervalo contém seu valor. Abaixo são apresentados os passos envolvidos no algoritmo de agrupamento em passos iguais:

1. Encontrar o intervalo global dos dados, definido pelo menor e o maior valor dentre o conjunto de valores;

2. Dividir o intervalo global em k intervalos. Cada intervalo define um grupo;

3. Associar cada elemento do conjunto ao grupo cujo intervalo o contém seu valor.

Uma vez definidos os passos de cada algoritmo, desacoplados de estruturas de dados específicas, o próximo passo é identificar quais requisitos os algoritmos demandam das possíveis estruturas de dados sobre as quais irá atuar. Observa-se que:

1. Ambos os algoritmos necessitam que a estrutura sobre a qual sejam aplicados, forneça um mecanismo de percorrimento de cada um de seus elementos.

2. Os elementos das estruturas devem possuir uma forma de comparação entre si.

Um conceito bem definido que permite o desacoplamento do algoritmo dos detalhes de percorrimento de cada estrutura específica é o iterador. O iterador trata a estrutura de dados como uma seqüência de elementos, referindo-se a um dos elementos e fornecendo operações necessárias para iterar nessa seqüência. Do ponto de vista do algoritmo o iterador permite o percorrimento de estruturas sem o conhecimento exato de qual tipo seja a estrutura (Stroustrup, 1997).

Os algoritmos foram implementados no ambiente TerraLib (Câmara et al., 2001), que é uma biblioteca de classes para o desenvolvimento de aplicações GIS, em linguagem de programação C++ (Meyers, 1997) utilizando o compilador Microsoft Visual C++ 6.0, na plataforma PC/Windows. A TerraLib oferece uma classe chamada TeRaster para a representação de dados matriciais, a qual pode ser instanciada a partir de imagens em diferentes formatos, como GeoTIFF e JPEG (TerraLib, 2002). Para a aplicação dos algoritmos genéricos de agrupamento, foi implementado na classe TeRaster o conceito de iterador, atendendo aos requisitos do algoritmo, conforme definido na seção 3.

A biblioteca possui também suporte para a manipulação de objetos geográficos discretos, com uma representação vetorial para a sua componente espacial e com atributos descritivos os quais podem ser usados em critérios de agrupamento. A classe TeSelectedObject é a estrutura de dados fornecida para armazenar um conjunto desses objetos e sobre ela podem ser aplicados os algoritmos de agrupamento. Nessa classe também foi implementado o conceito de iterador sobre os objetos.

A implementação dos algoritmos genéricos de agrupamento, em função de iteradores, é mostrada na Figura 6-1. A aplicação do K-Médias a uma imagem, tem por objetivo agrupar pixels de valor de intensidade próximos, o que corresponde, no caso de imagens de sensores remotos, a um tipo de classificação (Mather, 1999). A Figura 6-2 mostra em (a) a utilização do algoritmo K-Médias sobre uma imagem, e em (b) o resultado do agrupamento onde o tom de cinza de cada pixel da imagem resultante corresponde ao grupo ao qual pertence.

A aplicação do K-Médias a um conjunto de objetos vetoriais tem por objetivo agrupar objetos segundo o critério de semelhança sobre um de seus atributos descritivos. A Figura 6-3 mostra o resultado da aplicação do mesmo algoritmo de k-médias ao atributo ÁREA dos objetos relativos aos setores censitários do município de São Paulo.

Esse trabalho apresentou um exemplo de aplicação de programação genérica a algoritmos geográficos de agrupamento. Mostrou-se que usando esse paradigma obtem-se maior eficiência no desenvolvimento de GIS, uma vez que os algoritmos não precisam ser reimplementados em diferentes estruturas de dados. Ou seja, o código dos algoritmos fica mais modular e reusável, pois alterações nas estruturas de dados não se refletem na reimplementação dos algoritmos e vice-versa.