Robust indexing and retrieval of electronic ink

• US 20070230791A1
• Filed: 04/04/2006
• Published: 10/04/2007
• Est. Priority Date: 04/04/2006
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Chellapilla, Kumar, Platt, John
• Granted Patent: US 7,646,940 B2
• Time in Patent Office: Days
• US Class Current: 382/188
• CPC Class Codes: G06F 18/2135 based on approximation criteria, e.g. principal component analysis
• CPC Class Codes: G06V 30/36 Matching; Classification

Abstract

A unique system and method that facilitates indexing and retrieving electronic ink objects with improved efficiency and accuracy is provided. Handwritten words or characters are mapped to a low dimension through a process of segmentation, stroke classification using a neural network, and projection along directions found using OPCA, for example. The employment of OPCA makes these low dimensional representations robust to handwriting variations or noise. Each handwritten word or set of characters is stored along with neighborhood hyperrectangle that represents word variations. Redundant bit vectors are used to index the hyperrectangles for efficient storage and retrieval. Ink-based queries can be submitted in order to retrieve at least one ink object. To do so, the ink query is processed to determine its query point which is represented by a (query) hyperrectangle. A data store can be searched for any hyperrectangles that match the query hyperrectangle.

Claims

1. A system that facilitates indexing and retrieving electronic handwritten ink characters comprising:

a featurization component that featurizes input ink to yield a membership matrix for each input ink;

a processor component that projects at least the membership matrix for each input ink into a low dimensional space; and

an index component that indexes each input ink using redundant bit vectors in one or more bit vector indices.

2. The system of claim 1, wherein the input ink comprises at least one of the following:

a word, one or more characters, or one or more symbols.

3. The system of claim 1 further comprises a normalization component that smoothes and scales the input ink to a unit height while maintaining its aspect ratio to make retrieval of the input ink indifferent to translation and scale variations.

4. The system of claim 1 further comprises a segmentation component that segments each input ink into a plurality of segments by cutting the input ink where a y-coordinate reaches a minimum value and starts to increase.

5. The system of claim 1, wherein the processor component projects the membership matrix for each input ink into the low dimensional space in a plurality of projection directions defined by at least one of the following:

oriented principal component analysis (OPCA) and multiple discriminant analysis (MDA).

6. The system of claim 1, wherein the processor component maps the segmented input ink to the membership matrix using a neural network before projecting it into the low dimensional space.

7. The system of claim 1, wherein the processor component creates low dimensional representations of the membership matrix for a given input ink to facilitate ink retrieval that is robust to user and instance variations.

8. The system of claim 1 further comprises a retrieval component that processes a query ink and searches a plurality of hyperrectangles stored in one or more bit vector indices to locate a match to the query ink.

9. The system of claim 8, wherein the query ink is converted to a query point and the retrieval component searches at least one data store for hyperrectangles that include the query point.

10. The system of claim 9, wherein the retrieval component optimizes recall to return more results by creating a hyperrectangle around the query point that can be successively grown in volume by iteratively including extra neighboring bit-dimensions during query processing

11. The system of claim 8, wherein the retrieval component optimizes precision of a results list by ranking the results using a similarity metric and truncating the results list to return the top-F best matches.

12. An ink indexing and retrieval method that facilitates retrieving electronic handwritten ink objects comprising:

featurizing input ink to yield a membership matrix for each input ink;

projecting the membership matrix for each input ink into a low dimensional space; and

indexing each input ink using redundant bit vectors.

13. The method of claim 12, wherein featurizing the input ink comprises:

splitting the input ink into a plurality of segments;

determining segments features based on the plurality of segments; and

classifying the stroke features to mitigate entropy and variance to create a membership matrix for the input ink.

14. The method of claim 13 further comprises creating a plurality of distorted versions of the input ink and creating membership matrices for the distorted versions.

15. The method of claim 14 further comprises mapping the membership matrices for the distorted versions of the input ink onto the low dimensional space.

16. The method of claim 12, wherein the low dimensional space is defined by at least a subset of projection directions.

17. The method of claim 16 further comprises using at least one of OPCA and MDA to determine the projection directions.

18. The method of claim 12 further comprises:

receiving a query ink;

determining a projected query point for the query ink, wherein the query point is represented as a query hyperrectangle; and

searching a data store for hyperrectangles that intersect the query point.

19. The method of claim 18 further comprises widening a query results list to include more results comprising:

adding one or more neighboring intervals in each dimension and increasing a number of ON bits in B_q to widen the bit vector,

ORing together bit dimensions that correspond to a same projection dimension; and

ANDing together any resulting bit vectors for each projection dimension.

20. A system that facilitates indexing and retrieving electronic handwritten ink characters comprising:

means for featurizing input ink to yield a membership matrix for each input ink;

means for projecting at least the membership matrix for each input ink into a low dimensional space;

means for indexing each input ink using redundant bit vectors; and

means for processing a query ink to yield a query hyperrectangle and searching one or more bit vector indices for hyperrectangles that at least closely match the query ink.