PatentDe  


Dokumentenidentifikation EP0712089 07.11.2002
EP-Veröffentlichungsnummer 0712089
Titel Oberfläche zur Programmierung von Dokumentanalyseanwendungen
Anmelder Canon K.K., Tokio/Tokyo, JP
Erfinder Nguyen, Thieu Quang, Placentia, California 92670, US;
Chang, Mann, Irvine, California 92715, US
Vertreter derzeit kein Vertreter bestellt
DE-Aktenzeichen 69528434
Vertragsstaaten DE, FR, GB, IT
Sprache des Dokument EN
EP-Anmeldetag 09.11.1995
EP-Aktenzeichen 953080140
EP-Offenlegungsdatum 15.05.1996
EP date of grant 02.10.2002
Veröffentlichungstag im Patentblatt 07.11.2002
IPC-Hauptklasse G06K 9/62

Beschreibung[en]

This application is being filed with an appendix of computer program listings.

A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objections to the facsimile reproduction by any one of the document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

The present invention relates to an application programming interface (API) for accessing document analysis functionality of a block selection program and for accessing the data structures resulting therefrom. More particularly, the present invention relates to a page analysis API library and a method for making a page analysis program utilizing the API library, whereby the functions in the API library can traverse and access data in a hierarchical tree structure resulting from a block selection technique.

EP-A-0567344, EP-A-0660256 and EP-A-0712088 corresponding respectively to U.S. Applications Serial No. 07/873,012, "Method And Apparatus For Character Recognition", Serial No. 08/171,720, "Method And Apparatus For Selecting Text And/Or Non-Text Blocks In A Stored Document", and Serial No. 08/338,781, "Page Analysis System", all describe block selection techniques.

Recently developed block selection techniques, such as the techniques described in U.S. Patent Application Serial Nos. 07/873,012 and 08/171,720, automatically analyze images within a document page in order to distinguish between different types of image data within the document page. The result of such a block selection technique is used to determine the type of subsequent processing to be performed on the image, such as optical character recognition (OCR), data compression, data routing, etc. For example, image data which is designated as text data will be subjected to OCR processing while image data, which is designated as picture data, would not be subjected to OCR processing. As a result, the different types of image data can be input and automatically processed without an operator's intervention.

An example of how a block selection technique operates, such as the ones referenced above, will be discussed below with respect to Figures 1-3.

Figure 1 shows the page of a representative document. Document page 101 is arranged in a two-column format. The page includes title 102, horizontal line 104, text areas 105, 106 and 107, which include lines of text data, halftone picture area 108, which includes a graphic image which is non-text, table 110, which includes text information, framed area 116, halftone picture area 121 accompanied by caption data 126, and picture areas 132 and 135 accompanied by caption data 137. According to the block selection techniques described in U.S. Patent Application Serial Nos. 07/873,012 and 08/171,720, each area of document page 101 is designated in accordance with a type of image data obtained therein and image data is then segmented based on its respective type. As the block selection program processes the document page, a hierarchical tree structure is created as shown in Figure 2.

As shown in Figure 2, hierarchical tree structure 200 contains a plurality of nodes which represent segmented blocks of image data. Each node of the tree contains feature data which defines the feature of each block of image data in the processed document page. For example, the feature data may include block location data, size data, attribute data (image type, such as text, picture, table, etc.), sub-attribute data, and child node and parent node pointers. In the present invention, child or "descendent" nodes represent image data which exist entirely within a larger block of image data. Child nodes are depicted in the hierarchical tree structure as a node branching from a parent node, such as the nodes at the same level as node 211, which branch from parent or root node 201. In addition to the feature data described above, a node which represents a text block may also contain feature data defining the block's reading orientation and reading order.

Once a hierarchical tree structure, such as hierarchical tree structure 200, has been created, it is stored in memory. Upon receiving a request to process the image data in the document image, hierarchical tree structure 200 is retrieved from memory and image data which has been blocked together is processed according to the feature data stored in its corresponding node.

In addition to using the hierarchical tree structure to process image data of a document page, the hierarchical tree structure can be used to generate and display a comprehensible format of document page 101 as shown in Figure 3. As a result, block template 301 of the document page is generated and displayed to the user based on the feature data stored in the hierarchical tree structure shown in Figure 2.

The block template of the document page directly reflects the structure of the hierarchical tree as well as the feature data stored in each node of the hierarchical tree structure. The feature data in the node is utilized to generate the block outline, location, and size. In addition, feature data in each node is used to identify the type of image data contained within the block and, if appropriate, reading order and reading orientation. For example, as shown in Figure 3, block template 301 includes text blocks 302, 304, 305 and 309, each of which corresponds to nodes 202, 204, 205 and 209, respectively. As shown, each text block includes feature data which designate the block as text and also define a block's reading order and reading orientation.

However, in order for the user to utilize functions of the block selection program or to access information in the resulting hierarchical tree structure, the user must be familiar with the low level process steps of the block selection program as well as how data is stored in the resulting hierarchical tree structure. That is, application developers, in order to interface with the block selection program, must understand the low level process steps of the block selection program as well as the tree structure and node information. Consequently, if the low level implementation of the block selection process steps and resulting hierarchical tree structure are changed, all applications which have been developed to interface at a low level interaction must be changed accordingly.

There is, therefore, a need to develop an API which includes functions and data files which insulate the user from the tree and node details such that the functions and data files of API may remain the same regardless of the low level implementation of the block selection technique used.

It is an object to the present invention to provide an application programming interface (API) for page analysis to use functions of a block selection program and to access a data structure resulting therefrom.

This object is fulfilled by computer program code according to claim 1 and a method for creating a program according to claim 12.

This summary of the invention has been provided so that the nature of the invention may be understood quickly. A more complete understanding of the invention and its advantages may be obtained by reference to the following detailed description in connection with the appended drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

  • Figure 1 is a representational view of a document page;
  • Figure 2 is a representational view of a hierarchical tree structure resulting from a block selection operation on the document page illustrated in Figure 1;
  • Figure 3 is representational view of the document page which is created based on the hierarchical tree structure shown in Figure 2;
  • Figure 4 is a perspective view showing the outward appearance of an apparatus according to the present invention;
  • Figure 5 is a block diagram of the Figure 1 apparatus;
  • Figure 6, comprising Figures 6A and 6B, is an example of an API library which includes both API functions and API data files which are utilized to create a page analysis program according to the present invention; and
  • Figure 7 is a flow diagram describing a method for creating an application program utilizing the API of the present invention.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT

