In this dissertation, level set methods are employed to segment masses in digital mammographic images and to classify land cover classes in hyperspectral data. For the mammography computer aided diagnosis (CAD) application, level set-based segmentation methods are designed and validated for mass periphery segmentation, spiculation segmentation, and core segmentation. The proposed periphery segmentation uses the narrowband level set method in conjunction with an adaptive speed function based on a measure of the boundary complexity in the polar domain. The boundary complexity term is shown to be beneficial for delineating challenging masses with ill-defined and irregularly shaped borders. The proposed method is shown to outperform periphery segmentation methods currently reported in the literature. The proposed mass spiculation segmentation uses a generalized form of the Dixon and Taylor Line Operator along with narrowband level sets using a customized speed function. The resulting spiculation features are shown to be very beneficial for classifying the mass as benign or malignant. For example, when using patient age and texture features combined with a maximum likelihood (ML) classifier, the spiculation segmentation method increases the overall accuracy to 92% with 2 false negatives as compared to 87% with 4 false negatives when using periphery segmentation approaches. The proposed mass core segmentation uses the Chan-Vese level set method with a minimal variance criterion. The resulting core features are shown to be effective and comparable to periphery features, and are shown to reduce the number of false negatives in some cases. Most mammographic CAD systems use only a periphery segmentation, so those systems could potentially benefit from core features.

Document page segmentation is one of the most crucial steps in document image analysis. It ideally aims to explain the full structure of any document page, distinguishing text zones, graphics, photographs, halftones, figures, tables, etc. Although to date, there have been made several attempts of achieving correct page segmentation results, there are still many difficulties. The leader of the project in the framework of which this PhD work has been funded (*) uses a complete processing chain in which page segmentation mistakes are manually corrected by human operators. Aside of the costs it represents, this demands tuning of a large number of parameters; moreover, some segmentation mistakes sometimes escape the vigilance of the operators. Current automated page segmentation methods are well accepted for clean printed documents; but, they often fail to separate regions in handwritten documents when the document layout structure is loosely defined or when side notes are present inside the page. Moreover, tables and advertisements bring additional challenges for region segmentation algorithms. Our method addresses these problems. The method is divided into four parts:1. Unlike most of popular page segmentation methods, we first separate text and graphics components of the page using a boosted decision tree classifier.2. The separated text and graphics components are used among other features to separate columns of text in a two-dimensional conditional random fields framework.3. A text line detection method, based on piecewise projection profiles is then applied to detect text lines with respect to text region boundaries.4. Finally, a new paragraph detection method, which is trained on the common models of paragraphs, is applied on text lines to find paragraphs based on geometric appearance of text lines and their indentations. Our contribution over existing work lies in essence in the use, or adaptation, of algorithms borrowed from machine learning literature, to solve difficult cases. Indeed, we demonstrate a number of improvements : on separating text columns when one is situated very close to the other; on preventing the contents of a cell in a table to be merged with the contents of other adjacent cells; on preventing regions inside a frame to be merged with other text regions around, especially side notes, even when the latter are written using a font similar to that the text body. Quantitative assessment, and comparison of the performances of our method with competitive algorithms using widely acknowledged metrics and evaluation methodologies, is also provided to a large extend.(*) This PhD thesis has been funded by Conseil Général de Seine-Saint-Denis, through the FUI6 project Demat-Factory, lead by Safig SA

