CN1466737A - Image conversion and coding technology - Google Patents

Abstract

A method of creating a depth map comprising the steps of: assigning a depth to at least one pixel or portion of an image; determining the relative position and image properties of the at least one pixel or portion of the image; using the depth, image properties, and respective relative positions to determine An algorithm to determine depth characteristics as a function of relative position and image characteristics; using said algorithm to calculate depth characteristics for each pixel or portion of the image, wherein the depth characteristics form a depth map of the image. In the second stage of processing, the depth map forms key frames, which are used to generate a depth map of non-key frames using relative positions, image characteristics, and distances to key frames.

Description

Image conversion and coding technology

field of invention

The present invention is an improved technique for obtaining a depth map from one or more 2D images.

Background of the invention

A certain number of image processing tasks require that the depth of objects within an image be known. Such tasks include the application of special effects to films and video sequences and the conversion of 2D images to stereoscopic 3D. Determining the depth of a target is known as the process of creating a depth map. In a depth map, each object is colored in shades of gray, whereby the depth of the object from a fixed point is indicated by the shade. Typically, distant objects will be shaded darker, while nearby objects will be shaded lighter. The standard transformations for creating depth maps have not been adopted, and inverted coloring can be used or different colors can be used to represent different depths. For ease of explanation in this article, distant targets are colored darker than closer targets, and the coloring is usually a gray scale.

Traditionally, manual methods have been used to create depth maps from existing 2D images. Understandably, an image is just a series of pixels to a computer, although the operator is able to discern the target and its associated depth.

The creation of a depth map involves a system by which each target image to be converted is manually delineated and the depths assigned to the targets. This process is understandably slow, time consuming and expensive. The delineation step is usually accomplished using a software program in conjunction with a mouse. An example of a software program that can be used to perform this task is Adobe "After Effects". Operators using After Effects typically sketch around the outline of each target that needs to be assigned depth, and then fill or "color" the target with a shade of gray that determines the depth or distance from the viewer. This process will then be repeated for each object in the image. Furthermore, where several images are involved, such as in a movie, these steps must also be performed for each image or frame of the movie.

In traditional systems, the outline of an image is usually described in the form of a curve (such as a Bezier curve). The use of such a curve enables the operator to change the shape of the profile so that the profile of the target can be accurately aligned with the target.

If a sequence of images needs to be drawn for - say - the depth of a film or video, the process needs to be repeated for each frame in succession.

A target may continuously vary in size, position and/or depth. In this case, the operator needs to manually track the target in each frame and process each frame by correcting the curve and updating the target depth by changing shades of gray as needed. Understandably, this is a slow, tedious, time-consuming and expensive process.

Attempts have been made in the past to improve this process. The prior art describes techniques aimed at automatically tracking the contours of objects as they move frame by frame. An example of this technique is the application of Active Contours (References: Active Contours - Andrew Blake and Michael Isard - ISBN 3-540-76217-5). The main limitation of this approach is the need to provide the software using the technique with the expected motion of the tracked target. This is severely limited when the expected motion is unknown and complexly deformed, or when multiple targets with different motion characteristics need to be tracked simultaneously.

Point-based tracking methods have also been used to determine the motion of contour lines. These are prevalent in editing environments such as Commotion and After Effects. However, their application is very limited, since it is usually impossible to determine a suitable tracking point whose motion reflects the motion of the whole object. Point tracking is sometimes acceptable when the object is doing simple translations, but it cannot handle shape deformations, occlusions, or a variety of other common problems.

An Israeli company, AutoMedia, has produced a software product called AutoMasker. It enables the operator to outline a target and track it frame by frame. This product depends on tracking of the target color, so it will not work when similar colors cross together. The product may also have problems tracking objects that vary in size across successive frames when, for example, an object approaches the viewer or moves forward on the screen.

None of these methods satisfactorily allocate or track depth maps, so manual systems are still used for depth map creation.

There are also other techniques described in the prior art which rely on motion reconstruction of the camera originally used to record the 2D sequence. The limitations of these techniques are the need for camera motion in the original image sequence and well-defined features in each frame that can be used as tracking points.

purpose of invention

Today, operators must manually create depth maps for each image frame to obtain acceptable results. It is an object of the present invention to reduce the number of frames for which depth needs to be manually created, thereby reducing the time required for the operator to create the depth map.

There is still a set of frames where the depth map needs to be manually created. Another object of the invention is to assist the manual process of depth map creation for these frames.

Contents of the invention

Considering the above purpose, the present invention provides a method for creating a depth map, which includes the following steps:

assigning a depth to at least one pixel or portion of the image;

determining the relative position and image characteristics of at least each pixel or portion of the image;

using said depth, image properties and respective relative positions to determine the configuration of the first algorithm to determine depth properties as a function of relative position and image properties;

using said first algorithm to calculate a depth characteristic for each pixel or portion of said image;

Wherein, the depth characteristics form a depth map of the image.

Another aspect of the present invention provides a method for creating a depth map, which includes the following steps:

assigning depth to at least one pixel or a portion of an image;

determining x,y coordinates and image properties for at least each of said pixels or portions of said image;

using said depth, image properties and respective x, y coordinates to determine a first algorithm to determine depth properties as a function of x, y coordinates and image properties;

