RCAAP Repository

O presente texto descreve a tese de doutorado intitulada Análise de Formas usando Wavelets em Grafos. O tema está relacionado à área de Visão Computacional, particularmente aos tópicos de Caracterização, Descrição e Classificação de Formas. Dentre os métodos da extensa literatura em Análise de Formas 2D, percebe-se uma presença menor daqueles baseados em grafos com topologia arbitrária e irregular. As contribuições desta tese procuram preencher esta lacuna. É proposta uma metodologia baseada no seguinte pipeline : (i) Amostragem da forma, (ii) Estruturação das amostras em grafos, (iii) Função-base definida nos vértices, (iv) Análise multiescala de grafos por meio da Transformada Wavelet Espectral em grafos, (v) Extração de Características da Transformada Wavelet e (vi) Discriminação. Para cada uma das etapas (i), (ii), (iii), (v) e (vi), são inúmeras as abordagens possíveis. Um dos desafios é encontrar uma combinação de abordagens, dentre as muitas alternativas, que resulte em um pipeline eficaz para nossos propósitos. Em particular, para a etapa (iii), dado um grafo que representa uma forma, o desafio é identificar uma característica associada às amostras que possa ser definida sobre os vértices do grafo. Esta característica deve capturar a influência subjacente da estrutura combinatória de toda a rede sobre cada vértice, em diversas escalas. A Transformada Wavelet Espectral sobre os Grafos revelará esta influência subjacente em cada vértice. São apresentados resultados obtidos de experimentos usando formas 2D de benchmarks conhecidos na literatura, bem como de experimentos de aplicações em astronomia para análise de formas de galáxias do Sloan Digital Sky Survey não-rotuladas e rotuladas pelo projeto Galaxy Zoo 2 , demonstrando o sucesso da técnica proposta, comparada a abordagens clássicas como Transformada de Fourier e Transformada Wavelet Contínua 2D.

A criptografia de chave pública sem certificado (certificateless) é uma alternativa ao modelo convencional de criptografia assimétrica, pois a autenticação da chave pública ocorre implicitamente durante a execução dos protocolos, sem a necessidade de gerenciamento e distribuição de certificados digitais. Potencialmente reduz custos computacionais e o nível de segurança alcançado é maior quando comparado ao modelo baseado em identidade. Nesta tese de doutorado, modelos formais de segurança para acordo de chave com autenticação sem certificado são aprimorados visando dois objetivos paralelos: (1) aumentar o nível de confiança que usuários podem depositar na autoridade geradora de chaves secretas parciais e (2) viabilizar protocolos que sejam eficientes computacionalmente e com propriedades de segurança relevantes, dentre as quais se inclui resistência a ataques de adversários que têm total controle do canal de comunicação e que podem substituir chaves públicas de usuários por valores arbitrários. Para atestar que as melhorias efetuadas são praticáveis e possibilitam que os objetivos sejam alcançados, novos protocolos são propostos para o caso que envolve dois participantes na comunicação. Os protocolos são provados seguros, usando-se técnica de redução de problemas computacionais.

