Patent Description:
Computing devices continue to become more ubiquitous to daily life. They take the form of computer desktops, laptop computers, tablet computers, hybrid computers (<NUM>-in-<NUM>), e-book readers, mobile phones, smartphones, wearable computers (including smartwatches, smart glasses/headsets), global positioning system (GPS) units, enterprise digital assistants (EDAs), personal digital assistants (PDAs), game consoles, and the like. Further, computing devices are being incorporated into vehicles and equipment, such as cars, trucks, farm equipment, manufacturing equipment, building environment control (e.g., lighting, HVAC), and home and commercial appliances.

Computing devices generally consist of at least one processing element, such as a central processing unit (CPU), some form of memory, and input and output devices. The variety of computing devices and their subsequent uses necessitate a variety of interfaces and input devices. One such input device is a touch sensitive surface such as a touch screen or touch pad wherein user input is received through contact between the user's finger or an instrument such as a pen or stylus and the touch sensitive surface. Another input device is an input surface that senses gestures made by a user above the input surface. A further input device is a position detection system which detects the relative position of either touch or non-touch interactions with a non-touch physical or virtual surface. Any of these methods of input can be used generally for drawing or inputting text. The user's handwriting is interpreted using a handwriting recognition system or method. Other systems for handwriting input to computing devices include electronic or digital pens which interact with paper, encoded surfaces or digitizing surfaces in order to have their movement relative to the surface tracked by a computing device, such as the systems provided by Anoto AB. , Leapfrog Enterprises, Inc. , and Livescribe, Inc.

Regardless of the input method used, handwriting recognition systems and methods typically involve determining the initiation of a digital ink stroke, such as when first contact with a touch sensitive surface is made (pen-down event); the termination of the stroke, such as when contact with the touch sensitive surface is ceased (pen-up event); and any movement (gestures or strokes) made between stroke initiation and termination. These determined strokes are processed to recognize and interpret the input. The type of computing device or input surface can also determine the type of handwriting recognition system or method utilized. For instance, if the input surface is large enough (such as a tablet), the user can handwrite input anywhere on or above the input surface, as if the user was writing on paper. This however adds complexity to the recognition task, because the separate elements to be recognized may be related dependent of the relative positions of the elements or may be unrelated independent of their relative positions.

For example, for structured content, such as mathematical equations, tables and matrices, the relative positioning of the handwritten elements are necessary for defining the structure. Some systems are available for dealing with the recognition of mathematical matrices, for example, <CIT> and <CIT>. These systems rely on indicative elements for recognition, such as brackets or spatial alignment, e.g., within rows and columns, and as such merely recognize the structure without regard to the content itself. Whilst such recognition is applicable to relatively simple and well-formed matrices, they are unable to deal with more complex matrices, e.g., containing complex elements like equations, sub-matrices, etc., ill-aligned matrix elements or matrices having empty element cells, e.g., row and column positions. Further, the described systems of these patents provide absolute recognition of these structures thereby influencing recognition of the content itself. A method for recognition of mathematical matrices from the relative positions of matrix elements is known from "<NPL>.

What is required is a system that recognizes matrices and like complex content structures, that do not rely on the input of specific designation elements or gestures and do not significantly increase processing time or complexity to the recognition of themselves whilst retaining sufficient recognition accuracy.

The present invention includes a method for recognizing an arrangement of multiple objects on computing devices according to claim <NUM>. The dependent claims set forth advantageous embodiments of the invention. The invention includes also a non-transitory computer readable medium according to claim <NUM> and a computing device according to claim <NUM>.

The present system and method will be more fully understood from the following detailed description of the examples thereof, taken together with the drawings. In the drawings like reference numerals depict like elements. In the drawings:.

In the following detailed description, numerous specific details are set forth by way of examples in order to provide a thorough understanding of the relevant teachings. However, it should be apparent to those of ordinary skill in the art that the present teachings may be practiced without such details. In other instances, well known methods, procedures, components, and/or circuitry have been described at a relatively high-level, without detail, in order to avoid unnecessarily obscuring aspects of the present teachings. Reference to and discussion of directional features such as up, down, above, below, lowest, highest, horizontal, vertical, etc., are made with respect to the Cartesian coordinate system as applied to the input surface on which the input to be recognized is made.

The various technologies described herein generally relate to capture, processing and management of hand-drawn and handwritten content on portable and non-portable computing devices in a manner which retains the inputted style of the content while allowing conversion to a faithful typeset or beautified version of that content. The systems and methods described herein may utilize recognition of users' natural writing and drawing styles input to a computing device via an input surface, such as a touch sensitive screen, connected to, or of, the computing device or via an input device, such as a digital pen or mouse, connected to the computing device or via a physical or virtual surface monitored by a position detection system. Whilst the various examples are described with respect to recognition of handwriting input using so-called online recognition techniques, it is understood that application is possible to other forms of input for recognition, such as offline recognition in which images rather than digital ink are recognized. The terms hand-drawing and handwriting are used interchangeably herein to define the creation of digital content by users through use of their hands either directly onto a digital or digitally connected medium or via an input tool, such as a hand-held stylus. The term "hand" is used herein to provide concise description of the input techniques, however the use of other parts of a users' body for similar input is included in this definition, such as foot, mouth and eye.

<FIG> shows a block diagram of an example computing device <NUM>. The computing device may be a computer desktop, laptop computer, tablet computer, e-book reader, mobile phone, smartphone, wearable computer, digital watch, interactive whiteboard, global positioning system (GPS) unit, enterprise digital assistant (EDA), personal digital assistant (PDA), game console, or the like. The computing device <NUM> includes components of at least one processing element, some form of memory and input and/or output (I/O) devices. The components communicate with each other through inputs and outputs, such as connectors, lines, buses, cables, buffers, electromagnetic links, networks, modems, transducers, IR ports, antennas, or others known to those of ordinary skill in the art.

The illustrated example of the computing device <NUM> has at least one display <NUM> for outputting data from the computing device such as images, text, and video. The display <NUM> may use LCD, plasma, LED, iOLED, CRT, or any other appropriate technology that is or is not touch sensitive as known to those of ordinary skill in the art. At least some of the display <NUM> is co-located with at least one input surface <NUM>. The input surface <NUM> may employ technology such as resistive, surface acoustic wave, capacitive, infrared grid, infrared acrylic projection, optical imaging, dispersive signal technology, acoustic pulse recognition, or any other appropriate technology as known to those of ordinary skill in the art to receive user input. The input surface <NUM> may be bounded by a permanent or video-generated border that clearly identifies its boundaries. Instead of, or additional to, an on-board display, the computing device <NUM> may have a projected display capability. Alternatively, the computing device may include the input surface independent of, or without, a display. In the case of a device having no display, input made via the input surface is not displayed by the computing device, rather the device acts as an input device only with the recognized input (discussed later) used for control input, for example, or displayed as content on a connected device or dedicated display device.

