JP5130381B2 - Method and apparatus for efficient video processing - Google Patents

Abstract

A video compression method and apparatus uses an active decoder. The corresponding encoder can produce an encoded bitstream with a greatly reduced overhead by encoding a reference frame (102) based on the structural information inherent to the image (e.g., image segmentation, geometry, color, and/or brightness), and then predicting other frames relative to the structural information. Typically, the description of a predicted frame would include kinetic information (e.g., segment motion data and/or associated residues representing information in previously occluded areas and/or inexact matches and appearance of new information, and portion of the segment evolution that is not captured by motion per se, etc.). Because the decoder is capable of independently determining the structural information (and relationships thereamong) underlying the predicted frame, such information need not be explicitly transmitted to the decoder. Rather, the encoder need only send information that the encoder knows the decoder cannot determine on its own.

Description

(Cross-reference of related applications)
This application is priority to US Provisional Patent Application No. 60 / 129,853 filed on April 17, 1999 and US Provisional Patent Application No. 60 / 129,854 filed on April 17, 1999. Insist on the interests of.

(Field of Invention)
The present invention relates generally to video data compression, and more particularly to a synchronous encoder and smart decoder system for efficient transmission and storage of video data.

(Background of the Invention)
(1. Simple introduction)
As consumers desire more video intensive modes of communication, current communication modes with limited bandwidth (eg, broadcast, cable, telephone lines, etc.) are very expensive. The introduction of the Internet and the subsequent popularity of the World Wide Web, video conferencing, and digital and interactive television demand more efficient use of existing bandwidth. Furthermore, video intensive applications require enormous storage capacity. The advent of multimedia performance on most computer systems has made extreme use of traditional storage devices such as hard drives.

  By compressing, a digital moving image can be expressed efficiently and inexpensively. An advantage of compression is that more information can be transmitted within a predetermined amount of time or stored within a predetermined storage medium. The ultimate goal of video compression is that the bit stream of the video sequence, i.e., while the decoder or receiver retains sufficient information to reconstruct the video image sequence in a manner appropriate for specific applications such as television, video conferencing To reduce the video information flow as much as possible.

  Most digital signals contain a large amount of redundant useless information. For example, a still video scene produces an almost identical image in each scene. Most video compression routines attempt to remove useless information, and related image frames can be represented by previous image frames, thus eliminating the need to transmit the entire scene of each video frame. Alternatively, routines such as video JPEG encode each video frame separately and ignore temporal redundancy.

(2. Previous attempts)
There have been many attempts to properly compress video images. These methods generally fall into two categories: 1) Spatial redundancy reduction, and 2) Temporal redundancy reduction.

(2.1 Spatial redundancy reduction)
The first type of video compression is to focus on reducing spatial redundancy, i.e., to use the interrelationships between adjacent pixels to derive a more efficient depiction of important information in the image frame. . These methods are more appropriately called still image compression routines because they work fairly well on individual video image frames, but are temporally or frame-to-frame as described in section 2.2. This is because it does not address the problem of redundancy. Common still image compression schemes include JPEG, wavelets, and fractals.

(2.1.1 Image compression based on JPEG / DCT)
One of the first commonly used methods of still image compression was the direct cosine transform (DCT) compression system. This is located at the center of JPEG.

  DCT operates by representing each digital image frame as a series of cosine waves or cosine frequencies. Later, the cosine series coefficients are quantized. Higher frequency coefficients are more severely quantized than lower frequency coefficients. The result of the quantization is a very large number of zero coefficients and can be encoded very efficiently. However, JPEG and similar compression schemes do not address the very serious problem of temporal redundancy.

(2.1.2 Wavelet)
As a slight improvement over the DCT compression scheme, a wavelet deformation compression scheme was devised. This system is similar to DCT, but differs mainly in that the image frame is represented as a series of wavelets or electromagnetic window amplitudes instead of a series of cosine waves.

(2.1.3 Fractal)
Another technique is known as fractal compression. The goal of fractal compression is to capture an image and determine a function or set of functions that adequately represent the image frame. A fractal is an object that is self-similar at different scales or resolutions, ie the object remains the same no matter what resolution the person sees. Theoretically, very high compression ratios can be achieved when fractals and simple equations can represent complex images.

  Unfortunately, fractal compression is not a likely method of general compression. High compression ratios can only be achieved for specially constructed images and only with considerable help from the human who guides the compression process. Furthermore, fractal compression is very computationally intensive.

(2.2 Reduction of temporal and spatial redundancy)
Proper video compression requires a reduction in both temporal and spatial redundancy in the sequence of frames containing the video. Temporal redundancy removal relates to the removal of information already encoded in previous image frames from the bitstream. Block matching is the basis for the currently most effective method of temporal redundancy removal.

(2.2.1 Motion estimation based on blocks)
In block matching, the image is subdivided into uniformly sized blocks (more commonly polygons), and each block is re-encoded and placed in the bitstream for the second time, It is tracked from one frame to the next and is represented by a motion vector. Examples of compression routines that use block matching include MPEG and its modifications.

  MPEG encodes the first frame in a series of related frames as a so-called intra frame, or I frame. An I-frame is a type of key frame, meaning an image frame that is completely self-contained and is not represented in association with any other image frame. To generate an I frame, MPEG performs still image compression on the first frame, including dividing the frame into 16 pixel by 16 pixel square blocks. Other (so-called “predicted”) frames are encoded with respect to the I frame by predicting the corresponding block of the other frame associated with the block of I frame. That is, MPEG tries to find each block of an I frame within another frame. For each block still present in the other frame, MPEG transmits the block's motion vector, or motion, along with the block identifying information. However, the blocks can change slightly as they move from frame to frame. The difference associated with an I frame is known as the remainder. In addition, as the blocks move, previously hidden areas may only be visible. These hidden areas are also known as the remainder. That is, the collective remaining information after the block motion is transmitted is known as the remainder and is coded using JPEG and sent to the receiver to complete the image frame.

  Subsequent frames are predicted with respect to either a block of I-frames or a previous predicted frame. Further, the prediction can be bi-directional, i.e., both for the previous I frame and the subsequent I frame or for the predicted frame. The prediction process continues until a new key frame is inserted, at which point a new I frame is encoded, and the process repeats.

  Although state of the art, block matching is very inefficient and cannot use known physical properties or other information inherent in the image. The blocking method is arbitrary and rough. This is because the block has no relationship with the real object in the image. A given block may include part of an object, all of an object, or even a plurality of different objects with irrelevant motion. In addition, nearby objects often have similar movements. However, because blocks do not represent real objects, block-based systems cannot use this information to further reduce the bitstream.

  However, another major limitation of block-based matching arises. This is because the remainder generated by matching based on blocks is generally noisy and inconsistent. Therefore, block-based residuals are not suitable for good compression via standard image compression schemes such as DCT, wavelets, or fractals.

