Ayoub Tamim

Khalid Minaoui

Khalid Daoudi

Abderrahman Atillah

Driss Aboutajdine

Detection of Moroccan Coastal Upwelling in SST images using the Expectation-Maximization

Keywords: Upwelling, Sea Surface Temperature, Expectation-Maximisation, Davies-Bouldin index, Dunn index, Area opening

This paper proposes an unsupervised algorithm for automatic detection and segmentation of upwelling region in Moroccan Atlantic coast using the Sea Surface Temperature (SST) satellite images. This has been done by exploring the Expectation-Maximization algorithm. The good number of clusters that best reproduces the shape of upwelling areas is selected by using the two popular Davies-Bouldin and Dunn indices. Area opening technique is developed that is used to remove and discarded the residuals noise in offshore waters not belonging to the upwelling region. The complete system has been validated by an oceanographer using a database of 30 SST images of the year 2007, demonstrating its capability and robustness for precise detection of Moroccan coastal upwelling.

I. INTRODUCTION

The Moroccan Atlantic coast located in the central canary current system is characterized by persistent and variable upwelling throughout the year [START_REF] Atillah | Produits opérationnels d'océanographie spatiale pour le suivi et l'analyse du phénomène d'upwelling marocain[END_REF]. In fact, the upwelling is a wind-driven ocean process, which brings cooler, saltier, and usually nutrient-rich deep water upward to replace surface water displaced offshore due to Ekman transport. The upwelling waters stimulates the growth and reproduction of primary producers such as phytoplankton, and consequently play a major contribution in the fisheries management and also in the study of the oceanic circulation and dynamics [START_REF] Chassot | Satellite remote sensing for an ecosystem approach to fisheries management[END_REF], [START_REF] Bakun | Fronts and eddies as key structures in the habitat of marine fish larvae : opportunity, adaptive response and competitive advantage[END_REF]. The upwelling phenomenon is evidenced at the surface by the presence of cool temperatures and high chlorophyll-a concentrations in onshore waters [START_REF] Anderson | A 300 kyr record of upwelling off oman during the late quaternary: Evidence of the asian southwest monsoon[END_REF].

The increasing demand and rapid expansion of the satellitederived products of the ocean have allowed the scientists to replace the labor intensive manual interpretation of the satellite data made by the oceanographers by an automatic detection [START_REF] Holyer | Edge detection applied to satellite imagery of the oceans[END_REF], [START_REF] Cayula | Edge detection algorithm for SST images[END_REF]. In particular, the infrared images of the ocean obtained from Advanced Very High Resolution Radiometer (AVHRR) sensor onboard the NOAA satellite are often rich in oceanographic structures and have been frequently used to study the sea surface temperature patterns related to upwelling activity [START_REF] Holyer | Edge detection applied to satellite imagery of the oceans[END_REF], [START_REF] Cayula | Edge detection algorithm for SST images[END_REF], [START_REF] Tamim | A simple and efficient approach for coarse segmentation of Moroccan coastal upwelling[END_REF].

A number of automated techniques and algorithms have been proposed in order to detect and localise the upwelling features in SST images. These algorithms vary in complexity from simple classification and thresholding methods [START_REF] Tamim | A simple and efficient approach for coarse segmentation of Moroccan coastal upwelling[END_REF], [START_REF] Nascimento | Automated computational delimitation of SST upwelling areas using fuzzy clustering[END_REF] to histogram analysis [START_REF] Nieto | Mesoscale frontal structures in the canary upwelling system: New front and filament detection algorithms applied to spatial and temporal patterns[END_REF] and structure growing process [START_REF] Marcello | Automatic tool for the precise detection of upwelling and filaments in remote sensing imagery[END_REF]. These wide range of developed algorithm reflects the nature of the problem encountered when attempting to analyse the oceanographic data; namely cloud contamination, artifacts, strong morphological variation and the absence of valid analytical model for the upwelling structures.

Tamim et al. [START_REF] Tamim | A simple and efficient approach for coarse segmentation of Moroccan coastal upwelling[END_REF] were the first investigators to show that classification of the SST images using any of the two strategies of partitioning, fuzzy or hard, leads to similar and satisfactory results. The investigators were specifically interested in detecting the Moroccan coastal upwelling in infrared satellite imagery. The algorithm used respectively the Otsu's and Fuzzy c-means algorithms as underlying hard and fuzzy clustering strategies to generate a labelled images with homogenous and non-overlapping temperatures. Then region-growing process is used to automatically segment and extract the upwelling area from the remaining residuals offshore waters.

Nieto et al. [START_REF] Nieto | Mesoscale frontal structures in the canary upwelling system: New front and filament detection algorithms applied to spatial and temporal patterns[END_REF] developed an edge detection algorithm for the automatic detection of oceanographic features in SST images. The algorithm is based on the analysis of the bimodality of the image, and the edge is considered to be present if the algorithm detect two different population. The result is series of thermal fronts which separating two waters masses of distinct temperatures.

Marcello et al. [START_REF] Marcello | Automatic tool for the precise detection of upwelling and filaments in remote sensing imagery[END_REF] have combined two approaches in order to detect the upwelling area in SST images. The latter started with the initial structures detection to obtain preliminary coarse segmentation based on the structure analysis and thresholding stage, followed by structures growing step in order to attain the fine detail of the upwelling structures, based on the watershed transform. The algorithm has been tested and validated over database of multisensorial images.

The main aim of this paper is to provide a simple tool for automatic detection and segmentation of upwelling area in the coastal ocean of Morocco using the well-known classification algorithm.

The rest of this paper is organized as follows: Section 2 presents the database and the geographic area used in this study. The proposed methodology to detect and segment the upwelling area in the SST images are listed in Section 3. Section 4 highlights the results and the validation of the algorithm. Finally, Section 5 gives our conclusions and future work.

II. STUDY AREA AND DATA

A total of 30 AVHRR SST images of the year 2007 covering the southern part of Moroccan Atlantic coast (spans from 20°50 -27°52 N and 13°5 -20°10 W) are used throughout this study in order to test and validate the applicability of our proposed approach for the automatic detection of upwelling region. The database were received and processed at the Royal The cloud and land masks are applied to each image in order to reduce the number of contaminated pixels in the input SST image, and they are generated by using a sequence of multispectral contrast, spectral, and spatial signature threshold tests to perform the classification of the pixel as cloud pixel [START_REF] Larry | Scientific basis and initial evaluation of the clavr-1 global clear/cloud classification algorithm for the advanced very high resolution radiometer[END_REF]. The size of each SST images is 714 × 750 pixels with a spatial resolution of 1.1 × 1.1 and each pixel represent a temperature in Celsius degree. In order to help and facilitate the interpretation made by the users or oceanographers for the detection of upwelling areas in SST image, a color scale of 25 levels is applied for each image.

III. THE PROPOSED ALGORITHM

A. Clustering algorithm

The main aims of cluster analysis [START_REF] Jain | Algorithms for Clustering Data[END_REF] is the classification of patterns and objects according to similarities among them, and then organizing data into clusters. Generally, the cluster is a group of patterns that are more similar to one another than to members of other clusters.

The clustering techniques [START_REF] Anderberg | Cluster Analysis for Application[END_REF] are among the unsupervised methods when the only data available are unlabelled, and no structural information about it is available. Different classifications approaches can be distinguished depending on the algorithm used: Partitioning, hierarchical, graph-theoretic, and methods based on objective function. In this work we are focused on the partitioning approach, especially for hard clustering methods. In fact, one possible classification of clustering methods can be according to whether the clusters are fuzzy or hard. Hard clustering methods are based on classical set theory, and require that an object either does or does not belong to a cluster. In contrast, Fuzzy clustering methods allow objects to belong to several clusters simultaneously, with different degrees of membership. In this study we have used the expectation-maximization algorithm as underlying hard clustering techniques.

The expectation-maximization (EM) algorithm [START_REF] Bradley | Scaling em (expectation maximization) clustering to large databases[END_REF] is considered to be an appropriate optimization algorithm for constructing proper statistical models of data. It provides a probabilistic clustering where each data element has a certain probability of being a member of any cluster. EM is widely used in applications such as computer vision, speech processing and pattern recognition [START_REF] Nefian | A coupled hmm for audio-visual speech recognition[END_REF]. In fact, EM starts with an initial estimate for the missing variables and iterates to find the maximum likelihood (ML) for these variables. Maximum likelihood methods estimate the parameters by values that maximize the sample's probability for an event. EM is typically used with mixture models.

