Video motion vector detection including rotation and/or zoom vector generation

[0002] This invention relates to video compression and, more particularly, to the detection and generation of motion vectors which describe the movement of video picture information from one video frame to another, namely rotational and zoom movement.

[0003] The transmission and recording of video information, such as television signals, in digital form generally requires a large amount of digital information to assure the accurate reproduction of high quality video pictures. As an example, if each video frame of picture information is digitized, approximately 250 Mbps are needed. With the advent of high definition television (HDTV), the amount of information needed to reproduce an HDTV picture is significantly increased. In addition, proposed digital standards for high fidelity sound reproduction are expected to be satisfied by still additional digital data, resulting in an anticipated transmission (or data transfer) rate in a digital video system to be on the order of about 1000 Mbps.

[0004] The foregoing data requirements have made it impractical to digitize, on a frame-by-frame basis, all of the video information included in each frame of a video picture. Moreover, and recognizing that the video information contained in one video frame of a particular scene is quite similar to (and in many cases almost identical to) the video information included in an immediately preceding frame, it is appreciated that the complete digitization of a video frame consists, to a large degree, of redundant data. This redundancy suggests that a substantial savings in bandwidth and data transfer rate can be realized by relying upon data compression techniques. Two types of video compression processing have been proposed heretofore: intraframe compression, wherein the spatial redundancy within a given frame of video information can be exploited to reduce the amount of digital data needed to represent that frame; and interframe compression wherein the redundancy of information from one frame to the next can be exploited so that only digital data representing changes need be transmitted.

[0005] Various mathematical models have been proposed for eliminating spatial redundancy in a given frame. One technique which has proved to be quite successful and has been implemented by digital processing relies upon orthogonal transformation of the video information included in a video frame; such as discrete cosine transformation (DCT). As is known to those of ordinary skill in the art, DCT processing is carried out by segmenting a video frame of digitized video information, such as pixels, into blocks formed of n×n arrays of pixels and then taking the discrete cosine transformation of each block. DCT coefficients of different frequency components are produced and only those coefficients which exceed a threshold level are processed further. This results in a significant reduction of data needed to represent a video frame, with only a small sacrifice in picture quality that is not easily perceived by a viewer. Further compression is achieved by quantizing these DCT coefficients and then relying upon variable length encoding, such as Huffman coding, for still further data reduction or compression. As a result, the amount of data needed to represent a frame of video information, such as an HDTV frame, is significantly reduced.

[0006] Interframe encoding refers to the process by which only those changes in a new frame (referred to herein as a “present frame”) relative to a preceding frame, such as the immediately preceding frame, are transmitted or recorded. If there is virtually no change between frames, only minimal data is needed to describe the present frame. However, if there is little resemblance of the new frame to the preceding frame, as will be the case when the first frame of a new scene is present, then the amount of data which may be needed to describe the present frame is so large that it would be more efficient simply to rely upon intraframe encoding to represent the present frame. Thus, in a practical transmission or recording system, intraframe and interframe encoding are used in an adaptive manner to achieve optimum reduction or compression of the digital data needed to represent a video frame. The frame-to-frame changes which are transmitted or recorded in interframe encoding generally represent localized movement in the video picture of the preceding frame which results in the present frame and such changes are referred to as motion vectors. As is understood, the addition of motion vectors to the digital data which describes a preceding video frame results in the present frame. The addition of motion vectors to a preceding video frame also is known as motion compensation or motion prediction. That is, a present frame may be “predicted” simply by adding motion vectors to the data which describes the preceding frame.

[0007] Conventional motion compensation operates by detecting rectilinear motion of a present frame relative to a preceding frame. That is, changes in the vertical and horizontal directions of, for example, the blocks which constitute a video frame are detected and used to predict the corresponding blocks of the present frame. However, such rectilinear motion compensation assumes that the objects in a preceding frame may move only in x and y directions. On the contrary, it has been found that the objects in a preceding frame may undergo rotational movement from that frame to the present frame. The generation of rectilinear motion vectors, that is, rectilinear motion compensation, often does not provide an accurate or acceptable indication of such rotational movement. Hence, the use of rectilinear motion vectors to describe rotational movement may not be satisfactory.

[0008] Another drawback in limiting motion compensation to rectilinear motion vectors is the inability to account for common camera techniques which often are used, such as zoom-in and zoom-out. When a zooming factor that is positive or greater than unity is used, that is, when a cameraman zooms in on a subject, the effective size of a given block in the present frame appears to increase relative to that same block in the preceding frame. Conversely, when the zooming factor is negative or less than unity, that is, when the cameraman zooms out on a subject, the apparent size of a given block in the present frame relative to that same block in the preceding frame seems to decrease. Similarly, the movement of a subject toward or away from the camera gives rise to a zooming effect. Rectilinear motion compensation does not account for this zooming factor. Hence, conventional two-dimensional motion compensation often does not provide a satisfactory reconstruction of a video picture which was produced with relatively simple video camera techniques, such as zoom-in or zoom-out.

[0009] Therefore, it is an object of the present invention to provide an improved technique for video compression which may be used to represent both conventional and HDTV video pictures.

[0010] Another object of this invention is to provide an improved interframe encoding technique.

[0011] A further object of this invention is to provide motion compensation which considers, in addition to rectilinear movement, rotational and zoom-in/zoom-out movement.

[0012] An additional object of this invention is to provide four-dimensional video motion compensation.

[0013] Yet another object of this invention is to provide a technique which detects a rotational motion vector from one video frame to the next.

[0014] Still another object of this invention is to provide a technique which detects a zoom vector from one video frame to the next.

[0015] Various other objects, advantages and features of the present invention will become readily apparent from the ensuing detailed description, and the novel features will be particularly pointed out in the appended claims.

[0016] In accordance with this invention, a technique is provided for sensing rotation of video information between adjacent video frames, for example, from a previous video frame to a present frame. Rotation vector data is generated to represent the magnitude of the sensed rotation, and this rotation vector data is combined with other motion vector data, such as linear motion vectors which detect linear motion of the two frames.

[0017] As another aspect of this invention, zoom-in and zoom-out of video information from a previous frame to a present frame is detected, and zoom vector data representing the magnitude of the sensed zoom is generated and combined with the aforementioned motion vector data.

[0018] In the preferred embodiment, both rotation and zoom vector data are generated. This is achieved by segmenting a present frame of video data into plural blocks, establishing a search block which is displaced over a constrained portion of stored video data (which represents a preceding frame) in a rectilinear, rotational and zoom-in/zoom-out directions to search for a block of stored video data that most resembles a selected block segmented from the present frame. Motion vectors x, y, r and z corresponding to the rectilinear, rotational and zoom-in/zoom-out position of the search block that most resembles the selected block are produced. The rotational vector r thus represents the rotation of the selected block relative to its corresponding block in the preceding frame; and the zoom vector z represents the zoom-in or zoom-out of the selected block relative to its corresponding block in the preceding frame.

