Method and system for providing a volumetric representation of a 3-dimensional object

ES 2 444 643 T3

DESCRIPTION

Procedure and system to provide a volumetric representation of a three-dimensional object

[0001] The present invention relates to methods and systems for providing three-dimensional representations and will now be described with reference to this application. However, it will be appreciated that the invention is not limited to this particular application.

[0002] Various methods for providing volumetric representations of three-dimensional objects are known in the art. An example of a method for providing volumetric representations of three-dimensional objects includes providing a shape reconstruction of three-dimensional (3D) objects from multiple points of view. Calculating the visual envelope of silhouettes of objects is a popular technique.

[0003] The method, also called shape-from-silhouette, provides a 3D description of the object. Focusing requires a set of images of the silhouette from calibrated cameras. A silhouette image is a binary (or in some cases, grayscale) image, where each pixel indicates whether this pixel belongs to the object or not. The silhouette information can be determined by any suitable segmentation process. This is advantageously done using chroma-keying (color key) or difference-keying as described in our patent GB-0,220,972.4 and in our earlier applications mentioned therein.

[0004] The 3D shape reconstruction can be formulated as the intersection of generalized cones from the silhouette images. A generalized cone is the union of the visual rays from all the points of the silhouette of a particular image. This intersection gives only an approximation of the shape of the real object and is called the visual envelope. In particular, the concavities cannot be modeled with this procedure.

[0005] Various algorithms for calculating the visual envelope have been published, for example: W. Martin and JK Aggarwal, Volumetric descriptions of objects from multiple views, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 5, no. 2, pp. 150-158, March 1983; M. Potmesil, Generating octree models of 3D objects from their silhouettes in a sequence of images, Computer Vision, Graphics and Image Processing, vol. 40, pp. 1-29, 1987; Richard Szeliski, Rapid octree construction from image sequences, CVGIP: Image Understanding, vol. 58, no. 1, pp. 23-32, July 1993; and Wolfgang Niem, Robust and fast modeling of 3d natural objects from multiple views, in SPIE Proceedings, Image and Video Processing II, San Jose, February 1994, vol. 2182, pp. 388-397. These approaches try to solve the problem in a representation of the volumetric space. The most common of these representations is to subdivide a 3D box of a 3D Euclidean space into a set of discrete-sized voxels. The size of the box is predetermined so that the object can fit inside. In order to save memory these can be represented as octrees or they are encoded throughout the execution.

[0006] For the use of 3D reconstruction, for example in a graphics application, a description of the surface must be generated, usually a polygon mesh. An often used algorithm is the marching cubes algorithm, described in patents. 4,710,876, 4,719,585, 4,885,688 and at http://www.exaflop.org/docs/marchcubes/ind.html, which creates an iso-surface of a volumetric data set, the iso-surface being formed by contiguous triangles that have vertices located at midpoints of the voxel edges. Since the aforementioned shape-from-silhouette procedures compute binary voxels, the 3D surfaces generated from those using the marching cube algorithm are very noisy. This noise is introduced due to the spatial discretization of the volumetric representations. That is, the real data of the real shape of the object is lost during the processing of the algorithm.

[0007] An improvement over the prior art is described in the same applicant's British Patent Publication Number 2 399 703, which discloses combining voxel data with data obtained by projecting sets of lines into two-dimensional representations of a 3 dimensional object. The combined data is then used in the marching cubes algorithm in such a way that the position of the vertices of the generated iso-surface triangles are more precisely positioned on the respective voxel edges. While this improved procedure is useful, it tends to use up the available processing power to a great extent.

[0008] The article by M. Magnor entitled Spacetimecoherent geometry reconstruction from multiple video streams published on September 6, 2004 refers to the modeling of 3D objects from a set of 2D images taken from different points of view. The intersection between the silhouettes and the 3D space, divided into voxels, is performed with sub-voxel precision to obtain a 3D model. In this article, a voxel is assigned a number of uniformly sampled points and these points are projected onto each 2D image and the percentage of sampled points whose projections coincide with each 2D image is determined.

