Robust indexing and retrieval of electronic ink

• US 7,646,940 B2
• Filed: 04/04/2006
• Issued: 01/12/2010
• Est. Priority Date: 04/04/2006
• Status: Expired due to Fees

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Platt, John C., Chellapilla, Kumar H.
• Primary Examiner(s): Mehta; Bhavesh M
• Assistant Examiner(s): Rosario; Dennis
• Application Number:
  US11/397,436
• Publication Number:
  US 20070230791A1
• Time in Patent Office: 1,379 Days
• Field of Search: 382/186, 382/187, 382/314, 382/305, 707 3- 6
• US Class Current: 382/305
• 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:

an ink processing module to;

featurize input ink to yield a membership matrix for each input ink,

project at least the membership matrix for each input ink into a low dimensional space, and

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

a retrieval module to;

search a data store for hyperrectangles that intersect the query point to produce query results, and

widen the query results by adding one or more neighboring intervals in each dimension and increasing a number of ON bits in a binary representation of the query hyperrectangle.

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 culling the input ink where a y-coordinate value of the input ink reaches a minimum value and starts to increase.

5. The system of claim 1, wherein the ink processing module 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 ink processing module 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 ink processing module 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, wherein the ink processing computes a binary representation for the query hyperrectangle.

9. The system of claim 1, wherein the retrieval component widens the query results by ORing together bit dimensions that correspond to a same projection dimension.

10. The system of claim 1, wherein the retrieval component widens the query results by:

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

ANDing together any resulting bit vectors for each projection dimension.

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

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

receiving an input ink;

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

projecting the membership matrix, via a processor component, for each input ink into a low dimensional space;

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

computing a binary representation for the query hyperrectangle;

indexing each input ink using redundant bit vectors to build a data store;

searching the data store for hyperrectangles that intersect the guery point to produce query results;

widening the query results comprising;

adding one or more neighboring intervals in each dimension and increasing a number of ON bits in the computed binary representation for the query hyperrectangle to widen a bit vector,

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

ANDing together any resulting bit vectors for each projection dimension.

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. A system that facilitates indexing and retrieving electronic handwritten ink characters comprising:

a processor; and

a memory into which a plurality of computer-executable instructions are loaded, the plurality of instructions performing a method comprising;

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

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

indexing each input ink using redundant bit vectors;

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; and

widening the searching by increasing a number of ON bits in a binary representation of the query hyperrectangle.