Method and apparatus for dynamically grouping a plurality of graphic objects

• US 5,889,523 A
• Filed: 11/25/1997
• Issued: 03/30/1999
• Est. Priority Date: 11/25/1997
• Status: Expired due to Term

• Current Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Fuji Xerox Company Limited (Xerox Holdings Corp.), Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Chiu, Patrick, Golovchinsky, Gene, Schilit, William N., Wilcox, Lynn D., Sullivan, Joseph W.
• Primary Examiner(s): Breene, John E.
• Assistant Examiner(s): BAUTISTA, XIOMARA L
• Application Number:
  US08/977,810
• Time in Patent Office: 490 Days
• Field of Search: 345/357, 345/358, 345/978, 707/531
• US Class Current: 715/854
• CPC Class Codes: G06F 3/04842 Selection of displayed objects or displayed text elements G06F3/0482 takes precedence
• CPC Class Codes: G06F 3/04845 for image manipulation, e.g. dragging, rotation, expansion or change of colour
• CPC Class Codes: G06F 3/04883 for inputting data by handwriting, e.g. gesture or text
• CPC Class Codes: Y10S 715/978 Audio interaction as part of an operator interface

Abstract

When dynamically grouping a plurality of graphic objects, such as displayed on a graphic input display apparatus, a cluster tree is formed for the plurality of graphic objects. The cluster tree is based on a plurality of different types of distance measures. These include a time distance and a spatial distance. These distances are combined to form a distance metric indicting a distance between a pair of the graphic objects. Each level of the cluster tree defines a new cluster of the graphic objects. At least one of the graphic objects is selected. The different cluster levels of the cluster tree containing the selected graphic object are displayable. The displayed cluster of the graphic objects can be modified to increase or decrease the cluster level of the cluster containing the selected graphic object.

Claims

1. A method for dynamically grouping a plurality of graphic objects displayed on a graphic input display device, comprising:

determining at least one distance, each distance being between a pair of graphic objects and based on a plurality of different types of distance measures; and

forming a cluster tree for the graphic objects based upon each determined distance, each cluster level of the cluster tree defining one new cluster of the graphic objects.

2. The method of claim 1, further comprising:

selecting at least one graphic object;

displaying a graphic object group including the selected at least one graphic object, based on an associated cluster level on the graphic input display device.

3. The method of claim 2, further comprising:

selecting another cluster level of the cluster tree whose corresponding cluster contains the selected at least one graphic object; and

displaying on the graphic input display device another graphic object group based on the selected cluster level.

4. The method of claim 3, wherein selecting another cluster level includes at least one of:

using an up/down interface to select the cluster level;

using a gesture recognition device to select the cluster level;

using a voice response device to select the cluster level; and

determining the cluster level based on a duration of selection of the at least one graphic object.

5. The method of claim 2, wherein the associated cluster level is predetermined.

6. The method of claim 5, wherein the predetermined cluster level corresponds to one of a graphic object, a word, a line, a paragraph or a page.

7. The method of claim 2, wherein selecting at least one graphic object includes at least one of:

using an up/down interface to select the at least one graphic object;

using a gesture recognition device to select the at least one graphic object; and

using a voice response device to select the at least one graphic object.

8. The method of claim 1, wherein forming the cluster tree comprises:

selecting one of the graphic objects; and

forming the cluster tree based on the selected graphic object.

9. The method of claim 1, wherein each distance is a function of a time distance and a spatial distance.

10. The method of claim 9, further comprising scaling the spatial distance based on relative sizes of the plurality of graphic objects.

11. The method of claim 9, wherein, for each pair of graphic objects X and Y the distance is:

space="preserve" listing-type="equation">D=D.sub.T (X,Y)+α

D.sub.S (X,Y)

where;

D is the pairwise distance;

D_T is the pairwise time distance;

D_S is the pairwise spatial distance; and

α

is a constant relating the time distance to the spatial distance.

12. The method of claim 11, wherein:

space="preserve" listing-type="equation">D.sub.S =d.sub.x +β

d.sub.y,

where

d_x is a distance between the graphic object X and the graphic object Y along the horizontal coordinate direction;

d_y is a distance between the graphic object X and the graphic object Y in the vertical coordinate direction; and

β

is a constant specifying a relative importance of the d_x and d_y distances.

13. The method of claim 11, wherein:

##EQU9## where;

X_L is the length of the graphic object X in a horizontal coordinate direction;

Y_L is the length of the graphic object Y in the horizontal coordinate direction;

X_H is the height of the graphic object X in the vertical coordinate direction;

Y_H is the height of the graphic object Y in the vertical coordinate direction; and

β

is a constant defining a relative importance of the d_x and d_y distances.

14. The method of claim 11, wherein:

space="preserve" listing-type="equation">D.sub.T =M, Y.sub.s -X.sub.e >

M,=Y.sub.s -X.sub.e, otherwise,

where;

M is a constant defining a limiting time between the creation of graphic object X and graphic object Y;

X_e is the end time for the creation of graphic object X; and

Y_s is the start time for the creation of graphic object Y.

15. A method for dynamically grouping a plurality of graphic objects displayed on a graphic input display device, comprising:

initially grouping each of the plurality of graphic objects as its own cluster;

determining at least one pairwise distance, each pairwise distance being between a pair of the clusters and based on a combination of a time distance between creation of the pair of clusters and a spatial distance between the pair of clusters; and

merging the pair of clusters closest to each other based on the at least one pairwise distance to form a single cluster and a cluster level.

16. The method of claim 15, further comprising repeating, for each successive cluster level, the determining and the merging steps until at most one cluster exists after the merging step.

