US 7,099,517 B2Grant

Codebook search methods

Issue Date:2006-08-29

•8 Claims

•2 Drawing Sheets

Abstract

A method of compressing an image frame composed of an array of pixels in the form of digital signals comprises a two stage codebook search. In the first stage the pixelated image frame and the pixelated codebook patches are transformed to frequency domain coefficients and a pattern comparison is made between the coefficients of the image patch and the codebook patches to identify a short list of possible match codebook patches by discarding incorrectly matching patterns. In the second stage the image frame is compared with the short list of codebook patches by any desired method, e.g. by pixel comparisons, to select the best matching codebook patch.

Metadata

Assignee

University of Strathclyde

Inventors

Richard John Fryer
Robert Bartholemew Lambert
David James Breslin
Paul Edward George Devlin

Application Information

Application Number:US 10/182,299

Filing Date:2001-01-31

Priority Date:2000-02-05

Art Unit:2621

Classifications

IPC:

G06K9/36G06K9/46

Patent Drawings (2 sheets)

Description

[0001] This application is a 371 of PCT/GB01/0039.4 Jan. 31, 2001

FIELD OF THE INVENTION

Background of the Invention

[0002] During image and video compression it may be necessary, dependent upon the mixture of techniques used, to select from a set of candidate image patches that patch which best (in some sense) corresponds to a patch separately held. For instance in the technique commonly known as Vector Quantisation (VQ) a small patch of an image is compared to a set of patches held in a ‘codebook’ to determine which patch from the codebook can best be used to represent the image patch. This process is often known as ‘codebook search’.

[0003] Codebook exhaustive search involves the full computation of the actual quality-of-match measure for each codebook patch separately, and the slection of the adopted codebook patch on the basis of these measures. Quality-of-match measures can be of many types including: total absolute pixel differences, total squared pixel differences, averages of these etc. Codebook exhaustive search can be a computational intensive process since, in principle, the process will involve every pixel in the image patch and in the set of all codebook patches. It is therefore desirable, in the interests of computational efficiency and speed, to limit the search process in some way.

[0004] It is possible to compare the image patch to a codebook patch directly on the basis of a comparison of the values of equivalent pixels. This is known as an ‘image space process’.

BRIEF SUMMARY OF THE INVENTION

[0005] It is an object of the present invention to obviate or at least mitigate one or more problems in the prior art.

[0006] It is a further object of at least one embodiment of the present invention to provide an improved codebook search method whereby a codebook can be searched in an appreciably faster manner than by exhaustive search.

[0007] It is a further object of at least one embodiment of the present invention to seek to exclude from a comparison process all codebook patches that would not be selected as the best match.

[0008] It is a yet further object of at least one embodiment of the present invention to provide a codebook search method where occasional non-optimal image patch to codebook patch associations are acceptable, by excluding from the search all codebook patches which, according to some criterion, will probably not be selected as the best match.

[0009] In making a decision as to whether a given codebook patch will certainly or probably not be selected some processing must be performed. It is evidently important that this processing be less than that involved in fully evaluating that codebook patch as to whether it is the best match.

[0010] According to a first aspect of the present invention there is provided a codebook search method comprising the steps of:

[0011] a) providing a plurality of codebook patches;

[0012] b) providing at least one image patch;

[0013] c) transforming by means of a lossless transform the plurality of codebook patches and the at least one image patch into sets of frequency domain codebook coefficients and a set(s) of frequency domain image coefficients, respectively;

[0014] d) for the/each image patch selecting a shortlete (ie. shortlist) of possible match codebook patches by means of a pattern comparison of + and − signs of the image coefficients of the/each image patch with the codebook coefficients; and

[0015] e) undertaking a further comparison of the image patch(es) against the shortlete codebook patches to select a substantially best match, this further comparison being effected by any desired method.

[0016] It will be appreciated that steps (a) to (e) may be carried out in any suitable order, and that indeed one or more of the steps may be carried out substantially simultaneously, if appropriate. However, preferably the steps are undertaken in the order (a), (b), (c), (d) and then (e), though steps (a) and (b) may be carried out in the order (b) then (a).

[0017] Each set of codebook coefficients or image coefficients thus represents a frequency spectrum of a pixel value distribution across a codebook patch or image patch, respectively.

[0018] The frequency domain codebook and image coefficients may be said to be characteristics of a ‘frequency space’.

[0019] Herein, a lossless transform is defined as one which permits an original data distribution to be reconstructed precisely by use of an ‘inverse transform’ process.

[0020] The lossless transform may be selected from one of a Haddamard transform, Wavelets, a discrete cosine transform or the like.

[0021] In a particular embodiment the number of image coefficients used in the pattern comparison may at least initially be equal in number to the number of pixels in a patch.

[0022] However, in a modification the number of image coefficients required to make a comparison may be reduced, eg. to those most significant in the frequency spectrum, eg. down to typically 15.

[0023] Each frequency space coefficient is representative of a property that is global to the transformed patch, whereas, a pixel value is representative only of one specific point in the patch, and can convey little or no global information. Useful patch comparisons can, therefore, be made on the basis of a small subset of all the frequency coefficients but which could not be made on an equivalent subset of the pixels in the original patch(es). It should be noted that in a lossless transform there will be as many frequency coefficients as there are pixels in the transformed patch.

[0024] Preferably, the transform is computed for each of the codebook patches and the codebook coefficients stored with the codebook patch to which they apply.

[0025] Preferably also, the transform is computed for each image patch as it comes under examination.

[0026] In a preferred embodiment, a subset of the coefficients is selected. For example, a set of 16 coefficients which represent predetermined most significant frequency properties of the pixel value distribution, eg. the lowest 16 frequencies of the pixel value distribution. It will be appreciated, however, that a different number of coefficients could be chosen, or coefficients representative of different portions of the frequency spectrum.