using said first algorithm to calculate a depth characteristic for each pixel or portion of said image;

Wherein, the depth characteristics form a depth map of the image.

Another aspect of the invention provides a method of creating a series of depth maps for an image sequence, comprising the steps of:

receiving a depth map of at least one frame of the sequence of images;

using said depth map to determine the configuration of an algorithm to determine depth characteristics as a function of relative position and image characteristics;

The algorithm is used to create a depth map for each frame in the sequence of images.

Still another aspect of the present invention provides a method for creating a series of depth maps of an image sequence, which includes the following steps:

selecting at least one key frame from the sequence of images;

For each of the at least one keyframe, assigning a depth to at least one pixel or a portion of each frame;

determining the relative position (e.g., x, y coordinates) and image characteristics of at least one pixel or portion of each of said frames;

determining a configuration of an algorithm for each of said at least one frame using the depth, image characteristics and relative position of each said at least one frame to determine a depth characteristic as a function of the relative position and depth characteristic;

computing a depth characteristic for each pixel or portion of each of said at least one frame using each configuration of said algorithm;

Wherein, the depth characteristics form a depth map of each of the at least one frame,

Use each depth map to determine the second configuration of the second algorithm, thereby determining each frame as a relative position and

using each depth map to determine a second configuration of the second algorithm to determine depth characteristics for each frame as a function of relative position and image characteristics;

Individual depth maps for each frame of the sequence of images are created using the second algorithm.

It will be appreciated that a system involving algorithms may actually create several different functions to create a depth map as a result of relative position and image properties. In a preferred system, the relative position will be a measure of x,y coordinates.

A system embodying the present invention may optionally predetermine which frames in the sequence are considered key frames, such as every fifth frame. The algorithm can also ideally consider the time input to the algorithm to further refine the processing.

Brief description of the invention

The present invention aims to improve the process of generating a depth map of a correlated 2D image. The preferred embodiment includes two stages of generating keyframe depth maps and generating residual maps.

The first stage gets a small amount of data from the user. This data represents the basic structure of the scene. The 2D image and its associated data yield an algorithm capable of obtaining the relationship between the depth z assigned by the user to different image pixels, their x and y positions, and image properties. The image properties include, but are not limited to, the RGB values of each pixel. In general, the algorithm solves the equation z=f(x, y, R, G, B) that the user has defined for each pixel in the frame.

The algorithm then applies this obtained relationship to other pixels in the image to produce a depth map. Users can refine their data to improve the accuracy of the depth map if desired. It should be noted that the initial depth data does not have to be specified by the user - it could be determined by some other processing including, but not limited to, depth predictions from motion algorithms using automatic structures or from stereo images.

The second stage requires setting a 2D image and associated depth map at selected keyframes. Depth maps at these keyframes can be generated as previously disclosed by applicant, or automatically using depth capture techniques including laser rangefinders, i.e. LIDAR (Light Direction and Range) instruments and depth of field technology, but not only limited to this.

From each keyframe's 2D image and the associated depth map an algorithm is able to obtain the relationship between the depth z assigned to each pixel in other frames, its x and y position and image properties. The image properties include, but are not limited to, the RGB values of each pixel. In general, the algorithm solves the equation z=f(x,y,R,G,B) for each pixel in the keyframe.

The algorithm is then presented with each successive frame between adjacent keyframes, and the algorithm is used to calculate the value of z for each pixel.

Description of drawings

Figure 1 shows an embodiment of the Phase 1 training process.

Figure 2 illustrates one embodiment of a Phase 1 conversion process.

Figure 3 illustrates one embodiment of a Phase 2 training process.

Figure 4 illustrates one embodiment of a Phase 2 conversion process.

Figure 5 depicts how the learning process can partition the feature space.

FIG. 6 shows an alternative process for stage 2 generation of a depth map.

Figure 7 shows an alternative method of determining individual pixel depths at stage 2.

Fig. 8 shows the process of searching for candidate training samples.

Figure 9 shows the process of computing depth from several candidate training samples.

Detailed description of the invention

The present invention provides an improved technique for deriving a depth map from one or more 2D images. The invention preferably comprises two stages, each theoretically comprising an automatic learning process.

stage 1

The first stage operates on a single image. This image is presented to the user, who uses a simple graphical interface to determine the approximate depth of different areas in the image. The graphical interface provides tools to help the user assign depth to pixels, including but not limited to pen and paint brush tools, area fill tools, and tools to assign depth based on pixel color. The result of this process is to determine depth for a subset of pixels in the image.

This process is illustrated in Figure 1, where a 2D image 1 can be presented to the user. The user can then assign depths to different pixels in image 2. In the example of FIG. 1, pixels marked with an "X" are pixels whose depth has not been specified by the user. The system then correlates the 2D image 1 with depth data 2 provided by the user and uses a training algorithm 3 to assist in the creation of a mapping function 4 that is able to solve for each pixel in the image as a function of depth.

The information provided by the user determines the training data used together with the learning process which will be described later to relate depth to each pixel in the single image. The process can be interactive in that the user can only determine the approximate depth of some areas. Based on the results of the region learning process, the user can provide further depth predictions for regions where the learning process is poorly done. This interaction between the user and the learning process can be repeated several times. In fact, the user can guide the learning process at this stage. It should be noted that the original depth does not have to be specified by the user - it could be determined by some other process as described above.

