A Method of Generating Calligraphy of Japanese Character using Deformable Contourse

1 Introduction

Writing style varies from person to person. Inherently, imitating and generating diverse calligraphy of a charac­ ter automatically with a computer is always demanded. However, because of the shape variety of the strokes making up a character and the complexity of the shape deformation, it is usually difficult to capture the inner re­ lationship between different writing style by simple rules. Therefore, to cope with the situation, currently two mea­ sures are mainly adopted for calligraphy generation: one is preserving some different fonts in advance, and giv­ ing out a type of writing among them opportunely, as used in almost all editor or printing tool, and the other one is using some manually defined regulations based on some experience, as applied in many calligraphy systems (Nakamura et al., 1994, 1995, Zhang et al:, 1993.]

Obviously, the first method lacks flexibility, the num­ ber of type of calligraphy generated is font-limited, and enormous computer resources are required with the in­ crease of amounts of the font . The second one lacks gen­ erality, it is based on trial-and-error, fine result can be obtained from it without special knowledge about callig­ raphy. The problem of generating different calligraphys from limited existing fonts with human intervention as little as possible is left.

More formally, our problem may be formulated as follows: Given two sample calligraphys Co, C1 and t E [0, 1], construct versatile intermediate object C~, together with the increasing of t, where, C1 is a more violent deformation in resembling tendency from Co to C1· In a way, this is a multidimensional shape interpo­ lation problem, and, as such, is ill-posed, in the sense that there are many possible interpolants C1 satisfying this very vague condition.

There are also some research carryed out for the shape interpolation problem [Sederberg et al., 1992]. As a com­ mon consent, the regularization [Poggio et al., 1985] tech­ nique is a powful tool of transforming a ill-posed problem into a well-posed one. By finding some natural condi­ tions which are not explicit in the input it reduces the number of solutions. In this paper, we propose a method for dealing with the problem of generating calligraphy from limited fonts by applying regularization technique.

We apply regularization to our calligraphy generation problem grounded on following argument:

A different calligraphy of a character is a defor­ mation of its stroke contours satisfying energy minimum principle under some external con­ straints.

Some deformable contour models based on the energy minimum principle of regularization have been developed and successfully applied to many aspects of machine vi­ sion. Kass first established a well-known active contour model, the snake model to process low-level vision tasks such as edge detection, boundary formulation and stereo and motion matching [Kass et al., 1988]. To achieve the aim of contour extraction of arbitrary object under noisy image [Lai and Chin, 1995], Lai gives a more in­ novative one, so-called generalized active contour, the g-.make model, based on the stochastic relaxation the­ ory [Geman, 1995]. The common feature of both models is that, for each model, there is a defined internal energy, which is used to keep the initial shape of a contour, and an imaginary external force acted on the contour. The contour is attracted by such actions to a desirable final state, where the sum of internal and external energy of the contour is minimal. Due to the different usage, the external force could be image intensity, edge, termina­ tion etc. An advantage of g-snake is that it is capable of representing any arbitrary shape, not only accounts for global changes due to rigid motions, but also retains the ability for local control.

We argue that to deal with the calligraphy generation problem, we must consider both global and local defor­ mation of a stroke. Accordingly, the g-snake is a fittable contour model for our task. We develop a calligraphy generation method based on g-snake. In our method, we use a pair of existing font data as samples, one is for C0 , another is for C1 , represent each stroke of a sam­ ple by a closed g-snake, investigate global deformation between corresponding strokes, imagine that there are pulling forces acted on Co to make it deform to C1 , and learn the contour deformable control parameter by using the C1 as the final convergence of energy minimization from initial position C0 · Then we can control the genera­ tion of a series of interpolation Ct by varying the learned parameters.

The remaining of this article is arranged as follows: In section 2, we introduce g-snake model, in section 3, we describe the application of g-snake model for our prob­ lem in detail, in section 4 we show some examples of ex­ perimental results and discuss about them, and finally, the conclusion and the future work is summarized in sec­ tion 5.

