JP7833962B2 - Similarity region detection device and similarity region detection program - Google Patents

Description

This invention relates to a similarity region detection device and a similarity region detection program for detecting similar regions in images.

Methods based on feature quantities, such as color features and local features, are widely known for detecting similar regions in images. One example of a method based on color features is the method described in Non-Patent Document 1. This method detects regions with a high similarity between the input image and the color histogram. While it is not suitable for detecting minute differences in object shape, it is robust to changes in object shape.
Another example of a method based on local features is the method described in Non-Patent Document 2. This method creates a Visual Word (dictionary) from local features and detects regions with high similarity in the histogram of the frequency of occurrence of the Visual Words. It enables robust detection against changes in shape such as object rotation and scale, as well as changes in brightness.

M. J. Swain, D. H. Ballard, “Color indexing”, International Journal of Computer Vision, Vol.7, No.1, 1991, pp.11-32 G. Csurka, C. Dance, L. Fan, J. Willamowski, C. Bray, “Visual categorization with bags of keypoints”, ECCV Workshop on Statistical Learning in Computer Vision, 2004

For example, when detecting the position within an input image that has the greatest similarity to a target image template, conventional search techniques involve sequentially shifting the search area (search window) and comparing whether the features of the search area (search window) are similar to the features of the target image (template).
When detecting similar images based on this search method, if the target image in the input image is the same size and orientation as the target image (template), the position in the input image that maximizes the similarity to the target image (template) can be detected by sequentially shifting the position of the search window.
However, if the size and orientation of the target image in the input image are unknown compared to the target image (template) (for example, twice the size and tilted at an angle), it was necessary to search for images similar to the target image (template) by considering various sizes of the search area (search window) (for example, 1/2 the size, 1:1 the size, 3/2 the size, 2 times the size of the target image (template)) and various directions (for example, directions that tilt the target image (template) to 0 degrees, 30 degrees, 60 degrees, etc.). Therefore, the search in conventional technology had the problem of requiring a huge amount of matching processing by changing parameters related to the shape of the search area (search window), such as its size and orientation, in addition to parameters related to the position of the search area (search window).

This invention has been made in view of the problems of the prior art, and aims to provide a similarity region detection device and program that can detect similar regions within an input image that are similar to a target image by detecting regions with similar histograms of image features with a constant amount of computation, regardless of the position or shape of the search region.

The similarity region detection device according to the present invention comprises: an input unit that receives a target image and an input image; a feature extraction unit that extracts features from the target image and from each of the divided regions obtained by dividing the input image into predetermined sizes; a mathematical modeling unit that generates a mathematical model based on the features extracted from the target image and the features extracted from each of the divided regions of the input image, using which of the divided regions to select as a variable; a model variable calculation unit that obtains a solution for the variable that minimizes the mathematical model so that the value of the mathematical model generated by the mathematical modeling unit satisfies a predetermined threshold condition; and a region detection unit that determines the similarity region identified by the solution of the variable obtained by the model variable calculation unit, and outputs the similarity region determined by the region detection unit.

The mathematical modeling unit may pre-set the target size for detecting similar regions determined by the region detection unit.

The mathematical model may comprise a histogram similarity model, a region size model, and a region clumping model. The histogram similarity model is minimized to ensure that the histogram of features in the divided regions approaches the histogram of features extracted from the target image. The region size model is minimized to ensure that the number of divided regions selected from the divided regions satisfies a predetermined condition. The region clumping model is minimized to increase the degree to which adjacent divided regions are selected from among the divided regions.

The model variable calculation unit may obtain a solution for the variables that minimizes the overall function, calculated by adding the histogram similarity model, the region size model, and the region clumping model after weighting them with different balance coefficients, so that it satisfies a predetermined threshold condition.

The model variable calculation unit may use the solution obtained by minimizing the overall function to satisfy a predetermined threshold to calculate the values of the histogram similarity model, the region size model, and the region clumping model, and adjust the balance coefficient so that the values of each model are below a predetermined threshold.

The region detection unit may determine the similar region by performing post-processing using the partitioned region identified by the solution of the variables obtained by the model variable calculation unit.

The post-processing may consist of one of the following: a process that sets the largest of the four connected components generated from the divided region as a similar region; a process that sets the largest of the eight connected components generated from the divided region as a similar region; a closing process that performs several dilation operations on the binary image followed by the same number of condensation operations as the dilation operations; or an opening process that performs several condensation operations on the binary image followed by the same number of dilation operations as the condensation operations.

The similarity region detection program according to the present invention is intended to enable a computer to function as the similarity region detection device.

According to the present invention, a similarity region detection device and program are provided that can detect similar regions within an input image that are similar to a target image by detecting regions with similar histograms of image features with a constant computational load, regardless of the position or shape of the search region.

This figure shows the configuration of the similarity region detection system in the embodiment. This is a functional block diagram showing an example of the configuration of the mathematical modeling unit included in the similarity region detection device in the embodiment. This figure schematically represents the divided region and adjacent region used in the mathematical modeling unit of the similarity region detection device in the embodiment. This figure shows an example of processing by the domain blockage model formulation unit, which constitutes the mathematical modeling unit in the embodiment. This figure shows an example of processing by the domain blockage model formulation unit, which constitutes the mathematical modeling unit in the embodiment. This figure shows an example of processing by the domain blockage model formulation unit, which constitutes the mathematical modeling unit in the embodiment. This figure shows an example of processing by the domain blockage model formulation unit, which constitutes the mathematical modeling unit in the embodiment. This diagram shows a flowchart illustrating the operation of the similarity region detection device in the embodiment.

