Title of Invention

METHOD AND SYSTEM FOR DETERMINIG A VECTOR FOR ENCODING A PIXEL SET.

Abstract

There is disclosed a first search window (111) within a reference frame (102) of video data is identified along with a first correlation threshold value (202) for the first window (111). The first correlation threshold value (202) is a value to which correlation factors (204) between a pixel set being encoded and pixels sets (203) of the first search window (111) are compared. For example, if a correlation factor (204) between a specific pixel set (203) of the first search window (111) and a pixel set being encoded meets the first threshold value (205), a successful match between the two pixel sets has been found, and a corresponding motion vector can be assigned to the pixel set being encoded. If none of the pixel sets (203) within the first window (111) meet the first threshold value, a second search window (112) within the first frame is selected (210) along with a second correlation threshold value (204). The correlation factors for pixel sets in the second window (112) are compared to the second correlation threshold value (204).

Full Text

METHOD AND SYSTEM FOR DETERMINING A MOTION VECTOR FOR ENCODING A PIXEL, SET FIELD OF THE DISCLOSURE The present invention relates to method and system for determining a motion vector for encoding a pixel set, and pertains generally to video processing, and more particularly to a method and system of encoding video data. BACKGROUND Encoding of digital video data is generally performed in order to compress the amount of data needed to represent a video stream. It is known in the art to encode a frame one set of pixels at a time. For example, each macroblock of a frame can be encoded by comparing the macroblock's pixels to the pixels of other macroblocks of a frame that has been previously displayed, or decoded. Once a set of pixels in the previous frame that corresponds closely to the set of pixels being encoded is found, a motion vector pointing to that set of pixels is identified. Once a motion vector to the set of pixels is identified, any information difference between the two sets of pixels can be quantified and efficiently compressed. Known methods of encoding will correlate the set of pixels being encoded to sets of pixels in the previous frame or a portion of the previous frame until a correlation threshold is met. Once the correlation threshold is met, it is known that a pixel set in a previous frame that corresponds sufficiently close to the pixel set being encoded has been found. In one such technique disclosed in United States Patent 5,872,604 (Ogura), a conventional motion detection search is made in one search area and a second search is performed in a larger area. The searches are performed in parallel without one search being dependent on the other. Due to the large amount of data associated with video streams, and video frames, the encoding process can be a very time- consuming process. Therefore, a system or method capable of more efficiently encoding pixels sets would be useful. According to the present invention there is provided a method of determining a motion vector for a pixel set being encoded, said method comprising the steps of: selecting a first search window of a first frame of video data, the first search window having a first window size; determining if a pixel set associated with the first search window meets a first correlation requirement with respect to the pixel set being encoded; determining a motion vector for the pixel set being encoded when any pixel set associated with the first search window meets the first correlation requirement; and when no pixel set associated with the first search window meets the first correlation requirement: selecting a second search window of the first frame of video data, the second search window having a second window size larger than the first window size; determining if a pixel set associated with the second search window meets a second correlation requirement with respect to the pixel set being encoded, the second correlation requirement being different from the first correlation requirement; and determining a motion vector for the pixel set being encoded when any pixel set associated with the second search window meets the second correlation requirement. BRIEF DESCRIPTION OF THE ACCOMPANYING DRAWINGS [0004] Figure 1 illustrates, in block diagram form, the graphical representation of a reference frame of video data in accordance with the present disclosure; [0005] Figure 2 illustrates, in flow diagram form, a method in accordance with the present disclosure; and [0006] Figure 3 illustrates, in block diagram form, a system for implementing specific embodiments of the present disclosure. DETAILED DESCRIPTION OF THE FIGURES [0007] In accordance with the specific embodiment of the present disclosure, a first window is selected in a reference frame of video data. The first window contains one or more pixel sets, each that are to be correlated with a pixel set being encoded to determine a correlation factor. In addition, a first threshold value is determined for the first search window. The first threshold value is the value to which correlation factors are compared. For example, if a correlation factor between a specific pixel set of the first search window and the pixel set being encoded meets the first threshold value, a successful match between the two pixel sets has been found, and a corresponding motion vector can be assigned to the pixel set being encoded. [0008] If none of the pixel sets within the first window meet the first threshold value, a second search window within the first frame is selected. A second threshold value different than the first threshold value, is determined for the second search window. Typically, the second threshold value will be less stringent than the first threshold value. The correlation factors for the pixel sets of the second search window that are correlated to the pixel set being encoded are compared to the second threshold value. By using multiple search windows with varying threshold values, a more efficient encoding process can be obtained. For example, by setting the first search window to be relatively small, a faster match can be expected while maintaining a high correlation level. This provides a decoder system a mechanism to set a trade off between processing power of an encode process, and the desired quality of the encode process. Figures 1 through 4 further illustrate specific embodiments of the present disclosure. [0009] Figure 1 illustrates frames F1 102 and F2 104. Frame Fl 102 represents a reference frame with respect to the frame F2 104 that is being encoded. Frame Fl 102 is a reference frame in that the pixel data associated with frame Fl will be available, and used, at the time that pixel sets of frame F2 104 are being encoded or decoded. Therefore, during the encoding process each pixel set, such as a macroblock or a block, of frame F2 104 will be compared against a portion of Frame Fl 102 to determine whether a substantially similar set of pixels resides within Frame Fl 102. A specific embodiment of the present disclosure will be further discussed with reference to the method of Figure 2 and frame data of FIG. 1. [0010] At step 201 a first search window size and location is determined. For example, referring to Figure 1, the search window 111 is defined. The search window 111 represents an area of frame Fl 102 that has one or more pixel sets that will be correlated to macroblock F2/52. Note that F2/52 refers to the macroblock at macroblock location 52 in frame F2 104, which is the macroblock being encoded. It will be further appreciated, that within specific search windows, the searches are not constrained by specific pixel sets, such as macroblock boundaries. In other words, the pixel sets identified within a search window can reside across encoding pixel set boundaries. In one embodiment, the first search window 111 contains a single pixel set to be searched. In other embodiments, multiple pixel sets are contained with the first search window. [0011] It will be appreciated that the location of the first search window is generally be based upon a predicted motion vector. It will be appreciated that there are many method of predicting motion vectors, and how the initial location of the first search window is determined can be determined by a variety of methods. [0012] At step 202 of Figure 2, a correlation threshold is set for the first window. As the pixel set being encoded is correlated to the pixel sets of the first window a correlation factor is determined. This correlation factor is compared to the correlation threshold of the first window to determine when a successful match between the pixel sets has been found. Generally, the correlation threshold for the first window would be set relatively high, compared to other correlation thresholds, because the number of pixels sets within the first window is relatively small. Because of the relatively small number pixel sets anticipated within the first window, a somewhat higher correlation factor can be used without affecting performance. [0013] At step 203, a search window pixel set is determined. With respect to Figure 1 a single search window pixel set may be present. Regardless, one pixel set within the search window will be identified. [0014] At step 204, a correlation factor is determined between the pixel set being encoded and the search window pixel set. The correlation factor can be determined using any of a variety of correlation techniques. Such techniques can be as simple as subtracting one pixel set from the other to determine a difference between the pixel sets. Other techniques can be more complicated. For example, where the pixel set information represents spatial data, the correlation technique can perform a mathematical transform to convert the data to non-spatial pixel set data. For example, sub-sampling techniques and/or techniques that operate on frequency domain data can be used. Furthermore, it will be appreciated, that each application of the step 204, in the loop formed by steps 204-205-211-210, can apply the same correlation technique or different correlation techniques. For example, the first search window location can use a different correlation technique than a subsequent search window. [0015] At step 205, a determination is made whether or not the correlation factor meets the correlation threshold identified in step 202. If the correlation factor does meet the correlation threshold the flow proceeds to step 206 where a motion vector is used corresponding to the search window pixel set. If at step 205 the correlation factor does not meet the correlation threshold, the flow proceeds to step 211. Note that in an embodiment where the current window is to be the last window searched, the correlation threshold can be set so that it will never be met. This would allow the pixel set with the best correlation factor to be selected at step 221. [0016] At step 211a determination is made whether or not more search window pixel sets exist in the current search window. If so, the flow proceeds to step 210, otherwise the flow proceeds to step 209. [0017] At step 210, a next search window pixel set is determined within the current window. Once the next search window pixel set is determined the flow proceeds to step 204. A loop including steps 204, 205, 211, and 210 continues until all of the search window pixel sets within the current window have been correlated to the pixel set being encoded, or until a successful correlation has occurred. [0018] When no more search window pixel sets exist in the current search window the flow proceeds from step 211 to step 209. At step 209, a determination is made whether or not more search windows are to be identified. If not, the flow proceeds from step 209 to step 221 where the method of FIG. 2 selects the best pixel set location and/or terminates without a successful correlation being found. However, if additional search windows are to be identified, the flow proceeds to step 208. [0019] At step 208, a next search window size and location is determined. Referring to Figure 1, a search window 112 is the next search window identified. [0020] Step 207, a correlation threshold is set for the next search window 112. Again, with reference to Figure 1, a new correlation threshold value would be set for the window size 112. Because the window size 112 contains more pixel sets than the search window 111a less stringent correlation factor will be tolerated. In other words, to avoid a long encode time, a tradeoff in the quality of correlation is allowed. [0021] At step 203, a new search window pixel set is identified. It will be appreciated that where the first search window 111 is a subset of the new search window 112, the correlation factors associated with the pixel sets of the first search window can be maintained, without re-correlating, and compared to the new threshold value. By saving the correlation factors for the first search window only the search window pixel sets that are unique to the second search window 112 would have to be correlated, thereby saving processing time. [0022] Again in the manner previously described, the steps 204, 205, 211, and 210 will be repeated until either all of the search window pixel sets have been correlated against the pixel set being encoded, or a successful pixel set correlation has occurred. [0023] In the manner described, a plurality of search windows, i.e., search windows 111, 112, and 113, can each be searched for pixels sets meeting different correlation threshold values. In this manner, tradeoffs between picture quality and the amount of processing time expected to be potentially spent can be dynamically maintained. It will be appreciated, that this is an advantage over the prior art, which would identify a single window and a single threshold value. [0024] Figure 3 illustrates a system in accordance with a specific embodiment of the present disclosure. Specifically, Figure 3 illustrates a system 300 having a data processor 310, and a memory 320. In operation, the data processor 310 accesses the memory 300 to execute program instructions 322 and to manipulate video data 324. For example, the video data 324 would generally include the video frame data of frames F1 202 and F2 204 of Figure 1. Likewise, the video processor 310 would generally comprise an instruction execution unit for implementing the instructions. In addition, the data processor 310 can include co-processors 312, which can include specific hardware accelerators and/or microcode engines, capable of implementing some or all of the encoding process described herein. In will be further appreciated, that the information processor 300 of Figure 3 can be part of a general purpose computer, special purpose computer, or integrated as a portion of a larger system. [0025] In the preceding detailed description of the embodiments, reference has been made to the accompanying drawings which for a part thereof, and in which is shown by way of illustration specific embodiments in which the disclosure may be practiced. These embodiments are described in sufficient detail to enable those skilled in the art to practice the disclosure, and it is to be understood that other embodiments may be utilized and logical, mechanical and electrical changes may be made without departing from the spirit or scope of the present disclosure. To avoid detail not necessary to enable those skilled in the art to practice the disclosure, the description may omit certain information known to those skilled in the art. Furthermore, many other varied embodiments that incorporate the teaching of the disclosure may be easily constructed by those skilled in the art. Accordingly, the present disclosure is not intended to be limited to the specific form set forth herein, but on the contrary, it is intended to cover such alternatives, modifications, and equivalents, as can be reasonably included within the spirit and scope of the disclosure. The preceding detailed description is, therefore, not to be taken in a limiting sense, and the scope of the present disclosure is defined only by the appended claims. WE CLAIM: 1. A method of determining a motion vector for a pixel set being encoded, said method comprising the steps of: selecting a first search window of a first frame of video data, the first search window having a first window size; determining if a pixel set associated with the first search window meets a first correlation requirement with respect to the pixel set being encoded; determining a motion vector for the pixel set being encoded when any pixel set associated with the first search window meets the first correlation requirement; and when no pixel set associated with the first search window meets the first correlation requirement: selecting a second search window of the first frame of video data, the second search window having a second window size larger than the first window size; determining if a pixel set associated with the second search window meets a second correlation requirement with respect to the pixel set being encoded, the second correlation requirement being different from the first correlation requirement; and determining a motion vector for the pixel set being encoded when any pixel set associated with the second search window meets the second correlation requirement. 2. The method as claimed in claim 1, involving the steps of: determining the correlation between the pixel set associated with the first search window and the pixel set being encoded based on a first correlation technique, and determining the correlation between the pixel set associated with the second search window and the pixel set being encoded based on a second correlation technique different from the first correlation technique. 3. The method as claimed in claim 1, involving the steps of: in response to determining that no pixel set associated with the second search window meets the second correlation requirement: selecting a third search window of the first frame having a third window size greater than the second window size; and determining a motion vector for the pixel set being encoded when any pixel set associated with the third search window meets the third correlation requirement. 4. The method as claimed in claim 2, involving the steps of: determining the correlation between the pixel set associated with the second search window and the pixel set being encoded based on a first correlation technique, and determining the correlation between the pixel set associated with the third search window and the pixel set being encoded based on a second correlation technique different from the first correlation technique. 5. The method as claimed in claim 2 or 4, wherein the second correlation requirement is less stringent than the first correlation requirement. 6. A system for determining a motion vector for a pixel set being encoded, said system comprising: a video data processing element; a memory coupled to the video data processing element, the memory comprising: a video data storage region to store a first frame of video data and a second frame of video data; and a program storage region to store program instructions, the program instructions operable to manipulate the video data processing element to : select a first search window having a first window size for the first frame of video data; determine if a pixel set associated with the first search window meets a first correlation requirement with respect to the pixel set being encoded; determine a motion vector for the pixel set being encoded when the pixel set associated with the first search window meets the first correlation requirement; in response to determining that no pixel set associated with the first search window meets the first correlation requirement select a second search window having a second window size greater than the first window size for the first frame of video data; determine if a pixel set associated with the second search window meets a second correlation requirement with respect to the pixel set being encoded, the second correlation requirement being different from the first correlation requirement; and determine a motion vector for the pixel set being encoded when the pixel set associated with the second search window meets the second correlation requirement. 7. The system as claimed in claim 6, wherein the program instructions are operable to manipulate the video data processing element to: determine the correlation between the pixel set associated with the first search window and the pixel set being encoded based on a first correlation technique, and determine the correlation between the pixel set associated with the second search window and the pixel set being encoded based on a second correlation technique, the second correlation technique being different from the first correlation technique. 8. The system as claimed in claim 6, wherein the program instructions are operable, in response to determining that no pixel set associated with the second search window meets the second correlation requirement, to manipulate the video data processing element to: select a third search window of the first frame having a third window size greater than the second window size; and determine a motion vector for the pixel set being encoded when any pixel set associated with the third search window meets the third correlation requirement. 9. The system as claimed in claim 8, wherein the program instructions are operable to manipulate the video data processing element to: determine the correlation between the pixel set associated with the second search window and the pixel set being encoded based on a first correlation technique, and determine the correlation between the pixel set associated with the third search window and the pixel set being encoded based on a second correlation technique different from the first correlation technique. 10. The system as claimed in claim 7 or 9, wherein the program instructions are operable to manipulate the video data processing element to make the second correlation requirement less stringent than the first correlation requirement. There is disclosed a first search window (111) within a reference frame (102) of video data is identified along with a first correlation threshold value (202) for the first window (111). The first correlation threshold value (202) is a value to which correlation factors (204) between a pixel set being encoded and pixels sets (203) of the first search window (111) are compared. For example, if a correlation factor (204) between a specific pixel set (203) of the first search window (111) and a pixel set being encoded meets the first threshold value (205), a successful match between the two pixel sets has been found, and a corresponding motion vector can be assigned to the pixel set being encoded. If none of the pixel sets (203) within the first window (111) meet the first threshold value, a second search window (112) within the first frame is selected (210) along with a second correlation threshold value (204). The correlation factors for pixel sets in the second window (112) are compared to the second correlation threshold value (204).

Documents:

1330-KOLNP-2005-CORRESPONDENCE.pdf

1330-KOLNP-2005-FORM 27.pdf

1330-KOLNP-2005-FORM-27.pdf

1330-kolnp-2005-granted-abstract.pdf

1330-kolnp-2005-granted-assignment.pdf

1330-kolnp-2005-granted-claims.pdf

1330-kolnp-2005-granted-correspondence.pdf

1330-kolnp-2005-granted-description (complete).pdf

1330-kolnp-2005-granted-drawings.pdf

1330-kolnp-2005-granted-examination report.pdf

1330-kolnp-2005-granted-form 1.pdf

1330-kolnp-2005-granted-form 18.pdf

1330-kolnp-2005-granted-form 3.pdf

1330-kolnp-2005-granted-form 5.pdf

1330-kolnp-2005-granted-gpa.pdf

1330-kolnp-2005-granted-reply to examination report.pdf

1330-kolnp-2005-granted-specification.pdf