Computer system and method of matching for images and graphs

• US 8,666,170 B2
• Filed: 02/18/2011
• Issued: 03/04/2014
• Est. Priority Date: 09/29/2010
• Status: Expired due to Fees

• Current Assignee: Hitachi, Ltd.
• Original Assignee: Hitachi, Ltd.
• Inventors: Guo, Tao
• Primary Examiner(s): Chu, Randolph I
• Application Number:
  US13/030,428
• Publication Number:
  US 20120076409A1
• Time in Patent Office: 1,110 Days
• Field of Search: None
• US Class Current: 382/209
• CPC Class Codes: G06V 10/752 Contour matching
• CPC Class Codes: G06V 10/758 Involving statistics of pixels or of feature values, e.g. histogram matching

Abstract

It is provided a computer system for matching between images/graphs comprising a processing unit, a storage unit, an input unit and a data recording unit, wherein the computer system includes a feature pattern generating unit for generating a set of feature patterns of the image and the graph from the received image and the received graph, segmenting each of the image and the graph into a plurality of regions centered on a sample point, and determining characteristics of the plurality of regions; a correspondence computing unit for computing correspondence between the image and the graph to be matched by comparing the generated feature patterns; a transform unit for transforming a coordinate system of at least one of the image and the graph to be matched; and a combination unit for combining the image and the graph that have been subjected to the transform of the coordinate system.

Claims

1. A computer system for matching between images, between graphs, and between an image and a graph, the computer system comprising:

a processing unit for executing a program;

a storage unit for storing the program executed by the processing unit;

an input unit for receiving at least two of the image and the graph to be matched;

a data recording unit for storing, in a storage device, the received image and the received graph;

a feature pattern generating unit for generating a set of locoregional feature patterns of a plurality of sampling points allocated on each of the two of the image and the graph to be matched on the basis of the received image and the received graph;

a correspondence computing unit for computing a correspondence between the two of the image and the graph to be matched by comparing the generated locoregional feature patterns;

a transform unit for transforming a coordinate system of at least one of the image and the graph to be matched based on the computed correspondence; and

a combination unit for combining the image and the graph that have been subjected to the transform of the coordinate system thereof,

wherein the feature pattern generating unit is configured to;

provide a moving point for each of the plurality of sample points, the moving point being positioned on a periphery of a circle centered on the corresponding one of the sample points;

and for each of the sample points;

segment a local region around the sample point on each of the two of the image and the graph into a plurality of concentric circle and ring regions centered on the sample point,

scan the concentric circle and ring regions of each of the two of the image and graph along a scan line, which is defined with the sample point and the moving point as ends thereof, under a condition that an azimuth angle of the moving point is a particular angle to generate a feature vector of each of the two of the image and graph,

repeatedly scan the concentric circle and ring regions along the scan line while the moving point is moved along the periphery of the circle by a predetermined center angle to generate a series of feature vectors; and

combine the generated series of feature vectors to generate the locoregional feature pattern of each of the two of the image and graph regarding the point.

2. The computer system according to claim 1, wherein:

the feature pattern generating unit is further configured to;

count a number of significant pixels included in each of the concentric circle and ring regions along line;

obtain a normalized feature value of the each of the concentric circle and ring regions by dividing the counted number of significant pixels by a total number of pixels within each of the concentric circle and ring regions on the scan line; and

generate the feature vectors each having the normalized feature values, as elements thereof.

3. The computer system according to claim 1, wherein the feature pattern generating unit is further configured to:

evaluate the generated feature patterns by using an angle between each of the feature vectors and a vector having all elements thereof equal to 1; and

generate the set of the feature patterns including feature patterns determined to be good as a result of the evaluation.

4. The computer system according to claim 3, wherein the feature pattern generating unit is further configured to:

compute an angle between the each of the feature vectors and a central vector having all elements thereof equal to 1;

compute an average of all the angles of one of the plurality of sample points as an angle of the feature pattern;

determine whether the average of the angles between the feature vectors and the central vector falls within a given range;

determine whether a direction of a vector having the average of the angles is similar to a direction of the central vector by using a given threshold; and

determine that the feature pattern of the one of the plurality of sample points is a good feature pattern in a case where it is determined that the direction of the vector having the average of the angles is similar to the direction of the central vector.

5. The computer system according to claim 3, wherein the feature pattern generating unit is further configured to:

select the good feature patterns so that an average of the angles of the feature patterns becomes smaller than a given threshold; and