(2.3 Alternative)
It is well understood that the state-of-the-art needs improvement, particularly in that block-based methods are extremely inefficient and do not produce an optimally compressed bitstream for moving picture information. To that end, modern compression schemes such as MPEG4 do not simply use blocks of arbitrary size, but instead provide limited structural information on selected items in the frame, if available. May be included. Although some compression gain has been achieved, the associated overhead information has increased substantially. Because, in addition to motion and residual information, these schemes require that structural or shape information about each object in the frame also needs to be sent to the receiver. This is because all current compression schemes use dumb receivers—receivers that cannot determine the structure of the image by themselves.

  Furthermore, as noted above, current compression methods are simply another that are compressed by JPEG using a fixed compression technique without attempting to determine if other more efficient methods are possible. The remainder is treated as an image frame.

(3. Advantages of the present invention)
The present invention provides various advantages regarding the video compression problem. As described above, the goal of video compression is to accurately represent a sequence of video frames with a minimal bitstream or video information flow. As mentioned earlier, the above spatial redundancy reduction method is not suitable for moving picture compression. In addition, current temporal and spatial redundancy reduction methods such as MPEG waste valuable bitstream space due to the need to transmit a lot of overhead information.

  Accordingly, there is a need for an improved technique for encoding (and decoding) video data that exhibits increased compression efficiency, reduced overhead, and a smaller encoded bitstream.

(Summary of the Invention)
Digital video compression is a process in which both spatial and temporal useless or redundant information contained within a sequence of related video frames is reduced. With video compression, a sequence of frames can be represented by a reduced bitstream or data flow, while retaining the performance that is reconstructed in a visible enough manner.

  Conventional methods of video compression impose much of the compression load (e.g., computational and / or transmission) on the encoder while minimizing the use of a decoder. In conventional video encoder / decoder systems, the decoder is “dumb” or passive. The encoder performs all calculations, communicates its decision to the decoder, and then sends video data to the encoder along with instructions for the reconstruction of each image.

  In contrast, the present invention includes a “smart” or active decoder that performs much of the transmission and command load otherwise required of the encoder. Thus, overhead is reduced, resulting in a much smaller encoded bitstream. Thus, the corresponding (ie, compatible) encoder of the present invention can generate an encoded bitstream with very reduced overhead. This encodes the reference frame based on the structural information inherent in the image (eg, image segmentation, geometric structure, color, and / or luminance) and then others related to the structural information. This is achieved by predicting a frame of. Typically, the predicted frame description represents motion of the corresponding structure (eg, image segment) from the underlying reference frame (eg, segment motion data, and / or previously occupied area). Related residuals resulting from retrieval and / or motion information (such as inaccurate matching and exposure of new information). Because the decoder can independently determine the structural information underlying the predicted frame (and the relationship between them), such information need not be explicitly communicated to the decoder. Rather, the encoder only needs to send information that the encoder knows that the decoder cannot determine by itself.

  In another aspect or embodiment of the present invention, both the decoder and the encoder make the same prediction for the subsequent image based on the previous sequence of associated images, and (not in addition to or in addition to structural information per se) These predictions are used as a basis for encoding the actual values of later images. Thus, the encoder can only transmit the difference between the predicted value and the actual value, which also reduces the bitstream.

  In yet another aspect or embodiment of the present invention, the decoder may replay the decisions made by the encoder regarding segment ordering or segment association / separation so that such decisions need to be sent to the decoder. Disappear.

  In yet another aspect or embodiment of the invention, the encoder may instruct to encode the prediction using various compression techniques and to use a decompression technique corresponding to the decoder.

  The foregoing and other aspects and embodiments of the invention are described in further detail below.

FIG. 1 is a block diagram of an encoder according to an embodiment of the present invention. FIG. 2 is a flowchart showing the operation of the encoder according to the embodiment of the present invention. FIG. 3 is a block diagram of a decoder according to an embodiment of the present invention. FIG. 4 is a flowchart illustrating an operation of the decoder according to the embodiment of the present invention. FIG. 5a is a block diagram of a codec according to an embodiment of the present invention. FIG. 5b is a block diagram of a codec according to an embodiment of the present invention. FIG. 6 is a flowchart illustrating the operation of the codec according to an embodiment of the present invention. FIG. 7 is a diagram of a reference frame. FIG. 8 is a flowchart illustrating a procedure in which a reference frame is first processed by an encoder according to an embodiment of the present invention. FIG. 9 is a flowchart illustrating a procedure for segmenting a reconstructed reference frame by an encoder according to an embodiment of the present invention. FIG. 10 is a diagram of segmentation according to one embodiment of the present invention. FIG. 11 is a diagram of motion matching according to an embodiment of the present invention. FIG. 12 is a flowchart illustrating a procedure for determining whether grouping is performed by an encoder according to an embodiment of the present invention. FIG. 13 is a flowchart illustrating motion vector grouping according to an embodiment of the present invention. FIG. 14 is a flowchart illustrating motion prediction according to an embodiment of the present invention. FIG. 15 is a flowchart illustrating motion multiscale grouping according to one embodiment of the invention. FIG. 16 is a diagram in which a region hidden before due to the movement of the segment becomes visible. FIG. 17 is a flowchart illustrating a procedure for predicting the structure of previously hidden information according to an embodiment of the present invention. FIG. 18 is a diagram of the local residual portion. FIG. 19 is a flowchart illustrating encoding a local remainder according to an embodiment of the present invention. FIG. 20 is a flowchart illustrating a procedure for embedding a command according to an embodiment of the present invention. FIG. 21 is a flowchart illustrating a procedure for transmitting a frame according to an embodiment of the present invention. FIG. 22 is a flowchart illustrating a process in which a decoder receives a reference frame according to an embodiment of the present invention. FIG. 23 is a flowchart illustrating segmentation by a decoder according to an embodiment of the present invention. FIG. 24 is a flowchart illustrating a procedure in which a decoder receives motion related information according to an exemplary embodiment of the present invention. FIG. 25 is a flowchart illustrating a procedure for determining whether a decoder can be grouped according to an embodiment of the present invention. FIG. 26 is a flowchart illustrating a procedure in which a decoder performs motion vector grouping according to an embodiment of the present invention. FIG. 27 is a flowchart illustrating a procedure of processing a background residual by a decoder according to an embodiment of the present invention. FIG. 28 is a flowchart illustrating a procedure of processing a local remainder by a decoder according to an embodiment of the present invention. FIG. 29 is a flowchart illustrating a procedure for embedding a command according to an embodiment of the present invention. FIG. 30 is a flowchart illustrating a procedure for handling user-driven events according to an embodiment of the present invention.

(Description of specific embodiments)
(1. Overview)
The following sections are specific to this embodiment, using encoders, decoders, and structure information (hereinafter referred to as “segments” in this embodiment), but are not necessarily required in another embodiment of the present invention. A description of one embodiment of the invention is provided, including specific details that are not.

