No description available.

Per al càlcul de la il·luminació global per a la síntesi d'imatges d'escenaris virtuals s'usen mètodes físicament acurats com a radiositat o el ray-tracing. Aquests mètodes són molt potents i capaços de generar imatges de gran realisme, però són molt costosos. A aquesta tesi presenta algunes tècniques per simular i/o accelerar el càlcul de la il·luminació global. La tècnica de les obscurances es basa en la suposició que com més amagat és un punt a l'escena, més fosc s'ha de veure. Es calcula analitzant l'entorn geomètric del punt i ens dóna un valor per a la seva il·luminació indirecta, que no és físicament acurat, però sí aparentment realista.Aquesta tècnica es millora per a entorns en temps real com els videojocs. S'aplica també a entorns de ray-tracing per a la generació d'imatges realistes. En aquest context, el càlcul de seqüències de frames per a l'animació de llums i càmeres s'accelera enormement reusant informació entre frames.Les obscurances serveixen per a simular la il·luminació indirecta d'una escena. La llum directa es calcula apart i de manera independent. El desacoblament de la llum directa i la indirecta és una gran avantatge, i en treurem profit. Podem afegir fàcilment l'efecte de coloració entre objectes sense afegir temps de càlcul. Una altra avantatge és que per calcular les obscurances només hem d'analitzar un entorn limitat al voltant del punt.Per escenes virtuals difuses, la radiositat es pot precalcular i l'escena es pot navegar amb apariència realista, però si un objecte de l'escena es mou en un entorn dinàmic en temps real, com un videojoc, el recàlcul de la il·luminació global de l'escena és prohibitiu. Com les obscurances es calculen en un entorn limitat, es poden recalcular en temps real per a l'entorn de l'objecte que es mou a cada frame i encara aconseguir temps real.A més, podem fer servir les obscurances per a calcular imatges de gran qualitat, o per seqüències d'imatges per una animació, com en el ray-tracing. Això ens permet tractar materials no difusos i investigar l'ús de tècniques normalment difuses com les obscurances en entorns generals. Quan la càmera està estàtica, l'ús d'animació de llum només afecta la il·luminació directa, i si usem obscurances per a la llum indirecta, gràcies al seu desacoblament, el càlcul de sèries de frames per a una animació és molt ràpid. El següent pas és afegir animació de càmera, reusant els valors de les obscurances entre frames. Aquesta última tècnica de reús d'informació de la il·luminació del punt d'impacte entre frames la podem usar per a tècniques acurades d'il·luminació global com el path-tracing, i nosaltres estudiem com reusar aquesta informació de manera no esbiaixada. A més, estudiem diferents tècniques de mostreig per a la semi-esfera, i les obscurances es calculen amb una nova tècnica, aplicant depth peeling amb GPU. / To compute global illumination solutions for rendering virtual scenes, physically accurate methods based on radiosity or ray-tracing are usually employed. These methods, though powerful and capable of generating images with high realism, are very costly. In this thesis, some techniques to simulate and/or accelerate the computation of global illumination are studied. The obscurances technique is based on the supposition that the more occluded is a point in the scene, the darker it will appear. It is computed by analyzing the geometric environment of the point and gives a value for the indirect illumination for the point that is, though not physically accurate, visually realistic. This technique is enhanced and improved in real-time environments as videogames. It is also applied to ray-tracing frameworks to generate realistic images. In this last context, sequences of frames for animation of lights and cameras are dramatically accelerated by reusing information between frames.The obscurances are computed to simulate the indirect illumination of a scene. The direct lighting is computed apart and in an independent way. The decoupling of direct and indirect lighting is a big advantage, and we will take profit from this. We can easily add color bleeding effects without adding computation time. Another advantage is that to compute the obscurances we only need to analyze a limited environment around the point. For diffuse virtual scenes, the radiosity can be precomputed and we can navigate the scene with a realistic appearance. But when a small object moves in a dynamic real-time virtual environment, as a videogame, the recomputation of the global illumination of the scene is prohibitive. Thanks to the limited reach of the obscurance computation, we can recompute the obscurances only for the limited environment of the moving object for every frame and still have real-time frame rates. Obscurances can also be used to compute high quality images, or sequences of images for an animation, in a ray-tracing-like. This allows us to deal with non-diffuse materials and to research the use of a commonly diffuse technique as obscurances in general environments. For static cameras, using light animation only affects to direct lighting, and if we use obscurances for the indirect lighting, thanks to the decoupling of direct and indirect illumination, the computation of a series of frames for the animation is very fast. The next step is to add camera animation, reusing the obscurances results between frames. Using this last technique of reusing the illumination of the hit points between frames for a true global illumination technique as path tracing, we study how we can reuse this information in an unbiased way. Besides, a study of different sampling techniques for the hemisphere is made, obscurances are computed with the depth-peeling technique and using GPU.

