Method and apparatus for automatically positioning images within a region

• US 6,636,650 B1
• Filed: 05/05/2000
• Issued: 10/21/2003
• Est. Priority Date: 05/10/1999
• Status: Expired due to Term

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Politis, George, Long, Timothy Merrick, Herceg, Marija, Stone, Lincoln David
• Primary Examiner(s): Tran, Phuoc
• Application Number:
  US09/565,469
• Time in Patent Office: 1,264 Days
• Field of Search: 382/295, 382/294, 345/634, 345/639, 345/640
• US Class Current: 382/295
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text

Abstract

A method of automatically positioning one or more images within a region. The method comprises of computing (101) a field at each image due to every other image, wherein the field at any image due to any other image is a function of the distance between any image and any other image and the surface area of that any other image. The method then computates (102) a net force exerted on each image by every other image, wherein the net force acting on any one image is a function of the field acting on the said any one image and a characteristic of the said any one image. The method then moves (104) each image a distance, which is a function of the net force acting on the image, in the direction of the net force.

Claims

1. A method of automatically positioning a plurality of images within a region, the method comprising the steps of:

(a) computing a net force exerted on each said image by all other said images, wherein the net force exerted on each said image is the total of forces exerted on that image, and wherein any said force exerted on any one said image by any other said image is a function of the distance between the said any one image and the said any other image, a first image characteristic of said any one image and a second image characteristic of said any other image; and

(b) moving each said image a distance, which is a function of the net force acting on the image, in the direction of the net force.

2. A method as claimed in claim 1, wherein said step (a) comprises the sub-step of:

(a)(i) computing all fields at each said image due to every other said image, wherein any said field at any said image due to any other said image is a function of the distance between said any image and said any other image and the second image characteristic of said any other image.

3. A method as claimed in claim 2, wherein step (a) further comprises the sub-steps of:

(a)(ii) summing all the fields at each said image to provide a net field at each said image; and

(a)(iii) computing the net force exerted on each said image by every other said image, wherein the net force acting on any one said image is a function of the net field acting on the said any one image and the first image characteristic of said any one image.

4. A method as claimed in claim 2, wherein said step (a) further comprises the sub-steps of:

(a)(ii) computing all forces at each said image due to every other said image, wherein any said force acting on any one said image is a function of a said field acting on the said any one image and the first image characteristic of the said any one image; and

(a)(iii) summing the forces exerted on each image to produce a said net force at each image.

5. A method as claimed in claim 1, wherein the method further comprises the step of:

(c) iteratively repeating steps (a) to (b).

6. A method as claimed in claim 5, wherein the iterations stop after a predetermined number of iterations have been completed.

7. A method as claimed in claim 5, wherein the iterations stop after the moved distances are less than a predetermined threshold.

8. A method as claimed in claim 2, wherein the field at any said image due to another said image is inversely proportional to a polynomial of the distance between them.

9. A method as claimed in claim 2, wherein the field at any said image due to another said image is inversely proportional to the distance between them.

10. A method as claimed in claim 2, wherein the field at any said image due to another said image is inversely proportional to the square of the distance between them.

11. A method as claimed in claim 2, wherein the field at any said image due to another said image decreases as the distance between them increases.

12. A method as claimed in claim 2, wherein one or more of said fields have an elliptical field as a near field and a circular field as a far field.

13. A method as claimed in claim 4, wherein one or more of said fields are elliptical fields having a main axis non-parallel with the main axis of the region and step a(i) further comprises the following sub-step for each elliptical field:

rotating, prior to computing the fields, the main axis of the region by some angle whereby the main axis of the elliptical field is parallel to the main axis of the region; and

step a(ii) further comprises the following sub-step for each elliptical field; and

rotating, after computing the forces, the main axis of the region by an angle equal but opposite to said some angle.

14. A method as claimed in claim 3, wherein one or more of said fields are elliptical fields having a main axis non-parallel with the main axis of the region and step a(i) further comprises the following sub-steps for each elliptical field:

rotating, prior to computing the fields, the main axis of the region by some angle whereby the main axis of the elliptical field is parallel to the main axis of the region; and

rotating, after computing the fields, the main axis of the region by an angle equal but opposite to said some angle.

15. A method as claimed in claim 2, wherein the images are defined by a height h and width w and said computing step (a)(i) comprises:

computing a field E at each said image due to every other said image, where a said field E due to a said image at a distance p from the centre of the image is $E=\frac{\mathrm{\alpha <br><br>}}{{\left(\frac{d_x}{w}\right)}^2+{\left(\frac{d_y}{h}\right)}^2}+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>\frac{\mathrm{wh}}{d_x^2+d_y^2},$

 

