# Patent

## Title
Dealiasing method and device for 3D view synthesis

## Abstract

The present disclosure is directed to a method and a device for dealiasing borders in a 3D interpolated view, the interpolated view comprising at least foreground pixels with foreground video in formation and background pixels with background video information. The method comprises the step of detecting, in an interpolated disparity map, associated to the 3D interpolated view, an aliased border between the foreground pixels with a foreground disparity value and the background pixels with a background disparity value, the aliased border delimiting an inner aliased contour formed by foreground pixels and an outer aliased contour formed by background pixel, the aliased border having the form of a stair line; determining a weighting/dealiasing coefficient for each pixel of the outer contour said coefficient corresponding to the part of the pixel area included in the virtual right triangle defined by the two sides of each stair line to the area of the pixel; calculating video information for each pixel of the outer contour in combining the background video information and the foreground video information in a proportion defined by the determined weighting/dealiasing coefficient and replacing video information for each pixel of the outer contour by the calculated video information.

## Background
This application claims the benefit, under 35 U.S.C. §365 of International Application PCT/EP13/050701, filed Jan. 16, 2013, which was published in accordance with PCT Article 21(2) on Jan. 3, 2014 in English and which claims the benefit of European patent application No. 12174005.4, filed Jun. 28, 2012.
FIELD OF THE INVENTION
The invention relates to a device and a method for dealiasing borders in 3D view synthesis. The invention relates to rendering of 3D content.
BACKGROUND OF THE INVENTION
View interpolation consists in interpolating a disparity map for the new view, and then in synthesizing the view by interpolating video information using this interpolated disparity map and the left or right views.
Aliasing will appear in the interpolated disparity map. During the view synthesis, the picture information is interpolated using this interpolated disparity map with this aliasing. This introduces aliasing in the projected view.
This problem occurs because the common disparity map format defines only one disparity value per pixel. As a result for a pixel lying on an object border this value can either be the disparity value of the background object or the disparity value of the foreground object. This means that in the disparity map objects have aliased borders. Since this disparity map is used to render the synthesized view, the synthesized view will also show aliased object borders.
A disparity map represents for each pixel the disparity between the left and the right frames or pictures. A depth map represents for each pixel the depth of the corresponding object in the 3D scene. The invention will be described using a disparity map but is exactly the same if using a depth map.
However on object borders for some pixels there is background and foreground video information. But since in the disparity (resp. depth) map only one disparity value per pixel can be stored, this value cannot be exactly correct. For a pixel on the object border this value can either be the disparity value of the background object, the disparity value of the foreground object, or a value in between.
As a result object borders in the disparity map can only be located at pixel borders. This means that in the disparity map object borders exhibit aliasing.
Document D1 (Boundary matting for view synthesis from S. Hasinoff) proposes a method called boundary matting to reduce the “cut-out” appearance. This method exploits multiviews to perform alpha matting and to refine stereo depths at the boundaries with sub-pixel accuracy. The method aims at defining precise object boundaries using the picture information and relies on quite complex matting techniques.
Document D2 (U.S. Pat. No. 6,577,307) discloses an anti aliasing process for 3D graphic rendering. The method retrieves the depth of two nearest polygons, and stores the corresponding color information and a weighing value indicating the percentage of coverage of a pixel. This weighting value is used to blend the foreground and background colors. The object boundaries and the percentage of coverage of a pixel depend only on the position of the polygons which are perfectly known. This method cannot be used in case of view synthesis since the exact object border shapes are not known.
SUMMARY OF THE INVENTION
The present invention is directed to a method of dealiasing borders in a 3D interpolated view, the interpolated view comprising at least foreground pixels with foreground video information (V1) and background pixels with background video information (V2). The method comprises the step of detecting, in an interpolated disparity map, associated to the 3D interpolated view, an aliased border between the foreground pixels with a foreground disparity value (D1) and the background pixels with a background disparity value (D2), the aliased border delimiting an inner aliased contour formed by foreground pixels and an outer aliased contour formed by background pixel, the aliased border having the form of a stair line; determining a weighting/dealiasing coefficient (DC) for each pixel of the outer contour said coefficient corresponding to the part of the pixel area included in the virtual right triangle defined by the two sides of each stair line to the area of the pixel; calculating video information for each pixel of the outer contour in combining the background video information and the foreground video information in a proportion defined by the determined weighting/dealiasing coefficient (DC) and replacing video information for each pixel of the outer contour by the calculated video information.
Thus the present invention proposes a dealiasing method which considers only the data of the disparity map to determine how to combine foreground and background video information.
In a preferred embodiment, the transition video information is calculated in adding to a part corresponding to the weighting/dealiasing coefficient of the foreground video information and the complementary part of the background video information
In a preferred embodiment, the inner aliased contour consists in foreground disparity pixels neighbored by pixels so that the absolute difference of a neighbor pixel disparity value with the foreground disparity value is bigger than a determined threshold value.
In a preferred embodiment the outer aliased contour consists in background disparity pixels neighbored by pixels so that the absolute difference of a neighbor pixel disparity value with the background disparity value is bigger than a determined threshold value.
In a preferred embodiment, the given threshold corresponds to one pixel disparity.
In a preferred embodiment, straight lines are segments between stair lines end points.
In a preferred embodiment, straight lines are limited to 32 pixels
In a preferred embodiment, the method is applied to 2D to 3D conversion.
The invention consists, too, in a device for dealiasing a border in a 3D interpolated view, the view comprising at least foreground pixels with a corresponding foreground video information (V1) and background pixels with a corresponding background video information (V2). The device comprises detecting means for detecting in an interpolated disparity map, an aliased border between foreground pixels with a corresponding foreground disparity value (D1) and background pixels with a corresponding background disparity value (D2), the aliased border delimiting an inner aliased contour formed by foreground pixels and an outer aliased contour formed by background pixels, the aliased border having the form of a stair line; determining means for determining a weighting/dealiasing coefficient (DC) for each pixel of the outer contour said coefficient corresponding to the part of the pixel area included in the virtual right triangle defined by the two sides of each stair line to the area of the pixel; calculating means for calculating video information for each pixel of the outer contour in combining the background video information and the foreground video information in a proportion defined by the determined weighting/dealiasing coefficient (DC) and means for replacing the video information for each pixel of the outer contour by the calculated video information.
In a preferred embodiment the calculating means of the device for calculating the transition video information consists in means for adding to a part corresponding to the weighting/dealiasing (DC) coefficient of the foreground video information (V1) the complementary part (1−DC) of the background video information (V2).
In a preferred embodiment, the device is used for 2D to 3D conversion.