[0027] Further, for each codebook patch a ‘sign string’ may be established. A sign string may, for example, comprise a 16-bit pattern in which each bit corresponds to a specific instance of the set of 16 coefficients chosen for examination. Each bit in the string may be assigned a first value, eg. 0, if the corresponding coefficient is negative or a second value, eg. 1, if it is positive.

[0028] Yet further, for each codebook patch an ‘amplitude significance string’ may be established. An amplitude significance string may, for example, comprise a 16-bit pattern in which each bit corresponds to a specific instance of the set of 16 coefficients chosen for examination. Each bit in the string may be assigned a first value, eg. 0, if the corresponding coefficient is ‘insignificant’, or a second value, eg. 1, if it is ‘significant’. A coefficient may be considered significant if its absolute value exceeds a threshold value and insignificant otherwise. The threshold value may be set as a defined fraction of the average absolute amplitude of all the 16 coefficients selected for each of the patches in the codebook. It will be appreciated, however, that there may be other ways of assigning such a threshold value. It is not required that there should be a single threshold value for all coefficients. Indeed, there could be created other criteria for judging significance.

[0029] It should be noted that all these codebook computations may be performed off-line, and therefore represent no overhead during use of an encoder.

[0030] When an image patch is selected for examination its Haddamard coefficients may be established in a manner analogous to that for a single codebook patch. Further, a sign string may also be established for an image patch.

[0031] A codebook block or patch may be accepted for further examination, or rejected, as follows:

[0032] 1. A bitwise ‘exclusive or’ of the sign strings of the codebook patch and the image patch may be computed. This is a set of bits, each of which is of a first value, eg. 0, if the corresponding bits in the sign strings are the same and of a second value, eg. 1, if they are different. E.g. the bitwise exclusive or of 0011 with 0110 would produce 0101.

[0033] 2. The bit-string so produced may be bitwise ANDed with the significance string of the codebook patch. The bitwise AND is a set of bits, each of which is set to a first value, eg. 1, if the corresponding bits in the two strings are equal to the first value and to a second value 0 otherwise e.g. the bitwise AND of 0110 with 0101 would produce 0100. The effect of this operation is to set to a first value, eg. 0, all bits that are ‘insignificant’ and to leave all ‘significant’ bits unchanged.

[0034] 3. The final resulting bit pattern may be examined and if every bit is of a first value, eg. 0, the codebook patch may be accepted for further examination, otherwise it may be rejected. The effect of this decision may be to ensure that every significant coefficient in the codebook set has the same sign as the corresponding coefficient in the image patch set; insignificant coefficients being disregarded. Such codebook patches should bear a closer resemblance to the image patch than will codebook patches that have significant coefficients of opposite sign.

[0035] There remains a second case in which a codebook patch should be retained for examination. This is the case where the codebook and image patches are similar except that the codebook patch needs to be inverted before use, i.e. each of its pixel values must be multiplied by −1. The codebook patches are normalised in the sense that their pixel values are restricted to lie between plus and minus 1. This has implications for the computation of similarity with image patches (which typically will have pixel values in the range 0 to 127) but has no implications for the accept/reject criteria. An advantage of this method is that the use of frequency space coefficients eliminates the need to adjust the codebook patch pixel values before use.

[0036] The sequence of operations required to determine whether to retain a codebook patch for further examination on this basis may be as follows.

[0037] 1. The bitwise exclusive-or of the sign strings of the codebook patch and the image patch may be established.

[0038] 2. The bit-string so produced may be bitwise ORed with the inverse of the significance string of the codebook patch. A bitwise OR produces set of bits, each of which is set to a second value, eg. 1 if one or more of corresponding bits in the two strings is of a second value, eg. 1 and to a first value, eg. 0, otherwise e.g. the bitwise OR of 0110 with 0101 would produce 0111. Inversion of a bit-string converts each first value to a second value, and vice versa eg. 0 to 1 and each 1 to 0. E.g. the inverse of 0110 is 1001.

[0039] 3. The final resulting bit pattern may be examined and if every bit is 1 the codebook patch is accepted for further examination, otherwise it is rejected. The effect of this decision is to ensure that significant coefficients in the codebook set has the opposite sign to a corresponding coefficient in the image patch set; insignificant coefficients are disregarded.

[0040] There are thus two criteria upon which a codebook patch may be retained for further examination. Rejected patches need not be examined further as potential matches for the current image patch and may not therefore contribute further to the computational burden. The computation so avoided more than compensates for the additional computation involved in any computation of the Haddamard transform coefficients for the image patch and their use in determining accept/reject for the codebook patches. The method therefore can provide a very useful increase in speed for the searching of a codebook.

[0041] The Haddamard coefficients can further be used to compute the mismatch between a codebook patch and an image patch for purposes of determining the quality of a match and hence of the best patch to select from a codebook as the equivalent of an image patch.

[0042] The difference E between a codebook patch and an image patch can be expressed as:

[0043]

E = \sum_{i} {(W_{i}^{T} * σ - X_{i}^{T})}^{2}

where W^T_idenotes the ith transform coefficient for the codebook patch, σ is a contrast multiplier and X^T_iis the i^thtransform coefficient for the image patch. σ can be computed from the coefficients.

[0044] E can be estimated by summation over a subset of the coefficients and it can be shown that the estimate monotonically approaches the true value of E as the number of coefficients used increases. E bears a direct relationship (multiplication by a computable factor) to the error computed by an analogous formula involving the pixel values in the image space versions of the patches.

[0045] Thus, the use of frequency domain or space coefficients permits selection of a best match between an image patch and a delivered codebook in an integrated and efficient manner.

[0046] According to a second aspect of the present invention there is provided a method of compressing an image frame composed of an array of pixels in the form of digital signals, including the step of providing a codebook search method which comprises the steps of:

