KR100780124B1 - Encoding and Decoding of Images - Google Patents

Abstract

Some embodiments provide a method for encoding first set pixels of a first image with reference to a second image of a video sequence. In a first search window in the second image, the method searches to identify a first specific portion of the second image that best matches the first set of pixels of the first image. In a first search window in the second image, the method identifies a first location corresponding to the first specific portion. In a second search window in the second image, the method then searches to identify a second specific portion of the second image that best matches the first set of pixels of the first image, wherein the second The search window is defined near the first position.

Video sequence, image, pixel, interblock, encoding, decoding, matching, search window, position

Description

Encoding and decoding of images {ENCODING AND DECODING IMAGES}

The present invention relates to a method of encoding and decoding images.

Video codecs are compression algorithms designed to reduce the size of streams by encoding (ie, compressing) and decoding (ie, decompressing) video data streams for faster transmission and smaller storage space. Although lossy, current video codecs seek to maintain video quality while compressing the binary data of the video stream.

A video stream is typically formed by a sequence of video frames. Video encoders usually divide each frame into several macroblocks, where each macroblock is a set of 16 × 16 pixels. Video encoders typically encode video frames or macroblocks within video frames using intraframe encoding or interframe encoding. An intra frame encoded frame or macroblock is an encoded frame or macroblock independent of other frames or macroblocks of other frames.

An interframe encoded frame or macroblock is a frame or macroblock that is encoded with reference to one or more other frames or macroblocks of other frames. Interblock encoding is typically time consuming because the encoding must compare macroblocks or partitions within macroblocks of a particular frame to macroblocks or partitions within macroblocks of another reference frame. Therefore, the industry needs more efficient interblock encoding methods. Ideally, these encoding methods would accelerate encoding and decoding operations.

Some embodiments provide a method for encoding a first set of pixels of a first image with reference to a second image of a video sequence. In a first search window in the second image, the method searches to identify a particular first portion of the second image that best matches the first set of pixels of the first image. In a first search window in the second image, the method identifies a first location corresponding to the particular first portion. In a second search window of the second image defined near the first position, the method then determines to identify a particular second portion of the second image that best matches the first set of pixels of the first image. Search.

Some embodiments provide a method for interblock encoding of images of a video sequence. Each image of the video sequence has several integer pixel locations, each integer pixel location having one or more image values (eg, luminance values). The method selects a first image for encoding with reference to the second image. The method then identifies a set of non-integer pixel locations of the second image that match the set of pixels of the first image. This identification involves interpolating image values associated with non-integer pixel positions of the second image from image values for some integer pixel positions of the second image. The method stores interpolated image values of non-integer pixel positions for subsequent use while encoding the third image with reference to the second image.

Some embodiments provide a method for interblock decoding images of a video sequence. Each image of the video sequence has several integer pixel positions, each integer pixel position having one or more image values (eg, luminance values). The method selects a first image for decoding with reference to the second image. The method then identifies the first image. The method then interpolates the image values associated with the non-integer pixel positions of the second image from the image values for some integer pixel positions of the second image. The method stores interpolated image values of non-integer pixel positions for subsequent use while decoding the third image with reference to the second image.

Some embodiments provide a method for interblock processing a first portion of a first image with reference to a second image in a sequence of video images. The method divides the second image into a set of tiles and stores the tiles in the first non-cache memory storage. Each time a sub-set of tiles is needed to match the first portion of the first image with the second image portion, the method retrieves the sub-set of tiles from the first non-cache memory storage, and the first portion. And for a quick comparison between the second image portions that are part of the retrieved subset of tiles, store the retrieved subset of tiles in a second cache memory storage. The retrieved sub-set of tiles is smaller than the full set of tiles.

In some embodiments, the method identifies a tile when identifying the location of the second image, corresponding to a sub-set of tiles, to be searched to identify a second image portion that matches the first portion. To determine if a subset of these needs to be retrieved and stored in the second cache memory storage. In some embodiments, cache memory storage is a computer's RAM, while non-cache memory storage is a computer's non-volatile storage. Also, while the interblock processing method is an interblock encoding method in some embodiments, it is an interblock decoding method in other embodiments. Further, the set of tiles in some embodiments includes two or more horizontally adjacent tiles and two or more vertically adjacent tiles.

Some embodiments provide a method of selecting a first search pattern from a set of search patterns that each define a pattern for inspecting second image portions that may match the first set of pixels, thereby selecting a first search pattern of the first video image. An interblock encoding method for encoding first set of pixels is provided. This encoding method adaptively selects a first search pattern in a set of search patterns based on a set of criteria. The set of criteria in some embodiments includes the media type of the video image.

The novel features of the invention are set forth in the appended claims. However, for illustrative purposes, some embodiments of the invention are described in the following figures.

1 presents a process conceptually illustrating the flow of an encoder using several novel pruning techniques to simplify its encoding process.

2 shows a process for performing a two-step motion-prediction operation to identify a motion vector specifying the motion of a macroblock between one or two reference frames and the current frame.

3 illustrates a method in which some embodiments arrange a first search window near a position of a reference frame corresponding to a macroblock position in a current frame.

4 illustrates one way of identifying a first search window position based on a predicted motion vector associated with a macroblock of the current-frame.

5 shows an example of multiple starting points in the first search window.

6 shows an example of a second stage search window.

7 shows a refined motion estimation process performed to identify a set of partitions of pixels in a reference-frame that best matches a set of partitions of pixels of the current-frame macroblock.

8 conceptually illustrates a search window with several location points.

9 conceptually illustrates a process for searching for a partition of pixels for a reference-frame macroblock at the multiple pixel level.

10 conceptually illustrates some possible partition (ie, block) sizes.

11 conceptually illustrates several search locations for different pixel levels.

12 conceptually illustrates a macroblock of the current-frame that is aligned with sub-pixel positions in the reference frame.

13 conceptually illustrates several frames that include motion vectors pointing to the same frame.

