JPH0863604A - Image processor and its method - Google Patents

Abstract

PURPOSE: To quickly judge the similarity (e.g. rotational similarity) of shapes between plural image areas. CONSTITUTION: A centroid computing circuit 104 detects the centroid of an image area, a polar coordinate converting circuit 106 converts contour of the detected image area into polar coordinate data around the centroid and a similarity judging circuit 107 judges the similarity of shapes between plural image areas based upon the polar coordinate data. When plural areas are in mutually similar (expanded or reduced) relation, the contour functions of both the areas expressed by respective polar coordinate data are similar. When both the areas are in rotated relation, their contour functions are mutually similar and their phases are mutually shifted. Thereby the similarity of shapes between plural image areas can easily be judged by comparing their contour functions.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to an image processing apparatus and an image processing method, and more particularly to an image processing apparatus and an image processing method for determining the similarity of the shapes of regions of an image.

[0002]

2. Description of the Related Art In a conventional image processing apparatus and image processing method, a method for determining whether the shape of a reference area and the shape of an area to be compared coincide with each other There is a template matching method using an image) and an image of an area to be compared (input image). The procedure of a general template matching method is shown below.

The reference image and the input image are compared pixel by pixel. If a match is obtained by the processing of step 1, it is determined that the reference image and the input image have the same shape.

If no match is obtained, the reference image is shifted by one pixel in the horizontal or vertical direction and the processing is executed again.

If no match is obtained even if the above processing is executed over the entire image area of the input image, it is determined that the shape of the reference image and the shape of the input image do not match.

FIG. 8 shows an example of the template matching method. FIG. 9 is a diagram showing a case where the shape of the input image has a rotational relationship with the shape of the reference image and a case where the shape has an enlargement or reduction relationship, that is, a case where there is similarity. In the template matching method, in the case of FIG. 9, even if the input image has the same shape as the reference image, it is determined that they do not match.

As a method for solving the above-mentioned problem when the shape of the input image has a rotational relationship with the shape of the reference image, Japanese Patent Laid-Open No. 5-312058
In No. -12446, template matching is executed at various rotation angles by adding a means for rotating a reference image to the template matching method,
An image processing apparatus has been proposed that determines whether the shape of a reference image and the shape of an input image that are in a rotational relationship match.

In the reference image rotating means, the coordinates (0, 0), ..., (X _m , Y _m ), ..., (X _M , Y _M ) of the contour pixels of the reference image are used as the origin in this order. The coordinates are calculated and generated when is gradually rotated. Then, each time the coordinates of the contour pixels detected input image (0,0), ..., (X n, Y n), ..., (X N, Y N) the sum F of pixel values in the matching coordinates Is required.
When the outline F of the input image is larger than the threshold and the maximum of the total F of the image values that can be regarded as matching the outline of the reference image. It has been said that the coordinates of represent the rotational relationship of the input image with respect to the reference image, that is, the rotational relationship between the image shape of the reference area and the image shape of the area to be compared.

Even if the shape of the reference image and the shape of the input image have a similarity (enlargement / reduction) relationship, the contour ratio of the contour of the reference image is changed from the coordinates of the contour pixels of the reference image to obtain the contour of the contour similar to the contour of the reference image. By calculating the pixel coordinates and obtaining the sum F of pixel values as in the case where the shape of the reference image and the shape of the input image have a rotational relationship as described above, the shape of the input image with respect to the shape of the reference image can be obtained. It is also possible to determine the similarity relationship of.

[0010]

However, as described above, when the template matching method is added with means such as rotation, enlargement, reduction, etc., and a match or similarity is determined by trial and error, the number of trials is enormous. become. For example, if the number of trials required is h times in the horizontal direction, v times in the vertical direction, r times for rotation, and s times for enlargement / reduction, the total number of trials t is expressed by equation (1).

T = h * v * r * s (1) Since the respective elements are multiplied, the total number of trials t becomes enormous and the processing time becomes long.

As the means for rotating the reference image,
Affine transformation can be considered, but if affine transformation is applied to all pixels, there is a problem that the processing time also becomes long.

The present invention has been made to solve the above problems, and an image processing apparatus capable of determining the similarity (rotation / similarity) of image shapes in a short processing time. The purpose is to obtain an image processing method.

