Spatial diffusion in images

This application claims the benefit, under 35 U.S.C. §119 of EP Application 07301345.0, filed Sep. 6, 2007.

The invention is related to spatial diffusion in images. Spatial diffusion is used for rendering images, especially but not exclusively for non-photorealistic rendering (NPR). Spatial diffusion helps blurring small discontinuities. Edges become sharper by spatial diffusion as well.

NPR comprises stylization techniques for transforming natural images and/or videos into painterly styled or cartoon styled images and/or videos. In this specification, we will use the term image as referring to a still image as well as an image frame in a video sequence.

Primarily, stylization was applied for artistic purposes only. But, as styled images comprise less details and/or larger areas of uniform pixel stylization it is used for efficient visual telecommunication, also. A stylized image comprises a smaller high frequency portion than the corresponding natural image. Therefore, it is better compressible. A decoded stylized image comprises less annoying artefacts than the corresponding natural image compressed with the same compression rate.

A common technique for spatial diffusion is iterative Gaussian spatial bilateral filtering.

In visual telecommunication, it is important that stylization is achieved in real time.

Thus, there is a need for efficient stylization techniques.

This is achieved by a method for spatial diffusion in an image, the method comprising the features of claim 1 .

Said method comprises applying an inverted Gaussian spatial bilateral filter on the input image.

It is preferred that the inverted Gaussian spatial bilateral filter comprises a spatial weight which takes the form of an inverted Gaussian.

The inverted Gaussian spatial bilateral filter, which uses an inverted-Gaussian function as the kernel of spatial filter, can remove small spots in large smooth areas more efficiently than traditional Gaussian-spatial bilateral filter. In a single pass, it achieves blurring and edge sharpening comparable to that achievable with traditional filtering in several passes.

The inverted-Gaussian-spatial bilateral filter is suited especially for NPR but might be useful in photorealistic rendering, as well.

Preferably, the method further comprises receiving a user input and applying on the input image a mean shift modification instead of the inverted Gaussian spatial bilateral filter in dependency on the user input.

This allows a user for switching between a computationally more efficient spatial diffusion method and an aesthetically more attractive spatial diffusion method.

An exemplary embodiment of the invention is illustrated in the drawing and is explained in more detail in the following description.

In the figure:

FIG. 1 shows a flowchart of an exemplary spatial diffusion method allowing a user to switch between different spatial diffusion techniques

FIG. 2 shows a workflow of an exemplary Mean-shift modification.

In an exemplary embodiment of FIG. 1 , spatial diffusion is realized in a switching method SWM. This switching method SWM allows a user to switch between two different spatial diffusion techniques. That is, the user may decide whether s/he prefers highly aesthetic cartoon effects over efficient computation or vice versa.

The switching method SWM also allow for performing both spatial diffusion techniques in parallel. So stylization of a common source image for different applications like preparation for streaming on wireless devices and preparation for movie theatre presentation can be done, both.

In a first step INP, an input image and the user's choice on the spatial diffusion techniques which shall be applied to the input image are received. Then, in a first decision step 1 DEC it is decided whether the user's choice comprises application of a mean shift modification. If so, step MSM, which performs the mean shift modification, is executed and the method passes on to a second decision step 2 DEC. Otherwise, step MSM is skipped and the method passes directly to the second decision step 2 DEC. In step 2 DEC it is decided whether the user's choice indicates execution of inverted Gaussian spatial bilateral filtering. If so, the method transits to inverted Gaussian spatial bilateral filtering in step IGSB. Then the results of mean shift modification and/or inverted Gaussian spatial bilateral filtering are outputted in step OUT.

The different spatial diffusion techniques are explained in detail below.

Mean Shift Modification

If highly aesthetic cartoon effects are desired, a mean-shift algorithm adapted for a graphic processing unit (GPU) is applied for spatial diffusion. For a given center pixel C n =(x c , y c , L c , a c , b c ) n with spatial components x and y and colour components L, a and b in CIE-Lab color space, a mean-shift vector m h,G (C) is calculated as follows:

m h , G ⁡ ( c n ) = ∑ s ∈ Ω ⁢ ⁢ s * g h ⁡ ( s , c n ) ∑ s ∈ Ω ⁢ ⁢ g h ⁡ ( s , c n ) - c n ( 1 )

wherein s=(x s , y s , L s , a s , b s ) is one of the surrounding pixels in a set of pixels Ω around center pixel C n wherein the pixel set Ω comprises only those pixels which are in a vicinity of the current center pixel and have a color space distance to the center pixel which is below a given threshold:

( L s −L cn ) 2 +( a s −a cn ) 2 +( b s −b cn ) 2 <T ∀sεΩ   (2)

Good results were achieved with T=20.

g h ( • ) is a profile of a kernel function G( • ):

