Patent ID: 8514457

Claim:
An information extraction apparatus comprising: an obtaining unit that obtains image data that includes therein information that are printed with multiple types of patterns in a matrix therein; a line-segment-sequence calculating unit that calculates a plurality of vertical-line-segment sequences, each of which is obtained by connecting patterns arranged in a vertical row in the image data with a particular polygonal line, and calculates a plurality of horizontal-line-segment sequences, each of which is obtained by connecting patterns arranged in a horizontal row in the image data with another polygonal line; a search unit that searches, for each combination of one vertical-line-segment sequence of the vertical-line-segment sequences and one horizontal-line-segment sequence of the horizontal-line-segment sequences, vertical line segments that form the one vertical-line-segment sequence and horizontal line segments that form the one horizontal-line-segment sequence for a vertical line segment and a horizontal line segment that intersect with each other; an intersection-point calculating unit that calculates a point of intersection between the vertical line segment and the horizontal line segment having been found by the search unit as a position of a pattern; and an extracting unit that extracts the information by identifying types of patterns at the points, calculated by the intersection-point calculating unit, of intersection between the vertical line segments and the horizontal line segments, wherein the search unit selects a vertical line segment and a horizontal line segment to be subjected to intersection determination calculates a point of intersection between the selected vertical line segment or an extension thereof and the selected horizontal line segment or an extension thereof by using values of parameters, and determines whether the vertical line segment and the horizontal line segment intersect with each other based on the values of the parameters, and wherein if the vertical line segment and the horizontal line segment are determined not to be intersecting with each other based on the values of the parameters the search unit selects a vertical line segment and a horizontal line segment to be subjected to intersection determination next based on the values of the parameters.