Figure 4 is a view showing the outward appearance of a representative embodiment of the invention. Shown in Figure 4 is computing equipment 10, such as a MacIntosh or an IBM PC or PC compatible computer having a windowing environment, such as Microsoft Windows®. Provided with computing equipment 10 is display screen 12, such as a color monitor, keyboard 13 for entering user commands, and pointing device 14, such as a mouse for pointing to and for manipulating objects displayed on screen 12.

Computing equipment 10 includes a mass storage device such as computer disk 11 for storing data files which include document image files, in either compressed or uncompressed format, and for storing application program files which can include at least one block selection program and an application programming interface library which includes both functions and data files. Also stored in disk 11 are various hierarchical tree structure data for each document page which has been subjected to a block selection program, and various claimant page analysis programs for variously manipulating block selection functionality and for accessing data within the hierarchical tree structure.

Document image data is input by scanner 16 which scans documents or other images and provides bitmap image of those documents of computing equipment 10. The document image data may also be input into computing equipment 10 from a variety of other sources such as network interface 24 or other external devices via facsimile/modem interface 26. Printer 18 is provided for outputting process document images.

It should be understood that, although a programmable general purpose computer arrangement is shown in Figure 4, a dedicated or stand alone computer or other type of data processing equipment can be used to practice the present invention.

Figure 5 is a detailed block diagram showing the internal construction of computing equipment 10. As shown in Figure 5, computing equipment 10 includes a central processing unit (CPU) 20 interfaced with computer bus 21. Also interfaced with computer bus 21 is scanner interface 22, printer for interface 23, network interface 24, fax/modem interface 26, display interface 27, keyboard interface 28, mouse interface 29, main memory 30, and disk 11.

Main memory 30 interfaces with computer bus 21 so as to provide random access memory storage for use by CPU 20 while executing stored program instructions such as the page analyzer API or various process steps of the block selection program. More specifically, CPU 20 loads those programs from disk 11 into main memory 30 and executes those stored programs out of main memory 30.

In accordance with a user's instructions, stored application programs provide for image processing and manipulating of data. For example, a desktop processing program, such as Wordperfect® for Windows, may be activated by an operator to create, manipulate, and view documents before and after block selection has been applied. Likewise, a page analysis program may be executed to run a block selection operation to analyze various types of image data in an input document page and to display the results of the page analysis to an operator via a windowing environment.

Figures 6A and 6B illustrate an API function library and an API data file, respectively, which are used to create a page analysis program according to the present invention.

To create a program for page analysis, the contents of the API library are retrieved from disk 11. In order to get the desired resulting program, the page analysis program is created by combining both functions and data files which are in the API library. For example, as shown in Figure 6A, API function library 601 contains functions to manipulate processes of a block selection program and contains functions to access the data structures resulting therefrom. The API functions listed in API function library 601 are merely examples of some of the page analysis functions which can be utilized with the present invention. In this regard, other functions which could be used with the present invention are set forth in the appendix attached hereto.

As shown in Figure 6A, API function library 601 contains page analysis functions 602, node relationship functions 609, text block functions 614, table block functions 618, line functions 623 and picture functions 625. A page analysis program could use some or all of these functions in order to perform a desired task. Each of these functions will be discussed in greater detail below.

In the present invention, page analysis functions 602 are utilized to manipulate various block selection process steps. Generally, prior to running page analysis, the page analysis program executes InitializePageAnalysis function 603 which initializes internal variables and allocates internal memory necessary for the block selection operations called by AnalyzePage function 604 to operate. Once the memory has been allocated and variables initialized, the page analysis program executes AnalyzePage function 604 which executes a page analysis operation on a stored input page of a document. The results of AnalyzePage function 604 are stored in memory as a hierarchical tree structure. At the completion of the AnalyzePage function 604, the hierarchical tree structure is completed and a root block ID is returned. If additional pages are to be analyzed, FreePageData is executed to clear memory space which was utilized in processing the previous page.

After page analysis is completed, the program executes EndPageAnalysis function 605 to free memory allocated by the InitializePageAnalysis function 603 and to exit the page analysis application.

Page analysis function 602 also includes BlockType function 606 which, when executed, returns an attribute of a specified block, such as picture, text, and non-text. PageSkew function 607, when executed, returns a skew angle of an entire page in tenths of a degree, wherein a 0 value indicates no page skew while, for example, a return value of 11 and 22 will represent a skew degree of 1.1 and 2.2, respectively.

Once the page has been analyzed and the hierarchical tree structure has been created, utilizing various functions in the API library, the user can interrogate the hierarchical tree structure in order to determine node relationships between nodes in the tree. That is, by utilizing the NodeRelationship functions 609, the user can interrogate a node in the tree to determine its relationship to another node in the tree. Thus, for example, GetAllChildren function 610 will return block IDs of all nodes of a specified type of image data having a specified parent or root node. Utilizing GetNumberOfChildren function 612, the program will return the number of children nodes of a specified node. Similarly, utilizing the GetParent function 613, the program will return a block ID of a parent node of a specified child node.

Other functions in API function library 601 permit the user to interrogate each of the nodes more closely. For example, utilizing various features of text block functions 614, a user can obtain a first text-line, a last text-line, or the next text-line of a text block. Utilizing GetFirstTextLine function 614, the program will return a pointer which is a block ID of a first text-line in a specified text node. Likewise, utilizing the GetLastTextLine function 615, and the GetNextTextLine function 617, the program will return a pointer which is a block ID or the last text-line and the next text-line, respectively, in a text block. If the user wishes to interrogate table nodes in the hierarchical tree, the user can examine data in each table node by utilizing table block function 618 which consists of GetFirstTableCell 619, GetLastTableCell 620, GetNextTableCell 621, and GetNumberOfCellsInTable function 622.

Other API functions such as line function 623 and picture function 625 permit the user to examine information in line nodes and picture nodes, respectively, in the hierarchical tree structure.

