Sloven Dubois

Renaud P Éteri

Michel M Énard

A 3D DISCRETE CURVELET BASED METHOD FOR SEGMENTING DYNAMIC TEXTURES

Keywords: 2D+T discrete curvelet transform, video segmentation, octree structure, dynamic textures

This paper presents a new approach for segmenting a video sequence containing dynamic textures. The proposed method is based on a 2D+T curvelet transform and an octree hierarchical representation. The curvelet transform enables to outline spatio-temporal structures of a given scale and orientation. The octree structure based on motion coherence enables a better spatio-temporal segmentation than a direct application of the 2D+T curvelet transform. Our segmentation method is successfully applied on video sequences of dynamic textures. Future prospects are finally exposed.

INTRODUCTION

A moving crowd, rippling water, smoke or grass blown by the wind are different aspects of visual patterns called Dynamic Textures (DT). DT are time-varying patterns with a certain spatial and temporal stationarity. As the real world scenes include a lot of these motion patterns, any advanced video processing application will need to be able to handle DT. Dynamic textures are currently a very active research topic ( [START_REF] Filip | Fast synthesis of dynamic colour textures[END_REF][START_REF] Szummer | Temporal texture modeling[END_REF][START_REF] Doretto | Dynamic texture segmentation[END_REF][START_REF] Péteri | Dynamic texture recognition using normal flow and texture regularity[END_REF][START_REF] Zhao | Dynamic texture recognition using local binary patterns with an application to facial expressions[END_REF][START_REF] Dubois | A comparison of wavelet based spatio-temporal decomposition methods for dynamic texture recognition[END_REF]). Being able to segment these DT spatially and temporally is a highly challenging problem because of their unknown spatial and temporal extend. In this article, we present a method for segmenting DT based on an advanced tool of signal processing, the 3D discrete curvelet transform [START_REF] Candes | Curvelets : A Surprisingly Effective Nonadaptive Representation for Objects with Edges[END_REF].

The curvelet transform has been designed for improving the limitations of the wavelet transform : while wavelets catches 1D singularities, curvelets can detect structures of other dimensional structures (of co-dimension 1). The discrete curvelet has been recently extended to the third dimension [START_REF] Candes | Fast discrete curvelet transforms[END_REF][START_REF] Ying | 3d discrete curvelet transform[END_REF].

In this article, time is considered as the third dimension and curvelets are applied to image sequences. These 2D+T curvelets detect surface-like singularities and can then be a promising tool for studying dynamic textures that are often composed of propagating fronts.

This article is organized as follows : section 2 presents the main properties of the 3D discrete curvelet transform. In section 3, the 3D discrete curvelet transform is directly applied to synthetic video sequences and results are discussed. A new method for segmenting a video with dynamic textures is described in section 4. This method is based on a 2D+T curvelet transform and an octree hierarchical representation. The curvelet transform enables to outline spatio-temporal structures of a given scale and orientation. The octree structure based on motion coherence enables a better spatio-temporal segmentation than a direct application of the 2D+T curvelet transform. Our segmentation method is then applied on video sequences containing dynamic textures (section 5). Future prospects are finally exposed.

THE 3D DISCRETE CURVELET TRANSFORM

The 3D curvelet transform of a volume f (x), f ∈ L 2 (R 3 ), x corresponding to 3D coordinates x = (x 1 , x 2 , x 3 ), outputs a collection of coefficients c(j, ℓ, k) defined by the following inner product :

c(j, ℓ, k) := f, ϕ j,ℓ,k = R 3 f (x)ϕ j,ℓ,k (x)dx (1)
where ϕ j,ℓ,k is the curvelet at scale j ∈ Z, in direction ℓ ∈ Z and position k = (k 1 , k 2 , k 3 ). Formula (1) can be expressed in the frequency domain as :

c(j, ℓ, k) := 1 (2π) 2 f (ω ω ω) ϕ j,ℓ,k (ω ω ω)dω ω ω (2)
where ω ω ω = (ω 1 , ω 2 , ω 3 ) are frequency domain variables. In this work, the discrete implementation of the curvelet transform is used (see [START_REF] Candes | Fast discrete curvelet transforms[END_REF]).

