Directional hole filling in images

0001The invention relates to image processing, more particularly to assigning pixel values to unassigned pixel locations in an image.

0002Providing depth perception when displaying video information comprising image sequences on a compatible 2D display is an area of growing interest. A possible method of providing depth perception is by presenting to a viewer at least two images of a same scene, viewed from two positions a little way apart from each other. Apparent displacement or difference in apparent direction of objects of the same scene viewed from two different positions is called parallax. Parallax allows the viewer to perceive the depth of objects in a scene. A plurality of images of the same scene, viewed from different virtual positions, can be obtained by transforming a 2D image supplied with depth data for each pixel value of the 2D image. For each point in the scene, a distance of the point to the image capturing device, or to another reference point, or to a plane such as a projection screen, is captured in addition to a pixel value. Such a format is usually referred to as a 2.5 D (image+depth) video format.

0003When transforming a 2.5D video format to a plurality of images viewed from different positions, it can occur that for certain output pixels, no input data is available. Therefore, these output pixels do not have any definite values assigned in their pixel locations. These unassigned pixel values cause artifacts called ‘holes’ in the transformed images. In this document, a ‘hole’ or a ‘region with unassigned pixels’ will be interchangeably used to refer to a region comprising pixel locations of unassigned pixel values. The adverse visual effect of a hole is more pronounced in an occlusion region. An occlusion and a de-occlusion region in video information are caused by the movement of a foreground object against a background region. Discontinuities in depth data typically occur at the transition from foreground to background, causing de-occlusion of the background resulting in holes in the transformed plurality of images. Hole filling algorithms can be employed to overcome these artifacts.

0004Holes can also occur in decoded output of 2D video information comprising image sequences that were encoded according to well known video compression schemes that use forward motion compensation. In such a video compression scheme, regions of pixels in a frame are predicted from projected regions of pixels of a previous frame. This is called a shift motion prediction scheme. In this scheme of prediction, some regions overlap and some regions are disjoint due to motion of objects in the frames. Pixel locations in the disjoint areas do not get assigned with definite pixel values. Thus holes occur in the decoded output of 2D video information comprising image sequences. Furthermore, in object based video encoding schemes e.g. MPEG-4, where backgrounds and foregrounds are coded separately, un-referenced areas may be present in the background causing holes. Hole filling algorithms can be employed to overcome these artifacts.

0005Several algorithms for hole filling are discussed in the article “Depth-Image-Based Rendering (DIBR), Compression and Transmission for a New Approach on 3D-TV” by C. Fehn in Proceedings of SPIE Stereoscopic Displays and Virtual Reality Systems XI, pages 93-104, San Jose, Calif., USA, January 2004. The algorithms discussed include linear colour interpolation between scene foreground and background, simple extrapolation of the scene background and mirroring of background colour information along the borders of occlusion regions. Smoothing the depth information with a suitable Gaussian filter is also suggested. All these techniques obviously lead to varying amounts of visual distortions in the displayed image.

0006It is desirable to provide a method of hole filling in an image that leads to less visual distortion in the displayed image.

0007Accordingly, in a method of hole filling or assigning pixel values in a region comprising pixel locations of unassigned pixel values in an image, a first pixel location is selected in a first neighbourhood adjoining the region of unassigned pixel values. A second neighbourhood that includes the first pixel location is also selected. A direction of an image feature relative to the first pixel location is estimated using a first set of pixel values from the second neighbourhood. A second set of pixel values is selected from pixel locations in the estimated direction from the first pixel location. A third set of pixel values are computed from the second set of pixel values. At least a part of the region comprising pixel locations of unassigned pixels is assigned with pixel values by using the third set of pixel values.

0008It is also desirable to provide an image processing device for hole filling in an image that leads to less visual distortion in the displayed image.

