Tang Hui

Bao Xu Dong

Luo Limin

A multi-volume visualization method for spatially aligned volumes after 3D/3D image registration Méthode de fusion et de visualisation de volumes spatialement alignés après recalage 3D/3D

Keywords: Direct volume rendering, Medical imaging, Multi-volume rendering, Scientific visualization, Vectorial volume classification, 3D image registration Classification de volumes vectoriels, Imagerie médicale, Recalage 3D, Rendu de volume, Visualisation de volumes fusionnés, Visualisation scientifique

Objective A new method for the visualization of spatially aligned volumes after 3D/3D image registration is presented in this paper. This work aims at displaying the full information of the multi-volume in the same scene.

Materials and methods

First, we form a vectorial volume from spatially aligned multi-volume after 3D registration. Then, a statistical vectorial volume classification method based on neighborhood weighted Gaussian mixture model is applied to analyze the vectorial volume and get material distribution information. Finally, several rendering techniques are adapted to visualize the parameters.

Results

We imply an application case: the visualization of preoperative kidney planning system to express our visualization method, but this method is not limited to the specific application case.

Discussion According to the levels where the data intermixing occurs, our method mixes the data at the earliest level so that it is called the acquisition level intermixing method.

Introduction

In medical imaging, multiple images are often acquired from the same subject at different times, and often with different imaging modalities. These multiple acquisitions contain different kind of information of a complementary nature (time evolution of metabolism, different anatomical structures, etc.). A medical image registration process must then be performed in order to bring the different acquisitions into a single reference space [START_REF] Maintz | A survey of medical image registration[END_REF][START_REF] Zitova | Image registration methods: a survey[END_REF][START_REF] Hill | Medical image registration[END_REF][START_REF] Jannin | Fusion de données en imagerie médicale: revue méthodologique basée sur le contexte clinique[END_REF][START_REF] Betrouni | Le recalage en imagerie médicale : de la conception à la validation[END_REF]. Image registration is the process of overlaying two or more images of the same scene at different times, from different viewpoints, and/or by different sensors [START_REF] Zitova | Image registration methods: a survey[END_REF]. After the 3D/3D registration, we got several volumes spatiallyaligned on a common grid. If these volumes are rendered individually, the registration process will be useless. So that a combined presentation of registered volume datasets is needed to give a better view of the information content, so that a multi-volume visualization method will be discussed in this paper.

For the visualization of a single volume, direct volume rendering convey an entire 3D dataset in a 2D image directly. Many studies have been conducted on direct volume rendering [START_REF] Levoy | Display of surfaces from volume data[END_REF][START_REF] Levoy | Efficient ray tracing of volume data[END_REF][START_REF] Kaufman | The visualization Handbook; chap. Overview of volume rendering[END_REF]. The process of constructing an image from a volumetric dataset using direct volume rendering can be summarized by the following steps [START_REF] Hadwiger | Real-time Volume Graphics[END_REF]:

1. Data traversal: The positions of sample points within the volume are determined, which is usually according to the viewing point. 2. Sampling and interpolating: The dataset is sampled at the chosen positions. The sampling points typically do not coincide with the grid points, and so interpolation is needed to recover the sample value. 3. Gradient computation: The data gradient is often needed, in particular as an input to the shading component. Gradient computation requires additional sampling. 4. Transfer function: The sampled values are mapped to optical properties, typically color and opacity values. The transfer function will help to visually distinguish materials in the volume. 5. Shading and illumination: Shading and illumination effects can be used to modulate the appearance of the samples. The three-dimensional impression is often enhanced by gradient-based shading which gives information about surface orientation. 6. Compositing: The pixels of the rendered image are computed by compositing the optical properties and the colors of the sample points according to the volume rendering integral.

Based on the fundamental algorithms used for single volume rendering, a few literature did some research about multi-volume rendering techniques [START_REF] Cai | Data intermixing and multi-volume rendering[END_REF][START_REF] Wilson | Interactive multi-volume visualization[END_REF][START_REF] Roettger | Spatialized transfer functions[END_REF][START_REF] Firle | Multi-volume visualization using spatialized transfer functions. gradient-vs. multi-intensity-based approach[END_REF].

