S+-trees: An efficient structure for the representation of large pictures

Wiebren de Jonge, Peter Scheuermann, Ardie Schijf

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


We are concerned in this paper with the efficient encoding and manipulation of pixel trees that are resident on secondary devices. We introduce a new structure, the S+-tree, that consists of a paged linear treecode representation of the picture (data) and an index whose entries represent separators among some of the leafcodes implicitly embedded in the linear representation. Our scheme combines the advantages of treecode and leafcode representations by offering the space efficiency of DR-expressions and the indexing capabilities of B+-trees, thus permitting easy sequential and random access to a compact representation of pictorial data. We describe an algorithm which encodes our structure from an ordered list of black leafcodes. The paged structure of the S+-tree, whereby each data page is a self-contained tree, enables to design an efficient random access search algorithm to find the color of a given region that corresponds to a quadrant or semi-quadrant. The search algorithm is non-recursive in nature and it can be optimized to work bytewise instead of bitwise. We also present an efficient method for performing translation operations on large pictures stored on secondary devices and illustrate its efficiency with the S+-tree structure.

Original languageEnglish (US)
Pages (from-to)265-280
Number of pages16
JournalComputer Vision and Image Understanding
Issue number3
StatePublished - May 1994

ASJC Scopus subject areas

  • Software
  • Signal Processing
  • Computer Vision and Pattern Recognition

Fingerprint Dive into the research topics of 'S<sup>+</sup>-trees: An efficient structure for the representation of large pictures'. Together they form a unique fingerprint.

Cite this