Uma Abordagem Utilizando mpiJava para a Paralelização de Algoritmos de Processamento de Imagens

August 21, 2017 | Autor: Ricardo Sabatine | Categoria: Processamento de Imagens
Share Embed


Descrição do Produto

Uma Abordagem Utilizando mpiJava para a Paralelização de Algoritmos de Processamento de Imagens Priscila T. M. Saito, Ricardo J. Sabatine, Fátima L. S. Nunes, Kalinka R. L. Jaquie Castelo Branco Univem – Centro Universitário Eurípides de Marília Fundação de Ensino “Eurípides Soares da Rocha” Bacharelado em Ciência da Computação Av. Hygino Muzzi Filho 529, CEP 17509-901, Marília, SP {psaito, sabatine, fatima, kalinka}@univem.edu.br Resumo O presente trabalho de pesquisa tem como objetivo principal demonstrar a viabilidade na otimização do tempo de processamento de imagens, mais especificamente de imagens médicas. Para tanto, utiliza-se a programação paralela e distribuída, viabilizada por sistemas distribuídos e pela biblioteca de passagem de mensagens mpiJava. Foi implementado o algoritmo de detecção de bordas Robinson de forma seqüencial e paralela. A partir dos resultados foi possível demonstrar o ganho de desempenho com o uso do paralelismo.

1. Introdução O processamento de imagens é amplamente utilizado em muitas aplicações. Essa área de conhecimento exige intenso poder computacional, visto que as imagens apresentam, em sua grande maioria, tamanho elevado, constituindo grande volume de dados a serem processados. Quando o contexto trata de imagens médicas, esta questão é ainda mais crítica, uma vez que aplicações médicas, em geral, requerem curto tempo de resposta e não se pode permitir armazenamento com perda de dados, caso a imagem seja usada para diagnóstico [3]. O tamanho elevado aliado à necessidade de aplicação de algoritmos complexos, aumenta o tempo de processamento dessas imagens, prejudicando a avaliação das mesmas [6]. A necessidade de alto desempenho e alto poder computacional para o processamento desse tipo de imagem pode ser resolvida por meio do uso de sistemas distribuídos e de bibliotecas de passagem de mensagens, que viabilizam a computação paralela distribuída. Este artigo apresenta a implementação do algoritmo de detecção de bordas Robinson de forma seqüencial e paralela, aplicados a imagens mamográficas (radiografia das mamas). Apresenta,

ainda, uma comparação entre o desempenho obtido com essas duas formas de processamento. O artigo está estruturado da seguinte forma: a seção 2 faz uma descrição da computação paralela distribuída. A seção 3 apresenta conceitos sobre o processamento de imagens médicas. A seção 4 apresenta um modelo de paralelismo para o processamento de imagens. Na seção 5 encontram-se os testes e resultados obtidos e a seção 6 conclui o artigo.

2. Computação Paralela Distribuída Os sistemas computacionais distribuídos aplicados à computação paralela permitem uma melhor relação custo/benefício para a computação paralela. Estes sistemas oferecem a potência computacional adequada às aplicações paralelas que não necessitam de uma máquina maciçamente paralela, porém necessitam de uma potência computacional maior que uma máquina seqüencial pode oferecer [4]. Para a realização da computação paralela sobre sistemas distribuídos, é necessária uma camada de software que possa gerenciar o uso paralelo, pois existe a necessidade da passagem de informações entre as várias máquinas que compõem a plataforma. Os sistemas baseados na troca de mensagens mais utilizados são o MPI (Message Passing Interface) e o PVM (Parallel Virtual Machine). Com o surgimento da linguagem Java, inúmeras propostas foram apresentadas para a utilização dessas bibliotecas nessa linguagem, na qual pode-se citar o mpiJava [2], ambiente de passagem de mensagens utilizado neste trabalho. A escolha desse ambiente para o processamento paralelo dos algoritmos vem em decorrência do uso da linguagem Java que possibilita: portabilidade, permitindo a independência de plataforma, simplicidade e clareza nos códigos, além da existência de APIs especializadas, permitindo o reuso de código e facilitando a construção de aplicações

nos mais diversos domínios, como é o caso do processamento de imagens.

2.1. mpiJava mpiJava é uma interface, amplamente utilizada na computação paralela e distribuída, que permite fazer uso da orientação a objetos em Java juntamente com a biblioteca MPI [2]. Dentro das formas de comunicação possíveis em Java, a biblioteca apresenta bons resultados [1]. O uso de mpiJava já foi validado em diversas implementações e avaliações de desempenho [7].