14 conceptually illustrates how data (eg, integers, non-integers) about a set of pixels may be stored in a cache.

15 shows a low-density search pattern in a search window.

16 shows a high-density search pattern in a search window.

17 shows an example of a search pattern biased in the vertical direction.

18 shows an example of a search pattern biased in the horizontal direction.

19 shows a process for selectively checking a sub-set of motion-prediction solutions to identify motion-prediction solutions that need to calculate an RD cost.

20 illustrates a computer system in which some embodiments of the present invention are implemented.

In the following detailed description of the invention, several details, examples and embodiments of the invention are described and described. However, it will be apparent to one skilled in the art that the present invention is not limited to the described embodiments, and that the present invention may be practiced without some of the specific details and examples discussed.

1. Overview

Some embodiments of the present invention provide a novel interblock encoding and decoding process. These novel processes include (1) a multi-stage motion estimation process, (2) an interpolation caching process for caching non-integer pixel position values of a reference frame, and (3) a subset of tiles of the reference frame. A tile caching process for caching the set, and (4) a motion prediction process for adaptively selecting a search pattern for use in the search in the reference frame.

A. Multistage motion  prediction

The multi-stage motion prediction process of some embodiments encodes the first set of pixels of the first image with reference to the second image of the video sequence. In the first search window in the second image, the motion prediction process searches to identify a particular first portion of the second image that best matches the first set of pixels of the first image. In the first search window in the second image, the motion prediction process identifies a first location corresponding to the particular first portion. In a second search window in the second image, the motion prediction process then searches to identify a particular second portion of the second image that best matches the first set of pixels of the first image, in which case the first Two search windows are defined near the first position. In some embodiments, the first search is a coarse motion prediction process, while the second search is a refined motion prediction process. Further, in some embodiments, the granular motion prediction process searches for variable block sizes.

B. Interpolation Caching

The encoder of some embodiments of the present invention interblock encodes images of a video sequence. Each image of the video sequence has several integer pixel positions, each integer pixel position having one or more image values (eg, luminance values). The encoder refers to the second image to select the first image for encoding. The encoder then identifies a set of non-integer pixel locations of the second image that match the set of pixels of the first image. This identification involves interpolating image values associated with non-integer pixel positions of the second image from image values for some integer pixel positions of the second image. The encoder stores interpolated image values of non-integer pixel locations in an interpolation cache for subsequent use while encoding a third image with reference to the second image.

The decoder of some embodiments of the present invention uses a similar interpolation cache. In detail, the decoder selects a first image for decoding with reference to the second image. Next, the decoder identifies a set of non-integer pixel positions of the second image corresponding to the set of pixels of the first image. The decoder then interpolates the image values associated with the non-integer pixel positions of the second image from the image values for some integer pixel positions of the second image. The decoder stores interpolated image values of non-integer pixel positions for subsequent use while decoding the third image with reference to the second image.

C. Tile Caching Process

Some embodiments use a tile caching process for interblock processes that process a first portion of a first image with reference to a second image in a sequence of video images. This caching process divides the second image into a set of tiles and stores the tiles in the first non-cache memory storage. Each time a sub-set of tiles is needed to match the first portion of the first image to the second image portion, the caching process retrieves the sub-set of tiles from the first non-cache memory storage, and the first portion. And store the retrieved sub-set of tiles in a second cache memory storage for quick comparisons between the second image portions that are part of the retrieved subset of tiles. The retrieved sub-set of tiles is smaller than the full set of tiles.

In some embodiments, the caching process, when the caching process identifies a location of a second image to search to identify a second image portion that matches the first portion, a sub-set of tiles is retrieved to generate a second Determine if it needs to be stored in cache memory storage, where the location so identified corresponds to a subset of tiles. In some embodiments, cache memory storage is a computer's RAM, while non-cache memory storage is a computer's non-volatile storage. Further, the interblock process is in some embodiments the encoding process of the interblock, while in other embodiments the interblock decoding process. Further, the set of tiles in some embodiments includes two or more horizontally adjacent tiles and two or more vertically adjacent tiles.

D. Adaptive search  pattern

The motion prediction process of some embodiments of the present invention is directed to selecting a first search pattern from a set of search patterns that each define a pattern for inspecting second image portions that may match the first set of pixels. By encoding the first set of pixels of the first video image. The motion prediction process adaptively selects a first search pattern in a set of search patterns based on a set of criteria. The set of criteria in some embodiments includes the media type of the video image.

Before describing the novel interblock encoding and decoding processes mentioned above, the following will first describe the overall flow of the encoding process including the interblock encoding process of the present invention.

II. Overall flow

FIG. 1 presents a process 100 conceptually illustrating the flow of an encoder using several novel pruning techniques to simplify its encoding process. Some embodiments do not use all of the pruning techniques described in this section. In addition, some embodiments use these vestibular techniques in conjunction with the multi-stage motion prediction operations described below in section II.

As shown in FIG. 1, process 100 begins by determining whether to ignore encoding (in step 105) a macroblock into an interblock. In some embodiments, the process ignores interblock encoding under certain circumstances. These circumstances include placing the encoder in a debugging mode that requires coding each frame as an intrablock, indicating an intrablock refresh requiring coding some macroblocks as intrablocks, and intrablock encoding finally An implementation to be selected, an implementation in which too few macroblocks are intrablock encoded, or some other indication that requires a macroblock to be coded into an intrablock.

If process 100 determines that the macroblock does not need to be encoded as an interblock, process 100 transitions to step 110. In step 110, the process encodes the macroblock into an intrablock. A number of new ways to perform intrablock encoding are described in a US patent application entitled "Selecting Encoding Types and Predictive Modes for Encoding Video Data" with Attorney Docket APLE.P0078 ("Intrablock Encoding Application"). Such US patent applications are incorporated herein by reference.

