Specification
Description:FORM 2
THE PATENTS ACT, 1970
(39 of 1970)
&
THE PATENT RULES, 2003
COMPLETE SPECIFICATION
(See Section 10 and Rule 13)
Title of invention:
METHOD AND SYSTEM FOR OPTIMAL PACKING OF BOUNDING BOXES IN IMAGE FOREGROUND
Applicant
Tata Consultancy Services Limited
A company Incorporated in India under the Companies Act, 1956
Having address:
Nirmal Building, 9th floor,
Nariman point, Mumbai 400021,
Maharashtra, India
Preamble to the description:
The following specification particularly describes the invention and the manner in which it is to be performed.
TECHNICAL FIELD
The disclosure herein generally relates to image processing, and, more particularly, to a method and system for optimal packing of bounding boxes in an image foreground.
BACKGROUND
In the context of synthetic defect data generation for computer vision applications, a subproblem arises wherein multiple defect regions belonging to various defect categories need to be placed, overlaid and packed into the foreground object of interest, within an image. In the general scenario, defect regions do not overlap since defects of various types do not co-occur. Scaling and packing arbitrary shaped regions within the foreground region of object of interest can be converted into the problem of packing the corresponding bounding boxes. In other words, the problem can be transformed into packing various bounding boxes of defect regions within the overall bounding box of the foreground representing the object of interest.
The closest equivalent of this optimization problem is the box-packing problem in operations research. However, none of them deal with the resizing aspect of boxes while maintaining their aspect ratios, and while obeying certain separation constraints. This renders the formulation of this problem different from that of the box packing problem in terms of both the optimization objective as well as the constraints on the solution.
SUMMARY
Embodiments of the present disclosure present technological improvements as solutions to one or more of the above-mentioned technical problems recognized by the inventors in conventional systems. For example, in one embodiment, a processor implemented method is provided. The method includes receiving, via one or more hardware processors, an input data comprising a) an outer box, wherein the outer box is a bounding box of a foreground object of interest, b) one or more inner boxes, and c) one or more inter-box separation related parameters, as input data. Further, a set of points associated with a plurality of centroids of each of the one or more inner boxes, within the outer box is sampled, via the one or more hardware processors, to satisfy a plurality of constraints, wherein each of the plurality of constraints is associated with a minimum absolute separation between the plurality of centroids. Further, each of the one or more inner boxes is placed, via the one or more hardware processors, at the sampled set of points associated with the plurality of centroids of each of the one or more inner boxes, wherein centroid of each of the one or more inner boxes is overlaid on each of the sampled set of points within the outer box. Further, it is determined if one or more sides of any of the placed one or more inner boxes have extended beyond one or more sides of the outer box, via the one or more hardware processors. Further, portion of the placed one or more inner boxes that has been determined as to have extended beyond the one or more sides of the outer box is trimmed out, via the one or more hardware processors. Further, the placed one or more inner boxes are scaled, via the one or more hardware processors, by processing each of a plurality of pairs of the inner boxes from among the plurality of inner boxes, to cause maximization of associated post-placement sizes satisfying the plurality of constraints, for optimal packing.
In an embodiment, the plurality of constraints used in the method include a) one or more box overlap constraints, b) at least one constraint associated with sampling distribution of centroids of the one or more inner boxes, c) at least one constraint associated with a minimum absolute separation during placement of the one or more inner boxes, d) at least one constraint associated with a minimum relative separation during placement of the one or more inner boxes, e) one or more constraints associated with protruding of the one or more inner boxes, and f) one or more constraints associated with order of placement of the one or more inner boxes.
In yet another embodiment, a system is provided. The system includes one or more hardware processors, a communication interface, and a memory storing a plurality of instructions. The plurality of instructions cause the one or more hardware processors to receive an input data comprising a) an outer box, wherein the outer box is a bounding box of a foreground object of interest, b) one or more inner boxes, and c) one or more inter-box separation related parameters, as input data. Further, a set of points associated with a plurality of centroids of each of the one or more inner boxes, within the outer box is sampled, via the one or more hardware processors, to satisfy a plurality of constraints, wherein each of the plurality of constraints is associated with a minimum absolute separation between the plurality of centroids. Further, each of the one or more inner boxes is placed, via the one or more hardware processors, at the sampled set of points associated with the plurality of centroids of each of the one or more inner boxes, wherein centroid of each of the one or more inner boxes is overlaid on each of the sampled set of points within the outer box. Further, it is determined if one or more sides of any of the placed one or more inner boxes have extended beyond one or more sides of the outer box, via the one or more hardware processors. Further, portion of the placed one or more inner boxes that has been determined as to have extended beyond the one or more sides of the outer box is trimmed out, via the one or more hardware processors. Further, the placed one or more inner boxes are scaled, via the one or more hardware processors, by processing each of a plurality of pairs of the inner boxes from among the plurality of inner boxes, to cause maximization of associated post-placement sizes satisfying the plurality of constraints, for optimal packing.
In yet another embodiment, the plurality of constraints used by the system include a) one or more box overlap constraints, b) at least one constraint associated with sampling distribution of centroids of the one or more inner boxes, c) at least one constraint associated with a minimum absolute separation during placement of the one or more inner boxes, d) at least one constraint associated with a minimum relative separation during placement of the one or more inner boxes, e) one or more constraints associated with protruding of the one or more inner boxes, and f) one or more constraints associated with order of placement of the one or more inner boxes.
In yet another aspect, a non-transitory computer readable medium is provided. The non-transitory computer readable medium includes a plurality of instructions, which when executed, cause the one or more hardware processors to receive an input data comprising a) an outer box, wherein the outer box is a bounding box of a foreground object of interest, b) one or more inner boxes, and c) one or more inter-box separation related parameters, as input data. Further, a set of points associated with a plurality of centroids of each of the one or more inner boxes, within the outer box is sampled, via the one or more hardware processors, to satisfy a plurality of constraints, wherein each of the plurality of constraints is associated with a minimum absolute separation between the plurality of centroids. Further, each of the one or more inner boxes is placed, via the one or more hardware processors, at the sampled set of points associated with the plurality of centroids of each of the one or more inner boxes, wherein centroid of each of the one or more inner boxes is overlaid on each of the sampled set of points within the outer box. Further, it is determined if one or more sides of any of the placed one or more inner boxes have extended beyond one or more sides of the outer box, via the one or more hardware processors. Further, portion of the placed one or more inner boxes that has been determined as to have extended beyond the one or more sides of the outer box is trimmed out, via the one or more hardware processors. Further, the placed one or more inner boxes are scaled, via the one or more hardware processors, by processing each of a plurality of pairs of the inner boxes from among the plurality of inner boxes, to cause maximization of associated post-placement sizes satisfying the plurality of constraints, for optimal packing.
In yet another embodiment, the plurality of constraints used by the non-transitory computer readable medium include a) one or more box overlap constraints, b) at least one constraint associated with sampling distribution of centroids of the one or more inner boxes, c) at least one constraint associated with a minimum absolute separation during placement of the one or more inner boxes, d) at least one constraint associated with a minimum relative separation during placement of the one or more inner boxes, e) one or more constraints associated with protruding of the one or more inner boxes, and f) one or more constraints associated with order of placement of the one or more inner boxes.
It is to be understood that both the foregoing general description and the following detailed description are exemplary and explanatory only and are not restrictive of the invention, as claimed.
BRIEF DESCRIPTION OF THE DRAWINGS
The accompanying drawings, which are incorporated in and constitute a part of this disclosure, illustrate exemplary embodiments and, together with the description, serve to explain the disclosed principles:
FIG. 1 illustrates an exemplary system for box packing, according to some embodiments of the present disclosure.
FIG. 2 is a flow diagram depicting steps involved in the process of box packing being performed by the system of FIG. 1, according to some embodiments of the present disclosure.
FIGS. 3A through 3J depict scaling of the one or more inner boxes, by the system of FIG. 1, in accordance with some embodiments of the present disclosure.
FIGS. 4A through 4D depict examples of various overlapping patterns of the one or more inner boxes, according to some embodiments of the present disclosure.
FIGS. 5A through 5C depict shrinking of the one or more inner boxes, by the system of FIG. 1, in accordance with some embodiments of the present disclosure.
DETAILED DESCRIPTION OF EMBODIMENTS
Exemplary embodiments are described with reference to the accompanying drawings. In the figures, the left-most digit(s) of a reference number identifies the figure in which the reference number first appears. Wherever convenient, the same reference numbers are used throughout the drawings to refer to the same or like parts. While examples and features of disclosed principles are described herein, modifications, adaptations, and other implementations are possible without departing from the scope of the disclosed embodiments.
The closest equivalent of optimization problem is the box-packing problem in operations research. However, none of these approaches deals with resizing aspect of boxes while maintaining their aspect ratios, and while obeying certain separation constraints. This renders the formulation of this problem different from that of the box packing problem in terms of both the optimization objective as well as the constraints on the solution. To address these challenges, method and system disclosed in the embodiments herein provide an approach for box packing which includes packing of inner boxes within an outer box of a foreground object.
The method includes receiving an input data comprising a) an outer box, wherein the outer box is a bounding box of a foreground object of interest, b) one or more inner boxes, and c) one or more inter-box separation related parameters, as input data. Further, a set of points associated with a plurality of centroids of each of the one or more inner boxes, within the outer box is sampled to satisfy a plurality of constraints, wherein each of the plurality of constraints is associated with a minimum absolute separation between the plurality of centroids. Further, each of the one or more inner boxes is placed at the sampled set of points associated with the plurality of centroids of each of the one or more inner boxes, wherein centroid of each of the one or more inner boxes is overlaid on each of the sampled set of points within the outer box. Further, it is determined if one or more sides of any of the placed one or more inner boxes have extended beyond one or more sides of the outer box. Further, portion of the placed one or more inner boxes that has been determined as to have extended beyond the one or more sides of the outer box is trimmed out. Further, the placed one or more inner boxes are scaled by processing each of a plurality of pairs of the inner boxes from among the plurality of inner boxes, to cause maximization of associated post-placement sizes satisfying the plurality of constraints, for optimal packing.
Referring now to the drawings, and more particularly to FIG. 1 through FIG. 5C, where similar reference characters denote corresponding features consistently throughout the figures, there are shown preferred embodiments and these embodiments are described in the context of the following exemplary system and/or method.
FIG. 1 illustrates an exemplary system for box packing, according to some embodiments of the present disclosure. In the context of the embodiments disclosed herein, the term “box packing” refers to packing of inner boxes covering defects / defect regions, inside an outer box containing a foreground object on which the defects are present. The system 100 includes or is otherwise in communication with hardware processors 102, at least one memory such as a memory 104, an I/O interface 112. The hardware processors 102, memory 104, and the Input /Output (I/O) interface 112 may be coupled by a system bus such as a system bus 108 or a similar mechanism. In an embodiment, the hardware processors 102 can be one or more hardware processors.
The I/O interface 112 may include a variety of software and hardware interfaces, for example, a web interface, a graphical user interface, and the like. The I/O interface 112 may include a variety of software and hardware interfaces, for example, interfaces for peripheral device(s), such as a keyboard, a mouse, an external memory, a printer and the like. Further, the I/O interface 112 may enable the system 100 to communicate with other devices, such as web servers, and external databases.
The I/O interface 112 can facilitate multiple communications within a wide variety of networks and protocol types, including wired networks, for example, local area network (LAN), cable, etc., and wireless networks, such as Wireless LAN (WLAN), cellular, or satellite. For the purpose, the I/O interface 112 may include one or more ports for connecting several computing systems with one another or to another server computer. The I/O interface 112 may include one or more ports for connecting several devices to one another or to another server.
The one or more hardware processors 102 may be implemented as one or more microprocessors, microcomputers, microcontrollers, digital signal processors, central processing units, node machines, logic circuitries, and/or any devices that manipulate signals based on operational instructions. Among other capabilities, the one or more hardware processors 102 is configured to fetch and execute computer-readable instructions stored in the memory 104.
The memory 104 may include any computer-readable medium known in the art including, for example, volatile memory, such as static random-access memory (SRAM) and dynamic random-access memory (DRAM), and/or non-volatile memory, such as read only memory (ROM), erasable programmable ROM, flash memories, hard disks, optical disks, and magnetic tapes. In an embodiment, the memory 104 includes a plurality of modules 106.
The plurality of modules 106 include programs or coded instructions that supplement applications or functions performed by the system 100 for executing different steps involved in the process of box packing, being performed by the system 100. The plurality of modules 106, amongst other things, can include routines, programs, objects, components, and data structures, which performs particular tasks or implement particular abstract data types. The plurality of modules 106 may also be used as, signal processor(s), node machine(s), logic circuitries, and/or any other device or component that manipulates signals based on operational instructions. Further, the plurality of modules 106 can be used by hardware, by computer-readable instructions executed by the one or more hardware processors 102, or by a combination thereof. The plurality of modules 106 can include various sub-modules (not shown). The plurality of modules 106 may include computer-readable instructions that supplement applications or functions performed by the system 100 for the box packing.
The data repository (or repository) 110 may include a plurality of abstracted pieces of code for refinement and data that is processed, received, or generated as a result of the execution of the plurality of modules in the module(s) 106.
Although the data repository 110 is shown internal to the system 100, it will be noted that, in alternate embodiments, the data repository 110 can also be implemented external to the system 100, where the data repository 110 may be stored within a database (repository 110) communicatively coupled to the system 100. The data contained within such external database may be periodically updated. For example, new data may be added into the database (not shown in FIG. 1) and/or existing data may be modified and/or non-useful data may be deleted from the database. In one example, the data may be stored in an external system, such as a Lightweight Directory Access Protocol (LDAP) directory and a Relational Database Management System (RDBMS). Functions of the components of the system 100 are now explained with reference to the steps in flow diagram in FIG. 2 and the example diagrams in FIG. 3A through FIG. 5C.
FIG. 2 is a flow diagram depicting steps involved in the process of box packing being performed by the system of FIG. 1, according to some embodiments of the present disclosure.
In an embodiment, the system 100 comprises one or more data storage devices or the memory 104 operatively coupled to the processor(s) 102 and is configured to store instructions for execution of steps of the method 200 by the processor(s) or one or more hardware processors 102. The steps of the method 200 of the present disclosure will now be explained with reference to the components or blocks of the system 100 as depicted in FIG. 1 and the steps of flow diagram as depicted in FIG. 2. Although process steps, method steps, techniques or the like may be described in a sequential order, such processes, methods, and techniques may be configured to work in alternate orders. In other words, any sequence or order of steps that may be described does not necessarily indicate a requirement that the steps be performed in that order. The steps of processes described herein may be performed in any order practical. Further, some steps may be performed simultaneously.
At step 202 of a method 200 in FIG. 2, the system 100 receives, via one or more hardware processors 102, an input data comprising a) an outer box, wherein the outer box is a bounding box of a foreground object of interest, b) one or more inner boxes, and c) one or more inter-box separation related configuration parameters, as input data. For example, coordinates of selected points (top left, bottom right etc.) of the outer box and that of the one or more inner boxes may be received as input. Also, the inter-box separation related configuration parameters maybe sep_(abs,inner) and sep_(percentage,inner).
Further, at step 204 of the method 200, the system 100 samples a set of points associated with a plurality of centroids of each of the one or more inner boxes within the outer box, via the one or more hardware processors 102, to satisfy a plurality of constraints, wherein each of the plurality of constraints is associated with a minimum absolute separation between a plurality of centroids of each of the one or more inner boxes. In an embodiment, the sampling has to satisfy all of the plurality of constraints. In another embodiment, the plurality of constraints are characterized by the one or more inter-box separation related parameters received as the input data. The plurality of constraints used may include a) one or more box overlap constraints, b) at least one constraint associated with sampling distribution of centroids of the one or more inner boxes, c) at least one constraint associated with a minimum absolute separation during placement of the one or more inner boxes, d) at least one constraint associated with a minimum relative separation during placement of the one or more inner boxes, e) one or more constraints associated with protruding of the one or more inner boxes, and f) one or more constraints associated with order of placement of the one or more inner boxes. These are further shown below.
For example, during a problem formulation, the constraints to be satisfied by the solution are:
maximize ?_(i=0)^n¦a_i
s.t.
?i,j?[0,n]:i?j and((c_(i,inner,x)±(a_i ?*w?_(i,inner))/2)n(c_(j,inner,x)±(a_j*w_(j,inner))/2)=Ø) (boxes do not overlap) ---- (1)
?i,j?[0,n]:i?j and((c_(i,inner,y)±(a_i*h_(i,inner))/2)n(c_(j,inner,y)±(a_j*h_(j,inner))/2)=Ø) (boxes do not overlap) ---- (2)
{c_(i,inner) }:i?[0,n] and c_(i,inner)~U(0,max?(h_outer,w_outer ) ) (centroids of inner boxes are uniformly sampled) ---- (3)
?i,j?[0,n]:i?j and(abs(c_(i,inner) ?-c?_(j,inner) )>sep_(abs,inner) ) (minimum absolute separation during placement) ---- (4)
?i,j?[0,n]:i?j and(abs(c_(i,inner) ?-c?_(j,inner) )>sep_(percentage,inner)*(h_outer,w_outer )) (minimum relative separation during placement) ---- (5)
?i?[0,n]:(0=(c_(i,inner)±?a_(i*) h?_(i,inner)/2)=h_outer )(placed box must not protrude out) ---- (6)
?i?[0,n]:(0=(c_(i,inner)±(a_i*w_(i,inner))/2)=w_outer )(placed box must not protrude out) ---- (7)
?i,j?[0,n]:i?j and i
Documents
Application Documents
| # |
Name |
Date |
| 1 |
202321034908-STATEMENT OF UNDERTAKING (FORM 3) [18-05-2023(online)].pdf |
2023-05-18 |
| 2 |
202321034908-REQUEST FOR EXAMINATION (FORM-18) [18-05-2023(online)].pdf |
2023-05-18 |
| 3 |
202321034908-PROOF OF RIGHT [18-05-2023(online)].pdf |
2023-05-18 |
| 4 |
202321034908-FORM 18 [18-05-2023(online)].pdf |
2023-05-18 |
| 5 |
202321034908-FORM 1 [18-05-2023(online)].pdf |
2023-05-18 |
| 6 |
202321034908-FIGURE OF ABSTRACT [18-05-2023(online)].pdf |
2023-05-18 |
| 7 |
202321034908-DRAWINGS [18-05-2023(online)].pdf |
2023-05-18 |
| 8 |
202321034908-DECLARATION OF INVENTORSHIP (FORM 5) [18-05-2023(online)].pdf |
2023-05-18 |
| 9 |
202321034908-COMPLETE SPECIFICATION [18-05-2023(online)].pdf |
2023-05-18 |
| 10 |
202321034908-FORM-26 [23-06-2023(online)].pdf |
2023-06-23 |
| 11 |
Abstract.1.jpg |
2023-12-15 |
| 12 |
202321034908-FORM-26 [05-11-2025(online)].pdf |
2025-11-05 |