Computer graphics processing and selective visual display system – Computer graphics processing – Three-dimension
Reexamination Certificate
1999-01-21
2004-02-24
Zimmerman, Mark (Department: 2671)
Computer graphics processing and selective visual display system
Computer graphics processing
Three-dimension
C348S423100, C348S403100, C348S722000, C348S416100
Reexamination Certificate
active
06697061
ABSTRACT:
The present invention relates to image compression. More particularly, this disclosure provides a compression system that re-uses as appropriate compressed data from a compressed input signal when forming a compressed output signal.
BACKGROUND
Conventional editing or other processing of film or video images is performed in the “spatial” domain, that is, upon actual images rather than upon a compressed representation of those images. Since the final product of such editing or processing is frequently an uncompressed signal (such as a typical “NTSC” television signal), such editing or processing can sometimes with today's digital editors and computers be accomplished in real-time. With increasing tendency toward high resolution pictures such as high definition television (“HDTV”), however, Internet, cable, television network and other service providers will likely all have to begin directly providing compressed signals as the final product of editing.
A conventional television distribution system
11
is illustrated using
FIG. 1
, which shows use of a satellite
13
, a digital receiving and processing system
15
, and a number of individual television subscribers
17
. The digital processing system decodes a satellite signal
21
(or alternatively, a compressed, stored signal) and provides a decoded signal
19
to a service provider
23
, for distribution via Internet, cable or another broadcasting network
25
. Conventionally, the service provider
23
will perform some edits on the decoded signal, such as to mix different signals or feeds together, provide reverse play of an input signal, insert a logo or provide other edits (such as color correction or blue matting). Examples of conventional editing include mixing different camera angles of a live sports event, as well as inserting television commercials into a signal. These and other types of editing are collectively represented by a reference box
27
in
FIG. 1
, and are also further illustrated in FIG.
2
.
In particular,
FIG. 2
shows a set of input images
31
which is to be edited to form a set of output images
33
. Two hypothetical edits are illustrated, including a first edit which combines five frames
35
of a first image sequence with five frames
37
of a second image sequence to produce the output images
33
. A second edit is also represented by a (hypothetical) logo
39
of a local television station “TF5” which is to be combined with the input images
31
such that the logo appears in the lower right hand corner of the output images
33
. To perform these edits, compressed input data
41
must first be processed by a de-compression engine
43
. Following editing, the output images
33
must then also be re-compressed by a compression engine
47
to produce compressed output data
49
. Both the compressed input and output data are seen to be in partially compressed MPEG format, with image frames encoded as “I,” “P,” or “B” frames as will be explained below. One of the most time intensive steps in this process is the compression of the output images
33
, which will be explained with reference to FIG.
3
.
In this regard, compression techniques generally rely on block-based (e.g., tile-based or object-based) encoding, which is introduced with reference to FIG.
3
. Well known compression techniques include “JPEG,” “MPEG,” “MPEG-2,” “MPEG-4,” “H.261,” and “H.263.”
FIG. 3
shows two image frames
51
and
53
. The second image frame
53
of
FIG. 3
is divided into a number of square tiles
55
, and it is desired to compress the second frame so that relatively less data is used for image representation. In typical image compression, each tile
65
will be separately compressed to remove either spatial redundancies within the same frame (the second frame
53
) or temporal redundancies between frames (e.g., by comparison to the first frame
51
). In this example, it is to be assumed that the second frame will be compressed only to remove temporal redundancies between different frames, but similar principles can be applied to reduce spatial redundancies within the same frame.
In performing compression, a digital editor or computer compares pixels in each tile in the second frame with image pixels found at or near an expected tile location
61
(e.g., the same position) within the first image frame
51
. This comparison is indicated by a reference tile
57
in the second image frame and an arrow
59
which points to the same tile location in the first image frame. The digital processing device sequentially compares pixels from the reference tile
57
with different pixel subsets of a fixed “search window”
63
to determine a “closest match.” The “closest match” in
FIG. 3
is indicated by a hatched square
65
, which is illustrated as slightly offset from position of the tile
61
. With the “closest match” having been found, the digital processing device calculates a motion vector
67
and a set of pixel difference values called “residuals.”
Once all tiles have been placed into motion vector and residual format, the motion vectors and residuals are then encoded in a compact manner, usually through “run-length coding,” “quantization” and “Huffman coding.” During later de-compression, for example, at a network, television station, editing facility, or at an end-viewer's computer or television, the second frame is completely re-calculated from an already-de-compressed first frame by re-constructing each tile using motion vectors and residuals. The various standards mentioned above generally operate in this manner, although some new standards call for subdividing images into variable size objects instead of tiles (the principles are, however, similar).
A compressed input signal is conventionally edited in the spatial domain only after an entire group of frames of the input signal have been completely de-compressed. Frames within the de-compressed group can then be edited for color, frame order such as for reverse play or splicing, or frame content (such as logo insertion). Once an edited signal is ready for output, the signal is then usually compressed anew, using a closest match search for each tile of images of the desired output signal. Typically, all images in a sequence, and all portions of all images affected by any edits, are de-compressed prior to editing. Thus, re-compression can be quite time intensive. For example, as much as seventy percent (70%) of resources used by a digital processing device to compress an image are applied to searching for the “closest matches” and associated motion vectors. Practically speaking, it is extremely difficult to compress these image sequences in real-time. Taking HDTV as an example, compressing many millions of bits per second is difficult even for today's multi-megahertz computers.
A need exists for a system that can more quickly compress edited signals, particularly those signals which have previously been compressed. Ideally, such a system would operate in a manner compatible with existing object-based and block-based standards, and would operate on spatial regions within an image, e.g., such that it can specially handle logo insertion and the like. Further still, such a system ideally should be implemented in software, so as to improve the speed at which existing machines process video and facilitate applications of real-time editing or compression. The present invention satisfies these needs and provides further, related advantages.
SUMMARY OF THE INVENTION
The present invention provides for quicker compression of an edited image by determining whether prior compression information (or data) for certain parts of the unedited image may be re-used. For example, by re-using motion vectors from the un-edited image data, the present invention provides for substantial savings in processor time and resources that would otherwise be occupied with motion search. Certain aspects of the present invention also provide for reduction of quantization errors in re-compressing an edited signal. With increasing use of high definition television (“HDTV”) and high resolu
Schuyler Marc P.
Wee Susie J.
Nguyen Kimbinh T.
Schuyler Marc P.
Zimmerman Mark
LandOfFree
Image compression featuring selective re-use of prior... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image compression featuring selective re-use of prior..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image compression featuring selective re-use of prior... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3330457