Figure 6B illustrates an API data file which comprises parameters and definitions. The parameters and definitions contained in API data file 701 are utilized by associated API functions, defined in API function library 601. The API functions utilize their associated data files to access data in the hierarchical tree and to translate the accessed data into a user-friendly format. The parameters and definitions listed in the API data file 701 are merely examples of some of the definitions and parameters which can be utilized with the present invention. In this regard, other definitions and parameters which could be used with the present invention are set forth in the appendix attached hereto.

In the present invention, API data file 701 includes error codes 703 which are used by InitializePageAnalysis function 603, and AnalyzePage function 605 to return an error code in the case the page analysis cannot be performed due to the occurrence of a predefined event. For example, an error code may be output in the case the amount of memory required to perform a block selection operation is not sufficient or the skew of a page is too great to perform an accurate page analysis operation.

Block relationship-type definitions 704 are used by node relationship function 609 to return information regarding a relationship between specified nodes, such as parent, child, and no relation, etc. Line-type definitions 705 are accessed when returning information in response to line functions 623; and picture-type definitions 706 are accessed when returning information in response to picture functions 625.

Utilizing the API data file and API functions stored in API libraries 601 and 701, the user can create a page analysis program by combining at least one of the plural page analysis functions and at least one data file to create a desired API. For example, the user may select AnalyzePage function 603 in order to execute the block selection program stored on disk 11. Depending on the user's goal, the user may also select at least one of the plurality of relationship functions or one of the plurality of specific node feature functions, such as text block function, table block function, line block function, or picture block functions. Each of the selected functions will be coupled with its corresponding data file from API data file 701.

Upon combining desired functions and their associated data files, a page analysis program is formed. The newly created program can then be used to perform its predefined task. For example, the user's goal may be to perform optical character recognition (OCR) operation on all text blocks existing in the document page. Accordingly, the program could consist of AnalyzePage function 603 and GetAllChildrenBlock function 604 in order to return all children blocks of the root node which have a text attribute. By utilizing at least these two functions, the user can get all children blocks of the root node which are text and then submit the results of that program to an OCR processing program.

Figure 7 is a detailed flow diagram of a method by which a page analysis program can be created utilizing the API library of the present invention.

In step S701, the API library, such as the one illustrated in Figures 6A and 6B, is downloaded from disk 11 into a random access memory (not shown). The API library loaded in random access memory is displayed to the user in step S702. Depending on the user's goal, one or more functions and corresponding data structures are selected and combined from the API library to obtain a program which produces a desired result.

Thus, in step S704, the user selects one or more functions and corresponding data files from the API library. In step S705, the functions and data files are compiled to form a desired application program.

In step S707, the newly created program is stored on disk 11 and can be executed from disk 11 to perform its desired function either directly by the user or by another program.

APPENDIX Overview

The Page Analyzer SDK provides a set of functions for analyzing the logical structure of a page image in a systematic and uniform way. Abstractly, a page consists of smaller components of various types such as text, title, table, picture, frame, line or just simply noise. Some of these components can also contain smaller components. The SDK is designed and implemented to ensure usability and flexibility.

The Page Analyzer SDK accepts an image of a page, decomposes it into blocks (also called "zones"), classifies the blocks according to types, determines their reading order, and creates a tree structure in memory representing the page. The API functions allow the user to traverse the tree and utilize the information in it, but they do not allow any direct modification of the tree. Several API functions require the caller to take responsibility for memory allocation and deallocation.

Block Selection Technology Block Objects

Block selection analyzes the document and categorizes all important areas of the document. The following image block are recognized:

  • TEXT: No strict rule about how many text paragraphs are contained. The reading direction of text area could be vertical, horizontal or unknown. Text could be regular text, title, text inside the table, caption or the text associated with some picture.
  • PICTURE:
    • Line drawing picture: line art style picture. The text enclosed can also be recognized.
    • Halftone picture: the original image could be gray-scale picture, halftone picture, continuous tone picture, or photo.
  • TABLE: Any typical table with visible lines dividing the table into smaller cells. The algorithm works better for clearly scanned table in which all separator lines are visible and complete. For tables with incomplete lines after scanning, the error probability may be higher.
  • LINE: A solid line which thickness might be within the majority text thickness of the same page. Dotted line and slanted line can also be recognized. The edge of the line should be smooth enough after the scanning in order to get better recognition. There are 3 types of lines:
    • Horizontal line: A horizontal solid/dotted line.
    • Vertical line: A vertical solid/dotted line.
    • Joint line: Exact horizontal and vertical lines intersected at a 90 degree angle. Sometimes a joint line behaves as a separator which may separate different areas; therefore, we try to recognize the joint line.
  • FRAME: A frame is typically surrounded by a rectangle. The frame thickness and the density of the frame interior may affect the recognition.
  • REGION: A special type of picture entity which may contain separate image components as well as captions and/or text associated with the picture.

API Definitions & Structures

This section describes all functions and data structures used in the Page Analysis SDK.

The user should include only the file pa.h which includes other related include files.

pa.h File

This is an include file describing structures and functions for PA SDK.

Miscellaneous Definitions

PA API Error Codes

Document type

Depending on the layout style or the language, a document can be a regular, left-to-right, English type of document, or an up-and-down, Japanese or Chinese type, or a mixture of both.

Block direction type

The Page Analyzer identifies the boundaries of blocks. It also detects the orientation of each block.

Line attribute

Line type

Line Information

Picture type

Two types of pictures are identified:

  • PA_PICT_HALFTONE (grey scaled) and PA_PICT_LINEART (composed of straight and curve lines). A picture can be a stand-alone, independent picture without children blocks, or consists of smaller images and related text blocks such as captions. (Please see the function PA_GetNumberOfChildrenBlocks discussed in API function section.)

Picture Information

Basic block type

The Page Analyzer classifies blocks into the following categories.

Block relationship type

The Page Analyzer determines the relationships among blocks in the tree.

Block ID structure

The PA_BLOCK_ID structure is a handle to the block.

General Functions

Generic Block Functions

Block Hierarchy-related Functions

Line Functions

Picture Functions

Text Block Functions

