JP2014229263A - Data processor, image processor, data processing method, and computer program - Google Patents

Abstract

Provided are a data processing device, an image processing device, a data processing method, and a computer program capable of calculating a similarity between data with high accuracy by simple calculation compared to SAD. An image processing apparatus includes a processor array unit. The processor array unit 130 performs an exclusive OR operation between the pixel data of the candidate frame image stored in the data buffer 121 and the pixel data of the macroblock image stored in the input register 131 by the exclusive OR operation unit 133. Operate bit by bit. The obtained exclusive ORs for each bit are combined with each other so as to be treated as exclusive OR data as one numerical data. The exclusive OR data obtained for each pixel is added, and the sum of the exclusive OR is calculated. [Selection] Figure 3

Description

  The present invention relates to a data processing device, an image processing device, a data processing method, and a computer program for calculating the similarity between two data.

  In order to encode a moving image (moving image compression), motion vector detection by block matching is used. Block matching is a technique for detecting a motion vector of an object from the correspondence between objects in two temporally continuous images (frames). That is, in block matching, the similarity of blocks of the same size extracted from each of two frames is calculated, and the relative positional relationship between the blocks with the highest similarity is detected as a motion vector.

Sum of Absolute Difference (SAD) is widely used as an index of similarity in block matching. SAD is a value obtained by calculating the absolute difference (absolute value of the difference) of all the coordinates for the two blocks to be compared and summing them. When the candidate motion vector is d (d _x , d _y ), the SAD value is obtained by equation (1). At this time, r (x, y) and c (x, y) represent the luminance at the coordinates (x, y) of the reference block and the candidate block, respectively. The SAD value becomes closer to 0 as the two blocks to be compared are more similar.

  In order to calculate such SAD, it is necessary to calculate an absolute difference, so that a large amount of arithmetic processing is required, and in addition, a huge number of SAD calculations are required for motion vector detection in one frame. For this reason, when SAD is calculated by hardware, the circuit configuration is complicated and the size of the circuit is increased.

JP-A-8-237661 JP 2000-278691 A JP 2003-324734 A

  The present inventors use the property that when the exclusive OR for each bit of two data is regarded as numerical data having the concept of a digit, it becomes a value close to the absolute difference between the two data. The idea was to calculate the degree of similarity between data by an exclusive OR operation that was simpler than the operation.

Here, the use of exclusive OR in block matching is disclosed in Patent Documents 1 to 3.
However, Patent Documents 1 to 3 only describe exclusive OR operation for each bit of data, count the number of different bits, and perform block matching using this as an evaluation value. Absent. However, the correlation between the number of different bits and the magnitude of the absolute difference is low, and the ones described in Patent Documents 1 to 3 indicate that the exclusive OR for each bit of two data is the absolute difference between the two data. It does not use the above-mentioned property that the values are close.

  The present invention uses the property that the result of an exclusive OR operation becomes a value close to an absolute difference, and is a data processing device capable of calculating the similarity between data by a simpler operation than SAD An object is to provide an image processing apparatus, a data processing method, and a computer program.

(1) The present invention is a data processing apparatus for evaluating the degree of similarity between first data and second data each including a plurality of processing data composed of a bit string of a predetermined length, and is included in the first data An exclusive logical OR configured as the bit string of the predetermined length in which the exclusive OR of the processing data and the processing data included in the second data is calculated for each bit, and the obtained exclusive OR for each bit is continuous. An exclusive OR operation unit that obtains sum data, and a similarity operation unit that calculates an index indicating the similarity between the first data and the second data, and the similarity operation unit includes a plurality of similarity operation units. By treating each of the plurality of exclusive OR data acquired for each of the processing data as numerical data, a sum by an arithmetic operation of the plurality of exclusive OR data is obtained, and the sum is an index indicating the similarity A data processing device for.

  According to the present invention, since an exclusive OR that can be realized by a simpler operation than the absolute difference is used instead of the absolute difference, the index indicating the similarity of data by a simpler operation than the method using the SAD Can be calculated. Also, exclusive OR data in which exclusive OR is continuous is equal to the result of excluding the carry processing from the calculation of the absolute difference between the processing data of the first data and the processing data of the second data, and in many cases, the absolute OR data is absolute. The value is close to the difference. In particular, in a combination in which no carry occurs, the value is the same as the absolute difference. Accordingly, it is possible to suppress a decrease in accuracy of calculation of an index indicating similarity.

(2) The exclusive OR operation unit includes an exception processing unit that calculates a value of an upper predetermined bit of the exclusive OR data, and the exception processing unit includes processing data included in the first data, The value of the upper predetermined bit of the absolute difference from the processing data included in the second data is calculated, and the exclusive OR operation unit calculates the value of the upper predetermined number of bits of the absolute difference calculated by the exception processing unit. Preferably, the exclusive OR data included in the upper predetermined number of bits is acquired.
In many cases, exclusive OR data obtained by connecting exclusive ORs for each bit takes a value close to an absolute difference, but it is not always the same value. Even if there are few combinations of processing data, the error becomes large. Therefore, with the above configuration, the value of the upper predetermined number of bits of the numerical data becomes the same as the result of the absolute difference, so that the error between the numerical data and the absolute difference can be reduced.