The human vision system is generally recognized as being superior to all known artificial vision systems. Visual attention, among many processes that are related to human vision, is responsible for identifying relevant regions in a scene for further processing. In most cases, analyzing an entire scene is unnecessary and inevitably time consuming. Hence considering visual attention might be advantageous. A subfield of computer vision where this particular functionality is computationally emulated has been shown to retain high potential in solving real world vision problems effectively. In this monograph, elements of visual attention are explored and algorithms are proposed that exploit such elements in order to enhance image understanding capabilities. Satellite images are given special attention due to their practical relevance, inherent complexity in terms of image contents, and their resolution. Processing such large-size images using visual attention can be very helpful since one can first identify relevant regions and deploy further detailed analysis in those regions only. Bottom-up features, which are directly derived from the scene contents, are at the core of visual attention and help identify salient image regions. In the literature, the use of intensity, orientation and color as dominant features to compute bottom-up attention is ubiquitous. The effects of incorporating an entropy feature on top of the above mentioned ones are also studied. This investigation demonstrates that such integration makes visual attention more sensitive to fine details and hence retains the potential to be exploited in a suitable context. One interesting application of bottom-up attention, which is also examined in this work, is that of image segmentation. Since low salient regions generally correspond to homogenously textured regions in the input image; a model can therefore be learned from a homogenous region and used to group similar textures existing in other image regions. Experimentation demonstrates that the proposed method produces realistic segmentation on satellite images. Top-down attention, on the other hand, is influenced by the observer’s current states such as knowledge, goal, and expectation. It can be exploited to locate target objects depending on various features, and increases search or recognition efficiency by concentrating on the relevant image regions only. This technique is very helpful in processing large images such as satellite images. A novel algorithm for computing top-down attention is proposed which is able to learn and quantify important bottom-up features from a set of training images and enhances such features in a test image in order to localize objects having similar features. An object recognition technique is then deployed that extracts potential target objects from the computed top-down attention map and attempts to recognize them. An object descriptor is formed based on physical appearance and uses both texture and shape information. This combination is shown to be especially useful in the object recognition phase. The proposed texture descriptor is based on Legendre moments computed on local binary patterns, while shape is described using Hu moment invariants. Several tools and techniques such as different types of moments of functions, and combinations of different measures have been applied for the purpose of experimentations. The developed algorithms are generalized, efficient and effective, and have the potential to be deployed for real world problems. A dedicated software testing platform has been designed to facilitate the manipulation of satellite images and support a modular and flexible implementation of computational methods, including various components of visual attention models.

In biology, many different kinds of microscopy are used to study cells. There are many different kinds of transmission microscopy, where light is passed through the cells, that can be used without staining or other treatments that can harm the cells. There is also fluorescence microscopy, where fluorescent proteins or dyes are placed in the cells or in parts of the cells, so that they emit light of a specific wavelength when they are illuminated with light of a different wavelength. Many fluorescence microscopes can take images on many different depths in a sample and thereby build a three-dimensional image of the sample. Fluorescence microscopy can also be used to study particles, for example viruses, inside cells. Modern microscopes often have digital cameras or other equipment to take images or record time-lapse video. When biologists perform experiments on cells, they often record image sequences or sequences of three-dimensional volumes to see how the cells behave when they are subjected to different drugs, culture substrates, or other external factors. Previously, the analysis of recorded data has often been done manually, but that is very time-consuming and the results often become subjective and hard to reproduce. Therefore there is a great need for technology for automated analysis of image sequences with cells and particles inside cells. Such technology is needed especially in biological research and drug development. But the technology could also be used clinically, for example to tailor a cancer treatment to an individual patient by evaluating different treatments on cells from a biopsy. This thesis presents algorithms to find cells and particles in images, and to calculate tracks that show how they have moved during an experiment. We have developed a complete system that can find and track cells in all commonly used imaging modalities. We selected and extended a number of existing segmentation algorithms, and thereby created a complete tool to find cell outlines. To link the segmented objects into tracks, we developed a new track linking algorithm. The algorithm adds tracks one by one using dynamic programming, and has many advantages over prior algorithms. Among other things, it is fast, it calculates tracks which are optimal for the entire image sequence, and it can handle situations where multiple cells have been segmented incorrectly as one object. To make it possible to use information about the velocities of the objects in the linking, we developed a method where the positions of the objects are preprocessed using a filter before the linking is performed. This is important for tracking of some particles inside cells and for tracking of cell nuclei in some embryos.       We have developed an open source software which contains all tools that are necessary to analyze image sequences with cells or particles. It has tools for segmentation and tracking of objects, optimization of settings, manual correction, and analysis of outlines and tracks. We developed the software together with biologists who used it in their research. The software has already been used for data analysis in a number of biology publications. Our system has also achieved outstanding performance in three international objective comparisons of systems for tracking of cells. / Inom biologi används många olika typer av mikroskopi för att studera celler. Det finns många typer av genomlysningsmikroskopi, där ljus passerar genom cellerna, som kan användas utan färgning eller andra åtgärder som riskerar att skada cellerna. Det finns också fluorescensmikroskopi där fluorescerande proteiner eller färger förs in i cellerna eller i delar av cellerna, så att de emitterar ljus av en viss våglängd då de belyses med ljus av en annan våglängd. Många fluorescensmikroskop kan ta bilder på flera olika djup i ett prov och på så sätt bygga upp en tre-dimensionell bild av provet. Fluorescensmikroskopi kan även användas för att studera partiklar, som exempelvis virus, inuti celler. Moderna mikroskop har ofta digitala kameror eller liknande utrustning för att ta bilder och spela in bildsekvenser. När biologer gör experiment på celler spelar de ofta in bildsekvenser eller sekvenser av tre-dimensionella volymer för att se hur cellerna beter sig när de utsätts för olika läkemedel, odlingssubstrat, eller andra yttre faktorer. Tidigare har analysen av inspelad data ofta gjorts manuellt, men detta är mycket tidskrävande och resultaten blir ofta subjektiva och svåra att reproducera. Därför finns det ett stort behov av teknik för automatiserad analys av bildsekvenser med celler och partiklar inuti celler. Sådan teknik behövs framförallt inom biologisk forskning och utveckling av läkemedel. Men tekniken skulle också kunna användas kliniskt, exempelvis för att skräddarsy en cancerbehandling till en enskild patient genom att utvärdera olika behandlingar på celler från en biopsi. I denna avhandling presenteras algoritmer för att hitta celler och partiklar i bilder, och för att beräkna trajektorier som visar hur de har förflyttat sig under ett experiment. Vi har utvecklat ett komplett system som kan hitta och följa celler i alla vanligt förekommande typer av mikroskopi. Vi valde ut och vidareutvecklade ett antal existerande segmenteringsalgoritmer, och skapade på så sätt ett heltäckande verktyg för att hitta cellkonturer. För att länka ihop de segmenterade objekten till trajektorier utvecklade vi en ny länkningsalgoritm. Algoritmen lägger till trajektorier en och en med hjälp av dynamisk programmering, och har många fördelar jämfört med tidigare algoritmer. Bland annat är den snabb, den beräknar trajektorier som är optimala över hela bildsekvensen, och den kan hantera fall då flera celler felaktigt segmenterats som ett objekt. För att kunna använda information om objektens hastighet vid länkningen utvecklade vi en metod där objektens positioner förbehandlas med hjälp av ett filter innan länkningen utförs. Detta är betydelsefullt för följning av vissa partiklar inuti celler och för följning av cellkärnor i vissa embryon. Vi har utvecklat en mjukvara med öppen källkod, som innehåller alla verktyg som krävs för att analysera bildsekvenser med celler eller partiklar. Den har verktyg för segmentering och följning av objekt, optimering av inställningar, manuell korrektion, och analys av konturer och trajektorier. Vi utvecklade mjukvaran i samarbete med biologer som använde den i sin forskning. Mjukvaran har redan använts för dataanalys i ett antal biologiska publikationer. Vårt system har även uppnått enastående resultat i tre internationella objektiva jämförelser av system för följning av celler. / <p>QC 20161125</p>

