Browse Prior Art Database

Parallel, Contiguous in Memory Histogram Computation for Volume Data

IP.com Disclosure Number: IPCOM000195043D
Original Publication Date: 2010-May-10
Included in the Prior Art Database: 2010-May-10
Document File: 5 page(s) / 510K

Publishing Venue

Siemens

Related People

Juergen Carstens: CONTACT

Abstract

The combination of a histogram and an index provides fast access to volume data with specific values. For the construction of histograms for volume data, currently a single pass technique is used. Thereby, the entire volume data is traversed only once. Thus, the values of each data point are noted and added to a list, corresponding to the value of the indices, as shown in Figure 1. The vertical table contains all the values which are possible in the volume data and the horizontal list contains the cell indices with the corresponding value. The disadvantage of the single pass technique is the reduced speed in implementation and also it leads to severe memory fragmentation. The single pass technique also does not enable a simple disk swapping.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 5

Parallel, Contiguous in Memory Histogram Computation for Volume Data

Idea: Saikat Mukherjee, IN-Bangalore; M. Ravi Krishna, IN-Bangalore; Sabishaw Bhaskaran, IN- Bangalore; Donny T. Daniel, IN-Bangalore

The combination of a histogram and an index provides fast access to volume data with specific values.

For the construction of histograms for volume data, currently a single pass technique is used. Thereby,

the entire volume data is traversed only once. Thus, the values of each data point are noted and

added to a list, corresponding to the value of the indices, as shown in Figure 1. The vertical table

contains all the values which are possible in the volume data and the horizontal list contains the cell

indices with the corresponding value. The disadvantage of the single pass technique is the reduced

speed in implementation and also it leads to severe memory fragmentation. The single pass technique

also does not enable a simple disk swapping.

In the following a parallel, two-pass technique for creating histograms is proposed. At first, a frequency

distribution table is created from the volume data, shown in Figure 2. Afterwards, a cumulative

frequency distribution table is created from the results. Then the entire histogram is allocated to the

contiguous memory using the cumulative frequency distribution as an index to store the indices in a

second pass, shown in Figure 3. This mechanism of creating the histogram takes place in parallel

using multiple CPU cores (CPU: Central Processing Unit). For illustrating the parallel technique the 3D

volume needs to be imagined as slices of 2D data, shown in Figure 4 (3D: Three Dimensional; 2D:

Two Dimensional). To parallelize the frequency distribution calculation, the slices are distributed

between so-called threads. The number of threads depends on the number of available CPU cores

and also corresponding to the number of the frequency distribution tables. Each thread is assigned to

a certain number of 2D slices (Figure 5). The total number of slices each thread has to handle is given

as:

n = integer (N / MAX_THREAD) (1)

In equation (1), N stands for the total number of slices. The number of slices being processed for the

last thread, the MAX_THREAD, is given as:
(N - n * (MAX_THREAD - 1)) (2)

Each thread creates a frequency distribution table for the slices which are allocated to them. This is

shown in Figure 6, whereby the color of the tables represents the specific thread that is responsible for

the computation of that table. The FD value represents the number of pixels having the value v. Once

all threads have completed filling up the frequency distribution tables, each thread is assigned to

create the cumulative frequency distribution table for a certain range, given by:
range = Max Value / MAX_THREAD (3)

The number of values being processed for the last MAX_THREAD is calculated with:

                   (Max Value - range *(MAX_THREAD-1)) (4) The entire parallel process is shown in Figure 7, whereby each co...