Block matching between first data and second data

Patent metadata

Field	Value
Publication number	US-12393400-B1
Application number	US-202418431707-A
Country	US
Kind code	B1
Filing date	Feb 2, 2024
Priority date	Feb 2, 2024
Publication date	Aug 19, 2025
Grant date	Aug 19, 2025

Abstract

A processor, method, and non-transitory computer-readable storage medium for performing a block matching between first data and second data are provided. The block matching is performed using an iterative process, wherein, for each iteration, a portion of the first data and a corresponding portion of the second data is selected using a sliding window approach. When differences data, used for block matching, is calculated for a specific subset of first and second data, many of the calculations overlap with those needed for a nearby subset. Summed area table, SAT, data used for determining the difference data is continuously stored and updated in a buffer, such that overlapping computations can be avoided.

First claim

What is claimed is:

1. A method for block matching performed by a processor between first data and second data, the method comprising the steps of:
a) configuring a buffer in internal memory of the processor for storing summed area table, SAT, data;
b) populating the buffer with initial SAT data based on a difference between at least an initial portion of the first data and second data;
c) performing an iterative process, wherein each iteration of the iterative process comprises:
c1) selecting a first portion of the first data and a corresponding second portion of the second data, wherein the selecting is performed using a sliding window approach, wherein a window used for selecting moves with a predefined window offset for each iteration;
c2) determining a subset of the first portion of the first data and a subset of the second portion of the second data;
c3) computing absolute differences, AD, data between the determined subset of the first portion and the determined subset of the second portion;
c4) computing SAT data using the computed AD data and at least a portion of the SAT data stored in the buffer;
c5) replacing a subset of the SAT data stored in the buffer with at least portions of the computed SAT data;
c6) calculating difference data between the first portion and the second portion using the SAT data stored in the buffer, wherein the difference data comprises a difference result for each of a plurality of comparisons between the first data and the second data; and
c7) storing the calculated difference data between the first portion and the second portion to memory; and

d) using the stored difference data to determine matched blocks of data between the first data and second data.

2. The method of claim 1 , wherein the step b) comprises:
b1) computing initial AD data between the initial portion of the first data and the initial portion of the second data;
b2) computing the initial SAT data using the computed initial AD data;
b3) storing the initial SAT data in the buffer.

3. The method of claim 1 , further comprising:
defining a template block size;
wherein the step c6) is performed according to the template block size.

4. The method of claim 3 , wherein the difference data calculated during an iteration of the iterative process comprises 16 difference results.

5. The method of claim 1 , wherein step c2) comprises:
determining a subset of the first portion and a subset of the second portion not previously selected during the iterative process.

6. The method of claim 1 , wherein a maximum size of each SAT data item is T bits, where the step of calculating difference data between the first portion and the second portion comprises, upon determining that a difference result for a comparison between the first portion and the second portion has a negative size, adding 2 T-1 to the difference result.

7. The method of claim 6 , wherein T=16.

8. The method of claim 1 , wherein the first data comprises a plurality of data items, wherein each difference result is associated with a data item of the plurality of data items.

9. The method of claim 8 , wherein steps a)-d) is performed for a plurality of search offsets, wherein the method further comprises:
applying each search offset of the plurality of search offsets by:
step c1) comprising selecting the corresponding second portion of the second data according to the search offset,
step d) comprising, for each data item of the plurality of data items, upon determining that the difference result calculated for the data item is lower than the difference result(s) calculated for all previous offsets for that data item, associating the search offset with the data item.

10. The method of claim 9 , wherein step d) comprises, upon determining that at least a threshold number of difference results in the difference data calculated for the search offset is below a threshold value, aborting the method and using the search offsets associated with the data items of the first data to determine matched blocks of data between the first data and second data.

11. The method of claim 9 , wherein the plurality of search offsets are applied in an order according to a predefined search pattern.

12. The method of claim 9 , further comprising receiving a list of search offset displacements and an initial search offset, wherein the plurality of search offsets are applied in an order according to the list of search offset displacements, starting at the initial search offset.

13. The method of claim 9 , further comprising:
for each data item of the first data, using the search offset associated the data item to determine a motion vector between first data and second data for the data item.

14. The method of claim 1 , wherein the difference data is one of: sum of absolute differences, SAD, data, or sum of squared differences, SSD, data.

15. A non-transitory computer-readable storage medium comprising a set of computer-readable instructions stored thereon which, when executed by at least one processor are arranged to cause the at least one processor to perform a block matching operation between first data and second data by:
a) configuring a buffer in internal memory of the processor for storing summed area table, SAT, data;
b) populating the buffer with initial SAT data based on a difference between at least an initial portion of the first data and second data;
c) performing an iterative process, wherein each iteration of the iterative process comprises:
c1) selecting a first portion in the first data and a corresponding second portion of the second data, wherein the selecting is performed using a sliding window approach, wherein a window used for selecting moves with a predefined window offset for each iteration;
c2) determining a subset of the first portion and a subset of the second portion;
c3) computing absolute differences, AD, data between the determined subset of the first portion and the determined subset of the second portion;
c4) computing SAT data using the computed AD data and at least a portion of the SAT data stored in the buffer;
c5) replacing a subset of the SAT data stored in the buffer with at least portions of the computed SAT data;
c6) calculating difference data between the first portion and the second portion using the SAT data stored in the buffer, wherein the difference data comprises a difference result for each of a plurality of comparisons between the first data and the second data; and
c7) storing the calculated difference data between the first portion and the second portion to memory; and

d) using the stored difference data to determine matched blocks of data between the first data and second data.

16. A processing module configured to perform a block matching operation between first data and second data, the processing module configured to:
obtain task data describing a block matching task to be executed between first data and second data;
configure a buffer in internal memory of the processor for storing summed area table, SAT, data;
populate the buffer with initial SAT data based on a difference between at least an initial portion of the first data and second data;
perform an iterative process, wherein each iteration of the iterative process comprises:
select a first portion of the first data and a corresponding second portion of the second data using a sliding window approach, wherein a window used for selecting moves with a predefined window offset for each iteration;
determine a subset of the first portion of the first data and a subset of the second portion of the second data;
compute

Assignees

• Advanced Risc Mach Ltd

Inventors

• Brothers Iii John Wakefield
• Ünal Metin Gokhan
• VENU Balaji
• Holm Rune

Classifications

• G06V10/74

  Image or video pattern matching; Proximity measures in feature spaces · CPC title

• G06T7/223

  using block-matching · CPC title

• G06F16/148 Primary

  File search processing · CPC title

• G06F7/20 Primary

  Comparing separate sets of record carriers arranged in the same sequence to determine whether at least some of the data in one set is identical with that in the other set or sets · CPC title