This thesis puts forward the conjecture that for <i>n</i> > 3<i>k</i> with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case <i>n</i> = 3<i>k</i> + 1 and <i>k</i> greater than or equal to 1. We do this mainly by means of an induction which takes us from <i>GP</i>(3<i>k</i> + 1, <i>k</i>) to <i>GP</i>(3(<i>k</i> + 2) + 1, <i>k</i> + 2). The induction takes the form of mapping a Hamilton path in the smaller graph piecewise to the larger graph an inserting subpaths we call <i>rotors</i> to obtain a Hamilton path in the larger graph.

Traditional algorithms for hidden Markov model decoding seek to maximize either the probability of a state path or the number of positions of a sequence assigned to the correct state. These algorithms provide only a single answer and in practice do not produce good results. The most mathematically sound of these algorithms is the Viterbi algorithm, which returns the state path that has the highest probability of generating a given sequence. Here, we explore an extension to this algorithm that allows us to find the k paths of highest probabilities. The naive implementation of k best Viterbi paths is highly space-inefficient, so we adapt recent work on the Viterbi algorithm for a single path to this domain. Out algorithm uses much less memory than the naive approach. We then investigate the usefulness of the k best Viterbi paths on the example of transmembrane protein topology prediction. For membrane proteins, even simple path combination algorithms give good explanations, and if we look at the paths we are combining, we can give a sense of confidence in the explanation as well. For proteins with two topologies, the k best paths can give insight into both correct explanations of a sequence, a feature lacking from traditional algorithms in this domain.

This thesis puts forward the conjecture that for <i>n</i> > 3<i>k</i> with <i>k</i> > 2, the generalized Petersen graph, <i>GP</i>(<i>n,k</i>) is Hamilton-laceable if <i>n</i> is even and <i>k</i> is odd, and it is Hamilton-connected otherwise. We take the first step in the proof of this conjecture by proving the case <i>n</i> = 3<i>k</i> + 1 and <i>k</i> greater than or equal to 1. We do this mainly by means of an induction which takes us from <i>GP</i>(3<i>k</i> + 1, <i>k</i>) to <i>GP</i>(3(<i>k</i> + 2) + 1, <i>k</i> + 2). The induction takes the form of mapping a Hamilton path in the smaller graph piecewise to the larger graph an inserting subpaths we call <i>rotors</i> to obtain a Hamilton path in the larger graph.

Traditional algorithms for hidden Markov model decoding seek to maximize either the probability of a state path or the number of positions of a sequence assigned to the correct state. These algorithms provide only a single answer and in practice do not produce good results. The most mathematically sound of these algorithms is the Viterbi algorithm, which returns the state path that has the highest probability of generating a given sequence. Here, we explore an extension to this algorithm that allows us to find the k paths of highest probabilities. The naive implementation of k best Viterbi paths is highly space-inefficient, so we adapt recent work on the Viterbi algorithm for a single path to this domain. Out algorithm uses much less memory than the naive approach. We then investigate the usefulness of the k best Viterbi paths on the example of transmembrane protein topology prediction. For membrane proteins, even simple path combination algorithms give good explanations, and if we look at the paths we are combining, we can give a sense of confidence in the explanation as well. For proteins with two topologies, the k best paths can give insight into both correct explanations of a sequence, a feature lacking from traditional algorithms in this domain.

Not available / text