La résolution satisfaisante d'un problème d'optimisation difficile, qui comporte un grand nombre de solutions sous-optimales, justifie souvent le recours à une métaheuristique puissante. La majorité des algorithmes utilisés pour résoudre ces problèmes d'optimisation sont les métaheuristiques à population. Parmi celles-ci, nous intéressons à l'Optimisation par Essaim Particulaire (OEP, ou PSO en anglais) qui est apparue en 1995. PSO s'inspire de la dynamique d'animaux se déplaçant en groupes compacts (essaims d'abeilles, vols groupés d'oiseaux, bancs de poissons). Les particules d'un même essaim communiquent entre elles tout au long de la recherche pour construire une solution au problème posé, et ce en s'appuyant sur leur expérience collective. L'algorithme PSO, qui est simple à comprendre, à programmer et à utiliser, se révèle particulièrement efficace pour les problèmes d'optimisation à variables continues. Cependant, comme toutes les métaheuristiques, PSO possède des inconvénients, qui rebutent encore certains utilisateurs. Le problème de convergence prématurée, qui peut conduire les algorithmes de ce type à stagner dans un optimum local, est un de ces inconvénients. L'objectif de cette thèse est de proposer des mécanismes, incorporables à PSO, qui permettent de remédier à cet inconvénient et d'améliorer les performances et l'efficacité de PSO. Nous proposons dans cette thèse deux algorithmes, nommés PSO-2S et DEPSO-2S, pour remédier au problème de la convergence prématurée. Ces algorithmes utilisent des idées innovantes et se caractérisent par de nouvelles stratégies d'initialisation dans plusieurs zones, afin d'assurer une bonne couverture de l'espace de recherche par les particules. Toujours dans le cadre de l'amélioration de PSO, nous avons élaboré une nouvelle topologie de voisinage, nommée Dcluster, qui organise le réseau de communication entre les particules. Les résultats obtenus sur un jeu de fonctions de test montrent l'efficacité des stratégies mises en oeuvre par les différents algorithmes proposés. Enfin, PSO-2S est appliqué à des problèmes pratiques, en segmentation d'images et en électronique / The successful resolution of a difficult optimization problem, comprising a large number of sub optimal solutions, often justifies the use of powerful metaheuristics. A wide range of algorithms used to solve these combinatorial problems belong to the class of population metaheuristics. Among them, Particle Swarm Optimization (PSO), appeared in 1995, is inspired by the movement of individuals in a swarm, like a bee swarm, a bird flock or a fish school. The particles of the same swarm communicate with each other to build a solution to the given problem. This is done by relying on their collective experience. This algorithm, which is easy to understand and implement, is particularly effective for optimization problems with continuous variables. However, like several metaheuristics, PSO shows some drawbacks that make some users avoid it. The premature convergence problem, where the algorithm converges to some local optima and does not progress anymore in order to find better solutions, is one of them. This thesis aims at proposing alternative methods, that can be incorporated in PSO to overcome these problems, and to improve the performance and the efficiency of PSO. We propose two algorithms, called PSO-2S and DEPSO-2S, to cope with the premature convergence problem. Both algorithms use innovative ideas and are characterized by new initialization strategies in several areas to ensure good coverage of the search space by particles. To improve the PSO algorithm, we have also developed a new neighborhood topology, called Dcluster, which can be seen as the communication network between the particles. The obtained experimental results for some benchmark cases show the effectiveness of the strategies implemented in the proposed algorithms. Finally, PSO-2S is applied to real world problems in both image segmentation and electronics fields