After the process encodes the macroblock into an intrablock (in step 110), the process transitions to step 150 to indicate an encoding solution. In this case, the process indicates the intracoding result of the process in step 110, because this is the only encoding that process 100 checked on this path through the flow. After step 150, process 100 ends.

Alternatively, if process 100 determines (in step 105) that process 100 should not ignore (i.e. pruning) the interblock encoding, then the process (in step 115) skips the skip mode encoding of the macroblock. And if necessary, direct mode encoding of the macroblock. In skip mode encoding, the macroblock is coded as a skipped macroblock; On the decoder side, this macroblock will be decoded with reference to the motion macros of the neighboring macroblocks and / or partitions within the neighboring macroblocks. Skip mode encoding is further described in a U.S. patent application filed under the name "Pruning During Video Encoding" with Attorney Docket APLE.P0073 ("Pruning Application"). This application is incorporated herein by reference. In direct mode encoding, direct mode encoding is similar to skip mode encoding except that some of the macroblock's texture data is quantized and transmitted with the encoded bit stream. In some embodiments, direct mode encoding is performed for B-mode encoding of a macroblock. Some embodiments may perform direct mode encoding even during P-mode encoding. After step 115, process 100 determines (at step 120) whether skip mode encoding has generated the best encoding solution at step 115. This would obviously be the case when direct mode encoding is not performed in step 115. On the other hand, if direct mode encoding is performed in step 115 and this encoding resulted in a better solution than skip mode encoding, the process transitions to step 135 to perform intercoding, which will be described later.

However, if the process (in step 120) determines that the skip mode encoding produced the best result in step 115, the process determines (in step 125) whether the skip mode encoding was good enough to terminate the encoding. One way to make this determination is described in the aforementioned Pruning Application.

If the process determines (at step 125) that the skip mode encoding was good enough, process 100 transitions to step 130, where the process determines whether the skip mode encoding solution should be discarded. Some embodiments determine solutions based on an encoding cost called a rate-distortion cost. As described below in section II, the RD cost of the encoding solution often accounts for distortion in the encoded macroblock and counts the actual bits that will be generated for the encoding solution. Skip mode solutions sometimes can still be poor solutions, despite having significant RD costs. This is because these solutions have very small rate costs and these rate costs sometimes deviate from the total RD costs by a size sufficient to make the bad solution appear to be the best solution.

Thus, even after selecting the skip mode encoding solution in step 125, process 100 determines (step 125) whether the skip mode solution should be removed. In some embodiments, the criterion for making this determination is whether the distortion for skip mode encoding of the current macroblock is greater than twice the maximum distortion for adjacent neighboring macroblocks of the current macroblock.

If the process determines (at step 130) that the skip-mode solution should not be removed, the process transitions to indicate the encoding solution. In this case, the process indicates the result of the skip-mode encoding. After step 150, process 100 ends. On the other hand, if process 100 determines (at step 130) that the skip-mode encoding solution should be removed, the process transitions to step 135. The process transitions to step 135 even if the process determines (at step 125) that the skip mode solution is not good enough to terminate the encoding.

In step 135, the process checks various interblock encodings. In some embodiments, process 100 may include various macroblock and sub-macroblock encodings (eg, 16 × 16, 8 × 16, 16 × 8, 8 × 8, 8, as discussed in section II). X4, 4x8, and 4x4 B-mode and P-mode encodings). However, as described in the aforementioned Pruning Application, some embodiments may interleave (i.e. ignore) the inspection and / or analysis of some of the macroblock or sub-macroblock encoding modes. To accelerate.

After performing interblock encoding in step 135, the process (in step 140) determines whether the interblock encoding of the macroblock is good enough to ignore the intrablock encoding of the macroblock. Different embodiments perform this determination differently. Some of these approaches are discussed in Section II below.

If process 100 determines (in step 140) that intrablock encoding should be performed, the process transitions to step 145, where the process performs this encoding. As mentioned above, several new specifications for intrablock encoding of this process are described in the aforementioned Intrablock Encoding Application. After step 145, the process transitions to step 150. The process transitions to step 150 even if the process determines (in step 140) that the intrablock should be ignored.

As described above, the process directs (at step 150) an encoding solution for the macroblock. If process 100 identifies multiple encoding solutions during the processing operation prior to step 150, the process selects one of these solutions (at step 150). In some embodiments, process 100 selects the solution with the best RD cost. Some examples of RD costs are provided below. After step 150, the process ends.

III. Interblock  Encoding

A. Multistage motion  prediction

As described above, some embodiments use multistage motion prediction computation in conjunction with the process 100 shown in FIG. In some embodiments, multistage motion prediction operations are performed when the macroblocks are interblock encoded. As described below, some multistage motion prediction operations include coarse motion prediction and granular motion prediction. In some embodiments, process 100 is performed after an initial coarse motion prediction operation. However, one skilled in the art will appreciate that an initial coarse motion prediction operation may be performed during the process 100 (eg, at step 140 between steps 105 and 115).

1. Overall flow

2 shows a process for performing a multi-stage motion-prediction operation to identify a motion vector specifying a macroblock motion between one or two reference frames and a current frame. To clarify the discussion of the multi-stage motion prediction operation of the present invention, process 200 is described below in terms of finding the location of the current-frame macroblock in one reference frame. However, one skilled in the art will appreciate that this process usually examines two reference frames to identify the best motion-prediction encoding for the macroblock.

The first step of this process is an approximate search (eg, approximate motion prediction) that identifies an approximate approximation to the location of the current-frame macroblock in the reference frame, while the second step is a current-frame in the reference frame A more refined search (eg, refined motion prediction) that identifies a more accurate approximation of the location of the macroblock.

The process first performs a first search of the reference frame for the macroblock that best matches the current-frame macroblock (in step 210). The first search is performed in the first search window in the reference frame. Different embodiments identify the location of the first search window differently. For example, as shown in FIG. 3, some embodiments place the first search window 300 near the location 310 of the reference frame corresponding to the location 320 of the macroblock 330 of the current frame.

