+

WO2002037860A1 - Moving vector detector - Google Patents

Moving vector detector Download PDF

Info

Publication number
WO2002037860A1
WO2002037860A1 PCT/JP2000/007598 JP0007598W WO0237860A1 WO 2002037860 A1 WO2002037860 A1 WO 2002037860A1 JP 0007598 W JP0007598 W JP 0007598W WO 0237860 A1 WO0237860 A1 WO 0237860A1
Authority
WO
WIPO (PCT)
Prior art keywords
search
pixel
motion vector
vector
block
Prior art date
Application number
PCT/JP2000/007598
Other languages
English (en)
French (fr)
Inventor
Mitsuyoshi Suzuki
Original Assignee
Mitsubishi Denki Kabushiki Kaisha
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Mitsubishi Denki Kabushiki Kaisha filed Critical Mitsubishi Denki Kabushiki Kaisha
Priority to JP2002540466A priority Critical patent/JPWO2002037860A1/ja
Priority to CN00817874.7A priority patent/CN1415171A/zh
Priority to EP00970180A priority patent/EP1331826A1/en
Priority to PCT/JP2000/007598 priority patent/WO2002037860A1/ja
Publication of WO2002037860A1 publication Critical patent/WO2002037860A1/ja

Links

Classifications

    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/503—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving temporal prediction
    • H04N19/51—Motion estimation or motion compensation
    • H04N19/557—Motion estimation characterised by stopping computation or iteration based on certain criteria, e.g. error magnitude being too large or early exit
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
    • H04N19/43—Hardware specially adapted for motion estimation or compensation
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/42—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals characterised by implementation details or hardware specially adapted for video compression or decompression, e.g. dedicated software implementation
    • H04N19/43—Hardware specially adapted for motion estimation or compensation
    • H04N19/433—Hardware specially adapted for motion estimation or compensation characterised by techniques for memory access
    • H—ELECTRICITY
    • H04—ELECTRIC COMMUNICATION TECHNIQUE
    • H04N—PICTORIAL COMMUNICATION, e.g. TELEVISION
    • H04N19/00—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals
    • H04N19/50—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding
    • H04N19/503—Methods or arrangements for coding, decoding, compressing or decompressing digital video signals using predictive coding involving temporal prediction
    • H04N19/51—Motion estimation or motion compensation