The computing device <NUM> may include one or more additional I/O devices (or peripherals) that are communicatively coupled via a local interface. The additional I/O devices may include input devices such as a keyboard, mouse, scanner, microphone, touchpads, bar code readers, laser readers, radio-frequency device readers, or any other appropriate technology known to those of ordinary skill in the art. Further, the I/O devices may include output devices such as a printer, bar code printers, or any other appropriate technology known to those of ordinary skill in the art. Furthermore, the I/O devices may include communications devices that communicate both inputs and outputs such as a modulator/demodulator (modem; for accessing another device, system, or network), a radio frequency (RF) or other transceiver, a telephonic interface, a bridge, a router, or any other appropriate technology known to those of ordinary skill in the art. The local interface may have additional elements to enable communications, such as controllers, buffers (caches), drivers, repeaters, and receivers, which are omitted for simplicity but known to those of skill in the art. Further, the local interface may include address, control, and/or data connections to enable appropriate communications among the other computer components.

The computing device <NUM> also includes a processor <NUM>, which is a hardware device for executing software, particularly software stored in the memory <NUM>. The processor can be any custom made or commercially available general purpose processor, a central processing unit (CPU), commercially available microprocessors including a semiconductor based microprocessor (in the form of a microchip or chipset), microcontroller, digital signal processor (DSP), application specific integrated circuit (ASIC), field programmable gate array (FPGA) or other programmable logic device, discrete gate or transistor logic, discrete hardware components, state machine, or any combination thereof designed for executing software instructions known to those of ordinary skill in the art.

The memory <NUM> can include any one or a combination of volatile memory elements (e.g., random access memory (RAM, such as DRAM, SRAM, or SDRAM)) and nonvolatile memory elements (e.g., ROM, EPROM, flash PROM, EEPROM, hard drive, magnetic or optical tape, memory registers, CD-ROM, WORM, DVD, redundant array of inexpensive disks (RAID), another direct access storage device (DASD), or any other magnetic, resistive or phase-change nonvolatile memory). The memory <NUM> can have a distributed architecture where various components are situated remote from one another but can also be accessed by the processor <NUM>. Further, the memory <NUM> may be remote from the device, such as at a server or cloud-based system, which is remotely accessible by the computing device <NUM>. The memory <NUM> is coupled to the processor <NUM>, so the processor <NUM> can read information from and write information to the memory <NUM>. In the alternative, the memory <NUM> may be integral to the processor <NUM>. In another example, the processor <NUM> and the memory <NUM> may both reside in a single ASIC or other integrated circuit.

The software in memory <NUM> includes an operating system <NUM>, an application <NUM> in the form of a non-transitory computer readable medium having a computer readable program code embodied therein, and a handwriting recognition (HWR) system <NUM>, which may each include one or more separate computer programs, each of which has an ordered listing of executable instructions for implementing logical functions. The operating system <NUM> controls the execution of the applications <NUM> and the HWR system <NUM>. The operating system <NUM> may be any proprietary operating system or a commercially or freely available operating system, such as WEBOS, WINDOWS®, MAC and IPHONE OS®, LINUX, and ANDROID. It is understood that other operating systems may also be utilized. Alternatively, the application <NUM> of the present system and method may be provided without use of an operating system.

The application <NUM> may be related to handwriting recognition as described herein, different functions, or both. The application <NUM> includes programs provided with the computing device <NUM> upon manufacture and may further include programs uploaded or downloaded into the computing device <NUM> after manufacture. Some examples include a text editor, telephone dialer, contacts directory, instant messaging facility, computer-aided design (CAD) program, email program, word processing program, web browser, and camera.

The HWR system <NUM>, with support and compliance capabilities, may be a source program, executable program (object code), script, application, or any other entity having a set of instructions to be performed. When a source program, the program needs to be translated via a compiler, assembler, interpreter, or the like, which may or may not be included within the memory, so as to operate properly in connection with the operating system. Furthermore, the handwriting recognition system with support and compliance capabilities can be written as (a) an object oriented programming language, which has classes of data and methods; (b) a procedure programming language, which has routines, subroutines, and/or functions, for example but not limited to C, C++, Pascal, Basic, Fortran, Cobol, Perl, Java, Objective C, Swift, and Ada; or (c) functional programing languages for example but no limited to Hope, Rex, Common Lisp, Scheme, Clojure, Racket, Erlang, OCaml, Haskell, Prolog, and F#. Alternatively, the HWR system <NUM> may be a method or system for communication with a handwriting recognition system remote from the device, such as server or cloud-based system, but is remotely accessible by the computing device <NUM> through communications links using the afore-mentioned communications I/O devices of the computing device <NUM>. Further, the application <NUM> and the HWR system <NUM> may operate together or be combined as a single application. Further still, the application <NUM> and/or the HWR system <NUM> may be integrated within the operating system <NUM>.

Strokes entered on or via the input surface <NUM> are processed by the processor <NUM> as digital ink. A user may enter a stroke with a finger or some instrument such as a pen or stylus suitable for use with the input surface. The user may also enter a stroke by making a gesture above the input surface <NUM> if technology that senses motions in the vicinity of the input surface <NUM> is being used, or with a peripheral device of the computing device <NUM>, such as a mouse or joystick. A stroke is characterized by at least the stroke initiation location, the stroke termination location, and the path connecting the stroke initiation and termination locations as captured by the application <NUM> and/or HWR system <NUM>. Further information such as timing, pressure, angle at a number of sample points along the path may also be captured to provide deeper detail of the strokes. Because different users may naturally write the same object, e.g., a letter, a shape, or a symbol, with slight variations, the present system accommodates a variety of ways in which each object may be entered whilst being recognized as the correct or intended object.

<FIG> is a schematic pictorial of an example of the HWR system <NUM>. The HWR system <NUM> includes stages such as preprocessing <NUM>, recognition <NUM> and output <NUM>. The preprocessing stage <NUM> processes the digital ink to achieve greater accuracy and reducing processing time during the recognition stage <NUM>. This preprocessing may include normalizing of the path connecting the stroke initiation and termination locations by applying size normalization and/or methods such as B-spline approximation to smooth the input. The preprocessed strokes are then passed to the recognition stage <NUM> which processes the strokes to recognize the objects formed thereby. The recognized objects are then output <NUM> to the display <NUM> generally as a typesetted version of the handwritten elements/characters.