Segundo o Instituto Nacional do Câncer (INCA), o câncer de colorretal é o terceiro tipo de câncer mais comum entre os homens e o segundo entre as mulheres. Atualmente a avaliação visual feita por um patologista é o principal método utilizado para o diagnóstico de doenças a partir de imagens microscópicas obtidas por meio de amostras em exames convencionais de biópsia. A utilização de técnicas de processamento computacional de imagens possibilita a identificação de elementos e a extração de características, o que contribui com o estudo da organização estrutural dos tecidos e de suas variações patológicas, levando a um aumento da precisão no processo de tomada de decisão. Os conceitos e técnicas envolvendo redes complexas são recursos valiosos para o desenvolvimento de métodos de análise estrutural de componentes em imagens médicas. Dentro dessa perspectiva, o objetivo geral deste trabalho foi o desenvolvimento de um método capaz de realizar o processamento e a análise de imagens obtidas em exames de biópsias de tecidos de pólipo de cólon para classificar o grau de atipia da amostra, que pode variar em: sem atipia, baixo grau, alto grau e câncer. Foram utilizadas técnicas de processamento, incluindo um conjunto de operadores morfológicos, para realizar a segmentação e a identificação de estruturas glandulares. A seguir, procedeu-se à análise estrutural baseada na identificação das glândulas, usando técnicas de redes complexas. As redes foram criadas transformado os núcleos das células que compõem as glândulas em vértices, realizando a ligação dos mesmos com 1 até 20 arestas e a extração de medidas de rede para a criação de um vetor de características. A fim de avaliar comparativamente o método proposto, foram utilizados extratores clássicos de características de imagens, a saber, Descritores de Haralick, Momentos de Hu, Transformada de Hough, e SampEn2D. Após a avaliação do método proposto em diferentes cenários de análise, o valor de acurácia geral obtida pelo mesmo foi de 82.0%, superando os métodos clássicos. Conclui-se que o método proposto para classificação de imagens histológicas de pólipos utilizando análise estrutural baseada em redes complexas mostra-se promissor no sentido de aumentar a acurácia do diagnóstico de câncer colorretal / According to the National Cancer Institute (INCA), colorectal cancer is the third most common cancer among men and the second most common cancer among women. Currently the main method used for the diagnosis of diseases from microscopic images obtained through samples in conventional biopsy tests are the visual evaluation made by a pathologist. The use of computational image processing techniques allows the identification of elements and the extraction of characteristics, which contributes to the study of the structural organization of tissues and their pathological variations, leading to an increase of precision in the decision making process. Concepts and techniques involving complex networks are valuable resources for the development of structural analysis methods of components in medical images. In this perspective, the general objective of this work was the development of a method capable of performing the image processing and analysis obtained in biopsies of colon polyp tissue to classify the degree of atypia of the sample, which may vary in: without atypia, low grade, high grade and cancer. Processing techniques including a set of morphological operators, were used to perform the segmentation and identification of glandular structures. Next, structural analysis was performed based on glands identification, using complex network techniques.The networks were created transforming the core of the cells that make up the glands in vertices, making the connection of the same with 1 to 20 edges and the extraction of network measurements to create a vector of characteristics. In order to comparatively evaluate the proposed method, classical image characteristic extractors were used, namely, Haralicks Descriptors, Hus Moments, Hough Transform, and SampEn2D. After the evaluation of the proposed method in different analysis scenarios, the overall accuracy value obtained by it was 82.0%, surpassing the classical methods. It is concluded that the proposed method for the classification of histological images of polyps using structural analysis based on complex networks is promising in order to increase the accuracy of the diagnosis of colorectal cancer

