N Ducros

C D'andrea

A Bassi

F Peyrin

Fluorescence diffuse optical tomography: time-resolved versus continuous-wave in the reflectance configuration

Keywords: Fluorescence diffuse optical tomography, time-resolved approach, turbid media, 3D reconstructions, reflectance, transmittance

Context and objectives-In the context of fluorescence diffuse optical tomography, in the transmittance configuration, the time-resolved approach was shown to improve the reconstruction quality compared to the continuous-wave approach but this improvement seriously decreases in the presence of noise. In this paper the additional value of time-resolved approach is investigated in the reflectance configuration. Material and methods-A comparative study between time-resolved and continuous-wave reconstructions is provided in the reflectance configuration. Reconstructions are performed from synthetic measurements in a slab geometry assuming Poisson noise statistics.

Results and discussion-In the reflectance configuration, the reconstruction quality, expressed in terms of the global reconstruction error or in terms of the localization and quantification of a local inclusion, is shown to be sensibly higher when the time-resolved approach is considered rather than the continuous-wave one. This behavior is observed for maximum numbers of detected photons as low as 10 4 . Conclusion-In the reflectance configuration, considering realistic level of signal, the time-resolved approach is shown to outperform continuous-wave approach.

Résumé

Contexte et objectif -Dans le cadre de la tomographie optique diffuse de fluorescence, l'approche temporelle permet une amélioration de la qualité de reconstruction par rapport à l'approche en continu plus classique. Cette amélioration reste cependant limitée en présence de bruit. Cette observation vaut lorsque le milieu est étudié en transmission. L'objectif du présent article est d'évaluer l'apport du temporel par rapport au continu lorsque le milieu est étudié en réflexion. Matériel et méthodes -Nous présentons une étude comparative entre l'approche temporelle et l'approche continue pour une acquisition en réflexion. Les reconstruction sont réalisées à partir de mesures simulées dans un milieu parallélépipédique, considérant un bruit de Poisson. Résultats et discussion -En réflexion, la qualité de reconstruction est sensiblement meilleure pour l'approche temporelle que pour l'approche continue, que la qualité de reconstruction soit exprimée en termes d'erreur de reconstruction globale ou bien en termes de localisation et de quantification d'une inclusion locale. Ce comportement est observé pour un nombre maximum de photons détecté se réduisant jusqu'à 10 4 . Conclusion-Dans des scénarios réalistes, pour lesquels le nombre maximum de photons détectés est de l'ordre de 10 6 , l'approche temporelle surpasse en performance l'approche en continu pour une acquisition en réflexion, alors que les deux approches présentent des prestations similaires pour une acquisition en transmission.

Mots-clefs : Tomographie optique de fluorescence, approche temporelle, milieux diffusants, reconstructions 3D, réflection, transmission.

Introduction

In the near-infrared region (NIR), the absorption of biological tissues is low enough to allow photons for propagating several centimeters. This enables to localize optical heterogeneities embedded in thick media [START_REF] Yodh | Spectroscopy and imaging with diffusing light[END_REF]. By employing a setup comprising a set of external light sources and detectors, the optical properties of a tissue can be recovered by applying the principles of tomography. In this context, the aim of diffuse optical tomography (DOT) is to provide three-dimensional (3-D) maps of the absorption and scattering coefficients of a tissue [START_REF] Boas | Imaging the body with diffuse optical tomography[END_REF][START_REF] Gibson | Recent advances in diffuse optical imaging[END_REF]. More recently, the development of NIR fluorescent markers such as Indocyanine Green (ICG) has led to a novel technique, called fluorescence DOT (FDOT) or fluorescence molecular tomography (FMT), which is capable of determining the 3-D local concentrations of fluorescent markers [START_REF] Paithankar | Imaging of fluorescent yield and lifetime from multiply scattered light reemitted from random media[END_REF][START_REF] Ntziachristos | Fluorescence molecular tomography resolves protease activity in vivo[END_REF][START_REF] Hervé | Noncontact fluorescence diffuse optical tomography of heterogeneous media[END_REF]. New markers can tag specific proteins, acting as molecular probes. The so-called active probes are designed to exhibit fluorescence only in the vicinity of an enzyme cleaving a peptide [START_REF] Bremer | Optical-based molecular imaging: contrast agents and potential medical applications[END_REF]. The development of quantum dots is also promising to enlarge the range of fluorescent markers [START_REF] Medintz | Quantum dot bioconjugates for imaging, labelling and sensing[END_REF]. In this context, FDOT can play a significant role in small-animal imaging as well as in drug discovery.

FDOT approaches can be broadly classified into three groups that differ in the type of excitation and detection. Continuouswave (CW) FDOT is based on the measurement of the attenuation of a steady state excitation light [START_REF] Ntziachristos | Diffuse optical tomography of highly heterogeneous media[END_REF][START_REF] Roy | Fluorescence-enhanced optical tomography using referenced measurements of heterogeneous media[END_REF][START_REF] Graves | A submillimeter resolution fluorescence molecular imaging system for small animal imaging[END_REF][START_REF] Koenig | In vivo mice lung tumor followup with fluorescence diffuse optical tomography[END_REF]. Frequency-domain (FD) FDOT is based on the measurement of the phase and demodulation of an amplitude-modulated excitation [START_REF] Yu | Frequencydomain multiplexing system for in vivo diffuse light measurements of rapid cerebral hemodynamics[END_REF]. Time-resolved (TR) FDOT exploits the measurement of the temporal distortion of an excitation light pulse [START_REF] Lam | Time domain fluorescent diffuse optical tomography: analytical expressions[END_REF][START_REF] Liebert | Non-invasive detection of fluorescence from exogenous chromophores in the adult human brain[END_REF][START_REF] Gao | A linear, featured-data scheme for image reconstruction in time-domain fluorescence molecular tomography[END_REF][START_REF] Laidevant | Analytical method for localizing a fluorescent inclusion in a turbid medium[END_REF][START_REF] Riley | Choice of data types in time resolved fluorescence enhanced diffuse optical tomography[END_REF][START_REF] Ducros | A comprehensive study of the use of temporal moments in time-resolved diffuse optical tomography: part i. theoretical material[END_REF][START_REF] Ducros | A comprehensive study of the use of temporal moments in time-resolved diffuse optical tomography: part ii. three-dimensional reconstructions[END_REF]. FD and TR provide significant advantages with respect to CW approach. In particular, they allow to separate absorption and diffusion contributions [START_REF] Arridge | Nonuniqueness in diffusion-based optical tomography[END_REF], to derive fluorescence lifetime [START_REF] Kumar | A time domain fluorescence tomography system for small animal imaging[END_REF] and more generally to provide a data set with a higher information content which can lead to better reconstruction of deeply-embedded markers [START_REF] Selb | Linear 3d reconstruction of time-domain diffuse optical imaging differential data: improved depth localization and lateral resolution[END_REF]. This last aspect, is particularly relevant for TR measurements, which contain any modulation frequency, while FD measurements can only be performed, in practice, for few of them.

