USRE42853EExpiredUtilityPatentIndex 49
Method and apparatus for coding an image object of arbitrary shape
Assignee: UNIV HONG KONG SCIENCE & TECHNPriority: Aug 14, 2000Filed: Nov 20, 2006Granted: Oct 18, 2011
Est. expiryAug 14, 2020(expired)· nominal 20-yr term from priority
H04N 19/649H04N 19/20H04N 19/61
49
PatentIndex Score
0
Cited by
28
References
38
Claims
Abstract
It is known to represent a square block of an image which has a maximum horizontal or vertical extension N as N vectors each representing one column or row, and encode it using an N×N discrete cosine transform matrix. We introduce a technique which transforms an input vector, or array, representing a portion of an arbitrarily-shaped object block in which the maximum horizontal or vertical extension is at most N, by adding to it additional padding elements, to produce a vector or array which can be encoded using an N×N discrete cosine transform. The padding maximises the number of transformed elements which are zero. We propose encoding arbitrarily-shaped objects based on this padding technique.
Claims
exact text as granted — not AI-modified1. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one pixel of said image object and at least one further pixel, the method including for each boundary block:
(i) deriving K object elements which are respectively the pixel values of K pixels of the image object within the boundary block spaced along a first direction;
(ii) employing said K object elements to obtain (N−K) padding elements;
(iii) deriving a padded vector consisting of said K object elements and said (N−K) padding elements,; and
(iv) transforming the padded vector using a predetermined N×N transform matrix to produce a transformed vector,
wherein said transformed vector has (N−K) elements in (N−K) predetermined transform locations which are zero.
2. A method according to claim 1 in which said transform matrix produces a discrete Fourier transform, and said (N−K) transform locations are the locations of the transformed vector which represent the (N−K) components of highest spatial frequency in the first direction.
3. A method according to claim 1 in which said (N−K) padding elements are at (N−K) respective padding locations in said padded vector, said locations being selected based on the value of K.
4. A method according to claim 3 in which said (N−K) padding locations are chosen to minimise the value of the L 2 -norm of a K×K matrix K which relates a vector u consisting of the K pixel values of the input object and a vector U consisting of the K non-zero elements of the transformed vector according to the expression U=K.u.
5. A method according to claim 3 in which said (N−K) padding locations are chosen in dependence upon the determinant of a (N−K)×(N−K) matrix C 11 defined by
[
[
C
11
=
[
c
(
β
^
0
,
β
0
)
K
c
(
β
^
0
,
β
N
-
1
-
K
)
M
O
M
c
(
β
^
N
-
1
-
k
,
β
0
)
K
c
(
β
^
N
-
1
-
K
,
β
N
-
1
K
)
]
]
]
C
11
=
[
c
(
β
^
0
,
β
0
)
…
c
(
β
^
0
,
β
N
-
1
-
K
)
⋮
⋱
⋮
c
(
β
^
N
-
1
-
k
,
β
0
)
…
c
(
β
^
N
-
1
-
K
,
β
N
-
1
-
K
)
]
where the padding locations are at positions β 0 , . . . , β N−1−K , where 0≦β 0 , . . . , β N−1−K ≦N−1,
[
[
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
]
]
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
c p √{square root over (½)} if p=0 and c p =1 otherwise.
6. A method according to claim 3 in which said (N−K) padding locations are chosen in dependence upon the condition number of a (N−K)×(N−K) matrix C 11 defined by
[
[
C
11
=
[
c
(
β
^
0
,
β
0
)
K
c
(
β
^
0
,
β
N
-
1
-
K
)
M
O
M
c
(
β
^
N
-
1
-
k
,
β
0
)
K
c
(
β
^
N
-
1
-
K
,
β
N
-
1
K
)
]
]
]
C
11
=
[
c
(
β
^
0
,
β
0
)
…
c
(
β
^
0
,
β
N
-
1
-
K
)
⋮
⋱
⋮
c
(
β
^
N
-
1
-
k
,
β
0
)
…
c
(
β
^
N
-
1
-
K
,
β
N
-
1
-
K
)
]
where the padding locations are at positions β 0 , . . . , β N−1−K , where 0≦β 0 , . . . , β N−1−K ≦N−1,
[
[
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
]
]
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
c p =√{square root over (1/2)} if p=0 and c p =1 otherwise.
7. A method according to claim 3 in which said (N−K) padding locations are chosen in dependence upon ratio of the maximum and minimum eigenvalues of a (N−k)×(N−k) matrix C 11 defined by
[
[
C
11
=
[
c
(
β
^
0
,
β
0
)
K
c
(
β
^
0
,
β
N
-
1
-
K
)
M
O
M
c
(
β
^
N
-
1
-
k
,
β
0
)
K
c
(
β
^
N
-
1
-
K
,
β
N
-
1
K
)
]
]
]
C
11
=
[
c
(
β
^
0
,
β
0
)
…
c
(
β
^
0
,
β
N
-
1
-
K
)
⋮
⋱
⋮
c
(
β
^
N
-
1
-
k
,
β
0
)
…
c
(
β
^
N
-
1
-
K
,
β
N
-
1
-
K
)
]
where the padding locations are at positions β 0 , . . . , β N−1−K , where 0≦β 0 , . . . , β N−1−k ≦N−1,
[
[
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
]
]
c
(
p
,
q
)
=
2
N
c
p
cos
p
(
2
q
+
1
)
π
2
N
c p =√{square root over (1/2)} is p=0 and c p =1 otherwise.
8. A method according to claim 1 in which the transformed vector is transmitted together with information identifying the locations of the pixels of the image object within the boundary block.
9. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 1 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one pixel of said image object and at least one further pixel, the method including for each boundary block:
(i) deriving K object elements which are respectively the pixel values of K pixels of the image object within the boundary block spaced along a first direction;
(ii) employing said K object elements to obtain (N−K) padding elements;
(iii) deriving a padded vector consisting of said K object elements and said (N−K) padding elements; and
(iv) transforming the padded vector using a predetermined N×N transform matrix to produce a transformed vector;
wherein said transformed vector has (N−K) elements in (N−K) predetermined transform locations which are zero.
10. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
i) determining a plurality of sets j=1, . . . , N of image pixels, the K j image pixels of each set being spaced apart in a first direction and the sets of image pixels being spaced apart in a second direction orthogonal to said first direction;
(ii) for each of the sets, employing the K j values of the image pixels and a predetermined N×N transform matrix to produce a transformed vector representing spatial frequencies in the first direction, wherein each said transformed vector has (N−K j ) elements in (N−K j ) predetermined transform locations which are zero; and
(iii) employing the elements plurality of transformed vectors and a predetermined N×N transform matrix which generates a transform in the second direction, to produce an array of transformed values having a number of non-zero elements equal to the number of image pixels in the boundary block.
11. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 10 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) determining a plurality of sets j=1, . . . , N of image pixels, the K j image pixels of each set being spaced apart in a first direction and the sets of image pixels being spaced apart in a second direction orthogonal to said first direction;
(ii) for each of the sets, employing the K j values of the image pixels and a predetermined N×N transform matrix to produce a transformed vector representing spatial frequencies in the first direction, wherein each said transformed vector has (N−K j ) elements in (N−K j ) predetermined transform locations which are zero; and
(iii) employing the elements plurality of transformed vectors and a predetermined N×N transform matrix which generates a transform in the second direction, to produce an array of transformed values having a number of non-zero elements equal to the number of image pixels in the boundary block.
12. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) padding the boundary block in a first direction to form a first padded block, carrying out a spatial frequency transform of the first padded block in the first direction using a first predetermined N×N transform matrix to derive a first transformed block, padding the first transformed block in a second direction orthogonal to the first direction to derive a second padded block, and carrying out a spatial frequency transform of the second padded block in the second direction using a second predetermined N×N transform matrix to derive a second transformed block;
ii) padding the first padded block in the second direction to derive a third padded block, carrying out a spatial frequency transform of the third padded block in the first direction using the first predetermined N×N transform matrix to derive a third transformed block, and carrying out a spatial frequency transform of the third transformed block in the second direction using the second predetermined N×N transform matrix to derive a fourth transformed block; and
(iii) selecting one of the second and fourth transformed blocks according to a predetermined criterion.
13. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 12 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) padding the boundary block in a first direction to form a first padded block, carrying out a spatial frequency transform of the first padded block in the first direction using a first predetermined N×N transform matrix to derive a first transformed block, padding the first transformed block in a second direction orthogonal to the first direction to derive a second padded block, and carrying out a spatial frequency transform of the second padded block in the second direction using a second predetermined N×N transform matrix to derive a second transformed block;
(ii) padding the first padded block in the second direction to derive a third padded block, carrying out a spatial frequency transform of the third padded block in the first direction using the first predetermined N×N transform matrix to derive a third transformed block, and carrying out a spatial frequency transform of the third transformed block in the second direction using the second predetermined N×N transform matrix to derive a fourth transformed block; and
(iii) selecting one of the second and fourth transformed blocks according to a predetermined criterion.
14. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array having rows in a first direction and columns in a second direction orthogonal to the first direction, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) padding the rows of the boundary block, and subsequently using the padded image and two predetermined transform matrices which respectively represent spatial frequency transforms in the first and second directions, to derive a first array;
(ii) padding the columns of the boundary block, and subsequently using the padded image and said two predetermined transform matrices to derive a second array; and
(iii) selecting one of the first and second arrays according to a predetermined criterion.
15. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 14 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array having rows in a first direction and columns in a second direction orthogonal to the first direction, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) padding the rows of the boundary block, and subsequently using the padded image and two predetermined transform matrices which respectively represent spatial frequency transforms in the first and second directions, to derive a first array;
(ii) padding the columns of the boundary block, and subsequently using the padded image and said two predetermined transform matrices to derive a second array; and
(iii) selecting one of the first and second arrays according to a predetermined criterion.
16. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) determining N sets j=1, . . . , N of image pixels, the K j image pixels of each i-th set being spaced apart in a first direction and the sets of image pixels being spaced apart in a second direction orthogonal to said first direction;
(ii) for each set of image pixels, deriving a respective N-vector consisting of K j object elements which are respectively the values of the K j image pixels, and (N−K j ) padding elements, and
(iii) transforming each said padded vector using a predetermined N×N Fourier transform matrix which produces a spatial frequency transform in said first direction,
(iv) deriving N sets, k=1, . . . , N of transformed values, the elements of each k-th set of transformed values being the non-zero k-th elements of the transformed vectors;
(v) for any said set of transformed values having fewer than N values, increasing the number of elements to N by adding additional padding elements; and
(vi) transforming each set of transformed values using a second predetermined N×N Fourier transform matrix which produces a spatial frequency transform in the second direction normal to derive a respective second transformed vector;
wherein the total number of non-zero values in the second transformed vectors is equal to the number of image pixels in said boundary block.
17. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 16 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) determining N sets j=1, . . . , N of image pixels, the K j image pixels of each i-th set being spaced apart in a first direction and the sets of image pixels being spaced apart in a second direction orthogonal to said first direction;
(ii) for each set of image pixels, deriving a respective N-vector consisting of K j object elements which are respectively the values of the K j image pixels, and (N−K j ) padding elements, and
(iii) transforming each said padded vector using a predetermined N×N Fourier transform matrix which produces a spatial frequency transform in said first direction,
(iv) deriving N sets, k=1, . . . , N of transformed values, the elements of each k-th set of transformed values being the non-zero k-th elements of the transformed vectors;
(v) for any said set of transformed values having fewer than N values, increasing the number of elements to N by adding additional padding elements; and
(vi) transforming each set of transformed values using a second predetermined N×N Fourier transform matrix which produces a spatial frequency transform in the second direction normal to derive a respective second transformed vector;
wherein the total number of non-zero values in the second transformed vectors is equal to the number of image pixels in said boundary block.
18. A method of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) determining N first sets j=1, . . . , N of values, each first set consisting of K j image values of K j image pixels of the boundary block spaced apart in a first direction;
(ii) for each first set of values, in the case that K j is greater than zero, deriving an N-vector consisting of the K j image values and (N−K j ) padding elements,
(iii) deriving N second sets k=1, . . . , N of values, the elements of each k-th second set of values being the non-zero k-th elements of said N-vectors;
(iv) for any said second set having fewer than N values, increasing the number of elements to N by adding additional padding elements;
(v) forming an N×N array of said second sets of values;
(vi) transforming said array using a first predetermined N×N Fourier transform matrix which produces a spatial frequency transform in said first direction; and
(vii) transforming said array using a second predetermined N×N Fourier transform matrix which produces a spatial frequency transform in a second direction normal to said first direction.
19. A non-transitory computer-readable medium storing computer-executable programming for causing instructions that, if executed on a processor, cause the processor to perform a method according to claim 18 of encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one image pixel which is part of said image object and at least one further pixel, the method including for each boundary block:
(i) determining N first sets j=1, . . . , N of values, each first set consisting of K j image values of K j image pixels of the boundary block spaced apart in a first direction;
(ii) for each first set of values, in the case that K j is greater than zero, deriving an N-vector consisting of the K j image values and (N−K j ) padding elements,
(iii) deriving N second sets k=1, . . . , N of values, the elements of each k-th second set of values being the non-zero k-th elements of said N-vectors;
(iv) for any said second set having fewer than N values, increasing the number of elements to N by adding additional padding elements;
(v) forming an N×N array of said second sets of values;
(vi) transforming said array using a first predetermined N×N Fourier transform matrix which produces a spatial frequency transform in said first direction; and
(vii) transforming said array using a second predetermined N×N Fourier transform matrix which produces a spatial frequency transform in a second direction normal to said first direction.
20. An apparatus for encoding an image object consisting of pixel values at each of a plurality of pixel locations in a pixel array, the array being divided into a plurality of blocks of size N×N, at least one of said plurality of blocks being a boundary block including both at least one pixel of said image object and at least one further pixel, the apparatus comprising:
(i) derivation means which, for each boundary block, derive K object elements which are respectively the pixel values of K pixels of the image object within the boundary block spaced along a first direction;
(ii) padding means which employ said K object elements to obtain (N−K) padding elements, and derive a padded vector consisting of said K object elements and said (N−K) padding elements, and
(iii) transform means which transform the padded vector using a predetermined N×N transform matrix to produce a transformed vector,
wherein said transformed vector has (N−K) elements in (N−K) predetermined transform locations which are zero.
21. An image encoder to encode image data, the image coder comprising:
a first circuit to provide at least one of a vertical padding and a horizontal padding of image data to provide a padded image vector that will produce one or more zero-value transform locations after a transform operation during image compression; and a second circuit coupled with the first circuit, the second circuit to perform a transform on the padded image vector to provide compressed image data as output data of the image encoder, wherein the compressed image data comprises one or more transform locations including a zero value.
22. The image encoder of claim 21, further comprising:
a quantizer coupled with the second circuit and includes a first table, wherein the quantized is configured to receive the transformed padded image vector from said second circuit, and to provide, in response, quantized output data, using data stored in the first table; and an entropy encoder coupled to quantizer and includes a second table, wherein the entropy encoder is configured to receive the quantized output data from the quantizer, and to provide in response, the compressed image data as output data of said image encoder, using data stored in the second table.
23. The image encoder of claim 21, wherein the image data comprises (N−K) transform locations in an N×N array which represent high spatial frequencies.
24. An article of manufacture comprising a non-transitory computer readable storage medium having instructions stored therein, that if the instructions are executed by a processor, the instructions cause the processor to:
pad image data to provide a padded image vector that will produce one or more zero-value transform locations after a transform operation during image compression; and transform the padded image vector to provide compressed image data, wherein the compressed image data comprises one or more transform locations which include a zero value.
25. The article of manufacture of claim 24, wherein the instructions, if executed, further cause the processor to:
quantize the transformed padded image vector to provide quantized output data; and entropy encode the quantized output data to provide the compressed image data.
26. The article of manufacture of claim 24, wherein the image data comprises (N−K) transform locations in an N×N array that represent high spatial frequencies.
27. An apparatus, comprising:
means for padding image data to provide a padded image vector that will produce one or more zero-value transform locations after a transform operation during image compression; and means for transforming the padded image vector to provide compressed image data; wherein the compressed image data comprises one or more transform locations including a zero value.
28. The apparatus of claim 27, further comprising:
means for quantizing the transformed padded image vector to provide quantized output data; and means for entropy encoding the quantized output data to provide the compressed image data.
29. The apparatus of claim 27, wherein the image data comprises (N−K) transform locations in an N×N array.
30. An image encoder to encode image data, the image encoder comprising:
a first circuit to provide padding of image data in a first direction to provide one or more first-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; a second circuit coupled with the first circuit, the second circuit to provide a padding of image data based on the one or more first-direction padded vectors in a second direction orthogonal to the first direction to provide one or more second-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; and a third circuit coupled with the second circuit, the third circuit to perform a transform on the one or more second-direction padded vectors to provide transformed image data comprising one or more zero-value transform locations.
31. The image encoder of claim 30, wherein the second circuit is configured to provide padding of the one or more first-direction padded vectors in a pixel domain.
32. The image encoder of claim 30, further comprising a fourth circuit coupled with the first circuit, the fourth circuit to perform a transform on the one or more first-direction padded vectors to provide one or more transform image data; and
wherein:
the second circuit is coupled to the first circuit through the fourth circuit; and,
the second circuit is configured to provide padding to the transform image data output by the fourth circuit in a transform domain.
33. An article of manufacture comprising a non-transitory computer readable storage medium having instructions stored therein, configured to cause an apparatus, in response to execution of the instructions by the apparatus, to perform operations comprising:
padding image data in a first direction to provide one or more first-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; padding data based on the one or more first-direction padded vectors in a second direction orthogonal to the first direction to provide one or more second-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; and transforming the one or more second-direction padded vectors to provide transformed image data comprising one or more zero-value transform locations.
34. The article of manufacture of claim 33, wherein padding data based on the one or more first-direction padded vectors in a second direction comprises padding the first-direction padded vectors in the second direction in a pixel domain.
35. The article of manufacture of claim 33, wherein the operations further comprises transforming the one or more first-direction padded vectors to provide first-direction transformed image data; and padding the first direction transformed image data in the second direction in a transform domain.
36. An apparatus, comprising:
means for padding image data in a first direction to provide one or more first-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; means for padding data based on the one or more first-direction padded vectors in a second direction to provide one or more second-direction padded vectors that will produce one or more zero-value transform locations after a transform operation; and means for transforming the one or more second-direction padded vectors to provide transformed image data comprising one or more zero-value transform locations.
37. The apparatus of claim 36, wherein the means for padding data based on the one or more first-direction padded vectors in a second direction comprises means for padding the one or more first-direction padded vectors in a pixel domain.
38. The apparatus of claim 36, further comprising means for transforming the one or more first-direction padded vectors to provide first-direction transformed image data; and
wherein the means for padding data based on the one or more first-direction padded vectors in a second direction comprises means for padding the first-direction transformed image data in a transform domain.Cited by (0)
No later patents cite this yet.
References (0)
No backward citations on record.