Method and apparatus for generating and producing two-dimensional graphic object by polynominal parametric curves

• US 4,949,281 A
• Filed: 04/19/1988
• Issued: 08/14/1990
• Est. Priority Date: 04/23/1987
• Status: Expired due to Fees

• Current Assignee: H Berthold AG Teltowkanalstrasse
• Original Assignee: H Berthold AG
• Inventors: Schroer, Klaus, Sprenger, Dietmar, Dlabka, Michael, Hillenbrand, Franz, Rebs, Frank
• Primary Examiner(s): Harkcom, Gary V.
• Assistant Examiner(s): Bayerl, Raymond J.
• Application Number:
  US07/183,603
• Time in Patent Office: 847 Days
• Field of Search: 340/730, 340/735, 340/751, 382/22, 364/200 MS File, 364/900 MS File, 364/523, 364/518
• US Class Current: 345/442
• CPC Class Codes: B41B 19/02 the characters appearing on the screen in succession
• CPC Class Codes: G06K 15/02 using printers
• CPC Class Codes: G06K 2215/0028 characterised by the format per se
• CPC Class Codes: G06K 2215/0034 Outline coding
• CPC Class Codes: G06T 9/20 Contour coding, e.g. using detection of edges
• CPC Class Codes: G06V 10/46 Descriptors for shape, contour or point-related descriptors, e.g. scale invariant feature transform [SIFT] or bags of words [BoW]; Salient regional features colour feature extraction G06V10/56
• CPC Class Codes: G09G 1/08 the beam directly tracing characters, the information to be displayed controlling the deflection and the intensity as a function of time in two spatial co-ordinates, e.g. according to a cartesian co-ordinate system
• CPC Class Codes: G09G 1/14 the beam tracing a pattern independent of the information to be displayed, this latter determining the parts of the pattern rendered respectively visible and invisible

Abstract

The invention utilizes polynomials, where the graphic objects are predetermined in the form of reference contours in contour coordinates. The generation process involves subdividing the length of each contour segment into a multiple of curve segments each, preferably a straight line. The coordinate points associated with the respective curve segments are compared with those of the given contour segment and the distance between them is determined. If a predetermined distance between them is exceeded, the coordinate location on the contour segment which is at the greatest distance from the straight line is chosen. A curve defined by the use of parametric spline functions is then laid between the starting and end point and incorporating the chosen base point. At a time when the predetermined distance no longer is exceeded, the base points assigned are stored in a memory. The apparatus contains a central processing unit, a register for storage of the scanned pixel matrix and the outside contours, and a register for storage of the reference contours and the spline data. Corner recognition and filtering circuitry provides the recognition of corners and filtering where the scanned contour is smoothed for determining the reference contour. A step counter and a step register are provided for coordination between the deviation stored in a register and the respective coordinates.

Claims

1. A method for generating two-dimensional graphic objects for electronic or electromechanical reproduction by the use of polynomials, where the graphic objects are provided as reference contours in contour coordinates, and where the number of contours per object and the number of contour segments per contour is predetermined, and where the starting point and the end point of the contour segments are established, the method comprising the steps of:

(a) subdividing the length of any given contour segment into a plurality of curve segments;

(b) defining the starting point and the end point of the given contour segment;

(c) connecting the starting point and the end point of the given contour segment by a defined curve section, the length of which is subdivided into the same number of curve segments as the given contour segment;

(d) comparing the coordinate points of the respective curve segment of the defined curve section and the contour segment with each other;

(e) determining the distance between the coordinate points of the defined curve segment and the contour segment;

(f) choosing a base coordinate point, when the distance between the coordinate points of the defined curve segment and the contour segment exceeds a predetermined amount, which is at the greatest distance from the defined curve segment;

(g) laying a resulting curve through the starting point and the end point and the base point with the use of parametric spline functions;

(h) again subdividing the resulting curve segment into the same number of curve segments as the given contour segment;

(i) comparing the coordinate points of the resulting curve with the coordinate points of the given contour segment;

(j) determining the distance between the coordinate points of the resulting curve and the contour segment;

(k) choosing a further base point, when the distance between the coordinate points of the resulting curve and the contour segment exceeds a determined amount, which is the greatest distance from the the given contour segment; and

(1) repeating steps g through k until the predetermined distance amount is no longer exceeded.

2. The method of claim 1 further including the step of storing the chosen base points and the starting points and the end points of each contour segment and, also, the difference of the curve segments between the base points.

3. The method of claim 1 further including the step of employing periodic spline functions for smooth closed contours.