Other embodiments place the first search window at the location predicted for the current-frame macroblock in the reference frame. 4 illustrates one way of identifying a first search window location based on a predictive motion vector associated with a current-frame macroblock. 4 shows a current-frame macroblock 410 of the current frame 400. This figure also shows a prediction vector 420 associated with the current-frame macroblock 410. This predictive motion vector 420 may be calculated based on the motion vectors of the macroblocks adjacent to the current-frame macroblock 410 of the current frame. As shown in FIG. 4, the predictive motion vector 420 points to the location point 460 of the current frame 400 corresponding to the location 440 of the reference frame 430. Thus, as further shown in FIG. 4, some embodiments place the first search window 450 of the reference frame 430 near the location point 440.

The process 200 (at step 210) may roughly identify within the first search window to identify a motion vector that specifies how much the current-frame macroblock has moved since the current-frame macroblock appeared in the reference frame. Perform a search. The process can identify this motion vector by searching for a reference-frame macroblock in the first search window that most closely matches the current-frame macroblock. It is not necessary for the process to examine all the reference-frame macroblocks in the search window, but it is sufficient to determine that it falls within certain predefined parameters.

After the process has identified enough reference-frame macroblocks, the process (in step 210) identifies the best reference-frame macroblock that the process will find during this approximate search. The process then uses the best reference-frame macroblock identified (in step 210) to specify a motion vector that indicates an approximate approximation to the position of the current-frame macroblock in the reference frame.

After step 210, the process (in step 220) determines whether the process has sufficiently repeated the coarse search in the first search window. Some embodiments perform only one search within this window. In such embodiments, the process 200 does not need to make a determination at step 220, but instead proceeds directly from step 210 to step 230. Alternatively, other embodiments perform multiple searches starting at different multiple points in this window.

If the process 200 determines (at step 220) that the process should perform another coarse search within the first search window, the process is at a different location than the previous coarse searches performed at step 210 for the macroblock. Return to step 210 to perform another search (within this window) to begin.

5 shows an example of multiple starting points in the first search window. Specifically, the figure shows four starting points 510-540 in the first search window 500. Each starting point 510-540 results in a search identifying different reference-frame macroblocks. In some embodiments, different starting points may identify the same reference-frame macroblocks.

Once the process has determined (in step 220) that the process has sufficiently repeated the approximate search in the first search window, the process (in step 230) identified through one or more process iterations through step 210, the best possible Identify an approximate step solution. This solution identifies, as shown in FIG. 6, the motion vector 620 that identifies the position 610 for the macroblock 410, corresponding to the position 630 of the reference frame, in the current frame.

Next, the process performs a second refined motion-estimation search for the reference-frame macroblock that matches the current-frame macroblock (at step 240). The second search is performed in the second search window of the reference frame. In some embodiments, this second search window is smaller than the first search window used during the approximate first-stage search in step 210. Further, in some embodiments, the second search window is defined near a position in the reference frame, identified by the motion vector generated by the first stage search (ie, by the motion vector selected in step 230). 6 shows an example of such a second stage search window. Specifically, this figure shows a second search window 640 near the location point 630 specified in the first search.

In some embodiments, the search process used during the second search phase (at step 240) is more thorough than the search process used during the first search phase. For example, some embodiments use exhaustive sub-macroblock search using rate distortion optimization during the second stage, while simpler 3- during the first search stage. Use simpler three-step search.

At the end of the second search step in step 240, process 200 provides a motion vector specifying how much the current-frame macroblock has moved since appearing in the reference frame. After step 240, the process ends.

2. Subdivided motion  prediction

7 shows a granular motion prediction process 700 performed to identify a set of partitions of pixels of a reference-frame that best matches a set of partitions of pixels of the current-frame macroblock. In some embodiments, process 700 is implemented during a second search (in step 240) of process 200.

As shown in this figure, process 700 selects a location point within the search window (at step 705). In some embodiments, the search window is initially defined near the reference-frame macroblock identified in step 230 of process 200.

8 conceptually illustrates a search window 800 with several location points. As shown in this figure, the search window 800 includes nine location points 805-845. In some embodiments, these location points 805-845 may be generated randomly. In other embodiments, these location points 805-845 are pre-determined by a set of criteria. Each of these location points 805-845 corresponds to an integer pixel level reference-frame macroblock. 8 also shows location points of non-integer pixel levels (ie, sub pixel level), such as location points of 1/2 and 1/4 pixel levels. The use of these sub pixel level location points will be discussed with reference to FIG. 9.

Next, for each possible partition of pixels in the current-frame macroblock, process 700 (in step 710) determines how close a particular partition of pixels at the selected location point is to the partition of pixels of the current-frame macroblock. Is matched correctly. 10 conceptually illustrates some possible partition (ie, block) sizes. Specifically, this figure shows nine possible block sizes, where each block size represents a particular block of pixels. For example, block size 1 represents a block of pixels that contains a 16x16 array of pixels. Block size 2 represents a block of pixels comprising a 16x8 array of pixels. Although this figure shows only nine block sizes, process 700 may search for block sizes with other pixel configurations. Some embodiments search for all of these block sizes, while other embodiments may search for only some of these block sizes.

Once the check is performed (at 710), process 700 updates the reference-frame macroblock for each block size (in step 715) to the best location. Process 700 determines (at 720) whether another location point exists. If so, process 700 proceeds to step 705 to select another location point and performs another iteration of steps 710-720.

Once the process 700 determines (at step 720) that there are no more location points, the process 700 determines (at step 725) whether the search results for certain block sizes are good enough. . In some embodiments, if the block size of the updated location meets certain criteria (eg, SAD below a certain threshold), the search result is good enough. In some embodiments, if the difference between the cost associated with the particular block size and the cost associated with the lowest cost is greater than the threshold, the search result is not good enough. In some embodiments, the threshold is dynamically defined during the search. If process 700 determines (at step 725) that the search results for certain block sizes are not good enough, process 700 excludes these block sizes from any subsequent searches (at step 730).