O presente texto descreve métodos e apresenta resultados do projeto de pesquisa de mestrado intitulado \"Dois Problemas em Análise de Formas de Estruturas de Ramificação\". Ambos os problemas abordados estão relacionados às sub-áreas da Análise de Formas denominadas Caracterização e Descrição de Formas. O primeiro problema consiste na investigação de um conjunto de características propostas para distingüir, primeiramente, entre estruturas de ramificação de vasos sangüíneos em imagens de retina segmentadas manualmente e automaticamente. A seguir, as mesmas características são aplicadas para discernir entre estruturas de ramificação de vasos sangüíneos em imagens de retina com e sem retinopatia diabética proliferativa (Proliferative Diabetic Retinopathy - PDR). A PDR é uma das patologias associadas à diabetes, que pode culminar na cegueira do indivíduo. Diagnósticos são possíveis por meio de imagens de fundo de olho e, quando efetuados precocemente, viabilizam intervenções oportunas evitando a perda da visão. Neste trabalho, 27 imagens digitais de fundo de olho foram segmentadas por dois processos distintos, isto é, segmentação manual por um especialista e a segmentação automática, mediante a transformada contínua Wavelet - CWT e classificadores estatísticos. Visando à caracterização destas formas, um conjunto de 08 características foi proposto. Este conjunto foi formado por três grupos, a saber: descritores tradicionais geométricos (Área, Perímetro e Circularidade), descritores associados à transformada wavelet ( 2o momento estatístico da distribuição de módulos da CWT, Entropia de Orientação da distribuição de fases da CWT e Curvatura) e um descritor fractal (Dimensão de Correlação - Global e Mediana). Uma Análise Discriminante Linear LDA revelou que as características geométricas tradicionais não detectam o início da retinopatia diabética proliferativa. A maior capacidade discriminante individual foi exibida pela Curvatura, com Área sob a curva ROC de 0.76. Um subconjunto com 6 características apresentou grande capacidade discriminante com Área sob a curva ROC de 0.90. O segundo problema diz respeito à extração de contorno de estruturas de ramificação bidimensionais de neurônios tridimensionais. Este trabalho contribui originalmente com uma solução para este problema, propondo dois algoritmos desenvolvidos para Rastreamento de Ramos e Extração do Contorno Paramétrico de estruturas de ramificação, capazes de transpor regiões críticas formadas por cruzamentos ocasionados pela projeção de estruturas 3D no plano das imagens 2D. Grande parte dos métodos baseados em contorno para análise de formas de estruturas de ramificação de células neuronais não produz representações corretas destas formas, devido à presença de sobreposições entre processos neuronais, levando os algoritmos tradicionais de extração de contorno a ignorar as regiões mais internas destas estruturas, gerando representações incompletas. O sistema proposto neste trabalho foi desenvolvido objetivando a solução do problema de extração de contorno, mesmo na presença de múltiplas sobreposições. Inicialmente, a imagem de entrada é pré-processada, gerando um esqueleto 8-conexo com ramos de um pixel de largura, um conjunto de sementes de sub-árvores dendríticas e um conjunto de regiões críticas (bifurcações e cruzamentos). Para cada sub-árvore, o algoritmo de rastreamento rotula todos os pixels válidos de um ramo, até chegar em uma região crítica, onde o algoritmo decide a direção em que deve continuar o rastreamento. Nosso algoritmo mostrou-se robusto, mesmo quando aplicado a imagens com segmentos paralelos muito próximos. Resultados obtidos com imagens reais (neurônios) são apresentados.

Nesta tese, dois diferentes problemas de programação da produção são abordados, o Flexible JobShop Scheduling Problem com Flexibilidade de sequenciamento e o Flowshop Scheduling Problem com tempos de espera e permutação de sequência. Para ambos, inicialmente um algoritmo list scheduling (LS) que explora características do problema é desenvolvido e então estendido para um método do tipo Beam Search (BS) que utiliza o LS em seus principais elementos: (1) expansão dos níveis, (2) avaliação local dos candidatos e (3) avaliação global dos candidatos. Todos os métodos propostos são determinísticos e seus pseudocódigos são cuidadosamente descritos para garantir a replicabilidade dos resultados reportados. O desempenho dos métodos propostos são avaliados utilizando instâncias e outros métodos heurísticos da literatura. Os resultados computacionais obtidos mostram a eficiência das heurísticas propostas que superaram os métodos da literatura utilizando pouco tempo computacional.