[0009] Another problem with volumetric reconstructions from silhouette images is that of redundant voxels that occur due to approximation errors in the reconstructed 3D volumetric representation when using a small number of cameras. The reconstruction is always larger than the actual object. This error is compounded in the reconstruction of volumetric representations of moving objects.

ES 2 444 643 T3

When an object is moved, the edges formed by two adjacent camera views move relatively over the object, resulting in a reconstruction that is visibly quite annoying for the viewer. It is an object of at least one of the preferred embodiments of the present invention to overcome or ameliorate at least one of the disadvantages of the prior art.

According to one aspect of the invention, there is provided a method for providing a volumetric representation of a three-dimensional object according to claim 1.

[0011] An example not forming part of the invention provides a method for providing a volumetric representation of a three-dimensional object, in which a three-dimensional space is composed of a plurality of voxels, and in which the voxels are classified as foreground or background according to at least one silhouette image of the object, the method comprising subsampling said at least one silhouette image and comparing a projection of at least one voxel with said subsampled image to classify said voxel.

[0012] An example not forming part of the invention provides a method of providing a volumetric representation of a three-dimensional object as the intersection of generalized cones of at least one silhouette image of this object, the method comprising selectively removing volume from the representation as a function of the geometry of the intersections of the generalized cones.

According to an example not forming part of the invention, a method is provided for providing a volumetric representation of a three-dimensional object, in which a three-dimensional space comprises a plurality of voxels, and in which the voxels are classified as foreground or background according to at least one silhouette image of the object, the method comprising representing the object over a period of time as a 4D model that defines a hypersurface. A smoothing operator can then be applied to said 4D hypersurface.

[0014] As will be appreciated by the person skilled in the art, a voxel is generally defined along orthogonal axes, typically of a cube, however, it will be appreciated that for different applications of the invention, the voxels used may be of one or more different shapes, such as a rectangular, tetrahedron, rhomboid, or other three-dimensional polyhedron prism that is capable of forming part of a matrix in which adjacent shapes share adjacent edges. For the purposes of description, unless otherwise defined, the term voxel is therefore not to be limited to any particular form.

[0015] Preferred embodiments of the invention will now be described, by way of example only and where like reference numerals denote like parts, with reference to the accompanying drawings in which:

Figure 1 is a perspective view of a person posing for a prior art chroma-key imaging process used with embodiments of the present invention;

Figure 2 is the chroma-key image that results from the processes involved in figure 1;

Figure 3 is a perspective view showing a typical study arrangement;

Figure 4 is an array of volumetric imaging elements (voxels);

Figures 5 and 6 illustrate steps of preferred embodiments of the present invention, where a single voxel divided into octants, illustrating the footprint of an octant projecting in a 2D representation;

Figure 7 is an image resolution pyramid in accordance with an alternative embodiment of the present invention;

Figures 8 and 9 illustrate an approach procedure in accordance with another alternative embodiment of the present invention; Y

Figures 10 and 11 illustrate a procedure for approximating a polyline to a 3D volumetric representation.

[0016] A preferred embodiment of the present invention comprises a method for providing a volumetric representation of a three-dimensional object. Referring to Figures 1 and 2, the object is in the shape of a person 10. Of course, the object is not limited to people, but can be any object within reason. The procedure comprises several stages. The first stage includes obtaining two binary two-dimensional (2D) representations or images of the silhouette 12, of the object 10, using a camera and conventional chroma key techniques. In one embodiment, this is achieved using a multi-camera studio system with known camera parameters, as described in our application GB 0220972.4. For example, Figure 2 illustrates a chromakey representation of a view of object 10 in front of a retro-reflective background 14 that is illustrated in Figure 1. In the embodiment of the invention described below, two 2D representations of the object are obtained from chroma-keying, which represent different side views of the object. However, in alternative embodiments, the procedure can be based on more than two images, such as ten or more. When alternative conditioners can be used, it may be possible to use a single image.