BRIEF DESCRIPTION OF THE DRAWINGS
The above and other aspects of the invention will become more apparent by the following detailed description of exemplary embodiments thereof with reference to the attached drawings in which:
FIG. 1 represents a block diagram corresponding to the interpolation of a view
FIG. 2 represents an example of a disparity map with object border
FIG. 3 illustrates the definition of the inner and outer contours according to an embodiment of the invention
FIG. 4 represents an example of a virtual triangle defined on the contour in the disparity map according to the invention
FIG. 5 represents a disparity map and corresponding interpolated video image without dealiasing
FIG. 6 represents a disparity map and corresponding interpolated video image with dealiasing according to the invention
FIG. 7 corresponds to a video image before and after the dealiasing and shows how the aliasing and the “cut-out” appearance are reduced



The local contour shape of object aliasing is detected in the disparity map. Accordingly a sub-pixel shape is added to smooth this contour.
So that along the object borders of the interpolated view the pixels video information will be a combination of background and foreground video information.
The view interpolation consists in interpolating a disparity map, either the left disparity map or the right disparity map or both. It consists further in synthesizing the view by interpolating video information using disparity values of the interpolated disparity map, the video information of the left and/or right views.
The aliasing effect occurs because in the 1-layer disparity map format we use, only one disparity value is stored per pixel. Therefore in the disparity map, object borders are located at pixel borders between pixels with a foreground disparity value corresponding to the disparity of the foreground object and pixels with a background disparity value corresponding to the disparity of the background.
FIG. 1 corresponds to a block diagram of a 3D view synthesis obtained from a left view and a right view, a left disparity map and a right disparity map. The disparity map projection block consists in projecting at least one disparity map onto the view to be synthesized.
To suppress the aliasing effect, which can appear on the object borders, a dealiasing block according to the invention is added to the disparity map projection block. The video interpolation block combines values of the dealiased disparity map, the left view and the right view to create the interpolated view.
FIG. 2 represents in a disparity map the border of an object in form of stairs corresponding to a pixels border between a foreground disparity value D1 and a background disparity value D2.
A solution according to the invention consists in using locally a 2-layer representation. It is thus possible to store two disparity values per border pixel. But instead of using the video information to define an alpha value using matting information estimation like in Document 1, the invention proposes to simply fill the stairs along the object borders with some foreground video information. The part of foreground video information is determined by a combination of the two disparity values. This is done by detecting the aliased borders in the interpolated disparity map and by virtually adding a sub-pixel shape to smooth these contours.
Thus, the invention proposes a solution which relies on replacing in the interpolated disparity map the stair lines of the aliased contours by virtual straight lines. The lines are “virtual” because these lines will not be visible contrary to the visible stairs.
The corresponding virtual surface between the aliased border and the proposed straight line in the interpolated view is filled with some foreground information. By construction, this process will alter only one line of pixels around the objects.
Therefore to one line of pixels along the object borders will correspond two disparity values, and thus a combination of background and foreground video information.
Each pixel intersecting these virtual triangles will be rendered using foreground and background video information. These two video information values will be combined with a weighting/dealiasing coefficient depending of the virtual line, as it will be further explain with the FIG. 4.
The visibility of aliasing in the rendered image depends on the position of the object borders in the disparity map in relation to the position of the object borders in the video/picture. If the object borders in the disparity map include a “sufficient” part of the background, and if the background is homogeneous, in this case no aliasing will be visible. But as soon as the background is not homogeneous near the disoccluded or occluded area, or as soon as the object borders in the disparity map does not include background video or picture information, aliasing becomes visible. This means that depending on the local configuration, it can be better to have or not to have a part of background included in the segmentation of the foreground object in the disparity map.
These aliasing effects can be quite visible on high contrast borders between foreground and background objects, and can get even more visible when they start moving, even slightly. This can happen for various reasons like slight motion, noise or small instabilities.
This aliasing effect is the result of another artifact: the hard transitions, which occur because the disparity map has hard transitions. Hard transitions appear when there is no soft transition between objects; this happens in the present case because, as we have seen previously, the disparity map cannot correctly handle soft borders. These hard transitions in the synthesized view do not look natural and are usually not consistent with the rest of the picture. The proposed solution suppresses also these hard transitions.
Hard transitions can be seen as the effect of cutting an object along its borders, and then pasting it onto the background; and aliasing as the same effect while cutting the object along pixels borders.
Thus, with the method of the invention, object borders are softened by adding some foreground video information to fill the stairs along the object borders. First, the aliased contours need to be detected. These contours correspond to the object borders in the interpolated disparity map. Therefore we propose to detect them by comparing the disparity values of neighbor pixels in the interpolated disparity map.
In the disparity map two kinds of pixels need to be detected: the pixels belonging to the inner contours with a foreground disparity value D1, and the pixels belonging to the outer contours with a background disparity value D2. FIG. 3 illustrates an aliasing contour in a disparity map with the inner contours represented in black and the outer contours in gray of the aliased border. The inner contours belong to the foreground objects and therefore occlude the outer contours. Pixels belonging to the outer contours are in the local background. These are the pixels to which a second disparity value corresponding to the disparity value of the pixels of the inner contours will be assigned. The inner contour pixels define the aliasing shape, and thus the altering that will be applied to the outer contour pixels.
The object contours can be for example detected by comparing the disparity value of each pixel with the disparity values of its direct neighbor pixels. A pixel can be tagged as belonging to a contour if one of the differences with its neighbor pixels is bigger than a given threshold, for example 1 pixel disparity. And two direct neighbor pixels tagged as belonging to a contour can be tagged as belonging to the same object inner contour if the absolute difference of their disparity values is smaller than a given threshold; for example 0.5 pixel disparity.
Once the object contours have been identified, the contour or aliasing shapes need to be evaluated.
Referring to FIG. 4, the two end points A and B of the local aliasing element which form a step from the edge to the riser of the aliasing element need to be identified. These end points A and B of a stair are used to define the virtual triangles, and thus a weighting/dealiasing coefficient DC will be defined for each pixel intersecting this defined triangle as following: the weighting/dealiasing coefficients DC for each pixel correspond to the part of the area inner the virtual triangle relative to the area of the pixel.
An example of a virtual triangle is given by the FIG. 4. The weighting coefficients are easy to determine once the virtual triangle is known. For the example in FIG. 4, the weighting/dealiasing coefficients DC1 to DC11 of pixels P1 to P11 correspond to the part of the area inner the virtual triangle relative to the area of the pixel. These weighting/dealiasing coefficients DC1 to DC11 (from left to right) are equal to: 21/22, 19/22, 17/22, 15/22, 13/22, 11/22, 9/22, 7/22, 5/22, 3/22 and 1/22 respectively. Thus with these weighting/dealiasing coefficients DC1 to DC11 which corresponds to the proportion of the foreground disparity in the pixel, a corresponding part of foreground video information will be added to the background video information to fill the stairs along the object borders of the interpolated view. In this example, associated to the pixel P1 the weighting/dealiasing coefficient is DC1=21/22. And consequently associated to the pixel P1, a part corresponding to this weighting/dealiasing coefficient DC1 of the video information is the foreground video information, the complementary part (1−DC1) being background video information. Associated to the pixel P2 the weighting/dealiasing coefficient is DC2=19/22. And consequently, associated to the pixel P2, a part corresponding to this weighting/dealiasing coefficient DC2 of the video information is the foreground video information, the complementary part (1−DC2) being background video information. If a pixel belongs to several virtual triangles, the maximum of the weighting/dealiasing coefficients can be used and it will determine which virtual triangle to use to alter the pixel. More complex solutions evaluating the visible surface of each virtual triangle are also possible taking into account the potential occlusions depending on the local disparity of each virtual triangle.
It is possible to limit the size of the triangles, for example to 32 pixels. A sufficient size can suppress the aliasing effect while bigger sizes would not give significant improvement, and depending on the implementation this can limit the search range for the contours.
This operation assigns two disparity values and one weighting coefficient to each pixel. As indicated above it is possible to assign more disparity values and corresponding weighting coefficients depending on the level of complexity. One disparity value corresponds to background information which is the former disparity value of the outer contour pixel, the others) correspond(s) to the foreground object(s).
The principle of the invention is that added foreground video information to the background video information corresponds to triangular surfaces in the disparity map which is the difference between the aliased contour and the proposed straight line.
The intersection between these triangles and each pixel surface defines indirectly the percentage of foreground video information that will be added to the background video information of each pixel as each pixel intersecting the added triangle will use for the foreground information the same disparity as the closest pixel in the corresponding inner contour. The advantage of using direct neighbor disparity values is that continuous foreground information is used to render the object borders, thus preventing additional visible artifacts from appearing.
In the rendered view, the result will be similar to anti-aliasing applied directly to a perfect 3D model of the views. It is however different since in the present case the aliased object borders are not known as only the aliased border of the disparity map is known.
The invention can be implemented using different methods.
A method of the invention is that the detection of the object contours can be done once for the complete picture, tagging each pixel belonging to an inner and/or an outer contour accordingly. For each inner contour, the local segments of the aliasing shape needs to be identified; this determines the virtual triangles to be added. Then for each outer contour pixel, depending on the virtual triangle intersections with the pixel, and optionally the local disparity of each inner contour depending on the chosen strategy, the inner contour(s) to consider are chosen.
A method of the invention is that the operation can be done pixel by pixel: for each pixel, a preferred method consists in determining if this pixel belongs to an outer contour. For each corresponding inner contour pixel, find the local end points of the aliasing shape by comparing the disparity values of the successive direct neighbors. From these end points which are the positions of the edge and the riser A and B, determine the right triangle surface associated to each inner contour. Then decide which inner contour(s) to consider depending on the virtual triangle intersections with the pixel, and optionally the local disparity of each inner contour. This defines the weighting/dealiasing coefficient linked to each inner contour. Finally the video information value of the pixel can be evaluated using these weighting/dealiasing coefficients, foreground video information and background video information
Disparity map and corresponding interpolated video information without dealiasing are represented by the left picture of FIG. 5 and the right picture of FIG. 5 respectively.
Disparity map and corresponding interpolated video with dealiasing are represented by left picture of FIG. 6 and the right picture of FIG. 6 respectively.
The FIGS. 5 and 6 illustrate this process on a basic example. The FIG. 5 shows on the left an interpolated disparity map without dealiasing and on the right the result of video information interpolation without dealiasing. The FIG. 6 shows on the left the same disparity map with the virtual shape, thus indicating the part of the foreground video information to be added to the background video information of the aliased contour. FIG. 6 shows on the right the corresponding result of the interpolated video information using the dealiasing method of the invention.
The results on the 3D interpolated view are represented by FIG. 7 by comparing how the aliasing and the “cut-out” appearance are reduced between the above view and the under view.
This problem can also occur during 2D to 3D conversion. The difference is that the disparity map is obtained differently and that the disocclusions are handled differently, using in-painting technique for example.
Since this solution is applied after the disparity map projection, this requires only small modifications of the view synthesis architecture.
This can be used in post-production tools e.g. for 2D to 3D conversion, or for view synthesis, or in TV or in STB to interpolate new views e.g. for depth adjustment.