Um Processo de Decisão Markoviano (MDP) pode ser usado para modelar problemas de decisão sequencial. No entanto, podem existir limitações na obtenção de probabilidades para modelagem da transição de estados ou falta de confiabilidade nas informações existentes sobre estas probabilidades. Um modelo menos restritivo e que pode resolver este problema é o Processo de Decisão Markoviano com Probabilidades Intervalares (BMDP), que permite a representação imprecisa das probabilidades de transição de estados e raciocínio sobre uma solução robusta. Para resolver BMDPs de horizonte infinito, existem os algoritmos síncronos de Iteração de Valor Intervalar e Iteração de Política Robusto, que são ineficientes quando o tamanho do espaço de estados é grande. Neste trabalho são propostos algoritmos assíncronos de Iteração de Política baseados no particionamento do espaço de estados em subconjuntos aleatórios (Robust Asynchronous Policy Iteration - RAPI) ou em componentes fortemente conexos (Robust Topological Policy Iteration - RTPI). Também são propostas formas de inicializar a função valor e a política dos algoritmos, de forma a melhorar a convergência destes. O desempenho dos algoritmos propostos é avaliado em comparação com o algoritmo de Iteração de Política Robusto para BMDPs para domínios de planejamento existentes e um novo domínio proposto. Os resultados dos experimentos realizados mostram que (i) quanto mais estruturado é o domínio, melhor é o desempenho do algoritmo RTPI; (ii) o uso de computação paralela no algoritmo RAPI possui um pequeno ganho computacional em relação à sua versão sequencial; e (iii) uma boa inicialização da função valor e política pode impactar positivamente o tempo de convergência dos algoritmos.

Knowledge representation in ontologies is based on Description Logics, which are decidable fragments of first-order logic. Since knowledge is not static, it is necessary to deal with the acquisition of new information, which may contradict the existing knowledge. Belief Revision aims to solve this problem, but the classical AGM framework assumes an ideal agent that is able to deal with logically closed sets of sentences, and some of its generalisations for belief bases (such as ontologies represented in Description Logics) may lead to loss of information due to the fact that no sentence can be added when a contraction operation is performed. In this work, we analyse kernel constructions for pseudo-contraction operations and their formal properties. Also, we show the close relationship between concepts and definitions of Belief Revision and Ontology Repair (such as pseudo-contractions and gentle repairs, respectively), and we propose a unified notation for their operations.

A teoria de Compressive Sensing proporciona uma nova estratégia de aquisição e recuperação de dados com bons resultados na área de processamento de imagens. Esta teoria garante recuperar um sinal com alta probabilidade a partir de uma taxa reduzida de amostragem por debaixo do limite de Nyquist-Shanon. O problema de recuperar o sinal original a partir das amostras consiste em resolver um problema de otimização. O método de Gradiente Espectral Projetado é um método para minimizar funções suaves em conjuntos convexos que tem sido aplicado com frequência ao problema de recuperar o sinal original a partir do sinal amostrado. Este trabalho dedica-se ao estudo da aplicação do Método do Gradiente Espectral Projetado ao problema de Compressive Sensing.

Uma importante etapa do desenvolvimento de software é o de levantamento e análise dos requisitos. Porém, durante esta etapa podem ocorrer inconsistências que prejudicarão o andamento do projeto. Além disso, após finalizada a especificação, o cliente pode querer acrescentar ou modificar as funcionalidades do sistema. Tudo isso requer que a especificação do software seja revista, mas isso é altamente custoso, tornando necessário um processo automatizado para simplificar tal revisão. Para lidar com este problema, uma das abordagens utilizadas tem sido o processo de Revisão de Crenças, juntamente com o processo de Verificação de Modelos. O objetivo deste trabalho é utilizar o processo de revisão de crenças e verificação de modelos para avaliar especificações de um projeto procurando inconsistências, utilizando o fragmento universal da Computation Tree Logic (CTL), conhecido como ACTL, e revisá-las gerando sugestões de mudanças na especificação. A nossa proposta é traduzir para lógica clássica tanto o modelo (especificação do software) quanto a propriedade a ser revisada, e então aplicar um resolvedor SAT para verificar a satisfazibilidade da fórmula gerada. A partir da resposta do resolvedor SAT, iremos gerar sugestões válidas de mudanças para a especificação, fazendo o processo de tradução reversa da lógica clássica para o modelo original.