The recognition stage <NUM> may include different processing elements or experts. <FIG> is a schematic pictorial of the example of <FIG> showing schematic detail of the recognition stage <NUM>. Three experts (segmentation expert <NUM>, recognition expert <NUM>, and language expert <NUM>) are illustrated which collaborate through dynamic programming to generate the output <NUM>.

The segmentation expert <NUM> defines the different ways to segment the input strokes into individual element hypotheses, e.g., alphanumeric characters and mathematical operators, text characters, individual shapes, or sub expression, in order to form expressions, e.g., mathematical equations, words, or groups of shapes. For example, the segmentation expert <NUM> may form the element hypotheses by grouping consecutive strokes of the original input to obtain a segmentation graph where each node corresponds to at least one element hypothesis and where adjacency constraints between elements are handled by the node connections.

The recognition expert <NUM> provides classification of the features extracted by a classifier <NUM> and outputs a list of element candidates with probabilities or recognition scores for each node of the segmentation graph. Many types of classifiers exist that could be used to address this recognition task, e.g., Support Vector Machines, Hidden Markov Models, or Neural Networks such as Multilayer Perceptrons, Deep, Convolutional or Recurrent Neural Networks. The choice depends on the complexity, accuracy, and speed desired for the task.

The language expert <NUM> generates linguistic meaning for the different paths in the segmentation graph using language models (e.g., grammar or semantics). The expert <NUM> checks the candidates suggested by the other experts according to linguistic information <NUM>. The linguistic information <NUM> can include a lexicon, regular expressions, etc. and is the storage for all static data used by the language expert <NUM> to execute a language model. A language model can rely on statistical information on a given language. The linguistic information <NUM> is computed off-line, with or without adaption according to the results of recognition and user interactions, and provided to the linguistic expert <NUM>. The language expert <NUM> aims at finding the best recognition path. In one example, the language expert <NUM> does this by exploring a language model such as final state automaton (FSA) representing the content of linguistic information <NUM>. In addition to the lexicon constraint, the language expert <NUM> may use a language model with statistical information modeling for how frequent a given sequence of elements appears in the specified language or is used by a specific user to evaluate the linguistic likelihood of the interpretation of a given path of the segmentation graph.

The system and method described herein make use of the HWR system <NUM> in order to recognize handwritten input to the device <NUM>. In particular, the present system and method recognizes content input within structures, such as matrices. A matrix is defined herein as the layout of several elements which are generally related, typically numbers, characters, symbols, mathematical expressions, in one or more rows and columns without the use of row and/or column designators, like lines and headers which may be present in a table, or dot points and numbers which may be present in a list, for example. Such matrices are typically used in mathematical operations, and may be input by one or more users of the device <NUM> in order to capture information and/or carry out such operations, either manually through the process of handwriting or automatically through capabilities of the application <NUM>, for example, to provide mathematical solutions (discussed later).

Unlike the afore-discussed known systems for recognizing structured input, such as matrices, the present system and method do not require users to input specific content to enable the recognition, such as brackets, nor use processes which fail to recognize matrices having more complex elements, like equations, sub-matrices, ill-aligned elements and missing elements. Further, the known systems use geometrical projection to detect rows and columns and only process entire structures for recognition, whereas the present system and method may use incremental recognition and geometrical relationships of all elements without projection. These and other features of the present system and method are now discussed.

<FIG> illustrate various examples of handwritten or hand-drawn matrices, with some shown in typeset version also. <FIG> shows handwritten input which has been made onto the input surface <NUM> of the device <NUM>, for example, rendered as a <NUM> by <NUM> (or <NUM>×<NUM>; herein the standard use of 'number of rows' × 'number of columns' is used) digital ink matrix <NUM>. The matrix <NUM> has four content elements <NUM>, being "<NUM>", <NUM> being "<NUM>", <NUM> being "<NUM>" and <NUM> being "<NUM>". The elements <NUM> and <NUM> are located in a first substantially horizontal line or row <NUM>, the elements <NUM> and <NUM> are located in a second substantially horizontal line or row <NUM>, the elements <NUM> and <NUM> are located in a first substantially vertical line or column <NUM>, and the elements <NUM> and <NUM> are located in a second substantially vertical line or column <NUM>. These content elements are contained within a first substantially vertical bracket or fence element <NUM> (e.g., on the left hand side of the first column <NUM>) and a second substantially vertical bracket or fence element <NUM> (e.g., on the right hand side of the second column <NUM>). The relative positions of the content elements in one or more rows and one or more columns provides a first characteristic of the matrix <NUM> based on at least one geometrical relationship of the recognized elements of the input and the containment of the content elements within one or more fence elements provides a second characteristic of the matrix <NUM>.

The application <NUM> of the present system and method detects the first characteristic either alone or in combination with the second characteristic in conjunction with the handwriting recognition performed by the HWR system <NUM> to determine that the input <NUM> is a matrix, and applies pre-determined and/or user settable, e.g., via a user interface (UI) on the device <NUM>, formatting to output a typeset matrix <NUM>' as shown in <FIG>. As can be seen, the typeset matrix <NUM>' has typeset versions <NUM>' to <NUM>' of the digital ink content elements <NUM> to <NUM>, respectively, still arranged in the rows <NUM>,<NUM> and columns <NUM>,<NUM>, and typeset versions <NUM>' and <NUM>' of the digital ink fence elements <NUM> and <NUM>, respectively. Accordingly, the present system and method displays the recognized matrix <NUM> in a format that is expected by users for a digital version of a matrix, for example. It is understood, that the display format of the recognized matrix made be different, and may not necessarily be in 'typeset ink', but 'beautified' digital ink; that is, the display of digital ink is retained but the natural variations of handwriting are softened or normalized by modifying the relative positions of the elements, smoothing and/or normalizing the ink elements, such as the characters themselves, etc. Whether beautification is carried out in digital ink or typeset ink (e.g., the relative positions of the matrix elements are aligned), or both, users may be provided with feedback on the recognition of the matrix and its content, such as through a preview of the recognition result or elements thereof, such as display of brackets if not already input.

The input of <FIG> is a relatively simple example of a matrix with single digit numbers as content elements relatively well-aligned in rows and columns and with relatively clear fences around that content. <FIG> shows a similarly simple <NUM>×<NUM> digital ink matrix rendered from handwritten input but with alphabetic content elements. <FIG> shows the recognized output of the present system and method as a typeset matrix. Like <FIG>, the input of <FIG> is a relatively simple example of a matrix with single alphabetic characters as content elements relatively well-aligned in rows and columns and with relatively clear fences around that content. <FIG> shows a similarly simple <NUM>×<NUM> digital ink matrix rendered from handwritten input with single digit numbers as content elements relatively well-aligned in rows and columns but surrounded or contained by differently shaped fence elements, e.g., round brackets instead of square brackets are used. The present system and method is configured to recognize these different, and other, fence forms in order to assist in the detection of matrix input. It is noted that while a fence element is the secondary characteristic of a matrix, other structures having a primary characteristic of content in rows and/or columns have similar secondary characteristics, such as drawn vertical and/or horizontal lines in tables, for example. Further, recognition of the first characteristic of the input matrix alone, that is without consideration of the second characteristic (e.g., fence elements may not even be present), may be sufficient for such detection, as described in detail later.