[0047] a) providing a plurality of codebook patches;

[0048] b) providing at least one image patch;

[0049] c) transforming by means of a lossless transform the plurality of codebook patches and the at least one image patch into sets of frequency domain codebook coefficients and a set(s) of frequency domain image coefficients, respectively;

[0050] d) for the/each image patch selecting a shortlete of possible match codebook patches by means of a pattern comparison of + and − signs of the image coefficients of the/each image patch with the codebook coefficients; and

[0051] e) undertaking a further comparison of the image patch(es) against the shortlete codebook patches to select a substantially best match, this further comparison being effected by any desired method.

[0052] According to a third aspect of the present invention there is provided an apparatus for compressing an array of data entries in the form of digital signals, the apparatus comprising a computer apparatus, for example of known type, set up to run a program embodying a codebook search method according to the first aspect.

[0053] According to a fourth aspect of the present invention there is provided a computer program product carrying a computer program adapted to perform the codebook search method according to the first aspect.

[0054] The computer program product may be a floppy disk, CD or the like.

[0055] According to a fifth aspect of the present invention there is provided a computer program adapted to perform the codebook search method according to the first aspect.

BRIEF DESCRIPTION OF THE DRAWINGS

[0056] An embodiment of the present invention will now be described by way of example only, with reference to the accompanying drawings which are:

[0057] FIGS. 1 (A)–(E) a schematic view of a codebook having five codebook patches or vectors each representing a 4×4 pixel image block for use in an embodiment of the present invention; and

[0058] FIG. 2 a schematic view of a source 4×4 pixel image block or patch for use in the embodiment referred to in FIG. 1.

DETAILED DESCRIPTIONS OF EMBODIMENTS OF THE INVENTION

[0059] By way of illustration, and as shown in FIGS. 1(A) to (E), in an embodiment of a codebook search method (fast search process) according to the present invention, a codebook having five vectors 0, 1, 2, 3 and 4, each with a dimensionality of sixteen is provided. Each of the five vectors represents an image block of 4×4 pels as shown in FIG. 1. Actual pel values assigned to each vector are given in Table 1 hereinbelow, where f_c(i,j) denotes the pel value at position i,j.

[0060] When searching in the spatial domain, each vector element (ie. pixel) is equally significant and is, therefore, included in the evaluation of each codebook vector (patch) as a potential match to a source image block. However, according to the invention, transforming each codebook vector into the frequency domain using an appropriate transform function (the basis vectors of the function being orthogonal) gives a set, of transform coefficients equal in number to the number of pixels in each codebook vector.

[0061] The frequency domain concentrates the most significant information about each codebook vector into a small number of coefficients allowing both the rapid rejection of codebook vectors that do not well represent the source image block, and the identification of a good match from the remaining codebook vectors, by comparing a sub-set of the total transform coefficients.

[0062] The Walsh-Haddamard Transform has been found to be both simple and efficient for the purpose of codebook search. The forward 2-D Haddamard transform is given by;

[0063]

\begin{matrix} H (u, v) = \frac{1}{N^{2}} \sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1} f (x, y) (- 1) \sum_{i = 0}^{n - 1} [β (i, x) β (i, u) + β (i, y) β (i, v)] & (1) \end{matrix}

where, n=log₂N, and the function β(q,r) is defined as;

[0064]

β (q, r) = {\begin{matrix} 0 if bit q in the binary representation of r is zero \\ 1 if bit q in the binary representation of r is zero \end{matrix}

[0065] The significance of a frequency coefficient is defined in terms of its discriminatory power within the codebook; i.e. the degree of change in the coefficient across the codebook vectors, and hence its “usefulness” in segmenting the codebook into vectors that are similar/dissimilar to a source vector.

[0066] Applying the Haddamard Transform to the codebook in FIGS. 1(A) to (E) gives the transform coefficients shown in Table 2 hereinbelow, where H_c(u,v) denotes the value of coefficient u,v from the 2-D representation of the frequency space. The relative significance of each coefficient within the codebook as a whole may be given by the mean absolute magnitude of each coefficient with respect to all the codebook vectors, or by the standard deviation of each coefficient. The standard deviation of each coefficient within the codebook is shown in Table 2.

[0067] Sorting the Haddamard coefficients by standard deviation gives a coefficient significance ordering of:

[0068] 2→8→12→3→1→4→14→11→15→10→9→5→13→7→6→0
where coefficient 2 has the greatest standard deviation.

[0069] Consider the source block shown in FIG. 2 having the pel values and transform coefficients as given in Table 3, where f_s(i,j) denotes the pel intensity at position i,j within the source image block. Note that the transform coefficient H₃(0,0) corresponds to the DC value or mean of the source block.

[0070] Matching in the spatial domain is done using an error function:

[0071]

\begin{matrix} ε = \sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1} {(f_{s} (x, y) - σ f_{c} (x, y) - γ)}^{2} & (2) \end{matrix}

where σ is a contrast adjustment applied equally to all codebook elements, and γ is the mean of the source block. An optimal value for σ is given by:

[0072]

\begin{matrix} σ = \frac{\sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1} [f_{s} (x, y) - γ] f_{c} (x, y)}{\sum_{x = 0}^{N - 1} \sum_{y = 0}^{N - 1} {(f_{c} (x, y))}^{2}} & (3) \end{matrix}

[0073] The optimal value of σ and the corresponding error ε between the source block and each codebook vector is shown in Table 4. From the table it is clear that the best “fit” to the source block is from codebook vector 0 with a negative contrast adjustment.

[0074] The first step in searching the codebook using frequency space is to discard those codebook vectors that are “unlikely” to give a good approximation to the source block. This is done by matching on the sign of the most significant coefficients.

