Image compression using content-based image similarity

• US 6,625,319 B1
• Filed: 03/30/1999
• Issued: 09/23/2003
• Est. Priority Date: 03/30/1999
• Status: Expired due to Fees

• Current Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Original Assignee: Koninklijke Philips Electronics N.V. (Koninklijke Philips N.V.)
• Inventors: Krishnamachari, Santhana
• Primary Examiner(s): Patel, Jayanti K.
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US09/281,353
• Time in Patent Office: 1,638 Days
• Field of Search: 382/232, 382/233, 382/238, 382/166, 382/225, 382/155, 382/159, 382/244, 382/173, 382/276, 382/250, 382/246, 382/260, 348/394.1, 348/398.1, 348/403.1, 348/715, 348/699, 358/450, 358/453, 358/261.2, 358/432
• US Class Current: 382/238
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 19/60 using transform coding

Abstract

A method for compressing a set of images that includes the steps of grouping the images into at least two clusters based on color content similarity, identifying at least one representative image in each of the clusters, all other images within each of the clusters being identified as non-representative images, independently coding the representative image(s) from each of the clusters, e.g., using a lossy (e.g., JPEG) or lossless coding algorithm; and, predictively coding each of the non-representative images from each of the clusters using the representative image(s) from that cluster as a reference image(s).

Claims

1. A method for compressing a set of images, including the steps of:

grouping the images into at least two clusters based on image similarity according to at least one similarity measure;

identifying at least one representative image in each of the clusters, all other images within each of the clusters being identified as non-representative images;

independently coding the representative image(s) from each of the clusters; and

,

predictively coding each of the non-representative images from each of the clusters using the representative image(s) from that cluster as a reference image(s).

2. The method as set forth in claim 1, wherein each of the non-representative images is coded with reference to a selected reference image in the predictively coding step by:

partitioning the non-representative image into a plurality of target blocks of pixels;

for each of the target blocks, searching the reference image for a same-sized reference block in the reference image that constitutes a best match according to a prescribed search metric; and

,

producing a coded data stream representative of which reference block, if any, in the reference image constitutes the best match for each target block.

3. The method as set forth in claim 2, wherein the independently coding step is carried out using a JPEG coding algorithm.

4. The method as set forth in claim 2, wherein the independently coding step is carried out using a lossless coding algorithm.

5.The method as set forth in claim 1, wherein each of the non-representative images is coded with reference to a selected reference image in the predictively coding step by:

partitioning the non-representative image into a plurality of target blocks of pixels;

for each of the target blocks, searching the reference image for a same-sized reference block in the reference image that constitutes a best match according to a prescribed search metric; and

,

for each of the target blocks, computing a difference between that target block and the reference block that constitutes its best match to produce a residual value for each target block; and

,

coding the residual values produced in the computing step to produce a coded data stream representative of the computed residual values.

7. The method as set forth in claim 1, wherein each of the non-representative images is coded with reference to a selected reference image in the predictively coding step by:

partitioning the non-representative image into a plurality of target blocks of pixels;

for each of the target blocks, searching within prescribed horizontal and vertical search ranges within the reference image for a same-sized reference block in the reference image that constitutes a best match according to a prescribed search metric; and

,

producing a coded data stream representative of which reference block in the reference image constitutes the best match for each target block.

8. The method as set forth in claim 1, wherein each of the non-representative images is coded with reference to a selected reference image in the predictively coding step by:

partitioning the non-representative image into a plurality of target blocks of pixels;

for each of the target blocks, searching within prescribed horizontal and vertical search ranges within the reference image for a same-sized reference block in the reference image that constitutes a best match according to a prescribed search metric; and

,

for each of the target blocks, computing a difference between that target block and the reference block that constitutes its best match, to produce a residual value for each target block; and

,

coding the residual values produced in the computing step to produce a coded data stream representative of the computed residual values.

9. The method as set forth in claim 1, wherein the independently coding step is carried out using a JPEG coding algorithm.

10. The method as set forth in claim 1, wherein the independently coding step is carried out using a lossless coding algorithm.

11. The method as set forth in claim 1, wherein the grouping step is carried out by using a hierarchical clustering algorithm.

12. The method as set forth in claim 1, wherein the predictively coding step includes DCT and VLC coding sub-steps.

13. The method as set forth in claim 1, wherein each of the non-representative images is coded with reference to a selected reference image in the predictively coding step by:

partitioning the non-representative image into a plurality of target blocks of pixels;

for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference image according to a prescribed search metric, and producing an error metric value for each comparison made;

for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and;

if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,

if not, independently coding that target block.

20. The method as set forth in claim 1, wherein the image similarity measure comprises a color similarity measure.

22. The method as set forth in claim 1, wherein the similarity measure includes at least one similarity measure selected from a group consisting of a color similarity measure, a texture similarity measure, a shape similarity measure, a geometrical similarity measure, and a content similarity measure.

23. The method as set forth in claim 1, further including the steps of:

partitioning each of the images into a plurality of color comparison blocks;

computing a normalized histogram for each of the color comparison blocks of each image; and

,

using the computed normalized histograms in performing the grouping and identifying steps.

25. A device that implements the method set forth in claim 1.

5. The method as set forth in claim 5, wherein the independently coding step is carried out using a JPEG coding algorithm.

6. The method as set forth in claim 5, wherein the independently coding step is carried out using a lossless coding algorithm.

14. The method as set forth in claim 14, wherein the sub-step of independently coding that target block is carried out using a JPEG coding algorithm.

