Identificação e Quantificação de Células Oncocíticas em Imagens Microscópicas

Faculdade de Engenharia da Universidade do Porto Identification and Quantification of Oncocytes in Microscopic Images Tiago Marques Dias da Mota Mestrado Integrado em Engenharia Inform´atica e Computa¸c˜ao Supervisor: Rui Camacho - FEUP Co-supervisor: Lu´ısa Pereira - IPATIMUP June 23, 2014 Identification and Quantification of Oncocytes in Microscopic Images Tiago Marques Dias da Mota Mestrado Integrado em Engenharia Inform´atica e Computa¸c˜ao Approved in oral examination by the committee: Chair: Hugo Jos´e Sereno Lopes Ferreira External Examiner: Carlos Alberto da Costa Bastos Supervisor: Rui Carlos Camacho de Sousa Ferreira da Silva June 23, 2014 Abstract Nowadays great scientific fields, such as Medicine, have been recurring to technological advances in terms of computational power and storage capacity. Now it is possible to store large quantities of high resolution images in databases, allowing medical images to be saved for posterior analysis by experts. The problem associated with this resides in the task of manually analyze the images, which can be exhausting and time consuming, with the probability of having direct influence on the results and conclusions obtained by the pathologists, due to these factors and also their subjectivity. By applying Image Processing techniques and Data Mining methods, many medical images have been successfully analyzed with a computer, by means of automatic procedures showing results with high accuracies, that expert pathologists may use to better support their medical diagnosis decisions. Previous studies show that the presence of oncocytic cells in certain types of diseases, like thyroid tumors, may have direct influence on used treatments, which makes extremelly important for a pathologist to have access to this information, at the time he or she is performing the diagnosis. OncoFinder shows that it is possible to create a software tool totally capable of identifying and classify automatically the oncocytes present in microscopic images of thyroid tumors with high quality and resolution, provided by the National Institute of Health. With the help of OncoFinder, the experts, that worked with us, had automatic access to images with cell nuclei segmented, ready to be classified as oncocyte, non-oncocyte or any other component. They generated data that was used to build appropriate datasets to train and test different learning algorithms. The outcomes show that some algorithms can achieve accuracies around 90% of correctly classified oncocytic cells. i ii Resumo Hoje em dia grandes ´areas cient´ıficas como a Medicina tˆem vindo a usufruir dos avan¸cos tecnol´ogicos feitos a n´ıvel de poder computacional e capacidade de armazenamento. Agora ´e poss´ıvel armazenar grandes quantidades de imagens em bases de dados, permitindo que essas possam ser guardadas e analisadas posteriormente por peritos. O problema reside na tarefa de analisar manualmente estas imagens, o que pode ser extremamente cansativo e demorado, com a probabilidade de os resultados serem directamente influenciados por estas condi¸c˜oes, assim como pela subjetividade da avalia¸c˜ao do patologista. Atrav´es da aplica¸c˜ao de t´ecnicas de Processamento de Imagem e m´etodos de ”Data Mining”, diferentes imagens m´edicas tˆem vindo a ser analisadas com sucesso, utilizando um computador, por meio de processos autom´aticos que mostram resultados de elevada precis˜ao que os patologistas podem usar para melhorar e apoiar na decis˜ao dos seus diagn´osticos m´edicos. Estudos pr´evios demonstram que a presen¸ca de c´elulas oncoc´ıticas em certos tipos de doen¸cas, como tumores na tir´oide, pode ter interferˆencia direta com alguns dos tratamentos que s˜ao utilizados, o que torna extremamente importante o acesso, por parte do patologista, a esta informa¸c˜ao na altura em que define o seu diagn´ostico. OncoFinder demonstra que ´e poss´ıvel a cria¸c˜ao de uma ferramenta inform´atica totalmente capaz de identificar e classificar automaticamente os onc´ocitos presentes em imagens de microscopia de tumores na tir´oide com elevada qualidade e resolu¸c˜ao, fornecidas pelo ”National Institute of Health”. Com ajuda do OncoFinder, os especialistas que trabalharam conosco, tiveram acesso autom´atico a imagens com os n´ucleos de c´elulas segmentados, prontos a serem classificados como onc´ocitos, n˜ao onc´ocitos ou outro elemento qualquer. Eles geraram dados que foram usados para a cria¸c˜ao de conjuntos de dados apropriados para treinar e testar diferentes algoritmos de aprendizagem autom´atica. Os resultados obtidos demonstram que alguns destes algoritmos conseguem obter 90% de efic´acia na classifica¸c˜ao autom´atica de c´elulas oncoc´ıticas. iii iv Acknowledgements First of all, I would like to thank my parents for all the support in the past 5 years of collage education, as well as their economic effort to provide me with everything I needed to reach this chapter of my life. I would like to thank my supervisor, the professor Rui Camacho for all the help and guidance he gave me during the development of this Dissertation, and to the expert biologists, Dr. Lu´ısa Pereira and Dr. Valdemar M´aximo for all the help on the Biology terms and concepts of this work and all the patience they had with me. To my girlfriend, all my friends and colleagues, specially the ones from 2009: Thank you for being there, always. Tiago Mota v LIST OF FIGURES A.1 Selection of tile image for manual classification. . . . . . . . . . . . . . . . . 75 A.2 Tile with corrections necessary. . . . . . . . . . . . . . . . . . . . . . . . . . 76 A.3 Addition of new contour and respective classification. . . . . . . . . . . . . . 77 A.4 Group selection of contours. . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 A.5 Final state when corrections and classifications are done. . . . . . . . . . . . 78 xii List of Tables 2.1 Most common Feature Detectors. . . . . . . . . . . . . . . . . . . . . . . . . 11 2.2 Additional ImageJ features. . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.3 Additional OpenCV features. . . . . . . . . . . . . . . . . . . . . . . . . . . 13 4.1 Initial set of attributes results: Accuracy, Precision and Recall. . . . . . . . 51 4.2 Initial set of attributes results: F-measure and ROC. . . . . . . . . . . . . . 52 4.3 Attributes based on Neighbour Cell Nuclei: Accuracy, Precision and Recall. 55 4.4 Attributes based on Neighbour Cell Nuclei: F-measure and ROC. . . . . . . 55 4.5 Attributes based on the histograms and correlation to the circular geometrical form: Accuracy, Precision and Recall. . . . . . . . . . . . . . . . . . . 57 4.6 Attributes based on the histograms and correlation to the circular geometrical form: F-measure and ROC. . . . . . . . . . . . . . . . . . . . . . . . . 58 4.7 All attributes combined: Accuracy, Precision and Recall. . . . . . . . . . . . 60 4.8 All attributes combined: F-measure and ROC. . . . . . . . . . . . . . . . . 60 4.9 Summarized experimental results. . . . . . . . . . . . . . . . . . . . . . . . . 63 xiii LIST OF TABLES xiv Abbreviations CPU Central Processing Unit DIP Digital Image Processing GUI Graphical User Interface IPATIMUP Institute of Molecular Pathology and Immunology of the University of Porto IDE Integrated Development Environment KNN K Nearest Neighbor KDD Knowledge Discovery from Databases LEM2 Learning from Examples Module 2 mtDNA Mitochondrial DNA MLP MultiLayer Perceptron NIH National Institute of Health RAM Random-access memory RMI Remote Method Invocation SVM Support Vector Machines xv Chapter 1 Introduction 1.1 Context and Framing In the past years, the computational power has grown, the cost to manufacture more powerful computers got lower and the storage space available got a significant increase. This made possible for a user to store large amounts of high resolution images, such as images in life sciences studies. By using the available computational power, these images can be treated by computers in order to solve complex problems. Two areas that are very useful to process and analyze large images are Digital Image Processing and Data Mining. Digital Image Processing, processes digital images by means of a computer, in order to find information that might be hidden from the human eye (out of the visible spectrum) or to find specific characteristics in large data sets, which would be hard for a person to do manually. Data Mining provides algorithms to classify or cluster images. These two fields, joined together, allow great scientific accomplishments to be achieved in a wide variety of research topics. The work covered by this thesis concerns both of the above mentioned fields. The goal of the thesis work is to develop a tool to count automatically oncocytic cells in digital images. This is accomplished with direct application of Digital Image Processing techniques, in order to identify oncocytes in microscopic images of great quality, followed by their classification and posterior quantification, using Data Mining methods. 1.2 Problem Description The study of mitochondrial DNA (mtDNA) mutations has shown that these are intimately related with some complex diseases [1]. One example of a disease in this scope are tumors. Tumors on the thyroid, kidney and other tissues and organs, sometimes show a particular phenomenon where cells start to have an abnormal accumulation of mitochondria, which 1 Introduction are the cell components responsible for energy production. These cells are known as oncocytes, as well as Hurthle cells [2]. The thyroid is an example of an organ, where usually these oncocytes show a low invasion rate and are benign. But, some of them might become malign, especially on the thyroid. When this situation happens, it might interfere with the cell ingestion of the iodine-131, used in treatments [3,4]. Here lies the importance of a pathologist identifying this phenomenon or not, since it can help him decide which treatment is best during diagnosis. According to [5], thyroid tumors are designated as oncocytic if 75% of their cells can be described as oncocytes. The affected cells can be identified by their reaction to the phenomenon, where the cells itself has a more rounded nucleus and a eosinophilic1appearance. In this dissertation, the problem in study is based on the identification and classification of these oncocytes in microscopic images. The main objective is to create a tool that is able to identify, classify and quantify this phenomenon automatically, in images available on public databases. The users of this tool will be all pathologists and experts working with tumors that develop this kind of mutations, in order to help them to have an automatic way to determine if a tumor is oncocytic or not. Due to the nature of the problem in study, it is possible to easily break it down into two different sequential steps: Data Acquisition and Data Analysis. This separation is done in order to simplify the explanation and also to expose better, which are the underlying problems present in each one of them. The Data Acquisition step is related to the implemented process responsible for acquiring an image from a specific place and processing it, which identifies cell nuclei in the image. It is also responsible for representing the raw pixel data into useful datasets for the Data Analysis step. In this later step a decision is made on whether an identified cell is an oncocyte or not. The overall objective is to quantify all the identified oncocytes in the tumor. The high quality microscopic images2that will be used are available through the National Institutes of Health3(NIH), and one example can be seen in Figure 1.1a. In order to successfully classify these oncocytes, we need to analyze the images with the help of experts to define which are the structural and morphological characteristics that will help with their identification. For this dissertation we count with the collaboration of experts from Institute of Molecular Pathology and Immunology at the University of Porto (IPATIMUP)4. To achieve this objective, efficient image processing techniques must be applied to the problem. It is also necessary to select the appropriate algorithms or method to apply on the retrieved image data. 1The tendency of a cell, tissue, or organism to be readily stained by the dye eosin. 2Database: https://tcga-data.nci.nih.gov/tcga/showFiles.htm?archiveId=6998 3http://www.nih.gov/ 4https://www.ipatimup.pt/Site/ 2 Introduction (a) (b) Figure 1.1: Test image from NIH (a) and identified oncocytes (b), from [5]. 1.3 Motivation One area that benefits daily with the relation between Data Mining and image processing is Medicine. By analyzing the hidden information on high resolution medical images with a computer, it is possible to provide better support for scientists and researchers, achieving new discoveries that could change our lives. In the context of the topic of our work, pathologists from all over the world struggle to effectively verify the existence of oncocytes inside a tumor - usually thyroid - in order to know the best treatment that should be applied to their patients. The main motivation for our project is to help these pathologists improve their final diagnosis. 1.4 Goals The objective of this project is to create a tool capable of automatically identify oncocytes in digital microscopic images, telling if certain tumor cases are, in it’s total, oncocytic or not. To achieve this goal, we must: •process the provided high quality images. •identify the cells, their nucleus or both. •distinguish between oncocytic and non-oncocytic cells. •quantify the number of oncocytes present in a tumor image. 1.4.1 Thesis Contribution We aim to contribute with a methodology to identify automatically oncocytes in real digital images of human tissues. The methodology includes: •which image processing techniques are adequate. •which machine learning algorithms are appropriate. 3 Introduction 1.5 Structure of the Report Besides this introduction, this thesis has other 4 chapters. In Chapter 2we present the state-of-the-art related to the research areas involved in the problem domain, giving insights on fields such as Digital Image Processing, Data Mining and Machine Learning. It also surveys the available software tools, that might be adapted and used to help solving the addressed problem. Section 3.1 presents the approach taken to achieve the desired goals. In Section 3.2, we propose a general data flow, including a detailed description of how we handle the big microscopic images, how the images are segmented and how we use the learning algorithms to obtain results. Next, in Chapter 4we present the experimental set up and the results obtained using the implemented prototype. Finally in Chapter 5, a retrospective on what is the problem, the work that was done, the objectives fulfilled and the future work are provided. 4 Chapter 2 Digital Image Processing and Machine Learning: Techniques and Tools In this chapter we give meaningful insights on the existing work and research, relevant to the problem domain. The major domains concerning this dissertation include image processing and machine learning. The target application concerns a Medical/Biological problem and therefore we introduce the relevant Biological concepts, which are briefly addressed in Section 2.1. In Section 2.2, an overview on the Digital Image Processing is given, followed by the most used techniques and available software libraries. In Section 2.3, we survey existing software tools used for the identification of cells in images. Section 2.4 refers to the field of Data Mining and its relation with machine learning, as well as an overview on the available learning algorithms and software tools that provide a simple way of using the algorithms. Finally, at the end of this Chapter, a global overview of the state-of-the-art is presented. 2.1 Biological Background To fully understand the application for which the tool was developed it is important to be acquainted with some biological concepts. First, it is crucial to have an overview over the structure of an animal cell and its components [6]. Figure 2.1, gives an overview of the cell structure. 5 Digital Image Processing and Machine Learning: Techniques and Tools One popular approach to extract image features using deformable models is the Active Contours Model, also known as snakes. It is a framework that attempts to minimize an energy associated to the current contour as a sum of internal and external energy, with the objective of delineating an object outline from a noisy or not, 2D image [13]. The external energy is supposed to be minimum when the snake is at the object boundary position, and the internal energy when the snake has a shape which is relevant considering the object being sought. Snakes can be viewed as a rubber band of arbitrary shape that is deforming with time trying to get as close as possible to the object contour. It can be defined with a set o Npoints, an internal elastic energy term and an external edge based energy term. This techniques has high applicability in object tracking, shape recognition, segmentation and edge detection. Different famous implementations of snakes are available [13] like the Gradient Vector Flow, Ballon Snake, Diffusion Snakes and Geometric Active Contours. 2.2.3 Available Libraries Researchers, on different scientific fields, used image processing techniques, to solve different problems, ending up creating algorithms that could be used in other areas and domains. This situation lead to the need of having libraries or frameworks that could offer simple access to implementations of those algorithms, instead of losing time re-implementing them over and over. Some of the libraries that exist are presented below. ImageJ ImageJ 2is an open source collection of image processing algorithms, developed by Wayne Rasband at the National Institutes of Health (NIH), the same institute that is providing the high quality images that will be used in this project. It was designed with an architecture prone to extension, via plug-ins, allowing users to develop on top of the existent library, to solve their specific image processing and Analysis problems. It runs on any computer that has Java 5 or higher. Another library that can be considered a distribution of ImageJ, is Fiji3. This library was made with the purpose and focus on life sciences research, providing a better support for the problems in this domain then the base version ImageJ. OpenCV OpenCV 4, stands for Open Source Computer Vision Library, and it puts together a large collection of algorithms used in image processing. The library was implemented in optimized C/C++ and can take full advantage of all the cores contained in a central 2http://rsbweb.nih.gov/ij/index.html 3http://fiji.sc/Fiji 4http://opencv.org/ 12 Digital Image Processing and Machine Learning: Techniques and Tools Table 2.2: Additional ImageJ features. Feature Description File Formats Open and save GIF, JPEG, BMP, PNG, PGM, FITS and ASCII. Selections Create rectangular, elliptical or irregular area selections. Image Enhancements Supports smoothing, sharpening, edge detection, median filtering and thresholding on both 8-bit gray scale and RGB color images. Color Processing Split a 32-bit color image into RGB or HSV components. Merge 8-bit components into a color image. process unit (CPU). It supports multiple operative systems such as Windows, Linux and Android, providing interfaces for several known programming languages like Java and Python. It has a large active community estimated on almost fifty thousand people. The library can be applied to a lot of problem domains, as well as the one in our work. Table 2.3: Additional OpenCV features. Feature Description Smoothing Images This involves applying blur, Gaussian blur, median blur and bilateral filters to images. Eroding and Dilating The two most common morphology operators: Dilation and Erosion. Morphology Transformations OpenCV provides the morphologyEx function to apply morphological transformations such as opening, closing, TopHat and BlackHat. Basic Thresholding Operations Provides thresholding segmentations using OpenCV function threshold. Histogram Calculation For simple purposes, OpenCV implements the function calcHist, which calculates the histograms of the different color channels of images. 2.3 Tools for Medical Image Analysis With the development of several techniques in image processing, it was clear that different scientific and research areas could take advantage of them. Biologists and other researchers, can use applications, based on these technologies, to start analyzing even further the 13 Digital Image Processing and Machine Learning: Techniques and Tools images they are able to capture over the human body mechanisms, organs and processes. Regarding cellular level images, in the recent past, great accomplishments have been made, that currently help researchers to study their images datasets. In this chapter we present the software tools that relate to the problem domain of this thesis, since these tools are the ones that were developed to aim for the segmentation of cells or cell nuclei in images as the ones we have available for this work. CellNote CellNote5is a software tool designed to help biologists and biomedical researchers in the slow task of manual analysis of microscopic images. The software was developed in the Faculty of Sciences of the University of Porto, with the help of other Portuguese research groups. It provides a semi-automated way of counting cells in microscopic images, in a very versatile approach that allows to change the configuration of the cells that are counted and also the associations that might be needed to help during the analysis. Apart from that, the framework is prepared to receive updates, through the installation of plug-ins, as the one presented in this study [14]. CellNote is still on close beta development, which means that can only be used with an authorization from the developers. CellProfiler CellProfiler [15] is a software tool for modular image analysis, capable of handling thousands of images. CellProfiler simultaneously measures the size, shape, intensity and texture of a variety of cell types in a high throughput manner [16]. It is an open-source software, with a friendly interface and also an actively participating community. Besides this tool, the same developers also offer CellAnalyst [15], which includes machine learning algorithms to apply on image-derived data. CognitionMaster CognitionMaster [17], is a recent software tool, created in the year of 2013, designed for automated image analysis. In the tools presented before, the basic processing unit is the pixel, which is the smallest processable unit of a digital image that contains intensity and color information. In CognitionMaster, the basic processing unit is a group of pixels that together form meaningful biological segments or objects, allowing an object-based analysis. Also, through this approach, CognitionMaster provides an easy access to features of these segments (e.g. Cell Nuclei) like area, length, form factor and others, through an object oriented way. It is a tool made in C#, providing a flexible functionality with a good collection of image analysis algorithms, that can be combined and used through processing chains (pipeline-style) totally editable by the user. The tool also have direct support 5http://cellnote.up.pt/?act=home 14 Digital Image Processing and Machine Learning: Techniques and Tools for images using certain dyes, like the haematoxylin, by having dedicated segmentation operations using the value of the intensity on the dye on certain contour. 2.4 Data Mining 2.4.1 Overview Since computers began to be faster and cheaper people could perform more and more powerful tasks on them, leading up to massive amounts of generated data. Soon, the lack of storage space and ability to analyze this overwhelming data became evident, and right after, a strong need of tools and methods emerged, in order to tackle this issue, so that more useful and task-oriented knowledge could be extracted. According to [18], data is doubling every two years and it is growing faster than the Moore’s Law. This can show the importance of these tools for several fields of study or even industries. 2.4.2 Knowledge Discovery Process How does Data Mining (also known as Knowledge Extraction, data pattern processing, ...) relates with this issue? In fact, what does Data Mining actually means? First, it is necessary to know that this relatively new hot-topic in computer science causes some diverge of opinions on where it place might be. Some say that Data Mining is a synonym for another popular term: Knowledge Discovery from Databases, or KDD. Others think it is the essential step in the Knowledge Discovery Process [19]. As usual in the academic and scientific environment, there are a big number of definitions available. One of them written by W. Frawley on [20] say that: ”Knowledge discovery is the nontrivial extraction of implicit, previously unknown, and potentially useful information from data.” Another one, more metaphoric but self-explanatory was stated by Fred Menger, in 1937: ”If you torture data sufficiently, it will confess almost anything.” Figure 2.5: Sequencial steps of KDD, from [21]. 15 Digital Image Processing and Machine Learning: Techniques and Tools The KDD [21], consists in a iterative sequence of steps followed by practitioners when implementing a knowledge discovery project. There are many different models for this process, but they all follow the same structure and basic steps: 1. Data cleaning — Remove noise and inconsistent data. 2. Data integration — Where multiple data sources may be combined 3. Data selection — Where data relevant to the analysis task is retrieved from the database. 4. Data transformation — Data is transformed into a suitable form, appropriate for the Data Mining method that will be applied. Might be performed before the previous step. 5. Data mining — Essential process where intelligent methods are applied in order to extract patterns from the data. 6. Evaluation — Identify the truly interesting patterns. 7. Knowledge presentation — where visualization and representation techniques are used to show the mined knowledge. The steps 1 to 4 can be considered as different forms of data preprocessing, where the data is ”prepared” for mining. Fayyad et al [22] proposed a structure of a model to this process, which can be seen through the scheme provided in Figure 2.6. This model states that the multiple steps are executed in sequence. Each step that follows the first one, starts its execution upon completion of the previous step, taking as input the output generated by it. Another feature is the possibility to set back to previous the previous step in case the results are not satisfactory. Many models appeared soon in both academic and industrial fields, where the main differences lie on the number of steps and the scope that each model have. On the other hand, all models share the common feature of having the definition of inputs and outputs which typically can be raw database data, flat files, images or video as input and rules, patterns, classification models or associations for output. 16 Digital Image Processing and Machine Learning: Techniques and Tools Figure 2.6: Overview of the steps in the Knowledge Discovery from Databases, from [22]. Data Mining is, therefore, one stage in the the KDD process. It is, however, often used to refer to the whole KDD process. At the early stages of Data Mining, academics started to research on a standard KDD model. The ones that ended up as strongest were the nine step model by Fayyad et al [22] and the eight step model by Anand and Buchner [23]. At the industry level, soon after, attempts to achieve a standard model were being held as well, ending up with two candidates for that position: the five step model by Cabena et al [24] and the six-step CRISP-DM model, which stands for CRoss-Industry Standard Process for Data Mining. Right after, hybrid models started to appear, such as the six-step KDD model described by Pal et al [25] This process ranges from the understanding of the project/problem domain and data, through the analysis and preparation of that data, to evaluation, understanding and interpretation of the mined results, to, finally, apply the generated knowledge. KDD is highly iterative, and includes feedback loops and repetitions that are triggered by revision processes. The main reason why these models appeared, was to formalize knowledge discovery projects within a common framework, in order to achieve time and cost savings, improvement in understanding and acceptance of such projects. A remark that should be added is related to the time spent to complete each of the steps, especially in the data preparation or data preprocessing, since it concerns deciding which data will be served as input for the next step in the process, Data Mining. 2.4.3 Machine Learning According to [19], before the term Data Mining became so popular in academic fields such as statistics, machine learning, pattern recognition and econometrics, researchers in these areas were working on the same technologies, solving similar problems, but in different domains. So, Data Mining, as stated before is applying intelligent methods to extract patterns from data. The word ”intelligent” is the reason why the Data Mining field 17 Digital Image Processing and Machine Learning: Techniques and Tools Figure 2.7: Six-step KDD model, from [25]. overlaps with the machine learning. As said by T. Mitchell [26], the definition of machine learning is: ”A computer program is said to learn from experience Ewith respect to some class of tasks Tand performance measure P, if its performance at tasks in T, as measured by P, improves with experience E.” There are 2 different kinds of goals in Data Mining: predictive and descriptive. This distinction matches directly the differentiation done by the machine learning community, of supervised and unsupervised learning6[19]. The predictive approach focus on solving a specific problem by predicting one or more attributes, in a data set, using the rest of the data. It is about making an educated guess on the value of certain unknown attributes, given the values of other known ones. On the other hand, the descriptive approach is not about solving a specific problem but presenting interesting patterns that a domain expert in the area might not know of yet. These goals can be achieved using Data Mining methods, for the following primary Data Mining learning tasks: •Classification Use of a predictive learning function to classify a data item, as one of the several predefined classes. 6http://www.nyoug.org/Presentations/2005/20050929datamining.pdf 18 Digital Image Processing and Machine Learning: Techniques and Tools •Regression Use of a predictive learning function to map a data item to a real value prediction variable. •Clustering Common descriptive task to seek for a set of categories or clusters to describe the data. •Summarization Additional descriptive task to find a compact description for a set (or subset) of data. •Dependency Modeling Find a local model to describe significant dependencies between variables or between the values of a feature in a data set or in a part of a data set. •Change and Deviation Detection Discover the most significant changes in the data set. The Data Mining methods are basically algorithms, used to fulfill the above tasks. These methods or algorithms, incorporate some type of measures of how good or how interesting a certain pattern needs to be, in order to use it while searching for patterns, to be able to decide which ones to keep, discard or explore further. In our work we are addressing a typical Classification problem, using predictive learning functions, such as the ones described in the following subsection. 2.4.4 Machine Learning Classification Algorithms These algorithms are well-defined procedures that take data as input, and produces models or patterns as outputs7. The explored algorithms in the next sub-section have roots in mathematics, statistics and machine learning. Therefore, these algorithms are not exclusive to Data Mining, but part of these overlapping research fields. In the following sections, some examples of algorithms that can be used for classification problems, are presented. 7http://www.cedar.buffalo.edu/~srihari/CSE626/Lecture-Slides/Ch5-Part1-SystematicOverview. pdf 19 Digital Image Processing and Machine Learning: Techniques and Tools Decision Trees Figure 2.8: Simple Decision Tree, from [27]. A decision tree representation is a logic method that allows one to visualize all the possibilities that follows a decision, in a tree like structure. As we can see in Figure 2.8, they are formed by nodes and branches. Nodes contain attribute’s tests and there is a branch for each possible outcome of the test. It is a predictive model that maps observations about one event to its conclusions, and according to [27], is an efficient non-parametric method to use on classification and regression problems. According to [28], decision tree algorithms take a divide and conquer approach in the way its own structure is built. The problem of building one tree can be expressed as recursive. First, an attribute is chosen to be placed as the root node, then one branch is made for each possible outcome. This splits up the tree into new nodes, that will be processed recursively and independently, for each one of the new nodes, using only the instances needed to reach the new branch. An example of algorithms used to generate decision trees are J. Ross Quilan’s ID3 [29] or its extended version, C4.5 [30]. This improved algorithm include methods to deal with numeric attributes, missing values, noisy data and generating rules from trees. Rule Induction Rule Induction8is one of the most powerful techniques in machine learning, mainly because regularities in data can easily be expressed in terms of rules, that can be used, for example, to classify new samples. Rules usually take the form of expressions like the following: i f (att1,val1)and (att2,val2)and ... and (attn,valn)then (decision,value) 8http://sierpes.cs.us.es/cursos/ia2/trabajos/Rule-Induction-new.pdf 20 Digital Image Processing and Machine Learning: Techniques and Tools where att stands for attribute and val for value. In order to be able to induce rules from the available data some things need to be considered. The most common form of representing data, from where rules can be extracted, is in tables where different samples are listed under columns of independent attributes (i.e. temperature, headache, nausea...) and a dependent decision (i.e. Flu). The data must be consistent and with no errors. If so, rules like this one can be induced: (temperature >38)&(headache =yes)→(Flu =yes) Known and representative examples of types of algorithms are CN2 [31], LEM2 and AQ [32]. Support Vector Machine (SVM) The work on this algorithm started with Vladimir Vapnik, and was originally developed for classification problems, but it has been recently extended to the domain of regression problems. Therefore, for classification problems a more accurate denomination might be Support Vector Classification (SVC). The SVM [27] is a supervised learning algorithm, and very shortly, it is used to create learning functions or models from training data and requires a set of samples to train itself. In the simple example presented by [27], the learning function is created in order to classify the available samples as black or gray. The goal is to produce one classification function that work on unseen examples, which means, a function that generalizes well. Figure 2.9: SVM, from [27]. Through the samples, the SVM creates a model or classifier, where the samples are represented and points in space, mapped in a way that a wide and clear gap is seen between the different categories, which in this case are black and gray. Then the unseen examples are mapped according to the classification function to the side they fall on. This method provides certain advantages, like the easy training process and it also scales well when dealing with more than two dimensions. As disadvantages, it might be a bit inefficient in computational terms [27]. 21 Digital Image Processing and Machine Learning: Techniques and Tools Data Mining, while proving at the same time a powerful tool for experienced users and researchers that want to develop and test their own algorithms. The tool is also extensible by the development of new widgets or self-contained add-ons. Tool comparison According to the research conducted by Wahbeh et al [45]: ”...no tool is better than the other if used for a classification task, since the classification task itself is affected by the type of dataset and the way the classifier was implemented within the toolkit.” The tools tested were Weka, Orange, KNIME and Tanagra15, a free Data Mining software used for research and education purposes. They were tested for classification purposes, with 9 different datasets to judge the results on all these tools, when using six different algorithms: Naive Bayes (NB), Decision Tree (C4.5), Support Vector Machine (SVM), K Nearest neighbour (KNN), One Rule (OneR), and Zero Rule (ZeroR). 2.5 Chapter Conclusions The rapid growth of computational power and storage capacity gave the possibility to different research areas and the industry to process huge amounts of data, in order to withdraw hidden information that can be used in many different ways. One area that has been profiting from the technological advances is Medical Image Analysis, where the availability of high quality images allows different experts in the area to have more accurate insights on the data available on those images, decreasing the usual effects of the manual analysis usually performed. Our work addresses the problem of automatic identification and classification of cells present in high resolution microscopic images of tumors, with the objective of finding the cells that are affected by an unusual amount of mitochondria at the cell’s cytoplasm. For this, image processing techniques need to be applied, as well as machine learning algorithms, in order to classify the identified cells. In both components a vast amount of different research topics were conducted. In terms of cell identification through image processing procedures, a large number of investigations have been done and the usual conclusion is that there is no default recipe that can be used to tackle problems of this nature, since most of the techniques need to be adapted to the problems they are trying to solve. In Section 2.2, an overview of these procedures was presented. Even though there is no basic method that can be applied, these studies give a direction, in the ocean of possible image processing techniques, that are most commonly used to identify cells on images. 15http://eric.univ-lyon2.fr/~ricco/tanagra/ 28 Digital Image Processing and Machine Learning: Techniques and Tools Also, in Section 2.3, some tools were presented, where segmentation techniques can be used by anyone with relative easiness. Regarding the classification of cells, learning algorithms can be used. Once again, there are different methods that can be applied to different problem domains, and there is no right method available for this type of problems, as discussed through Section 2.4.4. However some of them have been successfully applied to solve similar problems, and therefore might be able to solve ours. 29 Digital Image Processing and Machine Learning: Techniques and Tools 30 Chapter 3 Oncofinder: a Tool for Oncocyte Detection 3.1 Approach As stated before, the problem addressed in this Dissertation can be divided into two main phases. The first one corresponds to the identification of oncocytes and the extraction of useful data, from the available tumor images. This information is required in the second phase, which relates to the testing of automatic classification using machine learning methods. In the following sections, the procedure and decisions made, during the development of both phases, are explained. 3.1.1 Phase 1 - Image Processing To be able to successfully identify an oncocyte, the very first step was to identify its characteristics, such as shape, texture and color. So the experts from IPATIMUP, showed us how to visually spot the cells affected by this abnormal amount of mitochondria. The conclusion we reached was that in order to be able to differentiate oncocytes from other components, we ought to get the information about the nucleus of all cells present in the image, since through their morphological characteristics (size, shape, color) together with the distance from their neighbours, we could know if the cell was displaying from this phenomenon, which is present in the cell cytoplasm, that usually is not easily delimited from the background tissue. So the first objective was to segment the nuclei present in a given image, gather and store the morphological information about them. The second objective was to provide the experts with a way to tell if the extracted data corresponded to an oncocyte or not, so that we could be sure what category an identified cell nuclei would fit. With good classified data, we would then be able to apply automatic learning methods on it, verifying if the automatic classification is possible or not. For this task, we implemented a software tool - named OncoFinder - capable of opening an image, automatically run segmentation techniques and show the identified cell nuclei. 31 Oncofinder: a Tool for Oncocyte Detection The tool allow the expert to easily classify the spotted elements into oncocytes, nononcocytes or something else. However, there was another problem that needed to be addressed, before starting the experimentation with segmentation techniques and software tools. The images available to use, provided by the National Institute of Health (NIH), have file sizes reaching 15 or more gigabytes, as well as big resolutions in the order of 40 000 pixels. Adding to this, the images were stored in a format called Aperio Slides (.svs), which is not supported by most of the existing image processing libraries and tools. This format is just a single pyramidal TIFF file divided in layers. Those layers contain different information, stored using key-value pairs. Usually the number of layers in these images are only three, where the first is the baseline (full resolution) image, the second is a thumbnail of the original image and the third, a picture of the case label (case number). After extracting the original image from the first layer, it was necessary to take into account that the resolution of these images reached 40 000 pixels of both width and height, which added the problem of being a wide image to display in a computer screen, way to big for the expert to see and manually classify the segmented cell nuclei. On other hand, processing an image as big as these ones, would take a lot of time, whichever the segmentation technique used, and even impossible for the common computer, since the necessary RAM memory to store the information needed would be huge. Therefore, to solve these problems, the full resolution image needed to be split into several small tiles, suitable for the manual task, required from the experts. After achieving the division of the images into small tiles, the experimentation with existing techniques to segment the cell nucleus started. The first attempt was to see if tools like CellNote, CellProfiler and CognitionMaster could be used to achieve this. We started by checking CellNote, which was on a closed beta stage, requiring the application for a license to use it and, therefore we decided not to use it. CognitionMaster application was the second attempt that offered a nice and intuitive user interface to start experiments with our own images right away, allowing us to check different stages of the segmentation, after executing chained methods. Besides that, the tool provided two different ways of applying segmentation techniques: through the interface menus or by external XML files, with C# methods and respective arguments stored in XML nodes. After testing combinations of techniques, the output segmentation was missing some nuclei present in the image, as well as some clusters of nucleus being identified as only one nucleus, or one contour. Afterwards we tried CellProfiler. The tool has a lot more segmentation techniques than the previous one. We tested several combinations and after some time we did not achieve better results than the ones obtained before, so we decided to move on and try to implement our own combination of techniques using OpenCV. 32 Oncofinder: a Tool for Oncocyte Detection We started with the most simple techniques like Thresholding and Watershed, which led to bad results, where most of the nuclei were not segmented, especially for the overlapped ones. Afterwards, we tried more complex techniques, like Canny Edge Detection 1, K-Means Clustering 2, Hough Circle Transform 3, combining more than one technique, as well as image pre-processing operations like smoothing, blurring, contrast enhancement and morphological operations, such as opening, closing, erosion and dilation, achieving no better results than the ones we got from CognitionMaster. The main reasons why this happened were already stated before in Section 2.2.2. The available tumor cases differ from one another in various aspects, like the intensity of the dye used to separate the existent structures, the shape and color of the nucleus, and sometimes the bad focus on areas with many nucleus together, leading to a blurred overlap of these elements. Also, even inside the same case, the differences in these characteristics could be great. So, together with the pathologist we reached the conclusion that implementing our own combination of techniques would lead to a complex problem, as well as time consuming, and therefore decided upon using the CognitionMaster tool. Besides providing the best segmentation results, the tool could be easily used by external applications, by providing an easy interface to execute chains of image processing techniques, requiring only the XML file containing the desired steps. Also, CognitionMaster automatically calculates attributes of encountered cell nuclei (contours): •Area and length of the contour. •Form factor - length ∗length/area, which corresponds to the shape of a contour in terms of a number. •Mean HDAB - the mean haematoxylin intensity, which is the mean intensity of the used dye in that specific contour. Besides these reasons, CognitionMaster has direct support for images stained with dyes, as the one used in the available images, the haematoxylin. However this decision brought the problem of not having an 100% accurate segmentation, which meant that the segmentation would count with errors: missing contours and wrongly classified ones. To solve this problem, we agreed with the experts to provide a way of correcting the automatic segmentation results using the software tool we were aiming to develop. Through OncoFinder, we allow the user to manually classify obtained contours, as well as adding missing contours and correcting clusters of wrongly segmented ones. The corrections made are then stored to be used in the next phase. After developing OncoFinder, we gave it to the experts, so that they could test it and give us feedback of problems and needs of the tool. As soon as the tool was good enough, 1http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/canny_detector/canny_detector. html 2http://docs.opencv.org/modules/core/doc/clustering.html 3http://docs.opencv.org/doc/tutorials/imgproc/imgtrans/hough_circle/hough_circle.html 33 Oncofinder: a Tool for Oncocyte Detection they started classifying tile images, generating data for us to move on to the second phase of the project. 3.1.2 Phase 2 - Data Analysis and Classification After gathering the data generated by the manual classification, the next step was to apply machine learning algorithms to see if any of them could be used to achieve good automatic results. To do so, it was necessary to choose from a set of available machine learning tools. There is no tool better than other at performing a classification task [45], yet Weka shows good ability on running them by providing a good command-line interface, which allows the development of scripts capable of running multiple learning algorithms. It also allows to access detailed results and metrics such as Accuracy, True Positives rate, False Positives rate, Precision, Recall, F-Measure and ROC Area, which are explained in Section 2.4.5. First, the stored analyzed data by the experts, needed to be treated and transformed into suitable datasets, which relates to the first, second, third and fourth steps in the Knowledge Discovery Process as stated in Section 2.4.2. By choosing Weka as the tool to apply learning methods, the datasets ought to be files with Comma-separated Values (.csv) format or Attribute-Relation File Format (.arff). Also, in order to evaluate the efficiency of machine learning methods there are at least, three empirical ways of doing so, which were referred in Section 2.4.5. The selected way was the hold-out methodology. From the available stored data, 10 balanced datasets were created, where 70% of the data is set to train the model that is built by the chosen classifier, and the remainder 30% to test it. In both training and testing sets, the number of contours, manually classified as oncocytes, was the same as other contours present, in order to guarantee that a certain dataset will always have a good number of oncocytes to build a good classification model. Therefore, our datasets are perfectly balanced. The contours are randomly selected for each one of the 10 datasets, which means that from one to another the present contours in the training and testing sets might be different. The results obtained with this small number of attributes, was around 80% of correctly classified instances by some of the used learning algorithms, which was not a good percentage for the problem in question, since the number of instances was around 1500 for training, and 500 for testing - 10 to 15 tiles - from 3 different cases. This means that with a lot more instances to classify, the generated models would skip and miss too many oncocyte contours. So, in order to achieve better results, we started looking for new attributes that could be added to each of the contours. Our first approach was to compare the histogram variations of a set of contours classified by the experts. We randomly select 5 of the same classification and took the bonding box, from the original tiles, that could entirely contain them, as well as a bit of the surrounding area, in order to retrieve the histograms for the different colors: red, green, blue and the gray level intensities. With this information we created 3D plot graphics using the 34 Oncofinder: a Tool for Oncocyte Detection points that defined the bounding box as the xand y-axis. As for the z-axis the intensity values from the calculated histograms were used. This resulted in 4 different plots just for a single contour. After comparing the plots of different colors and different types of contours, we analyzed them through the calculus of new attributes based on the intensities returned by the histograms, to see if there was any characteristic in their colors that could help to differentiate them from one another. So for each contour (cell nuclei) and for each histogram we calculated the following attributes: •Number of pixels with intensity values within the defined boundaries, as Figure 3.1 shows: –1%, 5% and 10% in both maximum and minimum of the scale. •Maximum and Minimum intensities. •Average of intensities and respective standard deviation. With this approach we could add to each instance of a contour in the dataset 40 new attributes that can help to describe them. Figure 3.1: Illustrative drawing of the histogram intensity values organization and boundaries, that allow for us to calculate new attributes. One example of the type of plots we generated is displayed in Figure 3.2, showing the blue intensities variation of the retrieved bounding box, as well as the area of the contour itself, which is delimited by the yellow dots. 35 Oncofinder: a Tool for Oncocyte Detection Figure 3.2: 3D plot of the blue intensities of an oncocyte and respective bounding box. The next approach explored the correlation between the contours of cell nuclei we were getting and the circular geometric form. As Figure 3.3 tries to explain, through each contour center we drawn circles around it increasing the radius at a constant pace, until we reached the biggest possible circle that would not go outside of the contour. By doing we so, we could extract as a new attribute the percentage of the contour area (identified in the image with the gray color) that is not inside the biggest drawn circle. Our last approach relates to determine oncocytes by the distance between neighbour cell nuclei (contours). For each one of the well segmented contours, we searched for the closest neighbours, taking into account the corrections made by the experts (missing and wrongly segmented contours). Afterwards we searched only for the closest contours that had the classification of oncocyte. Through the first group of contours, we calculated new attributes: •Percentage of oncocytes present in the founded group of closest neighbours. •Minimal distance to a oncocyte neighbour. 36 Oncofinder: a Tool for Oncocyte Detection Figure 3.3: Correlation between the cell nuclei (contour) and the circular form. •Maximum distance to a oncocyte neighbour. •Average of distances to all oncocytes neighbours. For the second group, where exists only oncocytic nucleus, we calculated the attributes: •Minimal distance to oncocyte. •Maximum distance to oncocyte. In total we added six new attributes to each instance of the dataset. To look for the neighbours effectively we added a limit to the search area around the contour, by using its attribute length and multiplying it by a constant. By doing so, we guaranteed that if a contour is small or big, the search area will be set accordingly. On other hand, we calculated these new attributes with different limits of neighbours to find. First we searched only the 10 closest neighbours, moving to 20 closest and finally to the 30 closest, adding six new attributes to the contours, for each one of these limits. In the end we founded 18 more attributes that can help describe the contours. In the situation where there are no neighbours at all, we consider that the next closest one is one million pixels away, both for the minimal and maximum distances. For the second group of contours, in the cases where there was not enough oncocytes in the vicinity, we just considered the ones that existed to calculate the desired attributes, otherwise the same method was applied: one million pixels away to the minimal and maximum distances. With this approach the results obtained with several learning classifiers, increased to 90% of correctly classified instances. The achieved results are shown and explained, in better detail, at Chapter 4. 37 Oncofinder: a Tool for Oncocyte Detection OncoFinder Main Functionalities In this Section we will address the main functionalities provided to the experts, for the task of classifying image tiles, since it is crucial to have correctly classified data to be able to apply learning methods on it, otherwise the output results would not be relevant at all. Therefore, OncoFinder aimed to give the user a set of operations that would make the job easier. The available operations are given to the user through a menu on the right of the tool’s interface, as Figure 3.9 shows. Figure 3.9: OncoFinder Menu. The main interaction with the tool is done through the mouse, where different events are triggered when certain conditions are met. The most basic and obvious one is the possibility of selecting a certain identified contour, in order to classify it. By clicking with the left button of the mouse on the contour, it can be selected, with visual feedback, where the pixels that define the contour turn into a different color. However, despite being a straightforward requirement, the solution is not that simple, since the contour is 44 Oncofinder: a Tool for Oncocyte Detection a set of points that define its boundaries, its shape does not follow a specific pattern and the user just want to click once to select it. The solution found resides in the Winding Number algorithm [46]. It accurately determines if a point is inside a closed polygon, by computing how many times the polygon winds around the given point in the 2D space. The point is outside, only when the result of the algorithm is 0. As Figure 3.10 shows, by drawing horizontal lines starting at the point we want to check, the algorithm sees how many upwards and downwards edges are crossed by the drawn line, subtracting to the final result if it is an downwards edge or adding if it is an upwards edge. In the end if the result is 0, the point is outside of the polygon. Figure 3.10: Horizontal lines checking if P is outside or inside the Polygon. The pseudo-code of the algorithm is shown next, in Listing 3.3. 1winding_number ( Point P, Point V[] , int n ) 2{ 3int wn = 0; // the winding number counter 4// loop through all edges of the polygon 5for (each edge E[i]:V[i]V[i +1] of the polygon ) { 6if (E[i] crosses upward ( Rule #1) ) { 7if (P is strictly left of E[i]) // Rule #4 8++ wn ;//a valid up intersect right of P.x 9} 10 else if (E[i] crosses downward ( Rule #2)) { 11 if (P is strictly right of E[i]) // Rule #4 12 --wn;// a valid down intersect right of P.x 13 } 14 } 15 return wn;// =0 <=> P is outside the polygon 16 } Listing 3.3: Winding Number algorithm pseudo-code. The referred rules, on the pseudo-code provided, correspond to the Edge Crossing Rules, which can be considered as part of the algorithm itself, despite the fact that they are used for other algorithms and methods as well. 45 Oncofinder: a Tool for Oncocyte Detection 1. An upward edge includes its starting endpoint, and excludes its final endpoint. 2. A downward edge excludes its starting endpoint, and includes its final endpoint. 3. Horizontal edges are excluded. 4. The edge-ray intersection point must be strictly right of the point P. OncoFinder allows the user to select groups of contours by using the mouse to draw a rectangle around the desired cluster of nucleus. Every contour inside the drawn rectangle will be selected, provided that if every pixel, that define the contour, is inside the rectangle. This functionality allows for a quicker selection of groups of contours that will have the same classification. The classification step is done through the menu present at the right side of the interface, where the user can classify all the selected contours with two clicks: one for selecting the desired classification in the given combo box, and the second for clicking ”Ok”, confirming the classification. Each contour starts with the classification of ”Unknown” and the available classifications given to the pathologist are: •Oncocyte. •Non-Oncocyte. •Other (blood vessels, ...). Another functionality provided is the possibility of classifying the remaining contours easily. For instance, if 70% of the encountered contours by the automatic segmentation are already classified by the user, and the remaining are all fit in the same category of Oncocyte, Non-oncocyte or Other, he can simple classify them all at once by using the second combo box provided in the interface menu. Regarding the automatic segmentation errors: missing and wrongly segmented contours, the user can proceed to correcting them by selecting the check box ”Image Correction”. Afterwards he just needs to click on the pixel where a missing contour should be and a pop-up shows asking for the classification the user wants to give to that missing contour. On the other hand, if the user finds a contour that is wrongly segmented it can just erase it by right clicking on it with the mouse, and then add a new contour on that position, just like if it were missing one there. If, by chance, the user commits a mistake it can simple hit ”Ctrl+Z” to undo the changes he has just done. In the end, after all the corrections are done, the pathologist can hit the save button to store all the corrections done to that image tile. Also, after achieving the classification of all the contours that, in the pathologist opinion, are worth being classified, he or she just needs to press the save button to store the information. 46 Oncofinder: a Tool for Oncocyte Detection 3.2.3 Automatic Classification Regarding the automatic classification, we chose to use the Weka Machine Learning tool to apply several learning methods on the analyzed data by the pathologists. However, to use Weka, we needed to generate the datasets, which we decided to make balanced and not purely random, since it could happen that the training set would have a small amount of oncocytes, or even any, to train the model, which would lead to a weak built model to classify the instances present in the testing set. Also, despite the fact that the pathologist could classify a contour as Oncocyte, Non-Oncocyte or Other, the generated datasets count only with instances classified as Oncocytes and Other. Currently the classes Non-Oncocyte and Other are treated as the latter. By doing so, we narrow down the classes, the model has to choose from, when classifying automatically a given instance. To achieve these datasets, the class model used to build OncoFinder was extended, to perform the calculus of the desired attributes, and output all the instances, existing in the raw manually classified data, into an Attribute Relation File (.arff), ready to be used by the Weka framework. As stated before in Section 2.4.6, Weka provides a real simple and flexible commandline interface that can be easily used and automated with Bash scripts. We made a wrapper capable of running several algorithms with different combinations of parameters for each one of them. It also applies the algorithms to every available dataset, giving as output the mean values of each one of the metrics stated in Section 2.4.5, as well as the mean standard deviations. The objective of this wrapper is to gather all the results obtained from the tests performed and collect the best result, directly to a .csv file, which we can use to analyze the achieved results. In Chapter 4, we show and explain with better detail the outcomes obtained. The algorithms, available on Weka, that we used are: •Support Vector Machines: –SMO –LibSVM •Decision Trees: –J48 –FT - Functional Trees –ADTree –BFTree –SimpleCART •Ensembles: 47 Oncofinder: a Tool for Oncocyte Detection –Classification Via Regression –Attribute Classifier –AdaBoostM1 –RandomForest •K-Nearest Neighbours: –IBk •Neural Networks: –MultilayerPerceptron –RBFNetwork •Rule Induction: –DTNB 48 Chapter 4 Experiments and Results In this section we present the methodology and tests performed to verify the possibility of having automated classification of oncocytes using high quality images of thyroid tumor cases. 4.1 Experimental Set Up In order to achieve such outcomes we had to choose good test samples, which means good high quality images from the database provided by the NIH. The experts from IPATIMUP selected three different tumor cases1. The cases selected were: •TCGA-BJ-A0YZ-01Z-00-DX1 •TCGA-BJ-A0Z5-01Z-00-DX1 •TCGA-BJ-A0ZB-01Z-00-DX1 These images were captured at their original resolution, which implies that all of them have the same amplification rate. This gives us certainty that 1 pixel in one image will match, in terms of size, with another pixel of any other case image. All the images were stained with the same dye, haematoxylin, to differentiate the several structures existing in the images. All three cases were divided into tiles of 760 pixels of width and height. It is important to note that some of the output tiles have smaller sizes, since the resolution of each case may not be divisible by 760, resulting in smaller tiles. However, this only happens to tiles near the right and bottom edges of the images, which are blank areas, with no content at all. Therefore they are not important for this experimentation, but might be for future improvements, addressed in Chapter 5. The total number of resulting tiles, for each one of the cases are: 1https://tcga-data.nci.nih.gov/tcga/showFiles.htm?archiveId=6998 49 Experiments and Results •TCGA-BJ-A0YZ-01Z-00-DX1 - 19266 tiles •TCGA-BJ-A0Z5-01Z-00-DX1 - 17550 tiles •TCGA-BJ-A0ZB-01Z-00-DX1 - 14464 tiles From these tiles, only a few where actually analyzed by the pathologist, using OncoFinder: •TCGA-BJ-A0YZ-01Z-00-DX1 - 10 tiles •TCGA-BJ-A0Z5-01Z-00-DX1 - 15 tiles •TCGA-BJ-A0ZB-01Z-00-DX1 - 10 tiles Through the gathered data obtained by the experts analysis we needed to generate treated datasets to use with Weka. We decided to build 10 datasets from the available data, where 70% was used for training and the remainder 30% for testing. The instances present in the different datasets were chosen randomly, but we ensured that each training set would have enough oncocytes, by having the same number of instances of cell nuclei contours, classified as oncocyte and classified as Other. Therefore, we achieved 10 balanced datasets with 2082 instances to train the learning algorithms, and 930 instances to test them. The tests presented in the following sections were performed by a computer with an Intel Core i7-26270QM CPU, 16 gigabytes of RAM and the Ubuntu 14.04 LTS operative system. The version of Weka used was the 3.6. 4.2 Experiments To successfully test different learning algorithms we used the Weka, version 3.6, through the available command-line interface. We implemented Bash scripts, capable of running the selected algorithms with different combinations of parameters. Weka also outputs other metrics, that we already addressed in Section 2.4.5. We can use those metrics to compare learning algorithms as well, therefore we choose to analyze the ROC values, which can tell us if a certain learning method is optimal or if it is simply doing random guessing. 4.2.1 Initial set of used Attributes Our first experiment was conducted using only the attributes that were obtained automatically by CognitionMaster: •Area of contour. •Length of contour. 50 Experiments and Results •Form factor of contour: length ∗length/area. •Mean intensity of haematoxylin in the contour. The objective of this experiment was to see if these attributes were enough to successfully classify a given contour as an oncocyte or not. The outcomes are presented in Tables 4.1 and 4.2, where each row corresponds to the results achieved by each of the tested learning algorithms, in terms of Accuracy, Precision, Recall, F-measure and ROC area. The values presented in these tables are averages given by the 10 results obtained from each of the generated datasets, followed by their standard deviations (between parenthesis). Table 4.1: Initial set of attributes results: Accuracy, Precision and Recall. Algorithms Accuracy Precision Recall classificationViaReg 81.38(1.00) 0.82(0.0097) 0.81(0.0091) smo 81.02(0.90) 0.81(0.0092) 0.81(0.0090) libsvm 62.09(1.62) 0.65(0.0164) 0.62(0.0162) mlpercept 81.42(0.89) 0.81(0.0089) 0.81(0.0086) rbfnet 81.15(0.65) 0.81(0.0110) 0.81(0.0130) attsclass 81.27(0.84) 0.81(0.0083) 0.81(0.0083) adaboost 80.08(0.84) 0.80(0.0084) 0.80(0.0084) rf 81.40(0.64) 0.81(0.0088) 0.81(0.0087) BFTree 80.26(0.84) 0.80(0.0108) 0.80(0.0119) ADTree 80.84(0.96) 0.81(0.0086) 0.81(0.0084) ft 81.38(1.26) 0.82(0.0122) 0.81(0.0101) simpcart 80.28(1.01) 0.80(0.0101) 0.80(0.0102) j48 80.27(1.04) 0.80(0.0101) 0.80(0.0097) dtnb 79.92(1.12) 0.80(0.0097) 0.80(0.0094) ibk 81.06(0.70) 0.81(0.0086) 0.81(0.0086) The best accuracy result was given by Multilayer Perceptron, hereby referenced as MLP, an artificial feed-forward neural network that uses back propagation, a supervised learning technique, to train the network, with an average value of 81.42% of correctly classified instances, using the model built automatically from the generated balanced training set and the 5 attributes that describe each one of the cell nuclei. Although MLP was the one returning the best mean accuracy, the others are not that far off, except for the LibSVM classifier - an implementation of Support Vector Machines - with 62.09% which has the lowest accuracy result. The second best was also an ensemble method: Random Forest with 81.40% of accuracy achieved. Since these two classifiers have close accuracies, we need to look at their standard deviation values to check if the results obtained for the different versions of the datasets (10) are far from the average value. When we compare the MLP with the Random Forest, we see that the first achieved a higher deviation (0.89) than the second (0.64). This 51 Experiments and Results Table 4.2: Initial set of attributes results: F-measure and ROC. Algorithms F-measure ROC classificationViaReg 0.81(0.0091) 0.89(0.0071) smo 0.81(0.0091) 0.81(0.0090) libsvm 0.60(0.0207) 0.62(0.0162) mlpercept 0.81(0.0088) 0.89(0.0072) rbfnet 0.81(0.0134) 0.88(0.0079) attsclass 0.81(0.0083) 0.85(0.0085) adaboost 0.80(0.0084) 0.86(0.0071) rf 0.81(0.0087) 0.89(0.0073) BFTree 0.80(0.0119) 0.87(0.0074) ADTree 0.81(0.0084) 0.88(0.0071) ft 0.81(0.0102) 0.86(0.0199) simpcart 0.80(0.0102) 0.87(0.0089) j48 0.80(0.0098) 0.84(0.0125) dtnb 0.80(0.0094) 0.88(0.0079) ibk 0.81(0.0086) 0.88(0.0086) shows that MLP is having more variation of results for the different balanced datasets, when compared with Random Forest. In terms of ROC values, both MLP and Random Forest show the same result: 0.89. This demonstrate that both of them are not randomly guessing which instance is an oncocyte and which is not, when considering 0.5 has the lowest acceptable value. In Figures 4.1 and 4.2, we present the obtained accuracy and ROC area results in bar plots, in order to be easier to compare the different outcomes of the used algorithms. 52 Experiments and Results Classifiers Accuracy 50 60 70 80 90 100 81.38 81.02 62.09 81.42 81.15 81.27 80.08 81.40 80.26 80.84 81.38 80.28 80.27 79.92 81.06 classificationViaReg smo libsvm mlpercept rbfnet attsclass adaboost rf BFTree ADTree ft simpcart j48 dtnb ibk Figure 4.1: Accuracy results using only the initial set of attributes. Classifiers ROC 0.0 0.2 0.4 0.6 0.8 1.0 0.89 0.81 0.62 0.89 0.88 0.85 0.86 0.89 0.87 0.88 0.86 0.87 0.84 0.88 0.88 classificationViaReg smo libsvm mlpercept rbfnet attsclass adaboost rf BFTree ADTree ft simpcart j48 dtnb ibk 0.7 Figure 4.2: ROC results using only the initial set of attributes. 53 Experiments and Results 4.2.4 All Attributes Combined In our last experiment we simply joined every attribute we calculated to describe each instance of a contour, in the same datasets. This allowed for the usage of 63 different attributes to describe each contour. The obtained results by the Weka Wrapper are shown in Table 4.7 and 4.8. Table 4.7: All attributes combined: Accuracy, Precision and Recall. Algorithms Accuracy Precision Recall classificationViaReg 90.41(0.71) 0.91(0.0071) 0.90(0.0072) smo 89.26(0.94) 0.89(0.0091) 0.89(0.0095) libsvm 86.47(1.39) 0.87(0.0130) 0.86(0.0139) mlpercept 90.42(0.94) 0.91(0.0101) 0.90(0.0098) rbfnet 83.55(1.70) 0.84(0.0088) 0.84(0.0140) attsclass 89.92(0.85) 0.90(0.0080) 0.90(0.0087) adaboost 89.97(0.74) 0.90(0.0080) 0.90(0.0088) rf 89.94(0.79) 0.90(0.0079) 0.90(0.0062) BFTree 88.08(1.38) 0.88(0.0151) 0.88(0.0138) ADTree 89.39(1.14) 0.89(0.0087) 0.89(0.0088) ft 88.55(0.71) 0.89(0.0055) 0.89(0.0054) simpcart 88.37(1.14) 0.88(0.0128) 0.88(0.0132) j48 87.98(0.89) 0.88(0.0073) 0.88(0.0070) dtnb 86.87(0.92) 0.87(0.0080) 0.87(0.0093) ibk 87.54(1.07) 0.88(0.0103) 0.88(0.0107) Table 4.8: All attributes combined: F-measure and ROC. Algorithms F-measure ROC classificationViaReg 0.90(0.0070) 0.96(0.0053) smo 0.89(0.0093) 0.89(0.0095) libsvm 0.86(0.0140) 0.86(0.0139) mlpercept 0.90(0.0098) 0.96(0.0076) rbfnet 0.83(0.0158) 0.90(0.0139) attsclass 0.90(0.0087) 0.96(0.0060) adaboost 0.90(0.0088) 0.96(0.0048) rf 0.90(0.0062) 0.96(0.0042) BFTree 0.88(0.0155) 0.93(0.0150) ADTree 0.89(0.0088) 0.96(0.0042) ft 0.89(0.0054) 0.94(0.0103) simpcart 0.88(0.0133) 0.93(0.0111) j48 0.88(0.0070) 0.93(0.0094) dtnb 0.87(0.0097) 0.94(0.0073) ibk 0.88(0.0107) 0.94(0.0059) In our last experiment the best accuracy was achieved by the MLP algorithm once 60 Experiments and Results again, with an average of 90.42%. However in terms of the standard deviation values we see that other algorithms, like the Classification Via Regression had less variation in the obtained results. The classifier that achieved the worst result was, like in the previous test, the RBFNetwork with an average of 83.55%. By analyzing the standard deviations obtained by the different classifiers in this last experiment, we see that they are much better than in the previous one. In terms of ROC values obtained they are good for all the used classifiers. In Figures 4.7 and 4.8, we present the obtained accuracy and ROC area results of this test. Classifiers Accuracy 50 60 70 80 90 100 90.41 89.26 86.47 90.42 83.55 89.92 89.97 89.94 88.08 89.39 88.55 88.37 87.98 86.87 87.54 classificationViaReg smo libsvm mlpercept rbfnet attsclass adaboost rf BFTree ADTree ft simpcart j48 dtnb ibk Figure 4.7: Accuracy results using all the attributes combined. 4.3 Discussion In the previous sections we gave a detailed description of the experimental set up and the tests performed on the gathered data from the expert’s manual classification of tiles of images of thyroid tumors. The purpose of these tests was to verify if it is possible to automatically classify cells in images as oncocytes or not. In Table 4.9 we summarize the outcomes of the performed experiments. The displayed data show a significant improvement in the automatic classification accuracy in almost 10% from the first to the second and fourth experiments. The third one only shows 61 Experiments and Results Classifiers ROC 0.0 0.2 0.4 0.6 0.8 1.0 0.96 0.89 0.86 0.96 0.90 0.96 0.96 0.96 0.93 0.96 0.94 0.93 0.93 0.94 0.94 classificationViaReg smo libsvm mlpercept rbfnet attsclass adaboost rf BFTree ADTree ft simpcart j48 dtnb ibk 0.7 Figure 4.8: ROC results using all the attributes combined. an improvement of 5%. These experiments show that to achieve better results, the best attributes to use to differentiate oncocytic from normal tumor cells, from all the attributes explored in this thesis are the ones related to the distances between neighbour cells. The other approaches do not show such a big improvement and even when joined together with the attributes related to the distances, the outcomes are slightly worse. It is important to notice that, despite the fact that the best algorithm changed from the first to the fourth experiments, however the one that achieved better results was the Adaboost in terms of accuracy and also standard deviation. Nevertheless, most of the other algorithms tested had good results as well. One other thing to notice is the result of the LibSVM classifier from the two first experiments to the last two, where the accuracy outcome improved from around 60% to 80%. Some research was conducted to understand why the results differed so much from the SMO algorithm in the first two experiments, which is another implementation of optimizers to find linear and non-linear support vector machines. As we searched through the differences we noticed that the Weka’s SMO version of the algorithm the attributes are normalized by default, while in LibSVM they are not. We then realized that we only tested the LibSVM without normalizing the data in the two first experiments, which means that the attributes did not have an equal influence when the dot products where computed to create the model, due to the different scales that are used among the different attributes. 62 Experiments and Results Table 4.9: Summarized experimental results. Test 1 Test 2 Test 3 Test 4 Best Algorithm Multilayer Perceptron Adaboost Classification Via Regression Multilayer Perceptron Datasets CognitionMaster CognitionMaster + Distances CognitionMaster + Histograms + Correlation Circular All Attributes Accuracy 81.42% 91.03% 85.62% 90.42% Standard Deviation 0.89 0.53 1.55 0.94 ROC 0.89 0.96 0.93 0.96 On other perspective it is important to properly select the attributes used in the second experiment, since we looked for neighbours of cell nuclei in different limits (10, 20 and 30) and for every one of these we extract as an attribute the minimal distance to the closest neighbour, which will always be the same for each of the 3 defined limits, introducing redundancy to the dataset. Since the second experiment achieved the best result, as a final test we decided to see if there was any significant statistical difference between the Adaboost and Random Forest results, since they were the ones showing better ability at classifying oncocytes automatically. For this we performed a Paired t-Test using the accuracy values obtained by each of the two algorithms, for each one of the 10 datasets. This test uses a probability value (P−value) to check if the difference is significant, where the traditionally confidence interval used is 95%. If P−value <0.05, the outcomes performed by the classifiers have statistical difference. The achieved P−value was 0.7542, which means that there is no significant statistical difference between them. However it is important to notice that the available samples to perform this test may not be enough to take this conclusion right away. 63 Experiments and Results 64 Chapter 5 Conclusions and Future Work The importance of acquiring information from images is increasing every day, especially in the medical and biological fields. The hidden patterns and details available on images, that many researchers already use to perform ”manual” analysis, can be of the uttermost importance since they can change basic opinions and concepts we take for granted due to our limited vision of the electro-magnetic spectrum. In this Dissertation we addressed the problem of identifying oncocytic cells in thyroid tumors. These cells present an abnormal amount of mitochondria in their cytoplasm, which is a hard task for a pathologist to do that has the probability of having direct impact when choosing the best treatment for a certain patient [3,4]. In the following Sections we compare our results with the initial objectives determined for this Dissertation, as well as the future work needed to improve further the presented work. 5.1 Objectives Fulfillment During the work made for this thesis, together with the experts from IPATIMUP we analyzed tumor cases, to learn how we could identify an oncocyte, in order to create a tool capable of segmenting the existing structures of the available images, provided by the National Institute of Health (NIH). We focused in the cell nuclei, since the abnormal amount of mitochondria in some cells have a side effect, which is the swelling of the cytoplasm resulting in a bigger inter-cellular distance between cell nuclei, which would not happen if the cells were not oncocytic. We faced problems trying to segment these nuclei, testing and experimenting with different tools and techniques, resulting in reasonable results, that we compensated by providing a tool to the pathologists capable of performing a automatic preliminary segmentation, that could be corrected using the functionalities of the very same tool. 65 Conclusions and Future Work After implementing this tool, named OncoFinder, the experts used it in order to create raw pixel data, enabling us to generate datasets readable by different Machine Learning algorithms, to see if these images can be used to perform automatic classification. Even with a not perfect segmentation step, the generated data was good enough to prove that the available images can be processed, to find if the tumor is oncocytic, since the results we obtained in our experimentation, using different learning classifiers, showed that some of them can build trustworthy models with accuracies better than 90%, at the task of classifying segmented cell nuclei, as nucleus of oncocytic or normal cells. These results also show that it is possible to have a good prediction from a computer about thyroid tumor cases like the ones tested, to help experts in the task of determining which is the best treatment for their patients. To summarize, according to the goals that were set, the segmentation methods applied are not sufficient to successfully identify all cell nuclei, has explained in Section 3.1.1. However, even with a limited segmentation we succeed at finding the type of characteristics that need to be calculated, so that widely known learning classifiers can build a model and perform automatic classification over the segmented data. 5.2 Future Work The ultimate goal of this Dissertation, is to implement a totally automatized tool, ready to open, process and classify images of thyroid tumors with the minimal error probability possible. To fulfill it there is some work that has to be improved. In order to have a powerful and reliable segmentation of the high quality images, it is necessary to find a more effective set of techniques, external tool/library, or even study further the CognitionMaster framework [17]. With better segmentation, the need for certain interventions of the expert may become nearly or totally unnecessary, resulting in a much more automated work flow and user-friendly tool. OncoFinder, can also be improved in terms of usability. The feedback of the experts, of what they would change/add to the tool, is fundamental to improve the tool. The experience of the expert pathologists is also important to select data to train the learning classifiers, in the early stages of the tool usage, where the available manually classified data may be little or inexistent. Also, joining together with the pathologists, more research can be done on attributes to add to the identified contours of cell nuclei, that could improve the accuracy of the automatic classification. On the other hand, the size of the original images were to big for us to process right away, due to the machine limitations and the effort required from the pathologist to manually generate raw data to train classifiers, from a 40000 pixels of width and height image. However, in order to have a quantification of the total number of oncocytes of a certain case, it is necessary to handle the images in another way than the one we did, or 66 Conclusions and Future Work find a way to match pixels from one tile to the global original image, so that the structures caught by the division in tiles, are not discarded or counted twice. Also, when achieved very good segmentation results and less intervention is needed from the experts, the automatic analysis of the images will generate more and more data and it is necessary to link OncoFinder to a database that can securely store the raw pixel data, in order to be easily queried to extract treated and balanced datasets for posterior automatic classification. In the end, after integrating all this improvements it is required of OncoFinder to be able to handle all the necessary stages until it can return to the user an educated guess, of weather a tumor is oncocytic or not (75% of all the cells are oncocytic). The stages needed are: •Open and process high quality microscopic images. •Perform a high accuracy cell nuclei segmentation. •Generate training data (Early usage): –Manual classification of achieved contours by experts. –Calculation of the necessary attributes to distinguish each classified contour. –Generation of treated datasets, to train and test learning algorithms. •Test new tumor cases (Enough training data available): –Generation of datasets for testing with the models trained with the available data. •Display results: What kind of tumor and possible plots for easy access to statistics of the process. Achieving a totally automated tool is only possible if there is enough correctly classified contours by experts, to build a strong model capable of distinguish new data with acceptable accuracies. Thus it is necessary to have manual classification at the very beginning, in order to have available good training data. After accomplishing all these requirements, OncoFinder can be set available to experts from all over the world, to help them reach better and more accurate diagnosis. 67 Conclusions and Future Work 68 Glossary D DNA A long linear polymer found in the nucleus of a cell and formed from nucleotides and shaped like a double helix; associated with the transmission of genetic information. xv,1,6,70 E eosinophilic The tendency of a cell, tissue, or organism to be readily stained by the dye eosin. 2, 6,70 H haematoxylin Haematoxylin or hematoxylin is extracted from the heartwood of the logwood tree. When oxidized it forms haematein, a compound that forms strongly coloured complexes with certain metal ions, the most notable ones being Fe(III) and Al(III) salts. Metal-haematein complexes are used to stain cell nuclei prior to examination under a microscope. Haematoxylin and eosin together make up haematoxylin and eosin stain, one of the most commonly used stains in histology. It is a permanent stain as opposed to temporary stains (e.g. iodine solution in KI). 15,33,41,49,51,70 histology Histology is the study of the microscopic anatomy of cells and tissues of plants and animals. It is commonly performed by examining cells and tissues by sectioning and staining, followed by examination under a light or electron microscope. 70 M mitochondria Cell organelle, found in most eukaryotic cells, involved in energy conversion, metabolism and other cell processes. 1,6,28,31,65,70 69 OncoFinder User Guide segmented into only one contour, identified by the green arrow. Also, it shows small colored dots that represent missing contour errors that were already corrected. These corrections are done manually by left-clicking on the spots where a contour segmentation is lacking. Figure A.2: Tile with corrections necessary. To remove the wrongly segmented contours, it is enough to click with the right button of the mouse over it. This allows for the addition of new contours that are missing on the erroneous area. When they are added a new window appears, as shown in Figure A.3, in order to classify, right away, the new contour that is being added. If, by any chance, a contour is removed or added by mistake, the user can simply hit ”Ctrl+Z” to undo it, or access this functionality through the top menu in the ”Edit” separator. When all the necessary corrections are performed they can be and should be stored. To do so, it is only necessary to click on the right menu button named ”Save New Contours”. The next step is to classify the contours that were well segmented automatically. For this, a contour can be selected by left-clicking on it or, if the user wants to select several contours at the same time, by dragging the mouse over the region of desired contours, as displayed in Figure A.4. It is possible to classify contours in two different ways, by using the two different check boxes located in the right menu of the interface. The first one classify all the selected contours with the class selected at the first check box. The second way is to classify all th remainder contours (not selected) using the second check box. This is to provide the user with a fast way of classifying the remaining contours that will have the same class, since 76 OncoFinder User Guide Figure A.3: Addition of new contour and respective classification. Figure A.4: Group selection of contours. they are usually apart from each other rendering useless the group box selection, as well as making hard the manual selection of each one of them. 77 OncoFinder User Guide In the end, after all the necessary classifications and corrections are done the user just have to hit the button ”Save Data to File” to store the contour information that is used to create treated and balanced datasets, which are given to learning classifiers to build a model and achieve automatic classification. Figure A.5: Final state when corrections and classifications are done. 78