[0075] Taking the significance order as determined by the standard deviation of each coefficient, the first Q coefficients, where Q is less than the total number of coefficients, may be used to discard poor matches. The following worked example illustrates this using the first 6 significant Haddamard coefficients:

[0076] Table 5 below shows the significance of coefficients 2, 8, 12, 3, 1 and 4, where the significance is 0 if the coefficient has an absolute magnitude less than a threshold, otherwise the significance is represented by the sign of the coefficient. For this example, the threshold used to select significance is for the coefficient to have an absolute value greater or equal to 25% of the mean absolute magnitude for all the codebook coefficients.

[0077] For each codebook vector, form a string of bits (one per coefficient) where a bit is 0 if the corresponding coefficient is less than zero or 1 if the corresponding coefficient greater or equal to zero. This is the sign string or mask. The sign masks for each of the codebook vectors are given in Table 6.

[0078] For each codebook vector, create a bit significance mask (one per coefficient), based on the amplitude significance of each of the coefficients. A bit is only one if the corresponding coefficient is non-zero in Table 5. The significance masks for each of the codebook vectors are given in Table 7.

[0079] Construct a sign mask for the source block to be matched where each bit gives the sign of the respective coefficient. The sign mask for the source block is shown in Table 8.

[0080] Determine the match for a positive contrast adjustment by performing a bit-wise exclusive-or between the source sign mask and each codebook sign mask. For an exclusive-or, the result is a zero if the two source bits have the same value and is one if they have different values. Any 1's in the result indicates a difference in sign between the source and codebook coefficients. To determine the quality of the match, a bit-wise AND between the result of each bit-wise exclusive-or and the significance mask of each codebook vector is performed. The codebook vector is only considered a potential match if the result contains no 1's. Table 9 shows the result of the bit-wise exclusive-or followed by the bit-wise AND for each codebook vector.

[0081] Determine the match for a negative contrast adjustment by performing a bit-wise exclusive-or between the source sign mask and the inverse of each codebook sign mask. Any 1's in the result indicates a difference in sign between the source and codebook coefficients. To determine the quality of the match, a bit-wise AND between the result of each bit-wise exclusive-or and the significance mask of each codebook vector is performed. As before, the codebook vector is only considered a potential match if the result contains no 1's. Table 10 shows the result of the inverse bit-wise exclusive-or followed by the bit-wise AND for each codebook vector.

[0082] The match using the sign of each coefficient taken together with the significance yields three possible candidate matches. For positive contrast (as shown in Table 9), codebook vectors 1 and 2 have the correct significant signs. For negative contrast (as shown in table 10), codebook vector 0 has the correct significant signs. In other words, codebook vectors 3 and 4 have been rejected from the search process.

[0083] The best match from codebook vectors 0, 1 and 2 could be calculated in the spatial domain using Equation 2, but this is computationally expensive. An alternative is to calculate the match between the source block and the remaining codebook vectors in the frequency domain.

[0084] For the search in the frequency domain to be less computationally expensive than searching in the spatial domain, the error must be determined using a sub-set of the coefficients. This is done by applying a “cut-off” to the error calculation. To understand the “cut-off” search, it is necessary to understand how the error in the frequency domain relates to the error in the spatial domain.

[0085] Let w be a codebook vector representing a block of intensity values, where the mean of the intensity values is zero and the vector is of unit length. The match ε between a source vector {right arrow over (x)} and the vector {right arrow over (w)} must, therefore, include the multiplication of the codebook vector elements by a constant contrast adjustment σ, plus the addition to each modified vector element of a constant intensity offset γ. This match is defined as,

[0086]

\begin{matrix} ε = \sum_{i = 0}^{N - 1} {(x_{i} - σ ω_{i} - γ)}^{2} & (4) \end{matrix}

where x_iis the i^thelement of the source block vector {right arrow over (x)}, ω_iis the i^thelement of the codebook vector {right arrow over (w)}, and N is the dimensionality of the vectors {right arrow over (x)} and {right arrow over (w)}. This equation is equivalent to Equation 2 where the two-dimensional intensity values are mapped onto the elements of a vector.

[0087] The optimal values for σ and γ to minimise ε are calculated from

[0088]

\frac{ⅆ ɛ}{ⅆ σ} = \frac{ⅆ ɛ}{ⅆ γ} = 0

as follows:
as

[0089]

\sum_{i = 0}^{N - 1} ω_{i} = 0, and \sum_{i = 0}^{N - 1} ω_{i}^{2} = 1,

then Equation 4 can be expressed as:

[0090]

\begin{matrix} ε = \sum_{i = 0}^{N - 1} x_{i}^{2} - 2 γ \sum_{i = 0}^{N - 1} x_{i} - 2 σ \sum_{i = 0}^{N - 1} x_{i} ω_{i} + σ^{2} + N γ^{2} & (5) \end{matrix}

giving:

[0091]

\begin{matrix} \frac{ⅆ ε}{ⅆ γ} = 2 N γ - 2 \sum_{i = 0}^{N - 1} x_{i} = 0 γ = \frac{1}{N} \sum_{i = 0}^{N - 1} x_{i} & (6) \\ \frac{ⅆ ε}{ⅆ σ} = 2 σ - 2 \sum_{i = 0}^{N - 1} x_{i} ω_{i} = 0 σ = \sum_{i = 0}^{N - 1} x_{i} ω_{i} & (7) \end{matrix}

[0092] Since both

[0093]

\frac{ⅆ^{2} ε}{ⅆ γ^{2}}

and

[0094]

\frac{ⅆ^{2} ε}{ⅆ σ^{2}}

are positive,

[0095]

\frac{ⅆ ε}{ⅆ σ} = \frac{ⅆ ε}{ⅆ γ} = 0