Definitions

  • each block obtained by dividing a frame in an image sequence is subjected to a motion estimation with respect to an already encoded frame.
  • the present invention relates to a motion vector detecting device that detects a vector.
  • FIG. 1 is a block diagram showing a configuration of a conventional motion vector detecting device.
  • FIG. 2 is a block diagram showing an example of a circuit for controlling the input / output of a memory in the search window memory unit of FIG.
  • FIG. 3 is a block diagram showing an example of the configuration of the exchanger shown in FIG. 1
  • FIG. 4 is a block diagram showing an example of the configuration of a selector unit in the horizontal switching unit shown in FIG.
  • FIG. 4 is a block diagram showing a configuration example of a selector unit in the vertical exchange unit in FIG. 3.
  • FIG. 6 is a block diagram showing an example of a circuit for controlling input / output of a memory in the reference memory unit of FIG.
  • This conventional motion vector detection device is for the case where the reference block is 16 rows and 16 columns, and the division block when the reference block is divided is 4 rows and 4 columns.
  • reference numeral 1 denotes pixel data of a frame that has already been coded by inter-frame predictive coding in an image processing method such as the H.261 method or the MPEG method, and the frame to be coded at the current time.
  • This is a pre-coded frame memory that stores pixel data for prediction in.
  • a motion vector for each block obtained by dividing the frame to be encoded is detected. That is, the horizontal and vertical distances between the position of the block in the currently encoded frame and the position of the block corresponding to the block in the already encoded frame are detected as motion vectors.
  • a pixel 141 is supplied with a write address at the time of writing pixel data to the memory 111 (I, J), and a pixel data from the memory 111 (I, J) is supplied.
  • a selector that is supplied with a read address at the time of reading and supplies one of those addresses to the memory 111 (I, J) according to the value of the write detection switch signal.
  • 13 1 is an adder that calculates the sum of the horizontal component of the search vector and the horizontal position of the upper left corner of the reference block from the upper left corner of the search window, and outputs the calculation result It is.
  • 1 32 is a subtractor that subtracts the column number I of the memory 1 1 1 (I, J) from the output value of the adder 13 1 and outputs the calculation result.
  • 1 33 is an adder that calculates the sum of the output value of the subtractor 1 32 and the constant 3 and outputs the calculation result.
  • 1 4 2 is 4 times the output value of the adder 1 3 3 and the horizontal address q (described later) of the divided process An adder that calculates the sum of the values and outputs the result.
  • 1 34 is a divider that outputs an integer part of a value obtained by dividing the output value of the adder 14 2 by a constant 4.
  • 1 35 calculates the sum of the vertical component of the search vector and the vertical position of the upper left corner of the reference project from the upper left corner of the search window, and outputs the calculation result.
  • It is. 136 is a subtracter for subtracting the row number J of the memory 111 (I, J) from the output value of the adder 135, and outputting the calculation result.
  • 13 7 is an adder that calculates the sum of the output value of the subtractor 13 6 and the constant 3 and outputs the calculation result.
  • Reference numeral 150 denotes an adder that calculates the sum of the output value of the adder 1337 and a value obtained by multiplying the vertical address (described later) of the divided block by 0.4, and outputs the calculation result.
  • a divider 38 outputs an integer part of a value obtained by dividing an output value of the adder 150 by a constant 4.
  • 13 9 is a multiplier that calculates the product of the output value of the divider 13 8 and the constant 14 and outputs the calculation result.
  • reference numeral 103 denotes the pixel data stored in the memory 1 1 1— (0, 0) to 1 1 1 1 3, 3) of the search window memory section 102.
  • the pixel blocks included in the search block that is the same size as the divided block of the reference block and that is separated from the position of the divided block of the reference block by the search vector are supplied and searched.
  • This is an exchanger that outputs each pixel data whose coordinate value is (I, J) to the pixel comparison unit 113- (I, J) of the evaluation unit 104.
  • 114 1 stores pixel data from memory 111 1 (0, J) to: L 1 1— (3, J) for each row J of the search division block. -Even the pixel is supplied, and the built-in selector section 1.5 1-(0, J)-15 1-(3, J) is used to search all pixel data from one pixel data to one pixel data.
  • This is a horizontal exchange unit that selects and outputs according to the value of the horizontal component of the torque.
  • 1 15 is a selector section 15 2 — (I, 0) of the horizontal switching section 1 14 from the L 5 1-1 (I, 3). 0) to 15 2 _ (I, 3) and the selector section 15 2 — (I, 0) to 1
  • 5 2-(1, 3) is a vertical switching unit that selects and outputs one pixel data from each pixel data according to the value of the vertical component of the search vector.
  • 123 is the sum of the column number I of the selector section 151- (I, J) and the horizontal component of the search vector.
  • I an adder that calculates the result and outputs the calculation result to the ROM 124.
  • Reference numeral 124 denotes a ROM that supplies the value of the remainder obtained by dividing the value from the adder 123 by 4 to the selector 125 as a selection signal.
  • a selector 125 selects a value from the memory 111 (S S, J) according to the value S S of the selection signal from the ROM 124 and outputs the selected value.
  • 126 is the sum of the row number J of the selector section 152- (I, J) and the vertical component of the search vector. , And outputs the calculation result to ROM127.
  • Reference numeral 127 denotes a ROM which supplies the value of the remainder obtained by dividing the value from the adder 126 by 4 to the selector 128 as a selection signal.
  • Reference numeral 128 denotes a selector for selecting and outputting a value from the selector section 151- (1, SS) in accordance with the value S S of the selection signal from the ROM 127.
  • reference numeral 5 denotes an encoded frame memory for storing pixel data of a frame to be encoded at the present time.
  • the 106 is a 16-by-16 column that divides the frame currently encoded
  • the memory stores the pixel data of the same row I and the same column J in the divided blocks.
  • each memory 1 16— (1 , J) store M pixel data of the same row I and the same column J in each divided block.
  • 145 is a multiplication that calculates the product of the vertical address of the divided block supplied from the vertical quaternary counter 144 of the block accumulator 108 and the constant 4, and outputs the calculation result. It is a vessel. 146 calculates the sum of the output value of the multiplier 144 and the horizontal address q of the divided block supplied from the horizontal quaternary counter 143 of the block accumulator 108, and stores the result in the memory. 1 16—Adder that outputs to selector 147 as a read address for (I, J).
  • the horizontal block 143 and the vertical quaternary counter 144 shown in Fig. 6 divide the divided blocks in the reference block in the horizontal direction. And the vertical direction, and those count values are used as the vertical address r and the horizontal address q of the divided block in the search window memory section 102, the switchboard 103, and the reference memory section 106.
  • the comparison result of each pixel comparison unit 1 13 — (I, J) of the evaluation unit 104 is temporarily stored for each divided block, and the above comparison results for all divided blocks constituting the block are stored.
  • each pixel comparison unit 1 13-(I, J) calculates the difference between two pixel data, and searches the reference block when the sum of the absolute values of those differences in the reference block is minimum.
  • the toll is the motion vector.
  • FIG. 7 is a diagram showing an example of a search window and a search division block
  • FIG. 8 is a diagram showing a search division block and a horizontal address and a vertical address of the search division block in the second embodiment.
  • the pre-coded frame memory 1 stores the same window I in the same row I and the same column J in the divided area when the search window is divided into areas of the same size as the divided blocks of the reference block.
  • the pixel data is output to the memory 1 1 1— (I, J) of the search window memory section 102.
  • the horizontal address q and the vertical address r in the block are allocated to each divided block when the block is divided into 16, and the horizontal address in the search window is assigned.
  • memory 1 1 1 1 (I, J) Stores the pixel data of the J-th row and the I-th column in the divided block of the horizontal address h and the vertical address V at an address having a value (14 XV + h).
  • the search vector is supplied from the motion vector detection unit 107 to the search window memory unit 102 and the exchanger 103, and the block accumulator is also stored.
  • the horizontal address q and the vertical address r of the search division block are sequentially supplied to the search window memory section 102, the exchange 103 and the reference memory section 106.
  • the water component of the search vector is supplied to the adder 131, and the vertical component of the search vector is supplied to the adder 135.
  • the value obtained by quadrupling the horizontal address q of the search division block is supplied to the adder 142, and the value obtained by quadrupling the vertical address r of the split block is supplied to the adder 150.
  • the adders 131, 1.33, 135, 137, 140, 142, 150, the subtractors 1332, 1336, the dividers 134, 133 and the multiplier 139 the read address for the memory 1 1 1— (I, J) corresponding to the supplied search vector and the horizontal address q and the vertical address r of the divided block is calculated.
  • the memory 1 1 1— (I, J) stores the pixel data stored in the supplied read address into the selector section 15 1— (0, J) to 15 1— (3, J ).
  • the read address A (I, J) for the memory 111 (1, J) is such that X is the horizontal component of the search vector, y is the vertical component of the search vector, and SWH 0 is the search component.
  • the calculation is performed according to the following equation by the calculators 13 2, 1 36, the dividers 134, 1 38 and the multiplier 1 39.
  • a (I, J) (int ((SWV 0 + y- J + r x4 + 3) / 4)) x 14 + int ((SWH 0 + x- I + q x4 + 3) / 4)
  • i n t () is a function or an operator that truncates the decimal part of its argument.
  • the selectors 151- (I, J) of the horizontal exchanger 114 are used to determine the horizontal components of the search vector supplied from the motion vector detector 107. Select one of the values from the memory 1 1 1— (0, J) to: L 1 1— (3, J), and replace the selected value ′ with the selector 1 of the vertical exchange unit 1 1 5 5 2— (1, 0) to: Output to 1 5 2 (1, 3).
  • each selector section 151- (1, J) the addition section 123 and the ROM 124 cause the column number I of the selector section 151- (1, J) and the search vector.
  • a selection signal is calculated based on the horizontal component and supplied to the selector 125.
  • the value from the memory 111 (S S, J) is output according to the value S S of the selection signal.
  • the value SS of the selection signal is calculated based on the column number I of the selector section 151- (1, J) and the horizontal component X of the search vector by the addition section 123 and the ROM 124 according to the following equation. Is calculated.
  • each selector section 15 2— (I, J) of the vertical exchange section 115 becomes a selector section according to the vertical component of the search vector supplied from the moving vector detection section 107. 1 5 1— (1, 0) to: L 5 1—Select one of the values from (I, 3), and select the value.
  • the row number J of the selector section 152- (1, J) and the search vector are determined by the adder section 126 and the ROM 127.
  • a selection signal is calculated based on the vertical component of the torque and supplied to the selector 1 28. Then, in accordance with the value SS of the selection signal, the value from the selection section 15 1— (I, SS) is output.
  • the value SS of the selection signal is determined by the addition unit 126 and the ROM 127 based on the row number J of the selector unit 152- (I, J) and the vertical component y of the search vector. It is calculated according to the formula. '
  • the encoding frame memory 105 stores the pixel data of one of the blocks obtained by dividing the frame to be encoded in the same row I and the same column J in the divided program. Each pixel is stored in memory 1 16-(I, J) every night.
  • the memory 1 16— (0, 0) to 1 16— (3, 3) of the reference memory section 106 stores the divided blocks corresponding to the supplied horizontal address q and vertical address r.
  • the pixel data is supplied to the pixel comparison unit 113- (0, 0) -113- (3, 3) of the evaluation unit 104 every clock.
  • the pixel comparison section 113- (I, J) of the evaluation section 104 converts the pixel data from the selector section 152- (1, J) of the converter 103 into: The difference from the pixel data from the memory 1 16— (I, J) of the reference memory unit 106 is calculated, and the difference is supplied to the block accumulation unit 108.
  • the block accumulating unit 108 When the pixel data difference is supplied, the block accumulating unit 108 outputs a horizontal address q and a vertical address r for designating the next divided block, and outputs the pixel data difference for one block. When is accumulated, the difference between the pixel data is output to the motion vector detection unit 107.
  • the motion vector detection unit 107 stores, as an evaluation value, the sum of absolute values of the differences between the pixel data supplied from the evaluation unit 104 in association with the search vector at that time.
  • the motion vector detecting unit 107 searches the search window for a new search vector based on the predetermined order or based on the relationship between the search vector already calculated and the evaluation value. It is supplied to the dough memory section 102 and the exchanger 103.
  • the motion vector detection unit 107 updates the search vector until the predetermined order is completed or until the evaluation value becomes equal to or less than the predetermined value.
  • the search vector when small is determined to be the motion vector.
  • the reference memory unit 106 stores the pixel data constituting the divided block obtained by dividing the reference block
  • the search window memory unit 102 stores the pixel data.
  • the search window of the encoded frame is divided into regions of the same size as the divided block, encoding is performed for each pixel data in the same row and the same column in the divided region.
  • the pixel data of the search window of the divided frame is stored, and the same row in the divided area stored in the memory 111 (I, J) of the search window memory unit 102 is stored.
  • the conventional motion vector detection device is configured as described above, the number of pixel comparison units 113- (I, J) of the evaluation unit 104 is reduced to reduce the circuit scale, Although it is possible to reduce the cost of the device, it is necessary to perform comparison of pixel data for all divided blocks constituting the entire block, and in this regard, it is necessary to reduce the time required to detect a motion vector. There was a problem that it was difficult.
  • the conventional motion vector detection device when performing bidirectional prediction, a device for detecting a forward motion vector and a device for detecting a backward motion vector are used. There were problems, such as the necessity of two devices for detection, and an increase in the size of the device.
  • the present invention has been made in order to solve the above-described problems, and includes a first storage unit ′ for storing data of pixels constituting a plurality of pixel patterns constituting a block.
  • the predetermined A second storage means for storing data of pixels in a range specified by a predetermined search vector, and selecting one pixel pattern in a block designated by the search vector in the predetermined range Means for comparing the pixel pattern selected by the selection means with the same pixel pattern stored in the first storage means for each pixel; So as to comprise a detecting means for detect the motion base-vector based on the result of comparison by means of the comparison result for each pixel patterns is approximated to a comparison result of the proc throughout required comparison result It is not necessary to compare all the pixel patterns that make up the entire block, depending on the accuracy with which the blocks are obtained, and the comparison result for
  • the present invention has been made to solve the above-mentioned problem, and has a first storage means for storing a plurality of pixel patterns constituting a work or a data of pixels constituting a plurality of divided work.
  • the data of the pixels in the predetermined range of the coded frame are obtained.
  • a plurality of search vectors which are motion vector candidates, and the same pixel pattern or the same pixel pattern in a block designated by each search vector within a predetermined range.
  • Selection means for sequentially selecting a division block, a pixel pattern or division block selected by the selection means, and a pixel pattern or division block stored in the first storage means identical to the pixel pattern or division block Means for comparing each pixel with each other, and comparison of all pixel patterns or all divided blocks by the comparison means for one search vector
  • the processing by the selection means and the comparison means for the search vector is stopped according to the comparison result of the pixel pattern or the divided vector up to that point, and the search vector is moved to the motion vector.
  • a motion vector detection device that cuts off the search vector that is unlikely to be detected, reduces the amount of calculation required to detect the motion vector, and can detect the motion vector in a short time.
  • the present invention has been made to solve the above-mentioned problem, and has a first storage means for storing a predetermined number of pixel data among the pixel data constituting a block; Second storage means for storing pixel data within a first range for detecting a forward motion vector and a second range for detecting a backward motion vector of the frames obtained
  • the search vector in the forward direction and the search vector in the backward direction are supplied, and the search vector is separated from the position of the block in the pixel data stored in the second storage means by the search vector.
  • Selecting means for selecting a predetermined number of pixel data among the pixel data in the same size range as the block at the set position, and a predetermined number of pixel data stored in the first storage means And a predetermined number of pixel data selected by the selection means.
  • Storage means required for the second storage means comprising: comparison means; and detection means for detecting a forward movement vector and a backward movement vector based on a result of the comparison by the comparison means.
  • a motion vector detection device includes: a first storage unit configured to store data of pixels constituting a plurality of pixel patterns constituting a block; and a predetermined range of an encoded frame.
  • a first storage unit configured to store data of pixels constituting a plurality of pixel patterns constituting a block
  • a predetermined range of an encoded frame In a plurality of pixel patterns composed of a predetermined number of pixels every predetermined number of pixels, each pixel of the same position in the pixel pattern has a predetermined range of pixels in the encoded frame.
  • a second storage unit for storing data, a selection unit supplied with a predetermined search vector, and selecting one pixel pattern in a block specified by the search vector within a predetermined range; and a selection unit Selected by Comparing means for comparing, for each pixel, the selected pixel pattern with the same pixel pattern stored in the first storage means, and a motion vector based on a result of the comparison by the comparing means.
  • a detecting means for detecting As a result, the comparison result for each pixel pattern approximates the comparison result for the entire block, and the comparison is not necessarily performed for all pixel patterns constituting the entire block depending on the accuracy required for the comparison result. This eliminates the need to perform the operation, and the comparison result for each block can be obtained in a short time, so that the effect that the motion vector can be detected in a short time can be obtained.
  • a motion vector detection device includes: a first storage unit that stores a plurality of pixel patterns constituting a block or data of pixels constituting a plurality of divided blocks; For each pixel of the same position in a plurality of pixel patterns or a plurality of divided blocks constituting the predetermined range, the data of the pixels in the predetermined range in the encoded frame are stored.
  • the second storage means and a plurality of search vectors that are motion vector candidates are supplied, and within the predetermined range, the same pixel pattern or each division in a block specified by each search vector is provided.
  • Selecting means for sequentially selecting blocks; a pixel pattern or a divided block selected by the selecting means; and a first storage means identical to the pixel pattern or the divided block.
  • a comparison means for comparing the pixel pattern or the divided block stored in each pixel with each pixel, and a comparison means for comparing all pixel patterns or all divided blocks by the comparison means for one search vector before the comparison is completed.
  • the processing by the selection means and the comparison means for the search vector is stopped, and the search vector is deleted from the motion vector candidates.
  • a detection means for detecting a motion vector from candidates of the vector. This has the effect of terminating the search vector that is unlikely to be a motion vector, reducing the amount of calculation required to detect the motion vector, and enabling the motion vector to be detected in a short time. can get.
  • the search vector narrowing-down unit performs the same pixel pattern or the same pixel pattern for a plurality of search vectors for each of the same pixel pattern or the same divided block. After each comparison of the same divided block is completed, at least one of the plurality of search vectors is deleted from the motion vector candidates if a predetermined condition is satisfied. This has the effect of simplifying the process for terminating the accumulation of evaluation values.
  • the comparing means calculates an evaluation value as a comparison result
  • the search vector narrowing means sets the evaluation value of each of the search vectors in a plurality of pixel patterns.
  • the cumulative values are calculated, and the cumulative values of the evaluation values for the plurality of search vectors are arranged and stored in ascending or descending order, and one or more search vectors are determined based on the order of the evaluation values in the array. Is removed from the motion vector candidates.
  • the comparing means calculates the evaluation value as a comparison result
  • the search vector narrowing means calculates the evaluation value based on the cumulative value of the evaluation values for the plurality of search vectors.
  • the search vector corresponding to the minimum or maximum evaluation value is selected, the evaluation value is accumulated for the selected search vector, and the detecting means is the cumulative number of the minimum or maximum evaluation value. But If the number is a predetermined number, the search vector is set as a motion vector. As a result, the accumulation of the evaluation values of the search vector that is likely to become a motion vector progresses more, so that the effect that the motion vector can be detected in a shorter time can be obtained. .
  • the search vector narrowing down means stores the cumulative values of the evaluation values of the plurality of search vectors in ascending or descending order, and stores The search vector corresponding to the top of the array is selected, the evaluation values are accumulated for the selected search vectors, and the accumulated evaluation values for multiple search vectors are re-ordered in ascending or descending order. If the cumulative number of evaluation values at the beginning of the array is a predetermined number, the search vector is used as the motion vector. Thus, when selecting the next search vector for executing the accumulation of evaluation values, it is sufficient to simply select the first search vector in the array, and accumulate the evaluation values for each search vector. There is no need to refer to the value, and the effect is obtained that the search vector that terminates the accumulation of the evaluation values can be selected quickly.
  • the motion vector detecting device includes a pixel data forming a block.
  • a first storage means for storing a predetermined number of pixel data in the evening; a first range of encoded frames within a first range for detecting a forward motion vector; and a backward direction.
  • a second storage means for storing pixel data within a second range for detecting a motion vector of the motion vector, a forward search vector and a backward search vector, and A predetermined number of pixel data in the pixel data in the same size range as the block at a position separated by the search vector from the position of the block in the pixel data stored in the storage means of (2).
  • Selecting means for selecting one night comprising: comparing means for comparing a predetermined number of pixel data stored in the first storage means with a predetermined number of pixel data selected by the selecting means; Forward and backward motion vectors based on the results of the comparison And a detecting means for detecting the direction of the movement vector.
  • This increases the storage capacity required for the second storage means, but has the effect of detecting vectors moving in the forward and backward directions without increasing other components.
  • FIG. 1 is a block diagram showing a configuration of a conventional motion vector detecting device.
  • FIG. 2 is a block diagram showing an example of a circuit for controlling the input and output of the memory in the search window memory section of FIG.
  • FIG. 3 is a block diagram showing a configuration example of the exchanger of FIG.
  • FIG. 4 is a block diagram showing a configuration example of a selector unit in the horizontal exchange unit of FIG.
  • FIG. 5 is a block diagram showing a configuration example of a selector unit in the vertical exchange unit of FIG.
  • FIG. 6 is a block diagram showing an example of a circuit for controlling input / output of a memory in the reference memory unit of FIG. 1.
  • FIG. 7 is a diagram showing an example of a search window and a search division block. '
  • FIG. 8 is a diagram showing a horizontal address and a vertical address of a search division block and a search division block according to the second embodiment.
  • FIG. 9 is a block diagram showing a configuration of a motion vector detecting device according to the first embodiment of the present invention.
  • FIG. 10 is a block diagram showing an example of a circuit for controlling the input and output of the memory in the search window memory section of FIG.
  • FIG. 11 is a block diagram showing a configuration example of the exchanger in FIG.
  • FIG. 12 is a block diagram showing a configuration example of a selector unit in the horizontal exchange unit of FIG.
  • FIG. 13 is a block diagram showing a configuration example of a selector unit in the vertical exchange unit of FIG.
  • Fig. 14 shows an example of the correspondence between the address of each pixel in the search window memory section and the memory in which each pixel is stored, and an example of the pixel pattern in the search window.
  • FIG. 15 shows an example of a correspondence relationship between an address of each pixel data in the reference memory unit and a memory in which each pixel data is stored, and an example of a pixel pattern in a search window.
  • FIG. 16 is a diagram showing an example of a pixel pattern selection order.
  • FIG. 17 is a diagram showing an example of pixels used by a divided block and pixels used by a pixel pattern.
  • FIG. 18 is a block diagram showing a configuration of a motion vector detecting device according to Embodiment 2 of the present invention.
  • FIG. 19 is a block diagram showing a configuration example of a motion vector detecting unit and a pixel pattern accumulating unit according to the second embodiment.
  • FIG. 20 is a view showing an example of the cumulative number of evaluation values and the cumulative value of each search vector stored in the storage means.
  • FIG. 21 is a diagram illustrating an example of discontinuing the accumulation of evaluation values according to the third embodiment.
  • FIG. 22 is a block diagram showing a configuration of a motion vector detection unit and a storage unit of a pixel pattern accumulator according to the fourth embodiment.
  • FIG. 23 is a block diagram showing a configuration example of each storage unit in FIG. 22 ⁇ ) o
  • FIG. 24 shows an example of the order of accumulation of evaluation values in the fifth embodiment.
  • FIG. 25 is a block diagram showing a configuration example of a motion vector detection unit in the motion vector detection device according to the sixth embodiment.
  • FIG. 26 is a diagram showing an example of a forward search window and a forward search block.
  • FIG. 27 is a diagram showing an example of a backward search window and a backward search block. Best mode for carrying out the invention
  • FIG. 9 is a block diagram showing a configuration of the motion vector detecting device according to the first embodiment of the present invention.
  • FIG. 10 is a block diagram showing an example of a circuit for controlling the input / output of the memory in the search window memory unit of FIG.
  • FIG. 11 is a block diagram showing a configuration example of the exchanger of FIG. 9, and
  • FIG. 12 is a block diagram showing a configuration example of a selector unit in the horizontal exchange unit of FIG.
  • FIG. 13 is a block diagram showing a configuration example of a selector unit in the vertical exchange unit of FIG.
  • the motion vector detecting device is a device in which the reference block has 16 rows and 16 columns, and the reference block has 16 pixel patterns.
  • reference numeral 1 denotes pixel data of a frame that has already been encoded by inter-frame predictive encoding in an image processing system such as the H.261 system, the MPEG system, etc. This is a pre-coded frame memory that stores pixel data for prediction in.
  • a motion vector for each block obtained by dividing the frame to be encoded is detected. That is, the horizontal and vertical distances between the position of the block in the frame currently coded and the position of the range corresponding to the block in the already coded frame are defined as the motion vector. Is detected.
  • a search window memory unit (second storage unit, selection unit) that stores the data of the pixels constituting the search window.
  • 11-(I, J) represents a plurality of pixel patterns constituting each divided block obtained by dividing the search window into the same size as the reference block.
  • This is a memory for storing pixel data at the same position.
  • the size of the search window is 64 pixels x 32 pixels
  • the size of the reference block is 16 pixels x 16 pixels
  • each pixel pattern is a pixel every three pixels in the vertical and horizontal directions.
  • the search window is first divided into eight blocks, two vertically and four horizontally, and each pixel (16 pixels vertically and 16 pixels horizontally) is a 16-pixel area of 4 pixels vertically and horizontally.
  • each pixel pattern is represented by a pixel (, 0 + p, 0). + q), pixel (4 + p, 0 + q), pixel (8 + p, 0 + q), pixel (12 + p, 0 + q), pixel (0 + p, 4 + q), pixel (4 + p, 4 + q), pixel (8 + p, 4 + q), pixel (12 + p, 4 + q), image Element (0 + p, 8 + q), pixel (4 + p, 8 + q), pixel (8 + p, 8 + q), pixel (12 + p, 8 + q), pixel (0 + p, 1 2 + q), pixel (4 + p, 1 2 + q), pixel (8 + p, 1 2 + q), and pixel (1 2 + p, 1 2 + q) Is done.
  • 41 is supplied with a write address when writing pixel data to memory 11— (I, J), and is a read address when reading pixel data from memory 11— (I, J).
  • 42 is a memory 11 1 (I, J) readout for simultaneously outputting pixel data constituting one pixel pattern from the memory 1 1— (0, 0) to: 1 1 1 (3, 3).
  • This is a read address calculation unit that calculates the address A (I, J) according to the equation (1).
  • a (1, J) (int ((yl + 1 2-4 xj) / 16) x 4 + mod (yl, 4)) xl 6 + int ((xl + 1 2-4 xi) / 16 ) x4 + mod (xl, 4) (1)
  • x l 24 + x + p
  • y l 8 + y + q
  • (x, y) is a search vector. Note that this equation is for the case where the position where the motion is 0 with respect to the origin of the search window is (24, 8).
  • reference numeral 3 denotes a search from the position of the reference block in the pixel data stored in the memory 11— (0, 0) to: L1— (3, 3) of the search window memory unit 2.
  • the pixel data constituting one of the pixel patterns in the search block at a position separated by a vector is supplied, and the 16 pixel data constituting the pixel pattern are arranged in a predetermined order and the evaluation unit (3)
  • the pixel comparators 1 3 exchangers (selectors) that output to (I, J) Means).
  • the pixel 14 is supplied with pixel data from the memory 11 (0, J) to 11 (3, J) for each row J, and has a built-in selector section. From 5 1— (0, J) to 5 1— (3, J), one pixel data is selected from all pixel data according to the value of the horizontal component of the search vector.
  • Output horizontal exchange unit. 15 is the selector section 5 2— (1,0) with a built-in pixel decoder from the selector section 5 1— (1,0) to 51— (1,3) of the horizontal exchange section 14.
  • To 5 2— (I, 3), and the selector section 52— (I, 0) to 52— (1, 3) converts one pixel data from all pixel data
  • the vertical exchange unit selects and outputs according to the value of the vertical component of the search vector.
  • 21 is the number I of the selector section 51— (I, J), the horizontal component X of the search vector, and the pixel pattern of the pixel pattern.
  • a selection signal generation unit that generates a selection signal having a value Sh calculated based on the horizontal offset p according to the equation (2).
  • Reference numeral 2 denotes a selector for selecting a value from the memory 11 (S h, J) in accordance with the value S h of the selection signal from the selection signal generation unit 21 and outputting the selected value.
  • 26 is the number J of the selector section 52— (1, J), the vertical component y of the search vector, and the pixel pattern of the pixel pattern.
  • a selection signal generation unit that generates a selection signal having a value SV calculated according to the equation (3) based on the vertical offset q.
  • reference numeral 5 denotes an encoded frame memory for storing pixel data of a frame to be encoded at the present time.
  • each memory 16— (I, J) is provided.
  • J.) store M pixel data at the same position in each pixel pattern.
  • a pixel pattern accumulator (detection means) that collectively outputs the above comparison results for the pixel pattern of the pixel vector to the motion vector detection unit 7.
  • a motion vector detection unit that detects motion as a torque. For example, each pixel comparison unit 1 3— (I , J), the difference between the two pixel data is calculated, and the search vector when the sum of the absolute values of the differences in the reference block is the minimum is taken as the motion vector.
  • FIG. 14 shows an example of the correspondence between the address of each pixel data in the search window memory section and the memory in which each pixel data is stored, and an example of the pixel pattern in the search window
  • FIG. 15 is a diagram showing an example of a correspondence relationship between each pixel address in the reference memory unit and a memory in which each pixel data is stored, and an example of a pixel pattern in a search window It is.
  • FIG. 16 is a diagram showing an example of a selection order of pixel patterns.
  • the search window memory unit 2 stores the data of the pixels constituting the search window in the coded frames in the pre-coded frame memory 1 every time the pixels at the same position in the plurality of pixel patterns are decoded. You. That is, the pixels constituting one pixel pattern are stored in different memories 11 1-(I, J).
  • the memory 11— (1, J) in the search window memory unit 2 includes a plurality of pixel patterns constituting each divided block obtained by dividing the search window into the same size as the reference block.
  • the pixel data at the same position in is stored.
  • the size of the search window is 64 pixels ⁇ 32 pixels
  • the size of the reference block is 16 pixels ⁇ 16 pixels.
  • the search window is first divided into eight blocks, two by two, four by six, and each block (16 pixels by 16 pixels)
  • the read address calculation unit 42 of the search window memory unit 2 calculates the offset (p, q) of the pixel pattern from the pixel pattern accumulation unit 8 and the search vector (X) from the motion vector detection unit 7. , y), the read address A (I, J) of the memory 11— (I, J) is calculated according to the equation (1), and is supplied to the selector 41.
  • the read address is supplied to the memory 11-(I, J) via the selector 41, and the pixel data at that address is supplied to the switch 3.
  • FIG. 14 shows a pixel pattern when the search vector is (19, 16) and the offset is (2, 1).
  • the exchanger 3 arranges the pixel data constituting the pixel pattern from the search window memory unit 2 in a predetermined order, and outputs the pixel data to the pixel comparison unit 13 1 (I, J) of the evaluation unit 4.
  • the horizontal exchange section 14 is first supplied with pixel data from the memory 11— (0, J) to: LI— (3, J) for each row J. From the pixel selectors 5 1— (0, J) to 51— (3, J), one pixel data is searched for each pixel data. Select according to the value and output to the vertical exchange unit 15. At this time, in each of the selector sections 51-(I, J), a selection signal having a value Sh calculated by the selection signal generation section 21 according to the equation (2) is supplied to the selector 22. The selector 22 selects a value from the memory 11 (Sh, J) according to the value Sh of the selection signal.
  • the vertical exchange unit 15 converts the pixel data from the selector units 51- (I, 0) to 51- (I, 3) of the horizontal exchange unit 14 into each of the built-in selectors.
  • Part 5 2 From (1, J), select all pixel data from each pixel data according to the value of the vertical component of the search vector and output.
  • the selector unit 52-(I, J) the selection signal having the value Sv calculated according to the equation (3) by the selection signal generation unit 26 is supplied to the selector 27, and the selector 27 Accordingly, the value from the selector section 51-(1, Sv) is selected according to the value SV of the selection signal.
  • the data of the pixels constituting the pixel pattern selected according to the search vector (X, y) and the offset (p,) are supplied to the evaluation unit 4.
  • the reference memory unit 6 stores one of the 16-row / 16-column processes (reference blocks) obtained by dividing the frame to be coded at this time from the coding frame memory 5.
  • One pixel at the same position in a plurality of pixel patterns is read out and stored in the built-in memory 16- (I, J). That is, each pixel constituting one pixel pattern is stored in different memories 16- (I, J).
  • the pixel pattern specified by is output to the pixel comparison unit 13-(I, J) of the evaluation unit 4 in an array similar to the array of the pixel data from the exchanger 3 to the evaluation unit 4.
  • the evaluation unit 4 includes a pixel data from each memory 16— (I, J) of the reference memory unit 6 and a pixel data from the selector unit 52— (I, J) of the exchanger 3.
  • the pixel comparison section 13 — (I, J) compares the evening and the evening with each other, and supplies an evaluation value as a comparison result to the pixel pattern accumulator 8.
  • the evaluation value at this time is, for example, the pixel data from each memory 16— (I, J) of the reference memory unit 6 and the pixel data from the selector unit 52— (I, J) of the exchanger 3.
  • the evaluation value at this time may be the sum of the squares of the difference between the two pixel values.
  • the pixel pattern accumulator 8 sequentially selects the horizontal component p and the vertical component q of the offset value of the pixel pattern in a predetermined order, and stores those values P and q in the search window memory unit 2, the exchange 3, and It is supplied to the reference memory unit 6 and accumulates the evaluation values from the pixel comparison units 13— (I, J) of the evaluation unit 4 in the case of each of the offset values p and q, and for each search vector, The evaluation values for all the pixel patterns constituting the block are collectively output to the motion vector detection unit 7.
  • the pixel pattern accumulator 8 selects offsets (p, q) of the pixel pattern without offset, for example, as shown in FIG. 16 (a).
  • three pixel patterns corresponding to the offset selected three times are as shown in FIG. 16 (b).
  • the motion vector detection unit 7 sets the next search vector in the search window memory unit 2 and the exchange 3 based on the evaluation value of one block from the pixel pattern accumulator 8, and performs an optimal search.
  • the vector is detected as a motion vector.
  • the reference memory unit 6 stores the data of the pixels forming the plurality of pixel patterns forming the blocks
  • the search window memory unit 2 stores the codes in the search window memory unit 2.
  • a predetermined search window of the structured frames a predetermined number of pixels at a predetermined number of pixels is provided.
  • the pixel data is stored, one pixel pattern is selected by the search window memory unit 2 and the exchanger 3 according to the search vector from the motion vector detection unit 7, and the selection is performed by the evaluation unit 4.
  • the pixel pattern obtained is compared with the same pixel pattern stored in the reference memory unit 6 for each pixel, and the pixel pattern is accumulated.
  • the vessel 8, the evaluation unit 4 for a plurality of pixel patterns The comparison results are summarized and the motion vector detection unit 7 detects the motion vector based on the results of those comparisons, so that the pixels used for comparison among the pixels in the block are Since the pixel pattern is distributed over the entire block, the comparison result for each pixel pattern approximates the comparison result for the entire block, and depending on the accuracy required for the comparison result, the pixel pattern that necessarily constitutes the entire block This eliminates the need to perform comparisons for all of the blocks, so that the comparison result for each block can be obtained in a short time, and the effect that a motion vector can be detected in a short time can be obtained.
  • FIG. 17 is a diagram showing an example of a pixel used by a divided block and a pixel used by a pixel pattern. That is, as shown in FIG. 17, when comparison is performed on a divided block as in the related art (FIG. 17 (a)), pixel data is locally referred to in the block, In the case where comparison is performed for the above-described pixel pattern as in the first embodiment (FIG. 17 (b)), pixel data is uniformly referred to in the block.
  • Embodiment 2 is a diagram showing an example of a pixel used by a divided block and a pixel used by a pixel pattern. That is, as shown in FIG. 17, when comparison is performed on a divided block as in the related art (FIG. 17 (a)), pixel data is locally referred to in the block, In the case where comparison is performed for the above-described pixel pattern as in the first embodiment (FIG. 17 (b)), pixel data is uniformly referred to in the block.
  • the motion vector detection device calculates the accumulation of the evaluation values in a plurality of search vectors for one pixel pattern, and searches for the search vector having the small cumulative value of the evaluation values.
  • the evaluation value for is stopped, and the search vector is deleted from the motion vector candidates.
  • FIG. 18 is a block diagram showing a configuration of a motion vector detecting device according to Embodiment 2 of the present invention.
  • 7A operates in the same manner as the motion vector detection unit 7 and calculates the evaluation value by the evaluation unit 4 for all pixel patterns or all divided blocks for one search vector. But Before completion, according to the evaluation value of the pixel pattern up to that point, the processing by the exchanger 3 and the evaluation unit 4 for the search vector is stopped, and the search vector is changed to the motion vector. It is a motion vector detection unit (detection means, search vector narrowing means) to delete from candidates.
  • FIG. 19 is a block diagram showing a configuration example of a motion vector detection unit 7A and a pixel pattern accumulator 8 according to the second embodiment.
  • 61 is an adder for adding the evaluation value from the evaluation unit 4 and the cumulative value of the past evaluation values from the storage means 66, and 66 is each search vector.
  • Storage means such as a memory and a memory for storing the cumulative number of evaluation values and the cumulative value of the evaluation value, and 67 represents the evaluation value based on the cumulative number of evaluation values and the cumulative value of each search vector. It is an arithmetic means such as a sequencer or processor that determines a search vector that terminates the calculation of.
  • FIG. 18 The other components in FIG. 18 are the same as those according to the first embodiment, and a description thereof will not be repeated.
  • the motion vector detector 7A does not continuously calculate the cumulative value of the evaluation values for all pixel patterns for each search vector, but searches for the offset (p,) of each pixel pattern. By changing the vector (x, y), the calculation is performed in parallel for a plurality of search vectors at the offset (p, q) of each pixel pattern.
  • the calculating means 67 changes the search vector (X, y) for the offset (p, q) of each pixel pattern, and stores the offset (p, q) in the search window memory section 2,
  • the search vector (x, y) is supplied to the exchange 3 and the reference memory unit 6, and the search vector (x, y) is supplied to the search window memory unit 2 and the exchange 3, and the cumulative value of the evaluation values of the search vector is calculated.
  • the data is supplied from the storage means 66 to the adder 61. Then, the evaluation values for the offset and the search vector are calculated by the evaluation unit.
  • FIG. 20 is a diagram showing an example of the cumulative number of evaluation values and the cumulative value of each search vector stored in the storage means 66.
  • the calculating means 67 selects a search vector for which the accumulation of the evaluation values is stopped based on the cumulative value of the evaluation values for each search vector. Does not execute the calculation and deletes it from motion vector candidates.
  • the motion vector detector 8A sequentially selects a plurality of search vectors for each pixel pattern, and for each search vector, Before the comparison of all the pixel patterns for one search vector is completed, the comparison of the search vector is performed according to the comparison result of the pixel patterns up to that point. Since the comparison of the pixel patterns of the search vectors was terminated, the search vector was deleted from the motion vector candidates, and the motion vector was detected from the remaining search vectors based on the result of the comparison. The search vector that is unlikely to become a motion vector is aborted, the amount of calculation required to detect the motion vector is reduced, and the motion vector can be detected in a short time. The effect is obtained that. '
  • the block is divided into a plurality of divided blocks as in the conventional technology instead of a plurality of pixel patterns, and the accumulation of the evaluation values in a plurality of search vectors for one divided block is calculated.
  • the search vector with a low cumulative value of the search vector stops accumulating the evaluation values, and the search vector is moved to the motion vector.
  • a similar effect can be obtained by deleting the file from the file candidates.
  • the motion vector detecting device is characterized in that the calculating means 67 of the motion vector detecting unit 7A performs the calculation based on the cumulative value of the evaluation value for each search vector at each cumulative number of times. Then, a search vector that terminates the accumulation of the evaluation values is selected and deleted from the motion vector candidates.
  • the configuration of the motion vector detecting device according to the third embodiment is the same as that according to the second embodiment, and a description thereof will not be repeated.
  • FIG. 21 is a diagram illustrating an example of discontinuing evaluation value accumulation according to the third embodiment.
  • the calculating means 67 of the motion vector detecting unit 7A firstly accumulates the first evaluation value of a predetermined number of search vectors, and then evaluates the evaluation value of those search vectors. Smaller than 1 Delete anything other than 6. For example, in FIG. 21, the accumulation of evaluation values for search vectors other than the search vectors (xO, yO) to (xl5, yl5) is terminated.
  • the calculating means 67 of the motion vector detection unit 7A executes the second accumulation of the evaluation values for the 16 search vectors.
  • the calculating means 67 calculates the accumulation of the evaluation values of the search vectors for which the accumulation of the evaluation values is continued.
  • the accumulation of evaluation values for search vectors that have a cumulative value of 1.5 times or more the average value is discontinued.
  • the accumulation of the evaluation values for the search vector (X4, 4) and the search vector (X7, y7) is terminated. No.
  • search vectors (xl1, y11), search vectors (xl3, y13), and search vectors (X15, y15) are obtained.
  • the search vector (xl, y1) s search vector (X12, 12) and the search vector (xl4 , 14)
  • the accumulation of evaluation values for the search vector (x9, y9) is terminated after the accumulation of evaluation values for the fifth time.
  • the calculating means 67 determines that one of the search vectors in which the accumulation of the evaluation values is continued is one of the search vectors having the largest cumulative value of the evaluation values. The accumulation of evaluation values for is terminated. However, if the number of search vectors that continue to accumulate evaluation values becomes 2, the accumulation of evaluation values for the search vectors is not terminated. Then, among the search vectors remaining until the end, the one with the smallest evaluation value is regarded as the motion vector.
  • the operation of the other components is the same as that according to the second embodiment, and a description thereof will not be repeated.
  • the rating The conditions for terminating the accumulation of the value are not limited to the above-described method, and the number of search vectors in the first and last rounds, the cumulative number of times for changing the conditions, and the like may of course be changed.
  • the calculating means 67 of the motion vector detecting unit 7A calculates the evaluation value based on the cumulative value of the evaluation value for each search vector at each cumulative number. Since the search vector for terminating the accumulation of the motion vectors is selected and deleted from the motion vector candidates, the effect of simplifying the process for terminating the accumulation of the evaluation values is obtained.
  • the motion vector detecting device is the motion vector detecting device according to the third embodiment, wherein the accumulated values of the evaluation values for the plurality of search vectors are arranged in ascending or descending order. In this way, one or more search vectors are deleted from the motion vector candidates based on the order of the evaluation values in the array.
  • FIG. 22 is a block diagram showing a configuration of a motion vector detection unit 7A and a storage means 66 of a pixel pattern accumulator 8A according to the fourth embodiment.
  • 7 1 ⁇ 1 to 7 1 ⁇ (n + 1) constitute a shift register as storage means 66 (n + 1) pieces ( For example, 17 storage units.
  • FIG. 23 is a block diagram showing a configuration example of each storage unit in FIG. In each storage unit ⁇ 1 shown in FIG. 23, reference numeral 81 denotes the accumulated value E (i) of the accumulated data stored in the register 84 and the accumulated value E (i) of the accumulated data from the pixel pattern accumulator 8 A.
  • a comparator for comparing the accumulated value E (new) with a comparator 8 2 is a comparison result from the comparator 81 of the built-in storage unit 7 1-i, and a comparison result of the storage unit 7 1-(i _ 1) of the preceding stage. Comparison result from comparator 81, and comparison of storage unit 7 1 — (i + 1) at the subsequent stage Based on the comparison result from the storage unit 81, the accumulated data from the preceding storage unit 7 1— (i-1) and the accumulated data from the subsequent storage unit 7 1— (i + 1) are stored.
  • a selection signal for selecting one of the accumulated data of the storage unit 71 1-i, the new accumulated data from the pixel pattern accumulator 8A, and the accumulated data having a predetermined maximum value as the accumulated value is generated.
  • Reference numeral 83 denotes a selector for selecting any one of the accumulated data based on the selection signal from the control circuit 82, and reference numeral 84 denotes a register for storing the accumulated data.
  • the arithmetic means 67 controls the control circuit 82 of each storage unit 71-i to cause the selector 83 to select accumulated data having a predetermined maximum value, and to cause the register 84 to select. .
  • each storage unit 7 1—i stores the accumulated value E (i) of the accumulated data stored in the register 84 and the accumulated value E (i) of the accumulated data from the pixel pattern accumulator 8A. It compares with the accumulated value E (new), That is, the control circuit 82, and the storage units 7 1-(i-1) and 7 1-(i + 1) of the preceding and succeeding stages determine whether or not E (i)> E (new). To the control circuit 82.
  • the control circuit 82 when E (i)> E (new) is not satisfied, the control circuit 82 generates a selection signal for selecting the accumulated data of the register 84, and when E (i)> E (new) is satisfied. If E (i-1)> E (new) for i> l, a selection signal for selecting new accumulated data from the pixel pattern accumulator 8A is generated, and for i> l If E (i-1)> E (new), a selection signal for selecting the accumulated data from the register 84 in the memory 71-(i-1) in the preceding stage is generated. The control circuit 82 generates the selection signal and supplies it to the selector 83.
  • the selector 83 In response to the selection signal, the selector 83 accumulates the accumulated data from the register 84 and the accumulated data from the pixel pattern accumulator 8 A—the evening and previous storage units 7 1-(i-1) and 7 1-(i + Select one of the cumulative data from 1) and supply it to Regis 84.
  • the register 84 updates the stored cumulative data with the supplied cumulative data in synchronization with a predetermined clock signal CLK.
  • the evaluation values for the n search vectors are stored in the storage unit 66 in ascending order by the accumulation of the first evaluation values.
  • the accumulated data is supplied to the arithmetic means 67 and the pixel pattern accumulator 8A from the first storage unit 71-1, that is, the storage unit having the accumulated data having the smallest accumulated value.
  • the calculating means 67 specifies the search vector and the next pixel pattern in the accumulated data to calculate the evaluation value.
  • the pixel pattern accumulator 8A stores the evaluation value from the storage unit 66.
  • the evaluation value from the evaluation unit 4 is accumulated to the evaluation value in the accumulated data of, and the accumulation count is increased by one to generate a new accumulated data. Supply to i.
  • the arithmetic means 67 controls the (n + 1) -th control circuit 82 of the storage sections 71-1 to 71- (n + 1) to store the (n + 1) -th storage section 71- (n + 1 ),
  • the new cumulative data is memorized in the regis 84.
  • the arithmetic means 67 shifts the accumulated data stored in the register 84 of the storage units 7 1-1 to 7 1-(n + 1), and the storage unit 7 1-(i +1)
  • the storage unit 7 1— 1 to 7 1— (n ⁇ 1) stores the accumulated data with the accumulated count of 1, and the storage unit 7 1—n has the accumulated count of 2 and A certain accumulated data is stored.
  • the accumulated data (the accumulated data having the smallest accumulated value among the accumulated data whose accumulation count is 1) is stored in the first storage unit 71-1—1 by the arithmetic means 67 and the pixel pattern accumulator 8A. Supplied.
  • the calculating means 67 specifies the search vector and the next pixel pattern in the accumulated data and calculates the evaluation value.
  • the pixel pattern accumulator 8A accumulates the evaluation value from the evaluation unit 4 on the evaluation value in the accumulated data from the storage unit 66, and The number of times is increased by 1 to generate new accumulated data, which is supplied to each storage unit 7 1-i of the storage unit 66.
  • the arithmetic means 67 operates only the control circuit 82 of the storage unit ⁇ 1-n for storing the accumulated data whose accumulation number is 2, and the new accumulated value E (new) is stored in the register 8
  • the new cumulative value E (new) is greater than or equal to the cumulative value E (n) of Reg.
  • the accumulated data of the register section 84 of the storage section 7 1-2 to 7 1-n is sequentially stored in the register section 84 of the storage section 7 1-1 to 7 1-(n-1).
  • the accumulated data is stored in the register 84 of the storage unit 7 1-n.
  • the calculating means 67 calculates the register value of the storage unit 71-2-71- (n-1).
  • the accumulated data in the evening 84 is shifted, and is sequentially stored in the register 84 of the storage unit 7 1-l to 7 1-(n-2), and the new accumulated data is stored in the storage unit 7 1-(n- 1)
  • the calculating means 67 calculates the register value of the storage unit 71-2-71- (n-1).
  • the memory 7 1; 7 7 1— (n ⁇ 2) stores the accumulated data whose cumulative number is 1.
  • the storage units 7 1-(n ⁇ 1) and 7 1 ⁇ n store the accumulated data whose cumulative number is 2. One night is remembered.
  • the evaluation values are calculated for the m-th search vector sequentially shifted to the storage unit 71-1, and the new accumulated data is calculated.
  • the generated arithmetic means 67 operates the control circuit 82 of the storage unit 7 1— (n—m + l) to 71—n to store the accumulated data having the accumulated number of 2 to obtain the new accumulated value.
  • the storage unit 7 1 1 2 to 7 1—j is shifted the accumulated data of the evening of 84, and is sequentially stored in the memory unit 7 1—1 to 7 1— (j-1) at the evening of 84.
  • the new cumulative data is stored in the storage unit 7 1 —J Regis E 84 To ⁇ .
  • the calculating means 67 calculates the value of the number n of the search vectors as Update to the value (n-D).
  • the third and subsequent accumulations are performed in the same way as the accumulation of the second evaluation value.
  • the motion vector detecting device includes a search vector corresponding to the minimum or maximum evaluation value in the cumulative evaluation value of the plurality of search vectors by the evaluation unit 4. Select the search vector, accumulate the evaluation values for the selected search vector, and if the number of accumulations of the minimum or maximum evaluation value is a predetermined number, move the search vector to the It is intended to be a supplement.
  • the configuration of the motion vector detecting device according to the fifth embodiment is the same as that according to the second embodiment, and the operation of the motion vector detecting unit 7A Only different.
  • FIG. 24 is a diagram illustrating an example of an order of accumulation of evaluation values according to the fifth embodiment.
  • the calculating means 67 of the motion vector detection unit 7A firstly accumulates the first evaluation value of a predetermined number of search vectors, and then calculates the evaluation value of the search vectors. Small ones Delete anything but six.
  • the calculating means 67 of the motion vector detecting unit 7A causes the second and subsequent evaluation values to be accumulated for the 16 search vectors.
  • the calculating means 67 selects the search vector having the smallest cumulative value of the evaluation values from the 16 search vectors regardless of the cumulative number. Then, for the search vector, an evaluation value is calculated by designating the next pixel pattern at an offset, the evaluation value is accumulated, and the accumulated evaluation value is updated.
  • the calculating means 67 calculates the accumulation of the evaluation value until a search vector having a predetermined number of times (the same number as the number of pixel patterns) of the search vector with the minimum value of the evaluation value appears. For the search vector having the minimum value, the evaluation value of the next pixel pattern is accumulated, the cumulative value of the evaluation value is updated, and the cumulative number of search vectors having the minimum evaluation value is a predetermined number.
  • the search vector that is (the number of pixel patterns) is the motion vector.
  • the search vector corresponding to the minimum value or the maximum value in the cumulative value of the evaluation values by the evaluation unit 4 for a plurality of search vectors is selected. Then, the evaluation value is accumulated for the selected search vector, and if the cumulative number of the minimum or maximum evaluation value is a predetermined number, the search vector is set as a motion vector candidate. In this way, the accumulation of evaluation values for search vectors that are likely to become motion vectors progresses further, so that motion vectors can be detected in a shorter time. The effect is obtained. Further, since the search vector having the smallest cumulative value is always selected, the search vector having the smallest cumulative value at the predetermined cumulative number of times is surely regarded as the motion vector. Implementation form ⁇ 6.
  • the motion vector detection device is the motion vector detection device according to the fifth embodiment, wherein the accumulated values of the evaluation values for the plurality of search vectors are arranged in ascending or descending order.
  • the search vector corresponding to the top of the array is selected, the evaluation values are accumulated for the selected search vector, and the accumulated evaluation values for a plurality of search vectors are calculated. Rearranged in ascending or descending order, and when the cumulative number of evaluation values at the top of the array is a predetermined number, the search vector is set as a motion vector. Things.
  • FIG. 25 is a block diagram showing a configuration example of a motion vector detection unit 7A in the motion vector detection device according to the sixth embodiment.
  • 7 1 ⁇ 1 to 7 1 ⁇ n represent n accumulated data so that the accumulated values of the evaluation values for n (for example, 16) search vectors are in ascending order.
  • N is a storage unit that constitutes a shift register that stores the evaluation values.
  • 67 is a unit for executing the accumulation of the evaluation value for the search vector in the accumulated data of the storage unit 71-1-1.
  • the accumulated evaluation values of the search vector are rearranged in ascending order, and when the cumulative number of evaluation values at the head of the array is a predetermined number, the search vector is calculated as a motion vector. is there.
  • the other components of the motion vector detecting device according to the sixth embodiment are the same as those according to the fifth embodiment, and a description thereof will not be repeated.
  • the storage unit 71-i is the same as the storage unit 71-i shown in FIG.
  • the arithmetic means 67 controls the control circuit 82 of each storage unit 71 1 i to cause the selector 83 to select accumulated data having a predetermined maximum value, and to cause the register 84 to select. .
  • each storage unit 7 1—i stores the accumulated value E (i) in the accumulated data stored in the register 84 and the accumulated data in the accumulated data from the pixel pattern accumulator 8A.
  • the control circuit 82 compares the accumulated value E (n ew) with the accumulated value E (n ew), that is, whether or not E (i)> E (n ew), and the storage sections at the preceding and subsequent stages. It is supplied to the control circuits 82 of 7 1— (i-1) and 7 1— (i + 1).
  • the control circuit 82 when E (i)> E (new) is not satisfied, the control circuit 82 generates a selection signal for selecting the accumulated data of the register 84, and when E (i)> E (new) is satisfied. If E (i-1)> E (new) for i> l, a selection signal for selecting new accumulated data from the pixel pattern accumulator 8A is generated, and for i> l If E (i-1)> E (new), a selection signal for selecting the accumulated data from the register 84 of the storage unit 7 1-(i-1) in the preceding stage is generated. The control circuit 82 generates the selection signal and supplies it to the selector 83.
  • the selector 83 In response to the selection signal, the selector 83 accumulates the accumulated data from the register 84 and the accumulated data from the pixel pattern accumulator 8 A—the evening and previous storage units 7 1— (i ⁇ 1), 7 1— (i + 1) Select one of the accumulated data from and supplies it to Regis 84.
  • the register 84 updates the stored cumulative data with the supplied cumulative data in synchronization with a predetermined clock signal CLK.
  • the accumulated data of the n search vectors is stored in the storage means 66 in the ascending order of the evaluation values (accumulated values) by the first accumulation of the evaluation values.
  • the calculating means 67 calculates the accumulated data stored in the first storage unit 711, that is, the accumulation data having the smallest accumulated value.
  • the next pixel pattern is specified by offset for the search vector in the night, and the next evaluation value is calculated.
  • the evaluation value is supplied from the evaluation unit 4 to the pixel pattern accumulator 8A.
  • the new accumulated data is supplied from the pixel pattern accumulator 8 A to the comparators 81 and selectors 83 of the storage units 71-1 to 71-n.
  • each storage unit 7 1 i stores the accumulated value E (i) of the accumulated data stored in the register 84 and the accumulated value E (new) of the accumulated data from the pixel pattern accumulator 8 A. ) And the result of the comparison, that is, whether or not E (i)> E (new) is determined by the control circuit 82 and the preceding and succeeding storage units 7 1— (i ⁇ 1), 7 1— (i + 1) are supplied to the control circuit 82.
  • the storage unit 7 1- Generate a selection signal to select the accumulated data from (i + 1), and if E (i + 1)> E (new) and not E (i)> E (new), Generate a selection signal from the pattern accumulator 8 A for selecting a new accumulated data, and E (i)> E (new) and E (i + 1)> E (new) If the Regis 84 generates a selection signal to select the cumulative de-night.
  • the control circuit 82 of the storage unit 71-n When E (n)> E (n ew) is not satisfied, the control circuit 82 of the storage unit 71-n generates a selection signal for selecting new accumulated data from the pixel pattern accumulator 8A.
  • the control circuit 82 generates a selection signal and supplies it to the selector 83.
  • the selector 83 selects one of the accumulated data from the register 84, the accumulated data from the pixel pattern accumulator 8A, and the accumulated data from the memory 71- (i + 1) in the subsequent stage. Choose one and supply to Regis Evening 84.
  • the register 84 updates the stored accumulated data with the supplied accumulated data in synchronization with a predetermined clock signal CLK.
  • the accumulation of the evaluation values for the second and subsequent times the accumulation of the evaluation values for the search vector having the smallest cumulative value is sequentially performed, and a new accumulated data for the search vector is obtained.
  • the data is supplied to the storage means 66, the original accumulated data of the search vector is discarded, and n accumulated data including the new accumulated data are arranged in ascending order of the accumulated value. .
  • the accumulated data are arranged in ascending order of the accumulated values of the evaluation values, but may be arranged in descending order depending on how the evaluation values are calculated.
  • the cumulative values of the evaluation values for a plurality of search vectors are arranged and stored in ascending or descending order, and the search corresponding to the top of the array is performed.
  • Select a vector accumulate the evaluation values for the selected search vector, rearrange the accumulated evaluation values for multiple search vectors in ascending or descending order, and evaluate the top of the array.
  • the search vector is set as a motion vector, so the next time a search vector for executing evaluation value accumulation is selected, an array
  • the search vector at the beginning of the search vector only needs to be selected, and there is no need to refer to the cumulative value of the evaluation values for each search vector, and the accumulation of the evaluation values is terminated. This has the effect of being able to do so.
  • the motion vector detecting device when performing bidirectional prediction as in the MPEG 2 method, performs a predetermined row and a predetermined line from a block position in an encoded frame. Rows of forward movement
  • the pixel data of the first search window for detecting the vector and the second search window for detecting the backward motion vector are stored in the search window memory unit 2 in the same manner as described above. Thus, a forward motion vector and a backward motion vector are detected.
  • the configuration of the motion vector detecting device according to the seventh embodiment is the same as that according to any one of the first to sixth embodiments.
  • the memory 111 of the search window memory unit 2 (I , J) stores pixel data in the forward and backward search windows.
  • FIG. 26 is a diagram showing an example of a forward search window and a forward search block.
  • FIG. 27 shows an example of a backward search window and a backward search block.
  • the memory 11-(I, J) of the search window memory unit 2 stores pixel data in the forward search window, and thereafter, The pixel data in the backward search window is stored at the address.
  • the forward motion vector is searched and detected as in the above-described first to sixth embodiments.
  • a backward motion vector is searched and detected in the backward search window as in the above-described first to sixth embodiments.
  • the first search window for detecting a forward motion vector in a predetermined row and a predetermined column from a block position in an encoded frame is stored in the search window memory unit 2 and the forward motion vector and the backward motion vector are stored from the data. Since the motion vector is detected, the search window Although the storage capacity required for the memory section 2 is increased, an effect is obtained that the forward and backward motion vectors can be detected without increasing other components.
  • the seventh embodiment is applied to any of the first to sixth embodiments, it may be applied to a conventional motion vector detecting device.
  • the number of pixels in the above search window, blocks and pixel patterns, and the number of memories 11- (I, J) and 16- (I, J) are only examples and may be changed as necessary. May be other numbers.
  • the present invention is suitable for detecting a motion vector in an image processing method for performing motion prediction.

