Thresholding method for segmenting gray scale image, method for determining background concentration distribution, and image displacement detection method

• US 5,555,318 A
• Filed: 11/07/1995
• Issued: 09/10/1996
• Est. Priority Date: 07/13/1990
• Status: Expired due to Fees

• Current Assignee: Nippon Telegraph and Telephone Corporation
• Original Assignee: Nippon Telegraph and Telephone Corporation
• Inventors: Ito, Minoru, Watanabe, Toshifumi
• Primary Examiner(s): COUSO, YON JUNG
• Application Number:
  US08/551,811
• Time in Patent Office: 308 Days
• Field of Search: 382/130, 382/132, 382/168, 382/271, 382/294, 382/171, 382/174, 382/291, 382/511, 364/413.16
• US Class Current: 382/168
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/136 involving thresholding
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns

Abstract

In a thresholding method for segmenting gray scale image which is less dependent on the concentration distribution of the input image, the threshold in determined as a zero-cross point of a histogram difference between the concentration histograms for the gray scale image within the window at a window position at which the window contains more high concentration region and at a window position at which the window contains more low concentration region. Also, in a method of determining a background concentration distribution from an image having an arbitrarily distributed pattern, the background concentration level is determined as a peak concentration or a mean value concentration of a low concentration section of the histogram difference of the concentration histograms for two associated windows. Also, in an image displacement detection method capable of detecting a displacement of a pattern in a two dimensional image accurately by using only a one-dimensional pattern matching without any period mismatching error even for an image of a repetitious pattern, the discplacements in the vertical and lateral direction which are locally minimum and for which a discrepancy in an oblique direction is minimum are selected as the actual displacements.

Claims

1. A method of detecting a displacement of an observed image with respect to a reference image in vertical and lateral directions, comprising the steps of:

(a) obtaining a vertical cumulative projection pattern with respect to the vertical direction for each of the observed image and the reference image, and a lateral cumulative projection pattern with respect to the lateral direction for each of the observed image and the reference image;

(b) obtaining candidate vertical displacements Δ

x of the observed image with respect to the reference image in the vertical direction for which a vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference image is locally minimum, and candidate lateral displacements Δ

y of the observed image with respect to the reference image in the lateral direction for which a lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image is locally minimum;

(c) obtaining an oblique cumulative projection pattern with respect to an oblique direction for each of the observed image and the reference image;

(d) calculating an estimated oblique displacement Δ

z from each of the candidate vertical displacements Δ

x and each of the candidate lateral displacements Δ

y obtained at the step (b);

(e) adjusting the oblique cumulative projection pattern for the observed image by the estimated oblique displacement Δ

z calculated at the step (d) to obtain an adjusted oblique cumulative projection pattern;

(f) obtaining an oblique discrepancy between the oblique cumulative projection pattern for the reference image and the adjusted oblique cumulative projection pattern for the observed image; and

(g) determining the displacement in the vertical and lateral directions as one of the candidate vertical displacements Δ

x and one of the candidate lateral displacements Δ

y for which the oblique discrepancy obtained at the step (f) satisfies a prescribed condition.

2. The method of claim 1, wherein at the step (b) the vertical discrepancy is obtained by successively changing a relative position of the vertical cumulative projection patterns for the observed image and the reference image, calculating the vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference image at each relative position, and selecting the calculated vertical discrepancy which is locally minimum, while the lateral discrepancy is obtained by successively changing a relative position of the lateral cumulative projection patterns for the observed image and the reference image, calculating the lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image at each relative position, and selecting the calculated lateral discrepancy which is locally minimum.

3. The method of claim 1, wherein at the step (b) the candidate vertical displacements Δ

x of the observed image with respect to the reference image in the vertical direction are those for which a vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference image is locally minimum and less than a prescribed critical level, while the candidate lateral displacements Δ

y of the observed image with respect to the reference image in the lateral direction are those for which a lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image is locally minimum and less than a prescribed critical level.