(1.1 Encoder)
FIG. 1 is a block diagram of an exemplary encoder for use with a compatible decoder, as will be described later with reference to FIGS. 3 and 4, and FIG. 2 is an overview of the operation of the encoder of FIG. It is. In step 201, the encoder 100 obtains a first (eg, reference) image frame. In step 202, the functional block 102 of the encoder 100 encodes the image frame from step 201. In step 203, the image encoded from step 202 is reconstructed by functional block 103 of encoder 100 in the same manner that the decoder reconstructs the image. In step 204, functional block 104 of encoder 100 obtains structural information from the segmented, reconstructed image, that segment is of segment dynamics (eg, motion and / or residual data). Used as a basis for predicting subsequent frames from a viewpoint. A person skilled in the art how to perform image segmentation using techniques such as edge detection, edge linking, region merging, or watershed methods that need not be described in detail herein. Understand easily. Alternatively, step 203 is skipped and the encoder segments the original reference image frame from step 201. This eliminates the segment reconstruction step, which increases the efficiency of the encoder somewhat while providing a basis for predicting an image that is more similar to the image reconstructed at the decoder. To avoid. In step 205, the segments determined in step 204 are ordered by functional block 105 of encoder 100 in the same manner that the decoder orders the segments. In one embodiment, it is performed according to a predetermined standard ordering scheme known to both encoders and decoders.

  In step 206, the functional block 106 of the encoder 100 obtains a new (eg, second) image frame to be encoded corresponding to the segmented reference frame. In step 207, motion related information for each of the segments generated in step 204 is determined by function block 107 of encoder 100 by motion matching. That is, motion matching is the process of determining the change in location of an image segment from one frame to the other. Motion matching can be adapted for forward, backward and / or non-sequential frames.

  In step 208, functional block 108 of encoder 100 encodes motion related information.

  At step 209, based on the motion related information from step 208, the previously hidden area in the reference frame (hereinafter referred to as background residue) may be exposed in the new frame. In step 210, the functional block 110 of the encoder 100 orders the background residuals in the same way that the decoder uses a common predetermined standard ordering scheme. In step 211, the encoder 100 attempts to fill each of the background residuals by extrapolating from the known segment values using techniques such as linear techniques, polynomial techniques, or other predictive techniques. To do. Replenishment is also aided by considering information about the ordering or hierarchy of segments surrounding the newly exposed area. Segment ordering defines depth information known as Z-ordering. For example, if the image is an aerial view of the car motion of FIG. 7, the area exposed by the motion of the segment representing the car (segment 71) is predicted based on the segment representing the road under the car (segment 72) Can be done. In step 212, the encoder determines the difference between the actual value and the predicted value of each background residual region.

  In addition to the background residue caused by the exposure of previously blocked areas, there may also be local residues. Local residuals are associated with, for example, inaccurate matching and exposure of new information. The overall complete description of the segment therefore includes consideration of motion data and residual data (both background and local), all of which are collectively shown as reaction kinetic information. In step 213, the encoder determines a local residual area of the second image frame from the segment motion related information. In step 214, the functional block 110 of the encoder 100 orders the local residue from step 113 in the same way that the decoder uses a common predetermined standard ordering scheme. To do. In step 215, the functional block 115 of the encoder 100 encodes the background residue from step 212 and the local residue obtained from step 213. In one embodiment, the encoding may use one of many available techniques selected based on a particular residual structure that is immediately determined by the decoder.

  If the second frame image can be reasonably reconstructed primarily from motion related information with assistance from residual information, then in step 216, the encoder directly (eg, a video conference) (In application) or indirectly (eg, written to a storage medium to be decrypted for later playback) and transmitted. (A) a flag indicating that the frame is not a key frame, (b) motion related information for the segment, (c) background residual information if necessary (along with a flag indicating the coding technique used), And (d) local residual information if necessary (optionally with a flag indicating the coding technique used). After transmission, the encoder repeats this cycle beginning at step 206 with a new (eg, third) image frame to be encoded with respect to the previous reference frame. The previous reference frame may be an existing key frame or a non-key frame (ie, a reconstructed video frame). However, if the second image cannot be reasonably reconstructed primarily from motion related information with the aid of residual information, in step 217 the image is encoded as a key frame and the frame is a key frame. Is transmitted to the decoder together with a flag indicating. After transmission, the encoder repeats this cycle starting at step 203.

  The transmission may also include the transmission of any specific instructions associated with the frame by function block 118.

  Alternatively, as described in FIGS. 1 and 2, instead of determining the dynamic information from the segment of the first frame, the encoder uses the structural information from the first frame to describe the second frame. Determine the best set of basis functions or building blocks. This set of basis functions is the same set that the decoder determines, so only the coefficients of the second frame need to be transmitted from the encoder to the decoder.

(1.2 Decoder)
FIG. 3 is a block diagram of an exemplary decoder for use with a compatible decoder as described in FIGS. 1 and 2, and FIG. 4 is an overview of the operation of the decoder of FIG. In step 401, the functional block 301 of the decoder 300 receives an encoded image frame (eg, the encoded reference frame generated in step 202 of FIG. 2). In step 402, the encoded image frame from step 401 is reconstructed by functional block 302 of decoder 300 in the same manner as the encoder. In step 403, the reconstructed image frame structure information from step 402 is determined and ordered by functional block 303 of decoder 300 in the same manner as the encoder. In step 404, the decoder receives a flag from the encoder that describes whether the subsequent image frame (eg, see step 206 of the encoder descriptor) is a key frame. If it is a key frame, the decoder returns to step 401. If not, the decoder continues at step 405.

  In step 405, functional block 305 of decoder 300 receives motion related information (eg, motion and / or residual data) for the segment. In step 406, the decoder begins to reconstruct subsequent image frames using the segment obtained in step 403 and the motion part of the dynamic information obtained in step 405.

  In step 407, based on the motion related information from step 404, for the segment determined in step 403, the decoder determines the location where the previously hidden image portion, if any, is now exposed. These are known as background residue locations. In step 408, the background residue location calculated from step 407 is ordered in the same way that it is ordered by the encoder using a common predetermined standard protocol. At step 409, an attempt is made to replenish background residual locations (eg, predict background residual information) using a technology type that satisfies the same prediction as the technology used by the encoder. In step 410, the decoder receives the encoded background residual information (corresponding to the predicted background residual information) and further displays the coding method from the encoder (FIG. 2, step 216 (c)). Receive a flag to do. In step 411, the functional block 311 of the decoder 300 decodes the received background residual information. In step 412, predicted (calculated) background residual information, if any, is added to the received background residual information to determine overall background residual information, which is then Added to the second image frame.

  In step 413, for the segment determined in step 403 based on the motion related information received in step 404, the decoder determines the location of the local remainder, if any, in function block 311. In step 414, the local residual locations are ordered in the same way that the encoders are ordered using a common predetermined standard ordering scheme. In step 415, the decoder receives the encoded local residual information and a flag indicating the coding method for each local residual location. In step 416, the decoder decodes the local residual information. In step 417, the decoded local residual information is added to the second frame. In step 418, functional block 318 of decoder 300 receives any particular instruction and adds the instruction to the second frame. In step 419, functional block 319 completes the reconstruction of the second frame.

  At step 420, if there are more frames, the routine continues at step 404.

  Alternatively, as described in FIGS. 3 and 4, instead of receiving dynamic information from a segment of the first frame, the decoder uses structural information from the first frame to describe the second frame. Determine the best set of basis functions or building blocks for This set of basis functions is the same set that the encoder determines, so the decoder need only receive the coefficients of these basis functions and initiate the reconstruction.