[0014]

An image processing apparatus according to claim 1 of the present invention comprises a detection means for detecting the center of gravity of an image area,
Conversion means for converting the contour of the image area into polar coordinate data centered on the detected center of gravity, and determination means for determining shape similarity between the areas of the plurality of images based on the converted polar coordinate data. Is provided.

According to a second aspect of the present invention, in the image processing apparatus according to the first aspect, the determination means of the image processing apparatus includes: (a) a function representing the contour of the image area composed of polar coordinate data between the plurality of image areas. Means for obtaining a normalized correlation coefficient of (b)
One or both of (a) and (b) of means for obtaining the cosine of the angle formed by the functions representing the contours of the regions of the image composed of polar coordinate data between the regions of the plurality of images are provided.

An image processing apparatus according to a third aspect of the present invention is the image processing apparatus according to the first or second aspect, further comprising means for giving a difference to a central angle of a function representing a contour composed of polar coordinate data.

An image processing apparatus according to a fourth aspect of the present invention is the image processing apparatus according to any one of the first to third aspects, further comprising storage means for storing the central angle of polar coordinate data as an address and the polar coordinate radius as data. It is a thing.

An image processing method according to a fifth aspect of the present invention represents a step of expressing the contours of a plurality of regions of an image by a function consisting of polar coordinate data centered on the center of gravity of the regions, and a contour consisting of a plurality of polar coordinate data. When determining the degree of coincidence of the functions, there is provided a step of performing comparison while shifting the central angle of the function representing the contour composed of polar coordinate data.

[0019]

According to the image processing apparatus of the present invention, the center of gravity of the area of the image is detected, the contour of the area of the image is converted into polar coordinate data having the center of gravity as the center, and a plurality of data are converted based on the polar coordinate data. Since the shape similarity is determined between the regions of the image of, when the above regions have a similarity (enlargement / reduction) relationship,
The contour function represented by the polar coordinate data becomes similar.

Furthermore, when the above areas are in a rotational relationship, the contour functions are similar to each other and out of phase with each other. This phase difference represents the direction difference of the image area.

FIG. 1 illustrates the situation. Figure 1 (d)
Is the area of the reference image (FIG. 1A) and the area of the image having a similarity (reduction) relationship with the area of the reference image (FIG. 1B) and the area of the reference image. A region that is similar to the region (similarity ratio 1: 1) and has a rotational relationship (see FIG. 1).
(C)) is a comparison of the respective contour functions represented by the polar coordinate data.

In FIG. 1, the horizontal axis is the central angle θ [°], and the vertical axis is the distance r from the center of the image area to the contour.

The contour function 1 is a contour function of a reference image area. The contour function 2 is a contour function of an image area having a similarity (reduction) relationship with the reference image area. The contour function 3 is a contour function of an image region that is similar (similarity ratio 1: 1) and has a rotational relationship to the reference image region.

The contour function 2 is obtained by reducing the contour function 1 in the vertical axis direction with respect to the contour function 1.

Since the contour function 3 has a similarity ratio of 1: 1 to the contour function 1, the contour functions have the same magnitude but are out of phase. If the similarity ratio is not 1: 1, the contour function 1 is enlarged or reduced in the vertical axis direction as in the case of the contour function 2.

Therefore, by comparing the contour functions as described above, it is possible to easily determine the similarity of the shapes of the regions of the image.

In the image processing apparatus of claim 2,
(A) Obtaining a normalized correlation coefficient of a function representing the contour of an area of an image composed of polar coordinate data between areas of a plurality of images, (b) an area of an image composed of polar coordinate data between areas of a plurality of images Either (a), (b), or both are performed to find the cosine of the angle formed by the functions representing the contours of the contour. Therefore, in (a), if the normalized correlation coefficient is a value close to 1, It can be determined that there is similarity between the plurality of image regions. In (b), if the cosine has a value close to 1, it can be determined that there is similarity between the plurality of image regions.

In the image processing device of the third aspect, since the difference in the central angle of the function representing the contour, which is composed of the polar coordinate data, can be given, the size of the central angle of the function representing the contour can be arbitrarily changed. .

