Tree pruning of icon trees via subtree selection using tree functionals

• US 20070168856A1
• Filed: 01/13/2006
• Published: 07/19/2007
• Est. Priority Date: 01/13/2006
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Berkner, Kathrin, Gormish, Michael
• Granted Patent: US 8,683,314 B2
• Time in Patent Office: Days
• US Class Current: 715/210
• CPC Class Codes: G06F 16/34 Browsing; Visualisation therefor

Abstract

A method and apparatus for creating visualizations using tree functionals is described. In one embodiment, the method comprises representing a group of document images using a plurality of visualizations that visualize document layout information for the group of document images based on one or more display device characteristics and based on content of the group of documents, and adapting the plurality of visualizations to an available display by removing one or more visualizations from the plurality of visualizations based on at least two functional values.

Claims

1. A method comprising:

representing a group of document images using a plurality of visualizations that visualize document layout information for the group of document images based on one or more display device characteristics and based on content of the group of documents; and

adapting the plurality of visualizations to an available display by removing one or more visualizations from the plurality of visualizations based on at least two functional values.

2. The method defined in claim 1 wherein removing the one or more visualizations comprises reducing clusters of document images.

3. The method defined in claim 1 wherein the plurality of visualizations comprises an iconic representation of discriminative visualizable features of document layout as a collection of iconic visual elements.

4. The method defined in claim 1 where each visualization represents a group of document images.

5. The method defined in claim 1 wherein the functional values measure geometric properties of the visualization and are characteristic of layout features of documents in the group.

6. The method defined in claim 1 wherein the plurality of visualizations comprises an iconic tree representation of layout features of a document collection, and wherein adapting the plurality of visualizations comprises adapting the iconic tree representation by removing one or more icon subtrees via subtree selection using a plurality of tree functional values.

7. The method defined in claim 6 wherein the tree functional values are distortion of a subtree to a parent tree and visualization area of the iconic tree representation.

8. The method defined in claim 6 wherein adapting the plurality of visualizations to an available display width comprises evaluating a plurality of subtrees by at least two tree functionals and selecting a subtree that has a preselected ratio among the tree functional values subject to a size constraint on subtree visualization.

9. The method defined in claim 8 wherein the preselected ratio of tree functional values comprises a smallest ratio of distortion versus the required visualization area of all subtrees with a specified root node.

10. The method defined in claim 8 wherein adapting the plurality of visualizations to an available display width comprises, for each subtree, measuring layout dissimilarity in the documents in the leaf modes and size of iconic representation using tree functionals

11. The method defined in claim 6 wherein adapting the plurality of visualizations to an available display width comprises removing icon trees via a subtree selection based on tree functionals.

12. The method defined in claim 7 wherein tree functional selection is performed in a manner that assures monotonicity and linearity of functionals.

13. The method defined in claim 1 wherein the functional values comprise dissimilarity of elements of a cluster and visualization width.

14. The method defined in claim 1 wherein adapting the plurality of visualizations to an available display width comprises applying a generalized BFOS algorithm to tree functional values to evaluation distortion of node clusters versus the size of the iconic visualization subject to a constraint on the total size of leave node icons.

15. An article of manufacture having one or more recordable media storing instructions thereon which, when executed by a system, cause the system to perform a method comprising:

representing a group of document images using a plurality of visualizations that visualize document layout information for the group of document images based on one or more display device characteristics and based on content of the group of documents; and

adapting the plurality of visualizations to an available display width by removing one or more visualizations from the plurality of visualizations based on at least two functional values.

16. The article of manufacture defined in claim 15 wherein the plurality of visualizations comprises an iconic tree representation of layout features of a document collection, and wherein adapting the plurality of visualizations comprises adapting the iconic tree representation by removing one or more icon trees via subtree selection using a plurality of tree functional values.

17. The article of manufacture defined in claim 16 wherein the tree functional values are distortion of a subtree and visualization area of the iconic tree representation.

18. The article of manufacture defined in claim 16 wherein adapting the plurality of visualizations to an available display width comprises evaluating a plurality of subtrees by at least two tree functionals and selecting a subtree that has a preselected ratio among the tree functional values subject to a size constraint on subtree visualization.

19. The article of manufacture defined in claim 18 wherein the preselected ratio of tree functional values comprises a smallest ratio of distortion versus the required visualization area of all subtrees with a specified root node.

20. The article of manufacture defined in claim 18 wherein adapting the plurality of visualizations to an available display width comprises, for each subtree, measuring layout dissimilarity in the documents in a node and size of iconic representation using tree functionals

21. The article of manufacture defined in claim 16 wherein adapting the plurality of visualizations to an available display width comprises removing icon trees via a subtree selection based on tree functionals.

22. The article of manufacture defined in claim 21 wherein subtree selection is performed in a manner that assures monotonicity and sub-linearity of functionals.

23. The article of manufacture defined in claim 15 wherein the functional values comprise dissimilarity of elements of a cluster and combined icon width.

24. The article of manufacture defined in claim 15 wherein adapting the plurality of visualizations to an available display width comprises applying a generalized BFOS algorithm to tree functional values to evaluation distortion of node clusters versus the size of the iconic visualization subject to a constraint on the total size of leave node icons.

28. The method defined in claim 23 wherein navigating through the document collection comprises:

identifying the next best subtree from existing subtrees in the iconic tree representation; and

displaying the next best subtree in the size-constrained display.

25. An apparatus comprising:

means for representing a group of document images using a plurality of visualizations that visualize document layout information for the group of document images based on one or more display device characteristics and based on content of the group of documents; and

means for adapting the plurality of visualizations to an available display width by removing one or more visualizations from the plurality of visualizations based on at least two functional values.

26. An apparatus comprising:

an icon-creation unit to create an iconic representation of discriminative visualizable features of document layout as a collection of iconic visual elements; and

a tree-pruning unit to reduce one or more clusters based on at least two tree functionals to display icons at leaf notes of the pruned tree.

27. A method comprising:

representing a document collection in a size-constrained display using an iconic tree representation of discriminative visualizable features of document layout as a collection of iconic visual elements

navigating through the document collection by performing successive subtree selection.

29. A method comprising:

selecting page units of a single document page for visualization based on one or both of user specifications and application requirements;

selecting iconic elements for the page units;

determining positions of icon elements in an output icon; and

composing the output icon using iconic elements or page image data.