(1.3 Encoder decoder)
The previous section describes the encoder and decoder separately, but the encoder assumes the presence of a compatible decoder and encodes the image to be decoded by a compatible decoder, and vice versa. Both are closely related. Therefore, it is useful to consider the interrelationship between the various steps of FIGS. Accordingly, FIG. 5 illustrates an exemplary encoder decoder (codec) architecture of the present invention, and FIG. 6 illustrates the exemplary (codec) operation of FIG. In step 601, the encoder obtains, encodes and transmits a reference frame, and the decoder receives the reference frame. In step 602, the reference frame from step 602 is reconstructed by both the encoder and decoder. In step 603, the same segment in the reference frame is determined by both the encoder and the decoder. In step 604, the segments from step 603 are ordered in the same manner by both the encoder and decoder.

  In step 605, the encoder obtains a new image frame. In step 606, the encoder determines the motion related information for the segment from step 603 by the motion matching the frame obtained from step 605. In step 607, the encoder encodes motion related information.

  In step 608, based on the motion related information from step 606, the encoder determines the location of the previously hidden area (background residue location) that is currently exposed in the second frame. In step 609, the encoder orders the background residue locations. In step 610, the encoder attempts to mathematically predict the image in the background residual region. In step 611, the encoder determines whether the mathematical prediction is correct based on the difference between the prediction and the actual background residual information. The encoder sends this difference so that additional background residual information is calculated if necessary.

  In step 612, based on the motion related information from step 606, the encoder determines structure information for the local remainder. In step 613, the structural information of the local remainder from step 612 is ordered by the encoder. In step 614, the encoder encodes the local remainder.

  In step 615, the encoder transmits, the decoder transmits in step 601, and the received frame should be displayed using dynamics (motion and residual) information or as a key frame. A flag identifying whether or not is received. If it is a key frame, the system returns to step 601. If not, the system continues at step 616.

  In step 616, the encoder transmits and the decoder receives segment motion related information from the encoder. In step 617, the decoder determines and orders the background residue locations in the same manner that the encoder did in steps 608 and 609. In step 618, the decoder performs the same prediction that the encoder made in step 610 for the background residual. In step 619, the encoder transmits the local residual information, if any, and a flag indicating the coding scheme, and the decoder receives. In step 620, the decoder determines and orders the local residual information in the same manner that the encoder did in steps 612 and 613. In step 621, the encoder transmits and the decoder receives a flag indicating the local residual information and coding scheme. In step 622, the particular command, if any, is transmitted and the decoder receives. In step 632, both the encoder and decoder similarly reconstruct the frame based on the dynamic information. If additional frames are encoded at step 624, the frame reconstructed at step 622 becomes the reference frame and the routine continues at step 605.

  Alternatively, instead of the encoder decoder system utilizing the dynamic information from the first frame segment, the encoder decoder uses the structural information from the first frame and uses a basis function to describe the second frame or Determine the best set of building blocks. Both the encoder and decoder determine these basis functions separately, so only the coefficients of the basis functions need to be transmitted.

(2. Encoder)
While the operation of the encoder has been generally described above, this is also an instruction that indicates the operation for some specific image examples as well as a detailed description of the specific steps of the encoding process.

(2.1 Reference frame transmission)
Referring to FIG. 7, the encoder receives a reference frame, in this case an image with the sun in the background and the car moving from left to right. A reference frame generally refers to a frame in which any other frame is described. In the first pass of the encoder cycle, the reference frame is generally a key frame. Alternatively, in subsequent passages, the reference frame may be a previously encoded non-key frame.

  FIG. 8 is a flow diagram illustrating the procedure by which the encoder first processes the key frame. In step 810, the encoder receives the frame shown in FIG. In step 820, the encoder encodes the frame. In step 830, the encoder transmits the encoded frame to the receiver (eg, to a decoder or storage medium for subsequent decoding). The encoder reconstructs the frame that was encoded in step 840.

(2.2 Segmentation)
Segmentation is the process by which a digital image is subdivided into components, ie, segments where each segment represents a region that is limited by abrupt changes in values in the image shown in FIG.

  Those skilled in the art of computer vision recognize that segmentation can be performed in a number of ways. For example, one such method is the so-called “watershed method”, which can be found at www. csu. edu. au / ci / vol3 / csc96f / csc96f. It is described in html. This segmentation technique and other segmentation techniques available in the present invention are known to those skilled in the art and need not be described in detail herein.

  Referring now to FIG. 9, in step 910, the encoder segments the reconstructed reference frame to determine image-specific structural features. Alternatively, in step 910, the encoder segments the original image frame for the same purpose. The encoder determines that the segments of FIG. 7 are car, rear wheel, front wheel, rear window, front window, road, sun, and background. Alternatively, in step 910, the encoder segments both the original frame and the reconstructed frame and determines the segmentation difference between the two frames. In this case, the encoder transmits this difference to the decoder as part of the motion related information. This difference is shown herein as segmentation enhancement.

  In step 920, the encoder orders the segments based on any predetermined criteria, representing segments 1001 through 1008, respectively, as shown in FIG.

  Segmentation allows the encoder to perform effective motion matching, Z ordering, motion prediction, and effective residual coding, as further described in this description.

(2.3 Dynamics information)
Once segmentation is complete, the encoder determines and encodes kinetic information regarding the progress for each frame. The dynamic information includes a description of motion related information and residual information. The motion related information can consist of motion data such as segments, Z-ordering information, segmentation enhancement, if necessary. Residual information consists of information about previously occluded regions and / or inaccurate matching and exposure of new information, and part of the segment evolution that is essentially not captured by motion.

(2.3.1 Matching and segment motion data)
The motion part of the dynamic information is determined through a process known as motion matching. Motion matching is a procedure for matching similar regions (often segments) from one frame to another. At each pixel in the digital image frame, the image is represented as a numerical value. Matching occurs when an area in one frame has a pixel value that is the same or sufficiently similar to an area in another frame.

  For example, a segment can be considered to match another segment in a different frame because the first segment is appropriately moved and placed on the second segment, and the average of the absolute values of the pixel value differences is calculated. This is a case where the average value is calculated and falls below a predetermined threshold value. The average absolute value of pixel value differences is often used because it provides a simple measure of similarity, but any other number of criteria is sufficient. Criteria that can be used to determine matching will be apparent to those skilled in the art and need no further mention.

  FIG. 11 shows an example of motion matching of a gray hot air balloon between the frame 1110 and the frame 1120. In frame 1110, there is a gray hot air balloon 1111, and in frame 1120, there is a white sphere 1122 next to the gray hot air balloon 1121. The gray hot air balloon 1121 is slightly smaller than the gray hot air balloon 1111 and is twisted. When the hot air balloon 1111 moves onto the white sphere 1122, the pixel value included in the white sphere 1122 in the frame 1120 is subtracted from the pixel value included in the gray hot air balloon 1121 in the frame 1110, and as a result, is not zero. The difference is obtained. Therefore, the gray hot air balloon and the white sphere do not match. However, when the gray hot air balloon 1110 moves onto the gray hot air balloon 1120, the gray hot air balloon 1121 in the frame 1120 is subtracted from the gray hot air balloon 1111 in the frame 1110. The result is mostly zero and close to zero. Thus, these two gray hot air balloons are considered matched.

