Method for detecting slope of image data utilizing hough-transform

• US 6,408,105 B1
• Filed: 05/12/1999
• Issued: 06/18/2002
• Est. Priority Date: 05/12/1998
• Status: Expired due to Fees

• Current Assignee: Advantest Corporation
• Original Assignee: Advantest Corporation
• Inventors: Maruo, Kazuyuki
• Primary Examiner(s): Mehta, Bhavesh
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/310,789
• Time in Patent Office: 1,133 Days
• Field of Search: 382/281, 382/168, 382/172, 382/266, 382/141, 382/171, 382/190, 382/191, 382/193, 382/194, 382/199, 382/201-204, 382/268, 382/269, 382/286, 701/28, 348/135
• US Class Current: 382/281
• CPC Class Codes: G06T 2207/10056 Microscopic image
• CPC Class Codes: G06T 2207/20061 Hough transform
• CPC Class Codes: G06T 2207/30141 Printed circuit board [PCB]
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/001 using an image reference approach
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/168 involving transform domain methods
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80

Abstract

Image data is edge-processed and then digitized. This image data is Hough-transformed to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space, from which coordinates with multiple intersected Hough-curves are extracted and grouped. For each group, representative coordinates are selected to estimate slopes of linear components in the image data. In this way, the linear components can be recognized from the image data to estimate the slope, thereby making it possible to modify slopes of linear components in image data of a semiconductor wafer taken at an arbitrary angle or the like.

Claims

1. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

Hough-transforming the inputted image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space;

extracting a plurality of coordinates from the parameter plane;

detecting relative distances between the extracted coordinates;

grouping the extracted coordinates in the parameter plane in accordance with the detected relative distances therebetween;

selecting representative coordinates for each group; and

estimating slopes of linear components in the image data from the selected coordinates.

2. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

edge-processing the inputted image data to enhance values of the pixels in edge portions in the image data;

comparing each of the values of the pixels in the edge-processed image data with a predetermined threshold to convert the edge-processed image data into binary data;

Hough-transforming the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

detecting relative distances between the extracted coordinates;

grouping the extracted coordinates in the parameter plane in accordance with the detected relative distances therebetween;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

4. The method according to claim 2, wherein said generating a parameter plane from the binary image data comprises performing the Hough-transform for each pixel represented with position coordinates (x, y) in the image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

, and

wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.

3. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

edge-processing the inputted image data to enhance values of the pixels in edge portions in the image data;

comparing each of the values of the pixels in the edge-processed image data with a predetermined threshold to convert the edge-processed image data into binary data;

performing Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

5. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average of values of all the pixels in the inputted image data;

calculating a difference between the calculated average and a value of each pixel in the image data;

comparing the calculated difference of the value with a predetermined threshold for each pixel to convert the image data into binary data;

Hough-transforming the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

grouping the extracted coordinates in the parameter plane in accordance with the proximity thereof;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

7. The method according to claim 5, wherein said generating a parameter plane from the binary image data comprises performing the Hough-transform for each pixel represented with position coordinates (x, y) in the image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

, and

wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.

12. The method according to claim 5, further comprising:

calculating a difference between the calculated average M of values of the pixels and a value of each pixel;

calculating a standard deviation Σ

from the average M of values of pixels and the difference between the average and a value of each pixel; and

calculating a threshold t to convert the image data into binary data represented as “

t=M+3Σ

”

from the average M and the standard deviation Σ

.

6. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average of values of all the pixels in the inputted image data;

calculating a difference between the calculated average and a value of each pixel in the image data;

comparing the calculated difference of the value with a predetermined threshold for each pixel to convert the image data into binary data;

performing Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

13. The method according to claim 6, further comprising:

calculating a difference between the calculated average M of values of the pixels and a value of each pixel;

calculating a standard deviation Σ

from the average M of values of pixels and the difference between the average and a value of each pixel; and

calculating a threshold t to convert the image data into binary data represented as “

t=M+3Σ

”

from the average M and the standard deviation Σ

.

8. A method of processing data comprising:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average M of values t of all the pixels in the inputted image data;

calculating a difference |t−

M| between the calculated average and a value of each pixel in the image data as a weighting coefficient; and

performing Hough-transform for each pixel represented with position coordinates (x, y) in the image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sinθ

with for each mutually intersected the Hough-curves the weighting coefficient corresponding thereto added to the number of the curves thereof.

