JP2003522999A - Block-based intensity reconstruction method for static display scenes contained in a frame sequence divided into an array of blocks - Google Patents

Abstract

(57) [Summary] In order to display a static scene, a value related to the intensity of each block is assigned to each of the frame sequences divided into each of the patterns of the block.

Description

Detailed Description of the Invention

The invention relates to a method as described in the preamble of claim 1. Block-based image reconstruction, as distinguished from feature-based reconstruction, has the potential to achieve fast resolution, with many operations performed for it in parallel.

BACKGROUND OF THE INVENTION Matching between various images is systematically performed on all blocks in the image. Therefore, this solution can be successfully applied in situations where only a few and / or very ambiguous features in the image may be identified. Furthermore, the method of the present invention may function as a pre-processing step for a feature-based method so that the combination with the feature-based method is more economical with respect to the required throughput. Feature-based reconstruction is itself part of the prior art. The invention is used in interpolation between consecutive frames in an inter alia.

Block-based intensity reconstruction algorithms to date have assigned a single intensity value to each rectangular block of pixels in the image, producing a more continuous intensity-based resolution of the intensity map than the original image. Sometimes. Moreover, the prior art method is essentially a motion estimation algorithm, where a set of intensity data is assigned based on only two consecutive images in the original sequence.

The prior art therefore creates intensity maps with low resolution and limited accuracy due to the inability to use time integration based on long sequences of received images. The present invention ensures that these two problems are mitigated.

SUMMARY OF THE INVENTION Consequently, and in particular, it is an object of the invention to create intensity maps with improved resolution and accuracy. This is a value (depth-as
Sociated value) to each of the pixels of the block, allowing multiple depth candidate depth values per block, and systematically with an excessive set of candidate intensity values. This is due to pruning.

Accordingly, according to one of its aspects, the invention is characterized according to the characterizing part of claim 1.

The invention also relates to a device configured to implement the method described above. Further advantageous aspects of the invention are set out in the independent claims.

DETAILED DESCRIPTION OF THE INVENTION These and further aspects and advantages of the present invention are illustrated in detail below with reference to the disclosure of a preferred embodiment, and in particular with reference to the accompanying drawings.

[0009]   The principle of the present invention is shown below.

A: To store a frame, each pixel of the block gets uniformly a value related to the intensity assigned to the entire block in question.

B: One or more candidate intensity-related values are used to assign intensity-related values to the block. Each of the values is derived from the previous block in the mapping of the frame sequence for a particular block. The actual allocation may be postponed through holding multiple candidates.

C: The resulting allocation uses an error minimization procedure based on the candidates that are actually available for the block in question.

In addition, in a preferred embodiment, the method proposed herein uses the following additional means. Needless to say, or instead of the various ones mentioned above, are limited to less scalable ones.

1. In the preferred embodiment, instead of the intensity values themselves, they are used as intensity-related values rather than mutual intensity values. This value is the uncertainty interval (v, d)
, V is a value related to the expected intensity, d is the predicted uncertainty, preferably the standard deviation in the Gaussian probability distribution. Instead of exact intensity values, in a preferred embodiment, to accurately reflect the difference between assigning intensity to near parts of the scene and assigning intensity to distant parts of the scene,
Use mutual intensity values. Through the use of mutual intensities, the absolute accuracy that can be achieved is approximately uniform over near and far parts of the scene.

[0015]   2. Each pixel has an interval of uncertainty of intensity assigned to it.

3. During the first two time steps, ie the frames at instants t and t + 1, a typical block-based matching procedure is used. This means that, for example, 5 × 5 pixels are measured together with the predicted value for the associated uncertainty interval and a single mutual intensity value is assigned to all standard blocks.

4. All pixels in the block receive this intensity-related value plus its associated uncertainty interval.

5. The information between t + 1 and t + 2 is then considered by interpolating each of the pixels in frame t as a single point plus the spacing of the associated intensities in three-dimensional space. Based on the assumed camera movement, the information is t +
These points are transferred to the peer system associated with the image at 1 and given from the external space.

