Altering the shape of an artwork

• US 6,642,923 B1
• Filed: 05/04/2000
• Issued: 11/04/2003
• Est. Priority Date: 05/10/1999
• Status: Expired due to Term

• Current Assignee: Canon Information Systems Research Australia Pty Limited (Canon Inc.)
• Original Assignee: Canon Information Systems Research Australia Pty Limited (Canon Inc.)
• Inventors: Stone, Lincoln David, Bock, Oliver
• Primary Examiner(s): Zimmerman, Mark
• Assistant Examiner(s): Sealey, Lance W.
• Application Number:
  US09/564,027
• Time in Patent Office: 1,279 Days
• Field of Search: 345/419, 345/427, 717/8
• US Class Current: 345/427
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

The artwork is defined by a tree structure having leaf nodes comprising objects and parent nodes comprising graphical operators. Each node has fields storing values indicative of horizontal and vertical alteration rules applicable to that node or its sub-tree. The method comprises a selection step, a traversal step and two application steps. In the selection step (300) a target area is selected for fitting the artwork. In the traversal step, the method traverses the nodes of the tree structure (318,342,336,338) traversing one or more of the said nodes. In the first application step, the method applies, for each one of the traversed nodes that is a leaf node, a horizontal alteration rule (344). The horizontal rule re-positions each point within the object comprising the leaf node to another point within a target area, whereby altering the shape of the artwork in a horizontal direction. In the second application step, the method applies a vertical alteration rule (346) in a similar manner as the first application step, whereby altering the shape of the artwork in a vertical direction.

Claims

1. A method of altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising associated graphical objects and parent nodes comprising associated graphical operators, whereby sub-trees of the tree structure comprise associated graphical objects, wherein each node has fields adapted for storing values indicative of one or more associated alteration rules applicable to that node or that node'"'"'s sub-tree, the method comprising the steps of:

selecting a target area for fitting the artwork;

traversing one or more of the nodes; and

applying, for each one of the traversed nodes, one or more said alteration rules associated with said traversed node to each point within the graphical object associated with said traversed node to re-position said each point with respect to the target area, thereby altering the shape of the artwork.

2. A method as claimed in claim 1, wherein one or more of said re-positioned points are re-positioned within the target area.

3. A method as claimed in claim 1, wherein said one or more alteration rules comprise two one-dimensional alteration rules.

4. A method as claimed in claim 1, wherein said artwork has associated therewith a source area.

5. A method as claimed in claim 4, wherein said source and target areas are each a right-angled parallelogram.

6. A method as claimed in claim 5, wherein one of said alteration rules comprises a stretch rule, which is adapted to be implemented by applying a scale factor equivalent to the ratio between the target and source parallelogram heights to the y-coordinates of said points of a said traversed node.

7. A method as claimed in claim 5, wherein one of said alteration rules comprises a stretch rule, which is adapted to be implemented by applying a scale factor equivalent to the ratio between the target and source parallelogram widths to the x-coordinates of said points of a said traversed node.

8. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve outer rule which during the re-positioning ensures that points near the outer edges of the source parallelogram are put near the outer edges of the target parallelogram.

9. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve inner rule which during the re-positioning ensures that points near the middle of the source parallelogram are put near the middle of the target parallelogram.

10. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve left rule which during the re-positioning ensures that points near the left of the source parallelogram are put near the left of the target parallelogram.

11. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve right rule which during the re-positioning ensures that points near the right of the source parallelogram are put near the right of the target parallelogram.

12. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve top rule which during the re-positioning ensures that points near the top of the source parallelogram are put near the top of the target parallelogram.

13. A method as claimed in claim 5, wherein one of said alteration rules comprises a preserve bottom rule which during the re-positioning ensures that points near the bottom of the source parallelogram are put near the bottom of the target parallelogram.

14. A method as claimed in claim 5, wherein the method, prior to the traversal step and after the selection step, further comprises the steps of:

rotating the artwork and associated source parallelogram to the horizontal in the event an axis of the parallelogram is not parallel to the horizontal.

15. A method as claimed in claim 5, wherein the method, prior to the traversal step and after the selection step, further comprises the step of:

rotating the target parallelogram from a non-horizontal orientation to a horizontal orientation.

16. A method as claimed in claim 15, wherein the method, after the application step, further comprises the step of:

rotating the altered artwork to said non-horizontal orientation.

17. A method as claimed in claim 4, wherein the method, prior to traversal step and after said selection step, further comprises the step of:

scaling the artwork so that the source area is equal to the target area.

18. A method as claimed in claim 5, wherein the artwork comprises an image and the method, prior to the traversal step and after the selection step, further comprises the step of:

transforming the target parallelogram for the image to a target parallelogram for the entire artwork.

19. A method of altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each node has fields adapted for storing values indicative of one or more alteration rules applicable to that node or its sub-tree, the method comprising the steps of:

selecting a target area for fitting the artwork;

traversing one or more of the said nodes; and

applying, for each one of the traversed nodes that is a leaf node, a said alteration rule to each point within the graphical object comprising the leaf node to re-position said each point in a first direction with respect to the target area, thereby altering the shape of the artwork in said first direction.

20. A method as claimed in claim 19, wherein said method further comprises the step of:

applying, for each one of the traversed nodes that is a leaf node, a said alteration rule to each point within the graphical object comprising the leaf node to re-position said each point in a second direction with respect to the target area, wherein at least one said graphical object has at least one said alteration rule which is different from at least one said alteration rule of another said graphical object, thereby altering the shape of the artwork in said second direction.

21. A method as claimed in claim 19, wherein said first direction is the horizontal direction.

22. A method as claimed in claim 19, wherein said first direction is the vertical direction.

23. A method as claimed in claim 20, wherein said first direction is the horizontal direction and said second direction is the vertical direction.

24. A method as claimed in claim 19, wherein said artwork has associated therewith a source area.

25. A method as claimed in claim 24, wherein said source and target areas are each a right-angled parallelogram.

26. A method as claimed in claim 25, wherein one of said alteration rules comprises a stretch rule, which is adapted to be implemented by applying a scale factor equivalent to the ratio between the target and source parallelogram heights to the y-coordinates of said points of a said traversed node.

27. A method as claimed in claim 25, wherein one of said alteration rules comprises a stretch rule, which is adapted to be implemented by applying a scale factor equivalent to the ratio between the target and source parallelogram widths to the x-coordinates of said points of a said traversed node.

28. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve outer rule which during the re-positioning ensures that points near the outer edges of the source parallelogram are put near the outer edges of the target parallelogram.

29. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve inner rule which during the re-positioning ensures that points near the middle of the source parallelogram are put near the middle of the target parallelogram.

30. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve left rule which during the re-positioning ensures that points near the left of the source parallelogram are put near the left of the target parallelogram.

31. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve right rule which during the re-positioning ensures that pints near the right of the source parallelogram are put near the right of the target parallelogram.

32. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve top rule which during the re-positioning ensures that points near the top of the source parallelogram are put near the top of the target parallelogram.

33. A method as claimed in claim 25, wherein one of said alteration rules comprises a preserve bottom role which during the re-positioning ensures that points near the bottom of the source parallelogram are put near the bottom of the target parallelogram.

34. A method as claimed in claim 25, wherein the method, prior to the traversal and after the selection step, further comprises the step of:

rotating the artwork and associated source parallelogram to the horizontal in the event an axis of the parallelogram is not parallel to the horizontal.

35. A method as claimed in claim 25, wherein the method, prior to the traversal step and after the selection step, further comprises the step of:

rotating the target parallelogram from a non-horizontal orientation to a horizontal orientation.

36. A method as claimed in claim 24, wherein the method, prior to traversal step and after said selection step, further comprises the step of:

scaling the artwork so that the source area is equal to the target area.

37. A method as claimed in claim 25, wherein the artwork comprises an image component and the method, prior to the traversal step and after the selection step, further comprises the step of:

transforming the target parallelogram given by a user for the image to a target parallelogram for the entire artwork.

38. A method of altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each node has fields adapted for storing values indicative of one or more horizontal and vertical alteration rules applicable to that node or its sub-tree and a field for storing a value indicative of whether or not a mapping restriction is applicable to that node and its sub-tree if any, the method comprising the steps of:

selecting a target area for fitting the artwork;

traversing one or more of the said nodes;

applying, for each of the traversed nodes that has a value indicating a mapping restriction, an affine transformation to the sub-tree of that node;

applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said horizontal alteration rule to each point within the graphical object comprising the leaf node to horizontally re-position said each point with respect to the target area; and

applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said vertical alteration rule to each point within the graphical object comprising the leaf node to vertically re-position said each point with respect to the target area, thereby altering the shape of the artwork.

39. A method as claimed in claim 38, wherein said step of applying an affine transformation comprises the steps of:

obtaining a bounding box, for each of the traversed nodes that have a mapping restriction;

applying horizontal and vertical alteration rules, for each one of the obtained bounding boxes, to the corners of the bounding box to re-position the corners;

computing an affine transformation matrix from the corners and the re-positioned corners; and

applying the computed affine transformation matrix to the sub-tree of the traversed node.

40. A method as claimed in claim 39, wherein said step of applying an affine transformation further comprises, after the application step and prior to the computing step, the following steps:

further re-positioning the corners in order to maintain the aspect ratio of the image associated with the traversed node, in the event the traversed node has a field value indicating that the aspect ratio is to be maintained.

41. A method of adapting for later alteration an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and the method comprises the steps of:

attaching one or more fields to each node for designating horizontal and vertical alteration rules applicable to that node or its sub-tree; and

adding values to said one or more fields indicative of a said horizontal and vertical alteration, wherein the artwork is adapted to be altered in accordance with said alteration rules.

42. A method as claimed in claim 41, wherein the method further comprises:

attaching a field to each node for storing a value indicative of whether or not a mapping restriction is applicable to that node and its sub-tee.

43. A method as claimed in claim 41, wherein the method further comprises:

attaching a field to each node for storing a value indicative of whether the bounding box of that node is a source rectangle within which the artwork fits.

44. Apparatus for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising associated graphical objects and parent nodes comprising associated graphical operators, whereby sub-trees of the tree structure comprise associated graphical objects, wherein each node has fields adapted for storing values indicative of one or more associated alteration rules applicable to that node or that node'"'"'s sub-tree, the apparatus comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of said nodes; and

means for applying, for each one of the traversed nodes, one or more said alteration rules associated with said traversed node to each point within the graphical object associated with said traversed node to re-position said each point with respect to the target area, thereby altering the shape of the artwork.

45. Apparatus for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each node has fields adapted for storing values indicative of one or more alteration rules applicable to that node or its sub-tree, the apparatus comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of the said nodes; and

means for applying, for each one of the traversed nodes that is a leaf node, a said alteration rule to each point within the graphical object comprising the leaf node to re-position said each point in a first direction with respect to the target area, thereby altering the shape of the artwork in said first direction.

46. Apparatus for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each nude has fields adapted for storing values indicative of one or more horizontal and vertical alteration rules applicable to that node or its sub-tree and a field for storing a value indicative of whether or not a mapping restriction is applicable to that node and its sub-tree if any, the apparatus comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of the said nodes;

means for applying, for each of the traversed nodes that has a value indicating a mapping restriction, an affine transformation to the sub-tree of that node;

means for applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said horizontal alteration rule to each point within the graphical object comprising the leaf node to horizontally re-position said each point with respect to the target area; and

means for applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said vertical alteration rule to each point within the graphical object comprising the leaf node to vertically re-position said each point with respect to the target area, thereby altering the shape of the artwork.

47. Apparatus for adapting for later alteration an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and the apparatus comprises:

means for attaching one or more fields to each node for designating horizontal and vertical alteration rules applicable to that node or its sub-tree; and

means for adding values to said one or more fields indicative of a said horizontal and vertical alteration, wherein the artwork is adapted to be altered in accordance with said alteration rules.

48. A computer readable medium comprising a computer program for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising associated graphical objects and parent nodes comprising associated graphical operators, whereby sub-trees of the tree structure comprise associated graphical objects, and wherein each node has fields adapted for storing values indicative of one or more associated alteration rules applicable to that node or that node'"'"'s sub-tree, the computer program comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of said nodes; and

means for applying, for each one of the traversed nodes, one or more said alteration rules associated with said traversed node to each point within the graphical object associated with said traversed node to re-position said each point with respect to the target area, thereby altering the shape of the artwork.

49. A computer readable medium comprising a computer program for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each node has fields adapted for storing values indicative of one or more alteration, rules applicable to that node or its sub-tree, the computer program comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of the said nodes; and

means for applying, for each one of the traversed nodes that is a leaf node, a said alteration rule to each point within the graphical object comprising the leaf node to re-position said each point in a first direction with respect to the target area, thereby altering the shape of the artwork in said first direction.

50. A computer readable medium comprising a computer program for altering the shape of an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and wherein each node has fields adapted for storing values indicative of one or more horizontal and vertical alteration rules applicable to that node or its sub-tree and a field for storing a value indicative of whether or not a mapping restriction is applicable to that node and its sub-tree if any, the computer program comprising:

means for selecting a target area for fitting the artwork;

means for traversing one or more of the said nodes;

means for applying, for each of the traversed nodes that has a value indicating a mapping restriction, an affine transformation to the sub-tree of that node;

means for applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said horizontal alteration rule to each point within the a graphical object comprising the leaf node to horizontally re-position said each point with respect to the target area; and

means for applying, for each one of the traversed nodes that is a leaf node and has a value indicating no mapping restriction, a said vertical alteration rule to each point within the graphical object comprising the leaf node to vertically re-position said each point with respect to the target area, thereby altering the shape of the artwork.

51. A computer readable medium comprising a computer program for adapting for later alteration an artwork, wherein the artwork is defined by a tree structure having leaf nodes comprising graphical objects and parent nodes comprising graphical operators, and the computer program comprises:

means for attaching one or more fields to each node for designating horizontal and vertical alteration rules applicable to that node or its sub-tree; and

means for adding values to said one or more fields indicative of a said horizontal and vertical alteration, wherein the artwork is adapted to be altered in accordance with said alteration rules.