ES 2 444 643 T3

[0017] A technique such as shape from silhouette, as described in W. Niem, 'Robust and fast modeling of 3D natural objects from multiple views', SPIE Proceedings, Image and Video Processing II, Vol 2182, pp 88 -397, San José, February 1994 is particularly suitable for 3D reconstruction in this application. Alternative techniques can also be used. For example, for applications such as 3D photography with static objects, fewer cameras (or just one camera) can be used by taking multiple pictures of the object either by fixing the camera and rotating the object on a turntable or by moving the camera. around the object. In the latter case, you need a monitoring system that gives the camera parameters. A suitable system for this is described in GB-A-2325807.

With particular reference to Figure 3, an example of a multi-camera study system with known parameters is illustrated. Details of these components are described in GB 2325807, GB 2321814 and UK patent application number 0.206.214.9, the descriptions of which are incorporated herein by reference.

[0019] The system depicted in Figure 3 uses multiple cameras and chroma-key techniques to calculate a 3D model of an actor 10. Studio cameras 16 are arranged to take images of the scene, including: at least one modified fixed camera 16a with an illuminator comprising a ring of blue LEDs to illuminate the object from the direction of the camera so that the background retro-reflective 14 reflects light back towards the camera, and a similarly modified camera 16b with a tracking system.

[0020] One embodiment of the invention employs the aforementioned marching cubes algorithm to determine a volumetric representation of the object. To use the marching cubes algorithm, an octree corresponding to the object is required. An octree is a hierarchical data structure that divides a volume, such as a voxel, into eight octants, and so on. The resolution of the determined volumetric representation depends on the resolution of the octree data.

[0021] The marching cubes algorithm uses an array of voxels in a defined space that is predetermined to fit the object inside. An example of a voxel matrix 18 is illustrated in Figure 4, where eight vertices 20 define each voxel 22. In turn, each adjacent pair of vertices 20 defines a voxel edge 24 between them. It is then determined in which of the voxels 22 the object 10 is present, and through which voxels an edge of the object 10 passes. For the purpose of description, these latter voxels are called intersecting voxels.

[0022] A list of the intersected voxels and their intersected edges is then compiled (in terms of the voxel vertices 20 defining the respective voxel edge 24). This data is executed by the rest of the marching cubes algorithm, which first assumes that the object's edge passes through a midpoint 26 of the voxel's edge 24, and then searches a lookup table of fifteen variations of the triangles that have their vertices at the midpoints of the edge of the voxel 26 between the adjacent voxel vertices and assign one or two suitable triangles to the given intersected voxel. Although the object's edge can have intersecting edges at any point along the edges, the standard marching cubes algorithm assigns this voxel a triangle (not shown) with vertices at the edge midpoints 26.

[0023] A known iterative procedure for obtaining higher resolution octree data is described below. First, a set of voxels is projected onto the silhouette images. Each non-intersecting voxel is ignored relative to the background space, and set to false. Each intersected voxel is considered part of the foreground, set to true, and subdivided into eight subvoxels, or octants. Each non-intersecting octant is then set to false, while each intersecting octant is set to true and then subdivided in turn and so on up to a predetermined number of iterations, or maximum level Lmax Lmax which will generally be predetermined to obtain resolution of the desired resulting image, or at least limited by the amount of acquired data that can be properly processed. In this conventional octree-based reconstruction, the value of a voxel can be true or false, giving the known quantization error in the description of the surface from the marching cubes algorithm.

In one embodiment of the present invention, once Lmax has been reached, the remaining octants are subdivided into eight equal parts up to a predetermined number Lss of levels, and the sum of the number of true subdivided voxel portions are assigned to the remaining octants. This is represented by the following equation:

^r or, "Zj

Jl k ~ Q

Voi is then normalized in the range 0 to 1, for use with the marching cubes algorithm:

ES 2 444 643 T3 ^, = ^ / (8^Χ·)