Create mapping function

Once the system is provided with an image and some pixel depth, the system then analyzes the pixel with the determined depth, thereby creating a mapping function. The mapping function may be a procedure or a function that takes as input any measurement of a pixel or group of pixels from an image and provides as output a depth value for the pixel or group of pixels.

Individual pixel measurements may include red, green, and blue values, or other measurements such as luminance, chroma, contrast, and spatial measurements such as horizontal and vertical fixed in the image. Additionally, the mapping function can operate on higher level image features such as larger groups of pixels, or measurements such as mean and variation across groups of pixels, or at edges, corners, etc. (i.e., feature detection device response). A larger group of pixels may represent, for example, a segment in an image, which is a connected group of pixels forming a homogeneous region.

Just for descriptive purposes, a pixel can be represented in the form of x, y, R, G, B, z, where x and y represent the relative position as the pixel's x and y coordinates, and R, G, B represent the red color of the pixel , green and blue values, and z represents the depth of the pixel. The value of z is determined only where the user has specified a value.

The mapping function is obtained by capturing the relationship between image data and depth data of pixels specified by the user. The mapping function can take the form of any ordinary processing unit that receives and processes input data and provides output. Preferably, the processing unit is subjected to a learning process, wherein its properties are determined by examining user data and associated image data.

Those working in the field of artificial intelligence or machine learning will understand that the learning process of this relationship between input data and desired output can take many forms. It is to be noted that these people generally do not work in the field of stereoscopic systems or the conversion of 2D images to 3D. In machine learning, such mapping functions are well known and include, but are not limited to, neural networks, decision trees, decision graphs, model trees, and nearest neighbor classifiers. A preferred embodiment of the learning algorithm seeks to design a mapping function that minimizes the error of some mapping measurement and generalizes satisfactorily to values outside the original data set.

The learning algorithm attempts to determine both the relationship between 2D image information and overall depth over the entire image, and its relationship to depth over local smaller spatial regions.

This relationship can then be applied to complete a depth map of the entire sequence.

This relationship is shown in FIG. 2 , where data is input from a 2D image 1 to the created mapping function 4 , thereby creating a depth map 5 of the 2D image 1 .

Examples of successful learning algorithms are the backpropagation algorithm for learning neural networks, the C4.5 algorithm for learning decision trees, locally weighted linear regression, and the K-means algorithm for learning stick-beam classifiers.

For descriptive purposes only, the learning algorithm can be considered to compute the following relationship for each pixel in a frame of a 2D image sequence

z _n =k _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n where

n is the nth pixel in the keyframe image

z _n is the depth value assigned to the pixel at x _n , y _n

k _a to k _e are constants and determined by the algorithm

R _n is the red component value of the pixel at x _n , y _n

G _n is the green component value of the pixel at x _n , y _n

B _n is the blue component value of the pixel at x _n , y _n

This process is shown in FIG. 1 .

Those skilled in the art will appreciate that the above equations are simplified for the convenience of description, and may not work ideally in practice. In a practical application using eg a neural network and given a large number of pixels in an image, the network will learn a large equation with many values of k, multiplications and additions. In addition, the K value will change at different x, y positions in the image to fit local image features.

Apply the mapping function to the 2D image

Next, the present invention will take this mapping function and apply it over the entire frame of the 2D image sequence. For a given pixel, the input to the mapping function is determined in a similar manner as the mapping function is obtained during learning. For example, if the mapping function is obtained by taking measurements of individual pixels as input, the mapping function will require these same measurements as input. With these inputs, the mapping function does what it has learned and outputs a depth measurement. Again, in this example, for a single pixel, this depth measurement could be a simple depth value. In this example, the mapping function is applied over the entire image, thus completing the entire set of depth data for the image. Additionally, if a larger set of pixels is used to train the mapping function, such a larger set of pixels needs to be generated for the image. Higher level measures of these pixel groups, such as mean and variance, are done in the same way as in the learning process. With these now established inputs, the mapping function generates the desired depth measurement for this set of pixels.

This process is shown in Figure 2 and results in a full depth map of the 2D image. If the resulting depth map contains areas of error, the user data will be modified and the process repeated to correct these areas. This mapping function can also be used on other frames to generate depth maps.

Those familiar with the field of machine learning will understand that this training phase may be implicit in the general configuration of the algorithm. The method is called instance-based learning and includes techniques such as locally weighted linear regression, but is not limited to them. In an alternative embodiment, a user may define a set of targets and assign pixels to those targets. In this embodiment, the process of summarizing user data for other pixels of the image may segment the entire image into target groups initially defined by the user. The mapping function definition target or the target itself may be the desired output of this embodiment. In addition, functions can be applied to objects to specify the depths of these objects, thereby constituting the depth map of the image. These functions may take the form of depth ramps and other methods of defining the depth of the target such as defined in prior application PCT/AU00/00700.

