Systems and methods for creating and interactive 3D visualization of indexed media

• US 20050183041A1
• Filed: 02/12/2004
• Published: 08/18/2005
• Est. Priority Date: 02/12/2004
• Status: Active Grant

• Current Assignee: Fujifilm Business Innovation Corp. (Fujifilm Holdings Corporation)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.)
• Inventors: Girgensohn, Andreas, Chiu, Patrick, Polak, Wolfgang, Lertsithichai, Surapong, Shipman, Frank III
• Granted Patent: US 7,340,678 B2
• Time in Patent Office: Days
• US Class Current: 715/850
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: G06F 2203/04802 3D-info-object: information is displayed on the internal or external surface of a three dimensional manipulable object, e.g. on the faces of a cube that can be rotated by the user
• CPC Class Codes: G06F 3/04815 Interaction with a metaphor-based environment or interaction object displayed as three-dimensional, e.g. changing the user viewpoint with respect to the environment or object
• CPC Class Codes: G06F 3/0482 Interaction with lists of selectable items, e.g. menus
• CPC Class Codes: G06T 11/206 Drawing of charts or graphs
• CPC Class Codes: G06T 2200/04 involving 3D image data

Abstract

A 3D graphical user interface includes a two-dimensional ground-plane layout representing the relationship between one or more leaf elements of a tree data structure. The interface further includes at least one building-like structure, each of the at least one building-like structure corresponding to a respective one of the one or more leaf elements. Each of the at least one building-like structure provides a summary of media associated with the respective one of the more leaf elements corresponding to at least one building-like structure.

Claims

1. A method for creating a layout for a 3D visualization comprising:

inputting a tree data structure, each leaf of the tree associated with one or more forms of media;

obtaining a plurality of candidate layouts;

comparing the plurality of candidate layouts;

selecting a solution layout based on the comparison; and

constructing a 3D visualization of the tree data structure based on the solution layout, wherein the representation of each leaf of the tree data structure within the 3D visualization provides a summary of the media associated with that leaf.

2. The method of claim 1, wherein obtaining the plurality of candidate layouts further comprises:

assigning each leaf a rectangular layout;

arranging, for each node of the tree data structure whose subnodes are all leaves, the rectangular layouts of the leaves of that node into a layout for that node.

3. The method of claim 2, wherein, for each node that has a rectangular layout for each subnode, one of the rectangular layouts being larger than a leaf rectangular layout, obtaining the plurality of candidate layouts further comprises:

arranging—

for each node that has more than one leaf subnode and more than one non-leaf subnode, each non-leaf subnode having a rectangular layout—

the rectangular layouts of the more than one leaf subnodes of that node into a rectangular layout; and

arranging, for that node, the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes into a plurality of candidate layouts, the candidate layouts each defined by an aspect ratio.

4. The method of claim 3, wherein:

obtaining the plurality of candidate layouts further comprises arranging, for each node that does not have more than one leaf subnode and more than one non-leaf subnode, each non-leaf subnode having a rectangular layout, the layouts of the subnodes of that node into a plurality of candidate layouts, the candidate layouts defined by an aspect ratio.

5. The method of claim 4, wherein:

comparing the plurality of candidate layouts comprises determining a total area of each candidate layout that does not contain the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes; and

selecting the solution layout comprises selecting the candidate layout with the smallest total area that does not contain the rectangular layouts of the non-leaf subnodes and the rectangular layout of the leaf subnodes.

6. The method of claim 5, wherein constructing the 3D visualization based on the layout comprises:

associating, for each leaf within the input tree data structure, the media associated with that leaf with a location of the layout of that leaf with the solution layout; and

creating, for each leaf within the input tree data structure, a summary of the media associated with that leaf.

7. The method of claim 6, wherein the summary of the media contained by that leaf is a building-like structure with visual summaries of the media on each side of the building and the roof of the building.

8. The method of claim 1, wherein obtaining a plurality of candidate layouts comprises:

determining, for each leaf, a rectangular layout, a size of the rectangular layout being determined by a quality of the media associated with that leaf;

assigning, for each leaf, the determined rectangular layout to a new set of layouts; and

associating, for each leaf, the new set of layouts with a parent node of that leaf;