(2.3.2 Grouping)
Consider related segments as a group so that the encoder only needs to transmit motion related information about that group (along with any additional refinements for individual segments, if necessary) Then, it is possible to reduce the motion related information transmitted to the decoder. For example, in the case of segment motion data, the encoder transmits a representative motion vector or characteristic motion vector (along with any motion vector offset) to the decoder so that the individual motion of each segment in the group is transmitted. Just represent it. The characteristic motion vector may be of virtually any type, for example a single base segment or an average characteristic motion vector for the entire group.

  Grouping is possible when there is previous dynamic information around the segment or when there is multi-scale information around the segment. Multiscale is described in Section 2.3.4 below. Without further limiting to this particular embodiment of the present invention, only motion vector grouping will be further described.

  Referring to FIG. 12, at step 1210, the encoder determines whether the first frame is a key frame (ie, is not described in relation to other frames). If the first frame is a key frame, the motion grouping routine groups the segments using multi-scaling information (if possible). If the first frame is not a key frame, some previous motion data available for the group segment is provided. Thus, if the first frame is not a key frame, at step 1220, a motion grouping routine, described below in section 2.3.2, is executed. However, using previous motion data does not prevent the use of multiscaling for further grouping.

  However, if the first frame is a key frame, at step 1230, the encoder determines whether there is multi-scale information available. If there is multiscale information available, then at step 1240, the multiscaling routine described below in section 2.3.4 is executed. If no multiscale information is available, at step 1250 the encoder does not perform segment grouping.

(2.3.2.1 Motion-based grouping)
Motion-based grouping occurs only when there is previous motion related information and the encoder can determine the association target segment. The decoder also groups the segments in the same way that the encoder does. Motion-based grouping begins at step 1310 in FIG. 13 where previous motion data for each segment is considered. In step 1320, segments that show similar motion vectors are grouped.

(2.3.2.2 Multi-scale grouping)
Multi-scaling grouping is an alternative to segment grouping using previous motion. Furthermore, multiscaling can be used in conjunction with motion grouping. Multiscaling is a process that generates a lower resolution version of an image. An exemplary process for creating multiple scales is through iterative application of a smoothing function. As a result of the generation of the lower resolution image, the resolution is reduced and only large, dominant features are visible. Thus, for example, if the resolution is low, the football seam is not visible, but the football itself is recognizable.

  An example of a multiscale process is shown below. Referring to FIG. 15, at step 1510, the encoder considers, for example, the sparsest image scale (ie, the lowest resolution) for the frame, and at step 1520 determines the segments that remain visible. For such sparse image scales, only the largest and most dominant features (usually joined as the outline of the main object) remain visible and non-normal (usually corresponding to the features that make up the main object) The dominant segment becomes unrecognizable. In step 1530, segments that are invisible at the sparsest scale and that together contain a given visible segment are associated with a group. This is because small and invisible segments often share relationships with large objects and tend to have similar dynamic information. Therefore, a sparser scale image display is considered to represent a finer scale cluster. In step 1540, a determination is made. If there are more visible segments, at step 1550 the encoder considers the next segment and proceeds to step 1530. If there are no more visible segments, the multi-scaling grouping process ends.

  Although the above exemplary embodiment used a sparse image scale, this of course follows a specific range of multiscaling used for a specific image. It should be apparent that one or more other scales may be utilized in other exemplary embodiments.

  The decoder performs grouping in the same or similar manner as the encoder does.

(2.3.3 Motion prediction)
Referring to FIG. 14, at step 1410, the encoder considers a segment. In step 1420, the encoder determines whether there is previous motion related information for the segment, so that the motion can be predicted. The decoder predicts the motion or group of segments in the same or similar manner as the encoder. If there is no previous motion related information, the encoder proceeds to step 1460 as follows.

  If there is previous motion related information, the encoder predicts the motion of the segment at step 1430 and compares the prediction result with the actual motion of the segment. The motion vector offset is initially calculated at step 1440 as the difference between the actual motion vector and the predicted motion vector. In step 1450, the encoder further represents the motion vector offset as a difference between the motion vector offset and the associated characteristic (or group) motion vector.

  In step 1460, the encoder determines whether there are more segments. If there are more segments, at step 1470, the encoder considers the next segment and proceeds to step 1420. If there are no more segments, the prediction routine ends.