After excluding these block sizes (at step 730) or after determining that all the search results are good enough (at step 725), the process 700 performs another search (at step 735). During this search, for each block size, process 700 searches in the reference frame a partition of pixels that best matches the partition of the current-frame macroblock. This search includes searching for a partition of pixels at the sub-pixel level. This sub-pixel level search will be discussed further in the following. After the search phase (in step 735), the process 700 ends.

3. At the subpixel level Search

9 conceptually illustrates a process 900 for searching for a partition of pixels for a reference-frame macroblock at the multiple pixel level. In some embodiments, process 900 is performed during a search of process 700 (step 735). As shown in this figure, process 900 selects (in step 905) a partition of pixels (ie, block size) for the current-frame macroblock. Process 900 repeats several times through step 905. In the iterations of the process through step 905, the process of some embodiments is based on the numerical designations of the partitions shown in FIG. 10 in sequence, so that partitions that were not destroyed in step 730 (ie, Blocks are selected repeatedly. For example, if none of the partitions were destroyed at step 730, process 900 selects blocks 1-9 sequentially.

After step 905, process 900 defines (ie, defines the search granularity) the initial pixel resolution (eg, pixel level) of the search (at step 910). For example, process 900 may initially define that the pixel resolution is at every other location in the integer pixel (ie, half resolution of integer pixel level resolution). Next, process 900 defines the search location (at step 915) to be the best location identified so far for the selected partition of the current-frame macroblock. This best identification location may be identified during the pixel level search for process 700 of FIG. 7, or may be identified during any one of the pixel resolution searches for process 900 of FIG. 9, as further described below. Can be.

For each given current-frame partition not discarded in step 730, process 900 (in step 920) includes (1) near the search location identified in step 915 with a defined pixel level resolution (i.e., search granularity). Examine the reference-frame partitions, and (2) identify the particular reference-frame partition examined that best matches the current-frame partition.

Next, for each of the current-frame partitions not destroyed in step 730, process 900 (in step 925), the predetermined reference-frame partition identified in step 920 for the given current-frame partition. It is determined whether this is a better match than the best match previously identified for this given current-frame partition. If so, the process (in step 925) defines the location of the particular reference-frame partition identified in step 920 as the best location for the particular current-frame partition.

Next, process 900 determines (at step 930) whether the process has examined the reference frame at the maximum pixel level resolution for the selected partition. If not, process 900 (in step 935) increases the pixel level resolution to the subsequent pixel level resolution (eg, 1/2, 1/4) and returns to step 915 described above. Thus, in subsequent iterations of steps 915-935, process 900 checks the partitions of the current-frame macro block at the subpixel level (eg, 1/2, 1/4).

If process 900 determines (in step 930) that the process has examined the reference frame at the maximum pixel level resolution for the selected partition, process 900 (in step 940) indicates that the process has not been destroyed in step 730 Determine whether all frame partitions have been checked. If not, process 900 returns to step 905 to select a subsequent current-frame partition and then repeats steps 910-935 for this partition. If process 900 determines (at step 940) that the process has examined all of the partitions of pixels that have not been discarded at step 730, process 900 ends.

11 conceptually illustrates several search locations for different pixel levels. Specifically, this figure shows the search area 860 bounded by four integer pixel level positions 825-830 and 840-845. In some embodiments, this bounded search area 860 is disposed within the search window 800, as shown in FIG. 8.

There are five half pixel level locations within the boundary search area 860. In addition, there are sixteen quarter pixel level locations within this bounded search area 860. Different embodiments may specify different boundary search areas that include more or less integer and non-integer positions. If process 900 defines (at step 915) the search location to be location 850, some embodiments may search at and around this bordered area 860 during the search at step 920. .

In some embodiments, the above-described steps are repeated several times. As mentioned above, some embodiments perform separate searches for each pixel level. However, one of ordinary skill in the art would appreciate that some embodiments may search for several block sizes at the same time at different pixel levels for each search location (ie, for each location an integer, 1 / for all block sizes). One may search simultaneously at 2 and 1/4 pixel levels. Although the sub pixel levels are described as half and quarter pixel levels, those skilled in the art will appreciate that the sub pixel level may be any non-integer pixel level.

Process 700 also describes (at step 725) determining whether the search results for a given block size (s) are good enough. In some embodiments, this determination 725 may also be performed during process 900. Those skilled in the art will also appreciate that such a determination 725 may be performed during different steps of processes 700 and 900. For example, this determination process 725 may be performed after finding the best location of each block size.

In addition, some embodiments may not perform a search at step 735 during process 700. In addition, although the processes 700 and 900 describe performing searches for a reference-frame macroblock, those skilled in the art will appreciate that processes 700 and 900 may be implemented in other types of pixel arrays (eg, 16). It will be appreciated that it may be used to search for x8 sub-macroblocks).

B. Of interpolation values  Caching

12 conceptually illustrates several pixel and sub-pixel positions in a reference frame. These sub-pixel positions include half and quarter pixel positions. As further shown in this figure, the macroblock 1200 of the current-frame is aligned with ½ sub-pixel positions 1205 (ie, the pixel positions of the current frame macroblock are 1 in the reference frame). / 2 sub-pixel positions and aligned in a row).

As mentioned above, the encoder checks macroblocks or macroblock partitions that are aligned with sub-pixel positions of the reference frame (ie, not aligned with pixel positions) during the motion prediction operation of some embodiments. From the reference frame, the decoder of some embodiments may in some cases need to search for macroblocks or macroblock partitions that are aligned by sub-pixel positions (ie, not aligned by pixel positions).

Inspection and retrieval of macroblocks or macroblock partitions that are aligned with sub-pixel positions requires that the encoder or decoder correspond to the pixel positions of the current frame during the decoding operation and to the pixel positions of the current frame during the encoding operation. Generating image values (eg, luminance values) for the reference frame at the sub-pixel locations.