## Claims

1. A method of dealiasing a border in a 3D interpolated view, the view comprising at least a border determined by foreground pixels with a corresponding foreground video information and background pixels with a corresponding background video information, the method comprising:
detecting, in an interpolated disparity map associated with the 3D interpolated view, an aliased border between the foreground pixels with a corresponding foreground disparity value and the background pixels with a corresponding background disparity value, the aliased border delimiting an inner aliased contour formed by foreground pixels and an outer aliased contour formed by background pixel, the aliased border having the form of a stair line;
determining a weighting/dealiasing coefficient for each pixel of the outer contour said coefficient corresponding to the part of the pixel area included in the virtual right triangle defined by the two sides of each stair line to the area of the pixel, wherein straight lines, limited to 32 pixels, are segments between stair line end points, and form a side of the virtual right triangle;
calculating video information for each pixel of the outer contour in combining the background video information and the foreground video information in a proportion defined by the determined weighting/dealiasing coefficient; and
replacing video information for each pixel of the outer contour by the calculated video information.

2. The method of dealiasing as claimed in claim 1 wherein calculating the transition video information consists in adding to a part corresponding to the weighting/dealiasing coefficient of the foreground video information and the complementary part of the background video information.

3. The method of dealiasing as claimed in claim 1 wherein the inner aliased contour consists in foreground disparity pixels neighbored by pixels so that the absolute difference of a neighbor pixel disparity value with the foreground disparity value is bigger than a determined threshold value.