2 Deformable Contours Model: g-snake

In[Lai and Chin, 1995], the major role of the g-snake model is to deal with an ill-posed problem, extracting contour of any object from an observational image.

2.1 Representing Contour of an Object

The g-snake model represents a contour as a link of point vector, U = .[u1 , u 2 , · · ·, un], where, each u E E = {(x,y): x,y = 1,2,·· ·,M}, thusU E En. Such a point is also called snaxel (snake pixel). Each snaxel u; can be expressed as a linear combination of its two adjacent snaxel vectors:

where the basis indices are given by:

Accordingly, the shape equation of the contour of an object can be written down as:

where A is called shape matrix that contains the nec­ essary information to describe the shape:

A contour U is called nontrivial if lx;BYi p -x;p Yi~ I > 0 for 1 ~ i ~ n. Such shape representation is account for both global and local deformations:

· Global Deformations

Global deformations correspond to rigid motion of contour such as scaling, rotation, stretching and di­ lation. It has been proven in [Lai and Chin, 1995] that the contour representation mentioned above keeps the following invariance property for a con­ tour:

Two nontrivial contours satisfy the same shape equation if and only if they are re­ lated by a linear transformation.

Therefore, according to this invariance property, the global deformation of a contour can be computed simplely by affine transformations without any in­ fluence on the shape matrix.

· Local Deformations

The g-snake models the local deformations as ran­ dom fluctuation of snaxels in a interested family of contours U En 2 En. An internal energy induced by shape matrix A is defined to represent such fluc­ tuation:

where R = diag{ a-?, a-~, · · · , a-~} are the deforma­ tion variances a-r of snaxel i, l(U) is a normali?:ing constant:

Now the probabilities of contour U may be assigned as expression 5 which is so-called Gibb.9 mea.mre:

where Z is also a normalizing constant:

Equivalently, expression 5 also defines the conditional probability of Markov random field to yield prior distri­ butions for any arbitrary contour.

The expression 6 means that a contour U is entirely specified given all probability of u;, while a probability of u; is specified given its two adjacent basis snaxels.

2.2 Maximum Posterior Estimation

The g-snake model treats the contour extraction task as a process to estimate unknown deformation of con­ tour from an image. By using Bayesian framework, it can be realized as maximum posterior(MAP) estimation. Rewriting and denoting the internal and external energy as follows:

where g is an arbitrary reference point, h; is an unit vector indicates the interested deformation direction of a snaxel on the contour, and function f(x) corresponds the external force, which can be edge intensity for exam­ ple, depends on task that pulls the contour to desirable position.

Then contour extraction task turns into solving prob­ lem of MAP estimation, formulated as an energy mini­ mization problem of finding Umap and gmap in expres­ sion 9.

where

are the local regularization parameters which control the amount of local template deformation. u~ is the Gaussian distribution of the noise contained in force measurement.

3 Calligraphy Generation System

The different calligraphy of a character is indeed the de­ formation of its strokes in a lot of styles. Because of the deformation complexity, it is difficult to arrange sim­ ple and plain rules to comprehend deformations of every points make up a stroke. Our basic thinking is to investi­ gate the deformation of several salient feature points on sample calligraphy Co and C1 , assuming the deforma­ tion is owing to some forces coming from C1 and acting on the outline of strokes of C0 , and it will convergence to somewhere where the sum of energy of points is mini­ mum so that we can charge the position determination of remaining points with the energy minimum processing, and hence, to generate versatile calligraphy the defor­ mation of strokes can be simply described as the energy minimum principle. Up to now, we use only Japanese alphabet, the Hiragana, for the calligraphy generation. So we describe our system concentrated on processing of Hiragana.

3.1 Processing Flow

Given two samples C0 , C1, in order to generate varying calligraphys C11 our system proceeds in following stages:

• Pre-process.
• Extract strokes of from input characters.
• Complete the correspondence completion between each stroke of Co and Ct.
• Initialize a g-snake on each stroke.
• Investigate global deformation between correspond­ ing strokes.
• Learn g-snake parameter to control local deforma­ tion.
• Varying the learned parameters to generate new calligraphy.

3.2 Pre-processing

Giving two sample calligraphys C0 , C1 as the input, because they are all binary images, By investigating whether the 8 neighbors of a pixel are all black, we can easily get binary array matrix T0 , T1 , whose elements corresponds to each pixels of Co, C1 , take value of 1 if a boundary pixel or 0 for a non-boundary pixel.

3.3 Stroke Extraction

Since the stroke is the basic processing unit in our sys­ tem, we must decompose sample calligraphy to separate stroke set. In contrast to no extra work just an bound­ ary tracing needs for a Hiragana without intersection, procedure for a intersection one is slight tiresome.

At this time, the processing is semi-automatic, i.e. the salient feature points must be decided manually. Having n feature points clicked near the related stroke of each sample C0 and C1 , a stroke is divided into n segments, then the processing saves their coordinates in two lists Ko = [koo,kot, .. ·,kon] and Kt = [kiO,kn, .. ·,ktn] at first, where, the elements in K0 and K1 with the same subscript are thought as correspondence. We call it a partial correspondence. For example, to extract the first stroke of Hiragana "a", points dotted in Figure 1 have to be clicked.

Following processing is: aligning each points clicked i.e. all elements in K1(l E 0, 1) on their nearest boundary by matching it to T1(l E 0, 1), obtained in pre-processing stage. For each pair kbi,kb(i+l),O :c.:; i < n,b = 0 or 1, using T1(l E 0, 1) to trace and record a route along the boundary of the stroke( for the point last clicked search­ ing a route to the first clicked one), If an intersection is encountered, the program will switch boundary tracing operation to spline interpolation, to fill the interval of boundary due to the intersection. Figure 2 is an exam­ ple of decomposing Hiragana "a" and "u" into strokes.

7

Figure 2: Decomposing calligraphy into strokes

3.4 Correspondence Completion

In this stage, the partial correspondence of feature points will be turned into a full correspondence of snaxels. Can­ didate snaxels to initialize a g-snake are selected from each route between two feature points produced at last stage for each related stroke, and an full correspondence for related stroke of two samples is established. Given a space between the snaxel, the necessary number and coordinates of snaxels for a element in Co to its next one can be calculated except the last one who's com­ ing element is the first element. Then, for an element in C1, assuming the number of snaxel to next element should be the. same as its correspondence element in C0 , the proper adjusted space can be calculated and snaxel can be selected from the route produced for cl in last stage. Finally, a full correspondence is obtained by bind­ ing these selected snaxels orderly.

3.5 G-snake Initialization

To prepare for the deformation, using the snaxels found in the last stage, a closed g-snake is located on the con­ tour of stroke, which contains the necessary shape information. Figure 3 is the example of locating two g-snakes on the first stroke of Hiragana "a" and "u":

3.6 Investigate Global Deformation

In this processing stage, the global deformation of rigid motions such as rotation scale and stretching and dila­ tion arose between sample stroke is investigated. Be­ cause the rotation and the stretching have the strongest visual appeal, we investigate rotation and stretching be­ tween each related stroke of sample C0 and C1· The investigation occurs along the g-snakes in the unit of a pair of partial correspondence segments. Supposing there are m segments on one g-snake, we first put the start snaxel on C1 together with that on Co by transla­ tion, then by comparing their coordinates of start and end snaxel, we can know the necessary stretching and ro­ tation angle for Co to deform to c~. and put them in list Su = (.Y\, 82, · · ·, sm) and Su = (81, 82, · · ·, 8m)· For ex­ ample shown in Figure 4, assuming arc AB and AB' are contour correspondence segments, the global stretching is calculated by comparing the length of line segment AB and AB', and the rotation angle a is the angle between them.

3. 7 G-snake control parameter learning