In some embodiments, generating image values corresponding to the sub-pixel positions may comprise interpolating the image values from the image values of neighboring pixel positions (ie, for the sub-pixel position from the image values of the pixel positions). Deriving an image value). In many cases, interpolating the image value for the sub-pixel position is a difficult operation (eg, computationally intensive operation) involving more than just a mean of the image values of the two nearest pixel positions. Thus, some embodiments may be easily retrieved if the interpolated image value for the sub-pixel position is to be examined by a subsequent search of another current frame partition to check the interpolated image value mentioned above for the sub-pixel position. Store it in a cache. Some embodiments store all interpolated values in the cache, while other embodiments store only some of the interpolated values in the cache.

During encoding and / or decoding operations, multiple motion vectors for the set of current-frame macroblocks will point to the same reference frame. For example, as shown in FIG. 13, frame 1310 has motion vectors defined with reference to frames 1305 and 1325. Also, both frames 1315 and 1320 have motion vectors defined with reference to frame 1305. Thus, in some cases, a reference frame may be used to encode or decode one or more other frames. Thus, since interpolated sub-pixel values for a reference frame may be used for encoding of other frames, it is desirable to cache all or some of them.

C. cache Tiling (Cache Tiling)

14 conceptually illustrates a method for storing a reference frame in a cache. In some embodiments, this method is implemented with the interpolation operation described above. As shown in this figure, the reference frame 1305 is divided into several tiles 1430. In some embodiments, frame 1305 is divided in a manner that includes two or more columns of tiles and two or more rows of tiles.

14 also shows pixel block 1450, which may or may not be aligned with pixel positions of the reference frame. Pixel block 1450 represents the portion of the reference frame to be examined during the encoding operation (ie, during motion prediction) or to be retrieved during the decoding operation.

As shown in FIG. 14, portions of the tiles 1430a-1430d are needed to inspect or retrieve the pixel block 1450. Thus, to facilitate inspection of pixel blocks (such as pixel block 1450) during an encoding or decoding operation, some embodiments cache the reference frame 1305 in terms of the tiles of the reference frame. In other words, instead of caching rows of pixels that extend across reference frame 1305 (eg, pixel rows 1401-1425 that include pixel block 1450), some embodiments provide a reference frame. Cache only tiles within.

If a set of tiles is needed for the analysis of a particular pixel block, the encoder or decoder of these embodiments determines whether all of the tiles that the particular pixel block overlaps are in the cache. If so, the encoder or decoder uses cached tiles to process the particular pixel block. Otherwise, the encoder or decoder retrieves (1) certain tiles from the non-cache storage (ie, tiles that overlap a particular pixel block but are not currently in the cache), and (2) retrieve these tiles into the cache. After saving, (3) use these tiles to process a specific block of pixels. For example, when attempting to process pixel block 1450, the encoder or decoder determines that the block overlaps tiles 1380a-143Od. Thus, the encoder or decoder fetches these tiles 143Oa-143Od into the cache (if these tiles are not already in the cache) and then uses these tiles to process block 1450.

In some embodiments, cache storage is a cache of a computer system processor used to perform encoding or decoding operations. In other embodiments, cache storage is a dedicated section of non-volatile memory (eg, random access memory) of a computer system used to perform encoding or decoding operations. In addition, although FIG. 14 shows quarter-shaped tiles for caching, some embodiments may use other shapes, such as rectangles, for their tiles.

D. motion  For prediction Adaptive search  pattern

Some embodiments perform searches using different search criteria during the multi-stage motion prediction operation described above. Some embodiments use a fixed search pattern when performing searches. Other embodiments may use different search patterns. For example, some embodiments adaptively select a search pattern based on certain criteria.

One example is to choose between a low-density and high-density search pattern. 15 illustrates a low density search pattern in search window 1500. This figure shows the search pattern in terms of black circles representing the locations that the pattern specifies for the search. As shown in FIG. 15, this search pattern specifies only 16 positions for the search, out of the 49 potential macroblock positions (identified by black and white circles) that can be examined. 16 illustrates a high density search pattern in search window 1500. The search pattern in this figure specifies 25 positions for search, out of 49 potential macroblock positions (identified by black and white circles) that can be examined.

Some embodiments may adaptively select between the search patterns shown in FIGS. 15 and 16 based on certain encoding results. For example, some embodiments may use the high density pattern shown in FIG. 16 for high resolution encodings (eg, HD TV encoding), while other embodiments may stream live video delivered over a network. For example, the low density pattern shown in FIG. 15 may be used.

Alternatively, some embodiments use a search pattern that emphasizes vertical search movements, while other embodiments use a search pattern that emphasizes horizontal search movements. 17 shows an example of a search pattern in a search window in which the center is located near the predicted macroblock position. This search pattern is biased in the vertical direction. If this search pattern is limited in the number of locations that can be inspected, the pattern shown in FIG. 17 is the location of the encoder's limited search budget present in vertical columns near the predicted macroblock location in the center of the search window 1500. To test them.

18 shows an example of a search pattern in a search window centered near the predicted macroblock position. This search pattern is biased in the horizontal direction. If this search pattern is limited in the number of locations that can be inspected, the pattern shown in FIG. 18 is a location where the limited search budget of the encoder exists in horizontal rows near the predicted macroblock location in the center of the search window 1500. To test them.

Some embodiments adaptively select between the two patterns shown in FIGS. 17 and 18 based on vectors of adjacent macroblocks. If most or all of them point to a particular direction (eg vertical or horizontal direction), these embodiments select the patterns shown in FIG. 17 or FIG. 18. Some embodiments provide for determining whether the absolute value of a motion vector along one direction (eg, the y-axis) is greater than the absolute value of the motion vector along the other direction (eg, the x-axis). By determining whether the motion vectors of adjacent macroblocks point in a particular direction. Some embodiments take into account the directions of motion vectors for adjacent macroblocks as well as the magnitudes of these vectors. Some embodiments also consider the motion field for a set of images in adaptively selecting a search pattern (eg, consider whether the set of images depicts movement in a particular direction).

