Ces travaux de thèse, dans le domaine de l'adéquation algorithme architecture pour la vision par ordinateur, ont pour cadre l'étiquetage en composantes connexes (ECC) dans le contexte parallèle des architectures hautes performances. Alors que les architectures généralistes modernes sont multi-coeur, les algorithmes d'ECC sont majoritairement séquentiels, irréguliers et utilisent une structure de graphe pour représenter les relations d'équivalences entre étiquettes ce qui rend complexe leur parallélisation. L'ECC permet à partir d'une image binaire, de regrouper sous une même étiquette tous les pixels connexes, il fait ainsi le pont entre les traitements bas niveaux tels que le filtrage et ceux de haut niveau tels que la reconnaissance de forme ou la prise de décision. Il est donc impliqué dans un grand nombre de chaînes de traitements qui nécessitent l'analyse d'image segmentées. L'accélération de cette étape représente donc un enjeu pour tout un ensemble d'algorithmes.Les travaux de thèse se sont tout d'abord concentrés sur les performances comparées des algorithmes de l'état de l'art tant pour l'ECC que pour l'analyse des caractéristiques des composantes connexes (ACC) afin d'en dégager une hiérarchie et d’identifier les composantes déterminantes des algorithmes. Pour cela, une méthode d'évaluation des performances, reproductible et indépendante du domaine applicatif, a été proposée et appliquée à un ensemble représentatif des algorithmes de l'état de l'art. Les résultats montrent que l'algorithme séquentiel le plus rapide est l'algorithme LSL qui manipule des segments contrairement aux autres algorithmes qui manipulent des pixels.Dans un deuxième temps, une méthode de parallélisation des algorithmes directs utilisant OpenMP a été proposé avec pour objectif principal de réaliser l’ACC à la volée et de diminuer le coût de la communication entre les threads. Pour cela, l'image binaire est découpée en bandes traitées en parallèle sur chaque coeur du l'architecture, puis une étape de fusion pyramidale d'ensembles deux à deux disjoint d'étiquettes permet d'obtenir l'image complètement étiquetée sans avoir de concurrence d'accès aux données entre les différents threads. La procédure d'évaluation des performances appliquée a des machines de degré de parallélisme variés, a démontré que la méthode de parallélisation proposée était efficace et qu'elle s'appliquait à tous les algorithmes directs. L'algorithme LSL s'est encore avéré être le plus rapide et le seul adapté à l'augmentation du nombre de coeurs du fait de son approche «segments». Pour une architecture à 60 coeurs, l'algorithme LSL permet de traiter de 42,4 milliards de pixels par seconde pour des images de taille 8192x8192, tandis que le plus rapide des algorithmes pixels est limité par la bande passante et sature à 5,8 milliards de pixels par seconde.Après ces travaux, notre attention s'est portée sur les algorithmes d'ECC itératifs dans le but de développer des algorithmes pour les architectures manycore et GPU. Les algorithmes itératifs se basant sur un mécanisme de propagation des étiquettes de proche en proche, aucune autre structure que l'image n'est nécessaire ce qui permet d'en réaliser une implémentation massivement parallèle (MPAR). Ces travaux ont menés à la création de deux nouveaux algorithmes.- Une amélioration incrémentale de MPAR utilisant un ensemble de mécanismes tels qu'un balayage alternatif, l'utilisation d'instructions SIMD ainsi qu'un mécanisme de tuiles actives permettant de répartir la charge entre les différents coeurs tout en limitant le traitement des pixels aux zones actives de l'image et à leurs voisines.- Un algorithme mettant en œuvre la relation d’équivalence directement dans l’image pour réduire le nombre d'itérations nécessaires à l'étiquetage. Une implémentation pour GPU basée sur les instructions atomic avec un pré-étiquetage en mémoire locale a été réalisée et s'est révélée efficace dès les images de petite taille. / This PHD work take place in the field of algorithm-architecture matching for computer vision, specifically for the connected component labeling (CCL) for high performance parallel architectures.While modern architectures are overwhelmingly multi-core, CCL algorithms are mostly sequential, irregular and they use a graph structure to represent the equivalences between labels. This aspects make their parallelization challenging.CCL processes a binary image and gathers under the same label all the connected pixels, doing so CCL is a bridge between low level operations like filtering and high level ones like shape recognition and decision-making.It is involved in a large number of processing chains that require segmented image analysis. The acceleration of this step is therefore an issue for a variety of algorithms.At first, the PHD work focused on the comparative performance of the State-of-the-Art algorithms, as for CCL than for the features analysis of the connected components (CCA) in order to identify a hierarchy and the critical components of the algorithms. For this, a benchmarking method, reproducible and independent of the application domain was proposed and applied to a representative set of State-of-the-Art algorithms. The results show that the fastest sequential algorithm is the LSL algorithm which manipulates segments unlike other algorithms that manipulate pixels.Secondly, a parallelization framework of directs algorithms based on OpenMP was proposed with the main objective to compute the CCA on the fly and reduce the cost of communication between threads.For this, the binary image is divided into bands processed in parallel on each core of the architecture and a pyramidal fusion step that processes the generated disjoint sets of labels provides the fully labeled image without concurrent access to data between threads.The benchmarking procedure applied to several machines of various parallelism level, shows that the proposed parallelization framework applies to all the direct algorithms.The LSL algorithm is once again the fastest and the only one suitable when the number of cores increases due to its run-based conception. With an architecture of 60 cores, the LSL algorithm can process 42.4 billion pixels per second for images of 8192x8192 pixels, while the fastest pixel-based algorithm is limited by the bandwidth and saturates at 5.8 billion pixels per second.After these works, our attention focused on iterative CCL algorithms in order to develop new algorithms for many-core and GPU architectures. The Iterative algorithms are based on a local propagation mechanism without supplementary equivalence structure which allows to achieve a massively parallel implementation (MPAR). This work led to the creation of two new algorithms.- An incremental improvement of MPAR using a set of mechanisms such as an alternative scanning, the use of SIMD instructions and an active tile mechanism to distribute the load between the different cores while limiting the processing of the pixels to the active areas of the image and to their neighbors.- An algorithm that implements the equivalence relation directly into the image to reduce the number of iterations required for labeling. An implementation for GPU, based on atomic instructions with a pre-labeling in the local memory has been realized and it has proven effective from the small images.