The main idea of these multi-volume rendering algorithms is to mix the multi-information together at a certain level of the rendering pipeline. Cai and Sakas [START_REF] Cai | Data intermixing and multi-volume rendering[END_REF] classified the methods according to the levels where the data intermixing occurs. Three levels were defined: image level intermixing, composition level intermixing and illumination model level intermixing (Fig. 1).

• The simplest mixing technique is image level intermixing. It consists to render each volume separately as a scalar dataset and then to blend the result images according to some weighting function that possibly includes the z-buffer of opacity channel. This method doesn't require any modification of the volume renderer but it loses the depth ordering information.

• The composition level intermixing method solved this problem. For each voxel of each volume, the opacity and color are estimated according to the voxel value and the illumination model. These opacities and colors are then intermixed at the compositing step, thus preserving the depth information. Most transfer function based methods belong to this category [START_REF] Roettger | Spatialized transfer functions[END_REF][START_REF] Firle | Multi-volume visualization using spatialized transfer functions. gradient-vs. multi-intensity-based approach[END_REF].

• The third method is illumination model level intermixing. The volume samples are combined before colors and opacities are computed. Cai and Sakas [START_REF] Cai | Data intermixing and multi-volume rendering[END_REF] proposed this method for their special application context and compared it with the two former methods. They also indicated its possibility to be applied in other multi-volume rendering contexts.

All these above methods render the multi-volume by mixing the component volumes at one certain step of volume rendering pipeline. But actually, these volumes are different acquisitions taken from the same patient so that they are not independent. While analyzing the registered volume dataset, each sample point should contain several elements which are sampled from the corresponding volumes. Therefore we can form a vectorial volume dataset, in which each voxel contains a vector of n elements corresponding to the information of the acquisitions (n is equal to the number of acquisitions). Then the analysis can be performed on this vectorial volume instead of several individual volumes. That is to say, the intermixing level can then occur before the rendering pipeline. We will call this level acquisition level intermixing (Fig. 1). This method is realized by the following steps: first form a vectorial volume from the multi-volume; then apply a statistical multi-dimensional classification method to get the material property information; finally render the multi-volume according to the classified material properties.

The key idea of this paper is to consider the multi-volume as a vectorial volume and get the material distribution information by a vectorial volume classification method so that the acquisitions concerning the same subject can be considered together for the presentation of information. The rest of this paper is organized as follows. Section 2 expresses the proposed multivolume rendering framework. The detail of the statistical vectorial volume classification method is presented in section 3. After classification, several rendering methods can be used to display the material information, which are discussed in section 4. We take an application case of the proposed multi-volume visualization method for detail demonstration in this section. Finally, the conclusions are given in Section 5.

Multi-volume rendering framework

Based on the discussion in Section 1, we proposed a multi-volume rendering method which belongs to the acquisition level intermixing. The framework of this method is described in Fig. 2.

After registration, several volumes will be aligned into the same space (Fig. 3-a to c). As analyzed before, the spatially aligned volumes can form a vectorial volume. If we analyze this vectorial volume instead of the individual volumes, all acquisitions can be taken into account at the same time. So that we propose to first perform analysis on this vectorial volume and then apply rendering techniques to show the analysis result parameters. Since the multi-volumes are mixed together at the beginning, according to the levels where the data intermixing occurs, our method is called acquisition level intermixing. The intermixing step is realized by a vectorial volume classification method. It seems that any vectorial volume classification technique can be applied in this framework. But see Fig. 2 again, we can find that the rendering result relies much on the classification result so that the choice of the classification method becomes the essential step in this pipeline. We implemented a vectorial volume soft segmentation method based on neighborhood weighted Gaussian mixture model which has been presented in our previous paper [START_REF] Tang | A vectorial image soft segmentation method based on neighborhood weighted gaussian mixture model[END_REF] because this method is less affected by noises and it can avoid mis-classification on the boundaries.

