Real time data matching

• US 7,130,467 B1
• Filed: 03/19/2003
• Issued: 10/31/2006
• Est. Priority Date: 03/19/2003
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Frankcom, Tracey M., Bronder, Matthew L.
• Primary Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US10/392,740
• Time in Patent Office: 1,322 Days
• Field of Search: 382/143, 382/144, 382/145, 382/147, 382/240, 382/243, 382/218, 382/305, 382/176, 367/38, 365/185.22, 369/103, 702/14
• US Class Current: 382/218
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

Representing source data with predefined data patterns, or identifying predefined data patterns in source data, where each data pattern includes a unique combination of pattern elements, without comparing every pattern element of each data pattern to the source data. A hierarchical structure of relationships between the data patterns is predetermined in an initialization stage by comparing the data patterns to identify identical pattern elements among groups of the data patterns. Selected node elements in a resulting relationship tree are compared to the source data to determined deviations. The deviations are propagated and accumulated throughout the relationship structure of the tree, and data patterns having the minimum deviation are selected to represent corresponding source data cells. A graphics pipeline preferably is used to determine the deviations and select data patterns in real time.

Claims

1. A method for representing source data with a plurality of data patterns, wherein each data pattern includes a unique combination of pattern elements, and wherein data patterns are selected to represent the source data without comparing all of the pattern elements of each of the plurality of data patterns to the source data, said method comprising the steps of:

(a) predefining each of the plurality of data patterns with the plurality of pattern elements arranged along at least one dimension, wherein identical pattern elements are disposed at corresponding locations in some of the plurality of data patterns;

(b) comparing the plurality of data patterns to each other to define a relationship tree having nodes at a plurality of levels and leaves at a lowest level, said data patterns being grouped within the relationship tree as a function of the pattern elements that are disposed at corresponding locations within the plurality of data patterns, wherein each data pattern is represented by a different leaf of the relationship tree, nodes at each successive level above the lowest level representing pattern elements that are the same and pattern elements that are different in a subset of nodes on an immediately lower level;

(c) subdividing the source data into a plurality of source cells, wherein each of the plurality of source cells includes a plurality of source cell elements corresponding in number and arrangement to the pattern elements comprising each of the plurality of data patterns;

(d) at selected nodes of the relationship tree, determining a set of deviations for the node by calculating a deviation between;

(i) data derived from the plurality of data patterns, and

(ii) the plurality of source cells;

(e) propagating the set of deviations to related nodes according to a hierarchical structure of relationships between nodes of the relationship tree; and

(f) for each source cell of the plurality of source cells, selecting a matching data pattern from among the plurality of data patterns that provides a smallest set of deviations from the source cell, so that the source data are represented by the data patterns thus selected.

2. The method of claim 1, further comprising the steps of:

(a) comparing the plurality of data patterns to each other;

(b) forming subsets of the plurality of data patterns comprising the leaves, by selecting the data patterns having the most pattern elements that are the same at the corresponding locations in the data patterns, to be in each subset.

3. The method of claim 2, wherein the step of comparing the plurality of data patterns to each other comprises the steps of:

(a) determining the subset of data patterns from the plurality of data patterns that comprise a maximum number of identical pattern elements disposed at corresponding locations within the plurality of data patterns;

(b) storing the subset of data patterns as a set of child nodes in the relationship tree;

(c) removing the child nodes from further consideration for another set of child nodes; and

(d) repeating steps (a) through (c) until all of the data patterns comprising the plurality of data patterns have been stored in one of the sets of child nodes.

4. The method of claim 3, further comprising the steps of:

(a) after at least one set of child nodes has been stored, constructing a parent node that identifies equivalent pattern elements disposed at corresponding locations in all data patterns for all child nodes of the parent node;

(b) repeating step (a) to create other parent nodes at a current level of the relationship tree; and

(c) repeating steps (a) and (b) for successive levels of the relationship tree, until a single parent node is constructed as a root node of the relationship tree.

5. The method of claim 4, wherein the subsets of data patterns generally comprise a number of data patterns, said number being equal to a product of a number of color channels per pixel supported by a graphics pipeline used to implement the method, and a number of simultaneous render targets supported by the graphics pipeline.

6. The method of claim 4, wherein the step of constructing a parent node comprises the steps of:

(a) creating an aggregate mask that identifies each location at which corresponding pattern elements are equivalent in all of the data patterns referenced by the set of child nodes;