(3) It is preferable that the exception processing unit calculates the upper predetermined number of bits of the absolute difference based on the upper bits of the processing data of the first data and the processing data upper bits of the second data.
In this case, since a part (upper bits) of each processing data is used for processing by the exception processing unit, it is possible to suppress the calculation amount by the exception processing unit.

(4) It is preferable to calculate the most significant bit of the absolute difference based on the upper 2 bits of the processing data of the first data and the upper 2 bits of the processing data of the second data.
In this case, since only the upper 2 bits of each processing data are used for processing by the exception processing unit, the amount of calculation by the exception processing unit can be further suppressed. In addition, since the most significant bit with the largest digit is calculated by the exception processing unit and used as the most significant bit of the exclusive OR data, it is possible to obtain a high error reduction effect while suppressing the calculation of exception processing. It becomes.

(5) The exclusive OR operation unit includes a plurality of EXOR gates corresponding to each of the plurality of bits of the processing data, and the plurality of EXOR gates performs the plurality of bits of the exclusive OR operation in parallel. Is preferred.
In this case, the exclusive OR operation for each of the plurality of bits of each processing data is executed in parallel by the plurality of EXOR gates, so that the exclusive OR can be calculated at high speed.

(6) The exclusive OR operation unit includes a plurality of unit operation units that calculate exclusive OR of one processing data included in the first data and one processing data included in the second data. It is preferable that each unit operation unit execute an exclusive OR operation on a plurality of processing data in parallel.
In this case, since the exclusive OR operation for a plurality of processing data is executed in parallel by the plurality of unit operation units, it is possible to calculate an index indicating the similarity at high speed.

(7) The present invention from another viewpoint is an image processing apparatus for evaluating the similarity between first image data and second image data each including a plurality of pixel data composed of a predetermined-length bit string, The bit string of the predetermined length in which the exclusive OR of the pixel data included in the first image data and the pixel data of the second image data is calculated for each bit, and the obtained exclusive OR for each bit continues. An exclusive OR operation unit configured to acquire exclusive OR data configured as: a similarity operation unit that calculates an index indicating the similarity between the first image data and the second image data; The similarity calculation unit obtains a sum by arithmetic operation of the plurality of exclusive OR data by treating each of the plurality of exclusive OR data acquired for each of the plurality of pixel data as numerical data, The sum is an image processing apparatus as an index indicating the similarity.

(8) The present invention viewed from still another viewpoint is a data processing method for evaluating the degree of similarity between first data and second data each including a plurality of processing data composed of a predetermined-length bit string,
The bit string of the predetermined length in which the exclusive OR of the processing data included in the first data and the processing data included in the second data is calculated for each bit, and the obtained exclusive OR is continuous for each bit. Obtaining the exclusive OR data configured as: and calculating an index indicating the similarity between the first data and the second data, the first data and the second data, The step of calculating an index indicating the degree of similarity of each of the plurality of pieces of exclusive OR data acquired for each of the plurality of processing data is treated as numerical data, thereby calculating a sum of arithmetic operations of the plurality of exclusive OR data. A data processing method including obtaining the sum as an index indicating the similarity.

(9) According to another aspect, the present invention provides a computer program for causing a computer to execute a process of evaluating the similarity between first data and second data each including a plurality of processing data composed of a bit string of a predetermined length. The processing includes calculating the exclusive OR of the processing data included in the first data and the processing data included in the second data for each bit, and obtaining the exclusive logical for each bit obtained. Obtaining the exclusive OR data configured as the predetermined-length bit string in which the sum is continuous, and calculating an index indicating the similarity between the first data and the second data, The step of calculating an index indicating the degree of similarity between one data and the second data includes calculating each of a plurality of exclusive OR data acquired for each of a plurality of processing data. By handled as data, the total sum by arithmetic operation of a plurality of exclusive OR data, the sum is a computer program that includes an index indicating the degree of similarity.

  According to the present invention, it is possible to calculate the similarity between data by a simpler calculation than SAD.

1 is a block diagram illustrating a configuration of an image processing apparatus according to a first embodiment. FIG. 3 is a schematic diagram illustrating a detailed configuration of a data buffer unit and a processor array unit in the image processing apparatus according to the first embodiment. The schematic diagram which shows the structure of a processor element. The schematic diagram which shows the circuit structure for calculating an absolute difference. FIG. 3 is a schematic diagram illustrating a circuit configuration of an exclusive OR operation unit according to the first embodiment. 6 is a graph showing an error between exclusive OR data and an absolute difference by the exclusive OR operation unit according to the first embodiment. FIG. 9 is a schematic diagram illustrating a part of the configuration of an exclusive OR operation unit of the image processing apparatus according to the second embodiment. 9 is a graph showing an error between exclusive OR data and an absolute difference by an exclusive OR operation unit according to the second embodiment. FIG. 4 is a functional block diagram of an image processing apparatus according to a third embodiment. 10 is a flowchart showing a flow of image processing by the image processing apparatus according to the third embodiment.

  Hereinafter, preferred embodiments of the present invention will be described with reference to the accompanying drawings.

