Source: http://www.google.com/patents/US4771474?dq=%22Meaning-based+advertising+and+document+relevance+determination%22
Timestamp: 2014-09-21 09:03:15
Document Index: 715792308

Matched Legal Cases: ['art 60', 'art 60', 'art 61', 'art 62', 'art 66', 'art 67', 'art 68', 'art 61', 'art 66', 'art 69', 'art 62', 'art 67', 'art 70', 'art 68', 'art 71', 'art 68', 'art 68', 'art 69', 'art 61', 'art 62', 'art 60', 'art 66', 'art 60', 'art 66', 'art 68', 'art 61', 'art 70', 'art 71', 'art 71', 'art 71', 'arts 70', 'art 67', 'art 69', 'art 62', 'art 69', 'art 71', 'art 71', 'art 71', 'art 71', 'art 71', 'art 70']

Patent US4771474 - Apparatus for processing character or pictorial image data - Google PatentsSearch Images Maps Play YouTube News Gmail Drive More »Sign in<nobr>Advanced Patent Search</nobr>PatentsAn apparatus for processing character or pictorial image or the like for splitting the outline of a character, which is developed on x- and y-coordinates, into a plurality of blocks [P1, Pn ] (where P1 and Pn are a start point and an end point of an arbitrary block respectively) each defined by a univalent...http://www.google.com/patents/US4771474?utm_source=gb-gplus-sharePatent US4771474 - Apparatus for processing character or pictorial image dataAdvanced Patent SearchPublication numberUS4771474 APublication typeGrantApplication numberUS 07/057,390Publication dateSep 13, 1988Filing dateJun 2, 1987Priority dateOct 3, 1983Fee statusLapsedPublication number057390, 07057390, US 4771474 A, US 4771474A, US-A-4771474, US4771474 A, US4771474AInventorsMasatake Takashima, Shinichiro Fukuda, Hiroyuki ShibataOriginal AssigneeShaken Co., Ltd.Export CitationBiBTeX, EndNote, RefManPatent Citations (7), Referenced by (43), Classifications (6), Legal Events (6) External Links: USPTO, USPTO Assignment, EspacenetApparatus for processing character or pictorial image dataUS 4771474 AAbstract An apparatus for processing character or pictorial image or the like for splitting the outline of a character, which is developed on x- and y-coordinates, into a plurality of blocks [P1, Pn ] (where P1 and Pn are a start point and an end point of an arbitrary block respectively) each defined by a univalent function involving x as a variable, then producing block data to specify the shape of each block, and storing a set of such block data as the compressed data of one character to accomplish compression of the data.
What is claimed is: 1. An apparatus for processing character or pictorial image data comprising:(a) a vector computing means for obtaining length of a vector Vi having a start point Pi and an end point Pi+1 on any outline points among a plurality of outline points Qj constituting a character image outline and deviation between said vector and said outline points, and further obtaining said vector Vi which is so established as to become maximum in length li while said deviation is maintained to be less than a given allowable value, (b) a first comparing means for comparing said length li of said vector Vi with a preset length L, (c) a second comparing means for comparing an intersection angle θi between said vector Vi and a vector Vi-1 adjacent to said vector Vi with a preset angle θ, (d) a discriminating means for identifying an outline segment [Pi, Pi+1 ] approximated by said vector Vi with a straight portion when the result of said comparison by said first comparing means is li >L, further identifying said outline segment [Pi, Pi+1 ] with a curved portion when the result of said comparison is li ≦L, then repeating said comparison with respect to the next vector when the result of said comparison by said second comparing means is θi ≧θ, and further for identifying the preceding outline segments [Pi, Pi+k ] with a single continuous curved portion upon change of the result to li+k >L or θi+k <θ with respect to a vector Vi+k, (e) a third comparing means for establishing a sampling segment in the outline segments [Pi, Pi+k ] of said curved portion, selecting the outline start point Qj as a first sampling point, then establishing a sampling candidate segment [Qj, Qj+r ] while selecting an arbitrary outline point Qj+r on said outline as a sampling point candidate, subsequently computing a cubic polynomial f(x) to approximate said sampling candidate segment [Qj, Qj+r ] with a curved line on the basis of the coordinates (xj, yj) and (xj+r, yj+r) of said sampling point Qj and said sampling point candidate Qj+r and also the inclinations tj and tj+r thereof, and comparing the deviation ε between the cubic polynomial f(x) and each of said outline points on said sampling candidate segment, with an allowable error Δ, (f) a sampling segment establishing means for shifting a present sampling point candidate on the basis of said comparison results, then similarly comparing the deviation ε with the allowable error Δ with respect to the newly selected sampling candidate segment, establishing the sampling point candidate as the next sampling point in case that said comparison results meets ε≦Δ with respect to all outline points and that said sampling candidate segment becomes maximum, and thereafter establishing sampling segments sequentially over the entire outline segments [Pi, Pi+k ] which are identified with said signle continuous curved portion by making said newly established sampling point as a start point of the next sampling candidate segment, and (g) a memory means for storing the start point coodinates of the straight portion, and the start point coordinates of each sampling segment established on the curved portion, and the coefficient and the degree of said cubic polynomial which approximates each sampling segment. 2. An apparatus as claimed in claim 1 wherein the inclinations of said outline points are obtained on the basis of a mean value of inclination of each line segment connecting the outline points on the outline segments [Pi Pi+k ] of said curved portion to the given outline points which are located before and behind said outline points, obtaining a plurality of cubic polynomials f(x) which approximate each section of said outline segments on the basis of said obtained inclinations of the outline points and coordinates of said outline points, obtained in advance the inclination t of all the outline points on said outline segments on the basis of a linear derived functions f'(x) of said cubic polynomials f(x), and obtaining cubic polynomials f(x) which approximate said sampling candidate segments [Qj, Qj+r ] by using said obtained inclinations of said outline points.
3. An apparatus as claimed in claim 1, wherein the computation of said deviation ε is executed as ##EQU4## (in which m is the inclination of a straight line passing through the start and end points of a sampling candidate segment; and εx and εy are deviations between the outline point and the approximate curve in the x- and y-directions, respectively).
4. An apparatus as claimed in claim 1, wherein the outline point Qj+r+1 adjacent to the present sampling point candidate segments [Qj, Qj+r ] is rendered a new sampling point candidate, the deviation ε is similarly compared with the allowable error Δ with reference to a renewed sampling candidate segment [Qj, Qj+r+1 ], said sampling point candidate is shifted in turn until any of the comparison results becomes ε>Δ and the comparison is repeated, and the sampling point candidate Qj+r-p is established as the next sampling point when all the outline points in the sampling candidate segments [Qj, Qj+r-p ] have been ε≦Δ.
CROSS REFERENCE TO OTHER APPLICATION This application is a continuation-in-part of application Ser. No. 569,959, filed Jan. 11, 1984, now abandoned.
This invention relates to an apparatus for processing the data of a character, pictorial image or the like (hereinafter called "character"), the apparatus storing the outline shape of the character so as to compress the amount of stored data. In particular, this invention provides an apparatus for classifying the outline of the character into straight lines and curved lines and further shifting a sampling point candidate on the curved portion in trial and error. It is determined based on deviation ε obtained every outline point within a sampling candidate segment, whether the above trial and error is effected and in which direction the sampling point candidate is advanced or retraced. Then the curved portion is split into a plurality of sampling segments with establishing the sampling segments in turn from the start point of the curved portion, and thereby the straight portion and each sampling segment being stored.
In such prior methods mentioned above, however, there exists an essential disadvantage that an optimal result is not guaranteed with regard to the smoothness of the outline (continuity in inclination of the outline), as is obvious from the example of FIG. 1 where the start points and end points P of the individual vectors are rendered discontinuous, and also from another example of FIG. 2 where the inclination angles δ of the left and right tangential lines on the two sides of each break point Pc of the n-degree curves 3 are rendered discontinuous.
SUMMARY OF THE INVENTION It is an object of the present invention to provide a novel data processing apparatus based on an improved mode of outline reproduction.
BRIEF DESCRIPTION OF THE DRAWINGS FIGS. 1 and 2 are diagrams for explaining the conventional outline method;
PREFERRED EMBODIMENT OF THE INVENTION At first, the summarized operation of the apparatus according to this invention will be described with reference to the flow chart shown in FIG. 3.
In FIG. 4, reference numeral 41 depicts a memory means which stores the position of an outline point Qj of a character image, 42 shows a vector computing means which obtains length of a vector Vi having a start point Pi and an end point Pi+1 on any points among a plurality of outline points Qj constituting a character image outline, and deviation between the vector and the outline points, and further obtaining the vector Vi which is so established as to become maximum in length li while the deviation is maintained to be less than a given allowable value, 43 illustrates a comparator which compares the length li of the vector Vi with a preset length L, 44 indicates a comparator which compares an intersection angle θi of the vector Vi and a vector Vi-1 adjacent to the vector Vi with a preset angle θ, 45 shows a discriminating means which identifies an outline segment [Pi, Pi+1 ] approximated with the vector Vi with a straight portion when the result of the comparison is li >L, further identifying the outline segment [Pi, Pi+1 ] with a curved portion when the result of the comparison is li ≦L, then repeating said comparison with respect to the next vector upon θi ≧θ, and identifying the preceding outline segments [Pi, Pi+k ] with a single continuous curved portion upon change of the result to li+k >L or θi+k <θ with a vector Vi+k, 46 depicts a curve approximating means which establishes a sampling segment in the outline segments [Pi, Pi+k ] of the curved portion, selecting the outline start point Qj as a first sampling point, then establishing a sampling candidate segment [Qj, Qj+r ] while selecting an arbitrary outline point Qj+r on said outline as a sampling point candidate, subsequently computing an cubic polynomial f(x) to approximate said sampling candidate segment [Qj, Qj+r ] with a curved line on the basis of the coordinates (xj, yj) and (xj+r, yj+r) of the sampling point Qj and the sampling point candidate Qj+r and also the inclinations tj and tj+r thereof, 47 indicates a deviation computing means which obtains the deviation ε between the cubic polynomial f(x) and each of the outline points on said sampling candidate segment, 48 illustrates a comparator which compares the obtained deviation ε with an allowable error Δ, 49 depicts a sampling segment establishing means which shifts a preset sampling point candidate on the basis of the comparison result, then similarly comparing the deviation ε with the allowable error Δ with respect to the newly selected sampling candidate segment, establishing the sampling point candidate as the next sampling point in case that the comparison result meets ε≦Δ with respect to all outline points and that the sampling candidate segment becomes maximum, and thereafter establishing sampling segments sequentially over the entire outline segments [Pi, Pi+k ] which are identified with said continuous curved portion by making said newly established sampling point as a start point of the next sampling candidate segment; and 50 shows a memory which stores the start point coordinates of the straight portion, and the start point coordinates of each sampling segment established on the curved portion, and the coefficient and the degree of said cubic polynomial which approximates each sampling segment.
[Image input 30] A character or pictorial image is resolved into x-y matrix dots through raster scanning by means of a scanner or the like, and bit pattern data acquired therefrom is fed as character data to be processed.
[Outline extraction 31] There are obtained dot positions (outline points Q) where the binary data corresponding to the resolved character data change from "0" to "1" or from "1" to "0" in the x- or y-direction. The obtained positions of the outline points are stored in the outline point memory 41.
FIG. 6 shows the character outline shown in FIG. 5, in which portions parallel to Y axis are excluded. In FIG. 6, the marks "0" show the start and end points of each outline and the space defined by the marks is an excluded portion. It is obvious from this figure that the value of x axis of coordinates merely increases or decreases. Namely it is a univalent function (y) involving x as a variable. Thus the outline of FIG. 6 can be obtained by continuously obtaining the segments (blocks B1, B2, B3 . . . ) in which the x-coordinate values of the outline increase or decrease monotonously in respect to the outlines of FIG. 5.
[Straight line approximation 32] In the vector computing means 42 in FIG. 4, straight line approximation is performed with a multiplicity of vectors Vi so established that the deviation thereof from the outline is maintained to be smaller than a predetermined allowable error and the length li becomes maximal.
For example, FIG. 7 shows an exemplary straight line approximation executed for an outline 51, which is represented by a dotted line, in a block [Pi, Pn ] with a set of vectors Vi (where i=1 to n-1). The coordinates (xj, yj) of outline point Qj (where j=1 to m) corresponding to break point Pi (where i=1 to n) of the vectors Vi are stored in a break point coordinate storing part 60 shown in FIG. 8.
[Discrimination between straight portion and curved portion of outline 33] As mentioned already, the outline of a character generally has both straight portions and curved portions. In U.S. Pat. No. 4,542,412; Fuse filed by the present applicant, due to the attempt for approximating the entire outline of one block at a time, a large number of sampling points need to be established in the vicinity of break points in any region where straight portions and curved portions are mutually joined, and further division into many approximate expressions is necessary, so that the quantity of data in this region comes to increase as a result to bring about a disadvantage of reduction in the compression rate.
In view of the circumstances described above, the present invention has been contrived in order to eliminate such problems by first discriminating between the straight portion and the curved portion of the vector-approximated outline segment in accordance with the lengths li of the respective vectors obtained by the aforesaid straight line approximation, and then processing the straight portion and the curved portion individually, hence achieving a satisfactory image even when the character has a complicated outline.
FIG. 8 is a block diagram of an exemplary constitution designed to implement the discrimination between a straight portion and a curved portion of a character outline, and FIG. 9 is a diagram detailedly showing a main portion of the operating process in the construction in FIG. 8. These figures show ones corresponding to the vector computing means 42, comparators 43, 44 and discriminating means 45 as shown in FIG. 4. In FIG. 8, there are shown a break point coordinate storing part 60 for storing the break points of each block obtained by the straight line approximation (32); a straight-portion threshold vector length establishing part 61 for previously establishing a threshold length L to discriminate a vector; a curve split point threshold angle establishing part 62 for previously establishing a threshold angle θ to discriminate a curve splitting point; a next break point coordinate register 63 for holding the coordinates of an (i+1)th break point Pi+1, i.e. the coordinates (xj+s, yj+s) of an outline point Qj+s corresponding to the break point Pi+1 ; a present break point coordinate register 64 for holding the coordinates (xj, yj) of an outline point Qj corresponding to an i-th break point Pi ; a preceding break point coordinate register 65 for holding the coordinates (xj-u, yj-u ) of an outline point Qj-u corresponding to an (i-1)th break point Pi-1 ; a vector length computing part 66 for computing the length li of a vector Vi from the respective coordinates held in the next break point coordinate register 63 and the present break point coordinate register 64; an inter-vector angle computing part 67 for computing the inter-vector angle θi at the break point Pi from the respective coordinates held in the registers 63, 64 and 65; a vector length comparing part 68 for comparing the vector length L established by the part 61 with the vector length li computed by the part 66; an angle comparing part 69 for comparing the curve split point threshold angle θ established by the part 62 with the inter-vector angle θi computed by the part 67; a straight line portion storing part 70 for storing a straight segment in accordance with the result of comparison performed by the vector length comparing part 68; and a curve portion storing part 71 for storing a curved segment in accordance with the results of comparison performed by the vector length comparing part 68, or by the vector length comparing part 68 and the angle comparing part 69.
In the above embodiment, the operation is performed in the following manner. First, a vector length L and an angle θ are established respectively in the straight-portion threshold vector length establishing part 61 and the curve split point threshold angle establishing part 62. Subsequently, the coordinates of start point Pi of one block [Pi, Pn ] are transferred from the break point coordinate storing part 60 to the next break point coordinate register 63. In this stage, since no coordinate data is stored in the present break point coordinate register 64, it is impossible to obtain the vector length in the computing part 66 which will be described later. Then the break point coordinates stored in the next break point coordinate register 63 are shifted to the present break point coordinate register 64, and the coordinates of a next break point P2 are newly stored in the register 63. Thereafter, the coordinates stored in the present break point coordinate register 64 are shifted to and stored in the preceding break point coordinate register 65, and the coordinates stored in the next break point coordinate register 63 are shifted to and stored in the present break point coordinate register 64. And subsequently the next break point coordinates obtained from the break point coordinate storing part 60 are stored in the register 63.
The vector length computing part 66 computes a vector length li =√(xj+s -xj)2+(yj+s -yj)2 from the coordinates (xj+s, yj+s) of the (i+1)th break point Pi+1 in the next break point coordinate register 63 and the coordinates (xj, yj) of the i-th break point Pi in the present break point coordinate register 64. The vector length li thus computed is compared by the vector length comparing part 68 with the vector length L previously established by the straight-portion threshold vector length establishing part 61. And when li >L, the outline segment [Pi, Pi+1 ] approximated by the said vector Vi is recognized as a straight portion, and the coordinates of the start and end points thereof are stored in the straight line storing part 70 as the information relative to one straight portion.
In the case of li ≦L, the outline segment (Pi, Pi+1 ] is recognized as a curved portion and, after the coordinates of start and end points of the segment [Pi, Pi+1 ] are stored in the curve storing part 71 as the information relative to the curved portion, the next segment [Pi+1, Pi+2 ] is discriminated. And if this segment [Pi+1, Pi+2 ] is also a curved portion, the segments [Pi, Pi+2 ] recognized heretofore as curved portions are joined together to form a single continuous curved portion, and the coordinates of its start and end points are stored in the curve storing part 71 as the information relative to one curved portion.
The foregoing comparison is repeatedly executed until the next outline segment is recognized as a straight portion and, when the result of such comparison is changed to li+k >L with a vector Vi+k the coordinates of start and end points corresponding to the preceding outline segments [Pi, Pi+k ] and stored already in the curve storing part 71 are fixed as the information relative to one curved portion.
As mentioned hereinabove, when the information representing one straight portion or one curved portion is obtained, the foregoing recognition is repeatedly executed with respect to the successive vectors, and the data of the straight and curved portions constituting the arbitrary block (Pi, Pn ] are held respectively in the storing parts 70 and 71. And thereafter discrimination is further executed with regard to the entire blocks that constitute one character.
[Outline splitting 34] Meanwhile, in the inter-vector angle computing part 67, the respective coordinates (xj-u, yj-u), (xj, yj) and (xj+s, yj+s) of the break points Pi-1, Pi and Pi+1 are read out from the next break point coordinate register 63, the present break point coordinate register 64 and the preceding break point coordinate register 65, and subsequently the inter-vector angle θi (intersection angle of vectors Vi and Vi-1 adjacent to each other) shown in FIG. 7 is computed. The angle θi thus obtained is compared by the angle comparing part 69 with the curve split point threshold angle θ established previously in the part 62. And when the result of such comparison is θi <θ, a curve split signal is fed from the angle comparing part 69 to the curve storing part 71.
In another case where the instruction is so prepared as to operate the curve storing part 71 in response to a curve split signal, if curved portions are recognized in succession from a vector Vi and the result of comparison is changed to θi+k <θ with a vector Vi+k, the curve split signal is fed to the curve storing part 71. Then a break point Pi+k is newly recognized as a curve split point by the curve storing part 71, and the coordinates of start and end points corresponding to the preceding outline segment [Pi, Pi+k ] and stored already in the curve storing part 71 are fixed as the information relative to one curved portion.
In the figure, a mark " " denotes a start point and an end point of each block; a mark " " denotes a break point obtained by descrimination between straight line and curved line; and a mark " " denotes a curve split point. A straight portion is marked with , while a curved portion is not marked with any symbol. Two curve splitting points as shown in the figure are established since the intersection angle θn is less than the given discrimination angle θ.
[Computation of inclinations at outline points 35] In approximating the outline shape of the computed curved portion by means of cubic polynomials, the expressions are determined definitely when the coordinates of two points and the inclinations thereat are specified. In this case, therefore, it is necessary first to obtain the inclination at each outline point on the outline.
First, in the case of computing an inclination t1 at an outline point Q1 (start point of curved portion) in FIG. 11(a), an arbitrary number of outline points existent posterior to the outline point Q1 are extracted, then the respective inclinations of the line portions between the outline point Q1 and the other outline points are computed, and the inclination t1 at the outline point Q1 is computed on the basis of the respective inclinations of the line segments by the expressions which will be described later.
In an exemplary case of finding the inclination with extraction of two outline points posterior to the outline point Q1 whose inclination is to be obtained, first the inclination m12 of a line portion Q1 Q2 and the inclination m13 of a line portion Q1 Q3 are computed. The line portion inclination m12 can be obtained from the coordinates (x1, y1) and (x2, y2) of the two points as
m12 =(y2 -y1)/(x2 -x1)
Meanwhile, the inclination m13 is also obtainable in the same manner.
On the basis of the line portion inclinations m12 and m13, the inclination t1 at the outline point Q1 is determined by the equation:
t1 =tan{(tan-1 m12 +tan-1 m13)/2}
Now a description will be given on an exemplary case of computing an inclination t2 at the next outline point Q2 with reference to FIG. 11(b).
In this case, a predetermined number of outline points existing anterior and posterior to the point Q2 are extracted, then the respective inclinations of the line segments between the outline point Q2 and the individual extracted points are computed, and the inclination t2 at the outline point Q2 is obtained therefrom.
For example, in the case of finding the inclination with extraction of two points relative to the desired outline point, merely a single point Q1 can be extracted on the side anterior to outline point Q2. Therefore, one anterior point and one posterior point are extracted with respect to the outline point Q2, and the inclination t2 is determined by the following equation:
t2 =tan{(tan-1 m12 +tan-1 m23)/2}
In the next case of computing an inclination t3 at an outline point Q3 as shown in FIG. 11(c), the designated number of outline points are existent posterior and anterior to the point Q3. Therefore, the inclinations m13, m23, m34 and m35 of the line segments between the outline point Q3 and the other outline points are computed, and the inclination t3 at the outline point Q3 is determined by the following equation:
t3 =tan{(tan-1 m13 +tan-1 m23 +tan-1 m34 +tan-1 m35)/4}
Thereafter the inclination at each outline point is computed by the same procedure as the above, wherein the inclination tn at the end point Qn of the curved portion is computed similarly as in the case of obtaining the inclination at the start point Q1 shown in FIG. 11(a), or the inclination tn-1 at the outline point Qn-1 adjacent the point Qn is computed similarly as in the case of obtaining the inclination at the outline point Q2 adjacent the point Q1 shown in FIG. 11(b).
[Determination of sampling points 36] As described above, there is obtained the inclination at each of the outline points constituting the curved portion so that a sampling segment is established on the outline corresponding to the curved portion. The establishment of the sampling segment is performed by means of a curve approximating means 46, deviation computing means 47, comparator 48 and sampling segment establishing means 49. FIG. 12 is a diagram showing this operating process.
At first, two outline points Qj, Qj+r are selected in turn by way of the following process to establish a sampling segment. (refer to FIG. 13)
In the following description, the anterior outline point Qj is termed a sampling point while the posterior outline point Qj+r is termed a sampling point candidate. And the segment defined by such two points forming a start point and an end point respectively is termed a sampling candidate segment [Qj, Qj+r ].
The sampling point Qj is established under the initial condition at the start point of the curved portion, while the sampling point candidate Qj+r is established at a position spaced apart from the sampling point Qj by a distance corresponding to the number r of outline points.
First, the coefficients and degrees of a cubic polynomial f(x) passing through the two points are computed on the basis of the coordinates (xj, yj), (xj+r, yj+r) and inclinations tj, tj+r of the sampling point Qj and the sampling point candidate Qj+r, and comparison is executed to find whether each of the deviation ε between the entire outline points existent in the sampling candidate segment [Qj, Qj+r ] and the approximate curve obtained by the aforesaid cubic polynomial is smaller than a predetermined allowable error Δ, whereby the said approximate curve is judged to be proper or not.
Supposing now that the result of comparison is ε≦Δ at every outline point in the sampling candidate segment [Qj, Qj+r ], the approximate curve obtained is judged to be allowable.
With respect to the sampling candidate segment [Qj, Qj+r ] determined by using the initially established outline point Qj+r as a sampling point candidate, each deviation ε between the approximate curve obtained as mentioned above and each of the outline points in the sampling candidate segment [Qj, Qj+r ] is computed and then compared with the allowable error Δ, and when every result of such comparison is ε≦Δ, further comparison is executed while the outline point Qj+r+1 adjacent to the present sampling point candidate Qj+r is selected as a new sampling point candidate. Thereafter, with sequential renewal of the sampling point candidate, the comparison is repeated until at least one result thereof becomes ε>Δ. And when at least one result has become ε>Δ at an outline point Qj+r+p, an outline point Qj+r+p-1 immediately anterior thereto is set as a second sampling point to establish a sampling segment [Qj, Qj+r+p-1 ], and an approximate curve in this sampling segment [Qj, Qj+r+p-1 ] is determined to be one of approximate curves needed to represent the given outline.
Meanwhile, with respect to the sampling candidate segment [Qj, Qj+r ] determined by using the initially established outline point Qj+r as a sampling point candidate, a deviation ε between the approximate curve obtained as mentioned above and each of the outline points in the sampling candidate segment [Qj, Qj+r ] is computed and then compared with the allowable error Δ, and when at least one result of such comparison is ε>Δ further comparison is executed while the outline point Qj+r-1 adjacent to the present sampling point candidate Qj+r is selected as a new sampling point candidate. Thereafter, with sequential renewal of the sampling point candidate, the comparison is repeated until every result thereof becomes ε≦Δ. And when every result has become ε≦Δ at an outline point Qj+r-p, the sampling point candidate Qj+r-p is selected as a second sampling point to establish a sampling segment [Qj, Qj+r-p ], and an approximate curve in the sampling segment [Qj, Qj+r-p ] is determined to be one of approximate curves needed to represent the given outline.
The processing mentioned above determines that a sampling segment is the longest where the deviation ε is within the limit of an allowable error Δ, and thus the entire outline is divided into sampling segments. And the outline is approximated according to cubic polynomials by such sampling segments.
In FIG. 13(a), there are shown an outline 90, an outline point B on the outline 90, an approximate curve 91 of a cubic polynomial f(x), a straight line 92 between a start point Qj and an end point Qj+r of a sampling candidate segment [Qj, Qj+r ], a perpendicular 93 extending from the point B to the straight line 92, an intersection C of an approximate curve 91 and the perpendicular 93, a deviation εx designated by BA in the x-direction between the outline 90 and the approximate curve 91, a deviation ε designated by BC between the outline 90 and the approximate curve 91, and a deviation εy designated by BD in the y-direction between the outline 90 and the approximate curve 91.
Inclinations tj and tj+r of the start point Qj and the sampling point candidate Qj+r and also coordinate values (xj, yj) and (xj+r, yj+r) previously computed are introduced into the following third-degree equation. ##EQU1##
Subsequently to determination of the approximate curve in the manner mentioned, a deviation ε between the approximate curve and each outline point is computed.
FIG. 13(b) is an enlarged view of the deviation ε between the outline 90 and the approximate curve 91 shown in FIG. 13(a). Supposing now that a line segment CA is parallel with a straight line 92, the inclination of the straight line 92 is considered to be equal to the inclination m of the line portion CA.
And when |m|>1 as shown, the deviation εx in the x-direction between the point B and the approximate curve 91 is computed, so that the desired deviation ε can be obtained as ##EQU2##
Although not shown, when |m|≦1, the desired deviation ε can be obtained similarly as ##EQU3##
In the exemplary case mentioned above, the process is so carried out that when the deviation ε has exceeded the allowable error within the next sampling candidate segment [Qj, Qj+r+p ], the sampling point candidate Qj+r+p-1 immediately anterior thereto is selected as an established sampling point to determine a sampling segment.
However, a modified procedure may be executed in such a manner that, when the deviation has exceeded the allowable error, the sampling point candidate Qj+r+p at the moment is stored temporarily, and the deviation ε is further appreciated with respect to a sampling candidate segment after several points. And when the allowable error condition is satisfied in the sampling candidate segment after several sampling point candidates, this segment is established correctively as a new sampling segment, and the aforementioned appreciation is executed repeatedly while advancing the sampling point therefrom. Due to such preliminary recognition in advance, it becomes possible to further lengthen the sampling segment, thereby increasing the data compression rate eventually.
It is a matter of course that if the deviation still exceeds the allowable error even after a predetermined number of points, a sampling segment is established with the aforesaid Qj+r+p-1 selected as a sampling point. [Recomputation of inclinations at outline points 37]
[Redetermination of sampling points 38] In case the inclination at each outline point is computed again in [Recomputation of inclinations at outline points 37] mentioned above, the same processing as in [Determination of sampling points 36] is executed by using such recomputed inclination at each outline point, and sampling segments are determined while establishing the sampling points again. The sampling segment thus redetermined is approximated according to a third-degree polynomial f(x) which is more faithful to the outline. Since the number of sampling segments is further reducible, the data compression rate can be raised as a result.
In the case of a simple character, its outline can be faithfully approximated so that the above procedures are not necessary. FIG. 14 shows an example that the outline of FIG. 10 is processed by determination of sampling points (36) to redetermination of sampling points (38). In FIG. 14, marks " " shows start and end point, respectively, a break point, a curved line splitting point, a straight line portion, no-mark a curved portion and Δ a sample point newly established.
[Encoding 39] and [Storage of compressed data 40] Each straight portion stored at the straight line storing part 70 is regarded as a sampling segment and the coordinate of a start point is coded.
As a result of experimentally applying the above-described character data processing apparatus of this invention to a Japanese Ming-style hiragana character " " composed of 800�800 dots, it has been verified that a data compression rate of 1.21% is attainable with one dot determined as an allowable error to a desired character image.
Patent CitationsCited PatentFiling datePublication dateApplicantTitleUS3699318 *Aug 19, 1970Oct 17, 1972Leeds & Northrup CoIncremental slope method for optimum continuous digital linearizationUS4254468 *May 3, 1979Mar 3, 1981Eltra CorporationTypesetter character generating apparatusUS4298945 *May 3, 1979Nov 3, 1981Eltra CorporationCharacter generating method and apparatusUS4338673 *Aug 27, 1980Jul 6, 1982Compugraphic CorporationPhototypesetting system and methodUS4513444 *Jul 18, 1983Apr 23, 1985Dainippon Screen Seizo Kabushiki KaishaMethod of compressing dataUS4524456 *Nov 10, 1982Jun 18, 1985Dainippon Screen Seizo Kabushiki KaishaMethod for compressing data of two-value picture imageUS4542412 *Feb 1, 1983Sep 17, 1985Shaken Co., Ltd.Method for compressing character or pictorial image data* Cited by examinerReferenced byCiting PatentFiling datePublication dateApplicantTitleUS4912664 *Feb 1, 1988Mar 27, 1990Mentor Graphics CorporationMethod and apparatus for generating a mesh for finite element analysisUS5036544 *Mar 10, 1989Jul 30, 1991Mitsubishi Kenki Kabushiki KaishaApparatus for discriminating linearity of line segment in image processing systemUS5073956 *Oct 23, 1989Dec 17, 1991Brother Kogyo Kabushiki KaishaApparatus for converting image outline data into dot data representative of dots to be formedUS5081689 *Mar 27, 1989Jan 14, 1992Hughes Aircraft CompanyApparatus and method for extracting edges and linesUS5091976 *Feb 14, 1990Feb 25, 1992Ricoh Company, Ltd.Image coding method for extracting, segmenting, and coding image contoursUS5113453 *May 14, 1990May 12, 1992L'etat Francais Represente Par Le Ministre Des Postes Et Telecommunications Centre National D'etudes Des TelecommunicationsCharacter recognition method and apparatusUS5127063 *Sep 20, 1989Jun 30, 1992Hitachi, Ltd.Processor for pattern data, measured process information, and image informationUS5150431 *Jan 23, 1991Sep 22, 1992Brother Kogyo Kabushiki KaishaDevice for converting normal outline data into compressed outline data, or vice versaUS5165072 *Apr 26, 1991Nov 17, 1992Canon Kabushiki KaishaImage processing apparatus which detects a line imageUS5214718 *Oct 19, 1992May 25, 1993Ampex Systems CorporationScan-in polygonal extraction of video imagesUS5231676 *Jun 8, 1990Jul 27, 1993Xerox CorporationHierarchical operations on border attribute data for image regionsUS5233671 *Sep 12, 1991Aug 3, 1993Ricoh Company Ltd.Image coding method for coding characters using a modified Bezier curveUS5339367 *Dec 2, 1992Aug 16, 1994National Research Council Of CanadaIdentifying curves within a scanned imageUS5469513 *Sep 1, 1994Nov 21, 1995Canon Kabushiki KaishaMethod and apparatus for generating patternUS5572605 *Sep 1, 1993Nov 5, 1996Toraichi; KazuoApparatus and method for inputting, compressing and outputting characters, illustrations, drawings and logomarksUS5583955 *Dec 28, 1993Dec 10, 1996Canon Kabushiki KaishaImage processing apparatusUS5590220 *Aug 12, 1992Dec 31, 1996International Business Machines CorporationBending point extraction method for optical character recognition systemUS5596658 *Jun 1, 1993Jan 21, 1997Lucent Technologies Inc.Method for data compressionUS5644654 *Feb 13, 1995Jul 1, 1997Canon Kabushiki KaishaImage processing apparatus capable of efficient coding of complex shape informationUS5668894 *Jul 22, 1994Sep 16, 1997Matsushita Electric Industrial Co., Ltd.Method for processing three-dimensional shape dataUS5696844 *May 26, 1994Dec 9, 1997Matsushita Electric Industrial Co., Ltd.Outline pattern data extraction device for extracting outline pattern of a pattern distribution in a multi-dimensional feature vector space and its applicationsUS5719959 *May 9, 1995Feb 17, 1998Canon Inc.Computer-implemented processUS5818963 *Nov 4, 1996Oct 6, 1998Murdock; MichaelMethod and system for recognizing a boundary between characters in handwritten textUS5841906 *Nov 21, 1997Nov 24, 1998Nec CorporationGraphic form recognition apparatusUS6032106 *Sep 9, 1997Feb 29, 2000Ishii; MasaharuApparatus and method for selecting parameters corresponding to physical characteristicsUS6048116 *Apr 13, 1992Apr 11, 2000Canon Kabushiki KaishaMethod and apparatus for drawing characters for display in a draft mode and a high resolution modeUS6101280 *Jan 3, 1997Aug 8, 2000Hewlett-Packard CompanyMethod and apparatus for compression of electronic inkUS6285788 *May 27, 1998Sep 4, 2001Sharp Laboratories Of America, Inc.Method for fast return of abstracted images from a digital image databaseUS6304677 *Apr 7, 1998Oct 16, 2001Adobe Systems IncorporatedSmoothing and fitting point sequencesUS6314197 *Feb 25, 1998Nov 6, 2001International Business Machines CorporationDetermining an alignment estimation between two (fingerprint) imagesUS6925207Mar 23, 2000Aug 2, 2005Sharp Laboratories Of America, Inc.Method for fast return of abstracted images from a digital images databaseUS8085266 *Apr 19, 2005Dec 27, 2011Jostens, Inc.System and method for smoothing three dimensional imagesUS8285791Oct 23, 2009Oct 9, 2012Wireless Recognition Technologies LlcMethod and apparatus for sharing information using a handheld deviceUS8300946 *May 14, 2007Oct 30, 2012Canon Kabushiki KaishaImage processing apparatus, image processing method, and computer programUS8384917 *Feb 15, 2010Feb 26, 2013International Business Machines CorporationFont reproduction in electronic documentsUS8473088Dec 2, 2010Jun 25, 2013Jostens, Inc.System and method for generating instructions for customizationUS8515713Jan 19, 2012Aug 20, 2013Jostens, Inc.System and method for embellishment placementUS20110199627 *Feb 15, 2010Aug 18, 2011International Business Machines CorporationFont reproduction in electronic documentsUSRE44696Sep 20, 2011Jan 7, 2014Jostens, Inc.Automated engraving of a customized jewelry itemCN1096657C *Jul 22, 1994Dec 18, 2002松下电器产业株式会社Three dimentional shaped data processing methodDE4444583A1 *Dec 14, 1994Jun 22, 1995Masaharu IshiiSelecting physical characteristic from parameter data for digital filterDE4444583B4 *Dec 14, 1994Sep 30, 2004Masaharu Nagoya IshiiApproximationsvorrichtung und Approximationsverfahren zum Bestimmen eines technischen SystemsWO1989007301A1 *Jan 27, 1989Aug 10, 1989Mentor Graphics CorpGenerating a mesh for finite element analysis* Cited by examinerClassifications U.S. Classification382/241, 358/1.9, 382/242International ClassificationG06T9/20Cooperative ClassificationG06T9/20European ClassificationG06T9/20Legal EventsDateCodeEventDescriptionNov 14, 2000FPExpired due to failure to pay maintenance feeEffective date: 20000913Sep 10, 2000LAPSLapse for failure to pay maintenance feesApr 4, 2000REMIMaintenance fee reminder mailedMar 11, 1996FPAYFee paymentYear of fee payment: 8Mar 9, 1992FPAYFee paymentYear of fee payment: 4Jun 10, 1988ASAssignmentOwner name: SHAKEN CO., LTD., 26-13, MINAMIOTSUKA 2-CHOME, TOSFree format text: ASSIGNMENT OF ASSIGNORS INTEREST.;ASSIGNORS:TAKASHIMA, MASATAKE;FUKUDA, SHINICHIRO;SHIBATA, HIROYUKI;REEL/FRAME:004886/0599Effective date: 19880519Owner name: SHAKEN CO., LTD., A CORP. OF JAPAN,JAPANFree format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:TAKASHIMA, MASATAKE;FUKUDA, SHINICHIRO;SHIBATA, HIROYUKI;REEL/FRAME:004886/0599RotateOriginal ImageGoogle Home - Sitemap - USPTO Bulk Downloads - Privacy Policy - Terms of Service - About Google Patents - Send FeedbackData provided by IFI CLAIMS Patent Services©2012 Google