• Initialization step: initialize the hypothesis

θ 0 = (µ 0 1 , µ 0 2 , • • • , µ 0 K ) θ 0 k = µ 0 k ( 1
)
Where K is the current number of Gaussians. σ is the standard deviation, θ 0 is the estimate at 0 th iteration and µ is the mean.

• Expectation step: estimate the expected values of the hidden variables z i j (mean and standard deviation) using the current hypothesis

θ t = (µ t 1 , µ t 2 , • • • , µ t K ) E(Z ik ) = exp[- (x i -µ t k ) 2σ 2 ] ∑ K j=1 exp[- (x i -µ t j ) 2 2σ 2 ] (2)
Where t is the number of iteration, E(z ik ) is the expected value for the hidden variables (namely mean and standard deviation), k is the dimension, σ is the standard deviation.

• Maximization step: provides a new estimate of the parameters.

µ t+1 k = ∑ n i=1 E(z ik )x i ∑ n i=1 E(z ik ) (3)
• Convergence step: if θ t+1θ t+1 stop (finish iteration); otherwise, go to step 2.

The hidden variables are the parameters of the model. In our case we use mixtures of Gaussians; hence our hidden variables are the mean and standard deviation for each Gaussian distribution. We start with an initial estimate of those parameters and iteratively run the algorithm to find the maximum likelihood for our estimates. For convergence we run it number of times so that the values stop increasing.

B. Optimal Number of Clusters

Once the collection of hard c-partitions labeled images are generated, one needs to determine the optimal number of clusters, c * -partition, which better reproduces the shape of the SST patterns. Indeed, the clusters validity indices are widely used to evaluate the c-partitions and then extract the optimal number of clusters.

A number of validity indices for hard clustering exist in the literature [START_REF] Xu | A comparative study of cluster validation indices applied to genotyping data[END_REF], [START_REF] Wu | A cluster validity index for fuzzy clustering[END_REF], all of which have a common goal to find the clustering which results in compact clusters that are well separated. In particular, the Davies-Bouldin (V DB ) [8] and Dunn's (V DI ) [START_REF] Dunn | A fuzzy relative of the isodata process and its use in detecting compact well-separated clusters[END_REF] indices have been frequently used due to their computational efficiency and effectiveness for estimating the good number of clusters [START_REF] Pakhira | Validity index for crisp and fuzzy clusters[END_REF].

Davies-Bouldin index is a function of ratio of the sum of within cluster scatter to between cluster scatter [START_REF] Pakhira | Validity index for crisp and fuzzy clusters[END_REF]. The optimal cluster number c * is found by solving min c min c c max V DB (c) to produce the best clustering performance for data. In other hand, the Dunn index is a ratio of within cluster and between cluster separations. The number of clusters that maximizes the V DI index is taken as the optimal number of clusters, max C min C C max V DI (c). Consequently, these two indices are used in the current work to assess the quality of the obtained hard c-partitions. Hence, the best cpartition is obtained by taking respectively the global minimum and the global maximum of V DB and V DI indices with respect to c = 2, 3, ..., c max .

The results of the two validity indices (V DB and V DI ), applied to the original SST images in Fig. 1 using the EM algorithm with number of cluster varying from c min = 2 to c max = 7, are shown in Fig. 2.

As shown, the absolute extremum of the four curves is reached by the cluster number c * = 2, which is consistent with the suitable number of cluster to reproduce the areas covered by upwelling waters for SST images in Fig. 1, and also for all the images analyzed in this study.

Once the labeled image is generated using the expectationmaximization algorithm with the optimal number of clusters, c * = 2, the upwelling area is defined as the clusters with the lowest mean value, based on the fact that the upwelling region is characterized by a cold temperature waters compared to the offshore warmer waters [START_REF] Tamim | A simple and efficient approach for coarse segmentation of Moroccan coastal upwelling[END_REF]. Fig. 3 shows the binary image results after the application of the expectation-maximization algorithm with the automatic selection of the number of clusters using the Davies-Bouldin and Dunn's indices.

C. Segmentation algorithm

The binary images results in Fig. 3 include the upwelling area plus additional noise structures in offshore waters not belonging to the upwelling region, mainly due to the cloud contamination pixels which are not properly masked by the cloud detection algorithm used in this study [START_REF] Larry | Scientific basis and initial evaluation of the clavr-1 global clear/cloud classification algorithm for the advanced very high resolution radiometer[END_REF]. Therefore, a segmentation procedure is required consisting on the application of the area opening algorithm to remove pixels and contiguous regions faraway from the coast, not belonging to the upwelling waters. The area opening is a transformations using a structuring element which locally adapts its shape to the image structures, and therefore filtering out small regions (lower than a given threshold) without damaging the remaining structures in the images [START_REF] Vincent | Morphological area openings and closings for grey-scale images[END_REF]. An evaluation has been carried out for this study using the 30 SST AVHRR images, in order to select a single threshold value that remove the noisy structures from the images. After an extensive evaluation, good results are obtained by the threshold value of 200 pixels. So, each regions less than 200 pixels, will be discarded from the given image. Fig. 4 shows the results of the area opening algorithm applied to the binary images of Fig. 3 with the thresholding value fixed at 200 pixels. As we can see, all the remaining pixels in offshore waters have been removed and separated from the upwelling area.

IV. EXPERIMENTAL RESULTS AND DISCUSSION

The performance of the proposed methodology of segmentation of Moroccan coastal upwelling in SST images has been tested by using the visual inspection made by the oceanographer based on the scientific knowledge of the Moroccan atlantic coast. The in-situ measurement, e.g., buoys data, can give us a sounder support to the results obtained by the proposed algorithm. However, these measures are very complex to establish and would be extremely challenging for a use in coastal zone context, because of lack of these measures for all the satellite data and for every specific region in the study area. In this sense, it is a well-known fact that validation in the case of ocean data is often and truly performed by assessing the results by professional oceanographers [START_REF] Tamim | A simple and efficient approach for coarse segmentation of Moroccan coastal upwelling[END_REF], [START_REF] Nascimento | Automated computational delimitation of SST upwelling areas using fuzzy clustering[END_REF], [START_REF] Sousa | Identification of upwelling areas on sea surface temperature images using fuzzy clustering[END_REF], which has been done in the case of this work.

The oceanographic interpretation is applied in order to check if the proposed approach correctly identify the upwelling area over the 30 SST images. For this purpose, four grades are used: "Bad", "Poor", "Good" and "Excellent". The grade "Bad" is attributed when the upwelling area is not welldelimitated, and "Excellent" is reached when the upwelling region is correctly segmented. The results of the oceanographer interpretation are presented in Fig. 5.

As we can see, the Fig. 5 shows that the grades "Bad" and "Poor" reached respectively the values 3% and 7%, resulting in a total of 10% of 30 SST images. In other hand, the values of 51% and 39% are reached respectively by the grades "Good" and "Excellent", making a total of 90%. After this evaluation of the segmentation methodology, over this representative database, we can conclude that the proposed algorithm has provided satisfactory results.

V. CONCLUSIONS AND FUTURE WORK

In the present research we have presented a classification methodology for automatic detection and segmentation of Moroccan coastal upwelling using the SST images. The algorithm is started with the application of Expectation-Maximization algorithm followed by cluster validity indices, for the purpose of generating labeled image with homogeneous groups of pixels and no-overlapping classes. Then a segmentation procedure is developed to eliminate isolated components, in offshore waters, not belonging to the upwelling structure, based on the area opening algorithm. The algorithm is applied and tested over 30 AVHRR SST images on board the NOAA satellite serie and evaluated using the scientific knowledge of the Moroccan costal upwelling provided by the oceanographer. The proposed algorithm has demonstrated a great performance for automatic detection of upwelling region in coastal region of Morocco for majority of images used in this study. This work can be continued in order to investigate the interannual variability of the upwelling in terms of upwelling activity, and also the objective of using this segmentation methodology to other satellite data products, such as the remotely sensed seasurface chlorophyll field, to give us a sounder support to the results already obtained.

Fig. 1 :

 1 Fig. 1: SST images obtained on (a) 2007-07-26 and (b) 2007-09-10, showing two upwelling scenarios.