In the image processing apparatus according to the fourth aspect, since the central angle of the function representing the contour formed by the polar coordinate data is used as the address and the polar coordinate radius is stored as the data, it is possible to give the difference to the central angle by shifting the address. Therefore, it is possible to easily obtain a function representing the contour, which is composed of polar coordinate data with a difference in the central angle (phase-shifted).

In the image processing method of the fifth aspect, the contours of the regions of the plurality of images are represented by a function composed of polar coordinate data centered on the center of gravity of the regions, and the degree of coincidence of the functions representing the contour composed of the plurality of polar coordinate data. When determining, the comparison is performed while shifting the central angle of the function representing the contour formed by the polar coordinate data, so it is possible to determine whether or not there is a rotational relationship between the regions of the plurality of images.

[0031]

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS An embodiment of an image processing apparatus according to the present invention will be described below with reference to the drawings.

FIG. 2 is a block diagram showing the configuration of an embodiment of the image processing apparatus of the present invention. In FIG. 2, the image processing apparatus includes an image pickup apparatus 101, a binarization circuit 102 that binarizes image information, a frame memory 103 that stores binarization information, and a centroid calculation circuit 104 that calculates the centroid.
, A contour detection circuit 105 for detecting contour pixels, and a polar coordinate conversion circuit 106 for converting coordinate data into polar coordinate data.
And a shape similarity determination circuit 107 that determines the similarity between the shapes of the input image and the reference image.

The shape similarity determination circuit 107 stores the memory 108 for storing the polar coordinate data of the contour of the input image, the memory 109 for storing the polar coordinate data of the contour of the reference image, and the shape similarity between the input image and the reference image. The shape similarity determination circuit 110, a control circuit 111, an address generation circuit 112 that generates an address of the memory 108, and an address shift circuit 113 that shifts the address are included. The shape similarity determination circuit 110 further includes a normalized correlation coefficient calculation circuit 201 and a threshold circuit 202.

The image pickup device 101 picks up an image of an area to be compared. The binarization circuit 102 is connected to the image pickup apparatus 101, and converts an image (input image) of a comparison target imaged by the image pickup apparatus 101 into binarized image information. The frame memory 103 includes a binarization circuit 10
2, the input image is stored in a two-dimensional coordinate system, and the image information binarized by the binarization circuit 102 is stored as image information of a two-dimensional address corresponding to the two-dimensional coordinate.

Centroid calculation circuit 104 and contour detection circuit 1
Reference numeral 05 is connected to the frame memory 103, and the center-of-gravity calculation circuit 104 reads out the image information stored in the frame memory 103, calculates the center-of-gravity coordinates of the input image, and outputs the center-of-gravity coordinate information. The contour detection circuit 105 detects the coordinates of the contour pixel of the input image that is the target of polar coordinate conversion.
The polar coordinate conversion circuit 106 is connected to the centroid calculation circuit 104 and the contour detection circuit 105, and based on the centroid coordinates input from the centroid calculation circuit 104 and the coordinates of the contour pixel obtained from the contour detection circuit 105, the input image. Is converted into polar coordinate data centered on the center of gravity of the region. The shape similarity determination circuit 107 is connected to the polar coordinate conversion circuit 106 and determines the similarity between the shape of the input image and the shape of the reference image based on the polar coordinate data of the contour of the input pixel obtained from the polar coordinate conversion circuit 106.

In the shape similarity determination circuit 107, the memory 108 is connected to the polar coordinate conversion circuit 106 and stores the polar coordinate data obtained from the polar coordinate conversion circuit 106 as the central angle of the polar coordinate and the distance as data. The memory 109 stores the contour of the reference image as polar coordinate data centered on the center of gravity of the image, and stores the central angle of the polar coordinate as an address and the distance as data, like the memory 108.

The shape similarity determination circuit 110 is used in the memory 10
8 and the memory 109, the polar coordinate data of the contour of the input image read from the memory 108, and the memory 109
It is compared with the polar coordinate data of the contour of the reference image read from to determine the similarity between the contour functions.

By the way, the normalized correlation coefficient is 1 between similar functions. Therefore, it is a convenient operation for determining the similarity relationship of functions.

FIG. 3 shows a first example of the shape similarity determination circuit 110.
3 is a block diagram showing a configuration example of FIG. 3, the shape similarity determination circuit 110 includes a normalized correlation coefficient calculation circuit 201 that calculates a normalized correlation coefficient and a threshold circuit 202 that has a threshold value of the normalized correlation coefficient.

