Στόχος της παρούσας διπλωματικής εργασίας είναι η μελέτη της ομαδοποίησης των προσημασμένων γράφων. / The main theme of this dissertation is the blockmodeling of signed graphs.

A binary clutter is cycling if its packing and covering linear program have integral optimal solutions for all Eulerian edge capacities. We prove that the clutter of odd st- walks of a signed graph is cycling if and only if it does not contain as a minor the clutter of odd circuits of K5 nor the clutter of lines of the Fano matroid. Corollaries of this result include, of many, the characterization for weakly bipartite signed graphs, packing two- commodity paths, packing T-joins with small |T|, a new result on covering odd circuits of a signed graph, as well as a new result on covering odd circuits and odd T-joins of a signed graft.

In recent years several depth cameras have emerged on the consumer market, creating many interesting possibilities forboth professional and recreational usage. One example of such a camera is the Microsoft Kinect sensor originally usedwith the Microsoft Xbox 360 game console. In this master thesis a system is presented that utilizes this device in order to create an as accurate as possible 3D reconstruction of an indoor environment. The major novelty of the presented system is the data structure based on signed distance fields and voxel octrees used to represent the observed environment. / Under de senaste åren har flera olika avståndskameror lanserats på konsumentmarkanden. Detta har skapat många intressanta applikationer både i professionella system samt för underhållningssyfte. Ett exempel på en sådan kamera är Microsoft Kinect som utvecklades för Microsofts spelkonsol Xbox 360. I detta examensarbete presenteras ett system som använder Kinect för att skapa en så exakt rekonstruktion i 3D av en innomhusmiljö som möjligt. Den främsta innovationen i systemet är en datastruktur baserad på signed distance fields (SDF) och octrees, vilket används för att representera den rekonstruerade miljön.

A graph in which every edge is labeled positive or negative is called a signed graph. We determine the number of ways to sign the edges of the McGee graph with exactly two negative edges up to switching isomorphism. We characterize signed graphs that are both sign-symmetric and have a frustration index of 1. We prove some results about which signed graphs on complete multipartite graphs have frustration indices 2 and 3. In the final part, we derive the relationship between the frustration index and the number of parts in a sign-symmetric signed graph on complete multipartite graphs.

No description available.

