S+-Trees: An Efficient Structure for the Representation of Large Pictures

W. Dejonge*, P. Scheuermann, A. Schijf

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

25 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+-treestructure.

Original languageEnglish (US)
Pages (from-to)265-280
Number of pages16
JournalCVGIP: Image Understanding
Issue number3
StatePublished - May 1 1994
Externally publishedYes

ASJC Scopus subject areas

  • Environmental Science(all)
  • Engineering(all)
  • Earth and Planetary Sciences(all)


Dive into the research topics of 'S+-Trees: An Efficient Structure for the Representation of Large Pictures'. Together they form a unique fingerprint.

Cite this