4. The method of dealiasing as claimed in claim 1 wherein the outer aliased contour consists in background disparity pixels neighbored by pixels so that the absolute difference of a neighbor pixel disparity value with the background disparity value is bigger than a determined threshold value.

5. The method of dealiasing as claimed in claim 3 wherein the given threshold corresponds to one pixel disparity.

6. The method of dealiasing as claimed in claim 1 wherein the method is applied to 2D to 3D conversion.

7. A device for dealiasing a border in a 3D interpolated view, the view comprising at least foreground pixels with a corresponding foreground video information and background pixels with a corresponding background video information, comprising:
at least one processor and a memory, said at least one processor being coupled to said memory and said at least one processor being configured to:
detect in an interpolated disparity map, an aliased border between foreground pixels with a corresponding foreground disparity value and background pixels with a corresponding background disparity value, the aliased border delimiting an inner aliased contour formed by foreground pixels and an outer aliased contour formed by background pixels, the aliased border having the form of a stair line;
determine a weighting/dealiasing coefficient for each pixel of the outer contour said coefficient corresponding to the part of the pixel area included in the virtual right triangle defined by the two sides of each stair line to the area of the pixel, wherein straight lines, limited to 32 pixels, are segments between stair line end points, and form a side of the virtual right triangle;
calculate video information for each pixel of the outer contour in combining the background video information and the foreground video information in a proportion defined by the determined weighting/dealiasing coefficient; and
replace the video information for each pixel of the outer contour by the calculated video information.

8. The device as claimed in claim 7 wherein the at least one processor is further configured to calculate video information and further configured to add to a part corresponding to the weighting/dealiasing coefficient of the foreground video information the complementary part of the background video information.

9. The device as claimed in claims 7 and 8 wherein the device is used for 2D to 3D conversion.