keep only a good feature pattern closest to the average of the angles of the feature patterns among the selected good feature patterns, and remove the other selected good feature patterns from the selected good feature patterns.

6. The computer system according to claim 1, further comprising a refinement unit for transforming shapes of modules included in the at least one of the image and the graph to be matched, according to coordinates obtained through the transform of the coordinate system to reduce derivatives of the modules,

wherein the combination unit combines the image and the graph that have been subjected to refinement of the shapes of the modules.

7. The computer system according to claim 6, wherein the refinement unit is configured to:

extract edges in a destination image/graph of the image and the graph to be matched in the case where transforming the shapes of the modules; and

deform edges in a source image/graph to fit the edges in the destination image/graph.

8. A method of matching between images, between graphs, and between an image and a graph using a computer, the method comprising:

an input step of receiving at least two of the image and the graph to be matched, and storing, in a storage device, the received image and the received graph;

a feature pattern generating step of generating a set of locoregional feature patterns of a plurality of sampling points allocated on each of the two of the image and the graph to be matched on the basis of the received image and the received graph;

a corresponding computing step of computing a correspondence between the image and the graph to be matched by comparing the generated locoregional feature patterns;

a transform step of transforming a coordinate system of at least one of the image and the graph to be matched based on the computed correspondence; and

a combination step of combining the image and the graph that have been subjected to the transforming of the coordinate system thereof,

wherein the feature pattern generating step further comprises;

providing a moving point for each of the plurality of sample points, the moving point being positioned on a periphery of a circle centered on the corresponding one of the points;

and for each of the sample points;

segmenting a local region around the sample point on each of the two of the image and the graph into a plurality of concentric circle and ring regions centered on the sample point,

scanning the concentric circle and ring regions of each of the two of the image and graph along a scan line, which is defined with the sample point and the moving point as ends thereof, under a condition that an azimuth angle of the moving point is a particular angle to generate a feature vector of each of the two of the image and graph,

repeatedly scanning the concentric circle and ring regions along the scan line while the moving point moves alone the periphery of the circle by a predetermined center angle to generate a series of feature vectors; and

combining the generated feature vectors to generate the locoregional feature pattern of each of the two of the image and graph regarding the point.

9. The method of matching according to claim 8, wherein:

the feature pattern generating step further comprises;

counting a number of significant pixels included in each of the concentric circle and ring regions along the scan line;

obtaining a normalized feature value of the each of the concentric circle and ring regions by dividing the counted number of significant pixels by a total number of pixels within each of the concentric circle and ring regions on the scan line; and

generating the feature vectors each having the normalized feature values, as elements thereof.

10. The method of matching according to claim 8, wherein the feature pattern generating step further comprises:

evaluating the generated feature patterns by using an angle between each of the feature vectors and a vector having all elements thereof equal to 1; and

generating the set of the feature patterns including feature patterns determined to be good as a result of the evaluating.

11. The method of matching according to claim 10, wherein the feature pattern generating step further comprises:

computing an angle between the each of the feature vectors and a central vector having all elements thereof equal to 1;

computing an average of all the angles of one of the plurality of sample points as an angle of the feature pattern;

determining whether the average of the angles between the feature vectors and the central vector falls within a given range;

determining whether a direction of a vector having the average of the angles is similar to a direction of the central vector by using a given threshold; and

determining that the feature pattern of the one of the plurality of sample points is a good feature pattern in a case where it is determined that the direction of the vector having the average of the angles is similar to the direction of the central vector.

12. The method of matching according to claim 10, further comprising, in the generating the set of the feature patterns:

selecting the good feature patterns so that an average of the angles of the feature patterns becomes smaller than a given threshold; and

keeping only a good feature pattern closest to the average of the angles of the feature patterns among the selected good feature patterns, and removing the other selected good feature patterns from the selected good feature patterns.

13. The method of matching according to claim 8, further comprising, after the transform step, transforming shapes of modules included in the at least one of the image and the graph to be matched, according to coordinates obtained in the transforming the coordinate system to reduce derivatives of the modules,

wherein the combination step comprises combining the image and the graph that have been subjected to refinement of the shapes of the modules.

14. The method of matching according to claim 13, further comprising, in the transforming the shapes of the modules:

extracting edges in a destination image/graph of the image and the graph to be matched; and

deforming edges in a source image/graph to fit the edges in the destination image/graph.