Especificações formais são úteis para descrever o que um sistema deve fazer sem definir como, e, em virtude da sua natureza formal e da possibilidade de abstração, é possível analisá-las sistematicamente. No entanto, o uso de especificações formais como parte do desenvolvimento de software não constitui prática comum. Isso se dá, em parte, pelo fato de existirem apenas um pequeno número de metodologias e ferramentas adequadas que dêem suporte a esse desenvolvimento. O primeiro objetivo deste trabalho é propor uma metodologia de desenvolvimento que possibilite, a partir de uma especificação formal em notação Z, produzir uma implementação dessa especificação em Java. Essa metodologia centra-se na geração do esqueleto da aplicação Java e na instrumentação desse esqueleto com mecanismos de verificação de condições (invariantes, pré e pós-condições) e rastreamento de violações dessas condições. Através desses mecanismos, possibilita-se intercalar desenvolvimento formal e informal no processo global de desenvolvimento de software. O segundo objetivo é desenvolver uma ferramenta que implemente parte dessa metodologia, produzindo uma implementação parcial que deverá ser complementada pelo usuário.

O uso de abordagens de predição de mudanças conjuntas auxilia os desenvolvedores a encontrar artefatos que mudam conjuntamente em uma tarefa. No passado, pesquisadores utilizaram análise estrutural para construir modelos de predição. Mais recentemente, têm sido propostas abordagens que utilizam informações históricas e análise textual do código fonte. Apesar dos avanços obtidos, os desenvolvedores de software ainda não usam essas abordagens amplamente, presumidamente por conta do número de falsos positivos. A hipótese desta tese é que informações contextuais obtidas das tarefas, da comunicação dos desenvolvedores e das mudanças dos artefatos descrevem as circunstâncias e condições em que as mudanças conjuntas ocorrem e podem ser utilizadas para realizar a predição de mudanças conjuntas. O objetivo desta tese consiste em avaliar se o uso de informações contextuais melhora a predição de mudanças conjuntas entre dois arquivos em relação às regras de associação, que é uma estratégia frequentemente usada na literatura. Foram construídos modelos de predição específicos para cada par de arquivos, utilizando as informações contextuais em conjunto com o algoritmo de aprendizagem de máquina random forest. Os modelos de predição foram avaliados em 129 versões de 10 projetos de código aberto da Apache Software Foundation. Os resultados obtidos foram comparados com um modelo baseado em regras de associação. Além de avaliar o desempenho dos modelos de predição também foram investigadas a influência do modo de agrupamento dos dados para construção dos conjuntos de treinamento e teste e a relevância das informações contextuais. Os resultados indicam que os modelos baseados em informações contextuais predizem 88% das mudanças corretamente, contra 19% do modelo de regras de associação, indicando uma precisão 3 vezes maior. Os modelos criados com informações contextuais coletadas em cada versão do software apresentaram maior precisão que modelos construídos a partir de um conjunto arbitrário de tarefas. As informações contextuais mais relevantes foram: o número de linhas adicionadas ou modificadas, número de linhas removidas, code churn, que representa a soma das linhas adicionadas, modificadas e removidas durante um commit, número de palavras na descrição da tarefa, número de comentários e papel dos desenvolvedores na discussão, medido pelo valor do índice de intermediação (betweenness) da rede social de comunicação. Os desenvolvedores dos projetos foram consultados para avaliar a importância dos modelos de predição baseados em informações contextuais. Segundo esses desenvolvedores, os resultados obtidos ajudam desenvolvedores novatos no projeto, pois não têm conhecimento da arquitetura e normalmente não estão familiarizados com as mudanças dos artefatos durante a evolução do projeto. Modelos de predição baseados em informações contextuais a partir de mudanças de software são relativamente precisos e, consequentemente, podem ser usados para apoiar os desenvolvedores durante a realização de atividades de manutenção e evolução de software