[0019] When the present invention is used in a video compression system, the four-dimensional motion vectors x, y, r and z are added to differential pulse code modulated (DPCM) data (or residual data) which represents the preceding frame (more accurately, the DPCM data represents the residual frame). The video compression system also includes an intraframe encoder which comprises an intraframe spatial redundancy processor, such as an orthogonal transform processor, for example, a DCT processor, for establishing the compressed data to represent an initial video frame.

[0020] As an aspect of the present invention, the displacement of a search block for the purpose of producing the motion vectors x, y, r and z is produced by establishing coordinates x_m, y_n, r_Θ and z_p, wherein m and n are variable integers, Θ is a variable angle and p is a variable zoom factor. When preset values of m, n, Θ and p are used, the positioning of a pixel in the search block may not coincide with a pixel in the stored video frame; and in that event, the value of the pixel in the search block is interpolated from adjacent pixels in the stored frame. Then, the differences between the interpolated pixels in the search block and the corresponding pixels in the selected block are determined in order to find a “match,” from which the motion vectors are produced.

[0021] The following detailed description, given by way of example, will best be understood in conjunction with the accompanying drawings in which:

[0022] FIG. 1 is a block diagram of a video compression system which incorporates the present invention;

[0023] FIGS. 2A-2C are schematic representations of the manner in which the blocks of a preceding frame may be rectilinearly moved to reconstitute the blocks of the present frame;

[0024] FIGS. 3A-3C are schematic representations of the manner in which the blocks of a preceding frame may be both rectilinearly and rotationally moved to reconstitute the blocks of the present frame;

[0025] FIGS. 4A-4D are schematic representations of the manner in which a block in the preceding frame may be changed by a zoom factor into a block of the present frame;

[0026] FIGS. 5A-5C are schematic representations of the manner in which the blocks of a preceding frame may be moved rectilinearly, rotationally and by a zoom factor to reconstitute the blocks of a present frame;

[0027] FIGS. 6-15 are schematic representations of the manner in which a search block is established from the pixels included in a preceding frame and is displaced rectilinearly, rotationally and by a zoom factor to provide a match with a given block of the present frame;

[0028] FIG. 16 is a schematic representation of the rotation of a pixel in a block of the present frame relative to that same pixel in the corresponding block of the preceding frame;

[0029] FIG. 17 is a schematic representation of the change of a pixel in a block of the present frame relative to that same pixel in the corresponding block of the preceding frame resulting from a zoom-in operation;

[0030] FIG. 18 is a schematic representation of the manner in which a pixel in the search block is interpolated from pixels in a preceding frame; and

[0031] FIGS. 19A-19B comprise a flow chart representing the manner in which four-dimensional motion vectors are produced in accordance with the present invention.

[0032] Turning now to FIG. 1, there is illustrated a block diagram of one embodiment of a video compression system which incorporates intraframe data compression and interframe data compression, the latter including means for generating motion vectors which represent rectilinear (or x, y), rotational (or r) and zoom (or z) motion of picture information from one frame to the next. The present invention is directed to detecting rotational and zoom motion and generating motion vectors representative thereof. As will be appreciated from the following discussion, the present invention thus provides four-dimensional motion vector information to characterize frame-to-frame motion of picture information in the x, y, r and z directions.

[0033] The block diagram shown in FIG. 1 is adapted to receive and process digitized color video signals which are supplied thereto as digital luminance and digital color components Y, U and V, derived from analog color components R, G, B in a manner known to those of ordinary skill in the art. These digitized video components Y, U, V are preliminarily processed in a preprocessor 101 for initial data reduction, as is also known, and then combined. As seen in FIG. 1, this preprocessor supplies digitized video information to the data compression apparatus, which video information typically consists of picture elements, or pixels, included in those lines of a frame interval which contain useful, viewable picture information.

[0034] The data compression apparatus which incorporates the present invention is comprised of segmenting modules 102 and 105, an orthogonal transform circuit 104, a frame store 110, a motion compensator 112 and a motion vector detector 114. Segmenting module 102 is coupled to preprocessor 101 and is adapted to receive the digitized video pixels included in a frame interval and to segment, or divide, those pixels into a number of blocks, each block being formed as an n×n array of pixels. In one embodiment, n=8, but other values of n may be used, as desired. Also, each block formed by segmenting circuit 102 may be comprised of an n×m array, wherein n≠m. The preprocessor also is coupled to orthogonal transform circuit 104 by way of a difference circuit 103 and segmenting module 105 which segments the pixels into blocks formed of an 8×8 array of pixels, as is known. Segmenting module 102 is coupled to motion vector detector 114.

[0035] Orthogonal transform circuit 104 is adapted to carry out an orthogonal transform operation on each block of pixels supplied thereto from segmenting circuit 105 and thereby reduce the quantity of data needed to represent the video information included in that block, orthogonal transform circuits are well known to those of ordinary skill in the art and in the preferred embodiment, circuit 104 comprises a discrete cosine transform (DCT) circuit. The operation of DCT circuit 104 forms no part of the present invention per se; and the advantages and operation of this circuit are well documented and known to those of ordinary skill in the art. The DCT coefficients produced by the DCT circuit are supplied to an encoder 106 and are added to a motion compensated frame derived from motion compensator 112 (as will be described) for storage in frame store 110 by way of an inverse DCT circuit 108. Encoder 106 is adapted to encode the DCT coefficients in a conventional data compression code, such as a variable length code, a run length code, or the like. One example of such a run length code implemented by encoder 106 is the well-known Huffman code. The resultant data-compressed encoded data produced by encoder 106 is supplied as an output signal for recording, transmission or further processing.

[0036] Although not shown, a quantizing circuit may be coupled to the output of DCT circuit 104 for further data compression; and this introduces noise such that if the original video data is recovered therefrom, the recovered video data would differ from the video data subjected to DCT transformation. Inverse DCT circuit 108 is adapted to operate in a complementary manner to DCT circuit 104 and serves to recover the original pixel data that had been data compressed by the DCT circuit, but with this error. The recovered pixel data is referred to as residual frame data and is summed in an adder 109 with motion compensated frame data produced by motion compensator 112, to be described. The summed output represents the frame of pixel data supplied by preprocessor 101 and is stored in frame store 110 whose capacity is at least sufficient to store a complete frame of video information. It will be appreciated, then, that the pixels stored in frame store 110 are the pixels which comprised the preceding frame interval that had been supplied by preprocessor 101 to the illustrated video compression apparatus. Thus, when a present frame of video information is supplied to segmenting module 102, the preceding frame of video information is stored in frame store 110. The output of the frame store is coupled to motion compensator 112 and to motion detector 114.