The normalized correlation coefficient calculation circuit 201 has a terminal m.
2 is a memory 108, and terminal n is a memory 109 of FIG.
, And the polar coordinate data of the contour of the input image read from the memory 108 and the polar coordinate data of the contour of the reference image read from the memory 109 are respectively expressed as a contour function, and the normalized correlation coefficient is calculated.

An arithmetic expression for obtaining a normalized correlation coefficient of these functions in a discrete system is represented by the expression (2).

The threshold circuit 202 is connected to the normalized correlation coefficient calculation circuit 201, and the normalized correlation coefficient calculation circuit 20.
As a result of calculating the normalized correlation coefficient with 1, the value of the normalized correlation coefficient (value close to 1) that can determine that there is similarity between the contour functions is used as a threshold value to determine whether there is a similarity relationship. It is determined and output to the terminal k.

Similar to the above-mentioned normalized correlation coefficient, the cosine of the angle formed by the functions is 1 between similar functions, which is a convenient operation for determining the similarity relationship of functions.

FIG. 4 shows a second example of the shape similarity determination circuit 110.
3 is a block diagram showing a configuration example of FIG. In FIG. 4, the shape similarity determination circuit 110 includes a cosine arithmetic circuit 301 that is an arithmetic circuit that calculates the cosine of the angle formed by the functions, and a threshold circuit 102 that has a threshold value of the angle formed.

The cosine calculation circuit 301 is connected to the memory 108 of FIG. 2 at a terminal m and the memory 109 of FIG. 2 at a terminal n, and polar coordinate data of the contour of the input image read from the memory 108 and the memory 109. The read polar coordinate data of the contour of the reference image are expressed as contour functions, and the cosine of the angle formed by these contour functions is calculated.

An arithmetic expression for obtaining the cosine of the angle formed by two functions in a discrete system is expressed by Expression (3).

[0047]

[Equation 1]

In the equation (2), r ₁ (θ _i ) is the distance from the center of gravity of the reference image area to the contour. r ₂ (θ
_i ) is the distance from the center of gravity of the area of the input image to the contour. r ₁ ′ Is the average of the distance r ₁ (θ _i ) from the center of gravity of the region of the reference image to the contour. r ₂ ′ Is the average of the distance r ₂ (θ _i ) from the center of gravity of the region of the input image to the contour. θ is a central angle (rotation angle).

In equation (3), r ₁ (θ _i ) is the distance from the center of gravity of the reference image area to the contour. r ₂ (θ
_i ) is the distance from the center of gravity of the area of the input image to the contour. θ is the central angle (rotation angle), and x is the contour function r ₁
Is the angle formed by and r ₂ .

The threshold circuit 302 is a cosine calculation circuit 30.
1 and the cosine calculation circuit 301 calculates the cosine, and the cosine value (value close to 1) that can be determined to have similarity is used as a threshold value to determine whether or not there is a similarity relationship. , To terminal k.

The control circuit 111 is connected to the shape similarity determination circuit 110 at a terminal k, and when the determination by the shape similarity determination circuit 110 is completed, the address shift amount is output to the address shift circuit 113, and the contour function between contour functions is output. Continue similarity determination. Then, when the similarity between the contour functions is not obtained over all the addresses (all the phases), the shape of the input image is not similar to the shape of the reference image (they have no rotation or similarity relationship). judge.

The address generation circuit 112 includes the control circuit 11
Memory 10 of the input image connected to memory 1
In order to store the polar coordinate data of each contour of the reference image in 9, the central angle of each polar coordinate data (0 ° <0 °
An address corresponding to θ <360 °) is generated. The address shift circuit 113 is also connected to the control circuit 111 and the address generation circuit 112, and adds the address shift amount given from the control circuit 111 to the address read from the address generation circuit 113. Since the address represents the central angle of the polar coordinate data of the contour, that is, the phase of the contour function, the operation of shifting the address of the polar coordinate data of the contour of the reference image shifts the phase of the contour function (the phase difference is the phase difference). Means to give).

In this example, the polar coordinate data address of the contour of the reference image is shifted, but the polar coordinate data address of the contour of the input image may be shifted.