Fig. 1 (

 1 a) shows two SST upwelling scenarios encountered throughout this study: 1) SST images with clear, visible and well-define upwelling structure in the Moroccan Atlantique coast (Fig. 1(a)); 2) SST images where the presence of cloud contamination and artifacts affect the continuity of upwelling structures along the coast (Fig. 1(b)). The gray color region on the right side of the SST images in Fig. 1(a) and (b) corresponds to Moroccan land, whereas the white pixels in the ocean correspond to cloud pixels.

Fig. 2 :

 2 Fig. 2: Results of the validity indices with EM algorithm using respectively the V DB and V DI indices to the SST images in Fig. 1(a) ((a) and (b)) and Fig. 1(b) ((c) and (d)).

Fig. 3 :

 3 Fig. 3: Binary image result after the application of the expectation-maximization algorithm the two SST images in Fig. 1, with the automatic selection of the number of clusters using the Davies-Bouldin and Dunn's indices.

Fig. 4 :

 4 Fig. 4: Retrieved upwelling areas using the area opening algorithm of the two binary images results of Fig. 3.

Fig. 5 :

 5 Fig.5: Qualitative interpretation made by the oceanographer of the 30 SST images for the proposed approach using the Expectation-Maximization.


Shanghong Zhao

Wei Tsang Ooi

Axel Carlier

Geraldine Morin

Vincent Charvillat

Bandwidth Adaptation for 3D Mesh Preview Streaming

Keywords: Descriptors: I.3.2 [Computer Graphics]: Graphics Systems-Distributed/network graphics Algorithms, Human Factors, Performance Progressive mesh streaming, 3D preview, camera path

Online galleries of 3D models typically provide two ways to preview a model before the model is downloaded and viewed by the user: (i) by showing a set of thumbnail images of the 3D model taken from representative views (or keyviews); (ii) by showing a video of the 3D model as viewed from a moving virtual camera along a path determined by the content provider. We propose a third approach called preview streaming for mesh-based 3D objects: by streaming and showing parts of the mesh surfaces visible along the virtual camera path. This article focuses on the preview streaming architecture and framework and presents our investigation into how such a system would best handle network congestion effectively. We present three basic methods: (a) STOP-AND-WAIT, where the camera pauses until sufficient data is buffered; (b) REDUCE-SPEED, where the camera slows down in accordance to reduce network bandwidth; and (c) REDUCE-QUALITY, where the camera continues to move at the same speed but fewer vertices are sent and displayed, leading to lower mesh quality. We further propose two advanced methods: (d) KEYVIEW- AWARE, which trades off mesh quality and camera speed appropriately depending on how close the current view is to the keyviews, and (e) ADAPTIVE-ZOOM, which improves visual quality by moving the virtual camera away from the original path. A user study reveals that our KEYVIEW-AWARE method is preferred over the basic methods. Moreover, the ADAPTIVE-ZOOM scheme compares favorably to the KEYVIEW-AWARE method, showing that path adaptation is a viable approach to handling bandwidth variation.

INTRODUCTION

The ease in 3D acquisition, editing, viewing, and printing have led to websites that support online publishing of 3D models. Individual users can now share 3D models on websites, such as p3d.in1 or Sketchfab. 2 Organizations are also publishing 3D scans of cultural artifacts through websites, such as 3D-COFORM. 3These websites typically allow users to preview a 3D model so that a user can decide whether to actually download the 3D content. Such a preview is normally achieved through either (i) displaying thumbnail images of the 3D model, taken from representative views (or keyviews), or (ii) providing a video depicting the 3D model from a camera that moves along a camera path, which connects through the keyviews. Image-based preview requires lower transmission bandwidth but conveys a limited amount of information about the model. On the other hand, video-based preview requires a higher transmission bandwidth, but it allows a smooth transition between the keyviews, conveying the overall 3D shape.

We previously proposed a third approach to preview a 3D model, called 3D preview streaming [START_REF] Zhao | 3D mesh preview streaming[END_REF]] that is designed for previewing large 3D models encoded as progressive meshes. 3D preview streaming is similar to video-based preview in that it displays the 3D model at the client as viewed from a moving camera that navigates along a predefined camera path, connecting the keyviews. Unlike video-based previewing, however, 3D preview streaming uses view-dependent progressive mesh streaming to transmit 3D content and renders, locally for the user, parts of the 3D model that are visible from the current viewpoint.

The advantages of 3D preview streaming over video-based preview are as follows. First, if the user decides to interact with and view the 3D model after watching the preview, the 3D model information has already been (partially) downloaded and can be reused. Whereas for video-based preview, the video data downloaded is useless for 3D rendering and interaction. Second, since the user visualizes 3D data, he can choose to preview the model under different rendering parameters (e.g., lighting condition). The video-based preview approach would require a new video every time a rendering parameter is changed. Third, depending on the 3D model's geometric complexity, 3D preview streaming may require lower bandwidth than a high-quality video-based preview. Finally, progressive representation of 3D models allows for quality adaptation to available network bandwidth and display resolution. While scalable video coding and rate adaptation can be used for streaming video-based preview as well, the adaptation of quality is done in the 2D domain, leading to lower perceptual quality of the 3D model.

3D mesh preview streaming has many similarities with video streaming, which allows many techniques of video streaming to be reused: (i) users watch a streamed media content (mostly) passively; (ii) the media content changes with time, and a playback deadline is associated with each element of the media; (iii) a start-up delay for buffering can ensure a smooth playback; and (iv) the quality of the media can be lowered to reduce the data rate.

There are, however, several intrinsic and interesting differences between 3D mesh preview streaming and video streaming. First, the data rate of a video is coupled with its display rate (i.e., frame rate). While reducing a video stream's frame rate can lower its transmission rate, it also lowers the perceptual quality if the frame rate reduces beyond a threshold [START_REF] Chen | Review of low frame rate effects on human performance[END_REF]. As for 3D mesh preview streaming, the data rate is decoupled from its display rate-the display rate is controlled by the rendering rate, whereas the data rate is controlled by the speed of moving camera. Thus, we can reduce the camera speed to reduce the data rate, while keeping the rendering rate constant.

Second, in video streaming, the content of every frame is assumed to be equally, semantically, important. In 3D mesh preview streaming, however, the keyviews are more important than intermediate viewpoints along the path.

Third, in video streaming, the rate control decision can be done independently for a frame or a group of frames. For 3D mesh preview streaming, one triangle can be visible from an arbitarily long sequence of viewpoints. Thus, if not sent, this triangle will still need to be transmitted for an arbitarily long time, leading to nontrivial rate control algorithms. Fourth, by adjusting the camera path, the system can dynamically trade off between the quality of rendered views and the amount of transmitted data, adding another dimension to bandwidth adaptation.

These characteristics of 3D mesh preview streaming lead to new techniques and challenges for bandwidth adaptation and buffer control. In our previous work [START_REF] Zhao | 3D mesh preview streaming[END_REF], we have presented three basic techniques that mirrored the common techniques used in video streaming. The first technique, STOP-AND-WAIT, stops the camera at a keyview when the sending rate reduces and starts moving the camera again when enough data is buffered. This technique is similar to how video playback pauses when there is insufficient data in the buffer. The second technique, REDUCE-SPEED, slows down the camera movement when the sending rate reduces and resumes normal speed when enough data is buffered. This technique is analogous to reducing the video frame rate, but as already explained, is able to maintain a smooth display rate due to decoupling of rendering rate and data rate. The third technique, REDUCE-QUALITY, lowers the quality of the mesh (by sending fewer refinements of progressive meshes) when the sending rate reduces. This technique is analogous to sending fewer layers in a scalable video but with a reduction of quality in the 3D domain.

STOP-AND-WAIT can tolerate the most amount of reduction in bandwidth but is most disruptive to the user viewing experience. We found that both REDUCE-SPEED and REDUCE-QUALITY can adapt to bandwidth reduction up to a certain threshold without causing perceptually obvious differences.

We have also proposed a hybrid strategy that simultaneously reduces the camera speed and reduces the mesh quality. This technique allows the preview to adapt to the importance of the viewpoint and trades off mesh quality with camera speed. As the camera is near the keyviews, the mesh quality is reduced as little as possible, while the camera movement is slowed down. Conversely, the camera speed is maintained as much as possible when viewing other less important regions of the mesh, but the mesh quality is reduced. We call this scheme KEYVIEW-AWARE. User experiments have shown that KEYVIEW-AWARE is preferred by most users, compared to the naive strategies.