Os operadores de Robinson executam operações na vizinhança do pixel fazendo com que o valor do pixel resultante seja diretamente proporcional à diferença existente entre o pixel e sua vizinhança. Assim, se o valor de um pixel for exatamente igual aos valores de seus vizinhos, o valor resultante no pixel processado será zero. Para realizar estas operações são utilizadas máscaras de coeficientes. A Figura 1(a) ilustra a matriz de pontos da imagem. As máscaras horizontal superior e inferior, vertical esquerda e direita, 45º inferior e superior e 135º inferior e superior são apresentadas, respectivamente, na Figura 1(b), (c), (d), (e), (f), (h), (i) e (g).

3. Processamento de Imagens Médicas A finalidade das imagens médicas é auxiliar na composição do diagnóstico de anomalias e fornecer material para acompanhamento de terapias, sendo estas imagens provenientes de diversos tipos de modalidades como Radiografia, Ultra-sonografia e Ressonância Magnética Nuclear [6]. As técnicas de processamento de imagem, reconhecimento de padrões, entre outras, são aplicadas com o objetivo de melhorar as imagens e extrair delas informações úteis aos diagnósticos. Existem inúmeros métodos de processamento de imagens. A escolha de procedimentos a serem aplicados depende do objetivo que se deseja em relação a uma determinada categoria de imagem. De forma geral, as operações com imagens podem ser classificadas em baixo nível (pré-processamento), nível médio (segmentação) e nível alto (reconhecimento de padrões). Neste trabalho o objetivo é verificar o desempenho de técnicas implementadas de forma seqüencial e paralela. Inicialmente foi escolhida uma técnica de detecção de bordas (Robinson) [8] a fim de verificar a relação custo benefício decorrente da aplicação das tecnologias de computação paralela distribuída.

3.1. Detecção de Bordas Representar uma imagem por meio de suas bordas pode ser vantajoso, pois se reduz sensivelmente a quantidade de dados que estavam sendo guardados na imagem sem perder muita informação. A detecção de bordas é útil principalmente quando se deseja conhecer informações a respeito de tamanho e forma dos objetos representados na imagem [5]. Há vários algoritmos para detecção de bordas. Assim como os demais filtros no domínio espacial, esses algoritmos exigem uma série de operações aritméticas sobre o pixel e sua vizinhança. Para avaliação neste artigo foi utilizado o algoritmo de detecção de bordas fazendo uso dos operadores de Robinson.

-1 -2 -1

X1

X2

X3

X4

X5

X6

X7

X8 X9 (a)

1

2

1

-1

0

1

1

0

-1

0

-2

0

0

0

0

0

-2

0

2

2

0

1

2 (b)

1

-1 -2 -1 (c)

-1

0 1 (d)

1

0 -1 (e)

2

1

0

-2 -1

0

0

1

2

0

-1 -2

0

-1

-1

0

1

-1

0

1

1

0

-1 -2 (f)

0

1 2 (g)

-2 -1 0 (h)

2

1 0 (i)

1 0

-1

Figura 1 – Região e máscaras para detecção de bordas: (a) Região de pixels; (b) máscara horizontal superior; (c) máscara horizontal inferior; (d) máscara vertical esquerda; (e) máscara vertical direita; (f) máscara 45º inferior; (g) máscara 45º superior; (h) máscara 135º inferior; (i) máscara 135º superior.

Para obter o valor do pixel central, representado por X5 na Figura 1(a), efetua-se a soma das multiplicações de cada pixel da vizinhança pelo coeficiente correspondente na máscara em questão. A soma, que apresentar maior valor, é atribuída ao pixel central X5. No exemplo da Figura 1, considera-se uma vizinhança de 3x3 pixels em torno do ponto central X5. As equações de 1 a 8 definem os operadores de Robinson. Shs = (x7 + 2x8 + x9) - (x1 + 2x2 + x3) Shi = (x1 + 2x2 + x3) - (x7 + 2x8 + x9) Sve = (x3 + 2x6 + x9) - (x1 + 2x4 + x7) Svd = (x1 + 2x4 + x7) - (x3 + 2x6 + x9) Sdid = (x2 + 2x1 + x4) - (x6 + 2x9 + x8) Sdse = (x6 + 2x9 + x8) - (x2 + 2x1 + x4) Sdie = (x2 + 2x3 + x6) - (x4 + 2x7 + x8) Sdsd = (x4 + 2x7 + x8) - (x2 + 2x3 + x6)

(1) (2) (3) (4) (5) (6) (7) (8)

Em que: Shs, Shi, Sve, Svd, Sdid, Sdse, Sdie e Sdsd são os valores resultantes dos operadores de detecção de bordas horizontal superior e inferior, vertical esquerda e direita, 45º inferior e superior e 135º