Text block is a special case of blocks. Text block manipulation can be achieved by calling generic block functions directly. Text block functions are implemented as macros calling generic block functions.

Table Block Functions

Table block is a special case of blocks. Table block manipulation can be achieved by calling generic block functions directly. Table block functions, except PA GetIthTableCell, are implemented as macros calling generic block functions.

rbm.h File

This is an include file describing structures and functions for dealing with raw bitmap. They are used by Page Analysis APIs, but they are independent of those PA APIs and are thus suitable for use in other contexts. Please refer to the RBM API document for details.

The RBM_RAW_BITMAP structure keeps the information regarding the image to be analyzed. The member pImage points to an uncompressed image which is stored as a top-to-bottom concatenation of the scanlines of the image. Each scanline is stored left-to-right, 1 bit-per-pixel.

API Functions

The API functions are grouped into logical categories and described individually in this section. In each category, functions are listed in alphabetical order. Each function description also includes the information about the input parameters and function return value. For the meaning of the returned error, please refer to the defines in pa.h file in the previous section.

General Functions

The following are general functions.

PA_AnalyzePage

PA_AnalyzePage runs page analysis on a given area of a given page image. The results are stored in memory as a hierarchy (tree) of blocks. The caller should call PA_InitPageAnalyzer before calling this function. Currently, up to ten pages can be processed simultaneously. The caller has to call this function once for each page and save the root block id for each page. The caller does not have to call PA_FreePageData to free a page before processing another page. However, it is important that the caller calls PA_FreePageData passing the saved root block id to free resources used by a page once it finishes processing that page.

PA_EndPageAnalyzer

PA_EndPageAnalyzer frees memory allocated by the PA_InitPageAnalyzer function. This function does nothing if PA_InitPageAnalyzer was not called. This function should be called before exiting the application.

PA_FreePageData

PA_FreePageData frees the page analysis block hierarchy created by PA_AnalyzePage. The caller does not have to call this function before calling PA_AnalyzePage to analyze another page. Currently, up to ten pages can be processed simultaneously. However, it is important that the caller calls PA_FreePageData passing the root block id returned by PA_AnalyzePage to free resources used by a page once it finishes processing that page.

PA_InitPageAnalyzer

PA_InitPageAnalyzer initializes internal variables and allocates internal memory necessary for the Page Analyzer. This function should be called once for the entire application. Extra calls to this function are ignored. PA_EndPageAnalyzer should be called to free memory allocated by this function.

Generic Block Functions

The following functions are not specific to any block type.

PA_BlockIdIsNull

PA_BlockIdIsNull checks if a block id is the PA_NULL_BLOCK_ID.

PA_ExtractBlockImageBit1D

PA_ExtractBlockImageBit1D extracts the bitmap image of a block into a 1-D bit-per-pixel array. The user is responsible for allocating and freeing the required space. The minimum required size of the destination bitmap can be determined by calling the PA_GetBlockBoundary function.

PA_ExtractBlockImageByte2D

PA_ExtractBlockImageByte2D extracts the bitmap image of a block into a 2-D byte-per-pixel array. A 2-D byte-per-pixel array is defined as an array of pointers. Each pointer points to an array of unsigned char which representing a single row of the image.

The user is responsible for allocating and freeing the required space. The minimum required size of the destination bitmap can be determined by calling the PA_GetBlockBoundary function.

PA_GetBlockBoundary

PA_GetBlockBoundary returns the boundary of a block.

PA_GetBlockType

PA_GetBlockType returns the block type of a block.

PA_GetPageSkew

PA_GetPageSkew returns the skew angle of the entire page in tenths of a degree. A zero value indicates that the page is not skew, while, for example, the return values of 11 and 22 show the skew degree of 1.1 and 2.2, respectively.

PA_SameBlocks

PA_SameBlocks checks if two blocks are the same.

Hierarchy-related Functions PA_BlockIsComposite

PA_BlockIsComposite checks if a block contains one or more children blocks.

PA_GetAllChildrenBlocks

PA_GetAllChildrenBlocks gets all "immediate" children blocks of a specified type of a block. The caller should call PA_GetNumberOfChildrenBlocks and allocate memory for the block id array before calling this function.

PA_GetAllDescendantBlocks

PA_GetAllDescendantBlocks gets all descendant blocks of a block matching the specified type and within the specified levels.

Note that children of PA_BLOCK_TEXT blocks (e.g. PA_BLOCK TEXTLINE blocks) are not counted. The caller should call PA_GetNumberOfDescendantBlocks and allocate memory for the block id array before calling this function.

PA_GetAncestorBlock

PA_GetAncestorBlock returns the most deeply nested (closest) ancestor block which contains two specified blocks.

PA_GetBlockRelation

PA_GetBlockRelation returns the relationship of the specified first block with respect to the second block.

PA_GetDepthOfBlock

PA_GetDepthofBlock returns the depth of a block.

If the page is a white empty page (i.e. root block is PA_NULL_BLOCK_ID), 0 will be returned.

PA_GetFirstChildBlock

PA_GetFirstChildBlock returns the first child block of the specified type.

PA_GetLastChildBlock

PA_GetLastChildBlock returns the last child block of the specified type.

PA_GetNextChildBlock

PA_GetNextChildBlock returns the next child block of the specified type of the current child block. Note that the next child block is on the same level as the current child block.

PA_GetNumberOfChildrenBlocks

PA_GetNumberOfChildrenBlocks returns the number of "immediate" children blocks of the specified block type.

PA_GetNumberOfDescendantBlocks

PA_GetNumberOfDescendantBlocks returns the number of descendant blocks of the specified block type and levels of a block. Note that children of PA_BLOCK_TEXT blocks (e.g. PA_BLOCK_TEXTLINE blocks) are not counted.

PA_GetParentBlock

PA_GetparentBlock returns the parent block of a block.

PA_GetPreviousChildBlock

PA_GetPreviousChildBlock returns the previous child block of a specified type of the current child block. Note that the previous child block is on the same level as the current child block.

Text Block Functions

The following functions provide a detailed description of PA_BLOCK_TEXT blocks. A PA_BLOCK_TEXT block consists of smaller text line blocks. PA_BLOCK_TEXT blocks are important in OCR-related applications.

