- Comparison of Automated Feature Extraction Methods for Image Based Screening of Cancer Cells
Student: Michael Brennan
Supervisor: Mats Gustafsson, Dept. of Medical Sciences
Reviewer: Ewert Bengtsson
Publisher: UPTEC F 11 068
Abstract: Image based screening is an important tool used in research for development of drugs to fight cancer. Phase contrast video microscopy - a cheap and fast image screening technology - enables a rapid generation of large amounts of data, which requires a fast method for analysis of this data. As videos contain a lot of redundant information, the difficulty is to extract usable information in form of features from the videos, by compressing available information, or filter out redundant data. In this thesis, the problem is approached in an experimental fashion where three different methods have been devised and tested, to evaluate different ways to automatically extract features from phase contrast microscopy videos containing cultured cancer cells. The three methods considered are, in order: an adaptive linear filter, an on-line clustering algorithm, and an artificial neural network. The ambition is that outputs from these methods can create time-varying histograms of features that can be used in further mathematical modeling of cell dynamics. It is concluded that, while the results of the first method is not impressive and can be dismissed, the remaining two are more promising and are able to successfully extract features automatically and aggregate them into time-varying histograms.
- Efficient Volume Rendering on the Face Centered and Body Centered Cubic Grids
Student: Max Morén
Supervisor: Elisabeth Linnér
Reviewer: Robin Strand
Publisher: UPTEC IT 12 013
Abstract: In volumetric visualization, the body centered cubic grid (BCC) and its reciprocal, the face centered cubic grid (FCC), are despite their good sampling properties not well off regarding available rendering software and tools.
Described in this thesis is the development of an extension for the volume rendering engine Voreen, implementing two recently presented GPU accelerated reconstruction algorithms for these grids, along with a simple nearest neighbor method. These reconstruction methods replace the trilinear reconstruction method used for data stored in a Cartesian cubic grid (CC). The goal is for the produced software to be useful for efficiently visualizing results from experiments with the BCC and FCC grids and thus help make such data easier to observe.
The performance and rendering quality of the new raycasters is measured and compared to Voreen's existing Cartesian cubic ray caster. The experimental results show that the raycasters can render data in the BCC and FCC format at interactive frame rates while maintaining comparable visual quality.
- Counting Sertoli Cells in Thin Testicular Tissue
Student: Abdolrahim Kadkhodamohammadi
Supervisor: Azadeh Fakhrzadeh
Reviewer: Cris Luengo
Publisher: UPTEC IT 12 017
Abstract: This master thesis develops a novel system to model the tubular structure in thin sections of testicular tissue and count the Sertoli cells. A three-phase method is proposed to model the tubular structure in microscopic images of the tissue, the model is deployed to detect the cells. In the first phase, the germ-mass, which represents the inside layer of tubules, are detected. All cells are detected by radial symmetry transform and then the graph cut algorithm is used to separate the germ cells. Each region covered by a compact set of germ cells is considered as the germ-mass. In the second phase, all bright areas in the image are detected and used to adjust the germ-mass regions. In the last phase, all edges that are line-like are identified and straight lines are fitted to the edges. The lines are later connected to compensate for the broken parts of the tubules' boundaries.
The closest cells to the germ-mass are chosen as the Sertoli cell candidates. The approximate boundary of tubules and the angle between the candidate cells are used to detect the Sertoli cells. Our experimental results show that our system is able to detect the tubule and the Sertoli cells with reasonable accuracy. If the method can not find enough edges to approximate the tubule's boundary, detecting Sertoli cells is complicated; the system can report those situations to the experts.
Since we use the symmetry attribute of the cells to detect them, the method is quite robust against noise, artifacts, and non-uniform illumination. The method is able to capture all tubules, even tubules that do not have any bright region in the middle (lumen). To the best of my knowledge, no one has proposed a method to model tubular structure without lumen. The border approximation method can work well even for tubules that are partially in the image. It should be mentioned that the proposed method could be applied to model any tubular structure with one or more cells types.
- Requirements and Needs for 3D Visualizations
Student: Henrik Jacobsson
Supervisor: Kent Johansson, Scania AB, Södertälje
Reviewer: Anders Hast
Publisher: UPTEC IT 12 022
Abstract: Product development within the automotive industry is progressing towards using more 3D models and less conventional 2D drawings. When development is done in a parallel cooperative way, demands for availability of relevant and current data are high. Engineering design in a 3D environment requires visualization that incorporates wide spread sharing and simple access, which after implementation would support demands for shorter lead times and reduced development costs.
In this master thesis a focus to compile and present requirements for 3D visualizations, from different groups within Scania, has been at hand. These requirements will be featured in both text and with a graphical form conceptual.
Moreover has the framing of questions within the area of information sharing been treated in respect to 3D visualizations and their impact on lead times for iterations for the product development process.
Spreading of information could be made easier if more people would gain access to 3D visualizations. According to our results from conducted interviews would problems be detected earlier and in that way shorter lead times would be achieved.
Knowledge, ideas and experience have been collected partly from interviews with employees at Scania (mostly R&D, but also from purchase, production and aftermarket), and partly from reference visits at Volvo Cars, White architects and SAAB Aeronautics. The reference visits have been a valuable source with their experience from implementing solutions for 3D visualizations.
Conclusions that can be drawn from this master thesis are among others the importance of using one common and updated database. Furthermore it can be said that spreading and using 3D visualizations could imply shorter lead times.
- Implementation of a Semi-automatic Tool for Analysis of TEM Images of Kidney Samples
Student: Jing Liu
Supervisor: Gustaf Kylberg
Reviewer: Ida-Maria Sintorn
Publisher: UPTEC IT 12 033
Abstract: Glomerular disease is a cause for chronic kidney disease and it damages the function of the kidneys. One symptom of glomerular disease is proteinuria, which means that large amounts of protein are emerged in the urine. To be more objective,transmission electron microscopy (TEM) imaging of tissue biopsies of kidney are used when measuring proteinuria. Foot process effacement (FPE), which is defined as less than1 ``slit'' (gap)/micrometer at the glomerular basement membrane (GBM). Measuring FPE is one way to detect proteinuria using kidney TEM images, this technique is a time-consuming task and used to be measured manually by an expert.
This master thesis project aims at developing a semi-automatic way to detect the FPE patients as well as a graphic user interface (GUI) to make the methods and results easily accessible for the user.
To compute the slits/micrometer for each image, the GBM needs to be segmented from the background. The proposed work flow combines various filters and mathematical morphology to obtain the outer contour of the GBM. The outer contour is then smoothed, and unwanted parts are removed based on distance information and angle differences between points on the contour. The length is then computed by weighted chain code counts. At last, an iterative algorithm is used to locate the positions of the "slits" using both gradient and binary information of the original images.
If necessary, the result from length measurement and "slits" counting can be manually corrected by the user. A tool for manual measurement is also provided as an option. In this case, the user can add anchor points on the outer contour of the GBM and then the length is automatically measured and "slit" locations are detected. For very difficult images, the users can also mark all "slits" locations by hand.
To evaluate the performance and the accuracy, data from five patients are tested,for each patient six images are available. The images are 2048 by 2048 gray-scale indexed 8 bit images and the scale is 0.008 micrometer/pixel. The one FPE patient in the dataset is successfully distinguished.
- Automatic Identification and Cropping of Rectangular Objects in Digital Images
Student: Tomas Toss
Supervisor: Henrik Johansson, National Library of Sweden, Stockholm
Reviewer: Anders Brun
Publisher: UPTEC IT 12 040
Abstract: Today, digital images are commonly used to preserve and present analogue media. To minimize the need for digital storage space, it is important that the object covers as large part of the image as possible. This paper presents a robust methodology, based on common edge and line detection techniques, to automatically identify rectangular objects in digital images. The methodology is tailored to identify posters, photographs and books digitized at the National Library of Sweden (the KB). The methodology has been implemented as a part of DocCrop, a computer program written in Java to automatically identify and crop documents in digital images. With the aid of the developed tool, the KB hopes to decrease the time and manual labour required to crop their digital images.
Three multi-paged documents digitized at the KB have been used to evaluate the tool's performance. Each document features different characteristics. The overall identification results, as well as an in-depth analysis of the different methodology stages, are presented in this paper. In average, the developed software identified 98% of the digitized document pages successfully. The software's identification success rate never went below 95% for any of the three documents. The robustness and execution speed of the methodology suggests that the methodology can be a compelling alternative to the manual identification used at the KB today.
- 3D Co-occurrence Matrix Based Texture Analysis Applied to Cervical Cancer Screening
Student: Meng Liang
Supervisor: Patrik Malm
Reviewer: Ewert Bengtsson
Publisher: UPTEC IT 12 041
Abstract: Cervical cancer is the second most common cancer in women worldwide, approximately 471,000 new cases are diagnosed each year. In 2005, there were about 500,000 cases of cervical cancer and 260,000 cases caused death in worldwide. Cervical cancer starts as a precancerous condition, however the changes of precancerous are hardly detected by the naked eyes, special test such as Papanicolaou test are used to spot the conditions. These are time consuming to inspect visually. In the last 50 years there have been many projects to develop automated computer image analysis system for screening.
One of the most important changes in a cell when it becomes precancerous is a change in chromatin texture. The field of nuclear texture analysis gives information about the spatial arrangement of pixel gray levels in a digitized microscopic nuclei image. A well known method for quantifying textures in digital images is the gray level co-occurrence matrix(GLCM). This method tries to quantify specific pairwise gray level occurrence at specific relative positions. In this project, firstly we have developed and tested three image normalization methods : gradient based intensity normalization, histogram equalization and standardizing normal random variables; secondly we have developed 2D gray level co-occurrence matrix calculation and 3D gray level co-occurrence matrix calculation, thirdly compared Haralick features with adaptive feature vectors from class distance and class difference matrices (adaptive texture feature) based on the 2D gray level co-occurrence matrix; compared the Haralick features with adaptive feature based on the 3D gray level co-occurrence matrix. Our result shows that neither of the 3D results yields a significant improvement from 2D results.
- Adaptive Binarization of 17th Century Printed Text
Student: Carl Carenwall
Supervisor: Fredrik Wahlberg
Reviewer: Anders Brun
Publisher: UPTEC IT 12 055
Abstract: This work focused on implementing and evaluating an adaptive water flow model for binarization of historical documents, as presented by Valizadeh and Ehsanollah in an article published in early 2012.
While the original method sought an optimal result for all kinds of degraded documents, both on hand written and printed, the work presented here only needed to be concerned with printed documents. This was due to being focused on specific documents scanned by the Uppsala university library.
The method itself consists of several steps, including a couple that uses other methods for binarization to achieve a good result.
While the implementation appears to have been largely successful in replicating the results of the original method, it is very possible that some minor tweaking could result in further improvements. To replicate the results, however, a new parameter had to be inserted in the method. Regardless if this was because of some mistake, or if the sample data used by Valizadeh and Ehsanollah simply differs from the one used here, this may be worth looking more at. In the end of this report are comparisons with a couple of common and state-of-the-art methods for binarization, and this method appear to perform favourably in most cases.
- Stitching of X-ray Images
Student: Krishna Paudel
Supervisor: Felix Rutscher, Protec GmbH & Co, Oberstenfeld, Germany
Reviewer: Cris Luengo
Publisher: UPTEC IT 12 057
Abstract: Image processing and analysis algorithms are widely used in medical systems to analyze medical images to help diagnose the disease of a patient. This thesis covers one of the demanding problems of a medical system: Stitching of X-ray Images. The flat panel of an X-ray system cannot cover all part of a body, so image stitching is incorporated in the medical system to combine two or more X-ray images and get a single high resolution image. The output of this thesis work is to develop a real-time and user interactive stitching application which works for all X-ray images with different intensity and orientation.
The stitching of X-ray images is carried out by employing two basic steps: registration and blending. The classical registration methods search for all the pixels to get the best registration. These methods are slow and cannot perform well for high resolution X-ray images. The feature based registration methods are faster and always gives the best registration. This thesis evaluates three popular feature based registration methods: HARRIS, SIFT and SURF. The exhaustive nearest neighborhood method has been modified to get faster matching of key points.
The overlapping areas of the composite image are blended to remove the seams and discontinuities. This thesis evaluates some faster blending techniques and incorporates an advanced blending method using blending masks to blend complexly aligned images.
- Online Learning of Multi-class Support Vector Machines
Student: Xuan Tuan Trinh
Supervisor: Christian Igel, the Image Group, University of Copenhagen, Denmark
Reviewer: Robin Strand
Publisher: UPTEC IT 12 061
Abstract: Support Vector Machines (SVMs) are state-of-the-art learning algorithms for classification problems due to their strong theoretical foundation and their good performance in practice. However, their extension from two-class to multi-class classification problems is not straightforward. While some approaches solve a series of binary problems, other, theoretically more appealing methods, solve one single optimization problem. Training SVMs amounts to solving a convex quadratic optimization problem. But even with a carefully tailored quadratic program solver, training all-in-one multi-class SVMs takes a long time for large scale datasets. We first consider the problem of training the multi-class SVM proposed by Lee, Lin and Wahba (LLW), which is the first Fisher consistent multi-class SVM that has been proposed in the literature, and has recently been shown to exhibit good generalization performance on benchmark problems. Inspired by previous work on online optimization of binary and multi-class SVMs, a fast approximative online solver for the LLW SVM is derived. It makes use of recent developments for efficiently solving all-in-one multi-class SVMs without bias. In particular, it uses working sets of size two instead of following the paradigm of sequential minimal optimization. After successful implementation of the online LLW SVM solver, it is extended to also support the popular multi-class SVM formulation by Crammer and Singer. This is done using a recently established unified framework for a larger class of all-in-one multi-class SVMs. This makes it very easy in the future to adapt the novel online solver to even more formulations of multi-class SVMs. The results suggest that online solvers may provide for a robust and well-performing way of obtaining an approximative solution to the full problem, such that it constitutes a good trade-off between optimization time and reaching a sufficiently high dual value.
- Seed Surface Measurements From Multiple Views: Using Image Analysis
Student: Prabhu Mani
Supervisor: Jaan Luup, Maxx Automation AB, Uppsala
Reviewer: Cris Luengo
Publisher: UPTEC IT 12 071
Abstract: Analyzing the properties of seed helps in determining the quality of seeds. Seeds like wheat, barley, rye, oats and triticale are considered for the quality analysis. It is important that in a sample of seeds (for instance wheat) there should be no adulteration. To find the quality of seeds, samples have to be examined to find the percentage of damaged seeds and foreign seeds among good seeds. To accomplish this task each seed should to be examined manually to identify if a seed is good, which is a time consuming task. A machine is built to automate this task. It is capable of separating seeds individually and makes it slide one after the other quickly. The sliding seeds images are captured by a camera for analysis. The setup uses mirrors in such a way that image has 3 different views of a seed covering the entire surface of a seed.
From this new type of seed images, image processing techniques are developed to identify different properties of a seed like, height, width etc. A mathematical 3-D model for a seed is developed and each seed image is converted to this model to estimate the volume of the seed. From the volume data seeds weight is estimated. Also different forms of seed damages such as broken seeds, husk damages are analyzed and estimated. However in finding husk damage, a general solution for all the seeds could not be devised as distinct features of husk and seed is not common in all the seeds. But different approaches for finding few common patterns of husk damages are discussed. All the implementations are discussed in detail and the test results of implementations are compared with manually calculated data.
- Stabilization of Handheld Firearms Using Image Analysis
Student: Alexander Lindstedt
Supervisor: Göran Backlund, Combitech, Linköping
Reviewer: Cris Luengo
Publisher: UPTEC F 12 010
Abstract: When firing a handheld weapon, the shooter tries to aim at the point where he wants the bullet to hit. However, due to imperfections in the human body, this can be quite hard. The weapon moves relative to the target and the shooter has to use precise timing to fire the shot exactly when the weapon points to the intended target position. This can be very hard, especially when shooting at long range using a magnifying rifle scope.
In this thesis, a solution to this problem using image analysis is described and tested. Using a digital video camera and software, the system helps the shooter to fire at the appropriate time. The system is designed to operate in real-time conditions on a PC.
The tests carried out have shown that the solution is promising and helps to achieve better accuracy. However it needs to be optimized to run smoothly on a smaller scale embedded system.
- Implementing the Circularly Polarized Light Method for Determining Wall Thickness of Cellulosic Fibres
Student: Marcus Edvinsson
Supervisor: Thomas Storsjö
Reviewer: Cris Luengo
Publisher: UPTEC F 12 014
Abstract: The wall thickness of pulp fibers plays a major role in the paper industry, but it is currently not possible to measure this property without manual laboratory work. In 2007, researcher Ho Fan Jang patented a technique to automatically measure fiber wall thickness, combining the unique optical properties of pulp fibers with image analysis. In short, the method creates images through the use of an optical system resulting in color values which demonstrate the retardation of a particular wave length instead of the intensity. A device based on this patent has since been developed by Eurocon Analyzer. This thesis investigates the software aspects of this technique, using sample images generated by the Eurocon Analyzer prototype.
The software developed in this thesis has been subdivided into three groups for independent consideration. First being the problem of solving wall thickness for colors in the images. Secondly, the image analysis process of identifying fibers and good points for measuring them. Lastly, it is investigated how statistical analysis can be applied to improve results and derive other useful properties such as fiber coarseness.
With the use of this technique there are several problems which need to be overcome. One such problem is that it may be difficult to disambiguate the colors produced by fibers of different thickness. This complication may be reduced by using image analysis and statistical analysis. Another challenge can be that theoretical values often differ greatly from the observed values which makes the computational aspect of the method problematic. The results of this thesis show that the effects of these problems can be greatly reduced and that the method offers promising results.
The results clearly distinguish between and show the expected characteristics of different pulp samples, but more qualitative reference measurements are needed in order to draw conclusions on the correctness of the results.
- Fibre Network Generation and Analysis: Method for simulation of inhomogeneous static fibre networks
Student: Abdellah Mesquine
Supervisor: Tomas Nyberg, Dept. of Engineering Sciences
Reviewer: Anders Brun
Publisher: UPTEC F 12016
Abstract: In paper optics, advanced modeling of the interaction of light with complex structures are required for optimization of the optical properties of paper. Monte Carlo simulation routines have been developed in an Open Source project, PaperOpt, in order to simulate light scattering in paper. The goal of the project is to make the tool more modular and extensible so that researchers within the paper optics field can make their own contributions to the model. This thesis is a part of Open PaperOpt project and its goal is to generate paper structures that resemble real paper sheets. This Master's thesis describes the design and implementation of a model for generation of virtual fiber networks with controlled fiber distribution within the papersheet. A C++ written program that generates a fiber network according to a fibermass distribution table has been developed. A qualitative and quantitative comparison between simulated paper structures and real paper obtained from beta-scan measurements is also described.
- Interactive Visualization of Financial Data: Development of a Visual Data Mining Tool
Student: Joakim Saltin
Supervisor: Patrik Johansson, SkySparc, Stockholm
Reviewer: Filip Malmberg
Publisher: UPTEC F 12 023
Abstract: In this project, a prototype visual data mining tool was developed, allowing users to interactively investigate large multi-dimensional datasets visually (using 2D visualization techniques) using so called drill-down, roll-up and slicing operations. The project included all steps of the development, from writing specifications and designing the program to implementing and evaluating it.
Using ideas from data warehousing, custom methods for storing pre-computed aggregations of data (commonly referred to as materialized views) and retrieving data from these were developed and implemented in order to achieve higher performance on large datasets. View materialization enables the program to easily fetch or calculate a view using other views, something which can yield significant performance gains if view sizes are much smaller than the underlying raw dataset. The choice of which views to materialize was done in an automated manner using a well-known algorithm - the greedy algorithm for view materialization - which selects the fraction of all possible views that is likely (but not guaranteed) to yield the best performance gain. The use of materialized views was shown to have good potential to increase performance for large datasets, with an average speedup (compared to on-the-fly queries) between 20 and 70 for a test dataset containing 500 000 rows.
The end result was a program combining flexibility with good performance, which was also reflected by good scores in a user-acceptance test, with participants from the company where this project was carried out.
- Eigen-birds: Exploring Avian Morphospace with Image Analytic Tools
Student: Mikael Thuné
Supervisor: Anders Brun; Jochen Wolf, Dept. of Ecology and Genetics
Reviewer: Ida-Maria Sintorn
Publisher: UPTEC F 12024
Abstract: The plumage colour and patterns of birds have interested biologists for a long time. Why are some bird species all black while others have a multitude of colours? Does it have anything to do with sexual selection, predator avoidance or social signalling? Many questions such as these have been asked and as many hypotheses about the functional role of the plumage have been formed. The problem, however, has been to prove any of these. To test these hypotheses you need to analyse the bird plumages and today such analyses are still rather subjective. Meaning the results could vary depending on the individual performing the analysis. Another problem that stems from this subjectiveness is that it is difficult to make quantitative measurements of the plumage colours. Quantitative measurements would be very useful since they could be related to other statistical data like speciation rates, sexual selection and ecological data. This thesis aims to assist biologists with the analysis and measurement of bird plumages by developing a MATLAB toolbox for this purpose. The result is a well structured and user friendly toolbox that contains functions for segmenting, resizing, filtering and warping, all used to prepare the images for analysis. It also contains functions for the actual analysis such as basic statistical measurements, principal component analysis and eigenvector projection.
- Detection of Free-lying Epithelial Cells by Low Resolution Image
Analysis of Cell Samples - The First Step in an Automated System for Early
Detection of Cervical Cancer
Student: Marine Astruc
Supervisor: Patrik Malm
Reviewer: Ewert Bengtsson
Publisher: Ecole Centrale Nantes, France
Abstract: Automated cervical cancer screening systems require high resolution analysis of a large number of epithelial cells, involving complex algorithms, mainly analysing the shape and texture of cell nuclei. This can be a very time consuming process. An initial selection of relevant fields-of-view in low resolution images could limit the number of fields to be further analysed at a high resolution. In particular, the detection of cell clusters is of interest for nuclei segmentation improvement, and for diagnostic purpose, malignant and endometrial cells being more prone to stick together in clusters than other cells. In this study, methods aiming at evaluating the quality of fields-of-view in bright field microscope images of cervical cells are proposed. The approach consists in the construction of neighbourhood graphs using the nuclei as the set of vertices. Transformations are then applied on such graphs in order to highlight the main structures in the image. The methods result in the delineation of regions with varying cell density and the identification of cell clusters. Clustering methods are evaluated using a dataset of manually delineated clusters and compared to a related work.
- Stochastic Watershed: A Comparison of Different Seeding Methods
Students: Kenneth Gustavsson, Karl Bengtsson Bernander
Supervisor: Bettina Selig
Reviewer: Martin Sjödin, Dept. of Engineering Sciences, UU
Publisher: UPTEC TVE 12024
Abstract: We study modifications to the novel stochastic watershed method for segmentation of digital images. This is a stochastic version of the original watershed method which is repeatedly realized in order to create a probability density function for the segmentation. The study is primarily done on synthetic images with both same-sized regions and differently sized regions, and at the end we apply our methods on two endothelial cell images of the human cornea. We find that, for same-sized regions, the seeds should be placed in a spaced grid instead of a random uniform distribution in order to yield a more accurate segmentation. When images with differently sized regions are being segmented, the seeds should be placed dependent on the gradient, and by also adding uniform or gaussian noise to the image in every iteration a satisfactory result is obtained.
Comment: Bachelor thesis