Compression of Position Data

Figure 5.3: Encoding of voxel positions: slice scanned from top left to bottom right a) long sequences and sequence continuations b) re-encoding of voxels and non-default stepping direction to reduce number of sequence starts and thus position specifications

(a)	(b)

Boundary voxels within a single $z$-slice form object contours which consist of face-connected voxels (see figure 5.3). Exploiting spatial coherence and connectivity, voxels can be grouped into ``sequences'' which spatially follow the object contour. During compression, the slice is scanned for non-encoded voxels. Whenever one is found, a new sequence is started and the position of the voxel $(P_x, P_y)$ is stored. The sequence is continued, by selecting and appending one of the neighbor voxels at it's end. As the contour voxels are face-connected, potential candidates for continuation are located at $(P_x+dx, P_y)$ or $(P_x, P_y+dy)$ with $dx, dy$ being respectively -1 or 1. Encoding the selection of one of the four neighbors as a successor would require 2bits. If the choice is restricted to two neighbors by using constant values of $dx$ and $dy$ for a whole sequence, each voxel continuing a sequence can be specified by a single bit, which defines whether a step by $dx$ or $dy$ is used. Although this restriction reduces the flexibility and thus the average length of sequences, the cost per voxel within a sequence is cut by half, outweighting the disadvantage of shorter sequences.

In cases where a direct neighbor of the trailing voxel of a sequence is present, but can not be reached using the current (fixed) $dx$ and $dy$ values, a sequence restart can be performed, continuing the sequence at this neighbor with a new value for $dx$ or $dy$. To realize this, each sequence is followed by a command code which specifies whether the sequence ends, or restarts with a different stepping direction. The presence of a restart code implicitly defines the position of the start voxel of the new sequence. As the previous sequence had to be terminated, no successors of it's last voxel are present in it's $dx$ and $dy$ direction. One of the remaining two neighbors is the second but last voxel of the interrupted sequence, so the other one necessarily is the starting voxel of the new sequence. The new values of $dx$ and $dy$ are derived from $dx$ and $dy$ of the old sequence. Depending on whether the last step of the sequence was $dx$ or $dy$ either $dx$ or $dy$ is inverted. Although being more restrictive than with an explicit specification of $dx$ and $dy$, this strategy still allows encoding of cyclic structures with a single position specification and restart commands within a chain of sequences.

For each combination of $dx$ and $dy$ values, one of the possible stepping directions is preferred, whenever both ways can be taken. The preference is chosen in a way, that a clockwise processing of closed objects will stay as close to the outer border as possible. For example, for $dx=1$ and $dy=1$ like in the first sequence of figure 5.3a, steps by $dx$ are preferred.

After the creation of long sequences, usually groups of short sequences or even non-connected voxels remain. Starting a new sequence for each of these voxels is expensive. Usually most of these voxels can be encoded at a lower cost by joining them into sequences re-using voxels already encoded earlier in the process (figure 5.3b). In general, a sequence has to be continued, reusing already encoded voxels, if this allows to reach non-encoded voxels at a cost which is lower than a ``sequence end'' and the start of a new sequence.

As the scan for non-encoded voxels within a slice is performed in ascending $x$ and $y$ direction, using $dx=1$ and $dy=1$ as a default stepping direction for newly started sequences is usually a good solution - voxels with smaller $x$ and $y$ coordinates compared to the current one are already encoded in this case. In some cases however, keeping $dx=1$ and $dy=1$ as default directions tends to generate a lot of short sequences ``sequence trashing'' (figure 5.3b). Instead it is better to first search ``backwards'' from the identified non-encoded voxel (using $dx=-1$, $dy=1$) and to start the new sequence using $dx=1$ and $dy=-1$ at the last voxel found (for reasons of simplicity no backward scan was performed for the sequences of figure 5.3a). At each sequence start one bit is used to store, whether the default stepping direction $(1,1)$, or the direction of the backward scan $(1,-1)$ is used.

For further compression, the sequence data is separated into four streams. The position stream stores starting positions and stepping directions. Positions are stored using Huffman encoded differences between successive coordinate values (Typically 12bits per starting code). The length stream stores information about sequence lengths (Huffman encoded, 5bits per sequence). The step stream stores the information for building up sequences (onebit per voxel). As $dx$ and $dy$ steps tend to cluster due to the presence of a preferred stepping direction, this information is run-length encoded, using again Huffman encoding for the run-lengths. The control stream is used for the sequence control information (end/restart, 1bit per sequence). As many restarts at the beginning of encoding a slice are followed by short sequences collecting isolated voxels towards the end of encoding, which leads to clustering of restart and end commands, run-length encoding combined with Huffman encoding is also used here. Combining all those streams, an average of 2bits is required to encode the position of a single voxel.

Within all other data channels, voxels are encoded in the same order as their position data. This ordering allows to exploit spatial coherence within voxel sequences also for attribute encoding. For subsequent occurrences of re-encoded voxels, of course, no attribute information is stored.

mailto:mroz@cg.tuwien.ac.at.