[0025] This fractional part is therefore more representative of the quantity of the octant in Lmax through which the image passes, than a true or false value (1 or 0, respectively). This additional information can be used in the marching cubes algorithm to produce a more accurate estimate of the surface of an object.

[0026] There is a limit to the number of useful levels, which can be used in an octree, since there is no more information available if the footprint of the subdivided portion projected on the input image is less than one pixel in this image. Therefore, the algorithm of the invention can be implemented adaptively. In one embodiment, if the useful limit described above is reached before all the Lss levels have been divided, the algorithm does not attempt to further divide this octet. In practice, to reduce the amount of computation required, Lss is normally equal to 1.

[0027] A marching cubes algorithm can then be used to calculate the volumetric or iso-surface representation of the object. Since the structure is represented by a continuous range of values ​​(as opposed to a binary representation) a marching cubes algorithm can be used where the surface is defined by a threshold Vthreshold. The threshold Vthreshold is usually half the number of slices divided, that is, V'threshold = 0.5. This modified procedure provides a more accurate representation of the object than the standard marching cubes procedure.

An embodiment example will now be described with reference to Figures 4 to 6. Figure 4 illustrates a cube-shaped array 18 of voxels 22. In Fig. 5, a voxel 22a is illustrated through which an image surface 12 'passes. Therefore, voxel 22a is subdivided into octants 28, of which one 28a is projected next in image 12 '. The shape, or footprint, of octant 28a as projected in image 12 'is indicated as 30. If Lmax has not been reached at this point, as the image passes through octant 28a, octant 28a is in turn subdivided as explained above. Of course, at the same time, it would be considered in which of the octants a second silhouette image (not shown) passes. Only those octants for which all images pass are considered true.

[0029] An embodiment example will now be described with reference to Figures 4 to 6. Figure 4 illustrates a cube-shaped array 18 of voxels 22. In Fig. 5, a voxel 22a is illustrated through which an image surface 12 'passes. Therefore, voxel 22a is subdivided into octants 28, of which one 28a is projected next in image 12 '. The shape, or footprint, of octant 28a as projected in image 12 'is indicated as 30. If Lmax has not been reached at this point, as the image passes through octant 28a, octant 28a is in turn subdivided as explained above. Of course, at the same time, it would be considered in which of the octants a second silhouette image (not shown) passes. Only those octants for which all images pass are considered to be true.

[0030] The present embodiment allows a more accurate volumetric representation of an object, without the need to increase Lmax. Using the value of Voi in the marching cubes algorithm instead of increasing Lmax requires relatively less processing time.

[0031] In an alternative embodiment of the present invention, the footprints of each true or octant voxel projected on the silhouette images are considered once Lmax has been reached. In the embodiment explained above, the true octants at the Lmax level are subdivided into Lss levels, and a fractional value is calculated for the true octants. In this embodiment, a fractional value for a true octant is calculated by counting the number of pixels in the image that are delimited by a footprint of this octant as a fraction of the total possible number of pixels delimited by the footprint. For example, in Figure 5, the shaded portion 32 represents the number of pixels delimited by the footprint 30 that corresponds to a voxel 28a. The decimal fraction of the number of pixels in part 32 divided by the total possible number of pixels delimited by footprint 30 is calculated and then assigned to that voxel. It is not necessary to calculate the exact footprint, and an approximation, such as a bounding box, could be used instead to reduce computational complexity at the expense of precision. This data is then used in the marching cubes algorithm as described above with reference to the previous embodiment.

[0032] An example not forming part of the invention also employs an algorithm to provide a volumetric representation of an object, the algorithm preferably being the marching cubes algorithm. In this embodiment, prior to projection of voxels into the images, or vice versa, the image resolution is reduced by a predetermined amount, for example by subsampling. An example of this embodiment is illustrated in Figure 7. For this example, the reduction factor is 16 and is achieved in two stages. This is accomplished by first subsampling image 12a by a factor of two in both the x and y directions. Therefore, each pixel in the reduced image 12a 'contains a sum of the pixels of the associated 2x2 region of the original image 12a. The reduced image 12a 'is then further subsampled by a factor of two in both the x and y directions. Each pixel of the even smaller image 12a contains the sum of the pixels of the