In another alternative embodiment, the training algorithm may attempt to introduce a random component to user information. Utilizing any learning algorithm can help overcome the problem of overtraining. Overtraining refers to the situation where the learning algorithm only memorizes the training information. This is like a child who only learns to write the multiplication table without any understanding of multiplication itself. This problem is well known in the field of machine learning, and one way to alleviate it is to introduce random noise to the training data. A good learning algorithm will be applied to discriminate between noise and quality information of the training data. In doing so, learning the nature of the data rather than just memorizing it is encouraged. An embodiment of the method refers to the previous example, where the training algorithm learns the following function:

z _n =k _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n

When z, x, y, R, G, and B are input to the training algorithm, a small noise component may be added to these values. This noise component can be a small positive or negative random number. In a preferred embodiment, no noise is added to the z component.

learning process

In a preferred embodiment, the inputs to the learning process are:

1. A number of training samples that have certain properties including depth.

2. A number of "classification" samples that have properties that match the training samples and whose depth is determined by the learning process.

The characteristics of each pixel included in the training sample include the pixel's position (x, y), color (R, G, B) and depth (z). The purpose of this learning process is to compute the depth (z) of each classified pixel whose properties include position (x, y) and color (R, G, B).

For each classified sample, the first stage of the learning algorithm consists of identifying a group of training samples that share image properties that are "similar" to the classified pixel in question.

Search for candidate training samples

In order to identify training samples with characteristics similar to those of the current classifier, we imagine an n-dimensional feature space of generated samples. In the preferred embodiment, this is a 5-dimensional space, with each dimension representing an image property: x, y, R, G, and B. The axes of this space are normalized to account for differences in the extent of each dimension. We can therefore use relative percentages to indicate differences between samples. For example, the R component of a given sample may differ by 10% (relative to the absolute range of the R component) relative to a second sample.

The distance between two samples in this space is a measure of their similarity. In order to detect training samples similar to the current classification sample, a search radius is defined. Any training sample whose distance to the classified sample is smaller than the search radius is considered similar to the classified sample and used for depth calculation. Use a simple Euclidean scale to measure distances in an n-dimensional search space. In data that does not occupy a large portion of the n-dimensional feature space, the Mahalanobis distance scale is used to provide better results. Alternative methods of extending the data range such as histogram equalization or principle analysis of RGB, YUV or HSV components offer similar advantages.

The search radius is a critical parameter in accurate estimation of depth and is set relative to data characteristics. In data exhibiting high spatial or high temporal autocorrelation, the value of this radius is set to be smaller than that of images with low spatial or low temporal autocorrelation.

The search radius can be different for each dimension of the feature space. For example, the search radius in the x-axis may be different from the search radius in the axis representing red intensity. Additionally, the learning process can apply these parameters to data within some user-defined bounds. For example, if no suitable training samples are identified among a 5% spatial radius and a 10% colored radius, the spatial radius will be increased to 10%.

Fig. 8 shows a typical example of candidate search processing. The figure depicts a 2-dimensional search space to describe the change in the spatial x-coordinate of the plotted sample versus the change in red intensity. In this space are several training samples 20 . There are no training samples within the distance of the first radius 21 of the target pixels 11 . Therefore, the learning process extends its search to the second search radius 22 of the target pixel 11 and identifies 3 candidate training samples.

Alternative search strategies can be used to identify suitable training candidates. With this strategy, training data can be stored in structures such as hash trees, k-d trees, or n-dimensional Voronoi graphs. Although such strategies increase the speed at which candidate training samples are identified, they do not affect the properties of the invention.

Similarly, a search strategy that exploits the proximity of later classified samples in feature space by caching training samples can improve the speed of identifying candidate training samples, but does not add significantly to the present invention.

distance weighted learning

In order to compute the depth for any given classified sample, we need one or more training samples that are considered to be similar to the classified samples as described above. We refer to these training samples as "candidate" training samples.

We compute the depth of the classified samples as a weighted average of the depths of the candidate training samples. The weight of any candidate training sample is relative to the distance from the classified sample in n-dimensional space. As described above, this distance is normalized and the data can be biased using the Mahalanobis scale or principal component type analysis.

Fig. 9 shows a simplified example of the depth calculation process. As shown in FIG. 8, FIG. 9 depicts a 2-dimensional search space for plotting a change in the spatial x-coordinate of the mapped sample versus a change in red intensity. These candidate training samples 19 are shown at different distances from the target pixel 11 (labeled w1, w2 and w3). This depth can be calculated as a weighted average of candidate training samples using the following formula:

Among them, D1 is the depth of the training sample at a distance w1 from the target pixel 11, D2 is the depth of the training sample at a distance w2 from the target pixel, and D3 is the depth of the training sample at a distance w3 from the target pixel 11.

In a preferred embodiment, the weights are inversely proportional to the square of the distance in n-dimensional space.

Alternative embodiment

In an alternative embodiment, the learning process analyzes the entire set of available training data and deduces rules that determine the relationship of image properties to sample depth.

In this process, the n-dimensional feature space is segmented or partitioned into a set of regions. Figure 5 shows a simplified representation of this principle. In this example, the n-dimensional space is divided into several rectangular areas by the decision boundary 23 . A depth value is assigned to the target pixel 11 according to the occupied area.