A slightly more complex example of a handwritten matrix is shown in <FIG>, where the input <NUM>×<NUM> matrix has double digit numbers as content elements with at least one slightly misaligned column, e.g., the left-hand column. This slight misalignment coupled with the spaces between the digits of each double digit element provide a challenge for correct recognition of the matrix being a <NUM>×<NUM> matrix, since one or more of the spaces may be considered as spaces between columns rather than between components of double digits, and as such it is conceivable that without robust recognition rules, the matrix of <FIG> could be detected as a <NUM>×<NUM> matrix of single digit elements (e.g., the "<NUM>"s of the "<NUM>", the "<NUM>" and "<NUM>" of the "<NUM>", the "<NUM>" and "<NUM>" of the "<NUM>" and the "<NUM>" and "<NUM>" of the "<NUM>" are treated separately with the first "<NUM>" of the "<NUM>" allocated to the first column, the second "<NUM>" of the "<NUM>" and the "<NUM>" of the "<NUM>" allocated to the second column, the "<NUM>" of the "<NUM>" allocated to the third column, the "<NUM>" of the "<NUM>" and the "<NUM>" of the "<NUM>" allocated to the fourth column, and the "<NUM>" of the "<NUM>" and the "<NUM>" of the "<NUM>" allocated to the fifth column. Similar results of course can occur for larger numbers. If such an incorrect recognition is made, then the consequential beautified output of the recognition would display a recognized matrix which is quite different to that intended by the user and/or any subsequent use of the data re). The present method and system employs criteria to minimize the occurrence of such incorrect matrix recognition caused by over-segmentation of the content elements which returns more columns than applicable to the matrix, which is described in detail later.

Other content element forms also provide a challenge, with or without apparent misalignment. For example, <FIG> shows a handwritten matrix having content elements as single digit numbers where some have designators, e.g., minus signs, which designate a mathematical meaning to those content elements. Such designators may be formed by a wide variety of symbols, marks or characters, and like for the large(r) number example of <FIG>, the over-segmentation of the content elements would result in these designators being allocated into columns separate from the content which they designate. Similar issues apply also to numerical content elements involving decimals as shown in the example matrix of <FIG>, and fractions as shown in the example matrix of <FIG>.

Minimization of incorrect recognition for such matrix input is provided in the present system and method by taking the recognition of the content elements themselves into account in the matrix detection process of the application <NUM>. That is, for the example matrix of <FIG> the HWR system <NUM> recognizes the designators as minus signs connected to the numbers on the immediate right hand side thereof forming "-<NUM>", "-<NUM>" and "-<NUM>", for example, such that the application <NUM> treats these as a single content element each, for the example matrix of <FIG> the HWR system <NUM> recognizes the decimal point between adjacent numbers forming "<NUM>", for example, such that the application <NUM> treats this as a single content element, and for the example matrix of <FIG> the HWR system <NUM> recognizes the divider line between adjacent numbers forming the fraction "<NUM>/<NUM>", for example, such that the application <NUM> treats this as a single content element. The manner in which the present system and method takes the recognition results into account for content structure detection is described in detail later.

Other matrix types include a mixture of content element types, such as numbers or alphabetic characters, and still other matrix content element types include abstract mathematical forms, such as subscripts and superscripts. For example, <FIG> shows a handwritten matrix having both numerical content elements, being "<NUM>", and alphanumeric content elements having alphabetic characters designated with subscript numerals. Similar to the designator examples of <FIG> described above, by taking the recognized content into account,, e.g., the HWR system <NUM> recognizes the subscripts connected to the numbers on the immediate left hand side thereof forming "a<NUM>", "a<NUM>" and "a<NUM>", the application <NUM> provides the recognized matrix shown in <FIG> displayed in typeset ink, since the subscripts are treated as part of a greater content element and not as an entire content element themselves.

<FIG> shows a similar example input matrix with content elements including subscripts. However, unlike the earlier examples, the matrix of <FIG> also includes empty content element positions or cells. That is, each row and column position is considered as a cell, such that the content element position at the first row (e.g., identified as row <NUM>, say) and the first column (e.g., identified as column <NUM>, say) corresponds to "cell <NUM>,<NUM>", for example. Other forms of identifying matrix element positions are possible however. Further, the application <NUM> and/or HWR system <NUM> may apply such identifiers to the recognized content as positional data, such as data tags, stored in the memory <NUM> of the device <NUM>, for example. The presence of such empty cells can cause another challenge for the proper recognition of two-dimensional structured content, such as matrices, since the identification of the rows and columns of the structure is conceivably only ascertainable through the consideration of elements from other rows and/or columns, not from within the same row and/or column of the element under consideration. For example, an element in an otherwise empty row (or column) is not aligned with any other element and therefore the identification of the row (or column) is made by considering non-aligned elements. The present system and method provides robust matrix detection even in such content scenarios, as described in detail later.

As described earlier, the presence of fence elements can be used to assist the recognition of a matrix, particularly when empty cells are present. This is because, if the presence of fence elements is interpreted to mean that the content surrounded, contained or otherwise adjacent (e.g., in a single fence scenario) the fence element(s) is laid out in one or more rows and one or more columns, the empty cells are considered as part of such row(s) and/or column(s) rather than as non-content. However, as also described earlier, the present system and method is capable of recognizing two-dimensional content structures without the presence or aide of structural indicators, such as fence elements for matrices. For example, <FIG> shows an example input matrix with empty cells, like the example of <FIG>, but unlike <FIG> no fence elements are present. The present system and method still correctly identifies the row and column structure of <FIG>, however the recognition result may or may not be identified as a matrix. That is, it may just be identified as two-dimensional structure, which may not have any practical consequential effect depending on any subsequent use of the recognition result. Even in such a case, selection by users to designate the recognized structure as a matrix may be provided, via the UI or the like, and/or through feedback or preview of the recognition result, such as the display of generated digital or typeset ink fence elements about the displayed content elements, for example. Such features of the present system and method are described in detail later.