ES 2 444 643 T3 associated 2x2 region of reduced image 12a Techniques for performing these subsamples are well known, and any appropriate technique may be employed.

The information describing the three images 12a, 12a 'and 12a and their relationship to each other is kept in a lookup table of a pyramid of the images. The voxels and octants can then be projected onto the image of a selected resolution in order to verify the true octants. When evaluating a fingerprint for the presence of pixels in the image, it is desirable to use an image with a lower resolution as this requires access to fewer pixels. Suitably, for an octant of a certain size, or at a certain level an image having a corresponding level is selected, that is, thick voxels can be projected in lower resolution images and without a substantial reduction in precision. Higher resolution images can be accessed as an algorithm passes through subsequent octet levels.

As will be apparent to one of ordinary skill in the art, the time required to collect true pixel data can be decreased using this procedure.

[0034] In alternative arrangements of this embodiment, the pyramid may include additional levels of images still smaller, or levels where the images are reduced by different amounts, such as 0.5 or 3, for example. On the other hand, if the desired resolution of the reconstructed volumetric representation is less than that which would be obtained using pixels from the original image, the algorithm could be adjusted to access reduced image data from within the pyramid.

[0035] An example that is not part of the invention considers the problem of redundant voxels, which can occur due to approximation errors in the reconstructed 3D volumetric representation. These errors are typically larger when using a small number of cameras. For example, the hatched areas 34 illustrated in Figure 8 indicate the approximation error of an object reconstructed from just two cameras 36 and 38. A theoretically exact reconstruction of the object is indicated at 40. However, in combination with hatched areas 34, the marching cubes algorithm returns an approximation limited by lines 42 to 45. These lines represent surfaces in the 3D model and will be referenced to cut lines or cut surfaces, as appropriate.

As mentioned above in connection with the prior art, this error is compounded when reconstructing volumetric representations of moving objects, as indicated by dotted lines 46 in Figure 8. Although it is not possible to reconstruct the shape With shape-from-silhouette techniques, this embodiment employs an algorithm based on the model that it is possible to remove voxels in hatched areas 34 on a heuristic basis.

[0037] In this aspect of the invention, voxels that are considered redundant are removed from a reconstructed object, based on a number of parameters related to cutting lines or surfaces. Referring to Figure 9, voxels are suitably removed preferably at intersections of cut lines 48, 50, 52 and 54, and adjacent to cut lines.

[0038] A first parameter is the length of the cutting line. The longer the cut line, the greater the volume that is removed (or the number of voxels that are removed). A second related parameter is the distance of a voxel from the intersection of the cut line or cut surfaces. The regions that are closest to the intersections are preferably eliminated. A third parameter is the angle of intersection of two cut surfaces. Increased volume is eliminated at intersections that have sharper angles.

[0039] Therefore, the number of voxels removed at or adjacent to intersection points will tend to increase proportionally with increasing edge length. The number of voxels removed at or adjacent to intersection points will tend to increase proportionally with the decreasing angle between adjacent edges, and, in the region adjacent to the intersection point, more voxels will tend to remove closer to the edge than away from the edge. . These considerations reflect the assumption in this model that more natural objects have more rounded edges than square ones.

[0040] Some embodiments of the invention use combinations of functions of said parameters to define algorithms for the elimination of voxels. In addition to the voxel data, other data relating to the cutting surfaces is desirably stored. This information can include which cameras are associated with which cut surfaces.

[0041] In the example illustrated in figure 9, 56 indicates the approximate reconstruction of the object. As illustrated, the intersection angle 52 is less than the intersection angle 48, and the edges 43 and 44 are longer than the bounding portions of the edges 42 and 45. Therefore, more voxels were set as true at intersection or adjacent to this 52 compared to intersection 48, which is indicated by the fact that the shaded area (removed) 34 'is larger than the shaded area (removed) 34 Therefore, the resulting reconstruction 56 of the object is more accurate than the reconstruction obtained by known procedures, and delimited by lines 42 to 45.

