WO1993000651A1

WO1993000651A1 - Method for visually representing a volumetric set of non-geometric multidimensional data

Info

Publication number: WO1993000651A1
Application number: PCT/US1992/005352
Authority: WO
Inventors: Jeffrey S. Saltzo; William Clifford
Original assignee: Digital Equipment Corp
Current assignee: Digital Equipment Corp
Priority date: 1991-06-28
Filing date: 1992-06-25
Publication date: 1993-01-07
Anticipated expiration: 1993-12-28

Abstract

The present invention pertains to a method for transforming non-geometric data into a volumetric representation. Non-geometric data is difficult to represent in three-dimensional space because there is typically no inherent spatial relationship between the data. The present invention transforms the data into a volumetric form and it is then displayed using known visualization techniques. The transformation to volumetric representation facilitates the viewer's perception of relationships between the data.

Description

METHOD FOR VISUALLY

REPRESENTING A VOLUMETRIC SET

OF NON-GEOMETRIC MULTIDIMENSIONAL DATA

FIELD OF THE INVENTION The present invention relates to a method for

visualizing a volumetric representation of non-geometric multidimensional data, and more particularly to a method of visually displaying a volumetric data set representing non-geometric multidimensional data in a manner that permits the analysis of various independent variable parameters of the non-geometric multidimensional data. BACKGROUND OF THE INVENTION

With large databases containing vast amounts of multidimensional data, difficulties arise in communicating the relevant information and the relationship between various parameters of the relevant information contained in the databases in a reasonable and coherent fashion. In many areas, including both the scientific and business fields, the need to "understand" data has always been an elusive, but desired goal. "Understanding data" means the ability of the user of the database to visually perceive the data and relationships between portions or parameters of the data in a meaningful fashion. In particular, the use of 3-D graphic imaging of data is commonly used in the scientific and medical fields but has been under-utilized within the business field due to the inadequacy of current techniques for visualizing non-geometric multidimensional business data.

Certainly, two dimensional alphanumeric printed reports of the relationship between selective portions of a database are useful in both the scientific/medical and business fields. However, it is well known that a more powerful or cognitive way to convey information to human observers about the relationship between portions of a database is achieved through 3-D visualization and graphic representation of the information. The 3-D visualization or graphic representation conveys large amounts of

information, and relationships between the information, quicker and more effectively than any two-dimensional alphanumeric printed format. Indeed, relationships which are nearly undetectable in a two-dimensional alphanumeric report format can be readily perceived when the data relationship is represented in a 3-D visual image.

The visualization of 2-dimensional data in a 2-dimensional plane poses no technical difficulty. There are many ways to display such data including plotting points, drawing lines or curves, and using shading. The perception of the relation between such 2-dimensional data being represented is generally an easy task-for the viewer.

However, the task of understanding the data and the

relationship between various parameters or portions of the data becomes difficult when one attempts to display non-geometric multidimensional data in a 3-dimensional space. In particular, such non-geometric multidimensional business data containing a plurality of independent variables does not lend itself naturally to 3-D graphical representation because there is no inherent spatial relationship among the multiple independent variables in the data base.

The graphical technique of scatter plotting represents one known method for visualizing non-geometric

multidimensional data in a 3-dimensional space. With the scatter plotting technique, a 3-dimensional frame or graph is used, with each coordinate of the data independently displayed as a dot or point. The observer of the scatter plot must exercise subjective judgment to infer patterns by visually perceiving the density of the dots or points within a specific region on the graph. However, problems or difficulties arise with the scatter plotting technique due to the overlapping of coincident dots, the loss of depth perception and the inability to detect clustering or proximity of dots. Thus, the ability of the scatter plot technique to convey relationships between portions or parameters of the data, for example, density information, is limited. In addition, the scatter plot technique does not provide the relationships between portions or

parameters of the data in a format that facilitates

additional techniques to enhance different relationships within the data. SUMMARY OF THE INVENTION