E. RD Cost Calculations

As mentioned above, some embodiments of the present invention calculate the cost for a particular macroblock, such as a rate distortion (RD) cost, during a motion prediction operation. It is computationally intensive to induce RD costs for all possible modes during motion prediction. This is especially true given that this cost mostly involves measuring distortion and counting the actual bits to be generated. Thus, some embodiments do not calculate the RD cost for all possible modes. Instead, these embodiments reduce the number of possible modes by ranking motion-prediction solutions, selecting the top N motion-prediction solutions, and then calculating the RD cost for the selected solutions.

19 shows a process 1900 for some embodiments of the present invention. This process optionally checks a sub-set of motion-prediction solutions to identify the motion-prediction solutions for which the process needs to calculate the RD cost. In some embodiments, before this process begins, a number of encoding solutions have already been calculated. Other embodiments perform this process with encoding solutions.

The process 1900 initially sorts (at step 1910) the encoding solution based on the lowest to highest prediction errors. In some embodiments, each encoding solution generates a motion vector as well as a predicted error. Different embodiments use different metric calculations to quantify the error. For example, some embodiments use mean absolute difference (MAD) metric scores, while others use the sum of absolute differences (SAD) metric score described in the above-mentioned application. Still other embodiments use a combination of two or more metric scores.

Next, the process selects (at 1920) the top N encoding solutions from the sorted list. In some embodiments, the value of N is a predetermined number, while in other embodiments, the value of N is a dynamically generated number. Next, the process calculates (in step 1930) the RD cost for the selected top N results, selects the lowest RD cost encoding solution (in step 1940), and then terminates.

Some embodiments express the RD cost of the encoding solution as:

Where λ is the weighting factor and NB is the number of bits generated due to encoding. This RdCost quantifies the amount of data to be transmitted and the amount of distortion associated with that data.

Instead of calculating a simple RD cost, some embodiments (at step 1930) calculate a cost that not only takes into account the RD cost but also the complexity of decoding a given mode in which an encoding solution is generated. This cost can be expressed as:

,

,

Here, RdCost is calculated as in Equation 1 specified above, α is an importance factor associated with decoding complexity, and cf is a complexity factor that quantifies the amount of decoding performed on the data.

After step 1930, the process selects (in step 1940) the motion-prediction solution that resulted in the lowest cost calculated in step 1930, and then ends. In initially aligning the motion prediction operation by the initial metric score and quantifying only the cost metric for the encoding solutions with the lowest initial metric score, the process 1900 finds an acceptable result in the fastest way the process can find. Guaranteed to pay.

IV. Computer systems

20 conceptually illustrates a computer system in which some embodiments of the present invention are implemented. Computer system 2000 includes bus 2005, processor 2010, system memory 2015, read-only memory 2020, persistent storage 2025, input devices 2030, and output devices. (2035).

The bus 2005 collectively represents a system, peripheral, and chipset buses that support communication between internal devices of the computer system 2000. For example, the bus 2005 connects the processor 2010 in communication with a ROM 2020, a system memory 2015, and a persistent storage 2025.

From these various memory units, processor 2010 retrieves instructions to execute and data to process to execute the processes of the present invention. ROM 2020 stores static data and instructions needed by processor 2010 and other modules of a computer system. On the other hand, persistent storage 2025 is a read and write memory device. This device is a non-volatile memory that stores instructions and data even when the computer system 2000 is powered off. Some embodiments of the present invention use mass storage (such as magnetic or optical disks and their corresponding disk drives) as permanent storage 2025. Other embodiments use removable storage devices (such as floppy disks or zip® disks, and their corresponding disk drives) as permanent storage devices.

As with persistent storage 2025, system memory 2015 is a read and write memory device. However, unlike storage device 2025, system memory is volatile read and write memory, such as random access memory (RAM). System memory stores some of the instructions and data that the processor needs at run time. In some embodiments, the processes of the present invention are stored in system memory 2015, persistent storage 2025, and / or ROM 2020.

In addition, bus 2005 connects to input and output devices 2030 and 2035. Input devices allow a user to communicate information to a computer system and to select instructions for the computer system. Input devices 2030 include alphanumeric keyboards and cursor-controllers. Output devices 2035 display images generated by the computer system. Output devices include printers and display devices, such as cathode ray tubes (CRT) or liquid crystal displays (LCD).

Finally, as shown in FIG. 20, bus 2005 couples computer 2000 to network 2065 through a network adapter (not shown). In this way, a computer may be part of a network of computers (such as a local area network, a wide area network, or an intranet) or a network of networks (such as the Internet). Any or all of the components of computer system 2000 may be used in connection with the present invention. However, it will be apparent to one skilled in the art that any other system configuration may be used in connection with the present invention.

While the invention has been described with reference to various specific details, those skilled in the art will recognize that the invention may be embodied in other specific forms without departing from the spirit of the invention. For example, many embodiments of the invention have been described above with reference to macroblocks. Those skilled in the art will appreciate that these embodiments may be used in conjunction with any other array of pixel values.

Claims (36)

