SYSTEM AND METHOD FOR DATA EXTRACTION

A system and method of data extraction is disclosed. An image file of a scan of a printed information list is received at a server via a network connection. When not in portable document format, the received image file is processed with an optical character recognition (OCR) engine at the server to identify all text therein and then the processed image file is stored in a memory. When in portable document format, the image file is processed using metadata and positional data at the server to generate sentences; process the sentences to identify prices, descriptions, items, and categories; link each identified item to an associated price, description, and category; and extract and link all modifiers from identified description, and then all identified and extracted information is stored in memory. A user interface is provided to a user via the server for graphically visualizing and editing a stored processed file.

FIELD

This disclosure relates generally to a system and method for data extraction, and, more particularly, to a system and method for extracting data from printed information lists such as a restaurant menu and selectively linking the extracted data within a user interface.

BACKGROUND

Modern point of sale systems and online ordering systems for restaurants are designed to address and streamline the operational needs of the restaurant. One requirement of such systems is that the restaurant menu data (e.g., the items available and associated price of each item) must be obtained, often from printed menus. This process is time-consuming when performed by hand and is difficult to automate because of the varied nature of each restaurant's menu, in terms of both content (e.g., items available) and presentation (e.g., menu layout).

Accordingly, there is a need for a more efficient way to extract data from printed information lists such as a restaurant menu.

DETAILED DESCRIPTION

In the present disclosure, like reference numbers refer to like elements throughout the drawings, which illustrate various exemplary embodiments of the present disclosure.

The system and method of the present disclosure provides an efficient way to extract data from printed information lists such as menus and the like. This system and method combine a machine learning-based optical character recognition (OCR) engine with a specialized web-based user interface in order to provide a complete solution for quickly and efficiently extracting all the necessary information from a printed information list (menu).

Referring now toFIG.1, a system100includes an application server110coupled to a user computer120via a network130. The server110provides a user with a user interface300(FIG.3) via a web server program. A web application consisting of a menu processor program150runs in conjunction with the web server program and provides processing, as discussed in detail with respect toFIG.6, of an input file140(e.g., a scanned menu) in order to generate an output file160(e.g., a comma separated value, or CSV, file) in a form useful for digital processing (e.g., populating a database for an online ordering system or configuring a point-of-sale system).

As shown inFIG.2, the server110may include one or more central processing units (processors)210, a network interface240, at least one hard disk (HD)230, volatile (dynamic) memory250, and non-volatile memory220. The non-volatile memory220includes a basic input/output system (BIOS) used to initiate a boot of the server110. The HD230may be any type of non-volatile memory device (i.e., a non-transitory computer-readable storage medium) used to hold an operating system for a computer-based system and the term “hard disk” as used herein is intended to be broadly defined to include both electro-mechanical data storage devices and solid state drives. The HD230holds the programs (software applications, including for example a web server program and one or more web applications which run in conjunction with the web server program) which load into volatile memory250upon boot of the operating system to provide the functionality discussed herein. It is to be noted that the components are shown schematically in greatly simplified form, with only those components relevant to understanding of the embodiments being illustrated. The various components (that are identified inFIG.2) are illustrated and the arrangement of the components is presented for purposes of illustration only. It is to be noted that other arrangements with more or less components are possible without departing from the teachings of the system and method presented herein. Server110may also be implemented on a virtual machine as known in the art.

The user interface (UI)300is shown inFIG.3. UI300includes a start portion310used to initiate menu processing and load a menu, a command portion320, a menu pane330, and an extracted data pane340. Command portion320includes a first portion350for file commands or file information (e.g., current filename, cancel, file save, file save as for versioning, and file export) and a second portion360for processing commands. These commands include link361, delete362, category363, item364, price365, description366, modifier367, and auto368. These commands are discussed further below. The menu pane330displays the current menu being processed (seeFIG.4) and provides the capability to scroll across pages of a multi-page menu. The extracted data pane340shows the current status of the information being extracted from the current menu (seeFIG.5).

A sample menu400(as would appear in menu pane330inFIG.3) is shown inFIG.4. The menu400includes a header portion410, a series of categories420(antipasto and pasta are shown as examples inFIG.4), and a series of menu items430in each category. Each menu item typically includes an item name440, a price450, and a description460of the item.