wherein, whenever there is only a single set of layouts associated with a root node, and no sets of layouts associated with any other nodes, selecting the solution layout comprises selecting a smallest layout from the set of layouts associated with the root node as the solution layout.

9. The method of claim 8, wherein obtaining the plurality of candidate layouts further comprises:

identifying each node that has a set of layouts associated with it for each of its subnodes;

combining, for each identified node, the sets of layouts associated with that identified node into a single set, wherein the single set contains combined layouts that are not larger than any other combined layouts within the set.

10. The method of claim 9, wherein, to be considered larger, a layout must be longer in width and longer in length than another layout of the other layouts within the set.

11. The method of claim 10, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set comprises:

selecting a first set of layouts associated with that identified node containing a smallest layout;

selecting a second set of layouts associated with that identified node, other than the first set of layouts, that contains a smallest layout;

creating a new set of layouts associated with that identified node;

horizontally combining a first layout from the first selected set of layouts with a first layout from the second selected set of layouts; and

assigning the horizontally combined first layout from the first selected set and first layout from the second selected to the new set of layouts associated with the identified node.

12. The method of claim 11, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set further comprises, for each layout within the first selected set of layouts:

horizontally combining, for each layout within the second selected set of layouts, that layout from the first selected set of layouts with that layout from the second selected set of layouts; and

comparing, for each layout within the new set for the identified node, the horizontally combined layout from the first selected set and layout from the second selected set with that layout within the new set;

wherein;

whenever the horizontally combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the horizontally combined layout from the first selected set and the second selected set is discarded;

whenever a layout within the new set for the identified node is larger than the horizontally combined layout from the first selected set and the second selected set, that layout within the new set for the identified node is discarded; and

if the horizontally combined layout from the first selected set and the second selected set has been compared with every layout in the new set for the identified node without being discarded, the horizontally combined layout from the first selected set and the second selected set is added to the new set for the identified node.

13. The method of claim 12, wherein combining, for each identified node, the sets of layouts associated with that identified node into a single set further comprises, for each layout within the first selected set of layouts:

vertically combining, for each layout within the second selected set of layouts, that layout from the first selected set of layouts with that layout from the second selected set of layouts; and

comparing, for each layout within the new set for the identified node, the vertically combined layout from the first selected set and layout from the second selected set with that layout within the new set;

wherein;

whenever the vertically combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the vertically combined layout from the first selected set and the second selected set is discarded;

whenever a layout within the new set for the identified node is larger than the vertically combined layout from the first selected set and the second selected set, that layout within the new set for the identified node is discarded; and

if the vertically combined layout from the first selected set and the second selected set has been compared with every layout in the new set for the identified node without being discarded, the vertically combined layout from the first selected set and the second selected set is added to the new set for the identified node.

14. The method of claim 13, wherein the first selected set and the second selected set are discarded.

15. A system for creating a 3D visualization comprising:

a node identifying circuit, routine, or application that accesses a tree data structure and identifies qualities of nodes within the tree data structure;

a rectangle assigning circuit, routine, or application that assigns rectangular layouts to nodes within the tree data structure;

a rectangle arranging circuit, routine, or application that arranges rectangular layouts into larger candidate rectangular layouts;

a layout testing circuit, routine, or application that compares candidate rectangular layouts and selects a solution layout; and

a media associating circuit, routine, or application that associates media with the solution layout to create a 3D visualization.

16. The system of claim 15, wherein:

the node identifying circuit, routine, or application accesses a tree data structure and identifies each leaf with the tree data structure; and

the rectangle assigning circuit, routine, or application assigns each identified leaf a rectangular layout.

17. The system of claim 16, wherein:

the node identifying circuit, routine, or application identifies each node whose subnodes are all leaves; and

the rectangle arranging circuit, routine, for each identified node whose subnodes are all leaves, arranges the rectangular layouts of the subnodes of that identified node into a larger rectangular layout and assigns the larger rectangular layout to that identified node.

18. The system of claim 17, wherein:

the node identifying circuit, routine, or application identifies each node that has a rectangular layout for each subnode, more than one of the rectangular layouts for each node being larger than a leaf rectangular layout and more than one of the rectangular layouts for each node being a leaf rectangular layout; and

