# US 10,311,199 B2 · Pattern matching using edge-driven dissected rectangles > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,311,199 B2 - Document ID: US10311199B2 - Status: Granted - Kind: B2 - Application number: 15/201,291 - Filed: 2016-07-01 - Published: 2018-01-04 - Granted: 2019-06-04 - Earliest claimed: 2016-07-01 - Assignees: Mentor Graphics Corporation - Applicants: Mentor Graphics Corporation - Inventors: Jea Woo Park; Robert A. Todd - Web page: https://patentgrep.com/patent/US10311199B2 ## CPC - G06F 30/398: Design verification or optimisation, e.g. using design rule check [DRC], layout versus schematics [LVS] or finite element methods [FEM] (optical proximity correction [OPC] design processes G03F1/36) - G06T 7/0006: {using a design-rule based approach} - G06T 7/12: Edge-based segmentation - G06T 7/60: Analysis of geometric attributes - G06T 2207/30148: Semiconductor; IC; Wafer - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL ## Abstract Aspects of the disclosed technology relate to techniques of pattern matching. Matching rectangles in a layout design that match rectangle members of a search pattern are identified based on edge operations. The rectangle members comprise an origin rectangle member and one or more reference rectangle members. Grid element identification values are attached to the matching rectangles. The matching rectangles that match the one or more reference rectangle members in neighborhoods of the matching rectangles that match the origin rectangle member are then analyzed. The neighborhoods are determined based on the grid element identification values. Based on the analysis, matching patterns in the layout design that match the search pattern are determined. ## Claims ### Claim 1 One or more non-transitory computer-readable media storing computer-executable instructions for causing one or more processors to perform a method, the method comprising: identifying matching rectangles in a layout design that match rectangle members of a search pattern based on edge operations and a first set of criteria, the layout design comprising data describing a mask or reticle for a plurality of microdevices to be formed on a single wafer, and the rectangle members comprising an origin rectangle member and one or more reference rectangle members; wherein the edge operations comprise identifying edges in the layout design that match respective edges of the rectangle members according to a first matching criterion in the first set of criteria; attaching grid element identification values to the matching rectangles, the grid element identification values being associated with a regular grid that divides the layout design into a number of equal rectangle regions (grid elements); determining first and second matching patterns in the layout design that match the search pattern based on a second set of criteria, the determining comprising analyzing those matching rectangles that match the one or more reference rectangle members in neighborhoods of respective first and second matching rectangles that match the origin rectangle member, wherein the neighborhoods are determined based on the grid element identification values; wherein the analyzing comprises comparing each of the one or more reference rectangle members with one or more of the those matching rectangles according to a second matching criterion of the second set of criteria, and wherein the first or second matching pattern is determined upon finding a matching one of the those matching rectangles for each of the one or more reference rectangle members; and storing the matching patterns, wherein the identifying, the attaching, the determining and the storing are part of a process of processing the layout design, a circuit design associated with the layout design, or both. ### Claim 2 (depends on 1) The one or more non-transitory computer-readable media recited in claim 1, wherein the edge operations are edge-based operations of a design rule checking (DRC) tool. ### Claim 3 (depends on 1) The one or more non-transitory computer-readable media recited in claim 1, wherein the second set of criteria comprise criteria for exact matching, fuzzy matching, partial matching, or any combinations thereof. ### Claim 4 (depends on 1) The one or more non-transitory computer-readable media recited in claim 1, wherein the regular grid is an adaptive grid. ### Claim 5 (depends on 4) The one or more non-transitory computer-readable media recited in claim 4, wherein size of the grid elements is adjusted to be comparable to size of a bounding box of the search pattern. ### Claim 6 (depends on 1) The one or more non-transitory computer-readable media recited in claim 1, wherein the determining comprises: identifying a first matching rectangle that not only matches one of the reference rectangle members but also has a distance from a second matching rectangle that matches the origin rectangle member the same as that of the search pattern; constructing a bounding box based on the first matching rectangle and the second matching rectangle; and determining whether the bounding box encloses the matching rectangles that match the rest of the reference rectangle members. ### Claim 7 (depends on 1) The one or more non-transitory computer-readable media recited in claim 1, wherein the edge operations further comprise comparison of width or spacing between pairs of identified edges in the layout design and the width or spacing between respective pairs of the matched edges of the rectangle members. ### Claim 8 A method, executed by at least one processor of a computer, comprising: identifying matching rectangles in a layout design that match rectangle members of a search pattern based on edge operations and a first set of criteria, the layout design comprising data describing a mask or reticle for a plurality of microdevices to be formed on a single wafer, and the rectangle members comprising an origin rectangle member and one or more reference rectangle members; wherein the edge operations comprise identifying edges in the layout design that match respective edges of the rectangle members according to a first matching criterion in the first set of criteria; attaching grid element identification values to the matching rectangles, the grid element identification values being associated with a regular grid that divides the layout design into a number of equal rectangle regions (grid elements); determining first and second matching patterns in the layout design that match the search pattern based on a second set of criteria, the determining comprising analyzing those matching rectangles that match the one or more reference rectangle members in neighborhoods of respective first and second matching rectangles that match the origin rectangle member, wherein the neighborhoods are determined based on the grid element identification values; wherein the analyzing comprises comparing each of the one or more reference rectangle members with one or more of the those matching rectangles according to a second matching criterion of the second set of criteria, and wherein the first or second matching pattern is determined upon finding a matching one of the those matching rectangles for each of the one or more reference rectangle members; and storing the matching patterns, wherein the identifying, the attaching, the determining and the storing are part of a process of processing the layout design, a circuit design associated with the layout design, or both. ### Claim 9 (depends on 8) The method recited in claim 8, wherein the edge operations are edge-based operations of a design rule checking (DRC) tool. ### Claim 10 (depends on 8) The method recited in claim 8, wherein the first set of criteria comprise criteria for exact matching, fuzzy matching, or both. ### Claim 11 (depends on 8) The method recited in claim 8, wherein the regular grid is an adaptive grid. ### Claim 12 (depends on 11) The method recited in claim 11, wherein size of the grid elements is adjusted to be comparable to size of a bounding box of the search pattern. ### Claim 13 (depends on 8) The method recited in claim 8, wherein the determining comprises: identifying a first matching rectangle that not only matches one of the reference rectangle members but also has a distance from a second matching rectangle that matches the origin rectangle member the same as that of the search pattern; constructing a bounding box based on the first matching rectangle and the second matching rectangle; and determining whether the bounding box encloses the matching rectangles that match the rest of the reference rectangle members. ### Claim 14 (depends on 8) The method recited in claim 8, wherein the edge operations further comprise comparison of width or spacing between pairs of identified edges in the layout design and the width or spacing between respective pairs of the matched edges of the rectangle members. ### Claim 15 A system comprising: one or more processors with memory coupled thereto, the one or more processors programmed to perform a method, the method comprising: identifying matching rectangles in a layout design that match rectangle members of a search pattern based on edge operations and a first set of criteria, the layout design comprising data describing a mask or reticle for a plurality of microdevices to be formed on a single wafer, and the rectangle members comprising an origin rectangle member and one or more reference rectangle members; wherein the edge operations comprise identifying edges in the layout design that match respective edges of the rectangle members according to a first matching criterion in the first set of criteria; attaching grid element identification values to the matching rectangles, the grid element identification values being associated with a regular grid that divides the layout design into a number of equal rectangle regions (grid elements); determining first and second matching patterns in the layout design that match the search pattern based on a second set of criteria, the determining comprising analyzing those matching rectangles that match the one or more reference rectangle members in neighborhoods of respective first and second matching rectangles that match the origin rectangle member, wherein the neighborhoods are determined based on the grid element identification values; wherein the analyzing comprises comparing each of the one or more reference rectangle members with one or more of the those matching rectangles according to a second matching criterion of the second set of criteria, and wherein the first or second matching pattern is determined upon finding a matching one of the those matching rectangles for each of the one or more reference rectangle members; and storing the matching patterns, wherein the identifying, the attaching, the determining and the storing are part of a process of processing the layout design, a circuit design associated with the layout design, or both. ### Claim 16 (depends on 15) The system recited in claim 15, wherein the first set of criteria comprise criteria for exact matching, fuzzy matching, or both. ### Claim 17 (depends on 15) The system recited in claim 15, wherein the second set of criteria comprise criteria for exact matching, fuzzy matching, partial matching, or any combinations thereof. ### Claim 18 (depends on 15) The system recited in claim 15, wherein the regular grid is an adaptive grid. ### Claim 19 (depends on 15) The system recited in claim 15, wherein the determining comprises: identifying a first matching rectangle that not only matches one of the reference rectangle members but also has a distance from a second matching rectangle that matches the origin rectangle member the same as that of the search pattern; constructing a bounding box based on the first matching rectangle and the second matching rectangle; and determining whether the bounding box encloses the matching rectangles that match the rest of the reference rectangle members. ### Claim 20 (depends on 15) The system recited in claim 15, wherein the edge operations further comprise comparison of width or spacing between pairs of identified edges in the layout design and the width or spacing between respective pairs of the matched edges of the rectangle members.