The present invention discloses a method of visually displaying a volumetric representation of nongeometric multidimensional data in a comprehensible fashion by quantizing the non-geometric data into 3-dimensional voxels of information. A voxel is a 3-dimensional unit of volume containing one or more values associated with it. The present invention utilizes a portion or subset of the data from a database containing a plurality of nongeometric multi-dimensional data records wherein each data record contains one or more variables of associated data. This non-geometric multidimensional data set is transformed into a volumetric data set. A volumetric data set is a three dimensional array of voxels. Quantification of the volumetric data set is achieved by partitioning each 3-dimensional axis with discrete incremental values. These incremental values respectively correspond to the length of each side of a given voxel. Then, the data set is analyzed to determine which data records are associated with each of the voxels. After locating the data associated with each voxel, the present invention performs a selected operation on the data to arrive at one or more values for each voxel. The user selects the operation depending upon the specific

relationship the user wishes to see between the data . The values of the voxels are determined by both the data records associated with each voxel and the operation performed on the data records.

In another embodiment of the present invention, quantization begins on two axes of a 3-dimensional space to form 2-dimensional square partitions. The third dimension is then quantized to add a third dimension to the 2-dimensional squares to form a plane of voxels. The data records are analyzed to determine which data records are associated with each voxel in the plane of voxels. After an operation is selected to arrive at one or more values for each voxel in the plane of voxels, a volumetric data set is created which has a length of one in the third dimension. Then, the remaining voxels and their associated "values" in the 3-dimensional space are determined at each successive increment in the 3-dimensional space. Once the voxels and their corresponding values are determined, a volumetric data set has been established.

The newly created volumetric data set provides the information needed to display the data and relationships between portions of the data contained in the non-geometric multidimensional data set using known methods of

visualization or graphics. The volumetric data set permits showing relationships among, at least 4 variables at one time. In addition, once the data is transformed to a volumetric data set, additionally known techniques are available to further enhance the visual relationships between various portions of the data. DESCRIPTION OF THE DRAWINGS

FIG. 1 is a flow chart implementing the present invention.

FIG. 2 shows a volumetric representation of data relationships between the selected variables age, salary and seniority according to the present invention.

FIG. 3 shows a known 3-D scatter plot technique of illustrating data relationships between the same data illustrated in FIG. 2.

FIG. 4 shows a shrink wrapping of the volumetric representation of FIG. 3 around all voxels with at least fifty people.

FIG. 5 shows apparatus for implementing the present invention. DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Referring to the drawings, FIG. 1 shows a flow chart of the method steps of the present invention and FIG. 5 shows apparatus for implementing the present invention.

As shown in step 10, multidimensional data from a non-geometric data base 110 contained on an auxiliary disk storage unit 108 is used as input. The data set is

comprised of records with each record having a plurality of variables. Communication between the central processing unit (CPU) 104, the Auxiliary Disk Storage 108, and the Graphic Display Terminal Workstation (terminal) 102 is achieved by access to a data bus 112.

After the data set is read into main memory 106, at step 12, the user, through a keyboard 100 attached to the Terminal 102, or other suitable input device, selects three variables from the plurality of variables of the

non-geometric multidimensional data set to identify the x, y, and z axes in the three-dimensional space. The three variables can be any three variables within the set of non-geometric multidimensional data. The user chooses the three variables depending upon the nature of the

relationships the user wishes to perceive. Depending upon the data and the nature of the relationships the user wishes to perceive, certain combinations of variables provide more useful information than others. For example, in a typical data base of employee information including records containing the variables age, social security number, address, salary, seniority, etc..., if a user were interested in certain characteristics of employees that relate to the employees' salaries, age and seniority, a user could define x to be the age of the employee, y to be the employee's salary, and z to be the employee's

seniority. In such a situation the use of the social security number as a variable for the x, y or z axis will not provide any meaningful information because the user is not interested in relationships of employees with respect to an arbitrary social security number. Of course, other databases of non-geometric multidimensional data related to business information can be used without departing from the teachings of the present invention. In essence the subject matter of the non-geometric multidimensional business data is not a limiting factor of the present invention.

The desired quantification for each axis is set at step 14. The user, through the use of the keyboard 100, assigns three incremental values to partition each x, y and z axis. In the example above, a user could define the quantification of the x axis to be on a per-year basis, the quantification of y to be per $1,000, and the

quantification of z to be in five year increments. The choice of incremental values selected need not be limited to a range of specific integer numbers or constant

incremental values for each axis. For example, if a user defined x to be sales commissions, y to be time, and z to be the color of the salespersons' eyes, then the