Background. Rasterization of triangle geometry has been the dominating rendering technique in the real-time rendering industry for many years. However, triangles are not always easy to work with for content creators. With the introduction of hardware-accelerated ray tracing, rasterization-based lighting techniques have been steadily replaced by ray tracing techniques. This shift may signify the opportunity of exploring other, more easily manipulated, geometry-type alternatives compared to triangle geometry. One such geometry type is implicit surfaces. Objectives. This thesis investigates the rendering speed, editing speed, and image quality of different implicit surface rendering techniques using a state-of-the-art, hardware-accelerated, path tracing implementation. Furthermore, it investigates how implicit surfaces may be edited in real time and how editing affects rendering. Methods. A baseline direct sphere tracing algorithm is implemented to render implicit surfaces. Additionally, dense and narrow band discretization algorithms that sphere trace a discretization of the implicit surface are implemented. For each technique, two variations that provide potential benefits in rendering speed are also tested. Additionally, a real-time implicit surface editor that can utilize all the mentioned rendering techniques is created. Rendering speed, editing speed, and image quality metrics are captured for all techniques using different scenes created with the editor and an existing hardware-accelerated path tracing solution. Image quality differences are measured using mean squared error and the image difference evaluator FLIP. Results. Direct sphere tracing achieves the best image quality results but has the slowest rendering speed. Dense discretization achieves the best rendering speed in most tests and achieves better image quality results compared to narrow band discretization. Narrow band discretization achieves significantly better editing speed than both direct sphere tracing and dense discretization. All variations of each algorithm achieve better or equal rendering and editing speed compared to their standard implementation. All algorithms achieve real-time rendering and editing performance. However, only discretized methods display real-time rendering performance for all scenes, and only narrow band discretization displays real-time editing performance for a larger number of primitives. Conclusions. Implicit surfaces can be rendered and edited in real time while using a state-of-the-art, hardware-accelerated, path tracing algorithm. Direct sphere tracing degrades in performance when the implicit surface has an increased number of primitives, whereas discretization techniques perform independently of this. Furthermore, narrow band discretization is fast enough so that editing can be performed in real time even for implicit surfaces with a large number of primitives, which is not the case for direct sphere tracing or dense discretization. / Bakgrund. Triangelrastrering har varit den dominerande renderingstekniken inom realtidsgrafik i flera år. Trianglar är dock inte alltid lätta att jobba med för skapare av grafiska modeller. Med introduktionen av hårdvaruaccelererad strålspårning har rastreringsbaserade ljussättningstekniker stadigt ersatts av strålspårningstekniker. Detta skifte innebär att det kan finnas möjlighet för att utforska andra, mer lättredigerade geometrityper jämfört med triangelgeometri, exempelvis implicita ytor. Syfte. Detta examensarbete undersöker rendering- och redigeringshastigheten, samt bildkvaliteten av olika renderingstekniker för implicita ytor tillsammans med en spjutspetsalgoritm för hårdvaruaccelererad strålföljning. Den undersöker även hur implicita ytor kan redigeras i realtid och hur det påverkar rendering. Metod. En direkt sfärspårningsalgoritm implementeras som baslinje för att rendera implicita ytor. Även algoritmer som utför sfärstrålning över en kompakt- och smalbandsdiskretisering av den implicita ytan implementeras. För varje teknik implementeras även två variationer som potentiellt kan ge bättre prestanda. Utöver dessa renderingstekniker skapas även ett redigeringsverktyg för implicita ytor. Renderingshastighet, redigeringshastighet, och bildkvalité mäts för alla tekniker över flera olika scener som har skapats med redigeringsverktyget tillsammans med en hårdvaruaccelererad strålföljningsalgoritm. Skillnader i bildkvalité utvärderas med hjälp av mean squared error och evalueringsverktyget för bildskillnader som heter FLIP. Resultat. Direkt sfärspårning åstadkommer bäst bildkvalité, men har den långsammaste renderingshastigheten. Kompakt diskretisering renderar snabbast i de flesta tester och åstadkommer bättre bildkvalité än vad smalbandsdiskretisering gör. Smalbandsdiskretisering åstadkommer betydligt bättre redigeringshastighet än både direkt sfärspårning och kompakt diskretisering. Variationerna för respektive algoritm presterar alla lika bra eller bättre än standardvarianten för respektive algoritm. Alla algoritmer uppnår realtidsprestanda inom rendering och redigering. Endast diskretiseringsmetoderna uppnår dock realtidsprestanda för rendering med alla scener och endast smalbandsdiskretisering uppnår realtidsprestanda för redigering med ett större antal primitiver. Slutsatser. Implicita ytor kan renderas och redigeras i realtid tillsammans med en spjutspetsalgoritm för hårdvaruaccelererad strålföljning. Vid användning av direkt sfärstrålning minskar renderingshastigheten när den ytan består av ett stort antal primitiver. Diskretiseringstekniker har dock en renderingshastighet som är oberoende av antalet primitiver. Smalbandsdiskretisering är tillräckligt snabb för att redigering ska kunna ske i realtid även för implicita ytor som består stora antal primitiver.