Connected-Component-Labeling (CCL) für 2D-Bilddaten ist ein bekanntes Problem im Bereich der Bildverarbeitung. Ziel ist es, zusammenhängende Pixelgruppen mit gleichen Eigenschaften zu erkennen und mit einem eindeutigen Label zu versehen. Zur Lösung von CCL-Problemen für 2D-Bilddaten werden sowohl sequentielle als auch parallele Algorithmen untersucht. Unter den bekannten Algorithmen gibt es solche, die asymptotisch optimale Eigenschaften besitzen. Speziell für den Bereich der Bildverarbeitung interessant sind außerdem auf Konturierung basierende Algorithmen. Die zusätzlich extrahierten Konturen können z.B. für die Buchstabenerkennung genutzt werden. Seit der jüngeren Vergangenheit werden Grafikprozessoren (GPUs) mit großem Erfolg für allgemeines Computing eingesetzt. So existieren auch mehrere Implementationen von Connected-Component-Labeling-Algorithmen für GPUs, welche im Vergleich mit Varianten für CPUs oft deutlich schneller sind. Diese GPU-basierten Ansätze verarbeiten typischerweise das Pixelgitter direkt. Im Rahmen der vorliegenden Arbeit werden mehrere neue parallele CCL-Algorithmen vorgeschlagen, welche auf Konturen basieren und sowohl für GPUs als auch für Multicore-CPUs geeignet sind. Diese werden experimentell mit Implementationen aus der Literatur unter Verwendung aktueller GPUs und CPUs verglichen. Dabei erreichen in vielen Fällen die vorgeschlagenen Techniken ein besseres Laufzeitverhalten. Das ist auf GPUs insbesondere dann besonders deutlich, wenn sich die evaluierten Datensätze durch einen geringen Anteil von Konturen im Vergleich zur Fläche der Connected-Components auszeichnen.

No description available.

Indiana University-Purdue University Indianapolis (IUPUI) / Collateral connections in the brain, also known as Leptomeningeal Anastomoses, are connections between blood vessels originating from different arteries. Despite limited knowledge, they are suggested as an important contributor to cerebral stroke recovery that allows additional blood flow through the affected area. However, few databases and algorithms exist for this specific task of locating them. In this paper, a MATLAB program is developed to find these connections and detect strokes to replace manual labeling by professionals. The limited data available for this study are 23 2D microscopy images of mice cerebral vascular structures highlighted by dyes. In the images, strokes are shown to diminish the pixel count of vessels below 80\% compared to the healthy brain. Stroke classification error is greatly reduced by narrowing the scope from comparing the entire hemisphere to one smaller region. A novel way of finding collateral connections is utilizing connected components. Connected components organize all adjacent pixels into a group. All collateral connections can be found on the border of two neighboring arterial flow regions, and belong to the same group of connected components with the arterial source from each side. Along with finding collateral connections, a newly created coordinate system allows regions to be defined relative to the brain landmarks, based on the brain's center, orientation, and scale. The method newly proposed in this paper combines stroke detection, brain coordinate system extraction, and collateral connection detection in stroke-affected mouse brains using only image processing techniques. This allows a simpler, more explainable result on limited data than other techniques such as supervised machine learning. In addition, the new method does not require ground truth and high image count for training. This automated process was successfully interpreted by medical experts, which allows for further research into automating collateral connection detection in 3D.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