This research investigates the travel paths of pedestrians along residential frontage roads in the immediate vicinity of bus stops. This investigation was performed to characterize association between seasonality, age, gender, physical impairments and travel path selection. For the purposes of this research, a pedestrian travel path is defined as the physical route chosen by transit users on their walking journey immediately before boarding or after alighting the transit bus, along residential frontage roads in the immediate vicinity of bus stops. A study site screening process that encompassed multiple site visits, Automated Passenger Counting / Automatic Vehicle Location and Geographic Information Systems data analyses identified four study sites (with two bus stops each). At these sites, unaware bus stop users were observed and their travel paths were classified into one of three categories: (a) pedestrian walking on the frontage road; (b) pedestrian walking on the outer separation; or (c) pedestrian walking on the main road. The required sample was collected during eight months, and was divided into ‘no-snow’ and ‘snow’ seasons. After performing statistical tests of association to the travel path selections of bus stop users, the research found that seasonal effects are statistically significant, indicating that there is a higher number of people walking on the main road during the ‘snow’ season. There was also a statistically significant difference in pedestrian path choices regarding site characteristics. When comparing the study sites, the only site that provided a splash strip was found to have a significantly higher amount of people walking along the outer separation, where the splash strip is provided, and which is used by pedestrians as a sidewalk. This finding indicates that if pedestrian facilities were provided along outer separations, they may have an impact on the path chosen by pedestrians when traversing frontage roads. There was not enough evidence to find a statistically significant relationship between pedestrian walking paths and gender, age or ambulatory capabilities.

The crossing number of a graph is the minimum number of pairwise edge crossings in a drawing of a graph. A graph $G$ is $k$-crossing-critical if it has crossing number at least $k$, and any subgraph of $G$ has crossing number less than $k$. A consequence of Kuratowski's theorem is that 1-critical graphs are subdivisions of $K_{3,3}$ and $K_{5}$. The graph $V_{2n}$ is a $2n$-cycle with $n$ diameters. Bokal, Oporowski, Richter and Salazar found in \cite{bigpaper} all the critical graphs except the ones that contain a $V_{8}$ minor and no $V_{10}$ minor. We show that a 4-connected graph $G$ has crossing number at least 2 if and only if for each pair of disjoint edges there are two disjoint cycles containing them. Using a generalization of this result we found limitations for the 2-crossing-critical graphs remaining to classify. We showed that peripherally 4-connected 2-crossing-critical graphs have at most 4001 vertices. Furthermore, most 3-connected 2-crossing-critical graphs are obtainable by small modifications of the peripherally 4-connected ones.

This research investigates the travel paths of pedestrians along residential frontage roads in the immediate vicinity of bus stops. This investigation was performed to characterize association between seasonality, age, gender, physical impairments and travel path selection. For the purposes of this research, a pedestrian travel path is defined as the physical route chosen by transit users on their walking journey immediately before boarding or after alighting the transit bus, along residential frontage roads in the immediate vicinity of bus stops. A study site screening process that encompassed multiple site visits, Automated Passenger Counting / Automatic Vehicle Location and Geographic Information Systems data analyses identified four study sites (with two bus stops each). At these sites, unaware bus stop users were observed and their travel paths were classified into one of three categories: (a) pedestrian walking on the frontage road; (b) pedestrian walking on the outer separation; or (c) pedestrian walking on the main road. The required sample was collected during eight months, and was divided into ‘no-snow’ and ‘snow’ seasons. After performing statistical tests of association to the travel path selections of bus stop users, the research found that seasonal effects are statistically significant, indicating that there is a higher number of people walking on the main road during the ‘snow’ season. There was also a statistically significant difference in pedestrian path choices regarding site characteristics. When comparing the study sites, the only site that provided a splash strip was found to have a significantly higher amount of people walking along the outer separation, where the splash strip is provided, and which is used by pedestrians as a sidewalk. This finding indicates that if pedestrian facilities were provided along outer separations, they may have an impact on the path chosen by pedestrians when traversing frontage roads. There was not enough evidence to find a statistically significant relationship between pedestrian walking paths and gender, age or ambulatory capabilities.