Tree pruning of icon trees via subtree selection using tree functionals

• US 8,683,314 B2
• Filed: 01/13/2006
• Issued: 03/25/2014
• Est. Priority Date: 01/13/2006
• Status: Expired due to Fees

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Berkner, Kathrin, Gormish, Michael
• Primary Examiner(s): Hong, Stephen
• Assistant Examiner(s): ROBINSON, MARSHON L
• Application Number:
  US11/331,481
• Publication Number:
  US 20070168856A1
• Time in Patent Office: 2,993 Days
• Field of Search: 715/210, 715/229, 715/237, 715/200
• 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, by a processor, 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, by the processor, 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, wherein the plurality of visualizations are adapted to the available display utilizing a layout function to minimize a dissimilarity of each of the plurality of visualizations that fit into the available display, wherein the plurality of visualizations comprises an iconic tree representation of layout features of a document collection, wherein each icon in the iconic tree representation includes a first part that represents a geometric feature of a layout element and a second part that represents a content type of the layout element, and wherein adapting the plurality of visualizations comprises adapting the iconic tree representation by pruning one or more icon subtrees with a non-greedy selection that is based on a ratio determined from a plurality of tree functional values to create a pruned tree, wherein the plurality of tree functional values utilized by the non-greedy selection include, for each subtree, at least a real-valued distortion function value computed from a subtree considered with a real-valued resource function value computed for a width of an iconic representation of the subtree, and wherein the ratio utilized by the non-greedy selection is a ratio of a real-valued resource function value versus a real-valued distortion function value for a subtree.

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 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.

7. The method defined in claim 6 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.

8. The method defined in claim 6 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.

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

10. The method defined in claim 1 wherein tree functional selection is performed in a manner that assumes monotonicity and linearity of functionals.

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

12. The method defined in claim 1 wherein adapting the plurality of visualizations to an available display width comprises applying a generalized Breiman, Friedman, Olshen, and Stone (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.

13. A non-transitory computer readable medium 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, wherein the plurality of visualizations are adapted to the available display utilizing a layout function to minimize a dissimilarity of each of the plurality of visualizations that fit into the available display, wherein the plurality of visualizations comprises an iconic tree representation of layout features of a document collection, wherein each icon in the iconic tree representation includes a first part that represents a geometric feature of a layout element and a second part that represents a content type of the layout element, and wherein adapting the plurality of visualizations comprises adapting the iconic tree representation by pruning one or more icon subtrees with a non-greedy selection that is based on a ratio determined from a plurality of tree functional values to create a pruned tree, wherein the plurality of tree functional values utilized by the non-greedy selection include, for each subtree, at least a real-valued distortion function value computed from a subtree considered with a real-valued resource function value computed for a width of an iconic representation of the subtree, and wherein the ratio utilized by the non-greedy selection is a ratio of a real-valued resource function value versus a real-valued distortion function value for a subtree.

14. The non-transitory computer readable medium defined in claim 13 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.

15. The non-transitory computer readable medium defined in claim 14 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.

16. The non-transitory computer readable medium defined in claim 14 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.

17. The non-transitory computer readable medium defined in claim 13 wherein adapting the plurality of visualizations to an available display width comprises removing icon trees via a subtree selection based on tree functionals.

18. The non-transitory computer readable medium defined in claim 17 wherein subtree selection is performed in a manner that assumes monotonicity and sub-linearity of functionals.

19. The non-transitory computer readable medium defined in claim 13 wherein the functional values comprise dissimilarity of elements of a cluster and combined icon width.

20. The non-transitory computer readable medium defined in claim 13 wherein adapting the plurality of visualizations to an available display width comprises applying a generalized Breiman, Friedman, Olshen, and Stone (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.

21. 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, wherein the plurality of visualizations are adapted to the available display utilizing a layout function to minimize a dissimilarity of each of the plurality of visualizations that fit into the available display, wherein the plurality of visualizations comprises an iconic tree representation of layout features of a document collection, wherein each icon in the iconic tree representation includes a first part that represents a geometric feature of a layout element and a second part that represents a content type of the layout element, and wherein adapting the plurality of visualizations comprises means for adapting the iconic tree representation by pruning one or more icon subtrees with a non-greedy selection that is based on a ratio determined from a plurality of tree functional values to create a pruned tree, wherein the plurality of tree functional values utilized by the non-greedy selection include, for each subtree, at least a real-valued distortion function value computed from a subtree considered with a real-valued resource function value computed for a width of an iconic representation of the subtree, and wherein the ratio utilized by the non-greedy selection is a ratio of a real-valued resource function value versus a real-valued distortion function value for a subtree.

22. An apparatus comprising:

a memory; and

a processor coupled with the memory to execute

an icon-creation unit to create an iconic representation of discriminative visualizable features of document layout as a collection of iconic visual elements, wherein the collection of iconic visual elements comprises an iconic tree representation of layout features of a document collection, and wherein each icon in the iconic tree representation includes a first part that represents a geometric feature of a layout element and a second part that represents a content type of the layout element, and

a tree-pruning unit to reduce one or more clusters with a non-greedy selection that is based on a ratio determined from at least two tree functionals and a layout function to minimize a dissimilarity between icons in clusters that fit into an available display based on constraints of the display device to display the icons at leaf nodes of a pruned tree, and wherein the one or more clusters are reduced by pruning one or more icon subtrees based on the at least two tree functional values to create a pruned tree, wherein the plurality of tree functional values utilized by the non-greedy selection include, for each subtree, at least a real-valued distortion function value computed from a subtree considered with a real-valued resource function value computed for a width of an iconic representation of the subtree, and wherein the ratio utilized by the non-greedy selection is a ratio of a real-valued resource function value versus a real-valued distortion function value for a subtree.

23. A method comprising:

representing, by a processor, 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 based on a layout function to fit the iconic tree representation into an available display based on constraints of the display while minimizing a dissimilarity between iconic visual elements in the iconic tree representation, wherein the iconic tree representation is adapted to the available display by pruning one or more icon subtrees with a non-greedy selection that is based on a ratio determined from a plurality of tree functional values to create a pruned tree, wherein the plurality of tree functional values utilized by the non-greedy selection include, for each subtree, at least a real-valued distortion function value computed from a subtree considered with a real-valued resource function value computed for a width of an iconic representation of the subtree, and wherein the ratio utilized by the non-greedy selection is a ratio of a real-valued resource function value versus a real-valued distortion function value for a subtree; and

navigating, by the processor, through the document collection by performing successive subtree selection.

24. 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.