9. The method according to claim 8, further comprising:

comparing the addition result with a threshold and extracting from the parameter plane coordinates with the addition result being greater than said threshold;

grouping the extracted coordinates in the parameter plane in accordance with the proximity thereof;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

10. The method according to claim 8, further comprising:

comparing the addition result with a threshold and extracting from the parameter plane coordinates with the addition result being greater than said threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

11. The method according to claim 9, wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.

14. The method according to claim 8, further comprising:

calculating a difference between the calculated average Mp of values for all the coordinates in the parameter plane and each value for the coordinates;

calculating a standard deviation Σ

using the average Mp of values and the difference between the average and each value for the coordinates; and

calculating a threshold Th to convert the image data into binary data represented as “

Th=Mp+3Σ

”

from the average Mp and the standard deviation Σ

.

15. An information storage medium comprising a program stored therein for causing a computer to perform:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

edge-processing the inputted image data to enhance values of the pixels in edge portions in the image data;

comparing each of the values of the pixels in the edge-processed image data with a predetermined threshold to convert the edge-processed image data into binary data;

Hough-transforming the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

detecting relative distances between the extracted coordinates;

grouping the extracted coordinates in the parameter plane in accordance with the detected relative distances therebetween;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

17. The information storage medium according to claim 15, wherein said generating a parameter plane from the binary image data comprises performing the Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

, and

wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.

16. An information storage medium comprising a program stored therein for causing a computer to perform:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

edge-processing the inputted image data to enhance values of the pixels in edge portions in the image data;

comparing each of the values of the pixels in the edge-processed image data with a predetermined threshold to convert the edge-processed image data into binary data;

performing Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

18. An information storage medium comprising a program stored therein for causing a computer to perform:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average of values of all the pixels in the inputted image data;

calculating a difference between the calculated average and a value of each pixel in the image data;

comparing the calculated difference of the value with a predetermined threshold for each pixel to convert the image data into binary data;

Hough-transforming the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

grouping the extracted coordinates in the parameter plane in accordance with the proximity thereof;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

20. The information storage medium according to claim 18, wherein said generating a parameter plane from the binary image data comprises performing the Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

, and

wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.

19. An information storage medium comprising a program stored therein for causing a computer to perform:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average of values of all the pixels in the inputted image data;

calculating a difference between the calculated average and a value of each pixel in the image data;

comparing the calculated difference of the value with a predetermined threshold for each pixel to convert the image data into binary data;

performing Hough-transform for each pixel represented with position coordinates (x, y) in the binary image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

;

comparing the number of mutually-intersected Hough-curves with a predetermined threshold and extracting from the generated parameter plane coordinates of the intersection of mutually-intersected Hough-curves, the number of which is greater than said threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

21. An information storage medium comprising a program stored therein for causing a computer to perform:

inputting image data comprising multiple pixels each having a multilevel value set in digital form;

calculating the average M of values t of all the pixels in the inputted image data;

calculating a difference |t−

M| between the calculated average and a value of each pixel in the image data as a weighting coefficient; and

performing Hough-transform for each pixel represented with position coordinates (x, y) in the image data to generate a parameter plane in which multiple Hough-curves are plotted in a parameter space with coordinates (θ

, ρ

) thereof in which θ

represents an angle with respect to an x axis and |ρ

| represents a distance from an origin point to a linear component ρ

=x cos θ

+y sin θ

with for each mutually intersected the Hough-curves the weighting coefficient corresponding thereto added to the number of the curves thereof.

22. The information storage medium according to claim 21, further comprising a program stored therein for causing said computer to perform:

extracting coordinates with a high value of the addition result from the parameter plane generated through a comparison with a predetermined threshold;

grouping the extracted coordinates in the parameter plane in accordance with the proximity thereof;

selecting representative coordinates for each group thus generated; and

estimating slopes of linear components in the image data from the selected coordinates.

23. The information storage medium according to claim 21, further comprising a program stored therein for causing said computer to perform:

extracting coordinates with a high value of the addition result from the parameter plane generated through a comparison with a predetermined threshold;

adding up the number of the extracted coordinates in the parameter plane for each angle θ

to generate a histogram; and

specifying an angle θ

with the maximum number of the extracted coordinates from the generated histogram.

24. The information storage medium according to claim 22, wherein said estimating slopes of linear components in the image data from the selected coordinates comprises specifying an angle θ

with a large number of the selected coordinates are concentrated.