After this classification, we get the material probability distributions on each grid of the volume. At this step, the user assigns some material properties i.e. the material color C k and the material global opacity α k with 1 ≤ k ≤ K, K the number of tissues (or material). With these material properties, several rendering techniques which are extended from scalar volume rendering techniques can be applied to get the final image. For the rendering techniques for scalar volumes, most of the algorithms can be classified into two categories: surface rendering algorithms and direct volume rendering algorithms [START_REF] Elvins | A survey of algorithms for volume visualization[END_REF]. Surface rendering algorithms first extract the surface representations from the volume data and then graphic techniques are used to render the extracted geometric primitives. Direct volume rendering algorithms get the final image from the volume data without going through an intermediate surface extraction step. In Section 4 we will show that both of the two rendering techniques can be adapted to the visualization of classified vectorial volume.

Statistical vectorial volume classification

As mentioned in the introduction section, our initial data is a vectorial volume composed of I voxels denoted by x i (i = 1, 2, . . . , I) and where each voxel is an n-dimensional vector (n the number of acquisitions). With K the number of tissues (or materials), the Gaussian mixture model assumes that each voxel is composed of K component densities mixed together with K mixing coefficients. The kth component density is denoted by p k (x i |Θ k ) governed by a parameter set Θ k ). Each component density follows a Gaussian distribution with Θ k the parameters of Gaussian, mean and standard deviation. The kth mixing coefficient is denoted by β k . Based on statistical theory, the parameters and mixing coefficients are estimated by maximum likelihood (ML) and expectation maximization (EM) algorithm is used as an optimization method so that we can get the class probabilities on each voxel according to the voxel intensity vector. But this model relies only on the intensity distributions, which will lead a misclassification on the boundaries and on inhomogeneous regions with noise. In order to solve this problem, we proposed a neighborhood weighted Gaussian mixture model by integrating the neighborhood information into the classification process according to the idea that for each voxel, the probability of the kth class should be affected by the neighbors' kth class probabilities. This neighborhood information is integrated as a weight W ik into the iterative EM scheme.

So that the final result of the segmentation is that for each voxel, we get the probability for the kth (k = 1, . . . , K) class (material) governed by the Gaussian mixture model parameters and a neighborhood weight W ik :

p(k|x i , Θ) = β k W ik p k (x i |Θ k ) ∑ K j=1 β k W jk p j (x i |Θ j ) (1)
In the rest of the paper, on one voxel, the probability of the kth material p(k|x i , Θ) will be denoted by p k .

Rendering methods

As shown in Fig. 2, after classification, we will get the material distribution information on each voxel. That is to say, for each voxel, we will know that it contains how many percent of the kth material. So the next step is to find appropriate rendering techniques to render the classified material information. In order to give a better explanation, we introduce the rendering methods through an application case.

An application case

Our application case concerns the treatment of renal cancer surgery. In this therapy, the CT uroscan is the classical clinical preoperative examination. It consists of three to four time spaced 3D acquisitions, which give complementary information about the kidney anatomy. The first acquisition is realized without injection of contrast agent and informs the surgeon about internal morphology of the patient. Just after a contrast medium injection, one or two acquisitions are taken, which reveal the renal vascular systems and the renal parenchyma and also give information about the nature and the location of the renal carcinoma. About ten minutes later on the last acquisition the renal collecting system is enhanced. The 3D/3D registration of these acquisitions has been presented in our previous work [START_REF] Tang | Intra subject 3D/3D kidney registration using local mutual information maximization[END_REF].

As an application example, we used a CT Urography taken by the GE product CTA1.0CO. This uroscan was composed by 3 acquisitions: unenhanced-, nephrographic-and excretory-phase. The pixel resolution is 0.65mm and the slice thickness is 5mm. After registration we get a database composed by a 132x119x155 voxels volume. As we introduced before, each voxel is a vector with 4 elements corresponding to the three contrast medium diffusion stage of the kidney.

The goal of our work now is the visualization of the four renal tissues (K = 4): fat, renal cortex, medulla and collecting system respectively.