ES 2 444 643 T3

[0042] A further example is illustrated in Figures 10 and 11. Referring to Figure 10, part of a reconstructed object surface is shown comprising cutting surfaces 702, 704, 706 and 708. These cutting surfaces will form an angle to each other, and define surface edges, or intersections, for example edge 710. The distance from each element on one cut surface to the closest edge with another cut surface is calculated. Therefore, a function of distance is created across the surface, and this function of distance will present local maxima or inflection points, as in 712 and 714. Referring now to Figure 11, a view is shown in 2D of a chain of cut surfaces. The local maxima or discontinuities of the distance function described above are indicated at points 802, 804 and 806. A spline function 810 is created at these points, and voxels outside the spline function are removed.

In addition, texture maps can be applied to the results of the above-described embodiments of the present invention to make a more realistic representation of an object.

[0044] An example that does not form part of the invention relates to the use of temporal information to improve the reconstruction of shapes. It has been recognized that in many applications there are properties of the 3D object that do not vary substantially with time. In particular, the volume of most objects remains approximately constant. Some embodiments of this aspect of the invention make use of these properties by producing a reconstruction over a period of time, which reconstruction can be limited or optimized to be temporally coherent, rather than independently computing a reconstruction at every instant. of time. In this way, the surface of the object is taken into account over time, that is, in 4D space. A surface in 4D is a hyper-surface.

[0045] The reconstruction problem can be formulated as an optimization of the hyper surface. In M. Magnor and B. Goldluecke, Spacetime-coherent Geometry Reconstruction from Multiple Video Streams, in Proc. 3D Data Processing, Visualization, and Transmission (3DPVTO4), Thessaloniki, Greece describes an approach that calculates a photo-consistent hyper surface using a level set evolution.

[0046] In some embodiments of the present invention a smoothing operator is applied to this hyper-surface, which can be implemented more efficiently than a level set evolution. Smoothing is capable of removing artifacts and in some cases redundant voxels. The smoothing operator can take into account the fact that the object does not vary (much) in volume.

[0047] It is desirable to use a tree 16 to store the data. A 16-tree is defined in 4D and is the generalization of an octree, which is defined in 3D. The amount of memory required for this representation is proportional to the surface and movement of the object.

[0048] Many of the previously described embodiments employ the marching cubes algorithm. As will be appreciated by those skilled in the art, other algorithms, or methods to obtain the approximate volumetric representation of the object may be used in alternative embodiments. For example, a marching triangles procedure (Marching Triangles: Range Image Fusion for Complex Object Modeling Hilton, 1., Stoddart, AJ, llingworth, J. and Windeatt, T. IEEE 1996 International Conference on Image Processing '.)

Although the present invention has been described in its preferred embodiments, it is to be understood that the words that have been used are words of description rather than limitation and that changes can be made to the invention without departing from its scope as stated. defined by the appended claims.

[0050] Each feature described in this description (term including claims) and / or shown in the drawings may be incorporated into the invention independently of other features described and / or illustrated.

[0051] The text of the jointly submitted abstract is repeated here as part of the description.

The invention provides a method for providing a volumetric representation of a three-dimensional object. First, at least two two-dimensional (2D) representations of the object are obtained, preferably by a chroma key process. A set of voxels is then projected onto the 2D representations and it is determined which of the voxels or parts of them the 2D representations intersect. For each voxel or portions thereof that the 2D representations intersect, data is determined representing a proportion, or fraction, of each voxel or portion thereof that intersects each 2D representation. This data is applied to a marching cubes algorithm to provide the volumetric representation. Several examples are given to determine the proportion, or fraction, of each voxel or portion thereof that intersects each 2D representation. The examples are based on either volumetric fractions, or pixel fractions.