Dans ce travail, nous proposons des procédures de test paramétriques et nonparamétrique localement et asymptotiquement optimales au sens de Hajek et Le Cam, pour trois modèles d'asymétrie. La construction de modèles d'asymétrie est un sujet de recherche qui a connu un grand développement ces dernières années, et l'obtention des tests optimaux (pour trois modèles différents) est une étape essentielle en vue de leur mise en application. Notre approche est fondée sur la théorie de Le Cam d'une part, pour obtenir les propriétés de normalité asymptotique, bases de la construction des tests paramétriques optimaux, et la théorie de Hajek d'autre part, qui, via un principe d'invariance permet d'obtenir les procédures non-paramétriques. Nous considérons dans ce travail deux classes de distributions univariées asymétriques, l'une fondée sur un développement d'Edgeworth (décrit dans le Chapitre 1), et l'autre construite en utilisant un paramètre d'échelle différent pour les valeurs positives et négatives (le modèle de Fechner, décrit dans le Chapitre 2). Le modèle d'asymétrie elliptique étudié dans le dernier chapitre est une généralisation multivariée du modèle du Chapitre 2. Pour chacun de ces modèles, nous proposons de tester l'hypothèse de symétrie par rapport à un centre fixé, puis par rapport à un centre non spécifié. Après avoir décrit le modèle pour lequel nous construisons les procédures optimales, nous obtenons la propriété de normalité locale asymptotique. A partir de ce résultat, nous sommes capable de construire les tests paramétriques localement et asymptotiquement optimaux. Ces tests ne sont toutefois valides que si la densité sous-jacente f est correctement spécifiée. Ils ont donc le mérite de déterminer les bornes d'efficacité paramétrique, mais sont difficilement applicables. Nous adaptons donc ces tests afin de pouvoir tester les hypothèses de symétrie par rapport à un centre fixé ou non, lorsque la densité sous-jacente est considérée comme un paramètre de nuisance. Les tests que nous obtenons restent localement et asymptotiquement optimaux sous f, mais restent valides sous une large classe de densités. A partir des propriétés d'invariance du sous-modèle identifié par l'hypothèse nulle, nous obtenons les tests de rangs signés localement et asymptotiquement optimaux sous f, et valide sous une vaste classe de densité. Nous présentons en particulier, les tests fondés sur les scores normaux (ou tests de van der Waerden), qui sont optimaux sous des hypothèses Gaussiennes, tout en étant valides si cette hypothèse n'est pas vérifiée. Afin de comparer les performances des tests paramétriques et non paramétriques présentés, nous calculons les efficacités asymptotiques relatives des tests non paramétriques par rapport aux tests pseudo-Gaussiens, sous une vaste classe de densités non-Gaussiennes, et nous proposons quelques simulations.

Antes de se fazer uma estimativa ou uma simulação geoestatística, os domínios geológicos devem ser modelados de forma que cada domínio utilize apenas dados que pertencem a ele. Na industria mineral a incerteza oriunda dos teores geralmente é levada em consideração, entretanto a incerteza gerada pelo modelo nem sempre é analisada. Sabendo que a maior fonte de incerteza está na transição de uma litologia para outra, essa dissertação visa avaliar a incerteza do modelo geológico através de simulações de funções distâncias assinaladas em zonas de maior incerteza, gerando vários modelos com diferentes proporções de cada litologias. Um estudo de caso em um banco de dados real com alta complexidade geológica é utilizado para avaliar o uso da metodologia. O método se mostrou eficaz para avaliar o impacto da diferença de volume que cada litologia pode alcançar, demonstrando a importância de medir a incerteza na construção de modelos geológicos. / Before making an estimation or a geostatistical simulation, geological domains must be modeled so that each domain uses only data that belongs to it. In the mineral industry the uncertainty derived from the grades is generally taken into account, however the uncertainty generated by the model is not always analyzed. Knowing that the greatest source of uncertainty is in the transition from one lithology to another, this dissertation aims to evaluate the uncertainty of the geological model through signed distances function simulation in uncertainty zones, generating several models with different proportions of each lithology. A case study in a real dataset with high geological complexity is used to evaluate the use of the methodology. The method proved effective in assessing the impact of the volume difference that each lithology can reach, demonstrating the importance of measuring uncertainty in the construction of geological models.

Previamente à cada estimativa ou simulação geoestatística os domínios geológicos do depósito devem ser modelados, o que tradicionalmente é feito de forma manual por um geomodelador, em um processo laborioso, demorado e subjetivo. Por essa razão novas técnicas conhecidas como métodos implícitos veem surgindo. Essas técnicas fornecem algoritmos que substituem o processo de digitalização manual dos métodos explícitos por alguma forma de procedimento automático. Essa dissertação visita alguns métodos implícitos bem estabelecidos com atenção especial à modelagem geológica implícita com funções distância assinalada. Um estudo de caso em um banco de dados real é apresentado e a aplicabilidade do método discutida. Embora não substitua por completo um geomodelador experiente, o método provou ser capaz de gerar modelos geológicos semi-automáticos realistas a partir dos dados amostrais, e se mostra útil principalmente nas fases iniciais da pesquisa mineral. / Prior to every geostatistical estimation or simulation study there is a need for delimiting the geologic domains of the deposit, which is traditionally done manually by a geomodeler in a laborious, time consuming and subjective process. For this reason, novel techniques referred to as implicit modelling have appeared. These techniques provide algorithms that replace the manual digitization process of the traditional methods by some form of automatic procedure. This dissertation covers a few well established implicit methods currently available with special attention to the signed distance function methodology. A case study based on a real dataset was performed and its applicability discussed. Although it did not replace an experienced geomodeler, the method proved to be capable in creating semi-automatic geological models from the sampling data, especially in the early stages of exploration.