FIG. 5 is a diagram for explaining the address shift circuit 113. In FIG. 5, the address shift circuit 113 includes an adder circuit 401. θ is an address (that is, a phase). Δθ ′ is an address shift amount (phase shift amount).

The adder circuit 401 is connected to the address generation circuit 112 of FIG.
2 is connected to the control circuit 111 of FIG. 2 at the terminal b, and the address shift amount Δθ ′ is obtained from the control circuit 111.
Then, the address is added to θ and the address shift amount Δθ ′, and a new address (θ + Δθ ′) is output from the terminal c to the memory 109. Here, when the output of the adder circuit 401 exceeds the value of the address corresponding to 360 ° (all phases), it is returned to the address corresponding to 0 °. This is realized by a general binary adder circuit by setting the discretization of the central angle so that the address corresponding to 360 ° (all phases) is a power of 2.

FIG. 6 is a flow chart showing the operation of the image processing apparatus of FIG. 2 of the present invention. In step S1 (hereinafter abbreviated as step), an area to be compared is imaged. This is performed by the imaging device 101. In S3,
The image (input image) of the area to be compared, which is captured in S1, is converted into data. This is the binarization circuit 10.
It is done in 2. In S5, the image data of S3 is stored. This is done in the frame memory 103. S7
Then, the center of gravity of the input image is calculated from the image data stored in S5, and the contour pixel is detected. This is performed by the center calculation circuit 104 and the contour detection circuit 105, respectively. In S9, the contour of the image is converted into polar coordinate data centered on the center of gravity of the center and the contour pixel detected in S7. This is performed by the polar coordinate conversion circuit 106. In step S11, the shape similarity between the input image and the reference image is determined based on the polar coordinate data of the contour of the input image obtained in step S9. This is performed by the shape similarity determination circuit 107.

FIG. 7 is a flow chart showing the detailed operation of S11. In FIG. 7, first, in S21, the address shift amount is set to 0 °. This is the control circuit 1
11, the address shift circuit 113 performs the operation. S
At 23, in order to store the polar coordinate data of the outlines of the reference image and the input image, an address corresponding to each central angle of the polar coordinate data is generated. This is the address generation circuit 1
Twelve. In S25, the normalized correlation coefficient or the cosine is obtained from the contour functions of the reference image and the input image, and the similarity between the contour functions is determined. This is performed by the shape similarity determination circuit 110. If it is determined in S27 that the functions have similarities in S27, it is determined that the shapes of the reference image and the input image are similar, and the processing ends. However, if it is determined that there is no similarity between the contour functions, it is checked whether the address shift amount Δθ is 360 °. If the address shift amount Δθ = 360 ° in S29, it is determined that the contour functions of the reference image and the input image have no similarity even when rotated, that is, there is no similarity. However, if the address shift amount Δθ ≠ 360 °, the address shift amount Δθ
Is further added to the shift amount Δθ ′ to generate a new address shift amount Δθ. The control circuit 111 performs steps S27 to S31. When a new address shift amount Δθ is generated in S31, the process returns to S23 again, and the same operations as in S27 to S31 are repeated until a similarity or dissimilarity determination is made.

[0058]

As described above, in the image processing apparatus according to the first aspect of the present invention, the center of gravity of the image area is detected, and the contour of the area of the image is converted into polar coordinate data centered on the center of gravity. Then, based on the polar coordinate data, the shape similarity is determined between the regions of the plurality of images. Therefore, when the regions of the images have a similarity (enlargement or reduction) relationship, The contour function will be similar.

Further, when the areas of the image have a rotational relationship, the contour functions are similar to each other and out of phase with each other.

Therefore, by comparing the contour functions, it is possible to easily determine the similarity of the shapes of the regions of the image.

In the image processing apparatus according to the second aspect of the present invention, (a) obtains a normalized correlation coefficient of a function representing the contour of the image area made up of polar coordinate data among a plurality of image areas. ) Since the similarity is determined by either (a) or (b) such as obtaining the cosine of a function that represents the contour of the image area composed of polar coordinate data between the areas of a plurality of images, (a) Then, if the normalized correlation coefficient has a value close to 1, it can be determined that the regions of the plurality of images have similarity. In (b), if the cosine has a value close to 1, it can be determined that the regions of the plurality of images have similarity.

