Granted Patent B2

US 8,111,749 · App. 12/468,374 · Granted Feb 7, 2012

Abstract

Claims (265)

1. A method for encoding or decoding an image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into vertical bands of blocks having said height of H blocks, wherein said method comprises the following steps:

obtaining N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 0≦i≦N−1 and

∑

i

=

0

N

-

1

⁢

K

i

=

W

;

for every level of coprocessors s, with 0≦s≦S−1, assigning M s coprocessors CP s,j to M s contiguous bands BCP s , having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

W

;

managing message sending to the processors and coprocessors according to the following rules, BP i,r being a line of row r of band BP i , and BCP s, j, r being a line of row r of band BCP s, j , with 0≦r≦H−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a line BP i,r , sending a first start message authorizing the processor P i+i to process line BP i+i, r ;

when a coprocessor CP s,j , with j≧0 and j<M s −1, has finished processing a line BCP s, j, r , sending a second start message authorizing the coprocessor CP s,j+1 to process line BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of line BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of line BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of line BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of line BCP s, j+1, r−1 has already been processed;

when the first block of line BCP s, j, r belongs to line BP i, r and the last block of line BCP s, j, r belongs to line BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of line BCP s, j, r is the last block of line BP i, r ,

then when the coprocessor CP s, j has finished processing line BCP s, j, r , sending a third start message authorizing the P i to process line BP i, r .

2. A method for encoding or decoding an image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into horizontal bands of blocks having said width of W blocks, wherein said method comprises the following steps:

obtaining N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 0≦i—N−1 and

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

for every level of coprocessors s, with 0≦s≦S−1, assigning M s coprocessors CP s,j to M s contiguous bands BCP s,j having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

managing message sending to the processors and coprocessors according to the following rules, BP i,r being a column of row r of band BP i , and BCP s, j, r being a column of row r of band BCP s, j , with 0≦r≦W−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a column BP i,r , sending a first start message authorizing the processor P i+1 to process column BP i+i, r ;

when a coprocessor CP s,j , with j≧0 and j<M s −1, has finished processing a column BCP s, j, r , sending a second start message authorizing the CP s, j+1 to process column BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of column BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of column BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of column BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of column BCP s, j+1, r−1 has already been processed;

when the first block of column BCP s, j r belongs to column BP i, r and the last block of column BCP s, j, r belongs to column BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of column BCP s, j, r is the last block of column BP i, r ,

then when the coprocessor CP s, j has finished processing column BCP s, j, r , sending a third start message authorizing the P i to process column BP i, r .

3. A method as claimed in claim 1 , wherein the encoding and decoding is compliant with a standard belonging to the group comprising: H.263, H.263+, H264 and MPEG-4 Video.

4. A non-transitory computer-readable storage medium storing a computer program comprising a set of instructions executable by a computer in order to implement a method for encoding or decoding an image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into vertical bands of blocks having said height of H blocks, wherein said method comprises the following steps:

obtaining N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 0≦i≦N−1 and

∑

i

=

0

N

-

1

⁢

K

i

=

W

;

for every level of coprocessors s, with 0≦s≦S−1, assigning M s coprocessors CP s,j to M s contiguous bands BCP s,j having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

W

;

managing message sending to the processors and coprocessors according to the following rules, BP i,r being a line of row r of band BP i , and BCP s, j, r being a line of row r of band BCP s, j , with 0≦r≦H−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a line BP i,r , sending a first start message authorizing the processor P i+1 to process line BP i+1, r ;

when a coprocessor CP s,j , with j≧0 and j<M s −1, has finished processing a line BCP s, j, r , sending a second start message authorizing the coprocessor CP s, j+1 to process line BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of line BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of line BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of line BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of line BCP s, j+1, r−1 has already been processed;

when the first block of line BCP s, j, r belongs to line BP i, r and the last block of line BCP s, j, r belongs to line BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of line BCP s, j, r is the last block of line BP i,r ,

then when the coprocessor CP s, j has finished processing line BCP s, j, r , sending a third start message authorizing the P i to process line BP i, r .

5. A non-transitory computer-readable storage medium storing a computer program comprising a set of instructions executable by a computer in order to implement a method for encoding or decoding an image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into horizontal bands of blocks having said width of W blocks, wherein said method comprises the following steps:

obtaining N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 01≦i≦N−1 and

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

for every level of coprocessors s, with 0≦s≦S−1, assigning M s coprocessors CP s,j to M s contiguous bands BCP s , having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

