In this Master Thesis the possibility to efficiently divide a graph into spanner islands is examined. Spanner islands are islands of the graph that fulfill the spanner condition, that the distance between two nodes via the edges in the graph cannot be too far, regulated by the stretch constant, compared to the Euclidian distance between them. In the resulting division the least number of nodes connecting to other islands is sought-after. Different heuristics are evaluated with the conclusion that for dense graphs a heuristic using MAX-FLOW to divide problematic nodes gives the best result whereas for sparse graphs a heuristic using the single-link clustering method performs best. The problem of finding a spanner path, a path fulfilling the spanner condition, between two nodes is also investigated. The problem is proven to be NP-complete for a graph of size n if the spanner constant is greater than n^(1+1/k)*k^0.5 for some integer k. An algorithm with complexity O(2^(0.822n)) is given. A special type of graph where all the nodes are located on integer locations along the real line is investigated. An algorithm to solve this problem is presented with a complexity of O(2^((c*log n)^2))), where c is a constant depending only on the spanner constant. For instance, the complexity O(2^((5.32*log n)^2))) can be reached for stretch 1.5. / I det här magisterarbetet undersöks om det är möjligt att på ett effektivt sätt dela upp en graf i spanneröar, dvs. öar som uppfyller spanneregenskapen som består i att avståndet mellan två noder via grafens bågar inte får vara för stort i förhållande till det euklidiska avståndet mellan noderna. Att hitta en uppdelning som skapar så få kontaktpunkter mellan öarna som möjligt eftersöks. Ett antal heuristiker testas och utvärderas med resultatet att en heuristik som använder sig av MAX-FLOW för att dela upp noder som bryter mot spannervillkoret presterar bäst för täta grafer medan en heuristik av typ single-link clustering presterar bäst för glesa grafer. I arbetet visas att problemet att finna en spannerväg, en väg där noderna som passeras uppfyller spannervillkoret, mellan två noder i en graf av storlek n är NP-komplett om spannerkonstanten är större än n^(1+1/k)*k^0.5 för något heltal k. En algoritm för att hitta spannervägar med komplexiteten O(2^(0.822n)) presenteras. Ett specialproblem där grafen ligger längs tallinjen och bara har noder på heltalspunkter studeras slutligen och här konstrueras en algoritm med komplexiteten O(2^((c*log n)^2))) där c är en konstant som beror på spannerkonstanten. Till exempel nås O(2^((5.32*log n)^2))) för stretch 1.5.

High resolution surveillance video cameras are invaluable resources for effective crime prevention and forensic investigations. However, increasing communication bandwidth requirements of high definition surveillance videos are severely limiting the number of cameras that can be deployed. Higher bitrate also increases operating expenses due to higher data communication and storage costs. Hence, it is essential to develop low complexity algorithms which reduce data rate of the compressed video stream without affecting the image fidelity. In this thesis, a computer vision aided H.264 surveillance video encoder and four associated algorithms are proposed to reduce the bitrate. The proposed techniques are (I) Speeded up foreground segmentation, (II) Skip decision, (III) Reference frame selection and (IV) Face Region-of-Interest (ROI) coding. In the first part of the thesis, a modification to the adaptive Gaussian Mixture Model (GMM) based foreground segmentation algorithm is proposed to reduce computational complexity. This is achieved by replacing expensive floating point computations with low cost integer operations. To maintain accuracy, we compute periodic floating point updates for the GMM weight parameter using the value of an integer counter. Experiments show speedups in the range of 1.33 - 1.44 on standard video datasets where a large fraction of pixels are multimodal. In the second part, we propose a skip decision technique that uses a spatial sampler to sample pixels. The sampled pixels are segmented using the speeded up GMM algorithm. The storage pattern of the GMM parameters in memory is also modified to improve cache performance. Skip selection is performed using the segmentation results of the sampled pixels. In the third part, a reference frame selection algorithm is proposed to maximize the number of background Macroblocks (MB’s) (i.e. MB’s that contain background image content) in the Decoded Picture Buffer. This reduces the cost of coding uncovered background regions. Distortion over foreground pixels is measured to quantify the performance of skip decision and reference frame selection techniques. Experimental results show bit rate savings of up to 94.5% over methods proposed in literature on video surveillance data sets. The proposed techniques also provide up to 74.5% reduction in compression complexity without increasing the distortion over the foreground regions in the video sequence. In the final part of the thesis, face and shadow region detection is combined with the skip decision algorithm to perform ROI coding for pedestrian surveillance videos. Since person identification requires high quality face images, MB’s containing face image content are encoded with a low Quantization Parameter setting (i.e. high quality). Other regions of the body in the image are considered as RORI (Regions of reduced interest) and are encoded at low quality. The shadow regions are marked as Skip. Techniques that use only facial features to detect faces (e.g. Viola Jones face detector) are not robust in real world scenarios. Hence, we propose to initially detect pedestrians using deformable part models. The face region is determined using the deformed part locations. Detected pedestrians are tracked using an optical flow based tracker combined with a Kalman filter. The tracker improves the accuracy and also avoids the need to run the object detector on already detected pedestrians. Shadow and skin detector scores are computed over super pixels. Bilattice based logic inference is used to combine multiple likelihood scores and classify the super pixels as ROI, RORI or RONI. The coding mode and QP values of the MB’s are determined using the super pixel labels. The proposed techniques provide a further reduction in bitrate of up to 50.2%.