Nesta dissertacao estudamos problemas de empacotamento de arvores em grafos, com enfase no caso de grafos completos. Denotamos por Ti uma arvore de ordem i. Dizemos que existe um empacotamento de arvores T1, . . . , Tn num grafo G se e possivel encontrar em G subgrafos H1, . . . , Hn, dois a dois disjuntos nas arestas, tais que Hi e isomorfo a Ti. Em 1976, A. Gyarfas e J. Lehel levantaram a seguinte questao, que conjecturaram ter uma resposta positiva: e possivel empaco- tar qualquer sequencia de arvores T1, . . . , Tn no Kn? Esta dissertacao tem como tema principal os estudos realizados por diversos pesquisadores na busca de uma resposta para esta pergunta, que permanece ainda em aberto. Tendo em vista a dificuldade para tratar esta questao, surge natural- mente a pergunta sobre a existencia de classes de arvores para as quais a resposta e afirmativa. Nessa linha, existem diversos resultados positivos, como por exemplo quando queremos empacotar estrelas e caminhos, ou estrelas e biestrelas. Por outro lado, em vez de restringir a classe das arvores, faz sentido restringir o tamanho da sequencia e reformular a pergunta. Por exemplo, dado s < n, e possivel empacotar qualquer sequencia de arvores T1, . . . , Ts no Kn? Em 1983, Bollobas mostrou ? que a resposta e afirmativa se s <= n / sqrt(2). Na primeira parte deste trabalho focamos nosso estudo em questoes desse tipo. Na segunda parte desta dissertacao investigamos algumas conjecturas que foram motivadas pela pergunta levantada por Gyarfas & Lehel. Por exemplo, Hobbs, Bourgeois e Kasiraj formularam a seguinte questao: para n par, e possivel empacotar qualquer sequencia de arvores T1, . . . , Tn no grafo bipartido Kn/2,n-1? Para essa pergunta apresentamos alguns resultados conhecidos analogos aos obtidos para a conjectura de Gyarfas & Lehel. Mais recentemente, Gerbner, Keszegh e Palmer estudaram a seguinte generalizacao da conjectura original: e possivel empacotar qualquer sequencia de arvores T1, . . . , Tk num grafo k-cromatico? Neste trabalho estudamos essas e outras questoes relacionadas e apresentamos os principais resultados que encontramos na literatura.

Cada vez mais o rastreamento do olhar tem sido usado para interação humano-computador em diversos cenários, como forma de interação (usualmente substituindo o mouse, principalmente para pessoas com deficiências físicas) ou estudo dos padrões de atenção de uma pessoa (em situações como fazendo compras no mercado, olhando uma página na internet ou dirigindo um carro). Ao mesmo tempo, dispositivos vestíveis tais quais pequenas telas montadas na cabeça e sensores para medir dados relativos à saúde e exercício físico realizado por um usuário, também têm avançado muito nos últimos anos, finalmente chegando a se tornarem acessíveis aos consumidores. Essa forma de tecnologia se caracteriza por dispositivos que o usuário usa junto de seu corpo, como uma peça de roupa ou acessório. O dispositivo e o usuário estão em constante interação e tais sistemas são feitos para melhorar a execução de uma ação pelo usuário (por exemplo dando informações sobre a ação em questão) ou facilitar a execução de várias tarefas concorrentemente. O uso de rastreadores de olhar em computação vestível permite uma nova forma de interação para tais dispositivos, possibilitando que o usuário interaja com eles enquanto usa as mãos para realizar outra ação. Em dispositivos vestíveis, o consumo de energia é um fator importante do sistema que afeta sua utilidade e deve ser considerado em seu design. Infelizmente, rastreadores oculares atuais ignoram seu consumo e focam-se principalmente em precisão e acurácia, seguindo a ideia de que trabalhar com imagens de alta resolução e frequência maior implica em melhor desempenho. Porém tratar mais quadros por segundo ou imagens com resolução maior demandam mais poder de processamento do computador, consequentemente aumentando o gasto energético. Um dispositivo que seja mais econômico tem vários benefícios, por exemplo menor geração de calor e maior vida útil de seus componentes eletrônicos. Contudo, o maior impacto é o aumento da duração da bateria para dispositivos vestíveis. Pode-se economizar energia diminuindo resolução e frequência da câmera usada, mas os efeitos desses parâmetros na precisão e acurácia da estimação do olhar não foram investigados até o presente. Neste trabalho propomos criar uma plataforma de testes, que permita a integração de alguns algoritmos de rastreamento de olhar disponíveis, tais como Starburst, ITU Gaze Tracker e Pupil, para estudar e comparar o impacto da variação de resolução e frequência na acurácia e precisão dos algoritmos. Por meio de um experimento com usuários analisamos o desempenho e consumo desses algoritmos sob diversos valores de resolução e frequência. Nossos resultados indicam que apenas a diminuição da resolução de 480 para 240 linhas (mantendo a proporção da imagem) já acarreta em ao menos 66% de economia de energia em alguns rastreadores sem perda significativa de acurácia.