0009Accordingly, a device is provided for hole filling or assigning pixel values to pixel locations in a region comprising pixel locations of unassigned pixel values in an image. The device comprises a first selector, a second selector, an estimator, a third selector, a first processor and a second processor. The first selector selects a first pixel location in a first neighbourhood adjoining the region of unassigned pixel values. The second selector selects a second neighbourhood that includes the first pixel location. The estimator estimates the direction of an image feature relative to the first pixel location using a first set of pixel values of the second neighbourhood. The third selector selects a second set of pixel values from pixel locations in the estimated direction from the first pixel location. The first processor computes a third set of pixel values from the second set of pixel values. The second processor assigns pixel values to pixel locations of at least a part of the region comprising pixel locations of unassigned pixel values using the third set of pixel values.

0010It is also desirable to provide an image processing device for hole filling, including a receiver for receiving a signal representing a sequence of images and a display device for displaying the sequence of images.

0011Accordingly an image processing device is provided which includes a receiver for receiving a signal representing a sequence of image and a device for hole filling or assigning pixel values to pixel locations in a region comprising pixel locations of unassigned pixel values in at least one image belonging to the sequence of images. The image processing device includes a display device for displaying the sequence of images.

0012It is also desirable to provide a computer program comprising code means for hole filling in an image that leads to less visual distortion in the displaced image.

0013Accordingly, a computer program comprising program code means is provided for hole filling or assigning pixel values to pixel locations in a region comprising pixel locations of unassigned pixel values in an image according to all the disclosed methods.

0014These and other aspects of the method and device for assigning pixel values to pixel locations in a region comprising pixel locations of unassigned pixel values in an image are apparent from and will be elucidated with reference to the implementation and embodiments described hereinafter and with reference to the accompanying drawings. These figures are schematic representations of one of many examples of the disclosed method and devices, wherein:

0015<figref idref="DRAWINGS">FIG. 1</figref> is an example image with a region comprising pixel locations of unassigned pixel values and associated neighbourhoods;

0016<figref idref="DRAWINGS">FIG. 2</figref> is an enlarged view of a part of the example image;

0017<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart illustrating a method of hole filling in images;

0018<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustrating a step of estimating the direction of an image feature;

0019<figref idref="DRAWINGS">FIG. 5</figref> illustrates relative positions of a first region and a number of candidate regions;

0020<figref idref="DRAWINGS">FIG. 6</figref> illustrates a method of filling a hole after finding the directions of image features relative to pixels on the first neighbourhood of the hole;

0021<figref idref="DRAWINGS">FIG. 7</figref> is an embodiment of a device for hole filling in images; and

0022<figref idref="DRAWINGS">FIG. 8</figref> is an embodiment of an image processing device including a device for hole filling, a receiver and a display device.

0023<figref idref="DRAWINGS">FIG. 1</figref> is an example image <b>100</b> with a region <b>110</b> comprising pixel locations of unassigned pixel values and associated neighbourhoods. The example image further shows a first pixel <b>120</b> selected from a first neighbourhood <b>130</b> of the region <b>110</b>, an estimated direction <b>140</b> of an image feature <b>160</b> relative to the first pixel location <b>120</b>, a second neighbourhood <b>150</b> whose pixel values are used in the estimation of direction <b>140</b>. While transforming a 2.5D image data, discontinuities in depth data in occlusion regions can be one of the causes for the region <b>110</b> to occur. The region <b>110</b> can occur while computing a set of multi-view images from a lesser number of multi-view images e.g. computing a set of ten multi-view images from a stereo pair. The region <b>110</b> can also occur as a result of shift motion prediction scheme or an object based coding scheme in a well known video compression scheme e.g. MPEG-4. The region <b>110</b> can be called a hole. The hole <b>110</b> generally contains random or zero pixel values causing visual artifacts in the rendered image.