Despite these remarks, CW approaches are the most frequently used to recover the marker concentration. This is partially due to instrumentation concerns, in fact, while the CW approaches are inexpensive and easy to develop, the FD and TR FDOT are more costly and requires careful handling. Moreover, this can be explained by a lack of comparative study that could set the domain of interest of both techniques. Although CW and TR are both long-standing approaches in FDOT, few studies have been dedicated to compare their reconstruction performances. In a recent work, we showed that the TR approach outperforms the CW approach in situations when a sufficient number of photons is collected [START_REF] Ducros | A time-domain wavelet-based approach for fluorescence diffuse optical tomography[END_REF]. However, this study was restricted to the transmittance configuration, i.e. for a medium lying between the sources and the detectors. Here, the performance of CW and TR FDOT are evaluated in the reflectance configuration, i.e. for sources and detectors lying on the same side of the medium. The reflectance configuration is quite relevant because in many applications (e.g. tissue oxymetry, brain function imaging and prostate tomography) it represents the only available geometry. Moreover, reflectance geometry can better exploit the information content of TR data set, because the information of the inclusion depth is encoded into the time of flight [START_REF] Laidevant | Analytical method for localizing a fluorescent inclusion in a turbid medium[END_REF].

The aim of this paper is to compare the quality of reconstruction in transmission and reflexion time-resolved acquisitions.

In section 2 we introduce the basic theory of light propagation as well as the modeling of the forward and inverse problems. Section 3 describes the methods used for the simulation of TR measurements and for reconstructions. Finally section 4 presents the results.

Theory

Light propagation

Light propagation within biological tissues is dominated by absorption and scattering. Such media are commonly referred to as turbid media. A variety of theoretical models accounting for the propagation of light within such media have been developed. Among them the deterministic models are based on the resolution of a partial derivative equation deriving from the radiative transfer equation (see Sec. 3 of [START_REF] Arridge | Optical tomography: forward and inverse problems[END_REF] for an overview). Although more general models are available, the light propagation in FDOT is classically assumed to follow the diffusion equation. Within this framework, the propagation operator acting on the photon density photons φ at position r and time t is given by:

P = -∇ 1 3µ s ∇ + 1 ν ∂ ∂t + µ a (1)
where µ a is the absorption coefficient, µ s is the reduced scattering coefficient, and ν is the speed of light within the medium.

FDOT equations

The principle of FDOT is depicted in Fig. 1. After illumination of the medium at position s, the photon density φ x propagates at wavelength λ x within the medium. It is absorbed by the fluorescent markers that act as secondary sources by re-emitting light at a higher wavelength λ f > λ x . Mathematically, this leads to the following system of coupled equations [START_REF] Patterson | Mathematical-model for time-resolved and frequency-domain fluorescence spectroscopy in biological tissue[END_REF]:

Pφ x (r, t) = δ(r -s, t), (2a) Pφ m (r, t) = [φ x (r, t) p(t)] c(r). ( 2b
)
Where φ x (r, t) and φ m (r, t) are respectively the photon density at wavelength λ x and λ m , and c(r) is the local concentration of the fluorescent markers. Equation (2a) describes the propagation of light at wavelength λ x , while Eq. (2b) describes the propagation of light at wavelength λ m . Note that the source term of Eq. (2b) is the temporal convolution of the excitation photon density and pulse response of the fluorescence marker p. The latter is given by where τ is the fluorescence lifetime of the marker, η its efficiency, and c(r) its local concentration. As recommended in [START_REF] Ducros | Approximations of the measurable quantity in diffuse optical problems: theoretical analysis of model deviations[END_REF], the photons density φ m is assumed to be the quantity measured by the acquisition set-up.

p(t) = η τ exp - t τ dV, (3)

Forward problems

Let {s i }, i ∈ {1, .., I} be the set of source points and {d j }, j ∈ {1, .., J} the set of detection points. The medium is discretized into N voxels centered in {r n }. We note m i, j the quantity of light detected at position d j after illumination at position s i and c n the marker concentration into the voxel centered in r n . FDOT is an intrinsically linear problem of the form [START_REF] Patterson | Mathematical-model for time-resolved and frequency-domain fluorescence spectroscopy in biological tissue[END_REF]

m(t) = W(t)c, (4)
where c = [c 1 , .., c N ] T is the marker concentration vector, m(t) = [m 1,1 (t), m 1,2 (t), .., m I,J (t)] T is the measurement vector, and W(t) is the weight matrix. The entries of W(t) for each couple of source s i and detector d j are given by

w i, j n (t) = g(s i , r n , t) p(t) g(d j , r n , t). ( 5
)
where g stands for the Green's functions of the propagation operator P.

The use of extended source patterns together with extended detection patterns have also been introduced [START_REF] Bassi | Temporal propagation of spatial information in turbid media[END_REF][START_REF] Lukic | Optical tomography with structured illumination[END_REF][START_REF] D'andrea | Fast 3d optical reconstruction in turbid media using spatially modulated light[END_REF][START_REF] Ducros | Full-wavelet approach for fluorescence diffuse optical tomography with structured illumination[END_REF].However, the framework defined in Eq. ( 4) and Eq. ( 5) remains identical.

Inverse problem

The inverse problem, which consists in finding c from Eq. ( 4), being ill-posed, a Tikhonov regularization scheme is used to solve it. For a forward problem of the form y = Ac, the following Tikhonov solution c * is considered

c * = arg min c ||y -Ac|| 2 Q + α||c|| 2 , ( 6
)
where α is the regularization parameter. To enable comparison between solutions obtained from different system matrix A and measurement vector y, the regularization parameter is chosen so as to set the variability of the solution to a prescribed value, i.e few percents (details are provided in [START_REF] Ducros | A comprehensive study of the use of temporal moments in time-resolved diffuse optical tomography: part i. theoretical material[END_REF]).

Method

Numerical phantom