In this article, we further propose an alternative technique for bandwidth adaptation. Exploiting the fact that changing the camera path changes the perceptual quality of the mesh and the amount of data that needs to be transmitted, the client modifies the camera path depending on the amount of buffers available, zooming out when the buffer fill level is low and keeping to the original path otherwise. This last technique is called ADAPTIVE-ZOOM. The rest of the article is organized as follows. We first present previous work related to ours in Section 2. Section 3 introduces the background and the basic algorithms of our proposed framework. The bandwidth adaptation schemes are presented in Section 4. We present the evaluation of our schemes in Section 5, and finally we conclude in Section 6.

RELATED WORK

3D Mesh Streaming

We now present previous work on 3D mesh streaming. Previous work considers situations where users are free to interact with the model. None has considered the problem of mesh preview streaming where the camera moves but no interaction is allowed. Meeting playback deadline is not a central issue in these works but is a core consideration of our approach. The concerns in previous work include how to improve the quality of the received mesh as fast as possible, mitigate distortion of the rendered mesh in the presence of packet losses, and scale to a large number of users. Al-Regib and Altunbasak [2005], [START_REF] Li | Middleware for streaming 3D progressive meshes over lossy networks[END_REF], and [START_REF] Chen | Hybrid and forward error correction transmission techniques for unreliable transport of 3D geometry[END_REF] investigated how to choose between different transport protocols for transmissions, trading reliability and delay. [START_REF] Harris Iii | The design of a transport protocol for on-demand graphical rendering[END_REF] designed a new transport protocol that exploits partially-ordered property of 3D objects organized into trees of bounding volumes.

Several existing works also consider error control techniques at the application layer. [START_REF] Park | Error resilient 3-D mesh compression[END_REF] and [START_REF] Yan | Error-resilient coding of 3-D graphic models via adaptive mesh segmentation[END_REF] segmented a progressive mesh into smaller partitions that are loss resilient. Al-Regib et al. [2005] and [START_REF] Chen | Hybrid and forward error correction transmission techniques for unreliable transport of 3D geometry[END_REF] studied error correction for 3D transmission, while [START_REF] Park | Error resilient coding of 3D meshes[END_REF] and [START_REF] Tang | Receiver-based loss tolerance method for 3D progressive streaming[END_REF] investigated error concealment methods. [START_REF] Cheng | An analytical model for progressive mesh streaming[END_REF] and [START_REF] Tian | On-demand transmission of 3D models over lossy networks[END_REF] used retransmissions for error control. We do not consider error control in this article. We believe many of these methods can be adapted into 3D preview streaming easily by additionally considering playback deadline in the error control decision. Such a situation is similar to video streaming and well-known solutions exist. [START_REF] Cheng | Peer-assisted view-dependent progressive mesh streaming[END_REF][START_REF] Cheng | Receiver-driven view-dependent streaming of progressive mesh[END_REF] studied two ways to scale 3D mesh streaming to many users. First, a receiver-driven approach with stateless server is proposed to reduce the computational overhead at the server [START_REF] Cheng | Receiver-driven view-dependent streaming of progressive mesh[END_REF]. Second, a peer-assisted approach is used to reduce the bandwidth overhead at the server [START_REF] Cheng | Peer-assisted view-dependent progressive mesh streaming[END_REF]]. We consider a client-server architecture in this work. The computational overhead of the server, however, is less, since the camera path is predetermined. The use of peer-assisted approach for 3D preview streaming remains an open problem.

The final set of previous work we want to highlight is that of De Silva et al. [2009,2010] who studied 3D progressive mesh streaming from the user perspective. In particular, they measured how well users would tolerate slow mesh refinements and high response time [START_REF] De Silva | Towards understanding user tolerance to network latency and data rate in remote viewing of progressive meshes[END_REF]. Their findings on high tolerance to response time (up to 1s) is relevant to our work, as it indicates that users are willing to view lower-quality meshes and it supports our REDUCE-QUALITY approach to 3D preview streaming. Our user study results validate this finding as well.

3D Object Preview

The related work on 3D object preview focuses on automatic determination of keyviews and generation of camera paths for previews. Many papers have addressed the problem of finding the best view or a set of best views for a scene. We focus here on techniques for a single object and discard the treatment of a whole scene. Early work by [START_REF] Kamada | A simple method for computing general position in displaying three-dimensional objects[END_REF] chose nondegenerated views. Some recent work focused on maximizing a criterion based on the 3D geometry, like maximizing the number of polygons seen or the area covered [START_REF] Plemenos | Intelligent display in scene modeling: New techniques to automatically compute good views[END_REF], the total curvature [START_REF] Sokolov | Virtual world explorations by using topological and semantic knowledge[END_REF], the viewpoint entropy [V ázquez et al. 2001], or the view stability [V ázquez 2009]. [START_REF] Dutagaci | A benchmark for best view selection of 3D objects[END_REF] gave a nice comparison of state-of-the-art methods. Perceptual criteria have also been proposed: gathering user experience [START_REF] Yannakakis | Towards affective camera control in games[END_REF] or tracking eye motion [START_REF] Burelli | Towards adaptive virtual camera control in computer games[END_REF][START_REF] Picardi | Modelling virtual camera behaviour through player gaze[END_REF]]. Some of these techniques generalize naturally to more than one view, such as the work of [START_REF] Feixas | A unified information-theoretic framework for viewpoint selection and mesh saliency[END_REF] which used the entropy of the same object.

Creating a virtual camera path is a common problem in robotics, gaming, or virtual walkthrough. The goals, however, are different. In the context of gaming and virtual walkthrough, the environment is usually a complex scene, and criteria like collision detection are main concerns, whereas visual quality may not be as important. Navigation of viewpoint in such complex worlds uses cinematographic rules [START_REF] Ranon | Accurately measuring the satisfaction of visual properties in virtual camera control[END_REF], dedicated language [START_REF] Lino | A real-time cinematography system for interactive 3D environments[END_REF], or interactions for the camera control [START_REF] Khan | HoverCam: Interactive 3D navigation for proximal object inspection[END_REF]]. 3D preview streaming has a simplified framework: we start from a set of keyviews, selected by an expert for describing the 3D object, and smoothly link the keyviews with an automatic approach. [START_REF] Han | Automatic preview video generation for mesh sequences[END_REF] chose among the visited keyviews using a shortest-path algorithm. In our work, we require an ordering of the keyviews and consider a different cost function between the keyviews. While their cost function depends on the similarity of the keyviews (e.g., viewing angles), our cost function considers the streaming cost. Moreover, their camera path lacks smoothness, which leads to a shaky effect in the resulting videos. Both [START_REF] Burtnyk | ShowMotion -camera motion based 3D design review[END_REF][START_REF] Újar | Way-Finder: Guided tours through complex walkthrough models[END_REF] used smooth paths, respectively, modeled by Bézier or Hermite polynomial curves. Similarly, we use Catmull-Rom splines to interpolate our keyviews and have a smooth path.

A STREAMING FRAMEWORK FOR 3D MESH PREVIEW

Background

Before we describe the framework for 3D mesh preview streaming, we need to describe some background terminologies and relevant techniques that enable preview streaming.

Progressive Mesh. We begin by describing how a 3D mesh is progressively represented, following Hoppe's model [START_REF] Hoppe | Efficient implementation of progressive meshes[END_REF]]. A 3D mesh can be progressively represented by repeatedly performing the edge collapse operation on the edges in the mesh. Each edge collapse operation merges two neighboring vertices into one, therefore simplifying the mesh by reducing the number of vertices by one. The simplified mesh after a sequence of operations is called the base mesh. We can obtain the original mesh from the base mesh by reversing the edge collapses, using an operation called vertex split that takes a merged vertex and splits it into two vertices.

A progressive mesh can be represented with a forest of binary trees, where the root of each tree is a vertex in the base mesh. Every intermediate node is a vertex split, with its two children as vertices that are split from the parent. The leaf nodes in the forest form the vertices of the original mesh.

View-Dependent Progressive Mesh Streaming. Streaming of progressive meshes is done by transmitting over the base mesh, followed by a sequence of vertex splits. As the client receives the vertex splits, it updates and renders the mesh with increased levels of detail. As a result, the user sees the mesh refining itself.