(2.3.2.1.1 Motion related information encoding)
After grouping and prediction occurs, grouping and prediction can be leveraged to reduce the re-overhead of encoding most of the extracted motion related information. For example, segmentation augmentation can be described more efficiently by referring to groups instead of individual segments. In step 1330, the group motion vectors are obtained by calculating representative features of all motion vectors in the group. Thus, for each segment in the group, only the motion vector difference (ie, the difference between the segment's motion vector (if any) and the characteristic (or group) motion vector) is transmitted (step 1340). reference). An example of a characteristic motion vector is an average motion vector. Further improvements in motion vectors can be achieved using only motion prediction and the encoded motion offset for the predicted motion.

(2.3.4 Z-ordering)
Z-ordering refers to the relative depth position within the image frame that each image occupies. The encoder determines and transmits the Z-ordering information, so that the depth information contained within the structural information is preserved as the structural information changes from one frame to another.

(2.3.5 Coding of remainder)
The residual information consists of information in previously occluded areas and / or incorrect matching and new information appearance, part of the segment evolution that is not captured by the motion itself, and so on.

(2.3.5.1 Background remainder)
As shown in FIG. 16, when the segment moves, the area that has been concealed or obstructed until now becomes visible for the first time. In FIG. 16, as the vehicle moves, three regions become visible. These three areas are areas behind the vehicle, and two of the areas are areas behind the wheels. These three areas are marked as areas 1601 to 1603, respectively.

  Referring to FIG. 17, in step 1710, the encoder determines where a previously concealed image area has occurred. In step 1720, the encoder orders the regions using a predetermined ordering system. In step 1730, using the information corresponding to the region (s) surrounding the region, the encoder makes a mathematical prediction on the structure of the previously concealed region. The encoder also accurately recognizes the image exposed in the area. Thus, in step 1740, the encoder examines the region and compares the predicted image with the actual image to determine if the mathematical prediction was sufficient. If the prediction result is not close to the actual image, at step 1770, the encoder encodes the region or difference and, at step 1780, stores the encoded information with a flag indicating the encoding mechanism. If the prediction result is close to the actual image, in step 1745, the encoder stores a flag to that effect.

  In step 1750, the encoder determines whether there are any new unblocked regions. If there are still new blocked areas, the next area is considered and the routine proceeds to step 1760, otherwise the routine ends.

(2.3.5.2 Local remainder)
The local remainder information includes information from inaccurate matching and the appearance of new information. For example, in FIG. 18, the vehicle and the sun are smaller in the frame 1802 than in the frame 1801. The structure of the residual information depends on the degree of difference between the new segment and the previous segment, and can be a well-defined region, a set of regions, or a mottled shape. Ideally, different types of encoding methods are used depending on the type of local residue. Since the decoder recognizes the segment motion, it recognizes where many of the local residuals are located. The encoder uses the knowledge about the structure information of the decoder (eg, segment boundary positions that can be considered) to improve the efficiency of local residual coding.

  Referring to FIG. 19, in step 1910, the encoder determines the position of the local residue. In step 1920, the encoder orders the areas where local residuals have occurred using a predetermined ordering scheme. In step 1930, the encoder reviews the first local residue to determine the most efficient way to encode the local residue, and then in step 1940 encodes the local residue. In step 1950, the encoder stores the encoded remainder and a flag indicating the encoding mechanism. If at step 1960 there is still a local residue position, then at step 1970 the next local residue position is considered and the routine continues to step 1940. If there is no local residue position, the routine ends.

(2.3.6 Special instructions)
The encoder embeds commands and instructions for each segment in the bitstream as needed. Examples of these commands include (but are not limited to) obtaining a static web page, obtaining another video bitstream, waiting for text, etc.

  After determining the segment, the encoder can embed these commands at any point in the bitstream and use the contents that the encoder can determine. FIG. 20 is an example of points where commands are embedded in the data stream.

  Referring to FIG. 20, at step 2010, the encoder considers the first segment. In step 2020, the encoder transmits a special instruction flag. In step 2030, the encoder determines whether there is a special instruction for the segment. If there are special instructions for the segment, at step 2040 the instructions are transmitted to the decoder, and at step 2050 the encoder determines whether there are more segments. If there is no special instruction associated with the segment at step 1730, the encoder proceeds directly to step 2050. If there are more segments in step 2050, then in step 2060, the encoder considers the next segment in step 2060 and proceeds to step 2020, otherwise the routine ends.

(2.4 Transmission)
After determining and encoding the dynamic (motion and residual) information, a determination is made regarding the transmission of frame information. Referring to FIG. 21, if, in step 2110, the image can be reasonably reconstructed primarily from motion related information with assistance from residual information, in step 2190 the encoder performs dynamics for the frame. Transmit information. If it is not possible to reasonably reconstruct the image primarily from motion related information with assistance from the remainder information, the frame is encoded as a key frame and in step 2185 the dynamic information is discarded. .

(2.5 alternative)
Alternatively, instead of using dynamic information from the segment from the first frame, the encoder uses structural information such as information including segmentation from the first frame to create the best basic feature set. And build a block to order or draw the second frame. This process may be referred to as an adaptive coding method or an adaptive transform coding method, which creates an appropriate basic function set based on the encoder's knowledge of the decoder's capabilities, or It builds blocks based on structural information available to the decoder. Since both the encoder and the decoder determine these basic functions independently, only the coefficients of the basic functions need be transmitted.

(3. Decoder)
(3.1 Reception of reference frame (reception))
FIG. 22 shows the process by which the decoder receives the reference frame. The reference frame is generally a frame that serves as a reference when a frame generated after another is drawn. In step 2210, the decoder receives an encoded reference frame. In step 2220, the decoder reconstructs the encoded reference frame.

  In step 2230, the decoder receives the key frame flag. This flag indicates whether the next frame is a key frame or whether the next frame can be reconstructed from the kinetic information. If the next frame is a key frame, the decoder returns to step 2210 to receive the next frame. If the next frame is not a key frame, the routine ends.

(3.2 Segmentation)
As described above, segmentation is the process of subdividing a digital image into its component parts (ie, segments), where each segment is joined by a dramatic or abrupt change in value in the image. Indicates the area.

  Referring to FIG. 23, in step 2310, the decoder segments the reconstructed reference decoder to determine unique structural features of the image. For example, the decoder determines that the segments in FIG. 7 are vehicles, rear wheels, front wheels, rear windows, front windows, roads, sun, and background. In step 2320, the decoder orders the segments based on the same criteria used by the encoder and marks the segments 1001-1007 as shown in FIG.

(3.3 Motion related information)
After segmentation is achieved, the encoder receives motion related information for each segment. The motion related information tells the decoder the segment position in the new frame relative to the segment position in the previous frame.

  FIG. 24 shows a process for receiving motion related information. In step 2410, the decoder considers one segment. In step 2420, the decoder determines whether there is previous motion data for the segment. If there is no previous motion data for the segment, the decoder proceeds to step 2450. If there is previous motion data for the segment, the decoder predicts the motion of the segment at step 2430, receives a motion vector modification at step 2440, and then proceeds to step 2450. In step 2450, the decoder determines whether there are more segments. If there are other segments, the decoder considers the next segment in step 2460 and then proceeds to step 2420. Otherwise, the routine ends.

  Dynamic information can be reduced when segments with associated motion are grouped together and represented by a single motion vector. The kinetic information received by the decoder is multi-scaling if several elements (ie 1) the previous (reference) decoder is a key decoder or 2) if the previous (reference) decoder is not a key decoder It depends on whether information is available.

  Referring to FIG. 25, in step 2510, the decoder determines whether the reference frame is a key frame (ie, a frame that is not defined in relation to any other frame). If the reference frame is a key frame, there is no information related to the previous motion that is the potential grouping of the segment. However, when such information is available, the decoder attempts to use multiscale information as a segment grouping target. In step 2520, the decoder determines whether there is multiscale information available. If the reference frame is a key frame and there is multiscale information available to the decoder, then in step 2530, the decoder first uses the multiscale routine, as described above for the encoder, to bring together the related segments. Group. Then, in step 2540, the decoder receives the motion vector and the motion vector offset. Conversely, if there is no multiscale information available for the reference frame, in step 2550, a motion vector (without offset) is received by the decoder.

  However, if in step 2510 the decoder determines that the first frame is not a key frame, then in step 2560 the decoder executes a motion vector grouping routine as described below. Instead of this motion vector grouping routine or in addition to this motion vector grouping routine, the decoder can also use the multi-scale grouping described above.

  FIG. 26 shows a motion vector grouping routine. In step 2610, the decoder considers the previous motion vector for each segment. In step 2620, the decoder groups together segments having similar previous motion vectors. In step 2630, the decoder determines whether the group motion is predictable. If the group motion is unpredictable, at step 2680, the decoder receives the motion vector and offset (if any) and then proceeds to step 2660. If the group motion is predictable, the decoder predicts the group motion at step 2640, then receives the prediction correction at step 2650 and then proceeds to step 2660. In step 2660, the decoder determines whether there are other groups. If there are other groups, the decoder considers the next group in step 2670 and proceeds to step 2630. If there are no other groups, the routine ends.

(3.4 Residual part)
After receiving the motion related information, the decoder receives residual information. The remaining part is classified into two types (ie, background residual part and local residual part).

(3.4.1 Background remainder)
As shown in FIG. 16, when the vehicle moves, the area previously concealed or blocked becomes visible for the first time. The decoder knows the location of these areas and orders these areas using a predetermined ordering scheme. In FIG. 16, the three areas are not blocked, and in particular, the areas behind the vehicle and behind the two wheels are not blocked. These areas are marked as areas 1601-1603.

  Referring to FIG. 27, at step 2710, the decoder examines the background residual region and then orders the region at step 2720. In step 2730, the decoder performs a mathematical prediction on the structure of the first background residual region. In step 2740, the decoder receives a flag indicating how well the prediction is and correction is required. In step 2750, the decoder determines whether the prediction is sufficient. If the prediction is sufficient, the routine continues to step 2770. If the prediction is not sufficient, in step 2760, the decoder receives the encoded region and a flag indicating the encoding scheme, reconstructs if necessary, and then proceeds to step 2770. In step 2770, the decoder determines whether there are other background residual regions. If there are other background residual regions, the decoder considers the next region at step 2780 and proceeds to step 2730. Otherwise, the routine ends.