PA_ExtractTextLineImageByte2D

PA_ExtractTextLineImageByte2D extracts the bitmap image of a text line block into a 2-D byte-per-pixel array. A 2-D byte-per-pixel array is defined as an array of pointers. Each pointer points to an array of unsigned char which representing a single row of the image. The user is responsible for allocating and freeing the required space. The minimum required size of the destination bitmap can be determined by calling the PA_GetTextLineBoundary function.

PA_GetFirstTextLine

PA_GetFirstTextLine returns the first text line block of a text block.

PA_GetLastTextLine

PA_GetLastTextLine returns the last text line block of a text block.

PA_GetNextTextLine

PA_GetNextTextLine returns the next text line block of the current text line block. Note that the next text line block is on the same level as the current text line block.

PA_GetNumberOfTextLinesInBlock

PA_GetNumberOfTextLinesInBlock returns the number of text line blocks of a text block.

PA_GetPreviousTextLine

PA_GetPreviousTextLine returns the previous text line block of the current text line block. Note that the previous text line block is on the same level as the current text line block.

PA_GetTextLineBoundary

PA_GetTextBoundary returns the boundary information of a text line block.

Table Functions PA_GetFirstTableCell

PA_GetFirstTableCell returns the first table cell block of a specified type of a table block.

PA_GetIthTableCell

PA_GetIthTableCell returns the table cell block at the specified cell position in a text block.

PA_GetLastTableCell

PA_GetLastTableCell returns the last table cell block of a specified type of a table block.

PA_GetNextTableCell

PA_GetNextTableCell returns the next table cell block of a specified type of the current table cell block. Note that the next table cell block is on the same level as the current table cell block.

PA_GetNumberOfCellsInTable

PA_GetNumberOfCellsInTable returns the number of table cell blocks of the specified block type of a table block.

PA_GetPreviousTableCell

PA_GetPreviousTableCell returns the previous table cell block of a specified type of the current table cell block. Note that the previous table cell block is on the same level as the current table cell block.

Line Functions

The following function is provided for PA_BLOCK_LINE blocks.

PA_GetLineInfo

PA_GetLineInfo returns a structure of line information such as line type, line attribute, line slant angle, etc.

Picture Functions

The following function is provide for PA_BLOCK_PICT blocks.

PA_GetPictureInfo

PA_GetPictureInfo returns a structure of picture information such as picture type.