In view-dependent progressive mesh streaming, only vertex splits visible from the current viewpoint are sent. Further, only vertex splits that cause changes larger than one pixel (in the screen space) are sent. We also support out-of-core rendering for large 3D models, where the out-of-view region of the mesh is collapsed to reduce memory requirement.

Mesh Preview Streaming

We now introduce the notion of 3D mesh preview streaming, which is a specific form of view-dependent progressive mesh streaming. In 3D mesh preview streaming, there is no interaction between the user and the 3D model. The sequence of views (viewpoints and virtual camera parameters) is predetermined in the form of a parametric camera path P(•), which is precomputed by the server and communicated to the client. In addition to the camera path, the server also precomputes the in-view vertex splits along the path before streaming and transmits the vertex splits in sequence to the client. The client buffers the base mesh and all the vertex splits of the initial view before it starts playing back the preview.

The client renders the 3D mesh according to the camera path P(t) = (Pos(t), C(t)): at time t, the vertices visible from viewpoint Pos(t) are rendered using the virtual camera parametrized by C(t). The set of parameters C(t) specifies near plane, far plane, field of view, color model, etc. Ideally, the client has received all the vertex splits needed to refine the visible part of the mesh to its full level of detail by time t. The server determines which vertices to send based on the camera path. Ideally, the server always sends all vertices visible from viewpoint P(t 1 ) before the vertices visible only from P(t 2 ) if t 1 < t 2 . Under such conditions, the client would playback the preview of the mesh smoothly at uniform camera speed and at the highest level of detail as the viewpoint moves along the camera path.

Bandwidth-Aware Camera Path

To compute the camera path, we assume that a set of representative views, called keyviews, is given as input. These keyviews can be set manually by the content provider or can be algorithmically determined using the existing methods (see Section 2.2). Given these keyviews, we first determine the order in which the keyviews should be visited. We model the problem as a traveling salesman problem and find the order which maximizes the amount of shared data visible from two consecutive keyviews. We then find a Catmull-Rom spline curve interpolating the keyviews in the chosen order. The details can be found in our previous work [START_REF] Zhao | 3D mesh preview streaming[END_REF]].

Basic Streaming Algorithm

We now describe how the server and the client work in tandem to enable 3D mesh preview streaming.

First of all, we need an arc-length parameterization of the camera path such that the position Pos(t) is at a distance on the path of tt 0 from the starting point Pos(t 0 ). To do that, we compute dense samples on the curve from equally-spaced samples in the parameter space. The distance on the curve is approximated by the length of the piecewise linear approximation of the sample points. This approximated arc-length parameterization is used in the following.

We discretize the camera path into N sample viewpoints corresponding to parameters taken at an equal distance d. The time taken for the camera to travel between two sampled views is 1 unit time. The camera speed is therefore d. We assume the camera speed is constant in the ideal streaming algorithm (unlimited bandwidth).

The server computes M(t), the set of vertices visible from any point along the curve between P(t) and P(t + 1) (inclusive) that have not appeared before in any set M(t ′ ) for t ′ < t. These are the vertices that have not been seen before if the client follows the camera path from P(0) to P(t). The size of the data in M(t) can also be precomputed. We denote the size of M(t) as B(t) (in bits). The playback rate, that is, the rate at which the data are consumed and display, is B(t) (in bits per unit time) in this ideal case.

The server algorithm is simple: for each time t = 0, 1, . . . , N -2, the server sends M(t) with the data rate of B(t). Suppose we start the clock t = 0 at the client one unit time later (plus some delay to account for network latency and jitter) than the server. Then, assuming that the data rate of B(t) is sustainable, this algorithm ensures that the client will receive all data of M(t) by time t for rendering within the next unit time. Now we consider the case where the server has a maximum sending rate of r.

Let B max = max{B(i)|0 ≤ i ≤ N -2}. If r < B max ,
it is possible that at some time t, where B(t) = B max , the client would not have received enough data to display the mesh at full resolution. To counter the mismatch between playback rate and sending rate, the client can wait for an additional B max /r time before starting to render. This start-up delay ensures that the client would continue to playback the 3D preview smoothly and is analogous to the start-up delay introduced in video streaming.

HANDLING BANDWIDTH VARIATIONS

We now consider what would happen if r reduces during streaming. This condition could happen for several reasons. First, there could be a congestion in the network, causing the server to clamp down on the congestion window, effectively reducing the value of r. Second, there could be new clients in the system, causing the server to reduce the value of r for one client to reallocate the bandwidth for the new clients.

A reduction in r would cause the client not to download enough data, since the start-up delay is no longer sufficient to absorb the difference in playback rate and sending rate. While it is possible for the client to be conservative and have a higher start-up delay than B max /r to absorb the variation in r, higher start-up delay sacrifices user experience. Furthermore, if r drops significantly for a longer period, there is no guarantee that the higher start-up delay is sufficient.

As such, we need to support variation of the sending rate r in 3D preview streaming by answering the following question: what should the client (and the server) do when there is insufficient data to display the mesh at full resolution?

In the rest of this section and the next section, we review three basic techniques and a more sophisticated technique that is a hybrid of the three, first proposed in [START_REF] Zhao | 3D mesh preview streaming[END_REF]. We then introduce a new method in Section 4.5.

Pause During Buffering

An obvious solution for the client is to pause the camera at viewpoint P(t) until all data in M(t) are completely received. This method, however, may lead to frequent pausing and jittery camera movement and is thus undesirable.

An alternative is for the client to pause and rebuffer enough data to ensure smooth playback for the rest of the camera path assuming that the current sending rate r(t) stays above a value r min for the rest of the playback. Since B max (t) = max{B(i)|t ≤ i ≤ N -2}, if the client stalls for B max (t)/r min before starting to move the camera again, then there would be sufficient data for the client to render along the rest of the camera path.

These techniques, however, do not exploit a unique property of 3D mesh streaming: some viewpoints are more important and interesting than others. With such semantic information available, we note that if we need to pause, it is better to pause at one of the keyviews. This idea has led to our first method of handling bandwidth variation. The method works as follows: let the sequence of keyviews along the camera path be P(R 1 ), P(R 2 ), . . . , P(R k ), where P(R 1 ) = P(0). After the initial start-up delay, the client first waits for all vertices for P(R 2 ) to arrive (which also implies that all vertices on preceding viewpoints have arrived). The client then starts moving the camera. Upon reaching the viewpoint P(R i ), if the vertices for P(R i+1 ) have not been received, then the client pauses and waits until the vertices for P(R i+1 ) has been received before starting to moving again. This strategy might lead to longer buffering time initially, but if it needs to pause for rebuffering, it always does so at a keyview that is interesting and important.

We collectively call these three methods STOP-AND-WAIT and call the variations "naive", "rebuffer", and "at-keyview", respectively.

Note that for this technique, the server still sends all the vertex splits even when r(t) < B(t). The consequence is that the server will take longer than one unit time to transmit M(t), increasing the duration of the preview.

Reducing Mesh Quality

Another obvious strategy for the client, if it has not fully received M(t) by time t, is to render the set of received vertices anyway, resulting in a mesh of lower level-of-detail. We call this technique REDUCE- QUALITY. Since progressive meshes are used and the client already has the base mesh, the client always has some data to display. The advantage of this approach is that the camera moves continuously at full speed, leading to smooth movement and preserving the preview time of the ideal path.

Unlike the previous technique, the server stops sending M(t) after one unit time and starts sending vertices in M(t + 1). The server's camera speed in this case remains constant.

This technique is similar to streaming fewer layers in a scalable video but having a reduced quality in the 3D domain. Note that, at the end of the preview, the model will not be available at full resolution.

Reducing Camera Speed

The previous two basic techniques are minor variations of well-known techniques in the domain of video streaming. We now consider the third technique which capitalizes on the unique property of 3D mesh preview streaming. Since the rendering rate and playback rate are decoupled, we slow down the playback rate by slowing down the camera when the sending rate r(t) reduces. We call this technique REDUCE-SPEED.

To control the speed of the camera at the client, the client keeps track of the latest viewpoint received and rendered. Suppose the client is rendering viewpoint P(t disp ) and the latest complete viewpoint received is P(t recv ).Consider what happens when the sending rate reduces. Like in STOP-AND-WAIT, the server slows down its camera movement to ensure that full mesh quality is received at the client, allowing t disp to catch up with t recv . To control the camera speed, the client computes periodically the catch-up time, t catch , defined as the time it takes before t disp = t recv .