(b) creating a coverage mask that defines pattern elements for which the deviation is calculated and propagated;

(c) creating a composite map of the subset of data patterns, wherein the composite map comprises a multi-dimensional array of pattern elements from all data patterns of the subset, and the multi-dimensional array stores together groups of pattern elements, wherein each group of pattern elements comprises pattern elements disposed at a common location in the subset of data patterns; and

(d) creating a channel mask that associates a color channel of a graphics pipeline with a child node of a parent node and indicates whether the child node will inherit the deviation from the parent node as a function of a color channel intensity.

7. The method of claim 6, further comprising the step of creating a bilinear mask for source data of a black and white image, wherein the bilinear mask identifies pattern elements for which a bilinear optimization may be employed by marking all non-overlapping 2×

2 groupings of pattern elements that are of an equal color, have equal channel masks, and lie within the coverage mask.

8. The method of claim 1, wherein the source data comprises an image, and each of the plurality of data patterns comprises a pixel map.

9. The method of claim 1, wherein the step of determining a set of deviations comprises the steps of:

(a) rearranging all of the source cell elements from the plurality of source cells so as to group together source cell elements from identical locations within a source cell, thereby creating swizzled source cell elements;

(b) setting a number of swizzled source cell elements as inputs to a pixel shader of a graphics pipeline, wherein said number corresponds to at least one unique pattern element of the data derived from the plurality of data patterns associated with the node;

(c) selecting as a constant for the pixel shader, the at least one unique pattern element of the node from the data derived from the plurality of data patterns associated with the node;

(d) rendering the number of swizzled source cell elements with the pixel shader of the graphics pipeline and thereby comparing each of the number of swizzled source cell elements to the at least one unique pattern element for determining a deviation between each of the number of swizzled source cell elements and the at least one unique pattern element; and

(e) repeating steps (c) through (d) until all of the at least one unique pattern elements have been compared to the number of swizzled source cell elements, to calculate a set of deviations between all unique pattern elements of the node and the number of swizzled source cell elements.

10. The method of claim 1, wherein the step of propagating the set of deviations comprises one of the steps of:

(a) propagating the set of deviations from a root node of the relationship tree down to a plurality of leaf-parent nodes at a level immediately above the leaves at the lowest level; and

(b) propagating the set of deviations from a leaf-parent node of the relationship tree up to the root node.

11. The method of claim 1, wherein the step of propagating the set of deviations comprises the step of accumulating the set of deviations for the node with another set of deviations for a related node of the relationship tree.

12. A memory medium having machine instructions comprising a boot code stored thereon for carrying out the steps of claim 1.

13. A system for representing source data with a plurality of data patterns, wherein each data pattern includes a unique combination of pattern elements, and wherein data patterns are selected to represent the source data without comparing all of the pattern elements of each of the plurality of data patterns to the source data, comprising:

(a) a processor; and

(b) a memory in communication with the processor, said memory storing the source data and the data patterns, and storing machine instructions that cause the processor to perform a plurality of functions, including;

(i) predefining each of the plurality of data patterns with the plurality of pattern elements arranged along at least one dimension, wherein identical pattern elements are disposed at corresponding locations in some of the plurality of data patterns;

(ii) comparing the plurality of data patterns to each other to define a relationship tree having nodes at a plurality of levels and leaves at a lowest level, said data patterns being grouped within the relationship tree as a function the pattern elements that are disposed at corresponding locations within the plurality of data patterns, wherein each data pattern is represented by a different leaf of the relationship tree, nodes at each successive level above the lowest level representing pattern elements that are the same and pattern elements that are different in a subset of nodes on an immediately lower level;

(iii) subdividing the source data into a plurality of source cells, wherein each of the plurality of source cells includes a plurality of source cell elements corresponding in number and arrangement to the pattern elements comprising each of the plurality of data patterns;

(iv) at selected nodes of the relationship tree, determining a set of deviations for the node by calculating a deviation between data derived from the plurality of data patterns and the plurality of source cells;

(v) propagating the set of deviations to related nodes according to a hierarchical structure of relationships of the nodes in the relationship tree; and

(vi) for each source cell of the plurality of source cells, selecting a matching data pattern from among the plurality of data patterns that provides a smallest set of deviations from the source cell, so that the source data are represented by the data patterns selected thereby.

14. The system of claim 13, wherein the machine instructions further cause the processor to perform the functions of:

(a) comparing the plurality of data patterns to each other; and