Anspruch[de]
  1. Computerprogrammcode, der derart konfiguriert ist, daß er als eine Schnittstelle mit einem Blockauswahlprogramm fungiert, um das Blockauswahlprogramm zur Analyse der Struktur einer Dokumentseite zu veranlassen, wobei der Schnittstellenprogrammcode umfaßt:
    • einen Seitenanalyseprogrammcode, der zur Manipulation der Funktionalität des Blockauswahlprogramms einschließlich Funktionen zur Analyse einer Dokumentseite zur Identifizierung von Textbereichen, Nicht-Textbereichen und Bitmaskenbildbereichen in der Dokumentseite, zur Erzeugung einer hierarchischen Baumstruktur entsprechend der analysierten Dokumentseite und zur Rückgabe eines Zeigers auf einen Wurzelknoten der analysierten Seite konfiguriert ist; und
    • einen Programmcode zum Zugriff auf eine hierarchische Baumstruktur, der zum Durchlaufen der durch das Blockauswahlprogramm erzeugten hierarchischen Baumstruktur und zur Lokalisierung gewünschter Knoten in der hierarchischen Baumstruktur konfiguriert ist.
  2. Computerprogrammcode nach Anspruch 1, wobei der Programmcode zum Zugriff auf eine hierarchische Baumstruktur ferner einen Programmcode umfaßt, der zur Rückgabe zumindest eines Zeigers auf zumindest einen gewünschten Knoten konfiguriert ist.
  3. Computerprogrammcode nach Anspruch 2, ferner mit einem Knotenabfrageprogrammcode zur Abfrage des zumindest einen Zeigers zum Erhalten von Eigenschaftsinformationen des dazu entsprechenden zumindest einen gewünschten Knotens.
  4. Computerprogrammcode nach Anspruch 3, wobei der Knotenabfrageprogrammcode einen Textblockabfrageprogrammcode umfaßt, wobei der Textblockabfrageprogrammcode einen Programmcode zur Rückgabe eines Zeigers auf eine erste Textzeile in einem gewünschten Textblock, zur Rückgabe eines Zeigers auf eine letzte Textzeile des gewünschten Textblocks, Rückgabe eines Zeigers auf eine nächste Textzeile in dem gewünschten Textblock, zur Rückgabe einer Anzahl von Textzeilen in dem gewünschten Textblock, zur Rückgabe eines Zeigers auf eine vorhergehende Textzeile in dem gewünschten Textblock, zur Rückgabe von Grenzinformationen einer Textzeile in dem gewünschten Textblock und zur Extraktion einer zweidimensionalen regelmäßigen Anordnung des Bitmaskenbilds der Textzeile in dem gewünschten Textblock aufweist.
  5. Computerprogrammcode nach Anspruch 3, wobei der Knotenabfrageprogrammcode einen Bildblockabfrageprogrammcode umfaßt, wobei der Bildblockabfrageprogrammcode einen Programmcode zur Rückgabe von Informationen bezüglich des Bildtyps eines gewünschten Bildblocks aufweist.
  6. Computerprogrammcode nach Anspruch 3, ferner mit einer Datendatei, wobei die Datendatei Definitionen und Parameter aufweist, die durch den Seitenanalyseprogrammcode zur Manipulation des Blockauswahlprogrammcodes, durch den Programmcode zum Zugriff auf eine hierarchische Baumstruktur zum Durchlaufen des hierarchischen Baums und zur Lokalisierung gewünschter Knoten, und durch den Knotenabfrageprogrammcode zur Abfrage der gewünschten Knoten verwendet werden.
  7. Computerprogrammcode nach Anspruch 3, wobei der Knotenabfrageprogrammcode einen Linienblockabfrageprogrammcode umfaßt, wobei der Linienblockabfrageprogrammcode einen Programmcode zur Rückgabe von Informationen bezüglich des Linientyps und anderer Eigenschaften eines gewünschten Linienblocks aufweist.
  8. Computerprogrammcode nach Anspruch 1 wobei der Seitenanalyseprogrammcode einen Initialisierungsprogrammcode zur Initialisierung des Blockauswahlprogramms durch eine Einstellung interner Variablen und durch eine Belegung von Speicher zur Verarbeitung und Speicherung von Ergebnissen davon, einen Ausführungsprogrammcode zur Ausführung des Blockauswahlprogramms bei einem eingegebenen Dokumentbild und einen Beendungsprogrammcode zur Freigabe von durch den Initialisierungsprogrammcode eingestelltem belegtem Speicher und zur Beendung des Ausführungsprogrammcodes umfaßt.
  9. Computerprogrammcode nach Anspruch 3, wobei der Programmcode zum Zugriff auf eine hierarchische Baumstruktur einen Knotenbeziehungsprogrammcode, der einen Programmcode zur Abfrage einer Beziehung zwischen Knoten und zur Angabe, wie tief ein Knoten in einem Baum verschachtelt ist, aufweist, einen Textknotenprogrammcode, der einen Programmcode zur Abfrage zumindest eines einen Textblock darstellenden Knotens aufweist, einen Tabellenknotenprogrammcode zur Abfrage zumindest eines einen Tabellenblock darstellenden Knotens, einen Bildprogrammcode zur Rückgabe eines Typs eines durch einen Bildknoten dargestellten Bilds und einen Linienprogrammcode zur Rückgabe eines Typs einer Linie und anderer durch einen Linienknoten dargestellter Eigenschaften umfaßt.
  10. Computerprogrammcode nach Anspruch 8, wobei der Tabellenknotenprogrammcode einen Programmcode zur Rückgabe eines Zeigers auf einen ersten Tabellenzellenblock eines bestimmten Tabellenblocks, zur Rückgabe einer Tabellenzelle einer bestimmten Zellenposition in einem Tabellenblock, zur Rückgabe eines Zeigers auf einen letzten Tabellenzellenblock eines bestimmten Tabellenblocks, zur Rückgabe eines nächsten Tabellenzellenblocks eines bestimmten derzeitigen Tabellenzellenblocks, zur Rückgabe einer Anzahl von Tabellenzellenblöcken eines bestimmten Blocktyps eines Tabellenblocks und zur Rückgabe eines Zeigers auf einen vorhergehenden Tabellenzellenblock eines bestimmten derzeitigen Tabellenzellenblocks aufweist.
  11. Computerprogrammcode nach einem der Ansprüche 2 bis 4, wobei der zurückgegebene Zeiger eine Blockidentifizierung ist.
  12. Verfahren zur Erzeugung eines Seitenanalyseprogramms, wobei das Verfahren eine zur Manipulation eines Blockauswahlprogramms und zum Zugriff auf eine sich daraus ergebende Datenstruktur konfigurierte Seitenanalyseschnittstelle verwendet, wobei das Verfahren die Schritte umfaßt:
    • Speichern einer Vielzahl von Seitenanalyseverarbeitungseinrichtungen in einem Speicher, die zur Manipulation einer Blockauswahlprogrammfunktionalität einschließlich einer Funktionalität zur Analyse einer Dokumentseite, zur Erzeugung einer hierarchischen Baumstruktur entsprechend der analysierten Dokumentseite und zur Rückgabe eines Zeigers auf einen Wurzelknoten der hierarchischen Baumstruktur, die die analysierte Seite darstellt, und zur Speicherung einer Vielzahl von Einrichtungen zum Zugriff auf eine hierarchische Baumstruktur zum Durchlaufen des Baums und zur Lokalisierung gewünschter Knoten in dem Baum konfiguriert sind;
    • Auswählen zumindest einer der Vielzahl von Seitenanalyseverarbeitungseinrichtungen und zumindest einer der Vielzahl von Einrichtungen zum Zugriff auf eine hierarchische Baumstruktur; und
    • Kombinieren der zumindest einen der Vielzahl von Seitenanalyseverarbeitungseinrichtungen und der zumindest einen der Vielzahl von Einrichtungen zum Zugriff auf eine hierarchische Baumstruktur, um das Seitenanalyseprogramm zu erzeugen.
  13. Verfahren zur Erzeugung eines Seitenanalyseprogramms nach Anspruch 12, wobei das erzeugte Seitenanalyseprogramm auch zur Rückgabe zumindest einen Zeigers auf zumindest einen gewünschten Knoten in der Lage ist.
  14. Verfahren zur Erzeugung eines Seitenanalyseprogramms nach Anspruch 12, ferner mit den Schritten des Speicherns einer Vielzahl von Datendateien in einem Speicher, die Datendateien aufweisen, die mit der Vielzahl von Seitenanalysefunktionalitäten und der Vielzahl von Einrichtungen zum Zugriff auf einen hierarchischen Baum verknüpft sind, und des Kombinierens zumindest einer der Vielzahl von Datendateien, die mit der zumindest einen ausgewählten der Vielzahl von Seitenanalysefunktionalitäten verknüpft ist, und des Kombinierens zumindest einer der Vielzahl von Datendateien, die mit der zumindest einen ausgewählten der Vielzahl von Einrichtungen zum Zugriff auf eine hierarchische Baumstruktur verknüpft ist.
  15. Computerprogrammerzeugnis, das Computerprogrammcode nach einem der Ansprüche 1 bis 11 speichert.
  16. Computerprogrammerzeugnis, das Computerprogrammcode speichert, der zur Durchführung eines Verfahrens nach einem der Ansprüche 12 bis 14, wenn er auf einer Berechnungseinrichtung laufen gelassen wird, wirksam ist.
