US5533148A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Method for restructuring physical design images into hierarchical data models
Assignee: International Business Machines Corp
•
Filing: 1993-09-30
•
Granted: 1996-07-02
•
Expires: 2013-09-30
Abstract
Abstract A method for restructuring information stored in physical design image form, such as an image of a layer in a semiconductor package, into a hierarchical area specification model useful in automated design applications. The restructuring results in recognizing identical patterns in the image and storing common information about the patterns in a single location to decrease storage space required and improve access efficiency by design application programs needing the information. Parameters controlling the method can be adjusted to produce a hierarchical model that is particularly suited to the needs of a particular application program.
Inventors
- 👤 John Y. Sayah
- 👤 Robert A. Rozwod
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 07:16
CPC Classifications
G; G06; G06T; G06T17/00; G06T17/005; G06F; G06F30/00; G06F30/30; G06F30/39; G06F30/398
Claims Analysis
Total Claims: 19
Claim 1
Independent Claim
120 words
A method for restructuring a physical design image into a data model comprising the steps of: providing a physical design image; identifying leaf areas in the physical design image; classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas; grouping adjacent leaf areas of equivalent type into one or more area arrays; recognizing equivalent adjacent and non-adjacent area arrays and forming a set of one or more unique area arrays; partitioning each unique area array into one or more partition areas; recognizing equivalent partition areas and forming a set of one or more unique partition areas; and generating area specifications for each unique partition area and for each unique leaf area.
Claim 2
Independent Claim
120 words
A method for restructuring a physical design image into a data model comprising the steps of: providing a physical design image; identifying leaf areas in the physical design image; classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas; grouping adjacent leaf areas of equivalent type into one or more area arrays; recognizing equivalent adjacent and non-adjacent area arrays and forming a set of one or more unique area arrays; partitioning each unique area array into one or more partition areas; recognizing equivalent partition areas and forming a set of one or more unique partition areas; and generating area specifications for each unique partition area and for each unique leaf area.
Claim 3
Dependent Claim
87 words
A method for restructuring an image into a data model according to claim 1 wherein the step of grouping adjacent leaf areas of equivalent type into one or more area arrays comprises the steps of: scanning the image in a first direction; grouping leaf areas of equivalent type that are adjacent in the first direction to form one dimensional area arrays; scanning the image in a second direction; and grouping equivalent one dimensional area arrays that are adjacent in the second direction to form the area arrays.
Claim 4
Dependent Claim
39 words
A method for restructuring an image into a data model according to claim 1 wherein the step of partitioning each unique area array comprises partitioning each unique area array into a hierarchical array of one or more partition areas.
Claim 5
Dependent Claim
30 words
A method for restructuring an image into a data model according to claim 3 further comprising the step of organizing the unique area specifications into a hierarchical area specification model.
Claim 6
Dependent Claim
42 words
A method for restructuring an image into a data model according to claim 1 wherein the step of partitioning comprises recursively partitioning each unique area array according to desired partitioning criteria to form a hierarchical array of one or more partition areas.
Claim 7
Dependent Claim
30 words
A method for restructuring an image into a data model according to claim 5 wherein the partitioning criteria are selected to produce a model for use by a particular application.
Claim 8
Dependent Claim
30 words
A method for restructuring an image into a data model according to claim 5 wherein regular partition areas are created that can be specified in a step and repeat fashion.
Claim 9
Dependent Claim
29 words
A method for restructuring an image into a data model according to claim 5 wherein partition areas that are as close to a square form as possible are created.
Claim 10
Dependent Claim
40 words
A method for restructuring an image into a data model according to claim 5 wherein the number of different types of partition areas are reduced by identifying identical patterns of leaf areas to reduce the number of different area specifications.
Claim 11
Dependent Claim
42 words
A method for restructuring an image into a data model according to claim 1 wherein the step of identifying leaf areas includes the step of flattening the hierarchy and creating leaf areas if the image has been previously organized into a hierarchy.
Claim 12
Dependent Claim
45 words
A method for restructuring an image into a data model according to claim 1 wherein the step of classifying the leaf areas as being of one or more types ignores different characteristics between areas provided that such areas have common characteristics relevant to an application.
Claim 13
Dependent Claim
35 words
A method for restructuring an image into a data model according to claim 1 further comprising the steps of storing the data model and generating an area tree from the stored data model whenever desired.
Claim 14
Independent Claim
292 words
A method for restructuring an image into a data model comprising the steps of: providing an image; identifying leaf areas in the image; classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas; grouping adjacent leaf areas of equivalent type into one or more area arrays; recognizing equivalent area arrays and forming a set of one or more unique area arrays; recursively partitioning each unique area array by desired partitioning criteria to form a hierarchical array of one or more partition areas according to a sequence of steps including: (a) exiting the sequence of steps if an area of N x by N y leaf areas has a number of leaf areas within it that is within a predetermined Desired Number of Leaf Areas Range; (b) creating a set of area slices of size New N x , by New N y leaf areas by slicing the area of N x by N y leaf areas; (c) recognizing equivalent slices from the set of area slices and removing redundant slices to form a set of unique area slices; (d) identifying slices from the set of unique area slices that have previously been assigned an area specification and removing such slices from the set of unique area slices; and (e) for every remaining distinct slice in the set of unique area slices performing the steps of: (i) creating a new area specification, and (ii) repeating the sequence of steps substituting New N x and New N y for N x and N y ; recognizing equivalent partition areas and forming a set of one or more unique partition areas; and generating area specifications for each unique partition area and for each unique leaf area.
Claim 15
Independent Claim
292 words
A method for restructuring an image into a data model comprising the steps of: providing an image; identifying leaf areas in the image; classifying the leaf areas as being of one or more types according to a characteristic of the leaf areas; grouping adjacent leaf areas of equivalent type into one or more area arrays; recognizing equivalent area arrays and forming a set of one or more unique area arrays; recursively partitioning each unique area array by desired partitioning criteria to form a hierarchical array of one or more partition areas according to a sequence of steps including: (a) exiting the sequence of steps if an area of N x by N y leaf areas has a number of leaf areas within it that is within a predetermined Desired Number of Leaf Areas Range; (b) creating a set of area slices of size New N x , by New N y leaf areas by slicing the area of N x by N y leaf areas; (c) recognizing equivalent slices from the set of area slices and removing redundant slices to form a set of unique area slices; (d) identifying slices from the set of unique area slices that have previously been assigned an area specification and removing such slices from the set of unique area slices; and (e) for every remaining distinct slice in the set of unique area slices performing the steps of: (i) creating a new area specification, and (ii) repeating the sequence of steps substituting New N x and New N y for N x and N y ; recognizing equivalent partition areas and forming a set of one or more unique partition areas; and generating area specifications for each unique partition area and for each unique leaf area.
Claim 16
Dependent Claim
76 words
A method for restructuring an image into a data model according to claim 13 wherein the step of creating a set of area slices by slicing the area of N x by N y , comprises dividing the area array of size N x by N y into slices of size New N x by New N y , the direction of the slices and the number of slices being selected according to predetermined partitioning criteria.
Claim 17
Dependent Claim
71 words
A method for restructuring an image into a data model according to claim 14 wherein the direction of the slices is determined by a partitioning criterion equal to Desired Minimum Number of Children in One Direction at Leaf Level, the slicing being performed in a direction such that N x or N y will not be sliced if below the Desired Minimum Number of Children in One Direction at Leaf Level.
Claim 18
Dependent Claim
55 words
A method for restructuring an image into a data model according to claim 15 wherein the number of slices is determined by a partitioning criterion equal to Desired Number of Children at Higher Levels Max and the number of slices is equal to 2 to maximum of the Desired Number of Children at Higher Level.
Claim 19
Dependent Claim
34 words
A method for restructuring an image into a data model according to claim 13 further comprising the step of post-processing grouping to reduce the number of area specifications at higher levels of the model.
References Cited (Backward Citations)
US4484292A
Cited
US4612618A
Cited
US4688072A
Cited
US4785391A
Cited
US4910690A
Cited
US4831543A
Cited
US4829446A
Cited
US4890238A
Cited
US4944023A
Cited
US4918614A
Cited
JPH02178775A
Cited
US5280547A
Cited
US5341309A
Cited
US5381343A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 1999-07-02 | 2000-01-01 | 2000-07-02 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2003-07-02 | 2004-01-01 | 2004-07-02 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2007-07-02 | 2008-01-01 | 2008-07-02 | $7700.00 | Window Closed / Lapsed |