Pulse or digital communications – Bandwidth reduction or expansion – Television or motion video signal
Reexamination Certificate
1999-04-12
2002-04-09
Britton, Howard (Department: 2613)
Pulse or digital communications
Bandwidth reduction or expansion
Television or motion video signal
C348S699000, C375S240140
Reexamination Certificate
active
06370195
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method and apparatus for detecting motion and, more particularly, to a method and apparatus for detecting motion of a picture occurring among different frames of image, i.e., occurring with a lapse of time. Especially, the invention relates to a method and apparatus which is for use with a video encoder for encoding motion images to make motion compensation.
ITU-T (International Telecommunication Union Tele-communication Standardization Sector) recommends H.261 and H.262 as methods for encoding, storing, and transmitting image signals. ISO (International Organization for Standardization) recommends MPEG-1(11172-2) and MPEG-2 (13818-2). These methods adopt interframe prediction for motion compensation in encoding image signals. It is known that video signals produce highly redundant signals. Motion compensation interframe prediction is a technique for removing such redundancy. In the technique of motion compensation interframe prediction, each image frame to be compressed is divided into plural blocks (hereinafter referred to as target compressing blocks) that will be compressed. The target compressing blocks to be compressed are handled separately. In particular, an image frame processed prior to one target compressing block to be compressed is referred to as a reference image frame. A search area in which motion is detected is set close to the target compressing block within the reference image frame. Plural blocks (hereinafter referred to as reference image blocks) having the same size as the target compressing blocks are extracted from the search area. These reference image blocks are searched for a reference image block closest to the target compressing blocks.
Then, the difference between the target compressing block and the found reference image block is encoded, thus producing a compressed code sequence about the target compressing block. Motion detection is processing to search for this closest reference image block. A motion vector is a displacement on the viewing screen between each target compressing block and each corresponding reference image block found. Usually, such motion detection is performed by a video encoder.
Motion detection is introduced by various papers, literature, patent specifications, and so on. Most common procedure starts with calculating the absolute values of the differences in pixel between the target compressing block (also referred to as the target block) and every reference image block within the reference image frame. The sum of the absolute values of the differences is calculated for each reference image block. A reference image block providing the least sum is found. The displacement on the viewing screen between the detected reference image block and the target block is expressed in terms of horizontal and vertical displacement components, thus producing a motion vector. This procedure is known as the full-search procedure.
In the full-search procedure, the absolute values of the differences between all pixels contained in the target block and all pixels contained in all reference blocks within a reference image frame are calculated. The sum of the absolute values of the differences needs to be calculated for each reference block. Therefore, the amount of calculation is exorbitant. Hence, high-speed computational speed is necessary.
A sub-sampling procedure as shown in
FIGS. 14-16
is considered as a method of detecting motion with a reduced amount of calculation. In this method, a target block
100
whose motion is to be detected within an encoded image frame is sub-sampled both horizontally and vertically at intervals of one pixel. Thus, a sub-sampled target block
101
is obtained. A search area
201
in which motion is detected is set within a reference image frame
200
shown in FIG.
15
. The differences between the pixels of all the reference blocks in the search area
201
within the frame
200
and sample pixels are taken. Using these differences, the degrees of approximation of images are found. A reference image block having the highest degree of approximation is found. The displacement on the viewing screen between this reference image block and the target block is represented as a motion vector.
A multi-stage search method for finding a motion vector is also conceivable. In particular, the sub-sampling procedure is effected not for all reference image blocks within a reference image frame. Reference image frames are taken horizontally and vertically as image frames at intervals of 2 pixels. That is, the number of reference image blocks within each reference image frame is reduced to one-fourth. The degrees of similarity of all the reference blocks are found. A reference image block having the highest degree of similarity is detected. The displacement on the viewing screen between the detected reference image block and the target block is represented by horizontal and vertical displacement components, thus producing a motion vector.
SUMMARY OF THE INVENTION
The aforementioned full-search method needs a large amount of calculation and so it is difficult to widen the search or to detect motion on a real-time basis. In the sub-sampling procedure, the number of pixels within one motion detection block is reduced to one-fourth, for example, and therefore, the amount of calculation can be reduced approximately to one-fourth. However, if one takes notice of reading of a reference image block within a search area, it is necessary to read out every pixel within the search area. Where a memory is attached to the outside of a motion-detecting LSI or processor and reference image frames are stored in this memory, if the memory has a limited bandwidth (transfer efficiency), a great problem takes place. That is, every pixel within the search area is read out. Consequently, a large amount of data needs to be transferred between the memory and the motion-detecting LSI.
In the full-search method, the amount of data transferred between the motion-detecting LSI and the memory is reduced. However, it is necessary to control the motion detection operation in stepwise fashion. This complicates the circuitry and control operation. As a result, a long time is required to detect motion.
It is a first object of the present invention to provide a method and apparatus for detecting motion at an improved rate while preventing deterioration of the motion detection efficiency.
It is a second object of the invention to provide a method and apparatus for transmitting data between a memory and a motion-detecting portion at an improved efficiency by reducing the amount of data read from a search area within a reference image frame.
Other objects and features of the invention will be understood from the following description and accompanying drawings.
A motion detection method for achieving the above-described objects of the present invention starts with dividing a target block into plural blocks(hereinafter referred to as divided target blocks) at different pixel positions. Each of the divided target blocks is allocated for one of motion vectors representing motions of the target block. A reference image block is extracted from a reference area within a reference image frame. Pixel data are extracted from each divided target block. The degrees of similarity of the divided target blocks to the reference image block is obtained by calculating the degrees of similarity between each of the divided target blocks and one reference image block which is commonly used for these divided target blocks. A divided target block having the highest degree of similarity is found. The vector indicated by allocated for the block having the highest degree of similarity is detected as an optimum motion vector.
The principle and the operation of the present invention are described by referring to
FIGS. 4-6
. As shown in
FIG. 4
, a target block
100
which is within an encoded image frame and whose motion should be detected is divided into four (4) divided target block units
101
-
104
that are in different pixel
Hatae Hiroshi
Iwata Kenichi
Watanabe Hiromi
LandOfFree
Method and apparatus for detecting motion does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for detecting motion, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for detecting motion will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2902025