GB2327024A

GB2327024A - Deriving a Polyhedral Approximation of a Range Image

Info

Publication number: GB2327024A
Application number: GB9807622A
Authority: GB
Inventors: Seong-Beom Kim
Original assignee: Daewoo Electronics Co Ltd
Current assignee: WiniaDaewoo Co Ltd
Priority date: 1997-06-30
Filing date: 1998-04-08
Publication date: 1999-01-06
Also published as: GB9807622D0

Abstract

An apparatus for approximating a range image by using a polyhedral approximation technique first estimates depth data of the range image by using a predetermined 2-dimensional plane containing MxN pixels, M and N being positive integers, respectively. Based on the depth data for the range image, the apparatus calculates a weight for each of pixels in a target region within the predetermined 2-dimensional plane to thereby provide depth information containing the depth data and weights for the range image. Then, polyhedral approximation is performed on the range image based on the depth information to thereby provide plane information. A reconstructed range image is generated by using the plane information and a polyhedral approximated range image is produced by smoothing the reconstructed range image.

Description

METHOD AND APPARATUS FOR POLYGONALLY APPROXIMATING A RANGE IMAGE The present invention relates to a computer vision system; and, more particularly, to a method and apparatus capable of approximating a range image based on 3-dimensional depth data thereof.

Recovering useful information from huge arrays of sensed values has been one of major thrust of development in a computer vision system. Direct interpretation of large amount of raw data by a computer is difficult. Therefore it is convenient to segment an image into low-level entities, e.g., groups of pixels with similar properties.

Many segmentation algorithms work with range images, where intensity of pixels is given as a function of the distance or range from a sensor. The image can then be treated as a digitized surface. Polyhedral approximation of digitized surfaces has the advantage of being a simple representation capable of approximating any sampled surface arbitrarily closely.

In general, surface triangulation has been used in some computer vision applications in order to achieve the polyhedral approximation. The surface triangulation usually uses range data obtained by converting depth data, wherein the depth data is obtained by calculating the distance between the sensor and a 3-dimensional object represented by the range image. However, since the range data is represented by 3dimensional coordinates (x, y, z)'s in a 3-dimensional space, it is difficult to take account of the correlation between equal-distanced points on the object and the range data corresponding to the points on the object may be concentrated on limited regions dependent on the shapes of the object.

It is, therefore, a primary object of the present invention to provide a method and apparatus for approximating a range image based on 3-dimensional depth data thereof.

In accordance with one aspect of the present invention, there is provided a method for approximating a range image, which comprises the steps of: (a) estimating depth data of the range image by using a predetermined 2-dimensional plane containing MxN pixels, M and N being positive integers, respectively, to thereby produce depth information; (b) polyhedral-approximating the range image based on the depth information to thereby provide plane information; (c) forming a reconstructed range image by using the plane information; and (d) generating the approximated range image by smoothing the reconstructed range image.

In accordance with a second aspect of the present invention, there is provided an apparatus for approximating a range image, which comprises: a distance estimation unit for detecting depth data of the range image by using a predetermined 2-dimensional plane containing MxN pixels, M and N being positive integers, respectively; a weight calculation unit for computing a weight for each of pixels in a target region within the predetermined 2-dimensional plane by using the depth data to thereby produce depth information containing the depth data and weights for the range image; a polyhedral approximation unit for approximating the range image based on the depth information to thereby provide plane information; and a post processing unit for forming a reconstructed range image by using the plane information and generating a polyhedral-approximated range image by smoothing the reconstructed range image.

The above and other objects and features of the present invention will become apparent from the following description of preferred embodiments given in conjunction with the accompanying drawings, in which: Fig. 1 shows a block diagram of an apparatus for approximating a range image in accordance with the present invention; Fig. 2 represents a detailed block diagram of a polyhedral approximation unit in Fig. 1; Figs. 3A and 3B illustrate a weight calculation process; and Figs. 4A to 4D describe a block division process.

Referring to Fig. 1, there is shown a block diagram of an apparatus in accordance with the present invention. A range image is inputted to a distance estimation unit 100.