An example of an embodiment of the present invention will be described below.
Figure 1 shows the configuration of the similarity region detection system 100 in this embodiment.
The similarity region detection system 100 comprises a similarity region detection device 1 and a computer 2.

The similarity region detection device 1 receives the target image and the input image from the input device 50. It detects similar regions from the input image that are similar to the target region within the target image containing the image to be detected, and outputs the detected similar regions to the output device 60. Therefore, the similarity region detection device 1 formulates a mathematical model of a combinatorial optimization problem that takes the minimum value when selecting a subset of partitioned regions similar to the target region, using the selection of which partitioned region to choose from a pre-divided set of partitioned regions of the input image as a variable.

Here, we will briefly explain the mathematical model of the combinatorial optimization problem. In this embodiment, the mathematical model H is constructed using the QUBO (Quadratic Unconstrained Binary Optimization) representation shown in (Equation 1) below.

H=Σ _i Σ _j (Q(i, j)q _i q _j ) = ^{q T} Qq
(Formula 1)
Here, q _i and q _j are the i-th and j-th elements of the vector q, and are binary variables that take the value of 0 or 1.
Furthermore, Σ _i and Σ _j are operators that take the sum of all elements of vector q.
The symbol ^T above and to the right of a vector represents the transpose of the vector.
Q(i,j) is the element in the i-th row and j-th column of the parameter matrix Q, and is the coefficient of the binary product q _i q _j .
In addition to the QUBO representation, the mathematical model H may also use an equivalent Ising model representation.
The similarity region detection device 1 uses the selection of one of the predetermined candidate division regions as a variable to formulate the mathematical model H of the combinatorial optimization problem into a QUBO representation, for example, as shown in Equation 1.

Computer 2 calculates the solution to the mathematical model generated by the similarity region detection device 1. Specifically, Computer 2 calculates the set of q shown in equation (1). Computer 2 can be any computer that calculates the solution to the mathematical model generated by the similarity region detection device 1. For example, Computer 2 could be a QUBO or an Ising machine that solves the Ising model. Furthermore, Computer 2 does not need to be a separate component; it may be integrated into the similarity region detection device 1.

Figure 1 shows the functional configuration of the similarity region detection device 1 that constitutes the similarity region detection system 100 in this embodiment.
The similarity region detection device 1 is an information processing device equipped with a control unit 10 and a storage unit 20, and may be implemented as a general-purpose device such as a server or personal computer, or as dedicated hardware. The control unit 10 functions as an input unit 11, a feature extraction unit 12, a mathematical modeling unit 13, a model variable calculation unit 14, a region detection unit 15, and an output unit 16, which will be described later, by reading and executing a similarity region detection program etc. stored in the storage unit 20.
The similarity region detection device 1, through these functional units, can detect regions where the histograms of image features are similar with a constant amount of computation, regardless of the position or shape of the search region.
Next, we will explain the functions of the similarity region detection device 1.

The input unit 11 receives the target image and the input image from the input device 50, which is connected to the similarity region detection device 1 in a communicative manner. Here, the target image is an image that includes the target region, which is the image to be detected as similar. The input image is an image that is to be detected as having regions similar to the image of the target region. The input unit 11 outputs the received target image (image of the target region) and the input image to the feature extraction unit 12.
The target image and input image may each be of any shape, but in this embodiment, for the sake of simplicity, the target image is set as an object of any shape as the target area, and the input image is a general rectangular image as an example; however, the target image and input image are not limited to these. Both the target image and input image may be of any shape.

The feature extraction unit 12 extracts features from the target image (image of the target region) received by the input unit 11, and from the divided regions obtained by dividing the input image (input image region) into pre-set sizes. In this embodiment, color features extracted from pixel values, etc., are given as examples of features, but the type of features is not particularly limited. For example, local features extracted from the brightness gradient (i.e., shape features), or local features calculated using HOG (Histogram of Oriented Gradient) or SIFT (Scale-Invariant Feature Transform) may be used.
The feature extraction unit 12 extracts image features from the target image, specifically from the target region containing the object (image) to be detected as similar. Furthermore, the feature extraction unit 12 extracts features from each divided region of the input image, which is divided into pre-set sizes.
The feature extraction unit 12 outputs the extracted feature quantities of the target region and the feature quantities of each segmented region of the input image to the mathematical modeling unit 13.

The mathematical modeling unit 13 comprises a histogram similarity model formulation unit 131, a region size model formulation unit 132, and a region chunkiness model formulation unit 133.

The histogram similarity model formulation unit 131 generates an evaluation function that brings the histogram of the features of the selected segmented region in the input image as close as possible to the histogram of the features of the target region in the target image. Specifically, by minimizing the value of the evaluation function generated by the histogram similarity model formulation unit 131, the system ensures that the histogram of the features of the segmented region approaches the histogram of the features of the target region during the segmented region selection process.

The region size model formulation unit 132 generates an evaluation function for determining the number of segmented regions to select from the input image. Specifically, it works to maximize the number of selected segmented regions as much as possible, or to match the number of segmented regions targeted for detection. In doing so, it maximizes the sum of the size of the selected segmented regions from the input image, or matches the number of segmented regions targeted for detection.

