Methods and apparatus for automatic page break detection

• US 7,260,779 B2
• Filed: 09/30/2005
• Issued: 08/21/2007
• Est. Priority Date: 04/13/2000
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Subrahmonia, Jayashree, Ratzlaff, Eugene H., Keyser, Paul Turquand, Perrone, Michael Peter
• Primary Examiner(s): Hong; Stephen
• Assistant Examiner(s): Stork; Kyle R
• Application Number:
  US11/240,605
• Publication Number:
  US 20060031764A1
• Time in Patent Office: 690 Days
• Field of Search: 715/513, 715/517, 715/525, 715/530, 382/187
• US Class Current: 715/251
• CPC Class Codes: G06F 40/114 Pagination

Abstract

In one aspect of the present invention, page breaks are identified in the following manner. A set of ink data and a document description are processed by a variety of scoring methods, each of which generates a score for each possible insertion point in the ink. These scores are combined to produce a ranked list of hypothesized page breaks for the corresponding ink data. This ranked list is then used either to insert page breaks automatically using a predefined threshold to determine a cut-off in the list; or to present, on-line, to a human for verification/approval; or a mixture of the two based on two thresholds: one for automatic insertion and the other for human verification. It is to be understood not all scoring methods need be used, that is, one or more of the scoring methods may be used as needed.

Claims

1. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

measuring a spatial difference between consecutive pairs of strokes made in accordance with the handwriting system; and

labeling spatial differences not below a threshold value as possible insertion points.

2. The method of claim 1, further comprising the steps of:

for each spatial difference not below the threshold value, computing one of the number of strokes and the total arc length associated with strokes that occur between the current possible insertion point and one of the next page breaks in the electronic document and the end of the stroke set of the document; and

assigning one of the number of strokes and the total arc length as a score to be associated with the possible insertion point.

3. The method of claim 2, wherein the assigning step is performed when one of the number of strokes and the total arc length is not below a second threshold value.

4. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

measuring a temporal difference between consecutive pairs of strokes made in accordance with the handwriting system; and

labeling temporal differences not below a threshold value as possible insertion points.

5. The method of claim 4, further comprising the step of, for each temporal difference not below the threshold value, assigning a score to the corresponding possible insertion point based on a distance from the temporal difference to the threshold value.

6. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the step of identifying as a possible insertion point a point before a stroke, made in accordance with the handwriting system, wherein the stroke falls within a constrained region on a page associated with the document and wherein the stroke is not immediately preceded by another stroke in the same constrained region.

7. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein, in an electronic document that corresponds to a form with fields, the step of automatically identifying one or more potential page breaks further comprises the steps of;

computing a measure of field appropriateness for each stroke made in accordance with the handwriting system to indicate how well a stroke fits within a particular field; and

for N consecutive strokes which do not fit the field of a particular page of the document, identifying a potential page break before these N consecutive strokes.

8. The method of claim 7, wherein the potential page break indicates the page number of the page having a field with which the N consecutive strokes appropriately fit.

9. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

computing a measure of overlap for each stroke with a previous stroke; and

for N consecutive strokes with a total measure of overlap which is not less than a threshold value, identifying a potential page break before these N consecutive strokes.

10. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

computing a moving average of spatial positions of strokes, made in accordance with the handwriting system, on a page using a predetermined window width, the computation of the moving average resulting in a spatial position moving average curve;

computing a moving average of a slope associated with the spatial position moving average curve, the computation of the moving average resulting in a slope moving average curve; and

identifying one or more negative slopes in the slope moving average curve as potential page breaks.

11. The method of claim 10, wherein negative slopes are identified as potential page breaks based on peak-heights.

12. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

computing a moving average of temporal positions of strokes, made in accordance with the handwriting system, on a page using a predetermined window width, the computation of the moving average resulting in a temporal position moving average curve;

computing a moving average of a slope associated with the temporal position moving average curve, the computation of the moving average resulting in a slope moving average curve; and

identifying one or more positive slopes in the slope moving average curve as potential page breaks.

13. The method of claim 12, wherein positive slopes are identified as potential page breaks based on peak-heights.

14. A computer-based method of processing an electronic document generated in accordance with a handwriting system, the method comprising the steps of:

obtaining electronic ink data from the handwriting system, the ink data being associated with the electronic document; and

automatically identifying, using at least a portion of the electronic ink data, one or more potential page breaks for possible insertion in the electronic document to maintain a page correspondence between the electronic document and a physical document, also generated in accordance with the handwriting system, and so as to at least partially reduce asynchrony between an electronic page and a physical page;

wherein the step of automatically identifying one or more potential page breaks further comprises the steps of;

performing two or more scoring procedures, each scoring procedure generating a list whose elements include a possible insertion point and a corresponding score;

merging the lists generated by the two or more scoring procedures to form a combined list; and

selecting one or more top scoring possible insertion points as the one or more potential page breaks.

15. The method of claim 14, wherein the selecting step further comprises selecting a number of top scoring possible insertion points to match the number of expected pages of the document.

16. The method of claim 14, wherein the merging step further comprises merging the lists by one of (i) accepting all possible insertion points except duplicates;

(ii) unbiased voting;

(iii) biased voting;

(iv) using disjunctive normal forms; and

(v) using neural networks.