READING ORDER WITH POINTER TRANSFORMER NETWORKS

A method including receiving an image representing a document including a plurality of layout components, identifying textual information associated with the plurality of layout components, identifying visual information associated with the plurality of layout components, combining the textual information with the visual information, and predicting a reading order of the plurality of layout components based on the combined textual information and visual information using a self-attention encoder/decoder.

FIELD

Implementations relate to detecting a reading order for a document, an image, and the like.

BACKGROUND

Reading order detection is a component of any text perception system. Reading order detection is a document image understanding task that aims at identifying a coherent ordered relation between layout components (e.g., paragraphs, summaries, images, and/or the like). Reading order detection algorithms often use a set of handcrafted reading order rules. However, these rules fail to provide satisfactory results on many examples (e.g., tables and receipts) and need to be carefully tuned or manually adapted to support different languages (e.g., right-to-left languages such as Japanese or Arabic). Reading order detection is a component that can be an element of many text-related applications (e.g., text copy/pasting, read-out-loud in text-to-speech, document translation, and/or the like).

SUMMARY

In an example implementation, a document reading order can be predicted using an encoder/decoder structure. The encoder can be configured to generate an embedding based on a sequence of the layout components in a first, random, order and the decoder can be configured to generate a sequence of the layout components in a second, reading, order based on the embedding.

In a general aspect, a device, a system, a non-transitory computer-readable medium (having stored thereon computer executable program code which can be executed on a computer system), and/or a method can perform a process with a method including receiving an image representing a document including a plurality of layout components, identifying textual information associated with the plurality of layout components, identifying visual information associated with the plurality of layout components, combining the textual information with the visual information, and predicting a reading order of the plurality of layout components based on the combined textual information and visual information using a self-attention encoder/decoder.

Implementations can include one or more of the following features, or any combination thereof.

For example, the identifying of the textual information includes extracting text-based data from the image. The extracting of the text-based data may include using a neural network configured to generate an embedding including the textual information. The neural network might be a pretrained neural network that maps textual data to an embedding, and an array may include an element including the text-based data associated with each layout component of the plurality of layout components. The identifying of the visual information may include extracting visual-based data from the image. The extracting of the visual-based data may include using a neural network configured to generate an embedding including the visual information. The neural network might be a two-dimensional convolution operation, the embedding may include an array, and the array may include an element including the visual-based data associated with each of the plurality of layout components. The neural network might include a plurality of two-dimensional convolution operations, and the embedding might include an array including an element including the visual-based data associated with an associated layout component and the visual-based data associated with at least one additional layout component. Also, the textual information might be associated with a first embedding, the visual information might be associated with a second embedding, and the combining of the textual information with the visual information might include concatenating the first embedding with the second embedding. The self-attention encoder/decoder might include: a self-attention encoder configured to generate an embedding based on a first sequence associated with the plurality of layout components, the first sequence having a first order, and a self-attention decoder configured to generate a second sequence based on the embedding, the second sequence having a second order. The self-attention encoder/decoder might include a self-attention encoder configured to: weight relationships between pairs of elements in a set, and generate an embedding for the elements. The self-attention encoder/decoder might include a self-attention encoder configured to determine an influence of each element in an embedding based on the combined textual information and visual information. The self-attention encoder/decoder might include a self-attention decoder configured to operate as an auto-regressive inference. The self-attention encoder/decoder might include a self-attention decoder configured to auto-regressively predict a next layout component in the reading order associated with the plurality of layout components. The self-attention encoder/decoder might include a self-attention encoder and a self-attention decoder, and the self-attention decoder might be configured to perform a QKV outer product between elements of the self-attention encoder and inputs to the self-attention decoder.

DETAILED DESCRIPTION