(Embodiment 1)
Hereinafter, the configuration and operation of an image processing apparatus that calculates an index indicating the degree of similarity between two image data will be described.

The image processing apparatus 100 according to the present embodiment is a processor configured by hardware (FPGA or the like) including an EXOR gate. This image processing apparatus 100 performs block matching processing of blocks of the same size extracted from each of two temporally continuous frames, and detects the relative positional relationship between the blocks with the highest similarity as a motion vector It is.
In the block matching process, the exclusive OR of the pixel data included in the two blocks is calculated, and the sum of the exclusive OR obtained for each pixel data is calculated as an index indicating the similarity between the two image data. The

  FIG. 1 is a block diagram showing the configuration of the image processing apparatus according to this embodiment. As shown in FIG. 1, the image processing apparatus 100 includes an input unit 110, a data buffer unit 120, a processor array unit 130, a summation unit (similarity calculation unit) 140, a minimum value detection unit 150, and an output. Part 160.

  The input unit 110 includes a buffer memory and the like, and can temporarily hold image data input to the image processing apparatus 100. The input unit 110 receives a macroblock image, which is reference image data used for block matching, and a candidate frame image for searching for a block similar to the macroblock image. In the present embodiment, the size of the macroblock image is 16 [pixels] × 16 [pixels], and the size of the candidate frame image is 256 [pixels] × 256 [pixels], which is larger than the macroblock image. is there. Each pixel data (process data; word data) is multi-value data having a bit length of 8 bits (a plurality of bits).

  FIG. 2 is a schematic diagram showing a detailed configuration of the data buffer unit 120 and the processor array unit 130. As shown in FIG. 2, the data buffer unit 120 includes 16 × 256 data buffers 121, 121,. The data buffers 121, 121,... Are arranged in a matrix of 16 rows and 256 columns. In the data buffers 121, 121,... For one row, one row (256 pixels) of the candidate frame image is stored. That is, the bit length of each data buffer 121 is 8 bits, and pixel data for one pixel is stored in one data buffer 121. The entire data buffer unit 121 can store pixel data for 16 rows (16 × 256 pixels) of the candidate frame image. The data buffer unit 121 functions as a shift register that shifts the candidate frame image in units of pixel data.

  The data buffers 121, 121,... Shift the stored pixel data to the data buffers 121, 121,. The pixel data in the rightmost data buffers 121, 121,... Are shifted to the leftmost data buffers 121, 121,.

  In the data buffer unit 120, the processor array unit 130 is provided in an overlapped manner in the 16 × 16 region at the right end. The processor array unit 130 has a total of 256 processor elements 131, 131,. In other words, one data buffer 121, 121,... Corresponds to each processor element 131, 131,.

The processor array unit 130 calculates the sum of exclusive ORs (hereinafter referred to as “SXOR (Sum of Exclusive-OR)”) as an index of similarity in block matching. Here, the “total sum of exclusive OR” refers to a value obtained by taking a logical value as a result of the exclusive OR operation as a numerical value and taking the total (sum as an arithmetic sum) for the numerical value.
When the candidate motion vector is d (d _x , d _y ), the SXOR value is obtained by equation (2). At this time, r (x, y) and c (x, y) represent the luminance at the coordinates (x, y) of the reference block and the candidate block, respectively.

  Each of the processor elements 131, 131,... Can hold pixel data for one pixel of the macroblock, and the macroblock pixel data and the candidate frame pixel data are mutually exclusive for each clock cycle. Output logical OR. .. Are connected to each other via the data bus 125, and the result of the exclusive OR is sequentially transmitted to the processor elements 131, 131,. When the processor element 131 receives the result of the exclusive OR from the processor element 131 directly above, the exclusive OR calculated by the processor element 131 and the received exclusive OR are added, and the processor element 131 performs intermediate processing. Retained as a result. Further, the intermediate result is transmitted to the processor element 131 immediately below the processor element 131, and the result of the exclusive OR calculated in the processor element 131 is added to the intermediate result and held as a new intermediate result. Finally, the intermediate results for 16 columns are given to the summation unit 140.

  FIG. 3 is a schematic diagram showing the configuration of the processor element 131. As described above, the processor element 131 is provided with the data buffer 121 which is an input register having a bit length of 8 bits. The processor element 131 includes an exclusive OR operation unit in which an input register 132 having a bit length of 8 bits and eight (a plurality; a number corresponding to the bit length of the processing data) EXOR gates are arranged in a line. 133, a 12-bit adder (arithmetic adder) 134, and a 12-bit output register 135 are provided.