The distance estimation unit 100 derives depth data of the range image by using a predetermined 2-dimensional plane containing MxN elements, e.g., pixels, M and N being positive integers, respectively. That is, the depth data of the range image is determined by estimating a perpendicular distance from each of the MxN pixels on the 2-dimensional plane to the range image and it is outputted in a form (x, y, d) for each of the MxN pixels on the 2-dimensional plane, wherein the x and y represent coordinates of each of the MxN pixels on the 2-dimensional plane and the d represents the perpendicular distance corresponding to each of the MxN pixels. The depth data containing the distances for all of the pixels on the 2dimensional plane is transferred to a weight calculation unit 110.

In accordance with an embodiment of the present invention, as shown in Figs. 3A and 3B, once the depth data for the 2-dimensional plane is coupled thereto and a depth data matrix 10 containing the perpendicular distances corresponding to the MxN pixels is formed based on the depth data, the weight calculation unit 110 computes a weight for each of pixels in a target region 20 within the depth data matrix 10 by using depth data for its neighboring pixels.

Referring to Fig. 3B, the weight for each of the pixels in the target region 20 is calculated as follows:

wherein Wij represents a weight of an (ij)th target pixel in the target region 20; dj,j is depth data of the (ij)th target pixel, i and j being positive integers, respectively; and dj+p,j+q depicts depth data of a pixel neighboring to the (ij)th target pixel, p and q being integers ranging from -1 to 1, respectively.

After weights for all of the pixels in the target region 20 are ciphered through the use of EQ. 1, the weight calculation unit 110 provides a polyhedral approximation unit 120 with depth information including the depth data and the calculated weights, wherein, as a result of the above calculation process, the weight and the depth data are obtained for each of the pixels within the target region 20 while the rest pixels in the depth data matrix 10 have only the depth data.

Referring to Fig. 2, there is provided a detailed block diagram of the polyhedral approximation unit 120 in Fig. 1 which includes a division sector 121, a sample point selection sector 122, a plane approximation sector 123, a comparison sector 124, and a switching sector 125. The depth information derived at the weight calculation unit 110 is coupled to the division sector 121 in the polyhedral approximation unit 120.

Once receiving the depth information provided from the weight calculation unit 110, the division sector 121 first stores the depth information therein; separates the depth data matrix 10 with their weights into a preset number of blocks based on the depth information, each block having depth data and weights, i.e., the depth information corresponding to pixels therein; and provides separated depth information on each of the blocks to the sample point selection sector 122.

However, in accordance with an embodiment of the present invention, at the first time the depth information is coupled to the division sector 121, the depth information is directly provided to the sample point selection sector 122 without the division process.

Based on separated depth information on a block supplied from the division sector 121, the sample point selection sector 122 chooses a predetermined number of sample points among the pixels of the block; performs a plane approximation process based on the depth data on the sample points through the use of a well known plane approximation technique; and calculates an approximation error ERR. In the above, the number of the sample points is determined by taking account of a size of the block and a mean of the weights associated with the block. More specifically, the number of the sample points increases in a predetermined rate as the mean of the weights becomes larger while it is predetermined depending on the size of the block.

According to the well known plane approximation technique, the plane approximation process is performed for each of the sample points by using plane approximation equations.

wherein i is a positive index ranging from 1 to K, K being the number of the sample points.

By using the above equations EQ. 2 and EQ.3, the plane approximation sector 123 detects coefficients A, B, C and D of EQ. 2 to make the approximation error ERR defined by EQ.

3 have a minimum value. The detected coefficients A, B, C and D are applied to EQ. 2 in order to compute the approximation error ERR. As a result of the above approximation process, plane information including, e.g., A, B, C and D, which defines the approximated plane, is delivered to the switching sector 125 via a line L10 and the approximation error ERR is fed to the comparison sector 124 through a line L20.