the rectangle arranging circuit, routine, or application arranges each of the more than one leaf rectangular layouts into a larger leaf rectangular layout and then arranges the larger leaf rectangular layout and the more than one of the larger than a leaf rectangular layout for the subnodes of the node into a plurality of candidate layouts for the node.

19. The system of claim 18, wherein:

the node identifying circuit, routine, or application identifies each node that has a rectangular layout for each subnode, and does not have both more than one of the rectangular layouts for each node being larger than a leaf rectangular layout and more than one of the rectangular layouts for each node being a leaf rectangular layout; and

the rectangle arranging circuit, routine, or application arranges the rectangular layouts for the subnodes of the node into a plurality of candidate layouts for the node.

20. The system of claim 19, further comprising an aspect ratio adjusting circuit, routine, or application, wherein the rectangle arranging circuit, routine, or application only creates candidate layouts within a defined aspect ratio and, if the rectangle arranging circuit routine or application cannot arrange various rectangular layouts for the subnodes of the identified node, the aspect ratio adjusting circuit, routine, or application increases the defined aspect ratio.

21. The system of claim 20, wherein:

the node identifying circuit, routine, or application identifies each node that has a plurality of candidate layouts associated with that node; and

the layout testing circuit, routine, or application, for each identified node that has a plurality of candidate layouts associated with that node, selects the candidate layout for that node with the least amount of empty space as the solution layout for that node.

22. The system of claim 21, wherein, if there are two candidate layouts with the least amount of empty space, the layout testing circuit, routine, or application selects the candidate layout with the smallest circumference as the solution layout for that node.

23. The system of claim 21, wherein, if the layout testing circuit, routine, or application has selected a solution layout for a root node of the tree data structure, the media associating circuit, routine, or application associates summary media that summarizes data within each leaf of the tree data structure with the respective location of each leaf within the solution layout.

24. A system for creating a 3D visualization comprising:

a node identifying circuit, routine, or application that accesses a tree data structure and identifies qualities of nodes within the tree data structure;

a set creating circuit, routine, or application that creates sets with which layouts may be associated;

a set associating circuit, routine, or application that associates one or more sets of layouts with a node of the tree data structure;

a layout constructing circuit, routine, or application that creates rectangular layouts for the leaves of the tree data structure;

a layout size comparing circuit, routine, or application that compares dimensions of a plurality of layouts;

a horizontal layout combining circuit, routine, or application that combines two layouts horizontally;

a vertical layout combining circuit, routine, or application that combines two layouts vertically;

a layout testing circuit, routine, or application that compares candidate rectangular layouts and selects a solution layout; and

a media associating circuit, routine, or application that associates media with the solution layout to create a 3D visualization;

25. The system of claim 24, wherein:

the node identifying circuit, routine, or application identifies each leaf of a tree data structure;

the set creating circuit, routine, or application, creates a new set of layouts for each identified leaf;

the layout constructing circuit, routine, or application, for each identified leaf, creates a layout for that identified leaf and stores the created layout in the new set of layouts; and

the set associating circuit, routine, or application, for each identified leaf, associates the new set of layouts with the parent node of that identified leaf.

26. The system of claim 25, wherein:

the node identifying circuit, routine, or application identifies each node that has a single set of layouts associated with it; and

the set associating circuit, routine, or application, for each identified node that has a single set of layouts and no sets of layouts associated with any subnodes, associates that single set of layouts with the parent node of the identified node that has a single set of layouts and no sets of layouts associated with any subnodes.

27. The system of claim 26, wherein:

the node identifying circuit, routine, or application identifies each node that has more than one set of nodes associated with it;

the set creating circuit, routine, or application, for each identified node that has more than one set of nodes associated with it, creates a new set of layouts; and

the set associating circuit, routine, or application, for each identified node that has more than one set of nodes associated with it, associates the new set with that identified node that has more than one set of nodes associated with it.

28. The system of claim 27, wherein:

the horizontal combining circuit, routine, or application, selects a first set of layouts associated with that identified node, the first set of layouts containing a smallest layout, selects a second set of layouts associated with that identified node, other than the first set of layouts, that contains a smallest layout, horizontally combines a first layout from the first selected set of layouts with a first layout from the second selected set of layouts, and assigns the horizontally combined layout to the new set of layouts.