represents a minimum of ε. Thus substituting the optimal values for γ and σ into Equation 5 gives a best match between {right arrow over (x)} and {right arrow over (w)} of:

[0096]

\begin{matrix} ε = \sum_{i = 0}^{N - 1} x_{i}^{2} - \frac{1}{N} {(\sum_{i = 0}^{N - 1} x_{i})}^{2} - {(\sum_{i = 0}^{N - 1} x_{i} w_{i})}^{2} & (8) \end{matrix}

[0097] From equation 8 it can be seen that given a set W of normalised codebook vectors, where W={{right arrow over (w)}₀, {right arrow over (w)}₁, . . . ,{right arrow over (w)}_c}, the best match to an arbitrary source block vector {right arrow over (x)} is the codebook {right arrow over (w)}_jε W that gives the maximum absolute value for σ. That is,

[0098]

\begin{matrix} | \overset{N - 1}{\sum_{i = 0}} x_{i} ω_{j, i} | \geq | \sum_{i = 0}^{N - 1} x_{j} w_{k, i} | \forall w_{-> k} \in W & (9) \end{matrix}

where ω_j,iis the i^thelement of the codebook vector {right arrow over (w)}_j.

[0099] Equation 4 represents the error in the spatial domain between a source vector {right arrow over (x)} and codebook vector {right arrow over (w)}. Each element of {right arrow over (x)} and {right arrow over (w)} represents the spatial structure of the source and codebook blocks respectively and contributes equally to the error ε. The elements of {right arrow over (x)} and {right arrow over (w)} are said to have equal “energy”.

[0100] An alternative is to perform the match between the source and codebook blocks in the frequency domain. Unlike the spatial domain, the energy is concentrated into a few low frequency coefficients allowing the quality of the match between {right arrow over (x)} and {right arrow over (w)} to be assessed from a small sub-set of the total coefficients. However to be of value, the match in the frequency domain must correspond to the match in the spatial domain.

[0101] Let {right arrow over (X)} and {right arrow over (W)} be N element vectors where the j^thelement of {right arrow over (x)} and {right arrow over (W)} are given by:

[0102]

X_{j} = \sum_{i = 0}^{N - 1} (x_{i} - \overline{x}) z_{j, i}, W_{j} = \sum_{i = 0}^{N - 1} w_{i} z_{j, i}

where z_j,iis the i^thelement of an N element vector {right arrow over (z)}_j, and {overscore (x)} is the mean of the elements of the vector {right arrow over (x)}.

[0103] Let ε be the sum of the squared difference between the equivalent elements of {right arrow over (X)} and {right arrow over (W)} weighted by σ such that;

[0104]

\begin{matrix} \begin{matrix} ɛ = \sum_{j = 0}^{N - 1} {(X_{j} - σ W_{j})}^{2} \\ = \sum_{j = 0}^{N - 1} {(\sum_{i = 0}^{N - 1} z_{j, i} (x_{i} - \overline{x} - {σω}_{i}))}^{2} \\ = \sum_{j = 0}^{N - 1} \sum_{i = 0}^{N - 1} \sum_{k = 0}^{N - 1} (Z_{j, i} Z_{j, k} (x_{i} - \overline{x} - {σω}_{i}) (x_{k} - \overline{x} - {σω}_{k})) \\ = \sum_{j = 0}^{N - 1} \sum_{k = 0}^{N - 1} ((x_{i} - \overline{x} - {σω}_{i}) (x_{k} - \overline{x} - {σω}_{k}) \sum_{j = 0}^{N - 1} Z_{j, i} Z_{j, k}) \end{matrix} & (10) \end{matrix}

[0105] Using the 1-D Haddamard transform, one can define each vector {right arrow over (z)}_jas a basic function such that:

[0106]

\begin{matrix} z_{j, i} = \frac{1}{N} (- 1) \sum_{l = 0}^{n - 1} β (j, l) β (i, l) & (12) \end{matrix}

where, n=log ₂N, and the function β(q,r) is defined as:

[0107]

