Function approximation processing method and image processing method

• US 20050238244A1
• Filed: 04/20/2005
• Published: 10/27/2005
• 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
• Granted Patent: US 7,873,218 B2
• Time in Patent Office: Days
• US Class Current: 382/242
• 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:

an input step of inputting image data;

a binarization step of binarizing the input image data;

a contour extraction step of extracting contour from the binarized image data;

a tangent point estimation step of estimating tangent points in horizontal and vertical directions from the extracted contour; and

a function approximation step of approximating the contour between adjacent tangent points with a predetermined function.

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 at said tangent point estimation step, a straight line pattern in said horizontal and vertical directions is detected by pattern matching, and estimation 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 at said function approximation 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 the 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 at said tangent point estimation 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 at said function approximation step, approximation processing is performed on a contour line segment group between tangent points where the 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.

26. A program for executing the function approximation method in claim 1, 8 or 12 by a computer.

8. A function approximation processing method for allocating a cubic Bezier curve to a point sequence forming a curve, comprising:

a curve dividing step of extracting a point sequence drawing an arc from said point sequence; and

an approximation step of allocating a cubic Bezier curve to the extracted point sequence so as to obtain a straight line connecting two anchor points of the cubic Bezier curve and a straight line connecting two control points parallel to each other.

9. The function approximation processing method according to claim 8, wherein said curve dividing step has a step of extracting a tangent element of curve in divided points, and said approximation step has a characterizing point extraction step of extracting one characterizing point from the point sequence extracted at said curve dividing step,

and wherein approximation is performed with a cubic Bezier curve by using the one characterizing point on the divided curve, two divided points, and a tangent element in the respective divided points.

10. The function approximation processing method according to claim 9, wherein at said characterizing point extraction step, a point of the point sequence on the divided curve, away from the straight line connecting the anchor points by a maximum distance, is extracted.

11. The function approximation processing method according to claim 9, wherein said approximation step has a step of extracting a characterizing point on an approximated curve, comparing said characterizing point with the characterizing point obtained at said characterizing point extraction step, and if the difference is large, performing curve dividing with the characterizing point obtained at said characterizing point extraction step as a new anchor point.

12. A function approximation processing method comprising:

an input step of inputting image data;

a binarization step of binarizing the input image data;

a contour extraction step of extracting contour from the binarized image data;

a step of detecting an area surrounded by a closed curve based on the extracted contour and obtaining the size of the area;

a step of, upon function approximation of a profile line by said area, defining a parameter for the function approximation in accordance with the size of the area; and

a step of performing function approximation on contour pixels in the area in accordance with the defined parameter.

13. The function approximation processing according to claim 12, further comprising a step of outputting the result of approximation as data in the form of predetermined shape modeling language.

14. An image processing method comprising:

a step of segmenting raster image data then extracting a character area, and cutting out characters from the character area by each character;

an outline conversion step of converting the cut character to outline data having straight lines and curves; and

a step of outputting the result of conversion as data in the form of predetermined shape modeling language.

15. The image processing method according to claim 14, wherein said cutting step has a character size detection step of detecting character size information,

and wherein at said outline conversion step, a parameter for outline conversion is changed in correspondence with the character size information detected at said character size detection step.

16. The image processing method according to claim 15, wherein at said outline conversion step, a character object in said character area is converted to outline having straight lines and curves, and an outline conversion parameter for said character object is changed in correspondence with the character size information detected at said character size detection step.

27. A program for executing the image processing method in claim 14 or 17 by a computer.

17. An image processing method for converting binary image data to outline data using Bezier curves, comprising:

a curve dividing step of dividing a contour point sequence of a binary image extracted from input computerized data into contour segments each can be approximated with a Bezier curve and storing position information of start point and terminal point of each divided contour segment into storage means;

a characterizing point determination step of determining at least one point of the contour point sequence belonging to each divided contour segment as a characterizing point satisfying a first distance condition to a first line segment connecting the start point and the terminal point of said divided contour segment, and storing position information of the characterizing point into said storage means;

a control point determination step of comparing position information on a second line segment parallel to the first line segment satisfying a second distance condition to said first line segment, with position information on tangents to the respective start point and terminal point of said divided contour segment, determining intersection points where both position information correspond with each other as control points, and storing position information of the determined control points into said storage means; and

an approximation computation step of reading the position information of the start point and terminal point of said divided contour segment and the position information of said characterizing point and said control points from said storage means, and approximating said divided contour segment with said Bezier curve.

18. The image processing method according to claim 17, wherein at said characterizing point determination step, distances between respective contour points to said first line segment specified with the start point and terminal point of said divided contour segment are calculated, and a contour point with a maximum distance, obtained by comparison of calculation results, is determined as the characterizing point.

19. The image processing method according to claim 17, wherein said second line segment obtained at said control point determination step satisfies the relation, the second distance condition=(4/3)×

the first distance condition.

20. The image processing method according to claim 17, wherein at said approximation computation step, the position information of the characterizing point is compared with the position information of a point on an approximated Bezier curve corresponding the characterizing point, and if said position information is within the range of allowable threshold coordinate value, said approximated curve is confirmed,

and wherein if said position information is without the range of allowable threshold coordinate value, said divided contour segment is redivided in the position of said characterizing point determined at said characterizing point determination step, at said curve dividing step.

21. 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 contour from the binarized image data;

tangent point estimation means for estimating tangent points in horizontal and vertical directions from the extracted contour; and

function approximation means for approximating the contour between adjacent tangent points with a predetermined function.

22. A function approximation processing apparatus for allocating a cubic Bezier curve to a point sequence forming a curve, comprising:

curve dividing means for extracting a point sequence drawing an arc, from a point sequence; and

approximation means for allocating a cubic Bezier curve so as to obtain a straight line connecting two anchor points of the cubic Bezier curve and a straight line connecting two control points parallel to each other.

23. 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 contour from the binarized image data;

means for detecting an area surrounded by a closed curve based on the extracted contour and obtaining the size of the area;

means for, upon function approximation of a profile line by said area, defining a parameter for the function approximation in accordance with the size of the area; and

means for performing function approximation on contour pixels in the area in accordance with the defined parameter.

24. An image processing apparatus comprising:

means for segmenting raster image data then extracting a character area, and cutting out characters from the character area by each character;

outline conversion means for converting the cut character to outline data having straight lines and curves; and

means for outputting the result of conversion as data in the form of predetermined shape modeling language.

25. An image processing apparatus for converting binary image data to outline data using Bezier curves, comprising:

curve dividing means for dividing a contour point sequence of a binary image extracted from input computerized data into contour segments each can be approximated with a Bezier curve and storing position information of start point and terminal point of each divided contour segment into storage means;

characterizing point determination means for determining at least one point of the contour point sequence belonging to each divided contour segment as a characterizing point satisfying a first distance condition to a first line segment connecting the start point and the terminal point of said divided contour segment, and storing position information of the characterizing point into said storage means;

control point determination means for comparing position information on a second line segment parallel to the first line segment satisfying a second distance condition to said first line segment, with position information on tangents to the respective start point and terminal point of said divided contour segment, determining intersection points where both position information correspond with each other as control points, and storing position information of the determined control points into said storage means; and

approximation computation means for reading the position information of the start point and terminal point of said divided contour segment and the position information of said characterizing point and said control points from said storage means, and approximating said divided contour segment with said Bezier curve.