quantification of the x axis could be 50% of the sales commission goal for the first incremental value and 10% of the sales commission goal for subsequent incremental values, the quantification of the y axis could be by months of the year, and the quantification of the z axis could be brown, blue, hazel, green, and other. The quantification of the x, y and z axis establishes the height, width, and length of each voxel in units of the chosen x, y and z increments. Thus, the volume that each voxel occupies in the quantized three-dimensional space is defined.

After assigning variables to each axis and a

quantification to each variable, at step 16, all records in the data set are analyzed by the CPU 104 to identify which data records are within each voxel. In the above example, the specific group of person s having age, salary and seniority within the specified quantized ranges are

considered to be contained within the same voxel. This is accomplished by "bucketizing" or rounding the x, y and z variables to the nearest year, $1000 and 5 years,

respectively. In an alternate embodiment of the present invention all records in the data set are analyzed by CPU 104 to identify which records are associated with each voxel. Data records contained within a given voxel and data records within neighboring voxels can be associated with the given voxel. For example, a weighted average of the data records contained within voxels neighboring a selected voxel can be used to determine the value of said selected voxel. Neighboring means the defined relationship between voxels such as adjacent voxels or voxels no more than two removed from the subject voxel or any other defined relationship. Such a technique can be used to smooth or accentuate all areas where surrounding voxels have abrupt changes in values.

A distribution function is then selected by the user through the keyboard 100 at step 18 to map the identified data records for each voxel to one or more values for that voxel. The distribution function in mapping to the value or values for a voxel can consider either the data within the voxel or the data associated with the voxel. The choice of distribution functions implementing the present invention depends entirely upon the database information and the relationships between the portions of the data the user wishes to view. Examples include averaging last year's pay raises, counting the number of employees, and determining the median number of dependents of all

employees within each voxel of quantized space. In

addition, the distribution function has the capability of operating on more than one variable in the data set. For example, the distribution function could, for each

employee, take the number of work days in a year and subtract all vacation time, sick days, and personal days to arrive at the number of days each employee worked during the year. Then, the, average value of all employees within a voxel can be ascertained and associated with the given voxel. Of course, the distribution function could

selectively not compute a value for some voxels or

selectively compute a zero value for some voxels. The selection of appropriate distribution functions is well within the abilities of someone ordinarily skilled in this field.

In the preferred embodiment, the data is also

filtered. At step 20, the user through use of a keyboard 100 selects if filtering is required. If filtering is chosen by the user, the user enters the type of filtering through use of the keyboard 100 at step 22 and the

filtering is performed by the CPU 104 at step 24.

Filtering provides the ability to isolate selected data records in the database. For example, the preferred embodiment has the capability to take a "time-slice" of the volumetric data set at any given point in time. This is achieved by the user, through use of a keyboard 100, selecting the filtering option at Step 20 and assigning a specific filtering time frame at Step 22. Then, the CPU 104 filters out all data records outside of the chosen time frame at Step 24.

At Step 26, the distribution function is implemented by the CPU 104 to determine the values of each voxel. The distribution function maps the data records associated with each voxel to one or more values for each voxel. With one or more values associated to each voxel, a volumetric data set is created and represented by a 3-dimensional array containing one or more values for each voxel. The

volumetric data set is then stored on the auxiliary disk storage 108 at step 28.

A computer program written in the C-programming language capable of performing the steps 10 through 28 of the present invention is the preferred embodiment and is set forth in Table A. The program uses a non-geometric multidimensional data set and user input to generate a file containing a volumetric representation of the non-geometric multidimensional data.

TABLE A: C LANGUAGE PROGRAM

#include <stdio . h>

#include <string. h>

#include <math. h>

#define NUM_VALUES_ PER_LINE 12

#define NUM VOXELS ( 64*64*64 )

#define Z_OFFSET (64*64)

#define Y_OFFSET ( 64)

#define QUANTIZE_Z (int)

#define QUANTIZE_Y (int)

#define QUANTIZE_X (int)

float perform_count_math_function ( bucket_count)

int bucket_count;

{

return ( ( (float) (bucket_count * 2.55) ) );

}

#define VOLUME_ELEMENT ( x,y, z )\

( QUANTIZE_Z(z) * Z_OFFSET + QUANTIZE_Y (y) * Y_DFFSET + QUANTIZE_X(x) )