The input register 132 holds pixel data for one pixel of the macroblock. The input register 132 and the data buffer 121 are connected to the input side of the exclusive OR operation unit 133, and the macroblock pixel data B (B _{0 to} B ₇ ) held in the input register 132 and the data The pixel data of the candidate frame image A (A _{0 to} A ₇ ) held in the buffer 121 is given, and an exclusive OR S (S _{0 to} S ₇ ) is calculated for each corresponding bit. .
The 8-bit exclusive OR data (eight logic values) obtained by the exclusive OR operation unit 133 is handled as 8-bit numerical data.
For example, when the pixel data of the macroblock is {10010010} and the pixel data of the candidate frame image is {11010110}, the exclusive OR data is {01000100}. The absolute difference in this case is also {01000100}. Therefore, in this example, the exclusive OR data that is a set of logical values and the absolute difference that is a numerical value have the same value (the same bit string).
However, the exclusive OR data does not always match the absolute difference. For example, when the pixel data of the macroblock is {10011010} and the pixel data of the candidate frame image is {11010110}, the exclusive logic The sum data is {01100100}. The absolute difference in this case is {00111100}, and the exclusive OR data and the absolute difference are different values.

  Such exclusive OR data is regarded as numerical data and is given to the input of an adder (arithmetic adder) 134. The input side of the adder 134 is also connected to the output register 135 of the processor element 131 immediately above (one row above in the same column), and an intermediate result is given from the processor element 131. An output register 135 is connected to the output side of the adder 134, and a new intermediate result obtained by adding the exclusive OR data regarded as numerical data and the intermediate result is output to the output register 135. It is like that. The output register 135 is connected to the adder 134 (the summing unit 140 for the output register 135 of the processor element 131 in the bottom row) of the processor element 131 immediately below (one row below in the same column), and the intermediate result is It is designed to output.

  As shown in FIG. 1, the summation unit 140 is connected to each of the 16 bottom row processor elements 131, 131,..., And receives intermediate results output from these processor elements 131, 131,. . Further, by adding the intermediate results as numerical data, the sum of exclusive ORs for all the pixels of the block is calculated.

  The minimum value detection unit 150 always holds the minimum value of SXOR. That is, the minimum value detection unit 150 includes a comparator and the like, compares the SXOR given from the summation unit 140 with the minimum value of the SXOR so far, and the newly given SXOR is It is determined whether or not it is smaller than the minimum value of SXOR. When the newly given SXOR is smaller than the minimum value of SXOR so far, the minimum value detection unit 150 holds this as the minimum value of SXOR. Further, when the minimum value is updated, the minimum value detection unit 150 calculates a motion vector from the macroblock and the coordinates of the search range of the candidate frame image, and stores this. When all the search for candidate frame images is completed, the minimum value detection unit 150 outputs a motion vector for the macroblock to the output unit 160.

  The output unit 160 includes a register or the like, and holds the motion vector data given from the minimum value detection unit 150. The output unit 160 outputs the motion vector data to the outside of the image processing apparatus 100.

With the configuration as described above, in the image processing apparatus 100 according to the present embodiment, the block matching process can be simplified as compared with the block matching using the SAD.
Here, FIG. 4 is a schematic diagram illustrating a circuit configuration for calculating an absolute difference, and FIG. 5 is a schematic diagram illustrating a circuit configuration of the exclusive OR operation unit 133. As shown in FIG. 4, in the absolute difference arithmetic circuit, two subtractions AB and BA are simultaneously performed on two inputs A and B, and a positive output is selected by a multiplexer. The absolute difference is calculated.
On the other hand, as shown in FIG. 5, the exclusive OR operation unit 133 is configured by eight EXOR gates 133a, 133a,..., And performs exclusive OR operation simultaneously on each EXOR gate 133a, 133a,. Therefore, the number of steps required for calculation is small.

  Also, by treating exclusive OR data consisting of multiple exclusive ORs obtained for each bit as numerical data having the concept of digits, exclusive OR data is similar to absolute difference that is numerical data. Can be handled. That is, the exclusive OR data is equal to the result obtained by excluding the carry processing from the absolute difference calculation, and has a high probability and a value close to the absolute difference. In particular, in a combination where no carry occurs, the exclusive OR data is the same as the absolute difference. For this reason, SXOR, which is an index indicating the degree of similarity, is a value that reflects the degree of similarity with high accuracy.

  In addition, since there is no sign in the exclusive OR, the same value is obtained even if A and B are replaced in the exclusive OR operation. Therefore, it is not necessary to parallelize the circuit as in absolute difference calculation, and the circuit scale can be reduced. As in this embodiment, if the calculation bit width is 8, absolute difference calculation requires 188 gates in terms of NAND elements, but the exclusive OR is 32 gates, and the circuit scale is about 6 minutes. 1 Moreover, since there is no carry in the exclusive OR, the critical path is dramatically shortened. For this reason, an improvement in processing speed can be expected.