O Objetivo deste trabalho foi implementar um resolvedor distribuído para o problema de satisfabilidade em lógica proposicional (SAT) que pudesse ser executado em uma grade de computadores. Foi analisada a influência que o número de máquinas utilizadas pela grade para resolver diversas instâncias do SAT exerce sobre o desempenho do resolvedor implementado

Seleção de serviços em composições distribuídas considera principalmente a qualidade de serviço que atenda requisitos estabelecidos pelo usuário, como por exemplo, preço. No entanto, problemas relacionados a execução de composições de serviços podem ocorrer quando não se considera aspectos relacionados à rede e ao hardware, que afetam diretamente o desempenho da composição. Esse problema se agrava em composições coreografadas, pois a característica descentralizada requer um maior esforço para que essas informações possam ser consideradas em uma perspectiva global. Dessa forma, apesar da descentralização apresentar vantagens, é necessário que requisitos de qualidade de serviço da composição também sejam considerados em coreografias de serviços web para que a escolha de serviços para desempenhar um papel leve em consideração parâmetros importantes que podem afetar no desempenho da composição. Este trabalho apresenta um mecanismo, implementado sobre o framework OpenKnowledge, para selecionar serviços web em ambientes coreografados considerando primeiramente estimativas de atraso, taxa de perda e por fim considera a utilização de outros parâmetros, como utilização de CPU. Os primeiros experimentos em diferentes cenários de rede confirmaram as vantagens da proposta em relação a um seletor de serviços que ignora aspectos relacionados com a rede. Obteve-se ganhos de 20 a 97% no que diz respeito ao tempo total da execução da coreografia. Em seguida, experimentos inserindo utilização de CPU na escolha dos serviços confirmaram as vantagens de utilização de diferentes parâmetros para seleção de serviços em coreografias.

Wireless Sensor Networks (WSN) are distributed sensing network systems composed of tiny networked devices. These systems are employed to develop applications for sensing and acting on the environment. Each network device, or node, is equipped with sensors and sometimes actuators as well. WSNs typically have limited power, processing, and storage capability, and are also subject to faults, especially when deployed in harsh environments. Given WSNs limitations, application developers often design fault-tolerance mechanisms. Although developers implement some fault-tolerance mechanisms in hardware, most are implemented in software. Indeed, WSN application development mostly occurs at a low level, close to the operating system, which forces developers to focus away from application logic and dive into WSNs technical background. Some have proposed high-level programming solutions, such as macroprogramming languages and frameworks; however, few deal with fault-tolerance. This dissertation aims to incorporate fault-tolerance features into Srijan, an open-source WSN macroprogramming framework based on a mixed declarative-imperative language called Abstract Task Graph (ATaG). We augment Srijans framework to support code generation for dealing with devices that crash or report meaningless values. We present our feature implementation here, along with an evaluation of the tool, demonstrating that it is possible to provide a macroprogramming framework with appropriate support for developing fault-tolerant WSN applications.