In recent years semantic segmentation models utilizing Convolutional Neural Networks (CNN) have seen significant success for multiple different segmentation problems. Models such as U-Net have produced promising results within the medical field for both regular 2D and volumetric imaging, rivalling some of the best classical segmentation methods. In this thesis we examined the possibility of using a convolutional neural network-based model to perform segmentation of discrete bone fragments in CT-volumes with segmentation-hints provided by a user. We additionally examined different classical segmentation methods used in a post-processing refinement stage and their effect on the segmentation quality. We compared the performance of our model to similar approaches and provided insight into how the interactive aspect of the model affected the quality of the result. We found that the combined approach of interactive segmentation and deep learning produced results on par with some of the best methods presented, provided there were adequate amount of annotated training data. We additionally found that the number of segmentation hints provided to the model by the user significantly affected the quality of the result, with convergence of the result around 8 provided hints.

A área médica tem se beneficiado das ferramentas construídas pela Computação e, ao mesmo tempo, tem impulsionado o desenvolvimento de novas técnicas em diversas especialidades da Computação. Dentre estas técnicas a segmentação tem como objetivo separar em uma imagem objetos de interesse, podendo chamar a atenção do profissional de saúde para áreas de relevância ao diagnóstico. Além disso, os resultados da segmentação podem ser utilizados para a reconstrução de modelos tridimensionais, que podem ter características extraídas que auxiliem o médico em tomadas de decisão. No entanto, a segmentação de imagens médicas ainda é um desafio, por ser extremamente dependente da aplicação e das estruturas de interesse presentes na imagem. Esta dissertação apresenta uma técnica de segmentação semiautomática do endocárdio do ventrículo esquerdo em conjuntos de imagens cardíacas de Ressonância Magnética Nuclear. A principal contribuição é a segmentação considerando todas as imagens provenientes de um exame, por meio da propagação dos resultados obtidos em imagens anteriormente processadas. Os resultados da segmentação são avaliados usando-se métricas objetivas como overlap, entre outras, comparando com imagens fornecidas por especialistas na área de Cardiologia / The medical field has been benefited from the tools built by Computing and has promote the development of new techniques in diverse Computer specialties. Among these techniques, the segmentation aims to divide an image into interest objects, leading the attention of the specialist to areas that are relevant in diagnosys. In addition, segmentation results can be used for the reconstruction of three-dimensional models, which may have extracted features that assist the physician in decision making. However, the segmentation of medical images is still a challenge because it is extremely dependent on the application and structures of interest present in the image. This dissertation presents a semiautomatic segmentation technique of the left ventricular endocardium in sets of cardiac images of Nuclear Magnetic Resonance. The main contribution is the segmentation considering all the images coming from an examination, through the propagation of the results obtained in previously processed images. Segmentation results are evaluated using objective metrics such as overlap, among others, compared to images provided by specialists in the Cardiology field