A sample extracted data pane500(as would appear in extracted data pane340inFIG.3) is shown inFIG.5. Extracted data pane500is shown after the completion of processing of the sample menu400and includes categories520and menu items530for each of the categories520. Each of the menu items530includes an item name540, a price550, and a description560. Once the processing of the system and method of the present disclosure is complete, the information within extracted data pane500is saved to a file, e.g., a CSV file or equivalent.

As shown inFIG.6, a first part of the system and method of the present disclosure is a method600which automatically detects and links identified menu entities. The method600first scans a menu image automatically to look for common menu entities such as price, categories and items and provides a best guess effort to link these pieces of data together. All the information used to convert the image of the menu to a digital menu file is retained, which allows a customer to easily implement price changes by scanning an updated menu and then importing and applying any price changes.

According to the method600, a scan file of a menu is first input at step610, and then it is determined at step615if the input file is a portable document format (PDF) file or a pure image file.

If the uploaded file is an image file, processing proceeds to step660, where bounding boxes are generated with respect to all elements (e.g., words, numbers, etc.) detected within the image and extracted there from. More specifically, the processing at step660may include processing the image file with an OCR engine to identify all text-based elements present in the image file and generate/extract bounding boxes encompassing the identified elements. Then, at step655, this information (raw data) is stored in a database. This raw data is then available via the UI300to allow the user to create new annotations/associations of the detected elements without having to manually input the information.

When the uploaded file is a PDF file, processing proceeds to step620. Every page within the PDF file is processed separately, serially or, to expedite the process, in parallel. When a ten-page PDF file is processed in parallel, for example, a speed increase of up to 300 percent can be achieved. One benefit of a PDF file is that it provides access to metadata such as font name and font size. This metadata is stored along with the bounding boxes within the PDF file that are extracted at step620.

Next, at step625, the characters in the PDF file are processed one-by-one. This initial processing combines detected words into sensible sentences. This process is aided by using font metadata and positional data as menu wording is not often organized into complete sentences. In one example embodiment, the file is processed character-by-character, from left to right. Each character is evaluated to determine if it is a separator-type character. If so, a separator count is updated for identifying the descriptions later. If the character is a blank space, the next X (e.g., ten characters) are also checked to see if they are blank spaces. If so, this is considered as the end of a current sentence, and a new sentence is designated. The font and font size of each current character is compared to the font and font size of the previous character, and if either is found to be different, a new sentence is designated. This is for handling cases where an item and a description are on a same line with different fonts and/or different font sizes.

At step630, the price information is tagged by, for example, stripping every occurrence of a currency symbol (e.g., dollar sign) and then designating every number having a value less than a certain amount (e.g., 1,000) as a price. All detected numbers may be first designated as provisional prices, but the processing may remove extraneous numbers at the outset, e.g., four-digit numbers are treated as a year, a number in parentheses is considered a quantity, and a ten-digit number is considered a phone number.

At step635, descriptions are identified based on a number of separators contained therein. In particular, a ratio is calculated between the separator count and the total character count for each individual (different) font found. If the calculated ratio is above a particular threshold (e.g., 0.3), that font is considered to be a description font, and all lines with that font are designated as descriptions. The separators may be English function words (prepositions, conjunctions, etc.) or can be punctuation symbols.

At step640, all of the items are then tagged by identifying the one font (or several fonts) that appears most frequently on the page, but which is not used for either a description or a price. The category is also tagged, at this step, based, for example, on the assumption that the number of categories should not exceed the number of items. More specifically, the categories may be tagged based on a font that occurs with less frequency than a font for the items and which is not used for either a description or price. In some cases, the font frequency threshold may be reduced in order to tag more words as items in cases where the number of identified items is below a predetermined threshold. This may be particularly useful in situations where the menu does not include prices and/or descriptions. Steps620to640constitute a first identification phase.

At step645, the items and prices/descriptions are linked together by starting from the top of a current page, and then linking each item to the closest price/description to the right and/or immediately below. The same logic is then applied to link each item to an associated category. The detected categories may be used to divide the current page into columns and associate each item to a closest category at the top of and in the same column.

