Abstract:
Methods and apparatus for accelerating the processing of image data are disclosed that are particularly useful in conducting graphical pattern searches. Embodiments of the invention conduct and implement comparative calculations of reference and search image pel data on a multi-pel comparative basis, particularly, sum of the absolute differences (SAD) based calculation comparisons.

Description:
FIELD OF INVENTION 
       [0001]    This application is related to processors and methods of video data processing acceleration. 
       BACKGROUND 
       [0002]    One widespread method of capturing and/or displaying images is through the use of pixel-based image capture and/or display. As electronic imaging resolution has increased along with the increased demand of “real time” video display, the demands for quick and efficient processing of video image data continues to increase. 
         [0003]    For various types of video processing, such as video encoding, frame rate conversion, super-resolution, etc., it is desirable to perform motion estimation by finding where MBs of image data (or altered versions thereof) appear in a reference frame are located in a subsequent frame. Conventionally, the image data of a MB located a particular coordinate location in a reference frame is searched for in a subsequent frame within a search block that surrounds the MB reference block location. 
         [0004]    In image processing, pixels are generally represented by pixel data elements, commonly referred to as pels, that are often byte sized. For example, a pel may be defined by eight bits of data that represents one byte of data in a particular image display application. 
         [0005]    Performing a comparative calculation of differences between pels is used in a variety of video processing algorithms. Generally these operations are done to rapidly compare one set of pels to another. For example, such a comparison can form a base image correlation operation in many motion search algorithms. 
         [0006]    In such correlations, it is desirable to obtain a calculation of the differences between pels of a reference image and pels of a search image. One comparative calculation technique is known as the sum of the absolute differences (SAD). Although a single-pel SAD comparison can be made, conducting multi-pel SAD comparison operations are preferred. In a conventional multi-pel SAD comparison operation, pel data of a predefined number of reference pels is compared with pel data of a predefined number of search image pels on an individual pel basis. In a conventional multi-pel SAD comparison operation, the absolute value of the differences of corresponding individual pels from each respective set are summed. 
         [0007]      FIG. 1  illustrates an implementation of a conventional multi-pel SAD comparison calculation circuit  10 . A first input  12  is configured to receive four bytes of pel data, each byte representing one of a set of four consecutive pels from a reference image. A second input  14  is configured to receive four bytes of pel data representing a set of four consecutive pels from a search image. 
         [0008]    Four absolute value difference circuits  16   a - d  are provided, each configured to generate an absolute value of the difference in the values of pel data for a pel of the reference image received via the first input  12  with pel data of a corresponding pel of the search image received via the second input  14 . For example, absolute value difference circuit  16   a  generates an absolute value of the difference in the value of pel data for the pel represented by Byte° of the reference image data and the value of pel data for the pel represented by Byte° of the search image data. 
         [0009]    An adder  19  is provided that sums the results generated by the absolute value difference circuits  16   a - d  to provide a two byte output  20  representing a comparative value of the reference image set of four pels and the search image set of four pels. 
         [0010]    Typically, a reference image will comprise many more pels then can be processed in one multi-pel SAD comparison calculation. For example a 4 pel by 16 pel reference image contains sixteen different 4 pel sets. In using a search algorithm to perform a comparison of such a 4 by 16 block of reference image pels with a 4 by 16 block of pels within a search image, the conventional multi-pel SAD comparison calculation may be conducted with respect to each of the sixteen different 4 pel sets of the reference area. Typically, these multi-pel SAD comparison calculations are done in series and the result of each prior calculation is accumulated into the next calculation. 
         [0011]    To perform cumulative multi-pel, SAD comparison calculations, a merge value representing a comparison result (or an accumulated comparison result) with respect to one set of reference pels is accumulated with a subsequent SAD comparison calculation performed with respect to a “next” set of reference pels. Accordingly, the multi-pel, SAD comparison calculation circuit  10  includes a third input  22  configured to receive the merge value. The third input is coupled to the adder  19  or another type of merge device so that the previously produced comparative value generated by the previous multi-pel, SAD comparison operation and previously provided via output  20  is reflected in the comparative value for the multi-pel, SAD comparison calculation then being performed. 
         [0012]    For accumulation, the merge value can be a comparative value previously produced by a preceding multi-pel SAD comparison calculation and output from output  20  or some variation thereof. For example the merge value could be determined by multiplying or dividing the result of a preceding multi-pel SAD comparison calculation by a constant and rounding prior. Generally, the merge value will be initiated to zero for a first multi-pel SAD comparison calculation and thereafter is some function of a prior multi-pel SAD comparison calculation within a given series of calculations to compare a block of reference pels and a corresponding block of search image pels. 
         [0013]    For a motion-type search operation, generally the search image can be a selected larger display area encompassing a location where a smaller reference image had appeared. For example, the reference image may be a 4 by 16 pel block that had appeared in the center of a 12 by 24 pel search image. The reference image may have moved from the original center location to another location within the 12 by 24 pel search image. Accordingly, it may be required to make a comparison of the reference image with each different 4 by 16 pel block within the 12 by 24 pel search image. Accordingly, many, many multi-pel SAD comparison calculations are required. In this case, a series of 16 cumulative multi-pel SAD comparison calculations may be required for each of 64 different searches that compare the reference image to each of 64 different 4 by 16 pel block within the 12 by 24 pel search image. 
         [0014]    For example, for a first comparison search, a first multi-pel SAD comparison calculation may be commence with a first set of four pels of a reference image, [r 0 , r 1 , r 2 , r 3 ] with respect to a first set of four pels of a search image, [s 0 , s 1 , s 2 , s 3 ]. A second SAD operation of the first search would be conducted with a second set of four pels of the reference image, [r 4 , r 5 , r 6 , r 7 ] with respect to a second set of four pels of the search image, [s 4 , s 5 , s 6 , s 7 ] with the result of the first SAD operation being accumulated (added) into the result being generated for the second SAD operation of the first search. The first comparison search then continues based on four pel increments until a complete comparison with the 4 by 16 block of reference pels is made. 
         [0015]    A second comparison search may then be conducted starting with a first multi-pel SAD comparison operation of the reference image pels with respect to respective incremental sets of search image pels such as [s 1 , s 2 , s 3 ,  4 ], [s 2 , s 3 , s 4 , s 5 ], [s 3 , s 4 , s 5 , s 6 ], [s 4 , s 5 , s 6 , s 7 ] etc. As noted above, for a 4 by 16 pel reference image, sixteen multi-pel SAD comparison calculations are performed for each search. In addition, within each series of multi-pel SAD comparison operations, a shift type operation is required to be performed with respect to address of the pel values input to the multi-pel SAD comparison calculation circuit  10  for the next multi-pel SAD comparison operation to compare a next pair of reference and search image sets of pels. 
         [0016]    In some instances, it is desirable to search for an irregularly shaped object contained in a reference image so that the reference image is comprised of pels defining the object (“object pels”) and pels that are not part of the object, such as pels displaying background behind the object (“background pels”). In searching for such an object, it is immaterial whether or not a match is found with respect to the background pels, since they are not part of the object being searched for. 
         [0017]    The conventional multi-pel SAD comparison operation, however, is based upon the premise that all of the pels of the reference image are pertinent to the search. This is problematic where an object within the reference image is the subject of the search and the reference image is comprised of object pels and background pels. The conventional multi-pel SAD comparison calculation can produce erroneous results attributable to any background pels within a set of pels being compared in searching the search image for a specific object contained in the reference image. This can give rise to a need to perform individual pel SAD comparison calculations instead of utilizing the multi-pel SAD comparison calculation of  FIG. 1 . Where such an object search is to be conducted, the number of processing operations involved in comparing the reference image to the search image as in connection with performing a search algorithm is further increased, since the conventional multi-pel SAD comparison operation cannot be uniformly used without the risk of erroneous results. 
         [0018]    In the context of computer execution of image search algorithms, the number of times various operation need to be performed can be a significant factor in the overall processing speed that can be achieved. A SAD OpCode (operation code) is known with respect to instructing an arithmetic logic unit (ALU) of a processor to conduct the conventional multi-pel SAD comparison operation represented in the  FIG. 1  diagram. Typically, each multi-pel SAD comparison operation is performed by the ALU of a processor execution unit in response to the execution unit processing a microinstruction that identifies the SAD OpCode. Typically, after a SAD microinstruction is received, the execution unit will receive a microinstruction for at least one data shifting operation. Such a data shifting operation is generally required to provide a different input set of data for at least one of the multi-pel SAD comparison operation inputs for a next SAD microinstruction that is to be performed in the performance of a video search algorithm. 
       SUMMARY OF THE EMBODIMENTS 
       [0019]    Methods and apparatus for accelerating the processing of image data are disclosed that are particularly useful in conducting graphical pattern searches. Embodiments of the invention conduct and implement comparative calculations of reference and image pel data on a multi-pel comparison basis, particularly, sum of the absolute differences (SAD) based calculation comparisons. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0020]      FIG. 1  is a circuit diagram of an implementation of a conventional SAD pel set comparison calculation circuit. 
           [0021]      FIG. 2  is a circuit diagram of an implementation of a Masked SAD pel set comparison calculation circuit within an apparatus according to the teachings of the present invention. 
           [0022]      FIG. 3  is a circuit diagram of an implementation of a multi-operation pel set comparison calculation circuit within an apparatus according to the teachings of the present invention. 
           [0023]      FIG. 4  is a graphic illustration of an initial Masked Quad SAD operation for a search for a reference image within a search area according to the teachings of the present invention. 
           [0024]      FIG. 5  is a graphic illustration of a second Masked Quad SAD operation for the search for the reference image of  FIG. 4 . 
       
    
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
       [0025]    The following description of specific examples of the present invention is non-limiting. The examples are not intended to limit the scope and content of this disclosure. 
         [0026]    For various types of video processing, such as video encoding, frame rate conversion, super-resolution, etc., it is desirable to perform motion estimation by finding where blocks of image data (or altered versions thereof) appear in a reference frame are located in a subsequent frame. In order to support real time or fast than real time capture and/or display of video where motion estimation is used, all of the searches for image blocks of a reference frame must be fast enough so that video processing can be timely completed. The amount of processing required is generally related to the resolution of the video frames that are being processed. 
         [0027]    Although a specific type of pel data comparison disclosed in the following examples is based on a sum of the absolute differences (SAD) calculation, the invention is not limited to such a specific arithmetic comparative operation between reference pel data and search image pel data. Other types of comparisons may be used in place of the SAD calculation. 
         [0028]    Referring to  FIG. 2 , an implementation of a multi-pel Masked SAD comparison calculation circuit  30  is illustrated. The multi-pel Masked SAD comparison circuit/calculation/operation is referred to below simply as the “Masked SAD” circuit/calculation/operation. 
         [0029]    Preferably the multi-pel Masked SAD comparison calculation circuit  30  is an integral part of a system  300  that captures and/or displays video in connection with video motion estimation processing associated with video processing such as video encoding, frame rate conversion, super-resolution, etc. Such systems  300  include, but are not limited to, video recorders, camcorders, video cameras and other type of video capture devices, personal computers and other types of devices that display video, computer displays, televisions and other types of display devices. In particular, the multi-pel Masked SAD comparison calculation circuit  30  and associated methods described below apparatus can be advantageously incorporated and/or employed where such devices use high speed capture and/or high speed display of high resolution video. 
         [0030]    Similar to the conventional multi-pel SAD comparison circuit of  FIG. 1 , the Masked SAD circuit  30  has a first input  32  and a second input  34  configured to receive pel data representing equal sized sets of pels of respective reference and search images. Generally, the first input  32  and second input  34  are configured to receive a data vector of a plurality of words that may be defined as having a predetermined byte or bit size. Preferably, the data vector word size is a power of two, such as 8-bit, 16-bit or 32-bit words. In the example shown in  FIG. 2 , the first input  32  is preferably configured to receive four single-byte words of pel data, each byte representing one of a set of four consecutive pels of the reference image and the second input  34  is configured to receive four bytes of pel data representing a set of four consecutive pels of the search image. However, other pel and data set sizes can be used for example a pel could be represented by 4, 10 or 16 bits of data. If the number of bits in a pel is not a power of two then some padding may optionally added to still allow the total size of a data set to be a convenient power of two. 
         [0031]    Unlike the conventional multi-pel SAD comparison circuit of  FIG. 1 , the Masked SAD circuit  30  is configured to perform pel set comparison calculations even where an object within the reference image is the subject of the search such that the set of reference pels contains both object pels for which a valid comparison is needed and background pels for which it is immaterial whether there is a valid comparison. For example, a reference image may be defined with respect to a rectangular collection of x rows of pels in y columns, i.e. pels r 1 , r 12  . . . r 1   y , r 21  . . . r 2   y  . . . rx 1  . . . rxy where each pel is either part of an object of interest (an “object pel”) or purely a background pel. 
         [0032]    Both object pels and background pels in the reference image can typically be within a predetermined range of values in a source image from which the reference image is taken. In YUV video, for example, pels have a nominal value range of 16-235. YUV video is a type of video signal that consists of three separate signals: 1 for luminance (brightness) and two for chrominance (colors). 
         [0033]    Various manners of identifying object and background pels in a reference image are well known in the art. Conventionally, pixels are identified by an object segmentation algorithm as being part of the object or not being part of the object. Typically adapting the SAD calculations to only sum object pels prevents full time use of the more efficient multi-pel SAD comparison operation depicted in  FIG. 1 , and requires additional costly operations to locate consecutive groups of pixels where the more efficient multi-pel SAD comparison operation can be used. Failing to exclude the background pels leads to generation of SAD results that are false negatives—indicating that no good match was found even along a correct motion trajectory for the object where the background&#39;s motion was not on the object&#39;s motion trajectory. Thus, the search image can contained different background pels that provide an erroneous result when using the conventional multi-pel SAD comparison calculation. Accordingly, background pels, if not excluded, can distort the results of a motion search for an object contained in a reference image using the conventional multi-pel SAD comparison operation. 
         [0034]    Where a search image is to be searched to find a specific object contained in a reference image, the pel data for the reference image is preprocessed to set pel data for any background pels within the reference image to a fixed value outside the typical pel value range. The example Masked SAD circuit  30  is configured to make pel set comparison calculations where the typical pel value range of pels in the reference image excludes zero and the value of any background pels is set to zero in defining the reference pel set data to be received by input  32  of Masked SAD circuit  30 . The Masked SAD operation facilitates searching for objects of higher resolution and in a more uniform manner through which accelerated processing speed and searching accuracy may be achieved, since the Masked SAD operation can be utilized with respect to reference images comprised of both object and background pels. 
         [0035]    The Masked SAD circuit  30  has a plurality of processing circuits  36   a - d , preferably corresponding in number to the number of pels in the reference and search image pel sets for which the first and second inputs  32 ,  34  are respectively configured to receive pel data. In the example shown in  FIG. 2 , the Masked SAD circuit  30  is configured to conduct a comparison of reference and search image pel sets having four pels, so there are four processing circuits  36   a - d.    
         [0036]    Each processing circuit  36   a - d  is preferably configured to generate an absolute value of the difference in the values of pel data for a pel of the reference image received via the first input  32  with pel data of a corresponding pel of the search image received via the second input  34  and to direct that generated value to a respective multiplex component  37   a - d  of the processing circuit. For example, processing circuit  36   a  generates an absolute value of the difference in the value of pel data for the pel represented by Byte° of the reference image data and the value of pel data for the pel represented by Byte 0  of the search image data. The result of the calculation made by processing circuit  36   a  is passed to multiplex component  37   a.    
         [0037]    Each processing circuit  36   a - d  also includes a respective comparator component  38   a - d  coupled with the reference image data input  34  that is configured to direct a control signal to the respective multiplex component  37   a - d . Each comparator component  38   a - d  is configured to control the respective multiplex component  37   a - d  to output a predetermined value if the reference pel data value being processed by the respective processing circuit is a value that identifies that reference set pel as a background pel. If the reference pel data value being processed by the respective processing circuit  36   a - d  is a value that does not identify that reference set pel as a background pel, the respective multiplex component  37   a - d  is configured to output the generated absolute value of the difference pel values being processed by the respective processing circuit  36   a - d . The predetermined value output when a background pel is being processed is preferably selected to be the same or very close to the value generated by a comparison of matching reference and search image pels. 
         [0038]    In the illustrated example of  FIG. 2 , a zero value is the value that is used to identify a reference set pel as a background pel and values of reference set object pels are non-zero, so that the comparator components  38   a - d  can determine whether the respective reference pel values being processed by their respective processing circuits  36   a - d  are non-zero to determine how to control the respective multiplex components  37   a - d . Also a zero value is selected as the predetermined value output by the respective multiplex component  37   a - d  when a background pel is being processed, since a value that is 0 or very close to 0 is the value generated by a SAD comparison of matching reference and search image pels. 
         [0039]    In an example Masked SAD operation, processing circuit  36   a  generates an absolute value of the difference in the value of pel data for the pel represented by Byte° of the reference image data and the value of pel data for the pel represented by Byte° of the search image data, which value is then passed to multiplex component  37   a . However, the comparator components  38   a  will control the value output by multiplex component  37   a  to be the predetermined zero value if the value of pel data for the pel represented by Byte° of the reference image data is zero. 
         [0040]    A merge component, such as an adder,  39  is provided that merges, preferably sums, the results output from the multiplex components  37   a - d  of the processing circuits  36   a - d  to provide an output  40 . In lieu of simple addition, the merge component can be configured to use any suitable merge function. For example, the merge component can be configured to multiply or divide the results output from the multiplex components  37   a - d  by a constant and/or to perform rounding in performing the merge function in order to provide a result reflective of the multi-pel comparison being performed. 
         [0041]    Generally, the output  40  is configured to output a data vector of one or more words that may be defined as having a predetermined byte or bit size and that may represent either fixed or floating point values. In the illustrated example, preferably, the output data vector from output  40  is a sixteen-bit word representing a comparative value of a comparison of four pels of the reference image and four pels of the search image. This value is not distorted even if the set of four pels of the reference image contains background pels since the contribution to the comparative value attributable to any such background pels is 0. 
         [0042]    Preferably support for cumulative Masked SAD calculations is provided where a merge value is merged into the result of the Masked SAD calculation. To perform cumulative Masked SAD calculations, a merge value, preferably representing a comparison result (or an accumulated comparison result) with respect to one set of reference pels, is accumulated with a subsequent Masked SAD calculation performed with respect to a “next” set of reference pels. 
         [0043]    For accumulation, the merge value is preferably a comparative value previously produced by a preceding Masked SAD calculation and output from output  40  or some variation thereof. For example the merge value could be determined by multiplying or dividing the result of a preceding Masked SAD calculation by a constant and rounding prior. Generally, the merge value will be initiated to zero for a first of a series of Masked SAD calculations and thereafter the merge value will be some function of a prior Masked SAD calculation within a given series of calculations to compare a block of reference pels and a corresponding block of search image pels. 
         [0044]    For example, for a given comparison search, a first cumulative Masked SAD operation may commence with respect to a first set of four pels of a reference image, [r 0 , r 1 , r 2 , r 3 ] and a first set of four pels of a search image, [s 0 , s 1 , s 2 , s 3 ]. A “next” Masked SAD operation of the given search could then be conducted with respect to a “next” set of four pels of the reference image, [r 4 , r 5 , r 6 , r 7 ] and a next set of four pels of the search image, [s 4 , s 5 , s 6 , s 7 ]. The series of cumulative Masked SAD operations would typically continue for the given search, until all of the pels of the reference image have been compared with corresponding pels of the search image. 
         [0045]    As illustrated, the example Masked SAD circuit  30  includes a third input  42  configured to receive the merge value. The third input is coupled to the adder or another type of merge device  39  so that the previously produced comparative value generated by the previous Masked SAD operation and previously provided via output  40  is reflected in the comparative value for the Masked SAD calculation then being performed. 
         [0046]    Generally, the third input  42  is configured to receive a data vector of one or more words that may be defined as having a predetermined byte or bit size and that may represent either fixed or floating point values. Preferably, the third input  42  receives as its input a comparative value previously produced with respect to a pair of sets of reference and search image pels within a given cumulative search. In the Example of  FIG. 2 , such input is preferably a sixteen-bit word previously output from output  40 . In such case, the third input is coupled to the merge component configured as an adder  39  so that the previously produced comparative value is added into the comparative value for a next Masked SAD calculation within a series of Masked SAD operation being performed for a cumulative search. 
         [0047]    In lieu of simply adding a prior comparative value to the Masked SAD calculation, the merge component  39  may be configured to otherwise combine the merge value with the results output from the multiplex components  37   a - d  of the processing circuits  36   a - d . Examples for the configuration of the merge component  39  include but are not limited to being configured to perform an Add that saturates at a maximum value, to perform an Add that wraps, to perform an Add that generates a carry or to perform an Add that wraps and generates a carry. 
         [0048]    Preferably, a Masked SAD OpCode (operation code) is defined that is used to instruct an arithmetic logic unit of an execution unit of a processor to conduct the Masked SAD calculations described above in connection with  FIG. 2 . As with the conventional SAD operation, the Masked SAD operation described above will typically alternate with at least one data shifting operation to provide a different input set pair of pel data for a next Masked SAD operation within a series of Masked SAD operations to be performed for a given cumulative search. 
         [0049]      FIG. 3  illustrates an example of a further embodiment of a video image data processing circuit made in accordance with the teachings of the present invention where there is a consolidation of pel set comparison calculations. Referring to  FIG. 3 , a multi-operation pel set comparison calculation circuit  50  is illustrated. 
         [0050]    Preferably the multi-operation pel set comparison calculation circuit  50  is an integral part of a system  500  that captures and/or displays video in connection with video motion estimation processing associated with video processing such as video encoding, frame rate conversion, super-resolution, etc. Such systems  500  include, but are not limited to, video recorders, camcorders, video cameras and other type of video capture devices, personal computers and other types of devices that display video, computer displays, televisions and other types of display devices. In particular, the multi-operation pel set comparison calculation circuit  50  and associated methods described below apparatus can be advantageously incorporated and/or employed where such devices use high speed capture and/or high speed display of high resolution video. 
         [0051]    The circuit  50  includes a first input  52  configured to receive pel data for a set of a predetermined number N of pels of a reference image, where N is at least 2. Generally, the first input  52  is configured to receive a data vector of a plurality of N words that may be defined as having a predetermined byte or bit size. Preferably, the data vector word size is a power of two, such as 8-bit, 16-bit or 32-bit words. In the illustrated example, the first input  52  is configured to receive pel data with respect to a set of four pels of the reference image. Preferably, the pel data represents four consecutive eight-bit bytes and the input  52  is a 32-bit input. 
         [0052]    A second input  54  is configured to receive pel data for a set of a predetermined number M of pels of a search image where M is greater than N. Generally, the second input  54  is configured to receive a data vector of a plurality of M words that may be defined as having a predetermined byte or bit size. Preferably, the data vector word size is a power of two, such as 8-bit, 16-bit or 32-bit words. In the illustrated example, the second input  54  is configured to receive pel data with respect to a set of at least seven pels of the search image. The second input  54  is preferably configured to receive pel data with respect to a set of eight consecutive pels of the search image that are represented in eight eight-bit bytes and the input  54  is a 64-bit input. 
         [0053]    The first and second inputs  52 ,  54  are selectively coupled to a plurality of K arithmetic circuits  56   a - d . Each K arithmetic circuit  56   a - d  is configured to process the pel data for the set of N pels received via the first input  52  with pel data for a search image pel subset of N pels of the set of M pels received via the second input  54  such that the search image pel subset used by each arithmetic circuit  56   a - d  contains pel data with respect to different subsets of the set of M pels. In the illustrated example, there are four arithmetic circuits  56   a - d.    
         [0054]    Arithmetic circuit  56   a  is configured to process the pel data for the set of four pels of the reference image received via the first input  52  with the pel data for a search image pel subset of made up of the first, second, third and fourth pels of the set of eight pels of the search image received via the second input  54 . Arithmetic circuit  56   b  is configured to process the pel data for the set of four pels of the reference image received via the first input  52  with the pel data for a search image pel subset of made up of the second, third, fourth and fifth pels of the set of eight pels of the search image received via the second input  54 . Arithmetic circuit  56   c  is configured to process the pel data for the set of four pels of the reference image received via the first input  52  with the pel data for a search image pel subset of made up of the third, fourth, fifth and sixth pels of the set of eight pels of the search image received via the second input  54 . Arithmetic circuit  56   d  is configured to process the pel data for the set of four pels of the reference image received via the first input  52  with the pel data for a search image pel subset of made up of the fourth, fifth, sixth and seventh pels of the set of eight pels of the search image received via the second input  54 . 
         [0055]    Optionally, a fifth arithmetic circuit can be provided to process the pel data for the set of four pels or the reference image received via the first input  52  with the pel data for a search image pel subset of last four pels of the set of eight pels of the search image received via the second input  54 . However, a configuration containing four arithmetic circuits is preferred for preserving computational efficiency and resources in the normal binary-based processing of video data. For similar reasons the second input is configured as a 64-bit input even though only first 56 bits of the inputted data are processed, since the data representing the eighth pel of the search image pel set is not processed by any of the illustrated arithmetic circuits  56   a - d.    
         [0056]    Each arithmetic circuit  56   a - d  is configured to provide an output. Generally, each arithmetic circuit  56   a - d    40  is configured to output a data vector of one or more words that may be defined as having a predetermined byte or bit size and that may represent either fixed or floating point values. Preferably, each output data vector is a sixteen-bit word. Preferably, the output vectors from all of the arithmetic circuits  56   a - d  are collectively output as a single vector from an output  60  of the multi-operation pel set comparison calculation circuit  50 . 
         [0057]    In the example illustrated in  FIG. 3 , the output vector from each arithmetic circuit  56   a - d  is preferably a sixteen-bit word. The outputs from all of the arithmetic circuits  56   a - d  are collectively output as four sixteen-bit words from output  60  of the example multi-operation pel set comparison calculation circuit  50  of  FIG. 3 . Each sixteen-bit word output from the arithmetic circuits  56   a - d  represents a comparison result generated with respect to one of the search image pel subsets and the set of pels of the reference image. 
         [0058]    For example, arithmetic circuit  56   a  provides a first sixteen-bit word of the four sixteen-bit word output of output  60  that represents a comparison result generated with respect to the search image pel subset made up of the first, second, third and fourth pels of the set of eight pels of the search image and the set of pels of the reference image. Arithmetic circuit  56   d  provides a fourth sixteen-bit word of the four sixteen-bit word output of output  60  that represents a comparison result generated with respect to the search image pel subset made up of the fourth, fifth, sixth and seventh pels of the set of eight pels of the search image and the set of pels of the reference image. 
         [0059]    Each arithmetic circuit  56   a - d  is preferably configured to perform a multi-pel SAD or other multi-pel comparison type operation. For example, each arithmetic circuit  56   a - d  may be configured in accordance to  FIG. 1  to perform the conventional multi-pel SAD operation discussed above. With such a configuration, the example multi-operation pel set comparison calculation circuit  50  performs four multi-pel SAD operations in parallel, i.e. a Quad-SAD operation. 
         [0060]    Each arithmetic circuit  56   a - d  is preferably configured to perform the Masked SAD operation as illustrated and described in accordance with  FIG. 2 . Thus making multi-operation pel set comparison calculation circuit  50  suitable for use in producing comparative calculations results with respect to searching for an object contained in reference image comprised of object pels and background pels. In such instance the first input  52  is preferably configured to receive preprocessed pel data as discussed above with respect to first input  32  of the Masked SAD circuit  30 . With such a configuration, the example multi-operation pel set comparison calculation circuit  50  performs four Masked SAD operations in parallel, i.e. a Masked Quad-SAD operation. 
         [0061]    Preferably support for cumulative Quad SAD calculations is provided where a merge value is merged into the result of each SAD calculation. For example, a prior result produced from the output  60  can represent four comparison results with respect to a reference image set of pels and four different subsets of a search image set of pels. Such a prior result can be accumulated with a subsequent Quad-SAD calculation performed with respect to a “next” set of reference image pels and four similar subsets of a next set of search image pels. Such a cumulative Quad-SAD calculation will typically be performed in connection with concurrently conducting multiple searches of the reference image within corresponding blocks of the search image as explained in more detail below with respect to  FIGS. 4 and 5 . However, in lieu of simply accumulating a prior comparative value to a SAD calculation, each arithmetic circuit  56   a - d  may be configured to otherwise merge a merge value with the result it outputs, for example, as discussed with respect to the Masked SAD circuit  30  above. 
         [0062]    For cumulative calculation support, the multi operation pel set comparison calculation circuit, such as example circuit  50 , preferably includes a third input  62  configured to receive a set of merge values. The third input is preferably selectively coupled to each arithmetic circuit  56   a - d  so that a respective merge value from the inputted set of merge values is merged with that arithmetic circuit&#39;s output. Generally, the third input  62  is configured to receive a data vector of words that may be defined as having a predetermined byte or bit size and that may represent either fixed or floating point values. Preferably, this input data vector size is the same size as the collective output data vector output from output  60 . For example, the set of merge values received via the third input  62  may be a prior result (or derivative thereof) produced from the output  60  that represents four comparison results (or cumulative comparison results) with respect to a reference image set of pels and four subsets of a search image set of pels. The third input  62  is selectively coupled to the arithmetic circuits  56   a - d  to provide each with a third input such that a respective portion of the prior result is added or otherwise merged into the comparison result being generated by the respective arithmetic circuits  56   a - d.    
         [0063]    In the example multi-operation pel set comparison calculation circuit  50  of  FIG. 3 , the third input  62  is configured to selectively receive four sixteen-bit words. The third input  62  is coupled the arithmetic circuits  56   a - d  to provide a respective sixteen-bit word representing a prior Quad SAD result (or prior cumulative result) to each of the arithmetic circuits  56   a - d . For example, for a cumulative operation, where a prior result from output  60  is input to the third input  62  in the form of data made of four sixteen-bit words, the first sixteen-bit word is directed to the arithmetic circuit  56   a  and the fourth sixteen-bit word is directed to the arithmetic circuit  56   d . Where a Quad SAD calculation is being made for the same sets of reference and search image pels for which the prior result was produced, each respective reference set/search image pel subset comparison calculation will be accumulated with a respective portion of the prior result. 
         [0064]    Preferably, a Quad SAD OpCode is defined that is used to instruct an arithmetic logic unit of an execution unit of a processor to conduct the Quad SAD calculations described above in connection with  FIG. 3  having each of its arithmetic circuits  56   a - d  configured to perform the SAD operation discussed with respect to  FIG. 1 . More preferably, a Masked Quad SAD OpCode is defined that is used to instruct an arithmetic logic unit of an execution unit of a processor to conduct the Masked Quad SAD calculations described above in connection with  FIG. 3  having each of its arithmetic circuits  56   a - d  configured to perform the Masked SAD operation discussed with respect to  FIG. 2 . The use of such Quad SAD and/or Masked SAD operations can greatly reduce the number of shifting operations required to perform a video image search. 
         [0065]      FIG. 4  is a graphic depiction of a Masked Quad SAD operation being performed with the multi-operation pel set comparison calculation circuit  50  that has each of its arithmetic circuits  56   a - d  configured to perform the Masked SAD operation discussed with respect to  FIG. 2 . 
         [0066]    In this context, a search algorithm requiring multiple cumulative searches is being performed to locate a bird object contained in a reference image  110  within a search image  120 . The reference image  110  includes object pels that contain at least a portion of the bird object and background pels that do not contain any portion of the bird object so that a uniform rectangular reference image is defined for which to conduct the search algorithm. The background of the reference image is blank in the example for clarity and to also reflect the preprocessing of the reference image to set the background pels to a 0 value. 
         [0067]    In this example, the reference image  110  is defined by a 4 by 16 block of pels, (r 0 , 0 ) . . . (r 3 , 15 ), and the search image  120  is defined by a larger 12 by 24 block of pels, (s 0 , 0 ) . . . (s 11 , 23 ). The search algorithm proceeds by comparing the reference image pels to different 4 by 16 blocks of pels within the search image. A first cumulative comparative search of pels having been conducted with respect to a 4 by 16 block of pels that has pel (s 0 , 0 ) of the search image as its upper left most pel. 
         [0068]    With respect to  FIG. 4 , the search algorithm has reach a point where it is desirable to perform cumulative searches using multi-pel SAD comparative calculations with 4 by 16 blocks of pels spanning the fifth-eighth rows pels of the search image  120 . Four searches are being commenced, namely searches of 4 by 16 blocks of pels that respectively have pel (s 4 , 4 ), pel (s 4 , 5 ), pel (s 4 , 6 ) and pel (s 4 , 7 ) of the search image as their upper left most pel, hereinafter referred to as Block  4 , 4 , Block  4 , 5 , Block  4 , 6  and Block  4 , 7 , respectively. Each search commencing with a comparison with respect to a first set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )]. 
         [0069]    The first set of reference pels includes a background pel, namely pel (r 0 , 0 ), that forms no part of the bird object  100 . This would normally disqualify the reference pel set as a candidate for the conventional multi-pel SAD comparison operation. However, in this case the Masked SAD operation is available so that the reference pels, such as pel (r 0 , 0 ), will not distort the SAD calculation made with respect to the object pels that make up the bird object in conducting the cumulative multi-pel SAD comparative calculations. 
         [0070]    Preferably, these four searches using the Masked Quad SAD operation are commenced through providing a microinstruction to the execution unit of a processor that identifies the Masked Quad SAD operation as the operation to be performed using specified data for first and second operation inputs. The pel values of the set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] is specified as a first input as represented by  201 ; the pel values of a set of search image pels, [(s 4 , 4 ), (s 4 , 5 ), (s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 ), (s 4 , 11 )] is specified as the second input as represented by  202 . 
         [0071]    The Masked Quad SAD operation is preferably performed by the execution unit of the processor as described above to produce an output  203  of four sixteen-bit words that represent four comparison results with respect to the reference set of pels and four subsets of a search image set of pels. In the example illustrated in  FIG. 4 , a SAD value memory array  130  is preferably provided for storing words, (W 0 , 0 ) . . . (W 7 , 7 ). The output  203  is directed to the SAD value memory array  130  and is stored in four words, (W 4 , 4 ), (W 4 , 5 ), (W 4 , 6 ) and (W 4 , 7 ). 
         [0072]    The word stored at word (W 4 , 4 ) resulting from the Masked Quad SAD operation illustrated in  FIG. 4  represents the comparison result of the reference pel set [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] with a pel subset [(s 4 , 4 ), (s 4 , 5 ), (s 4 , 6 ), (s 4 , 7 )] of the search image set of pels. This represents the comparison of the initial four pels of the reference image with the initial four pels the Block  4 , 4  of the search image. 
         [0073]    Similarly, the word stored at word W 4 , 5  represent the comparison result of the reference pel set [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] with a pel subset [(s 4 , 5 ), (s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 )] of the search image set of pels. The two bytes stored at word W 4 , 6  represent the comparison result of the reference pel set [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] with a pel subset [(s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 ), (s 4 , 9 )] of the search image set of pels. The two bytes stored in the SAD value memory array  130  at word W 4 , 7  represent the comparison result of the reference pel set [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] with a pel subset [(s 4 , 7 ), (s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 )] of the search image set of pels. 
         [0074]    To support cumulative Masked Quad SAD operation, preferably the data previously stored in the SAD value memory array  130  is used as a third input when the microinstruction is provided to perform the Masked Quad SAD operation. For performing the searches with respect to Block  4 , 4 , Block  4 , 5 , Block  4 , 6  and Block  4 , 7  of the search image, the four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7 , respectively are used to accumulate the new result of each cumulative Masked Quad SAD operation performed for the respective block search. 
         [0075]    Preferably, in advance of the first Masked Quad SAD operation of the search with respect to Block  4 , 4 , Block  4 , 5 , Block  4 , 6  and Block  4 , 7  of the search image, the four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7  in the SAD value memory array  130  were initialized to 0. This permits, the first Masked Quad SAD operation to also have the data stored in the four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7  input as a third input for the first Masked Quad SAD operation without altering the result thereof. 
         [0076]      FIG. 5  illustrates a second Masked Quad SAD operation for the cumulative searches commenced in  FIG. 4  with respect to Block  4 , 4 , Block  4 , 5 , Block  4 , 6  and Block  4 , 7  of the search image. Such a second Masked Quad SAD operation is preferably commenced through providing a microinstruction to the execution unit of a processor that identifies the Masked Quad SAD operation as the operation to be performed using specified data for first and second operation inputs. A shift type instruction would be executed in advance of the second Masked Quad SAD operation so that pel data for the set of reference pels, [(r 0 , 4 ), (r 0 , 5 ), (r 0 , 6 ), (r 0 , 7 )] is specified as the first input  301  for the second Masked Quad SAD operation and pel data for the set of search image pels, [(s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 ), (s 4 , 11 ), (s 4 , 12 ), (s 4 , 13 ), (s 4 , 14 ), (s 4 , 15 )] is specified as the second input  302  for the second Masked Quad SAD operation. The result of the first Masked Quad SAD operation for this search is the data stored in the four words, W 4 , 4 , W 4 , 5 , W 4 , 6 , W 4 , 7  in the SAD value memory array  130  which is input as a third input  303  for the second Masked Quad SAD operation 
         [0077]    The second Masked Quad SAD operation is then performed by the execution unit of the processor as described above to produce an output  304  of four sixteen-bit that represent four comparison results with respect to the reference pel set of pels and four subsets of a search image set of pels that is directed to the SAD value memory array  130  and stored in four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7  overwriting the prior result that had been used as the third input for the second Masked Quad SAD operation. 
         [0078]    As a result of the second Masked Quad SAD operation, each of the four words represents an accumulation of comparative calculation result for eight pels. For example, the word stored at word W 4 , 4  at the completion of the operation illustrated in  FIG. 5  represents the prior comparison result for the first Masked SAD operation performed with respect to search image Block  4 , 4  per  FIG. 4  accumulated with the comparison result of the reference pel set [(r 0 , 4 ), (r 0 , 5 ), (r 0 , 6 ), (r 0 , 7 )] with the pel subset [(s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 ), (s 4 , 11 )] of the search image set of pels [(s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 ), (s 4 , 11 ), (s 4 , 12 ), (s 4 , 13 ), (s 4 , 14 ), (s 4 , 15 )]. 
         [0079]    Fourteen further Cumulative Masked Quad SAD operations continue with respect to successive  4 -pel sets of the reference image  110  and 8-pel sets of the search image  120 , to complete the searches with respect to search image Block  4 , 4 , Block  4 , 5 , Block  4 , 6  and Block  4 , 7 . The last Cumulative Masked Quad SAD operation in such searches, using values for the reference pel set [(r 3 , 12 ), (r 3 , 13 ), (r 3 , 14 ), (r 3 , 15 )] as the input for the first input  52 , and the values of the search image set of pels[(s 7 , 16 ), (s 7 , 17 ), (s 7 , 18 ), (s 7 , 19 ), (s 7 , 20 ), (s 7 , 21 ), (s 7 , 22 ), (s 7 , 23 )] as input for the second input  54 , and the cumulative values stored in the four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7  of the memory  130  as the input for the third input  62  of circuit  50 . Since the bird object within the reference image  110  corresponds to in position exactly to the bird object in Block  4 , 7  of the search image  120 , the final result of the four searches stored in the four words, W 4 , 4 , W 4 , 5 , W 4 , 6  and W 4 , 7  will result in the value of the word W 4 , 7  closest to 0 indicating that the best match of the location of the bird object in the search image is with respect to search image Block 4 , 7 . 
         [0080]    As an alternative to four concurrent cumulative searches using the Masked Quad Sad operation as discussed above with respect to  FIGS. 3-5 , four individual searches using the cumulative Masked SAD operation discussed with respect to  FIG. 2  can be performed to produce the same results. For example, a first search with respect to search image Block  4 , 4  using the Masked SAD operation of  FIG. 2  can be commenced through providing a microinstruction to the execution unit of a processor that identifies the cumulative Masked SAD operation of  FIG. 2  as the operation to be performed using specified data for first, second and third operation inputs as described with respect to  FIG. 2 . For the first Masked SAD operation of the search, the pel values of set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] is specified as a first input; the pel values of a set of search image pels, [(s 4 , 5 ), (s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 )] is specified as the second input. An initialized zero value stored at Word W 4 , 4  in the SAD value memory array  130  serves as the data for the third input. The output of such first Masked SAD operation is stored in word, W 4 , 4  overwriting the initialized zero value. The search with respect to search image Block  4 , 4  continues using Masked SAD operations until an accumulated value with respect to the entire reference image is obtained and stored in word, W 4 , 4 . 
         [0081]    A second search with respect to search image Block  4 , 5  using the Masked SAD operation can be commenced with a first Masked SAD operation using pel data with respect to the set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] and the set of search image pels, [(s 4 , 5 ), (s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 )]. A third search with respect to search image Block  4 , 6  using the Masked SAD operation can be commenced with a first Masked SAD operation using pel data with respect to the set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] and the set of search image pels, [(s 4 , 6 ), (s 4 , 7 ), (s 4 , 8 ), (s 4 , 9 )]. Finally, a fourth search with respect to search image Block  4 , 7  using the Masked SAD operation can be commenced with a first Masked SAD operation using pel data with respect to the set of reference pels, [(r 0 , 0 ), (r 0 , 1 ), (r 0 , 2 ), (r 0 , 3 )] and the set of search image pels, [(s 4 , 7 ), (s 4 , 8 ), (s 4 , 9 ), (s 4 , 10 )] is specified as the second input. 
         [0082]    Although the same resultant data can be produced by conducting four cumulative searches using the Masked SAD operation, the use of the Masked Quad-SAD operation provides the four search comparison results at an accelerated rate since it involves only one-fourth of the number of data shifting operations of inputted values. 
         [0083]    The above examples are not intended to be limiting and can be implemented with non-power-of-two sized values. In practice, it may be desirable to use 2-10-10-10 image data. In such a situation, an example multi-pel SAD or Masked SAD operation could preferably perform comparison calculations with respect to three (3) reference pels and three (3) searched image pels. The “Quad” SAD (or Masked “Quad” SAD) operation in such an example could be implemented as a “Tri” SAD That would receive six (6) searched image pels and perform  9  compares (three (3) sets of three (3)) with a single instruction. An example Tri SAD circuit in such case can include three (K=3) arithmetic circuits, each configured to process pel data for a set of three (N=3) pels received via a reference image input with pel data for a search image pel subset of three (N=3) pels of a set of six (M=6) pels received via a search image pel input to produce three (3) twenty-one-bit SAD values packed inside a 64 bit word. 
         [0084]    Although features and elements are described above in particular combinations, each feature or element can be used alone without the other features and elements or in various combinations with or without other features and elements. The methods or flow charts provided herein may be implemented in a computer program, software, or firmware incorporated in a computer-readable storage medium for execution by a general purpose computer or a processor. Examples of computer-readable storage mediums include a read only memory (ROM), a random access memory (RAM), a register, cache memory, semiconductor memory devices, magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks, and digital versatile disks (DVDs). 
         [0085]    Suitable processors include, by way of example, a general purpose processor, a special purpose processor, a conventional processor, a digital signal processor (DSP), a plurality of processors, one or more processors in association with a DSP core, a controller, a microcontroller, Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs) circuits, any other type of integrated circuit (IC), and/or a state machine. 
         [0086]    Embodiments of the invention may be represented as instructions and data stored on a computer readable memory. For example, aspects of the invention may be included in a hardware description language (HDL) code stored on such computer readable media. Such instructions, when processed may generate other intermediary data (e.g., net lists, GDS data, or the like) that can be used to create mask works that are adapted to configure a manufacturing process (e.g., a semiconductor fabrication facility). Once configured, such a manufacturing process is thereby adapted to manufacture processors or other semiconductor devices that embody aspects of the present invention.