# Knowledge base: Warsaw University of Technology

Back

## Division trees and their application to comparison of digital images

### Bartłomiej Zieliński

#### Abstract

This dissertation is devoted to the study of digital image tree representation. The area that is focused on relates to ideas in which an input set of pixels is recursively decomposed into subsets. In effect, a structure called image division tree arises. In the thesis a generalized algorithm of division tree construction is introduced. Many known methods of image analysis constitute variants of the algorithm. The most essential achievements proposed in the thesis is a novel approach of creating this type of tree and the tree comparison method. Structure of the trees built according to the routine is fixed, while the parameters depend on the input image. The tree constitutes a limited representation of the underlying image. Therefore, the method of constructing the tree realizes a hash function. For every such function collisions might occure. However, for an overwhelming percentage of images which are dealt with in everyday practice, the following rule is satisfied. Namely, for similar images, similar trees are produced. On the other hand, unalike trees are created upon dissimilar images. Generally, the greater the dissimilarity between corresponding images is, the greater is the degree of the difference between the trees. Therefore, it is possible to compare the trees and express the dissimilarity between two images as the dissimilarity between the trees. One can handle different types of images with the approach-binary, grayscale, and color, the latter after performing a transformation into a scalar-value domain. What is more, the algorithm can be used to deal with objects isolated from images. The method is invariant to translation, scaling, and rotation and resistant to different image transformations. Thus, it is a general purpose solution for determining dissimilarity between images. Theoretical justification of the proposed approach is provided, as well as complexity analysis. Presented methods have also been examined in a series of experiments. To this end, sets of different test images-binary, color, and objects separated from images-have been created. The designed approach has been juxtaposed with selected reference algorithms. It has been the proposedmethod which has achieved the best results. Presented solution is shown to outperform rival algorithms. Experimental outcomes confirm its effectiveness and testify its applicability to the issue of image dissimilarity assessment.
Record ID
WUT6d325ffd477d46359b15661265e74d95
Diploma type
Doctor of Philosophy
Author
Bartłomiej Zieliński Bartłomiej Zieliński,, The Institute of Control and Industrial Electronics (FoEE/ICIE)Faculty of Electrical Engineering (FoEE)
Title in Polish
Drzewa podziału i ich zastosowanie do porównywania obrazów cyfrowych
Title in English
Division trees and their application to comparison of digital images
Language
(pl) Polish
Certifying Unit
Faculty of Electrical Engineering (FoEE)
Discipline
information science / (technology domain) / (technological sciences)
Status
Finished
Start date
10-04-2013
Defense Date
26-02-2014
Title date
19-03-2014
Supervisor
Internal reviewers
External reviewers
Jacek Chmielewski Jacek Chmielewski,, External affiliation of publication: Warsaw University of Life Science
Pages
116
Keywords in English
image recognition, image tree representation, image comparison, image dissimilarity measure
Abstract in English
This dissertation is devoted to the study of digital image tree representation. The area that is focused on relates to ideas in which an input set of pixels is recursively decomposed into subsets. In effect, a structure called image division tree arises. In the thesis a generalized algorithm of division tree construction is introduced. Many known methods of image analysis constitute variants of the algorithm. The most essential achievements proposed in the thesis is a novel approach of creating this type of tree and the tree comparison method. Structure of the trees built according to the routine is fixed, while the parameters depend on the input image. The tree constitutes a limited representation of the underlying image. Therefore, the method of constructing the tree realizes a hash function. For every such function collisions might occure. However, for an overwhelming percentage of images which are dealt with in everyday practice, the following rule is satisfied. Namely, for similar images, similar trees are produced. On the other hand, unalike trees are created upon dissimilar images. Generally, the greater the dissimilarity between corresponding images is, the greater is the degree of the difference between the trees. Therefore, it is possible to compare the trees and express the dissimilarity between two images as the dissimilarity between the trees. One can handle different types of images with the approach-binary, grayscale, and color, the latter after performing a transformation into a scalar-value domain. What is more, the algorithm can be used to deal with objects isolated from images. The method is invariant to translation, scaling, and rotation and resistant to different image transformations. Thus, it is a general purpose solution for determining dissimilarity between images. Theoretical justification of the proposed approach is provided, as well as complexity analysis. Presented methods have also been examined in a series of experiments. To this end, sets of different test images-binary, color, and objects separated from images-have been created. The designed approach has been juxtaposed with selected reference algorithms. It has been the proposedmethod which has achieved the best results. Presented solution is shown to outperform rival algorithms. Experimental outcomes confirm its effectiveness and testify its applicability to the issue of image dissimilarity assessment.
PKT classification
410000, 412700
KBN classification
28
Thesis file
Request a WCAG compliant version

Uniform Resource Identifier
https://repo.pw.edu.pl/info/phd/WUT6d325ffd477d46359b15661265e74d95/
URN
urn:pw-repo:WUT6d325ffd477d46359b15661265e74d95

Confirmation
Are you sure?