Computing convexity properties of images on a pyramid computer
dc.contributor.author | Miller, Russ | en_US |
dc.contributor.author | Stout, Quentin F. | en_US |
dc.date.accessioned | 2006-09-08T19:09:48Z | |
dc.date.available | 2006-09-08T19:09:48Z | |
dc.date.issued | 1991-12 | en_US |
dc.identifier.citation | Miller, Russ; Stout, Quentin F.; (1991). "Computing convexity properties of images on a pyramid computer." Algorithmica 6(1): 658-684. <http://hdl.handle.net/2027.42/41351> | en_US |
dc.identifier.issn | 1432-0541 | en_US |
dc.identifier.issn | 0178-4617 | en_US |
dc.identifier.uri | https://hdl.handle.net/2027.42/41351 | |
dc.description.abstract | We present efficient parallel algorithms for using a pyramid computer to determine convexity properties of digitized black/white pictures and labeled figures. Algorithms are presented for deciding convexity, identifying extreme points of convex hulls, and using extreme points in a variety of fashions. For a pyramid computer with a base of n simple processing elements arranged in an n 1/2 × n 1/2 square, the running times of the algorithms range from Θ(log n ) to find the extreme points of a convex figure in a digitized picture, to Θ( n 1/6 ) to find the diameter of a labeled figure, Θ( n 1/4 log n ) to find the extreme points of every figure in a digitized picture, to Θ( n 1/2 ) to find the extreme points of every labeled set of processing elements. Our results show that the pyramid computer can be used to obtain efficient solutions to nontrivial problems in image analysis. We also show the sensitivity of efficient pyramid-computer algorithms to the rate at which essential data can be compressed. Finally, we show that a wide variety of techniques are needed to make full and efficient use of the pyramid architecture. | en_US |
dc.format.extent | 1767270 bytes | |
dc.format.extent | 3115 bytes | |
dc.format.mimetype | application/pdf | |
dc.format.mimetype | text/plain | |
dc.language.iso | en_US | |
dc.publisher | Springer-Verlag; Springer-Verlag New York Inc. | en_US |
dc.subject.other | Digital Geometry | en_US |
dc.subject.other | Image Processing | en_US |
dc.subject.other | Software Engineering/Programming and Operating Systems | en_US |
dc.subject.other | Parallel Computing | en_US |
dc.subject.other | Parallel Algorithms | en_US |
dc.subject.other | Convexity | en_US |
dc.subject.other | Pyramid Computer | en_US |
dc.subject.other | Computer Science | en_US |
dc.subject.other | Algorithm Analysis and Problem Complexity | en_US |
dc.subject.other | Computer Hardware | en_US |
dc.subject.other | Computer Systems Organization and Communication Networks | en_US |
dc.subject.other | Theory of Computation | en_US |
dc.subject.other | Data Structures, Cryptology and Information Theory | en_US |
dc.subject.other | Digitized Pictures | en_US |
dc.title | Computing convexity properties of images on a pyramid computer | en_US |
dc.type | Article | en_US |
dc.subject.hlbsecondlevel | Philosophy | en_US |
dc.subject.hlbsecondlevel | Mathematics | en_US |
dc.subject.hlbtoplevel | Humanities | en_US |
dc.subject.hlbtoplevel | Science | en_US |
dc.description.peerreviewed | Peer Reviewed | en_US |
dc.contributor.affiliationum | Department of Electrical Engineering and Computer Science, University of Michigan, 48109-2122, Ann Arbor, MI, USA | en_US |
dc.contributor.affiliationother | Department of Computer Science, State University of New York, 226 Bell Hall, 14260, Buffalo, NY, USA | en_US |
dc.contributor.affiliationumcampus | Ann Arbor | en_US |
dc.description.bitstreamurl | http://deepblue.lib.umich.edu/bitstream/2027.42/41351/1/453_2005_Article_BF01759066.pdf | en_US |
dc.identifier.doi | http://dx.doi.org/10.1007/BF01759066 | en_US |
dc.identifier.source | Algorithmica | en_US |
dc.owningcollname | Interdisciplinary and Peer-Reviewed |
Files in this item
Remediation of Harmful Language
The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.
Accessibility
If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.