Still further complexity in two-dimensional structures is possible. <FIG> shows the example <NUM>×<NUM> digital ink matrix of <FIG> with additional input. In particular, a <NUM>×<NUM> handwritten matrix is input to the immediate right of the <NUM>×<NUM> matrix followed by an equals sign, "=", and a further matrix which includes two mathematical equations. As can be seen, the rightmost matrix includes the partial result of the multiplication of the first two matrices, that is the product of row <NUM> of the <NUM>×<NUM> matrix and column <NUM> of the <NUM>×<NUM> matrix, and the product of row <NUM> of the <NUM>×<NUM> matrix and column <NUM> of the <NUM>×<NUM> matrix, where the full result would form an expected <NUM>×<NUM> matrix. <FIG> shows the recognized output in typeset form, and as can be seen the equations of the third matrix are properly recognized as belonging to cell <NUM>,<NUM> and cell <NUM>,<NUM> of a <NUM>×<NUM> matrix. This recognition results despite relatively significant overlap of the handwritten equations, as shown in <FIG>. As described earlier, this recognition is achieved by the present system and method through consideration of the recognition of the equations within the rows of third matrix and may also be recognized through consideration of the whole recognized content, e.g., the expected <NUM>×<NUM> matrix resulting from the product of a <NUM>×<NUM> matrix and a <NUM>×<NUM> matrix. These features are described in detail later.

By treating the content elements as belonging to cells of the two-dimensional structure with regard to the one or more recognized elements of each content element based on the recognition result from the HWR system <NUM>, rather than treating individual input elements individually to determine cell allocations, the present system and method is able to substantially accurately detect even more complex matrix forms. For example, <FIG> shows an example handwritten <NUM>×<NUM> matrix with each content element including relatively complex mathematical functions combining many of the afore-described content features, e.g., alphabetic characters, words, numbers, superscripts, brackets, symbols, and designators, such as a minus sign and divider lines. However, despite this complexity the present system and method detects the <NUM>×<NUM> matrix since the recognized composite parts of each recognized function is treated as a single content element belonging to a corresponding matrix cell. Further, <FIG> shows an example handwritten <NUM>×<NUM> matrix which includes nested matrices, e.g., cell <NUM>,<NUM> includes a <NUM>×<NUM> sub-matrix, cell <NUM>,<NUM> includes a <NUM>×<NUM> sub-matrix and cell <NUM>,<NUM> includes a <NUM>×<NUM> sub-matrix.

While relatively complex matrices present a challenge for detection and recognition, overly simple matrices, such as single row or single column matrices, also present a challenge. <FIG> shows an example <NUM>×<NUM> handwritten matrix and <FIG> shows an example <NUM>×<NUM> handwritten matrix. In either case since (similar to the empty cell issue discussed earlier) there is no inter-row relationship for the <NUM>×<NUM> matrix or inter-column relationship for the <NUM>×<NUM> matrix it may be difficult to determine the presence of multiple columns (or rows). This is because, only the content elements within that row or column itself are considerable for determining columns or rows, and as such the values of the distances or spaces between those elements in relation to set thresholds or the like for column or row determination are critical to that determination. Basically, less information is available such that determination is more problematic.

For example, in <FIG> depending on the threshold set for column determination, the content may be recognized as a <NUM>×<NUM> matrix with content elements "<NUM>", "<NUM>" and "<NUM>", or a <NUM>×<NUM> matrix with content elements "<NUM>" and "<NUM>", or not a matrix at all with content "<NUM>". Likewise, in <FIG> depending on the threshold set for row determination, the content may be recognized as a <NUM>×<NUM> matrix with content elements "<NUM>", "<NUM>" and "<NUM>", or a <NUM>×<NUM> matrix with content elements "<NUM>" and "<NUM>", or not a matrix at all with (vertically disposed) content "<NUM>". As discussed earlier, the secondary characteristic of a fence element(s) may assist with matrix detection per se, such that the no matrix result does not occur, but this does not inform the application <NUM> as to the internal structure of the matrix. In the present system and method, a further (or third or tertiary characteristic) can be considered with respect to certain content types to assist in this determination. For example, the space required between input elements, such as numbers, for columnar identification may be set to be less than for other input elements, such as alphabetic characters, for example. This is because, for numbers it is considered that they should be written reasonably close together when multi-digit numbers are specified. Such a criteria can also assist in more complex matrix detection, like in the example of <FIG>. Alternative, or additional, characteristics are also taken into account to properly detect such simple matrices as well as more complex matrices, which are discussed in detail later.

Furthermore, as discussed earlier, other forms of two-dimensional structures are also recognizable by the present system and method. For example, <FIG> shows a mathematical function involving a determinant of a matrix, which like a matrix has rows and columns of elemental cells. <FIG> shows such determinants nested within a matrix. Further, as can be seen (like some of the earlier examples) additional elements external to the two-dimensional structures may also be present, such as mathematical operators and functions. While such additional elements are recognized separately from the content of a matrix, for example, they may be used as context by the application <NUM> and/or HWR system <NUM> in order to guide recognition of the matrix content and the structure of the matrix, such as discussed above, for example.

As can be seen from the afore-described examples, the natural variation in hand-drawn matrices is wide and as such a system which robustly determines structural relationships, like these matrices, must be able to generally perform detection and recognition over this wide range of variations. Of course, some limits apply as to what should be correctly recognized as a matrix, for example, so that the general definition is adhered to. The present system and method therefore uses criteria and the results of recognition for correct detection of matrix structures as described below. It is noted that typically handwriting recognition only takes geometric relationships of recognized elements into account for recognition of these elements themselves, not the structure within which those elements are input. Accordingly, the present system and method uses further information to provide this recognition using a probability based approach which takes into account geometrical and language model features to provide coarse filtering of row and column candidates. These coarsely filtered matrix cell candidates may then be fine filtered using the results of the recognition process to recognize the actual matrix. In this way, the present system and method makes efficient use of recognition to detect matrices by pro-processing matrix element candidates. It is understood that the present system and method is applicable to recognition of other structural relationships of handwritten content in which the content is generally aligned in (horizontal or non-horizontal, e.g., diagonal) rows and (vertical or non-vertical, e.g., diagonal) columns such as tables, lists, etc., since the recognition of the structure is not reliant of specifically input indicators for the structure, but rather the relative geometry of the recognized content itself. These and other features of the present system and method are now discussed.