In operation, the M5 model tree algorithm is used to complete the division of the feature space. The M5 algorithm improves upon the basic example described above in two ways. The decision bounds do not have to be perpendicular to the feature space axis, and the depth can vary across regions as a linear function of image properties.

Those skilled in machine learning will understand that many learning schemes can be used in place of the M5 model tree algorithm, including neural networks, decision trees, decision graphs, and nearest neighbor classifiers. The actual nature of the learning algorithm does not affect the novelty of the invention.

In a preferred embodiment, the learning process operates on image properties x, y, R, G and B. Alternative embodiments may operate on higher level image properties such as larger groups of pixels, and may also operate on measurements such as mean and variance or bounds, corner values, etc. (i.e., response feature detector). Larger groups of pixels may eg represent segments in an image, which are connected groups of pixels forming homogeneous regions.

second stage

The second stage operates on a sequence of images, where at least one frame is identified as a keyframe. It receives 3D volumetric data, usually in the form of a depth map, for each keyframe. This depth map can be attributed to any process such as, but not limited to, manual specification, output of the first stage described above, depth determined from stereoscopic images, or depth obtained directly using a range finding system. Additionally, 3D stereo information may take other forms than depth maps, such as disparity information obtained from keyframes containing stereo pairs.

For all other frames in the 2D image sequence, the present invention provides the specification of the depth map according to the initially obtained key frame information. Hopefully, the number of keyframes is only a small fraction of the total number of frames. Thus, the present invention provides a method that greatly reduces the number of depth maps that need to be generated in the first place.

Create mapping function

Once the system is provided with keyframes and their corresponding depth maps, the system analyzes the keyframes and corresponding originally derived depth maps to create a mapping function. The mapping function may be a procedure or function that takes as input a given measurement of any 2D image and provides as output a depth map of that image. The map is learned by capturing the relationship between keyframe image data and the depth map data for those images.

The mapping function can take the form of any ordinary processing unit that receives and processes input data and gives an output. Preferably, the processing unit should be subject to a learning process, wherein the property is determined by examining keyframe data and their corresponding depth maps. Such mapping functions are well known in the field of machine learning and include, but are not limited to, neural networks, decision trees, decision graphs, model trees, and closest classifiers.

The system attempts to learn the relationship between input data and desired output data. During a learning process, the training algorithm is provided with information from 2D keyframe images. This information can be presented on a pixel-by-pixel basis, providing pixel measurements such as red, green, and blue values, or other measurements such as luminance, chromaticity, contrast, and other measurements such as horizontal and vertical position in the image such as spatial measurements. Additionally, information can be presented in the form of higher level image features, such as larger groups of pixels, and measurements such as mean and variance or boundary values, corner values, etc. are made over groups of pixels (i.e., the response of a feature detector ). Larger groups of pixels may eg represent segments in an image, which are connected groups of pixels forming homogeneous regions.

Just for description, 2D images can be represented in the form of x, y, R, G, B, where x and y represent the x and y coordinates of each pixel, and R, G, B represent the red, green and the blue value.

Next, the corresponding depth map is presented to the training algorithm so that the mapping it needs can be obtained. Individual pixels are typically presented to the training algorithm. However, if higher level image characteristics are being used, such as larger pixel groups or segments, then the depth map may be depth measurements for that pixel group, such as mean and variance.

For illustration purposes only, the depth map may be represented in the form z, x, y, where x and y represent the x and y coordinates of each pixel, and z represents the depth value assigned to the corresponding pixel.

Those working in artificial intelligence will understand that this process of learning the relationship between input data and desired output can take many forms. A preferred embodiment of the learning algorithm is designed to assign a mapping function that minimizes some measured mapping error.

This learning algorithm attempts to generalize the relationship between 2D image information and the depth map that occurs in keyframe instances. This inductive form is then applied to complete the depth map for the entire sequence. Examples of successful learning algorithms known in the art are backpropagation for learning neural networks, the C4.5 algorithm for learning decision trees, and the K-means algorithm for learning beam-type classifiers.

Just for descriptive purposes, the learning algorithm can be assumed to compute the following relationship for each pixel in a 2D image

z _n =k _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n where,

n is the nth pixel in the keyframe image

z _n is the depth value assigned to the pixel at x _n , y _n

k _a to k _e are constants and determined by the algorithm

R _n is the red component value of the pixel at x _n , y _n

G _n is the green component value of the pixel at x _n , y _n

B _n is the blue component value of the pixel at x _n , y _n

Those skilled in the art will appreciate that the above equation is a simplification for the sake of explanation and it will not work in practice. In practice, using e.g. a neural network and given a large number of pixels in an image, the network will learn a large equation involving k values, multiplication and addition.

This process is illustrated in Figure 3, which shows a similar process that can use a different number of keyframes.

apply mapping function

The invention will then take this mapping function and apply it on the set of 2D images for which no depth map is available. For a given 2D image in the set, the input to the mapping function is determined in a similar manner to that provided to the mapping function during learning. For example, if a mapping function is learned by taking measurements of individual pixels as input, the mapping function will require these same measurements for every pixel in the new image. Using these inputs, the mapping function does what it has learned and outputs a depth measurement. Also, in the single pixel example, the depth measurement may be a simple depth value. In this example, the mapping function is applied throughout the image sequence to complete the entire depth data set for the image sequence. Additionally, if larger pixel groups are used to train the mapping function, such larger pixel groups need to be generated for new image parameters. Higher level measurements on these groups of pixels, such as mean and variance, are done in the same way as in the learning process. Using these established inputs, the mapping function produces the desired depth measurement for that pixel group.

