Positioning device

• US 6,272,246 B1
• Filed: 01/06/1998
• Issued: 08/07/2001
• Est. Priority Date: 02/05/1997
• Status: Expired due to Fees

• Current Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Original Assignee: Sharp Kabushiki Kaisha (Hon Hai Precision Industry Co., Ltd.)
• Inventors: Takai, Kensuke
• Primary Examiner(s): Bella, Matthew C.
• Assistant Examiner(s): DESIRE, GREGORY M
• Application Number:
  US09/003,592
• Time in Patent Office: 1,309 Days
• Field of Search: 382/209, 382/217-219, 382/274, 382/227, 382/224, 358/520-523, 358/455-458
• US Class Current: 382/209
• CPC Class Codes: G06T 5/40 using histogram techniques
• CPC Class Codes: G06T 5/50 using two or more images, e.g. averaging or subtraction
• CPC Class Codes: G06T 5/92 based on global image properties
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors
• CPC Class Codes: G06V 30/2504 Coarse or fine approaches, e.g. resolution of ambiguities or multiscale approaches

Abstract

In a positioning device, a maximum-value/minimum-value calculating section calculates the maximum value and minimum value of densities with respect to each of a target image and a reference image that has been preliminarily stored. Further, based upon the maximum values and minimum values of densities of the two images, a barrel-shifter gradation conversion section carries out bit shifts of the original images of the two images respectively so as to allow them to contain effective bits related to contrast, and gradation-converts the respective images so as to have numbers of density levels that are fewer than the original numbers of density levels thereof, thereby outputting the resulting images that have been gradation-converted. With this arrangement, even if the contrast of an original image is poor, it is possible to reduce the amount of calculations for finding the degree of similarity between the reference image and the target image without impairing the operation accuracy in finding the degree of similarity. Therefore, even if the contrast of an original image is poor, it is possible to carry out an effective rough search by using a rough search section. Moreover, since the degree of similarity is found with high precision with a minimum of the amount of calculations, the circuit scale can be minimized to the corresponding extent.

Claims

1. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point, wherein the first calculating section is a first maximum-value calculating section for calculating a maximum value of densities of the target image, and the first gradation conversion section generates the rough target image by linearly converting the density levels of the target image in a rate corresponding to the maximum value.

2. The positioning device as defined in claim 1, wherein the first gradation conversion section includes a bit shifter which generates the rough target image by carrying out bit shifts on the densities of the target image so that when the density level varies within a range not more than the maximum value, more bits in a binary number indicating the density levels are allowed to vary.

3. The positioning device as defined in claim 2, wherein the bit shifter carries out bit shifts so that when the density levels are expressed by a binary number, the bit, which is located one-bit lower than the lowest order bit among bits always having the same value within density levels that are not more than the maximum value, forms the highest order bit of the rough target image.

4. The positioning device as defined in claim 2, further comprising:

a first image-reducing section, placed between the first gradation conversion section and the rough search section, for reducing the resolution of the rough target image.

5. The positioning device as defined in claim 2, further comprising:

a first image-reducing section, placed before the first gradation conversion section, for reducing the resolution of the target image.

6. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point, wherein the first calculating section is a first minimum-value calculating section for calculating a minimum value of densities of the target image, and the first gradation conversion section generates the rough target image by linearly converting the density levels of the target image in a rate corresponding to the minimum value.

7. The positioning device as defined in claim 6, wherein the first gradation conversion section includes a bit shifter which generates the rough target image by carrying out bit shifts on the densities of the target image so that when the density level varies within a range not less than the minimum value, more bits in a binary number indicating the density levels are allowed to vary.

8. The positioning device as defined in claim 7, wherein the bit shifter carries out bit shifts so that when the density levels are expressed by a binary number, the bit, which is located one-bit lower than the lowest order bit among bits always having the same value within density levels that are not less than the minimum value, forms the highest order bit of the rough target image.

9. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point, wherein the first calculating section is a first maximum-value/minimum value calculating section for calculating a maximum value and a minimum value of densities of the target image, and the first gradation conversion section generates the rough target image by linearly converting the density levels of the target image in a rate corresponding to the maximum value and the minimum value.

10. The positioning device as set forth in claim 9, wherein the first gradation conversion section includes a bit shifter which generates the rough target image by carrying out bit shifts on the densities of the target image so that when the density level varies within a range from the minimum value to the maximum value, more bits in a binary number indicating the density levels are allowed to vary.

11. The positioning device as defined in claim 10, wherein the bit shifter carries out bit shifts so that when the density levels are expressed by a binary number, the higher order bit between the bit which is located one-bit lower than the lowest order bit among bits always having the same value within density levels that are not less than the minimum value and the bit which is located one-bit lower than the lowest order bit among bits always having the same value within density levels that are not more than the maximum value, forms the highest order bit of the rough target image.

12. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point, wherein the first calculating section detects bits whose value changes at least once all through the entire target image among a plurality of bits indicating the density levels, and the first gradation conversion section produces the rough target image by carrying out bit shifts on the densities of the target image so that the highest order bit among the bits whose value changes have been detected forms the highest order bit of the rough target image.

13. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point, wherein the first calculating section is a first histogram-calculating section for calculating density histograms of the target image, and based upon the density histograms, the first gradation conversion section generates the rough target image by carrying out a histogram-conversion so that effective density histograms related to contrast of the target image are contained.

14. The positioning device as defined in claim 13, wherein the first gradation conversion section carries out the histogram conversion so as to equalize the density histograms of the target image.

15. The positioning device as defined in claim 13, wherein the first gradation conversion section carries out the histogram conversion by means of parametric conversion.

16. A positioning device, which carries out a positioning between a preliminarily registered reference image and a newly inputted target image, comprising:

a first calculating section for calculating features of the target image;

a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is contained to a greater extent, and so that the number of density levels of the target image is reduced;

a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and

a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point further comprising;

a second calculating section for calculating features of the reference image, the features being the same as those calculated by the first calculating section; and

a second gradation conversion section which converts the gradation of the reference image so as to produce the rough reference image based upon the results of calculations in the second calculating section so that information related to contrast of the reference image is contained to a greater extent, and so that the number of density levels of the reference image is reduced.

17. The positioning device as defined in claim 16, further comprising:

a second image-reducing section, placed between the second gradation conversion section and the rough search section, for reducing the resolution of the rough reference image.

18. The positioning device as defined in claim 16, further comprising:

a second image-reducing section, placed before the second gradation conversion section, for reducing the resolution of the reference image.