The region chunking model formulation unit 133 generates an evaluation function for determining chunking, which represents the degree to which adjacent divided regions are selected from the input image. Specifically, it is formulated so that a reward term is generated when either all adjacent regions are selected or none are selected, and a penalty term is generated when only one of the adjacent regions is selected. In other words, by minimizing the value taken by the evaluation function generated by the region chunking model formulation unit 133, the system acts to select more adjacent regions when selecting divided regions.
In explaining the mathematical modeling unit 13, we will now explain the definitions of symbols and other terms that are commonly used.

The target region within the target image that contains the object (image) to be detected for similarity is denoted as V ^* .
In this embodiment, as described above, the input image is exemplified as a rectangular image with width W pixels and height H pixels. Specifically, the input image is divided into pre-set sizes, and V is the set of vertices of the divided regions, with each divided region being v(x,y) (x=1,2,...,X, y=1,2,...,Y).
Then, v ^# (x,y) represents a binary function that takes the value 1 when the partition region v(x,y) is selected and the value 0 when it is not selected.
In other words, by dividing the input image, a divided region is generated.
Set V={v(x,y);(x=1,2,...,X,y=1,2,...,Y)}
This is created.
X and Y represent the number of horizontal and vertical divisions in the divided area, respectively. For example, if W=3000, H=2000, X=30, and Y=20, the size of the divided area will be 100 pixels × 100 pixels, and the number of divided areas will be 30 × 20 = 600.
For example, if W=3000, H=2000, X=3000, and Y=2000, the division regions will correspond to pixels, the size of the division region will be 1 pixel × 1 pixel, and the number of division regions will be 3000 × 2000 = 6,000,000.
The size of the divided region (for example, the number of vertical pixels and the number of horizontal pixels) can be set independently of the size of the target region V*.
The size of the division region affects the detection accuracy, such as making the detection of similar regions coarser or finer. For example, if the size of the division region is larger than the size of the target region V*, the detection of similar regions will become coarser; therefore, it is preferable to keep the size of the division region less than or equal to the size of the target region V*.
When high-precision detection is required, it is preferable to divide the region into smaller segments. However, the more finely the region is divided, the more variables are required, and the longer the computation time becomes. Therefore, the specific number of pixels should be determined based on the image and purpose.

For each partitioned region v(x,y), a binary function v ^# (x,y) is defined that takes the value 1 if it is selected as a similar region and the value 0 if it is not selected. As a result, as will be described later, the detection of similar regions can be reduced to calculating the solution for the binary variable v ^# (x,y) that minimizes the overall function _HALL , which is obtained by adding the histogram similarity model _H1 , the region size model _H2 , and the region clumping model _H3 , each expressed as a quadratic equation for the binary variable v ^# (x,y), using the balance coefficients _λ1 , _λ2 , and _λ3 .

H _ALL = λ ₁ H ₁ + λ ₂ H ₂ + λ ₃ H ₃
(Formula 2)

Next, the histogram similarity model formulation unit 131 will be described. The histogram similarity model formulation unit 131 generates an evaluation function that brings the histogram F(x,y) of the feature quantities of a selected segmented region v(x,y) in the input image as close as possible to the histogram h ^* of the feature quantities of the target region V ^* in the target image. Here, color features extracted from pixel values, etc., are used as examples of feature quantities.
Specifically, for example, when using 64 color features with 4 levels for each of RGB, the feature of each pixel is represented by a 64-dimensional one-hot vector f(w, h) where the element corresponding to the color number of each pixel (w, h) is 1 and the others are 0. As mentioned above, any feature may be applied as the feature, such as local features extracted from the luminance gradient (i.e., shape features). Regardless of the type of feature, it can be represented as a vector with dimensions equal to the number of features.

The histogram h ^* of the features in the target region V ^* can be defined as the relative frequency normalized by the sum of the occurrence frequencies using the following equation 3 ([Equation 1]).
The mathematical formulas in the specification are represented and cited using the formula n (where n is a natural number). However, the visualized formulas require the addition of numbers in black brackets. Therefore, the numbers indicating the formulas and the numbers within the black brackets are different.
(Formula 3)
Here, |V ^* | is an operator that represents the number of pixels (w, h) included in the target region V ^* , and Σ is an operator that takes the sum of f(w, h) for each pixel (w, h) included in V ^* .

The histogram F(x,y) of the features of each segmented region v(x,y) in the input image can also be defined as a relative frequency normalized by the sum of the occurrence frequencies, using the following equation 4.
(Formula 4)
Here, |v(x,y)| is an operator that represents the number of pixels (w,h) included in the divided region v(x,y), and Σ is an operator that takes the sum of f(w,h) for pixels (w,h) included in the divided region v(x,y).

Next, we have an XY-dimensional vector F whose elements are the histograms F(x,y) of the features of each partitioned region v(x,y).

F={F(1,1) F(1,2)...F(X,Y-1) F(X,Y)}
(Formula 5)
As defined,
A vector v ^# in XY dimensions, whose elements are the binary function values v ^# (x, y) of each partitioned region, can be defined as v ^# = {v ^# (1, 1) v ^# (1, 1) ... v ^# (X, Y - 1) v ^# (X, Y)}
(Formula 6)
This is how it is defined.
In that case, if the _target number of selected segmented regions v(x,y) in the input image is set in advance (hereinafter also referred to as "when the target number of segmented regions is set"), the histogram h of the features in the selected segmented region v(x,y) in the input image can be defined by the following equation 7 as the relative frequency obtained by normalizing the sum of the histograms F(x,y) of the features in the selected segmented region v(x,y) by the target number (|V _target |).
h=(1/|V _target |)Fv ^#
(Formula 7)
Here, "when a target number of divided regions is set" means, for example, the following case. For example, if the carrots included in the target image are to be detected as similar, if the number of pixels containing carrots in the input image can be known in advance, the target size of similar regions similar to the target image can be set in advance. In such a case, the target number |V _target | can be calculated from the target size.

