DLR-Logo -> http://www.dlr.de
DLR Portal Home | Impressum | Kontakt | English
Schriftgröße: [-] Text [+]

Pattern-oriented algorithmic complexity: towards compression-based information retrieval

Cerra, Daniele (2010) Pattern-oriented algorithmic complexity: towards compression-based information retrieval. Dissertation, German Aerospace Center (DLR).

PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader


The assimilation of informational content to computational complexity is more than 50 years old, but a way of exploiting practically this idea came only recently with the definition of compression-based similarity measures, which estimate the amount of shared information between any two objects. These techniques are effectively employed in applications on diverse data types with a universal and basically parameter-free approach; nevertheless, the difficulties in applying them to large datasets have been seldom addressed. This thesis proposes a novel similarity measure based on compression with dictionaries which is faster compared to known solutions, with no degradations in performance; this increases the applicability of these notions, allowing testing them on datasets with size up to 100 times larger than the ones previously analyzed in literature. These results have been achieved by studying how the classical coding theory in relation with data compression and the Kolmogorov notion of complexity allows decomposing the objects in an elementary source alphabet captured in a dictionary, regarded as a set of rules to generate a code having semantic meaning for the image structures: the extracted dictionaries describe the data regularities, and are compared to estimate the shared information between any two objects. This allows defining a content-based image retrieval system which requires minimum supervision on the user’s side, since it skips typical feature extraction steps, often parameter-dependant; this avoids relying on subjective assumptions which may bias the analysis, adopting instead a data-driven, parameter-free approach. Applications are presented where these methods are employed with no changes in settings to different kinds of images, from digital photographs to infrared and Earth Observation (EO) images, and to other data types, from texts and DNA genomes to seismic signals.

Dokumentart:Hochschulschrift (Dissertation)
Zusätzliche Informationen:The first part of the thesis is a summary in French of the thesis contents. The rest of the manuscript is in English.
Titel:Pattern-oriented algorithmic complexity: towards compression-based information retrieval
AutorenInstitution oder E-Mail-AdresseAutoren-ORCID
Datum:Mai 2010
In Open Access:Nein
In ISI Web of Science:Nein
Stichwörter:Kolmogorov complexity Similarity metric Data compression Information retrieval Remote sensing
Institution:German Aerospace Center (DLR)
Abteilung:Photogrammetry and Remote Sensing (MF-PB)
HGF - Forschungsbereich:Verkehr und Weltraum (alt)
HGF - Programm:Weltraum (alt)
HGF - Programmthema:W EO - Erdbeobachtung
DLR - Schwerpunkt:Weltraum
DLR - Forschungsgebiet:W EO - Erdbeobachtung
DLR - Teilgebiet (Projekt, Vorhaben):W - Vorhaben Photogrammetrie und Bildanalyse (alt)
Standort: Oberpfaffenhofen
Institute & Einrichtungen:Institut für Methodik der Fernerkundung > Photogrammetrie und Bildanalyse
Hinterlegt von: Cerra, Daniele
Hinterlegt am:04 Apr 2011 07:51
Letzte Änderung:12 Dez 2013 21:16

Nur für Mitarbeiter des Archivs: Kontrollseite des Eintrags

Hilfe & Kontakt
electronic library verwendet EPrints 3.3.12
Copyright © 2008-2013 Deutsches Zentrum für Luft- und Raumfahrt (DLR). Alle Rechte vorbehalten.