Landscapes

  • Engineering & Computer Science (AREA)
  • Multimedia (AREA)
  • Signal Processing (AREA)
  • Computing Systems (AREA)
  • Theoretical Computer Science (AREA)
  • Compression Or Coding Systems Of Tv Signals (AREA)

Description

明 細 書 動きべク トル検出装置 技術分野
この発明は、 H . 2 6 1方式、 M P E G ( Moving Picture Experts Group) 方式などの画像処理方式において、 画像デ一夕におけるフレ一 ムを分割した各プロックについて、 既に符号化されたフレームに対する 動きべク トルを検出する動きべク トル検出装置に関するものである。 背景技術
第 1図は、 従来の動きべク トル検出装置の構成を示すプロック図であ る。 第 2図は、 第 1図のサ一チウイ ン ドウメモリ部におけるメモリの入 出力を制御する回路の一例を示すブロック図である。 第 3図は、 第 1図 の交換器の構成例を示すブロック図であり、 第 4図は、 第 3図の水平交 換部におけるセレクタ部の構成例を示すプロック図であり、 第 5図は、 第 3図の垂直交換部におけるセレクタ部の構成例を示すプロック図であ る。 第 6図は、 第 1図のリファレンスメモリ部におけるメモリの入出力 を制御する回路の一例を示すブロック図である。
なお、 この従来の動きベク トル検出装置は、 リ ファレンスプロックが 1 6行 1 6列であり、 リファレンスブロックを分割したときの分割プロ ックが 4行 4列である場合のものである。
第 1図において、 1は、 H . 2 6 1方式、 M P E G方式などの画像処 理方式においてフレーム間予測符号化により既に符号化されたフレーム の画素データであって、 現時点で符号化されるフレームにおける予測の ための画素デ一夕を記憶する既符号フレームメモリである。 なお、 現時 点で符号化されるフレームの予測においては、 符号化されるフレームを 分割した各ブロックに対する動きベク トルが検出される。 すなわち、 現 時点において符号化されるフレームにおけるそのブロックの位置と、 既 に符号化されたフレームにおけるそのプロックに対応する範囲の位置と の水平方向および垂直方向の距離が動きべク トルとして検出される。
1 0 2は、 リファレンスブ口ックを所定の個数に分割したときの分割 ブロックと同一の大きさの領域にサ一チウィ ン ドウを分割したときの、 分割後の領域における同一の行 Iかつ同一の列 Jの画素デ一夕を記憶す るメモリ 1 1 1 — ( I , J ) を有するサーチウィ ンドウメモリ部である 。 すなわち、 メモリ 1 1 1 一 （ I， J ) は、 分割プロヅクの画素の数と 同一の数だけ設けられ、 リファレンスプロヅクを N個に分割したときの 分割ブロックでサーチウイ ン ドウが （N X M ) 個に分割された場合、 各 メモリ 1 1 1 一 （ I , J ) には、 各領域における同一の行 Iかつ同一の 列 Jの （N x M ) 個の画素データが記憶される。
第 2図において、 1 4 1は、 メモリ 1 1 1 一 （ I , J ) への画素デー 夕書込み時に書込みァドレスを供給され、 メモリ 1 1 1一ズ I , J ) か らの画素デ一夕読出し時に読出しアドレスを供給され、 書込みノ検出切 替信号の値に応じて、 それらのアドレスのいずれかをメモリ 1 1 1 一 （ I， J ) に供給するセレクタである。
1 3 1は、 探索べク トルの水平成分と、 サ一チウイ ン ドウの左上角か らのリファレンスブロックの左上角の水平方向の位置との和を計算し、 その計算結果を出力する加算器である。 1 3 2は、 加算器 1 3 1の出力 値からメモリ 1 1 1 一 （ I , J ) の列番号 Iを減算し、 その計算結果を 出力する減算器である。 1 3 3は、 減算器 1 3 2の出力値と定数 3との 和を計算し、 その計算結果を出力する加算器である。 1 4 2は、 加算器 1 3 3の出力値と、 分割プロヅクの水平ア ドレス q (後述） を 4倍した 値との和を計算し、 その計算結果を出力する加算器である。 1 3 4は、 加算器 1 4 2の出力値を定数 4で除した値の整数部を出力する除算器で ある。
1 3 5は、 探索ベク トルの垂直成分と、 サ一チウイ ン ドウの左上角か らのリファレンスプロヅクの左上角の垂直方向の位置との和を計算し、 その計算結果を出力する加算器である。 1 3 6は、 加算器 1 3 5の出力 値からメモリ 1 1 1一 （ I , J ) の行番号 Jを減算し、 その計算結果を 出力する減算器である。 1 3 7は、 減算器 1 3 6の出力値と定数 3との 和を計算し、 その計算結果を出力する加算器である。 1 5 0は、 加算器 1 3 7の出力値と、 分割プロックの垂直ァドレス （後述） を.4倍にし た値との和を計算し、 その計算結果を出力する加算器である。 1 3 8は 、 加算器 1 5 0の出力値を定数 4で除した値の整数部を出力する除算器 である。 1 3 9は、 除算器 1 3 8の出力値と定数 1 4との積を計算し、 その計算結果を出力する乗算器である。
1 4 0は、 除算器 1 3 4の出力値と乗算器 1 3 9の出力値との和を計 算し、 その計算結果をメモリ 1 1 1 一 （ I , J ) に対する読出しァドレ スとしてセレクタ 1 4 1に供給する加算器である。
第 1図に戻り、 1 0 3は、 サーチウィ ン ドウメモリ部 1 0 2のメモリ 1 1 1— ( 0， 0 ) 〜 1 1 1一 （ 3， 3 ) に記憶された画素デ一夕のう ちの、 リファレンスブロックの分割ブロックと同一の大きさで、 リファ レンスブ口ヅクの分割プロヅクの位置から探索べク トルだけ離れた位置 の探索ブロックに含まれる画素デ一夕を供給され、 探索.分割プロヅクに おける座標値が （ I , J ) である各画素データを評価部 1 0 4の画素比 較部 1 1 3— （ I , J ) にそれそれ出力する交換器である。
第 3図に示す交換器 1 0 3において、 1 1 4は、 探索分割プロックの' 行 Jごとにメモリ 1 1 1一 （ 0 , J ) 〜： L 1 1— ( 3 , J ) から画素デ —夕を供給され、 内蔵のセレクタ部 1.5 1— （ 0 , J ) 〜 1 5 1— （ 3 , J ) によりすベての画素デ一夕からそれそれ 1つの画素デ一夕を探索 べク トルの水平成分の値に応じて選択し、 出力する水平交換部である。
1 1 5は、 水平交換部 1 1 4のセレクタ部 1 5 1— （ I , 0) 〜： L 5 1 一 （ I , 3 ) から、 画素データを内蔵のセレクタ部 1 5 2— （ I , 0 ) 〜 1 5 2 _ ( I , 3 ) に供給され、 セレクタ部 1 5 2— ( I , 0) 〜 1
5 2 - ( 1， 3 ) によりすベての画素デ一夕からそれそれ 1つの画素デ 一夕を探索べク トルの垂直成分の値に応じて選択し、 出力する垂直交換 部である。 ·
第 4図に示すセレクタ部 1 5 1— （ I , J ) において、 1 2 3は、 セ レクタ部 1 5 1— ( I , J) の列番号 Iと探索べク トルの水平成分との 和を計算し、 その計算結果を ROM 1 24に出力する加算器である。 1 24は、 加算器 1 2 3からの値に対して 4で除した剰余の値を選択信号 としてセレクタ 1 2 5に供給する R OMである。 1 2 5は、 ROM 1 2 4からの選択信号の値 S Sに応じてメモリ 1 1 1— ( S S , J ) からの 値を選択し、 出力するセレクタである。
第 5図に示すセレクタ部 1 5 2— ( I , J ) において、 1 2 6は、 セ レクタ部 1 5 2— ( I , J ) の行番号 Jと探索べク トルの垂直成分との 和を計算し、 その計算結果を R OM 1 2 7に出力する加算器である。 1 27は、 加算器 1 2 6からの値に対して 4で除した剰余の値を選択信号 としてセレクタ 1 2 8に供給する R OMである。 1 2 8は、 ROM 1 2 7からの選択信号の値 S Sに応じてセレクタ部 1 5 1— ( 1， S S) か らの値を選択し、 出力するセレクタである。
第 1図に戻り、 5は、 現時点で符号化されるフレームの画素データを 記憶する符号化フレームメモリである。
1 0 6は、 現時点で符号化されるフレームを分割した 1 6行 1 6列の ブロックのうちのいずれかのブロック （ リ ファ レンスブロック） を所定 の個数の分割プロックに分割したときの、 その分割プロックにおける同 一の行 Iかつ同一の列 Jの画素デ一夕を記憶するメモリ 1 1 6— （ 1， J ) を有するリ ファ レンスメモリ部である。 すなわち、 メモリ 1 1 6— ( 1， J ) は、 分割プロックの画素の数と同一の数だけ設けられ、 リフ アレンスプロックを M個の分割プロックに分割した場合、 各メモリ 1 1 6— ( 1， J ) には、 各分割ブロックにおける同一の行 Iかつ同一の列 Jの M個の画素データが記憶される。
第 6図において、 14 5は、 ブロック累積器 1 08の垂直 4進カウン 夕 1 44より供給される分割プロックの垂直ァド レス と定数 4との積 を計算し、 その計算結果を出力する乗算器である。 1 46は、 乗算器 1 4 5の出力値と、 ブロック累積器 1 0 8の水平 4進カウン夕 143より 供給される分割プロックの水平アドレス qとの和を計算し、 その計算結 果をメモリ 1 1 6— ( I , J ) に対する読出しアドレスとしてセレクタ 1 47に出力する加算器である。 147は、 メモリ 1 1 6— （ I , J ) への画素データ書込み時に書込みァドレスを供給され、 メモリ 1 1 6— ( 1， J ) からの画素デ一夕読出し時に読出しア ドレスを供給され、 書 込み/検出切替信号の値に応じて、 それらのアドレスのいずれかをメモ リ 1 1 6— （ I， J ) に供給するセレク夕である。
第 1図に戻り、 1 04は、 リ ファ レンスメモリ部 1 0 6の各メモリ 1 1 6 - ( I , J ) ( 1 = 0 , · · · , 3 , J = 0 , . . · , 3) の画素 デ一夕と、 交換器 1 0 3のセレクタ部 1 5 2— （ 1， J ) からの画素デ —夕とをそれぞれ比較する画素比較部 1 1 3— （ I , J ) を有する評価 部である。
1 0 8は、 第 6図に示す水平 4進カウン夕 143および垂直 4進カウ ン夕 144により リ ファ レンスブロック内の分割ブロックを水平方向お よび垂直方向についてカウントしていき、 それらのカウン ト値を分割ブ ロックの垂直アドレス rおよび水平アドレス qとしてサーチウィ ンドウ メモリ部 1 0 2、 交換器 1 0 3およびリ ファ レンスメモリ部 1 0 6に供 給するとともに、 その評価部 1 04の各画素比較部 1 1 3— （ I , J ) の比較結果を分割プロックごとに一時的に蓄積し、 プロックを構成する すべての分割プロックに対する上記比較結果をまとめて動きべク トル検 出部 1 07に出力するプロック累積器である。
1 0 7は、 プロック累積器 1 0 8からの 1プロック分の比較結果に基 づいて、 最適な探索べク トルを動きべク トルとして検出するとともに、 サーチウィンドウメモリ部 1 0 2および交換器 1 03における探索べク トルを設定する動きべク トル検出部である。 例えば、 各画素比較部 1 1 3 - ( I , J ) により 2つの画素デ一夕の差を算出させ、 リ フ ァレンス プロックにおけるそれらの差の絶対値の総和が最小であるときの探索べ ク トルが動きべク トルとされる。
次に動作について説明する。 ·
第 7図は、 サ一チウイ ンドウおよび探索分割プロックの一例を示す図 であり、 第 8図は、 実施の形態 2における探索分割ブロックおよび探索 分割ブロックの水平アドレスおよび垂直アドレスを示す図である。
まず、 既符号フレームメモリ 1は、 サ一チウイ ン ドウをリ フ ァレンス プロックの分割プロックと同一の大きさの領域に分割したときの、 分割 後の領域における同一の行 Iかつ同一の列 Jの画素デ 夕をサーチウイ ン ドウメモリ部 1 02のメモリ 1 1 1— ( I , J) に出力する。
このとき、 例えば第 7図および第 8図に示すように、 プロックを 1 6 分割したときの各分割ブロックにブロック内の水平アドレス qおよび垂 直アドレス rを割り振るとともに、 サーチウィ ン ドウにおける水平アド レス hおよび垂直ァドレス Vを割り振ると、 メモリ 1 1 1一 （ I , J ) は、 水平ア ドレス hおよび垂直ァドレス Vの分割ブロックにおける第 J 行第 I列の画素データを、 値 （ 1 4 X V + h) のアドレスに記憶する。 次に、 動きベク トルの探索を実行する場合には、 動きベク トル検出部 1 0 7から探索べク トルがサーチウィ ンドウメモリ部 1 0 2および交換 器 1 0 3に供給されるとともに、 プロック累積器 1 08から探索分割ブ ロックの水平アドレス qおよび垂直ァドレス rがサーチウイ ン ドウメモ リ部 1 02、 交換器 1 03およびリファレンスメモリ部 1 06に順次供 糸口 c3れる。
サーチウイ ン ドウメモリ部 1 02においては、 探索べク トルの水平成 分が加算器 1 3 1に供給され、 探索べク トルの垂直成分が加算器 1 3 5 に供給される。 また、 探索分割プロックの水平ア ドレス qを 4倍にした 値が加算器 1 4 2に供給され、 割プロヅクの垂直ァドレス rを 4倍に した値が加算器 1 5 0に供給される。
そして、 加算器 1 3 1， 1.33 , 1 3 5 , 1 37 , 1 40 , 1 42 , 1 5 0、 減算器 1 3 2 , 1 3 6 , 除算器 1 34， 1 3 8および乗算器 1 39により、 供給された探索べク トルおよび分割プロックの水平ァドレ ス qおよび垂直アドレス rに対応したメモリ 1 1 1— ( I， J ) に対す る読出しアドレスが算出される。 メモリ 1 1 1— ( I， J ) は、 供給さ れた読出しァドレスに記憶された画素データを交換器 1 03のセレクタ 部 1 5 1— ( 0， J ) 〜 1 5 1— ( 3， J ) に出力する。
なお、 メモリ 1 1 1一 （ 1， J) に対する読出しア ドレス A ( I , J ) は、 Xを探索ベク トルの水平成分とし、 yを探索ベク トルの垂直成分 とし、 SWH 0をサ一チウイ ン ドウの左上角からのリ ファレンスプロヅ クの左上角の水平方向の位置とし、 SWV 0をサーチウィ ンドウの左上 角からのリ ファレンスブロックの左上角の垂直方向の位置としたとき、 加算器 1 3 1 , 1 33， 1 3 5， 1 37 , 1 40， 1 42 , 1 5 0、 減 算器 1 3 2 , 1 3 6、 除算器 1 34 , 1 3 8および乗算器 1 3 9により 、 次式に従って計算される。
A ( I , J) = ( i n t ( ( SWV 0 + y- J + r x4 + 3) /4) ) x 1 4 + i n t ( (SWH 0 +x- I +q x4 + 3 ) /4)
ここで、 i n t () は、 引数の小数点以下を切り捨てる関数または演 算子である。
そして、 交換器 1 0 3においては、 水平交換部 1 1 4の各セレクタ部 1 5 1 - ( I， J ) が、 動きベク トル検出部 1 0 7より供給された探索 べク トルの水平成分に応じて、 メモリ 1 1 1— ( 0 , J) 〜： L 1 1— ( 3 , J) からの値のいずれかを選択し、 選択した値'を垂直交換部 1 1 5 のセレクタ部 1 5 2— ( 1， 0 ) 〜： 1 5 2 ( 1， 3 ) に出力する。
このとき、 各セレクタ部 1 5 1— ( 1， J ) においては、 加算部 1 2 3および ROM 1 24により、 セレクタ部 1 5 1— （ 1， J ) の列番号 Iおよび探索べク トルの水平成分に基づいて選択信号が計算され、 セレ クタ 1 2 5に供給される。 そして、 その選択信号の値 S Sに応じて、 メ モリ 1 1 1一 （ S S , J ) からの値が出力される。 なお、 選択信号の値 S Sは、 セレクタ部 1 5 1— （ 1， J ) の列番号 Iおよび探索べク トル の水平成分 Xに基づいて、 加算部 1 2 3および ROM 1 24により次式 に従って計算される。
S S =mo d ( I +x， 4)
ここで、 mo d (a, b ) は aを bで除算したときの剰余である。 その後、 垂直交換部 1 1 5の各セレクタ部 1 5 2— ( I , J ) は、 動 きべク トル検出部 1 0 7より供給された探索べク トルの垂直成分に応じ て、 セレクタ部 1 5 1— （ 1， 0) 〜： L 5 1— ( I , 3) からの値のい ずれかを選択し、 選択した値を評価部 1 04の画素比較部 1 1 3— （ I 3i J ) に出力する。 このとき、 各セレクタ部 1 5 2— ( I , J ) においては、 加算部 1 2 6および ROM 1 27によ り、 セレクタ部 1 5 2— （ 1， J ) の行番号 Jおよび探索べク トルの垂直成分に基づいて選択信号が計算され、 セレ クタ 1 2 8に供給される。 そして、 その選択信号の値 S Sに応じて、 セ レク夕部 1 5 1— （ I , S S) からの値が出力される。 なお、 選択信号 の値 S Sは、 セレクタ部 1 5 2— ( I , J ) の行番号 Jおよび探索べク トルの垂直成分 yに基づいて、 加算部 1 2 6および ROM 1 27によ り 次式に従って計算される。 '
S S = mo d (J + y, 4)
一方、 符号化フレ一ムメモリ 1 0 5は、 符号化されるフレームを分割 したプロ ックのうちのいずれか 1ブロ ヅクの画素データを、 分割プロヅ クにおける同一の行 Iかつ同一の列 Jの画素デ一夕ごとにメモリ 1 1 6 - ( I， J ) に記憶させる。
そして、 リ ファレンスメモリ部 1 0 6のメモリ 1 1 6— （ 0， 0 ) 〜 1 1 6 - ( 3 , 3 ) は、 供給された水平ア ドレス qおよび垂直ァ ドレス rに対応する分割プロックの画素データを、 1クロックごとに評価部 1 04の画素比較部 1 1 3— （ 0 , 0) - 1 1 3 - ( 3， 3 ) にそれそれ 供給する。
このとき、 リファレンスメモリ部 1 0 6においては、 乗算器 145お よび加算器 1 46によ り、 供給された水平ァドレス qおよび垂直ア ドレ ス rから読出しア ドレス （= r x 4 + q) が計算され、 セレクタ 147 を介してメモリ 1 1 6— ( 0， 0) 〜 1 1 6— （ 3， 3 ) に供給される 交換器 1 0 3およびリ ファレンスメモリ部 1 0 6からそれそれ画素デ 一夕が供給されると、 評価部 1 04の画素比較部 1 1 3— （ I , J ) は 、 ¾換器 1 03のセレクタ部 1 5 2— ( 1， J ) からの画素データと、 リ ファレンスメモリ部 1 0 6のメモリ 1 1 6— （ I , J ) からの画素デ —夕との差を計算し、 その差をブロック累積部 1 0 8に供給する。 プロ ヅク累積部 1 0 8は、 画素データの差が供給されると、 次の分割プロヅ クを指定するための水平ア ドレス qおよび垂直ァドレス rを出力すると ともに、 1ブロック分の画素データの差が蓄積されると、 その画素デー 夕の差を動きべク トル検出部 1 0 7に出力する。 動きべク トル検出部 1 0 7は、 そのときの探索ベク トルに関連づけて、 評価部 1 0 4より供給 された画素データの差の絶対値の総和を評価値として記憶する。
そして、 動きべク トル検出部 1 0 7は、 所定の順番に基づいて、 ある いは既に計算された探索ぺク トルと評価値との関係に基づいて、 新たな 探索べク トルをサーチウイ ン ドウメモリ部 1 0 2および交換器 1 0 3に 供給する。
このようにして、 動きべク トル検出部 1 0 7は、 所定の順番が終了す るまで、 あるいは評価値が所定の値以下になるまで探索べク トルを更新 していき、 評価値の最も小さいときの探索べク トルを動きべク トルに決 定する。
以上のように、 この従来の動きベク トル検出装置では、 リ ファレンス メモリ部 1 0 6に、 リファレンスブロックを分割した分割プロックを構 成する画素デ一夕を記憶させ、 サーチウィ ンドウメモリ部 1 0 2に、 符 号化されたフレームのうちのサーチウイ ン ドウを分割ブロックと同一の 大きさの領域に分割したときの、 分割後の領域における同一の行かつ同 一の列の画素データごとに、 符号化されたフレームのうちのサーチウイ ン ドゥの画素デ一夕を記憶させ、 サーチウイ ン ドウメモリ部 1 0 2のメ モリ 1 1 1 一 （ I ， J ) に記憶された分割後の領域における同一の行か つ同一の列の画素デ一夕のうちのいずれか 1つをそれそれ選択して、 分 割プロックの位置から探索べク トルだけ離れた位置の探索分割プロック を選択し、 リ ファレンスメモリ部 1 0 6に'記憶された画素デ一夕と、 選 択された画素データとを画素ごとに比較し、 その比較の結果に基づいて 動きべク トルを検出するようにする。
従来の動きべク トル検出装置は以上のように構成されているので、 評 価部 1 0 4の画素比較部 1 1 3— （ I , J ) の数を低減して回路規模を 小さく し、 装置のコス トを低減することができるものの、 ブロック全域 を構成するすべての分割プロックについて画素データの比較を実行する 必要があり、 この点に関して動きベク トルを検出するために要する時間 を低減することが困難であるなどの課題があった。
また、 従来の動きべク トル検出装置は以上のように構成されているの で、 双方向予測を実行する場合、 前方向の動きベク トルを検出するため の装置と後方向の動きベク トルを検出するための装置の 2つの装置が必 要になり、 装置の規模が大きくなるなどの課題があった。
この発明は上記のような課題を解決するためになされたもので、 プロ ックを構成する複数の画素パターンを構成する画素のデ一夕を記憶する 第 1の記憶手段'と、 符号化されたフレームのうちの所定の範囲において 所定の画素数おきの所定の数の画素でそれそれ構成される複数の画素パ ターンにおける同一位置の画素のデータごとに、 符号化されたフレーム のうちの所定の範囲の画素のデータを記憶する第 2の記憶手段と、 所定 の探索べク トルを供給され、 その所定の範囲においてその探索べク トル で指定されたプロックにおける 1つの画素パターンを選択する選択手段 と、 選択手段により選択された画素パターンと、 その画素パターンと同 一の、 第 1の記憶手段に記憶された画素パターンとを画素ごとに比較す る比較手段と、 比較手段による比較の結果に基づいて動きべク トルを検 出する検出手段とを備えるようにして、 各画素パターンについての比較 結果をプロック全域についての比較結果に近似させ、 比較結果に必要と される精度に応じて、 必ずしもプロック全域を構成する画素パターンの すべてについて比較を実行する必要がなくなり、 短時間で各プロックに ついての比較結果が得られ、 動きベク トルを短時間で検出することがで きる動きべク トル検出装置を得ることを目的とする。
また、 この発明は上記のような課題を解決するためになされたもので 、 プロヅクを構成する複数の画素パターンまたは複数の分割プロヅクを 構成する画素のデ一夕を記憶する第 1の記憶手段と、 符号化されたフレ
—ムのうちの所定の範囲を構成する複数の画素パターンまたは複数の分 割プロックにおける同一位置の画素のデ一夕ごとに、 符号化されたフレ ームのうちの所定の範囲の画素のデータを記憶する第 2の記憶手段と、 動きべク トルの候補である複数の探索べク トルを供給され、 その所定の 範囲において各探索べク トルで指定されたプロックにおける同一の画素 パターンまたは各分割プロックを順次選択する選択手段と、 選択手段に より選択された画素パターンまたは分割プロックと、 その画素パターン または分割プロックと同一の、 第 1.の記憶手段に記憶された画素パター ンまたは分割プロックとを画素ごとに比較する比較手段と、 1つの探索 べク トルについて比較手段による全画素パターンまたは全分割プロック についての比較が完了する以前に、 その時点までの画素パターンまたは 分割プロヅクについての比較結果に応じて、 その探索べク トルについて の選択手段および比較手段による処理を中止させ、 その探索ぺク トルを 動きべク トルの候補から削除する探索べク トル絞込手段と、 比較手段に よる比較の結果に基づいて動きべク トルの候補から動きべク トルを検出 する検出手段とを備えるようにして、 動きベク トルとならない可能性の 高い探索べク トルを打ち切り、 動きべク トルを検出するまでの計算量を 低減し、 動きベク トルを短時間で検出することができる動きべク トル検 出装置を得ることを目的とする。 さらに、 この発明は上記のような課題を解決するためになされたもの で、 プロックを構成する画素デ一夕のうちの所定の数の画素データを記 憶する第 1の記憶手段と、 符号化されたフ レームのうち、 前方向の動き ぺク トル検出用の第 1の範囲内、 および後方向の動きべク トル検出用の 第 2の範囲内の画素データを記憶する第 2の記憶手段と、 前方向の探索 べク トルおよび後方向の探索べク トルを供給され、 第 2の記憶手段に記 憶された画素デ一夕のうちの、 プロックの位置から探索べク トルだけ離 れた位置の、 ブロックと同一の大きさの範囲の画素デ一夕のうちの所定 の数の画素デ一夕を選択する選択手段と、 第 1の記憶手段に記憶された 所定の数の画素データと、 選択手段により選択された所定の数の画素デ —夕とを比較する比較手段と、 比較手段による比較の結果に基づいて前 方向の動きべク トルおよび後方向の動きぺク トルを検出する検出手段と を備えるようにして、 第 2の記憶手段に必要な記憶容量が増加するもの の、 他の構成要素を増加させることなく、 前方向および後方向の動きべ ク トルを検出することができる動きべク トル検出装置を得ることを目的 とする。 発明の開示
この発明に係る動きべク トル検出装置は、 プロックを構成する複数の 画素パターンを構成する画素のデ一夕を記憶する第 1の記憶手段と、 符 号化されたフレームのうちの所定の範囲において所定の画素数おきの所 定の数の画素でそれそれ構成される複数の画素パターンにおける同一位 置の画素のデ一夕ごとに、 符号化されたフレームのうちの所定の範囲の 画素のデータを記憶する第 2の記憶手段と、 所定の探索べク トルを供給 され、 その所定の範囲においてその探索べク トルで指定されたブロック における 1つの画素パターンを選択する選択手段と、 選択手段により選 択された画素パターンと、 その画素パターンと同一の、 第 1の記憶手段 に記憶された画素パターンとを画素ごとに比較する比較手段と、 比較手 段による比較の結果に基づいて動きべク トルを検出する検出手段とを備 えるものである。 このことによって、 各画素パターンについての比較結 果がブロック全域についての比較結果に近似し、 比較結果に必要とされ る精度に応じて、 必ずしもプロック全域を構成する画素パターンのすべ てについて比較を実行する必要がなくなり、 短時間で各ブロックについ ての比較結果が得られ、 動きべク トルを短時間で検出することができる という効果が得られる。
この発明に係る動きべク トル検出装置は、 プロックを構成する複数の 画素パターンまたは複数の分割プロックを構成する画素のデ一夕を記憶 する第 1の記憶手段と、 符号化されたフレームのうちの所定の範囲を構 成する複数の画素パターンまたは複数の分割プロックにおける同一位置 の画素のデ一夕ごとに、 符号化されたフレームのうちの所定の範囲の画 素のデ一夕を記憶する第 2の記憶手段と、 動きベク トルの候補である複 数の探索べク トルを供給され、 その所定の範囲において各探索べク トル で指定されたプロ ックにおける同一の画素パターンまたは各分割プロッ クを順次選択する選択手段と、 選択手段によ り選択された画素パターン または分割ブロックと、 その画素パターンまたは分割ブロックと同一の 、 第 1の記憶手段に記憶された画素パターンまたは分割プロックとを画 素ごとに比較する比較手段と、 1つの探索べク トルについて比較手段に よる全画素パターンまたは全分割プロックについての比較が完了する以 前に、 その時点までの画素パターンまたは分割プロックについての比較 結果に応じて、 その探索べク トルについての選択手段および比較手段に よる処理を中止させ、 その探索べク トルを動きべク トルの候補から削除 する探索べク トル絞込手段と、 比較手段による比較の結果に基づいて動 きべク トルの候補から動きべク トルを検出する検出手段とを備えるもの である。 このことによって、 動きベク トルとならない可能性の高い探索 べク トルを打ち切り、 動きべク トルを検出するまでの計算量を低減し、 動きベク トルを短時間で検出することができるという効果が得られる。
この発明に係る動きべク トル検出装置によれば、 探索べク トル絞込手 段は、 複数の探索べク トルについての同一の画素パターンまたは同一の 分割ブロックごとに、 その同一の画素パターンまたは同一の分割プロッ クの比較が完了した後ごとに、 所定の条件を満足する場合に複数の探索 べク トルのうちの少なく とも 1つを動きべク トルの候補から削除する。 このことによって、 評価値の累積を打ち切るための処理が簡単になると いう効果が得られる。
この発明に係る動きベク トル検出装置によれば、 比較手段は、 比較結 果として評価値を算出し、 探索ベク トル絞込手段は、 各探索ベク トルに ついて複数の画素パターンでの評価値の累積値を計算し、 複数の探索べ ク トルについての評価値の累積値を昇順または降順に配列して記憶して いき、 その配列における評価値の順序に基づいて 1または複数の探索べ ク トルを動きべク トルの候補から削除する。 このことによって、 評価値 の累積を打ち切る探索べク トルを選択する際に、 改めてすベての探索べ ク トルについての評価値の累積値を参照する必要がなく、 評価値の累積 を打ち切る探索べク トルの選択を迅速に実行することができるという効 果が得られる。
この発明に係る動きベク トル検出装置によれば、 比較手段は、 比較結 果として評価値を算出し、 探索ベク トル絞込手段は、 複数の探索べク ト ルについての評価値の累積値において最小値または最大値の評価値に対 応する探索べク トルを選択し、 選択した探索べク トルについて評価値の 累積を実行し、 検出手段は、 最小値または最大値の評価値の累積回数が 所定の回数である場合、 その探索ベク トルを動きベク トルとする。 この ことによって、 動きべク トルとなる可能性の高い探索べク トルについて の評価値の累積がより進行していくため、 より短時間で動きベク トルを 検出することができるという効果が得られる。
この発明に係る動きべク トル検出装置によれば、 探索べク トル絞込手 段は、 複数の探索べク トルについての評価値の累積値を昇順または降順 に配列して記憶していき、 その配列の先頭に対応する探索べク トルを選 択し、 選択した探索ベク トルについて評価値の累積を実行し、 複数の探 索べク トルについての評価値の累積値を昇順または降順に再配列し、 配 列の先頭の評価値の累積回数が所定の回数である場合、 その探索べク ト ルを動きベク トルとする。 このことによって、 次に評価値の累積を実行 する探索べク トルを選択する際に、 単に配列の先頭の探索べク トルを選 択すればよく、 各探索ぺク トルについての評価値の累積値を参照する必 要がなく、 評価値の累積を打ち切る探索べク トルの選択を迅速に実行す ることができるという効果が得られる。
この発明に係る動きぺク トル検出装置は、 プロックを構成する画素デ
—夕のうちの所定の数の画素デ一夕を記憶する第 1の記憶手段と、 符号 化されたフレームのうち、 前方向の動きべク トル検出用の第 1の範囲内 、 および後方向の動きべク トル検出用の第 2の範囲内の画素デ一夕を記 憶する第 2の記憶手段と、 前方向の探索べク トルおよび後方向の探索べ ク'トルを供給され、 第 2の記憶手段に記憶された画素データのうちの、 ブロックの位置から探索べク トルだけ離れた位置の、 ブロックと同一の 大きさの範囲の画素デ一夕のうちの所定の数の画素デ一夕を選択する選 択手段と、 第 1の記憶手段に記憶された所定の数の画素データと、 選択 手段により選択された所定の数の画素データとを比較する比較手段と、 比較手段による比較の結果に基づいて前方向の動きべク トルおよび後方 向の動きべク トルを検出する検出手段とを備えるものである。 このこと によって、 第 2の記憶手段に必要な記憶容量が増加するものの、 他の構 成要素を増加させることなく、 前方向および後方向の動くベク トルを検 出することができるという効果が得られる。 図面の簡単な説明
第 1図は、 従来の動きべク トル検出装置の構成を示すプロック図であ る。
第 2図は、 第 1図のサーチウィン ドウメモリ部におけるメモリの入出 力を制御する回路の一例を示すプロック図である。
第 3図は、 第 1図の交換器の構成例を示すプロック図である。
第 4図は、 第 3図の水平交換部におけるセレクタ部の構成例を示すブ ロック図である。
第 5図は、 第 3図の垂直交換部におけるセレクタ部の構成例を示すブ ロック図である。
第 6図は、 第 1図のリ ファレンスメモリ部におけるメモリの入出力を 制御する回路の一例を示すブロック図.である。
第 7図は、 サーチウイ ンドウおよび探索分割ブロックの一例を示す図 である。 '
第 8図は、 実施の形態 2における探索分割プロックおよび探索分割ブ 口ックの水平ァドレスおよび垂直ァドレスを示す図である。
第 9図は、 この発明の実施の形態 1による動きべク トル検出装置の構 成を示すブロック図である。
第 1 0図は、 第 9図のサーチウィ ン ドウメモリ部におけるメモリの入 出力を制御する回路の一例を示すプロック図である。
第 1 1図は、 第 9図の交換器の構成例を示すブロック図である。 第 1 2図は、 第 1 1図の水平交換部におけるセレクタ部の構成例を示 すブロック図である。
第 1 3図は、 第 1 1図の垂直交換部におけるセレクタ部の構成例を示 すブロック図である。
第 1 4図は、 サーチウィ ン ドウメモリ部における各画素デ一夕のァ ド レスとその各画素デ一夕が記憶されるメモリ との対応関係の一例、 およ びサーチウィ ン ドウにおける画素パターンの一例を示す図である。
第 1 5図は、 リ ファレンスメモリ部における各画素デ一夕のアドレス とその各画素デ一夕が記憶されるメモリ との対応関係の一例、 およびサ 一チウイ ン ドウにおける画素パターンの一例を示す図である。
第 1 6図は、 画素パターンの選択順序の一例を示す図である。
第 1 7図は、 分割プロックにより使用される画素、 および画素パター ンによ り使用される画素の一例を示す図である。
第 1 8図は、 この発明の実施の形態 2 による動きべク トル検出装置の 構成を示すブロック図である。
第 1 9図は、 この実施の形態 2 における動きべク トル検出部および画 素パターン累積部の構成例を示すプロック図である。
第 2 0図は、 記憶手段に記憶された各探索べク トルについての評価値 の累積回数と累積値などの一例を示す図である。
第 2 1図は、 実施の形態 3における評価値の累積の打ち切りの一例を 説明する図である。
第 2 2図は、 実施の形態 4における動きべク トル検出部および画素パ ターン累積器の記憶手段の構成を示すプロック図である。
第 2 3図は、 第 2 2図における各記憶部の構成例を示すプロック図で め ^ ) o
第 2 4図は、 実施の形態 5 における評価値の累積の順序の一例を示す 図である。
第 2 5図は、 実施の形態 6による動きべク トル検出装置における動き べク トル検出部の構成例を示すプロック図である。
第 2 6図は、 前方向のサーチウィ ン ドウおよび前方向の探索プロック の一例を示す図である。
第 2 7図は、 後方向のサーチウイ ン ドウおよび後方向の探索プロック の一例を示す図である。 発明を実施するための豳良の形態
以下、 この発明をより詳細に説明するために、 この発明を実施するた めの最良の形態について、 添付の図面に従って説明する。
実施の形態 1 .
第 9図は、 この発明の実施の形態 1 による動きべク トル検出装置の構 成を示すブロック図である。 第 1 0図は、 第 9図のサーチウィ ン ドウメ モリ部におけるメモリの入出力を制御する回路の一例を示すプロック図 である。 第 1 1図は、 第 9図の交換器の構成例を示すプロック図であり 、 第 1 2図は、 第 1 1図の水平交換部におけるセレクタ部の構成例を示 すブロック図であり、 第 1 3図は、 第 1 1図の垂直交換部におけるセレ クタ部の構成例を示すブロック図である。
なお、 この実施の形態 1による動きベク トル検出装置は、 リファレン スブロックが 1 6行 1 6列であり、 リファレンスプロヅクが 1 6の画素 パターンで構成される場合のものである。
第 9図において、 1は、 H . 2 6 1方式、 M P E G方式などの画像処 理方式においてフレーム間予測符号化により既に符号化されたフレーム の画素データであって、 現時点で符号化されるフレームにおける予測の ための画素デ一夕を記憶する既符号フレームメモリである。 なお、 現時 点で符号化されるフ レームの予測においては、 符号化されるフ レームを 分割した各プロックに対する動きべク トルが検出される。 すなわち、 現 時点において符号化されるフレームにおけるそのブロ ヅクの位置と、 既 に符号化されたフ レームにおけるそのブロックに対応する範囲の位置と の水平方向および垂直方向の距離が動きべク トルとして検出される。
2は、 サーチウィ ン ドウ内の、 所定の画素数おきの所定の数の画素で それぞれ構成される複数の画素パターンにおける同一位置の画素のデ一 夕ごとに、 符号化されたフ レームのうちのサーチウィン ドゥを構成する 画素のデ一夕を記憶するサーチウィ ン ドウメモリ部 （第 2の記憶手段、 選択手段） である。
この実施の形態 1におけるサーチウィ ン ドウメモリ部 2において、 1 1 - ( I , J ) は、 サーチウィンドウをリ フ ァ レンスブロックと同一サ ィズに分割した各分割プロックを構成する複数の画素パターンにおける 同一位置の画素デ一夕を記憶するメモリである。 例えば、 サーチウィ ン ドウのサイズが 64画素 X 3 2画素であり、 リ フ ァレンスブロックのサ ィズが 1 6画素 X 1 6画素であり、 縦横 3画素おきの画素で各画素パ夕 ーンが構成される場合には、 サーチウィ ン ドウがまず、 縦 2つ横 4つの 合計 8つのプロックに分割され、 その各プロヅク （縦 1 6画素、 横 1 6 画素） における縦横 4画素の 1 6の領域 （ I , J) ( 1 = 0， · · ·， 3、 J = 0， · · ·， 3) の画素データが、 1 6のメモリ 1 1一 （ 1， J ) にそれそれ記憶される。
すなわち、 この場合、 各ブロックにおいて、 p ( p = 0， · · ·， 3 ) .および q ( q = 0 , · · ·， 3 ) として、 各画素パターンは、 画素 （, 0 + p , 0 + q ) 、 画素 （ 4 + p， 0 + q ) 、 画素 （ 8 + p， 0 + q ) 、 画素 （ 1 2 + p， 0 + q ) 、 画素 （ 0 + p , 4 + q ) 、 画素 （ 4 + p, ， 4 + q ) 、 画素 （ 8 +p, 4 + q ) 、 画素 （ 1 2 +p， 4 + q ) 、 画 素 （ 0 +p， 8 + q) 、 画素 （4 +p, 8 + q ) 、 画素 （ 8 + p , 8 + q) 、 画素 （ 1 2 +p， 8 + q) 、 画素 （ 0 +p， 1 2 +q) 、 画素 （ 4 +p, 1 2 +q) 、 画素 （ 8 +p, 1 2 + q ) および画素 （ 1 2 + p , 1 2 + q ) の 1 6の画素で構成される。 これにより、 1 6のメモリ 1 1一 （ 1， J ) から、 同時に、 1 6の画素で構成される画素パターンを 構成する画素デ一夕を読み出すことが可能になる。
第 1 0図において、 4 1は、 メモリ 1 1— ( I， J ) への画素デ一夕 書込み時に書込みァドレスを供給され、 メモリ 1 1— ( I , J) からの 画素データ読出し時に読出しアドレスを供給され、 書込み Z検出切替信 号の値に応じて、 それらのアドレスのいずれかをメモリ 1 1 _ ( 1， J ) に供給するセレク夕である。 42は、 メモリ 1 1— ( 0 , 0) 〜： 1 1 一 （ 3 , 3) から、 1つの画素パターンを構成する画素データを同時に 出力させる際のメモリ 1 1一 （ I , J) の読出しアドレス A ( I , J) を式 （ 1 ) に従って演算する読出しアドレス演算部である。
A ( 1， J ) = ( i n t ( (y l + 1 2 - 4 x j ) /1 6) x 4 + m o d (y l , 4) ) x l 6 + i n t ( (x l + 1 2 - 4 x i) / 1 6 ) x4 +mo d (x l , 4) · · · ( 1 )
ここで、 x l = 2 4 +x + p、 y l = 8 + y + qとし、 （x, y ) を 探索ベク トルとする。 なお、 この式はサーチウィ ンドウの原点に対して 動きが 0である位置が （ 24， 8) である場合のものである。
第 9図に戻り、 3は、 サーチゥイ ンドウメモリ部 2のメモリ 1 1— ( 0 , 0 ) 〜： L 1— ( 3， 3 ) に記憶された画素データのうちの、 リファ レンスプロックの位置から探索べク トルだけ離れた位置の探索プロック におけるいずれかの画素パターンを構成する画素デ一夕を供給され、 そ の画素パターンを構成する 1 6個の画素データを所定の順序に配列して 評価部 4の画素比較部 1 3— ( I , J ) にそれそれ出力する交換器 （選 択手段） である。
第 1 1図に示す交換器 3において、 14は、 行 Jごとにメモリ 1 1一 ( 0 , J ) 〜 1 1一 （ 3 , J ) から画素デ一夕を供給され、 内蔵のセレ クタ部 5 1— ( 0 , J ) 〜5 1— （ 3， J ) によりすベての画素デ一夕 からそれそれ 1つの画素デ一夕を探索べク トルの水平成分の値に応じて 選択し、 出力する水平交換部である。 1 5は、 水平交換部 14のセレク 夕部 5 1— （ 1， 0) 〜 5 1— （ 1 , 3) から、 画素デ一夕を内蔵のセ レク夕部 5 2— （ 1， 0 ) 〜 5 2— ( I , 3 ) に供給され、 セレクタ部 5 2— （ I , 0) 〜5 2— ( 1， 3 ) によりすベての画素デ一夕からそ れそれ 1つの画素データを探索べク トルの垂直成分の値に応じて選択し 、 出力する垂直交換部である。
第 1 2図に示すセレクタ部 5 1— ( 1， J ) において、 2 1は、 セレ クタ部 5 1— ( I， J) の番号 I、 探索ぺク トルの水平成分 Xおよび画 素パターンの水平方向のオフセヅ ト pに基づいて式 （ 2 ) に従って演算 した値 S hを有する選択信号を生成する選択信号生成部である。
S h = mo d ( i n t ( 24 +x + p + 4 x I ) / 4 , 4) · - · ( 2 )
2 2は、 選択信号生成部 2 1からの選択信号の値 S hに応じてメモリ 1 1一 ( S h , J) からの値を選択し、 出力するセレクタである。
第 1 3図に示すセレクタ部 5 2— ( I , J ) において、 2 6は、 セレ クタ部 5 2— （ 1， J ) の番号 J、 探索べク トルの垂直成分 yおよび画 素パターンの垂直方向のオフセヅ ト qに基づいて式 （ 3 ) に従って演算 した値 S Vを有する選択信号を生成する選択信号生成部である。
S v=mo d ( i n t ( 8 + y + q + 4 xJ) /4 , 4 ) · · · ( 3 )
2 7は、 選択信号生成部 2 6からの選択信号の値 S vに応じてセレク 夕部 5 1— ( I , S v ) からの値を選択し、 出力する.セレクタである。 第 9図に戻り、 5は、 現時点で符号化されるフレームの画素デ一夕を 記憶する符号化フレームメモリである。
6は、 現時点で符号化されるフレームを分割した 1 6行 1 6列のプロ ヅクのうちのいずれかのブロック （リファレンスブロック） を構成する 複数の画素パターンにおける同一位置の画素のデータをそれそれ記憶す るメモリ 1 6— （ I , J ) を有する リファレンスメモリ部 （第 1の記憶 手段） である。 すなわち、 メモリ 1 6— ( I , J ) は、 画素パターンを 構成する画素の数と同一の数だけ設けられ、 リファレンスプロックが M 個の画素パターンで構成される場合、 各メモリ 1 6— ( I , J.) には、 各画素パターンにおける同一位置の M個の画素データが記憶される。
4は、 リ ファレンスメモリ部 6の各メモリ 1 6— （ 1， J ) ( 1 = 0 ， · · ·， 3 , J = 0， · · ·， 3 ) の画素データと、 交換器 3のセレ クタ部 5 2— ( 1， J ) からの画素デ一夕とをそれそれ比較する画素比 較部 1 3— （ I , J ) を有する評価部 （比較手段） である。
8は、 画素パターンのオフセヅ ト ί直の水平成分 pおよび垂直成分 qを 所定の順番に従って順次選択していき、 それらの値 p , qを、 サ一チウ イ ン ドウメモリ部 2、 交換器 3およびリ ファレンスメモリ部 6に供給す るとともに、 評価部 4の各画素比較部 1 3— （ I， J ) の比較結果を画 素パ夕一ンごとに一時的に蓄積し、 プロヅクを構成するすべての画素パ 夕一ンに対する上記比較結果をまとめて動きべク トル検出部 7に出力す る画素パ夕一ン累積器 （検出手段） である。
7は、 画素パターン累積器 8からの 1 プロック分の比較結果に基づい て、 サーチウィ ン ドウメモリ部 2および交換器 3 における次の探索べク トルを設定し、 最適な探索べク トルを動きべク トルとして検出する動き べク トル検出部 （検出手段） である。 例えば、 各画素比較部 1 3— （ I , J ) により 2つの画素デ一夕の差を算出させ、 リ ファレンスプロック におけるそれらの差の絶対値の総和が最小であるときの探索ぺク トルが 動きベクトルとされる。
次に動作について説明する。
第 1 4図は、 サーチウィ ン ドウメモリ部における各画素データのァド レスとその各画素デ一夕が記憶されるメモリ との対応関係の一例、 およ びサ一チウイ ン ドウにおける画素パターンの一例を示す図である。 第 1 5図は、 リファレンスメモリ部における各画素デ一夕のア ドレスとその 各画素データが記憶されるメモリ との対応関係の一例、 およびサ一チウ ィ ン ドウにおける画素パターンの一例を示す図である。 第 1 6図は、 画 素パターンの選択順序の一例を示す図である。
サーチウィ ン ドウメモリ部 2は、 複数の画素パターンにおける同一位 置の画素のデ一夕ごとに、 既符号フレームメモリ 1 における符号化され たフレームのうちのサーチウィ ン ドウを構成する画素のデータを記憶す る。 すなわち、 1つの画素パターンを構成する各画素は互いに異なるメ モリ 1 1— ( I， J ) に記憶される。
例えば第 1 4図に示すように、 サーチウィ ン ドウメモリ部 2における メモリ 1 1— ( 1， J ) は、 サーチウィ ン ドウをリ ファレンスブロック と同一サイズに分割した各分割プロックを構成する複数の画素パターン における同一位置の画素データを記憶する。 この場合、 第 1 4図に示す ように、 サ一チウイ ン ドウのサイズが 6 4画素 X 3 2画素であり、 リフ ァレンスプロックのサイズが 1 6画素 X 1 6画素であり、 縦横 3画素お きの画素で各画素パターンが構成される場合には、 サーチウィ ン ドウが まず、 縦 2つ横 4つの合計 8つのプロックに分割され、 その各ブロック (縦 1 6画素、 横 1 6画素） における縦横 4画素の 1 6の領域 （ I , J ) ( 1 = 0 , - - · , 3 s J = 0 , ' · ·， 3 ) の画素デ一夕が、 1 6 のメモリ 1 1一 （ I , J) にそれそれ記憶される。
そして、 サーチウィ ン ドウメモリ部 2の読出しアドレス演算部 42は 、 画素パターン累積部 8からの画素パターンのオフセッ ト （p, q ) お ょぴ動きぺク トル検出部 7からの探索べク トル （X , y ) に基づいて、 式 （ 1 ) に従ってメモリ 1 1— ( I , J) の読出しア ドレス A ( I , J ) を演算し、 セレクタ 4 1に供給する。 画素デ一夕の読み出し時には、 セレクタ 4 1を介して、 その読み出しア ドレスがメモリ 1 1— ( I , J ) に供給され、 そのアドレスの画素デ一夕が交換器 3に供給される。 例 えば第 1 4図には、 探索べク トルが （ 1 9， 一 6 ) であり、 オフセ ヅ ト が （ 2 , 1 ) である場合の画素パターンが示されている。
交換器 3は、 サーチウィ ン ドウメモリ部 2からの、 画素パターンを構 成する画素データを所定の順序に配列させて評価部 4の画素比較部 1 3 一 （ I , J ) にそれそれ出力する。
このとき、 交換器 3では、 水平交換部 1 4が、 まず、 行 Jごとにメモ リ 1 1— ( 0， J) 〜 ： L I— ( 3， J) から画素デ一夕を供給され、 内 蔵のセレクタ部 5 1— ( 0 , J ) 〜5 1— ( 3， J ) によ りすベての画 素デ一夕からそれそれ 1つの画素デ一夕を探索べク トルの水平成分の値 に応じて選択し、 垂直交換部 1 5へ出力する。 このとき、 各セレクタ部 5 1— （ I , J ) においては、 選択信号生成部 2 1によ り式 （ 2 ) に従 つて演算された値 S hを有する選択信号がセレクタ 2 2に供給され、 セ レクタ 2 2により、 その選択信号の値 S hに応じてメモリ 1 1一 （S h , J ) からの値が選択される。
交換器 3では次に、 垂直交換部 1 5が、 水平交換部 14のセレクタ部 5 1 - ( I , 0 ) 〜5 1— （ I , 3 ) からの画素データを、 内蔵の各セ レク夕部 5 2— ( 1， J ) によ りすベての画素デ一夕からそれそれ 1つ の画素デ一夕を探索べク トルの垂直成分の値に応じて選択し、 出力する 。 このとき、 セレクタ部 5 2— （ I , J ) では、 選択信号生成部 2 6に より式 （ 3 ) に従って演算された値 S vを有する選択信号がセレクタ 2 7に供給され、 セレクタ 2 7によ り、 その選択信号の値 S Vに応じてセ レクタ部 5 1— ( 1， S v) からの値が選択される。
このようにして探索ベク トル （X , y ) およびオフセッ ト （ p , ) に応じて選択された画素パターンを構成する画素のデ一夕が評価部 4に 供給される。
一方、 リ ファレンスメモリ部 6は、 符号化フレームメモリ 5から、 現 時点で符号化されるフレームを分割した 1 6行 1 6列のプロ 'ソクのうち のいずれかのプロ ヅク （リファレンスブロック） を構成する複数の画素 パターンにおける同一位置の画素の 一夕をそれそれ読み出し、 内蔵の メモリ 1 6— （ I , J ) に記憶する。 すなわち、 1つの画素パターンを 構成する各画素は互いに異なるメモリ 1 6— ( I， J ) に記憶される。 そして、 リ ファレンスメモリ部 1 6は、 例えば第 1 5図に示すように、 画素パターン累積器 8からのオフセッ ト （p , q) (第 1 5図の場合、 p = 2、 q = 1 ) で指定された画素パターンを、 交換器 3から評価部 4 への画素データの配列と同様の配列で、 評価部 4の画素比較部 1 3— ( I , J ) にそれそれ出力する。
そして、 評価部 4は、 リファレンスメモリ部 6の各メモリ 1 6— ( I ， J ) からの画素デ一夕と、 交換器 3のセレクタ部 5 2— （ I , J ) か らの画素デ一夕とを画素比較部 1 3— （ I， J ) でそれそれ比較し、 そ の比較結果である評価値を画素パターン累積器 8に供給する。 このとき の評価値は、 例えば、 リ ファレンスメモリ部 6の各メモリ 1 6— ( I， J ) からの画素データと、 交換器 3のセレクタ部 5 2— （ I , J ) から の画素デ一夕との差の絶対値の総和とされる。 なお、 このときの評価値 を、 両者の画素デ一夕との差の 2乗の総和としてもよい。 画素パターン累積器 8は、 画素パターンのオフセッ ト値の水平成分 p および垂直成分 qを所定の順番に従って順次選択していき、 それらの値 P , qを、 サーチウィ ン ドウメモリ部 2、 交換器 3およびリファレンス メモリ部 6に供給し、 各オフセッ ト値 p , qの場合に評価部 4の各画素 比較部 1 3— （ I， J ) からの評価値を累積し、 各探索べク トルについ て、 プロックを構成するすべての画素パターンに対する評価値をまとめ て動きべク トル検出部 7に出力する。
このとき、 画素パターン累積器 8は、 画素パターンのオフセ ヅ ト （ p , q ) を、 例えば第 1 6図 （ a ) に示すように、 片寄りなく選択してい く。 これにより、 3回選択されたオフセッ トに応じた 3つの画素パター ンは第 1 6図 （b ) に示すようになる。
動きぺク トル検出部 7は、 画素パターン累積器 8からの 1ブロック分 の評価値に基づいて、 サーチウィ ンドウメモリ部 2および交換器 3にお ける次の探索ぺク トルを設定し、 最適な探索べク トルを動きべク トルと して検出する。
以上のように、 この実施の形態 1によれば、 リ フ ァ レンスメモリ部 6 に、 プロヅクを構成する複数の画素パターンを構成する画素のデ一夕を 記憶し、 サーチウィ ンドウメモリ部 2に、 符号化されたフ レームのうち の所定のサーチゥイ ンドウにおいて所定の画素数おきの所定の数の画素 でそれそれ構成される複数の画素パターンにおける同一位置の画素のデ 一夕ごとに、 そのサーチウィ ンドウにおける画素デ一夕を記憶し、 動き ぺク トル検出部 7からの探索ぺク トルに応じてサーチウィ ンドウメモリ 部 2および交換器 3により 1つの画素パターンを選択し、 評価部 4によ り、 その選択した画素パ夕一ンと、 その画素パ夕一ンと同一の、 リファ レンスメモリ部 6に記憶された画素パターンとを画素ごとに比較し、 画 素パ夕一ン累積器 8により、 複数の画素パターンについての評価部 4に よる比較結果をまとめ、 動きべク トル検出部 7により、 それらの比較の 結果に基づいて動きべク トルを検出するようにしたので、 ブロックにお ける画素のうち、 比較に使用される画素がプロック全域に分散している ため、 各画素パターンについての比較結果がプロック全域についての比 較結果に近似し、 比較結果に必要とされる精度に応じて、 必ずしもプロ ック全域を構成する画素パターンのすべてについて比較を実行する必要 がなくなり、 短時間で各ブロックについての比較結果が得られ、 動きべ ク トルを短時間で検出することができるという効果が得られる。
第 1 7図は、 分割ブロックにより使用される画素、 および画素パ夕一 ンにより使用される画素の一例を示す図である.。 すなわち、 第 1 7図に 示すように、 従来のように分割ブロックについて比較を実行する場合 （ 第 1 7図 （ a ) ) には、 ブロックにおいて局所的に画素デ一夕が参照さ れるが、 この実施の形態 1のように上述の画素パ夕一ンについて比較を 実行する場合 （第 1 7図 （ b ) ) には、 ブロックにおいて均一的に画素 データが参照される。 実施の形態 2 .
この発明の実施の形態 2による動きべク トル検出装置は、 1つの画素 パターンについて複数の探索べク トルでの評価値の累積を計算していき 、 評価値の累積値の小さい探索べク トルについての評価値の累積を打ち 切り、 その探索べク トルを動きべク トルの候補から削除するようにした ものである。
第 1 8図は、 この発明の実施の形態 2による動きベク トル検出装置の 構成を示すブロック図である。 第 1 8図において、 7 Aは、 動きべク ト ル検出部 7と同様に動作する他、 1つの探索ぺク トルについて全画素パ ターンまたは全分割プロックについての評価部 4による評価値の算出が 完了する以前に、 その時点までの画素パターンについての評価値に応じ て、 その探索ベク トルについての交換器 3および評価,部 4による処理を 中止させ、 その探索べク トルを動きべク トルの候補から削除する動きべ ク トル検出部 （検出手段、 探索べク トル絞込手段） である。
第 1 9図は、 この実施の形態 2における動きベク トル検出部 7 Aおよ び画素パ夕一ン累積器 8の構成例を示すブロック図である。 第 1 9図に おいて、 6 1は評価部 4からの評価値と、 記憶手段 6 6からの過去の評 価値の累積値とを加算する加算器であり、 6 6は各探索べク トルについ ての評価値の累積回数および累積値を記憶するレジス夕、 メモリなどの 記憶手段であり、 6 7は各探索べク トルについての評価値の累積回数お よび累積値に基づいて'評価値の計算を打ち切る探索べク トルを決定する シーケンサ、 プロセッサなどの演算手段である。
なお、 第 1 8図におけるその他の構成要素については実施の形態 1に よるものと同様であるので、 その説明を省略する。
次に動作について説明する。
動きべク トル検出部 7 Aは、 探索べク トルごとに全画素パターンに対 する評価値の累積値を連続して計算させるのではなく、 各画素パターン のオフセッ ト （p， ) について探索べク トル （x， y ) を変化させて 、 各画素パターンのオフセッ ト （p , q ) で複数の探索ベク トルについ て並行して計算させていく。
このとき、 演算手段 6 7は、 各画素パターンのオフセヅ ト （ p , q ) について探索ぺク トル （X , y ) を変化させて、 そのオフセッ ト （p , q ) をサーチウィ ン ドウメモリ部 2、 交換器 3およびリファレンスメモ リ部 6に供給し、 その探索ベク トル （x， y ) をサーチウィン ドウメモ リ部 2および交換器 3に供給し、 その探索べク トルについての評価値の 累積値を記憶手段 6 6から加算器 6 1へ供給させる。 そして、 そのオフセッ トおよび探索べク トルに対する評価値が評価部
4から加算器 6 1に供給され、 評価値の累積値が計算され、 その値で記 憶手段 6 6に記憶されている評価値の累積値が更新される。 第 2 0図は 記憶手段 6 6に記憶された各探索べク トルについての評価値の累積回数 と累積値などの一例を示す図である。
また、 演算手段 6 7は、 各探索ベク トルについての評価値の累積値に 基づいて、 評価値の累積を打ち切る探索べク トルを選択し、 選択した探 索ベク トルについては以降の評価値の計算を実行させず、 動きべク トル の候補から削除する。
なお、 その他の構成要素の動作については実施の形態 1によるものと 同様であるので、 その説明を省略する。
以上のように、 この実施の形態 2によれば、 動きベク トル検出部 8 A は各画素パターンについて複数の探索べク トルを順次選択し、 各探索べ ク トルに対して、 その画素パターンでの画素ごとの比較を実行させ、 1 つの探索べク トルについて全画素パターンの比較が完了する以前に、 そ の時点までの画素パターンについての比較結果に応じて、 その探索べク トルについての以降の画素パターンについての比較を打ち切り、 その探 索べク トルを動きべク トルの候補から削除し、 残った探索べク トルから 比較の結果に基づいて動きべク トルを検出するようにしたので、 動きべ ク トルとならない可能性の高い探索べク トルを打ち切り、 動きベク トル を検出するまでの計算量を低減し、 動きべク トルを短時間で検出するこ とができるという効果が得られる。 '
なお、 ブロックを複数の画素パターンではなく従来の技術のように複 数の分割プロックに分割して、 1つの分割プロックについて複数の探索 べク トルでの評価値の累積を計算していき、 評価値の累積値の低い探索 ぺク トルでの評価値の累積を打ち切り、 その探索べク トルを動きべク ト ルの候補から削除するようにしたも同様の効果が得られる。 実施の形態 3 .
この発明の実施の形態 3による動きべク トル検出装置は、 動きべク ト ル検出部 7 Aの演算手段 6 7が、 各累積回数において、 各探索ベク トル についての評価値の累積値に基づいて、 評価値の累積を打ち切る探索べ ク トルを選択し、 動きべク トルの候補から削除するようにしたものであ る。
なお、 実施の形態 3による動きべク トル検出装置の構成については、 実施の形態 2によるものと同様であるので、 その説明を省略する。
次に動作について説明する。
第 2 1図は、 実施の形態 3における評価値め累積の打ち切りの一例を 説明する図である。
動きべク トル検出部 7 Aの演算手段 6 7は、 まず、 所定の数の探索べ ク トルについての第 1回目の評価値の累積の後、 それらの探索べク トル のうちの、 評価値の小さいもの 1 6個以外のものを削除する。 例えば第 2 1図においては、 探索ぺク トル （x O， y O ) 〜 （x l 5 , y l 5 ) 以外の探索べク トルについての評価値の累積が打ち切られる。
次に、 動きべク トル検出部 7 Aの演算手段 6 7は、 その 1 6個の探索 べク トルについて第 2回目の評価値の累積を実行させる。
そして第 2回目から所定の第 8回目までの各回数の評価値の累積の後 に、 演算手段 6 7は、 評価値の累積を継続している探索ベク トルについ ての評価値の累積値の平均値の 1 . 5倍以上の累積値となっている探索 べク トルについての評価値の累積を打ち切る。 例えば第 2 1図において は、 第 2回目の評価値の累積の後、 探索ベク トル （X 4， 4 ) および 探索べク トル （X 7， y 7 ) についての評価値の累積が打ち切られ、 第 3回目の評価値の累積の後、 探索ベク トル （x l 1 , y 1 1 ) 、 探索べ ク トル （x l 3 , y 1 3 ) および探索べク トル （ X 1 5， y 1 5 ) につ いての評価値の累積が打ち切られ、 第 4回目の評価値の累積の後、 探索 ベク トル （x l， y 1 ) s 探索べク トル （X 1 2 , 1 2 ) および探索 ベク トル （x l 4 , 14 ) についての評価傅の累積が打ち切られ、 第 5回目の評価値の累積の後、 探索ぺク トル （x 9， y 9 ) についての評 価値の累積が打ち切られる。
その後、 第 9回目以降の評価値の累積では、 演算手段 6 7は、 評価値 の累積を継続している探索べク トルのうち、 評価値の累積値が最大であ る 1つの探索ベク トルについての評価値の累積を打ち切る。 ただし、 評 価値の累積を継続している探索べク トルの数が 2になった場合、 探索べ ク トルについての評価値の累積の打ち切りは実行しない。 そして最後ま で残った探索べク トルのうち、 評価値が最小であるものが動きべク トル とされる。
例えば第 2 1図においては、 第 9回目の評価値の累積の後、 探索べク トル （X 6， y 6 ) についての評価値の累積が打ち切られ、 第 1 0回目 の評価値の累積の後、 探索ベク トル （x 0 , y 0 ) についての評価値の 累積が打ち切られ、 第 1 1回目の評価値の累積の後、 探索べク トル （X 1 0， y 1 0 ) についての評価値の累積が打ち切られ、 第 1 2回目の評 価値の累積の後、 探索ベク トル （x 2， y 2 ) についての評価値の累積 が打ち切られ、 第 1 3回目の評価値の累積の後、 探索ベク トル （X 8 , y 8 ) についての評価値の累積が打ち切られる。 これにより、 第 2回目 以降では、 評価値の累積の処理は全体で 1 0 1 (= 1 6 + 14 + 1 1 + 8 + 7 + 7 + 7 + 7 + 6千 5 + 4 + 3 + 2 + 2 + 2 ) 回で済む。
なお、 その他の構成要素の動作については実施の形態 2によるものと 同様であるので、 その説明を省略する。 また、 各累積回数における、 評 価値の累積の打ち切りの条件については上述の方法に限定されるもので はなく、 初回および最終回での探索べク トルの数、 条件を変更する累積 回数などはもちろん変更してもよい。
以上のように、 この実施の形態 3によれば、 動きベク トル検出部 7 A の演算手段 6 7が、 各累積回数において、 各探索ベク トルについての評 価値の累積値に基づいて、 評価値の累積を打.ち切る探索べク トルを選択 し、 動きべク トルの候補から削除するようにしたので、 評価値の累積を 打ち切るための処理が簡単になるという効果が得られる。 . 実施の形態 4 .
この発明の実施の形態 4による動きべク トル検出装置は、 実施の形態 3による動きべク トル検出装置において、 複数の探索べク トルについて の評価値の累積値を昇順または降順に配列して記憶していき、 その配列 における評価値の順序に基づいて 1 または複数の探索べク トルを動きべ ク トルの候補から削除するようにしたものである。
第 2 2図は、 実施の形態 4における動きべク トル検出部 7 Aおよび画 素パターン累積器 8 Aの記憶手段 6 6の構成を示すプロック図である。 第 2 2図に示す動きぺク トル検出部 7 Aにおいて、 7 1— 1 ~ 7 1— ( n + 1 ) は記憶手段 6 6 としてのシフ ト レジス夕を構成する （ n + 1 ) 個 （例えば 1 7個） の記憶部である。 第 2 3図は、 第 2 2図における各 記憶部の構成例を示すプロック図である。 第 2 3図に示す各記憶部 Ί 1 において、 8 1はレジス夕 8 4に記憶された累積データのうちの累積値 E ( i ) と、 画素パターン累積器 8 Aからの累積データのうちの累積値 E ( n e w ) とを比較する比較器であり、 8 2は内蔵される記憶部 7 1 ― iの比較器 8 1からの比較結果、 前段の記憶部 7 1— （ i _ 1 ) の比 較器 8 1からの比較結果、 および後段の記憶部 7 1 — （ i + 1 ) の比較 器 8 1からの比較結果に基づいて、 前段の記憶部 7 1— （ i一 1 ) から の累積デ一夕、 後段の記憶部 7 1— ( i + 1 ) からの累積デ一夕、 内蔵 される記憶部 7 1— iの累積データ、 画素パターン累積器 8 Aからの新 たな累積データ、 および所定の最大値を累積値として有する累積データ のいずれかを選択させるための選択信号を生成する制御回路であり、 8 3は制御回路 8 2からの選択信号に基づいていずれかの累積データを選 択するセレクタであり、 8 4は累積デ一夕を記憶するレジス夕である。 第 2 2図において、 8 Aは評価部 4から評価値を供給され、 また記憶 手段 6 6における第 1番目の記憶部 7 1— 1からの累積デ一夕を供給さ れ、 その累積データにおける評価値の累積値に評価部 4からの評価値を 累積して新たな累積デ一夕を生成し、 各記憶部 7 1 - iに供給する画素 パターン累積器である。
なお、 実施の形態 4におけるその他の構成要素については、 実施の形 態 2 によるものと同様であるので、 その説明を省略する。
次に動作について説明する。
初期状態としてまず演算手段 6 7は、 各記憶部 7 1 - iの制御回路 8 2を制御してセレクタ 8 3に所定の最大値を有する累積データを選択さ せ、 レジス夕 8 4に選択させる。
次に n個の探索べク トルについての第 1回目の評価値の累積における 動きべク トル検出部 7 Aの動作について説明する。 画素パターン累積器 8 Aから、 評価部 4からの評価値、 現在の探索ベク トルおよび累積回数 ( = 1 ) で構成される新たな累積デ一夕が記憶部 7 1— 1〜 7 1— ( n + 1 ) の比較器 8 1およびセレクタ 8 3に供給される。
各記憶部 7 1— iの比較器 8 1は、 レジスタ 8 4に記憶されている累 積データのうちの累積値 E ( i ) と、 画素パターン累積器 8 Aからの累 積データのうちの累積値 E ( n e w ) とを比較し、 その比較結果、 すな わち、 E ( i ) > E (n ew) であるか否かを制御回路 8 2、，並びに、 前段および後段の記憶部 7 1— ( i - 1 ) , 7 1— ( i + 1 ) の制御回 路 8 2に供給する。
そして制御回路 82は、 E ( i ) > E (n ew) ではない場合、 レジ ス夕 84の累積デ一夕を選択する選択信号を生成し、 E ( i ) > E ( n e w) である場合であって、 i > lについて E ( i - 1 ) > E (n ew ) ではない場合、 画素パターン累積器 8 Aからの新たな累積データを選 択する選択信号を生成し、 i〉 lについて E ( i - 1 ) > E (n ew) である場合、 前段の記憶部 7 1 - ( i - 1 ) のレジス夕 84からの累積 データを選択する選択信号を生成する。 制御回路 8 2は選択信号を生成 するとセレクタ 8 3に供給する。 セレクタ 8 3はその選択信号に応じて レジス夕 84からの累積データ、 画素パターン累積器 8 Aからの累積デ —夕および前段の記憶部 7 1 - ( i - 1 ) ， 7 1— ( i + 1 ) からの累 積デ一夕のうちのいずれかを選択し、 レジス夕 84に供給する。 レジス 夕 84は所定のクロック信号 C LKに同期して、 記憶している累積デ一 夕を、 供給された累積データで更新する。
これにより、 第 1回目の評価値の累積により、 n個の探索べク トルに ついての評価値が記憶手段 6 6において昇順に記憶される。
次に第 2回目以降の評価値の累積における動きべク トル検出部 7 Aの 動作について説明する。
第 1番目の記憶部 7 1— 1、 すなわち累積値が最小である累積データ を有する記憶部からその累積データが演算手段 6 7および画素パターン 累積器 8 Aに供給される。
そして、 演算手段 6 7はその累積データにおける探索べク トルおよび 次の画素パターンを指定して、 評価値を演算させる。 その評価値が評価 部 4から供給されると、 画素パターン累積器 8 Aは、 記憶手段 6 6から の累積データにおける評価値に、 その評価部 4からの評価値を累積し、 累積回数を 1だけ増加させて、 新たな累積デ一夕を生成し、 記憶手段 6 6の各記憶部 Ί 1一 iに供給する。
このとき、 演算手段 6 7は、 記憶部 7 1— 1〜 7 1— （n + 1 ) の制 御回路 8 2を制御して、 第 （n+ 1 ) 番目の記憶部 7 1— (n+ 1 ) の レジス夕 8 4に、 その新たな累積デ一夕を記憶させる。 そして、 演算手 段 6 7は、 記憶部 7 1— 1〜7 1— (n + 1 ) のレジス夕 8 4に記憶さ れた累積デ一夕をシフ トさせ、 記憶部 7 1 - ( i + 1 ) ( i = l， · · • , η) のレジス夕 8 4に記憶された累積データを記憶部 7 1— iのレ ジス夕 8 4に記憶させる。
この時点では、 記憶部 7 1— 1〜 7 1— (n - 1 ) には、 累積回数が 1である累積データが記憶されており、 記憶部 7 1— nには、 累積回数 が 2である累積デ一夕が記憶されている。
次に、 第 1番目の記憶部 7 1— 1から累積データ （累積回数が 1であ る累積データのうちの累積値が最小であるもの） が演算手段 6 7および 画素パターン累積器 8 Aに供給される。
そして、 演算手段 6 7はその累積デ一夕における探索べク トルおよび 次の画素パターンを指定して、 評価値を演算させる。 その評価値が評価 部 4から供給されると、 画素パ夕一ン累積器 8 Aは、 記憶手段 6 6から の累積データにおける評価値に、 その評価部 4からの評価値を累積し、 累積回数を 1だけ増加させて、 新たな累積データを生成し、 記憶手段 6 6の各記憶部 7 1— iに供給する。
このとき、 演算手段 6 7は、 累積回数が 2である累積データを記憶す る記憶部 Ί 1— nの制御回路 8 2のみを動作させ、 新たな累積値 E (n e w) がレジス夕 8 4の累積値 E (n) 以上であるか否かを判断させ、 新たな累積値 E (n e w) がレジス夕 8 4の累積値 E (n) 以上である 場合、 記憶部 7 1— 2〜7 1— nのレジス夕 84の累積データを記憶部 7 1— 1〜7 1— ( n - 1 ) のレジス夕 84に順次記憶させていき、 新 たな累積デ一夕を記憶部 7 1— nのレジス夕 84に記憶させる。 一方、 新たな累積値 E (n ew) がレジス夕 84の累積値 E (n) よ り小さい 場合、 演算手段 6 7は、 記憶部 7 1— 2〜 7 1— (n— 1 ) のレジス夕 84の累積デ一夕をシフ トさせ、 記憶部 7 1— l〜 7 1— (n— 2 ) の レジスタ 84に順次記憶させていき、 新たな累積データを記憶部 7 1 - ( n - 1 ) のレジス夕 84に記憶させる。
この時点では、 記憶部 7 1—；！〜 7 1— (n- 2 ) には累積回数が 1 である累積デ一夕が記憶され、 記憶部 7 1 - (n— 1 ) , 7 1— nには 累積回数が 2である累積デ一夕が記憶されている。
以下、 第 2回目の評価値の累積では、 同様に、 記憶部 7 1— 1に順次 シフ トされて く る第 m番目の探索べク トルについて、 評価値が計算され 、 新たな累積データが生成され、 演算手段 6 7は、 累積回数が 2である 累積データを記憶する記憶部 7 1— （n— m+ l ) 〜7 1— nの制御回 路 82のみを動作させ、 新たな累積値 E (n ew) がレジス夕 84の累 積値 E ( j ) ( j = n - m + 15 · · · , n— 1 ) 以上であり、 かつ新 たな累積値 E (n ew) がレジス夕 84の累積値 E ( j + 1 ) より小さ い場合 （また、 新たな累積値 E (n ew) がレジス夕 84の累積値 E ( j ) ( j = n ) 以上である場合） 、 記憶部 7 1一 2〜7 1— jのレジス 夕 84の累積デ一夕をシフ トさせ、 記憶部 7 1— 1〜7 1— ( j - 1 ) のレジス夕 84に順次記憶させていき、 新たな累積データを記憶部 7 1 — jのレジス夕 84に記憶させる。 この処理を第 n (m= n) 番目の探 索ぺク トルについてまで繰り返し実行した場合、 第 2回目の評価値の累 積が完了し、 記憶部 7 1— 1〜7.1— nに、 累積回数が 2である n個の 累積データが昇順に記憶された状態になる。 ここまでで、 演算手段 6 7は、 すべて （n個） の探索ぺク トルについ ての累積回数が 1である累積データを供給されているので、 それらの累 積デ一夕における累積値に関して所定の条件を満たすか否かを判断して 、 評価値の累積を打ち切る探索べク トルを決定する。 評価値の累積を打 ち切る探索べク トルがある場合には、 評価値の累積を打ち切る探索べク トルの数を Dとすると、 演算手段 6 7は、 探索ベク トルの数 nの値を値 ( n - D ) に更新する。
その後、 第 2回目の評価値の累積と同様にして第 3回目以降の累積を 実行する。
以上のように、 この実施の形態 4によれば、 複数の探索ベク トルにつ いての評価値の累積値を昇順または降順に配列して記憶していき、 その 配列における評価値の順序に基づいて 1または複数の探索べク トルを動 きべク トルの候補から削除するようにしたので、 評価値の累積を打ち切 る探索べク トルを選択する際に、 改めてすベての探索べク トルについて の評価値の累積値を参照する必要がなく、 評価値の累積を打ち切る探索 べク トルの選択を迅速に実行することができるという効果が得られる。 実施の形態 5 .
この発明の実施の形態 5による動きべク トル検出装置は、 複数の探索 ベク トルについての評価部 4による評価値の累積値において最小値また は最大値の評価値に対応する探索べク トルを選択し、 選択した探索べク トルについて評価値の累積を実行し、 最小値または最大値の評価値の累 積回数が所定の回数である場合、 その探索べク トルを動きべク トルの候 補とするようにしたものである。
なお、 実施の形態 5による動きべク トル検出装置の構成については実 施の形態 2によるものと同様であり、 動きベク トル検出部 7 Aの動作の みが異なる。
次に動作について説明する。
第 2 4図は、 実施の形態 5における評価値の累積の順序の一例を示す 図である。
動きベク トル検出部 7 Aの演算手段 6 7は、 まず、 所定の数の探索べ ク トルについての第 1回目の評価値の累積の後、 それらの探索べク トル のうちの、 評価値の小さいもの 1 6個以外のものを削除する。
次に、 動きべク トル検出部 7 Aの演算手段 6 7は、 その 1 6個の探索 ぺク トルについて第 2回目以降の評価値の累積を実行させる。
そして第 2回目以降の評価値の累積では、 演算手段 6 7は、 1 6個の 探索ぺク トルのうち、 累積回数に拘わらず評価値の累積値が最小である 探索ぺク トルを選択し、 その探索べク トルについて次の画素パターンを オフセッ トで指定して評価値を計算させ、 その評価値を累積し、 評価値 の累積値を更新する。
演算手段 6 7は、 評価値の累積値が最小である探索べク トルの累積回 数が所定の回数 （画素パターンの数と同数） である探索べク トルが出現 するまで、 評価値の累積値が最小である探索べク トルについて次の画素 パターンの評価値を累積し、 評価値の累積値を更新し、 評価値の累積値 が最小である探索べク トルの累積回数が所定の回数 （画素パターンの数 ) である探索べク トルを動きべク トルとする。
例えば第 2 4図に示すように、 括弧内に示す第 2回目以降の評価値の 累積における累積の順序で、 評価値を計算する探索ぺク トルが選択され ていき、 第 9 3番目に、 画素パターン数と同数 （= 1 6 ) の累積回数で ある探索ベク トル （x 5， y 5 ) が、 累積値が最小である探索べク トル として出現するので、 この探索ベク トル （x 5 , y 5 ) が動きベク トル とされる。 これにより、 第 2回目以降では、 評価値の累積の処理は全体 で 9 3回で済む。 . なお、 その他の構成要素の動作については実施の形態 2 によるものと 同様であるので、 その説明を省略する。 また、 初回および第 2回目の評 価値の累積での探索べク トルの数などはもちろん変更してもよい。 また 、 ここでは、 評価値が最小となる探索べク トルを動きべク トルとしてい るが、 評価値の計算のしかたによっては評価値が最大となる探索べク ト ルが動きベク トルとされることもある。
以上のように、 この実施の形態 5 によれば、 複数の探索ベク トルにつ いての評価部 4による評価値の累積値において最小値または最大値の評 価値に対応する探索べク トルを選択し、 選択した探索べク トルについて 評価値の累積を実行し、 最小値または最大値の評価値の累積回数が所定 の回数である場合、 その探索べク トルを動きべク トルの候補とするよう にしたので、 動きべク トルとなる可能性の高い探索べク トルについての 評価値の累積がよ り進行していく ため、 よ り短時間で動きベク トルを検 出することができるという効果が得られる。 また、 常に累積値が最小で ある探索ベク トルが選択されるので、 確実に、 所定の累積回数で累積値 が最小である探索べク トルが動きべク トルとされる。 実施の形^ 6 .
この発明の実施の形態 6 による動きべク トル検出装置は、 実施の形態 5による動きべク トル検出装置において、 複数の探索べク トルについて の評価値の累積値を昇順または降順に配列して記憶していき、 その配列 の先頭に対応する探索ぺク トルを選択し、 選択した探索べク トルについ て評価値の累積を実行し、 複数の探索べク トルについての評価値の累積 値を昇順または降順に再配列し、 配列の先頭の評価値の累積回数が所定 の回数である場合、 その探索べク トルを動きべク トルとするようにした ものである。
第 2 5図は、 実施の形態 6 による動きべク トル検出装置における動き べク トル検出部 7 Aの構成例を示すプロック図である。 第 2 5図におい て、 7 1— 1〜 7 1— nは n個 （例えば 1 6個） の探索ベク トルについ ての評価値の累積値が昇順になるように n個の累積デ一夕を記憶するシ フ ト レジス夕を構成する n個の記憶部であり、 6 7は記憶部 7 1— 1の 累積デ一夕における探索べク トルについて評価値の累積を実行させ、 複 数の探索べク トルについての評価値の累積値を昇順に再配列させ、 配列 の先頭の評価値の累積回数が所定の回数である場合、 その探索べク トル を動きべク トルとする演算手段である。
なお、 実施の形態 6による動きべク トル検出装置におけるその他の構 成要素については実施の形態 5によるものと同様であるので、 その説明 を省略する。 また、 記憶部 7 1— iは、 第 2 3図に示す記憶部 7 1— i と同様である。
次に動作について説明する。
初期状態としてまず演算手段 6 7は、 各記憶部 7 1 一 iの制御回路 8 2を制御してセレクタ 8 3に所定の最大値を有する累積データを選択さ せ、 レジス夕 8 4に選択させる。
次に第 1回目の評価値の累積の場合における動きぺク トル検出部 7 A の動作について説明する。 演算手段 6 7は、 各探索べク トルについて第 1番目の画素パターンをオフセッ トで指定して第 1回目の評価値を順次 計算させる。 各評価値は評価部 4から画素パターン累積器 8 Aに供給さ れる。 そして、 画素パターン累積器 8 Aから、 評価部 4からの評価値、 現在の探索べク トルおよび累積回数 （= 1 ) で構成される新たな累積デ —夕が記憶部 7 1— ；！〜 7 1— nの比較器 8 1およびセレクタ 8 3 に供
?P口 れる。 各記憶部 7 1— iの比較器 8 1は、 レジス夕 84に記憶されている累 積デ一夕における累積値 E ( i ) と、 画素パターン累積器 8 Aからの累 積デ一夕における累積値 E (n ew) とを比較し、 その比較結果、 すな わち、 E ( i ) > E (n ew) であるか否かを制御回路 8 2、 並びに、 前段および後段の記憶部 7 1— ( i - 1 ) ， 7 1— ( i + 1 ) の制御回 路 8 2に供給する。
そして制御回路 82は、 E ( i ) > E (n ew) ではない場合、 レジ ス夕 84の累積デ一夕を選択する選択信号を生成し、 E ( i ) > E (n e w) である場合であって、 i > lについて E ( i - 1 ) > E (n ew ) ではない場合、 画素パターン累積器 8 Aからの新たな累積データを選 択する選択信号を生成し、 i > lについて E ( i - 1 ) > E (n ew) である場合、 前段の記憶部 7 1— ( i— 1 ) のレジス夕 84からの累積 データを選択する選択信号を生成する。 制御回路 8 2は選択信号を生成 するとセレクタ 83に供給する。 セレクタ 83はその選択信号に応じて レジス夕 84からの累積デ一夕、 画素パターン累積器 8 Aからの累積デ —夕および前段の記憶部 7 1— ( i - 1 ) , 7 1— ( i + 1 ) からの累 積データのうちのいずれかを選択し、 レジス夕 84に供給する。 レジス 夕 84は所定のクロック信号 C LKに同期して、 記憶している累積デ一 夕を、 供給された累積デ一夕で更新する。
これにより、 第 1回目の評価値の累積により、 n個の探索ベク トルに ついての累積デ一夕が記憶手段 6 6に いて評価値 （の累積値） の昇順 に記憶される。
次に第 2回目以降の評価値の累積の場合における動きべク トル検出部 7 Aの動作について説明する。
第 2回目以降の評価値の累積では、 演算手段 6 7は、 先頭の記憶部 7 1一 1に記憶されている累積データ、 すなわち累積値が最小である累積 デ一夕における探索べク トルについて次の画素パターンをオフセッ 卜で 指定して次の評価値を計算させる。 その評価値は評価部 4から画素パ夕 —ン累積器 8 Aに供給される。 そして、 画素パターン累積器 8 Aから新 たな累積デ一夕が記憶部 7 1— 1〜7 1— nの比較器 8 1およびセレク 夕 8 3に供給される。
各記憶部 7 1 iの比較器 8 1は、 レジスタ 84に記憶されている累 積データにおける累積値 E ( i ) と、 画素パターン累積器 8 Aからの累 積データにおける累積値 E (n ew) とを比較し、 その比較結果、 すな わち、 E ( i ) > E (n ew) であるか否かを制御回路 8 2、 並びに、 前段および後段の記憶部 7 1— ( i - 1 ) , 7 1— ( i + 1 ) の制御回 路 8 2に供給する。 - そして記憶部 7 1— i ( i = l， · · ·， n- 1 ) の制御回路 82は 、 E ( i + 1 ) > E (n ew) ではない場合、 後段の記憶部 7 1— （ i + 1 ) からの累積デ一夕を選択する選択信号を生成し、 E ( i ) > E ( n ew) ではなく、 かつ E ( i + 1 ) > E (new) である場合、 画素 パターン累積器 8 Aからの新たな累積デ一夕を選択する選択信号を生成 し、 E ( i ) > E (n ew) であり、 かつ E ( i + 1 ) > E (n ew) である場合、 レジス夕 84の累積デ一夕を選択する選択信号を生成する 。 また記憶部 7 1— nの制御回路 8 2は、 E (n) > E (n ew) では ない場合、 画素パターン累積器 8 Aからの新たな累積データを選択する 選択信号を生成する。 制御回路 8 2は選択信号を生成するとセレクタ 8 3に供給する。 セレクタ 83はその選択信号に応じてレジス夕 84から の累積データ、 画素パターン累積器 8 Aからの累積デ一夕および後段の 記憶部 7 1 - ( i + 1 ) からの累積デ一夕のうちのいずれかを選択し、 レジス夕 84に供給する。 レジス夕 84は所定のクロック信号 C L Kに 同期して、 記憶している累積データを、 供給された累積デ一夕で更新す る o
これにより、 第 2回目以降の評価値の累積では、 累積値が最小である 探索べク トルについての評価値の累積が順次実行され、 その探索ぺク ト ルについての新たな累積デ一夕が記憶手段 6 6に供給され、 その探索べ ク トルの元の累積デ一夕が破棄され、 新たな累積デ一夕を含めた n個の 累積デ一夕が、 累積値の昇順に配列される。
なお、 その他の構成要素の動作については実施の形態 5によるものと 同様であるので、 その説明を省略する。 また、 ここでは、 評価値の累積 値の昇順に累積デ一夕が配列されているが、 評価値の計算のしかたによ つては降順に配列される場合もある。
以上のように、 この実施の形態 6によれば、 複数の探索ベク トルにつ いての評価値の累積値を'昇順または降順に配列して記憶していき、 その 配列の先頭に対応する探索べク トルを選択し、 選択した探索べク トルに ついて評価値の累積を実行し、 複数の探索べク トルについての評価値の 累積値を昇順または降順に再配列し、 配列の先頭の評価値の累積回数が 所定の回数である場合、 その探索べク トルを動きぺク トルとするように したので、 次に評価値の累積を実行する探索ぺク トルを選択する際に、 単に配列の先頭の探索べク トルを選択すればよく、 各探索ぺク トルにつ いての評価値の累積値を参照する必要がなく、 評価値の累積を打ち切る 探索べク トルの選択を迅速に実行することができるという効果が得られ る。 実施の形態 7 .
この発明の実施の形態 7による動きべク トル検出装置は、 M P E G 2 方式などのように双方向予測を実行する際に、 符号化されたフレームの うちの、 ブロックの位置から所定の行および所定の列の、 前方向の動き べク トル検出用の第 1のサーチウィ ンドウ、 および後方向の動きべク ト ル検出用の第 2のサーチウイ ン ドウの画素のデ一夕をサーチウイ ンドウ メモリ部 2に記憶し、 上述と同様にして、 前方向の動きベク トルおよび 後方向の動きベク トルを検出するようにしたものである。
なお、 実施の形態 7による動きべク トル検出装置の構成については実 施の形態 1〜 6のいずれかによるものと同様であるが、 サ一チウイ ン ド ウメモリ部 2のメモリ 1 1一 （ I , J ) には、 前方向および後方向双方 のサ一チウイ ンドウにおける画素デ一夕が記憶される。
次に動作について説明する。
第 2 6図は前方向のサーチウイ ン ドウおよび前方向の探索プロックの 一例を示す図である。 第 2 7図は後方向のサーチウィ ン ドウおよび後方 向の探索ブロックの一例を示す図である。
例えば第 2 6図および第 2 7図に示すように、 サーチウィ ン ドウメモ リ部 2のメモリ 1 1— ( I， J ) には、 前方向のサーチウィ ン ドウにお ける画素データが記憶され、 その後のアドレスに、 後方向のサーチウイ ン ドウにおける画素デ一夕が記憶される。
そして、 まず、 前方向のサーチウィ ンドウにおいて前方向の動きべク トルが、 上述の実施の形態 1〜 6のように探索され、 検出される。 その 後に、 後方向のサ一チウイ ンドウにおいて後方向の動きベク トルが、 上 述の実施の形態 1 ~ 6のように探索され、 検出される。
以上のように、 この実施の形態 7によれば、 符号化されたフレームの うちの、 プロックの位置から所定の行および所定の列の、 前方向の動き べク トル検出用の第 1のサーチウィ ン ドウ、 および後方向の動きべク ト ル検出用の第 2のサーチウィ ン ドゥの画素のデータをサーチウイ ンドウ メモリ部 2に記憶し、 それらのデータから前方向の動きべク トルおよび 後方向の動きべク トルを検出するようにしたので、 サーチウイ ン ドウメ モリ部 2に必要な記憶容量が増加するものの、 他の構成要素を増加させ ることなく、 前方向および後方向の動きベク トルを検出することができ るという効果が得られる。
なお、 実施の形態 7は、 上述の実施の形態 1〜 6のいずれかに適用さ れるものであるが、 従来の動きべク トル検出装置に適用してもよい。 なお、 上記のサーチウィ ン ドウ、 ブロックおよび画素パターンにおけ る画素の数、 メモリ 1 1— ( I , J ) , 1 6— ( I , J ) の数などは一 例にすぎず、 必要に応じて他の数としてもよい。 産業上の利用可能性
以上のように、 この発明は、 動き予測を実行する画像処理方式におい て動きべク トルを検出するのに適している。