The ability to count people from video is a challenging problem. The scientific challenge arises from the fact that although the task is pretty well defined, the imaging scenario is not well constrained. The background scene is uncontrolled. Lighting is complex and varying. And, image resolution, both in terms of spatial and temporal is usually poor, especially in pre-stored surveillance videos. Passive counting of people from video has many practical applications such as in monitoring the number of people sitting in front of a TV set, counting people in an elevator, counting people passing through a security door, and counting people in a mall. This has led to some research in automated counting of people. The context of most of the work in people counting is in counting pedestrians in outdoor settings or moving subjects in indoor settings. There is little work done in counting of people who are not moving around and very little work done in people counting that can handle harsh variations in illumination conditions. In this thesis, we explore a design that handles such issues at pixel level using photometry based normalization and at feature level by exploiting spatiotemporal coherence that is present in the change seen in the video. We have worked on home and laboratory dataset. The home dataset has subjects watching television and the laboratory dataset has subjects working. The design of the people counter is based on video data that is temporally sparsely sampled at 15 seconds of time difference between consecutive frames. Specific computer vision methods used involves image intensity normalization, frame to frame differencing, motion accumulation using autoregressive model and grouping in spatio-temporal volume. The experimental results show: The algorithm is less susceptible to lighting changes. Given an empty scene with just lighting change it usually produces a count of zero. It can count in varying illumination conditions. It can count people even if they are partially visible. Counts are generated for any moving objects in the scene. It does not yet try to distinguish between humans and non-humans. Counting errors are concentrated around frames with large motion events, such as a person moving out from a scene.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2017-04-06T12:58:28Z No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-04-06T12:58:41Z (GMT) No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-04-06T12:58:41Z (GMT). No. of bitstreams: 2 Dissertação - Marby Zuley Bolaños Ortiz - 2017.pdf: 1515856 bytes, checksum: 739fa4d4c051b1c82f2f7ed1e4427c73 (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-03-30 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / In this work, we estudied three special subgroups of bounded index in G: The intersection of subgroups definables of G, the small type-definable subgroup and the small invariant subgroup of G, called connected components of G and denoted G0G00 e G¥. We give an exposition of theorem of Gismatullim, where he proved the existence of G¥ in a theory with NIP. / Neste trabalho estudamos três subgrupos de um grupo G com índices limitados em G: A interseção de todos os subgrupos definíveis de G , o menor subgrupo tipo-definível e o menor subgrupo invariante de G, chamados componentes conexas de G, denotados respectivamente G0G00 e G¥. Apresentamos uma demonstração da existência de G¥ em uma teoria NIP, baseados na prova feita por Gismatullin em 2011.

Árvore de componentes é uma forma hierárquica de representar imagens em níveis de cinza baseada nas relações de inclusão dos componentes conexos da imagem. A escolha da vizinhança utilizada para gerar os componentes impacta diretamente na árvore resultante, de forma que uma alteração na escolha da vizinhança pode acarretar em uma alteração na árvore de componentes obtida. Em particular, quando uma sequência de vizinhanças crescentes é usada, os nós das árvores obtidas a partir dessas vizinhanças satisfazem uma relação de inclusão, de forma que se é possível estabelecer relações entre nós de diferentes árvores. Assim sendo, o principal objetivo desta dissertação consiste no desenvolvimento de um algoritmo eficiente para a construção de uma sequência de árvores de componentes. Para tanto, será introduzida uma classe particular de sequências de vizinhanças, que não apenas satisfaz a propriedade crescente como também permite que as árvores de componentes associadas a ela sejam construídas de forma incremental. Com base nestas propriedades, um novo algoritmo de construção de árvores de componentes associado a esta classe de vizinhanças será proposto. Para analisar a eficiência do algoritmo proposto apresentamos, ao final do texto, alguns resultados práticos e teóricos obtidos com relação ao consumo de tempo e à complexidade computacional. / Component tree is a hierarchical way of representing gray-level images based on the inclusion relation of the connected components of the image. The choice of the neighborhood used to generate these components directly impacts in the resulting tree: changing the neighborhood used may cause a change in the resulting component tree. In particular, when considering a sequence of increasing neighborhoods, the nodes of the obtained from these neighborhoods will also satisfy an inclusion relation and that will make it possible to link nodes from different trees. Therefore, the main goal of this dissertation is the development of an efficient algorithm to build a sequence of component trees. In order to do that, we will introduce a class of sequences of neighborhood that not only satisfy the increasing property but also makes it possible to incrementally build the trees associated to it. This additional property will guide us to a novel algorithm, that will build the component trees associated to this class of neighborhoods. To show how efficient the proposed algorithm is, we present some experimental and theoretical results regarding time consumption and computational complexity.

This paper concerns a specific pursuit-evasion problem with a node-located evader which we call the monk problem. First, we propose a way of verifying a strategy using a new kind of recursive systems, called EL-systems. We show how an EL-system representing a graph-instance of the problem can be represented using matrices, and we give an example of how this can be used to efficiently implement a verifier. In the later parts we propose heuristics to construct a strategy, based on a greedy algorithm. Our main focus is to minimise the number of pursuers needed, called the search number. The heuristics rely on properties of minimal stable components. We show that the minimal stable components are equivalent to the strongly connected components of a graph, and prove that the search number is equal to the maximum search number of its strongly connected components. We also establish lower and upper bounds for the search number to narrow the search space. / Denna rapport avhandlar ett specifikt pursuit-evasion problem med en hörnplacerad flykting, som vi kallar för munkproblemet. Först föreslår vi ett sätt att verifiera en strategi med en ny typ av rekursivt system, kallat EL-system. Vi visar hur ett EL-system som representerar en grafinstans av munkproblemet kan representeras med matriser, och vi ger ett exempel på hur detta kan användas för att effektivt implementera en verifikator. I de senare delarna föreslår vi heuristiker för att konstruera en strategi, baserad på giriga algoritmer. Vårt huvudfokus är att minimera antalet förföljare som krävs för att dekontaminera grafen, det så kallade söktalet. Vår heuristik förlitar sig på egenskaper för minimala stabila komponenter. Vi visar att minimala stabila komponenter är ekvivalenta med de starka komponenterna i en graf, och härleder att söktalet är lika med det maximala söktalet för grafens starka komponenter. Vi etablerar också undre och övre gränser för söktalet i syfte att minska sökintervallet.

Analysis of overhead imagery has a great potential to produce real-time data cost-effectively. This can be an important foundation for decision-making for businesses and politics. Every day a massive amount of new satellite imagery is produced. To fully take advantage of these data volumes a computationally efficient pipeline is required for the analysis. This thesis proposes a pipeline which outperforms the Segment Before you Detect network [6] and different types of fast region based convolutional neural networks [61] with a large margin in a fraction of the time. The model obtains a prediction error for counting cars of 1.67% on the Potsdam dataset and increases the vehiclewise F1 score on the VEDAI dataset from 0.305 reported by [61] to 0.542. This thesis also shows that it is possible to outperform the Segment Before you Detect network in less than 1% of the time on car counting and vehicle detection while also using less than half of the resolution. This makes the proposed model a viable solution for large-scale satellite imagery analysis. / Analys av flyg- och satellitbilder har stor potential att kostnadseffektivt producera data i realtid för beslutsfattande för företag och politik. Varje dag produceras massiva mängder nya satellitbilder. För att fullt kunna utnyttja dessa datamängder krävs ett beräkningseffektivt nätverk för analysen. Denna avhandling föreslår ett nätverk som överträffar Segment Before you Detect-nätverket [6] och olika typer av snabbt regionsbaserade faltningsnätverk [61]  med en stor marginal på en bråkdel av tiden. Den föreslagna modellen erhåller ett prediktionsfel för att räkna bilar på 1,67% på Potsdam-datasetet och ökar F1- poängen for fordons detektion på VEDAI-datasetet från 0.305 rapporterat av [61]  till 0.542. Denna avhandling visar också att det är möjligt att överträffa Segment Before you Detect-nätverket på mindre än 1% av tiden på bilräkning och fordonsdetektering samtidigt som den föreslagna modellen använder mindre än hälften av upplösningen. Detta gör den föreslagna modellen till en attraktiv lösning för storskalig satellitbildanalys.