G(x)=α*g h (∥x∥ 2 ) with a normalising constant α. g h ( • ) depends on parameter h:

The kernel function is determined by help of a Sobel operator.

After calculation of the mean shift vector the center pixel is shifted by the mean shift vector spatially and/or in one or more color dimensions. Calculation and shifting is repeated until the mean-shift vector equals Zero. In the mean shift filtered final image, the colour components of convergence (L con , a con , b con ) are assigned to a pixel p after at the position (x c0 ,y c0 ) of the initial center point c 0 :

p after =(x c0 ,y c0 ,L con ,a con ,b con )  (4)

In practice, repetition is terminated as soon as the mean-shift vector is below a shifting threshold.

Such mean shift filtering may be applied to some or all pixels.

The GPU-Version mean-shift algorithm used in the exemplary embodiment terminates after a fix number of iteration, independent from the mean-shift vector values. By doing so, the algorithm could be implemented on GPUs much easier and with great improvement of computational efficiency. The workflow is shown in FIG. 2 . On side of a central processing unit (CPU), data is arranged and a rendering environment is initialized. The “Original Texture” stores a current input image frame. On side of a graphic processing unit (GPU), mean-shift vectors are updated iteratively in a pixel shader. The “Ping Texture” and the “Pong Texture” are used during the iterative rendering. The number of the iterations is fixed. Good results were achieved with five iterations over a window size of 10×10.

The results were highly aesthetic with cartoon-like effect justifying an increased computational effort due to a larger filtering window and a higher number of iterations compared to bilateral filtering.

Inverted-Gaussian-Spatial Bilateral Filtering

Alternatively, if efficient computation is preferred over aesthetics, an adapted bilateral filter is applied.

Bilateral filters have the attribute of preserving crisp edges.

The intensity change dI Ω′ (c) of a pixel c due to bilateral filtering over an area Ω′ could be derived in a generalized form as follows:

Here, a is a neighbouring pixels in a window Ω′ around pixel c, and I( • ) returns a pixel's intensity value of one of the CIE-Lab colour space colour components in the input picture. P( • ) returns the position of a pixel, f( • ) is a spatial filtering function and g( • ) is an intensity filtering function.

Bilateral filtering is often iterated until intensity changes drop below a chosen filtering threshold or even until they reach zero.

The inverted-Gaussian-spatial bilateral filter uses for spatial filtering the following filtering functions which takes a curve of inverted Gaussian:

f ⁡ ( P ⁡ ( a ) - P ⁡ ( c ) ) = C - ⅇ - 1 2 ⁢ ( D ⁡ ( P ⁡ ( a ) , P ⁡ ( c ) ) σ d ) 2 ( 6 )

wherein D( • ) is a distance function like Euclidean distance or absolute distance. Good results were achieved with an Euler distance function E( • ) returning the Euler distance between two pixels. C is a freely selectable constant. Good results were achieved with C=2.

By using an inverted Gaussian filter function a larger area is taken into account for filtering whereby the area directly surrounding the pixel subject to filtering is taken less into account. Given, there is a small spot of a first colour within a large area of a continuous colour which is different from the first colour. Then, closely located pixels of the spot do contribute less to the filtering of a spot pixel than with a standard Gaussian filter function. At the same time, more distant pixels of the continuous colour contribute more to the filtering than with a standard Gaussian filter function. Therefore, the inverted Gaussian filter contributes to an improved removal of spots from large areas with continuous colours.

For intensity filtering the following filtering function gave good results:

Thus, within the exemplary embodiment the intensity I′ Ω′ (c) of a pixel c after inverted Gaussian spatial bilateral filtering over an area Ω′ is determined as:

I Ω ′ ′ ⁡ ( c ) = ∑ a ∈ Ω ′ ⁢ ⁢ I ⁡ ( a ) ⁢ ⅇ - 1 2 ⁢  I ⁡ ( a ) - I ⁡ ( c ) σ r  2 ( 2 - ⅇ - 1 2 ⁢ ( D ⁡ ( P ⁡ ( a ) , P ⁡ ( c ) ) σ d ) 2 ) ∑ a ∈ Ω ′ ⁢ ⁢ ⅇ - 1 2 ⁢  I ⁡ ( a ) - I ⁡ ( c ) σ r  2 ( 2 - ⅇ - 1 2 ⁢ ( D ⁡ ( P ⁡ ( a ) , P ⁡ ( c ) ) σ d ) 2 ) ( 8 )

wherein σ d is related to the blur radius and so determines the window Ω′ and σ r is related to the extent of the intensity filtering. With σ r =4.5 and σ d =2.5 good results were achieved. Filtering for some or all colour components in CIE-Lab colour space is performed.

The spatial diffusion step blurs small discontinuities and sharpens edges within each frame, guided by a nonlinear diffusion function that varies over the image.