Finally, at step650, all noun phrases are extracted from the identified descriptions, designating them as modifiers and attaching the extracted information to an associated item. For example, consider a menu entry which reads “This delicious hamburger comes on your choice of a sesame seed bun or whole wheat bun and includes lettuce, pickle, and tomato.” All of the nouns and phrases including “sesame seed bun,” “whole wheat bun,” “lettuce,” “pickle,” and “tomato” would be designated as modifiers that are attached to the item (i.e., the hamburger). Steps645and650constitute a second entity linking phase. Once all the information is collected via steps620to650(for each page), the information is stored at step655.

A second part of the system and method of the present disclosure is a modern, responsive web user interface (i.e., UI300inFIG.3) for graphically visualizing the menu data and associations between detected menu data elements and providing user intelligent tools which allow a user to adjust and finalize the data extraction and linking before completing the information extraction. UI300is used to upload a new menu file for processing. If the uploaded menu file is in PDF format, the menu is processed by the method of flowchart600in order to extract all (or nearly all) the data from a menu, e.g., menu400inFIG.4, into the extracted data pane (FIG.5). If the uploaded menu file is not in PDF format, or if some cleanup is required in order to finalize the process, the remaining commands within pane360can be used. The link command361is used to link an item to a price, or an item to a category (e.g., by clicking on the command and then using a mouse (or the like) to draw a box around the elements to be linked within menu pane330). The delete command362is used to delete items from extracted data pane340. The category command363is used to designate a category (e.g., the category420of antipasto inFIG.4). The item command364is used to designate an item (e.g., the item440of artichoke hearts inFIG.4). The price command365is used to designate prices (e.g., the price450of $6.95 inFIG.4). The description command366is used to designate descriptions of items (e.g., the description460of “breaded, fried, or serviced with butter sauce” inFIG.4). The modifier command367is used to designate item modifiers (e.g., a modifier is an added cost item, such as “extra meatball”). Modifiers will have an associated price. The auto command367is used to initiate the auto-linking process discussed below. A user can quickly complete the extraction process for an uploaded menu in PDF format using the various tools in toolbar360, or efficiently perform the process, when the uploaded menu is in a format other than PDF. Once the process is complete, the user then exports the extracted data into a file in a suitable format, e.g., CSV, for further use in a point-of-sale system or an online ordering system.

The UI300provides adaptive threshold text selection, dynamic line detection, automated annotation suggestions, automatic linking, and user input (as discussed above).

For adaptive threshold text selection, a user draws a box with their mouse to select text in the menu pane330. The UI300then checks to determine if any text is more than X percent (e.g., X=60) contained in the drawn box. If so, that text (and only that text) is selected. If not, the threshold is reset to a lower number, e.g., thirty (30) percent, and the check is repeated. This can be done iteratively, reducing the threshold each time. The thresholds may, in some cases, be set based on machine learning, adaptively adjusting the threshold over time as more data is obtained.

For dynamic line detection, a user draws a large box with their mouse that covers multiple lines/text rows in the menu pane330. UI300determines the line position for each word of the selected text by the amount of vertical overlap of each word to existing lines (or to the first word in the upper left corner of the box which is designated as a new line). If a word has at least X percent (e.g., 60%) overlap with an existing line, it is designated as on that line. If the overlap does not meet this threshold, the text is considered a new line. Here again, the threshold may, in some cases, be set based on machine learning, adaptively adjusting the threshold over time as more data is obtained.

For automation annotation suggestions, when a user manually selects a category, item, or price, the metadata from that annotation is extracted. The extracted text metadata is then used (font, style, size, position) to determine and suggest other text that matches that type.

For automatic linking, when a user links a price to an item, the menu is scanned for unlinked prices. Based on position of the prices and unlinked items on the menu, automatic links are suggested, preferably based on prices that are below and/or to the right of the unlinked item. In other cases, a proximity factor can be used to designate a price for an unlinked item.

Although the present disclosure has been particularly shown and described with reference to the preferred embodiments and various aspects thereof, it will be appreciated by those of ordinary skill in the art that various changes and modifications may be made without departing from the spirit and scope of the disclosure. It is intended that the appended claims be interpreted as including the embodiments described herein, the alternatives mentioned above, and all equivalents thereto.