After registration, according to the framework we proposed (Fig. 2), a vectorial volume is formed. The vectorial 3D volume classification method based on the neighborhood weighted Gaussian mixture model is applied and this classification step gives the material distribution on each voxel of the volume. In order to show the classification result, we compute each pixel color of the result image (Fig. 3) by the following equation:

C(x i ) = K ∑ k=1 C k p k ( 2
)
where C(x i ) is the color assigned to the ith voxel and C k is the color assigned to the kth material: red denotes fat, green denotes renal cortex, blue denotes renal medulla and white denotes collecting system.

Besides the material color C k , the user should also assign a material opacity α k to the kth material. With these material distributions and material properties, both surface rendering and volume rendering techniques can be expanded to the vectorial volume visualization in the acquisition level intermixing method.

Surface rendering method

For scalar volume, surface rendering techniques approximate a surface by some geometrical primitives, most commonly triangles, which can then be rendered using conventional graphics accelerator hardware. A surface can be defined by applying a binary decision function B(v) to the volumetric data, where B(v) evaluates to 1 if the value v is considered part of the object, and evaluates to 0 if v is part of the background. The surface is then contained in the region where B(v) changes from 0 to 1. When B(v) is a step function: B(v) = 1, ∀v ∈ v iso , where v iso is called the iso-value, the resulting surface is called the iso-surface [START_REF] Kaufman | The visualization Handbook; chap. Overview of volume rendering[END_REF]. The Marching Cubes algorithm [START_REF] Lorensen | Marching cubes: A high resolution 3D surface construction algorithm[END_REF] was developed to approximate an iso-valued surface with a triangle mesh.

This surface extraction cannot be applied on the vectorial volume directly because the vectorial iso-value is difficult to define. But the class distributions we get after applying the vectorial classification method are relatively separated, as shown in Fig. 3. Each material distribution can be treated as an independent volume. Each material distribution volume is closed to a binary volume with the value range [0, 1] (especially at the border) instead of only 1 in a binary volume. We can get the surfaces of each material and then render them in the same scene as multiple objects so that the materials can be merged in the final image.

The value range of the material distribution is [0, 1]. From Fig. 3 we can see that this data range only happens at the border and inside the object the material probabilities tend to 1, so that we choose 0.5 as the iso-value to extract the surfaces of the objects. The algorithm is summarized as follows:

1. Set the iso-value to 0.5 and extract surfaces from each material distribution volume. 2. Assign material color and transparency to the corresponding surface.

Render the surfaces in the same scene by the graphical rendering techniques

The results get from step 1) and 2) are illustrated in Fig. 4. In this figure, we do not consider fat because it's not useful for the illustration of the renal anatomical structure. We can see that the three materials are relatively independent from each other. At the border of two materials, the algorithm detects the surface for each of them respectively. That is to say, the algorithm cannot separate the surface inside and outside of the object and all of the borders are detected as surfaces. The three surfaces are rendered as three different objects with transparency properties and the final merged image is illustrated in Fig. 5. From the results, we can see that the multi-object solution is practical for this situation. The advantage of this method is that the final image can be rendered very fast (> 24 Fps) after the surface extraction. The disadvantage is that the surfaces should be extracted first and the volumes are reduced to the boundaries of materials and all the other information is lost.

Volume rendering methods

We choose to perform direct volume rendering using ray casting. The framework of its rendering process is shown in Fig. 6. As introduced before, the input of this rendering pipeline is the material probabilities on each voxel (Eq.1) and the material properties (color C k and opacity value α k ) assigned by the user. The difficulty of the expansion from scalar volume to vectorial exists in the gradient computation and the transfer function design because the sample values are material probabilities and material properties instead of scalar values.

