Generating a linear octree from voxel data for a connected object

Renben Shu; Mohan S. Kankanhalli

doi:10.1117/12.59481

1 May 1992 Generating a linear octree from voxel data for a connected object

Renben Shu, Mohan S. Kankanhalli

Proceedings Volume 1653, Medical Imaging VI: Image Capture, Formatting, and Display; (1992) https://doi.org/10.1117/12.59481
Event: Medical Imaging VI, 1992, Newport Beach, CA, United States

Abstract

Interactive needs of medical visualization require fast processing of huge amounts of data. There is a need for compact storage and efficient handling of the voxel input from CT and MRI machines. The linear octree data structure is an efficient representation technique which leads to less storage and is amenable to different kinds of geometric operations. This data structure is particularly useful in visualizing thresholded images which are binary images. There are several algorithms to generate a linear octree from binary voxel data with time complexity O(n3) for an input of size n3 voxels. We present an algorithm which first extracts the surface of the object. Based on this surface data, the object is partitioned into a set of parallelepipeds where each parallelepiped is a contiguous run of voxels along one axis. Starting from the lowest level of the octree, the algorithm proceeds iteratively to the highest level, computing maximal overlaps of the parallelepipeds at each level. For any level, the voxels which are not in the overlap are octree nodes and are output at that level. The maximal overlapped parallelepipeds form the input to the next higher level in the algorithm. For a connected object having n3 voxels, the algorithm has a time complexity of O(S) where S is the size of the surface of the object. The algorithm has been implemented and tested for a variety of medical data. We also show how this algorithm can be parallelized.

Citation Download Citation

Renben Shu and Mohan S. Kankanhalli "Generating a linear octree from voxel data for a connected object", Proc. SPIE 1653, Medical Imaging VI: Image Capture, Formatting, and Display, (1 May 1992); https://doi.org/10.1117/12.59481

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available