4. The method of claim 1 further including the step of employing natural spline functions for non-smooth contours.

5. The method of claim 1 further including the step of smoothing a reference contour provided by a digital data source by an averaging procedure across neighboring coordinate points.

6. The method of claim 1 further including the steps of reproducing two-dimensional graphic objects comprising the steps of:

linearly transforming the base points which are stored for each contour and which are dependent upon the curve segments of the contour segments between two respective base points for each desired dimensional change with the aid of cubic spline functions and the given base points to define the coefficients x(t), y(t) of the cubic polynomials;

transforming the polynomial coefficients into starting values which respectively correspond to the value of the function and the first, second and third differentials at a location t+0; and

respectively determining new starting values for each new coordinate location of the contour segment through the addition of two different previous starting values.

7. An apparatus for generating two-dimensional graphic objects for electronic or electromechanical reproduction by the use of polynominals where the graphic objects are provided as reference contours in contour coordinates, and where the number of contours per object and the number of contour segments per contour is predetermined, and where the starting point and the end point of the contour segments are established, the apparatus comprising:

central processing means;

means, responsive to the central processing means, for scanning an original character;

first storage means, responsive to the output of the scanning means, for storing the scanned pixel matrix and the outside contours of the original character;

second storage means, response to the output of the scanning means, for storing reference contours and spline function data;

means for recognizing the corners of each character and for filtration of outside contour points of the character to smooth out the scanned contour for determining the reference contour; and

approximation means for approximating the reference contour segment.

8. The apparatus of claim 7 wherein the corner recognition and filtration means comprises:

first address counter means, connected to the first storage means, for storing the starting address of the scanned outside contour stored in the first storage means;

second address counter means for storing the starting address of the resultant smooth reference contour;

first and second contour filter means for generating the average and difference values, respectively, of the coordinates of a plurality of sequential contour points;

a corner filter for recognizing the corner of a contour; and

sequence controller means, responsive to the central processing means, for operating the corner recognition and filtration means.

9. The apparatus of claim 8 wherein each of the first and second contour filter means comprises:

first stack register means for temporarily storing the coordinate of each contour point;

subtraction means, connected to the first stack register means, for subtracting a value delayed by N-value from the value stored in the first stack register means;

register means for storing partial flowing sums;

adder means for adding the increment output from the subtraction means to the output of the register means;

second, third and fourth stack register means for storing average values each of which has been delayed by N-steps, respectively; and

summation means for suming the outputs of the register means and of the second, third and fourth stack register means.

10. The apparatus of claim 9 wherein each contour filter further comprises:

subtraction means for generating differences between the contents of the register means and the first stack register means and the third and fourth stack register means, respectively, which correspond to generated average values which are input to the corner filter.

11. The apparatus of claim 10 wherein the corner filter comprises:

multiplier means, responsive to the sequence controller means, for multiplying the differences of the x and y contours with each other in a crosswise fashion;

storage means for storing the resulting crosswise multiplication products; and

comparator means for comparing the resulting crosswise multiplication products with the resultant product of the sequential y-coordinate differences.

12. The apparatus of claim 7 wherein the approximation means comprises:

logic means, responsive to the central processing means, for generating the starting values of the coordinates of each contour point.

13. An apparatus for generating two-dimensional graphic objects for electronic or electromechanical reproduction by the use of polynomials where the graphic objects are provided as reference contours in contour coordinates, and where the number of contours per object and the number of contour segments per contour is predetermined, and where the starting point and the end point of the contour segments are established, the apparatus comprising:

central processing means;

means, responsive to the central processing means, for scanning an original character;

first storage means, responsive to the output of the scanning means, for storing the scanned pixel matrix and the outside contours of the original character;

second storage means, responsive to the output of the scanning means, for storing reference contours and spline function data;

means for recognizing the corners of each character and for filtration of outside contour points of the character to smooth out the scanned contour for determining the reference contour; and

approximation means for approximating the reference contour segment, the approximation means including logic means, responsive to the central processing means, for generating the starting values of the coordinates of each contour point, the logic means comprising;

reference contour storage register means for storing the coordinates of the reference contour;

comparison means for comparing the coordinates of the approximating contour with the coordinates of the reference contour; and

deviation storage register means for storing the deviation between the coordinates of the approximating contour and the coordinates of the reference contour;

the comparison means comparing the deviations of the two successive coordinates and storing the largest deviation in the deviation storage register means.

14. The apparatus of claim 13 further including:

step counter means; and

step register storage means for storing the associated contour parameter value.