If t catch falls below a threshold, the client slows down the camera. To recover, the client speeds up the camera if t catch increases beyond another threshold (up to the original camera speed). We limit the camera speed to fall within the range [S min , S max ], where S max , the maximum speed, is the original camera speed specified for the path.

Note that if r(t) drops significantly for a long period of time, REDUCE-SPEED could slow the camera to halt, reducing it to a STOP-AND-WAIT-like scheme. In both STOP-AND-WAIT and REDUCE-SPEED, the duration of the preview is not bounded. On the other hand, REDUCE-QUALITY could end up showing only the base mesh, as little or no data is being received. Neither of which is desirable.

The basic schemes either optimize for speed (REDUCE-QUALITY) or mesh quality (REDUCE-SPEED). We observe that REDUCE-SPEED is more appropriate for when P(t) is close to a keyview, as it gives users more time to view the mesh near the interesting regions. On the other hand, REDUCE-QUALITY is more appropriate away from the keyviews, as reducing the quality of the mesh around non-interesting regions is more acceptable. This observation has led us to design a new keyview-aware scheme that combines these basic schemes.

Keyview-Aware Streaming

Let I(t) be the importance of view P(t). We set I(t) to 1 at each keyview and 0 at the midpoint between two successive keyviews. For other points along the camera path, we interpolate I(t) linearly between 1 and 0

The server algorithm for the keyview-aware scheme is fairly simple: for each time t = 0, 1, . . . , N -2, the server computes its camera speed S s (t) as the following.

S s (t) = S min I(t + 1) + S max (1 -I(t + 1)).

(1)

With this adaptation, the server's camera moves at the slowest speed S min at the keyviews. Note that the control of the server's camera does not (directly) affect the client's camera speed. Rather, by slowing down the server's camera, the server has more time to transmit more vertices, leading to a higher mesh quality.

To slow down the camera at the client near the keyviews, the client controls its camera speed S c (t) similar to the server. S c (t) = S mid I(t + 1) + S max (1 -I(t + 1)), except that S mid is a speed threshold chosen to be higher than S min . We use S mid instead of S min here, since a large change in the client's camera speed is directly perceivable by the user, we keep small variations in the camera speed. Fig. 1. Screen areas of a given region with different perspective projections: with the virtual camera on the original path P(t, 0) (in red), and the virtual camera moved to P(t, z) (in grey). This control, however, does not adapt to sending rate r(t). We need to further adapt the camera speed at the client by considering the gap between t disp and t recv , similar to REDUCE-SPEED. Unlike REDUCE-SPEED, however, the client's camera speed is also dependent on the importance, complicating the calculation of t catch . We therefore use a slightly different method. We let l gap be the distance (along the camera path) between P(t disp ) and P(t recv ), and k be an input parameter that determines how speed scales with l gap . As l gap becomes narrower due to a lower r(t), the camera slows down naturally. The updated formula to compute the camera speed is thus

S c (t) = min{k × l gap , S mid I(t + 1) + S max (1 -I(t + 1))}.
(2)

Note that the camera speed is continuous. If r(t) is too low, then KEYVIEW-AWARE would pause and rebuffer whenever the buffer becomes empty, reducing it to the STOP-AND-WAIT method.

Adapting Camera Zoom

Another interesting difference between 3D preview streaming and video streaming can be exploited: in 3D preview streaming, different camera paths lead to different bandwidth requirements and different view quality. Thus, modifying the camera path provides another flexible dimension in which we can perform bandwidth adaptation. Modifying the camera path, generally, however, is rather challengingwe would like to keep to the given keyviews and computed camera path as much as possible, since they are computed offline. In this article, we therefore consider adapting the camera path by simply zooming away from the 3D object.

Before we explain how we adapt to the available bandwidth, we first explain what we mean by "zooming away" and its effect on the view quality. In our setting, zooming away means moving the camera backwards under the perspective projection, keeping the other camera parameters constant (see Figure 1). Although a zoom-in viewpoint in the original camera path shows the mesh in more detail, a drop in bandwidth (r(t) ≪ B(t)) can affect the quality of the mesh in the KEYVIEW-AWARE scheme, leading to visible flat faces in the rendered surface. In this case, details are missing, so the mesh is actually coarser than the necessary resolution. The original view reveals the piecewise linear structure of the mesh, reducing the perceptual quality for the user. When the camera zooms out, thanks to the perspective projection, the screen area of the mesh decreases, the unit screen area (pixels per polygon) also decreases, refining the view resolution of the mesh surface and retrieving the smoothness of the object.

These observations led us to design an extension of KEYVIEW-AWARE that zooms out the camera to maintain the view resolution, especially under the network condition r(t) ≪ B(t). We call this extension ADAPTIVE-ZOOM. 4.5.1 Camera Zoom. Before we present the technical details of ADAPTIVE-ZOOM, we first illustrate how to adapt the camera trajectory with respect to the original path. Let P(t) be a viewpoint in the original path. Figure 1 shows zooming the camera away at a chosen distance z, which moves the camera from its position on the original path P(t) to P(t, z), where z ≥ 0. We set P(t, 0) = P(t) and P(t, z) = P(t, 0) + z v, where v is a unit vector of direction opposite to the view direction of P(t).

Let K(t, z) be the set of polygons visible from the position P(t, z). We assume that K(t, 0) is not occluded by K(t, z). A(t) is the screen area of the polygons in K(t, 0) rendered with the virtual camera center at P(t, 0), and d(t) is their average depth. Similarly, A z (t) is the screen area of the polygons in K(t, 0) rendered with the virtual camera at P(t, z). Ideally, we have the following equation based on similar triangles.

A z (t) A(t) = d(t) d(t) + z 2 .
(3)

Fixing A(t) and d(t), the screen area A z (t) decreases as the zoom distance z increases. Thus, the unit screen area A z (t)/#K(t, 0) also decreases, improving the view resolution of the polygons in K(t, 0). However, A z (t) may decrease too much if z becomes large: it is undesirable to get a rendered object too small on the screen. 4.5.2 Adaptive Zoom Path. We now describe how to position the camera according to the screen area A z (t) and the unit screen area A z (t)/#K(t, 0).

We first define a range of possible zoom distances, constrained by the reduction in the screen area. In other words, we limit the zoom distance to avoid reducing A z (t) by too much. Given a user-defined minimum ratio (A z /A) min (we use 0.3 in our experiments), we can compute the maximum zoom distance z max (t) at time t based on Equation (3).

z max (t) = 1 ( A z /A) min -1 d(t). ( 4
)
Thus, at each position P(t) in the original camera path, we can zoom out, up to z max (t) units away from the object.

To accommodate zooming out, we extend the notation for M(t) to M(t, z), denoting the set of vertices visible from any point along the curve between P(t, z) and P(t + 1, z) (inclusive) that have not been transmitted before. Similarly, we extend the notation for B(t) (the size of M(t) in bits) to B(t, z).

With the range of zoom distance defined, the server algorithm for ADAPTIVE-ZOOM is as follows: for each t = 0, 1, . . . , N -2, the server sends the set of vertices M(t, z), for z = z max (t), . . . , 0 in decreasing order of z, until either all vertices are sent or the time is up. Similar to KEYVIEW-AWARE, the server's camera adapts its speed based on Equation (1). Let z(t) be the minimum zoom distance such that the server has transmitted M(t, z(t)). Before the server moves its camera to the next point in the camera path, the server notifies the client of the viewpoint P(t, z(t)). Therefore, for each viewpoint P(t), the minimum zoom distance z(t) changes according to the bandwidth r(t).

As in KEYVIEW-AWARE, we set a maximum screen area per polygon to a max pixels to avoid transmitting unnoticeable vertices. Specifically, the server computes and transmits the data in M(t, z) until the screen area of each polygon in the K(t, z) is smaller than a max . If K(t, 0) is not occluded by K(t, z), that is, K(t, 0) ⊆ K(t, z), a max is the upper bound of the average screen area A z (t)/#K(t, 0). In our experiments, a max is empirically set to be one pixel. At the client's side, the camera moves along the path defined by P(t, z(t)) as informed by the server, guaranteeing that the unit screen area of each view is smaller than a max . Similar to KEYVIEW-AWARE, the client updates its camera speed based on Equation (2).