β (q, r) = {\begin{matrix} 0 if bit q in the binary representation of r is zero \\ 1 if bit q in the binary representation of r is one \end{matrix}

[0108] Since for the Haddamard transform:

[0109]

\begin{matrix} \sum Z_{j, i} Z_{j, k} = {\begin{matrix} 0 if i \cdot k \\ \frac{1}{N} if i = k \end{matrix} \forall i, k ε {0, 1, \dots, N - 1} & (13) \end{matrix}

then equation 10 can be simplified to:

[0110]

\begin{matrix} ɛ = \frac{1}{N} \sum_{i = 0}^{N - 1} {(x_{i} - \overline{x} - σ w_{i})}^{2} & (14) \end{matrix}

[0111] As {overscore (x)}≡γ in Equation 4, the match in the frequency domain can be expressed in terms of the match in the spatial domain as,

[0112]

\begin{matrix} ɛ = \frac{ε}{N} & (15) \end{matrix}

[0113] Thus for the Haddamard transform, the error ε in the spatial domain is equal to N times the error ε in the transform domain.

[0114] For n Haddamard coefficients, where 1≦n≦N, let the error between the first n coefficients be:

[0115]

\begin{matrix} ɛ_{n} - \sum_{i = 0}^{n - 1} {(X_{i} - σ_{n} W_{i})}^{2} & (16) \end{matrix}

where σ_nis the contrast multiplier giving the best “fit” between the first n source and codebook Haddamard coefficients. If,

[0116]

A_{n} = \sum_{i = 0}^{n - 1} X_{i}^{2}, B_{n} = \sum_{i = 0}^{n - 1} (X_{i} W_{i}), C_{n} = \sum_{i = 0}^{n - 1} W_{i}^{2}

then the error ε_ncan be expressed as;
ε_n=A_n−2σ_nB_n+σ_n²C_n (17)

[0117] The optimal value of σ_nis calculated from;

[0118]

\begin{matrix} \frac{ⅆ ɛ_{n}}{ⅆ σ_{n}} = 2 σ_{n} C_{n} - 2 B_{n} = 0 σ_{n} = \frac{B_{n}}{C_{n}} & (18) \end{matrix}

[0119] Thus the error for n coeffs with optimised σ_nis given by:

[0120]

\begin{matrix} ɛ_{n} = A_{n} - \frac{B_{n}^{2}}{C_{n}} & (19) \end{matrix}

[0121] To reduce search time, it is desirable to “cut-off” the calculation of the error following the evaluation of error based on a sub-set of the total Haddamard coefficients. That is, terminate the calculation if the error ε_mis greater than the minimum error derived for a codebook match, where m<N. This cut-off is only possible if ε_n≦ε_n-1.

[0122] Proof:

[0123]

ɛ_{n} - ɛ_{n - 1} \begin{matrix} = A_{n} - \frac{B_{n}^{2}}{C_{n}} - A_{n - 1} + \frac{B_{n - 1}^{2}}{C_{n - 1}} \\ = A_{n - 1} + X_{n}^{2} - \frac{{(B_{n - 1} + X_{n} W_{n})}^{2}}{C_{n - 1} + W_{n}^{2}} - A_{n - 1} + \frac{B_{n - 1}^{2}}{C_{n - 1}} \\ = \frac{C_{n - 1}^{2} X_{n}^{2} + B_{n - 1}^{2}}{C_{n - 1}} - \frac{{(B_{n - 1} + X_{n} W_{n})}^{2}}{C_{n - 1} + W_{n}^{2}} \\ = \frac{{(C_{n - 1} X_{n} - B_{n - 1} W_{n})}^{2}}{C_{n - 1}^{2} + C_{n - 1} W_{n}^{2}} \end{matrix}

ɛ_{n} - ɛ_{n - 1} \geq 0

since (C_n-1X_n−B_n-1W_n)²≧0 and (C_n-1²+C_n-1W_n²)≧0.

[0124] As ε_n≧ε_n-1,the evaluation of the best codebook vector can be implemented by the following algorithm, where the codebook coefficients are assumed to be ordered by significance such that the last coefficient (coefficient N−1) is the DC value which has the value zero for all the codebook vectors.

Algorithm:

- [0125] for the first codebook coefficient vector {right arrow over (W)}₀do

[0126]

set best error = A_{N - 1} - \frac{B_{N - 1}^{2}}{C_{N - 1}}

- [0127] store the index of the first codebook vector as the best fit to {right arrow over (X)}
[0128] end for
- [0129] for each remaining codebook coefficient vector {right arrow over (W)}_cdo set the coefficient index j to one
- [0130] do
  - [0131] calculate

[0132]

ɛ = A_{j} - \frac{B_{j}^{2}}{C_{j}}

- - [0133] increment j by one
- [0134] while j<N and ε<best error
- [0135] if ε<best error then
  - [0136] set best error=ε
  - [0137] store the index of the codebook vector as the best fit to {right arrow over (X)}
[0138] end if
[0139] end for

[0140] This algorithm can be applied to the numerical example to determine the best match from codebook vectors 0, 1 or 2.

[0141] Table 11 gives the results of following the search algorithm. The error in frequency space for codebook vector 0, as the first vector, is evaluated from equation 19 with n=15. This gives the best error value for the subsequent search. Calculating the error between the first two coefficients for codebook vector 1 gives an error that exceeds the best error and thus vector 1 is rejected. The match between the source and codebook vector 3 is evaluated up-to 14 out of the 15 coefficients before the error exceeds the best error. As codebook vector 0 gave the minimum error, it represents the best match to the source block.

[0142] The final step is to calculate the contrast for codebook vector 0 that will map it onto the source block. Equation 18 gives a contrast of −0.944. Hence an optimal codebook vector with corresponding contrast can be determined by matching in both the spatial and frequency domain. A key advantage of using the frequency domain is a reduction in calculation necessary to determine a best match using both the significance of the source block frequency coefficients to discard poor matches and the error cut-off. Though the error cut-off could be applied in the spatial domain, it gives little benefit as the majority of pels must be used in the error calculation.

[0143] Note that the difference between the optimal contrast calculated in the spatial domain and in the frequency domain is due to loss of accuracy in the transform process.

[0144] It will be appreciated that the embodiment of the invention hereinbefore described is given by way of example only, and is not meant to limit the scope of the invention in any way.

[0145] It will further be appreciated that various modifications may be made without departing from the invention. For example, the specific embodiment hereinbefore described provides a method of making a comparison of image and codebook patches with the objective of eliminating—for low computational cost—codebook patches which will probably not be the best match to a supplied image patch. The frequency transform adopted in the specific embodiment is the Haddamard transform, though it will readily be recognised that other frequency transforms could be used in a similar fashion.

[0146] Further, it will be appreciated that the final selection of the best matching patch, from amongst those not rejected initially, can be made using the frequency space coefficients themselves. This in itself represents a reduction of computation in comparison to the determination of match quality of non-rejected codebook patches using image space.

[0147] It is further envisaged that the invention may find use in compression of ‘still’ two dimensional image frames or compression of a set of image frames forming a video sequence. One specific application is that of transmission of video images between videophones.

[0148] Yet further, it will be appreciated that the coefficients in the frequency domain are effectively an average type or global type of characterisation of each pattern in contradistinction to pixel data which is not.

[0149]

TABLE 1

Values assigned to the elements of the codebook vectors.
	CODEBOOK VECTOR
VECTOR	VECTOR	VECTOR	VECTOR	VECTOR	VECTOR
ELEMENT	0	1	2	3	4

0 f_c(0,0)	128	−127	−127	−6	113
1 f_c(1,0)	63	−125	−87	43	1
2 f_c(2,0)	−62	−127	−32	85	3
3 f_c(3,0)	−127	−125	−7	128	123
4 f_c(0,1)	128	−57	−87	−47	−17
5 f_c(1,1)	63	−61	−42	0	−127
6 f_c(2,1)	−62	−47	−1	23	−122
7 f_c(3,1)	−127	−47	43	85	7
8 f_c(0,2)	128	43	−32	−74	−7
9 f_c(1,2)	58	53	0	−32	−115
10 f_c(2,2)	−57	63	43	−5	122
11 f_c(3,2)	−124	55	85	33	13
12 f_c(0,3)	125	124	0	−127	109
13 f_c(1,3)	53	125	33	−74	1
14 f_c(2,3)	−62	125	83	−32	12
15 f_c(3,3)	−125	128	128	0	128

[0150]

TABLE 2

Haddamard Transform coefficients for the codebook
given in FIG. 1.
HADDAMARD	COEFFICIENT MAGNITUDE	STANDARD
COEFFICIENT	VECTOR 0	VECTOR 1	VECTOR 2	VECTOR 3	VECTOR 4	DEVIATION

0 H_c(0,0)	0	0	0	0	0	0
1 H_c(1,0)	133	−1	−76	−91	−15	79
2 H_c(2,0)	373	−12	−171	−158	−21	196
3 H_c(3,0)	3	−3	1	−4	234	93
4 H_c(0,1)	3	−145	−78	86	4	78
5 H_c(1,1)	0	−1	7	5	−2	3
6 H_c(2,1)	0	1	3	3	8	2
7 H_c(3,1)	−1	−6	−4	−1	3	3
8 H_c(0,2)	2	−358	−170	155	−9	174
9 H_c(1,2)	−3	1	0	−9	2	4
10 H_c(2,2)	7	0	−2	−7	0	4
11 H_c(3,2)	−3	5	−9	8	1	6
12 H_c(0,3)	−3	−1	−4	8	245	98
13 H_c(1,3)	0	−2	5	3	7	3
14 H_c(2,3)	0	10	−5	14	0	7
15 H_c(3,3)	1	4	−3	−9	−6	4

[0151]

TABLE 3

Source block pel values and transform coefficients
	Source Pel Value	Transform Coefficient

	f_s(0,0)	0	H_s(0,0)	519
	f_s(1,0)	1	H_s(1,0)	−147
	f_s(2,0)	63	H_s(2,0)	−342
	f_s(3,0)	241	H_s(3,0)	−7
	f_s(0,1)	0	H_s(0,1)	−63
	f_s(1,1)	24	H_s(1,1)	4
	f_s(2,1)	159	H_s(2,1)	−8
	f_s(3,1)	250	H_s(3,1)	49
	f_s(0,2)	2	H_s(0,2)	−150
	f_s(1,2)	102	H_s(1,2)	0
	f_s(2,2)	248	H_s(2,2)	−1
	f_s(3,2)	255	H_s(3,2)	129
	f_s(0,3)	20	H_s(0,3)	−1
	f_s(1,3)	204	H_s(1,3)	−36
	f_s(2,3)	252	H_s(2,3)	49
	f_s(3,3)	255	H_s(3,3)	5

[0152]

TABLE 4

Optimal σ and error from each codebook vector
CODEBOOK VECTOR	OPTIMAL σ	ERROR (ε)

0	−0.945	48350
1	0.457	157316
2	1.397	51142
3	0.597	165121
4	0.073	187906

[0153]

TABLE 5

Significance of principal coefficients in codebook
	COEFFICIENT SIGNIFICANCE
HADDAMARD	VEC-	VEC-	VEC-	VEC-	VEC-
COEFFICIENT	TOR 0	TOR 1	TOR 2	TOR 3	TOR 4

2 H(2,0)	1	−1	−1	−1	−1
8 H(0,2)	0	−1	−1	1	−1
12 H(0,3)	0	0	0	1	1
3 H(3,0)	0	0	0	0	1
1 H(1,0)	1	0	−1	−1	−1
4 H(0,1)	0	−1	−1	1	0

[0154]

TABLE 6

Sign mask for each codebook vector.
CODEBOOK	COEFFICIENT BIT
VECTOR	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

0	1	1	1	1	1	1	1	0	1	0	1	0	0	1	1	1
1	1	0	0	0	0	0	1	0	0	1	1	1	0	0	1	1
2	1	0	0	1	0	1	1	0	0	1	0	0	0	1	0	0
3	1	0	0	0	1	1	1	0	1	0	0	1	1	1	0	0
4	1	0	0	1	1	0	1	1	0	1	1	1	1	1	1	0

[0155]

TABLE 7

Significance mask for each codebook vector.
CODEBOOK	COEFFICIENT BIT
VECTOR	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	1	0	0	0	1	0	0	0	0	0	0	0
2	0	1	1	0	1	0	0	0	1	0	0	0	0	0	0	0
3	0	1	1	0	1	0	0	0	1	0	0	0	1	0	0	0
4	0	1	1	1	0	0	0	0	1	0	0	0	1	0	0	0

[0156]

TABLE 8

Sign mask for source block.
COEFFICIENT BIT
0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

1	0	0	0	0	1	0	1	0	1	0	1	0	0	1	1

[0157]

TABLE 9

Match based on sign of significant coefficients
for + ve contrast.
CODEBOOK	COEFFICIENT BIT
VECTOR	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
3	0	0	0	0	1	0	0	0	1	0	0	0	1	0	0	0
4	0	0	0	1	0	0	0	0	0	0	0	0	1	0	0	0

[0158]

TABLE 10

Match based on sign of significant coefficients
for negative contrast.
CODEBOOK	COEFFICIENT BIT
VECTOR	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0
1	0	0	1	0	1	0	0	0	1	0	0	0	0	0	0	0
2	0	1	1	0	1	0	0	0	1	0	0	0	0	0	0	0
3	0	1	1	0	0	0	0	0	0	0	0	0	0	0	0	0
4	0	1	1	0	0	0	0	0	1	0	0	0	0	0	0	0

[0159]

TABLE 11

Match between source and codebook Haddamard Coefficients.
	CODEBOOK MATCH ERROR
	VECTOR 0	VECTOR 1	VECTOR 2

A₂− (B²₂/C₂)	not evaluated	7088.92	1134.74
A₃− (B²₃/C₃)	not evaluated	not evaluated	1136.17
A₄− (B²₄/C₄)	not evaluated	not evaluated	1140.62
A₅− (B²₅/C₅)	not evaluated	not evaluated	1219.54
A₆− (B²₆/C₆)	not evaluated	not evaluated	1380.37
A₇− (B²₇/C₇)	not evaluated	not evaluated	1577.32
A₈− (B²₈/C₈)	not evaluated	not evaluated	2833.03
A₉− (B²₉/C₉)	not evaluated	not evaluated	2838.34
A₁₀− (B²₁₀/C₁₀)	not evaluated	not evaluated	2838.55
A₁₁− (B²₁₁/C₁₁)	not evaluated	not evaluated	2838.55
A₁₂− (B²₁₂/C₁₂)	not evaluated	not evaluated	2840.68
A₁₃− (B²₁₃/C₁₃)	not evaluated	not evaluated	2956.36
A₁₄− (B²₁₄/C₁₄)	not evaluated	not evaluated	3142.72
A₁₅− (B²₁₅/C₁₅)	3014.45	not evaluated	not evaluated

Claims

Certificate of Correction present

The claims shown below may not include correction changes. Use the corrected PDF for authoritative text.

The invention claimed is:

1. A codebook search method comprising the steps of:

a) providing a plurality of codebook patches;

b) providing at least one image patch;