[0019] 6. The frame at t + 1 is then divided into standard size blocks. The block at t + 1 may then contain pixels resulting from more than a single block of pixels associated with time t. As a result, one or more candidate intensity values are
It relates to a later block or part of it.

7. The block-based intensity prediction procedure between frames t + 1, t + 2, etc.
It operates in a similar manner to the previous frame, except that many candidate intensity values may be even larger. In particular, each of the blocks provides one or more intensity values to a candidate set associated with a subsequent block of a subsequent frame that has portions mapped from various previous blocks.

8. To avoid overly large candidate sets, the number of first values in one candidate set is reduced. This is done as follows.

(A) The first reduction may be based on confidence. Here, the values associated with the strength that can be improved are eliminated. For example, this may be associated with a candidate value derived from a very small portion of the previous block.

(B) Next, the sequences v [0], v [1] ,. ． ． v [n-
1], is assumed. Here, v [0] is the minimum value among the candidate values. Assuming the required tolerance ε, no distinction is made between intensity values closer to each other than the tolerance ε.

(C) Candidate sets w [0], w [1] ,. ． ． Is reduced as follows.

W [0] = v [0]; i = 1; j = 1 while (i <n) {if ((v [i] −w [j−1]> ε) or (i = n− 1)) {w [j] = v [i]; j = j + 1;} i = i + 1;} Note that if the entire range of initial values of candidates is large, the number of candidates remains large.

9. After completing the traditional block-based matching algorithm between frame t + 1 and frame t + 2 in the large candidate set, frame t + 1
Will have a set of block strength predictions at. These values are used to update the values at the pixels in the block, as shown below.

(A) Consider a pixel with mutual intensities and associated uncertainties (v _P , d _P ),
The block to which the pixel belongs obtains (v _b , d _b ) as the result of the block-based algorithm.

[0028]   (B) Then v_PThe new value of v_P’_P'Is v_PAnd v _b Should be a convex combination of_P’= Kv_P+ (1-k) v_bCall
And this demonstrates the mixing procedure. A large value of k, 0 ≦ k ≦ 1 is the pixel
It is shown that the history of intensity assignments to P yields only a small contribution from the time integral.
is doing. Therefore, history is important in the case of integration over previous values.
Of course, other convex couplings can be realized in the same way.

[0029] (c) a new value of _{d P,} if this is referred to as _{d P} ', which depends on the following items.

The previous d _P , eg proportionally, the value of d _P , eg proportionally, the inverse of the definite level of the block to which the pixel belongs, such as inverse proportionality, etc. | v _P −v _b | Agreement between v _P and v _b to be proportional 10. This process is repeated over the next time step. Moreover, pixels may exist such that they do not originate from any previous pixels being transferred to them. These "new" pixels can receive an initial intensity assignment taken as the average of the immediately adjacent neighbor pixels. The value of those uncertainties must be set to a large value.

For an embodiment of the invention, FIG. 1 shows a simple image field or frame divided into pixels. Field 20 is a uniform block 2 of 3 rows and 4 columns
It consists of two. In fact, the number of blocks is generally large. The block 22 is composed of pixels 24 arranged in 4 rows and 4 columns. In fact, the number of pixels in the block is
It is an odd square such as 5 × 5 pixels.

In contrast discrimination, the invention may be implemented with frames divided into non-uniform blocks. For example, in the center of the frame you have a relatively small block,
It has relatively large blocks around the frame. Further, consecutive frames may be divided into blocks in a non-uniform manner. For example, a frame with a relatively small spread in intensity may get a different pattern than a frame with a larger spread in intensity.

FIG. 2 shows an example of the relative spatial mapping of blocks at time-varying moments. At the first moment, the block 26 is located by the solid line. At the next (or previous) moment, the corresponding block is located by the dashed line. In this case, there is a uniform shift to the right by two pixels and a uniform shift down by one pixel.

Of course, the two shifts are independent of each other. Further feasible changes are changes in rotation and magnification. All the changes described may occur in combination with creating for every possible movement of the physical object that is the source of the image.