In the image processing apparatus according to the third aspect, since the central angle of the function representing the contour formed of polar coordinate data can be provided with a difference, the size of the central angle of the function representing the contour can be arbitrarily changed. .

In the image processing apparatus according to the fourth aspect, since the central angle of the function representing the contour formed by the polar coordinate data is used as the address and the polar coordinate radius is stored as the data, it is possible to give the difference to the central angle by shifting the address. Therefore, it is possible to easily obtain a function representing the contour, which is composed of polar coordinate data with a difference in the central angle (phase-shifted).

In the image processing method of the fifth aspect, the contours of the regions of the plurality of images are represented by a function composed of polar coordinate data centered on the center of gravity of the regions, and the degree of coincidence of the functions representing the contour composed of the plurality of polar coordinate data is represented. When determining, the comparison is performed while shifting the central angle of the function representing the contour formed by the polar coordinate data, so it is possible to determine whether or not there is a rotational relationship between the regions of the plurality of images.

As a result, it is possible to obtain an image processing apparatus and an image processing method for determining the similarity of shapes (rotation / similarity) between regions of an image in a short processing time.

[Brief description of drawings]

FIG. 1 is a diagram exemplifying a contour function for explaining an operation of the present invention.

FIG. 2 is a block diagram showing the configuration of an embodiment of the image processing apparatus of the present invention.

FIG. 3 is a block diagram showing a first configuration example of a shape similarity determination circuit 110 according to the exemplary embodiment of the present invention.

FIG. 4 is a block diagram showing a second configuration example of the shape similarity determination circuit 110 according to the exemplary embodiment of the present invention.

FIG. 5 is a block diagram showing a configuration of an address shift circuit 113 according to an embodiment of the present invention.

6 is a flowchart showing the operation of the image processing apparatus of the embodiment of FIG. 2 of the present invention.

7 is a flowchart showing a detailed operation of S11 of the flowchart of FIG. 7 of the embodiment of FIG. 2 of the present invention.

FIG. 8 is a diagram showing an example of a template matching method.

FIG. 9 is a diagram illustrating a case where the shape of an input image has similarity to the shape of a reference image.

[Explanation of symbols]

 Reference Signs List 101 image pickup device 102 binarization circuit 103 frame memory 104 centroid calculation circuit 105 contour detection circuit 106 polar coordinate conversion circuit 107 shape similarity determination circuit 108 memory 109 memory 110 shape similarity determination circuit 111 control circuit 112 address generation circuit 113 address shift circuit 201 Normalized correlation coefficient arithmetic circuit 202 Threshold circuit 301 Cosine arithmetic circuit 302 Threshold circuit 401 Adder circuit θ address Δθ address shift amount Δθ ′ address shift amount shift amount

Claims (5)

[Claims] 1. An image processing apparatus for determining a shape based on an image, comprising: detecting means for detecting a center of gravity of an area of the image; and a contour of the area of the image centered on the detected center of gravity. An image processing apparatus including: a conversion unit that converts the polar coordinate data into a polar coordinate data item; and a determination unit that determines a shape similarity between regions of a plurality of images based on the polar coordinate data. 2. The determining means comprises: (a) means for obtaining a normalized correlation coefficient of a function representing the contour of the area of the image composed of the polar coordinate data between the areas of the plurality of images; 2. The method according to claim 1, further comprising: (a), (b), or both of means for obtaining a cosine of an angle formed by the functions representing the contours of the image region formed of the polar coordinate data between the image regions. Image processing device. 3. The image processing apparatus according to claim 1, further comprising means for giving a difference to a central angle of a function representing the contour, which is formed by the polar coordinate data. 4. The image processing apparatus according to claim 1, further comprising storage means for storing a polar coordinate radius as data, with a central angle of a function representing the contour formed of the polar coordinate data as an address. 5. An image processing method for processing shape similarity determination between a plurality of image regions, wherein a contour of the plurality of image regions is a function composed of polar coordinate data centered on a center of gravity of the image regions. An image processing method comprising: a step of expressing and a step of making a comparison while shifting a central angle of the function representing the contour formed of the polar coordinate data when determining the coincidence degree of the function representing the contour formed of the plurality of polar coordinate data.