L’amélioration du contraste des images échographiques occupe une place importante en imagerie ultrasonore médicale puisque la qualité des images impacte directement le diagnostic médical. Les imageries de contraste sous et ultra-harmoniques sont deux techniques permettant de produire des images à fort contraste. Le développement de techniques de filtrage, permettant de mieux extraire les composantes sous et ultra-harmoniques présentes dans les signaux renvoyés par les produits de contraste ultrasonore, a pour conséquence d’améliorer encore plus le contraste des images. Les modèles non linéaires dits « boîtes noires » du type Volterra, Hammerstein, et Wiener, sont souvent utilisés pour identifier et modéliser les systèmes non linéaires tels que les produits de contraste ultrasonore. Ces modèles, bien que très bien adaptés pour modéliser les composantes harmoniques entières, ne le sont plus en présence de sous et ultra-harmoniques. Dans les années 2000, une méthode permettant la modélisation de sous et ultra-harmoniques en utilisant un modèle de Volterra à plusieurs entrées (Multiple Input Single Output : MISO) a été développée. Pourtant, bien que cette méthode soit complètement originale dans le domaine considéré, les points clés qui la sous-tendent ne sont pas clairement identifiés. C’est en identifiant clairement les points clés de la méthode existante que nous pouvons la généraliser et proposer plusieurs nouveaux paradigmes pour la modélisation et l’extraction de sous et ultra-harmoniques. Nous proposons alors des alternatives beaucoup plus simples du type mono-entrée mono-sortie (Single Input Single Output : SISO). En modulant en fréquence l’entrée du système, nous avons pu ainsi identifier les réponses impulsionnelles des différents canaux du modèle de Hammerstein généralisé. À partir de ce cadre général, nous avons aussi proposé de nouvelles approches pour réduire la complexité du modèle de Volterra. / Contrast enhancement of echographic images occupies an important place in medical ultrasound imaging, since the quality of images has a direct impact on medical diagnosis. Sub and ultraharmonic contrast imaging are two imaging techniques that provide high contrast images. Developing filtering techniques, that allow better extraction of sub and ultra-harmonic components present in the echo backscattered by the ultrasound contrast agents, results in additional improvement of the contrast. Non linear models known as “black box” models, like Volterra model, Hammerstein model, and Wiener model are usually used to identify and model non linear systems such ultrasound contrast agents. Although these models are well suited to model integer harmonic components, they are not suitable in the presence of sub and ultra-harmonic components. In the 2000s, A method that allows the modeling of sub and ultra-harmonic components, using a multi inputs single output Volterra model (MISO) has been developed. Although this method was original in the considered domain, the key points underlying this method are not clearly identified. By clearly identifying the key points of the existing method, we can generalize it and propose new paradigms for modeling and extraction of sub and ultra-harmonics. We propose much simpler alternatives based on single input single output (SISO) models. By modulating the input frequency of the system, we can also identify the different impulse responses of the different channels of the generalized Hammerstein model. From this general framework, we also propose new approaches to reduce the complexity of Volterra model.

This particular telling and retelling from a living narrative inquiry (Clandinin & Connelly, 2000) into the early experiences of three high school science teachers – Beth, Joel, and Christina – explores the emergent inquiry landscapes constructed as we implemented a renewed, decolonizing, science curriculum in Saskatchewan founded on a philosophy of inquiry and on a broader, more holistic definition of scientific literacy, both Western and Indigenous. This inquiry draws on an ontology of lived experience (Dewey, 1938) and, more subtly, on the borderland of narrative inquiry and complexity science in order to illustrate the emergence and coming to knowing (Delandshire, 2002; Ermine, as cited in Aikenhead, 2002) of our identities in a way that avoids the reduction in complexity of our experiences. While my initial wonders persisted throughout the research as I lived alongside Beth, Joel, and Christina for two years, they diffracted into the contextualized wonder: how do we share a philosophy of inquiry with each other and with our students? As such, this inquiry is a sharing about our own identities, about our own agency, about identity work, and about which experiences we choose to (re)engage with as we attempt to (re)find the narrative diversity, both individual and collective, necessary to shift from enacted identities to 'wished-we-could-enact' identities. This exploration of our 'mo(u)rning stories', early experiences from our shifting identities after stepping through the liminal and onto emergent inquiry landscapes, or our 'stories to relive with' provides a language and context to our shifting identities and hence, to science education, as we move towards a more holistic and humanistic form of scientific literacy for all our students. What emerged through the enmeshing of our landscapes and through the construction of voids in existing practices, followed by deformalizations in assessment and planning, was the development of a way of sharing our philosophy of inquiry and hence, our shifting identities. The artifacting and sharing of our contextualized inquiry experiences highlighted the rich assessment making, and curriculum making experiences (Huber, Murphy & Clandinin, 2011) we shared with our students and highlighted a view of assessment as a relationship. As we told and retold our stories to relive with, our identities shifted towards those more akin to facilitator and anthropologist and away from sage and engineer/architect.