Note: Descriptions are shown in the official language in which they were submitted.
CA 02573911 2007-01-12
1
FEATURE BLOCK COMPRESSION/DECOMPRESSION
TECHNICAL FIELD
The present invention relates to compression of blocks of feature vectors rep-
resenting a feature associated with image elements of an image. Such blocks
may represent features that control or influences the appearance of an image
element, such as normals in normal maps or chrominance information in
textures, but may also represent features stored in the image pixels them-
selves, such as color or chrominance information.
BACKGROUND
Texture compression is a technique for reducing bandwidth usage in 3D
graphics. A texture image is stored in compressed form in external memory,
and when a particular pixel in the texture is being accessed during 3D ren-
dering, a block of pixels is sent in compressed form over the bus. This data
is then decompressed on the fly, and used by the 3D graphics pipeline. This
results in bandwidth savings, since each pixel is often stored in as little as
4
bpp (bits per pixel), compared to 24 bpp in uncompressed form. The most
widely adopted texture compression (TC) scheme is known as S3TC or DXTC,
see [1-2].
Normal mapping and bump mapping are similar techniques, which add de-
tail to geometrical objects in an inexpensive way, see [3]. More specifically,
a
texture, called a bump map or normal map, is used at each pixel to perturb
its normal. When computing the shading of a surface. lighting depends on
the surface normal. In this way the surface appears to have a higher amount
of geometrical detail than it actually has. To create models that can be used
in, for example, real-time games, a common approach is to first create an
object with rich geometrical detail. Some polygon simplification algorithm is
then used to reduce the amount of geometry while keeping the general
CA 02573911 2008-01-17
2
shape. The "difference" between the highly detailed geometrical object and
the less detailed object can be computed and baked into a normal map. Us-
ing this normal map on the less detailed object makes for fast rendering of
objects that look geometrically detailed.
Even though normal mapping reduces the complexity, the normal map still
has to be stored. This requires some kind of texture compression technique
for normal maps. A normal map block compression scheme called 3Dc, has
been developed for this purpose, see [4]. One can also use existing DXT
schemes for normal map block compression, see [5]. However, since the DXT
schemes were originally designed for texture images, the results can often be
quite poor.
Another application of interest is high dynamic range (HDR) images. Images
in graphics are usually stored (in uncompressed mode) using 8 bits per color
component, resulting in 24 bpp for RGB. However, such images can only
represent a limited amount of the information present in real scenes, where
luminance values spanning many orders of magnitude are common. To ac-
curately represent the full dynamic range of an HDR image, each color corn-
ponent can be stored as a 16-bit floating-point number. In this case, an un-
compressed HDR RGB image needs 48 bpp. Compression of such images is
clearly desirable. An attempt in this direction is represented by [6].
SUMMARY
An object of the present invention is efficient compression of a block of fea-
ture vectors representing a feature associated with image elements of an
image.
Another object is decoding of a feature vector representing an image feature
from such a compressed image feature block.
CA 02573911 2008-01-17
3
Briefly, the present invention determines the distribution of the feature
vectors
and transforms each point pattern in a given set of point patterns to fit the
de-
termined distribution. The point pattern that after transformation best fits
the
determined distribution is selected for compression of the block. Using this
point pattern, the block of feature vectors is represented by:
an identifier identifying the selected point pattern in the set of point pat-
terns,
parameters representing the transformation associated with the selected
point pattern, and
an index for each feature vector representing the nearest point in the
transformed selected point pattern.
Decoding of a feature vector representing an image feature from such a com-
pressed image feature block involves determining the point pattern identifier
from the compressed image feature block to identify the predefined point pat-
tern, determining an index from the compressed image feature block represent-
ing one of the points in the selected point pattern, determining parameters
from the compressed image feature block representing the transformation of
the determined point pattern and creating the decompressed feature vector by
transforming the point represented by the determined index using the deter-
mined transformation parameters.
In particular, one embodiment of the present invention provides a method of
compressing a block of feature vectors representing a feature associated with
image
elements of an image, including the steps of:
determining the distribution of the feature vectors;
transforming each point pattern in a predetermined set of point patterns to
fit the
determined distribution;
CA 02573911 2008-01-17
3a
selecting a transformed point pattern that best fits the determined
distribution; and
representing the block of feature vectors by:
an identifier identifying the selected point pattern in the set of point
patterns;
parameters representing a transformation associated with the selected point
pattern; and
an index for each feature vector representing the nearest point in the
transformed
selected point pattern.
Another embodiment of the present invention provides a compressor for
compressing a
block of feature vectors representing a feature associated with image
elements, including:
a means for determining the distribution of the feature vectors;
a means for transforming each point pattern in a predetermined set of point
patterns to
fit the determined distribution;
a selector for selecting a transformed point pattern that best fits the
determined
distribution; and
an encoder for representing the block of feature vectors by:
an identifier identifying the selected point pattern in the set of point
patterns;
parameters representing the transformation associated with the selected point
pattern; and
an index for each feature vector representing the nearest point in the
transformed
selected point pattern.
Another embodiment of the present invention provides a method of decoding a
feature
vector representing an image feature from a compressed image feature block,
including
the steps of:
determining a point pattern identifier from the compressed image feature block
to
identify a predefined point pattern;
determining an index from the compressed image feature block representing one
of the
points in the selected point pattern;
determining parameters from the compressed image feature block representing a
transformation of the determined point pattern; and
CA 02573911 2008-01-17
3b
creating the feature vector by transforming the point represented by the
determined
index using the determined parameters.
Yet another embodiment of the present invention provides a decoder for
decoding a
feature vector representing an image feature from a compressed image feature
block,
including:
a means for determining a point pattern identifier from the compressed image
feature
block to identify a predefined point pattern;
an index selector for determining an index from the compressed image feature
block
representing one of the points in the selected point pattern;
a means for determining parameters from the compressed image feature block
representing a transformation of the determined point pattern; and
a means for creating a feature vector by transforming the point represented by
the
determined index using the determined parameters.
BRIEF DESCRIPTION OF THE DRAWINGS
The invention, together with further objects and advantages thereof, may best
be
understood by making reference to the following description taken together
with the
accompanying drawings, in which:
Fig. 1 is a diagram illustrating a block of feature vectors;
CA 02573911 2007-01-12
6 <
,
4
Fig. 2 is a diagram illustrating the distribution of the feature vectors il-
lustrated in Fig. 1;
Fig. 3 is a coordinate system including the endpoints of the vectors illus-
trated in Fig. 2;
Fig. 4 illustrates a first part of a prior art normal map block compression
method;
Fig. 5 illustrates a second part of the prior art normal map block com-
pression method;
Fig. 6 illustrates the representation of the compressed normal map block
in the prior art normal map block compression method;
Fig. 7 illustrates a set of point patterns suitable for normal map block
compression;
Fig. 8 illustrates one point pattern from Fig. 7 transformed to fit a block
of normals from a normal map;
Fig. 9a-e illustrates the different operations of a point pattern transfor-
mation;
Fig. 10 is a block diagram of an example of a compressor of feature
blocks in accordance with the present invention;
Fig. 11 is a block diagram of an example of a decompressor for decod-
2 0 ing a
feature vector of a feature block that has been compressed in accor-
dance with the present invention;
Fig. 12 illustrates a set of point patterns suitable for chrominance block
compression;
Fig. 13 is a flow chart illustrating the compression method in accordance
with the present invention;
Fig. 14 is a flow chart illustrating the decompression or decoding method
in accordance with the present invention;
Fig. 15 is a diagram illustrating a flip method used in a preferred em-
bodiment of the present invention;
Fig. 16 is a block diagram illustrating an embodiment of the decompres-
sor in accordance with the present invention based on the flip method in Fig.
15;
CA 02573911 2007-01-12
Fig. 17 is a block diagram of the flip control logic of the embodiment of
Fig. 16; and
Fig. 18 is a block diagram illustrating another embodiment of the de-
compressor in accordance with the present invention.
5
DETAILED DESCRIPTION
In the following description elements having the same or similar functions
will be provided with the same reference designations in the drawings.
Fig. 1 is a diagram illustrating a block of feature vectors. The feature
vectors
represent a feature associated with image elements in an image. The feature
may either represent a feature inherent to the image element, such as the
chrominance of image elements (pixels), or a feature controlling or
influencing
the appearance of image elements, such as a normal map block controlling the
brightness of image elements. Thus, the diagram in Fig. 1 represent either fea-
ture vectors of a part of an image or a block of feature vectors which at
least
partially controls the appearance of a part of an image. In Fig 1 the block 10
includes 4x4=16 elements 12, each including a feature vector 14.
Fig. 2 is a diagram illustrating the distribution of the feature vectors in
Fig. 1.
In this figure the connection to the original location of each vector has been
discarded. Only the distribution of the vectors is of interest.
In Fig. 3 the endpoints of the vectors of Fig. 2 have been collected in a
coordi-
nate system. Thus, the original feature vectors are represented by the coordi-
nates of the illustrated points in this coordinate system.
The compression method in accordance with the present invention will be
described with reference to normal map block compression and chrominance
block compression. However, the same principles may also be applied to
blocks of other features, such as projected 3D geometry on a 2D domain,
CA 02573911 2007-01-12
a
6
spherical harmonics coefficients, displacement maps, bidirectional reflec-
tance distribution functions (BRDF). Generally any feature that can be pro-
jected onto or represented as a set of N-dimensional coordinates (N-
dimensional feature vectors) can be approximated by a set of predefined
point patterns in accordance with the present invention.
Now, assume that the points in Fig. 1 represent a part of a normal map. In
this
case the uncompressed map is represented by the points in Fig. 3. Actually the
map should be called a normal map with unit length normals, since the vectors
represented by the points only have two components (x,y) . Since the vectors
are normalized to unity, the z -component may be obtained from the equation:
z = x2 - y2
(1)
This computation can either be done in a pixel shader, or by special purpose
hardware. In the following description the term normal map will be used to
simplify the terminology.
Reference [4] describes a prior art compression method that is especially de-
signed for compression of normal map blocks. The first step in this proce-
dure is to determine the axis aligned boundary of the distribution of the nor-
mals (feature vectors), as illustrated in Fig. 4. This boundary is represented
by the corner points (XMIN Y MIN) and (xMAX)YMAX )= The next step is to
distrib-
ute a grid of quantization points in this bounded region, as illustrated in
Fig.
5. The compression is obtained by representing each normal by the nearest
quantization point.
Fig. 6 illustrates the structure of a compressed normal map block. The first
four fields contain the corner coordinates of the boundary, typically 8 bits
for
each coordinate value, giving a total of 32 bits for the boundary. In Fig. 5
the
grid of quantization points includes only 4 quantization levels in each coor-
dinate direction to avoid cluttering of the figure. However, in practice there
CA 02573911 2007-01-12
-
7
may be 8 uniformly distributed quantization levels in each direction. To
specify a quantization point would thus require 3 index bits for each direc-
tion, which results in a total of 16(3 + 3) = 96 index bits. Thus, the
original
4x4 normal map block is compressed into a total of 128 bits, or 8 bpp.
Instead of using a single grid for quantization of the normals, the present
invention is based on using a set of different point patterns, as illustrated
by
the example in Fig. 7. Preferably at least one point pattern in the set has a
non-uniform point distribution. In accordance with the present invention
these point patterns are transformed to fit the distribution of normals in the
normal map block. The coordinates of the points in the different patterns are
given in Table 1 below.
TABLE 1
Shape pl p2 P3 P4
A (0, 0) (0.3, 0,2) (0.7, -0.2)
(1, 0)
B (0, 0) (0.3, -.2) (0.7, 0.2)
(1, 0)
C (0, 0) (0.5, 0.5) (0.8, 0.2)
(1, 0)
D (0, 0) (0.2, 0.2) (0.5, 0.5)
(1, 0)
E (0, 0) (0.33, 0) (0.67, 0)
(1, 0)
F (0, 0) (0.8, 0.2) (0.8, -0.2)
(1, 0)
G (0, 0) (0.5, 0) (0.5, 0.5)
(1, 0)
H (0, 0) (0.3, 0.6) (0.7, 0.6)
(1, 0)
After the transformation, the point pattern that best fits the normal map
block is selected for quantization of the normals. This is illustrated in Fig.
8,
where point pattern G has been found to have a good fit (after transforma-
2 0 tion) to the distribution of normals. The transformation is
illustrated in Fig.
9a-e. Fig. 9a illustrates the original pattern before transformation. Fig. 9b
illustrates a uniformly scaled version of this pattern. Fig. 9c illustrates a
ro-
tated pattern. Fig. 9d illustrates a displaced or translated pattern. Finally,
CA 02573911 2007-01-12
t
8
Fig. 9e illustrates a transformed point pattern, where the transformation in-
volves a combination of uniform scaling, rotation and translation. Thus, the
composite transformation may be expressed as a linear transformation.
The conceptually simplest method to find the transformation that gives the
best fit between the normals of a normal map block and a transformed point
pattern is to find the transformation that minimizes the sum of the squared
distances between each normal in the map and its closest point in the trans-
formed point pattern in an exhaustive search. This will give the minimum
average quantization error for each point pattern. The pattern giving the
smallest average quantization error is then used for the actual quantization.
If the computational complexity of an exhaustive search algorithm is not ac-
ceptable, there are also sub-optimal search algorithms. One such algorithm
is based on clustering and Procrustes analysis. An example of this approach
will be given below with reference to chrominance compression.
Fig. 10 is a block diagram of a feature block compressor in accordance with
the present invention. A control unit 20 controls a feature block storage 22
to output the feature vectors of a block to a matching unit 24, which is also
controlled by control unit 20. Furthermore, control unit 20 controls a point
pattern storage 26, for example storing the point patterns in Table 1 (and
Fig. 7), to output point patterns to a transformation unit 28. These trans-
formed point patterns are forwarded to matching unit 24. Transformation
unit 28 is controlled by control unit 20 to transform each point pattern with
several different transformations. Matching unit 24 determines the average
quantization error for each transformed point pattern. A selector 30 selects
the best pattern and its corresponding transformation parameters, and an
encoder 32 encodes this information into a compressed data block 34.
The compressed data block 34 is divided into sections:
CA 02573911 2007-01-12
= , Ir
9
One section stores the parameters defining the transformation used to
transform the selected point pattern. A convenient representation is
the endpoints (xM/N)YM/N) and (xmAx,ymAx) of the transformed point
pattern, as illustrated in Fig. 8. At the decompressor or decoder a
point (a, 13) of the selected point pattern may then be transformed to
its correct position with the transformation:
(x\
X MAX - X MIN L6 XmlAr
(2)
Y MAX - Y MIN X MAX - X MIN (WIN )
Another section stores a point pattern identifier corresponding to the
selected point pattern.
Finally, there is an index section with an index representing the near-
est point in the selected transformed point pattern for each feature
vector.
As an example, the endpoints may be represented by 8 bits for each coordi-
nate. Referring to Fig. 7, there are 8 point patterns, which requires 3 bits
for
the point pattern identifier. Finally, there are 4 points in each point
pattern,
which requires 2 bits for each index. In this example this gives a total of
4.8 + 3 +16.2 = 67 bits to represent the original 4x4 block.
Often it is desirable to have a compressed block size that is equal to 2" ,
where N is a positive integer. For example, it may be desirable to represent a
compressed block in 64 bits. In the previous example this can be achieved
by representing the coordinates in 7 bits and using 16 four point patterns
instead of 8. This gives a total of 4.7 + 4 +16.2 = 64 bits.
Fig. 11 is a block diagram of an example of a decompressor for decoding a
feature vector of a feature block that has been compressed in accordance
CA 02573911 2007-01-12
.,
with the present invention. The end point coordinates xmõõx,y,,õ,,yõ,,,x of
compressed feature block 34 are forwarded to a transformer 36 implement-
ing equation (2). The Indices Ii, 12, ..., 116 are forwarded to an index
selector
40. Another input of index selector 40 receives a signal identifying the point
5 in the
4x4 feature block that is to be decoded. Index selector 40 selects the
corresponding index IDX from the possible indices Ii, 12, ..., 116 and for-
wards it to a pattern and point selector 42. The point pattern identifier is
also forwarded to pattern and point selector 40. Together with index IDX this
determines the desired point (a,fl) from the selected point pattern. The
10 point
patterns are stored in a point pattern storage 26. Thus, the set of point
patterns are stored both in the compressor and decompressor and do not
have to be transferred. The selected point (a,fl) is forwarded to transformer
36 and is transformed into the final decoded feature vector (x, y) . In this
way each feature vector of a compressed block may be decoded.
Another feature that may be compressed in accordance with the principles
described above is the chrominance of a block (also denoted a tile) of pixels.
In the prior art the chrominance vectors of such a block have been quantized
to the nearest points on a line with uniformly distributed chrominance
points. However, this approximation fails if the blocks have complex chromi-
nance variations or sharp color edges. Such blocks may be more accurately
quantized if the quantizing point pattern is not restricted to a line with uni-
form point distribution as in [1], but can be selected from a set of different
point patterns in accordance with the present invention.
It has been found that the actual set of suitable point patterns depends on
the application (the feature of interest). Thus, the set of point patterns
illus-
trated in Fig. 7 is not necessarily the optimal set for chrominance. In fact
it
has been found (for the same number of patterns) that a suitable set of point
patterns for compressing chrominance blocks is represented by the set illus-
trated in Fig. 12 and specified in Table 2 below.
CA 02573911 2007-01-12
=
11
TABLE 2
Shape pl p2 P3 p4
A (0, 0) (11/32, 0) (21/32, 0) (1, 0)
= (0, 0) (1/4, 0) (3/4, 0) (1,
0)
= (0, 0) (1/8, 0) (1/4, 0) (1,
0)
= (0, 0) (1/2, 0) (3/4, 1/4) (1,
0)
= (0, 0) (1/2, 0) (1/2, 1/2) (1,
0)
= (0,0) (11/32, 11/32)
(21/32, 11/32) (1, 0)
= (0, 0) (0, 1/2) (1, 1/2) (1,
0)
= (0, 0) (1/4, 1/4) (1/2, 0) (1,
0)
Since the optimal set of point patterns depends on the feature of interest, a
method of determining suitable patterns will now be described with reference
to chrominance compression. The space of possible point patterns is very
large. In order to find a selection of patterns that perform well, the chromi-
nance content in a set of images (for example 500,000 tiles) is analyzed.
First, clustering is performed to reduce the chrominance values of each tile
to four chrominance points. Thereafter, the chrominance points are normal-
ized with respect to scale and rotation to produce a large collection of point
pattern candidates. Finally, the two closest candidates are iteratively merged
until the desired number of point patterns remains (8 in this example). If de-
sired, the selected point patterns may be slightly modified or "symmetrized".
Although described with reference to chrominance blocks, the same method
can also be used for other feature blocks, such as normal map blocks. Fur-
thermore, the procedure is of course not limited to 8 patterns, each includ-
ing 4 points. Both fewer and more patterns/points are possible, depending
on the number of bits to be spent on the compressed blocks.
The compressor in Fig. 10 and the decompressor in Fig. 11 may be used also
for compression and decompression, respectively, of chrominance blocks.
CA 02573911 2007-01-12
.1 e
12
An advantage of the present invention is the offered flexibility. The set of
point patterns may be chosen in such a way that they match the most fre-
quent feature vector distributions. For example, the set of point patterns of
Fig. 7 has been found work very well for normal map block compression,
while the set of point patterns of Fig. 12 has been found work very well for
chrominance blocks.
Fig. 13 is a flow chart illustrating the compression method in accordance with
the present invention. Step 51 determines the distribution of the feature vec-
1 0 tors in the block of interest. Step S2 transforms the different
point patterns to
fit this distribution. Step S3 selects the pattern having the best fit to the
distri-
bution of feature vectors. Step S4 compresses the block by representing it
with
a pattern identifier for the selected pattern, the transformation parameters
used to fit this pattern and indices representing the closest point in the
pattern
for each feature vector in the block.
Fig. 14 is a flow chart illustrating the decompression or decoding method in
accordance with the present invention. Step S5 determines the point pattern
identifier from the received compressed block. Step S6 determines the index
into the point pattern corresponding to the feature vector to be decoded. Step
S7 determines the transformation parameters. In step S8 these parameters are
used to transform the indexed point in the identified point pattern to create
the
decoded feature vector.
In a preferred embodiment for chrominance block compression/decompression
of for HDR images, the original (R, G, B) values are mapped into lumi-
nance/chrominance values (?, Et, U) with the following transformation:
Y = (Uri? + cogG + co,B
(3)
(Y, = (log2 Y, L3, or
Y Y
CA 02573911 2007-01-12
4 4
13
where co, + cog + cob =1, for example, co, = 0.299, cog = 0.587, cob = 0.114.
This
mapping has the property that the chrominance components 0,0 both lie
in the interval [0,1] and that ü +
1. These properties imply that all
chrominance points lie in the lower triangle of the chrominance plane, as
illustrated in Fig. 15. This property may be exploited to implicitly code two
bits of the pattern identifier by deliberately flipping one or both endpoints
of
the determined transformation into the upper triangle, as illustrated by the
ring in Fig. 15. For example, if none of the endpoints are flipped, this may
be
associated with code "00". If one of the endpoints is flipped, this will corre-
spond to code "01" or "10", respectively. Finally, if both endpoints are
flipped, this will correspond to code "11". Thus, by determining whether the
endpoints received at the decoder lie in the lower or upper triangle, two of
the bits of the pattern identifier may be decoded.
Fig. 16 is a block diagram illustrating an embodiment of the decoder in accor-
dance with the present invention based on the flip method in Fig. 15. This em-
bodiment is similar to the embodiment of Fig. 11, the difference being that a
flip control logic 44 has been inserted between compressed feature block 34
and transformer 36. As illustrated in Fig. 16 two bits of the pattern
identifier
are retrieved by flip control logic 44 by testing whether a + .170 > 1 and
+
>1, i.e. whether one or both of the endpoints lie above the lower trian-
gle in Fig. 15. Each of these tests produces one bit of the pattern
identifier.
The third bit is obtained from block 34. A detailed block diagram of the flip
logic is illustrated in Fig. 17. A comparator CO tests whether the first end-
point (u0, U0) lies in the lower triangle of Fig. 15. The output signal tO is
used
as one of the bits of the pattern identifier and controls two multiplexers MO
that select the endpoint unchanged or flipped, depending on the value of to.
The other endpoint (up Ui) is determined in the same way by elements Cl,
M1 and control signal ti.
CA 02573911 2007-01-12
I
14
Since the luminance information has a very large dynamic range, it is prefer-
able to spend as many bits as possible on luminance. For example, if a total
of
128 bits is used per block, the major part of these bits should be reserved
for
luminance coding. Thus, it is desirable to reduce the number of bits reserved
for chrominance as much as possible. The above "flip trick" is one step in
this
direction, since it reduces the number of explicitly required bits by 2 bits,
which are instead implicitly coded in the transformation parameters.
Another method to reduce the number of required bits for chrominance infor-
mation is sub-sampling. According to this method the original chrominance
block is divided into sub-blocks each containing a pixel and its nearest
neighbor. One bit may be reserved for specifying whether each sub-block
should include a horizontal or vertical neighbor (the strategy resulting in
the
least error is chosen). For a 4x4 tile this will reduce the number of required
in-
dices from 16 to 8. In a further embodiment the horizontal/vertical bit may be
omitted and the sub-sampling is always either horizontal or vertical. Other
sub-samplings techniques, such as 4x4, 1x4, etc, are also possible.
A further reduction of the number of bits required for chrominance information
is obtained by observing the definition of the chrominance components (u, u)
in (3). Since co, = 0.299 and cob = 0.114, the reconstructed color will be
more
sensitive to quantization errors in ü than in ü. Thus, less bits may be spent
on U than on D.
Fig. 18 is a block diagram illustrating another embodiment of the decoder in
accordance with the present invention where the three bit reduction ap-
proaches of the preceding paragraphs have been combined. By using the "flip
trick" two pattern identifying bits are obtained from the transformation pa-
rameters. Thus only 1 bit has to be explicitly signaled (assuming 8 patterns
are
used). Two further bits are obtained by using only 7 bits for the U values of
the
endpoints. Finally, by sub-sampling the tile, an extra horizontal/vertical bit
is
used, but this saves 8 indices. This results in only 2 = (8 + 7) +1+1 + 8 2 =
48
CA 02573911 2007-01-12
, a
bits, which leaves 128 -48 = 80 bits for luminance coding in this example. The
luminance bits may be spent as follows: 2=8 bits for the luminance endpoints
and 4 luminance index bits each for the 16 pixels in the image block. During
decoding a sub-block selector 46 associates the current pixel with its current
5 sub-block (horizontal/vertical) depending on the value of a SUB bit. The
deter-
mined sub-block selects the appropriate index in index selector 40.
The problem of matching point patterns to chrominance values will now be dis-
cussed in more detail. A landmark is a specific feature of an object, in our
case
10 represented as 2D coordinates. The idea behind Procrustes analysis, see
[7], is
to compare the shapes of objects, represented as sets of landmarks, by remov-
ing translation, rotation and scaling. The analysis finds the similarity trans-
formations to be applied to one set of landmarks Xi (point pattern
coordinates)
which minimize its Euclidean distance from a second set X2 (chrominance val-
15 ues). Thus, the object is to minimize the functional:
X2 - bX112 - lk v T12
(4)
where b represents (linear) scaling, R represents rotation, VT represents
(trans-
posed) translation and lk represents a unit matrix of order k. The problem of
finding the parameters that minimize this functional has an exact, fast solu-
tion: First, center Xi and X2 by subtracting the average from each coordinate.
The translation v is given as the average of X2 prior to centering. Form the
ma-
trix A = X,TXõ and apply a singular value decomposition A = VSUT . The
transform parameters that minimize the functional above are given by:
R = UVT
btrace (AR)
(5)
=
trace (Xi'. Xi)
In the previous example there are blocks of 4x4 pixels, containing 16 chromi-
nance values, which are sub-sampled by a factor two, so the problem is to fit
a
CA 02573911 2007-01-12
16
pattern with four landmarks to eight chrominance points (7.7i, 77) e [0,112.
To set
up the point correspondences, up to four clusters of the chrominance points
are created using pnn-clustering and the k-means algorithm, see [8].
Clustering
the points is an approximation of the optimal solution to the fitting problem,
but it allows comparison of blocks against point patterns in constant time.
Pro-
crustes analysis needs consistent ordering of the two sets of landmark points.
Therefore, each cluster is linked to a point on the point pattern. With four
landmarks per pattern, the number of unique mappings is 4! = 24, and all
combinations are tested. In order to treat the clusters equally, the points in
the
point pattern may be duplicated so that the number of points is the same in
the point pattern clusters and the chrominance value clusters. Another possi-
bility is to multiply the functional (4) by a diagonal weighting matrix to
account
for the different number of points in the clusters.
To evaluate the quality of a deteimined fit of a point pattern, the error:
E = ((a, - )2 (7, _ 17, )2)
(6)
is determined, where (i10,/70) are points in the original chrominance distri-
2 0 bution and (u, U) are the corresponding quantized points. The summation
is over all points in the tile. The pattern giving the smallest error is
selected
for quantization or compression.
Although the present invention has been described with reference to linear
transformations of the point patterns, it is also feasible to use non-linear
transformations, such as affine or projective transformations. Furthermore,
the dimensionality of the feature vectors may be higher than 2, which in
turn implies higher dimensional point patterns. Examples are: RGB color
data, volume color data for 3D rendering, color data in other color spaces
(YUV, CMYK, HSV), vector fields.
CA 02573911 2007-01-12
17
The functionality of the compressor and decoder of the present invention is
typically implemented in a dedicated graphics processor, but may also be
implemented by a micro processor or micro/signal processor combination
and corresponding software. Another possibility is a application specific in-
tegrated circuit (ASIC). The compression/decompression may also be per-
formed by software on general computing devices.
In the description above the feature of interest is typically stored in blocks
that are external to the actual image, e.g. normal maps and chrominance
textures, but control or influence the appearance of the image. However, the
same principles may also be used directly on image blocks, for example on
chrominance information stored in the image or on the RGB vectors them-
selves. In both situations the feature of interest is associated with the ele-
ments of the image.
The principles of the present invention are also applicable to blocks of
higher
dimensionality than 2, for example 3-dimensional blocks (volumes).
Comparison of the compression in accordance with the present invention
with the conventional prior art has shown that on the average the mPSNR
(multi-exposure Peak Signal-to-Noise Ratio) is at least 0.5 dB higher for the
present invention, see [9]. For normal map block compression an improve-
ment of 2 dB in PSNR (Peak Signal-to-Noise Ratio) has been obtained.
It will be understood by those skilled in the art that various modifications
and changes may be made to the present invention without departure from
the scope thereof, which is defined by the appended claims.
CA 02573911 2007-01-12
18
REFERENCES
[1] Konstantine Iourcha, Krishna Nayak, and Zhou Hong. System and
Method for Fixed-Rate Block-based Image Compression with Inferred
Pixels Values. In US Patent 5,956,431, 1999.
[2] G. Knittel, A. Schilling, A. Kugler, and W. Strasser. Hardware for Su-
perior Texture Performance. Computers & Graphics, 20(4):475-481,
July 1996.
[3] Jim Blinn. Simulation of Wrinkled Surfaces. In Proceedings of
SIGGRAPH, pages 286-292, 1978.
[4] ATI. Radeon x800: 3dc white paper. Technical report, 2005.
[5] Simon Green. Bump map compression. Technical report, NVIDIA,
2004.
[6] Kimmo Roimela, Tomi Aarnio, and Joonas Itaranta. High dynamic
range texture compression. ACM Transactions on Graphics, 25(3):707-
712, 2006.
[7] I. Dryden, K. Mardia: Statistical Shape Analysis, pp83-8'7, Wiley,
1998.
[8] K. Sayood: Introduction to Data Compression, pp266-68, Morgan
Kaufman, 1996.
[9] Jacob Munkberg, Petrik Clarberg, Jon Hasselgren, and Tomas
Akenine
Moller. High dynamic range texture compression for graphics hard-
ware, ACM Transactions on Graphics, 25(3):698-706, 2006.