A method for encoding a first set of pixels of a first image with reference to a second image of a video sequence, the method comprising: a) in the first search window in the second image, Searching to identify a first specific portion of the second image that best matches the first set of pixels of the first image; Identifying a first location corresponding to the first specific portion; And b) in a second search window in the second image, Searching to identify a second specific portion of the second image that best matches the first set of pixels of the first image, the second search window being defined near the first location How to include. The method of claim 1, And the second search window in the second image is smaller than the first search window of the second image. The method of claim 1, Searching for identifying the first specific portion comprises searching from one or more start locations. The method of claim 1, Searching in the first search window includes a coarse search, The searching in the second search window includes a refined search. The method of claim 1, Searching in the second search window, a) identifying a plurality of search points within the second search window; b) for each particular search point, repeatedly i. Identifying a plurality of second pixel groups; ii. Calculating a motion vector metric for each identified second group of pixels; iii. Designating a best second pixel group for each of the first pixel groups; And iv. If the criteria are met, further comprising ignoring the remaining search points. The method of claim 5, a) determining whether the designated second pixel group associated with the particular pixel group has a calculated motion vector metric that exceeds a threshold; And b) after determining that the designated second pixel group associated with the particular first pixel group exceeds the threshold, excluding the particular first pixel group from subsequent searches. The method of claim 6, The threshold is dynamically defined while searching in the second search window. The method of claim 5, Searching in the second search window comprises searching at a first pixel level. The method of claim 8, Searching in the second search window further includes searching at a second pixel level, Wherein the first pixel level is an integer pixel level and the second pixel level is a half pixel level. A method for interblock encoding images of a video sequence, each image of the video sequence having a plurality of integer pixel positions, each integer pixel position having at least one image value, a) selecting a first image for encoding with reference to a second image; b) identifying a first set of non-integer pixel positions of the second image that match the pixel set of the first image, wherein the identification is performed from image values for a plurality of integer pixel positions of the second image. Interpolating image values associated with the non-integer pixel locations of a second image; And c) storing the interpolated image values of the non-integer pixel positions for subsequent use during third image encoding referencing the second image. The method of claim 10, After identifying the set of non-integer pixel positions of the second image, interpolating image values for another group of non-integer pixel positions of the second image. The method of claim 11, And the group of non-integer pixel positions is located near the first set of non-integer pixel positions. A method for interblock decoding images of a video sequence, each image of the video sequence having a plurality of integer pixel positions, each of the integer pixel positions having at least one image value, a) selecting a first image for decoding with reference to the second image; b) identifying a set of non-integer pixel locations of the second image corresponding to the pixel set of the first image; c) interpolating image values associated with non-integer pixel positions of the second image from image values for a plurality of integer pixel positions of the second image; And d) storing the interpolated image values of the non-integer pixel positions for subsequent use during third image decoding referencing the second image. The method of claim 13, After interpolating image values associated with the non-integer pixel position, further comprising interpolating image values for a group of other non-integer pixel positions of the second image. The method of claim 14, And the group of non-integer pixel positions is located near the first non-integer pixel position. A method for interblock processing a first portion of a first image with reference to a second image in a sequence of video images, a) dividing the second image into a set of tiles; b) storing the tiles in a first non-cache memory storage; c) retrieving the sub-set of tiles from the first non-cache memory storage whenever a sub-set of tiles is needed; And d) storing the subset of the retrieved tiles in a second cache memory storage between the portions of the second image that are part of the subset of the retrieved tiles and the first portion, the sub-set of the retrieved tiles Set is smaller than the full set of tiles- How to include. The method of claim 16, The method includes, when identifying a location of the second image to search to identify the second image portion that matches the first portion, a sub-set of tiles is retrieved and stored in the second cache memory storage. Determining if there is a need to be made, and the location so identified corresponds to the sub-set of tiles. The method of claim 16, Said cache memory storage is a random access memory (RAM) of a computer. The method of claim 16, And the cache memory storage is a non-volatile storage device of a computer. The method of claim 16, The interblock processing method is an interblock encoding method. The method of claim 16, The interblock processing method is an interblock decoding method. The method of claim 16, Wherein the set of tiles comprises at least two horizontally adjacent tiles and at least two vertically adjacent tiles. The method of claim 16, The tiles are sequentially stored in the cache memory storage. An interblock encoding method for encoding a first set of pixels of a first video image, the method comprising: a) selecting a first search pattern from a set of search patterns each defining a pattern for inspecting second image portions that may match the first pixel set; And b) adaptively selecting the first search pattern in the set of search patterns based on the set of criteria. The method of claim 24, Wherein the set of criteria comprises a resolution encoding of the sequence of images of media. The method of claim 24, Wherein the set of criteria comprises motion vectors of adjacent motion vectors. The method of claim 24, Wherein the set of criteria comprises a motion field for the set of video images. A method for encoding a first set of pixels of a first image with reference to a second image in a sequence of images, the method comprising: a) identifying a plurality of second pixel sets in a second image; b) calculating a first metric score for each of the second set of pixels; c) based on the first metric score, identifying a subset of second pixel sets; d) from the subset of the identified second pixel sets, i. Calculating a second metric score for each of the identified second pixel sets; And ii. Selecting the identified second set of pixels having the best second metric score, wherein the selected and identified second set of pixels best matches the first set of pixels. How to include. The method of claim 28, Each of the second pixel sets includes a plurality of second grouping of pixels, and each of the second pixel groupings includes a plurality of second group of pixels. Way. The method of claim 29, Computing the first metric score, a) calculating a first metric score for each of the second pixel groupings; And b) calculating a first metric score for each of the second group of pixels. The method of claim 30, Identifying the subset of second pixel sets comprises identifying a subset of second pixel groupings and a subset of the second pixel groups. The method of claim 31, wherein Calculating the second metric score comprises calculating a second metric score for each second pixel grouping and each second pixel group. The method of claim 32, Wherein the first metric score is a sum absolute difference (SAD) metric score. The method of claim 28, Identifying the subset of second pixel sets comprises selecting an upper N second set of pixels with the lowest first metric score. The method of claim 34, wherein The second rate metric score is a rate distortion (RD) cost that quantifies the amount of data to be transmitted and the amount of distortion associated with the transmitted data. The method of claim 28, a) calculating a third metric score for the top N second set of pixels with the lowest second metric score; And b) selecting the identified second set of pixels having the best third score, wherein the selected and identified second set of pixels best matches the first set of pixels. How to include more.

Images