Motion estimator

Claim 2

A motion detector for video signals comprising: - means for reception and temporary storage of signals representing one line-scanned frame of a picture and of signals representing another such frame of the picture; and - means for comparing each of a plurality of blocks into which the said one frame is divided with the corresponding region of the other frame and with a plurality of positionally shifted regions of the other frame, to produce vector information indicating the positional shift if any between the position of the block and the position of that region of the other frame which meets a criterion of similarity between the block and the regions, characterised in that the comparison means is arranged to operate sequentially upon blocks disposed in rows aligned with the picture line direction of said one frame, and to compare each with the said plurality of positionally shifted regions of the other frame in a sequential column-by-column scan of part of said other frame.

Claim 3

A detector according to Claim 1 in which the reception and storage means comprise: (i) first picture storage means for simultaneously making available, for a period corresponding to a desired search extent in the line direction of the picture, a group of picture elements corresponding to a block of the said one frame, where successive groups within a sequence of such groups correspond to respective non-overlapping blocks; and (ii) second picture storage means for making simultaneously available a group of picture elements corresponding to a region of the other frame of the same size as the block, where successive groups within a sequence of such groups correspond to regions progressively shifted in a direction down in a column of the lines of the picture, and successive such sequences correspond to regions progressively shifted along the lines; and the comparing means comprise arithmetic means for forming the sum of the moduli or other monotonically increasing even function of the differences between the elements made available for a block and the elements made available for a region and means to ascertain for each block the vector information corresponding to the region whose sum meets the said criterion.

Claim 4

A detector according to Claim 2, in which the second picture storage means of Claim 2 comprises a FIFO array including m sections, where m is the width of a block along the line direction, each such section comprising a SIPO stage having n taps, where n is the depth of a block along a column of such lines, the SIPO stages being separated by FIFO stages, the length of each section being D, where D is the extent of the said column-by-column scan.

Claim 5

A detector according to Claim 3, in which the length of the FIFO stages is 2q + 1, where ±q is the maximum vertical positional shift of the most displaced region of the other frame with which each block is to be compared.

Claim 6

A detector according to Claim 3 for processing in parallel the vertically neighbouring blocks of a plurality A of horizontal rows, in which (where ±q is the maximum vertical positional shift of the most displaced region of the other frame with which each block is to be compared):- - there are provided A arithmetic means; - each is connected to a first delay and storage means such that each processes blocks of a different row of said one frame; - each is connected to a second delay means which includes one FIFO stage of such a length that the regions of said other frame which each arithmetic means at a given time is comparing are vertically displaced one from another by n rows; and - the lengths of the other FIFO stages of such second delay means are 2q + (A-1) n.

Claim 7

A detector according to Claim 2, in which the second delay means is arranged concurrently to make available additional sequences corresponding to regions (or blocks) shifted by successive multiples of n lines relative to the first mentioned sequence so as to correspond to regions for blocks) vertically adjacent the first sequence, and the comparing means include additional arithmetic means for processing the additional sequence(s).

Claim 8

A detector according to any one of claims 3 to 6, in which the length of the FIFO stages is controllably variable.

Claim 9

A detector according to any one of claims 2 to 6, in which the desired search extent in the line direction is greater than half the extent of a block in that direction, the delay and storage means is arranged concurrently to form a plurality B (where B is the lowest integer greater than 2p/m) of different sequences containing groups of picture elements corresponding to every B-th block in the line direction, and the arithmetic means comprises a plurality B of arrangements for forming the said sums for the respective sequences.

Claim 10

A detector according to any preceding claim, including store means for storing and outputting for a block either the region of said other frame to which it is most similar, or the block prediction error between the block and the region.

Claim 11

A detector according to claim 9 arranged to receive and process luminance and chrominance blocks of a colour picture signal.

Claim 12

A detector according to any one of the preceding claims, in which the said criterion is met by a region for which a comparison value equal in the case of the unshifted region to a predetermined proportion of the said sum and equal in the case of the other regions to the said sum is less than the comparison value for all other regions compared with the block.

Claim 13

A motion detector substantially as herein described with reference to the accompanying drawings.

Claim 14

A motion detector substantially as herein described with reference to the accompanying drawings.

Claim 15

A detector according to claim 1 comprising a plurality of processors each comprising; (i) first picture storage means for simultaneously making available, for a period corresponding to a desired search extent in the line direction of the picture, a group of picture elements corresponding to a block of the said one frame, where successive groups within a sequence of such groups correspond to respective non-overlapping blocks; and (ii) second picture storage means for making simultaneously available a group of picture elements corresponding to a region of the other frame of the same size as the block, where successive groups within a sequence of such groups correspond to regions progressively shifted in a direction down in a column of the lines of the picture, and successive such sequences correspond to regions progressively shifted along the lines; and (iii) arithmetic means for forming the sum of the moduli or other monotonically increasing even function of the differences between the elements made available for a block and the elements made available for a region and means to ascertain for each block the vector information corresponding to the region whose sum meets the said criterion; in which: the first and second picture storage means of some of the processors are configurable, so as to process blocks in vertically neighbouring rows simultaneously, and the arithmetic means of the processors are connectable and means are provided for forming the sum of the said sums of difference function for each processor, whereby the motion detector may be configured to compare composite blocks comprising a plurality of neighbouring said blocks.

Claim 16

A motion detector for video signals comprising: - means for reception and temporary storage of signals representing one line-scanned frame of a picture and of signals representing another such frame of the picture; and - means for comparing each of a plurality of blocks into which the said one frame is divided with the corresponding region of the other frame and with a plurality of positionally shifted regions of the other frame, to produce vector information indicating the positional shift if any between the position of the block and the position of that region of the other frame which meets a criterion of similarity between the block and the regions, characterised in that the comparison means is arranged to operate sequentially upon blocks disposed in columns aligned normal to the picture line direction of said one frame, and to compare each with the said plurality of positionally shifted regions of the other frame in a sequential row-by-row scan of part of said other frame.

Claim 17

A motion detector for video signals comprising: - means for reception and temporary storage of signals representing one line-scanned frame of a picture and of signals representing another such frame of the picture; and - means for comparing each of a plurality of blocks into which the said one frame is divided with the corresponding region of the other frame and with a plurality of positionally shifted regions of the other frame, to produce vector information indicating the positional shift if any between the position of the block and the position of that region of the other frame which meets a criterion of similarity between the block and the regions, characterised in that the comparison means is arranged to operate sequentially upon blocks disposed in columns aligned normal to the picture line direction of said one frame, and to compare each with the said plurality of positionally shifted regions of the other frame in a sequential row-by-row scan of part of said other frame.