The comparison sector 124 compares the approximation error ERR with a predetermined permitted error Ert wherein the Er becomes a standard determining whether the sample points are sufficiently close to the approximated plane or not. As a result of the comparison process, if the approximated error ERR is greater than the permitted error Ert the sample points cannot be treated to be on the approximated plane. Therefore, the comparison sector 124 issues a comparison signal Cl having a disabled state to the switching sector 125 via a line L30 so as to prevent the plane information provided via the line L10 from the plane approximation sector 123 from being outputted to a next circuit, i.e., a post processing unit 130 through the switching sector 125. At the same time, the comparison sector 124 provides a division control signal C2 to the division sector 121 via a line L40 in order to control the division process thereat. Consequently, in response to the division control signal C2, the division sector 121 subdivides the block that has already been processed at the plane approximation sector 123 into 4 subblocks. On the other hand, if the approximated error ERR is smaller than or equal to the permitted error ErZ the sample points can be referred to be on the approximated plane. Therefore, the comparison sector 124 generates a comparison signal C1 having an enabled state to the switching sector 125 so that the plane information provided via the line L10 from the plane approximation sector 123 is outputted to the post processing unit 130 through the switching sector 125. At this time, the division control signal C2 is disabled and the division sector 121 provides separated depth information of another block to the sample point selection sector 122 in response to the disabled division control signal C2 on the line L40.

Referring to Figs. 4A to 4D, hereinafter, the plane approximation process which is repetitively performed at the plane approximation sector 123 will be briefly explained again.

As aforementioned, the depth data matrix 10 is coupled to the division sector 121 to be stored therein and be provided to the sample point selection 122 at the same time without being divided. Therefore, at the plane approximation sector 123, the depth data matrix 10 is approximated as above and then its plane information and approximation error are outputted. As a result of comparison of the approximation error with the permitted error E" , for example, if the approximation error is greater than the permitted error Erj the depth data matrix 10 is divided into 4 blocks, e.g., B1 to B4, at the division sector 121 as shown in Fig. 4A. Then, separated depth information on the first block B1 is provided to the sample point selection sector 122 and the plane approximation process for the block B1 is performed through the plane approximation sector 123 and the comparison sector 124. At the comparison sector 124, if the approximation error for the block B1 is still greater than the permitted error Ert the block B1 is divided into 4 subblocks B11 to B14 again as described in Fig. 4B. In the same manner, if the subblock B14 is selected as a subblock to be sub-divided, the subblock B14 is separated into 4 subblocks B141 to B144 as shown in Fig.

4C and the approximation process is repetitively performed.

Once the polyhedral approximation process is performed on the block B1 and, thereafter, the plane information for the block B1 including at least one subblock is provided to the post processing unit 130, the blocks B2 to B4 are sequentially approximated through the above polyhedral approximation process until the depth data matrix 10 is totally processed and plane information therefor is supplied to the post processing unit 130. In other words, until the approximation error ERR for a block or a subblock is satisfied or a subblock having a minimum size is processed by the above polyhedral approximation, the polyhedral approximation process is continued.

Referring back to Fig. 1, the post processing unit 130 improves reliability of the plane information by taking account of the correlation between planes formed based on the plane information. Accordingly, the post processing unit 130 generates a reconstructed range image based on the plane information of the range image provided from the polyhedral approximation unit 120; adjusts the plane information so as to smooth the reconstructed range image which may have a rough structure since there can be substantial differences between adjacent planes of the reconstructed range image; and outputs a polyhedral-approximated range image. By employing the smoothing process, the original range image can be successfully reconstructed.

While the present invention has been described with respect to the particular embodiments, it will be apparent to those skilled in the art that various changes and modifications may be made without departing from the scope of the invention as defined in the following claims.

Claims

Claims:

1. A method for approximating a range image, which comprises the steps of: (a) estimating depth data of the range image by using a predetermined 2-dimensional plane containing MxN pixels, M and N being positive integers, respectively, to thereby produce depth information; (b) polyhedral-approximating the range image based on the depth information to thereby provide plane information; and (c) forming a reconstructed range image by using the plane information and generating a polyhedral-approximated range image by smoothing the reconstructed range image.

2. The method as recited in claim 1, further comprises, between the steps (a) and (b), the steps of: (aa) calculating a weight for each of pixels in a target region within the predetermined 2-dimensional plane by using the depth data to thereby produce the depth information containing the depth data and weights for the range image.

3. The method as recited in claim 1 or 2, wherein the depth data for the range image is determined by estimating a perpendicular distance from each of the MxN pixels on the 2dimensional plane to the range image.