[0037] The motion detector includes the present invention and is adapted to detect motion in the picture information of the present frame relative to the picture information of the preceding frame. As will be described in greater detail below, motion vector detector 114 functions to detect linear (also referred to as rectilinear) motion in the x and y directions, rotational motion and zoom-in/zoom-out motion. In particular, a given block in the present frame, as supplied to the motion vector detector by segmenting circuit 102′ is compared to that same block in the preceding frame, as supplied by frame store 110, to sense whether the block in the present frame has moved from its position in the preceding frame rectilinearly, rotationally and/or by a zoom factor. That is, the motion vector detector functions to detect four-dimensional motion in the x, y, r and z directions. Motion vector data representing the magnitude and direction of such four-dimensional motion is coupled to encoder 106 whereat it is encoded, multiplexed with and transmitted (or recorded) with the encoded DCT coefficients. It will be appreciated by those of ordinary skill in the art that the combination of such motion vector data and DCT coefficient data (or residual frame data) provides sufficient information from which the original video information in a frame interval can be reconstructed and displayed as a high quality video picture.

[0038] Motion vector detector 114 also is coupled to motion compensator 112 which functions to adjust the blocks in a preceding frame by the motion which such blocks underwent to result in the present frame, thus predicting the positioning of such blocks in the present frame. The motion compensator thus may be thought of as producing a predicted frame of video information; and this predicted frame is coupled to difference circuit 103 for comparison with the actual, present frame supplied thereto from multiplexer 101 by way of segmenting circuit 102. The output of the difference circuit thus represents the actual differences between the predicted frame and the actual frame, and such differences are subjected to DCT transformation and then are encoded for transmission or recording. These differences (which constitute the residual frame) plus the motion-compensated frame also are used to update the video information stored in frame store 110, thus enabling the frame store to store a reasonably accurate representation of the frame which had just been supplied to the video compression apparatus. It will be appreciated that, if there is little or no motion from one frame to the next, the amount of data needed to update frame store 110 is minimal and, moreover, motion vector detector 114 detects little or no motion.

[0039] As is conventional, since the first frame of a new video scene generally bears little resemblance to the video information stored in frame store 110, it is typical to encode this first frame without regard to the preceding frame and to store this first frame in frame store 110 as a base to which succeeding frames are compared. That is, this first frame is encoded in what generally is referred to as intraframe encoding and subsequent frames are compared thereto such that only the differences therebetween are encoded in what has been referred to as interframe coding.

[0040] Although the operation of the video compression apparatus shown in FIG. 1 should be readily apparent from the foregoing discussion it will, nevertheless, be briefly described. Let it be assumed that the first frame of a new video scene is supplied from preprocessor 101 to segmenting module 102. It will be appreciated that this first scene can be detected readily by, for example, sensing the magnitude of the motion vectors produced by motion vector detector 114. This present frame of video information also is segmented by segmenting module 105 and is subjected to discrete cosine transformation by DCT circuit 104, encoded in data compression format by encoder 106 and added to the motion compensated frame previously stored in frame store 110 (for this first scene it is assumed that there is no stored, previous frame) and then stored in the frame store.

[0041] When the next frame of video information is received, rectilinear, rotational and zoom motion in this frame relative to the preceding frame stored in frame store 110 is detected by motion vector detector 114. Motion vector data produced by the motion vector detector is supplied to encoder 106 together with DCT coefficients representing the residual frame, as is produced by DCT circuit 104. The residual frame together with the motion vectors are encoded and transmitted or recorded, as the case may be.

[0042] The motion vectors produced by the motion vector detector are supplied to motion compensator 112 which uses these motion vectors to modify the preceding frame of video information that had been stored in frame store 110. The motion-compensated preceding frame, as produced by motion compensator 112, thus corresponds to a predicted version of the present frame that had been supplied to segmenting module 102. Difference circuit 103 senses the differences between the actual present frame and the predicted frame; and it is these differences, or residual frame, which are subjected to DCT transformation by DCT circuit 104. The DCT coefficients produced by the DCT circuit are encoded by encoder 106 and, with the encoded motion vector data, result in data compression of the video information supplied to the video compression apparatus. The DCT coefficients also are subjected to an inverse operation by inverse DCT circuit 108, thereby recovering the residual frame pixels which were included in the frame that had just been subjected to video compression. These recovered pixels are added to the motion compensated, or predicted frame in summing circuit 109, and are stored in frame store 110 as the preceding frame. The foregoing operation then is repeated on the next-received frame interval of video information.

[0043] In the preferred embodiment, motion vector detector 114 may comprise a digital signal processor, a microprocessor or a hard-wired circuit capable of carrying out the functions described in greater detail below and represented by the flow chart shown in FIGS. 19A-19B. However, for a more complete understanding and appreciation of the motion vector detector, the following discussion is presented to describe the manner in which the video information included in the blocks of a preceding frame undergo movement from that frame to the next. Referring first to FIGS. 2A-2C, FIG. 2A schematically illustrates blocks 1, 2, . . . 16 of a previous frame 122 and FIG. 2B illustrates the relative movement, or changed position of those blocks, resulting in the present frame 124. For the purpose of simplification, it is assumed that those blocks of previous frame 122 undergo only rectilinear motion when being reconstituted as present frame 124. For example, block 1 undergoes movement in the −x direction, as does block 2. Block 3 also undergoes movement in the −x direction as well as movement in the +y direction. Block 4 is assumed to undergo movement in the −y direction and block 5 is assumed to remain stationary. The x and y displacements, or rectilinear motion, of the remaining blocks are evident by comparing FIGS. 2A and 2B.

[0044] The movement of a block from previous frame 122 to present frame 124, such as the movement of block 1, is detected in motion vector detector 114 by searching the stored pixels of previous frame 122 for a match with the pixels that constitute block 1 in present frame 124. Likewise, the movement of block 2 from frame 122 to frame 124 is detected by searching for a match between those pixels which constitute block 2 in the present frame with the pixels of the corresponding block 2 in the previous frame. Such searching is implemented by establishing a search block to function as a template, and then displacing that block in, for example, the x and y directions until the search block overlies a block in the previous frame which is substantially the same as the block in the present frame. Preferably, this match is determined by sensing when the pixels that are included in the search block as that search block is positioned at different rectilinear locations are substantially the same as the pixels which are included in the block under consideration in the present frame. For example, a pixel-by-pixel comparison is made for each such position of the search block, and differences between each pixel included in the search block and the corresponding pixels in the block of the present frame are summed to produce a block difference value. When the search block is moved to a new position, another block difference value is produced. These block difference values are stored as the search block is displaced over a constrained search area; and the minimum of the stored block difference values is selected to represent the linear motion vector of that block.