The method according to the invention receives a camera motion that captures a scene from an outer entity. Motion estimation itself is part of the prior art. For example, the motion value can be derived from the known motion of a camera mounted on the robot arm. Given this motion, the present invention starts to assign an intensity-related value for each block as to the image plane. Therefore, the lateral movement will cause an intensity parameter for the image plane independent of each pixel. The above scheme is used to interpolate intermediately between successive images in the image stream.

Pixels fall into various categories. First, the pixels in each of the two images are completely located within the block in question. Second, in either the first image or the second image, or both, the pixels are partially placed inside the block in question. Third, in one of the two images, the pixel of interest lies entirely outside the block of interest. This feature may also occur in combination with the second case.

FIG. 3 shows the value z 1 associated with the intensity in two consecutive frames t and t + 1.
2 shows a first mapping of two blocks b1 (t) and b2 (t) at z and z2 respectively.

Here, the relative movement between the moments belonging to frames t and t + 1 is such that the mapping of those blocks decays relative to each other. This makes it relatively easy to assign a strength-related value to the frame at t + 1 because the candidate set is small.

FIG. 4 shows the intensity-related value z in two consecutive frames t and t + 1.
Block b3 (t) at 3 and a block b4 (t) at a value z4 related to depth
2 are shown.

As shown, the relative motion between the instants belonging to frames t and t + 1 is such that the mappings of those blocks are closer to each other. This makes the assignment of intensity-related values to block b5 (t + 1) of the frame at t + 1 relatively complex, since both original blocks can produce candidate intensity-related values. Become. In fact, the candidate set is much larger than two. The present invention provides that at some moment in time a choice must be made and such choice may be postponed to some extent.

FIG. 5 shows the mapping of blocks 20 to scene elements 22 in frame 24. It will be appreciated that, according to the present invention, assigning a single intensity-related value to a block 20 may reduce the display quality while increasing the granularity of the block-based representation. Through considering the history of the individual pixels belonging to the block in question, the distribution of values associated with different intensities over the block in question is still achieved. Therefore, delaying the actual allocation improves quality.

FIG. 6 shows an apparatus configured to implement the method of the invention. A memory block (DEPTH) 30 receives a value associated with the intensity of each block and a value (IN1) of the uncertainty of each of them, and stores these two data separately for each pixel.

A motion realization block (MOTION) 32 is supplied with various pixel data from the storage block 30 and also receives relevant motion information from the outside. This allows
All pixel data received for various blocks of the next frame in the sequence can be mapped. Based on that, the assignment block (ASSIGN) 34
Provides a list of candidates that can be assigned to each of the blocks in the next frame for the above two values. Based on that, the reduction block (REDUCE) 36 reduces the list of each candidate of the block based on the previously determined optimization criteria.

The selection unit (SELECT) 38 then selects or mixes one of the available candidates for each of the blocks. This allows the display unit (DISPLA
Y) 40 can represent each of the blocks with a value associated with a single intensity. Furthermore, it allows the storage block 30 to store, for each pixel, a single possible value associated with the intensity and the associated uncertainty interval.

[Brief description of drawings]

[Figure 1]   An image field divided into blocks and pixels.

[Fig. 2]   It is a relative spatial mapping of blocks at time-varying moments.

[Figure 3]   A first mapping of two blocks into two consecutive frames.

[Figure 4]   A second mapping of two blocks into two consecutive frames.

[Figure 5]   It is a block-to-scene element mapping.

[Figure 6]   1 is an apparatus configured to implement the method of the present invention.

─────────────────────────────────────────────────── ─── Continued front page    (72) Inventor van Overfeld, Cornelis               Way A M             Netherlands, 5656 Earth Ardine             Fen, Plov Holstran 6 F-term (reference) 5C059 NN01                 5L096 CA04 GA19 HA02 HA07

Claims (10)