Anspruch[en]
  1. Computer program code configured to act as an interface with a block selection program so as to cause the block selection program to analyze the structure of a document page, the interface program code comprising:
    • page analysis program code configured to manipulate functionality of the block selection program including functions to analyze a document page in order to identify text regions, non-text regions and bitmap image regions in the document page, to create a hierarchical tree structure corresponding to the analyzed document page, and to return a pointer to a root node of the analyzed page; and
    • hierarchical tree structure accessing program code configured to traverse the hierarchical tree structure generated by the block selection program, and to locate desired nodes in the hierarchical tree structure.
  2. Computer program code according to Claim 1, wherein the hierarchical tree structure accessing program code further includes program code configured to return at least one pointer to at least one desired node.
  3. Computer program code according to Claim 2, further comprising node interrogating program code for interrogating the at least one pointer to obtain attribute information of the at least one desired node corresponding thereto.
  4. Computer program code according to Claim 3, wherein the node interrogating program code comprises text block interrogating program code, said text block interrogating program code including program code to return a pointer to a first text line in a desired text block, to return a pointer to a last text line of the desired text block, return a pointer to a next text line in the desired text block, to return a number of text lines in the desired text block, to return a pointer to a previous text line in the desired text block, to return boundary information of a text line in the desired text block, and to extract a two-dimensional array of the bitmap image of the text line in the desired text block.
  5. Computer program code according to Claim 3, wherein the node interrogating program code comprises picture block interrogating program code, said picture block interrogating program code including program code to return information regarding picture type of desired picture block.
  6. Computer program code according to Claim 3, further comprising a data file, said data file including definitions and parameters which are utilized by the page analysis program code to manipulate the block selection program code, by the hierarchical tree structure accessing program code to traverse the hierarchical tree, and to locate desired nodes, and by the node interrogating program code for interrogating the desired nodes.
  7. Computer program code according to Claim 3, wherein the node interrogating program code comprise line block interrogating program code, said line block interrogating program code including program code to return information regarding line type and other attributes of a desired line block.
  8. Computer program code according to Claim 1, wherein the page analysis program code comprises initialization program code to initialize the block selection program by setting internal variables and by allocating memory for processing and storing results thereof, execution program code for executing the block selection program on an input document image, and termination program code to free allocated memory set by the initialization program code and to terminate the execution program code.
  9. Computer program code according to Claim 3, wherein the hierarchical tree structure accessing program code comprises node relationship program code which includes program code for interrogating a relationship among nodes and for indicating how deeply nested a node is within a tree, text node program code which includes program code for interrogating at least one node representing a text block, table node program code for interrogating at least one node representing a table block, picture program code for returning a type of picture represented by a picture node, and line program code for returning a type of line and other attributes represented by a line node.
  10. Computer program code according to Claim 8, wherein the table node program code includes program code to return a pointer to a first table cell block of a specified table block, to return a table cell of a specified cell position in a table block, to return a pointer to a last table cell block of a specified table block, to return a next table cell block of a specified current table cell block, to return a number of table cell blocks of a specified block type of a table block, and to return a pointer to a previous table cell block of a specified current table cell block.
  11. Computer program code according to any of Claims 2-4, wherein the returned pointer is a block identification.
  12. A method of creating a page analysis program which method utilizes a page analysis interface configured to manipulate a block selection program and for accessing data structure resulting therefrom, the method comprising the steps of:
    • storing, in memory, plural page analysis processing means configured to manipulate block selection program functionality, including functionality to analyze a document page, to create a hierarchical tree structure corresponding to the analyzed document page, and to return a pointer to a root node of the hierarchical tree structure which represents the analyzed page, and for storing plural hierarchical tree structure accessing means for traversing the tree, and for locating desired nodes in the tree;
    • selecting, from memory, at least one of the plural page analysis processing means and at least one of the plural hierarchical tree structure accessing means; and
    • combining the at least one plural page analysis processing means and the at least one plural hierarchical tree structure accessing means so as to create the page analysis program,
  13. A method of creating a page analysis program according to Claim 12, wherein the created page analysis program is also capable of returning at least one pointer to at least one desired node.
  14. A method of creating a page analysis program according to Claim 12, further comprising the steps of storing, in memory, plural data files which include data files which are associated with the plural page analysis functionality, and the plural hierarchical tree accessing means, and combining at least one of the plural data files associated with the at least one selected plural page analysis functionality and combining at least one of the plural data files associated with the at least one selected plural hierarchical tree structure accessing means.
  15. A computer program product storing computer program code according to one of claims 1 to 11.
  16. A computer program product storing computer program code effective to perform a method according to one of claims 12 to 14 when run on a computing means.