[0045] FIG. 2C schematically illustrates a search block 126 which is displaced in the x and y directions over a constrained search area 130 while seeking a match between a particular block in the present frame and corresponding block 128 in the previous frame. In one embodiment, search block 126 may be the particular block in the present frame which then is displaced linearly in the x and y directions until it coincides with block 128 in the previous frame. The x displacement and y displacement of search block 126 which brings that block into coincidence with block 128 are used as the x and y motion vectors. That is, x and y vector data are produced by motion vector detector 114 to represent the magnitude of the linear movement of block 128 from the previous frame to the present frame.

[0046] FIGS. 2A and 2B schematically illustrate the manner in which linear motion of a block of pixels from one frame to the next is detected. However, if a block in the previous frame, such as block 128, undergoes rotational movement from the previous frame to the present frame, the detection of linear motion may not provide an accurate representation of such rotational motion. FIGS. 3A and 3B represent the manner in which one or more of blocks 1-16 in previous frame 142 undergo rotational movement (as well as rectilinear movement) so as to result in the blocks which constitute present frame 144. That is, if respective ones of blocks 1, 2, . . . 16 of previous frame 142 are rotated, the individual rotations of such blocks will appear as shown in FIG. 3B so as to constitute present frame 144. It is a feature of the present invention to detect such rotational motion and to generate rotation vector data representing the rotations of blocks 1, 2, 3, . . . 16 having the magnitude and direction illustrated in FIG. 3B.

[0047] FIG. 3C schematically illustrates the manner in which a search block 146 is displaced both linearly, in the x and y directions, and angularly, in the direction represented by vector r, over a constrained search area 150 in order to detect a match between a particular block in the present frame (from which the search block is derived) and the corresponding block 148 in the previous frame. For example, the search block, which may be thought of as a template corresponding to a given block in the present frame, is displaced by an incremental amount x and y to a new coordinate location within the constrained search area 150, and then the search block is rotated in the positive and negative directions (i.e. clockwise and counterclockwise) searching for a match between the search block and block 148 of the previous frame. It will be appreciated that the search block is displaced both rectilinearly and rotationally in a systematic manner while searching for block 148. Let it be assumed that any given position of search block 146 may be defined by the coordinates x_m, y_nand r_Θ, where m and n are variable integers (both positive and negative) and Θ is a variable angle. A unique position of the search block is established by the individual values of m, n and Θ. For each value of m, n and Θ, the pixels of the stored previous frame that are encompassed by the search block are compared, on a pixel-by-pixel basis, to the corresponding pixels of a given block in the present frame. The difference between the compared pixels is summed to produce a block difference value; and the block difference values that are obtained for each value of m, n and Θ are stored. After the search block 146 has been linearly and rotationally displaced over the constrained search area 150, the stored block difference value having the smallest value is selected and the values of m, n and Θ which produced that block difference value are used to generate the linear and rotational vector data. It is appreciated that the smallest block difference value represents a match between the given block in the present frame and block 148 in the previous frame. The values of m, n and Θ thus represent the amount of linear and rotational movement of block 148 relative to that block in the present frame.

[0048] While the technique of detecting linear and rotational motion provides a marked improvement over the detection of only linear motion, it has been found that the video information which constitutes a picture sometimes is produced by zooming in or zooming out on a subject. It is desirable to sense a zoom vector, if present, which represents a fourth dimension of motion. FIGS. 4A-4D illustrate the effect of a zoom operation from one block to the next.

[0049] Let it be assumed that a present block 154 is comprised of a 4×4 array of pixels, each of which may be represented as a pixel ¹⁵⁴_(m,n), where m represents an x coordinate and n represents a y coordinate. For simplicity, let it be further assumed that a zoom-in operation is carried out from one frame to the next, such that block 154 in the present frame now may be illustrated as block 156 in the previous frame. FIG. 4B schematically illustrates a superimposition of previous block 156 over present block 154, with the 4×4 pixel array of block 156 being represented by pixels 156_(m,n). It will be appreciated, therefore, that when the previous frame of video information is searched for a match with a given block of the present frame, the search block that is used as a template must be compensated by a zoom factor Z in order for a proper comparison between previous block 156 of reduced size and present block 154. That is, when searching the previous frame of video information, a block in the previous frame must be “shrunk.”

[0050] FIGS. 4C and 4D represent the effect on the size of a block in the present frame, such as a present block 162, caused by a zoom-out operation. As before, the present block is assumed, for simplicity, to be comprised of a 4×4 array of pixels 162_(m,n), as shown in FIG. 4C, and the superimposition thereon of the previous block 164 resulting from the zoom-out operation is illustrated in FIG. 4D. In FIG. 4B, the zoom factor which resulted in present block 156 of increased size may be thought of as a fraction that is greater than unity; and the zoom factor which results in present block 162 of reduced size, as shown in FIG. 4D, may be thought of as a fraction that is less than unity.

[0051] In accordance with this feature of the present invention, the zoom factor is used to “shrink” a previous block 156 when the video information of a previous frame is searched for a match when the zoom factor is greater than unity; and the zoom factor is used to “enlarge” previous block 164 when the previous frame of video information is searched for a match when a zoom factor less than unity is used. Since it often is not known whether a zoom factor is present and, if so, whether that factor is greater than or less than unity, it is a preferred embodiment of the present invention to establish a search block with a variable zoom factor z_p, where p is variable, and varying p from a value less than unity to a value greater than unity at each position x_m, y_nand r_Θ of the search block as that search block is displaced linearly and rotationally over the constrained search area.

[0052] The combination of rectilinear, rotational and zoom motion of the blocks in a previous frame so as to result in substantially the same blocks in the present frame is schematically represented by FIGS. 5A and 5B. It is assumed that FIG. 5A illustrates a previous frame 170 formed of blocks 1, 2, . . . 16, and these blocks undergo respective linear motion in the x and y directions, as well as rotational motion and a zooming motion. As a result of such motion vectors, the blocks which constituted previous frame 170 are re-formed as present frame 172 shown in FIG. 5B. It should be appreciated, however, that FIG. 5B is intended for explanatory purposes only. For example, FIG. 5B illustrates a zooming-out for block 1 and a zooming-in for block 4. It will be recognized that the use of two different types of zooming factors from one frame to the next may not be common if a given scene is present in a single frame. Of course, the use of special effects, editing, superposition and movement of a subject toward or away from the camera might result in a mixture of two different types of zooming factors, as shown in FIG. 5B, but for the purpose of understanding the present invention, this can be ignored.