(3.4.2 Local remainder)
The residual information consists of information resulting from incorrect matching and the appearance of new information. In FIG. 18, the vehicle and the sun appear smaller in the frame 1802 than in the frame 1801. The structure of the remainder depends on the degree of difference between the new segment and the previous segment. The decoder knows that most of the local residue is exposed at the segment boundaries. It is possible to increase the efficiency of local residual coding, taking into account the decoder's knowledge regarding the structural information (eg, the position of segment boundaries) that the decoder has.

  Referring to FIG. 28, at step 2810, the decoder considers the first segment. In step 2820, the decoder receives a flag indicating the encoding method (if necessary) and receives the encoded local residual of the segment. In step 2830, the decoder determines whether there are more segments. If there are other segments, the decoder considers the next segment in step 2840 and then proceeds to step 2820. Otherwise, the routine ends.

(3.4 Z-ordering)
Z-ordering indicates the depth position of each segment in the image frame. The decoder uses the Z-ordering information to determine which segments are completely visible and which are partially or completely hidden.

(3.5 Restructuring)
Finally, the frame is reconstructed based on the determined motion related information and the remaining part.

(3.6 Special instructions and object-based operations)
In addition to structural information about the image, the decoder can receive and execute commands embedded in the bitstream and associated with various segments. If the encoder and decoder are synchronized and operate on the same reference frame, the encoder may not transmit structure information associated with the command. It is also possible to hold the embedded command in a paused state until a user-driven event (eg, mouse click) occurs.

  FIG. 29 illustrates a procedure for processing an embedded command according to one embodiment of the present invention. In step 2910, the decoder considers the first segment. In step 2920, the decoder receives a special instruction flag. In step 2930, the decoder determines whether there are any special instructions or commands associated with the segment. If there is a special instruction or command associated with the segment, the decoder receives the command (s) at step 2940 and then proceeds to step 2950. Otherwise, the decoder proceeds directly to step 2950 and determines whether there are more segments. If there are other segments, the decoder considers the next segment in step 2960 and then returns to step 2920. If there are no other segments, the routine ends.

  FIG. 30 is a flowchart illustrating a procedure for handling user-driven events according to one embodiment of the invention. In step 3010, the decoder determines whether a user-driven event has occurred. If a user driven event has occurred, in step 3020, the decoder determines which segment the user driven event referred to. Then, in step 3030, the associated command is executed. Next, in step 3040, the decoder determines whether an end sequence has occurred. If an end sequence occurs, the tool resumes at step 3010. Otherwise, the routine ends.

  If, at step 3010, the decoder determines that no user-driven event has occurred, the decoder proceeds directly to step 3040.

  Utilizing the decoder's ability to compute structure information such as segmentation, it is possible to significantly reduce the overhead that must be sent in the majority of the structure information along with special instructions that can be attached to the structure information.

  For example, objects or different features in an image represented by separate segments can be conveniently manipulated as separate entities. Such operations include (but are not limited to) (a) editing within a frame, (b) exporting to other images or applications, and (c) interactive operations based on user input. In a system that synchronizes the encoder and decoder, the manipulated object or feature can be immediately re-encoded and thereby re-introduced into the current video stream or some other video stream. In this manner, the technique of the present invention solves the problem of limitations due to the use of conventional video coding bits or pixels, and makes conventional video coding useful as a tool for modeling actual objects. Make things.

  Alternatively, the decoder determines the best combination of basic functions that can be used to render the second video frame after determining the structural information of the video frame. The decoder then receives the coefficients from the encoder and reconstructs the second image frame. Since both the encoder and the decoder independently create and order the same basic function from the available structural information, only the basic function coefficients need be transmitted. This is an adaptive coding or adaptive transform coding method.

(4.0 video format)
In the present invention disclosed in this specification, a novel video format for transmitting video data has also been described. This video format consists of dynamic information associated with the structure information of the image frame. Examples of the structure information include, but are not limited to, information related to motion, residual information, and special instructions.

  Alternatively, the new video format may consist of a sequence of coefficients derived from a combination of basic functions.

(5.0 Conclusion)
In the above section, the operation of the encoder and decoder has been mainly described using flowcharts. The description has been made to enable those skilled in the art to implement these encoders and decoders in virtually any computer-based environment. Such an implementation is not limited to a particular software and / or hardware environment. For example, such an implementation can be implemented on a general purpose computer as a whole software as a series of functional modules (eg, I / O modules, motion matching modules, residual modules, etc.) using virtually any programming language. Can be implemented. Alternatively, such an implementation can be implemented as whole hardware (eg, as a custom VLSI chip) to provide faster operation. Still other implementations may include virtually any software and hardware combination (determined by the particular speed, cost, and transmission needs of a particular operating environment).

  The foregoing descriptions are all illustrative of exemplary embodiments and applications of the invention, and related modifications, improvements, and changes resulting from these descriptions can be made without departing from the spirit and scope of the invention. It is clear to the contractor. Accordingly, the invention is not to be limited to the above disclosure, but is to be construed according to the claims that follow.

100 Encoder 300 Decoder 1001-1008 Segment 1110, 1120 Frame 1801, 1802 Frame

Claims (18)

