Resolution sensitive layout of document regions

• US 20040145593A1
• Filed: 05/09/2003
• Published: 07/29/2004
• Est. Priority Date: 01/29/2003
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Berkner, Kathrin, Schwartz, Edward L.
• Granted Patent: US 7,177,488 B2
• Time in Patent Office: Days
• US Class Current: 345/619
• CPC Class Codes: G06F 16/9577 Optimising the visualization of content, e.g. distillation of HTML documents
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method and apparatus for reformatting a document is disclosed. In one embodiment, the method comprises selecting a plurality of image segments having a plurality of attributes and determining a plurality of positions and a plurality of geometric operations to be performed on the plurality of image segments according to the plurality of attributes.

Claims

1. A method comprising:

selecting a plurality of image segments having a plurality of attributes; and

determining a plurality of positions and a plurality of geometric operations to be performed on the plurality of image segments according to the plurality of attributes and display constraints.

2. The method of claim 1, further comprising outputting a plurality of instructions executable to cause performance of the plurality of operations on the plurality of image segments.

3. The method of claim 1, further comprising:

performing the plurality of operations on the plurality of image segments; and

displaying the image segments.

4. The method of claim 1, wherein the plurality of geometric operations includes scaling and cropping.

5. The method of claim 1, wherein the plurality of geometric operations includes scaling.

6. The method of claim 5 further comprising expanding each of the image segments to fill free space.

7. The method of claim 1, wherein the plurality of geometric operations includes cropping.

8. The method of claim 7 wherein cropping comprises cropping fragments.

9. The method of claim 7 wherein cropping comprises cropping segments.

10. The method of claim 7 wherein cropping comprises cropping sets.

11. The method of claim 1, wherein the plurality of positions includes a plurality of relative positions.

12. The method of claim 11, further comprising converting the plurality of relative positions into a plurality of absolute positions on a target canvas and displaying the plurality of image segments at the plurality of absolute positions on the target canvas.

13. The method of claim 1, wherein the plurality of attributes includes a preferred resolution and an importance value for each of the plurality of image segments.

14. The method of claim 13, wherein the plurality of operations includes scaling each of the plurality of image segments at the preferred resolution and packing as many scaled image segments as possible into a target display.

15. The method of claim 13, wherein the plurality of operations includes cropping one or more of the plurality of image segments and packing as many image segments as possible into a target display.

16. The method of claim 13, wherein the plurality of operations includes

cropping one or more of the plurality of image segments and packing image segments into a target display to maximize importance.

17. The method of claim 13, wherein the plurality of operations includes

cropping one or more of the plurality of image segments and packing as many image segments as possible into a target display.

18. The method of claim 13, wherein the plurality of operations includes

cropping one or more of the plurality of image segments and packing scaled image segments into a target display to maximize importance.

19. The method of claim 13, wherein the target display is on a personal digital assistant.

20. The method of claim 13, wherein the plurality of attributes further includes an image segment type, an alignment, an anchor point of segment, and a reading order.

21. The method of claim 13, further comprising initializing the plurality of image segments.

22. The method of claim 21, wherein initializing the plurality of image segments includes sorting the plurality of image segments by the importance value.

23. The method of claim 1, wherein the plurality of attributes is assigned to the plurality of image segments during text-based analysis and JPEG 2000-based wavelet analysis of the plurality of image segments.

24. The method of claim 1, wherein determining the plurality of operations comprises evaluating a plurality of cost functions.

25. The method of claim 24, wherein the plurality of cost functions relate importance values of the plurality of image segments and the plurality of operations to cost.

26. The method of claim 1, wherein the plurality of image segments is selected from a document.

27. The method of claim 1, wherein the plurality of image segments is selected from a plurality of documents.

28. The method of claim 1, wherein determining the plurality of positions and the plurality of geometric operations comprises:

determining a relative position for each of the plurality of image segments according to the plurality of attributes, wherein each of the plurality of image segments is associated with a cost function slope; and

expanding each of the plurality of image segments at the relative position such that the expanded image segments have substantially the same cost function slope.

29. The method of claim 28, wherein selecting the plurality of image segments is based on the cost function slope.

30. The method of claim 1, wherein determining the plurality of positions and the plurality of geometric operations comprises:

creating a plurality of boxes, with one box of the plurality of boxes for each of the plurality of image segments; and

for each box of the plurality of boxes associated with an image segment, determining a plurality of relative positions for the image segment with respect to said each box, and for each of the plurality of relative positions,

determining a scaling operation and a cropping operation, and

evaluating a cost function relating the scaling operation and the cropping operation at the relative position.

31. The method of claim 30, wherein the plurality of relative positions includes top, bottom, left, and right.

32. The method of claim 30, further comprising converting the plurality of boxes to a plurality of absolute locations on a canvas.

33. The method of claim 32, wherein the plurality of attributes includes a maximal scale.

34. The method of claim 32, further comprising expanding each of the plurality of image segments to fill free space in each of the plurality of boxes.