There are a few interesting properties of the ADAPTIVE-ZOOM scheme. First, A z (t) tends to decrease as the zoom distance z increases. In particular, when the whole mesh is in the frustum, increasing z decreases A z (t) (Equation ( 3)). Second, B(t, z) tends to decrease, that is, fewer triangles need to be transmitted as the screen area A z (t) decreases. This is because (i) we set the maximum pixel threshold a max so that the upper bound of the size of M(t, z) would be A z (t)/a max ; (ii) when the camera zooms out, it tends to view more vertices that have been transmitted before, reducing the size of M(t, z) effectively. Third, if the user-defined ratio ( A z /A) min is set to 1, then the maximum zoom distance z max (t) ≡ 0, and the ADAPTIVE-ZOOM scheme reduces to the KEYVIEW-AWARE scheme.

The proposed strategies, in particular the two advanced ones, are evaluated in the next section.

EVALUATION

In this section, we first summarize the evaluation results of the basic 3D preview streaming schemes proposed in [START_REF] Zhao | 3D mesh preview streaming[END_REF], followed by an evaluation of ADAPTIVE-ZOOM and KEYVIEW-AWARE.

Experimental Setup

We used the Thai Statue model from the Stanford 3D Scanning Repository for evaluation in this article. We converted the model into progressive meshes for streaming. The vertex coordinates are encoded with a lossy compression algorithm [START_REF] Cheng | Receiver-driven view-dependent streaming of progressive mesh[END_REF] and are of reduced size. We rendered each model on a 500 × 500 pixels canvas with OpenGL. Table I summarizes the mesh we used and some basic performance metrics of preview streaming. All measurements are done with a Linux PC equipped with Intel Core 2 Quad 2.83GHz CPU, 4GB memory, and NVIDIA GeForce G210 graphics card. We picked ten keyviews for the Thai Statue (three of the keyviews are shown in Figure 3), and constructed the camera path as described in [START_REF] Zhao | 3D mesh preview streaming[END_REF]. The final camera path is shown in Figure 2.

For evaluation, we also implemented a GROUND-TRUTH scheme which assumes the outgoing bandwidth is unlimited, and therefore the preview always has the best quality and constant camera speed.

To simulate the network using TCP with a maximum outgoing bandwidth r(t), we set up both server and client on the same machine. r(t) is tuned by tc, the Linux traffic controller. We tested the Thai Statue with the data rate r(t) that starts from 50KBps and switches between 10KBps and 50KBps every 20 seconds. We use this range of values as it roughly matches the variation in bandwidth required to transmit the Thai Statue model.

Quantitative Results