Claims

請 求 の 範 囲
1 . 画像データにおけるフレームを分割した各ブロックについて、 既に 符号化されたフレームに対する動きべク トルを検出する動きべク トル検 出装置において、
前記プロックを構成する複数の画素パターンを構成する画素のデータ を記憶する第 1の記憶手段と、
前記符号化されたフレームのうちの所定の範囲において所定の画素数 おきの所定の数の画素でそれそれ構成される複数の画素パターンにおけ る同一位置の画素のデータごとに、 前記符号化されたフレームのうちの 前記所定の範囲の画素のデ一夕を記憶する第 2の記憶手段と、
所定の探索ぺク トルを供給され、 前記所定の範囲においてその探索べ ク トルで指定されたプロックにおける 1つの画素パターンを選択する選 択手段と、
前記選択手段により選択された画素パターンと、 その画素パターンと 同一の、 前記第 1の記憶手段に記憶された画素パターンとを画素ごとに 比較する比較手段と、
前記比較手段による比較の結果に基づいて前記動きべク トルを検出す る検出手段と
を備えることを特徴とする動きベク トル検出装置。
2 . 画像データにおけるフレームを分割した各ブロックについて、 既に 符号化されたフレームに対する動きべク トルを検出する動きべク トル検 出装置において、
前記プロヅクを構成する複数の画素パターンまたは複数の分割プロッ クを構成する画素のデータを記憶する第 1の記憶手段と、 前記符号化されたフレームのうちの所定の範囲を構成する複数の画素 パターンまたは複数の分割プロックにおける同一位置の画素のデータご とに、 前記符号化されたフレームのうちの前記所定の範囲の画素のデ一 夕を記憶する第 2の記憶手段と、
前記動きべク トルの候補である複数の探索ぺク トルを供給され、 前記 所定の範囲において各探索べク トルで指定されたブロックにおける同一 の画素パターンまたは各分割プロックを順次選択する選択手段と、 前記選択手段により選択された画素パターンまたは分割プロックと、 その画素パターンまたは分割プロックと同一の、 前記第 1の記憶手段に 記憶された画素パターンまたは分割プロックとを画素ごとに比較する比 較手段と、
1つの探索べク トルについて前記比較手段による全画素パターンまた は全分割プロックについての比較が完了する以前に、 その時点までの画 素パターンまたは分割プロヅクについての比較結果に応じて、 その探索 べク トルについての前記選択手段および比較手段による処理を中止させ 、 その探索べク トルを前記動きぺク トルの候補から削除する探索べク ト ル絞込手段と、
前記比較手段による比較の結果に基づいて前記動きべク トルの候補か ら前記動きべク トルを検出する検出手段と
を備えることを特徴とする動きべク トル検出装置。
3 . 探索ベク トル絞込手段は、 複数の探索ベク トルについての同一の画 素パ夕一ンまたは同一の分割ブロックごとに、 その同一の画素パターン または同一の分割プロックの比較が完了した後ごとに、 所定の条件を満 足する場合に前記複数の探索べク トルのうちの少なく とも 1つを動きべ ク トルの候補から削除する ことを特徴とする請求の範囲第 2項記載の動きべク トル検出装置。
4 . 比較手段は、 比較結果として評価値を算出し、
探索べク トル絞込手段は、 各探索べク トルについて複数の画素パ夕一 ンでの評価値の累積値を計算し、 複数の探索ぺク トルについての前記評 価値の累積値を昇順または降順に配列して記憶していき、 その配列にお ける前記評価値の順序に基づいて 1 または複数の探索べク トルを動きべ ク トルの候補から削除する
ことを特徴とする請求の範囲第 3項記載の動きべク トル検出装置。
5 . 比較手段は、 比較結果として評価値を算出し、
探索べク トル絞込手段は、 前記複数の探索べク トルについての前記評 価値の累積値において最小値または最大値の評価値に対応する探索べク トルを選択し、 選択した探索べク トルについて前記評価値の累積を実行 し、 検出手段は、 最小値または最大値の評価値の累積回数が所定の回数 である場合、 その探索ベク トルを動きベク トルとする
ことを特徴とする請求の範囲第 2項記載の動きべク トル検出装置。
6 . 探索ぺク トル絞込手段は、 複数の探索べク トルについての評価値の 累積値を昇順または降順に配列して記憶していき、 その配列の先頭に対 応する探索べク トルを選択し、 選択した探索べク トルについて前記評価 値の累積を実行し、 複数の探索べク トルについての評価値の累積値を昇 順または降順に再配列し、 配列の先頭の評価値の累積回数が所定の回数 である場合、 その探索ベク トルを動きベク トルとする
ことを特徴とする請求の範囲第 5項記載の動きべク トル検出装置。
7 . 画像デ一夕におけるフ レームを分割した各ブロックについて、 既に 符号化されたフ レ一ムに対する動きぺク トルを検出する動きべク トル検 出装置において、
前記ブロックを構成する画素データのうちの所定の数の画素データを 記憶する第 1の記憶手段と、
前記符号化されたフ レームのうち、 前方向の動きべク トル検出用の第 1の範囲内、 および後方向の動きべク トル検出用の第 2の範囲内の画素 データを記憶する第 2の記憶手段と、
前方向の探索べク トルおよび後方向の探索ぺク トルを供給され、 前記 第 2の記憶手段に記憶された前記画素データのうちの、 前記プロックの 位置から前記探索べク トルだけ離れた位置の、 前記プロックと同一の大 きさの範囲の画素データのうちの所定の数の画素デ一夕を選択する選択 手段と、
前記第 1の記憶手段に記憶された所定の数の画素デ一夕と、 前記選択 手段によ り選択された所定の数の画素データとを比較する比較手段と、 前記比較手段による比較の結果に基づいて前方向の動きべク トルおよ び後方向の動きぺク トルを検出する検出手段と
を備えることを特徴とする動きベク トル検出装置。
PCT/JP2000/007598 2000-10-27 2000-10-27 Moving vector detector WO2002037860A1 (en)