In our system, the local deformation is simulated as the energy minimization process of closed g-snake on the out­ line of stroke. The function f(u;) describing the external energy in expression 8 is designated as a pulling force acted on snaxel on C0 , with direction points to its corre­ spondence snaxel on cl and the strength in proportion to the normalizing constant l (U) is described in the last section. Therefore, using the correspondence table cre­ ated in previous stage and putting the heads of g-snake on cl together with its corresponding global deformed one on C0 , such directions and strengthes to form a force map is easily generated. Then we use this force map to minimize the total energy for the g-snake, and the local regularization parameters ..\; in expression 9 can be esti­ mated by local minimax criterion[Lai and Chin, 1993].

3.8 Generate new Calligraphy

Having known global deformation parameter Sv, 0v and local regularization parameter ..\;, we can generate a new calligraphy by giving a different control variable t E (0, 1), deform each stroke segment globally using affine transformation under parameters tSv, t0v, and then deform it locally by g-snake energy minimization with regulation parameter t..\;. This control the defor­ mation from weakly to violently.

4 Experiment Results

This section shows some examples of generated callig­ raphy. In order to test the robust of our algorithm, we deliberately selected four kinds of Calligraphy fonts of Japanese "Hiragana" existing in our computer system which are called kaisho, gyosho, mini and gothic. These fonts have clearly different appearance. Calligraphy of such fonts for Hiragana "a" are shown in Figure 5:

Figure 5: Different type of calligraphy

Using a pair of calligraphy fonts of Hiragana "a" as samples, and executing the algorithm described in last section, some generated examples are shown in Figure 6.

In Figure 6, calligraphys of the first row is used as sample Co and last row for C1· This is done to test whether our algorithm is available for sample of any se­ lected type. Therefore, the first column in Figure 6 is an progressively proceeding from kaisho to gyosho, the second column is kaisho to mini, and the third is gothic to mini. After learning global and local deformation pa­ rameters, the calligraphys in second and third row are generated by setting t to 0.3 and 0.6.

Figure 7 gives generated calligraphys for some other Hiragana "i", "u", "e", and "o" of Japanese, the selected generation condition is: from the first row to the fourth row, the control parameter is set to be 0.1, 0.3, 0.6 and 0.9 respectively. We can observe from this picture that the increase of t makes the lose the peculiarity of C0 , simultaneously, get that of C1 .

We also test our method on processing real calligra­ phy. The right down of Figure 8 is a real calligraphy of Hiragana "a" read from a scanner. By using it and existing Hiragana "a" of font "kaisho" (left up of Figure 8) as samples, we can generate intermediate calligraphy, the right up and the left down shown in Figure 8 with t selected as 0.3 and 0.8.

4.1 Discussion

We can know from these figures, that our algorithm do generate the medium states of samples, and the sample calligraphy can be any type of font including the real cal­ ligraphy. The deformation can be controlled by varying the parameter t. The results are similar to calligraphy written by real people. But we have to indicate that something must be improved is also-left over. Some gen­ erated results are not acceptable in an aristic point of view. With the increase of t, the character generated looses the rhythm of the initial character, or it is a non canonical way. Because the final position of snaxel is de­ cided with the energy minimum and due to the control difficulty of this processing, some strokes of the gener­ ated character are locally blurred. We want to overcome these shortcomings in our next system version.

5 Conclusion

We demonstrate the problem of generating various callig­ raphy of Japanese character from different fonts can be modeled as global and local deformation of its stroke con­ tour obeying the energy minimization principle of regu­ larization technique. Therefore, we apply the deformable contour model g-snake solving the calligraphy generation problem. Such a method makes the generation more flex­ ible and the generated results are more natural. Some useful left work can be indicated as: extracting strokes of a character automatically, modeling the force or pressure applied on the brush and the dynamic of writing kana or kanji, interpolating writing scratch between strokes, i.e the semicursive style of writing, and the extension of the existing system to calligraph processing of Chinese characters. ·