Correlation degree operation apparatus, parallel correlation degree operation apparatus and correlation degree operation method

• US 5,929,939 A
• Filed: 04/18/1996
• Issued: 07/27/1999
• Est. Priority Date: 04/18/1995
• Status: Expired due to Term

• Current Assignee: Socionext Inc.
• Original Assignee: Matsushita Electric Industrial Company Limited (Panasonic Holdings Corporation)
• Inventors: Gion, Masahiro, Matsumoto, Yoshifumi, Aoki, Katsuji, Ubukata, Atsushi, Yoshida, Hisato, Ohtani, Akihiko, Sota, Akira
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): DIN, LUANNE PAN
• Application Number:
  US08/634,490
• Time in Patent Office: 1,195 Days
• Field of Search: 348/699, 348/700, 348/420, 348/421, 348/416, 348/405, 348/419, 348/719, 348/720, 348/721, 395/480
• US Class Current: 348/699
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation

Abstract

There is provided a correlation degree operation apparatus in which the search area is readily extensible, in which a high-speed process can be assured even though the search area is extended, and which can be formed in a simple arrangement. The search area memory stores the picture element data of a search area including ((m×M)×L) candidate blocks. The correlation degree operation unit executes an operation of a degree of correlation between a reference picture block and each of the candidate blocks, with the use of picture element data supplied from the search area memory, this operation being executed by a pipeline process for each candidate block group composed of (M×L) candidate blocks. The search area memory has the function of supplying four picture element data at the same clock cycle. This enables the correlation degree operation unit to continuously execute the pipeline processes for the candidate block groups. It is therefore possible to continuously execute the operations of correlation degree between the reference picture block having (M×N) picture elements and ((m×M)×L) candidate blocks.

Claims

1. A correlation degree operation apparatus for operating, according to a block matching method, a degree of correlation between a reference picture block having (M×

N) picture elements and each of ((m×

M)×

L) candidate blocks (in which each of M, N, L, m is a natural number, L is not less than N and m is not less than

     2), characterized in that;

an operation of correlation degree is executed by a pipeline process for each of m candidate block groups composed of (M×

L) candidate blocks, said m candidate block groups are continuously arranged to overlap one another in one of a horizontal direction and vertical direction;

said pipeline process is an operation of repeating, L times in the other direction than the direction in which said m candidate block groups overlap, a step of applying a block-matching process to a reference picture block with respect to each of M candidate blocks arranged to continuously overlap one another in said one direction; and

there are used, at the same clock cycle, both the picture element data required for an operation of correlation degree for one candidate block group and the picture element data required for an operation of correlation degree for another candidate block group to be executed subsequently to said first-mentioned operation for said one candidate block group.

2. A correlation degree operation apparatus for operating, according to a block matching method, a degree of correlation between a reference picture block having (M×

N) picture elements and each of ((m×

M)×

L) candidate blocks (in which each of M, N, L, m is a natural number, L is not less than N and m is not less than

     2), comprising;

a search area memory for storing the picture element data of a search area including ((m×

M)×

L) candidate blocks; and

a correlation degree operation unit for holding the picture element data of a reference picture block having (M×

N) picture elements and executing an operation of a degree of correlation between said reference picture block and each of said candidate blocks, with the use of said held picture element data of said reference picture block and the picture element data of each candidate block supplied from said search area memory, said operation being executed by a pipeline process for each candidate block group composed of (M×

L) candidate blocks,

said search area memory having the function of supplying, to said correlation degree operation unit at the same clock cycle, both the picture element data required for an operation of correlation degree for one candidate block group and the picture element data required for an operation of correlation degree for another candidate block group to be executed subsequently to said first-mentioned operation for said one candidate block group,

said correlation degree operation unit being arranged to continuously execute the operations for said candidate block groups.

3. A correlation degree operation apparatus according to claim 2, wherein said search area memory has the function of selecting, out of the picture element data of said search area having ((m+1)×

M-1) columns and (L+N-1) rows and including ((m×

M)×

L) candidate blocks, (i) a first picture element data and a second picture element data which is located on the row upper by one row from said first picture element data and which is located in the column rightward by M columns from said first picture element data, said first and second picture element data being required for said operation for said one candidate block group, and (ii) a third picture element data and a fourth picture element data which is located on the row upper by one row from said third picture element data and which is located in the column rightward by M columns from said third picture element data, said third and fourth picture element data being required for said operation for said another candidate block group, said first to fourth picture element data being supplied to said correlation degree operation unit at the same clock cycle.

