Image compression using exemplar dictionary based on hierarchical clustering

A method performed by a computer for encoding an image using an exemplar dictionary, the method comprising:

• selecting a target block from an image;
• searching for a predictor block matching the target block in an exemplar dictionary, wherein the exemplar dictionary is organized as a hierarchy of clusters comprising multiple levels of hierarchy, each level of the hierarchy associated with a set of dimensions of features vectors, the searching comprising at each level:
• representing the target block as a feature vector using the set of dimensions associated with the level;
• determining a matching cluster at the level for the target block;
• responsive to determining that the matching cluster is at a leaf level of the hierarchy, selecting an exemplar in the matching cluster that satisfies a selection criteria as the predictor block;
• encoding the target block using the predictor block;
• and
• storing an encoded image having the encoded target block.

A computer-implemented system for building an exemplar dictionary comprising exemplars for encoding images, the system comprising:

• a computer processor;
• and
• a computer-readable storage medium storing computer program modules configured to execute on the computer processor, the computer program modules comprising:
• a dictionary builder module configured to identify a set of exemplars, each exemplar comprising at least one image;
• a clustering module configured to perform hierarchical clustering of the set of exemplars to generate a plurality of clusters arranged as a hierarchy, the hierarchy comprising a high level and a low level, such that clusters at the high level are closer to a root of the hierarchy compared to clusters at the low level, the hierarchical clustering comprising:
• generating clusters at each level of the hierarchy, the generating comprising a filtering of exemplars such that the filtering performed at the high level generates less information per exemplar compared to the filtering performed at the low level;
• and
• the dictionary builder module, further configured to store an exemplar dictionary comprising information describing the hierarchy of clusters, wherein the exemplar dictionary is used to identify predictor blocks for encoding an image.

A computer program product having a non-transitory computer-readable storage medium storing computer-executable code for building an exemplar dictionary comprising exemplars for encoding images, the code comprising:

• a dictionary builder module configured to identify a set of exemplars, each exemplar comprising at least one image;
• a clustering module configured to perform hierarchical clustering of the set of exemplars to generate a plurality of clusters arranged as a hierarchy, the hierarchy comprising a high level and a low level, such that clusters at the high level are closer to a root of the hierarchy compared to clusters at the low level, the hierarchical clustering comprising:
• generating clusters at each level of the hierarchy, the generating comprising a filtering of exemplars such that the filtering performed at the high level generates less information per exemplar compared to the filtering performed at the low level;
• and
• the dictionary builder module further configured to store an exemplar dictionary comprising information describing the hierarchy of clusters, wherein the exemplar dictionary is used to identify predictor blocks for encoding an image.