Since the carry operation is not performed in the exclusive OR operation, the exclusive OR data is never smaller than the absolute difference when the inputs are the same. That is, when an error occurs between the exclusive OR data and the absolute difference, the exclusive OR data is always larger than the absolute difference (exclusive OR data ≧ absolute difference).
Here, when the degree of similarity between the two images to be compared is low, the pixel data included in each image is greatly different, and the absolute difference between the two pixel data is a large value. In this way, when the absolute difference between the two pixel data is large, if the exclusive OR data becomes smaller than the absolute difference, SXOR also becomes small. If the similarity is higher than the actual, erroneous evaluation is made. End up. However, as described above, the exclusive OR data always has a larger value than the absolute difference, so that the similarity between two pieces of pixel data having actually low similarity is erroneously determined to be high. Such a thing does not happen.

(Embodiment 2)
Although the exclusive OR data often takes a value close to an absolute difference, the probability that an error will occur is relatively high, and the magnitude of the error increases or decreases depending on the combination of inputs. FIG. 6 is a diagram illustrating an error between the exclusive OR data and the absolute difference by the exclusive OR calculating unit 133 according to the first embodiment. In the figure, the horizontal axis indicates input A, and the vertical axis indicates input B. Further, in the figure, the magnitude of the error is shown by shading so that the smaller the error is, the lighter it is, and the larger the error is, the darker it is. In the figure, a region surrounded by a broken line is a region where the difference between inputs A and B is small. The presence of errors in this region strongly affects the accuracy of block matching. For this reason, in this region, it is desired that the error between the exclusive OR data and the absolute difference is small. However, as can be seen from FIG. 6, a large error (dark portion) occurs in a part of the region surrounded by the broken line. For example, when the input bit string is {10000000} and {01111111}, the absolute difference is 1, whereas the exclusive OR data obtained from these inputs is treated as a numerical value (arithmetic value). The value is 255, and the error is as large as 254.
That is, as apparent from FIG. 6, when the upper 2 bits of the input bit string are {10} and {01}, respectively, the error between the exclusive OR data and the absolute difference becomes the largest.

  Therefore, in the image processing apparatus according to the present embodiment, by introducing exceptional processing in the exclusive OR operation, the exclusive OR data and the absolute data in the region where the difference between the inputs A and B is inherently small are absolute. Reduce the error with the difference. In this embodiment, exception processing is applied to the calculation of the upper bits (particularly, the most significant bit) of the exclusive OR operation unit that strongly affects the accuracy of block matching.

Hereinafter, enter each _A n XOR operation unit, _{B n,} the output will be described as _{S n.} However, n is an integer from 0 to 7, and the higher n indicates the higher bit.

The following truth table shows the relationship between the upper two bits of the input values A ₇ , A ₆ and B ₇ , B _{6 of the} exclusive OR operation unit 133 according to the first embodiment and the upper two bits of the output value SXOR. Is shown. In the table below, SAD indicates the output value of the upper 2 bits when the same input as that of the exclusive OR operation unit 133 is given to the absolute difference operation circuit.

From the above truth table, it can be seen that when the upper 2 bits of the input bit string are {10} and {01}, an error occurs between the exclusive OR data and the absolute difference. That is, {A ₇ , A ₆ }, {B ₇ , B ₆ } = {10}, {01} and {A ₇ , A ₆ }, {B ₇ , B ₆ } = {01}, {10} in case (points indicated by ○ mark in the table), but the most significant bit S ₇ of absolute differences SAD is 0, exclusive OR data most significant bit ₇ of SXOR is then equal to one.

Based on the above truth table, the most significant bit S ₇ of absolute differences SAD is expressed by the following logical expression (3).

Even when the most significant bit S ₇ of the exclusive OR data SXOR is 1, if the most significant bit S ₇ of the absolute difference SAD should be 0, the most significant bit S is exceptionally matched accordingly. ₇ should be 0. That is, the most significant bit S ₇ is not simply obtained as an exclusive OR of A ₇ and B ₇ , but if it is obtained by the above logical expression (3), it should match the most significant bit S ₇ of the absolute difference SAD. become.

Here, the logical expression (3) is equivalent to the following simplified logical expression (4).

In the exclusive OR operation unit, an EXOR gate having A ₇ and B ₇ as inputs and an EXOR gate having A ₆ and B ₆ as inputs already exist in order to calculate an exclusive OR between inputs. ing. Therefore, it is preferable to configure a logic circuit for exception processing using these EXOR gates. Therefore, when the logical expression (4) is modified so that the EXOR gate can be used, the following logical expression (5) can be derived.

  FIG. 7 is a schematic diagram illustrating a part of the configuration of the exclusive OR operation unit of the image processing apparatus according to the present embodiment. In the image processing apparatus according to the present embodiment, an exception processing circuit (exception processing unit) 236 is provided in the upper bits of the exclusive OR operation unit 233. The exception processing circuit 236 includes a total of five gates including two OR gates, two AND gates, and one NAND gate. The exception processing circuit 236 is a circuit for realizing the operation of the logical expression (6).

