Automated bounding box generation within the boundaries of arbitrary shapes

• US 9,082,189 B2
• Filed: 08/12/2011
• Issued: 07/14/2015
• Est. Priority Date: 08/12/2011
• Status: Active Grant

• Current Assignee: Oracle International Corporation (Oracle Corporation)
• Original Assignee: Oracle International Corporation (Oracle Corporation)
• Inventors: Look, Gary, Singh, Prashant
• Primary Examiner(s): Merouan, Abderrahim
• Application Number:
  US13/208,481
• Publication Number:
  US 20130038628A1
• Time in Patent Office: 1,432 Days
• Field of Search: 707/803, 707/812, 707/804, 345/619, 345/420, 345/424, 345/620, 345/622, 382/206, 382/286, 382/291, 382/203, 382/204
• US Class Current: 1/1
• CPC Class Codes: G06T 11/40 Filling a planar surface by adding surface attributes, e.g. colour or texture
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/30 Clipping
• CPC Class Codes: G06T 15/40 Hidden part removal
• CPC Class Codes: G06T 2210/12 Bounding box
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06V 10/245 by locating a pattern; Special marks for positioning

Abstract

One embodiment is directed to a computer program, embodied on a computer readable medium. The computer program is configured to control a processor to execute instructions. The instructions include sampling a plurality of points that lie within the interior of an arbitrary shape, drawing one or more rectangles from each of the points, gradually increasing the length and width of the rectangles until the rectangles no longer falls within the interior of the arbitrary shape, and assigning the largest of the increased rectangles as the interior bounding box.

Claims

1. A computer program, embodied on a non-transitory computer readable medium, the computer program configured to control a processor to automatically generate a bounding box, the generating comprising:

sampling a plurality of points that lie within an interior of an arbitrary shape;

automatically creating a rectangle from each of the points, wherein each of the rectangles lies completely within the interior and each rectangle comprises a pair of height sides and a pair of width sides;

increasing the height sides and the width sides of the rectangles until each of the rectangles touches at least one side of the arbitrary shape;

assigning a largest of the increased rectangles as an interior bounding box for the arbitrary shape, wherein the largest of the increased rectangles is the rectangle that has the largest area of the increased rectangles; and

placing an item within the interior bounding box, wherein the item is contained within the arbitrary shape and the item is at least one of an image or text.

2. The computer program embodied on a non-transitory computer readable medium according to claim 1, wherein each of the plurality of points is a point at a center of a square of a grid that is overlaid on the arbitrary shape.

3. The computer program embodied on a non-transitory computer readable medium according to claim 2, wherein the point at the center of the square is used as an upper-left hand corner for the rectangles.

4. The computer program embodied on a non-transitory computer readable medium according to claim 1, wherein the increasing comprises first increasing the width sides of the rectangle until at least a portion of the left and right height sides of the rectangles touch the arbitrary shape, and then increasing the height sides of the rectangles until at least a portion of the top and bottom width sides of the rectangles touch the arbitrary shape.

5. The computer program embodied on a non-transitory computer readable medium according to claim 1, wherein the increasing comprises first increasing the height sides of the rectangles until at least a portion of the top and bottom width sides of the rectangles touch the arbitrary shape, and then increasing the width sides of the rectangle until at least a portion of the left and right height sides of the rectangles touch the arbitrary shape.

6. The computer program embodied on a non-transitory computer readable medium according to claim 1, wherein the increasing comprises alternately increasing the height sides and width sides of the rectangles until at least a portion of all four sides of the rectangles touch the arbitrary shape.

7. A method for automatically generating a bounding box within an arbitrary shape, the method comprising:

sampling a plurality of points that lie within interior bounds of an arbitrary shape;

automatically creating a rectangle from each of the sampled points, wherein each of the rectangles lies completely within the interior and each rectangle comprises a pair of height sides and a pair of width sides;

stretching the height sides and the width sides of each of the rectangles until they no longer fall within the interior of the arbitrary shape;

assigning the largest of the stretched rectangles as the interior bounding box, wherein the largest of the stretched rectangles is the rectangle that has the largest area of the stretched rectangles; and

placing an item within the interior bounding box, wherein the item is contained within the arbitrary shape and the item is at least one of an image or text.

8. The method according to claim 7, wherein each of the plurality of points is a point at a center of a square of a grid that is overlaid on the arbitrary shape.

9. The method according to claim 8, wherein the point at the center of the square is used as an upper-left hand corner for the rectangles.

10. The method according to claim 7, wherein the stretching comprises first increasing the width sides of the rectangle until at least a portion of the left and right height sides of the rectangles touch the arbitrary shape, and then increasing the height sides of the rectangles until at least a portion of the top and bottom width sides of the rectangles touch the arbitrary shape.

11. The method according to claim 7, wherein the stretching comprises first increasing the height sides of the rectangles until at least a portion of the top and bottom width sides of the rectangles touch the arbitrary shape, and then increasing the width sides of the rectangle until at least a portion of the left and right height sides of the rectangles touch the arbitrary shape.

12. The method according to claim 7, wherein the stretching comprises alternately increasing the height sides and width sides of the rectangles until at least a portion of all four sides of the rectangles touch the arbitrary shape.

13. An apparatus for placing an item within an arbitrary shape, the apparatus comprising:

a processor;

a storage device coupled to the processor and storing a bounding box module, the bounding box module, when executed by the processor, causing the processor to implement a sampler, a generator and an assignor;

the sampler configured to sample a plurality of points that lie within an interior of the arbitrary shape;

the generator configured to automatically create a rectangle comprising a pair of height sides and a pair of width sides from each of the points, and to increase the height sides and the width sides of the rectangles until each of the rectangles touches at least one side of the arbitrary shape;

the assignor configured to assign a largest of the increased rectangles as the interior bounding box, wherein the largest of the increased rectangles is the rectangle that has the largest area of the increased rectangles, and place the item within the interior bounding box, wherein the item is contained within the arbitrary shape and the item is at least one of an image or text.

14. The apparatus according to claim 13, wherein each of the plurality of points is a point within the shape at a center of a square of a grid that is overlaid on the shape.

15. The apparatus according to claim 14, wherein the point at the center of the square is used as an upper-left hand corner for the rectangles.

16. The apparatus according to claim 13, wherein the generator is configured to increase the height sides and width sides of the rectangles by first increasing the width sides of the rectangles until at least a portion of the left and right height sides of the rectangles touch the arbitrary shape, and then increasing the height sides of the rectangles until at least a portion of top and bottom width sides of the rectangles touch the arbitrary shape.

17. The apparatus according to claim 13, wherein the generator is configured to increase the height and width sides of the rectangles by first increasing the height sides of the rectangles until at least a portion of the top and bottom width sides of the rectangles touch the arbitrary shape, and then increasing the width sides of the rectangle until at least a portion of left and right height sides of the rectangles touch the arbitrary shape.

18. The apparatus according to claim 13, wherein the generator is configured to increase the height and width sides of the rectangles by alternately increasing the height and width sides of the rectangles until at least a portion of all four sides of the rectangles touch the arbitrary shape.