For a 2D image sequence, the keyframes with the depth map can be spaced in any arbitrary way over the sequence. In a preferred embodiment, the mapping function will be provided with a set of keyframes and their corresponding depth maps across a set of 2D images with some common points. In the simplest case, two keyframes are used to train a mapping function, and the mapping function is then used to determine the depth map of the 2D image between the two said keyframes. However, there is no limit to the number of keyframes that can be used to train the mapping function. Furthermore, there is no limit to the number of mapping functions used to complete the entire set of 2D images. In the preferred embodiment, two keyframes separated by one or more intervening frames are defined as input to the second stage of the process. The purpose of this stage is to assign a depth map to each of these interpolated frames. The preferred order for assigning depth maps to interpolated frames is the processed frame closest in time to the keyframe first. The frame that has been processed then becomes the keyframe for the next frame of the depth map.

The addition of this time variable helps the training function generalize the information provided in the keyframes. Without a temporal variable, the depth information in the two keyframes would conflict with each other. This can happen when similarly colored pixels appear in the same spatial region in two keyframes but belong to different objects. For example, in the first keyframe, a green car can be observed in the center of the image whose foreground has depth features. In the next keyframe, the car may have moved, showing behind it a small green pasture whose depth properties define the terrain area in between. The training algorithm is provided with two keyframes, both with a green pixel in the center of the image, but with different depth characteristics. It is not possible to resolve the conflict, and the mapping function is not expected to work well in such regions. By introducing a temporal variable, the algorithm is able to resolve this conflict by identifying that the green pixel at the center of the image is the temporally closest foreground pixel to the first keyframe in the image sequence. As time progresses toward the second keyframe, the training algorithm will become more able to identify the green pixel in the middle of the image as the middle ground depth of the green pasture.

This process is shown in the example of FIG. 6 . Boxes represent individual frames of an image sequence. The upper row represents the source frames, numbering them according to their relative position in the image sequence. The bottom row represents the depth map produced by this stage. The number indicates the level at which the depth map was generated. While it should be understood that depth frames 1 and 2 may be processed in reverse order, depth frames 3 and 4 may similarly be reversed, and so on. Keyframe 7 is set as input to processing as described above. The first depth map to be generated is associated with source frame 1 as shown. Use the first two depth maps generated to generate any subsequent depth maps.

preferred embodiment

For each pixel in the frame for which depth is to be drawn, the image properties of the target pixel are used to determine the depth associated with that pixel. In the preferred embodiment, two depth estimates are retrieved, one for each keyframe. This process is illustrated in Figure 7, which shows how the target pixel 11 is compared to the closest source keyframe 6 before and after the current frame in the image sequence (steps 12 and 13). Similar to what was previously described, the learning process uses a search radius of 14 to identify pixels with similar image properties, and uses the depth associated with said pixels (steps 15 and 16) to compute the depth of the target pixel (steps 17 and 18) . Each keyframe yields an estimate of the target pixel depth, which we denote as D1 and D2.

In order to determine the final depth relative to the target pixel, D1 and D2 must be combined. In a preferred embodiment, a weighted average of these values is calculated using the position of the keyframe as a weighting parameter. If the distance from the current frame to the first keyframe is T1 and the distance from the current frame to the second keyframe is T2, then the depth of the target pixel is given by: $\mathrm{<figure-callout\; id="1"\; label="w"\; filenames="A0181621400231.png,A0181621400252.png"\; state="\{\{state\}\}">w</figure-callout>}1=\frac{1}{{\mathrm{<figure-callout\; id="1"\; label="T"\; filenames="A0181621400231.png,A0181621400252.png"\; state="\{\{state\}\}">T</figure-callout>}1}^2}$ $w2=\frac{1}{{T2}^2}$

where D1 and D2 are the depths calculated from keyframe 1 and keyframe 2, respectively.

In some cases, the learning process cannot determine the depth value for a given pixel. If during the above calculations one of the two keyframe depth estimates cannot be determined, assign the target pixel to the keyframe depth estimate to be assigned without weighting. If both estimates D1 and D2 are undefined, expand the search radius and repeat the process.

It should be noted that only one keyframe is needed to generate the depth map for any other frame. However, in cases where the depth of the object changes in the sequence of images, two or more keyframes weighted as described above will provide improved results.

It should be understood that the order in which frames are processed and the manner in which results from multiple key frames are combined can vary without substantially affecting the nature of the invention.

As in the case of 2D images, it will be appreciated that this training phase may be implicit in the learning-based example, determining a depth estimate at any pixel of an image in the sequence.

This process is shown in FIG. 4 .

It is to be understood that a learning process similar to that used for Phase 1 can be implemented in Phase 2 . Two of these mapping functions can be written as one file using 6000 bytes, then for that cost we get 20 frames of depth information. This effectively represents a file of size 6000/20 = 300 bytes per frame. In practical applications, this efficient compression will be important.