[0053] The manner in which the video information of a previous frame is searched for a block, such as block 176, which matches a given block in the present frame is schematically illustrated in FIG. 5C. Here, a search block 174, which is used as a template, is displaced in the x, y and r directions throughout a constrained search area 178, and for each incremental positioning of search block 174, the size of that search block is changed by the zoom factor z. That is, the search block is displaced to different coordinates x_m, y_n, r_Θ and z_pby varying integers m and n, varying angle Θ and varying the zoom factor p. With each change of each of m, n, Θ and p, a pixel-by-pixel comparison between the video information defined by the search block and the given block of the present frame is made and a block difference value is produced. As discussed above, all of the block difference values resulting from the displacement of search block 174 are stored, and the minimum block difference value is selected. The values of m, n, Θ and p which produce that block difference value are used to generate linear, rotational and zoom vector data. Such four-dimensional data is an accurate description and measurement of the motion of each block from a previous frame to the present frame. It is this four-dimensional vector data that is encoded by encoder 106, combined with the encoded DCT coefficients from DCT circuit 104 and transmitted or recorded as compressed video data.

[0054] The manner in which a search block is established and displaced rectilinearly, rotationally and by a zoom factor in order to search for a match between a given block of the present frame and the corresponding block in the previous frame and thus produce the four-dimensional motion vectors are illustrated in FIGS. 6-15, which now will be briefly described. As a feature of the present invention, a block of pixels in the present frame is compared to the stored pixels of a previous frame to identify a “match” by establishing a search block which is incrementally displaced in four dimensions x, y, r and z, with the search block serving as a template for defining the pixels of a previous frame to which the block of the present frame is compared. While various techniques may be used for displacing the search block, in the preferred embodiment, the zoom factor z is changed over its preset range from, for example, a zoom factor −5 to a zoom factor +5, and then the rotational coordinate r is incremented, whereafter the zoom factor z once again is incremented over its range from −5 to +5. The foregoing is reiterated for a change in the r coordinate over its preset range from, for example, −π/6 radians to +π/6 radians. Then, the x coordinate is incremented and the foregoing operation is repeated once again. All the while the pixels which are encompassed by the search block are compared to the pixels of the block in the present frame. This incrementing of the x, r and z coordinates is repeated over the preset range of the x coordinate from −8 to +8; and then the y coordinate is incremented. Here too, for each incremental change of the y coordinate, the z coordinate is changed over its preset range and then the r coordinate is incremented; and after the r coordinate has been changed over its preset range, the x coordinate is incremented; and after the x coordinate has been changed over its preset range, the y coordinate is incremented; and the y coordinate likewise is incremented over its preset range from −16 to +16, thereby completing the displacement of the search block for a match with the given block of the present frame. Thereafter, a new block in the present frame is selected and the foregoing search operation is reiterated in order to find a match between this new selected block and the pixels of the stored, previous frame. It will be appreciated that the particular values of x, y, r and z which result in the match, that is, the values which result in the least difference between the pixels of the selected block in the present frame and the stored pixels of the previous frame are used to derive the four dimensional motion vectors x, y, r and z.

[0055] With the foregoing in mind, FIG. 6A schematically illustrates a block 184 of the previous frame, which is defined by the search block having the coordinates x₂, y₋₂and z₁, relative to a block 186 in the present frame. Block 184 of the previous frame is assumed, for the purpose of the schematic illustration in FIG. 6A, to undergo no rotational displacement, that is, r=0. The pixels which are included in previous frame 184 are illustrated as pixels a, b, c, . . . p, and the corresponding pixels in selected block 186 of the present frame are represented as pixels a′, b′, . . . p′. To determine a match between previous block 184 having the particular coordinates (x₂, y₋₂, r₀, z₁) and selected block 186, the difference, if any, between pixels a and a′, b and b′, . . . p and p′ is determined. In the preferred embodiment, the absolute value of each difference is obtained and the absolute values are summed to produce a block difference value. This block difference value is stored for each particular coordinate location of the search block (that is, for each different coordinate location of previous block 184) and then, after the search block has been displaced throughout its constrained area, as aforedescribed, the smallest of the block difference values (i.e. the minimum block difference value) is selected as a “match” between previous block 184 and present block 186. The values of x, y, r and z which result in this match represent the motion vectors which define the movement of previous block 184 to present block 186. Preferably, and as a practical matter, all of the determined block difference values need not be stored. Rather, a block difference value is stored if it is less than the block difference value which then is in storage. It is appreciated that, at the end of the displacement of the search block throughout its constrained area, the block difference value that is stored is the minimum block difference value.

[0056] FIG. 6B is similar to FIG. 6A, except that previous block 184 in FIG. 6B is assumed to undergo rotation. That is, the r coordinate is assumed to be r=Θ₁. For convenience, it is preferred that a corner of previous block 184 remains fixed at a pseudo origin, and block 184 is rotated by Θ₁about this pseudo origin. Accordingly, in the example shown in FIG. 6B, the search block is assumed to exhibit the coordinates (x₂, y₋₂, r_Θ1, z₁) to define previous block 184; and pixels a and a′, b and b′, . . . p and p′ of previous block 184 and present block 186, respectively, are compared. The sum of the absolute differences between the compared pixels is stored.

[0057] FIG. 6C is similar to FIG. 6B, except that the search block which defines previous block 184 is assumed to be rotated by the amount r=Θ₂. Nevertheless, the remaining coordinates x, y and z remain the same as before. Thus, in FIG. 6C, the search block which defines previous block 184 is located at the coordinates (x₂, y₋₂, r_Θ2, z₁). FIGS. 6D, 6E and 6F are seen to be similar to FIG. 6B, except that the rotational coordinate r in FIG. 6D is assumed to be r=Θ₃(in the illustrated example, Θ₃may be equal to 0); in FIG. 6E, r=Θ₄and in FIG. 6F, r=Θ_5.

[0058] It will be appreciated that, in the example shown in FIGS. 6A-6F, the size of the search block which establishes previous block 184 is smaller than the size of present block 186. That is, the zoom factor is assumed to be a fractional value greater than unity. For convenience, a zoom factor that is less than unity is represented by a negative subscript and a zoom factor that is greater than unity is represented by a positive subscript. Although not shown, the value of the subscript of the zoom factor identifies the number of pixels that the search block is larger or smaller than the present block. For example, the coordinate z₋₃means that the previous block has zoomed in relative to the present block to a block three pixels larger, in the x and y directions, from the present block (and, of course, the present block appears smaller than the previous block). A zoom factor z₂means that the previous block has zoomed out to a block two pixels smaller in the x and y directions from the present block (and the present block appears larger than the previous block).

[0059] In FIGS. 7A-7F, the values of the x and y coordinates are assumed to be the same as the values of those coordinates shown in the example of FIGS. 6A-6F, that is, x₂and y₋₂, but now the zoom factor is assumed to be z₀. Thus, the size of previous block 184, as defined by the search block, is assumed to be of the same size as that of present block 186. With these coordinates (x₂, y₋₂, z₀), the rotational coordinate r is varied as follows: in FIG. 7B, r=Θ₁; in FIG. 7C, r=Θ₂; in FIG. 7D, r=Θ₃; in FIG. 7E, r=Θ₄; and in FIG. 7F, r=Θ₅. For each coordinate (x₂, y₋₂, r_Θ, z₀) shown in FIGS. 7B-7F, the difference between pixels a and a′, b and b′, . . . p and p′ of previous block 184 and present block 186, respectively, is determined and these differences are summed to produce the aforementioned block difference value.