4. The method of claim 2, wherein the oblique direction is inclined by 45°

from the vertical and lateral directions.

5. The method of claim 2, wherein at the step (g) the prescribed condition is that the oblique discrepancy is minimum.

6. The method of claim 2, wherein at the step (g) the prescribed condition is that the oblique discrepancy is less than a prescribed critical level.

7. A method of detecting a displacement of an observed image with respect to a reference image in vertical and lateral directions, comprising the steps of:

(a) obtaining a vertical cumulative projection pattern with respect to the vertical direction for each of the observed image and the reference image, a lateral cumulative projection pattern with respect to the lateral direction for each of the observed image and the reference image, and an oblique cumulative projection pattern with respect to an oblique direction for each of the observed image and the reference image;

(b) obtaining candidate vertical displacements Δ

x of the observed image with respect to the reference image in the vertical direction for which a vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference image is locally minimum, candidate lateral displacements Δ

y of the observed image with respect to the reference image in the lateral direction for which a lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image is locally minimum, candidate oblique displacements Δ

z of the observed image with respect to the reference image in the oblique direction for which a oblique discrepancy between the oblique cumulative projection patterns for the observed image and the reference image is locally minimum;

(c) calculating an estimated oblique displacement Δ

z from each of the candidate vertical displacements Δ

x and each of the candidate lateral displacements Δ

y obtained at the step (b);

(d) obtaining one of the candidate oblique displacements Δ

z obtained at the step (b) which is closest to the estimated oblique displacement Δ

z calculated at the step (c);

(e) calculating a function of a distance between said one of the candidate oblique displacements Δ

z obtained at the step (d) and the estimated oblique displacement Δ

z calculated at the step (c) as an evaluation value for said one of the candidate oblique displacements Δ

z obtained at the step (d); and

(f) determining the displacement in the vertical and lateral directions as one of the candidate vertical displacements Δ

x and one of the candidate lateral displacements Δ

y for which the evaluation value calculated at the step (e) for a corresponding candidate oblique displacement Δ

z satisfies a prescribed condition.

8. The method of claim 7, wherein at the step (b) the vertical discrepancy is obtained by successively changing a relative position of the vertical cumulative projection patterns for the observed image and the reference image, calculating the vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference image at each relative position, and selecting the calculated vertical discrepancy which is locally minimum, while the lateral discrepancy is obtained by successively changing a relative position of the lateral cumulative projection patterns for the observed image and the reference image, calculating the lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image at each relative position, and selecting the calculated lateral discrepancy which is locally minimum, and the oblique discrepancy is obtained by successively changing a relative position of the oblique cumulative projection patterns for the observed image and the reference image, calculating the oblique discrepancy between the oblique cumulative projection patterns for the observed image and the reference image at each relative position, and selecting the calculated oblique discrepancy which is locally minimum.

9. The method of claim 7, wherein at the step (b) the candidate vertical displacements Ax of the observed image with respect to the reference image in the vertical direction are those for which a vertical discrepancy between the vertical cumulative projection patterns for the observed image and the reference-image is locally minimum and less than a prescribed critical level, while the candidate lateral displacements Δ

y of the observed image with respect to the reference image in the lateral direction are those for which a lateral discrepancy between the lateral cumulative projection patterns for the observed image and the reference image is locally minimum and less than a prescribed critical level, and the candidate oblique displacements Δ

z of the observed image with respect to the reference image in the oblique direction are those for which a oblique discrepancy between the oblique cumulative projection patterns for the observed image and the reference image is locally minimum and less than a prescribed critical level.

10. The method of claim 7, wherein the oblique direction is inclined by 45°

from the vertical and lateral directions.

11. The method of claim 7, wherein at the step (e) the function of the distance is an inverse of the distance, and at the step (f) the prescribed condition is that the evaluation value is maximum.

12. The method of claim 7, wherein at the step (f) the prescribed condition is that the evaluation value is less than a prescribed critical level.