In another application, the above compression may allow efficient transfer of 3D information embedded in a 2D image source, ie a 2D image compatible with the 3D image. Adding a 3D image to a 2D image sequence can be done with very little overhead since the file length required by the mapping function is usually a small fraction of the 3D information provided by the 2D image data.

In this case, the 3D information is generated at the viewing end only by applying a mapping function on each 2D image in the sequence as it is viewed, either before viewing or at the time of viewing. This is only possible when the types of mapping functions found in machine learning are efficient for providing computation after they have been trained. Usually this training process is slow and resource intensive, and is usually done offline in the process of building 3D image content. Once trained, this mapping function can be delivered to the viewer and can be done with very high throughput suitable for real-time conversion of 2D images to 3D.

Applicant's own previous publication relates to techniques for converting 2D images to stereoscopic 3D images. The disclosed conversion process involves generalization of a depth map associated with a 2D image. In one embodiment, the depth map is manually created frame by frame. The improvements described in this application enable a smaller number of keyframes with created depth maps and computed intermediate depth maps. Since keyframes represent a very small fraction of the total number of frames, this new technique represents a significant conversion improvement that is both time and cost efficient.

The specific content of this publication is that the invention should be applied to the creation of depth maps, not to the generation of stereo maps.

Those skilled in the art will appreciate that this depth map is widely used in the special effects industry in a process known as rotoscoping. In order to composite live action or computer-generated images within 2D images, depth maps or shading for each 2D image frame typically must be manually generated. These shadings composite the additional image so that it appears moved with the approximate geometry of the original 2D image. The invention described above enables rapid generation of such shading.

It is also known to develop cameras capable of obtaining depth maps from live scenes. Typically these employ laser ranging technology and are commonly referred to as LIDAR devices. In order to capture depth maps at the speed of television frames, an expensive and complex system is required. The application of the present invention enables simpler and relatively uncomplicated LIDAR devices to be designed that only need to capture depth maps at a fraction of the video field rate or at other unusual periods, and the captures are generated by interpolation using the techniques described in this invention The missing depth map. Often a depth map or shading must be manually generated for each 2D image frame. These shadings composite the additional image so that it appears moved with the approximate geometry of the original 2D image. The invention described above enables rapid generation of such shading.

It is also known to develop cameras capable of obtaining depth maps from live scenes. Typically these employ laser ranging technology and are commonly referred to as LIDAR devices. In order to capture depth maps at the speed of television frames, an expensive and complex system is required. The application of the present invention enables simpler and relatively uncomplicated LIDAR devices to be designed that only need to capture depth maps at a fraction of the video field rate or at other unusual periods, and the captures are generated by interpolation using the techniques described in this invention The missing depth map.

Claims (38)