Anspruch[fr]
  1. Code de programme d'ordinateur configuré de façon à agir en tant qu'interface avec un programme de sélection de blocs afin d'amener le programme de sélection de blocs à analyser la structure d'une page de document, le code de programme d'interface comprenant:
    • un code de programme d'analyse de page configuré pour manipuler la fonctionnalité du programme de sélection de blocs comprenant des fonctions pour analyser une page d'un document afin d'identifier des régions de texte, des régions sans texte et des régions d'image en mode point dans la page de document, pour créer une structure arborescente hiérarchique correspondant à la page de document analysé, et pour ramener un pointeur sur un noeud de base de la page analysée; et
    • un code de programme accédant à une structure arborescente hiérarchique configuré pour parcourir la structure arborescente hiérarchique générée par le programme de sélection de blocs, et pour localiser des noeuds souhaités dans la structure arborescente hiérarchique.
  2. Code de programme d'ordinateur selon la revendication 1, dans lequel le code de programme d'accès à la structure arborescente hiérarchique comprend en outre un code de programme configuré pour ramener au moins un pointeur à au moins un noeud souhaité.
  3. Code de programme d'ordinateur selon la revendication 2, comprenant en outre un code de programme d'interrogation de noeud destiné à interroger le, au moins un, pointeur pour obtenir une information d'attribut du, au moins un, noeud souhaité lui correspondant.
  4. Code de programme d'ordinateur selon la revendication 3, dans lequel le code de programme d'interrogation de noeud comprend un code de programme d'interrogation de blocs de texte, ledit code de programme d'interrogation de blocs de texte comprenant un code de programme destiné à ramener un pointeur à une première ligne de texte dans un bloc de texte souhaité, à ramener un pointeur à une dernière ligne de texte du bloc de texte souhaité, à ramener un pointeur à une ligne de texte suivante dans le bloc de texte souhaité, à ramener un certain nombre de lignes de texte dans le bloc de texte souhaité, à ramener un pointeur à une ligne de texte précédente dans le bloc de texte souhaité, à ramener une information de ligne d'une ligne de texte dans le bloc de texte souhaité, et à extraire une matrice à deux dimensions de l'image en mode point de la ligne de texte dans le bloc de texte souhaité.
  5. Code de programme d'ordinateur selon la revendication 3, dans lequel le code de programme d'interrogation de noeud comprend un code de programme d'interrogation de bloc d'image, ledit code de programme d'interrogation de bloc d'image comprenant un code de programme destiné à renvoyer une information concernant un type d'image d'un bloc d'image souhaité.
  6. Code de programme d'ordinateur selon la revendication 3, comprenant en outre un fichier de données, ledit fichier de données comprenant des définitions et des paramètres qui sont utilisés par le code de programme d'analyse de page pour manipuler le code de programme de sélection de blocs, par le code de programme d'accès à la structure arborescente hiérarchique pour parcourir l'arborescence hiérarchique, et pour placer des noeuds souhaités, et par le code de programme d'interrogation de noeud pour interroger les noeuds souhaités.
  7. Code de programme d'ordinateur selon la revendication 3, dans lequel le code de programme d'interrogation de noeud comprend un code de programme d'interrogation de bloc de ligne, ledit code de programme d'interrogation de bloc de ligne comprenant un code de programme destiné à renvoyer une information concernant un type de ligne et d'autres attributs d'un bloc de ligne souhaité.
  8. Code de programme d'ordinateur selon la revendication 1, dans lequel le code de programme d'analyse de page comprend un code de programme d'initialisation destiné à initialiser le programme de sélection de bloc en positionnant des variables internes et en affectant une mémoire pour le traitement et le stockage de ses résultats, un code de programme d'exécution pour exécuter le programme de sélection de blocs sur une image d'un document d'entrée, et un code de programme d'achèvement pour libérer une mémoire affectée établie par le code de programme d'initialisation et pour terminer le code de programme d'exécution.
  9. Code de programme d'ordinateur selon la revendication 3, dans lequel le code de programme d'accès à la structure arborescente hiérarchique comprend un code de programme de relation de noeuds qui comprend un code de programme destiné à interroger une relation entre des noeuds et à indiquer à quelle profondeur un noeud est logé dans une arborescence, un code de programme de noeud de texte qui comprend un code de programme destiné à interroger au moins un noeud représentant un bloc de texte, un code de programme de noeud de table destiné à interroger au moins un noeud représentant un bloc de table, un code de programme d'image destiné à renvoyer un type d'image représenté par un noeud d'image, et un code de programme de ligne destiné à renvoyer un type de ligne et d'autres attributs représentés par un noeud de ligne.
  10. Code de programme d'ordinateur selon la revendication 8, dans lequel le code de programme de noeud de table comprend un code de programme destiné à ramener un pointeur à un premier bloc de cellule de table d'un bloc de table spécifié, à ramener une cellule de table d'une position de cellule spécifiée dans un bloc de table, à ramener un pointeur à un dernier bloc de cellule de table d'un bloc de table spécifié, à ramener un bloc de cellule de table suivant d'un bloc de cellule de table en cours spécifié, à ramener un certain nombre de blocs de cellule de table d'un type de bloc spécifié d'un bloc de table, et à ramener un pointeur à un bloc de cellule de table précédent d'un bloc de cellule de table en cours spécifié.
  11. Code de programme d'ordinateur selon l'une quelconque des revendications 2 à 4, dans lequel le pointeur ramené est une identification de bloc.
  12. Procédé de création d'un programme d'analyse de page, lequel procédé utilise une interface d'analyse de page configurée pour manipuler un programme de sélection de bloc et pour accéder à une structure de données qui en résulte, le procédé comprenant les étapes dans lesquelles:
    • on stocke, dans une mémoire, plusieurs moyens de traitement d'analyse de page configurés pour manipuler la fonctionnalité d'un programme de sélection de blocs, comprenant une fonctionnalité pour analyser une page de document, pour créer une structure arborescente hiérarchique correspondant à la page de document analysée, et pour ramener un pointeur à un noeud de base de la structure arborescente hiérarchique qui représente la page analysée, et pour stocker plusieurs moyens d'accès à la structure arborescente hiérarchique afin de parcourir l'arborescence, et pour localiser des noeuds souhaités dans l'arborescence;
    • à sélectionner, à partir de la mémoire, au moins l'un des moyens de traitement d'analyse de page et au moins l'un des moyens d'accès à la structure arborescente hiérarchique; et
    • à combiner le, au moins un, moyen de traitement d'analyse de page et le, au moins un, moyen d'accès à la structure arborescente hiérarchique afin de créer le programme d'analyse de page.
  13. Procédé de création d'un programme d'analyse de page selon la revendication 12, dans lequel le programme d'analyse de page créé est également capable de ramener au moins un pointeur à au moins un noeud souhaité.
  14. Procédé de création d'un programme d'analyse de page selon la revendication 12, comprenant en outre les étapes qui consistent à stocker, dans une mémoire, plusieurs fichiers de données qui comprennent des fichiers de données qui sont associés aux plusieurs fonctionnalités d'analyse de page, et aux moyens d'accès à l'arborescence hiérarchique, et à combiner au moins l'un des fichiers de données associés à la, au moins une, fonctionnalité d'analyse de page sélectionnée et à combiner au moins l'un des fichiers de données associés au, au moins un, moyen d'accès sélectionné à la structure arborescente hiérarchique.
  15. Produit à programme d'ordinateur stockant un code de programme d'ordinateur selon l'une des revendications 1 à 11.
  16. Produit à programme d'ordinateur stockant un code de programme d'ordinateur ayant pour effet de mettre en oeuvre un procédé selon l'une des revendications 12 à 14 qui tourne sur un moyen de calcul.






IPC
A Täglicher Lebensbedarf
B Arbeitsverfahren; Transportieren
C Chemie; Hüttenwesen
D Textilien; Papier
E Bauwesen; Erdbohren; Bergbau
F Maschinenbau; Beleuchtung; Heizung; Waffen; Sprengen
G Physik
H Elektrotechnik

Anmelder
Datum

Patentrecherche

Patent Zeichnungen (PDF)

Copyright © 2008 Patent-De Alle Rechte vorbehalten. eMail: info@patent-de.com