[0060] FIGS. 8A-8F schematically illustrate the displacement of the search block which establishes previous block 184 over the rotational range from Θ₁to Θ₅for the coordinates (x₂, y₋₂, z₋₁) It is seen that the size of previous block 184 is larger than that of present block 186, that is, the zoom factor is less than unity. For this zoom factor, a match between present block 186 and the pixels of the stored, previous frame is searched based upon the assumption that the previous frame has zoomed in on the subject (and, of course, the present frame has zoomed out). FIGS. 9A-9C are illustrative of the example wherein the x coordinate has changed from x₂to x₁, the y coordinate is assumed to remain at y₋₂, the zoom coordinate is assumed to be z₁and the rotational coordinate varies from Θ₁(FIG. 9B) through zero (FIG. 9A) to Θ₅(FIG. 9C). For simplification, other values of Θ are not illustrated in the example of FIG. 9. Nevertheless, it will be appreciated that, for each coordinate x₁, y₋₂, r_Θ, z₁, the difference between pixels a and a′, b and b′, . . . p and p′ is obtained, summed and stored as the block difference value.

[0061] FIGS. 10A-10C are similar to FIGS. 9A-9C, except that the zoom factor z is assumed herein to be z₀. The previous block 184 which is established by the search block is seen to undergo rotational displacement, wherein the r coordinate is changed over the range shown as r=0 (FIG. 10), r=Θ₁(FIG. 10B) and r=Θ₅(FIG. 10C). For each incremental displacement of the search block, the pixels a, b, . . . p encompassed thereby are compared to corresponding pixels a′, b′, . . . p′ of present block 186 to produce a block difference value for each such orientation of the search block.

[0062] Likewise, FIGS. 11A-11C illustrate different rotational displacements of previous block 184, as defined by the search block, for the coordinates (x₁, y₋₂, z₋₁). It is appreciated that the zoom factor z here is assumed to be less than unity, which means that the size of the search block is greater than the size of the present block and represents a zoom-out operation.

[0063] FIG. 12A illustrates yet another incremental displacement in the x direction, wherein the coordinates of previous block 184, as defined by the search block, are (x₀, y₋₂, r₀, z₁). FIG. 12B illustrates the incremental rotational displacement of the search block shown in FIG. 12A, wherein search block 184aillustrates an angular rotation r=Θ₁, search block 184billustrates the angular rotation r=Θ₂and search block 184cillustrates the angular rotation r=Θ₅. That is, the search block shown in FIG. 12A is subjected to incremental rotations of the type shown in FIG. 12B.

[0064] In FIG. 13, the search block is assumed to undergo yet another incremental displacement in the horizontal direction, resulting in an x coordinate of x₋₁. Here too, and simply for the purpose of illustration, the zoom factor z is assumed to be z₁and the y coordinate is assumed to remain at y₋₂. With this search block having the coordinates (x₋₁, y₋₂, z₁), FIG. 13 illustrates selected angular rotations of the search block, whereby search block 184aexhibits the rotational coordinate r=Θ₁, search block 184bexhibits the rotational coordinate r=Θ₃and search block 184cexhibits the rotational coordinate r=Θ₅. As before, the block difference value between each of the illustrated search blocks and present block 186 is obtained and stored.

[0065] FIG. 14 is similar to FIG. 13, but here illustrates the coordinates of the search block which establishes previous block 184 as (x₋₂, y₋₁, z₋₁). Thus, the x and y coordinates of the search block are changed from those of FIG. 13, and for illustrative purposes, the zoom factor z is assumed to be less than unity, as represented here by z_−1.

[0066] FIG. 15 illustrates yet another example of the coordinates of the search block which define previous block 184 as (x₋₁, y₂, z₁). It is seen that the x and y coordinates of the search block have been changed, the zoom factor is assumed to be greater than unity, and with the thus-defined search block, the rotational coordinate thereof is varied. As can be seen from FIG. 15, the rotational coordinate of search block 184 is varied over a range, and illustrative positioning thereof is depicted as search block 184a, wherein r=Θ₁; search block 184b, wherein r=Θ₃; and search block 184c, wherein r=Θ₅. As before, the block difference value between each of search blocks 184a, 184band 184cand present block 186, that is, the difference between the pixels of these search blocks and the pixels of present block 186, is obtained and stored.

[0067] After x, y, r and z have been varied over their preset ranges, as discussed above and as schematically illustrated in FIGS. 6-15, the minimum block difference value that has been produced is selected, and the values of the coordinates x_m, y_n, r_Θ and z_pwhich result in this minimum block difference value are used to derive the motion vectors x, y, r and z. That is, the particular location and size of the search block, as represented by these coordinates, which results in a match between present block 186 and a previous block 184, are used to determined the rectilinear, rotational and zoom movement of the previous block which results in the present block.

[0068] The rotation of a block of pixels in the present frame relative to that same block in the previous frame is further illustrated in FIG. 16. Let it be assumed that a pixel 194ain present block 194 is disposed at the coordinate location X, Y relative to an arbitrary origin. The corresponding pixel 192ain the previous block 192 is seen to be disposed at the coordinate location X′, Y′ and the rotation of previous block 192 which results in present block 194 is represented by the angle A. Now, the coordinate locations X′, Y′ of pixel 192ain the previous block are related to coordinates X, Y and rotational angle A by the following equations:

[0069] X′=Xcos A−Ysin A  (1)

[0070] Y′=Xsin A+Ycos A  (2)

[0071] Thus, when the pixels included in a present block 194 are known, the locations of corresponding pixels in the previous block may be determined from equations (1) and (2) above. Stated otherwise, if a search block is rotated by the angle A relative to the present block, then the pixel at location X′, Y′ in the rotated search block may be ascertained from the foregoing equations. As will be described below, a pixel in the stored previous frame may not be disposed exactly at the coordinate location X′, Y′. In that event, the pixel at this location X′, Y′ is determined by interpolating its value from pixels which are disposed in the stored, previous frame adjacent to this location.

[0072] FIG. 17 provides a schematic representation of the manner in which a pixel 198ain a block 198 of the present frame, located at coordinates X, Y is related to its corresponding pixel 196ain a block 196 of the previous frame when the zoom ratio between these frames is represented as Z. For example, it is assumed that present block 198 is produced by a zooming in operation which means that the previous block has zoomed out relative to the present block and results in a decrease in size of the previous block relative to the present block. Let it be assumed that pixels 198aand 196aare the same pixels in the present and previous blocks 198, 196, respectively, and pixel 198ais located at coordinates X, Y while pixel 196ais located at coordinates X′, Y′. Assuming a zoom ratio Z, then the coordinates X′, Y′ may be derived from coordinates X, Y as follows:

[0073] X′=Z X  (3)

[0074] Y′=Z Y  (4)

[0075] Thus, if the zoom ratio Z is assumed, and if the coordinates of a given pixel 198aare known, then the coordinates of the corresponding pixel in the search frame may be readily determined.

[0076] For simplicity, it has been assumed that there is no rotational movement from previous block 196 to present block 198. If there is rotational movement, then the coordinates X′, Y′ of the same pixel in the search block are determined by combining the rotational coordinate determination discussed above in conjunction with FIG. 16 with the zoom coordinate determination discussed in conjunction FIG. 17.

[0077] Consistent with the discussion set out hereinabove with respect to FIGS. 6-15, previous block 196 is defined by a search block. Pixel 196alocated at coordinates X′, Y′ in this search block may not coincide precisely with a pixel in the stored, previous frame. In that event, the value of pixel 196aat coordinates X′, Y′ is determined by interpolating from those pixels in the previous frame which are adjacent thereto. The manner in which the value of a pixel in a search block is interpolated from adjacent pixels in the stored, previous frame is illustrated in FIG. 18 and now is described.

[0078] Let it be assumed that, by reason of the rotation shown in FIG. 16, or the zoom factor shown in FIG. 17, or a rectilinear displacement such as shown in FIG. 2B, or a combination thereof, a particular pixel in a search block is located at a point having the coordinates (X, Y), as represented by pixel 196a, and the value of this pixel may be represented as P₁(X,Y). This pixel, although in the neighborhood of adjacent pixels 196b, 196c, 196dand 196ein the previous frame, nevertheless does not coincide with any of these actual pixels. For convenience, it is assumed that pixel 196bis located at coordinates (X′, Y′), pixel 196cis located at coordinates (X′+1, Y′), pixel 196dis located at coordinates (X′, Y′+1) and pixel 196eis located at coordinates (X′+1, Y′+1). Let it be further assumed that the distance between pixels 196band 196cmay be formed of PD divisions. For example, PD may be any convenient integer, such as 10. Let it also be assumed that pixels 196band 196dare separated by these same PD divisions. The location of pixel 196arelative to its adjacent pixels 196b-196eis as shown in FIG. 18. That is, the X coordinate of pixel 196ais spaced from pixel 196bby the amount X−X′ and is spaced from pixel 196cby the amount 1−(X−X′). The Y coordinate of pixel 196ais spaced from pixel 196bby the amount Y−Y′, and this pixel is spaced from pixel 196dby the amount 1−(Y−Y′). Now, the value of pixel 196aat coordinates (X, Y) may be mathematically determined from the following equation: $\begin{array}{cc}\begin{array}{c}{P}_1\left(X,Y\right)=[\left(X^{\prime },Y^{\prime }\right)·\left(\mathrm{PD}-\mathrm{RX}\right)·\left(\mathrm{PD}-\mathrm{RY}\right)+\\ \left(X^{\prime }+1,Y^{\prime }\right)·\mathrm{RX}·\left(\mathrm{PD}-\mathrm{RY}\right)+\\ \left(X^{\prime },Y^{\prime }+1\right)·\left(\mathrm{PD}-\mathrm{RX}\right)·\mathrm{RY}+\\ \left(X^{\prime }+1,Y^{\prime }+1\right)·\mathrm{RX}·\mathrm{RY}]/\left(\mathrm{PD}·\mathrm{PD}\right)\end{array}\mathrm{where}\mathrm{RX}=\left(X-X^{\prime }\right)·\mathrm{PD}\mathrm{RY}=\left(Y-Y^{\prime }\right)·\mathrm{PD}& \left(5\right)\end{array}$

[0079] It is appreciated that equation (5) can be easily implemented by a suitably programmed microprocessor or digital signal processor once the coordinates X, Y and the locations of pixels 196b-196eare known. In a practical embodiment, coordinates X, Y are readily determined, as illustrated in FIGS. 16 and 17, and pixels 196b-196eare, of course, pixels which are included in the stored, previous frame.

[0080] The manner in which the four-dimensional motion vectors x, y, r and z are determined by motion vector detector 114 now will be described in conjunction with the flow chart shown in FIGS. 19A-19B. In one embodiment, this flow chart is implemented by a suitably programmed microprocessor; and in the preferred embodiment, a digital signal processor or, alternatively, a hard-wired processor, is used to execute this flow chart.

[0081] As illustrated in FIG. 19A, the motion vector detecting routine commences with instruction 202 which fetches the next frame of video information supplied from preprocessor 101 and designates this frame as the present frame. Then, inquiry 204 is made to determine if the fetched frame is the first frame, such as the first frame in a scene. If so, instruction 206 is carried out, whereby the video information is compressed by relying upon intraframe encoding, whereby the spatial redundancy within this frame is reduced by direct cosine transformation or by other spatial redundancy reducing techniques known to those of ordinary skill in the art. Thereafter, the compressed, encoded video information is decoded at 207 and then stored as the previous frame at instruction 208. Then, the routine returns to instruction 202 and the next frame of video information supplied by multiplexer 101 is fetched. Assuming that the fetched frame is not the first frame in a scene, inquiry 204 is answered in the negative and the routine advances to instruction 210, whereby the present frame (that is, the frame which had been fetched by instruction 202) is segmented into blocks. In FIG. 1, this segmentation operation is illustratively carried out by segmenting circuit 102.

[0082] Thereafter, the routine advances to instruction 212 to select a block in the present frame. This block may be block 186 shown in FIGS. 6-15. Then, instruction 214 is carried out, which establishes a search block having coordinates x, y, r, z, such as one of the search blocks illustrated in FIGS. 6-15. It will be appreciated that these coordinates may be more accurately expressed as x_m, y_n, r_Θ, z_p, where m, n, Θ and p each are individually variable over respective ranges, such as mentioned above.

[0083] After the search block is established, each pixel therein is compared to its corresponding pixel in the selected present block, as represented by instruction 216. For example, each pixel may be represented as an 8-bit character corresponding to the brightness of that pixel and the absolute difference between an 8-bit pixel in the present block and an 8-bit pixel in the search block is obtained. The 8-bit pixel in the search block may be interpolated in the manner shown in FIG. 18 if its coordinate location in the search block does not coincide with a pixel in the previous frame. The differences obtained for each of the respective, compared pixels are summed to produce a block difference value and if the block difference value between the present block and the search block is a minimum value, it is stored at 218.

[0084] As an alternative, a block difference value may be produced by other conventional error detecting techniques, such as obtaining the sum of the squares of the differences between the pixels of the present and search blocks, or other conventional techniques.