Priority Applications (4)

Application Number Priority Date Filing Date Title
JP2002540466A JPWO2002037860A1 (ja) 2000-10-27 2000-10-27 動きベクトル検出装置
CN00817874.7A CN1415171A (zh) 2000-10-27 2000-10-27 运动矢量检测装置
EP00970180A EP1331826A1 (en) 2000-10-27 2000-10-27 Moving vector detector
PCT/JP2000/007598 WO2002037860A1 (en) 2000-10-27 2000-10-27 Moving vector detector

Applications Claiming Priority (1)

Application Number Priority Date Filing Date Title
PCT/JP2000/007598 WO2002037860A1 (en) 2000-10-27 2000-10-27 Moving vector detector

Publications (1)

Publication Number Publication Date
WO2002037860A1 true WO2002037860A1 (en) 2002-05-10

Family

ID=11736634

Family Applications (1)

Application Number Title Priority Date Filing Date
PCT/JP2000/007598 WO2002037860A1 (en) 2000-10-27 2000-10-27 Moving vector detector

Country Status (4)

Country Link
EP (1) EP1331826A1 (ja)
JP (1) JPWO2002037860A1 (ja)
CN (1) CN1415171A (ja)
WO (1) WO2002037860A1 (ja)

Families Citing this family (3)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JP4610523B2 (ja) * 2006-06-13 2011-01-12 Ｏｋｉセミコンダクタ株式会社 動画処理装置
EP2665271A4 (en) * 2011-01-12 2014-06-18 Panasonic Corp VIDEO CODING METHOD AND VIDEO CODING METHOD
KR101878008B1 (ko) 2011-03-03 2018-07-13 선 페이턴트 트러스트 동화상 부호화 방법, 동화상 복호 방법, 동화상 부호화 장치, 동화상 복호 장치 및 동화상 부호화 복호 장치

Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH02274083A (ja) * 1989-04-17 1990-11-08 Nec Corp 動ベクトル検出装置
JPH02295288A (ja) * 1989-05-10 1990-12-06 Nec Corp 動ベクトル検出装置
JPH04180382A (ja) * 1990-11-14 1992-06-26 Matsushita Electric Ind Co Ltd 動ベクトル検出方法
JPH05260460A (ja) * 1992-03-09 1993-10-08 Matsushita Electric Ind Co Ltd 動き検出装置
JPH07162864A (ja) * 1993-12-08 1995-06-23 Ricoh Co Ltd 動きベクトル検出方法
JP2000069484A (ja) * 1998-08-21 2000-03-03 Sony Corp 動きベクトル算出方法及び動きベクトル算出プログラムを記録した記録媒体