[Claims] 1. A method of assigning a value associated with intensity for each block to each of a sequence of frames divided into each pattern of the block to represent a static scene, the method comprising: During the first subsequence, a single intensity-related value for the associated intensity uncertainty interval and a prediction value are assigned to each of the blocks, and for each particular block, these two values are assigned to that value. Assigning uniformly to all pixels in the sequence, and during the subsequent frame (t + 2), assigning each of the pixels in the non-last frame of the sequence (t) to a single point and associated intensity in three-dimensional space. By interpreting it as an interval of uncertainty, we take into account the information between the last frame of the sequence (t + 1) and the following frame, and based on the predicted camera motion. And transferring various single points to the peer system associated with the last frame (t + 1) of the sequence, dividing the last image of the sequence (t + 1) into blocks, and Allowing such blocks to include pixels resulting from one or more blocks of interest and associating one or more intensity values with any such block, during subsequent frames t + 2, t + 3, etc. The block-based intensity prediction procedure is repeated in the same manner to allow multiple candidate intensity-related values per block, in particular a particular previous block may receive one or more intensity-related values for subsequent blocks. A step of allowing a plurality of candidate strength-related values to be given, and a block of frames between frames t + 1 and t + 2 in the actual plurality of candidates. After completing the matching had method comprising the steps of updating the value for the pixel in use, after the block prediction of a set of values associated with the intensity for the block in the frame t + 1, a. 2. A method according to claim 1, wherein the intensity-related value is the expected mutual intensity v subject to the predicted uncertainty interval d. 3. The method of claim 2, wherein the uncertainty interval is a standard deviation in a Gaussian probability distribution. 4. The method of claim 1, wherein under certain circumstances the actual number of intensity-related values in the plurality of candidate values is reduced to a lower number. 5. The method of claim 4, wherein the reduction is done by combining candidate values that are closer to each other than a preset tolerance value. 6. The method of claim 3, wherein said reducing is done by mixing two candidate intensity-related values for which a convex bond is formed. 7. The method according to claim 1, which is used as a preprocessing step for a reconstruction procedure based on image features. 8. The method according to claim 1, which is used as an interpolating method between frames. 9. A method according to claim 1, wherein a value associated with intensity per block is assigned to each of the frame sequences divided into each of the patterns of the block to represent a static scene. A device configured to provide a single intensity-related value and a prediction value for each of the blocks during the first sub-sequence of frame (t, t + 1) for the associated intensity uncertainty interval. Allocation, for each of the particular blocks, allocation means for evenly allocating these two values to all pixels therein, and not during the next subsequent frame (t + 2) of the sequence (t). By interpreting each of the pixels in a frame as a single point and associated intensity uncertainty interval in three-dimensional space, the last frame of the sequence (t + 1) and then Considering means for transferring information to and from the frame and transferring various single points to the peer system associated with the last frame (t + 1) of the sequence based on the predicted camera motion, said sequence ( t + 1) the last image is divided into blocks, allowing such blocks to include pixels resulting from one or more blocks associated with the non-last frame (t), and one or more intensity values in any such block. And a dividing means for allowing the association of the above, and similarly, during the subsequent frames t + 2, t + 3, etc., the above-described block-based intensity prediction procedure is similarly repeated to allow a plurality of candidate intensity-related values per block. In particular, it allows a particular previous block to provide one or more intensity-related values to multiple candidate intensity-related values of a subsequent block. And a prediction of the set of intensity-related values for the block at frame t + 1 after completing the block-based matching between frames t + 1 and t + 2 with the actual candidates. Updating means for updating the values for the pixels in the block. 10. Storage means for storing values relating to intensities belonging to each of the blocks of a particular frame, mapping all pixel data supplied by said storage means, and of the next frame in the sequence. Motion realization means for controlling externally generated motion information attached to the intensity value data for the various blocks, and for values related to the strength for each of the blocks in the next frame, provided by said motion realization means Assigning means for producing a list of allocatable candidates of and the respective uncertainty intervals of the value, and for each of the blocks based on pre-specified optimization criteria supplied by said assigning means Reducing means for reducing the list of candidate values, and display for next display, supplied by the reducing means Selection means for selecting or mixing only one for each of the blocks from the candidate values available to the storage means for repeating the reconstruction in stages and / or during subsequent frames; The apparatus of claim 1, comprising: