System and method for text line and text block extraction

Patent metadata

Field	Value
Publication number	US-12548358-B2
Application number	US-202217867440-A
Country	US
Kind code	B2
Filing date	Jul 18, 2022
Priority date	Jul 31, 2019
Publication date	Feb 10, 2026
Grant date	Feb 10, 2026

Abstract

The invention concerns a method implemented by a device for displaying strokes of digital ink in a display area and for performing text line extraction to extract text lines from the strokes. In particular, the text line extraction may involve slicing the display area into strips, ordering for each strip the strokes into ordered lists which form collectively a first set of ordered lists, forming for each strip a second set of ordered lists by filtering out from the ordered lists of the first set strokes which are below a given size threshold, and performing a neural net analysis based on said first and second sets to determine for each stroke a respective text line to which it belongs.

First claim

The invention claimed is:

1 . A method for performing text block extraction to extract text blocks from handwriting strokes on a computing device, the computing device comprising a processor, a memory and at least one non-transitory computer-readable medium for recognizing input under control of the processor, the method comprising:
displaying, in a display area, the handwriting strokes of digital ink which are input substantially along a handwriting orientation; performing text line extraction to extract a number of text lines from said strokes; ordering the extracted text lines vertically; generating an initial text block including a first ordered text line; generating an initial text block set including the initial text block; setting at least one current text block set as the initial text block set; setting at least one current text block as the initial text block; updating iteratively, until the last ordered text line, the at least one current text block set by:
generating a certain number of next text block sets, wherein the certain number of next text block sets is the number of the at least one current text block set plus the number of the at least one current text block of the at least one current text block set, by:
combining the next text line with each of the at least one current text block of the at least one current text block set to generate a first subset of the certain number of the next text block sets; and
including the next text line as one next text block in one of the next text block sets to generate a second subset of the certain number of next text block sets;

calculating costs of the certain number of next text block sets;
replacing, the at least one current text block set, with the at least one next text block set of the certain number of the next text block sets that fulfils one or more cost criteria; and
extracting the text blocks from one of the at least one current text block sets.

2 . The method of claim 1 , wherein calculating a cost of a next text block set comprises one or more of:
calculating a global alignment of the combined text lines; calculating a text height coherence of the combined text lines; calculating interline distances between the combined text lines; and calculating gap distances between the combined text lines with respect to the average text height of the combined text lines.

3 . The method of claim 1 , wherein said text line extraction comprises:
slicing said display area into strips extending transversally to the handwriting orientation, wherein adjacent strips partially overlap with each other so that each stroke is contained in at least two adjacent strips; ordering, for each strip, the strokes at least partially contained in said strip to generate a first timely-ordered list of strokes arranged in a temporal order and at least one first spatially-ordered list of strokes ordered according to at least one respective spatial criterion, thereby forming a first set of ordered lists; forming, for each strip, a second set of ordered lists comprising a second timely-ordered list of strokes and at least one second spatially-ordered list of strokes by filtering out strokes below a size threshold from said first timely-ordered list and from said at least one first spatially-ordered list respectively; performing a neural net analysis to determine as a decision class, for each pair of consecutive strokes in each ordered list of said first and second set, whether the strokes of said pair belong to a same text line, in association with a probability score for said decision class; selecting, for each pair of consecutive strokes included in at least one ordered list of said first and second sets, the decision class determined with the highest probability score during the neural net analysis; and defining text lines by combining strokes into line hypotheses based on the decision class with the highest probability score selected for each pair of consecutive strokes.

4 . The method of claim 1 , wherein said strokes of digital ink are input in a free handwriting format devoid of any handwriting guiding constraint.

5 . The method of claim 1 , wherein said slicing is configured so that the strips extend along a same strip orientation.

6 . The method of claim 5 , wherein said slicing comprises:
determining a width of the strips based on the scale of the strokes; and assigning each stroke to each strip in which said stroke is at least partially contained.

7 . The method of claim 5 , wherein said slicing is configured so that each pair of adjacent strips partially overlap with each other to share between 50% and 85% of their respective area.

8 . The method of claim 5 , wherein said at least one first spatially-ordered list generated for each strip in said ordering comprises at least one of:
a spatially-ordered list of strokes ordered according to the position, along the strip orientation, of the respective barycentre of each stroke of said strip; a spatially-ordered list of strokes ordered according to the outermost coordinate in a first direction along the strip orientation of each stroke of said strip; and a spatially-ordered list of strokes ordered according to the outermost coordinate in a second direction, opposite said first direction, along the strip orientation of each stroke of said strip.

9 . The method of claim 1 , wherein said forming a second set of ordered lists comprises, for each strip:
evaluating a first size of each stroke of said strip based on at least one of a height or maximum distance in the strip orientation of said stroke and a second size of each stroke of said strip based on the length of said stroke; and removing, from said first timely-ordered list and from said at least one first spatially-ordered list, each stroke when either said first or second size is below a size threshold, thereby generating respectively the second timely-ordered list and said at least one second spatially-ordered list.

10 . The method of claim 1 , wherein said neural net analysis comprises:
computing, by at least one artificial classifier or neural net, probability scores representing the probability that the strokes, in each pair of consecutive strokes included in the ordered lists of said first and second sets of ordered lists, belong to a same text line; and determining, as a decision class for each pair of consecutive strokes, that the strokes of said pair belong to a same text line if the probability score reaches at least a probability threshold.

11 . The method of claim 10 , wherein during the neural net analysis, said at least one artificial neural net sequentially analyzes each pair of consecutive strokes in each ordered list of said first and second sets to determine the respective decision class and probability score, based on spatial and temporal information related to the strokes in said ordered list.

12 . The method of claim 1 , wherein said selecting comprises:
compiling into a probability matrix the selected decision class, in association with the respective probability score, for each pair of consecutive strokes included in at least one ordered list of said first and second sets.

13 . The method of claim 1 , wherein said defining text lines comprises:
transforming the probability matrix into a vector list of entries including the decision class and associated probability score for each pair of consecutive strokes included in said probability matrix, said vector list being arranged according to an order of decreasing value of the probability scores of each pair; and determining sequentially for each pair of consecutive strokes in the

Assignees

• Myscript

Inventors

• Hébert David

Classifications

• G06V30/36

  Matching; Classification · CPC title

• G06V30/18086

  by performing operations within image blocks or by using histograms · CPC title

• G06V10/82

  using neural networks · CPC title

• G06V30/148

  Segmentation of character regions · CPC title

• G06F18/21

  Design or setup of recognition systems or techniques; Extraction of features in feature space; Blind source separation · CPC title