We consider the parallelepiped of size 5×2.5×1.8 cm 3 depicted in Fig. 2a. The absorption coefficient µ a is set to 0.1 cm -1 , the scattering coefficient µ s to 10 cm -1 , and the refractive index n to 1.4. The fluorescent marker we considered has a lifetime τ of 0.7 ns (Alexa 750). The markers concentrate to form three inclusions centered in r 1 = [0.9, 0.5, 0.5] cm, r 2 = [2.5, 1.1, 0.9] cm, and r 3 = [4.1, 1.9, 1.3] cm. At the center of each inclusion the marker concentration is set to 1 µM. Away from the center the marker concentration decays gradually to 0 µM.

Source-detector configurations

The medium is illuminated in S = 14 source points, and light is collected at D = 13 detection points. The sources and detectors are uniformly arranged onto two grids of size 4.2×1.8 cm 2 as depicted in Fig. 2b.

In this study, two source-detector configurations are investigated, namely the transmittance and the reflectance configurations. In the transmittance configuration, sources and detectors are arranged into two distinct planes that surround the medium. In this case, the sources are placed in the plane z = 0 cm and the detectors in the plane z = 1.8 cm. In the reflectance configuration, however, sources and detectors are arranged into the same plane, here the plane z = 0 cm.

Computation of the forward problem

The computation of the forward problem consists in the calculation of the weight matrix W(t) whose entries are given by Eq. ( 5). The required Green's functions of Eq. ( 1) are obtained by means of the finite element Matlab package TOAST [32]. At this step, a grid of 24225 voxels of size 0.1 × 0.1 × 0.1 cm 3 is considered and 128 time samples evenly distributed on the range [0 ; 5.12] ns are calculated. Such fine grids are necessary to ensure the accuracy of the weight matrix. However, for the rest of the computation, a space grid of 5100 voxels of size 0.2 × 0.2 × 0.1 cm 3 together with a time grid of 16 time windows of width 160 ps ranging from t = 0.12 ns to t = 2.64 ns are considered.

As given by Eq. ( 4), the numerical measurements m(t) are obtained multiplying the weight matrix W(t) by the phantom concentration vector c p .

Instrument response function

In order to simulate realistic conditions, the measurements are convolved by the instrument response function accounting for the experimental laser and detector. The following transformations are thus considered:

m i, j (t) ← m i, j (t) f (t), (7)
w i, j n (t) ← w i, j n (t) f (t), ( 8
)
where f is the instrument response function accounting for the instrument temporal jitter. We considered the experimental instrument response function represented in Fig. 3. This stateof-the-art system consists of a mode-locked Ti:sapphire laser (3900, Spectra Physics, USA) pumped by an argon laser (Innova 200, Coherent, USA) and a cooled micro-channel plate photomultiplier (R1564U, Hamamatsu, Japan) that offers good temporal resolution (<50 ps, FWHM) [START_REF] Pifferi | Fully automated time domain spectrometer for the absorption and scattering characterization of diffusive media[END_REF].

Noise model

The measurement vector and weight matrix are both multiplied by the same constant allowing to account for the experiment integration time -the longer the integration time, the larger the number of detected photons. Here the multiplicative constant, noted κ, is chosen so as to set the maximum number of detected photons N max to a prescribed value [START_REF] Ducros | A time-domain wavelet-based approach for fluorescence diffuse optical tomography[END_REF]:

max i, j κm i, j = N max . (9)
The measurements are finally corrupted by Poisson noise. Mathematically, the noisy version m i, j of the noiseless measurement m i, j is given by m i, j = P(λ = m i, j ), [START_REF] Roy | Fluorescence-enhanced optical tomography using referenced measurements of heterogeneous media[END_REF] where P(λ) denotes a Poisson distribution of mean λ. For any noiseless measurement m i, j , a set 50 different noise realizations m i, j is computed.

Reconstruction approach

Reconstructions are performed from both CW and TR measurements, leading to CW reconstructed concentration c * cw and the TR reconstructed concentration c * tr . More precisely, c * cw is obtained by inverting the CW forward model:

m cw = W cw c, (11a)
where m cw is the CW measurement vector and W cw is the CW weight matrix. Equation (11a) derives from the integration of Eq. ( 4) over time, which leads to m cw = m(t) dt and W cw = W(t) dt. The TR reconstructed concentration c * tr results from the inversion of the TR forward model:

m tr = W tr c, (11b)
where m tr is the TR measurement vector and W tr is the TR weight matrix. Equation ( 11b) is obtained by concatenating the Eq. ( 4) evaluated at different times {t 1 , .., t K }. This operation leads to m tr = [m(t 1 ), .., m(t K )] T and W tr = [W(t 1 ), .., W(t K )] T .

Performance metrics

To quantify the reconstruction quality, we consider one global performance metric and two local ones. The two local performance metrics depend on the position the centers r * i of the reconstructed inclusions. The center positions r * i are determined searching the local maximum of c * closest to the groundtruth inclusion position r i . This simple approach turns out accurate enough not to involve segmentation method.

The reconstruction error E. This global metric measures the distance between the phantom concentration c p and the reconstructed concentration c * . It is defined by

E = c * -c p 2 2 c p 2 2 . ( 12
)
The reconstruction quality increases as the reconstruction error tends to 0.

Localization error L. This criterion assesses the ability of localizing an inclusion. It is defined as the distance between the center of the phantom inclusion r i and the center of the reconstructed inclusion r * i . Mathematically:

L = r * i -r i 2 . ( 13
)
The reconstruction quality increases as the localization error tends to 0.

Quantification Q. This criterion assesses the ability of quantifying the concentration of an inclusion. It is defined as the ratio between the concentration of the reconstructed inclusion and the concentration of the phantom inclusion, i.e.

Q = c * (r * i ) c p (r i ) . (14)
The reconstruction quality increases as the quantification tends to 1.

Results and discussion

In this section, we present reconstructions and their associated performance metrics for different values of the maximum number of detected photons N max . The larger N max is -in practice the longer the integration time, the better the signal-to-noise ratio. The influence of N max is of particular interest since the reconstruction quality mainly depends on this parameter [START_REF] Ducros | A time-domain wavelet-based approach for fluorescence diffuse optical tomography[END_REF].