ϕ j,ℓ,k is defined in the frequency domain by :

ϕ j,ℓ,k (ω ω ω) = U j,ℓ (ω ω ω)e i x (j,ℓ) k ,ω ω ω (3)
with U j,ℓ (ω ω ω) is a discrete frequency window which isolates frequencies near scales j and direction ℓ.

e i x (j,ℓ) k ,ω ω ω represents the translation of the curvelet at position k. This frequency window is expressed by :

U j,ℓ (ω ω ω) = W j (ω ω ω)V j,ℓ (ω ω ω) (4)
where W j (ω ω ω) and V j,ℓ (ω ω ω) correspond respectively to the radial and angular frequency windows.

The radial window at scale j > 0 is expressed by :

W j (ω ω ω) = Φ 2 j+1 (ω ω ω) -Φ 2 j (ω ω ω) ( 5
)
where Φ is defined as the product of one dimensional lowpass windows

Φ j (ω 1 , ω 2 , ω 3 ) = φ(2 -j ω 1 )φ(2 -j ω 2 )φ(2 -j ω 3 ).
The function φ respects 0 φ 1, is equal to 1 on [-1; 1] and 0 on ] -∞; -2] and on [2; +∞[. This window is colored with mean gray on figure 1.

The angular window is defined according to the unit cube face. For example, V j,ℓ (ω ω ω) is defined relative to the axis ω 1 by :

V j,ℓ (ω 1 , ω 2 , ω 3 ) = φ 2 j/2 ω 2 -α ℓ ω 1 ω 1 φ 2 j/2 ω 3 -β ℓ ω 1 ω 1 (6)
For the other cube faces, the definition is similar by exchanging the role of ω 1 , ω 2 and ω 3 . This window is represented by light gray color on figure 1. Fig. 1. Discrete frequency tiling (adapted from [START_REF] Candes | Fast discrete curvelet transforms[END_REF]). The light and the mean gray colors represent respectively the window V j,ℓ (ω ω ω) and W j (ω ω ω). The composition of two windows U j,ℓ (ω ω ω) is colored in black.

The algorithm of the 3D discrete curvelet transform is summarized as follows :

-Compute the 3D Fourier transform of f .

-For each scale and each direction, obtain the product U j,ℓ (ω ω ω) f (ω ω ω). -Wrap this product around the origin to obtain W(U j,ℓ f )(ω ω ω).

W is the wrapping operation. -Take the inverse 3D Fourier transform to W(U j,ℓ f ) for collecting the different discrete coefficients c(j, ℓ, k).

For more information on the 3D discrete curvelet transform, one can refer to [START_REF] Candes | Fast discrete curvelet transforms[END_REF][START_REF] Ying | 3d discrete curvelet transform[END_REF].

The 3D discrete curvelet transform was originally designed for three dimensional spatial data (x, y and z). In order to apply this transform to video, we introduce z = c.t, where c is a constant that enables to keep the homogeneity between spatial and temporal variables. The constant c is homogeneous to speed and can be adapted to the considered video.

In the next section, the 2D+T curvelet transform is used for the spatio-temporal segmentation of videos.

DIRECT SEGMENTATION USING THE 2D+T DISCRETE CURVELET TRANSFORM

In this section, the 2D+T curvelet transform is applied for extracting DT occurring at different spatio-temporal scales and orientations. This 'direct' method is computed on video of figure 2 More a frequency with a given orientation ℓ and scale j occurs in a video, higher the energy of the corresponding curvelet will be. In the frequency domain, this phenomenon generates a high response in the window U j,ℓ . This sector represents the main spatio-temporal direction of the video.

Our method for extracting the main DT in a video is the following :

1. Compute the 2D+T discrete curvelet transform on the whole video.

2. For each direction ℓ at each scale j, compute the energy :

E j,ℓ = 1 N j,ℓ k |c(j, ℓ, k)| 2 (7)
where N j,ℓ is the number of coefficients located in the wedge (j, ℓ).

3. Compute the inverse 2D+T discrete curvelet transform by keeping the main energy peaks only.

Figure 3 shows the video with the computed mask superimposed. This mask is constructed according to the occurrence of the main direction and scale in the video.

OCTREE DECOMPOSITION USING THE 2D+T DISCRETE CURVELET TRANSFORM

In the previous section, the segmentation was obtained using a 2D+T discrete curvelet transform performed on the whole video. Due to this global computation of the curvelet transform, only the main DT is detected and the extracted spatial and temporal borders are imprecise.

A way to improve this segmentation is to divide the video into several smaller cubes and apply the 2D+T discrete curvelet transform onto each cube. Our method is based on an octree structure for dividing the video and uses the 2D+T discrete curvelet coefficients for the homogeneity criterion. If the video cube is homogeneous in terms of curvelets coefficient energy, the octree division is stopped, otherwise the video cube is again divided into eight subcubes (figure 4). This method tends to subdivide regions located next to the spatio-temporal borders and does not affect regions with homogeneous spatio-temporal frequencies. The octree algorithm outputs a tree decomposing the video. To get a spatio-temporal segmentation, the decomposition tree is scanned and similar cubes, in terms of curvelet orientation, are merged. Compared to the method of section 3, several DT can be extracted and a finer spatio-temporal segmentation can be achieved.

APPLICATION

The following examples illustrate the whole method on real videos. The first video 5. Results of the spatio-temporal segmentation using the proposed method are displayed on figure 6. The rippling water composed of one spatio-temporal direction (figure 5.(a)) is mainly detected as one homogeneous region (figure 6.(a)). The region containing the duck is considered as an ambiguous area and is thus not colored. One can noticed at the bottom of video 6.(a) an ambiguous area and oversplitted cubes caused by the disturbances created by the wake of the duck.

Video 5.(b) is a difficult case as the two dynamic textures are both transparent and sometimes overlap. One can however see on video 6.(b) that our algorithm was able to distinguish between the two dynamic textures. Some mistakes occur at the border, where ambiguity increases because of some overlaps between the two dynamic textures.

  .(a) that contains a DT orientated with two different directions and of figure 2.(b) where the same DT occurs at two different scales.

Fig. 2 .

 2 The image sequence (a) represents a dynamic texture (an escalator) with two spatio-temporal directions. One motion is oriented in the xt plane and the other in the yt plane. Video (b) represents the same DT at two different scales (one has a double frequency than the other).

Fig. 3 .

 3 Segmented videos of the main spatio-temporal scale and orientationResults of figure3clearly show that it is possible to segment a video into regions having similar spatio-temporal directions and scales. The segmentation frontiers are however imprecise and only one DT is detected. The next section proposes a method for improving the segmentation.

Fig. 4 .

 4 Fig. 4. General principle of the octree structure

Fig. 5 .

 5 (a) is a single dynamic texture of rippling water. This dynamic texture is 'disturbed' by a swimming duck. The second video 5.(b) is composed of two dynamic textures having different spatio-temporal characteristics : a waterfall and tree branches waving in the wind. Original videos. Main spatio-temporal directions are symbolized by arrows.

Extract a segmentation mask by thresholding in the video domain.

Our algorithm can separate dynamic textures in both space and time. Compared to the previous method presented in section 3, several DT can be extracted and the borders are more precisely segmented. One can mention that the precision of the border extraction depends on the shape and size of the smallest octree element.

CONCLUSION AND PROSPECTS

This paper explores the use of the 3D curvelet transform for video processing. Two methods for segmenting spatially and temporally image sequences with dynamic textures are exposed. The first method is a direct application of the curve-let transform to the whole video. The second method is based on an octree structure and uses curvelet coefficients as the homogeneity criterion. Applications of this new method on real videos are presented.

Current works aim at modifying the homogeneity criterion for refining the octree subdivisions next to borders. A more geometrically adapted scheme for computing the curvelet transform is also under study.

Segmentation results of this method will be used for the indexation of dynamic textures in large video database [START_REF] Dubois | A comparison of wavelet based spatio-temporal decomposition methods for dynamic texture recognition[END_REF].