The following description of the examples illustrated in FIGS. <NUM> to <NUM> is directed to matrix recognition, however similar description applies to recognition of other structures as described above. Further, the following description is related to column detection within an input matrix, however as will be apparent the same process may be used to detect rows also, such that the cells of the matrix are detected. In either case, the process generally involves detecting alignments of elements in the substantially horizontal and vertical directions (or directions otherwise based on the direction of writing), using the recognition of the elements belonging to those alignments to provide detection of possible columns or rows of the matrix and recognition of the elements themselves. The process of row detection is performed before column detection in order to provide matrix cell detection, and therefore overall detection of a matrix. In the below described examples, the alignments are detected as part of detecting the candidate matrix columns and rows, and then the candidate columns and rows are analyzed based on the recognized content to provide the recognized matrix output. Alternatively, the detection of either the vertical and/or horizontal alignments may be performed in a different manner separate from the matrix row and/or column hypothesizing, such as by the process of detecting multi-lines, e.g., multi-equations described in <CIT> titled "System for Recognizing Multiple Object Input and Method and Product for Same" filed in the name of the present Applicant and Assignee, the entire content of which is incorporated by reference herein.

<FIG> shows an example arrangement <NUM> of multiple input ink objects <NUM> to <NUM>. The ink objects represent handwritten input elements (e.g., one or more strokes forming one or more characters, symbols, etc.) input to the input surface <NUM> of the device <NUM>, for example, and rendered as digital ink thereon. The ink objects are generally illustrated as rectangles which correspond to the extent of the handwritten elements, and as such may represent bounding boxes of the elements as recognized by the HWR system <NUM>. At this point of the matrix detection process the content of the ink objects itself is not necessarily important rather it is the correspondence of the ink objects to recognized elements that is used by the process. It is noted that in the recognition process of the HWR system <NUM> the recognition result contains a hierarchical determination of recognition candidates for each stroke and groups of the strokes based on the language model employed. The ink objects shown relate to the most probable candidate of each recognized element, however the actual recognized content and therefore the recognized elements may change if different candidates are selected, for example, by users through the UI or the like, such that the arrangement itself changes. In such a case, the matrix detection process is at least partially used again to adapt to the changed arrangement, e.g., at least for that part of the arrangement which is changed.

As can be seen, in the arrangement <NUM> the ink objects <NUM>, <NUM> and <NUM> are generally horizontally aligned with one another, the ink objects <NUM> and <NUM> are generally horizontally aligned with one another, and the ink objects <NUM>, <NUM> and <NUM> are generally horizontally aligned with one another. As such these horizontal alignments are detected by the present system and method in the manner described earlier, and in the illustrated example would most likely be determined as corresponding to potential matrix rows since no overlap between elements of the alignments is present. Further, the ink objects <NUM>, <NUM> and <NUM> are generally vertically aligned with one another, the ink objects <NUM>, <NUM> and <NUM> are generally vertically aligned with one another, and the ink objects <NUM> and <NUM> are generally vertically aligned with one another. As such these vertical alignments may be detected by the present system and method, and in the illustrated example may be determined as corresponding to potential matrix columns. Accordingly, the arrangement <NUM> may be detected as corresponding to a <NUM>×<NUM> matrix, for example. The potential columns of such a matrix are detected as in the following examples of <FIG>.

As shown in <FIG> it is known that the objects <NUM>, <NUM> and <NUM> are substantially horizontally aligned, and from the recognition result of the HWR system <NUM>, it is known that the objects are (likely) separate content elements. Accordingly, the objects <NUM>, <NUM> and <NUM> are allocated by the application <NUM> into separate potential first, second and third columns C<NUM>, C<NUM> and C<NUM>, respectively. The hypothesis of these column allocations is tested by considering whether any ink objects in the next horizontal alignment (in the present example in the downward direction) overlap vertically with the ink objects of the columns. That is, it is determined whether any ink objects overlap with the width of each of the ink objects <NUM>, <NUM> and <NUM> by projecting the extents of these objects into the next horizontal line or row. This basically accords with checking whether the ink objects <NUM> and <NUM> overlap with the ink objects <NUM>, <NUM> and <NUM> in the vertical direction. In <FIG> this is depicted by dashed line projections of the right hand and left hand boundaries of the bounding boxes of the ink objects <NUM>, <NUM> and <NUM>. As can be seen, it is determined that the ink object <NUM> overlaps with the ink object <NUM>, but the ink object <NUM> does not overlap with any of the ink objects <NUM>, <NUM> and <NUM>. Accordingly, in <FIG> it is shown that the ink object <NUM> is allocated into the first column C<NUM> with the ink object <NUM>, the ink object <NUM> remains allocated into the second column C<NUM>, the ink object <NUM> is allocated into the third column C<NUM> (which is adjusted from the allocation depicted in <FIG>), and the ink object <NUM> is allocated into a fourth column C<NUM>.

Next, the hypothesis of these column allocations is again tested by considering whether any ink objects in the next horizontal alignment overlap vertically with the ink objects of the columns. That is, it is determined whether any ink objects overlap with the width of each of the ink objects <NUM>, <NUM>, <NUM> and <NUM> by projecting the extents of these objects into the next horizontal line or row. This basically accords with checking whether the ink objects <NUM>, <NUM> and <NUM> overlap with the ink objects <NUM>, <NUM> and <NUM> in the vertical direction. In <FIG> this is depicted by dashed line projections of the right hand and left hand boundaries of the bounding boxes of the ink objects <NUM>, <NUM>, <NUM> and <NUM>. As can be seen in <FIG>, it is determined that the ink object <NUM> overlaps with the ink object <NUM>, the ink object <NUM> overlaps with both of the ink objects <NUM> and <NUM>, and the ink object <NUM> overlaps with the ink object <NUM>. Accordingly, in <FIG> it is shown that the ink object <NUM> is allocated into the first column C<NUM> with the ink objects <NUM> and <NUM>, the ink object <NUM> is allocated into the second column C<NUM> with the ink object <NUM>, the ink object <NUM> is re-allocated into the second column C<NUM> as well, and the ink object <NUM> is allocated into the third column C<NUM> with re-allocation of the ink object <NUM> from the fourth column depicted in <FIG>. This recognition result of likely columns is depicted in <FIG> in which the respective boundaries of the three columns C<NUM>, C<NUM> and C<NUM> are illustrated as dashed bounding boxes surrounding the ink objects allocated into those columns.

The re-allocation of columns depicted in <FIG> basically represents a type of fine filtering of the column detection of the present system and method, in which the detection of columns converges as closer and closer spaced content elements are considered on a row-by-row basis. This filtering may not be performed at this stage however, and all potential columns found in each step may be retained until a subsequent filtering step, which checks whether any columns should be merged. Such processing is described in detail later.

Once all possible hypotheses have been determined and tested, the application <NUM> may provide (meta)data to the ink objects, such as a tag indicting the row and column allocations, e.g., the cell allocations, recognized for the ink objects, where such data is stored with the ink objects in the memory <NUM> of the device <NUM>, for example. In this way, in any subsequent interactions with the ink objects, such as typesetting or editing, the positional relationships between the objects can be taken into account.