0024The first neighbourhood <b>130</b> is selected such that the first pixel location <b>120</b> selected from it is substantially close and sufficiently away from the boundary of the hole <b>110</b> to avoid pixels in the transition region. In this example, the first neighbourhood <b>130</b> is shown as a narrow strip of a few pixels width around the perimeter of the hole <b>110</b>. In case of a foreground object moving against a background region, the first neighbourhood <b>130</b> is selected only from the background region. It is assumed that the foreground and background regions in a scene are already identified. The image feature <b>160</b> is a representative feature e.g. a linear feature or a texture feature present in the image <b>100</b>. The direction <b>140</b> of the image feature <b>160</b> relative to the first pixel location <b>120</b>, is estimated using a first set of pixel values in the second neighbourhood <b>150</b>. The first set of pixel values in the second neighbourhood <b>150</b> are selected by excluding the unassigned pixel values of the hole <b>110</b>. Note that the second neighbourhood <b>150</b> can overlap with the first neighbourhood <b>130</b> and also with the hole <b>110</b>.

0025<figref idref="DRAWINGS">FIG. 2</figref> is an enlarged view of a part <b>150</b> of the example image <b>100</b>. A first region <b>210</b> and a few candidate regions <b>220</b>, <b>230</b>, <b>240</b> are also shown. These candidate regions are used in the estimation of a direction <b>140</b> of an image feature <b>160</b> relative to the first pixel <b>120</b>. The first region <b>210</b> is shown to include the first pixel location <b>120</b> and overlapping with the hole <b>110</b>. A number of candidate regions <b>220</b>, <b>230</b>, <b>240</b> are adjacent to the first region <b>210</b> and are located in the second neighbourhood <b>150</b>. The first region <b>210</b> and the candidate regions <b>220</b>, <b>230</b>, <b>240</b> may be adjoining, overlapping or disjoint to each other. The shape of these regions need not be restricted to the square shape shown. Several shapes, e.g. rectangular or irregular shapes corresponding to an object in the image are possible. In the example shown, the image feature <b>140</b> is present in the first region <b>210</b> and in one of the candidate regions <b>230</b>. The location of the candidate region <b>230</b> is determined from the pixel values in the neighbourhood <b>150</b>.

0026<figref idref="DRAWINGS">FIG. 3</figref> is a flow chart illustrating a method <b>300</b> of hole filling in images. The image <b>100</b> comprising one or more regions of unassigned pixel values is made available at the starting step <b>301</b>. A first pixel location <b>120</b> is selected in a first neighbourhood <b>130</b> in the first step <b>310</b>. In the next step <b>320</b>, a second neighbourhood <b>150</b> is selected to include the first pixel location <b>120</b> . The second neighbourhood <b>150</b> is chosen such that it is possible to identify and estimate the direction <b>140</b> of an image feature <b>160</b> e.g. a texture or a linear feature in it. The direction <b>140</b> of the image feature <b>160</b> is estimated in the next step <b>330</b> from the pixel values of the second neighbourhood <b>150</b>. The details of direction estimation will be explained in the description of <figref idref="DRAWINGS">FIG. 4</figref>. In the next step <b>340</b>, a second set of pixel values are selected in the estimated direction <b>140</b>. The sequential order of the selected pixels is preserved for subsequent use. In step <b>350</b>, a third set of pixel values is computed from the second set of pixel values. In one of the embodiments, the third set of pixel values can be obtained by interpolating the values of the second set of pixel values. In another embodiment, the third set of pixel values can be extrapolated from the values of the second set of pixel values. The number of pixels in the second and the third set need not be the same. One of the many well known interpolation techniques e.g. polynomial curve fitting, of deriving a set of pixel values from another set of pixel values can be applied. A part of the region <b>110</b> is assigned with pixel values derived from the third set of pixel values in the next step <b>360</b>. In one of the embodiments, pixel values in the direction <b>140</b> of the image feature <b>160</b> are extended to fill the region <b>110</b>. The pixel locations lying in the extended direction of the image feature with reference to the first pixel location are filled using the third set of pixel values. When a foreground object is moving against a background region, the foreground object uncovers certain area of the background region. The hole created in such a case is typically filled with the pixels derived from the background region. Continuity of the image feature is preserved in the extended direction and the visual distortion is minimised. In one of the embodiments, pixel values from the estimated direction are used in the reverse order (mirroring) for filling the unassigned pixel locations in the region <b>110</b>. The results obtained from the proposed embodiments are better than blurring or extrapolation or interpolation of pixel values selected in fixed directions such as horizontal or vertical direction. The steps <b>310</b>-<b>360</b> are repeated for a number of selected first pixels in the first neighbourhood and the hole is filled gradually. A controlling step <b>370</b> is provided to ensure that the method <b>300</b> is repeated until the region <b>110</b> is completely filled. The controlling step <b>370</b> also ensures that all the regions with unassigned pixel values are filled with appropriate pixel values by one of the said embodiments. A few isolated pixel location may still be unassigned due to the errors that arise due to the representation of direction in a digital grid. Pixel values from the nearest neighbours can be used to fill in such isolated pixels. After being filled with appropriate pixel values in the regions of unassigned pixel values, the image <b>100</b> is made available at the output <b>371</b> of the method <b>300</b>.

