Motion compensated frame rate conversion

Motion compensation frame rate conversion technology

The present invention is about improving video and graphics processing.

In the low display update rate of advanced digital display devices (for example, 50 frames per second for interlaced video materials, 24 frames per second for film-originating materials), a display problem called "area flicker" occurs. Due to the high sensitivity to flicker in the peripheral area of human vision, the area flicker changes significantly as the size of the display increases. A simple way to reduce area flicker is to repeatedly input fields or frames at a higher rate (for example, 100 fields per second for interlaced video) to increase the display update rate. This solves the area flicker problem of static scenes. However, because the naked eye can track the trajectory of moving objects, new problems are repeatedly introduced into moving scenes, called "moving tremor" or "moving smudge", especially in high-contrast areas. Therefore, the motion compensation frame interpolation is better, and the pixels are calculated in the interpolation frame or field of the local movement track, so there is no difference between the expected image movement of the eye tracking and the display image movement. The movement vector depicts the movement trajectory of the partial image from one field or frame to the next.

The motion vector can be calculated at different levels of spatial resolution, such as pixel level, image repair level, or object level. Calculating the motion vector independently for each pixel theoretically leads to an ideal data set, but it is not feasible due to the large number of calculations required. Calculating the motion vector for each image patch reduces the number of calculations, but it will cause the motion vector in the image patch to be discontinuous. Object-based calculation of movement vectors can theoretically lead to high resolution and low computational requirements, but object segmentation is a challenging problem.

Therefore, it is necessary to determine the motion vector effectively and accurately so that there is no difference between the expected image motion due to eye tracking and the displayed image motion in the digital video.

The present invention provides a method and device for effectively and accurately determining the movement vector, so that there is no difference between the expected image movement of the eye tracking of the digital video and the displayed image movement.

In general, the present invention provides methods and devices including computer program products that implement and use techniques for calculating motion vectors in digital video sequences. The first image frame is received at the first resolution. The first image frame contains several image repairs with their respective first positions. The second image frame is received at the first resolution. The second image frame includes one or more image repairs corresponding to the image repairs of the first image frame, and each image repair has a respective second position. The motion vector is determined for each image repair of the first image frame with the corresponding image repair of the second image frame. The judgment includes generating two or more copies of each of the first and second image frames, each copy having a different resolution lower than the first resolution, and selecting the best motion vector from a plurality of vectors at each resolution . The determined movement vector is used to establish the middle position of the image repair of the inset frame between the first and second frames.

An advantageous implementation may include more than one of the following characteristics. The determination may include: a) selecting the copy of the first image frame at the lowest resolution; b) selecting the motion vector determined for the previous pair of image frames; c) selecting the selected motion vector to be projected onto the first image frame Copy; d) Generate more than one update vector in the selected copy of the first image frame; e) Select the new best motion vector from the projection vector and the update vector; f) Select the first image at a higher resolution level A new copy of the frame; g) Repeat steps c) to f) until the first resolution is reached; h) Use the selected best motion vector of the first resolution level as the determined motion vector. Each image patch may include a plurality of pixels, which may be 8×8.

Generating more than two copies may include generating two copies of each of the first and second image frames, each copy having a different resolution lower than the first resolution. Selecting the movement vector may include: if there is no continuity between the pair of image frames, or if the previous image frame does not exist, then selecting the zero vector as the movement vector. Selecting the motion vector can include filtering the motion vector previously determined for the image frame.

Filtering may include determining the median value of the previous pair of image frames in a set of two or more motion vectors. Filtering may include a temporary segmentation process for the motion vectors of the previous image frame in a group of two or more. Generating more than one update vector may include generating more than one vector whose origin is the same as the selected motion vector, and a pixel that ends from the selected motion vector ends in a different pixel in the horizontal or vertical direction. The update vector may end at a pixel separated by one or two pixels from the pixel where the selected movement vector ends in the horizontal and/or vertical direction.