Most approaches to reading order detection use manually developed rules-based algorithms, heuristics or learned models for reading order detection. One learned approach to extracting reading order from a set of layout components (e.g., paragraphs) uses a two-stage fashion. First, a naive Bayes classifier can be used to learn the probability of any two paragraphs being successive based on a set of manually designed descriptors (e.g., based on two paragraphs' locations, geometries, types and topological relationship). These probabilities are then converted into a reading order chain(s), by first finding the most likely initial paragraphs, and progressively growing the chain following the edges with highest probabilities. While these approaches can theoretically learn adaptive reading order rules, they require a manual feature engineering and hardcoded graph heuristics to convert the pairwise probabilities into a reading order. In addition, the learned model often works on one document structure or documents with a well-known structure, such as scientific articles.

Solving these reading order detection problems can include using a machine learned (ML) model to learn to predict the reading order of a set of layout components (e.g., paragraphs, titles, summaries, images, and the like) from labeled data. The reading order detection can include reordering a set of N input layout components {P1, P2, . . . . PN} in an unspecified order into a coherent reading order {PC(i)}i=1 . . . N where C(i)ε[1, N] where P represents a layout component and C represents an order with position (e.g., index) i. Implementations can model the reading order as a sequence-to-sequence problem where the elements of the output sequence (reordered layout components) should be sampled from the input sequence. Example implementations can use a modified pointer network to select a member of the input sequence as the output. A pointer network can use attention as a pointer to select a member of an input sequence as an output. Example implementations can use a Long Short-Term Memory (LSTM) backbone or an encoder-decoder transformer module.

This approach can generalize to variable size output sets, which can enable detecting or predicting a reading order when the number of paragraphs in the input sequence is unknown a priori. This technology can improve reading order accuracy compared to existing approaches that are based on manually designed rules and approaches that learn reading order rules.

In an example implementation, the reading order can be determined using an encoder/decoder structure. The encoder can be configured to generate an embedding based on a sequence of the layout components in a first order (e.g., an input sequence) and the decoder can be configured to generate a sequence of the layout components in a second order (e.g., an output sequence or a reading order sequence) based on the embedding.FIG.1can be used to describe a data flow (or information flow) in the encoder/decoder structure.

FIG.1illustrates a block diagram of a data flow diagram according to an example implementation. As shown inFIG.1, the data flow can include a document105block, an encoder110block, a decoder115block, a sequencer120block, and an attention function125block. The document105can include any document that can be processed as an image. The document105can include at least one layout component (e.g., paragraphs, summaries, text, images, and/or the like). In an example implementation the document and/or image includes text and/or textual data. A reading order for the document105can be desired. Therefore, the document105can be referred to as an input to a system (e.g., a computing system, a system including at least a memory and a processor, and/or the like) configured to generate a reading order for the document105. An example image705-1-1,705-1-2representing the document105is shown inFIG.7.

The encoder110can be configured to receive a portion of an image as a layout component. For example, image705-1,705-1-2shows a plurality of layout components identified with boxes around each layout component. Layout component715is one example of a layout component shown in image705-1,705-1-2. The layout component(s) received by the encoder110can be initially sequenced in a random order. In other words, information associated with the layout component(s) can be stored in a data structure and labeled such that the layout component(s) are initially stored (sequenced) in a random order. The information and/or data structure can be encoded as an embedding. Therefore, the encoder110can be configured to generate an embedding including information (including the random order sequence) representing the layout component(s). An embedding can be used to represent discrete variables as continuous vectors. In other words, an embedding can be a mapping of a discrete (e.g., categorical) variable to a vector of continuous numbers.

The encoder110can be configured to categorize each layout component(s) as a discrete variable and map them to vector(s) of continuous numbers (e.g., an embedding). The encoder110can be a neural network (e.g., deep-learning, a two-dimensional (2D) convolutional neural network (CNN), LSTM, Transformer, etc.) trained (e.g., pretrained) to generate the embeddings including being trained (e.g., pretrained) to identify the layout component(s), categorize the identified layout component(s) and generate the embedding based on the categorized, identified layout component(s). Training the neural network (of the encoder110) can include using images with labeled (and, therefore, identified) layout component(s). Thus, the training may include using a supervised learning technique.

The decoder115can be configured to map the vectors of continuous numbers (e.g., vector(s) or embeddings generated by the encoder110) to a sequence of discrete variables. A discrete variable can be a variable whose value is obtained by counting. There is a fixed number of layout components associated with the document105, and each component may be associated with (or identified by) a discrete variable. Therefore, the sequence of discrete variables can represent the initial sequence of the layout component(s). The sequence of discrete variables can include information representing the layout (e.g., of the document) and an index of the layout component(s). In other words, the discrete variables can represent the layout component(s) and the sequence represents information about the order of the layout components. Initially the sequential order may be a random order. The sequence of discrete variables is the output of the decoder115. The index of any particular layout component represents the position of that component in the reading order. The output of the decoder can be referred to as a predicted reading order.

The sequencer120can be configured to generate an ordered sequence as the reading order130based on a vector(s). For example, each vector (of the embedding) can represent a plurality of features associated with a layout component. The elements of the vector can represent the probability that the layout component is the next layout component in the reading order. The element of the vector with the largest or maximum value can represent the next layout component in the ordered sequence.

The sequencer120may perform an iterative analysis of the layout components (e.g., the embedding) to identify the ordered sequence, e.g., the output sequence. An initial analysis of the vectors can identify the first layout component in the reading order, a second analysis of the remaining vectors can identify the second layout component, and so forth until all vectors in the embedding have been analyzed. After a layout component is selected for the ordered sequence, the attention function125can be a self-attention function. The attention function125can be configured to prevent positions in a sequence from attending to subsequent positions in the sequence. This masking can ensure that the predictions for position i can depend only on the known outputs at positions less than i. The attention function125can attenuate the summed features or each feature of the corresponding vector. For example, the attention function125can set the summed feature or each feature of the corresponding vector to a predetermined value (e.g., −1, 0, 1). Accordingly, a summed feature representing the selected layout component should not be a summed feature with the largest or maximum value. A stop token vector can be used to end the analysis. For example, a stop token value can be added to the vectors in the embedding and if the vector being analyzed has a value equal to the stop token value, the sequencer120can cause the analysis to end. The above-described loop is represented by the line and arrow from the attention function125block to the decoder115block. The attention function125block can use the vectors in the embedding as the basis for attenuating components or summed components. This stop token vector is represented by the line and arrow from the encoder110block to the attention function125.

In some implementations, the decoder115, sequencer120, and the attention function125can be implemented as a single process operating together. Therefore, reference to the decoder115can infer the inclusion of the sequencer120and the attention function125.

In example implementations, neural networks can be used as (or as an element of) an encoder (e.g., encoder110) and/or a decoder (e.g., decoder115). The neural network can be a recurrent neural network (RNN). The neural network can be an encoding RNN that converts the input sequence to a code that is fed to a first layer of the RNN (sometimes called the generating network). At each step, the RNN can produce a vector that modulates a content-based attention mechanism over inputs. The content-based attention mechanism can be configured to create vectors based on the similarity between features of the input (e.g., one of the layout components) and features stored in memory (e.g., associated with previously processed layout components).

Example implementations can use a softmax function (or normalized exponential function). The softmax function can be used to normalize the output of a network to a probability distribution over predicted output classes or categories. The output of the softmax function can be used to represent a class or categorical distribution. The output of the content-based attention mechanism (e.g., a feature of the vector) can be a softmax distribution with a dictionary size equal to the length of the input. The softmax distribution can be based on a function configured to generate weights for values associated with (e.g., in a distributed manner) the feature(s) of the vector. The content-based attention mechanism can be an interface connecting the encoder and decoder. The interface can be configured to provide the decoder with information from encoder hidden state(s). A hidden state or output can be produced for each layout component in the input sequence (e.g., the sequence that is not in the reading order). A hidden state can be inputs generated using data from previous time steps (e.g., input to processing of previous layout component in the input sequence).

With this framework, the model can selectively focus on valuable parts of the input sequence. In other words, the content-based attention mechanism can selectively process relevant features (e.g., features of the layout component), while ignoring others. The content-based attention mechanism can be an attention mechanism based on cosine similarity. In machine learning, cosine similarity can be a measurement that quantifies a similarity between two or more vectors (as discussed above a vector can represent a layout component). The cosine similarity can be the cosine of the angle between vectors. Mathematically, cosine similarity can be described as the division between the dot product of vectors and the product of the Euclidean norms or magnitude of each vector.

Mathematically, the SoftMax function (e.g., as described above, a function configured to generate weights) can take as input a vector z of K real numbers and normalize the vector into a probability distribution consisting of K probabilities that are proportional to the exponentials of the input numbers. The encoder/decoder described inFIG.2Acan be an example of an attention encoder (e.g., encoder110) and/or attention decoder (e.g., decoder115).

FIG.2Aillustrates a data flow block diagram according to an example implementation. As shown inFIG.2A, the data flow includes the document105block, the encoder110block, the decoder115block, the sequencer120block, and an output220block. The document105includes layout components225-1,225-2,225-3,225-4, and225-5. The document105is input to the encoder110(e.g., as an image). The layout components225-1,225-2,225-3,225-4, and225-5are also shown in a random order in bracket245together with a stop token230.

The encoder110includes a self-attention encoder205block. The self-attention encoder205can be configured to generate an embedding including a random order of the layout components225-1,225-2,225-3,225-4,225-5, and the stop token230included in bracket245. Therefore, each vector in the embedding250represents one of the layout components225-1,225-2,225-3,225-4,225-5, and the stop token230included in bracket245.

The self-attention encoder205can be a self-attention module that weights the relationships between every pair of elements in the sequence and produces a high-dimensional embedding for every element in the input, e.g., the unordered layout components within bracket245. Each embedding can be used as the Query and Key inputs to the encoder-decoder attention210included in the decoder115. The self-attention encoder205can automatically learn to discover the influence of each element in the input on the other elements. This is advantageous because using the self-attention encoder205can create richer representations than using other encoder/decoder algorithms used for sequence-to-sequence learning (e.g., long short-term memory (LSTM)).

The decoder115includes a self-attention decoder215block. The self-attention decoder215can operate in a loop, sequentially producing each element of the output. The output at time T can be based on the input at time T-1. For example, the self-attention decoder215can auto-regressively predict pointers to the inputs (e.g., the index of the elements in the input sequence). In some implementations, the output elements can correspond to positions (e.g., an index) in an input sequence rather than using attention alone on the output of the encoder110to generate a reading order. The self-attention decoder215can be configured to apply attention (e.g., using a pointer network) over the input elements to pick one as the output at each decoder step (or iteration). The element picked at each decoder step can be the predicted (e.g., auto-regressively predicted) pointer. Auto-regressively predicted pointers can be modeled as a logit distribution. Line and arrow240represent that the decoder can operate as a loop operating on the embedding (e.g., vectors) until the vector corresponding to the stop token230is reached. In other words, stop token230can be added to the embedding250(as illustrated in bracket245) and when, during the loop, the stop token is processed or operated on, the loop ends and decoder115has completed processing. During the loop, if the stop token230is the vector with the maximum value, all vectors (e.g., layout components) have been processed and the loop can end.

One or more (or each) layer of the decoder215can be a query (or matrix), keys, values, (or tokens) (QKV) outer product between the encoder inputs and the existing decoder elements as Q· K the existing decoder V elements, producing a matrix of size|decoder inputs|×|encoder inputs|, whose rows can be thought of as logits over the encoder input identifiers (IDs), and thus can be regularized with any loss used for classification. The sequencer120can use, for example, the function argmax( ) to determine the index (e.g., pointer) to the next element. The sequencer120can start with a single-element sequence consisting of an auxiliary start-of-sequence token and auto-regressively predicts each new pointer given the previous elements until a pointer to another additional token (e.g., the stop token230or stop-of-sequence) is produced.

The output of the sequencer120can generate each element of the output sequence255during each loop represented by line and arrow240. The output sequence255can represent the reading order upon completion of the loop. The iteration of the loop is described below with regard toFIG.2B. The output220shows the document105with each layout component235-1,235-2,235-3,235-4, and235-5in reading order. In other words, the first layout component predicted to be read can be layout component235-1and the last layout component predicted to be read can be layout component235-5. Referring again toFIG.7, the dotted line720in image705-1-2can pictorially represent the reading order from start S to end E based on an associated output sequence.

FIG.2Billustrates a block diagram of a sequence loop and its output according to an example implementation. The sequence loop can be the functional part of executing the data flow ofFIG.2A, e.g., the loop represented by line and arrow240. As mentioned above, the sequencer120can use, for example, the function argmax( ) to determine the index (e.g., pointer) to the next element based on, for example, a vector sum of the features representing a layout component. Using the function argmax( ) can result in the vector with the maximum value being the next element which is output to the output sequence255. For example, each vector represents the likelihood of each layout component being the next, at a particular step in time. Each element of the vector can be a numeric value(s) representing the likelihood of the corresponding layout to be the next in the output order. The element of the vector (e.g., representing a layout component) with the largest value can be (e.g., predicted as) the next layout component in the reading order.

In iteration260-1, the function (e.g., argmax( ) of the sequencer120is executed with the vector having the maximum value being the vector associated with layout component225-4. Therefore, the sequencer120outputs the next element as layout component225-4which is added to the output sequence255(in iteration260-1, the output sequence contains only the component225-4). In iteration260-2, the function of the sequencer120is executed with the vector having the maximum value being the vector associated with layout component225-1. Therefore, the sequencer120outputs the next element, layout component225-1, adding it to the output sequence255, e.g., after component225-4. In iteration260-3, the function of the sequencer120is executed with the vector having the maximum value being the vector associated with layout component225-2. Therefore, the sequencer120outputs layout component225-2as the next element, adding it to the output sequence255after component225-1.

In iteration260-4, the function of the sequencer120is executed with the vector having the maximum value being the vector associated with layout component225-3. Therefore, the sequencer120outputs layout component225-3as the next element in the output sequence255. In iteration260-5, the function of the sequencer120is executed with the vector having the maximum value being the vector associated with layout component225-5. Therefore, the sequencer120outputs the layout component225-5as the next element in the output sequence255. In iteration260-6, the function of the sequencer120is executed with the vector having the maximum value being the vector associated with the stop token230. Therefore, the sequencer120outputs the stop token230as the next element in the output sequence255. As discussed above, each vector of the embedding can represent a respective layout component. Generating these vectors can be described with regard toFIG.3.

FIG.3illustrates a data flow block diagram according to an example implementation. As shown inFIG.3, the data flow includes the document105(as input), layout components305, ordered layout components310, a component model315block, and a reading order320model block. The component model315can be configured to take the document105as input to identify at least one layout component (e.g., paragraphs, summaries, text, images, and/or the like) as layout components305. Layout components305can be strung or linked together with an embedding330(e.g., an initial or first embedding) using a layout combiner335block which is then input to the reading order model320to predict (or generate) the ordered layout components310.

The component model315can be configured to identify at least one component (e.g., paragraphs, summaries, text, images, and/or the like) based on an input image (e.g., document105). The component model315can include a neural network, for example, at least one convolution325block, or convolution operation. The convolution325can be a two-dimensional (2D) convolution operation because a 2D convolution (e.g., CNN) can be effective at capturing image information across multiple scales. The convolution325can be configured to generate an embedding330including a plurality of vectors350. The number of vectors350can be based on a number of layout components associated with (e.g., identified in) document105. Thus, each vector can correspond to a respective layout component. Although corresponding to a respective layout component, each vector350can include information (e.g., features) associated with at least one other layout component as well. In other words, each successive convolution325can generate an information influence between components in a vector. For example, each vector350can include information about its respective component and adjacent components after each successive convolution325. This information influence can help in predicting the reading order.

A convolution325can be configured to extract features from an image representing the document105. Features can be based on layout components (e.g., paragraphs, titles, summaries, images, and the like), location of the components, size of the components, color, white space (no components), position of components relative to other components, and/or the like. The features can be represented using numeric values. A convolution can have a filter (sometimes called a kernel) and a stride. For example, a filter can be a 1×1 filter (or 1×1×n for a transformation to n output channels, a 1×1 filter is sometimes called a pointwise convolution) with a stride of 1 which results in an output of a cell generated based on a combination (e.g., addition, subtraction, multiplication, and/or the like) of the features of the cells of each channel at a position of the M×M grid. In other words, a feature map having more than one depth or channel is combined into a feature map having a single depth or channel. A filter can be a 3×3 filter with a stride of 1 which results in an output with fewer cells in/for each channel of the M×M grid or feature map. The output can have the same depth or number of channels (e.g., a 3×3×n filter, where n=depth or number of channels, sometimes called a depthwise filter) or a reduced depth or number of channels (e.g., a 3×3×k filter, where k<depth or number of channels). Each channel, depth, or feature map can have an associated filter. Each associated filter can be configured to emphasize different aspects of a channel. In other words, different features can be extracted from each channel based on the filter (this is sometimes called a depthwise separable filter). The filter (sometimes called kernel or mask) can have a weight or weights. The weights can be modified or learned during a training operation, e.g., during training of the component model315. In other words, in a ML model (e.g., CNN, RNN, and the like) the weights associated with the filter (kernel or mask) can be modified during a training operation. Other filters are within the scope of this disclosure.

Another type of convolution can be a combination of two or more convolutions, sometimes called a blended convolution. For example, a convolution can be a depthwise and pointwise separable convolution. This can include, for example, a convolution in two steps. The first step can be a depthwise convolution (e.g., a 3×3 convolution). The second step can be a pointwise convolution (e.g., a 1×1 convolution). The depthwise and pointwise convolution can be a separable convolution in that a different filter (e.g., filters to extract different features) can be used for each channel or each depth of a feature map. In some implementations, a first type of convolution can be used to extract text whereas a second type of convolution can be used to extract pictures. The convolution can be (or be an element of) a combination of a recurrent neural network and a recursive neural network. The recurrent neural network can be configured to extract information from an image by processing regions of the image. The recursive neural network can be configured to process object (e.g., layout components) relationships within a scene (e.g., the document105can be, can include, or can be considered a scene).

A convolution can be linear. A linear convolution describes the output, in terms of the input, as being linear time-invariant (LTI). Convolutions can also include a rectified linear unit (ReLU). A ReLU is an activation function that rectifies the LTI output of a convolution and limits the rectified output to a maximum. A ReLU can be used to accelerate convergence (e.g., result in more efficient training of the model).

Training the component model315can include modifying weights associated with convolution325(e.g., configuring the filter(s)). The component model315can be trained (e.g., pretrained) for distinguishing between layout components and identifying relationships between layout components. Although three convolutions325are illustrated, example implementations can include using four or more than four additional convolutions325.

Each convolution325in the component model315can have an associated weight. The associated weights can be randomly initialized and then revised in each training iteration (e.g., epoch). The training can be associated with implementing (or helping to implement) distinguishing between layout components and identifying relationships between layout components. In an example implementation, a labeled input image (e.g., document105with labels indicating a preferred reading order) and the predicted reading order can be compared. A loss can be generated based on the difference between the labeled reading order and the predicted reading order. Training iterations can continue until the loss is minimized and/or until loss does not change significantly from iteration to iteration. In an example implementation, the lower the loss, the better the predicted reading order.

The component model315can be configured to generate an embedding of layout components305. The embedding of layout components305can have the same structure as an embedding330. The layout combiner335can be configured to concatenate at least one of embedding330with layout components305. For example, the first of embedding330is illustrated by layout combiner335as being concatenated with layout components305. Concatenating embedding330with layout components305can cause an emphasis of the information associated with (e.g., associated with each vector of) the embedding330.

The output of the layout combiner335is the input to the reading order model320and a self-attention encoder340as an element of the reading order model320. The self-attention encoder340can be configured to generate a context embedding345, which is input to a self-attention decoder355as an element of the reading order model320. The self-attention decoder355can be configured to generate a reading order, as ordered layout components310, based on the context embedding345. The context embedding345can include a plurality of vectors360. The number of vectors360can be based on a number of layout components associated with (e.g., identified in) document105. Each vector360can include information associated with each layout component. Each vector360can include a plurality of values (e.g., integer values) that can be, for example, summed.

The self-attention encoder340can be composed of a stack of, for example, N=6 identical layers. Each layer can have two sub-layers. The first sub-layer can be a multi-head self-attention mechanism, and the second sub-layer can be a position-wise fully connected feed-forward network. A residual connection can be applied around each of the two sub-layers, followed by layer normalization. In other words, the output of each sub-layer can be LayerNorm(x+Sublayer(x)), where Sublayer(x) is the function implemented by the sub-layer. To facilitate these residual connections, all sub-layers in the model, as well as the embedding layers, produce outputs of dimension, for example, dmodel=512. Hyperparameters can be obtained, for example, through cross-validation.

The self-attention decoder355can also be composed of a stack of, for example, N=6 identical layers. In addition to the two sub-layers in each encoder layer, the decoder can insert a third sub-layer. The third sub-layer can be configured to perform multi-head attention over the output of the encoder stack. Similar to the encoder, residual connections can be applied around each of the sub-layers, followed by layer normalization. The self-attention can be modified in the sub-layer in the decoder stack to prevent positions from attending to subsequent positions. This masking, combined with output embeddings being offset by one position can ensure that the predictions for position i can depend only on the known outputs at positions less than i. In other words, predicting the ordered layout components310based on the context embedding345(e.g., the plurality of vectors360) can be based on previously predicted vectors360(e.g., corresponding to a layout component). For example, referring toFIG.2B, iteration260-3can be influenced by the result (e.g., layout components225-4,225-1) of iteration260-1and260-2. Further, the result of iteration260-3may not be influenced by the remaining layout components or the layout components that have not been added to the output sequence255(e.g., layout components225-3,225-5).

An attention function can be described as mapping a query and a set of key-value pairs to an output, where the query, keys, values, and output can all be vectors. In encoder-decoder attention layers, the queries can come from the previous decoder layer, and the memory keys and values can come from the output of the encoder. This can allow every position in the decoder to attend over all positions in the input sequence. The output can be computed as a weighted sum of the values, where the weight assigned to each value is computed by a compatibility function of the query with the corresponding key. Self-attention, sometimes called intra-attention is an attention mechanism relating different positions of a single sequence in order to compute a representation of the sequence.

The encoder can include self-attention layers. In a self-attention layer all of the keys, values and queries can come from the same place, in this case, the output of the previous layer in the encoder. Each position in the encoder can attend to all positions in the previous layer of the encoder. Similarly, self-attention layers in the decoder can allow each position in the decoder to attend to all positions in the decoder up to and including that position.

FIG.4illustrates a block diagram of a method for generating a reading order according to an example implementation. As shown inFIG.4, in step S405an image representing a document including layout component(s) is received (e.g., received by the encoder110, for example from a scanning unit, camera or storage medium). For example, the document (e.g., document105) can include any readable document in the form of an image. The document can include at least one layout component (e.g., paragraphs, summaries, text, images, and/or the like). A reading order for the document can be desired. An example image representing the document can be image705-1,705-1-2shown inFIG.7.

In step S410, an optional step, optical character recognition (OCR) is performed on the image (e.g., for identifying and/or separating textual and visual information). For example, OCR can be the process (e.g., implemented by a computing device) of extracting data from a scanned document or image file and then converting the text into a machine-readable form, which can then be used for additional data processing. In an example implementation, OCR can be used to extract text-based data from the image. The text-based data can be extracted using a convolution. In other words, the OCR can be performed using machine learning. In some implementations the machine learning may include a neural network and/or a convolution operation (e.g., an 2D convolution operation). Therefore, the OCR can generate an embedding or text embedding including at least one array including text-based data associated with the layout components of the input image (e.g., representing a document). The text-based data of a vector can include data (e.g., numeric values) representing word similarity, related word grouping, text classification or features, document clustering (e.g., location within a document), natural language, and/or the like. For example, referring toFIG.3, the component model315can be configured to use convolution325to perform, at least, the OCR process on document105. As discussed above, component model315can be configured to identify at least one layout component (e.g., paragraphs, summaries, text, images, and/or the like). In addition, if at least one layout component includes an image including text, the component model315can be configured to perform an OCR operation on the text. For example, one or more of the plurality of vectors350of embedding330can include OCR'd text.

In step S415a visual embedding is generated based on the image. For example, the visual embedding can include at least one array including data or visual data (e.g., information and/or features associated with an image) associated with the layout components of the input image (e.g., representing a document). Visual data can include location in the document and relationship to text (e.g., a header associated with the image). Visual data can include color, type of image (e.g., thumbnail, heading, and/or the like), content of the image (e.g., human, car, graph, and/or the like), and/or the like. In example implementations, layout component(s) (e.g., sequenced in a random order) associated with the image can be identified and encoded as the visual embedding. In other words, information associated with the layout component(s) can be stored in a data structure and labeled such that the layout component(s) are sequenced in a random order. The information and/or data structure can be encoded as an embedding. Therefore, the encoder110can be configured to generate an embedding including information (including the random order sequence) representing the layout component(s). For example, referring toFIG.3, the component model315can be configured to use convolution325to generate a visual embedding(s) generated based on an image associated with document105.

An embedding can be used to represent discrete variables as continuous vectors. In other words, an embedding can be a mapping of a discrete (e.g., categorical) variable to a vector of continuous numbers. The visual embedding can be generated using a neural network (e.g., deep-learning, a two-dimensional (2D) convolutional neural network (CNN)) trained (e.g., pretrained) to generate the embeddings including being trained (e.g., pretrained) to identify the layout component(s), categorize the identified layout component(s) and generate the embedding based on the categorized, identified layout component(s). Training the neural network can include using images with labelled (and, therefore, identified) layout component(s). The training may include using a supervised learning technique.

In step S420the OCR output, if performed, is combined with the visual embedding. For example, as mentioned above, the OCR can generate an embedding that includes at least one array including text-based data associated with the layout components of the input image (e.g., representing a document). The OCR generated embedding can have the same structure as the visual embedding. Therefore, combining the OCR output with the visual embedding can generate an embedding including textual information and visual information associated with the layout components. Combining can include concatenating the textual information (e.g., array elements) with the visual information (e.g., array elements). For example, referring toFIG.3, the layout combiner335can combine the text embedding and the visual embedding.

In step S425a reading order is generated (i.e., predicted) for the layout components in the image by decoding the combined OCR output and visual embedding. For example, the combined OCR output and visual embedding can be processed by a self-attention encoder. The self-attention encoder (e.g., self-attention encoder205,340) can be configured to generate a context embedding (e.g., context embedding345). The generated context embedding can be processed by a self-attention decoder (e.g., self-attention decoder215,355). The self-attention decoder can be configured to generate the reading order, as ordered layout components, based on the context embedding as described herein with regard toFIG.3. Thus, the self-attention encoder can be self-attention encoder340, the self-attention decoder can be self-attention decoder355, and the embedding can be the context embedding345.

FIG.5illustrates a block diagram of a system according to an example implementation. In the example ofFIG.5, the system (e.g., an augmented reality system, a virtual reality system, and/or any system configured to read (e.g., text-to-voice, translate) a document) can include a computing system or at least one computing device and should be understood to represent virtually any computing device configured to perform the techniques described herein. As such, the device may be understood to include various components which may be utilized to implement the techniques described herein, or different or future versions thereof. By way of example, the system can include a processor505and a memory510(e.g., a non-transitory computer readable memory). The processor505and the memory510can be coupled (e.g., communicatively coupled) by a bus515.

The processor505may be utilized to execute instructions stored on the at least one memory510. Therefore, the processor505can implement the various features and functions described herein, or additional or alternative features and functions. The processor505and the at least one memory510may be utilized for various other purposes. For example, the at least one memory510may represent an example of various types of memory and related hardware and software which may be used to implement any one of the modules described herein.

The at least one memory510may be configured to store data and/or information associated with the device. The at least one memory510may be a shared resource. Therefore, the at least one memory510may be configured to store data and/or information associated with other elements (e.g., image/video processing or wired/wireless communication) within the larger system. Together, the processor505and the at least one memory510may be utilized to implement the techniques described herein. As such, the techniques described herein can be implemented as code segments (e.g., software) stored on the memory510and executed by the processor505. Accordingly, the memory510can include the component model315, the reading order model320, and the layout combiner335.

As discussed above, the component model315can be configured to use a document as input to identify at least one component (e.g., paragraphs, summaries, text, images, and/or the like) as layout components. The component model315can be configured to generate an embedding corresponding to textual information associated with the layout components and an embedding corresponding to visual information associated with the layout components. The layout combiner335can be configured to concatenate the embedding corresponding to textual information associated with the layout components with the embedding corresponding to visual information associated with the layout components. The reading order model320can be configured to predict (or generate) the ordered layout components based on the combined embeddings using a self-attention encoder/decoder.

Implementations can include one or more, and/or combinations thereof, of the following examples.

Example 1. A method including receiving an image representing a document including a plurality of layout components, identifying textual information associated with the plurality of layout components, identifying visual information associated with the plurality of layout components, combining the textual information with the visual information, and predicting a reading order of the plurality of layout components based on the combined textual information and visual information using a self-attention encoder/decoder.

Example 2. The method of Example 1, wherein the identifying of the textual information can include extracting text-based data from the image.

Example 3. The method of Example 2, wherein the extracting of the text-based data can include using a neural network configured to generate an embedding including the textual information.

Example 4. The method of Example 3, wherein the neural network can be a pretrained neural network that maps textual data to an embedding and an array can include an element including the text-based data associated with each layout component of the plurality of layout components.

Example 5. The method of any of Example 1 to Example 4, wherein the identifying of the visual information can include extracting visual-based data from the image.

Example 6. The method of Example 5, wherein the extracting of the visual-based data can include using a neural network configured to generate an embedding including the visual information.

Example 7. The method of Example 6, wherein the neural network can be a two-dimensional convolution operation, the embedding can include an array, and the array can include an element including the visual-based data associated with each of the plurality of layout components.

Example 8. The method of Example 6, wherein the neural network can include a plurality of two-dimensional convolution operations and the embedding can include an array including an element including the visual-based data associated with an associated layout component and the visual-based data associated with at least one additional layout component.

Example 9. The method of any of Example 1 to Example 8, wherein the textual information can be associated with a first embedding, the visual information can be associated with a second embedding, and the combining of the textual information with the visual information can include concatenating the first embedding with the second embedding.

Example 10. The method of any of Example 1 to Example 9, wherein the self-attention encoder/decoder can include a self-attention encoder configured to generate an embedding based on a first sequence associated with the plurality of layout components, the first sequence having a first order and a self-attention decoder configured to generate a second sequence based on the embedding, the second sequence having a second order.

Example 11. The method of any of Example 1 to Example 10, wherein the self-attention encoder/decoder can include a self-attention encoder configured to weight relationships between pairs of elements in a set and generate an embedding for the elements.

Example 12. The method of any of Example 1 to Example 11, wherein the self-attention encoder/decoder can include a self-attention encoder configured to determine an influence of each element in an embedding based on the combined textual information and visual information.

Example 13. The method of any of Example 1 to Example 12, wherein the self-attention encoder/decoder can include a self-attention decoder configured to operate as an auto-regressive inference.

Example 14. The method of any of Example 1 to Example 13, wherein the self-attention encoder/decoder can include a self-attention decoder configured to auto-regressively predict a next layout component in the reading order associated with the plurality of layout components.

Example 15. The method of any of Example 1 to Example 14, wherein the self-attention encoder/decoder can include a self-attention encoder and a self-attention decoder and the self-attention decoder can be configured to perform a QKV outer product between elements of the self-attention encoder and inputs to the self-attention decoder.

Example 16. A non-transitory computer-readable storage medium comprising instructions stored thereon that, when executed by at least one processor, are configured to cause a computing system to perform the method of any of Examples 1-15.

Example 17. An apparatus comprising means for performing the method of any of Examples 1-15.

The memory604stores information within the computing device600. In one implementation, the memory604is a volatile memory unit or units. In another implementation, the memory604is a non-volatile memory unit or units. The memory604may also be another form of computer-readable medium, such as a magnetic or optical disk.

The processor652can execute instructions within the computing device650, including instructions stored in the memory664. The processor may be implemented as a chipset of chips that include separate and multiple analog and digital processors. The processor may provide, for example, for coordination of the other components of the device650, such as control of user interfaces, applications run by device650, and wireless communication by device650.

Processor652may communicate with a user through control interface658and display interface656coupled to a display654. The display654may be, for example, a TFT LCD (Thin-Film-Transistor Liquid Crystal Display), and LED (Light Emitting Diode) or an OLED (Organic Light Emitting Diode) display, or other appropriate display technology. The display interface656may include appropriate circuitry for driving the display654to present graphical and other information to a user. The control interface658may receive commands from a user and convert them for submission to the processor652. In addition, an external interface662may be provided in communication with processor652, so as to enable near area communication of device650with other devices. External interface662may provide, for example, for wired communication in some implementations, or for wireless communication in other implementations, and multiple interfaces may also be used.

The memory664stores information within the computing device650. The memory664can be implemented as one or more of a computer-readable medium or media, a volatile memory unit or units, or a non-volatile memory unit or units. Expansion memory674may also be provided and connected to device650through expansion interface672, which may include, for example, a SIMM (Single In-Line Memory Module) card interface. Such expansion memory674may provide extra storage space for device650, or may also store applications or other information for device650. Specifically, expansion memory674may include instructions to carry out or supplement the processes described above, and may include secure information also. Thus, for example, expansion memory674may be provided as a security module for device650, and may be programmed with instructions that permit secure use of device650. In addition, secure applications may be provided via the SIMM cards, along with additional information, such as placing identifying information on the SIMM card in a non-hackable manner.

The memory may include, for example, flash memory and/or NVRAM memory, as discussed below. In one implementation, a computer program product is tangibly embodied in an information carrier. The computer program product contains instructions that, when executed, perform one or more methods, such as those described above. The information carrier is a computer- or machine-readable medium, such as the memory664, expansion memory674, or memory on processor652, that may be received, for example, over transceiver668or external interface662.

In some implementations, the computing devices depicted in the figure can include sensors that interface with an AR headset/HMD device690to generate an augmented environment for viewing inserted content within the physical space. For example, one or more sensors included on a computing device650or other computing device depicted in the figure, can provide input to the AR headset/HMD device690or in general, provide input to an AR space. The sensors can include, but are not limited to, a touchscreen, accelerometers, gyroscopes, pressure sensors, biometric sensors, temperature sensors, humidity sensors, and ambient light sensors. The computing device650can use the sensors to determine an absolute position and/or a detected rotation of the computing device in the AR space that can then be used as input to the AR space. For example, the computing device650may be incorporated into the AR space as a virtual object, such as a controller, a laser pointer, a keyboard, a weapon, etc. Positioning of the computing device/virtual object by the user when incorporated into the AR space can allow the user to position the computing device so as to view the virtual object in certain manners in the AR space. For example, if the virtual object represents a laser pointer, the user can manipulate the computing device as if it were an actual laser pointer. The user can move the computing device left and right, up and down, in a circle, etc., and use the device in a similar fashion to using a laser pointer. In some implementations, the user can aim at a target location using a virtual laser pointer.

In some implementations, one or more input devices included on, or connect to, the computing device650can be used as input to the AR space. The input devices can include, but are not limited to, a touchscreen, a keyboard, one or more buttons, a trackpad, a touchpad, a pointing device, a mouse, a trackball, a joystick, a camera, a microphone, earphones or buds with input functionality, a gaming controller, or other connectable input device. A user interacting with an input device included on the computing device650when the computing device is incorporated into the AR space can cause a particular action to occur in the AR space.

In some implementations, a touchscreen of the computing device650can be rendered as a touchpad in AR space. A user can interact with the touchscreen of the computing device650. The interactions are rendered, in AR headset/HMD device690for example, as movements on the rendered touchpad in the AR space. The rendered movements can control virtual objects in the AR space.

In some implementations, one or more output devices included on the computing device650can provide output and/or feedback to a user of the AR headset/HMD device690in the AR space. The output and feedback can be visual, tactical, or audio. The output and/or feedback can include, but is not limited to, vibrations, turning on and off or blinking and/or flashing of one or more lights or strobes, sounding an alarm, playing a chime, playing a song, and playing of an audio file. The output devices can include, but are not limited to, vibration motors, vibration coils, piezoelectric devices, electrostatic devices, light emitting diodes (LEDs), strobes, and speakers.

In some implementations, the computing device650may appear as another object in a computer-generated, 3D environment. Interactions by the user with the computing device650(e.g., rotating, shaking, touching a touchscreen, swiping a finger across a touch screen) can be interpreted as interactions with the object in the AR space. In the example of the laser pointer in an AR space, the computing device650appears as a virtual laser pointer in the computer-generated, 3D environment. As the user manipulates the computing device650, the user in the AR space sees movement of the laser pointer. The user receives feedback from interactions with the computing device650in the AR environment on the computing device650or on the AR headset/HMD device690. The user's interactions with the computing device may be translated to interactions with a user interface generated in the AR environment for a controllable device.

In some implementations, a computing device650may include a touchscreen. For example, a user can interact with the touchscreen to interact with a user interface for a controllable device. For example, the touchscreen may include user interface elements such as sliders that can control properties of the controllable device.

While example implementations may include various modifications and alternative forms, implementations thereof are shown by way of example in the drawings and will herein be described in detail. It should be understood, however, that there is no intent to limit example implementations to the particular forms disclosed, but on the contrary, example implementations are to cover all modifications, equivalents, and alternatives falling within the scope of the claims. Like numbers refer to like elements throughout the description of the figures.

Methods discussed above, some of which are illustrated by the flow charts, may be implemented by hardware, software, firmware, middleware, microcode, hardware description languages, or any combination thereof. When implemented in software, firmware, middleware or microcode, the program code or code segments to perform the necessary tasks may be stored in a machine or computer readable medium such as a storage medium. A processor(s) may perform the necessary tasks.

Specific structural and functional details disclosed herein are merely representative for purposes of describing example implementations. Example implementations, however, be embodied in many alternate forms and should not be construed as limited to only the implementations set forth herein.

It will be understood that when an element is referred to as being connected or coupled to another element, it can be directly connected or coupled to the other element or intervening elements may be present. In contrast, when an element is referred to as being directly connected or directly coupled to another element, there are no intervening elements present. Other words used to describe the relationship between elements should be interpreted in a like fashion (e.g., between versus directly between, adjacent versus directly adjacent, etc.).

The terminology used herein is for the purpose of describing particular implementations only and is not intended to be limiting of example implementations. As used herein, the singular forms a, an and the are intended to include the plural forms as well, unless the context clearly indicates otherwise. It will be further understood that the terms comprises, comprising, includes and/or including, when used herein, specify the presence of stated features, integers, steps, operations, elements and/or components, but do not preclude the presence or addition of one or more other features, integers, steps, operations, elements, components and/or groups thereof.

In the above illustrative implementations, reference to acts and symbolic representations of operations (e.g., in the form of flowcharts) that may be implemented as program modules or functional processes include routines, programs, objects, components, data structures, etc., that perform particular tasks or implement particular abstract data types and may be described and/or implemented using existing hardware at existing structural elements. Such existing hardware may include one or more Central Processing Units (CPUs), digital signal processors (DSPs), application-specific-integrated-circuits, field programmable gate arrays (FPGAs) computers or the like.