where $\mathrm{\alpha <br><br>}=\frac{\mathrm{wh}}{p^2}$

when p is greater than {square root over (wh)} and α

=1 when p is less than or equal to {square root over (wh)}, and d_x is the horizontal distance and d_y is the vertical distance components of distance p.

16. A method as claimed in claim 1, wherein said first and second image characteristic are the same.

17. A method as claimed in claim 1, wherein said first and second image characteristic are different.

18. A method as claimed in claim 16, wherein the first image characteristic is the surface area wh of the image.

19. A method as claimed in claim 16, wherein the first image characteristic is the perimeter 2w+2h of the image.

20. A method as claimed in claim 2, wherein said step (a) comprises:

computing the total of forces exerted on each said image by every other said image, wherein said total of forces acting on any one said image is equal to the sum of the fields acting on the said any one image multiplied by the surface area wh of the said any one image.

21. A method as claimed in claim 1, wherein said step (b) comprises moving each said image a distance equal to a proportional factor of the net force exerted on it, in the direction of the net force.

22. A method as claimed in claim 21, wherein the proportional factor is equal to 0.001.

23. A method as claimed in claim 21, wherein the proportional factor is determined during the first iteration.

24. A method as claimed in claim 1, wherein the force on any said image by a boundary of the region is the same as would be exerted by an imaginary image of the same shape and size on the opposite side of the boundary at the same distance from the boundary.

25. A method as claimed in claim 1, wherein said plurality of said images comprise one image and a plurality of imaginary images, wherein the imaginary images are the same shape and size of said one image, are located on the opposite side of a corresponding boundary of the region, and exert a said force on said one image.

26. A method as claimed in claim 1, wherein said images, region and field are two-dimensional.

27. A method as claimed in claim 1, wherein said images, region and field are three-dimensional.

28. A method as claimed in claim 1, wherein said step (b) comprises moving each said image a distance dependent upon acceleration and instantaneous velocity associated with the net force and mass of the image, where said mass is dependent on the size of the image.

29. A method as claimed in claim 1, wherein said region is a page on a electronic photo-album.

30. A method of automatically positioning a plurality of images within a layout region, wherein the images are defined by a height h and width w and the method comprises the following steps of:

(a) computing a field E at each said image due to every other said image, where a said field E due to a said image at a distance p from the centre of the image is $E=\frac{\mathrm{\alpha <br><br>}}{{\left(\frac{d_x}{w}\right)}^2+{\left(\frac{d_y}{h}\right)}^2}+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>\frac{\mathrm{wh}}{d_x^2+d_y^2},$

 

where $\mathrm{\alpha <br><br>}=\frac{\mathrm{wh}}{p^2}$

when p is greater than {square root over (wh)} and α

=1 when p is less than or equal to {square root over (wh)}, and d_x is the horizontal distance and d_y is the vertical distance components of distance p;

(b) computing a sum of forces exerted on each said image by every other said image, where said sum of forces acting on any said image is equal to a sum of said fields acting on said any image multiplied by the surface area wh of said any image;

(c) moving each said image a distance proportional to the sum of forces acting on the image, in the direction of the sum of forces; and

(d) repeating steps (a) to (c) a predetermined number of times.

31. A method as claimed in claim 30, wherein the force on any said image by a boundary of the region is the same as would be exerted by an imaginary image of the same shape and size on the opposite side of the boundary at the same distance from the boundary.

32. A method as claimed in claim 30, wherein said plurality of said images comprise one image and a plurality of imaginary images, wherein the imaginary images are the same shape and size of said one image, are located on the opposite side of a corresponding boundary of the region, and exert a said force on said one image.

33. A method of automatically positioning one image within a region of one or more other images, the method comprising the steps of:

(a) computing a net force exerted on said one image by all of said other images, wherein the net force exerted on said one image is the total of forces exerted on that image, and wherein any said force exerted on said one image by any one of said other images is a function of the distance between the said one image and the said any one of the said other images, a first image characteristic of said one image and a second image characteristic of said any one of the said other images; and

(b) moving said one image a distance, which is a function of the net force acting on the said one image, in the direction of the net force.

34. Apparatus for automatically positioning a plurality of images within a region, the apparatus comprising:

means for computing a net force exerted on each said image by all other said images, wherein the net force exerted on each said image is the total of forces exerted on that image, and wherein any said force exerted on any one said image by any other said image is a function of the distance between the said any one image and the said any other image, a first image characteristic of said any one image and a second image characteristic of said any other image; and

means for moving each said image a distance, which is a function of the net force acting on the image, in the direction of the net force.

35. Apparatus for automatically positioning a plurality of images within a layout region, wherein the images are defined by a height h and width w and the apparatus comprises:

