Granted Patent B2

US 12,700,251 · App. 18/148,928 · Granted Aug 4, 2026

Inventors: David Montero (Valladolid, ES); Jose Javier Yebes Torres (Valladolid, ES)

Assignee: Nielsen Consumer LLC

G06V30/153G06V10/82G06V30/146G06V30/1801G06V30/414G06Q30/0201

Abstract

Claims (52)

1 . An apparatus to detect lines, comprising:

at least one memory;

machine readable instructions; and

at least one processor circuit to be programmed by the machine readable instructions to:

generate feature embeddings for text segments detected in a document image, the text segments associated with respective bounding boxes, wherein the text segments are to be represented by nodes in a graph;

identify candidate edges between ones of the text segments;

pass the feature embeddings through graph attention (GAT) layers to update the feature embeddings with information from neighbor nodes;

generate an adjacency matrix for the document image by determining confidence scores for the candidate edges based on the updated feature embeddings; and

cluster the nodes based on the adjacency matrix to group ones of the nodes that belong to a same line.

2 . The apparatus of claim 1 , wherein the document image corresponds to a receipt, and the text segments correspond to words in the receipt image.

3 . The apparatus of claim 1 , wherein the text segments include the bounding boxes and respective text strings, and wherein one or more of the at least one processor circuit is to discard the text strings.

4 . The apparatus of claim 1 , wherein one or more of the at least one processor circuit is to generate a first one of the feature embeddings for a first text segment of the text segments by:

extracting features for the feature embeddings from the first text segment, the features including a left center coordinate, a right center coordinate, and a rotation angle of a respective bounding box;

normalizing the left center and right center coordinates using a width of the document; and

concatenating the normalized left and right center coordinates and the rotation angle.

5 . The apparatus of claim 1 , wherein one or more of the at least one processor circuit is to identify a first candidate edge between a first text segment and a second text segment of the text segments in response to determining that an absolute value of vertical distance between a center coordinate of the first text segment and a center coordinate of the second text segment is less than a height of the first text segment multiplied by a constant.

6 . The apparatus of claim 1 , wherein one or more of the at least one processor circuit is to generate a global node by averaging the feature embeddings, the global node to be passed through the GAT layers with the feature embeddings to provide a global document perspective.

7 . The apparatus of claim 1 , wherein the graph attention layers include residual connections.

8 . The apparatus of claim 1 , wherein one or more of the at least one processor is to apply a sigmoid linear unit (SiLu) activation to an output of ones of the graph attention layers.

9 . The apparatus of claim 1 , wherein one or more of the at least one processor circuit is to determine a first confidence score for a first edge connecting a first text segment and a second text segment of the text segments by:

identifying respective updated feature embeddings for the first text segment and the second text segment;

concatenating the updated feature embeddings for the first text segment and the second text segment; and

passing the concatenated feature embeddings for the first text segment and the second text segment through a multi-layer perceptron, the multi-layer perceptron including two fully-connected layers and a sigmoid function.

10 . The apparatus of claim 1 , wherein one or more of the at least one processor circuit is to cluster the text segments based on the adjacency matrix by applying a limited connected component algorithm to the adjacency matrix.

11 . At least one non-transitory machine readable storage medium comprising machine readable instructions to cause at least one processor circuit to at least:

obtain text segments corresponding to a document image, the text segments including rotated bounding box coordinates, wherein the text segments are to be represented by nodes of a graph;

sample edges between ones of the text segments to generate a graph, the graph including nodes representing the text segments;

generate feature embeddings for the nodes based on geometric features extracted from the text segments;

provide the graph and the feature embeddings to graph attention layers, the graph attention layers to determine message passing weight values, the graph attention layers to enrich the feature embeddings with neighborhood nodes and a global node;

determine confidence values for the edges based on the enriched feature embeddings; and

cluster the text segments by line based on the confidence values to detect lines in the document image.

12 . The at least one non-transitory machine readable storage medium of claim 11 , wherein the text segments include text strings, the machine readable instructions are to cause one or more of the at least one processor circuit to dispose of the text strings.

13 . The at least one non-transitory machine readable storage medium of claim 11 , wherein the machine readable instructions are to cause one or more of the at least one processor circuit to extract the geometric features from bounding boxes associated with the text segments, the geometric features including left center coordinates, right center coordinates, and rotation angles.

14 . The at least one non-transitory machine readable storage medium of claim 13 , wherein the machine readable instructions are to cause one or more of the at least one processor circuit to generate a first one of the feature embeddings for a first text segment of the text segments by:

normalizing respective ones of the left and right center coordinates using a width of the document image; and

concatenating a respective rotation angle for the first text segment and the normalized left and right center coordinates for the first text segment.

15 . The at least one non-transitory machine readable storage medium of claim 11 , wherein the machine readable instructions are to cause one or more of the at least one processor circuit to identify a first edge between a first text segment and a second text segment in response to determining that an absolute value of vertical distance between a center coordinate of the first text segment and a center coordinate of the second text segment is less than a height of the first text segment multiplied by a constant.

16 . The at least one non-transitory machine readable storage medium of claim 11 , wherein the machine readable instructions are to cause one or more of the at least one processor circuit to generate the global node by averaging the feature embeddings for the text segments.

17 . The at least one non-transitory machine readable storage medium of claim 11 , wherein the document image is an image of a receipt, and the text segments correspond to words in the receipt image.

18 . The at least one non-transitory machine readable storage medium of claim 11 , where a first one of the text segments is connected to (a) a second one of the text segments that is laterally adjacent the first one of the text segments in a first direction, and (b) a third one of the text segments that is laterally adjacent the first one of the text segments in a second direction.

19 . An apparatus comprising:

means for extracting node features to generate feature embeddings for text segments detected in a document, the text segments associated with bounding boxes and represented by nodes in a graph;

means for sampling edges to identify candidate edges between ones of the text segments;

means for message passing to pass the feature embeddings through graph attention (GAT) layers, the means for message passing to update the feature embeddings for the text segments with information from neighbor nodes;

means for generating confidence scores to generate an adjacency matrix for the document by determining confidence scores for the candidate edges based on the updated feature embeddings; and

means for grouping to cluster the nodes based on the adjacency matrix to group ones of the nodes that belong to a same line.

20 . The apparatus of claim 19 , wherein the text segments include text strings, the means for extracting node features to remove text strings.

21 . The apparatus of claim 19 , wherein the means for extracting node features is to extract bounding box features from the text segments, the bounding box features including left-center coordinates, right-center coordinates, and rotation angles.

22 . The apparatus of claim 21 , wherein the means for extracting node features is to concatenate ones of the bounding box features corresponding to respective text segments.

23 . The apparatus of claim 19 , wherein the means for message passing is to generate a global node by averaging the feature embeddings for the text segments and to add a global aspect to the updated feature embeddings for the text segments based on the global node.

24 . The apparatus of claim 19 , wherein the means for generating confidence scores is to apply a multi-layer perceptron model to the updated feature embeddings and the candidate edges.

25 . The apparatus of claim 19 , wherein the means for grouping is to apply a limited connected components (LCC) algorithm to the confidence scores to group the text segments by line.

Assignments (3)

Continuity (2)

References Cited (400)