(b) forming subsets of the plurality of data patterns comprising the leaves, by selecting the data patterns having the most pattern elements that are the same at the corresponding locations in the data patterns to be in each subset.

15. The system of claim 14, wherein the machine instructions further cause the processor to compare the plurality of data patterns to each other by causing the processor to perform the functions:

(a) determining the subset of data patterns from the plurality of data patterns that comprise a maximum number of identical pattern elements disposed at corresponding locations within the plurality of data patterns;

(b) storing the subset of data patterns as a set of child nodes in the relationship tree;

(c) removing the child nodes from further consideration for another set of child nodes; and

(d) repeating steps (a) through (c) until all of the data patterns comprising the plurality of data patterns have been stored in one of the sets of child nodes.

16. The system of claim 15, further comprising a graphics pipeline, wherein the machine instructions further cause the processor to construct a parent node by causing the processor to perform the functions of:

(a) creating an aggregate mask that identifies each dimensional location at which a corresponding pattern element is equivalent in all of the data patterns referenced by the set of child nodes;

(b) creating a coverage mask that defines pattern elements for which the deviation must be calculated and propagated;

(c) creating a composite map of the subset of data patterns, wherein the composite map comprises a multi-dimensional array of pattern elements from all data patterns of the subset, and the multi-dimensional array stores together groups of pattern elements, wherein each group of pattern elements comprises pattern elements disposed at a common location in the subset of data patterns; and

(d) creating a channel mask that associates a color channel of the graphics pipeline with a child node of a parent node, indicating whether the child node will inherit the deviation from the parent node as a function of a color channel intensity.

17. The system of claim 15, wherein the machine instructions further cause the processor to perform the functions of:

(a) after at least one set of child nodes has been stored, constructing a parent node that identifies equivalent pattern elements disposed at corresponding locations in all data patterns for all child nodes of the parent node;

(b) repeating step (a) to create other parent nodes at a current level of the relationship tree; and

(c) repeating steps (a) and (b) at successive levels until a single parent node is constructed as a root node of the relationship tree.

18. The system of claim 13, wherein the machine instructions further cause the processor to determine a set of deviations by causing the processor to perform the functions of:

(a) rearranging all source cell elements from the plurality of source cells so as to group together source cell elements from identical locations within a source cell, thereby creating swizzled source cell elements;

(b) setting a number of swizzled source cell elements as inputs to a pixel shader of a graphics pipeline, wherein said number corresponds to at least one unique pattern element of the data derived from the plurality of data patterns associated with the node;

(c) selecting as a constant for the pixel shader, the at least one unique pattern element of the node from the data derived from the plurality of data patterns associated with the node;

(d) rendering the number of swizzled source cell elements with the pixel shader of the graphics pipeline, thereby comparing each of the number of swizzled source cell elements to the at least one unique pattern element and thereby determining a deviation between each of the number of swizzled source cell elements and the at least one unique pattern element; and

(e) repeating steps (c) through (d) until all of the at least one unique pattern elements have been compared to the number of swizzled source cell elements, thereby calculating a set of deviations between all unique pattern elements of the node and the number of swizzled source cell elements.

19. The system of claim 13, wherein the machine instructions further cause the processor to propagate the set of deviations by causing the processor to perform the functions of:

(a) propagating the set of deviations from a root node of the relationship tree down to a plurality of leaf-parent nodes at a level immediately above the leaves at the lowest level; and

(b) propagating the set of deviations from a leaf-parent node of the relationship tree up to the root node.

20. A method for representing source data with a plurality of data patterns, each of which includes a unique combination of pattern elements, without comparing all of the pattern elements of each of the plurality of data patterns to the source data, comprising the steps of:

(a) creating a relationship tree having nodes at a plurality of levels, including leaves at a lowest level, said relationship tree being created as a function of equivalent pattern elements being disposed at corresponding locations within the plurality of data patterns, wherein each data pattern is represented by a different leaf of the relationship tree, nodes at each successive level above the lowest level representing pattern elements that are the same and pattern elements that are different in leaves that are successors to the nodes at each successive level above the lowest level;

(b) at selected nodes of the relationship tree, determining a set of deviations for the node by comparison to the source data;

(c) propagating the set of deviations to related nodes according to a hierarchical structure of relationships in the relationship tree; and

(d) for each of a plurality of cells that subdivide the source image, selecting a matching data pattern from among the plurality of data patterns, said matching data pattern providing a smallest set of deviations from the source cell, so that the source data are represented by the data patterns thus selected.