A segmentação de imagens e, em visão computacional, uma tarefa de grande importância, para a qual existem várias abordagem. A complexidade de tais abordagens está relacionada à natureza da imagem e também ao grau de precisão da segmentação, que e um conceito bastante subjetivo, normalmente associado a semelhança que apresenta a segmentaçã produzida pela visão humana. Na segmentação de imagens baseada em algoritmos de agrupamento em grafos, geralmente os pixels da imagem compôem os nós do grafo e as arestas representam a similaridade entre estes nós. Assim, a segmentação pode ser obtida por meio do agrupamento dos nós do grafo. É importante salientar, no entanto, que as técnicas de agrupamento em grafos surgiram no contexto de reconhecimento de padrões, cujo objetivo primario era o tratamento de dados diversos que não envolviam imagens. O uso de tais tecnicas para a segmentação de imagens e relativamente recente e revela alguns problemas desaadores. O primeiro deles é a deficiente escalabilidade de alguns métodos, o que impede o seu uso efetivo em imagens de altas dimensões. Outra questão é a falta de estudos que avaliam as medidas de similaridade na montagem do grafo e critérios que aferem a qualidade do agrupamento para a área específica de segmentação de imagens. Em outras palavras, faltam na literatura análises mais específicas que indiquem quais algoritmos de agrupamento em grafos são mais efetivos para a segmentação de imagens e que procurem associar (ou correlacionar) as várias medidas de similaridade e métricas de qualidade de agrupamento que produzam segmentações mais precisas. Neste trabalho é apresentada a avaliação de 6 algoritmos de agrupamento em grafos formulados em base a 3 categorias identificadas (agrupamento espectral, algoritmos de particionamento multinível e algoritmos para detectar comunidades) e aplicadas na segmentação automática de imagens de cenas naturais com grandes dimensões. Esta avaliação objetiva aferir, sobretudo, a qualidade da segmentação, a escalabilidade, o desempenho de 7 funções de similaridade formuladas, e também visa corroborar a existência da correlação entre a qualidade do agrupamento e a qualidade da segmentação. Para reduzir o esforço computacional e contribuir com a escalabilidade dos algoritmos formulados é utilizado um algoritmo de pré-processamento (SLIC) que agrupa váarios pixels da imagem em uma unica região (superpixels), o que contribui para reduzir o tamanho do grafo e, consequentemente, reduzindo o custo computacional do agrupamento. Os resultados demostram que os algoritmos formulados LP (Label Propagation) e FG (Fast Greedy) apresentam boa escalabilidade e boa qualidade de segmentação. Seis das sete funções de similaridade avaliadas apresentam um bom desempenho, independentemente do algoritmo de agrupamento empregado. É mostrado também que exites correlação entre a medida de qualidade de agrupamento conhecido como índice de silhueta e a qualidade de segmentação, ou seja, quanto maior o valor de silhueta, melhor a segmentação. A qualidade de segmentação foi avaliada quantitativamente, utilizando-se um conjunto de imagens segmentadas manualmente / Image segmentation is an important task within computer vision for which many approaches are available. The complexity of such approaches are intrinsically related with the nature of the image and also the desired accuracy aimed at. Image segmentation accuracy, however, is a subjective concept and is normally associated with how much it resembles segmentation produced by the human vision system. In graphbased clustering image segmentation algorithms, pixels are normally represented as nodes and edges convey the similarity between such nodes. Hence, segmentation may be attained by means of grouping node of a graph. It is important, though, to point out that graph-based clustering techniques rst appeared in the context of pattern recognition and its primary data source were not images. The usage of such techniques for image segmentation is a recent trend and poses some challenge issues. The first is the poor scalability that many methods exhibit, impairing its application in images of larger dimensions. Another issues is that lack of studies that assess the goodness of similarity measures employed in graph computation and also clustering quality criteria assessments for the specic area of image processing. In other words, there is no evidences in the literature on how effective graph-based clustering algorithms are for image segmentation and no studies that associate similarity functions and clustering quality metrics with image processing quality. This work presents an evaluation of six graph-based clustering algorithms according to three major categories found in the literature (spectral clustering, multi layer partitioning algorithms and community detectors) applied to automatic segmentation of image of larger dimensions. This evaluation takes into account segmentation quality, scalability, the performance of seven similarity functions and, nally, bring some insights on the correlation between clustering and segmentation quality. To reduce computational costs and enhance scalability of the methods we employ a pre processing algorithm (SLIC) which combines many pixels into one single region (superpixel). This contributes to reduce the graph size and, consequently, the cost of clustering. Results have shown that the LP (Label Propagation) and FG (Fast Greedy) algorithms exhibit good scalability and good segmentation. Six out of the seven similarity functions presented good performance, regardless the clustering algorithm. We also have shown that there is correlation between clustering quality and image segmentation quality, when the Silhouette measure is employed. That is, the higher the Silhouette values, the better the segmentation. Image segmentation quality has been quantitatively assessed by means of ground-truth data or user segmented images