c) transforming by means of a lossless transform the plurality of codebook patches and the at least one image patch into sets of frequency domain codebook coefficients and a set(s) of frequency domain image coefficients, respectively;

d) for the/each image patch selecting a shortlete (ie. shortlist) of possible match codebook patches by means of a pattern comparison of + and − signs of the image coefficients of the/each image patch with the codebook coefficients; and

e) undertaking a further comparison of the image patch(es) against the shortlete codebook patches to select a substantially best match, this further comparison being effected by any desired method.

2. A method as claimed in claim 1, wherein the number of image coefficients used in the pattern comparison of step d) is, at least initially, equal in number to the number of pixels in a patch.

3. A method as claimed in claim 2, wherein the number of image coefficients required to make the pattern comparison of step d) is equal in number to those most significant in the frequency spectrum representative of the codebook coefficients.

4. A method as claimed in any preceding claim, wherein the transform of step c) is computed for each of the codebook patches and the codebook coefficients are stored with the codebook patch to which they apply.

5. A method as claimed in any preceding claim, wherein for each codebook patch a ‘sign string’ is established, comprising a multi-bit pattern in which each bit corresponds to a specific instance of the set of multiple coefficients chosen for examination, each bit in the string being assigned a first binary value if the corresponding coefficient is negative or a second binary value if the corresponding coefficient is positive.