First, a visual comparison between CW and TR reconstructions for both transmittance and reflectance configurations is provided in Fig. 4. In this figure, the maximum number of detected photons N max is set to 10 6 photons, which roughly corresponds to the largest value obtainable in experimental scenarios. Comparing the first row and the second row of Fig. 4, it can be seen that the reflectance configuration leads to reconstructions of lower quality than those in the transmittance configuration. When the transmittance configuration is considered the CW and the TR reconstructions are visually indistinguishable and, as a result, the TR information is of limited interested. This behavior has already been reported in [START_REF] Ducros | A time-domain wavelet-based approach for fluorescence diffuse optical tomography[END_REF]. As pointed out in the introduction, however, the reflectance configuration can be the only one available for some applications, as for instance in brain function imaging, prostate tomography, or tissue oxymetry. In this configuration, on the contrary, the TR reconstruction quality is observed to outperform the CW reconstruction quality. Indeed, the inclusions 1 and 2 seem to be better localized and quantified. The inclusion 3, which is not present in the CW reconstruction, is brought to light using the TR approach.

To test these visual findings, we evaluated a global performance metric, namely the reconstruction error E defined by Eq. ( 12). Its value is reported in Fig. 5 as a function of the maximum number of detected photons N max ranging from 10 3 to 10 7 photons. Both reflectance and transmittance configurations are investigated. Whatever the source-detector configuration, the reconstruction error is found to decrease for increasing N max , illustrating the improvement of the reconstruction quality when measurements with larger signal-to-noise ratio are considered. For a given N max , the reconstruction error confirms the previous observations. In the transmittance configuration, the CW and TR reconstruction errors are very close in value and almost identical for N max < 10 5 photons. On the contrary, the reconstructions in the reflectance configuration show that TR reconstruction error is significantly smaller than the CW reconstruction error even for N max as small as 3.10 4 photons.

Last, we evaluate for each of the three inclusions two local metrics, namely the localization error L and the quantification Q defined in Eq. ( 13) and Eq. ( 14), respectively. The results in the transmittance configuration are depicted in Fig. 6 while the reflectance results are depicted in Fig. 7. As far as the transmittance is concerned, the TR quantification and localization error slightly differ from the CW quantification and localization error. The benefit of the TR approach is limited to the quantification, for N max over 10 5 photons, and in areas close to the source or detector planes (see inclusion 1 and 3). For N max < 10 5 , photons difference between CW and TR for both localization error and quantification are hardly noticeable, which is in agreement with our previous findings as well as those reported in [START_REF] Ducros | A time-domain wavelet-based approach for fluorescence diffuse optical tomography[END_REF]. As far as the reflectance is concerned, both localization error and quantification are improved when the TR approach is used rather than the CW approach. It can be seen that the TR quantification is overestimated in surface (see of inclusion 1) for large N max . Yet, for all the other cases, the quantification of the CW approach is lower than that of the TR approach (see inclusions 2 and 3, notably). The same trend is observed with regard to the localization error of the three inclusions, which is always found to be better in the TR case than in the CW base. The observed oscillations in the value of the localization error in Fig. 6 can be mainly explained by numerical errors occurring when the localization error tends to zero. A substantial improvement is observed for inclusion 3, which is located far away from the source-detector plane in a zone where the CW exhibits poor performances.

Conclusion

In this work we addressed the problem of fluorescence diffuse optical tomography and we compared the performances of the time-resolved and continuous-wave approaches. Three different merit parameters for the quality of the reconstructions, namely reconstruction error, localization error and quantification, have been regarded. We observed that the reconstruction quality of a fluorescent inclusion embedded in a highly scattering media can be improved employing the time-resolved approach, even in realistic scenarios for which measurement noise and limited dynamic range are considered. Therefore our results indicate that the time-resolved information is more beneficial in the reflectance configuration than in the transmittance configuration. ). The localization error L is represented in the top row, the quantification Q in the bottom row. Inclusion 1 is considered in the left-hand column, inclusion 2 in the middle column, inclusion 3 in the right-hand column.

Figure 1 :

 1 Figure 1: Principle of FDOT. a) The medium is excited by at position s by a pulse of light at wavelength λ x . b) Fluorescence light is emitted at wavelength λ f > λ x by a fluorophore located at position r.

Figure 2 :

 2 Figure 2: a) Numerical phantom. The red dots represent the source points, the blue rings the detector points, and the thin black dots the mesh nodes (for clarity, only those at the border are represented). The optical properties of the medium are the following: µ a = 0.1 cm -1 , µ s = 10 cm -1 , n = 1.4, and τ = 0.3 ns. b) Source-detector configuration. On top is represented the reflectance configuration, in the bottom the transmittance configuration.

Figure 3 :

 3 Figure3: Instrument response function. The system consists of a mode-locked Ti:sapphire laser pumped by an argon laser and a cooled micro-channel plate photomultiplier[START_REF] Pifferi | Fully automated time domain spectrometer for the absorption and scattering characterization of diffusive media[END_REF].

Figure 4 :

 4 Figure 4: 3-D reconstructed marker concentration, for the CW modality (left-hand column) and the TR modality (right-hand column), in both the reflectance (bottom row) and the transmittance (top row) configurations. N max is set to 10 6 photons.

Figure 5 :

 5 Figure 5: Reconstruction error E as a function of the maximum number of detected photons for both CW modality (blue line marked with ) and TR modality (green line marked with ). Results for the transmittance configuration are plotted on the left while results for the reflectance configuration are plotted on the right.

Figure 6 :

 6 Figure 6: Reconstruction performances in the transmittance configuration for both CW modality (blue line marked with ) and TR modality (green line marked with ). The localization error L is represented in the top row, the quantification Q in the bottom row. Inclusion 1 is considered in the left-hand column, inclusion 2 in the middle column, inclusion 3 in the right-hand column.

Figure 7 :

 7 Figure 7: Reconstruction performances in the reflectance configuration for both CW modality (blue line marked with ) and TR modality (green line marked with). The localization error L is represented in the top row, the quantification Q in the bottom row. Inclusion 1 is considered in the left-hand column, inclusion 2 in the middle column, inclusion 3 in the right-hand column.

Acknowledgment

This work was supported in part by CARIPLO Foundation (grant 2009-2626).

Conflicts of interest statement

There is no conflict of interest.


Jean-Daniel Fekete
email: fekete@lri.frplaisant@cs.umd.edu

Catherine Plaisant

Interactive Information Visualization of a Million Items

Existing information visualization techniques are usually limited to the display of a few thousand items. This article describes new interactive techniques capable of handling a million items (effectively visible and manageable on screen). We evaluate the use of hardware-based techniques available with newer graphics cards, as well as new animation techniques and non-standard graphical features such as stereovision and overlap count.

These techniques have been applied to two popular information visualizations: treemaps and scatter plot diagrams; but are generic enough to be applied to other 2D representations as well.