Selecting a new optimal motion vector may include for each selected motion vector and update vector: centering the first window on the pixels of the first image frame forming the origin of the vector; centering the second window on the first image frame forming the end of the vector For the pixels of the second image frame, the size of the second window is the same as that of the first window; determine the sum of the absolute difference of the brightness value for the pixels of the first window and the pixels at the corresponding position of the second window; select the vector with the smallest sum of absolute differences to do Is the new best movement vector. The size of the first and second windows can be the same as the image repair size. The determination may further include: projecting the camera vector to the selected copy of the first image frame, the camera vector depicting the global movement between the first and second image frames; selecting the new best among the projection vector, update vector, and camera vector Movement vector.

The details of more than one embodiment of the invention are shown in the drawings and below. Other characteristics, objectives, and advantages of the present invention will be clarified from the description, drawings, and scope of patent application.

The present invention provides a method and device for effectively and accurately determining the movement vector, so that there is no difference between the expected image movement of the eye tracking of the digital video and the displayed image movement. This is done by using the regression hierarchy measure to determine the movement vector.

Generally, in order to make the movement compensation measures work well, including the regression hierarchy measures in this article, two basic assumptions are made on the nature of the object's movement: 1) the moving object has inertia, and 2) the moving object is large. The inertia hypothesis implies that the motion vector only gradually changes with the temporary vector sampling interval (ie, the frame rate of the digital video). The large object hypothesis implies that the movement vector only changes gradually with the sampling interval of the space vector, that is, the vector image field is smooth and there are few discontinuous border movement.

The goal of the regression hierarchy method is to find the movement vector as follows: use the source correlation window for the first image frame, the target correlation window for the subsequent image frame, place the target correlation window, and get the best match with the source correlation window. That is, the content of the source-related window and the target-related window are as similar as possible. At the same time, the number of calculations required for matching between the source correlation window and the target correlation window must be as low as possible, while still looking for the overall vector space limit. To achieve these goals, the regression hierarchy method uses multiple resolution levels of the image frame. Project the previous best motion vector at the highest resolution level to the lowest resolution level, test it and more than one update, and first determine the best motion vector for the lowest resolution level. Then this best motion vector is propagated to a higher resolution level, where some adjustments are made and a new best motion vector is determined. The new best motion vector is propagated to another higher resolution level, where more adjustments are made and another new best motion vector is determined. This process is repeated until the highest original resolution level is reached and the best motion vector is identified.

Figure 1 shows an embodiment of the regression hierarchy process (100). Assume that multiple resolution levels of the image frame have been generated. As shown in Figure 1, the regression hierarchy process (100) for determining the motion vector starts to project the motion vector from the previous image frame to the lowest resolution level (step 102). A set of update vectors are generated and tested to find the best motion vector at the lowest resolution level (step 104). In one embodiment, the source correlation window centered at the origin of the motion vector is compared with the pixels centered at the corresponding position of the target correlation window at the end of each respective update vector to perform this test. The comparison can be performed by subtracting the brightness value of each pixel of the source window from the corresponding pixel of the respective target window. In this case, find the minimum sum of the absolute difference (SAD) of the source correlation window and target correlation window pair to define the best match, and the best movement vector is the vector that matches the source correlation window and target correlation window pair.

After finding the minimum SAD, the best vector is selected (step 106). The process (100) then checks whether there are any higher resolution levels (step 108). If there is a higher resolution level, the process propagates the best vector to the next higher resolution level (step 110) and repeats steps 104 to 108. If there is no higher resolution level, the process proceeds to step 112, where the best vector is selected as the motion vector and used for motion compensation to complete the processing of the current frame.

The advantage of this measure is that at a lower level, the pixel update is equivalent to the update of two or more pixels at the next higher level, depending on the difference in resolution between the two levels. If there are, for example, three resolution levels (1:1, 1:2, 1:4) and updates of +/-1 pixels per level, the convergence delay may be reduced by a factor of four. The resolution level is used to accelerate the temporary regression convergence. This leads to a significant improvement, especially for frames containing small objects moving at high speeds.

