Submitted by Rosa Assis (rosa_assis@yahoo.com.br) on 2017-03-21T19:40:25Z No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Paola Damato (repositorio@mackenzie.br) on 2017-03-22T15:01:23Z (GMT) No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-03-22T15:01:23Z (GMT). No. of bitstreams: 2 LEANDRO JUVENCIO MOREIRA.pdf: 1183496 bytes, checksum: b7b7de6c9a5112b9705c906c6cbdaaec (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2016-12-14 / The data classification is a data mining task with relevant utilization in various areas of application, such as medicine, industry, marketing, financial market, teaching and many others. Although this task is an element search for many autors, there are open issues such as, e.g., in situations where there is so much data, noise data and unbalanced classes. In this way, this work will present a data classifier proposal that combines the SOM (Self-Organizing Map) neural network with INN (Informative Nearest Neighbors). The combination of these two algorithms will be called in this work as SOM-INN. Therefore, the SOM-INN process to classify a new object will be done in a first step with the SOM that has a functionality to map a reduced dataset through an approach that utilizes the prototype generation concept, also called the winning neuron and, in a second step, with the INN algorithm that is used to classify the new object through an approach that finds in the reduced dataset by SOM the most informative object. Were made experiments using 21 public datasets comparing classic data classification algorithms of the literature, from the indicators of reduction training set, accuracy, kappa and time consumed in the classification process. The results obtained show that the proposed SOM-INN algorithm, when compared with the others classifiers of the literature, presents better accuracy in databases where the border region is not well defined. The main differential of the SOM-INN is in the classification time, which is extremely important for real applications. Keywords: data classification; prototype generation; K nearest neighbors; self-organizing / A classificação de dados é uma tarefa da mineração de dados com utilização relevante em diversas áreas de aplicação, tais como, medicina, indústria, marketing, mercado financeiro, ensino e muitas outras. Embora essa tarefa seja elemento de pesquisa de muitos autores, ainda há problemas em aberto como, por exemplo, em situações onde há abundância de dados, dados ruidosos e desbalanceamento de classes. Nesse sentido, este trabalho apresenta uma proposta de classificador de dados em um processo de duas etapas que combina a rede neural SOM (Self-Organizing Maps) com o classificador vizinhos informativos mais próximos ou INN (Informative Nearest Neighbors). A combinação desses dois algoritmos será aqui chamada como SOM-INN. Portanto, o processo de uso do SOM-INN na classificação de um novo objeto será feito em uma primeira etapa com o SOM que tem a funcionalidade de mapear um conjunto reduzido dos dados de treinamento por meio de uma abordagem que utiliza o conceito de geração de protótipo, também denominado de neurônio vencedor e, em uma segunda etapa, com o algoritmo INN que é usado para classificar o novo objeto por meio de uma abordagem que encontra no conjunto de treinamento reduzido pelo SOM os objetos mais informativos. Foram realizados experimentos usando 21 conjuntos de dados públicos, comparando com os algoritmos clássicos da literatura de classificação de dados, a partir dos indicadores de redução do conjunto de treinamento, acurácia, kappa e tempo consumido no processo de classificação. Os resultados obtidos mostram que o algoritmo proposto SOM-INN, quando comparado com outros classificadores da literatura, apresenta acurácia melhor em bases de dados em que a região de fronteira não é bem definida. O principal diferencial do SOM-INN está no tempo de classificação, o que é de suma importância para aplicações reais.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-17T20:10:32Z No. of bitstreams: 1 danielrodriguespereira.pdf: 736772 bytes, checksum: d15b2f08bb14ed58ae985f6123258ed5 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-18T13:51:41Z (GMT) No. of bitstreams: 1 danielrodriguespereira.pdf: 736772 bytes, checksum: d15b2f08bb14ed58ae985f6123258ed5 (MD5) / Made available in DSpace on 2017-04-18T13:51:41Z (GMT). No. of bitstreams: 1 danielrodriguespereira.pdf: 736772 bytes, checksum: d15b2f08bb14ed58ae985f6123258ed5 (MD5) Previous issue date: 2017-02-07 / Apresentamos neste trabalho o algoritmo de pontos interiores e direções viáveis denominado FDIPA para resolução de problemas de otimização definido por uma função diferenciável e por restrições de desigualdades. O algoritmo gera uma sequência de pontos interiores a partir de um dado ponto inicial também de interior e converge globalmente com ordem superlinear para um par Karush-Kuhn-Tucker do problema. A cada iteração uma direção de descida da função potencial é calculada inicialmente pela resolução de um sistema nas variáveis dual e primal. Apresentamos também o algoritmo FDA para resolução de problemas de complementaridade definido por uma função diferenciável e não linear. Mostramos a equivalência entre os dois métodos no sentido de gerarem as mesmas direções de descida, viável e de restauração a partir de uma atualização dos multiplicadores de Lagrange do problema de otimização. Realizamos uma comparação entre os métodos em uma coletânea de problemas de complementaridade. / In this work we present the algorithm of internal points and viable directions denominated FDIPA to solve optimization problems defined by a differentiable function and by inequalities restrictions. The algorithm generates a sequence of interior points from a given interior starting point and converges globally with superlinear order to a Karush-Kuhn-Tucker pair of the problem. At each iteration a descent direction of the potential function is calculated initially by the solution of a system in the dual and primal variables. We also present the FDA algorithm to solve complementarity problems defined by a non-linear differentiable function. We show the equivalence between the two methods in the sense that they generate the same descent, feasible and restoring directions from an update to the Lagrange multipliers of the optimization problem. We perform a comparison between the two methods in a collection of complementarity problems.

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-04-25T15:55:49Z No. of bitstreams: 1 larafurtadobastos.pdf: 4369558 bytes, checksum: 7b36e77b964a5ec919c2c9967a654a03 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-04-26T12:06:02Z (GMT) No. of bitstreams: 1 larafurtadobastos.pdf: 4369558 bytes, checksum: 7b36e77b964a5ec919c2c9967a654a03 (MD5) / Made available in DSpace on 2017-04-26T12:06:02Z (GMT). No. of bitstreams: 1 larafurtadobastos.pdf: 4369558 bytes, checksum: 7b36e77b964a5ec919c2c9967a654a03 (MD5) Previous issue date: 2016-09-08 / O presente trabalho apresenta a adaptação e utilização de um algoritmo da área de inteligência artificial evolucionária, bioinspirado no sistema de ecolocalização de morcegos, para resolver o problema da localização global de robôs móveis em ambientes bidimensionais com mapas conhecidos. Sabe-se, por meio da literatura, que a localização de robôs baseada apenas em dedução via hodometria, do inglês deduced reckoning ou dead-reckoning, acumula diversos erros de origem estocástica, os quais não podem ser eliminados de maneira determinística, fazendo-se necessários métodos de filtragem estatística para a correta obtenção da localização. Dentre as diversas alternativas conhecidas para solucionar o problema de localização, escolheu-se o Método Recursivo de Monte Carlo, também denominado por Filtro de Partículas, para comparação com os resultados obtidos pelo algoritmo de morcego, por suas características multimodais e não-paramétricas, sendo este um algoritmo clássico na área de localização robótica. O algoritmo de morcegos, do inglês Bat Algorithm, é um método recursivo de otimização de estados de um sistema que se encontra num ambiente multimodal. É bioinspirado nos sistemas de ecolocalização encontradas em morcegos e outros animais na natureza. Nos resultados de comparação entre ambos os métodos, a técnica proposta demonstrou melhores resultados tanto para o erro entre a localização real e a estimada pelos métodos quanto para o número de iterações necessárias para alcançar a solução e, consequentemente, o tempo de convergência do algoritmo. Para o desenvolvimento deste trabalho, utilizou-se o programa Matlab R integrado com a plataforma ROS, juntamente com o robô móvel terrestre Pioneer P3-DX para os resultados simulados e reais. / This work presents the adaptation and use an algorithm from evolutionary artificial intelligence area, bioinspired in the echolocation system of bats to solve the problem of global location for mobile robots in two-dimensional environments with known maps. It is widely known in literature that the localization of robots based only on deduced reckoning accumulates many stochastic errors, which cannot be eliminated deterministically, requesting statistical filtering methods to obtain the correct location. Among the various alternatives known to solve the problem of localization, we chose the Recursive Method of Monte Carlo, also kown as Particle Filter, for comparison purposes with the results obtained by the Bat Algorithm, because of its multimodal and nonparametric features, and alse because it is a classic algorithm in robotics localization area. The Bat Algorithm is a recursive optimization method of system states immerse in multimodal environments. It is bioinspired in the echolocation systems found in bats and other animals in nature. In comparison results between the two methods, the proposed technique showed the best results for both localization error and the number of iterations required to reach the solution, and consequently the algorithm convergence time. To develop this work, the Matlab software was used with the ROS framework along with the terrestrial mobile robot Pioneer P3-DX for simulated and real results.

Aprendizado em fluxo de dados é uma área de pesquisa importante e que vem crescendo nos últimos tempos. Em muitas aplicações reais os dados são gerados em uma sequência temporal potencialmente infinita. O processamento em fluxo possui como principal característica a necessidade por respostas que atendam restrições severas de tempo e memória. Por exemplo, um classificador aplicado a um fluxo de dados deve prover uma resposta a um determinado evento antes que o próximo evento ocorra. Caso isso não ocorra, alguns eventos do fluxo podem ficar sem classificação. Muitos fluxos geram eventos em uma taxa de chegada com grande variabilidade, ou seja, o intervalo de tempo de ocorrência entre dois eventos sucessivos pode variar muito. Para que um sistema de aprendizado obtenha sucesso na aquisição de conhecimento é preciso que ele apresente duas características principais: (i) ser capaz de prover uma classificação para um novo exemplo em tempo hábil e (ii) ser capaz de adaptar o modelo de classificação de maneira a tratar mudanças de conceito, uma vez que os dados podem não apresentar uma distribuição estacionária. Algoritmos de aprendizado de máquina em lote não possuem essas propriedades, pois assumem que as distribuições são estacionárias e não estão preparados para atender restrições de memória e processamento. Para atender essas necessidades, esses algoritmos devem ser adaptados ao contexto de fluxo de dados. Uma possível adaptação é tornar o algoritmo de classificação anytime. Algoritmos anytime são capazes de serem interrompidos e prover uma resposta (classificação) aproximada a qualquer instante. Outra adaptação é tornar o algoritmo incremental, de maneira que seu modelo possa ser atualizado para novos exemplos do fluxo de dados. Neste trabalho é realizada a investigação de dois métodos capazes de realizar o aprendizado em um fluxo de dados. O primeiro é baseado no algoritmo k-vizinhos mais próximo anytime estado-da-arte, onde foi proposto um novo método de desempate para ser utilizado neste algoritmo. Os experimentos mostraram uma melhora consistente no desempenho deste algoritmo em várias bases de dados de benchmark. O segundo método proposto possui as características dos algoritmos anytime e é capaz de tratar a mudança de conceito nos dados. Este método foi chamado de Algoritmo Anytime Incremental e possui duas versões, uma baseado no algoritmo Space Saving e outra em uma Janela Deslizante. Os experimentos mostraram que em cada fluxo cada versão deste método proposto possui suas vantagens e desvantagens. Mas no geral, comparado com outros métodos baselines, ambas as versões apresentaram melhor desempenho. / Data stream learning is a very important research field that has received much attention from the scientific community. In many real-world applications, data is generated as potentially infinite temporal sequences. The main characteristic of stream processing is to provide answers observing stringent restrictions of time and memory. For example, a data stream classifier must provide an answer for each event before the next one arrives. If this does not occur, some events from the data stream may be left unclassified. Many streams generate events with highly variable output rate, i.e. the time interval between two consecutive events may vary greatly. For a learning system to be successful, two properties must be satisfied: (i) it must be able to provide a classification for a new example in a short time and (ii) it must be able to adapt the classification model to treat concept change, since the data may not follow a stationary distribution. Batch machine learning algorithms do not satisfy those properties because they assume that the distribution is stationary and they are not prepared to operate with severe memory and processing constraints. To satisfy these requirements, these algorithms must be adapted to the data stream context. One possible adaptation is to turn the algorithm into an anytime classifier. Anytime algorithms may be interrupted and still provide an approximated answer (classification) at any time. Another adaptation is to turn the algorithm into an incremental classifier so that its model may be updated with new examples from the data stream. In this work, it is performed an evaluation of two approaches for data stream learning. The first one is based on a state-of-the-art k-nearest neighbor anytime classifier. A new tiebreak approach is proposed to be used with this algorithm. Experiments show consistently better results in the performance of this algorithm in many benchmark data sets. The second proposed approach is to adapt the anytime algorithm for concept change. This approach was called Incremental Anytime Algorithm, and it was designed with two versions. One version is based on the Space Saving algorithm and the other is based in a Sliding Window. Experiments show that both versions are significantly better than baseline approaches.

[pt] Atualmente as Unidades de Saúde, em um grande número de países do mundo, apresentam demandas de serviços que superam suas capacidades reais. Por esta razão, o surgimento das listas de espera é inevitável. Preparar o planejamento das mesmas, de modo otimizado resulta, portanto, em um grande desafio, devido à quantidade de recursos que devem ser considerados. O caso particular dos procedimentos cirúrgicos é particularmente crítico pela quantidade de recursos que se precisam para a realização do mesmo. Poucos projetos têm sido desenvolvidos para a gestão completa dessas listas. O trabalho desenvolvido nesta Dissertação propõe o uso de um modelo, baseado em algoritmos genéticos com inspiração quântica, para a automatização e otimização do planejamento de procedimentos cirúrgicos eletivos. Este modelo, denominado Algoritmo Evolucionário com Inspiração Quântica para a Área de Saúde (AEIQ-AS), além de alocar os pacientes e os recursos necessários para que o processo cirúrgico seja exitoso, procura reduzir o tempo total para que todas as cirurgias sejam realizadas. Este trabalho apresenta também uma ferramenta que permite a modelagem, de modo simplificado, de uma Unidade Cirúrgica de Saúde. Esta ferramenta possibilita a realização de simulações com o objetivo de ver o efeito de diferentes configurações dos recursos nas Unidades de Saúde. Para a validação do modelo proposto foi criada, de modo artificial e fazendo uso da ferramenta de simulação, uma lista de espera de 2000 cirurgias. Caso as cirurgias fossem realizadas seguindo a ordem de chegada, seriam necessárias pouco mais de 37 semanas e teria 1066 operações fora do prazo. Foram feitos vários experimentos onde se buscava a otimização destes valores. Esta busca foi feita, primeiramente, tomando em consideração só um dos parâmetros e a continuação eles em conjunto. Na primeira abordagem o AEIQ-AS consegue a realização das mesmas cirurgias em aproximadamente 31 semanas. Assim, observa se que há uma redução de aproximadamente 16,25 porcento do tempo. O número de operações fora do prazo, por sua vez, foi reduzido pelo modelo para 927 (13,04 porcento). Na abordagem simultânea, o AEIQ-AS, consegue uma diminuição do tempo total de alocação em 16,22 porcento e o número de operações fora do prazo em 9,76 porcento. Foram feitas, também, várias simulações da Unidade de Saúde mantendo as caraterísticas da lista de cirurgias para ver seu efeito no tempo total de alocação de todos os processos cirúrgicos. / [en] Currently, Health Units in a large number of countries in the world present service demand that exceed their real capacities. For this reason, is inevitable the emergence of the waiting lists. To prepare the planning of this in an optimized manner results in a substantial challenge due to the number of resources that should be considered. The case of chirurgical procedures is particularly critical by the number of resources needed for their realization. A small quantity of projects has been developed to fully manage these lists. The work developed in this Dissertation proposes the use of a model based on evolutionary algorithms with quantum inspiration for the automation and optimization of the planning of elective chirurgical procedures. This model, denominated Evolutionary Algorithm with Quantum Inspiration for the Health Field (AEIQ-AS), beyond patients and necessary resources for the successful completion of the chirurgical procedure allocation, pursue the reduction of the total time of realization of all the surgeries. The work presents also a tool that allows the modeling, in a simplified manner, of a Chirurgical Health Unit. This tool enables the realization of simulations with the objective of seeing the effect of different configurations of the resources in the Health Units. To validate the proposed model was created, in artificial mode and employing the simulation tool, a waiting list of 2000 surgeries. In case that the surgeries were realized following the arrival order, will be needed a little more than 37 weeks and will have 1066 surgeries out of time. Several experiments were conducted in order to optimize these values. This search was executed, firstly, considering only one of the parameters and, in continuation, all together. In the first approach, the AEIQ-AS obtains the realization of the same surgeries in approximately 16,25 percent of the time. The number of operations out of time was reduced by the model to 927 (13,04 percent). In the simultaneous approach, the AEIQAS achieves a decrease of the allocation total time in 16,22 percent and the number of operations out of time in 9,76 percent. It were done, also, several simulations of the Health Unit maintaining the characteristics of the surgeries list in order to look the effect in the allocation total time of all the chirurgical procedures.

[pt] No ambiente da Internet, as informações que desejamos frequentemente encontram-se em diferentes localidades. Algumas aplicações, para funcionarem corretamente, precisam manter cópias locais de parte dessas informações. Manter a consistência e a atualidade de uma base de dados, mais especificamente um conjunto de cópias de páginas web, é uma tarefa que vem sendo sistematicamente estudada. Uma abordagem possível a esse problema é a aplicação de técnicas de aprendizado por reforço, que utiliza técnicas de programação dinâmica e análise estocástica para obter uma boa política de agendamento de atualizações das cópias de páginas web. O presente trabalho tem por finalidade validar o uso de técnicas de aprendizado por reforço no problema em questão, assim como encontrar aspectos do problema que possam ser úteis na modelagem da solução empregada. / [en] In the Internet, the information we desire is usually spread over different locations. For some applications, it is necessary to maintain local copies of this information. Keeping consistency as well as freshness of a data base, or more specifically a set of internet web pages, is a task systematically studied. An approach to this problem is the use of reinforcement learning techniques, using dynamic programming and stochastic analysis to obtain a good rescheduling policy for the web pages copies. This work is proposed to validate the use of reinforcement learning techniques over this problem, as well as finding features of the problem useful to model the developed solution.

[pt] Neste trabalho inicialmente foram modeladas as estruturas do dendrímero PAMAM G4 em diferentes estados de protonação utilizando-se o programa Hyperchem. A seguir essas estruturas foram inseridas em uma caixa d’água e simuladas por dinâmicamolecular, tendo sido observado um aumento de volume do dendrímero à medida que o grau de protonação foi aumentado, com a formação de uma estrutura mais aberta comparativamente à do dendrímero não protonado. Uma vez conhecidas as topologias do dendrímero PAMAM em diferentes pH, foram incluídas moléculas de rifampicina nas cavidades existentes no interior do dendrímero em pH neutro simulado, através de um algoritmo desenvolvido com a finalidade de otimizar este encapsulamento, o que definiu como número máximo de 20 moléculas de rifampicina complexadas no interior do dendrímero e resultou em uma redução importante no custo computacional. Após estes acoplamentos pelo algoritmo desenvolvido, o complexo foi simulado através de dinâmica molecular tendo sido verificado que se mantinha estável em pH neutro ao longo do tempo.O estudo da possível liberação das moléculas de rifampicina do complexo rifampicina/PAMAM G4 por dinâmica molecular, mostrou que as moléculas de rifampicina são liberadas gradativamente em pH ácido. Os resultados computacionais foram validados por resultados experimentais obtidos em um trabalho desenvolvido em colaboração entre o IQ/UFRJ e o IPEC/FIOCRUZ, cujo objetivo foi caracterizar e determinar a atividade tuberculostática de complexos rifampicina/PAMAM G4. / [en] The structures of PAMAM G4 dendrimer in different protonation states were initially modeled using the program Hyperchem. After this procedure the structures were inserted in a box of water and simulated with molecular dynamics. Was observed an increase in volume of the dendrimer when degree of protonation was increased. Once known the topologies of PAMAM dendrimer at different pH, the rifampin was included in cavities of dendrimer in Neutral and low pH. Using an algorithm designed for the purpose of optimizing this encapsulation, were encountered 20 molecules inside the cavities of dendrimer. This procedure resulted in a low computational cost for molecular dynamics because the molecules were in a optimal position in the structure of dendrimer. After these couplings of the systems these were simulated with molecular dynamics for observation of capacity in transport of dendrimer these molecules in neutral pH and liberation in low pH. The study of the possible release of the complex molecules of rifampicin (rifampicin / PAMAM G4) showed that the molecules are released gradually of the structures at low pH. The computational results were validated by experimental results on the work developed in collaboration between IQ / UFRJ and IPEC / FIOCRUZ, whose objective was to characterize and determine the tuberculostatic activity of complex.

[pt] Frações Contínuas são representações de números reais que independem da base de numeração escolhida. Quando se trata de aproximar números reais por frações, a escolha da base dez oculta, frequentemente, aproximações mais eficientes do que as exibe. Integrar conceitos de aproximações de números reais por frações contínuas com aspectos geométricos traz ao assunto uma abordagem diferenciada e bastante esclarecedora. O algoritmo de Euclides, por exemplo, ao ganhar significado geométrico, se torna um poderoso argumento para a visualização dessas aproximações. Os teoremas de Dirichlet, de Hurwitz-Markov e de Lagrange comprovam, definitivamente, que as melhores aproximações de números reais veem das frações contínuas, estimando seus erros com elegância técnica matemática incontestável. / [en] Continued fractions are representations of real numbers that are independent of the choice of the numerical basis. The choice of basis ten frequently hides more than shows efficient approximations of real numbers by rational ones. Integrating approximations of real numbers by continued fractions with geometrical interpretations clarify the subject. The study of geometrical aspects of Euclids algorithm, for example, is a powerful method for the visualization of continued fractions approximations. Theorems of Dirichlet, Hurwitz-Markov and Lagrange show that, definitely, the best approximations of real numbers come from continued fractions, and the errors are estimated with elegant mathematical technique.

[pt] O Método dos Elementos Discretos (DEM) com base em esferas pode fornecer aproximações para diversos fenômenos físicos complexos, tanto em escala micro quanto macro. Normalmente uma simulação DEM começa com um arranjo de partículas esféricas no interior de um determinado recipiente. Para domínios gerais a criação deste pacote de esferas pode ser complexo e demorado, especialmente se ele deve respeitar requisitos de precisão e de estabilidade da simulação. O objetivo deste trabalho é estender uma solução de empacotamento de discos 2D para gerar conjuntos aleatórios compostos por partículas esféricas não sobrepostas. O algoritmo construtivo proposto utiliza a técnica de frente de avanço, onde as esferas são inseridas uma a uma no pacote, de acordo com uma estratégia gulosa baseada nas partículas previamente inseridas. A técnica de frente de avanço requer a existência de um conjunto inicial de esferas que definem a fronteira do recipiente. Outra extensão importante proposta aqui é uma generalização do algoritmo para lidar com objetos arbitrários definidos por uma malha triangular qualquer. Este trabalho apresenta também alguns resultados que permitem algumas conclusões e sugestões de trabalhos futuros. / [en] The Discrete Element Method (DEM) based on spheres can provide acceptable approximations to many complex physical phenomena both in micro and macro scale. Normally a DEM simulation starts with an arrangement of spherical particles pack inside a given container. For general domains the creation of the sphere pack may be complex and time consuming, especially if the pack must comply with accuracy and stability requirements of the simulation. The objective of this work is to extend a 2D disk packing solution to generate random assemblies composed by non-overlapping spherical particles. The constructive algorithm, presented here, uses the advancing front strategy where spheres are inserted one-by-one in the pack, according to a greed strategy based on the previously inserted particles. Advance front strategy requires the existence of an initial set of spheres that defines the boundary of the pack region. Another important extension presented here is the generalization of algorithm to deal with arbitrary objects defined by a triangular boundary mesh. This work presents also some results that allow for some conclusions and suggestions of further work.

[pt] Foi desenvolvido pelos grupos MPEG (Moving Picture Expert Group) e VCEG (Video Coding Expert Group) um novo padrão de codificação de vídeo denominado AVC (Advanced Vídeo Coding). Este padrão fornece uma capacidade de compressão maior de vídeo se comparado com os padrões anteriores. A estimação de movimento é a fase da codificação de vídeo que demanda maior tempo de processamento. Estimação de movimento é computacionalmente custosa para H.264/AVC se o método Full Search [1] é usado. A fim de reduzir o tempo de codificação, o software de referência JM 9.8 adota um rápido método de estimação de movimento para pixel inteiro chamado UMHexagonS e um método para pixel fracionário chamado CBFPS. Um método proposto por Xiaoquan Yi, Jun Zhang, Nam Ling e Weijia Shang [2] chamado aqui, por simplicidade, de P021 apresenta, em comparação com o software de referência JM, uma melhor e simplificada forma de estimação de movimento para aumentar a velocidade do processo de codificação e manter a qualidade visual do vídeo. Visando diminuir ainda mais o tempo de processamento e o custo computacional apresentada pelos métodos citados anteriormente, o que é necessário principalmente para aplicações de codificação de vídeo móveis, como celulares e palm tops e aplicações de tempo real, como videoconferência, este trabalho propõe um método de estimação de movimento que consiste em evitar o processamento de blocos que não se beneficiam da pesquisa de metade de pixel. Após a execução dos testes, pode-se constatar que com uma qualidade de vídeo semelhante, o método proposto reduz o tempo de processamento em 76,17%, 75,95% e 11,74% em média quando comparado com os métodos Full Search, JM 98 e P021. Além disso, este método praticamente preserva a taxa de bits, apresentando um pequeno aumento de 8,72% , 8,06% e 8,02% em média quando comparado com os mesmos métodos. Isto representa, em nossa opinião, um pequeno preço a ser pago, considerando os benefícios em termos de tempo de processamento. / [en] The MPEG (Moving Picture Experts Group) and the VCEG (Video Coding Experts Group) have developed a new video compression standard entitled AVC (Advanced Video Coding). This standard offers the capacity of video compression greater than the previous standards.The motion estimation which is a phase of the video compression is extremely computer-intensive and therefore demands most of the processing time. When Full Search [1] method is used for H.264/AVC, this process is extremely expensive. In order to reduce encoding time, the reference software JM (throughout this work, JM98 is the version used) has respectively adopted a fast motion estimation method for the integer pixel called UMHexagonS and a method for the sub- pixel called CBFPS. A method proposed by Xiaoquan Yi, Jun Zhang, Nam Ling e Weijia Shang [2] called here P021 (as referenced by the Joint Video Team) has shown, when compared to the reference software JM, a simple way of motion estimation that increases the speed of coding process while maintaining the video visual quality. In order to decrease the processing time and computational cost of these methods, which are: i) particularly needed in mobile video coding applications such as mobile phones and palmtops; ii) in real time applications such as videoconference, this work proposes a motion estimation method that eliminates the processing of blocks that does not produce benefits for the half-pixel search. The simulation results show that the proposed method reduces the processing time in 76,17%, 75,95% and 11,74% in average when respectively compared with Full Search, JM98 and P021 methods, without relevant impact in video quality. Besides, this method produces a bits rate increase of 8,72% , 8,06% e 8,02% in average when compared with the same methods. This is in our opinion, an inexpensive price to be paid when the time benefits are considered.