35. The method defined in claim 1 further comprising:

placing a number of image segments on a grid;

checking to determine if positions on the grid are feasible; and

repositioning the number of image segments on the grid, if the positions are not feasible, until a set of feasible positions are located.

36. The method defined is claim 35 further comprising searching for positions on the grid.

37. The method defined in claim 36 further comprising eliminating equivalent positions for the image segments.

38. The method defined in claim 35 further comprising:

computing the amount of free space.

39. The method defined in claim 35 wherein computing the amount of free space is performed taking into account straddling.

40. A method comprising:

performing a first analysis and a second analysis on an image to generate a plurality of image segments with a first plurality of attributes and a second plurality of attributes;

performing a resolution sensitive layout on the plurality of image segments to reformat the image;

performing a plurality of operations on the plurality of image segments in response to results from the resolution sensitive layout; and

displaying the operated image segments on a target canvas.

41. The method of claim 40, wherein the first analysis is a text-based analysis comprising:

performing optical character recognition analysis on the image;

extracting optical character recognition analysis information;

segmenting the image into the plurality of text zones; and

assigning the first plurality of attributes to the plurality of text zones.

42. The method of claim 40, wherein the second analysis is a text-based analysis comprising:

performing JPEG 2000 encoding on the image;

extracting JPEG 2000 packet header data from the image;

segmenting the JPEG 2000 packet header data into a plurality of components; and

assigning the second plurality of attributes to the plurality of components.

43. The method of claim 40, wherein the resolution sensitive layout comprises:

initializing the plurality of image segments; and

determining a relative position of an image segment chosen from the plurality of image segments and a plurality of geometric operations on the image segment according to the first plurality of attributes and the second plurality of attributes.

44. The method of claim 43, wherein the resolution sensitive layout further comprises:

converting the relative position to an absolute position on the target canvas, wherein the operated image segments are displayed at the absolute position on the target canvas; and

outputting a plurality of instructions executable to cause performance of the plurality of geometric operations.

45. A machine-readable medium embodying instructions, the instructions, when executed by a system, causing the system to perform a method, the method comprising:

selecting a plurality of image segments having a plurality of attributes; and

determining a plurality of positions and a plurality of geometric operations on the plurality of image segments according to the plurality of attributes.

46. The machine-readable medium of claim 45, wherein the method further comprises outputting a plurality of instructions executable to cause performance of the plurality of operations on the plurality of image segments.

47. The machine-readable medium of claim 45, wherein the method further comprises:

performing the plurality of operations on the plurality of image segments; and

displaying the operated image segments.

48. The machine-readable medium of claim 45, wherein the plurality of geometric operations includes scaling and cropping.

49. The machine-readable medium of claim 45, wherein the plurality of positions includes a plurality of relative positions.

50. The machine-readable medium of claim 49, wherein the method further comprises converting the plurality of relative positions into a plurality of absolute positions on a target canvas and displaying the plurality of image segments at the plurality of absolute positions on the target canvas.

51. The machine-readable medium of claim 45, wherein the plurality of attributes includes a preferred resolution and an importance value for each of the plurality of image segments.

52. The machine-readable medium of claim 51, wherein the plurality of operations includes scaling each of the plurality of image segments at the preferred resolution and packing as many scaled image segments as possible into a target display.

53. The machine-readable medium of claim 52, wherein the target display is on a personal digital assistant.

54. The machine-readable medium of claim 51, wherein the plurality of attributes further includes image segment type, alignment, anchor point of segment, and reading order.

55. The machine-readable medium of claim 51, wherein the method further comprises initializing the plurality of image segments.

56. The machine-readable medium of claim 55, wherein initializing the plurality of image segments includes sorting the plurality of image segments by the importance value.

57. The machine-readable medium of claim 45, wherein the plurality of attributes are assigned to the plurality of image segments during text-based analysis and JPEG2000-based wavelet analysis of the plurality of image segments.

58. The machine-readable medium of claim 45, wherein determining the plurality of operations comprises evaluating a plurality of cost functions.

59. The machine-readable medium of claim 58, wherein the plurality of cost functions relate importance values of the plurality of image segments and the plurality of operations to cost.

60. The machine-readable medium of claim 45, wherein the plurality of image segments is selected from a document.

61. The machine-readable medium of claim 45, wherein the plurality of image segments is selected from a plurality of documents.

62. The machine-readable medium of claim 45, wherein determining the plurality of positions and the plurality of geometric operations comprises:

determining a relative position for each of the plurality of image segments according to the plurality of attributes, wherein each of the plurality of image segments is associated with a cost function slope; and

expanding each of the plurality of image segments at the relative position such that the expanded image segments have substantially the same cost function slope.

63. The machine-readable medium of claim 62, wherein selecting the plurality of image segments is based on the cost function slope.

64. The machine-readable medium of claim 45, wherein determining the plurality of positions and the plurality of geometric operations comprises:

creating a plurality of boxes, one box for each of the plurality of image segments; and