Introduction

Information visualization is a research domain aiming at supporting discovery and analysis of data through visual exploration. Made popular by Edward R. Tufte's books [START_REF] Tufte | The Visual Display of Quantitative Information[END_REF], its principle is to map the attributes of an abstract data structure to visual attributes such as Cartesian position, color and size, and to display the mapping. This is in contrast with scientific visualization, which deals with data that usually has an intrinsic representation.

Popular mappings exist for a large range of data structures such as tables, trees, graphs as well as more specialized ones. During the last decade, dozens of new visualization techniques were invented, such as treemaps [START_REF] Johnson | Tree-maps: A space-filling approach to the visualization of hierarchical information structures[END_REF] or ConeTrees [START_REF] Robertson | Cone Trees: animated 3D visualizations of hierarchical information[END_REF]. Most techniques have a strong interaction component allowing users to rapidly explore the data [START_REF] Ahlberg | Visual Information Seeking: Tight Coupling of Dynamic Query Filters with Starfield Display[END_REF][START_REF] Lamping | A focus+context technique based on hyperbolic geometry for visualizing large hierarchies[END_REF]. Commercial products are now available and successfully used in a wide array of applications domains such as oil production or drug discovery [START_REF] Card | Readings in Information Visualization: Using Vision to Think[END_REF].

Yet, little is known about the limits of information visualization techniques in term of scalability. Current systems tend to avoid the problem by relying on aggregation or sampling techniques that limit the number of visible items to about 10 4 and occasionally 10 5 at the cost of interaction. Our goal is to display and manage a million items. By item, we mean atomic object displayed as a distinguishable contiguous area using one visualization technique. For systems displaying the same object several times according to different attributes, we count each instance as a different item. Management of the items involves maintaining continuous interaction and smooth animation. Scalability issues are important in information visualization because of the proliferation of large data sets requiring human-supervised analysis, but maximizing the number of items visible for a given display size is also a challenge for designers of visualizations on small devices like PDAs.

In this article, we describe new techniques to visualize a million items using standard displays. These techniques rely on:

• hardware acceleration to achieve the speed required for interaction and animation;

• non-standard visual attributes such as stereovision or synthetic overlap count to enhance visualization;

• animation and interaction while replaying recorded visualization configurations (views) using time multiplexing techniques to analyze the data across several views and mappings without losing context.

We have applied these techniques to treemaps (Figure 1) and scatter plots. Treemaps are representative of space filling visualizations whereas scatter plots are representative of visualizations with overlapping, but the techniques we describe here are general enough to be applied to other kinds of 2D visualizations.

Previous Work

Visualizing one million items is a problem of visualization, perception and interaction.

Visualization of Large Data Sets

Existing information visualization techniques are usually limited to the display of a few thousand items or avoid the problem of visualizing large number of items by using aggregation, sampling and extracting, or by not managing occlusion and overlapping.

Among the popular techniques is the use of scatter plots connected to interactive controls such as in Dynamic Queries [START_REF] Ahlberg | Visual Information Seeking: Tight Coupling of Dynamic Query Filters with Starfield Display[END_REF]. Scatter plots visualize multidimensional data by mapping two dimensions to the X and Y coordinates and mapping other dimensions to visual attributes such as color, width, height, orientation, intensity or shape. When augmenting the number of visible data in scatter plots, overlapping cannot be avoided and is not managed at all by current systems.

Avoiding overlaps, space-filling techniques such as treemaps [START_REF] Johnson | Tree-maps: A space-filling approach to the visualization of hierarchical information structures[END_REF], VisDB [START_REF] Keim | Visual Exploration of Large Data Sets Communications of the ACM[END_REF] and SeeSoft [START_REF] Eick | SeeSoft-A Tool for Visualizing Line Oriented Software Statistics[END_REF], offer a high density of information. They use special layout algorithms to fill up all the screen pixels, thus requiring redrawing all these pixels when a visualization parameter changes. Current implementations of these systems are limited mostly by the redraw time and to a smaller extent by the time to compute the layout. VisDB handles 50,000 items; SeeSoft 50,000 lines of code and Microsoft NetScan project can render thousands of newsgroups in a treemap.

Treemaps are visualization techniques for trees. They were introduced by Shneiderman [13] and several variations have been created which improve their readability. The initial "slice and dice" algorithm is simple: it uses the entire screen to represent the tree root and its children. Each child of the root is given a horizontal or vertical strip of size proportional to the cumulative size of its descendents. The process is repeated recursively, flipping horizontal and vertical strips at each hierarchy level. Some variants try to avoid long thin rectangles and allocate strips containing sub-trees as square as possible [START_REF] Bederson | Ordered and Quantum Treemaps: Making Effective Use of 2D Space to Display Hierarchies[END_REF].

Hybrid techniques such as Mihalisin Associates System can visualize data sets ranging from 10 4 to 10 8 data points [START_REF] Keim | Visual Exploration of Large Data Sets Communications of the ACM[END_REF] along with several dimensions and "measures"; however, they rely on sampling, limiting the number of visible items to numbers not specified by the author. Jerding et al. "Information Mural" technique [START_REF] Jerding | The Information Mural: A Technique for Displaying and Navigating Large Information Spaces[END_REF] is a good example of system displaying hundreds of thousand items by relying on aggregation.

Current visualization systems are limited to about 10,000 items partly because control panels, labels and margins waste too many pixels, the data structures are not optimized for speed, and they use slow graphics libraries, which brings the interaction to a very slow motion when dealing with more than 10,000 items (for example Spotfire can load more than 10,000 items but the interaction suffers enormously). Addressing those three issues is necessarybut not sufficient -to handle a million items.

Perception