0027For filling holes in occlusion regions caused by the movement of a foreground object against a background region, the foreground object has to be identified first. While rendering frames for 3D displays, the foreground/background information can be obtained from the depth map and the rendering algorithm. In case of a motion compensated video compression system, the same information can be obtained from the motion vector field and the occlusion regions.

0028<figref idref="DRAWINGS">FIG. 4</figref> is a flow chart illustrating the step <b>400</b> of estimating the direction <b>140</b> of the image feature <b>160</b>. The region <b>100</b> comprising the hole <b>110</b>, the first pixel location <b>120</b>, the first neighbourhood <b>130</b> and the second neighbourhood <b>150</b> is made available at the input <b>401</b> of the step <b>400</b>. In the first step <b>410</b>, the first region <b>210</b> around the first pixel location <b>120</b> is chosen. The first region <b>210</b> contains a part of the image feature <b>160</b>. A number of candidate regions <b>220</b>, <b>230</b>, <b>240</b> are selected in the next step <b>420</b>. The candidate regions can be selected at a predetermined, fixed distance from the first region <b>210</b>. The candidate regions <b>220</b>, <b>230</b>, <b>240</b> may or may not overlap the region <b>100</b>. A large number of candidate regions may be selected to find the extension of the image feature <b>160</b>. Pixel values of the first region <b>210</b> are used in the calculation of a similarity value with pixel values of each one of the candidate regions. The unassigned pixel values that belong to the region <b>210</b> are excluded in the computation of similarity values.

0029A similarity value is calculated in the next step <b>430</b> for each one of the candidate regions by comparing the available pixels of the first region <b>210</b> with respective pixels of each one of the candidate regions <b>220</b>, <b>230</b>, <b>240</b>. The similarity value can be e.g. based on a correlation measure of pixels or a normalised sum of mean absolute deviation of the respective pixels. A correlation measure based on several values derived from pixel values e.g. mean intensity or variance can also be used in the computation of the similarity value. From the set of computed similarity values, a particular candidate region <b>230</b> that is best matching with the first region <b>210</b> is identified in the next step <b>440</b>. The best matching candidate region <b>230</b> typically contains the extension of the image feature <b>160</b> and the location of the particular candidate region <b>230</b> indicates the possible direction of the image feature <b>160</b>. In the next step <b>450</b>, the direction of the image feature <b>160</b> is estimated from the location of the first region <b>210</b> and the location of the best matching candidate region <b>230</b>.