When a target number of division regions is set, the histogram similarity model _H11 can be defined by the following equation 8.
(Formula 8)
Here, || || ₂ ² represents the L2 norm || || ₂ squared, and the symbol T above the vector represents the transpose of the vector.
Substituting the histogram h (Equation 7) of the features of the selected division region v(x,y) in the case where "a target number of division regions is set" into Equation 8, the histogram similarity model _H11 is expressed in the following Equation 9.
(Formula 9)

On the other hand, if "no target number of partitioned regions is set," the histogram h of the features of the selected partitioned region v(x,y) can be defined as the relative frequency obtained by normalizing the sum of the histograms F(x,y) of the features of the selected partitioned region v(x,y) by the total number of selected partitioned regions v(x,y) using the following equation 10.
(Formula 10)
Here, Σ is an operator that takes the sum of all the division regions v(x,y) of the input image. In other words, the value of Σ is the total number of division regions v(x,y) that are selected.

If "the target number of division regions is not set," the histogram similarity model _H12 can be defined by the following equation 11.
(Formula 11)
Substituting the histogram h (Equation 10) of the features of the selected partition region v(x,y) in the case where "the target number of partition regions is not set" into Equation 11,
The histogram similarity model _H12 is represented by Equation 12.
(Formula 12)
Here, _1XY is an XY-dimensional vector where all elements are 1, and 1 _(XY)×(XY) is an (XY)×(XY)-dimensional matrix where all elements are 1. Also, in equation 12, the symbol "X inside a circle" represents the tensor product.
In other words, the tensor product of 1 _XY and (h ^{* T} F) is a matrix of XY dimensions where all rows are (h ^{* T} F), and (h ^{* T} F) 1 _{(XY) × (XY)} is a matrix of (XY) × (XY) dimensions where all elements are (h ^{* T} F).
As described above, the histogram similarity model formulation unit 131 outputs the histogram similarity model H11 shown in Equation 9 and the histogram similarity model _H12 shown in Equation 12, depending on whether a target number of division regions is set or not. Subsequently, the histogram similarity model formulation unit 131 outputs either the histogram similarity model _H11 or the histogram similarity model _H12 to the model variable calculation unit ₁₄ .
As described above, the value taken by the evaluation function generated by the histogram similarity model formulation unit 131 is minimized, so that when selecting a division region, the histogram of the features of the division region approaches the histogram of the features of the target region.

The region size model formulation unit 132, as described above, generates an evaluation function for determining the number of segmented regions to select from the input image. Specifically, it works to maximize the number of selected segmented regions, or to match the number of segmented regions of the detection target. In doing so, it maximizes the sum of the sizes of the selected segmented regions in the input image.

The region size model formulation unit 132 outputs region size models H21 and H22 according to the cases of "when a target number of divided regions is set" and "when a target number of divided regions is not set, _" similar to the histogram similarity model formulation unit _131. Subsequently, the region size model formulation unit 132 outputs region size models _H21 and _H22 to the model variable calculation unit 14.
First, let's explain the case where "a target number of partitioned areas is set."

When a target number of partitioned regions is set, the region size model _H21 is expressed by Equation 13.
(Formula 13)
The region size model _H21 shown in Equation 13 is the square of the difference between the target number of segmented regions (target size) in the input image and the number of segmented regions to be selected in the input image. Therefore, by minimizing this difference, it works to bring the number of selected segmented regions as close as possible to the target number (target size) of segmented regions.

On the other hand, if "the target number of partitioned regions is not set," the region size model _H22 is expressed by Equation 14.
(Formula 14)
The region size model H22 shown in Equation 14 is the sum of the number of selected segmented regions from the input image, with a negative sign. Therefore, by minimizing this value, it works to maximize the number of selected segmented regions (target size) as much as possible.
The domain size model formulation unit 132 outputs the domain size model _H21 shown in equation (13) to the model variable calculation unit 14 when "a target number of divided domains is set", and the domain size model _H22 shown in equation (14) when "a target number of divided domains is not set".

Finally, the region chunking model formulation unit 133 will be explained. As mentioned above, the region chunking model formulation unit 133 generates an evaluation function for determining chunking, which represents the degree to which adjacent divided regions are selected from the input image. Specifically, it is formulated so that when all adjacent regions are selected or none are selected, it becomes a reward term, and when only one of the adjacent regions is selected, it becomes a penalty term. In other words, by minimizing the value taken by the evaluation function generated by the region chunking model formulation unit 133, it acts to select more adjacent regions when selecting divided regions.
To explain the degree of clumping, which represents the degree to which adjacent partitioned regions are selected, we will first explain adjacent partitioned regions.
Let E be the set of edges connecting two adjacent partitioned regions, and let (v(x,y), v(x',y')) be the pair of partitioned regions that represent the relationship between each adjacent region, where v(x,y) ≠ v(x',y'). There is a one-to-one correspondence between two adjacent regions and the edges they share (also called "edges connecting adjacent regions").
Here, we identify the set of adjacent regions with the set of edges E that connect these adjacent regions.
Furthermore, the outermost division region of the image is considered adjacent to the outermost edge of the image, and for convenience, the edges outside this division region are defined as being included in the edge set E. In this case, v(x', y') is assumed to be outside the image. Although v(x', y') is not included in the image, the value of v ^# (x', y') is assumed to be the same as the value of the function v ^# (x, y) of the adjacent region v(x, y).