Before we present the user study, we first illustrate the proposed schemes in greater detail. We present, in this section, the quantitative results from the ADAPTIVE-ZOOM scheme and compare it against KEYVIEW-AWARE. The results of the basic schemes and a more detailed analysis of the KEYVIEW-AWARE scheme can be found in [START_REF] Zhao | 3D mesh preview streaming[END_REF]. 5.2.1 Zoom Paths. Figure 4 illustrates the camera paths of ADAPTIVE-ZOOM at different zoom distances for previewing the Thai Statue. The three figures depict the same set of camera paths viewed from different angles. Each path is a sequence of the viewpoints P(t, z(t)) that are characterized by the zoom distance function z(t) with the maximum value z max (t), where t = 0, 1, . . . , N -2. The red curve is the original camera path with z(t) ≡ 0, while the blue curves are the intermediate zoom paths corresponding to z(t) ≡ α • z max (t), where α = 1 3 , 2 3 , 1. The green curve is the adaptive zoom path recorded on the client side, with the distribution of the z(t) shown in Figure 6(c). As we can see in Figure 4, the set of viewpoints P(t, z(t)) of the zoom path has a one-to-one correspondence to the set of viewpoints P(t, 0) of the original path. KEYVIEW-AWARE uses the original path. To compare with KEYVIEW-AWARE, the parameters of ADAPTIVE-ZOOM at the P(t, z(t)) are shown against the P(t, 0). Therefore, the x-axes of the graphs (Figures 5 andFigures Figure 5(a) shows how much data the two schemes require in total, if the bandwidth is sustainable. ADAPTIVE-ZOOM has a higher demand for transmission bandwidth. As this strategy sends all vertices visible from a camera positioned at different zoom distances, more data may need to be sent, especially in scenarios where zooming away causes more of the 3D object to fall into the camera's view. In total, for the Thai Statue model, an extra amount of 600 KBytes is needed, which is 14.3% more than 4,200 KBytes of KEYVIEW-AWARE. Figure 5(b) shows how much data the client receives at each t recv for both schemes. We see three dips in the figure. The first (around t recv = 200) and third (around t recv = 2000) dips are due to the lack of data to be sent at the corresponding viewpoints. The second (t recv between 1000 and 1500) dip is due to the decrease in bandwidth. We can observe that both schemes behave similarly in the amount of data received.

The next figure, Figure 5(c), shows the estimated bandwidth at the client, plotted against t disp . The number of bytes received in the last two seconds is used to estimate the network bandwidth.

Figure 5(d) plots the camera speed at each t disp . One can see that the camera speed adapts to the distance between the keyviews, slowing down near the keyviews, and achieving maximum speed in between two keyviews. Figure 6 (a) shows the gap between t recv and t disp , plotted against t disp . Note that the gap drops linearly to zero towards the end. Near the end of the session, no more data are being received, and the client is rendering the buffered vertices, allowing t disp to catch up with t recv .

So far, the observed behaviors of KEYVIEW-AWARE and ADAPTIVE-ZOOM are quite close. This result is expected, as ADAPTIVE-ZOOM is based on KEYVIEW-AWARE, sharing similar bandwidth adaptation of camera speed, gap, and received data size. The small divergences are usually caused by different estimated bandwidth (see Figure 5(c)).

The main difference between KEYVIEW-AWARE and ADAPTIVE-ZOOM is the camera position at the client. Even though the two schemes receive almost the same amount of data, ADAPTIVE-ZOOM renders the 3D mesh using a camera at a further distance away such that the average screen area per polygon is kept small, when the client is missing some details from the server. Figure 7 shows the difference between three pairs of simultaneous frames on KEYVIEW-AWARE and ADAPTIVE-ZOOM paths.

Figure 6(b) plots the amount of data that is still missing from the server, while using ADAPTIVE- ZOOM. Should the client received these missing vertex splits, it would have rendered the 3D mesh using the original camera path (i.e., P(t, 0)). We can see that as the estimated bandwidth starts to drop around t disp = 500, the amount of missing vertex splits starts to increase. Note that after the estimated bandwidth has restored to the original level, it takes some time for the amount of missing vertex splits to drop below 100KB. This lag is due to sharing of vertices among the views along the camera path: having less data sent earlier means that more data needs to be sent later.

Figure 6(c) illustrates how the zoom distance z(t) adapts to the bandwidth. When the bandwidth is sufficient (e.g., t disp ≤ 500 or t disp ≥ 1500 in Figure 5(c)), the amount of missing vertex splits starts to drop, allowing the virtual camera to smoothly zoom in, with the zoom distance z(t) → 0 (Figure 6(c)). The zooming operation enlarges the screen area of the mesh quickly (Figure 6(e)), with a small increase in the average screen area per polygon (Figure 6(f)). As such, the client receives all the missing vertex splits, and the ADAPTIVE-ZOOM scheme reduces to the KEYVIEW-AWARE scheme. This effect is especially obvious around t disp = 500 and between t disp of 1750 and 2000 (Figures 6(c)-(f)). Note that, the small fluctuation of camera zoom distance after t disp = 2000 is due to a sudden increase of the amount of required data (Figure 6(b)), due to missing vertex splits.

Moreover, corresponding to the amount of missing vertex splits, we can see that the zoom distance increases between t disp of 500 and 1750. Zooming out, however, leads to more polygons being rendered for the ADAPTIVE-ZOOM scheme between this period (compared to KEYVIEW-AWARE), as shown in Figure 6(d). Within this time period, however, placing the camera further away from the 3D mesh leads to a smaller total screen area for the object (Figure 6(e)). As a result, the average screen area per polygon for the mesh (Figure 6(f)) is kept below two pixels. Note that during this time, KEYVIEW-AWARE continues with the original camera path, and with the drop in bandwidth, the lack of vertex splits being received results in a coarse mesh being rendered-the average screen area per polygon increases to as much as 5 pixels. The last figure (Figure 6(f)) clearly illustrates the advantage of ADAPTIVE-ZOOM.

User Study

We now present the results from a user study which qualitatively evaluates the proposed strategies.

In [START_REF] Zhao | 3D mesh preview streaming[END_REF], we presented two sets of user study experiments, comparing KEYVIEW-AWARE with the basic schemes. We summarize the experimental results in the next section and present a user study comparing ADAPTIVE-ZOOM and KEYVIEW-AWARE in the next section. 5.3.1 Basic Schemes vs. KEYVIEW-AWARE. In the first set of user study, ten participants compare STOP-AND-WAIT schemes against the KEYVIEW-AWARE scheme. The Lucy model, obtained from the Stanford 3D Scanning Repository, is used. Only one participant finds the STOP-AND-WAIT strategy acceptable, regardless of whether the camera stops at a keyview or not. This study shows that, not surprisingly, STOP-AND-WAIT is not a good strategy.

The second set of user studies compares REDUCE-QUALITY, REDUCE-SPEED, and KEYVIEW-AWARE, using both the Thai Statue model (21 participants) and the Lucy model (25 participants). The users are asked to rank the three strategies. The average ranking yields KEYVIEW-AWARE as the best, followed by REDUCE-QUALITY, and then REDUCE-SPEED. Qualitative comments by the participants indicate that, even though they are looking for a better mesh quality, the camera speed of REDUCE-SPEED makes it too boring to watch. For REDUCE-QUALITY, the participants are able to spot coarse mesh quality at certain regions of the models. The KEYVIEW-AWARE scheme is designated by the participants as the most convincing compromise between mesh quality and camera speed. 5.3.2 ADAPTIVE-ZOOM vs. KEYVIEW-AWARE. We now describe the new user study to compare between ADAPTIVE-ZOOM and KEYVIEW-AWARE scheme. The setup and methodology are similar to the experiments to compare KEYVIEW-AWARE and the three basic schemes. We present the details here for completeness.

Set-up. To allow the participants in our user study to experience these different strategies without installing our client, we stream the Thai Statue model using ADAPTIVE-ZOOM and KEYVIEW-AWARE strategies and encode the rendered frames as high-quality video clips, with each video clip corresponding to one preview strategy. The snapshots of selected views of each video clip are shown in Figure 7. We then set up a website for the participants to access, view, and rate these video clips. This website has two pages. On the first page, we present the GROUND-TRUTH along with some instructions and explanations about the overall context of the study. After reading the instructions and viewing the GROUND-TRUTH, the participant moves to a second webpage, where we display two different previews that can be viewed independently and a form to collect participants' answers to questions. The two videos are displayed in a random order generated using a script. The answers are sent to and stored in a remote database. It takes between 10 to 20 minutes for a participant to complete the study, depending on the level of attention. Form. For each preview of the second webpage, we ask each participant whether the quality and the distance to the mesh are acceptable. We do not provide any clue regarding what "acceptable" means, and let the participants judge according to GROUND-TRUTH. Then the participants are asked which preview they prefer. The participants can justify their choices and leave comments in a specific dialog box. Finally, we ask the participants to state their own age, gender, and experience with 3D modeling.

Participants. A total of 21 participants-4 females and 17 males-with age ranging from 22 to 28 and averaging 25 participated in the user study. Table II presents their experience levels. Figure 8 presents the acceptance rate and user preference of each video recorded with different bandwidth settings; 12 participants left comments.

Results. The user study shows that for a bandwidth setting of 50-10-50KBps, more users (67%) preferred ADAPTIVE-ZOOM than KEYVIEW-AWARE. While the comparison between the ADAPTIVE-ZOOM and KEYVIEW-AWARE schemes is not statistically significant, these advanced schemes both provide a better user experience than naive schemes. Moreover, the qualitative comments from the users have confirmed our understanding. One participant commented that he/she prefers a bigger distance between the camera and the mesh, while another commented that the camera of KEYVIEW-AWARE was too close to the mesh to maintain the quality. About the same number of users have found the quality and distance from the object acceptable for ADAPTIVE-ZOOM.

CONCLUSION

3D mesh preview streaming is a new form of continuous media transmission that contains characteristics of both fully interactive 3D progressive mesh streaming and video streaming. We introduce a basic framework for 3D mesh preview streaming and identify several basic ways in which the system can adapt to varying bandwidth. We also introduce an approach that controls both the camera speed and the mesh quality, while being aware of the keyviews of the model. User study reveals that the keyview-aware approach is indeed preferred over the basic approaches. We also explore the possibility of adapting camera position to yield better (perceived) mesh quality by zooming out further away from the mesh when the quality is low. The user study shows that this adapted camera path improves the user experience.

There are many interesting new problems related to 3D mesh preview streaming. We give two examples here. One issue that we are looking at is the construction of a streaming-friendly camera path. Ideally, the data rate as the view moves along the camera path should be as smooth as possible. It is unclear how one can find such a camera path, while balancing the smoothness of data rate and the camera path. Further, in complex objects, the chance that the camera path intersects with the model increases.

Another area of interest is the automatic determination of keyviews. A set of chosen keyviews is a natural and efficient way to indicate a continuous camera path. Currently, finding keyviews and finding the camera path are two independent processes. It is, however, possible to refine both iteratively. A keyview can, for instance, be nudged if doing so would lead to a better camera path without sacrificing the importance of the area being viewed. Doing so would require analysis of the 3D model and some semantic/context information.

We note that the work is a first approach and can be extended to consider other cases (e.g., using artistic or dynamic camera paths). But a predefined camera path nails down the many degrees of 3D navigation freedom to one: the speed. Exploiting the camera speed is a first step and has already led to various proposed schemes. We have also shown that a simple edition of the path, here zooming away by moving the virtual camera, can help adapt the streaming to bandwidth variation. We could consider more degrees of freedom in the navigation in the future.

Fig. 2 .

 2 Fig. 2. The original camera path for the Thai Statue. The black points are the camera positions corresponding to keyviews.

Fig. 3 .

 3 Fig. 3. Three of the chosen keyviews for the Thai Statue.

Fig. 4 .

 4 Fig. 4. Zoom paths for the Thai Statue. The original path (in red), three zoom paths (in blue) for different z, and the adaptive zoom path (in green).

Fig. 5 .

 5 Fig. 5. Evolution of preview streaming schemes for the Thai Statue, recorded on the client side.

  6), the gap (Figure 6(a)), and the client's camera speed (Figure 5(d)) are shown in OpenGL coordinate units of the length of the original camera path. The vertical lines indicate the positions of the keyviews. 5.2.2 Evolution over Time. Figures 5(a)-(d) and Figures 6(a)-(f) illustrate how KEYVIEW-AWARE and ADAPTIVE-ZOOM behave over time as bandwidth changes.

Fig. 6 .

 6 Fig. 6. Evolution of preview streaming schemes for the Thai Statue, recorded on the client side.

Fig. 7 .

 7 Fig. 7. View quality of selected views of the Thai Statue. Top: KEYVIEW-AWARE. Bottom: ADAPTIVE-ZOOM.

Table I .

 I Measurements of 3D Mesh PreviewStreaming along a Camera Path (Figure2)

	Measure	Thai Statue
	Number of Vertices	5 million
	Number of Triangles	10 million
	Size of Transmitted Mesh	81.2 MB
	Size of Base Mesh	10.3 KB
	Number of Vertices in Base Mesh	16
	Size per Vertex-Split	17 bytes
	Precision of Vertex Coordinates	17 bits
	Render Frame rate	10-18 fps
	Network Overhead	244 bytes

Table II .

 II User Experience Levels with 3D Modeling Percentages of users finding whether the quality or the distance is acceptable for a given video, and whether this video is preferable.

	NO EXPERIENCE	NOVICE	AVERAGE	KNOWLEDGEABLE	EXPERT
	9	6	3	0	3
	Fig. 8.

http://p3d.in.

http://shw.gl.

http://www.3d-coform.eu.Authors' addresses: S. Zhao (corresponding author) and W. T. Ooi, National University of Singapore; email: {shzhao17, ooiwt}@ comp.nus.edu.sg; A. Carlier, G. Morin, and V. Charvillat, University of Toulouse; email: axel.carlier@enseeiht.fr; {morin, charvi}@n7.fr.

ACKNOWLEDGMENTS

We thank the participants of our user studies for their participation, Jia Han Chiam for his implementation of the TSP solution, and the Stanford Computer Graphics Laboratory for making available the meshes we use in this research.