S + -trees: an efficient structure for the representation of large pictures
S + -trees: an efficient structure for the representation of large pictures
复制标题
DOI：
10.1006/ciun.1994.1018
复制
发表时间：
1994-05
期刊：
影响因子：
--
通讯作者：
W. D. Jonge;P. Scheuermann;A. Schijf
中科院分区：
文献类型：
--
作者：
W. D. Jonge;P. Scheuermann;A. Schijf
摘要我们关心的是驻留在辅助设备上的像素树的有效编码和操作。我们引入了一种新的结构，S+树，它由图片(数据)的分页线性树码表示和一个索引组成，该索引的条目表示隐含在该线性表示中的一些叶码之间的分隔符。我们的方案结合了树码和叶码表示的优点，提供了DR表达式的空间效率和B+树的索引能力，从而允许轻松地顺序和随机地访问图像数据的紧凑表示。我们描述了一种算法，它从黑色叶码的有序列表中编码我们的结构。S+树的分页结构，其中每个数据页是一棵自包含树，使得能够设计一种有效的随机访问搜索算法来找到对应于象限或半象限的给定区域的颜色。搜索算法本质上是非递归的，它可以优化为按字节而不是按位工作。我们还提出了一种对存储在辅助设备上的大图片执行翻译操作的有效方法，并以S+树结构为例说明了该方法的有效性。
Abstract 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.