The sample positions depend on the direction of the casted rays. The material probabilities on the sample points are achieved by tri-linear interpolation method. From the sampled material probabilities and the assigned material properties, we get the sample color C s and sample opacity α s for the composition step of the rendering pipeline. The sample color and opacity are given by a transfer function. Concerning the opacity, the transfer function can have two roles [START_REF] Levoy | Display of surfaces from volume data[END_REF]: (a) assign to a specific voxel the tissue transparency and (b) enhance the surfaces by increasing the opacities in the boundary areas and decreasing them in homogeneous regions. Different transfer functions will lead us to different direct volume rendering methods. Besides the transfer function, shading is another important issue in the rendering pipeline. Shading effects can be used to modulate the appearance of the samples. We apply the widely used Phong's shading model [START_REF] Phong | Illumination for computer generated pictures[END_REF] to calculate the shaded color. Both the calculation of transfer function and shading requires the gradient information.

Gradient estimation

Normally, for a scalar volume the gradient is approximated by intensity differences on each grid. But for the vectorial volume, the intensity differences cannot be implemented as gradient information directly. Drebin et al. [START_REF] Drebin | Volume rendering[END_REF] proposed to form first a density volume by assigning a density value to each material and then composing the densities weighted by the materials' probabilities. In his paper, a density characteristic ρ k is assigned for the kth material and then the density is formed by the following formula for each grid:

D = K ∑ k=1 ρ k p k (3)
We can see that the greater ρ k is, the more important the kth material is. If ρ k equals to zero, the kth material will disappear in the final image. The material opacity α k has the similar effect: α k = 1 implies that the material is completely opaque, and α k = 0 implies that it is completely transparent so that we can use the opacity α k to replace ρ k to form the density volume. This replacement can reduce the input parameters of the rendering pipeline so that it can simplify the user input because the two properties: opacity α k and the density ρ k can be confused. The formula is as follows:

D = K ∑ k=1 α k p k (4)
Denote the gradient vector by G, and G = (G x , G y , G z ). G x , G y and G z are the directional gradient in x, y and z axis direction respectively. The gradient vector is calculated by 3D Sobel operator from the density volume D. The normal direction is the gradient vector normalized by its magnitude |G|:

N = (G x / |G| , G y / |G| , G z / |G|) (5)

Class decision method

When taking one sample during the ray casting process, the input are the material probabilities, it is natural to consider first to make a material decision from the p k 's (k = 1, . . . , K) and then to assign the corresponding material properties to the sample point. This method is called class decision method.

We first analyze the first derivate analysis of the material probabilities. Fig. 7 shows the corresponding first order derivate of the result probabilities along one cut line (represented in white). We can see the border of two materials very clearly. At the boundary region, the positive derivate indicates that the line is going inside the material and the negative derivate indicates going out of the material. The first derivate tends to zero when the line passes inside of the materials. When we cast a ray into the volume, we calculate the first derivate along the ray. With the analysis before, we can easily distinguish the inside of the one material and the borders of materials. We can also get the information that we are going from material B to material A if the first derivate of A is positive and the first derivate of B is negative, as illustrated in Fig. 7. Denote the directional first derivate of kth material as f ′ (k), and the color and opacity of the kth material as C k and α k respectively, the sample color C s and the sample opacity α s are given by:

C s = C p α s = α p where p = arg max k f ′ (k) (6)
With this formula, the inside of the materials will be discarded because the first derivate tends to zero. From Fig. 7 we can see that the highest first derivate appears at the border of two materials which will give a high opacity according to Eq.6. This formula defines a class decision for the boundary of two materials, so that it is called class decision method.

Composed color and opacity

Unlike the class decision method, the color and opacity for the sample position can be gotten from the material probabilities directly by multiplying the color and opacity assigned to that material by the probability of each material. The sample color C s and the sample opacity α s are given by:

C s = K ∑ k=1 C k p k α s = K ∑ k=1 α k p k ( 7
)
where p k denotes the probability of the kth material and the number of materials is K.