The exception processing circuit 236 calculates the value of the most significant bit of the absolute difference based on the upper 2 bits of the input A and the upper 2 bits of the input B, and the value of the most significant bit of the absolute difference is exclusive ORed. This is the value of the most significant bit of data.
FIG. 8 is a graph showing an error between the exclusive OR data and the absolute difference by the exclusive OR calculating unit 233 according to the present embodiment. In the figure, the horizontal axis indicates input A, and the vertical axis indicates input B. Further, in the figure, the magnitude of the error is shown by shading so that the smaller the error is, the lighter it is, and the larger the error is, the darker it is. Compared with FIG. 6, it can be seen that the upper 2 bits of the inputs A and B have reduced errors in {10} and {01}.

In the second embodiment, the exception processing circuit 236 calculates only the value of the most significant bit of the exclusive OR data, but a plurality of upper bits (for example, the upper 2 bits or the upper 3 bits of the exclusive OR data). Bit) value may be calculated.
When the exception processing circuit 236 obtains the value of X upper bits of the exclusive OR data, it is preferable to use (X + 1) or more upper bits of the inputs A and B.
Note that other configurations and operations of the image processing apparatus according to the present embodiment are the same as the configurations and operations of the image processing apparatus 100 according to the first embodiment, and thus description thereof is omitted.

(Embodiment 3)
In the present embodiment, an image processing apparatus that performs block matching using SXOR by information processing by software will be described.

  First, the configuration of the image processing apparatus according to the present embodiment will be described. FIG. 9 is a functional block diagram of the image processing apparatus according to the present embodiment. The image processing apparatus 300 includes a computer having a CPU and a memory as a main storage device. A computer program (hereinafter referred to as “image processing program”) for causing the computer to function as the image processing apparatus 300 is installed in the computer constituting the image processing apparatus 300. The following functions of the image processing apparatus 300 are exhibited when the image processing program is executed by a computer.

  The image processing apparatus 300 has functions as an input unit 301, a target block selection unit 302, an exclusive OR operation unit 303, a summation unit 304, a minimum value detection unit 305, and an output unit 306. The image processing apparatus 300 has a built-in auxiliary storage device including a hard disk device, and a candidate frame database 307 and a macroblock database 308 are configured by the auxiliary storage device.

  The input unit 301 is configured to accept input of candidate frames and macroblocks. Candidate frames accepted by the input unit 301 are stored in the candidate frame database 307, and macroblocks accepted by the input unit 301 are stored in the macroblock database 308.

  The target block selection unit 302 is for selecting a target block from the candidate frames stored in the candidate frame database 307. The target block selection unit 302 selects a 16 × 16 target block, which is a region to be processed, from 256 × 256 candidate frame images.

  The exclusive OR operation unit 303 calculates an exclusive OR of pixel data for the pixels of the target block selected by the target block selection unit 302 and the corresponding pixels of the macroblock that is the reference image. Is. The exclusive OR operation unit 303 calculates an exclusive OR of the pixel data for all 256 pixels of the target block and macroblock.

  The summation unit 304 adds the exclusive ORs obtained by the exclusive OR operation unit 303 to calculate SXOR.

  The minimum value detection unit 305 holds the minimum value of SXOR obtained by the summation unit 304, calculates a motion vector from the macroblock when the minimum value is obtained and the coordinates of the target block in the candidate frame image, Remember this.

  The output unit 306 is for outputting the motion vector obtained by the minimum value detection unit 305. The output unit 306 displays, for example, a motion vector on a display or stores a motion vector on a hard disk.

  The candidate frame database 307 stores image data of candidate frames. The macroblock database 308 stores macroblock image data that is a comparison target.

  Next, the operation of the image processing apparatus 300 according to this embodiment will be described. FIG. 10 is a flowchart showing a flow of image processing by the image processing apparatus according to the present embodiment.

  First, each of the candidate frame and macroblock input to the input unit 301 is stored in the candidate frame database 307 and the macroblock database 308 (step S1).

  Next, the block-of-interest selection unit 302 reads candidate blocks from the candidate frame database 307 and selects a block of interest that is a processing target area from the candidate frames (step S2).

  The exclusive OR operation unit 303 reads out the macroblock from the macroblock database 308, and calculates the exclusive OR of the pixel data for the selected target block and the corresponding pixels in the macroblock (step S3). . When the exclusive OR is calculated, the exclusive OR calculating unit 303 determines whether or not the exclusive OR is calculated for all the pixels of the block of interest (step S4), and the exclusive OR is calculated. If there is a pixel that has not been processed (NO in step S4), the process returns to step S3, and the exclusive OR of the pixel data is calculated for the pixel for which the exclusive OR has not been calculated (step S3). ). By repeating this, an exclusive OR is calculated for all 16 × 16 pixels.

  In step S4, when the exclusive OR is calculated for all the pixels of the block of interest (YES in step S4), the summation unit 304 calculates 256 exclusive logics calculated by the exclusive OR calculation unit 303. The sum is added to calculate SXOR (step S5).

  Next, the minimum value detection unit 305 compares the SXOR calculated by the summation unit 304 with the minimum value of SXOR calculated so far (step S6). If the new SXOR is smaller than the previous minimum value, the new SXOR is set to the minimum value, and the minimum value of SXOR is updated. At this time, the minimum value detection unit 305 calculates a motion vector from the coordinates of the block of interest when the new SXOR is calculated and the coordinates of the macroblock, and stores the motion vector. If the minimum value is smaller than the new SXOR, the previous minimum value is maintained. Note that this is the minimum value for the SXOR calculated for the first time.

  Next, it is determined whether or not the block of interest has been selected for all the regions of the candidate frame (step S7). If there remains a region not selected as the block of interest in the candidate frame (NO in step S7). Then, the process returns to step S2, an unselected region in the candidate frame is selected as a target block (step S2), and the processes after step S3 are executed.

  If the target block is selected for all regions of the candidate frame in step S7 (YES in step S7), the output unit 306 outputs a motion vector when the minimum value of SXOR is obtained (step S7). S8), the process is terminated.