4. A correlation degree operation apparatus according to claim 3, wherein said third picture element data is located on the row upper by L rows from said first picture element data and in the column rightward by M columns from said first picture element data.

5. A correlation degree operation apparatus for operating, according to a block matching method, a degree of correlation between a reference picture block having (M×

N) picture elements and each of ((m×

M)×

L) candidate blocks (in which each of M, N, L, m is a natural number, L is not less than N and m is not less than

     2), comprising;

a main control unit for generating and supplying a memory control signal and an operation control signal based on a given clock;

a search area memory which stores the picture element data of a search area including ((m×

M)×

L) candidate blocks, and which is arranged to supply stored picture element data according to the instruction of said memory control signal supplied from said main control unit;

a correlation degree operation unit for holding the picture element data of a reference picture block having (M×

N) picture elements and executing an operation of a degree of correlation between said reference picture block and each of said candidate blocks, with the use of said held picture element data of said reference picture block and the picture element data supplied from said search area memory, said operation being executed by a pipeline process for each candidate block group composed of (M×

L) candidate blocks; and

an operation control unit for controlling said correlation degree operation unit according to the instruction of said operation control signal supplied from said main control unit,

said search area memory having the function of supplying, to said correlation degree operation unit at the same clock cycle, both the picture element data required for an operation of correlation degree for one candidate block group and the picture element data required for an operation of correlation degree for another candidate block group to be executed subsequently to said first-mentioned operation for said one candidate block group,

said correlation degree operation unit being arranged to continuously execute the operations for said candidate block groups.

6. A correlation degree operation apparatus according to claim 5, wherein said search area memory has the function of selecting, out of the picture element data of said search area having ((m+1)×

M-1) columns and (L+N-1) rows and including ((m×

M)×

L) candidate blocks, (i) a first picture element data and a second picture element data which is located on the row upper by one row from said first picture element data and which is located in the column rightward by M columns from said first picture element data, said first and second picture element data being required for said operation for said one candidate block group, and (ii) a third picture element data and a fourth picture element data which is located on the row upper by one row from said third picture element data and which is located in the column rightward by M columns from said third picture element data, said third and fourth picture element data being required for said operation for said another candidate block group, said first to fourth picture element data being supplied to said correlation degree operation unit at the same clock cycle.

7. A correlation degree operation apparatus according to claim 6, wherein said third picture element data is located on the row upper by L rows from said first picture element data and in the column rightward by M columns from said first picture element data.

8. A correlation degree operation apparatus according to claim 5, wherein said search area memory has the function of supplying four picture element data for one clock cycle.

9. A correlation degree operation apparatus according to claim 8, wherein said search area memory comprises:

(m+1) memory element portions which respectively store the picture element data of (m+1) partial search areas obtained by dividing, per (M×

(L+N-1)) picture elements, said search area having ((m+1)×

M-1) columns and (L+N-1) rows and including ((m×

M)×

L) candidate blocks, and which are arranged to read out picture element data according to the access instruction of said memory control signal supplied from said main control unit; and

timing adjust means for adjusting, in timing, picture element data read out from said (m+1) memory element portions and supplying said picture element data to said correlation degree operation unit,

said main control unit being arranged to supply said memory control signal such that two accesses are made in said search area memory for one clock cycle,

said timing adjust means being arranged to select two picture element data out of the picture element data read from said (m+1) memory element portions at one access, and to supply, per clock cycle, four picture element data after adjusted in timing.

10. A correlation degree operation apparatus according to claim 9, wherein said timing adjust means comprises:

a first memory selector for selecting and supplying one picture element data out of the picture element data read from the first to mth memory element portions out of said (m+1) memory element portions;

a second memory selector for selecting and supplying one picture element data out of the picture element data read from the second to (m+1)th memory element portions out of said (m+1) memory element portions; and

delay means for delaying, by M clock cycles, said picture element data selected and supplied by said second memory selector, from said picture element data selected and supplied by said first memory selector.

11. A correlation degree operation apparatus according to claim 8, wherein said correlation degree operation unit comprises N line operation units each comprising:

two first selectors each for selecting and supplying one picture element data out of said four picture element data supplied from said search area memory, said two selected and supplied picture element data being different from each other; and

M picture element operation portions each of which holds each of the picture element data of a reference picture block, which selects one picture element data out of said two picture element data selectively supplied by said two first selectors and which operates an evaluation value of correlation between said selected one picture element data and said held picture element data,

said evaluation values of correlation operated by said picture element operation portions being accumulated by one another to obtain a degree of correlation between said reference picture block having (M×

N) picture elements and each of said candidate blocks.

12. A correlation degree operation apparatus according to claim 11, wherein each of said picture element operation portions comprises:

a reference picture storage unit for holding the entered picture element data of a reference picture block;

a second selector for selecting one picture element data out of said two picture element data respectively selected and supplied by said two first selectors;

an operation unit for operating an evaluation value of correlation between said picture element data held by said reference picture storage unit and said picture element data selected by said second selector;

an adder for adding said evaluation value operated by said operation unit to the accumulated evaluation value supplied from the previous-stage picture element operation portion; and

a register for once storing the output data of said adder and supplying said output data to the subsequent-stage picture element operation portion.

13. A correlation degree operation apparatus according to claim 11, wherein in each of said line operation units, said M picture element operation portions are symmetrically disposed in two lines at both sides of buses for transferring the picture element data selected and supplied by said first selectors.

14. A correlation degree operation apparatus according to claim 13, wherein an evaluation value is transferred, as successively accumulated by the previous-stage evaluation value, in the order (i) from, in the one line of picture element operation portions, the picture element operation portion disposed at the end at the side where said first selectors are disposed, toward the picture element operation portion disposed at the end at the side where said first selectors are not disposed, (ii) then, to the other-line picture element operation portion disposed at the end at the side where said first selectors are not disposed, (iii) then, in the other line of picture element operation portions, from said picture element operation portion disposed at the end at the side where said first selectors are not disposed, toward the picture element operation portion disposed at the end at the side where said first selectors are disposed.

15. A correlation degree operation apparatus according to claim 8, wherein said correlation degree operation unit comprises (M×

N) picture element operation portions each for holding each of the picture element data of a reference picture block, selecting one picture element data out of the four picture element data supplied from said search area memory, and operating an evaluation value of correlation between said selected one picture element data and said held picture element data,

said evaluation values operated by said picture element operation portions being accumulated by one another to obtain a degree of correlation between said reference picture block having (M×

N) picture elements and each of said candidate blocks.

16. A correlation degree operation apparatus according to claim 15, wherein each of said picture element operation portions comprises:

a reference picture storage unit for holding the entered picture element data of a reference picture block;

a selector for selecting one picture element data out of said four picture element data supplied from said search area memory;

an operation unit for operating an evaluation value of correlation between said picture element data held by said reference picture storage unit and said picture element data selected by said selector;

an adder for adding said evaluation value operated by said operation unit to the accumulated evaluation value supplied from the previous-stage picture element operation portion; and

a register for once storing the output data of said adder and supplying said output data to the subsequent-stage picture element operation portion.

17. A correlation degree operation apparatus according to claim 8, wherein

said correlation degree operation unit comprises N line operation units for holding M picture element data on each row of a reference picture block and operating evaluation values of correlation between said held picture element data and said picture element data supplied from said search area memory, and

said operation control unit comprises N line control units for respectively controlling said N line operation units.

18. A correlation degree operation apparatus according to claim 17, wherein said N line control units are cascade-connected to one another and said operation control signal entered into said operation control unit is transferred successively to said N line control units.

19. A correlation degree operation apparatus according to claim 18, wherein:

each of said line operation units comprises,

two first selectors each for selecting and supplying one picture element data out of said four picture element data supplied from said search area memory, said two selected and supplied picture element data being different from each other, and

M picture element operation portions each of which holds each of the picture element data of a reference picture block, which selects one picture element data out of said two picture element data selectively supplied by said two first selectors and which operates an evaluation value of correlation between said selected one picture element data and said held picture element data; and

each of said line control units comprises, a first control portion for controlling said two first selectors, and

M second control portions for respectively controlling said M picture element operation portions.