A segmentação é um passo importante em praticamente todas as tarefas que envolvem processamento de imagens digitais. Devido à variedade de imagens e diferentes necessidades da segmentação, a automação da segmentação não é uma tarefa trivial. Em muitas situações, abordagens interativas, nas quais o usuário pode intervir para guiar o processo de segmentação, são bastante úteis. Abordagens baseadas na transformação watershed mostram-se adequadas para a segmentação interativa de imagens: o watershed a partir de marcadores possibilita que o usuário marque as regiões de interesse na imagem; o watershed hierárquico gera uma hierarquia de partições da imagem sendo analisada, hierarquia na qual o usuário pode navegar facilmente e selecionar uma particular partição (segmentação). Em um trabalho prévio, propomos um método que integra as duas abordagens de forma que o usuário possa combinar os pontos fortes dessas duas formas de interação intercaladamente. Apesar da versatilidade obtida ao se integrar as duas abordagens, as hierarquias construídas dificilmente contêm partições interessantes e o esforço de interação necessário para se obter um resultado desejado pode ser muito elevado. Nesta tese propomos um método, baseado em aprendizagem computacional, que utiliza imagens previamente segmentadas para tentar adaptar uma dada hierarquia de forma que esta contenha partições mais próximas de uma partição de interesse. Na formulação de aprendizagem computacional, diferentes características da imagem são associadas a possíveis contornos de regiões, e esses são classificados como contornos que devem ou não estar presentes na partição final por uma máquina de suporte vetorial previamente treinada. A hierarquia dada é adaptada de forma a conter uma partição que seja consistente com a classificação obtida. Essa abordagem é particularmente interessante em cenários nos quais lotes de imagens similares ou sequências de imagens, como frames em sequências de vídeo ou cortes produzidas por exames de diagnóstico por imagem, precisam ser segmentadas. Nesses casos, é esperado que, a cada nova imagem a ser segmentada, o esforço de interação necessário para se obter a segmentação desejada seja reduzido em relação ao esforço que seria necessário com o uso da hierarquia original. Para não dependermos de experimentos com usuários na avaliação da redução no esforço de interação, propomos e utilizamos um modelo de interação que simula usuários humanos no contexto de segmentação hierárquica. Simulações deste modelo foram comparadas com sequências de interação observadas em experimentos com usuários humanos. Experimentos com diferentes lotes e sequências de imagens mostram que o método é capaz de reduzir o esforço de interação. / Segmentation is an important step in nearly all tasks involving digital image processing. Due to the variety of images and segmentation needs, automation of segmentation is not a trivial task. In many situations, interactive approaches in which the user can intervene to guide the segmentation process, are quite useful. Watershed transformation based approaches are suitable for interactive image segmentation: the watershed from markers allows the user to mark the regions of interest in the image; the hierarchical watershed generates a hierarchy of partitions of the image being analyzed, hierarchy in which the user can easily navigate and select a particular partition (segmentation). In a previous work, we have proposed a method that integrates the two approaches so that the user can combine the strong points of these two forms of interaction interchangeably. Despite the versatility obtained by integrating the two approaches, the built hierarchies hardly contain interesting partitions and the interaction effort needed to obtain a desired outcome can be very high. In this thesis we propose a method, based on machine learning, that uses images previously segmented to try to adapt a given hierarchy so that it contains partitions closer to the partition of interest. In the machine learning formulation, different image features are associated to the possible region contours, and these are classified as ones that must or must not be present in the final partition by a previously trained support vector machine. The given hierarchy is adapted to contain a partition that is consistent with the obtained classification. This approach is particularly interesting in scenarios where batches of similar images or sequences of images, such as frames in video sequences or cuts produced by imaging diagnosis procedures, need to be segmented. In such cases, it is expected that for each new image to be segmented, the interaction effort required to achieve the desired segmentation is reduced relative to the effort that would be required when using the original hierarchy. In order to do not depend on experiments with users in assessing the reduction in interaction effort, we propose and use an interaction model that simulates human users in the context of hierarchical segmentation. Simulations of this model were compared with interaction sequences observed in experiments with humans users. Experiments with different bacthes and image sequences show that the method is able to reduce the interaction effort.