Planejamento Probabilístico estuda os problemas de tomada de decisão sequencial de um agente, em que as ações possuem efeitos probabilísticos, modelados como um processo de decisão markoviano (Markov Decision Process - MDP). Dadas a função de transição de estados probabilística e os valores de recompensa das ações, é possível determinar uma política de ações (i.e., um mapeamento entre estado do ambiente e ações do agente) que maximiza a recompensa esperada acumulada (ou minimiza o custo esperado acumulado) pela execução de uma sequência de ações. Nos casos em que o modelo MDP não é completamente conhecido, a melhor política deve ser aprendida através da interação do agente com o ambiente real. Este processo é chamado de aprendizado por reforço. Porém, nas aplicações em que não é permitido realizar experiências no ambiente real, por exemplo, operações de venda, é possível realizar o aprendizado por reforço sobre uma amostra de experiências passadas, processo chamado de aprendizado por reforço em lote (Batch Reinforcement Learning). Neste trabalho, estudamos técnicas de aprendizado por reforço em lote usando um histórico de interações passadas, armazenadas em um banco de dados de processos, e propomos algumas formas de melhorar os algoritmos existentes. Como um estudo de caso, aplicamos esta técnica no aprendizado de políticas para o processo de venda de impressoras de grande formato, cujo objetivo é a construção de um sistema de recomendação de ações para vendedores iniciantes.

People with severe motor disabilities may communicate using their eye movements aided by a virtual keyboard and an eye tracker. Text entry by gaze may also benefit users immersed in virtual or augmented realities, when they do not have access to a physical keyboard or touchscreen. Thus, both users with and without disabilities may take advantage of the ability to enter text by gaze. However, methods for text entry by gaze are typically slow and uncomfortable. In this thesis we propose EyeSwipe as a step further towards fast and comfortable text entry by gaze. EyeSwipe maps gaze paths into words, similarly to how finger traces are used on swipe-based methods for touchscreen devices. A gaze path differs from the finger trace in that it does not have clear start and end positions. To segment the gaze path from the user\'s continuous gaze data stream, EyeSwipe requires the user to explicitly indicate its beginning and end. The user can quickly glance at the vicinity of the other characters that compose the word. Candidate words are sorted based on the gaze path and presented to the user. We discuss two versions of EyeSwipe. EyeSwipe 1 uses a deterministic gaze gesture called Reverse Crossing to select both the first and last letters of the word. Considering the lessons learned during the development and test of EyeSwipe 1 we proposed EyeSwipe 2. The user emits commands to the interface by switching the focus between regions. In a text entry experiment comparing EyeSwipe 2 to EyeSwipe 1, 11 participants achieved an average text entry rate of 12.58 words per minute (wpm) with EyeSwipe 1 and 14.59 wpm with EyeSwipe 2 after using each method for 75 minutes. The maximum entry rates achieved with EyeSwipe 1 and EyeSwipe 2 were, respectively, 21.27 wpm and 32.96 wpm. Participants considered EyeSwipe 2 to be more comfortable and faster, while less accurate than EyeSwipe 1. Additionally, with EyeSwipe 2 we proposed the use of gaze path data to dynamically adjust the gaze estimation. Using data from the experiment we show that gaze paths can be used to dynamically improve gaze estimation during the interaction.