29. The system of claim 28, wherein, for each layout within the first selected set of layouts:

the horizontal combining circuit, routine, or application, for each layout within the second selected set of layouts, horizontally combines that layout from the first selected set of layouts with that layout from the second set of selected layouts; and

the layout size comparing circuit, routine, or application, for each layout within the new set for the identified node that has more than one set of nodes associated with it, compares the horizontally combined layout from the first selected set of layouts and the second set of selected layouts and that layout within the new set for the identified node that has more than one set of nodes associated with it;

wherein;

whenever the horizontally combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the layout size comparing circuit, routine, or application discards the horizontally combined layout from the first selected set and layout from the second selected set;

whenever a layout within the new set for the identified node is larger than the horizontally combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application discards that layout within the new set for the identified node; and

if the layout size comparing circuit, routine, or application has compared the horizontally combined layout from the first selected set and the second selected set with every layout in the new set for the identified node without discarding the horizontally combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application adds the horizontally combined layout from the first selected set and the second selected set to the new set for the identified node.

30. The system of claim 29, wherein, for each layout within the first selected set of layouts:

the vertical combining circuit, routine, or application, for each layout within the second selected set of layouts, vertically combines that layout from the first selected set of layouts with that layout from the second set of selected layouts; and

the layout size comparing circuit, routine, or application, for each layout within the new set for the identified node that has more than one set of nodes associated with it, compares the vertically combined layout from the first selected set of layouts and the second set of selected layouts and that layout within the new set for the identified node that has more than one set of nodes associated with it;

wherein;

whenever the vertically combined layout from the first selected set and the second selected set is larger than a layout within the new set for the identified node, the layout size comparing circuit, routine, or application discards the vertically combined layout from the first selected set and layout from the second selected set;

whenever a layout within the new set for the identified node is larger than the vertically combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application discards that layout within the new set for the identified node; and

if the layout size comparing circuit, routine, or application has compared the vertically combined layout from the first selected set and the second selected set with every layout in the new set for the identified node without discarding the vertically combined layout from the first selected set and the second selected set, the layout size comparing circuit, routine, or application adds the vertically combined layout from the first selected set and the second selected set to the new set for the identified node.

31. The system of claim 30, wherein the layout size comparing circuit, routine, or application discards the first selected set and the second selected set.

32. The system of claim 31, wherein when the node identifying circuit routine or application determines that the root node has only one set of layouts associated with it, the layout testing circuit, routine, or application selects a smallest layout from the set of layouts associated with the root node as a solution layout.

33. The system of claim 32, wherein the media associating circuit, routine, or application associates summary media that summarizes the data within each leaf of the tree data structure with the respective location of each leaf within the solution layout.

34. A 3D graphical user interface comprising:

a two-dimensional ground-plane layout representing the relationship between one or more leaf elements of a tree data structure; and

at least one building-like structure, each of the at least one building-like structures corresponding to a respective one of the one or more leaf elements, wherein each of the at least one building-like structure provides a summary of media associated with the respective one of the more leaf elements corresponding to that at least one building-like structure.

35. The 3D graphical user interface of claim 34, wherein each of the one or more leaf elements is represented by a similarly sized substantially square plot within the two-dimensional ground plane.

36. The 3D graphical user interface of claim 34, wherein each of the one or more leaf elements is represented by a differently sized substantially square plot within the two-dimensional ground plane.

37. The 3D graphical user interface of claim 36, wherein dimensions of each differently sized substantially square plot reflect one or more characteristics of the media associated with the leaf element corresponding to that differently sized square plot.

38. The 3D graphical user interface of claim 34, wherein each of the at least one building-like structure provides the summary of media associated with the respective one of the more leaf elements corresponding to that at least one building-like structure by displaying a portion of that media on at least one of the sides or on the top of the building-like structure.

39. The 3D graphical user interface of claim 38, wherein the summary of the media comprises at least one frame of a video.

40. The 3D graphical user interface of claim 38, wherein the summary of the media comprises a side.

41. The 3D graphical user interface of claim 36, wherein the summary of the media comprises text.

42. The 3D graphical user interface of claim 38, further comprising text floating over the building-like structures.