15. The method as set forth in claim 14, wherein the predictively coding step further includes the sub-step of producing a coded data stream identifying the reference blocks of the reference images that constitute the best match for the respective target blocks of each of the non-representative images that are not independently coded, identifying which of the target blocks of each of the non-representative images are independently coded, and further, identifying which of the images of the set of images are reference images, and which are non-representative images.

16. The method as set forth in claim 14, wherein the predictively coding step further includes the sub-steps of:

for each of the target blocks that are not independently coded, computing a difference between that target block and the reference block that constitutes its best match, to produce a residual value for each of the target blocks that are not independently coded; and

,

coding the residual values produced in the computing step to produce a coded data stream representative of the computed residual values.

18. The method as set forth in claim 14, further including the steps of:

partitioning each of the images into a plurality of color comparison blocks;

computing a normalized histogram for each of the color comparison blocks of each image; and

,

using the computed normalized histograms in performing the grouping and identifying steps.

19. A device that implements the method set forth in claim 14.

17. The method as set forth in claim 17, wherein the coding sub-step of the predictively coding further includes coding into the coded data stream coded data identifying the reference blocks of the reference images that constitute the best match for the respective target blocks of each of the non-representative images that are not independently coded, identifying which of the target blocks of each of the non-representative images are independently coded, and further, identifying which of the images of the set of images are reference images, and which are non-representative images.

21. A device that implements the method set forth in claim 21.

24. A device that implements the method set forth in claim 24.

26. A method for compressing a set of sub-images, including the steps of:

grouping the sub-images into at least two clusters based on image similarity according to at least one similarity measure;

identifying at least one representative sub-image in each of the clusters, all other sub-images within each of the clusters being identified as non-representative sub-images;

independently coding the representative sub-image(s) from each of the clusters; and

,

predictively coding each of the non-representative sub-images from each of the clusters using the representative sub-image(s) from that cluster as a reference sub-image(s).

27. The method as set forth in claim 27, wherein each of the non-representative sub-images is coded with reference to a selected reference sub-image in the predictively coding step by:

partitioning the non-representative sub-image into a plurality of target blocks of pixels;

for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference sub-image according to a prescribed search metric, and producing an error metric value for each comparison made;

for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and;

if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,

if not, independently coding that target block.

28. The method as set forth in claim 27, wherein each of the non-representative sub-images is coded with reference to a selected reference sub-image in the predictively coding step by coding a difference between each non-representative sub-image and the representative sub-image(s).

29. A device that implements the method set forth in claim 27.

30. A method for compressing a set of images, including the steps of:

subdividing each image into a two or more partitions;

grouping corresponding ones of the partitions having corresponding locations in their respective images into at least two clusters based on image similarity according to at least one similarity measure, to thereby produce a set of clusters for each set of corresponding ones of the partitions;

identifying at least one representative image for each cluster of partitions, all other images within each of the clusters being identified as non-representative images;

independently coding a reference partition in the representative image(s) for each of the clusters; and

,

predictively coding each of the partitions in the non-representative images for each of the clusters using the reference partition(s) in the representative image(s) for that cluster as a reference partition(s).

31. The method as set forth in claim 31, further including the step of subdividing, for each cluster, each partition of each non-representative image into a plurality of smaller target blocks, and each partition of the representative image(s) into a plurality of smaller reference blocks having the same size as the target blocks, wherein the predictively coding step is carried out, for each cluster, by:

for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference partition(s) according to a prescribed search metric, and producing an error metric value for each comparison made;

for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and;

if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,

if not, independently coding that target block.

32. The method as set forth in claim 31, wherein the predictively coding step is carried out by, for each cluster, coding a difference between each non-representative partition and the reference partition(s) for that cluster.

33. A device that implements the method set forth in claim 31.

34. A method for compressing a set of images, including the steps of:

subdividing each image into a two or more partitions;

grouping the partitions into at least two clusters based on image similarity according to at least one similarity measure;

identifying at least one representative partition for each cluster of partitions, all other partitions within each of the clusters being identified as non-representative partitions;

independently coding the representative partition(s) for each of the clusters; and

,

predictively coding each of the non-representative partitions in each of the clusters using the representative partition(s) for that cluster as a reference partition(s).

35. The method as set forth in claim 35, further including the step of subdividing, for each cluster, each non-representative partition into a plurality of smaller target blocks, and the reference partition(s) into a plurality of smaller reference blocks having the same size as the target blocks, wherein the predictively coding step is carried out, for each cluster, by:

for each of the target blocks, comparing the pixels of that target block to the pixels of each of the same-sized reference blocks in the reference partition(s) according to a prescribed search metric, and producing an error metric value for each comparison made;

for each of the target blocks, determining whether the value of any of the error metric values produced is less than a prescribed maximum threshold value, and;

if so, identifying the one of the same-sized reference blocks that constitutes the best match for that target block, and,

if not, independently coding that target block.

36. The method as set forth in claim 35, wherein the predictively coding step is carried out by, for each cluster, coding a difference between each non-representative partition and the reference partition(s) for that cluster.

37. The method as set forth in claim 35 wherein in the case of a particular non-representative partition having more than one representative partition in its cluster, selecting a one of the representative partitions that is most similar to the particular non-representative partition as the reference partition for that particular non-representative partition.

38. The method as set forth in claim 35, wherein in the case of a particular non-representative partition having more than one representative partition in its cluster, selecting a one of the representative partitions that shares a nearest common ancestor node in a cluster tree for that cluster as the reference partition for that particular non-representative partition.

39. A device that implements the method set forth in claim 35.