Patent Citations (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
JPH02274083A (ja) * 1989-04-17 1990-11-08 Nec Corp 動ベクトル検出装置
JPH02295288A (ja) * 1989-05-10 1990-12-06 Nec Corp 動ベクトル検出装置
JPH04180382A (ja) * 1990-11-14 1992-06-26 Matsushita Electric Ind Co Ltd 動ベクトル検出方法
JPH05260460A (ja) * 1992-03-09 1993-10-08 Matsushita Electric Ind Co Ltd 動き検出装置
JPH07162864A (ja) * 1993-12-08 1995-06-23 Ricoh Co Ltd 動きベクトル検出方法
JP2000069484A (ja) * 1998-08-21 2000-03-03 Sony Corp 動きベクトル算出方法及び動きベクトル算出プログラムを記録した記録媒体

Also Published As

Publication number Publication date
EP1331826A1 (en) 2003-07-30
JPWO2002037860A1 (ja) 2004-03-11
CN1415171A (zh) 2003-04-30

Similar Documents

Publication Publication Date Title
US6690730B2 (en) Motion estimator
US5450553A (en) Digital signal processor including address generation by execute/stop instruction designated
JPH06334980A (ja) 動画像の動きベクトル検出装置
US6687299B2 (en) Motion estimation method and apparatus for interrupting computation which is determined not to provide solution
WO2002037860A1 (en) Moving vector detector
JPH0965339A (ja) 画像ブロック動き検出装置
JP4695124B2 (ja) 動画像符号化における動き探索装置
JP2004048512A (ja) 動画像符号化方法と動画像符号化回路
JP2002152750A (ja) 動きベクトル検出方法および装置
KR0178302B1 (ko) 양방향 병렬 파이프라인 구조에 근거한 탐색 이동 예측처리기
US6931066B2 (en) Motion vector selection based on a preferred point
KR20010052624A (ko) 움직임 추정
CN111968151A (zh) 一种运动估计精细搜索方法及装置
JP4859168B2 (ja) 動き検出装置及び動き検出方法
JP2885039B2 (ja) 動きベクトル検出回路
JPH10304371A (ja) 動きベクトル検出装置
JP2866325B2 (ja) 動きベクトル探索装置
JPH0993581A (ja) 動画像符号化装置の動き検出装置
JP2618146B2 (ja) 動きベクトル検出回路
WO2009074947A1 (en) Instruction set for parallel calculation of sad values for motion estimation
JP2901848B2 (ja) ベクトル相関検出回路
KR100223052B1 (ko) 비디오 움직임 추정장치
JP2931789B2 (ja) 動きベクトル探索装置
JPH10164586A (ja) 動きベクトル検出回路
JPH1079943A (ja) 動きベクトル検出装置

Legal Events

Date Code Title Description
WWE Wipo information: entry into national phase

Ref document number: 10130257

Country of ref document: US

WWE Wipo information: entry into national phase

Ref document number: 2000970180

Country of ref document: EP

ENP Entry into the national phase

Ref country code: JP

Ref document number: 2002 540466

Kind code of ref document: A

Format of ref document f/p: F

WWE Wipo information: entry into national phase

Ref document number: 008178747

Country of ref document: CN

121 Ep: the epo has been informed by wipo that ep was designated in this application
WWP Wipo information: published in national office

Ref document number: 2000970180

Country of ref document: EP

WWW Wipo information: withdrawn in national office

Ref document number: 2000970180

Country of ref document: EP

点击 这是indexloc提供的php浏览器服务，不要输入任何密码和下载