Multiresolution image segmentation [Elektronische Ressource] / von Mohammed Abdel-Megeed M. Salem

Salem Mohammed Abdel-Megeed M.

Sujets

• Informatik

Informations

• Publié par: humboldt-universitat_zu_berlin
• Publié le: 01 janvier 2008
• Nombre de lectures: 3
• Langue: English
• Poids de l'ouvrage: 5 Mo

Extrait

Multiresolution Image Segmentation
DISSERTATION
zur Erlangung des akademischen Grades
doctor rerum naturalium
(Dr. rer. nat.)
im Fach Informatik
eingereicht an der
Mathematisch-Naturwissenschaftlichen Fakultät II
Humboldt-Universität zu Berlin
von
Herr M.Sc. Mohammed Abdel-Megeed M. Salem
geboren am 23.02.1976 in Kairo, Ägypten
Präsident der Humboldt-Universität zu Berlin:
Prof. Dr. Dr. h.c. Christoph Markschies
Dekan der Mathematisch-Naturwissenschaftlichen Fakultät II:
Prof. Dr. Wolfgang Coy
Gutachter:
1. Prof. Dr.-Ing. Beate Meffert
2. Prof. Ulrich Rückert
3. Prof. Dr. Mohamed F. Tolba
eingereicht am: 26. August 2008
Tag der Verteidigung: 21. November 2008„Gedruckt mit Unterstützung
des Deutschen Akademischen Austauschdiensts“Abstract
More and more computer vision systems take part in the automation of var-
ious applications. The main task of such systems is to automate the process
of visual recognition and to extract relevant information from the images or
image sequences acquired or produced by such applications. One essential
and critical component in almost every computer vision system is image seg-
mentation. The quality of the segmentation determines to a great extent the
quality of the final results of the vision system.
New algorithms for image and video segmentation based on the multire-
solution analysis and the wavelet transform are proposed. The concept of
multiresolution is explained as existing independently of the wavelet trans-
form. The wavelet transform is extended to two and three dimensions to
allow image and video processing. The investigation of various Daubechies
wavelets shows that the Haar wavelet is the best suited wavelet for the pro-
posed algorithms and the investigated applications.
For still image segmentation the Resolution Mosaic Expectation Maxi-
mization (RM-EM) algorithm is proposed. The principle of this algorithm
is that the conventional EM algorithm is applied to a resolution mosaic of
the image as a kind of pre-processing. The resolution mosaic enables the
algorithm to employ the spatial correlation between the pixels. The level
of the local resolution depends on the information content of the individual
parts of the image. The use of various resolutions speeds up the processing
and improves the results.
New algorithms based on the 3D wavelet transform and the 3D wavelet
packet analysis are proposed for extracting moving objects from image se-
quences. The new algorithms have the advantage of considering the relevant
spatial as well as temporal information of the movement. Fast motions are
detected better in the first analysis levels whereas slow motions or motions
of big objects in the deeper layers. That is why a combination of different
levels gives the best results.Because of the low computational complexity of the wavelet transform an
FPGA hardware for the primary segmentation step was designed.
Actual applications are used to investigate and evaluate all algorithms:
the segmentation of magnetic resonance images of the human brain and the
detection of moving objects in image sequences of traffic scenes. All results
arecomparedwithothersobtainedfrompublishedwork. Thenewalgorithms
show robustness against noise and changing ambient conditions and gave
better segmentation results.
Keywords:
Image segmentation, Multiresolution, 3D wavelet transform, FPGA, Traffic
monitoring
ivZusammenfassung
Systeme der Computer Vision spielen in der Automatisierung vieler Pro-
zesse eine wichtige Rolle. Die wichtigste Aufgabe solcher Systeme ist die
Automatisierung des visuellen Erkennungsprozesses und die Extraktion der
relevanten Information aus Bildern oder Bildsequenzen. Eine wichtige Kom-
ponente dieser Systeme ist die Bildsegmentierung, denn sie bestimmt zu ei-
nem großen Teil die Qualität des Gesamtsystems.
Für die Segmentierung von Bildern und Bildsequenzen werden neue Al-
gorithmen vorgeschlagen. Mathematische Grundlage dieser Algorithmen sind
die Multiresolutionsanalyse und die Wavelet-Transformation. Das Konzept
der Multiresolution wird als eigenständig dargestellt, es existiert unabhän-
gig von der Wavelet-Transformation. Die Wavelet-Transformation wird zur
Verarbeitung von Bildern und Bildsequenzen zu einer 2D- bzw. 3D-Wavelet-
Transformationerweitert.DieUntersuchungverschiedenerDaubechies-Wave-
lets zeigt, dass das Haar-Wavelet für die vorgeschlagenen Algorithmen und
die ausgewählten Anwendungen am besten geeignet ist.
Für die Segmentierung von Bildern wird der Algorithmus Resolution Mo-
saic Expectation Maximization (RM-EM) vorgeschlagen. Das Prinzip dieses
Algorithmus ist, dass der konventionelle EM-Algorithmus auf ein vorverar-
beitetes Bild angewendet wird. Das Ergebnis der Vorverarbeitung sind un-
terschiedlich aufgelösten Teilbilder, das Auflösungsmosaik. Durch dieses Mo-
saik lassen sich räumliche Korrelationen zwischen den Pixeln ausnutzen. Der
Grad der Auflösung hängt vom Informationsgehalt der jeweiligen Teilbilder
ab. Die Verwendung unterschiedlicher Auflösungen beschleunigt die Verar-
beitung und verbessert die Ergebnisse.
Für die Extraktion von bewegten Objekten aus Bildsequenzen werden
neueAlgorithmenvorgeschlagen,dieaufder3D-Wavelet-Transformationund
auf der Analyse mit 3D-Wavelet-Packets beruhen. Die neuen Algorithmen
haben den Vorteil, dass sie sowohl die räumlichen als auch die zeitlichen Be-
wegungsinformationen berücksichtigen. Schnelle Bewegungen werden in den
ersten Analysestufen besser detektiert, langsame Bew oder die Be-
wegung großer Objekte dagegen erst in tieferen Stufen. Deshalb ergeben sich
die besten Ergebnisse durch Kombination verschiedener Stufen.WegendergeringenBerechnungskomplexitätderWavelet-Transformation
ist für den ersten Segmentierungsschritt Hardware auf der Basis von FPGA
entworfen worden.
Aktuelle Anwendungen werden genutzt, um die Algorithmen zu evaluie-
ren:dieSegmentierungvonMagnetresonanzbilderndesmenschlichenGehirns
und die Detektion von bewegten Objekten in Bildsequenzen von Verkehrs-
szenen. Die Ergebnisse werden mit denen anderer publizierter Arbeiten ver-
glichen. Die neuen Algorithmen sind robust gegenüber Rauschen und sich
ändernden Umgebungsbedingungen und führen zu besseren Segmentierungs-
ergebnissen.
Schlagwörter:
Bildsegmentierung, Mehrfachauflösung, 3D Wavelet-Transform, FPGA,
Verkehrsmonitoring
viDedication
To my mother, to my father, to Ahmed and Mostafa
viiContents
1 Introduction 1
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Thesis Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2 Image and Video Segmentation 9
2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Image Segmentation . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2.2 Pixel-based Approaches . . . . . . . . . . . . . . . . . 14
2.2.3 Region-basedhes . . . . . . . . . . . . . . . . 25
2.2.4 Template-based Approaches . . . . . . . . . . . . . . . 29
2.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 Video Segmentation . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.1 Principles . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.3.2 Frame Differencing . . . . . . . . . . . . . . . . . . . . 32
2.3.3 Optical Flow . . . . . . . . . . . . . . . . . . . . . . . 34
2.3.4 Background Estimation and Subtraction . . . . . . . . 36
2.3.5 Other Conventional Methods . . . . . . . . . . . . . . 41
2.3.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . 43
3 The Multiresolution Image Analysis 45
3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.2 Representation . . . . . . . . . . . . . . . . . 47
3.3 Pyramid Tools . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.1 Definition . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.3.2 Average-based Pyramid . . . . . . . . . . . . . . . . . . 50
3.3.3 Weighted Average-based Pyramid . . . . . . . . . . . . 50
3.3.4 Gaussian Pyramid . . . . . . . . . . . . . . . . . . . . 52
3.3.5 Laplacian . . . . . . . . . . . . . . . . . . . . 53
3.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
ix3.4.1 Multiresolution Microscopy . . . . . . . . . . . . . . . 55
3.4.2 Image Compression . . . . . . . . . . . . . . . . . . . . 55
3.4.3 Pattern Matching . . . . . . . . . . . . . . . . . . . . . 56
3.4.4 Image Segmentation . . . . . . . . . . . . . . . . . . . 57
4 The Discrete Wavelet Transform 61
4.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.2 Wavelet Transform . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.1 Foundations . . . . . . . . . . . . . . . . . . . . . . . . 64
4.2.2 Wavelet Analysis . . . . . . . . . . . . . . . . . . . . . 67
4.2.3 Wavelet Packet . . . . . . . . . . . . . . . . . . . . . . 73
4.2.4 Family of Daubechies Wavelets . . . . . . . . . . . . . 74
4.3 2D Discrete Wavelet Transform . . . . . . . . . . . . . . . . . 78
4.4 3D Wavelet T . . . . . . . . .