for each of the plurality of boxes associated with an image segment, determining a plurality of relative positions for the image segment with respect to the box, and for each of the plurality of relative positions,

determining a scaling operation and a cropping operation, and

evaluating a cost function relating the scaling operation and the cropping operation at the relative position.

65. The machine-readable medium of claim 64, wherein the plurality of relative positions includes top, bottom, left, and right.

66. The machine-readable medium of claim 64, wherein the method further comprises converting the plurality of boxes to a plurality of absolute locations on a canvas.

67. The machine-readable medium of claim 66, wherein the plurality of attributes includes a maximal scale.

68. The machine-readable medium of claim 67, wherein the method further comprises uniformly scaling the plurality of image segments to the maximal scale.

69. The machine-readable medium of claim 66, wherein the method further comprises expanding each of the plurality of image segments to fill free space in each of the plurality of boxes.

70. A machine-readable medium embodying instructions, the instructions, when executed by a processor, causing the processor to perform a method, the method comprising:

performing a first analysis and a second analysis on an image to generate a plurality of image segments with a first plurality of attributes and a second plurality of attributes;

performing a resolution sensitive layout on the plurality of image segments to reformat the image;

performing a plurality of operations on the plurality of image segments in response to result from the resolution sensitive layout; and

displaying the operated image segments on a target canvas.

71. The machine-readable medium of claim 70, wherein the first analysis is a text-based analysis comprising:

performing optical character recognition analysis on the image;

extracting optical character recognition analysis information;

segmenting the image into the plurality of text zones; and

assigning the first plurality of attributes to the plurality of text zones.

72. The machine-readable medium of claim 70, wherein the second analysis is a JPEG 2000-based wavelet analysis comprising:

performing JPEG 2000 encoding on the image;

extracting JPEG 2000 packet header data from the image;

segmenting the JPEG 2000 packet header data into a plurality of components; and

assigning the second plurality of attributes to the plurality of components.

73. The machine-readable medium of claim 70, wherein the resolution sensitive layout comprises:

initializing the plurality of image segments; and

determining a relative position of an image segment chosen from the plurality of image segments and a plurality of geometric operations on the image segment according to the first plurality of attributes and the second plurality of attributes.

74. The machine-readable medium of claim 73, wherein the resolution sensitive layout further comprises:

converting the relative position to an absolute position on the target canvas, wherein the operated image segments are displayed at the absolute position on the target canvas; and

outputting a plurality of instructions executable to cause performance of the plurality of geometric operations.

75. A system comprising:

an interface to receive an image;

a display device; and

a processor to perform analysis on the image to determine a plurality of attributes of the image, to select a plurality of image segments from the image, and to determine a plurality of positions of the plurality of image segments and a plurality of geometric operations on the plurality of image segments according to the plurality of attributes.

76. The system of claim 75, wherein the plurality of geometric operations includes scaling and cropping.

77. The system of claim 75, wherein the plurality of positions includes a plurality of relative positions, and the processor converts the plurality of relative positions to a plurality of absolute positions on the display device.

78. The system of claim 77, wherein the display device displays the operated image segments at the plurality of absolute positions.

79. The system of claim 75, wherein the analysis includes text-based analysis and JPEG 2000-based wavelet analysis.

80. A method comprising:

determining relative position of one or more areas in a document;

determining one or more geometric operations to be performed on relatively positioned areas;

determining whether a current set of areas chosen for inclusion in a target display is to be updated;

converting the relative position to absolute locations on the target display if the current set of areas chosen for inclusion in the target display is not to be updated; and

generating an output list of instructions to operate on the document.

81. A method comprising:

ordering areas in a set of areas with respect to importance value, for each area in the set of areas;

processing each box in said each area by

(a) analyzing relative position with respect to said each box

(b) determining scaling to fit said each area into free space in a target display at the relative position,

(c) evaluating a cost function, and

repeating steps (a)-(c) for each position;

converting grid locations to absolute locations in the target display for areas to be included in the target display based on a cost function; and

generating an output to control generation of the target display.

82. A method comprising:

selecting a set of areas in a document, where the set of areas have a maximum cost function slope;

determining relative position of one or more areas in the set of areas;

expanding areas in the set of areas in the set based on current relative position;

determining whether to include one or more additional areas into the set of areas and searching for more relative positions for areas in the set of areas;

converting the relative positions of areas to absolute locations on a target display after determining whether desired improvement is not found by including more areas or by searching more positions; and

generating an output list of instructions to operate on the document.

83. The method defined in claim 82 further comprising setting the scale for all areas to the minimum allowable scale.

84. The method defined in claim 82 wherein selecting a set of areas comprises computing a derivative of a cost function for each area in the document and identifying a plurality of areas with the largest magnitude slope.

85. The method defined in claim 82 wherein determining relative positions of one or more areas comprises searching for new positions of areas in the set of areas that are feasible.

86. The method defined in claim 82 wherein expanding areas comprises increasing scale of areas in the set of areas.