The above-described iterative approach of hypothesizing and testing column allocations row-by-row and through consideration of spatially adjacent content elements in those rows basically corresponds to iteratively considering <NUM>×<NUM> arrangements of objects across the entire arrangement in order to find potential columns. That is, the relative positions of two adjacent content elements in a first row are compared to two adjacent content elements in the next (second) row to determine (and adjust) column allocations. This can be performed in a number of ways. In one example, relative distances between features of the content elements are compared to a threshold to determine if the elements are potentially separated into different columns. That is, a suitable column spacing is searched for between these elements.

For example, in the present case the first column hypothesis tested is that the ink object <NUM> is in a first column and the next ink object of that row, i.e., the ink object <NUM>, is in a second column, the second column hypothesis tested is that the ink object <NUM> is in the first column and the leftmost ink object of the next row, i.e., the ink object <NUM>, is in the second column. This can be done by considering whether the horizontal distance between the right hand boundary of the bounding box of the ink object <NUM> and the left hand boundary of the bounding boxes of the ink objects <NUM> and <NUM>, say, is greater than a (first) threshold. The first threshold at its simplest is set to zero, or some non-zero (e.g., positive) value, such that any object which overlaps vertically with the object under consideration returns a negative distance. That is, measured distances like the distance between the objects <NUM> and <NUM> yield a positive value which is greater than the first threshold and measured distances like the distance between the ink objects <NUM> and <NUM> yield a negative value which is less than the first threshold. Accordingly, the application <NUM> correctly determines that it is likely that the ink objects <NUM> and <NUM> belong to different columns and the ink objects <NUM> and <NUM> do not belong to different columns.

The intra-row comparison is basically the horizontal line determination described earlier and the inter-row comparison is basically the projection of the higher leftmost object onto the next successive horizontal line described earlier, where this projection essentially forms the fourth element of the <NUM>×<NUM> arrangement being tested. It is understood that the ink objects may be defined by a different characteristic than the bounding box, such as the extent of the strokes themselves, a mean center or barycenter of the strokes making up each element, etc. Further, the distance may be measured in terms of pixels, as a function of some other parameter of the input surface <NUM>, like a guide for writing, such as an input line pattern or the like as described for example in <CIT> titled "System and Method of Digital Note Taking" filed in the name of the present Applicant and Assignee, the entire content of which is incorporated by reference herein, in terms of characteristics of the input itself, like average or mean dimensions of the handwritten objects, such as characters, the bounding boxes, etc., or a combination of such features or the like. Further still, it is understood that the iterative approach may be based on time order of entry of the strokes/elements rather than spatial order, as described above, or some combination thereof.

As such, the iterative <NUM>×<NUM> arrangement of objects is considered across the entire arrangement in order to find potential columns. In this way, localized variations in the handwritten elements of the arrangement are locally considered such that they do not influence the overall column detection across the entire arrangement. That is, the Applicant has found that users of digital applications for the handwritten input of two-dimensional structures, such a matrices, tend to skew the spacing of the structural elements as the dimensions of the structure increase, particularly in regular matrices, e.g., in which elements are of the same type. For example, for a simple <NUM>×<NUM> matrix, the relative spacing and sizing of the elements is reasonably consistent, e.g., like in <FIG>, whereas, as the matrix grows, certain local compression or extension of element spacing may result, e.g., like in <FIG> where the spacing of the elements toward the upper right hand corner is expanded and the spacing of the elements in the lower center is slightly compressed and misaligned horizontally compared to the elements at the upper left hand corner of the matrix, which is the starting position of writing.

The above-described spatial order approach is generally applicable to post-processing of the input, that is, once the user has handwritten all intended input of the matrix processing to recognize the matrix is performed through manual selection of a control element, like a menu button, or input of a gesture, like a multi-point touch on the interface surface such as a double tap, or through automatic processing, like the lapsing of a set amount of time after input, e.g., about half a second to about two seconds. Such a spatial approach is also applicable to processing during input, so-called incremental recognition, by using such triggers. The temporal approach is also applicable to either incremental or post-recognition processing. It is noted that the incremental approach using spatial and/or temporal considerations may decrease the processing time for final recognition of the input, for example, when the user indicates that conversion to typeset is desired or after a set time lapse since last input, since much of the processing has been performed during input.

It can be seen from the afore-described example that by projecting content elements of earlier rows onto later rows to determine likely columns, the presence of empty cells do not influence the detection of columns, and indeed the empty cells are correctly allocated within the columns, e.g., the empty cell between the ink objects <NUM> and <NUM> is allocated within the third column C<NUM>. This is also the case however, in input situations where there is only a single content element within a column such as in the example matrix of <FIG>. For example, <FIG> shows an alternative example arrangement <NUM>, which is the same as the arrangement <NUM> but the ink object <NUM> is not present. Accordingly, through the recognition process of the present system and method as described above, it may be determined that four columns C<NUM>, C<NUM>, C<NUM> and C<NUM> are present, as shown by dashed bounding boxes surrounding the ink objects allocated into those columns. This is because, unlike in the earlier example of the arrangement <NUM>, the ink object <NUM> does not overlap with both of the ink objects <NUM> and <NUM>, and as such these remain allocated to the second and third columns, as determined at the stage of <FIG> in the earlier example. Accordingly, in this alternative example each of the objects <NUM> and <NUM> are allocated as the only objects within their respective columns and the empty cells about these objects are also allocated into those columns.

The afore-described example 'coarse' column detection processes may cause the detection of excess vertical alignments, due to misaligned elements (from non-uniformity of handwriting), non-aligned elements (such as sign designators, e.g., plus and minus), and complex elements (such as sub-matrices, equations), as variously depicted in the examples of <FIG>. As such, as described earlier the present system and method may also process the coarse detection result with a fine detection process in which it is determined whether some of the detected possible columns should be merged. Examples of such further processing are now described with respect to <FIG>.

As described earlier, the first threshold may be set to a positive value. Such a setting basically causes a certain amount of padding to be provided about each ink object, thereby increasing the spacing required between columns for detection. Such padding can be used within the initial 'coarse' filtering or in subsequent 'fine' filtering to provide a mechanism to merge columns which are closely spaced. For example, <FIG> shows the process at the stage of the earlier example of <FIG>, but with a certain amount of padding p (designated by the circles in <FIG>) applied to the ink objects <NUM>, <NUM> and <NUM> for the alternative arrangement <NUM> of <FIG>. In this example, the value of the first threshold is set so that the padding p causes the ink object <NUM> to vertically overlap with the ink object <NUM>. Accordingly, the column detection process of the present system and method results in the column allocation as shown in <FIG>, in which the objects <NUM> and <NUM> are again allocated to the same column in a three column layout, like in the example of the arrangement <NUM>. The value of the first threshold can be arbitrarily set (and resettable by users through the UI for example), or can be automatically defined by the system and method, for example, in relation to characteristics of the handwriting, like average or mean dimensions of the handwritten objects, such as characters.