Take the three-level regression hierarchy mechanism of 1:1, 1:2, 1:4 resolution and the 4x4 pixel image repair gate as examples to describe the present invention in detail, referring to FIGS. 1-4. The vectors in Figures 2-4 only represent this example. The number of resolution levels and the number and/or type of vectors for each resolution level may vary with various factors, such as calculation cost, quality, processing speed, and so on.

Figure 4 shows the image repair grid (400), divided into 4x4 pixel image repair (405), where each pixel is displayed as a circle (410). The dark pixels (415) represent the positions where the motion vector is calculated for each 4x4 image patch of the pixel. As shown in Figure 4, a motion vector is calculated for each 4x4 image repair of pixels, and the position of the origin of the motion vector is the same in each 4x4 image repair. FIG. 3 shows the same pixel gate (400) with a half-resolution of the original pixel gate of FIG. 4. FIG. Fig. 2 shows the same pixel grid (400) with the lowest resolution. In this example, it is half the resolution of Fig. 3 or a quarter of the resolution of Fig. 4.

As shown in Figure 1 and Figure 2, the motion vector (205) is projected from the previous image to the lowest resolution level to determine the start of the regression hierarchical processing of the motion vector (step 102). This example is 1:4 of the original resolution, shown in figure 2. In one embodiment, the old motion vector (205) is filtered before projection, and mainly deals with the situation where the neighborhood contains the object background boundary that causes the vector discontinuity. In one embodiment, the vector neighborhood is removed and the vector median of the set of neighborhood vectors is found or a temporary segmentation procedure is performed to perform filtering. In the second case, the filtered output is a new basic vector at a level of 1:1, which is then projected to a level of 1:4. In the first frame of a sequence, that is, when there is no previous image, the processing (100) starts with the zero vector as the old motion vector. In one embodiment, when a scene is broken in the video, that is, when the two frames are not continuous, the zero vector is also used.

A set of update vectors (210a-210f) are generated and tested to find the minimum SAD of +/-1 pixel or +/-2 pixel from the old projection motion vector at the lowest resolution level (step 104). In Figure 2, six update vectors (210a-210f) are shown. Since the horizontal motion is usually greater than the vertical motion, there are two +/-1 pixels and two +/-2 pixels in the horizontal direction, and two + in the vertical direction. /-1 pixel. But for the projection vector (205), any number of update vectors can be generated and tested at any horizontal and/or vertical position. In one embodiment, the predicted camera vector is also projected to the 1:4 level. The camera vector is detailed below.

In one embodiment, the candidate vectors for image repair (all sent from the same image repair position of the source frame) are directed to different pixel positions of the target frame to calculate the SAD. For each candidate vector, the rectangular window is centered on the target frame on the pixel pointed to by the respective candidate vector. The corresponding rectangular window is centered on the source frame on the pixel where the candidate vector originates. Then, a pair of absolute differences of the corresponding brightness pixels of the two windows (that is, pixels with the same relative position in the two windows) are calculated. The sum of all absolute differences is the SAD value. The SAD decreases as the window matching becomes better. When the pixels are the same, it is ideally zero. In fact, of course, due to noise and other factors, the best vector has a non-zero SAD, but the set of candidate vectors has the smallest SAD of the vector.

After the minimum SAD finds the best vector, that is, the vector with the minimum SAD (210f) is selected and stored in the memory (step 106). The process then checks whether there are any higher resolution levels (step 108). As mentioned above, in this example, there are two higher resolution levels, so the best vector (210f) is projected to the 1:2 resolution level of FIG. 3 (step 110). After projecting to the 1:2 level, a set of update vectors (305a-305d) are generated next to the best vector (210f) (step 104). At this level, the second set of update vectors (310a-310d) are also generated next to the old 1:1 filter vector (205) projected to the 1:2 resolution level. Calculate the minimum SAD among all update vectors to find the new best vector (305a), as in the 1:4 resolution level. Then the best update vector is selected and stored in the memory (step 106).