As mentioned before, during the rendering process, the regions of interest are boundaries between materials and the transfer function is an efficient tool to express the boundaries [START_REF] Levoy | Display of surfaces from volume data[END_REF]. Eq.7 has given out the color and opacity of the sample position, but it doesn't have the ability to highlight any boundaries. The composed opacity has the same formula as the density volume (Eq.4). Fig. 8 illustrates the relationship between the sample location and the first derivative of the density volume. The first derivate is actually just the gradient magnitude [START_REF] Kindlmann | Semi-automatic generation of transfer functions for direct volume rendering[END_REF] (the gradient computed on the densities D). We can see that the gradient magnitude magnifies at the material boundaries and equals to zero at the interior of one material, which is corresponding to the separated materials' first derivative (Fig. 7).

Usually the gradient magnitude is very sensitive to the noise, but due to the efficiency of neighborhood weighted classification method, the result of the classified material is almost homogeneous. As the density volume is constructed according to the material opacities, the gradient magnitude agrees with the material opacity values. If two materials have similar opacities, the boundary between them will have small gradient magnitude; contrarily, if the two materials are quite different, the boundary between them will have a big gradient magnitude. The gradient magnitude can be considered as the "importance" of a boundary surface. If we use the gradient magnitude as an opacity mask, all the boundaries will appear in the final image according to their "importance".

The weighted opacity is described by the following formula:

α s = ( K ∑ k=1 α k p k ) • |G s | ′ (8)
where |G s | ′ is the normalized gradient magnitude at the sample position, it is given by:

|G s | ′ = |G s | -|G| min |G| max -|G| min (9)
where |G| max and |G| min denote respectively the global maximum and minimum gradient magnitude of the whole volume.

Volume rendering results

According to the framework described in Fig. 6, we did some experiment on the classified kidney volume. The input is the material probabilities on each grid and the materials' colors and opacities. The "fat" material is useless for the observer, so a totally transparent property (opacity equals to zero) is assigned to it. Fig. 9 shows the difference between the two transfer function design methods: Fig. 9(a): class decision method and Fig. 9(b): composed color and opacity. Comparing these two methods we can state the following remarks. In Fig. 9(a) and (b), the same material properties are applied. On Fig. 9(a), we can see that the class decision method can better discriminate the different material; there is less color confusion in the rendering result. But the decision making process is a 0-1 procedure so the rendering results appear discrete. In contrast, on Fig. 9(b), the final result appears more continual because the boundaries are composed of two materials. To go further, the comparison between the three results (Fig. 5 and Fig. 9(a) and (b)) is rather delicate because of the subjectivity of any visualization evaluation. As mentioned previously, the methods based on a decision (surface rendering and class decision method) give sharp boundaries and so seem to provide a more accurate visualization. However, this felt accuracy is totally subjective and depends entirely on the accuracy of the segmentation and the decision rules. Moreover, some pioneer works done in the early 90's [START_REF] Vannier | Diagnostic evaluation of three dimensional CT reconstruction methods[END_REF][START_REF] Höhne | adequacy of methods for different modalities and organs[END_REF] showed that methods based on the composition of color and opacity like direct volume rendering or our "composed color and opacity" can give visualization results with more useful information than the decision based one. This assertion is based on the fact that on direct volume rendering the data is visually analyzed and interpreted by the human psychovisual system and then some information can be perceived even if it cannot been formally extracted or described by a processing.

The computational costs of the two methods are almost the same because the difference of them only exists in the transfer function. For the volume rendering methods, the computation burden appears in the data resample part during data traversal. Every time the view direction changes, we need to recast the rays and perform the whole volume rendering process. So that comparing to the surface rendering method, low rendering speed is still a problem for volume rendering techniques. The improvement of the volume rendering speed is out of our discussion range in this paper. So that we use an eclectic method to interactively choose the appropriate visual direction: reduce resolution during the interactive process and back to resolution when the view direction is settled. The GPU based techniques [START_REF] Kruger | Acceleration techniques for GPU-based volume rendering[END_REF] can be applied to speed up volume rendering and achieve real-time rendering speed.

Conclusions

With the development of 3D/3D medical image registration methods, more and more applications meet the requirement of the visualization of spatially-aligned volumes. Most of the existing methods for multi-volume visualization are based on the intermixing of the volumes at one certain step in the rendering pipeline. In this paper, we propose an acquisition level intermixing method, in which the intermixing step appears at the beginning of the rendering process.