inferior e superior, respectivamente. O maior valor, dentre estes oito valores resultantes (Shs, Shi, Sve, Svd, Sdid, Sdse, Sdie e Sdsd) será atribuído ao pixel X5. Os demais Xis são os pixels pertencentes à vizinhança-de-8 de X5. A Figura 2 apresenta um exemplo do resultado obtido com a aplicação desses operadores.

(a)

(b)

Figura 2 – Exemplo de detecção de bordas pelos operadores de Robinson. (a) imagem original; (b) máscara 11x11.

A Figura 3 ilustra uma estratégia de paralelização em que uma imagem médica é dividida em blocos pelo mestre, e subseqüentemente é transmitida por meio da biblioteca mpiJava aos escravos. Estes têm a incumbência de processar a imagem e retransmitir os blocos já processados ao mestre, o qual os une reconstituindo a imagem. Pode-se perceber também que os blocos apresentam tamanhos variados (como observado pelo número de linhas em cada um dos blocos 1, 2 e 3), dependendo da característica de cada algoritmo. O algoritmo abordado neste artigo faz uso de máscaras coeficientes que operam sobre uma “vizinhança” de pontos da imagem, sendo assim, há necessidade de redundância nos blocos para o processamento (destacados em vermelho na Figura 3).

4. Um Modelo de Paralelismo para o Processamento de Imagens O requisito básico de um sistema de processamento paralelo de imagens consiste em uma infra-estrutura que permita a execução eficiente de algoritmos de nível baixo, médio ou alto. Essa infraestrutura é composta essencialmente de funções de comunicação e distribuição de dados adequados ao processamento de imagem [3]. Como mencionado anteriormente, os filtros executados no domínio espacial manipulam diretamente os pixels que compõem a imagem. São os mais utilizados devido à facilidade de implementação, mas exigem alto poder de processamento, visto que as imagens constituem, na maioria das vezes, matrizes enormes de pontos a serem processados. É neste contexto que as técnicas de processamento de imagens, em especial aquelas desenvolvidas especificamente para aplicação em imagens médicas, podem se beneficiar dos conceitos de paralelização de imagens. Uma proposta de paralelização eficiente seria a divisão da imagem em blocos distribuídos pelos processadores, de forma a processar ao mesmo tempo vários blocos de uma mesma imagem. Definir o tipo de paralelismo que melhor se adapte ao processamento proposto é tarefa que permite obtenção de melhor desempenho. Desse modo, o paralelismo de dados é o que melhor se enquadra, tornando-se o mais interessante neste caso, pois se pode definir que o processador execute as mesmas tarefas sobre diferentes dados aproximadamente do mesmo tamanho, tendo um único fluxo de controle – SPMD (Single Process Multiple Data). O desafio a ser vencido, neste caso e, mais especificamente em imagens médicas, é a divisão da imagem em blocos e a posterior junção desses blocos sem perdas dos dados e de processamento.

Figura 3. Estratégia de paralelização de imagens médicas.

5. Análise de Desempenho dos Resultados Obtidos A análise de desempenho do algoritmo de detecção de bordas foi realizada por meio de diferentes testes reais em um ambiente paralelo distribuído composto inicialmente por 3 máquinas homogêneas (Pentium IV de 2.7GHz com 512Mbytes, interligadas por uma rede ethernet de 100Mb/s) e posteriormente foram acrescidas máquinas idênticas para compor um ambiente de até 10 máquinas. Foram utilizadas imagens mamográficas de tamanho médio (aproximadamente 11 Megabytes – matrizes de tamanho médio 2500X3000 sendo do formato TIFF e possuindo uma resolução de 16 bits), característica típica das imagens médicas. O filtro de detecção de bordas foi avaliado com template de tamanho 11x11. Observa-se que o tamanho do template é o que define o tamanho da vizinhança a ser considerada. Dependendo do tipo da imagem, uma maior vizinhança indica um melhor resultado de processamento. Após a realização dos testes obteve-se uma média dos 30 tempos de processamento tanto para aplicação seqüencial quanto para a paralela. Quando da avaliação da execução em paralelo foram efetuados testes com até 10 máquinas e para cada uma delas, testes com até 11 processos sendo iniciados em

paralelo. Todos os resultados obtidos foram avaliados estatisticamente (teste de hipóteses) para comprovar seu grau de significância. A Figura 4 apresenta o resultado da execução seqüencial e paralela do filtro de detecção de bordas com a biblioteca mpiJava. Média dos Tempos de Execuções (ms)

30000 25000 20000 15000 10000 5000 0 3

4

Sequencial 7 Máquinas

5

6 7 8 Número de Processos

3 Máquinas 8 Máquinas