6. A method of compressing an image frame composed of an array of pixels in the form of digital signals, including the step of providing a codebook search method as claimed in any preceding claim.

7. An apparatus for compressing an array of data entries in the form of digital signals, the apparatus comprising a computer apparatus set up to run a program embodying a codebook search method according to any one of claims 1–5.

8. A computer program product carrying a computer program embodied in a computer readable medium adapted to perform the codebook search method according to any one of claims 1–5.

Patent Citations (9)

Patent	Date	Inventor	Cited By
US4958225(A)	1990-09-01	Bi et al.	Examiner
US5057940(A)	1991-10-01	Murakami et al.	Examiner
US5574573(A)	1996-11-01	Ray et al.	Examiner
US5668897(A)	1997-09-01	Stolfo	Examiner
US5826225(A)	1998-10-01	Hartung et al.	Examiner
US6049632(A)	2000-04-01	Cockshott et al.	Examiner
US6438268(B1)	2002-08-01	Cockshott et al.	Examiner
US2003/0138159(A1)	2003-07-01	Fryer et al.	Examiner
US2004/0096117(A1)	2004-05-01	Cockshott	Examiner

Non-Patent Literature (5)

Bong-Hwan Kim, Tae-Yong Kim, Jeun-Woo Lee and Heung-Moon Choi; DCT-Based High Speed Vector Quantization Using Classified Weighted Tree-Structured Codebook; IEEE International Conference on Systems, Man and Cybernetics; Oct. 14, 1996; pp. 935-940; Cybernetics; New York, NY (XP-000738332).Applicant
Yih-Chuan Lin and Shen-Chuan Tai; Dynamic Windowed Codebook Search Algorithm In Vector Quantization; Optical Engineering; Oct. 1996; pp. 2921-2929; vol. 35 No. 10; Society of Photo-Optical Instrumentation Engineers (XP-000634371).Applicant
A.A. Abdelwahab and S.C. Kwatra; Component Coding Of Color Video Signal With Vector Quantization In The Transform Domain; Tencon; 1987; pp. 433-437; Seoul (XP-000946213).Applicant
Nasser M. Nasrabadi and Robert A. King; Image Coding Using Vector Quantization: A Review; IEEE Transactions on Communications; Aug. 1988, pp. 957-971; vol. 36 No. 8; IEEE, Inc., New York, NY (XP-000052119).Applicant
Copy of International Search Report for PCT/GB01/00394; completed Apr. 18, 2001.Applicant