Technical reports 2003

A-2003-1 J. Mykkänen, J. Tohka, J. Luoma and U. Ruotsalainen, Automatic extraction of brain surface and mid-sagittal from PET images applying deformable models. May 2003.
Abstract. In this study, we propose new methods for automatic extraction of the brain surface and the mid-sagittal plane from functional positron emission tomography (PET) images.  Designing general methods for these segmentation tasks is challenging because the spatial distribution of intensity values in a PET image depends on the applied radiopharmaceutical and the contrast to noise ratio in a PET image is typically low.  We extracted the brain surface with a deformable model which is based on global minimization of its energy. The global optimization allows reliable automation of the extraction task.  Based on the extracted brain surface, the mid-sagittal plane was determined.  Since we did not apply information from the corresponding anatomical images, the extracted brain surface and mid-sagittal plane could be used also when registering PET images to anatomical images.  Furthermore, we applied the deformable model for extraction of the coarse cortical structure based on the tracer uptake from FDG-PET brain images. We tested the methods with the image of the Hoffman brain phantom (FDG) and images from brain studies with FDG (17 images) and 11 C-Raclopride tracers (4 images). The brain surface, the mid-sagittal plane, and the cortical structure were reliably delineated from all the images without any user guidance. The proposed segmentation methods provide a promising direction for automatic processing and analysis of PET brain images.
pdf-file

A-2003-2 Jouni Mykkänen, Delineation of brain structures from functional positron emission tomography images. July 2003.
Abstract. Positron emission tomography (PET) imaging is a unique method for studying biochemical processes involved in living species. It provides quantitative information about the processes at a cellular level, which is needed, for example in diagnosis of a disease and the development of new drugs. Quantitative information can be determined from PET images by extracting volumes of interest. In order to collect large databases of the functional data derived from PET, new automatic methods for image analysis are required. The delineation of PET images is a challenging task due to noise and individual data contents in PET images. It has not gained attention that it deserves.
This study proposes a new lossless image compression method and novel approaches to delineate brain surfaces from PET brain images. First, a low complexity lossless image compression method was developed for noisy PET brain images. Next, a user-guided software using intensity values of image was developed and utilized to determine quantitative values from the PET brain images. Next, a two-dimensional deformable model and the corresponding anatomical references from MR images were applied to delineate cortical surfaces from PET brain images. Deformable models are advanced delineation methods entailing geometric shape and evolution rules, which connect the model to data providing its adaptation to the salient features in an image. This method was able to improve the registration alignment and correct differences between the anatomical and functional structures. However, proper segmentation of volumetric PET images required a new three-dimensional deformable surface model which was developed in close collaboration with this study. It uses a global optimization to avoid the initialization problem common with deformable models. The new method was applied to extract surfaces from images in PET brain studies with $^{18}$FDG and $^{11}$C-Raclopride radiopharmaceuticals. The delineation procedure was fully automatic, repeatable and considerably faster than the entirely manual delineation methods applied with PET images. Consequently, the coarse cortical structures for the hemispheres were determined in an iterative way and no anatomical references or user interactions were required in the process.
This study contributes novel approaches for semi-automatic and fully automatic surface delineation from PET brain images. In addition, an image compression procedure for PET brain images is proposed. These provide new possibilities for developing fully automatic applications for neurological image analysis and databases.
Key words and phrases: brain surface extraction, volume of interest, deformable model, three-dimensional image analysis, mid-sagittal plane, segmentation, compression.
Ph.D. Dissertation.
A-2003-2 has appeared electronically as Acta Electronica Universitatis Tamperensis, vol. 271.

A-2003-3 Timo Poranen, Apptopinv - User's guide. September 2003.
Abstract. The maximum planar subgraph, maximum outerplanar subgraph, the thickness and outerthickness of a graph are all NP-complete optimization problems. Apptopinv is a program that contains different heuristic algorithms for these four problems: algorithms based on Hopcroft-Tarjan planarity testing algorithm, the spanning-tree heuristic and various algorithms based on the cactus-tree heuristic. Apptopinv contains also a simulated annealing algorithm that can be used to improve the solutions obtained from other heuristics. Most of the heuristics have also a greedy version.
We have implemented graph generators for complete graphs, complete k-partite graphs, complete hypercubes, random graphs, random maximum planar and outerplanar graphs and random regular graphs. Apptopinv supports three different graph file formats.
Apptopinv is written in C++ programming language for Linux-platform and GCC 2.95.3 compiler. To compile the program, a commercial LEDA algorithm library (version 4.3 or newer) is needed.
pdf-file

A-2003-4 Heikki Hyyrö, Practical Methods for Approximate String Matching. December 2003.
Abstract. Given a pattern string and a text, the task of approximate string matching is to find all locations in the text that are similar to the pattern. This type of search may be done for example in applications of spelling error correction or bioinformatics. Typically edit distance is used as the measure of similarity (or distance) between two strings. In this thesis we concentrate on unit-cost edit distance that defines the distance beween two strings as the minimum number of edit operations that are needed in transforming one of the strings into the other. More specifically, we discuss the Levenshtein and the Damerau edit distances.
Approximate string matching algorithms can be divided into off-line and on-line algorithms depending on whether they may or may not, respectively, preprocess the text. In this thesis we propose practical algorithms for both types of approximate string matching as well as for computing edit distance.
Our main contributions are a new variant of the bit-parallel approximate string matching algorithm of Myers, a method that makes it easy to modify many existing Levenshtein edit distance algorithms into using the Damerau edit distance, a bit-parallel algorithm for computing edit distance, a more error tolerant version of the ABNDM algorithm, a two-phase filtering scheme, a tuned indexed approximate string matching method for genome searching, and an improved and extended version of the hybrid index of Navarro and Baeza-Yates.
To evaluate their practicality, we compare most of the proposed methods with previously existing algorithms. The test results support the claim of the title of this thesis that our proposed algorithms work well in practice.
Ph.D. Dissertation.
A-2003-4 has appeared electronically in Acta Electronica Universitatis Tamperensis, vol. 308.

A-2003-5 Poika Isokoski and Roope Raisamo, Evaluation of a Multi-Device Extension of Quikwriting. December 2003.
Abstract. Several new text entry methods for mobile computers have been proposed recently. Many of these have not been tested to reveal whether they in fact perform as advertised. We report a longitudinal laboratory study on the use of a system known as Quikwriting. We have extended Quikwriting so that a stylus, a joystick, or a keyboard can be used as the input device. Twelve participants used the stylus and joystick modes of input in twenty 15-minute sessions. In the end their performance with the keyboard was tested to see if Quikwriting skill transfers to new devices easily. Quikwriting was found to be functional with all of the tested devices, but laborious to learn. The final text entry rates were 16.1 wpm with the stylus, 13.2 wpm with the joystick, and 6.1 wpm with the keyboard.
A-2003-5 is available as paper copy only.

1992-2001
2002
2004
2005
2006
2007
2008
2009
To the upper level