Ανατομικές δομές με δενδρική τοπολογία απαντώνται συχνά στο ανθρώπινο σώμα και οπτικοποιούνται σε ιατρικές εικόνες χρησιμοποιώντας απεικονιστικές τεχνικές με ακτίνες-χ και τη χρήση σκιαγραφικού υλικού. Χαρακτηριστικά παραδείγματα τέτοιων δομών είναι το βρογχικό δένδρο εντός των πνευμόνων το οποίο οπτικοποιείται με εικόνες αξονικής τομογραφίας και τα γαλακτοφόρα δένδρα εσωτερικά του μαστού τα οποία οπτικοποιούνται με γαλακτογραφίες. Σκοπός της παρούσας διδακτορικής διατριβής αποτελεί η ανάπτυξη ενός συνόλου αλγοριθμικών μεθόδων για την αυτοματοποίηση της ανάλυσης των ανατομικών δομών του ανθρωπίνου σώματος που έχουν τοπολογία δένδρου ή τοπολογία δικτύου. Πιο συγκεκριμένα, οι δύο βασικοί στόχοι της διατριβής είναι η ανάπτυξη μεθόδων ειδικά σχεδιασμένων για τη ψηφιακή επεξεργασία των ιατρικών εικόνων που απεικονίζουν δομές με διακλαδώσεις και η ανάπτυξη μεθοδολογικών πλαισίων για τη διερεύνηση της σχέσης μεταξύ τοπολογίας και παθοφυσιολογίας αυτού του τύπου ανατομικών δομών. Το πρώτο κεφάλαιο της διατριβής παρουσιάζει μια βιβλιογραφική ανασκόπηση σχετικά με τις ανατομικές δομές του ανθρωπίνου σώματος με τοπολογία διακλαδώσεων καθώς και το κίνητρο για την παρούσα έρευνα. Οι επιμέρους ερευνητικοί στόχοι, οι κύριες συνεισφορές και η γενικότερη απήχηση της διατριβής αναφέρονται επίσης. Το δεύτερο κεφάλαιο εστιάζει στην κατάτμηση εικόνας. Η κατάτμηση εικόνας αποτελεί το πρώτο βήμα στη διαδικασία ανάλυσης ιατρικών εικόνων και στα συστήματα αναγνώρισης προτύπων και οι αλγόριθμοι κατάτμησης αποτελούν κρίσιμα τμήματα των σύγχρονων ιατρικών διαγνωστικών συστημάτων. Παρά την πλούσια βιβλιογραφία στην περιοχή, η ανάγκη για αποδοτικές μεθοδολογίες κατάτμησης εφαρμόσιμες σε μεγάλο εύρος απεικονιστικών τεχνικών παραμένει. Προσπαθώντας να αντιμετωπιστεί αυτή η ερευνητική πρόκληση, μια καινοτόμα και πλήρως αυτοματοποιημένη μεθοδολογία για την κατάτμηση των δενδρικών ανατομικών δομών παρουσιάζεται. Η βασική ιδέα είναι ο συνδυασμός τεχνικών ανίχνευσης ακμών με μεθόδους ανάπτυξης περιοχών για να επιτευχθεί αποδοτική κατάτμηση. Η υβριδική αυτή προσέγγιση εφαρμόστηκε και αξιολογήθηκε σε δύο σύνολα δεδομένων ιατρικών εικόνων από διαφορετικές απεικονιστικές τεχνικές (γαλακτογραφίες και αγγειογραφίες) και η απόδοσή της συγκρίθηκε με τεχνικές κατάτμησης της υπάρχουσας τεχνολογικής στάθμης. Το τρίτο κεφάλαιο επικεντρώνεται στην ανίχνευση των κόμβων διακλάδωσης το οποίο συνιστά ένα σημαντικό υπολογιστικό στάδιο στα πλαίσια της επεξεργασίας των ιατρικών εικόνων που απεικονίζουν δομές δενδρικής τοπολογίας. Οι κόμβοι διακλάδωσης αποτελούν σημεία-κλειδιά για τον προσδιορισμό της θέσης του δένδρου και η σωστή ανίχνευσή τους είναι ένα σημαντική για την αυτοματοποίηση διαδικασιών επεξεργασίας εικόνας όπως ευθυγράμμιση εικόνας, κατάτμηση εικόνας και ανάλυση των προτύπων διακλάδωσης. Ωστόσο, η ανάπτυξη αυτοματοποιημένων τεχνικών για την ανίχνευση των κόμβων διακλάδωσης δυσχεραίνεται από τα διαφορετικά επίπεδα θορύβου που υπάρχουν κατά μήκος της δενδρικής δομής. Η προτεινόμενη μεθοδολογία ανίχνευσης απαρτίζεται από δύο κύρια στάδια: ανίχνευση γωνιακών σημείων σε διάφορες κλίμακες και προσδιορισμό της θέσης της διακλάδωσης. Η βασική συνεισφορά της νέας μεθοδολογίας είναι η χρήση ενός τοπικά προσαρμοζόμενου κατωφλιού κατά τη φάση της ανίχνευσης προκειμένου να αντιμετωπιστεί αποδοτικά η ανίχνευση των σημείων διακλάδωσης που βρίσκονται στα χαμηλά δενδρικά επίπεδα. Η αξιολόγηση της μεθόδου πραγματοποιήθηκε χρησιμοποιώντας ένα σύνολο δεδομένων από κλινικές γαλακτογραφίες και η απόδοσης της συγκρίνεται με αντίστοιχες τεχνικές της υπάρχουσας τεχνολογικής στάθμης. Στο τέταρτο κεφάλαιο παρουσιάζονται καινοτόμες μεθοδολογίες για τον χαρακτηρισμό και την κατηγοριοποίηση των ανατομικών δενδρικών δομών στοχεύοντας στη διερεύνηση της συσχέτισης μεταξύ τοπολογίας και παθολογίας των αντίστοιχων οργάνων. Οι μέθοδοι περιλαμβάνουν κατηγοριοποίηση χρησιμοποιώντας περιγραφικά χαρακτηριστικά της τοπολογίας όπως η δενδρική ασυμμετρία, η χωρική κατανομή των σημείων διακλάδωσης, η στρεβλότητα των κλάδων και άλλα γεωμετρικά χαρακτηριστικά του δένδρου. Επιπρόσθετα σε αυτό το κεφάλαιο, ένα νέο μεθοδολογικό πλαίσιο προτείνεται για την ανάλυση δενδρικών τοπολογιών χρησιμοποιώντας διανύσματα που κωδικοποιούν τις σχέσεις παιδιού-γονέα των κόμβων και ελαστικό ταίριασμα μεταξύ των ακολουθιών. Η υπεροχή της νέας αυτής μεθόδου έναντι των μεθόδων της υπάρχουσας τεχνολογικής στάθμης για την κατηγοριοποίηση δένδρων αξιολογήθηκε πειραματικά ως προς ευαισθησία, ειδικότητα και ακρίβεια. Στο πέμπτο κεφάλαιο μελετώνται τεχνικές συλλογικής μάθησης. Η ενοποίηση πολλαπλών αλγορίθμων μηχανικής μάθησης συνιστά σημαντική πρόοδο για τις μεθοδολογίες κατηγοριοποίησης και βασίζεται στην ιδέα του συνδυασμού των προβλέψεων ενός πλήθους κατηγοριοποιητών με σκοπό τη μεγιστοποίηση της ακρίβειας κατηγοριοποίησης. Τρεις τεχνικές συνδυαστικής μάθησης βασισμένες στην τεχνική της ενδυνάμωσης (boosting) και η χρήση ενός συνδυαστικού κανόνα που ονομάζεται Πρότυπο Απόφασης (Decision Template) χρησιμοποιούνται για τη βελτιστοποίηση της ακρίβειας που επιτυγχάνουν οι κατηγοριοποιητές βάσης. Τα πειραματικά αποτελέσματα επιβεβαιώνουν την υπεροχή των μεθόδων συλλογικής μάθησης. Κλείνοντας, τα συμπεράσματα της διατριβής παρουσιάζονται στο έκτο κεφάλαιο. Οι περιορισμοί των προτεινόμενων τεχνικών καθώς και οι προοπτικές για επιπρόσθετη ερευνητική εργασία αναλύονται. / Anatomical structures of branching topology are frequently met in the human body and are visualized in medical images using various image acquisition modalities. Examples of such structures include the bronchial tree in chest computed tomography images, the blood vessels in retinal images and the breast ductal network in x-ray galactograms. The current thesis aims at the development of a set of automated methods for the analysis of anatomical structures of tree and network topology. More specifically, the two main objectives include (i) the development of image processing methods for optimized visualization of anatomical branching structures, and (ii) the development of analysis frameworks sin order to explore the association between topology and pathophysiology of anatomical branching structures. The first chapter of the thesis presents a literature review regarding anatomical structures of the human body with branching topology and the motivation for this thesis. The specific research objectives, the main contributions and the impact of the thesis are also demonstrated. The second chapter focuses on image segmentation. Image segmentation is the first step of medical image analysis and pattern recognition systems and segmentation algorithms are critical components of today radiological diagnostic systems. Despite the large number of existing segmentation algorithms, the need for effective methodologies applicable to a range of imaging modalities still remains. Towards this challenge a novel and fully automated methodology for segmenting anatomical branching structures is presented. The main idea is the integration of edge detection techniques with region growing methods to achieve robust segmentation. The hybrid approach is applied and evaluated in two datasets of branching structures from different imaging modalities (x-ray galactograms and vasculature angiograms) and is compared to state-of-the-art segmentation techniques. The third chapter presents the image processing stage of detecting branching nodes of anatomical structures in medical images. The branching nodes are the key components for tree localization as well as topology modelling and node detection is a very important first step towards the automated processing of these structures including image registration, segmentation and analysis of branching patterns. Developing automated techniques for node detection is a very challenging task due to different levels of noise fluctuations throughout across tree levels. The proposed methodology of node detection consists of two main steps; multi-scale corner detection and branching localization. The main contribution of this work is the use of locally adaptive thresholding in the corner detection phase in order to facilitate node detection at lower tree levels. The evaluation of the methodology using a dataset of clinical galactograms and its comparison with state-of-the-art methods is also presented. In the forth chapter, novel methodologies for the classification of anatomical tree-shape structures are presented aiming at providing new insights into the association between topology and underlying pathology. The methods include classification using descriptive features of the branching topology such as the tree asymmetry index, the spatial distribution of branching nodes, the branch tortuosity and other geometry-based tree features. Additionally, in this chapter a novel framework is presented to analyze tree topologies using representative encodings of parent-child node relationships and elastic sequence matching techniques. The superiority of the new methods over state-of-the-art techniques in terms of sensitivity, specificity and accuracy is evaluated experimentally. In the fifth chapter the potential of ensemble learning schemes is explored. Ensemble schemes are important developments in classification methodology and are based on the idea to combine the predictions of multiple classifiers in order to maximize the classification accuracy. Three ensemble learning techniques based on the boosting technique and an effective combination rule named Decision Template are employed to optimize the accuracy of base classifiers. The experimental results confirm the superiority of ensemble techniques. Finally the conclusions of the thesis are presented in the sixth chapter. The limitations of the proposed approach and the perspectives for further work are discussed.

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. / This document describes methods and presents results from the Master of Science\'s research project in computer science entitled \"Two Problems in Shape Analysis of Branching Structures\". Both tackled problems herein are related to Shape Analysis sub-fields, namely Characterization and Description of shapes. The former problem consists of an investigation on a proposed set of features aimed at discriminating, firstly, between blood vessels branching structures manually and automatically segmented. In the sequel, the same features are used to assess their discriminative capability in distinguishing between blood vessels branching structures with and withoud proliferative diabetic retinopathy (PDR). The PDR is a pathology related to diabetes, which may lead to the blindness. Diagnosis is possible through optic fundus image analysis, which may allow timely interventions preventing vision loss. In this work, 27 digital optic fundus images were segmented by two distinct segmentation processes, i.e. manual segmentation carried out by an especialist and automated segmentation, through the CWT (Continuous Wavelet Transform) and statistical classifiers. In order to characterize such a shapes, a set of 8 features has been proposed. The aforementioned set was comprised of three features groups, that is: traditional geometric descriptors (Area, Perimeter and Circularity), wavelet-based descriptors (2nd statistical moment from the CWT Modulus distribution, Orientation Entropy from the CWT Phase distribution and Curvature) and a fractal descriptor (Correlation Dimension - global and median). Linear Discriminant Analysis LDA revelead that the traditional geometric features are not able to detect early proliferative diabetic retinopathy. The largest singular discriminant capability was shown by the Curvature, with area under the ROC curve of 0.76. A subset of 6 features presented a good discriminating power with area under the curve of 0.90. The second problem concerns contour extraction from 2D branching structures of 3D neurons. This work contributes with an original solution for such a problem, proposing two algorithms devised for Branches Tracking and Branching Structures Contour Extraction. The proposed algorithms are able to traverse critical regions implied by the projection of 3D structures onto a 2D image plane. Most of contour-based methods intended to shape analysis of neuronal branching structures fall short of yielding proper shape representations, owing to the presence of overlapings among neuronal processes, causing the traditional algorithms for contour following to ignore the innermost regions, thus generating incomplete representations. The proposed framework system was developed aiming at the solution of the contour extraction problem, even in the presence of multiple overlapings. The input image is pre-processed, so as to obtain an 8-connected skeleton with one-pixel wide branches, a set of seeds of dendritic sub-trees and a set of critical regions (bifurcations, crossings and superpositions). For each sub-tree, the Branches Tracking Algorithm labels all valid pixels of a branch, until reaching a critical region, where the algorithm decides about the direction to go on with the tracking. Our algorithm has shown robustness, even in images plenty of very close parallel segments. Results with real images (neurons) are presented.

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. / This document describes methods and presents results from the Master of Science\'s research project in computer science entitled \"Two Problems in Shape Analysis of Branching Structures\". Both tackled problems herein are related to Shape Analysis sub-fields, namely Characterization and Description of shapes. The former problem consists of an investigation on a proposed set of features aimed at discriminating, firstly, between blood vessels branching structures manually and automatically segmented. In the sequel, the same features are used to assess their discriminative capability in distinguishing between blood vessels branching structures with and withoud proliferative diabetic retinopathy (PDR). The PDR is a pathology related to diabetes, which may lead to the blindness. Diagnosis is possible through optic fundus image analysis, which may allow timely interventions preventing vision loss. In this work, 27 digital optic fundus images were segmented by two distinct segmentation processes, i.e. manual segmentation carried out by an especialist and automated segmentation, through the CWT (Continuous Wavelet Transform) and statistical classifiers. In order to characterize such a shapes, a set of 8 features has been proposed. The aforementioned set was comprised of three features groups, that is: traditional geometric descriptors (Area, Perimeter and Circularity), wavelet-based descriptors (2nd statistical moment from the CWT Modulus distribution, Orientation Entropy from the CWT Phase distribution and Curvature) and a fractal descriptor (Correlation Dimension - global and median). Linear Discriminant Analysis LDA revelead that the traditional geometric features are not able to detect early proliferative diabetic retinopathy. The largest singular discriminant capability was shown by the Curvature, with area under the ROC curve of 0.76. A subset of 6 features presented a good discriminating power with area under the curve of 0.90. The second problem concerns contour extraction from 2D branching structures of 3D neurons. This work contributes with an original solution for such a problem, proposing two algorithms devised for Branches Tracking and Branching Structures Contour Extraction. The proposed algorithms are able to traverse critical regions implied by the projection of 3D structures onto a 2D image plane. Most of contour-based methods intended to shape analysis of neuronal branching structures fall short of yielding proper shape representations, owing to the presence of overlapings among neuronal processes, causing the traditional algorithms for contour following to ignore the innermost regions, thus generating incomplete representations. The proposed framework system was developed aiming at the solution of the contour extraction problem, even in the presence of multiple overlapings. The input image is pre-processed, so as to obtain an 8-connected skeleton with one-pixel wide branches, a set of seeds of dendritic sub-trees and a set of critical regions (bifurcations, crossings and superpositions). For each sub-tree, the Branches Tracking Algorithm labels all valid pixels of a branch, until reaching a critical region, where the algorithm decides about the direction to go on with the tracking. Our algorithm has shown robustness, even in images plenty of very close parallel segments. Results with real images (neurons) are presented.