(Evaluation Experiment 1)
The image processing apparatus (motion detection processor) having the configuration described in the first and second embodiments is mounted on a 2.5 mm square LSI. Verilog HDL was used as the hardware description language, Design Compiler from Synopsys was used for logic synthesis, IC Compiler of the same company was used for automatic placement and routing, and ROHM 0.18 μm design process was used for design rules. For comparison, a motion detection processor using SAD was also manufactured under the same conditions.

Table 2 shows a motion detection processor by SAD (indicated as “SAD” in Table 2), a motion detection processor according to Embodiment 1 (indicated as “SXOR” in Table 2), and a motion detection processor according to Embodiment 2. The total area and the maximum operating frequency of the motion detection processor are shown for each of them (indicated as “SXOR with exception handling” in Table 2). The area of the motion detection processor was calculated based on the total of all installed macros, and the operating frequency was calculated based on the critical path of the entire processor.

Table 3 shows a motion detection processor by SAD (indicated as “SAD” in Table 3), a motion detection processor according to the first embodiment (indicated as “SXOR” in Table 3), and a motion according to the second embodiment. For each of the detection processors (indicated as “SXOR with exception handling” in Table 3), the area of the processor array section and the maximum operating frequency are shown.

  As can be seen from Tables 2 and 3, the operating frequency of the entire processor depends on the processor array section, and the difference in area is mostly due to the processor array section. As a result, the motion detection processor using SXOR has an area reduced by about 14% for the entire processor and about 40% for the processor array compared to the motion detection processor using SAD, and the operating frequency is improved by about 1.25 times. doing. Further, the motion detection processor using SXOR with exception processing is slightly inferior in both area and operating frequency as compared with the motion detection processor using SXOR, but the difference is around 1%. As described above, in the motion detection processor using SXOR with exception processing, good results were obtained in the same manner as the motion detection processor using SXOR.

(Evaluation Experiment 2)
In addition, the present inventors conducted an evaluation experiment by software simulation in order to evaluate the performance of the image processing apparatus according to the first to third embodiments. Specifically, a motion detection program using each of SXOR, SXOR with exception handling, and SAD was implemented, and a moving image was encoded by each program. Note that the video compression standard conforms to MPEG2 (Moving Picture Experts Group phase 2), and sample videos (Football, Susie, Mobile) provided by the Video Qualiuty Experts Group (VQEG) were used for the video to be encoded. Table 4 shows the experimental environment, and Table 5 shows the experimental results.

  For measurement of noise, Peak Signal to Noise Ratio (PSNR) was used. PSNR is a ratio of noise included in an image, and is measured by comparing the pre-encoded image and the encoded image. Generally, the PSNR of an image called high image quality is 30 db or more, and all the images encoded by this experiment satisfy this. Also, as shown in Table 5, in both the motion detection by SXOR without exception processing and the motion detection by SXOR with exception processing, the error from the motion detection by SAD is within 1.0 db, It can be said that the image quality is sufficiently high. In addition, in the motion detection by SXOR with exception processing, a better result than the motion detection by SXOR was obtained for all moving images.

  Also, in motion detection using XSOR, the calculation time required for encoding can be reduced by about 12% compared to motion detection using SAD.