First, the individual volumes are combined into a vector volume. The analysis is performed on this vectorial volume instead of several separated scalar volumes.

Then we performed a statistical vectorial volume classification method based on the Gaussian mixture model. But in order to integrate more information into the classification process, we propose a neighborhood weighted method for the analysis of the vectorial volume. The basic ideas of this method are that the voxels' intensity vectors distribution can be modeled by a mixture of Gaussians and that the classes distributions on each voxel are affected by its neighbors' class probability distributions. This neighborhood information is integrated into the classification process by amending the voxel' s class distributions at each iteration step.

Then several rendering techniques are applied on the classification result. Both of the surface rendering and direct volume rendering techniques can be adapted to this situation. Two kinds of transfer design methods for direct volume rendering (class decision method and composed color and opacity) are implemented and compared. Similar to the single volume visualization techniques, the volume rendering method takes longer time to compute the final image because it requires to resample the whole dataset each time when the view direction changes. The rendering results of the two methods are given and the comparison of them is discussed.

From this framework, we can see that the rendering results rely much on the classification result because the final rendering techniques are applied on the classification result. Comparing the traditional multi-volume visualization methods, in this framework, the rendering techniques play less important role. We can see that both surface rendering and volume rendering techniques can work well if the classification results are good. So that the key step of this framework becomes the classification instead of rendering, which should be further worked on.

Multi-volume rendering framework

Figure 2 :

 2 Figure 2: Multi-volume rendering pipeline

Figure 3 :Figure 4 :

 34 Figure 3: Registered slices from uro CT scans: a) unenhanced-, b) nephrographic-and c) excretory-phase. d) Classification result: fat (red), renal cortex (green), renal medulla (blue) and collecting system (white)

Figure 5 : 21 Figure 6 :

 5216 Figure 5: Merged scene rendered by semi-transparent surface rendering technique

Figure 7 :Figure 8 :

 78 Figure 7: Probability first order derivate along one cut line. The circled region means the line goes from material B (red part) to material A (green part)

Figure 9 :

 9 Figure 9: Rendering results with the same material properties. (a): Class decision; (b): Composed color and opacity

List of Figures


Dainis Zeps
email: dainis.zeps@lumii.lv

published or not. The documents may come

4-critical wheel graphs of higher order

We are using terminology from [START_REF] Bojan | Graphs on Surfaces[END_REF][START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of freeplanar graphs[END_REF][START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF]. In [START_REF] Antonio | On Hadwiger conjecture[END_REF] Jose Antonio Martin Hernandez suggested to use the theory of free minor closed classes of graphs in trying to prove the Hadwiger conjecture. We present here some examination in this direction.

For k > 1, let us call Hadwiger class of order k H k = N 0 (K k ), i.e. the one generated by the forbidden graph K k . Then, following many researchers, Hadwiger conjecture may be formulated as follows: In the Hadwiger class of order k > 1 graphs are k -1-colorable. For k < 7 this assumption is proved to be true, but other cases remain hypothetical.

In [START_REF] Antonio | On Hadwiger conjecture[END_REF] J.A.M. suggested to examine whether k-critical graphs belong to the class F ree(H k+1 ) [START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of freeplanar graphs[END_REF][START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF]. [Graph belonging to F ree(H k+1 ) we call free-Hadwiger graph.] Following Kratochvil theorem [START_REF] Kratochvíl | About minor closed classes and the generalization of the notion of freeplanar graphs[END_REF][START_REF] Zeps | Free Minor Closed Classes and the Kuratowski Theorem[END_REF], F ree(H k+1 ) would be the class without minors K - k+1 and K ⊙ k+1 , i.e. K k+1 without edge or with split vertex. It is easy to see that this assumption works for cases k < 4. Further, we present sequence of 4-critical graphs, G 9 (fig. 1), G 7 (fig. 2), G 5 (fig. 3), G 3 (fig. 4), where none of the graphs belong to the class F ree(H 5 ), i.e. they are not free-Hadwiger graphs because they all contain the minor K - 5 . Thus, the suggestion in [START_REF] Antonio | On Hadwiger conjecture[END_REF], at least for case k = 5, could be declined. Nevertheless, we find it useful that help us to forward some new conjectures. These newly discovered 4-critical graphs may be arranged in a sequence where each of them is a minor of the following, i.e.,

G 3 ≺ G 5 ≺ G 7 ≺ G 9 .
Indeed, it is easy to see that G 7 may be received from G 9 by contracting two successive edges on the sides. The same applies to the inclusive pairs G 5 ≺ G 7 and G 3 ≺ G 5 .

This sequence may be replenished with wheel graphs W i , i = 3, 5, 7, 9, as minors of these graphs. See what we get in fig. 5. We use here almost trivial fact that W i ≺ G i for i = 3, 5, 7, 9.

All graphs G i , i >= 3 may be considered as first order higher wheels. All they have as minor K - 5 . Thus, they all have minor brackets < K - 5 , K 5 > and < K - 3,3 , K 3,3 > where minor bracket for graph G we define as a pair of graphs < a, b > where a is minor of G, but b isn't. On the other side, ordinary [zero order]wheels W i , i > 4 have minor brackets < W 4 , K - 5 > and < C + 6 , K - 3,3 >. Besides, all these minor brackets are simple, i.e., tightest possible ones in the very natural sense. Moreover, higher than first order wheels should have the same minor brackets as first order wheels.

Further, we raise the question 1) are the only 4-critical graphs that belong to F ree(H 5 ), [zero order] wheel graphs and wheels with split edges [see fig. 6], i.e. 2) are all higher

¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 3 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 2
Figure 1: Example of 4-critical graph that is not free-planar, not even free-Hadwiger graph. This is a first order higher wheel G 9 .

order wheels non-free Hadwiger graphs? Thus, does there exist a critical free-Hadwiger non-free-planar 4-critical graph? Besides, we make some judgements concerning graph G 3 . It is easy to see that G 3 is the 'cube with one corner cut off' graph. We could ask about higher order cube graphs, what we could get after cutting off some of cube's corners? For 4-cube, it is rather easy to see that cutting off corners [one, two, three] can't give any 5-critical graph. See, for example, one case of 4-cube graph with two corners of the cube cut off on fig. 7. Judging from the 4-cube graph experience, we conjecture that none of the higher order cube graphs with cut off corners of the cube can be a critical graph.

¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 3 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 2
Figure 2: First order higher wheel G 7 . It is obtained from G 9 by contracting two of its side edges.

§ ¦ ¤ ¥ 4 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 3 § ¦ ¤ ¥
1 Figure 3: First order higher wheel G 5 . It is obtained from G 7 by contracting two of its side edges.

§ ¦ ¤ ¥ 1 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 3 § ¦ ¤ ¥ 3 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 2 § ¦ ¤ ¥
1 Figure 4: First order minimal possible higher wheel G 3 . It is obtained from G 5 by contracting two of its side edges. It is minimal in the sequence of these graphs obtained by contractions giving graph distinct from K 4 . Next graph by contractions should be K 4 . G 3 has minor K - 5 , thus, it is not Free-Hadwiger graph. Besides, it is easy to see that G 3 can be imagined as the cube with one corner cut off.

G 9 G 7 G 5 G 3 W 9 W 7 W 5 W 3 = K 4 s + ? ? ? ? q 9
) Figure 5: Lattice of 4-critical graphs, where arrows show reductions of graphs by contractions of edges. In place of G 9 may stand any G i with odd i. Any next column in the lattice would be wheel graphs with higher order. §

¦ ¤ ¥ 1 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 1 § ¦ ¤ ¥ 3 § ¦ ¤ ¥ 2 § ¦ ¤ ¥ 4 § ¦ ¤ ¥ 3

Figure 6 : 4 -Figure 7 : 4 -

 6474 Figure 6: 4-critical graph obtained from W 5 by spitting of an edge [or spoke of the wheel].The operation of the edge splitting preserving 4-criticality is easy to be generalized.