[0085] After the block difference value between the present block and the search block has been determined and, if of a minimum value compared to other block difference values, as described above has been stored, the routine advances to inquire, at 220, if all of the values of a selected one of the coordinates x, y, r and z have been searched. In the example described herein, inquiry 220 determines if all of the values of the zoom coordinate have been searched. If not, the routine advances to instruction 222 which increments the zoom coordinate z by one, thus displacing the search block by, for example, reducing the size of the search block. Thereafter, instructions 216 and 218 and inquiry 220 are repeated.

[0086] As before, instruction 218 stores the block difference value obtained for the incremented zoom coordinate if that block difference value is a minimum. The routine then cycles through the loop formed of instructions 216, 218, 222 and inquiry 220 until all of the preset values of the zoom coordinate have been searched. That is, as the search block is displaced, each displacement thereof is compared to the present block. After all of the zoom coordinate values have been searched, inquiry 220 is answered in the affirmative and the routine advances to inquiry 224, shown in FIG. 19B. Here, inquiry is made to determine if all of the values of the rotation coordinate have been searched over the preset range established therefor. If this inquiry is answered in the negative, instruction 226 is executed, whereby the value of the rotation coordinate r is incremented. It is appreciated that this incrementing of the rotation coordinate introduces an angular displacement in the search block; and the routine then returns to instruction 216, whereby the pixels of the displaced search block are compared once again to the pixels of the present block. Then, as before, the routine cycles through the loop formed of instructions 216, 218 and 222 and inquiry 220 until the zoom coordinate z has been incremented over its entire range. Then, inquiry 224 is made once again; and is assumed herein to be answered in the negative. Therefore, the rotation coordinate r is incremented, and the foregoing operation is repeated one more time. It is seen that the routine reiterates the incrementing of the zoom coordinate z and the rotation coordinate r until the rotation coordinate has been incremented over its entire range. At that time, when the routine reaches inquiry 224, this inquiry is answered in the affirmative, and the routine then advances to inquire, at 228, if all of the values of the x coordinate have been searched. If not, the x coordinate is incremented, as indicated by instruction 230, and the routine returns once again to instruction 216.

[0087] It is appreciated that, with each incremental change of the x coordinate, the routine cycles through the loop which includes instruction 222, and after the z coordinate has been incremented over its entire range, the rotation coordinate r is incremented, as represented by instruction 226, whereupon the search block and present block are compared, on a pixel-by-pixel basis, for each value of the z coordinate. Eventually, the rotation coordinate r is incremented over its entire range, whereupon the x coordinate is incremented one more time. This reiterative operation continues until the x coordinate has been incremented over its entire range. Thereafter, when the routine returns to inquiry 228, this inquiry is answered in the affirmative and inquiry 232 then is made to determine if all of the values of the y coordinate have been searched. If not, instruction 234 is executed to increment the y coordinate by one. The routine then returns to instruction 216, and the foregoing reiterative operation is repeated once again.

[0088] From the foregoing discussion, it is seen that a hierarchical order of incrementing the x, y, r and z coordinates is established; and although any one of these coordinates may be selected as having the least hierarchical value and any other coordinate may be selected as having the highest hierarchical value, in the present example it has been assumed that the zoom coordinate z exhibits the lowest hierarchical value and the y coordinate exhibits the highest hierarchical value. The coordinate having a higher hierarchical value is incremented by one only after the coordinate having the next lower hierarchical value is incremented over its entire range. In this manner, the search block established by instruction 214 is linearly, rotationally and zoom-in/zoom-out displaced over a constrained search area while the pixels of a previous block defined by the search block are compared to their corresponding pixels in the present block.

[0089] As has been discussed hereinabove in conjunction with FIGS. 16-18, it is likely that a pixel in the search block does not coincide with a stored pixel of the previous frame. In that event, the value of the pixel in the search block is interpolated from those stored pixels in the previous block which are adjacent thereto. The difference between a pixel in the present block and the corresponding pixel in the search block is determined by comparing the pixel in the present block to the interpolated pixel in the search block.

[0090] The minimum block difference value for the overall displacement of the search block is stored, as represented by the reiterative execution of instruction 218. After the y coordinate has been incremented over its entire range, as represented by an affirmative answer to inquiry 232, the routine advances to instruction 236 to use the minimum block difference value. As shown by instruction 236, the x, y, r and z coordinates which resulted in that minimum block difference value are obtained. That is, if coordinates x_m, y_n, r_Θ and z_pare stored with this minimum block difference value, the values of m, n, Θ and p are used to generate the motion vectors in the x, y, r and z directions. Stated otherwise, the values of m, n, Θ and p which define the position of the search block that results in the minimum block difference value are identified; and these values are used to generate the motion vectors.

[0091] After generating the motion vectors, the routine advances from instruction 236 to inquiry 238 which determines if the last of the segmented blocks in the present frame has been compared to the stored video information of the previous frame. That is, inquiry is made to determine if the last of the segmented blocks has been searched for a match with a previous block. If not, the routine returns to instruction 212 which establishes a new search block at coordinates x, y, r and z; and then the foregoing reiterative operation is repeated.

[0092] Eventually, all of the segmented blocks in the present frame will have been compared to the blocks of the previous frame. At that time, when inquiry 238 is reached, it is answered in the affirmative. Then, instruction 240 is carried out and the motion vectors which are produced by instruction 236 are encoded, as by encoder 106 (FIG. 1) and transmitted or recorded for subsequent use to reconstruct the corresponding video picture.

[0093] In addition, the motion vectors are decoded and, as shown in FIG. 1, used to compensate the previous frame that had been stored in frame store 110 pursuant to instruction 208. The motion-compensated frame is summed with the residual frame derived from DCT transformation circuit 104 (FIG. 1) and then stored as the previous frame, as represented by instruction 242. The routine then returns to its beginning, shown in FIG. 19A, to determine the four-dimensional motion vectors for the next frame of video information.

[0094] While the present invention has been particularly shown and described with reference to a preferred embodiment, it will be readily appreciated by those of ordinary skill in the art that various changes and modifications may be made without departing from the spirit and scope of the invention. For example, the hierarchical order in which the individual coordinates are incremented need not be limited solely to the example discussed above. Also, any technique which compares the present block to a previous block in order to detect a “match” therebetween may be used. Summing the absolute values of the differences between each pixel in the present block and the corresponding pixels in the previous block is not the only means contemplated to produce a block difference value. As mentioned previously, the sum of the squares of differences may be utilized and still other techniques known to those of ordinary skill in the art may be incorporated into the present invention. Still further, although encoding of the four-dimensional motion vectors has been described and is preferred, the present invention does not rely upon and should not be limited to the use of an encoding step.

[0095] Although the search block discussed herein has been used as a template to define a previous block to which the present block is compared, the search block may serve as a template for defining a present block to which a given previous block is compared.

[0096] Therefore, it is intended that the appended claims be interpreted as including the embodiment described herein, those modifications and alternatives which have been discussed above and all equivalents thereto.