The process then checks again whether there are any higher resolution levels (step 108). At this time, a higher resolution level remains in the resolution pyramid, so the process returns to step 104 again, where the best vector (305a) of the 1:2 resolution level in Figure 3 is filtered and projected to the highest in Figure 4 1:1 resolution level. A set of update vectors (405a-405d) are generated next to the best vector (305a) for projection and filtering (step 104). At this level, the second set of update vectors (410a-410d) are also generated next to the old 1:1 filter vector. The third set of update vectors (420a-420d) are generated next to the camera vector (415).

The camera vector depicts the global motion of the content of the frame, compared to the local vector of each image repair position that is calculated completely independently, so it can be used to help find a better true motion vector. In several co-occurring situations, the movement vector of the camera movement derived from each position of the frame can be easily predicted by a simple model. For example, if the camera lens shoots a landscape across the distance, all movement vectors are the same and equivalent to the camera speed. Another situation is when the camera lens is zoomed on an object on a flat surface, such as a photo on a wall. Then all motion vectors have a radial direction, increasing from zero at the center of the image to the maximum at the periphery of the image.

In one embodiment, the processing attempts to apply a mathematical model to the movement vector, using the least square method to calculate it. The good cooperation between the camera movement vector and the mathematical model indicates that one of the above situations may exist, and then the camera model prediction vector can be used as another candidate vector for the next regression level vector estimation step. Considering the camera vector, the regression part of the regression hierarchy search is a local search measure, which can converge to a false local minimum instead of a true minimum. Candidates for camera prediction vectors may help avoid detecting false local minimums and direct processing to true minimums.

Then find the new best vector (405d), like the resolution level of 1:4 and 1:2 (step 106), and store it in the memory. The process then checks again whether there are any higher resolution levels (step 108). At this time, there is no higher resolution level, so the process proceeds to step 112, where the best vector is selected and used for motion compensation to complete the processing of the current frame.

Perform the above processing on all 4x4 image repairs of the pixels of the frame. According to the determined motion vector, frame interpolation can be done between the source frame and the target frame, so there is no difference between the expected image movement of the eye tracking and the display image movement. difference.

It can be seen from the above that the present invention provides a smooth and accurate vector image field, and only uses a small amount of calculations fairly. Furthermore, the convergence delay is reduced due to the multiple levels of resolution. Compared with traditional measures, fewer resolution levels can be used, and the vector error of the lower level is not amplified due to the change of the resolution of the higher resolution level.

The present invention can be implemented in digital electronic circuits, or computer hardware, firmware, software, or a combination thereof. The device of the present invention can be implemented in a computer program product of a machine-readable storage device and executed by a programmable processor; the method steps of the present invention can be performed by a program processor that executes an instruction program, computing input data and generating output to perform the present invention Function. The present invention can be implemented in more than one computer program, can be executed on a programmable system including at least one programmable processor, and receives and transmits data and instructions to a data storage system, at least one input device, and at least one output device. Each computer program can be implemented in a high-level program or object-oriented programming language, or a combination or machine language; in any case, the language can be a compiled or interpreted language. Suitable processors include general and special purpose microprocessors. Generally, the processor receives commands and data from read-only memory and/or random access memory. Generally, a computer contains more than one mass storage device to store data files; this device includes disks such as internal disks and removable disks; magneto-optical disks; optical disks. Storage devices suitable for the implementation of computer program instructions and data include all forms of non-volatile memory, including semiconductor memory devices such as EPROM, EEPROM, and flash memory devices; disks such as internal disks and removable disks ; Magneto-optical disc; CD-ROM disc. Both can be incorporated into ASIC (Special Application Integrated Circuit).