17. The method of claim 15, further comprising scaling the spatial distance based upon relative sizes of the plurality of graphic objects.

18. The method of claim 15, wherein, for each pair of graphic objects X and Y the distance is:

space="preserve" listing-type="equation">D=D.sub.T (X,Y)+α

D.sub.S (X,Y)

where;

D is the pairwise distance;

D_T is the pairwise time distance;

D_S is the pairwise spatial distance; and

α

is a constant relating the time distance to the spatial distance.

19. The method of claim 18, further comprising:

selecting at least one graphic object;

displaying a graphic object group including the selected at least one graphic object, based on an associated cluster level on the graphic input display device.

20. The method of claim 19, further comprising:

selecting another cluster level of the cluster tree whose corresponding cluster contains the selected at least one graphic object; and

displaying on the graphic input display device another graphic object group based on the selected cluster level.

21. The method of claim 19, wherein the associated cluster level is predetermined.

22. The method of claim 21, wherein the predetermined cluster level corresponds to one of a graphic object, a word, a line, a paragraph or a page.

23. The method of claim 15, further comprising:

selecting at least one graphic object;

displaying a graphic object group including the selected at least one graphic object, based on an associated cluster level on the graphic input display device.

24. The method of claim 23, further comprising:

selecting another cluster level of the cluster tree whose corresponding cluster contains the selected at least one graphic object; and

displaying on the graphic input display device another graphic object group based on the selected cluster level.

25. The method of claim 24, wherein selecting another cluster level includes at least one of:

using an up/down interface to select the cluster level;

using a gesture recognition device to select the cluster level;

using a voice response device to select the cluster level; and

determining the cluster level based on a duration of selection of the at least one graphic object.

26. The method of claim 23, wherein selecting the at least one graphic object includes at least one of:

using an up/down interface to select the at least one graphic object;

using a gesture recognition device to select the at least one graphic object;

using a voice response device to select the at least one graphic object; and

determining the cluster level based on a duration of selection of the at least one graphic object.

27. The method of claim 15, further comprising:

selecting one of the graphic objects from the plurality of graphic objects, and wherein the determining step determines a pairwise distance between a cluster including the selected graphic object and each other graphic object to determine the graphic object closest to the cluster including the selected graphic object, and wherein the merging step merges the cluster containing the selected graphic object and the closest graphic object to define a single cluster.

28. The method of claim 27 further comprising repeating, for each successive cluster level, the determining and the merging steps until at most one cluster exists after the merging step.

29. The method of claim 27, wherein, for each pair of graphic objects X and Y the distance is:

space="preserve" listing-type="equation">D=D.sub.T (X,Y)+α

D.sub.S (X,Y)

where;

D is the pairwise distance;

D_T is the pairwise time distance;

D_S is the pairwise spatial distance; and

α

is a constant relating the time distance to the spatial distance.

30. The method of claim 29, further comprising scaling the spatial distance based upon relative sizes of the plurality of graphic objects.

31. The method of claim 29, further comprising:

selecting at least one graphic object; and

displaying a graphic object group including the selected at least one graphic object, based on an associated cluster level on the graphic input display device.

32. The method of claim 31, further comprising:

selecting another cluster level of the cluster tree whose corresponding cluster contains the selected at least one graphic object; and

displaying on the graphic input display device another graphic object group based on the selected cluster level.

33. The method of claim 32, wherein selecting another cluster level includes at least one of:

using an up/down interface to select the cluster level;

using a gesture recognition device to select the cluster level;

using a voice response device to select the cluster level; and

determining the cluster level based on a duration of selection of the at least one graphic object.

34. The method of claim 31, wherein selecting the at least one graphic object includes at least one of:

using an up/down interface to select the at least one graphic object;

using a gesture recognition device to select the at least one graphic object;

using a voice response device to select the at least one graphic object; and

determining the cluster level based on a duration of selection of the at least one graphic object.

35. A system for dynamically grouping a plurality of graphic objects, comprising:

a graphic input display device for at least displaying the plurality of graphic objects;

a control system communicating with the graphic input display device, the control system forming a cluster tree of the plurality of graphic objects by combining different types of distance measures between at least one pair of graphic objects to form each level of the cluster tree; and

a memory for storing the graphic objects and the cluster tree.

36. The system of claim 35, wherein the control system comprises:

a distance metric generator that determines a distance metric for at least one pair of graphic objects based on the different types of distance measures;

a cluster level generator that generates the cluster levels of the cluster tree based on at least one distance metric generated by the distance metric generator;

a cluster generator that generates the cluster tree; and

a display generator that generates a display of the graphic objects on the graphic input display device based on the cluster tree.

37. The system of claim 36, further comprising a selector usable to select a graphic object and usable to select a cluster level associated with the selected graphic object.

38. The system of claim 37, wherein the selector includes at least one of:

an up/down interface;

a gesture recognition device;

a voice response device; and

a selecting device, wherein the cluster level is determined based on a duration of selection of the at least one graphic object by the selection device.

39. The system of claim 36, wherein the distance metric generator determines the distance metric between each pair of the graphic objects, the pairwise distance metric being a combination of a time distance and a spatial distance.

40. The system of claim 39, wherein, for each pair of graphic objects X and Y, the distance metric is:

space="preserve" listing-type="equation">D=D.sub.T (X,Y)+α

D.sub.S (X,Y)

where;

D is the pairwise distance metric;

D_T is the pairwise time distance;

D_S is the pairwise spatial distance; and

α

is a constant relating the time distance to the spatial distance.