An alternative or additional mechanism for fine filtering the column allocations is to take into account the relative spacing of elements across the recognized two-dimensional structure. This can be done in several ways. <FIG> shows the arrangement <NUM> with the horizontal distances between each of the ink objects <NUM> to <NUM> illustrated. That is, the distance d<NUM> between the objects <NUM> and <NUM>, the distance d<NUM> between the objects <NUM> and <NUM>, the distance d<NUM> between the objects <NUM> and <NUM>, the distance d<NUM> between the objects <NUM> and <NUM> and the distance d<NUM> between the objects <NUM> and <NUM>. From these distances the mean, average, minimum and maximum distances between the content elements of each column can be determined. For example, the mean distance dm1 between the columns C<NUM> and C<NUM> is the mean of the distances d<NUM>, d<NUM> and d<NUM>, and the mean distance dm2 between the columns C<NUM> and C<NUM> is the mean of the distances d<NUM> and d<NUM>. Such normalized distances of the coarsely allocated columns can be compared to other parameters of the input arrangement to provide a check of the allocations, which are provided as another (second) threshold for column detection.

An example of such a parameter as the second threshold is the spacing between the detected potential columns. This spacing is shown for example in <FIG>, <FIG> and <FIG> variously as the distance dg1, dg2 and dg3 which are measured between the right and left hand boundaries of the column bounding boxes, indicated in subscript as "nL" and "nR" for each of the columns C<NUM> to C<NUM>, where "n" is the number of the column, e.g., <NUM> to <NUM>. For example, the second threshold set on this parameter for merging columns may be the maximum positive spacing, such as dg2 in <FIG>, scaled down by a pre-determined constant value, such as about <NUM> to about <NUM>, and typically about <NUM>, for example, to provide for natural variations in handwriting, which is used to compare with the mean distance of each column, e.g., the mean distances dm1 and dm2. Based on this comparison, if the mean distance is less than this second threshold value then the columns are merged. In this way, detected columns that are reasonably much less spaced than the largest spaced column, which is considered to have a high likelihood of being a column, are merged as they likely do not constitute columns.

Another example of such a parameter as the second threshold is the spacing within certain content elements. Such as the spacing between content features like alphabetic characters, words, numbers, superscripts, subscripts, brackets, symbols, and designators, such as minus and plus signs and divider lines. For example, <FIG> shows the ink object <NUM> constituted by two elements <NUM> and <NUM> separated by a distance dc1. For example, the element <NUM> may be a designator, such as a minus sign, and the element <NUM> may be a number. The present system and method may treat such adjacent elements as recognized by the HWR system <NUM> as single content elements based on rules set in the application <NUM> or the HWR system <NUM> itself may return ink objects in this way, for example, as described earlier with respect to <FIG> and <FIG>. For example, the second threshold set on this parameter for merging columns may be the maximum spacing between such elements scaled up by a pre-determined constant value, such as about <NUM> to about <NUM>, and typically about <NUM>, for example, to provide for natural variations in handwriting, and compare this value with the mean distance of each column. Based on this comparison, if the mean distance is less than this second threshold value then the columns are merged, as shown in <FIG> in which the first and second columns of <FIG> are merged because the distance dg1 is less than the scaled distance dc1, for example, so that two re-allocated columns C<NUM> and C<NUM> remain. In this way, detected columns that are reasonably spaced less than the largest spaced connected elements, like numbers with minus and plus signs, are merged as they likely do not constitute columns since it is expected that columns are spaced more widely than the inter-element spacing.

The use of the mean, or other common value, spacing of the ink objects in each coarsely detected column in the above-described merge operations based on global and maximal features of the recognized structure provide a relatively robust evaluation of any possible over-segmentation of the structure due to local variations within the structure.

As described earlier, the above-described examples of column detection can also apply to row detection, in which the vertical alignments are known from the HWR system <NUM> and used by the application <NUM> to determine the rows. Further, in the above-described examples of coarse and fine two-dimensional structure detection, the detection result can be provided as one or more probability scores for each detected column and row, which are calculated for example in terms of geometric cost for that probability result. That is, the described first and second thresholds are parameters against which the geometrical relationships of the recognized content of the handwritten input is compared to determine the geometrical cost of that recognized content being in a particular structure, such as rows and columns. This cost can be supplemented to the actual recognition results from the HWR system <NUM> and/or the structure detection result of the application <NUM> as weightings, for example, to the probability produced through the handwriting recognition results. In this way, the influence of certain recognized content on the subsequent allocation to structural elements can be easily made, such as allowing closer spacing for numerals as described earlier, merging of columns and/or rows, increasing the probability of a matrix based on the similarity of content, e.g., all numbers, characters, equations, increasing the probability score for a matrix if brackets or fence elements are detected in proximity to content elements.

The various examples described herein can be applied to forms of input for recognition other than handwriting, such as offline recognition in which images rather than digital ink are recognized, for example, the elements may be input as an image captured as a photograph of writing on paper or a whiteboard, digitally captured on an interactive smartboard, etc..

Claim 1:
A method for recognizing handwriting input comprising an arrangement of multiple ink objects representing handwritten elements in horizontal rows and vertical columns of a two-dimensional structure, the handwritten elements being input to a computing device, the method comprising:
recognizing, using online recognition techniques, a plurality of handwritten elements with respective bounding boxes;
determining geometrical relationships between the plurality of recognized handwritten elements of the handwriting input; and
allocating the recognized handwritten elements having the geometrical relationships therebetween to corresponding positions of the arrangement of the recognized handwritten elements,
wherein:
a first geometrical relationship is an overlap of projections of the plurality of bounding boxes in a vertical direction of the arrangement;
the overlap of the projections of two bounding boxes of respective ink objects on different rows is determined by considering whether the directional, horizontal distance between the projection of the right hand boundary of the bounding box of a first ink object and the projection of the left hand boundary of the bounding box of a second ink object is less than a first threshold, wherein, if the directional, horizontal distance is less than the first threshold, the two ink objects are allocated to the same column;
a second geometrical relationship is a mean distance between two detected columns; the mean distance is determined by taking the mean of the distances between pairs of ink objects that are substantially horizontally aligned and respectively allocated to the two detected columns;
if the mean distance is less than a second threshold, the two detected columns are merged.