means for computing a field E at each said image due to every other said image, where a said field E due to a said image at a distance p from the centre of the image is $E=\frac{\mathrm{\alpha <br><br>}}{{\left(\frac{d_x}{w}\right)}^2+{\left(\frac{d_y}{h}\right)}^2}+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>\frac{\mathrm{wh}}{d_x^2+d_y^2},$

 

where $\mathrm{\alpha <br><br>}=\frac{\mathrm{wh}}{p^2}$

when p is greater than {square root over (wh)} and α

=1 when p is less than or equal to {square root over (wh)}, and d_x is the horizontal distance and d_y is the vertical distance components of distance p;

means for computing a sum of forces exerted on each said image by every other said image, where said sum of forces acting on any said image is equal to a sum of said fields acting on said any image multiplied by the surface area wh of said any image;

means for moving each said image a distance proportional to the sum of forces acting on the image, in the direction of the sum of forces; and

means for repeating the operations of the means for computing a field, the means for a sum of forces, and the means for moving a predetermined number of times.

36. Apparatus for automatically positioning one image within a region of one or more other images, the apparatus comprising:

means for computing a net force exerted on said one image by all of said other images, wherein the net force exerted on said one image is the total of forces exerted on that image, and wherein any said force exerted on said one image by any one of said other images is a function of the distance between the said one image and the said any one of the said other images, a first image characteristic of said one image and a second image characteristic of said any one of the said other images; and

means for moving said one image a distance, which is a function of the net force acting on the said one image, in the direction of the net force.

37. A computer readable medium comprising a computer program for automatically positioning a plurality of images within a region, the computer program comprising:

code for computing a net force exerted on each said image by all other said images, wherein the net force exerted on each said image is the total of forces exerted on that image, and wherein any said force exerted on any one said image by any other said image is a function of the distance between the said any one image and the said any other image, a first image characteristic of said any one image and a second image characteristic of said any other image; and

code for moving each said image a distance, which is a function of the net force acting on the image, in the direction of the net force.

38. A computer readable medium as claimed in claim 37, wherein said code for computing a net force comprises:

code for computing all fields at each said image due to every other said image, wherein any said field at any said image due to any other said image is a function of the distance between said any image and said any other image and the second image characteristic of said any other image.

39. A computer readable medium as claimed in claim 38, wherein said code for computing a net force further comprises:

code for summing all the fields at each said image to provide a net field at each said image; and

code for computing the net force exerted on each said image by every other said image, wherein the net force acting on any one said image is a function of the net field acting on the said any one image and the first image characteristic of said any one image.

40. A computer readable medium as claimed in claim 38, wherein said code for computing a net force further comprises:

code for computing all forces at each said image due to every other said image, wherein any said force acting on any one said image is a function of a said field acting on the said any one image and the first image characteristic of the said any one image; and

code for summing the forces exerted on each image to produce a said net force at each image.

41. A computer readable medium as claimed in claim 37, wherein the computer program further comprises:

code for iteratively repeating the operations of the code for computing the net force and the code for moving.

42. A computer readable medium comprising a computer program for automatically positioning a plurality of images within a layout region, wherein the images are defined by a height h and width w and the computer program comprises:

code for computing a field E at each said image due to every other said image, where a said field E due to a said image at a distance p from the centre of the image is $E=\frac{\mathrm{\alpha <br><br>}}{{\left(\frac{d_x}{w}\right)}^2+{\left(\frac{d_y}{h}\right)}^2}+\left(1-\mathrm{\alpha <br><br>}\right)<br><br>\frac{\mathrm{wh}}{d_x^2+d_y^2},$

 

where $\mathrm{\alpha <br><br>}=\frac{\mathrm{wh}}{p^2}$

when p is greater than {square root over (wh)} and α

=1 when p is less than or equal to {square root over (wh)}, and d_x is the horizontal distance and d_y is the vertical distance components of distance p;

code for computing a sum of forces exerted on each said image by every other said image, where said sum of forces acting on any said image is equal to a sum of said fields acting on said any image multiplied by the surface area wh of said any image;

code for moving each said image a distance proportional to the sum of forces acting on the image, in the direction of the sum of forces; and

code for repeating the operations of the means for computing a field, the means for a sum of forces, and the means for moving a predetermined number of times.

43. A computer readable medium comprising a computer program for automatically positioning one image within a region of one or more other images, the computer program comprising:

code for computing a net force exerted on said one image by all of said other images, wherein the net force exerted on said one image is the total of forces exerted on that image, and wherein any said force exerted on said one image by any one of said other images is a function of the distance between the said one image and the said any one of the said other images, a first image characteristic of said one image and a second image characteristic of said any one of the said other images; and

code for moving said one image a distance, which is a function of the net force acting on the said one image, in the direction of the net force.