0030<figref idref="DRAWINGS">FIG. 5</figref> illustrates relative positions of a first region <b>500</b> and a number of candidate regions. In this example, a first pixel <b>501</b> is assumed to be located at the origin (<b>0</b>,<b>0</b>). The first region <b>500</b> is shown in solid lines as a square block of 8×8 pixels located at the origin. A set of eight possible candidate regions <b>510</b>-<b>580</b> are shown in discontinuous lines as square blocks of 8×8 pixels in the neighbourhood of the first region <b>500</b>. In this example, the locations of candidate regions are shown as blank circles. These locations are chosen such that their absolute distance from the first pixel location is eight pixel units in either or both the horizontal and vertical directions. More candidate regions can be selected at intermediate positions shown as filled circles. There are a total of 64 possible locations (blank and filled circles) shown in the neighbourhood of the first region. A boundary <b>590</b> of a hole is shown. The candidate regions whose locations e.g. (−<b>8</b>, <b>8</b>), (<b>8</b>,<b>8</b>) that fall within the hole need not necessarily participate in the computation of similarity values. The similarity values are calculated for the candidate regions that are located typically at all filled circles and blank circles outside the boundary <b>590</b> of the hole. From the set of similarity values, a candidate region closely matching with the first region <b>510</b> is selected. From the location of the selected candidate region, the direction relative to the first pixel is estimated. If the selected candidate region is located at e.g. (<b>8</b>,<b>0</b>), the direction <b>504</b> of the line joining (<b>0</b>,<b>0</b>) and (<b>8</b>,<b>0</b>) can be represented as (<b>8</b>,<b>0</b>) in this example. Two more examples of directions <b>503</b>, <b>505</b> of the line joining (<b>0</b>,<b>0</b>) with (<b>8</b>,−<b>1</b>) and (<b>8</b>, +<b>1</b>) are also illustrated in <figref idref="DRAWINGS">FIG. 5</figref>.

0031<figref idref="DRAWINGS">FIG. 6</figref> illustrates a method of filling a hole after finding the directions of image features relative to pixels on the first neighbourhood of the hole. The filling is demonstrated in four stages in the <figref idref="DRAWINGS">FIGS. 6</figref> (a), (b), (c) and (d). Blank squares represent the pixel locations of unassigned values and shaded squares represent the pixel locations of known values. The region of shaded squares is assumed to comprise one or more image features. The blank and shaded regions form a part of a digital image with row numbers from <b>200</b> to <b>209</b> and column numbers from <b>99</b> to <b>105</b>. The coordinates of the top left corner are (<b>91</b>, <b>200</b>). In column <b>105</b>, the directions of the image features at the respective pixel locations in that column are shown. The directions (<b>8</b>,<b>1</b>), (<b>8</b>,<b>0</b>) and (<b>8</b>,−<b>1</b>) follow the notations explained in the description of <figref idref="DRAWINGS">FIG. 5</figref>. Pixel locations in the hole are first filled with the row and column numbers of the known pixel values from the shaded squares of the image. In the first step, coordinates are filled and in the subsequent step, actual pixel values are filled. In one embodiment, known pixel values in the direction mentioned at each pixel location e.g. (<b>8</b>,<b>0</b>) in column <b>105</b> are first selected. The selected pixels are used to fill up the blank squares in the reverse order (mirroring) in the reverse direction. On a digital grid, discontinuities may occur while representing directions other than horizontal and vertical directions. Due to the discontinuities, the pixel values are filled up in a piece-wise linear fashion. In <figref idref="DRAWINGS">FIG. 6</figref> (<i>a</i>) and (<i>b</i>), the direction (<b>8</b>,<b>0</b>) being horizontal, three rows <b>207</b>, <b>208</b>, <b>209</b> at the lower parts of the hole are filled without any discontinuity. The next two lines in the extension of (<b>8</b>,<b>1</b>) are filled in a piece-wise linear fashion. As shown in <figref idref="DRAWINGS">FIG. 6</figref> (<i>b</i>), in row <b>206</b>, the four pixels closer to the column <b>105</b> are filled first. The remaining two pixels are shifted up by one row and therefore blank spaces are observed in the locations (<b>99</b>,<b>207</b>) and (<b>100</b>, <b>206</b>). In rows <b>202</b> and <b>203</b>, pixels from direction (<b>8</b>, −<b>1</b>) are used for filling blank locations. Four pixel locations in columns <b>99</b> and <b>100</b> in the rows <b>202</b>, <b>203</b> are already filled with the pixels from the direction (<b>8</b>,<b>1</b>). These four locations can either be filled with the pixels from the direction (<b>8</b>,<b>1</b>) or from the direction (<b>8</b>, −<b>1</b>). In such situations of multiple choices, the pixels from a stronger direction of an image feature, having a higher similarity value can be chosen. The number of pixels selected in the estimated direction need not be equal to the number of pixels required to be filled in the hole. Required number of unknown pixels can be derived from a lesser or more number of known pixels, by any one of the well known interpolation or extrapolation methods.