4. The method as recited in claim 3, wherein the step (b) includes the steps of: (bl) dividing the predetermined 2-dimensional plane into a plurality of blocks, each of the blocks having depth information corresponding to pixels therein, and selecting one of the blocks as a given block; (b2) choosing a number of sample points among the pixels of the given block, wherein the number of the sample points is predetermined based on a size of the given block; (b3) performing a plane approximation on the given block based on the depth data of the sample points through the use of a well known plane approximation technique to thereby produce the plane information and an approximation error ERR; (b4) comparing the approximation error ERR with a predetermined permitted error Er; (b5) outputting the plane information in response to a result of the comparison process; (b6) sub-dividing the given block into a multiplicity of subblocks in response to the result of the comparison process and selecting a new given block among the blocks and the subblocks; and (b7) repeating the steps (b2) to (b6) until the polyhedral approximation is performed on the whole range image.

5. The method as recited in claim 4, wherein in order to produce the plane information and the approximation error ERR, the plane approximation is performed by using following equations, Ax + By + Cz + D=0

wherein i is a positive index ranging from 1 to K, K being the number of the sample points and the coefficients A, B, C and D are determined such that the approximation error ERR becomes a minimum value.

6. The method as recited in claim 5, wherein if the approximated error ERR is smaller than or equal to the predetermined permitted error E" the plane approximation for the given block is completed so that its corresponding plane information is outputted and, if otherwise, the given block is sub-divided.

7. The method as recited in claim 2, wherein the weight for each of the pixels in the target region within the predetermined 2-dimensional plane is calculated as:

wherein Wij represents a weight of an (ij)th target pixel in the target region; djj is depth data of the (ij)th target pixel, i and j being positive integers, respectively; and d+p,j+q depicts depth data of a pixel neighboring to the (ij)th target pixel, p and q being integers ranging from -1 to 1, respectively.

8. The method as recited in claim 7, wherein the number of the sample points, predetermined according to a size of the given block, varies depending on a mean of the weights associated with the given block.

9. An apparatus for approximating a range image, which comprises: means for estimating depth data of the range image by using a predetermined 2-dimensional plane containing MxN pixels, M and N being positive integers, respectively; means for calculating a weight for each of pixels in a target region within the predetermined 2-dimensional plane by using the depth data to thereby produce depth information containing the depth data and weights for the range image; means for polyhedral-approximating the range image based on the depth information to thereby provide plane information; and means for forming a reconstructed range image by using the plane information and generating a polyhedral-approximated range image by smoothing the reconstructed range image.

10. The apparatus according to claim 9, wherein the depth data for the range image is determined by estimating a perpendicular distance from each of the MxN pixels on the 2dimensional plane to the range image.

11. The apparatus according to claim 10, wherein the weight for each of the pixels in the target region within the predetermined 2-dimensional plane is calculated as:

wherein Wij represents a weight of an (ij)th target pixel in the target region; dj,j is depth data of the (ij)th target pixel, i and j being positive integers, respectively; and dj+pj+q depicts depth data of a pixel neighboring to the (ij)th target pixel, p and q being integers ranging from -1 to 1, respectively.

12. The apparatus according to claim 11, wherein the polyhedral-approximating means includes: means for dividing the predetermined 2-dimensional plane into a plurality of blocks, each of the blocks having depth information corresponding to pixels therein, and selecting one of the blocks as a given block; means for choosing a number of sample points among the pixels of the given block; means for performing a plane approximation on the given block based on the depth data of the sample points through the use of a well known plane approximation technique to thereby produce the plane information and an approximation error ERR; means for comparing the approximation error ERR with a predetermined permitted error Er to thereby produce a comparison signal or a division control signal; and means for outputting the plane information in response to the comparison signal, wherein, in response to the division control signal, the dividing means sub-divides the given block into a multiplicity of subblocks and provides one of the blocks and the subblocks as a new given block to the sample point choosing means in order to repetitively perform the above polyhedral approximation process until the whole range image is processed.

13. The apparatus according to claim 12, wherein the number of the sample points, predetermined according to a size of the given block, varies depending on a mean of the weights associated with the given block.

14. The apparatus according to claim 13, wherein in order to produce the plane information and the approximation error ERR, the plane approximation is performed by using following equations, Ax + By + Cz + D = 0

15. The apparatus according to claim 14, wherein if the approximated error ERR is smaller than or equal to the permitted error Ef, the comparison signal is generated so that its corresponding plane information is outputted and, if otherwise, the division control signal is produced so that the given block is sub-divided.

16. An apparatus constructed and arranged substantially as herein described with reference to or as shown in Figures 1 to 4D of the accompanying drawings.