#define SEQUENCE_ELEMENT 5

#define MAX_BYTE_VALUE 255

mail (argc,argv)

int argc;

chart **argv;

{

int list[20];

int size;

int found,j,i,temp;

char *filename= "non_geomtric_data.dat";

char *filename_out = "volume_data_set.dat";

FILE *fp, *fp_out ;

int x_axis, y_axis, z_axis, bucket_val;

int sequence = -1;

int *bueket_count, *bucket_vol, vol_index;

unsigned char val;

foat bucket_val_after_math;

foat perform_count_math_function( );

fp - fopen ( filename, "r" );

if ( fp == NULL )

printf("open input file failed \n");

for (i=l,╌argc; argc>0; i++,╌argc) { if (argv[i][0] =='-') {

switch (argv[i][l]) {

case ' x' :

x_axis = atoi ( argv[i+l] );

i++; argc╌;

break;

case 'y' :

y_axis = atoi ( argv[i+l] );

i++; argc╌;

break;

case 'z' :

z_axis = atoi ( argv[i+l] );

i++; argc╌;

break;

case 'b' :

bucket_val = atoi ( argv[i+l] ); i++; argc╌;

break;

case ' s' :

sequence - atoi ( argv[i+l] );

i++; argc╌;

break;

default :

printf(" unknown argument %s \n", argv[i] ); else

printf (" unknown argument %s \n", argv[i] );

fp_out = fopen( filename_out, "w");

if ( fp_out == NULL)

printf("open output file failed \n");

size - NUM_VOXELS*sizeof (int) ;

bucket_count = (int *)malloc( size );

for( i = 0; i < NUM_VOXELS; i++ )

buσket_count [i] = 0;

if ( bucket val != -1) {

size = NUM_VOXELS*sizeof (int) ;

bucket_vol = (int *)malloc( size );

for( i = 0; i < NUM_VOXELS; i++ )

bucket_vol[i] = 0;

}

while ( fread( list, sizeof(int), NUM_VALUES_PER_LINE, fp ) != 0) { if ( sequence == -1 sequence == list [SEQUENCE_ELEMENT] ) { vol_index =

VOLUME_ELEMENT (list[x_axis ] ,list[y_axis],list{z_axis]);

bucket count [ vol index ]++; if(bucket_val != -1 )

bucket_vol [ vol_index ] += list [ bucket_val

];

}

output_char ( fp_out, 64 );

for ( i = 0; i < NUM_voxels; i++ ) {

if ( bucket_val == -1 ) {

bucket_val_after_math =

perform_count _math_function( bucket_count[ i ] if ( bucket_val_after_math > MAX_BYTE_VALUE )

bucket_val_after_math = MAX_BYTE_VALUE; val = bucket_val_after_math;

}

else {

if ( bucket_count [i] )

val = bucket_vol[i]/bucket_count[i]; else

val = bucket_vol[i];

}

output_char ( fp_out, val );

}

free ( bucket_count );

if ( bucket_val == -1 )

free( bucket_vol);

fclose ( f p ) ;

fclose ( fp_out ) ;

}

output_char( fp, info)

FILE *fp;

unsigned char info;

{

unsigned char temp [1];

temp[0] = (unsigned char) info;

if( fwrite ( temp, sizeof (unsigned char), 1, fp ) != 1) {

printf("can not write to output file \n" );

exit(0);

}

} Once the non-geometric data has been transformed into a volumetric representation the data is graphically displayed in three dimensions on the terminal 102. To visualize the volumetric data in the preferred embodiment, a graphical visualization tool like AVS is used. Using AVS, a sphere is displayed at each of the voxels on the terminal 102. The radii of the spheres are proportional to the values of each voxel. The voxel with the largest value has the largest sphere associated with it. The spheres are proportionally smaller in voxels which have proportionally smaller values.

There are other ways known in the art to visualize the volumetric data created by the present invention such as isosurfacing or shrink wrapping and slicing cross sections of the three-dimensional data set. However, it is

important to understand that transforming the non-geometric multidimensional data into a volumetric representation allows such graphic visualization to be possible.

An illustration of the graphic visualization generated by the present invention is set forth in FIG. 2. To generate FIG. 2, the employee database of the above example is used as input. The x, y and z variables are chosen as age, salary and seniority. The value of the voxel ╌ and the associated radius of the sphere within each voxel ╌ is determined by counting the number of employees within the given voxel. In this example, no filtering is performed. From FIG. 2, an expected trend is visually illustrated:

many people are hired young and become higher paid as they grow older. In addition, FIG. 2 also shows that very recently a large number of older, well paid, and more senior people have been hired.

FIG. 3 shows the results of the same data used to generate FIG. 2 displayed using the scatter plot technique. As can be seen in FIG. 3, the scatter plot technique is unable to convey the above mentioned trends in employee salary. FIG. 3 shows a cluster of salaries ranging from about 60 to 70; however, the age and seniority of the people in the cluster cannot be determined from FIG. 3.

.After the non-geometric multidimensional data is transformed into a volumetric data set, many known methods of visualizing the data can be used to display the

information. For example, the graphical technique commonly known as isosurfacing or shrink wrapping represents a method for visualizing multidimensional volumetric data in a 3-dimensional space. With the shrink wrapping technique, coordinates which contain the same selected values are graphically displayed and shaded together. FIG. 4 shows the volumetric data generated by the present invention in FIG. 2 shrink wrapped around all voxels with at least fifty people. Without the volumetric data generated by the present invention, the application of the shrink wrap technique is not possible. The shrink wrap technique requires a volumetric data set and cannot show

relationships between non-geometric multidimensional data. Thus, the preferred embodiment of the present

invention describes a method for visualizing a volumetric representation of non-geometric multidimensional data by quantizing selected variables of the non-geometric,

multidimensional data and then mapping the non-geometric data into one or more values associated with the newly created voxels in the three-dimensional space.

As is evident from the above description, the

implementation of the present invention can vary greatly depending upon the variables in the non-geometric

multidimensional database and the desired goal, or desired relationship, which the user is attempting to obtain.

However, the scope of the present invention is intended to cover all variations and substitutions which are and become apparent from the above illustrative embodiment of the present invention.

Claims

WHAT IS CLAIMED IS: 1. A method for visually representing as a volumetric data set a non-geometric multidimensional data set having a plurality of records each with a plurality of variables comprising the steps of: selecting three variables from said plurality of

variables in said non-geometric multidimensional data set for respectively defining one of the x, y and z axis of a three dimensional space; selecting quantized values for said selected variables on each of the three axis to establish a plurality of voxels within said three dimensional space; identifying said records of said non-geometric

multidimensional data set that are associated with each of said voxels; mapping said identified records associated with each of said voxels to at least one value for each of said voxels to establish a volumetric data set; and displaying said volumetric data set.

2. A method for visually representing as a volumetric data set a non-geometric multidimensional data set having a plurality of records each with a plurality of variables comprising the following steps of: selecting three variables from said plurality of

multidimensional data set that are associated with each of said voxels; filtering said non-geometric multidimensional data set to obtain selected records within said data set; mapping said identified records associated with each of said voxels to at least one value for each of said voxels to establish a volumetric data set; and displaying said volumetric data set.

3. A method for visually representing as a volumetric data set a non-geometric multidimensional data set having a plurality of records each with a plurality of variables comprising the steps of: selecting three variables from said plurality of variables in said non-geometric multidimensional data set for respectively defining one of the x, y and z axis of a three dimensional space; selecting quantized values for said selected variables on each of the three axis to establish a plurality of voxels within said three-dimensional space; identifying said records of said non-geometric

multidimensional data set that are within each of said voxels; mapping said identified records within each of said voxels to at least one value for each of said voxels to establish a volumetric data set; and displaying said volumetric data set.

4. A method for visually representing as a volumetric data set a non-geometric multidimensional data set having a plurality of records each with a plurality of variables comprising the following steps of: selecting three variables from said plurality of

variables in said non-geometric multidimensional data set for respectively defining one of the x, y and z axis of a three dimensional space; selecting quantized values for said selected variables on each of the three axis to establish a

plurality of voxels within said three dimensional space; identifying said records of said non-geometric

multidimensional data set that are within each of said voxels; filtering said non-geometric multidimensional data set to obtain selected records within said data set; mapping said identified records within each of said voxels to at least one value for each of said voxels to establish a volumetric data set; and displaying said volumetric data set.