Parallel Max-Tree Construction in Polylogarithmic Expected Time

Teeninga, Paul (2024) Parallel Max-Tree Construction in Polylogarithmic Expected Time. Master's Thesis / Essay, Computing Science.

Preview	Text MasterthesisCopy.pdf Download (2MB) | Preview
	Text Paul Teeninga _ degree programme_ Computing Science.pdf Restricted to Registered users only Download (132kB)

Abstract

A max-tree is an image analysis tool and represents a hierarchy of connected components in the threshold sets of a (typically) grayscale image. We introduce a computationally efficient parallel algorithm for max-tree construction of images in O(n log(n)/p + log2(n) log(p)) expected time, for any input with length n, where n is the number of pixels and p is the number of processors. The algorithm iteratively bisects the graph representation of the image by value. A significant advantage is that the running time does not depend on bit depth, assuming constant-time comparisons. Current parallel algorithms have a linear lower bound on running time when no assumptions are made about bit depth. Results show up to 27.4× speedup (64 cores) and 44 megapixel/s throughput on worst case images with random floating-point numbers. The implementation is 3.9× to 9.5× faster than another parallel max-tree algorithm for high bit depth images.

Item Type:	Thesis (Master's Thesis / Essay)
Supervisor name:	Wilkinson, M.H.F. and Perez Parra, J.A.
Degree programme:	Computing Science
Thesis type:	Master's Thesis / Essay
Language:	Dutch
Date Deposited:	01 Jul 2024 09:19
Last Modified:	01 Jul 2024 09:19
URI:	https://fse.studenttheses.ub.rug.nl/id/eprint/32936

Actions (login required)

View Item