A codec that encodes video information and decodes the video information, the video information including a plurality of frames, and the frame represents an image of the video information,
a) an input operable to receive the video information comprising a first frame and a second frame;
b) a segmenter operable to segment the first frame, wherein the segmentation of the first frame is an association of pixels and segments of the first frame based on pixel values or image content Represents the segmenter,
c) a kinetic information generator operable to generate kinetic information representative of a change in position of an image segment from the first frame to the second frame;
d) logic to encode the first frame to form a first encoded frame;
e) logic to encode the second frame to form a second encoded frame, wherein the second encoded frame includes at least a portion of the dynamic information; ,
An encoder comprising:
a) an input for receiving the first encoded frame and the second encoded frame;
b) logic to decode the first encoded frame to form a first reconstructed frame;
c) a segmenter operable to segment at least a portion of the first reconstructed frame to generate a plurality of segments;
d) using the segmentation generated by the segmenter of the decoder and the at least part of the kinetic information encoded in the second encoded frame to determine the second encoded frame Logic to decrypt to form a second reconstructed frame;
Comprising a decoder comprising
The segmenter is configured to form at least one segment from a group of segments smaller than the segment using multi-scale grouping, each of the smaller segments being invisible on a sparse scale, A codec that becomes visible when grouped.
An encoder that encodes video information, wherein the video information includes at least a plurality of frames, each frame representing an image of the video information,
An input unit for receiving video information including at least a first frame and a second frame;
Logic to encode the first frame to form a first encoded frame;
Logic for determining a first reconstructed frame, wherein the first reconstructed frame is a frame obtained from decoding the first encoded frame;
A segmenter for segmenting at least the first reconstructed frame to generate a plurality of segments, wherein the segmentation represents an association of pixels and segments of a frame based on at least pixel values or image content; and ,
A kinetic information generator for generating kinetic information representing a change in the position of a segment between the first reconstructed frame and the second frame;
Logic encoding the second frame to form a second encoded frame, the second encoded frame including at least a portion of the dynamic information; and An encoder comprising logic, wherein a frame is encoded so as to be reconstructable from the second encoded frame using the segmentation information generated by the decoder for the first reconstructed frame Because
The segmenter is configured to form at least one segment from a group of segments smaller than the segment using multi-scale grouping, each of the smaller segments being invisible on a sparse scale, An encoder that becomes visible when grouped. Difference logic encoding the second frame is further included in the logic, wherein the difference logic is a difference between the segmentation of the first reconstructed frame and the segmentation of the second frame. The encoder of claim 2, wherein the encoder is operable to use residual information comprising: A decoder for decoding video information, the video information including at least a plurality of frames, each frame representing an image of the video information;
An input for receiving a first encoded frame and a second encoded frame;
Logic to decode the first encoded frame to form a first reconstructed frame;
A segmenter for segmenting at least the first reconstructed frame to generate a plurality of segments;
Decoding the second encoded frame using the segmentation generated by the segmenter of the decoder and at least part of the dynamic information encoded in the second encoded frame; A decoder comprising logic to form a reconstructed frame of
The segmenter is configured to form at least one segment from a group of segments smaller than the segment using multi-scale grouping, each of the smaller segments being invisible on a sparse scale, Decoder that becomes visible when grouped. A method of encoding video information, wherein the video information includes a plurality of frames, each frame representing an image of the video information,
Obtaining a first frame of the plurality of frames;
Encoding the first frame to form an encoded first frame;
Reconstructing the first frame from the encoded first frame to generate a reconstructed first frame;
Obtaining segmentation information associated with the reconstructed first frame;
Using multi-scale grouping, the process of forming at least one segment from a group of smaller segments, each of which is invisible on a sparse scale, but is grouped And the process of becoming visible,
Obtaining a second frame of the plurality of frames;
Encoding the second frame;
Calculating dynamic information of the first frame and the second frame, wherein the dynamic information is associated with segments of the first frame and the second frame;
Generating encoded video information including at least a portion of the dynamic information, wherein the second frame uses the segmentation information for the reconstructed first frame, and Encoded to be reconstructable from the encoded second frame; and
Including methods. The method of claim 5, wherein the encoded video information includes at least one key frame encoded independently of other frames in the plurality of frames. The step of generating includes adaptively encoding the image content of the plurality of frames by adapting to the position of the image content relative to the segment boundary determined in the step of obtaining segmentation information. 5. The method according to 5. A method of decoding video information, wherein the video information includes at least a plurality of frames, each frame representing an image of the video information, and the plurality of frames at least a frame designated as a key frame. Including one,
Obtaining an encoded keyframe; and
Reconstructing a key frame from the encoded key frame;
Calculating segmentation information for the key frame from the reconstructed key frame, the segmentation information comprising a plurality of segments of the image of the key frame generated based on the image content of the key frame Related to the process,
Using multi-scale grouping, the process of forming at least one segment from a group of smaller segments, each of which is invisible on a sparse scale, but is grouped And the process of becoming visible,
Obtaining an encoded intermediate frame, the intermediate frame including kinetic information associated with a segment between the key frame and the intermediate frame;
Reconstructing an intermediate frame from the encoded intermediate frame using at least a portion of the dynamic information and at least a portion of the segmentation information.
An encoding method of video information,
Encoding a first frame of video information to form an encoded first frame, wherein the video information includes a plurality of frames, each frame representing an image of the video information; The process,
Reconstructing the encoded first frame to form a reconstructed first frame;
Segmenting the reconstructed first frame to generate a plurality of segments using multi-scale grouping to form at least one segment from a group of segments smaller than the segment, wherein Each of the smaller segments is invisible on a sparse scale, but becomes visible when grouped; and
Encoding the second frame with motion information representing at least a segmental position difference between the first frame and the second frame of the video information;
A step of incorporating into the encoded video information a command associated with one of the plurality of segments.
An encoding method of video information,
A process of encoding a first frame of video information, the video information including at least a plurality of frames, wherein each frame represents an image of the video information;
Reconstructing the encoded first frame to generate a reconstructed first frame;
Segmenting the reconstructed first frame to generate a plurality of segments using multi-scale grouping to form at least one segment from a group of segments smaller than the segment, wherein Each of the smaller segments is invisible on a sparse scale, but becomes visible when grouped; and
Encoding the second frame using a set of basis function coefficients indicating the image content of the second frame of the video information for the first frame, wherein the set of basis functions is Processes related to segmentation, and
A step of incorporating into the encoded video information a command associated with one of the plurality of segments. The codec of claim 1, wherein the encoder segmenter and the decoder segmenter are operable to generate the same segmentation for a given image frame. The encoder includes logic for generating segmentation enhancement information for the first frame, and the decoder is for use in generating at least a segmentation of the first reconstructed frame. The codec of claim 1 including logic to decode the segmentation enhancement information. The codec of claim 1, wherein the encoder segmenter and the decoder segmenter generate an ordered list of segments and the same ordered list for a given image frame. The codec of claim 1, wherein the encoder segmenter and the decoder segmenter classify segments and generate the same grouping for a given image frame. The dynamic information includes a group motion vector associated with a group of segments and at least one motion vector offset associated with a segment within the group, the at least one motion vector offset comprising the group The codec according to claim 1, wherein the codec represents the movement of the segment with respect to the movement of the segment. An encoding method of video information,
A process of encoding a first frame of video information, the video information including at least a plurality of frames, wherein each frame represents an image of the video information;
Reconstructing the encoded first frame to generate a reconstructed first frame;
Segmenting the reconstructed first frame to generate a plurality of segments;
Using multi-scale grouping, the process of forming at least one segment from a group of smaller segments, each of which is invisible on a sparse scale, but is grouped And the process of becoming visible,
Encoding the second frame using information representing at least a difference in position of image segments between the first frame and the second frame of the video information;
A step of incorporating into the encoded video information a command associated with one of the plurality of segments. The method of claim 16, wherein the information representing at least a segment position difference is based on at least one adaptive transformation of basis functions and dynamics information. An encoding method of video information,
A process of encoding a first frame of video information, the video information including at least a plurality of frames, each frame representing an image of the video information;
Reconstructing the encoded first frame to generate a reconstructed first frame;
Segmenting the reconstructed first frame to generate a plurality of segments;
Using multi-scale grouping, the process of forming at least one segment from a group of smaller segments, each of which is invisible on a sparse scale, but is grouped And the process of becoming visible,
Encoding the second frame using coefficients for a set of basis functions describing image content of a second frame of the video information for the first frame, the set of basis functions comprising segments The process related to
A step of incorporating into the encoded video information a command associated with one of the plurality of segments.

Images