managing message sending to the processors and coprocessors according to the following rules, BP i,r being a column of row r of band BP i , and BCP s, j, r being a column of row r of band BCP s, j , with 0≦r≦W−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a column BP i,r , sending a first start message authorizing the processor P i+1 to process column BP i+1, r ;

when a coprocessor CP s,j , with j≧0 and j<M s −1, has finished processing a column BCP s, j, r , sending a second start message authorizing the CP s, j+1 to process column BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of column BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of column BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of column BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of column BCP s, j+1, r−1 has already been processed;

when the first block of column BCP s, j, r belongs to column BP i, r and the last block of column BCP s, j, r belongs to column BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of column BCP s, j, r is the last block of column BP i, r ,

then when the coprocessor CP s, j has finished processing column BCP s, j, r , sending a third start message authorizing the P i to process column BP i, r .

6. An image encoding/decoding device, the image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into vertical bands of blocks, wherein said device comprises:

N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

means for assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 0≦i≦N−1 and

∑

i

=

0

N

-

1

⁢

K

i

=

W

;

for every level of coprocessors s, with 0≦s≦S−1, means for assigning M s coprocessors CP s,j to M s contiguous bands BCP s,j having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

W

;

means for managing message sending to the processors and coprocessors according to the following rules, BP i,r being a line of row r of band BP i , and BCP s, j, r being a line of row r of band BCP s, j , with 0≦r≦H−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a line BP i,r , sending a first start message authorizing the processor P i+1 to process line BP i+1, r ;

when a coprocessor CP s, j , with j≧0 and j<M s −1, has finished processing a line BCP s, j, r , sending a second start message authorizing the coprocessor CP s, j+1 to process line BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of line BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of line BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of line BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of line BCP s, j+1, r−1 has already been processed;

when the first block of line BCP s, j, r belongs to line BP i, r and the last block of line BCP s, j, r belongs to line BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of line BCP s, j, r is the last block of line BP i, r ,

then when the coprocessor CP s, j has finished processing line BCP s, j, r , sending a third start message authorizing the P i to process line BP i, r .

7. An image encoding or decoding device, the image comprising rectangular blocks of pixels, the image having a height of H blocks and a width of W blocks, the image being cut up into horizontal bands of blocks having said width of W blocks, wherein said device comprises:

N processors and M coprocessors, said M coprocessors being distributed over S levels, with N>1, S>0 and M>S;

means for assigning said N processors P i to N contiguous bands BP i having sizes of K i blocks, with 0≦i≦N−1 and

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

for every level of coprocessors s, with 0≦s≦S−1, means for assigning M s coprocessors CP s,j to M s contiguous bands BCP s,j having sizes of Q s,j blocks, with:

∑

j

=

0

M

s

-

1

⁢

Q

s

,

j

=

H

;

means for managing message sending to the processors and coprocessors according to the following rules, BP i,r being a column of row r of band BP i , and BCP s, j, r being a column of row r of band BCP s, j , with 0≦r≦W−1:

when a processor P i , with i≧0 and i<N−1, has finished processing a column BP i,r , sending a first start message authorizing the processor P i+1 to process column BP i+1, r ;

when a coprocessor CP s,j , with j≧0 and j<M s −1, has finished processing a column BCP s, j, r , sending a second start message authorizing the coprocessor CP s, j+1 to process column BCP s, j+1, r ;

when a processor P i , with i≧0 and i<N−1, must process the last block of column BP i, r , with r>0, sending a first verification message to the processor P i+1 so as to verify if the first block of column BP i+1, r−1 has already been processed;

when a coprocessor CP s, j , with j≧0 and j<M s −1, must process the last block of column BCP s, j, r , with r>0, sending a second verification message to the coprocessor CP s, j+1 so as to verify if the first block of column BCP s, j+1, r−1 has already been processed;

when the first block of column BCP s, j, r belongs to column BP i, r and the last block of column BCP s, j, r belongs to column BP i+k, r :

if k is greater than 0, or

if k is equal to 0 and the last block of column BCP s, j, r is the last block of column BP i, r ,

then when the coprocessor CP s, j has finished processing column BCP s, j, r , sending a third start message authorizing the P i to process column BP i, r .

8. A device as claimed in claim 6 , wherein the encoding or decoding is compliant with a standard belonging to the group comprising: H.263, H.263+, H264 and MPEG-4 Video.

9. A device as claimed in claim 7 , wherein the encoding or decoding is compliant with a standard belonging to the group comprising: H.263, H.263+, H264 and MPEG-4 Video.

10. A method as claimed in claim 2 , wherein the encoding and decoding is compliant with a standard belonging to the group comprising: H.263, H.263+, H264 and MPEG-4 Video.

Assignments (10)