Figure 3 shows the correspondence between two adjacent divided regions and the edges connecting them. Referring to Figure 3, there are 20 divided regions v(x,y) (x=1,2,3,4,5, y=1,2,3,4). If we consider the outermost divided region to be adjacent to the outermost edge of the image, then the outermost edge of the image can be represented for convenience by v(0,y), v(6,y) (y=1,2,3,4), v(x,0), and v(x,5) (x=1,2,3,4,5). When the value of y is fixed, there are 6 (=5+1) edges connecting two adjacent regions (indicated by arrows), and when the value of x is fixed, there are 5 (=4+1) edges. That is, the number of adjacent regions is (5+1) * 4 + 5 * (4+1) = 49.
Thus, we can see that the number of adjacent regions is X * (Y + 1) + (X + 1) * Y.

The regional aggregateness model formulation unit 133 can define the regional aggregateness model _H3 by the following equation 15.
(Formula 15)
Here, Σ is an operator that takes the sum of all adjacent partitioned regions of the input image.
Note that the value of v ^# (0,y) is the same as the value of the function v ^# (1,y) in the adjacent region v(1,y). Similarly, the value of v ^# (X+1,y) is the same as the value of the function v ^# (X,y) in the adjacent region v(X,y). The same applies to v ^# (x,0) and v#(x,Y+1).
Then, when either all adjacent regions are selected or none are selected,
[-(2v ^# (x,y)-1) * (2v ^# (x',y')-1)] = -1, and acts as a reward term when minimized.
On the other hand, when only one of the adjacent regions is selected,
[-(2v ^# (x,y)-1) * (2v ^# (x',y')-1)] = 1, and acts as a penalty term when minimized. Therefore, the domain aggregate model _H3 shown in this equation works to select as many adjacent partitioned regions as possible when minimized. If many adjacent regions are selected, the aggregate is high and the value of _H3 becomes smaller. If many non-adjacent regions are selected, the aggregate is low and the value of _H3 becomes larger.

Referring to Figures 4A and 4B, an example of the processing of the region blockiness model formulation unit 133 will be explained. Here, the case where X = 5 and Y = 4 is shown as an example. Here, the selected division regions are indicated by hatching. Furthermore, the cases where all adjacent division regions corresponding to the white arrows are selected or none are selected are shown, and the cases where only one of the adjacent division regions corresponding to the black arrows is selected are shown.
When selecting the division region as shown in Figures 4A, 4B, 4C, and 4D, the value of _H3 can be calculated as follows.

Referring to Figure 4A, there are 39 cases where all adjacent regions are selected or none are selected (white arrows), and 10 cases where only one of the adjacent regions is selected (black arrows).
H ₃ =-1・39+1・10=-29
This is the result.
Referring to Figure 4B, there are 37 cases where all adjacent regions are selected or none are selected (white arrows), and 12 cases where only one of the adjacent regions is selected (black arrows).
H ₃ =-1・37+1・12=-25
This is the result.
Referring to Figure 4C, there are 29 cases where all adjacent regions are selected or none are selected (white arrows), and 20 cases where only one of the adjacent regions is selected (black arrows).
H ₃ =-1・29+1・20=-9
This is the result.
Referring to Figure 4D, there are 25 cases where all adjacent regions are selected or none are selected (white arrows), and 24 cases where only one of the adjacent regions is selected (black arrows).
H ₃ =-1・25+1・24=-1
This is the result.
It can be seen that the value of _H3 is at its minimum in the case of Figure 4A and at its maximum in the case of Figure 4D. Thus, the regional clumping model _H3 represents the degree of clumping, which is the degree to which adjacent divided regions are selected from the input image. It can be seen that minimizing the value of the regional clumping model _H3 acts to select more adjacent regions when dividing regions.
The mathematical modeling unit 13 has been explained above.

The histogram similarity models _H11 and _H12 , the region size models _H21 and _H22 , and the region clumping model _H3 , generated by the mathematical modeling unit 13, are all expressed as quadratic equations in terms of the binary variable v ^# (x,y). Therefore, they can be transformed into the QUBO representation shown in equation (1) above by manipulating the equations.
It is obvious to those skilled in the art that binary variables can be converted to QUBO representations if their degree is second or lower. That is, for a binary variable q that takes the value 0 or 1, q and q squared are equivalent (squaring 0 or 1 does not change anything), so first-order terms and second-order terms can be converted to equivalent terms. Also, the constant term can be ignored because it does not affect the evaluation function regardless of how the binary variable is chosen. Thus, for the binary variable v ^# (x,y), the histogram similarity models _H11 and _H12 , the region size models _H21 and _H22 , and the region chunking model _H3 can all be converted to QUBO representations because their degree is second or lower.
Next, the model variable calculation unit 14 will be described.

The model variable calculation unit 14 calculates the solution for the variable that constitutes the optimal partition region in the mathematical model generated by the mathematical modeling unit 13, using the computer 2. The model variable calculation unit 14 outputs the overall function obtained by summing the mathematical models generated by the mathematical modeling unit 13 to the computer 2 and obtains the solution for the variable that is the calculation result.
Here, the model variable calculation unit 14 instructs the computer 2 to calculate the solution for v# (x, y), a binary variable that minimizes the overall function _HALL of equation _2-1 , which is obtained by adding the histogram similarity model H11, the region size model _H21 , and the region clumping model _H3 using the balance coefficients _λ1 , _λ2 , _{and λ3} , when ^" the target number of partitioned regions is set".
H _ALL = λ ₁ H ₁₁ + λ ₂ H ₂₁ + λ ₃ H ₃
(Formula 16)
Similarly, the model variable calculation unit 14 instructs the computer 2 to calculate the solution for v# (x, y), a binary variable that minimizes the overall function _HALL of equation _2-2 , which is obtained by adding the histogram similarity model H12, the region size model _H22 , and the region clumping model _H3 using the balance coefficients _λ1 , _λ2 , _{and λ3} , when ^" the target number of partitioned regions is not set".
H _ALL = λ ₁ H ₁₂ + λ ₂ H ₂₂ + λ ₃ H ₃
(Formula 17)

Here, the balance coefficients _λ1 , _λ2 , and _λ3 represent the weighting applied to each of the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 , respectively. The larger the value, the more weight is placed on the model associated with that value. Initial values are set in advance for the balance coefficients _λ1 , _λ2 , and _λ3 , and the computer is made to perform calculations to obtain the solution for the variable v ^# (x, y). For example, the initial values are set according to how similar the detected region is to the histogram of the target region, or how high the degree of aggregate is to detect the region, etc.
Using the solutions for the acquired variables, three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 are calculated, and the corresponding balance coefficients are adjusted so that the values (calculation results) of each of the three models are below a predetermined threshold. While adjusting the balance coefficients _λ1 , _λ2 , and _λ3 , the process of recalculating (solving) the overall function _HALL is repeated. For example, if the value of any of the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), or _H3 is not below a predetermined threshold, the weight assigned to that model is increased by increasing one of the balance coefficients _λ1 , _λ2 , or _λ3 . This can be used to decrease the value of that model.
By adjusting the balance coefficients _λ1 , _λ2 , and _λ3 in this way, the overall function _HALL can be optimized.
Furthermore, an upper limit may be set on the number of iterations for recalculating this overall function _HALL . Depending on the set upper limit on the number of iterations, the calculation may be terminated even if the value of any of the three models does not fall below a threshold.
Subsequently, the model variable calculation unit 14 outputs the solution for the variable v ^# (x, y) to the region detection unit 15.

The region detection unit 15 determines the region to be detected as a similar region based on the solution of the variable v ^# (x,y) calculated by the model variable calculation unit 14. When the solution of the variable v ^# (x,y) is used directly, the corresponding partitioned region v(x,y) may be used as the similar region.
Alternatively, a similar region may be obtained by post-processing using the partitioned region v ^# (x,y) corresponding to the solution of the variable v ^# (x,y). For example, if multiple quad-connected components are created from a set of partitioned regions corresponding to the solution, the largest of these quad-connected components may be used as the similar region. Note that an oct-connected component may be applied instead of a quad-connected component. Furthermore, a similar region may be obtained by applying closing or opening processes using dilation and deflation in binary image processing to the partitioned region corresponding to the solution.
The data format for similar regions may be data using v(x,y), data modified with pixel information, or image data indicating similar regions with borders, etc.
By determining similar regions in this way, it is possible to display these regions in an output format that suits the user's purpose, for example.
Subsequently, the region detection unit 15 outputs similar regions to the output unit 16.

The output unit 16 outputs the similar region determined by the region detection unit 15 to the output device 60. The output unit 16 may also output the similar region determined by the region detection unit 15 to a device (or system) (not shown) that is connected via communication, rather than to the output device 60.
The functions of the similarity region detection system 100 have been described above. Next, the operation of the similarity region detection device 1 will be described.

Figure 5 is a flowchart showing the operation of the similarity region detection device 1.
Referring to Figure 5, in step S01, the input unit 11 receives the target image and the input image via the input device 50.

In step S02, the feature extraction unit 12 extracts features from the target image and the input image received in step S01. Specifically, the feature extraction unit 12 extracts image features from the target image for the target region containing the object (image) to be detected as similar. Furthermore, the feature extraction unit 12 extracts features from the input image for each divided region v(x, y) obtained by dividing the input image region according to a predetermined size.

In step S03, the mathematical modeling unit 13 generates a histogram similarity model H1, a region size model _H2 , and a region chunking model H3 as mathematical models for determining the partitioned regions to be detected as similar regions, based on the features extracted in step _S02 . Specifically, if a target number of partitioned regions is set, the mathematical modeling unit ₁₃ generates a histogram similarity model _H11 , a region size model _H21 , and a region chunking model _H3 . If a target number of partitioned regions is not set, the mathematical modeling unit 13 generates a histogram similarity model _H12 , a region size model _H22 , and a region chunking model _H3 .

In step S04, the model variable calculation unit 14 sets initial values for the balance coefficients λ1, _λ2 , _{and λ3} used when calculating the overall function _HALL from the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 generated in step S03.

In step S05, the model variable calculation unit 14 uses the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 generated in step S03, and the balance coefficients _λ1 , _λ2 , and _λ3 set in step S04 or adjusted in step S08 (described later), to calculate the solution of the binary variable v ^# (x, y) that minimizes the overall function _HALL using the computer 2.

In step S06, the model variable calculation unit 14 determines whether the number of calculations required to calculate the variable that minimizes the overall function H _ALL is less than or equal to a predetermined threshold. If the number of calculations is less than or equal to the predetermined threshold (Yes), the operation proceeds to step S07. If the number of calculations exceeds the predetermined threshold (No), the operation proceeds to step S09.

In step S07, the model variable calculation unit 14 uses the solutions of the variables obtained in step S05 to calculate three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 , and determines whether the values of each mathematical model are below a predetermined threshold for each model. The thresholds for each of the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 can be freely set according to the desired performance. If the values of each of the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 are below the predetermined threshold for each model (Yes), the process proceeds to step S09. On the other hand, if the value of any of the three models _H1 ( _H11 or _H12 ), _H2 ( _H21 or _H22 ), and _H3 is not below a predetermined threshold for each model (i.e., No), the process proceeds to step S08.

In step S08, the model variable calculation unit 14 either increases the balance coefficient by adding a predetermined positive real number to the corresponding balance coefficient for mathematical models whose values are below a predetermined threshold, or decreases the balance coefficient by adding a predetermined negative real number to the balance coefficient for mathematical models whose values are not below a predetermined threshold. For example, if only the value of the histogram similarity model _H1 ( _H11 or _H12 ) is not below the threshold, the balance coefficient _λ1 is increased, or the balance coefficients _λ2 and _λ3 are decreased. After that, the operation returns to step S05.

In step S09, the region detection unit 15 determines a similar region based on the solution to the binary variable v ^# (x,y) obtained in step S05.

In step S10, the output unit 16 outputs the similar region determined by the region detection unit 15 to the output device 60.
The operation of the similarity region detection device 1 has been explained above.

According to this embodiment, in the similarity region detection device 1, the feature extraction unit 12 receives a target image V ^* and an input image, extracts feature quantities h ^* from the target image V ^* , and extracts feature quantities from each of the divided regions v(x,y) obtained by dividing the input image into predetermined sizes, the mathematical modeling unit 13 generates a mathematical model based on the feature quantities extracted from the target image and the feature quantities extracted from each divided region of the input image, using which of the divided regions to select as a variable, the model variable calculation unit 14 obtains a solution for the variable v ^# (x,y) that minimizes the mathematical model H so that the value of the generated mathematical model H satisfies a predetermined threshold condition, and the region detection unit 15 determines the similarity region identified by the solution of the variable.
As a result, the similarity region detection device 1 can detect similar regions within the input image that are similar to the target image by detecting regions with similar histograms of image features with a constant amount of computation, regardless of the position or shape of the search region.

The mathematical modeling unit 13 may pre-set the target size for detection of similar regions determined by the region detection unit 15. This reduces the computational complexity if the size of the detection target in the input image is known.

The mathematical model H comprises a histogram similarity model _H1 , a region size model _H2 , and a region clumping model _H3 . The histogram similarity model _H1 is minimized to ensure that the histogram h of the feature quantities of the divided regions approaches the histogram of the feature quantities h ^* extracted from the target image. The region size model _H2 is minimized to ensure that the number of divided regions selected from the divided regions satisfies a predetermined condition. The region clumping model _H3 is minimized to increase the degree to which adjacent divided regions are selected from among the divided regions. Thus, appropriate similarity region detection is possible.

The model variable calculation unit 14 may obtain a solution for the variable v# ₍ x, y) that minimizes the overall function _HALL, which is calculated by adding together the histogram similarity model _H1 , the region size model _H2 , and the region clumping model H3, each weighted by different balance coefficients _λ1 , _λ2 , and _λ3 , so as to satisfy ^a predetermined threshold condition.
In this way, the overall function _HALL , which is created based on the balance coefficients _λ1 , _λ2 , and _λ3, can be optimized.

The model variable calculation unit may further calculate the values of the histogram similarity model, the region size model, and the region clumping model using the solution of the variables obtained by minimizing the overall function to satisfy a predetermined threshold condition, and adjust the balance coefficient so that the values of each model are less than or equal to a predetermined threshold.
By adjusting the balance coefficients λ1, λ2, and λ3 in this way, the overall function HALL can be optimized.

The region detection unit may determine the similar region by performing post-processing using the partitioned region identified by the solution of the variables obtained by the model variable calculation unit.
Specifically, the post-processing may be any of the following: a process that sets the largest of the four connected components generated from the divided region as a similar region; a process that sets the largest of the eight connected components generated from the divided region as a similar region; a closing process that performs several dilation processes on the binary image followed by the same number of condensation processes as the dilation process; or an opening process that performs several condensation processes on the binary image followed by the same number of dilation processes as the condensation process.
By determining similar regions in this way, it becomes possible to display similar regions in an output format that suits the user's purpose, for example.

Furthermore, the similarity region detection program according to the present invention is intended to enable a computer to function as the similarity region detection device.

Although embodiments of the present invention have been described above, the present invention is not limited to the embodiments described above. Furthermore, the effects described in these embodiments are merely a list of the most preferred effects arising from the present invention, and the effects of the present invention are not limited to those described in these embodiments.

In this embodiment, the model variable calculation unit 14 calculates the histogram similarity model _H1 using color features extracted from pixel values. However, as mentioned above, the features may also be local features extracted from brightness gradients (i.e., shape features), local features calculated using HOG (Histogram of Oriented Gradient) or SIFT (Scale-Invariant Feature Transform), etc.
In other words, as a histogram similarity model _H1 , it is possible to generate two or more types of histogram similarity models _H1-1 , _H1-2, etc., based on different features.
Alternatively, one could seek to find the variable v#(x,y) that minimizes the overall ^function _HALL shown in Equation ₁₈ , which is obtained by adding two or more histogram similarity models _H1-1 , _H1-2 , etc., a region size model _H2 , and a region clumping model H3 using balance coefficients _λ1-1 , _λ1-2 , _λ2 , and _λ3 .
H _ALL = λ _1-1 H _1-1 +λ _1-2 H _1-2 +λ ₂ H ₂ +λ ₃ H ₃
(Formula 18)
By doing so, the similarity regions calculated by the overall function using histogram similarity models _H1-1 and _H1-2 , which utilize two or more types of features, can detect similarity regions that take two or more types of features into consideration.

In this embodiment, the configuration and operation of the similarity region detection device 1 have been mainly described, but the present invention is not limited thereto. It may also be configured as a method or program for outputting similarity regions to the output device 60, comprising the various components.

Furthermore, the functionality of the similarity region detection device 1 may be realized by recording a program for realizing the device's functions on a computer-readable recording medium, loading the program recorded on this medium into a computer system, and executing it.

Here, "computer system" includes hardware such as the operating system and peripheral devices. Furthermore, "computer-readable recording media" refers to portable media such as flexible disks, magneto-optical disks, ROMs, and CD-ROMs, as well as storage devices such as hard disks built into computer systems.

Furthermore, "computer-readable recording media" may include those that dynamically hold programs for short periods, such as communication lines used when transmitting programs via networks like the Internet or communication lines like telephone lines, as well as those that hold programs for a fixed period, such as volatile memory within the server or client computer systems. Moreover, the program itself may only implement a portion of the aforementioned functions, and may also be capable of implementing the aforementioned functions in combination with programs already recorded in the computer system.

100 Similar Region Detection System 1 Similar Region Detection Device 10 Control Unit
11 Input Unit 12 Feature Extraction Unit 13 Mathematical Modeling Unit 131 Histogram Similarity Model Formulation Unit 132 Region Size Model Formulation Unit 133 Region Bulking Model Formulation Unit 14 Model Variable Calculation Unit 15 Region Detection Unit 16 Output Unit 20 Storage Unit 50 Input Device 60 Output Device 2 Computer (Ising Machine)

Claims (9)

An input unit that receives the target image and the input image,
A feature extraction unit extracts features from the target image and also extracts features from each of the divided regions obtained by dividing the input image into pre-set sizes.
A mathematical modeling unit generates a mathematical model based on the features extracted from the target image by the feature extraction unit and the features extracted from each segmented region of the input image, with the selection of which segmented region to choose as a variable.
A model variable calculation unit obtains a solution for the variables that minimizes the mathematical model so that the values of the mathematical model generated by the mathematical modeling unit satisfy a predetermined threshold condition,
The system includes a region detection unit that determines a similar region identified by the solution of the variables obtained by the model variable calculation unit,
A similar region detection device that outputs similar regions determined by the region detection unit. The mathematical modeling unit is,
The similar region detection device according to claim 1, wherein the size of the detection target for the similar region determined by the region detection unit is set in advance. The aforementioned mathematical model comprises a histogram similarity model, a region size model, and a region clumping model.
The histogram similarity model is minimized so that the histogram of the features in the divided region approaches the histogram of the features extracted from the target image.
The aforementioned region size model is minimized so that the number of division regions selected from the division regions satisfies a predetermined condition.
The similarity region detection device according to claim 1 or claim 2, wherein the region clumping model is minimized to increase the degree to which adjacent divided regions are selected from among the divided regions. The aforementioned model variable calculation unit is:
The similarity region detection device according to claim 3, which obtains a solution for the variable that minimizes an overall function calculated by adding the histogram similarity model, the region size model, and the region clumping model, each weighted by different balance coefficients, so as to satisfy a predetermined threshold condition. The aforementioned model variable calculation unit is:
The similarity region detection device according to claim 4, wherein the values of the histogram similarity model, the region size model, and the region clumping model are calculated using the solution of the variables obtained by minimizing the overall function to satisfy a predetermined threshold condition, and the balance coefficient is adjusted so that the value of each model is less than or equal to a predetermined threshold. The aforementioned model variable calculation unit is:
The similarity region detection device according to claim 5, wherein the values of the histogram similarity model, the region size model, and the region clumping model are calculated using the solution of the variables obtained by minimizing the overall function to satisfy a predetermined threshold condition, and if the value of any of the models is not less than or equal to the threshold, the balance coefficient corresponding to the model is increased. The region detection unit,
The similarity region detection device according to claim 1 or claim 2, wherein the similarity region is determined by post-processing using the partitioned region identified by the solution of the variables obtained by the model variable calculation unit. The aforementioned post-processing is as follows:
The similarity region detection device according to claim 7, comprising any of the following processes: a process in which the largest of the four connected components generated from the divided region is designated as a similarity region; a process in which the largest of the eight connected components generated from the divided region is designated as a similarity region; a closing process in which a dilation process is performed on the binary image several times, followed by a stenosis process the same number of times as the dilation process; or an opening process in which a stenosis process is performed on the binary image several times, followed by a dilation process the same number of times as the stenosis process. A similar region detection program for causing a computer to function as a similar region detection device according to claim 1 or claim 2.