1. A method for creating a depth map, comprising the steps of: assigning a depth to at least one pixel or part of the image; determining the relative position and image characteristics of each of said at least one pixel or portion of said image; using said depth, image properties and respective relative positions to determine the configuration of the first algorithm to determine depth properties as a function of relative position and image properties; using said first algorithm to calculate a depth characteristic for each pixel or portion of said image; Wherein, the depth characteristics form a depth map of the image. 2. A method for creating a depth map, comprising the steps of: assigning a depth to at least one pixel or part of the image; determining x,y coordinates and image properties for each of said at least one pixel or portion of said image; using said depth, image properties and respective x, y coordinates to determine a first algorithm to determine depth properties as a function of x, y coordinates and image properties; using said first algorithm to calculate a depth characteristic for each pixel or portion of said image; Wherein, the depth characteristics form a depth map of the image. 3. The method according to claim 1, wherein said image characteristics include RGB values. 4. A method according to any preceding claim, further comprising the step of reassigning depth to any pixel or part of the image to correct any inconsistencies. 5. A method according to any preceding claim, wherein said image characteristic comprises any of a luminance, chrominance, contrast or spatial measure. 6. The method according to any preceding claim, wherein said first algorithm can be represented by the following equation: z=f(x, y, R, G, B) where x and y define the relative position of a sample. 7. A method according to any preceding claim, wherein a learning algorithm is used to determine the configuration of the first algorithm. 8. The method of claim 7, wherein, for each pixel in the image, the learning algorithm calculates: z _n =K _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n where n is the nth pixel in the keyframe image z _n is the depth value assigned to the pixel at x _n , y _n k _a to k _e are constants, determined by the algorithm R _n is the red component value of the pixel at x _n , y _n G _n is the green component value of the pixel at x _n , y _n B _n is the blue component value of the pixel at x _n , y _n . 9. A method according to claim 7 or 8, characterized in that a stochastic component is introduced into the learning algorithm to reduce overtraining. 10. The method according to claim 9, wherein said random component is a small positive or negative random number. 11. The method according to any one of claims 7-10, wherein the learning algorithm initially identifies pixels having characteristics similar to known pixels. 12. The method according to claim 11, characterized in that similar pixels are searched within a search radius. 13. The method of claim 12, wherein the search radius varies for each characteristic. 14. A method according to any one of claims 11 to 13, characterized in that the depth of a pixel is determined by a weighted average of the distances to similar pixels. 15. The method of claim 14, wherein the weighting value is inversely proportional to the distance. 16. The method of claim 7, wherein each property is segmented or divided into a set of regions and assigned a depth value according to the occupied region. 17. A method of creating a series of depth maps for a sequence of images comprising the steps of: receiving a depth map of at least one frame in the sequence of images; using said at least one depth map to determine a second configuration of a second algorithm to determine depth characteristics as a function of relative position and image characteristics; The algorithm is utilized to create a depth map for each frame of the sequence of images. 18. A method of creating a series of depth maps of a sequence of images comprising the steps of: receiving a depth map of at least one frame of the sequence of images; determining a second algorithm using said at least one depth map to determine depth characteristics as a function of x, y coordinates and image characteristics; The algorithm is utilized to create a depth map for each frame of the sequence of images. 19. The method according to claim 17 or claim 18, characterized in that at least two depth maps corresponding to at least two frames of the image sequence are received. 20. The method according to any one of claims 17 to 19, wherein said image characteristics include RGB values. 21. A method according to any one of claims 17 to 20, wherein said image characteristics comprise at least one of brightness, chromaticity, contrast or spatial measurements. 22. The method according to any one of claims 17 to 21, wherein a learning algorithm is used to determine the configuration of the second algorithm. 23. The method according to claim 22, wherein the learning algorithm is one of the backpropagation algorithm, the C4.5 algorithm or the K-means algorithm. 24. The method according to claim 22 or 23, wherein said second algorithm calculates: z _n =K _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n where n is the nth pixel in the keyframe image z _n is the depth value assigned to the pixel at x _n , y _n k _a to k _e are constants, determined by the algorithm R _n is the red component value of the pixel at x _n , y _n G _n is the green component value of the pixel at x _n , y _n B _n is the blue component value of the pixel at x _n , y _n . 25. A method according to any one of claims 17 to 24, characterized in that an additional algorithm configuration is created for each pair of frames for which a depth map has been received. 26. A method of creating a series of depth maps of a sequence of images comprising the steps of: receiving depth maps of at least two keyframes of the sequence of images; using said depth map to determine a second algorithm to determine depth characteristics as a function of x, y coordinates and image characteristics; The algorithm is utilized to create a depth map for each frame of the image sequence, wherein frames adjacent to the key frame are processed before non-adjacent frames. 27. The method of claim 26, wherein once the adjacent keyframes have been processed, the adjacent keyframes are used as keyframes for creating further depth maps. 28. The method according to claim 22, 23, 26 or 27, wherein said second algorithm calculates: z _n ＝K _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n +k _f .T where n is the nth pixel in the image z _n is the depth value assigned to the pixel at x _n , y _n k _a to k _f are constants previously determined by the algorithm R _n is the red component value of the pixel at x _n , y _n G _n is the green component value of the pixel at x _n , y _n B _n is the blue component value of the pixel at x _n , y _n T is the time measurement for that particular frame in the sequence. 29. A method of creating a sequence of depth maps of an image sequence, comprising the steps of: selecting at least one key frame from said sequence of images; For each of the at least one keyframe, assigning a depth to at least one pixel or a portion of each frame; determining the relative position and image characteristics of each of said at least one pixel or a portion of each of said keyframes; Using said depth, image characteristics and respective relative positions of each said at least one key frame to determine a first configuration of said first algorithm for each said at least one frame, thereby determining a function as a function of relative position and depth characteristics depth features; calculating a depth characteristic of each pixel or portion of each of said at least one keyframe using said first algorithm; Wherein, the depth characteristics form a depth map of each of the at least one key frame, using each depth map to determine a second configuration of the second algorithm to determine depth characteristics for each frame as a function of relative position and image characteristics; Using the second algorithm to create individual depth maps for each frame of the image sequence. 30. The method of claim 29, wherein frames adjacent to the key frame are processed before non-adjacent frames. 31. The method according to claim 30, characterized in that the next processed adjacent frame is regarded as a key frame for further processing. 32. A method of encoding a series of frames comprising transmitting with said frames at least one mapping function, characterized in that said mapping function comprises an algorithm for determining the depth features. 33. The method according to claim 32, wherein said image characteristics include RGB values. 34. A method according to claim 32 or 33, wherein said image characteristics comprise at least one of brightness, chromaticity, contrast or spatial measurements. 35. The method according to any one of claims 32 to 34, wherein said mapping function is determined using a learning algorithm. 36. The method according to claim 35, wherein the learning algorithm is one of the backpropagation algorithm, the C4.5 algorithm or the K-means algorithm. 37. according to the described method of claim 35 or 36, it is characterized in that, described mapping function calculation: z _n =K _a .x _n +k _b .y _n +k _c .R _n +k _d .G _n +k _e .B _n where n is the nth pixel in the keyframe image z _n is the depth value assigned to the pixel at x _n , y _n k _a to k _e are constants, determined by the algorithm R _n is the red component value of the pixel at x _n , y _n G _n is the green component value of the pixel at x _n , y _n B _n is the blue component value of the pixel at x _n , y _n . 38. A method according to any one of claims 32 to 37, characterized in that an additional algorithm is created for each pair of frames for which a depth map has been received.

Images