4 Máquinas 9 Máquinas

9

5 Máquinas 10 Máquinas

10

11

6 Máquinas

Figura 4 – Média dos tempos de execuções da aplicação seqüencial comparada com a aplicação paralela do filtro de detecção de borda.

É possível observar que independentemente do número de processos iniciados, o tempo médio paralelo é sempre melhor que o seqüencial. À medida que se aumenta o número de processos para certa quantidade de máquinas, o desempenho diminui, isso acontece porque quando se aumenta o número de processos em alguns casos é evidente a queda de desempenho. Observa-se também que a melhor média dos tempos de execuções é obtida quando se tem um processo a mais que o número de máquinas participantes. Isso é devido ao fato do mpiJava fazer uso de um processo mestre que é contabilizado, mas não efetua a tarefa escrava propriamente dita. Nesses casos, o escalonamento é do tipo round-robin. O uso da computação paralela distribuída no processamento de imagens permite uma melhora significativa de desempenho, conforme pode ser observado pelo gráfico da Figura 4. Os cálculos efetuados pelas máscaras, por serem volumosos, garantem uma melhoria do uso em paralelo uma vez que a comunicação em rede imposta se torna desprezível quando comparada ao ganho em relação aos cálculos efetuados, ou seja, o tempo utilizado para o envio de cada parte da imagem (subvetor) é menor que o tempo gasto pelos escravos para realizar o processamento (inúmeras multiplicações necessárias de acordo com o algoritmo).

6. Conclusões Partindo-se dos resultados obtidos pode-se verificar que existe um ganho em se fazer uso do processamento paralelo distribuído quando se pensa em processamento de imagens médicas. Foi possível observar que o uso do processamento paralelo é bastante vantajoso para processamentos intensos

como é o caso do algoritmo de detecção de bordas Robinson. Acredita-se que a utilização de outros filtros no domínio espacial também provenha melhora significativa de desempenho para a versão paralela quando comparada à execução seqüencial. Com base nesses resultados obtidos têm-se como trabalhos futuros o desenvolvimento de novos algoritmos de processamento de imagens, o que permitirá a obtenção de um conjunto maior de dados a partir do qual tais informações poderão ser extraídas com maior fidelidade a fim de construir uma base de comparação efetiva.

Agradecimentos Os autores gostariam de agradecer à agência de financiamento FAPESP pelo apoio dado aos projetos do Laboratório de Arquitetura de Sistemas (LAS) da UNIVEM, principalmente pelos processos nº 2006/06671-0 e nº 2007/00868-0.

7. Referências [1] BAKER, M.; CARPENTER, B.; FOX, G.; KO, S. H.; LIM, S. mpiJava: An Object-Oriented Java Interface to MPI. Presented at International Workshop on Java for Parallel and Distributed Computing, IPPS/SPDP 1999, San Juan, Puerto Rico, April 1999. [2] BAKER, M.; CARPENTER, B.; KO, S. H.; LI, X. (1998). mpiJava: A Java Interface to MPI. Submitted to First UKWorkshop on Java for High Performance Network Computing, Europar 1998. [3] BARBOSA, J. M. G. Paralelismo em Processamento e Análise de Imagem Médica. 240f. Tese (Doutorado) Departamento de Engenharia Electrotécnica e de Computadores, Faculdade de Engenharia da Universidade do Porto, 2000. [4] BRANCO, K. R. L. J. C. Extensão da Ferramenta de Apoio à Programação Paralela (F.A.P.P.) para Ambientes Paralelos Virtuais. 1999, 152f. Dissertação (Mestrado) Instituto de Ciências Matemáticas e de Computação de São Carlos, Universidade de São Paulo, São Carlos, 1999. [5] GONZALES, R. F.; Woods, P. Digital Image Processing, Addison-Wesley. 2002. [6] NUNES, F. L. S. M. “Investigações em Processamento de Imagens Mamográficas para Auxílio ao Diagnóstico de Mamas Densas”. 230f. Tese (Doutorado) - Instituto de Física de São Carlos, Universidade de São Paulo, São Carlos, 2001. [7] TABOADA, G. L.; TOURINO, J.; DOALLO, R. Performance Modeling and Evaluation of Java MessagePassing Primitives on a Cluster. Lecture Notes in Computer Science, v.2840, p.29-36, 2003. [8] ZAMBIASI, S. P.; TRAMONTIN JUNIOR, R. J. Proposta de Otimização para Algoritmos de Detecção de Bordas em Imagens. In: 4th International Information and Telecommunication Technologies Symposium, 2005, Florianópolis. I2TS' 2005, 2005.

Lihat lebih banyak...

Comentários

Copyright © 2017 DADOSPDF Inc.