Function approximation processing method and image processing method

• US 7,873,218 B2
• Filed: 04/20/2005
• Issued: 01/18/2011
• Est. Priority Date: 04/26/2004
• Status: Active Grant

• Current Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Original Assignee: Canon Kabushiki Kaisha (Canon Inc.)
• Inventors: Uzawa, Mitsuru
• Primary Examiner(s): Le; Vu
• Assistant Examiner(s): BLOOM, NATHAN J
• Application Number:
  US11/109,851
• Publication Number:
  US 20050238244A1
• Time in Patent Office: 2,099 Days
• Field of Search: 382/181, 382/185, 382/190, 382/195, 382199-200, 358/1.1, 358/2.99, 358/3.01, 358/400, 358/462, 358/500, 345440-443, 345/647, 345/657, 345/679
• US Class Current: 382/199
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges

Abstract

A function approximation processing method comprises inputting and binarizing image data, extracting contour from the binarized image data, estimating tangent points in horizontal and vertical directions from the contour, and approximating contour between adjacent tangent points among the estimated tangent points with a predetermined function, thereby an input object such as a character or a figure can be processed at high speed, and outline data with high image quality can be generated with a reduced number of points.

Claims

1. A function approximation processing method comprising:

performing by a processor the following steps;

an input step of inputting image data;

a binarization step of binarizing the input image data;

a contour extraction step of extracting line segments of horizontal and vertical directions from the binarized image data;

a tangent line segment extraction step of extracting, as a tangent line segment, a line segment that has a length satisfying predetermined conditions from the extracted line segments of horizontal and vertical directions;

an anchor point extraction step of extracting, as an anchor point, a point on the extracted tangent line segment, wherein the anchor point is an endpoint on the extracted tangent line segment in a case where a line segment adjacent to the extracted tangent line segment is a tangent line segment, or the anchor point is a point that corresponds to an end point on the extracted tangent line segment that is shifted, in a case where the line segment adjacent to the extracted tangent line segment is not a tangent line segment;

a curve approximation processing step of performing curve approximation processing in which a line segment between anchor points that are respectively extracted in the anchor point extraction step is approximated to a curve; and

a correction step of replacing the curve approximated in the curve approximation processing step with a diagonal straight line in a case where the line segment approximated in the curve approximation processing step was originally a diagonal straight line.

2. The function approximation processing method according to claim 1, wherein at said contour extraction step, the contour of said image is extracted by extracting a profile line so as to trace the periphery of said image while handling one pixel of said image as a square element formed with four points.

3. The function approximation processing method according to claim 1, wherein, in the tangent line segment extraction step, a straight line pattern in said horizontal and vertical directions is detected by pattern matching, and extraction is made based on relative positional relation between the detected straight line pattern and neighboring contour pixels.

4. The function approximation processing method according to claim 1, wherein the curve approximation processing step has:

first approximation processing of allocating one quadratic Bezier curve, one cubic Bezier curve or a straight line to a contour line segment group between tangent points where a number of contour line segments between said tangent points is smaller than a predetermined value; and

second approximation processing of allocating one or plural cubic Bezier curves to a contour line segment group between tangent points where the number of contour line segments between said tangent points is larger than a predetermined value.

5. The function approximation processing method according to claim 4, wherein in said first approximation processing, any one of a quadratic Bezier curve, a cubic Bezier curve or a straight line is allocated in correspondence with the result of detection of straight line pattern in said horizontal and vertical directions in said tangent line segment extraction step.

6. The function approximation processing method according to claim 4, wherein said second approximation processing is allocating one or plural cubic Bezier curves to a contour line segment group, and in use of the cubic Bezier curve, a straight line connecting anchor points and a straight line connecting control points are parallel to each other.

7. The function approximation processing method according to claim 1, wherein, in the curve approximation processing step, approximation processing is performed on a contour line segment group between tangent points where a number of contour line segments between said tangent points is smaller than a predetermined value, based on the relative positional relation between said tangent points.

9. A non-transitory computer-readable storage medium storing a program for executing the function approximation method of claim 1 by a computer.

10. The method according to claim 1, wherein in the anchor point extraction step, in a case where a vector V1 of a line segment adjacent to a vector V2 of the extracted tangent line segment is a tangent line segment, an end point on the vector V2 is extracted as an anchor point, or in a case where the vector V1 of a line segment adjacent to the vector V2 of the extracted tangent line segment is not a tangent line segment, a point away from an end point on the vector V2 by a|V1| (wherein “

a”

is a scalar multiplier) or the central point of the vector V2 is extracted as an anchor point.

8. A function approximation processing apparatus comprising:

input means for inputting image data;

binarization means for binarizing the input image data;

contour extraction means for extracting line segments of horizontal and vertical directions from the binarized image data;

tangent line segment extraction means for extracting, as a tangent line segment, a line segment that has a length satisfying predetermined conditions from the extracted line segments of horizontal and vertical directions;

anchor point extraction means for extracting, as an anchor point, a point on the extracted tangent line segment, wherein the anchor point is an end point on the extracted tangent line segment in a case where a line segment adjacent to the extracted tangent line segment is a tangent line segment, or the anchor point is a point that corresponds to an end point on the extracted tangent line segment that is shifted, in a case where the line segment adjacent to the extracted tangent line segment is not a tangent line segment;

curve approximation processing means for performing curve approximation processing in which a line segment between anchor points that are respectively extracted in the anchor point extraction step is approximated to a curve; and

correction means for replacing the curve approximated in the curve approximation processing step with a diagonal straight line in a case where the line segment approximated in the curve approximation processing step was originally a diagonal straight line.