Os surdos possuem a capacidade de utilizar a língua oral para se comunicar limitada e por isso tem como língua materna as línguas gestuais. Isso dificulta a utilização, de maneira satisfatória, dos serviços básicos, bem como a inserção na sociedade ouvinte, que é composta pela maioria da população. Devido ao fato desta língua ser gestual, é viável afirmar que se pode simular seus sinais através de animação de humanos virtuais, sem perder a percepção correta do significado do mesmo (que palavra o sinal representa). O presente trabalho descreve uma técnica de animação aplicada em LIBRAS. A idéia principal é, baseado na descrição da animação de um determinado sinal, executar seu movimento de forma mais, ou menos ampla para que se consiga aproveitar o espaço disponível para a gesticulação, sem entretanto perder o significado do sinal. A animação computacional de um sinal deve o mais próximo possível do real, ou seja, seu significado deve ser facilmente entendido e sua execução deve ser natural (suave e contínua). Para isso os sinais devem ser definidos de acordo com as limitações de movimentação das articulações humanas, bem como ao campo de visão do receptor. Além disso alguns parâmetros devem ser analisados e definidos: velocidade do movimento, tempo e amplitude dos sinais. Outro aspecto importante a ser tratado é o espaço que é disponível para a execução do sinal: dependendo do espaço, o sinal deve ser animado de forma a se adequar a ele. A implementação da técnica resultou em um sistema de animação para LIBRAS composto por três módulos: • um modelador do humano virtual, de forma que as articulações e DOFs deste sejam anatomicamente coerentes com a realidade; • um gerador de gestos, o qual é responsável pela transformação dos parâmetros como velocidade, tempo de execução do gesto, configuração das juntas, em um arquivo que descreve a animação da pose. Cabe ressaltar que as palavras em LIBRAS são conhecidas como sinais. Já um sinal é composto por um ou vários gestos e estes são compostos por poses; • um animador, o qual é responsável por gerar a animação de um sinal previamente criado, adequando (se necessário) a amplitude deste sinal ao espaço disponível para a execução do mesmo. O sistema criado foi submetido a testes para que a técnica fosse validada. O que se buscou com os testes foi verificar se os sinais gerados eram passíveis de entendimento, ou seja, se a animação gerada representava determinada palavra. Todos os aspectos acima mencionados são apresentados e analisados em detalhes. / Deaf people have a limited capacity of using oral language to communicate. Because of this, they use gestural languages as their native language. This makes it especially difficult for them to make use of basic services in a satisfactory way and to properly integrate the hearing world, to which the majority of the population belongs. Due to the fact that this language is only gestural, it is possible to say that the signs it comprises of can be simulated with the animation of virtual humans without losing the correct perception of their inherent meanings (what words they represent). This work describes a technique of animation for LIBRAS. The main idea is to take the movement of a sign from a description of its animation and execute it in a more or less wide manner in order to better use the available space for gesticulation without losing the meaning. The computer animation of a sign must be as close to the real gesture as possible. Its meaning must be easily understood and its execution must be natural (smooth and continuous). For that, the signs must be defined in accordance with the movement limitations imposed by the human joints, and the field of view of the receiver. Besides that, some relevant parameters must be analyzed and defined: speed of the movement, time and amplitude of the signs. Another important aspect to be addressed is the space that is available for the execution of the sign: depending on the area, the sign must be animated in a manner that makes it properly fit in it. The implementation of the technique resulted in a animation system for LIBRAS, that consists of three modules: • a virtual human modeler, so that the joints and DOFs are anatomically consistent with reality; • a gesture generator, which is responsible for the processing of parameters such as speed, time of execution of the gesture, joint configuration, in a file that describes the animation of the pose. It is worth emphasizing that the words in LIBRAS are known as signs. Already a sign is composed of one or more gestures and they are composed of poses; • an animator, which is responsible for generating the animation of a previously created sign, fitting (if necessary) the sign amplitude to the space available for its animation. The generated system has been submitted for tests in order to validate the technique. The goal of the tests was to check whether the generated signs were understandable - if the generated animation represented a certain word. All aspects above are presented and analyzed in detail.