0032<figref idref="DRAWINGS">FIG. 7</figref> is an embodiment of an image processing device <b>700</b> for hole filling in images The device <b>700</b> comprises a first selector <b>710</b>, a second selector <b>720</b>, an estimator <b>730</b>, a third selector <b>740</b>, a first processor <b>750</b> and a second processor <b>760</b>. The first selector <b>710</b> is arranged to select the first pixel <b>120</b> and the first neighbourhood <b>130</b>. The second selector <b>720</b> is arranged to select a second neighbourhood <b>150</b>. The estimator <b>730</b> is arranged to estimate a direction <b>140</b> of an image feature <b>160</b> relative to the first pixel location <b>120</b>. The third selector <b>740</b> is arranged to select a second set of pixel values from respective pixel locations in the estimated direction <b>140</b>. The first processor <b>750</b> is arranged to compute a third set of pixel values from the second set of pixel values. The second processor <b>760</b> is arranged to assign pixel values from the third set of pixel values to the unassigned pixel values.

0033<figref idref="DRAWINGS">FIG. 8</figref> is an embodiment of an image processing device <b>800</b> including a device for hole filling, a receiver <b>810</b> and a display device <b>830</b>. The receiver <b>810</b> is arranged to receive a signal representing a sequence of images. The device <b>700</b> is arranged to assign pixel values to pixel locations in a region comprising pixel locations of unassigned pixel values in at least one image belonging to the sequences of images. The sequence of images may be received through a cable or terrestrial or satellite transmission system or a digital network such as the Internet. The image processing device <b>800</b> may include additional components e.g. the display device <b>830</b> for displaying the output images. Alternately, the device <b>800</b> may supply images to a display outside the device <b>800</b>. The device <b>800</b> can support one or more of the following types of consumer and professional device by incorporating additional means: a TV, a set top box, a VCR/VCP, a satellite tuner, a DVD player/recorder. Optionally the device <b>800</b> comprises storage means like a hard-disk or means for storage on removable media such as optical disks. The image processing device <b>800</b> might also be a system being utilized by a film studio or a broadcaster or a re-transmitter.

0034The computer program may be embedded in a device such as an integrated circuit or a computing machine as embedded software or kept pre-loaded or loaded from one of the standard storage or memory devices. The computer program can be handled in a standard comprised or detachable storage, e.g. flash memory or hard disk or CD. The computer program may be presented in any one of the known codes such as machine level codes or assembly languages or higher level languages and made to operate on any of the available platforms such as hand-held devices or personal computers or servers.

0035It should be noted that the above-mentioned embodiments illustrate rather than limit the invention and those skilled in the art will be able to design alternate embodiments without departing from the scope of the appended claims. In the claims, any reference signs placed between parentheses shall not be construed as limiting the claim. The word ‘comprising’ does not exclude the presence of elements or steps not listed in a claim. The word ‘a’ or ‘an’ preceding an element does not exclude the presence of a plurality of such elements. The invention can be implemented by means of a suitably programmed computer. In the unit claims enumerating several means, several of these means can be embodied by one and the same item of hardware.