20. A correlation degree operation apparatus according to claim 19, wherein said M second control portions in each of said line control units, are cascade-connected to one another, and an operation control signal entered into each of said line control units is transferred successively to said M second control portions and then supplied after M clock cycles from the entry of said operation control signal.

21. A correlation degree operation apparatus for operating, according to a block matching method, a degree of correlation between a reference picture block having (M×

N) picture elements and each of a plurality of candidate blocks (in which each of M and N is a natural number), comprising;

a search area memory for storing the picture element data of a search area including candidate blocks subjected to an operation of correlation degree;

a correlation degree operation unit for holding the picture element data of a reference picture block having (M×

N) picture elements and executing, by a pipeline process, an operation of a degree of correlation between said reference picture block and each of said candidate blocks, with the use of said held picture element data of said reference picture block and the picture element data of each candidate block supplied from said search area memory; and

an operation control unit for controlling said correlation degree operation unit according to an operation control signal entered into said operation control unit,

said correlation degree operation unit comprising N line operation units each having M picture element operation portions for respectively holding the picture element data of said reference picture block and operating evaluation values of correlation between said held picture element data and picture element data supplied from said search area memory, and

said operation control unit comprising N line control units for respectively controlling said N line operation units.

22. A correlation degree operation apparatus according to claim 21, wherein said N line control units are cascade-connected to one another and said operation control signal entered into said operation control unit is transferred successively to said N line control units.

23. A correlation degree operation apparatus according to claim 22, wherein each of said line control units comprises M control portions for respectively controlling said M picture element operation portions.

24. A correlation degree operation apparatus according to claim 23, wherein said M control portions in each of said line control units, are cascade-connected to one another, and an operation control signal entered into each of said line control units is transferred successively to said M control portions and then supplied after M clock cycles from the entry of said operation control signal.

25. A parallel correlation degree operation apparatus operating at the same clock cycle comprising:

a first correlation degree operation apparatus for operating a degree of correlation between a first reference picture block and a candidate block;

a second correlation degree operation apparatus for operating a degree of correlation between a second reference picture block and a candidate block; and

a correlation degree adder for adding said degree of correlation operated by said first correlation degree operation apparatus to said degree of correlation operated by said second correlation degree operation apparatus,

wherein each of said first and second correlation degree operation apparatus is a correlation degree operation apparatus for operating, according to a block matching method, a degree of correlation between a reference picture block having (M×

N) picture elements and each of ((m×

M)×

L) candidate blocks (in which each of M, N, L, m is a natural number, L is not less than N and m is not less than

     2), and

said each of said first and second correlation degree operation apparatus comprises;

a search area memory for storing the picture element data of a search area including ((m×

M)×

L) candidate blocks; and

a correlation degree operation unit for holding the picture element data of a reference picture block having (M×

N) picture elements and executing an operation of a degree of correlation between said reference picture block and each of said candidate blocks, with the use of said held picture element data of said reference picture block and the picture element data of each candidate block supplied from said search area memory, said operation being executed by a pipeline process for each candidate block group composed of (M×

L) candidate blocks,

said search area memory having the function of supplying, to said correlation degree operation unit at the same clock cycle, both the picture element data required for an operation of correlation degree for one candidate block group and the picture element data required for an operation of correlation degree for another candidate block group to be executed subsequently to said first-mentioned operation for said one candidate block group,

said correlation degree operation unit being arranged to continuously execute the operations for said candidate block groups.

26. A correlation degree operation method of operating, according to a block matching method a degree of correlation between a reference picture block having (M×

N) picture elements and each of ((m×

M)×

L) candidate blocks (in which each of M, N, L, m is a natural number, L is not less than N and m is not less than

     2), comprising;

dividing ((m×

M)×

L) candidate blocks into m candidate block groups each composed of (M×

L) candidate blocks, said m candidate block groups are continuously arranged to overlap one another in one of a horizontal direction and a vertical direction;

executing, on each candidate block group, an operation of repeating, L times in the other direction than the direction in which said m candidate block groups overlap, a step of applying a block-matching process to a reference picture block with respect to each of M candidate blocks arranged to continuously overlap one another in said one direction,

wherein there are used, at the same clock cycle, both the picture element data required for an operation of correlation degree for one candidate block group and the picture element data required for an operation of correlation degree for another candidate block group to be executed subsequently to said first-mentioned operation for said one candidate block group.