To be effective, visualization techniques should rely as much as possible on preattentive graphical features [START_REF] Healey | Visualizing Real-Time Multivariate Data Using Preattentive Processing[END_REF][START_REF] Triesman | Preattentive Processing in Vision[END_REF]. These features are processed by the low level visual system and can be recognized "at a glance" without effort. An example of preattentive processing consists in spotting red dots among several blue dots. It does not take any effort to see whether there are one or several red dots and it can be done in less than 200 milliseconds if the region is small enough to be seen in one glimpse (more experiments can be found at http://www.csc.ncsu.edu/faculty/healey/PP/ PP.html). Without pre-attentive processing, spotting a feature requires time linear to the number of features and will not scale well to displays of millions of items. An example of non-preattentive feature is text reading. Finding a name in a non-sorted list requires a time proportional to the number of labels (or more when the user loses track or gives up.)

The list of visual features available to visualize abstract information is long, but only a small set can be used in a preattentive way. Healey lists them in [START_REF] Healey | Visualizing Real-Time Multivariate Data Using Preattentive Processing[END_REF] as: line (blob) orientation, length, width, size, curvature, number, terminators, intersection, closure, color (hue), intensity, flicker, direction of motion, binocular luster, stereoscopic depth, 3D depth cues and lighting direction. Furthermore, this list only means that in some controlled configuration, these features can be processed preattentively, not that they are always processed this way. For example, Healey has conducted experiments that show that only five to seven different well-chosen colors can be processed preattentively. When trying to use more colors, the error rate and time required to search colored items increased substantially and search time become linear. In addition, combining two or more preattentive features can create interferences so in practice only two or three features can be used together.

Interactive Techniques

In 1994, Ahlberg and Shneiderman [START_REF] Ahlberg | Visual Information Seeking: Tight Coupling of Dynamic Query Filters with Starfield Display[END_REF] defined the steps of visual information seeking as: start with an overview of the data set, zoom in on items of interest and filter out uninteresting items, then details on demands. Increasing the number of visible items permits richer overviews to be presented.

They also introduced the term "dynamic queries" to describe interactive methods for interactively specifying search queries in data sets. The definition is:

• visual presentation of the query's components (with buttons and range sliders); • visual presentation of results;

• rapid [around 100ms], incremental, and reversible control of the query; • selection by pointing, not typing; and immediate and continuous feedback. Coupling visualization with dynamic queries has increased the effectiveness of visualization techniques by allowing user-controlled temporal research on the visualized data. Current systems dynamically filter visualized data through sliders and buttons up to 10,000 items. Above that, the refresh rate becomes unacceptable.

An optimization technique developed by Tanin [START_REF] Tanin | Incremental Data Structures and Algorithms for Dynamic Query Interfaces[END_REF] demonstrates dynamic queries with 100,000 items by pre-computing the visible items for each reachable position of the slider bar but this technique was limited by the redisplay time. To show more items or dimensions, all the visualization techniques can use space multiplexing, time multiplexing, overlapping, or space deformation techniques. Space multiplexing techniques display two or more visualization configurations on the same screen, using fewer pixels for each configuration. This is impractical when attempting to visualize a million items because space is already scarce to begin with. Time multiplexing techniques show each configuration successively, either at a regular pace (animation), or by using control panels, or by following interactive methods such as dynamic queries.

Each configuration should appear in less than 100ms to maintain continuous interaction. Overlapping techniques such as Magic Lenses [START_REF] Bier | A Taxonomy of See-Through Tools[END_REF] and Excentric Labels [START_REF] Fekete | Excentric Labeling: Dynamic Neighborhood Labeling for Data Visualization[END_REF] show transient information over the visualization and can be used effectively on dense data. Several interactive techniques have been designed to enhance the interaction for visualization and sparing screen real estate. See-through tools [START_REF] Bier | A Taxonomy of See-Through Tools[END_REF] are interactive enhancements to Magic lenses; they filter the visualization in-place using transparency or overlapping. Extensions of Pie-Menus [START_REF] Callahan | An Empirical Comparison of Pie vs. Linear Menus[END_REF] such as Control Menus [START_REF] Pook | Context and Interaction in Zoomable User Interfaces[END_REF] can be used to overlay controls without using permanent screen real estate.

Space-deformation techniques such as [START_REF] Lamping | A focus+context technique based on hyperbolic geometry for visualizing large hierarchies[END_REF] are sampling or aggregation techniques that try to show details in the zones of interest and only show "important features" or samples elsewhere.

Aggregations provide powerful summaries but can sometime hide phenomena only visible at finer grain. For example, a US map of mortality data at the state level will hide local outliers and even errors in the data. This article focuses on techniques that push back further the need for aggregation and sampling.

Technical Constraints

To display one million of items, we need to address screen resolution and speed issues.

Screen definition and resolution: Current high end screens display around 2 million pixels (1600x1200) at a resolution of 150dpi, with the newest screens capable of displaying around ten million pixels at 200dpi. So displaying 1 million of items should not be a problem if each item fits in 2 to 10 pixels in average, not counting the overlaps. Screens or video projections can be tiled to increase the number of pixels available, virtually removing any limitation, but increasing the physical size of the display requires more head movements and slows down perception.

An alternative is to increase screen resolution. The limit would be human perception: theoretically around 24 million pixels, practically around 10 million, and head or body movements can still be used to get closer to or farther away from the display. The only alternative to these movements is time multiplexing, through constant animation or interactive control such as a scrollbars for panning and zooming, which are even less effective than movements.

We have focused our research on 1600x1200 displays because they are widespread and well managed by current accelerated graphics boards.

Redisplay time: when time multiplexing is used, the redisplay rate should be maintained around 10 frames per second. If one million items have to be displayed at this rate, using accelerated graphics cards is the only option and opens the door to visualization enhancements. Common graphics cards can display around 15 million triangles per second at best so maintaining an acceptable refresh rate for one million items demands special techniques and more expensive cards or waiting for the next generation of cards.

For our work, we have used NVidia GeForce3 and 3Dlab Wildcat hardware accelerated boards with 2GHz and 1.7GHz Pentium PCs and the OpenGL API [START_REF] Veldhuizen | Using C++ template metaprograms[END_REF] with code written in C++.

Reaching One Million Items

To address the technical issues involved in visualizing and interacting with one million items, we have designed novel techniques relying on accelerated graphics hardware to provide high-density interactive visualization.

The accelerated graphics hardware reduces the load of the main CPU (e.g. all rendering is done there) and offers many nonstandard graphics attributes that we used to enhance the visualization of dense data sets.

Appropriate Visual Attributes

We only use quadrilaterals to represent items because, in a dense configuration, the perception of shapes is subject to interference. As item density increases shapes overlap and appear to merge. Also, contrary to several existing systems, we don't outline items using a one-pixel black line, which wastes two lines and two columns of pixels and requires sending the coordinates twice. Instead, we use slightly shaded quadrilaterals so that they remain distinguishable when tiled or stacked (see figure 2). The other visual attributes use are saturated colors (for categorical or numeral attributes), intensity (for numeral attributes), quadrilateral sizes and position in scatter plots.

We describe each quad vertex with four values: X, Y, Z and S. X and Y are positions. S is a texture coordinate index. The Z coordinate is mainly used for fog and stereovision: we tilt the quads so that the upper left corner is closer to the camera and the lower right corner farther away; the fog function changes their intensity and smooth shading interpolates it across the rectangle.

Instead of sending RGBA colors for each quad, we use onedimensional texture indices. The texture can contain a set of colors for categorical attributes: one color per category. It can also contain starting and ending color for continuous valued attributes. We then rely on hardware linear filtering to generate in-between colors as shown in figure 2. We also use texture transforms to map from abstract attribute values to color values, avoiding all color computation on the CPU side.

More attributes can be used if required. For instance, for treemaps, we also use the fog function to fade the colors to black when items are deeper in the tree by assigning the tree depth attribute to the Z coordinate of the quadrilaterals (see Figure 1). More control could be obtained by using a two dimensional texture and assigning the U texture coordinate (also easily available via the accelerated graphics hardware) to one abstract attribute and the V coordinate to another one. However, the only coloring scheme we have found to be effective using pre-attentive features with two attributes was assigning a saturated set of colors to one attribute and varying the brightness with the other.

Synthetic overlap attribute

When sending data to the graphics hardware, the count of overlapping items can be calculated using the stencil buffer. Displaying the content of the stencil buffer as intensity shows the overlapping counts (see figure 3.) This synthetic attribute is very important for visualization techniques that cannot avoid overlaps such as scatter plots and parallel coordinates. Even with hundreds of items, the distribution tends to be sparse with areas of high density that are hard to see. Transparency is useful when up to five items overlap, but with one million items, hundreds of overlapping items are common.

The overlap count can also be mapped to color, or used to filter the display and reveal a specific layer of items. This technique is similar to dynamic queries on standard attributes but instead relies on the stencil buffer for rejecting fragments above or below a specified number of overlaps.

Transparency and Stereovision

Using an accelerated graphics card provides graphic attributes not available or usable with traditional graphics APIs. We have experimented with transparency and stereovision. Transparency is beneficial with overlapped items but is not sufficient by itself to understand the number of overlaps. Furthermore, by blending colors, it interferes with its preattentive processing. Therefore, transparency is only useful when it can be varied interactively to reveal overlaps and density of overlapping items.

Stereovision hardware is now available for all the standard graphics cards for less than $100 through shutter glasses. Stereovision is preattentive, but there again, overlaps interfere with it and cannot be avoided at all, even with space-filling visualization techniques, since stereovision requires a perspective projection that introduces occlusion and therefore overlaps. Like transparency, we have found stereovision mostly useful for transient inspections.

Animation and Interaction

Exploring a large data set without a-priori knowledge typically requires trying several mappings of data attributes to visual attributes. A special problem happens when changing views using time multiplexing: the whole layout of the screen changes and the user cannot tell where sets of regions of interest in the original view have gone on the new one. A long time may be required to understand the relationship between items visualized in the new view and in the previous one. This problem is not addressed at all by current systems. When the number of items is small and space multiplexing possible, two or more views could be displayed together using "snap together" techniques [START_REF] North | Snap-Together Visualization: Evaluating Coordination Usage and Construction[END_REF] and brushing and linking techniques [START_REF] Cleveland | Dynamic Graphics for Statistics[END_REF] can be used to explore the tightly coupled views by highlighting items in multiple views; but this is not an option in our case.

We first describe the simple case of non-geometrical changes and then the general case.

View Flipping

When the positions of the data items are preserved -i.e. when only changing colors or stacking order -flipping between views allows quick comparisons to be made using retina persistency. This technique is widely used in astronomy to track variations over time (called blinking.) By flipping back and forth and moving the focus of attention, two views can be compared in seconds.

More views can be flipped through, similar to flipping techniques of traditional animators, to help discover trends and outliers across multiple views. This technique only requires a redisplay time below 300ms and a refresh time below 50ms, only achievable with double buffering.

Interpolation of geometrical attributes

When the geometry is modified between two views, it becomes difficult to impossible to understand relationships between views with flipping [START_REF] Nowell | Change blindness in information visualization: a case study[END_REF].

We have implemented a set of interpolation techniques to animate the transformations from one view to the other so that the eye can follow sets of items and understand patterns of change between views. Because the changes could be complex, users can select a subset of items and we only animate those items. The animation lasts one or two second and can be replayed back and forth at will. A slider can also be used to manually control the interpolation between views to facilitate understanding of item movements.

The simplest technique for animation is linear interpolation. However, when several visual attributes change, linear interpolation is confusing [START_REF] Yee | Animated exploration of dynamic graphs with radial layout[END_REF] and only allow users to track position changes at best. To help users understanding changes, we found that animating in two stages was beneficial: changing positions, then changing dimensions.

For scatter-plot-like visualization, position and size are independent so the middle configuration is easy to compute. Linear interpolation of positions is used to reach the middle configuration from the initial and linear interpolation of sizes is used to reach the final configuration. Both show trends when they exist.

Space-filling visualizations compute positions according to the size of items. Most of them [START_REF] Baker | Space Filling Software Visualization[END_REF][START_REF] Eick | SeeSoft-A Tool for Visualizing Line Oriented Software Statistics[END_REF][START_REF] Jerding | The Information Mural: A Technique for Displaying and Navigating Large Information Spaces[END_REF] can be animated by linearly changing the size attributes since they use a layout that remains stable. Only some treemaps described in [START_REF] Bederson | Ordered and Quantum Treemaps: Making Effective Use of 2D Space to Display Hierarchies[END_REF] use layout algorithms that are not geometrically stable. However, we found a general way to stabilize all these layouts for stage 2 (i.e. size changes) by computing the final layout using the final sizes values and linearly changing the sizes of all areas according to their initial values. This is shown in figure 4 where the final layout is computed by the "squarified treemap" algorithm, and used by previous frames with the sizes interpolated. The final layout tries to have items as "square" as possible but not the previous ones. Still, trends are visible.

For stage 1 (i.e. position changes), linear interpolation is usually the only option. Layout changes may be due to the underlying algorithm or to the change of an axis on a scatter plot, or the sorting order of a dimension linked to an axis. However, by only changing positions and not sizes, items are easier to track and trends are noticeable. For example, when changing the attribute to be mapped on the X axis of a scatter plot, items only move along the Y axis.

With treemaps, texture mapping [START_REF] Aliaga | Visualization of Complex Models Using Dynamic Texture-Based Simplification[END_REF] is very effective at speeding-up both stage 1 and 2. Most space-filling techniques use hierarchical containment, preserved by attribute change so one set of items is always inside a rectangle that can be warped and turned during the animation and there is no need to interpolate each item separately. With this technique, smooth interpolation can be achieved with one million item treemaps.

Logging/playback: Interactively specifying mappings from data attributes to visual attributes can become tedious and diverts the user from the visualization analysis. To avoid this distraction from occurring too often, we developed a tool allowing users to record sets of configurations and view them in turn using the left and right arrow keys, with animated transitions as described above. These views and configurations can also be saved to a file and applied to other data sets (e.g. to simplify routine examination of similar datasets.)

Dynamic Queries

Dynamic queries implies interactively filtering and redisplaying of the dataset through continuous interaction. Current systems use "range-sliders" to filter one attribute at a time, either changing the lower or upper value, or sweeping a given range of values between the smallest and the largest. The dataset needs to be loaded into main memory. To achieve the redisplay speed required for smooth interaction, we have designed a technique that relies on hardware acceleration. When the user activates a slider to perform the series of queries, all the items are sent to the graphics processor (GPU) and stored in a display list. The Z coordinate is calculated according to the attribute being filtered by the slider (e.g. if the user is filtering a film database on the size of the film, the size is assigned to the Z-axis.) Each time the slider moves, a new near or far plane value is computed and sent to the GPU and the list is redisplayed, leaving the visibility computation to the hardware. This technique works very well as long as the GPU has enough memory to hold the items and the shape of the items doesn't change during the dynamic queries. Using quadrilaterals requires 64MB of free memory (4 vertices per item, 4 data per vertex with 4 bytes per data) for one million items and only fits on special machines such as SGI O2. When applying dynamic queries on scatter plots with PC graphics cards, we use points instead of quads. Currently, OpenGL doesn't allow sending one array of points with varying sizes, although it can be done with NVidia Vertex programs extension. We send arrays of points sorted by decreasing point-size, dividing by 4 the amount of data sent to the card and making dynamic queries possible with one million items on a PC.

Labeling

Text labels are not preattentive but are nevertheless important to understand the context in which visualized data appear. Labeling each item cannot be done statically on a dense visualization so we used the Excentric Labeling [START_REF] Fekete | Excentric Labeling: Dynamic Neighborhood Labeling for Data Visualization[END_REF] dynamic technique for the scatter plot and extended its design for the Treemap, as shown in figure 6.

Performance

Our system reads data encoded in XML or a directory structure as input formats. It is made of 23,000 lines of C++, using high-performance techniques such as template metaprogramming [START_REF] Veldhuizen | Using C++ template metaprograms[END_REF] to achieve the required speed. We have used it with an NVidia GeForce3 board on a 2 GHz Pentium and a 3Dlab Wildcat 5110 on a dual 1.7GHz Pentium. To scale to a million items, the computation of layouts should be done in time linear with the number of items. This is the case with some treemaps and scatter plots but not with VisDB for example. Even using the fastest techniques, layout computation takes about 50% of the redisplay time.

Despite the high theoretical performance of the boards, we have not been able to go beyond 6 million quads per second on any of the boards we tried. The theoretical speed of 15 million triangles per second is only achievable for triangle strips, which is of no use for scatter plots and would require expensive computation for treemaps.

Combining software and hardware techniques provides a sustained performance around 2.5 million quads per second. By using texture mapping for animating treemaps, we achieve 10 frames per second for animating across any family of treemap. For scatter plots we have only reached 3 frames per second for animations on 1 million items, and 6 frames per second for dynamic queries. Finding techniques for improving that speed would be useful but the next generation of graphics cards and computers will solve the problem.

Our estimate is that these results correspond to a 20 to 100 time improvement on the available systems.

Conclusion and Future Work

Using a set of novel techniques we were able to visualize and explore for the first time 1 million items on a 1600x1200 display without aggregation. Our techniques rely heavily on commonly available accelerated hardware for displaying items in a dense yet manageable manner. We designed new animation techniques to help understand view changes and show trends and outliers when they exist. We developed a method to perform dynamic queries using the Z-buffer of a graphics card and achieved the speed required to interact with a million items. Finally, we experimented with non-standard visual attributes such as transparency and stereovision and found them effective for temporary inspections.

This work shows that the technical limits of information visualization are well beyond the typical 10 4 items handled by most existing systems, and opens the door to new possibilities for users: a library manager can use a treemap to review usage patterns of a million individual books organized with the Dewey decimal system; large databases of highway incidents or juvenile justice cases can be first examined without sampling or aggregation.

Our early user testing has been limited to collecting feedback from colleagues about the large treemap displaying our shared drives of one million files. It seems to confirm that users' experience analyzing data transfers to large visualizations, allowing them to make local and global comments on the data presented. Users appreciated the fine patterns, e.g. the distinctive pattern of web page directories that combine text and graphics, and seemed to actively engage their visual skills to compare and make sense of patterns. We have now identified two applications for user testing: 1) the visualization of the University of Maryland catalog and years of circulation data, and 2) fine grain analysis of Census Bureau data. The user testing will involve domain expert users, who are more apt to make sense of such large datasets and make suggestions for improvements.

More experiments are needed to understand how humans can cope with a large number of items and the possible limits of visualization, e.g. how can we best use visualization to gain an understanding of the organization and content of the 7 million items of the Library of Congress American Memory collection?

We are confident that human visual skills and the evolution of hardware will push information visualization much further than the million of items.

Figure 1 :

 1 Figure 1: This treemap gives an overview of 970,000 files of a file system containing 1 million files (smaller files are smaller than one pixel and not counted), on a 1600x1200 display. The size of each rectangle is determined by the file's size; color represents file type. Deeply nested directories appear darker.

Figure 2 :Figure 3 :

 23 Figure 2: Smooth shaded rectangles help distinguish items in dense visualizations (details of scatter plots)

Figure 4 :Figure 5 :

 45 Figure 4: The animation of the treemap (with a squarified layout on the left or slice&dice layout on the right) allows users to follow specific items and observe patterns of change between two configurations using a different size attribute . A stabilized layout is used to avoid jumps.

Figure 6 :

 6 Figure 6: Dynamic Labeling of a Treemap (detail). When clicking on the treemap, labels are displayed dynamically on the outside of the region, which is grayed out. The popup menu allows users to adjust the depth of the region of interest.

Acknowledgments

This work was supported in part by Chevron Texaco. We want to thank Ben Bederson and Ben Shneiderman for their helpful feedback on the paper.

For more information and demonstration of animations see: http://www.cs.umd.edu/hcil/millionvis/