Selecting content in ink documents using a hierarchical data structure

Patent metadata

Field	Value
Publication number	US-11972097-B2
Application number	US-202217897193-A
Country	US
Kind code	B2
Filing date	Aug 28, 2022
Priority date	Dec 10, 2020
Publication date	Apr 30, 2024
Grant date	Apr 30, 2024

Abstract

Technology is described herein for facilitating a user's interaction with a digital ink document. The technology internally represents the ink document using a data structure having a hierarchy of nodes. The nodes describe respective elements in the ink document. The technology leverages the data structure to identify a set of nodes that grows upon the user's repeated selection of a particular part of the ink document. At each stage of the selection, the technology highlights a set of elements in the ink document that correspond to the current set of identified nodes. According to another illustrative aspect, the technology produces the data structure by modifying an original data structure provided by a text analysis engine. The technology performs this task with the objective of accommodating structured interaction by the user with the ink document.

First claim

What is claimed is:

1. A method for selecting elements in an ink document, comprising:
receiving an original data structure produced by parsing ink strokes in the ink document, the original data structure having nodes that describe respective elements in the ink document, an original arrangement of the nodes in the original data structure describing an organization of the elements in the ink document;
producing a modified data structure that includes a hierarchy of nodes, the hierarchy of nodes having an arrangement of nodes that differs from the original arrangement of nodes in the original data structure;
processing input signals received in response to repeated selection by a user of a particular element in the ink document; and
identifying a set of nodes in the modified data structure upon each selection of the particular element by the user, and highlighting a particular set of elements in the ink document corresponding to the set of nodes on a display device,
said producing of the modified data structure being performed by logic that includes each of:
identifying a particular parent node in the original data structure, the particular parent node having a set of child nodes arranged in an original order;
determining a type of element that the particular parent node represents, and determining a particular direction of flow of child elements associated with the type, different kinds of parent nodes being associated with different directions of flow;
identifying a correct order of elements in a set of child elements in the ink document associated with the set of child nodes, as specified by positions of the child elements and the particular direction of flow; and
determining that the original order differs from the correct order of the elements in the set of child elements, and changing an order of the child nodes compared to the original order to conform to the correct order of the elements in set of child elements, to produce a reordered set of child nodes, and including the reordered set of child nodes in the modified data structure.

2. The method of claim 1 , wherein the correct order of elements in the set of child elements is determined based on positions of respective bounding boxes associated with the elements in the set of child elements.

3. The method of claim 1 ,
wherein the particular parent node is classified as a line parent node that represents line element in the original data structure,
wherein the particular direction of flow of elements in the set of child elements for the line parent node is a set of horizontally-flowing elements, and
wherein the correct order of the horizontally-following elements in the ink document is determined based on left-most coordinates of respective bounding boxes of the horizontally-flowing elements.

4. The method of claim 3 ,
wherein respective bounding boxes of at least two elements associated with the set of child nodes have a same left-most coordinate, and
wherein the correct order of said at least two elements is also determined by respective top-most coordinates of the bounding boxes associated with said at least two elements.

5. The method of claim 1 ,
wherein the particular parent node is classified as a list parent node or a paragraph parent node that respectively represents a list element or a paragraph element in the original data structure,
wherein the particular direction of flow of elements in the set of child elements for the list parent node or the paragraph part node is a set of vertically-flowing elements, and
wherein the correct order of the vertically-following elements in the ink document is determined based on top-most coordinates of respective bounding boxes of the vertically-flowing elements.

6. The method of claim 5 ,
wherein respective bounding boxes of at least two elements associated with the set of child nodes have a same top-most coordinate, and
wherein the correct order of said at least two elements is also determined by respective left-most coordinates of the bounding boxes associated with said at least two elements.

7. The method of claim 1 , wherein said producing of the modified data structure is performed by logic that includes each of:
identifying a single paragraph parent node in the original data structure that describes a paragraph element in the ink document; and
determining that there is a non-paragraph element in the ink document within a vertical span of the paragraph element, and splitting up the single paragraph parent node into two paragraph nodes and including the two paragraph nodes in the modified data structure, the two paragraph nodes including a first paragraph node associated with a first paragraph that is positioned above the non-paragraph element in the ink document, and a second paragraph node associated with a second paragraph that is positioned below the non-paragraph element in the ink document.

8. The method of claim 1 , wherein said producing of the modified data structure is performed by logic that includes each of:
identifying a single paragraph parent node in the original data structure that describes a paragraph element in the ink document; and
determining that the paragraph element has a pair of neighboring lines that are farther apart than a prescribed threshold value, and splitting up the single paragraph parent node into two paragraph nodes and including the two paragraph nodes in the modified data structure, the two paragraph nodes including a first paragraph node associated with a first paragraph element that includes a first of the pair of neighboring lines, and a second paragraph node that is associated with a second paragraph element that includes a second of the pair of neighboring lines.

9. The method of claim 8 , wherein the method further comprises determining that the second paragraph element has a pair of neighboring lines that are farther apart than the prescribed threshold value, and in response thereto splitting up the second paragraph node into two paragraph nodes, and including the two paragraph nodes associated with the second paragraph node in the modified data structure.

10. The method of claim 1 , wherein one particular direction of flow for one kind of parent node is right to left, and wherein another particular direction of flow for another kind of parent node is top to bottom.

11. A computing system for selecting elements in an ink document, comprising:
hardware logic circuitry that includes one or more hardware processors and/or one or more configurable gate units, the hardware logic circuitry being configured to perform operations of:
generating an original data structure by parsing ink strokes in the ink document, the original data structure having nodes that describe respective elements in the ink document, an original arrangement of the nodes in the original data structure describing an organization of the elements in the ink document;
producing a modified data structure that includes a hierarchy of nodes, the hierarchy of nodes having an arrangement of nodes that differs from the original arrangement of nodes in the original data structure;
processing input signals received in response to repeated selection by a user of a particular element in the ink document; and
identifying a set of nodes in the modified data structure upon each selection of the particular element by the user, and highlighting a particular set of elements in the ink document corresponding to the set of nodes on a display device,
said producing of the modified data structure being performed by logic that includes each of:
identifying a particular parent node in the original data structure, the particular parent node having a set of child nodes arran

Assignees

• Microsoft Technology Licensing Llc

Inventors

• Solomon Oz
• Finkelstein Erich Søren
• Caldwell Gary Lee
• Fish Nathan James
• Doroshenko Sergey Aleksandrovich

Classifications

• G06F3/04842 Primary

  Selection of displayed objects or displayed text elements (G06F3/0482 takes precedence) · CPC title

• G06F3/04883 Primary

  for inputting data by handwriting, e.g. gesture or text · CPC title

• G06F9/451

  Execution arrangements for user interfaces · CPC title

• G06F40/137

  Hierarchical processing, e.g. outlines · CPC title

• G06F40/14

  Tree-structured documents (parsing G06F40/205; validation G06F40/226) · CPC title