Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-09-07
2003-09-16
Kelley, Chris (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
Reexamination Certificate
active
06621867
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to digital image processing and, more specifically, to the detection of edges in images, e.g., differentially encoded images.
BACKGROUND OF THE INVENTION
As a result of image processing, edges are often introduced into images. Letterboxing of movies for display on television is an example of one form of image processing that introduces horizontal edges into images. In the case of letterboxing, black regions are added to the lower and upper portions of an image.
An example of letter boxing is shown in FIG.
1
. As illustrated, a letterbox image
10
comprises upper and lower black borders
12
,
12
′ and a central image region
14
. Horizontal edges
13
,
13
′ result from the transition from the black border regions
12
,
12
′ to the center image region
14
. The horizontal edges
13
,
13
′ resulting from letter boxing are often strong edges due to the black nature of the border regions
12
,
12
′.
Various image processing operations require information about the presence of edges, such as those resulting from letterboxing, within an image.
One known edge detection technique, referred to as the gradient method is described in
Digital Image Processing
, by William K. Pratt (1991). The gradient method involves the computation of the first derivative of the pixel data. This usually involves calculating pixel differences from unencoded pixel values. This can involve a considerable number of processing operations.
Accordingly, the known gradient method edge detection technique suffers from the disadvantage of requiring a substantial amount of image processing to detect edges in an image. Furthermore, the known edge detection technique normally involves the use of unencoded, e.g., uncompressed, image data. Accordingly, in order to detect an edge in an encoded image, the image normally needs to be completely decoded prior to detecting edges within the image.
For data storage and transmission purposes, images are normally encoded, e.g., compressed, to reduce the amount of data used to represent an image. Prior to use, e.g., subsequent image processing and/or display, encoded images are normally decoded.
Differential coding of discrete cosine transform coefficients (DCTs) is used in a wide variety of image encoding schemes including, e.g., the international video standard. MPEG-2 (ISO/IEC 13818-2). MPEG-2 has been used as the basis for several commercial applications including digital video disks (DVD) and digital broadcast television.
In accordance with MPEG-2, pixels are normally grouped into blocks for encoding purposes. The term block is used in the present application to refer to luminance (luma) blocks. Each block corresponds to 16 pixels. There are four blocks per macroblock.
FIG. 2
illustrates the relationship of the four luma blocks (
0
,
1
,
2
,
3
) of a macroblock
20
.
In MPEG-2, the slice syntax element is used to encapsulate data used to decode individual macroblocks. Multiple slices may exist in a given macroblock row of an image, however a slice cannot span across rows of macroblocks. The slice syntax element also carries the slice_vertical_position which provides information about the vertical position of the macroblock data. The vertical position is measured in macroblock units from the top of the picture. MPEG-2 requires that all the slices that may be present in a given row of macroblocks carry the same slice_vertical_position value. The value of the slice_vertical_position may be used to determine when the macroblock data corresponding to a given row of macroblocks has been fully observed. This is done by noting when the value of the slice_vertical_position increases by one unit.
FIG. 3
illustrates an image segment
30
corresponding to an upper portion of the image
10
. In
FIG. 3
, a horizontal row of macroblocks corresponding to, e.g., a slice
31
, is shown passing through the horizontal edge
13
.
In the slice
31
, first and second blocks of each macroblock have similar luminance characteristics because they both correspond to the black border region
12
. In addition, the third and fourth blocks of each macroblock have similar luminance characteristics because they both correspond to the center image region
14
. However, it can be seen that, for each macroblock
32
,
33
,
34
,
35
,
36
, the upper two blocks (blocks
0
,
1
) will have a DC level that is noticeably different from that of the lower two blocks (blocks
2
,
3
) since there is a large, difference in the luminance characteristics of the upper and lower blocks. It is this difference in luminance characteristics which is responsible for the presence of the horizontal edge
13
.
As part of the MPEG-2 encoding process, discrete cosine transform encoding is performed on image data to produce a plurality of discrete cosine transform (DCT) coefficients. In order to reduce the amount of data used to represent the encoded images, DC DCT coefficients are frequently represented as differential values, i.e., values which indicate the difference from a preceding DC DCT coefficient value. Such a differential value is described in the MPEG-2 specification as a dc_dct_differential.
Thus, in MPEG-2, the DC components of blocks of intra-coded macroblocks are encoded differentially across a slice. This takes advantage of the fact that the DC level of a picture does not ordinarily exhibit sharp changes across small regions. By differentially encoding the DC coefficients, it is possible, in the mean, to obtain a certain degree of data compression.
FIG. 4
shows how MPEG-2 differential encoding proceeds throughout the blocks
32
,
33
in the slice
31
of macroblocks. For the very first macroblock
32
in a slice, the DCT DC predictors are reset. Thus, the first block, block
0
, is differentially coded using a preceding DC DCT value of 0 to generate the dc_dct_differential. The effect of coding the first block of a slice in this manner is the same as performing non-differential coding since the coding does not use an actual preceding DC DCT coefficient value. By restarting the differential coding with the first block of each slice, the propagation of errors is reduced at the expense of having to explicitly encode the first DC DCT coefficient of a slice. After the first block of the first macroblock of a slice, the DCT DC coefficients are differentially encoded using a preceding DC DCT coefficient in the slice as a reference value.
Since the macroblock
32
is the first macroblock in slice
31
, the dc_dct_differential for block
0
will correspond to the actual DC DCT value for this block. The DC DCT for block
1
of the first macroblock
32
is differentially coded using the DC DCT value of block
0
as the predictor. Considering the edge shown in
FIG. 1
there is uniformity between the DC DCT values of blocks
0
and
1
so the dc_dct_differential for block
1
will be small.
In the case of block
2
of macroblock
32
, the DC DCT will be differentially coded using the DC DCT value of block
1
as the predictor. When there is uniformity between the DC value of the blocks, the dc_dct_differential is expected to be small. However, a large dc_dct_differential is expected when a horizontal edge is present.
Considering
FIG. 3
as an example, it will be seen that when a horizontal edge is present there is a large difference in the DC levels of blocks
1
and
2
due to the horizontal edge
13
. This results in a dc_dct_differential for block
2
which will be large compared to that for block
1
.
When differentially coding block
3
, the DC DCT value of block
2
of the same macroblock is used as the predictor. In the
FIG. 3
example, the differential for block
3
of the first macroblock
32
will be small. This is because the differences in the DC levels of blocks
2
and
3
of macroblock
32
are small or non-existent. After coding the DC DCT values for block
3
, encoding of the first macroblock is finished.
To differentially encode the first block of a macroblock, which is not the first macroblock of a slice, the
Lane Frank Anton
Sazzad Sharif Mohammad
Hitachi America, Ltd
Kelley Chris
Senfi Behrooz
Straub Michael P.
Straub & Pokotylo
LandOfFree
Methods and apparatus for detecting edges within encoded images does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for detecting edges within encoded images, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for detecting edges within encoded images will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3096850