(Other embodiments)
In Embodiments 1 to 3 described above, the configuration using SXOR and SXOR with exception processing in motion detection for encoding a moving image has been described. However, the present invention is not limited to this. For example, in audio compression or the like, SXOR or SXOR with exception processing can be calculated.

100,300 Image processing device (data processing device)
DESCRIPTION OF SYMBOLS 120 Data buffer part 121 Data buffer 130 Processor array part 131 Processor element 132 Input register 133,233,303 Exclusive OR operation part 133a EXOR gate 134 Adder 135 Output register 140,304 Summation part (similarity calculation part)
150, 305 Minimum value detection unit 236 Exception processing circuit (exception processing unit)
302 Block selection unit 307 Candidate frame database 308 Macroblock database

Claims (9)

A data processing device for evaluating the degree of similarity between first data and second data each including a plurality of processing data composed of a bit string of a predetermined length,
The bit string of the predetermined length in which the exclusive OR of the processing data included in the first data and the processing data included in the second data is calculated for each bit, and the obtained exclusive OR is continuous for each bit. An exclusive OR operation unit for acquiring exclusive OR data configured as:
A similarity calculation unit that calculates an index indicating the similarity between the first data and the second data;
The similarity calculation unit obtains a sum by arithmetic operation of a plurality of exclusive OR data by treating each of the plurality of exclusive OR data acquired for each of the plurality of processing data as numerical data, and calculates the sum. A data processing apparatus that uses the similarity as an index. The exclusive OR operation unit includes an exception processing unit that calculates a value of an upper predetermined bit of the exclusive OR data,
The exception processing unit calculates a value of an upper predetermined bit of an absolute difference between the processing data included in the first data and the processing data included in the second data;
The exclusive OR operation unit acquires the exclusive OR data including the value of the upper predetermined number of bits of the absolute difference calculated by the exception processing unit in the upper predetermined number of bits. Data processing device. 3. The data according to claim 2, wherein the exception processing unit calculates an upper predetermined number of bits of the absolute difference based on an upper bit of the processing data of the first data and an upper bit of the processing data of the second data. Processing equipment. The exception processing unit calculates the most significant bit of the absolute difference based on the upper 2 bits of the processing data of the first data and the upper 2 bits of the processing data of the second data. Data processing equipment. 2. The exclusive OR operation unit includes a plurality of EXOR gates corresponding to each of a plurality of bits of the processing data, and executes the plurality of bits of the exclusive OR operation in parallel by the plurality of EXOR gates. The data processing apparatus of any one of -4. The exclusive OR operation unit includes a plurality of unit operation units for calculating exclusive OR of one processing data included in the first data and one processing data included in the second data, The data processing device according to any one of claims 1 to 5, wherein each unit operation unit performs an exclusive OR operation on a plurality of processing data in parallel. An image processing apparatus for evaluating the similarity between first image data and second image data each including a plurality of pixel data composed of a bit string of a predetermined length,
The bit string of the predetermined length in which the exclusive OR of the pixel data included in the first image data and the pixel data of the second image data is calculated for each bit, and the obtained exclusive OR for each bit continues. An exclusive OR operation unit for acquiring exclusive OR data configured as:
A similarity calculation unit that calculates an index indicating the similarity between the first image data and the second image data;
The similarity calculation unit obtains a sum by arithmetic operation of a plurality of exclusive OR data by treating each of a plurality of exclusive OR data acquired for each of a plurality of pixel data as numerical data, and calculates the sum. An image processing apparatus using the similarity as an index. A data processing method for evaluating the degree of similarity between first data and second data each including a plurality of processing data composed of a bit string of a predetermined length,
The bit string of the predetermined length in which the exclusive OR of the processing data included in the first data and the processing data included in the second data is calculated for each bit, and the obtained exclusive OR is continuous for each bit. Obtaining exclusive-or data configured as:
Calculating an index indicating the degree of similarity between the first data and the second data;
Including
The step of calculating an index indicating the degree of similarity between the first data and the second data is performed by treating each of a plurality of exclusive OR data acquired for each of a plurality of processing data as numerical data, thereby A data processing method comprising: calculating a sum of arithmetic logical OR data by an arithmetic operation and using the sum as an index indicating the similarity. A computer program for causing a computer to execute a process of evaluating the similarity between first data and second data, each of which includes a plurality of processing data composed of a bit string of a predetermined length,
The process is
The bit string of the predetermined length in which the exclusive OR of the processing data included in the first data and the processing data included in the second data is calculated for each bit, and the obtained exclusive OR is continuous for each bit. Obtaining exclusive-or data configured as:
Calculating an index indicating the degree of similarity between the first data and the second data;
Including
The step of calculating an index indicating the degree of similarity between the first data and the second data is performed by treating each of a plurality of exclusive OR data acquired for each of a plurality of processing data as numerical data, thereby A computer program comprising: obtaining a sum of arithmetic logical OR data by an arithmetic operation, and using the sum as an index indicating the similarity.