FIG. 5 shows a computer system 500 used to implement the present invention. The computer system 500 is only an example of a graphics system that can implement the present invention. The computer system 500 includes a central processing unit (CPU) (510), a random access memory (RAM) (520), a read-only memory (ROM) (525), one or more peripherals (530), and a graphics controller (560). ), main storage device (540 and 550), digital display unit (570). ROM is used to transfer data and instructions to the CPU (510) in one direction, while RAM (520) is usually used to transfer data and instructions in a two-way manner. The CPU (510) can generally contain any number of processors. The two main storage devices (540 and 550) can include any suitable computer-readable media. The secondary storage medium (580), which is usually a large number of memory devices, is also bidirectionally coupled to the CPU (510) to provide additional data storage capacity. The mass memory device (580) is a computer-readable medium that can be used to store programs including computer code, data, and the like. Generally, the mass memory device (580) is a storage medium such as a hard disk or tape, which is usually slower than the main storage device (540, 550). The mass memory storage device (580) can be in the form of a card reader or some other known devices. In appropriate circumstances, the information held in a large number of memory devices (580) can be incorporated as part of RAM (520) as virtual memory.

The CPU (510) is also coupled to more than one input/output device (590), which may include, but is not limited to, monitors such as video devices, trackballs, mice, keyboards, microphones, touch displays, card readers, tape readers Computer, tablet, voice or handwriting recognizer, or other known input devices such as other computers. Finally, the CPU (510) can be selectively coupled to a computer or a communication network, for example, the Internet or an internal network, using a network connection such as (595). With this network connection, the CPU (510) can receive information from the network, or can output information to the network during the process of performing the above method steps. Communication represents this information of a sequence of instructions to be executed by the CPU (510), which can be received from and output to the network, for example, in the form of a computer data signal on a carrier wave. Those who are familiar with computer hardware and software skills are familiar with the above-mentioned devices and materials.

The graphics controller (560) generates image data and corresponding reference signals, and provides them to the digital display unit (570). The image data can be generated based on pixel data received from the CPU (510) or external code (not shown). In one embodiment, the image data is in RGB format, and the reference signal includes VSYNC and HSYNC signals. However, the present invention can be implemented with data and/or reference signals in other formats.

The present invention can be modified in many ways by those who are familiar with the craftsmanship, but none of them deviates from the protection of the scope of the patent application. For example, in addition to the hierarchy and temporary vectors of the middle layer, the vectors generated by the camera model can also be used as candidates for SAD calculations. Furthermore, the motion vector generated above can be used for other purposes besides frame rate conversion, such as de-interlacing, noise reduction, and so on.

<p>400Grid</p><p>205Motion vector</p><p>210aUpdate vector</p><p>210bUpdate vector</p><p>210cUpdate vector</p><p>210dUpdate vector</p><p>210eUpdate vector</p><p>210fUpdate vector</p><p>305aUpdate vector</p><p>305bUpdate vector</p><p>305cUpdate vector</p><p>305dUpdate vector</p><p>310aUpdate vector</p><p>310bUpdate vector</p><p>310cUpdate vector</p><p>310dUpdate vector</p><p>405Image Repair</p><p>410round</p><p>415Dark pixels</p><p>405aUpdate vector</p><p>405bUpdate vector</p><p>405cUpdate vector</p><p>405dUpdate vector</p><p>410aUpdate vector</p><p>410bUpdate vector</p><p>410cUpdate vector</p><p>410dUpdate vector</p><p>420aUpdate vector</p><p>420bUpdate vector</p><p>420cUpdate vector</p><p>420dUpdate vector</p><p>500Computer system</p><p>510Central Processing Unit</p><p>520Random access memory</p><p>525Read only memory</p><p>530surroundings</p><p>560Graphics Controller</p><p>540Main storage device</p><p>550Main storage device</p><p>570digital display unit</p><p>580Secondary storage device</p><p>590Input/Output Device</p><p>595Internet</p>

Figure 1 shows a flow chart of the regression hierarchy process for determining the movement vector.

Figure 2 shows an example of determining the best motion vector with a resolution of 1:4 of the original resolution of the video frame.

Figure 3 shows an example of determining the best motion vector with a 1:2 resolution of the original resolution of the video frame.

Figure 4 shows an example of determining the best motion vector based on the original resolution of the video frame.

Figure 5 shows a computer system used to implement the present invention.