Image segmentation consists on its partition into relevant regions, such as to isolate the pixels belonging to desired objects in the image domain, which is an important step for computer vision, medical image processing, and other applications. Many times automatic segmentation generates results with imperfections. The user can correct them by editing manually, interactively or can simply discard the segmentation and try to automatically generate another result by a different method. Interactive methods combine benefits from manual and automatic ones, reducing user effort and using its high-level knowledge. In seed-based methods, to continue or repair a prior segmentation (presegmentation), avoiding the user to start from scratch, it is necessary to solve the Reverse Interactive Segmentation Problem (RISP), that is, how to automatically estimate the seeds that would generate it. In order to achieve this goal, we first divide the segmented object into its composing cores. Inside a core, two seeds separately always produce the same result, making one redundant. With this, only one seed per core is required. Cores leading to segmentations which are contained in the result of other cores are redundant and can also be discarded, further reducing the seed set, a process called Redundancy Analysis. A minimal set of seeds for presegmentation is generated and the problem of interactive repair can be solved by adding new seeds or removing seeds. Within the framework of the Image-Foresting Transform (IFT), new methods such as Oriented Image-Foresting Transform (OIFT) and Oriented Relative Fuzzy Connectedness (ORFC) were developed. However, there were no known algorithms for computing the core of these methods. This work develops such algorithms, with proof of correctness. The cores also give an indication of the degree of robustness of the methods on the positioning of the seeds. Therefore, a hybrid method that combines GraphCut and the ORFC cores, as well as the Robustness Coefficient (RC), have been developed. In this work, we present another developed solution to repair segmentations, which is based on IFT-SLIC, originally used to generate supervoxels. Experimental results analyze, compare and demonstrate the potential of these solutions.

Um ambiente inteligente é um sistema de computação ubíqua e sensível ao contexto onde os sistemas computacionais embutidos no ambiente, a comunicação entre dispositivos e o ambiente, e a acessibilidade aos serviços do ambiente são transparentes ao usuário. O presente trabalho tem como objetivo propor um modelo para ambientes inteligentes baseado em serviços web semânticos, em que os serviços disponíveis para os dispositivos do ambiente são proporcionados como serviços web e a interação dispositivo - ambiente é feita em um contexto de computação móvel, onde a disponibilidade dos serviços e a informação de contexto do dispositivo mudam freqüentemente. No modelo proposto todas as funcionalidades do ambiente são fornecidas como serviços. Estes serviços são descobertos e executados automaticamente com a finalidade de ajudar o usuário a desenvolver tarefas específicas, permitindo ao usuário se concentrar nas tarefas e não na interação com o ambiente. O modelo se fundamenta na oferta de serviços dirigida pela tarefa a ser desenvolvida, o que é conhecido como Task-driven Computing. Por outro lado, para a automação do processo de descoberta e execução dos serviços é necessário ter uma especificação não ambígua da semântica dos serviços. Empregamos para isso a ontologia WSMO (Web Services Modeling Ontology) que fornece os elementos necessários para a descrição dos serviços disponíveis no ambiente e o contexto do dispositivo. Finalmente, como prova de conceitos do modelo proposto, foi implementado um ambiente inteligente para uma biblioteca. A ativação de um ambiente inteligente baseado no modelo proposto se baseia na definição de ontologias, descrição semântica dos serviços no ambiente e a implementação de serviços web tradicionais.

Funções submodulares aparecem naturalmente em diversas áreas, tais como probabilidade, geometria e otimização combinatória. Pode-se dizer que o papel desempenhado por essas funções em otimização discreta é similar ao desempenhado por convexidade em otimização contínua. Com efeito, muitos problemas em otimização combinatória podem ser formulados como um problema de minimizar uma função submodular sobre um conjunto apropriado. Além disso, submodularidade está presente em vários teoremas ou problemas combinatórios e freqüentemente desempenha um papel essencial em uma demonstração ou na eficiência de um algoritmo. Nesta dissertação, estudamos aspectos estruturais e algorítmicos de funções submodulares, com ênfase nos recentes avanços em algoritmos combinatórios para minimização dessas funções. Descrevemos com detalhes os primeiros algoritmos combinatórios e fortemente polinomiais para esse propósito, devidos a Schrijver e Iwata, Fleischer e Fujishige, além de algumas outras extensões. Aplicações de submodularidade em otimização combinatória também estão presentes neste trabalho.