Extraction of Embedded Class Information from Universal Character Pattern
Seiichi Uchida

Megumi Sakai

Masakazu Iwamura

Shinichiro Omachi

Kyushu Univ., Japan

Kyushu Univ., Japan

Osaka Pref. Univ., Japan

Tohoku Univ., Japan

Koichi Kise
Osaka Pref. Univ., Japan

Abstract

1. Introduction
In upcoming ubiquitous computing era, character patterns in 3D-scene will be often exposed to cameras andsometimes recognized by machines. Thus, character patterns can be promising media for ubiquitous computing, if
they possess not only perfect human-readability but alsohigh machine-readability. In this paper, the character pattern which possesses both readabilities is called universal
pattern.
OCR/MICR fonts [1] are classical universal patterns.
Their machine-readabilities, however, are not sufficient in
the ubiquitous computing era; they were designed for scanners or magnetic readers and thus not for cameras. As listed
in [2], character patterns acquired by cameras undergo various distortions which do not appear in character patterns acquired by scanners. For example, projective distortion and

l ’1
l ’2

l1
l2

guide

This paper is concerned with a universal pattern, which
is defined as a character pattern designed to have highmachine-readability. This universal pattern is a character pattern printed with stripes. The cross ratio calculated
from the widths of the stripes represents the character class.
Thus, if the boundaries of the stripes can be detected formeasuring the widths, the class can be determined without
ordinary recognition process. Furthermore, since the crossratio is invariant to projective distortions, the correct classwill be still determined under those distortions. This paper describes a practical scheme to recognize this universal
pattern. The proposed scheme includes a novel algorithm todetect the stripe boundaries stably even from the universal
pattern image contaminated by non-uniform lighting andnoise. The algorithm is realized by a combination of a dynamic programming-based optimal boundary detection anda finite state automaton which represents the property of
the universal pattern. Experimental results showed the proposed scheme could recognize 99.6% of the universal pattern images which underwent heavy projective distortions
and non-uniform lighting.

l3

(a)

L

l ’3

observation(b) line p

Figure 1. (a) The universal pattern “A” proposed in [3, 4]. (b) Observation line to extractclass information.
non-uniform lighting will seriously disturb the recognitionof not only ordinary character patterns but also OCR/MICR
fonts.
In [3, 4], a universal pattern has been proposed forcamera-based recognition. Hereafter, the term “universal
pattern” refers to the character pattern proposed in [3, 4],although we can consider another universal pattern such as[5]. Figure 1 (a) shows the universal pattern of [3, 4]. This
universal pattern is a character pattern printed with a setof horizontal stripes, called a cross ratio pattern, to realize
high machine-readability. The cross ratio calculated fromthe widths of the stripes represents the character class. This
fact means the character class can be determined without
ordinary recognition process if the cross ratio is extracted
correctly. In addition, the correct class will be determined
under projective distortions because the cross ratio is invariant to projective distortions.
This paper describes a practical scheme to recognize theuniversal pattern in real scene. For determining the widthsof the stripes, the boundaries of the stripes should be detected. One of the main contributions of this paper is the
proposal of a novel algorithm to detect the boundaries stably
even from universal pattern images contaminated by nonuniform lighting and noise1 . The algorithm is realized by
a combination of dynamic programming (DP) and a finite
1 Note that the trial in [3, 4] was a simulation experiment without any
grayscale change and therefore the boundaries can be detected just bychecking the grayscale value at each pixel.

spurious
overlooked

(a)

(b)

(c)

(d)

Figure 2. Contamination of grayscale value by non-uniform lighting and noise. (a) Character image and an observation line. (b) Grayscale value f (x) along the observation line. (c) A boundary
detection result without FSA. (d) A result with FSA.
f(x)

N

n

x1
boundaries

minimum selection

1

xn-1
xn

xn

x
(a)

x

x
(b)

xN

(c)

Figure 3. (a) Grayscale value f (x) along anobservation line. (b) Search for optimal segmentation by DP. (c) Piecewise-constant approximation of f (x) and boundary sequencex1 , . . . , xN .
state automaton (FSA) which represents the property of theuniversal pattern. Note that the proposed boundary detection algorithm is rather general one and it can be applied
to other various tasks. Another contribution is to report
the results of a recognition experiment of universal patternimages really acquired by a camera. The results showedthat even universal patterns with heavy projective distortions and non-uniform lighting could be recognized with avery high accuracy.

2. Universal Pattern for Camera-Based Character Recognition
2.1. Embedment of class information
The universal pattern proposed in [3, 4] is a character
pattern printed with the cross ratio pattern of Fig 1 (a) torealize high machine-readability. The cross ratio pattern iscomprised of five horizontal stripes. The top and the bot-tom stripes are guides, which have a fixed width and define
the beginning and the end of the cross ratio pattern. The
remaining three stripes have variable widths, l1 , l2 , and l3
and provide a cross ratio r byr=(l1 + l2 )(l2 + l3 ).
l2 (l1 + l2 + l3 )(1)

In this paper, we assume that all the universal patternsof class k are printed with the same cross ratio pattern withr = rk . In addition, we also assume rk = rk if k = k  .
Under these assumptions, the class of a universal pattern
can be determined, theoretically, just by extracting the crossratio rk .

2.2. Extraction of class information —Overview
The cross ratio rk can be obtained by drawing an observation line p on the universal pattern. As shown in Fig. 1(b),the observation line p passes across the cross ratio pattern.
Since the stripes are parallel originally and the cross ratio isa projective invariant, we can obtain the original cross ratio
rk by using measured widths l1 , l2 , and l3 instead of l1 , l2 ,and l3 in (1) regardless of camera angle and the position andthe slope of the observation line p.
The extracted cross ratio may be erroneous due to insufficient camera resolution, blurring, non-uniform lighting, etc.
Thus, we use the following voting strategy for a robust estimation of rk : (i) we draw the observation line p on thecharacter pattern P times changing its position and slope
randomly, (ii) obtain P cross ratio values, (iii) quantize eachof those values into one of {rk }, and (iv) choose the mostfrequent rk as the cross ratio embedded.

3. FSA-Guided Boundary Detection for Extraction of Class Information
3.1. Optimization-based boundary detection
For measuring the widths l1 , l2 , and l3 , it is necessary to detect the boundaries on f (x) which represents the

B0

B1
B+

B0 G1

G1
B1

B2

F1

B+

F+

B2

B2

F2

F2

observationline p

(a)

G1
B1

F1

B+

F+

B2

F2

B2
F2

G2
B3

B0

B2

G2

G2
B3

B3

(b)

(c)

Figure 4. (a) Decomposition of the universal
pattern into ten region types. (b) Transition ofregion types along the observation line in (a).
(c) FSA representing all possible transitions.
grayscale value at the position x (xs ≤ x ≤ xe ) on an
observation line. Figure 2 (a) and (b) show a character pattern with an observation line and f (x) along the observation
line. Simple threshold-based techniques are insufficient todetect the boundaries because the grayscale value on the observation line will be contaminated by non-uniform lighting
and other noises. As shown in Fig. 2 (b), the originally different grayscale values pointed by two arrows become similar due to non-uniform lighting.
An alternative is an optimization-based boundary detection technique whose basic idea is optimal piecewiseconstant approximation of f (x). Figures 3 (a) and (c) show
an example of f (x) and its piecewise-constant approximation. The ends of constant segments will indicate a boundary of the stripes.
The objective function of the approximation is formulated as
N  xnf (x) − f¯x ,x  dx,
(2)
J1 =
n−1 n
n=2

xn−1

and to be minimized with respect to the boundary sequence,
x1 , . . . , xn , . . . , xN , subject to the conditions, xn−1 < xn ,x1 = xs , and xN = xe . The value f¯xn−1 ,xn is the averagegrayscale value within the segment [xn−1 , xn ]. The minimization can be represented as an optimal path problem
from x1 to xN as shown in Fig. 3 (b) and solved by a DP
algorithm efficiently. While we omit the details of the DP
algorithm here, readers can find similar DP algorithms as
recognition-based segmentation algorithms for handwritten
text [6] and speech [7].

3.2. Incorporation of FSA
The above boundary detection technique still has two
drawbacks for our task. First, it cannot distinguish theboundaries of the stripes from the boundaries between character stroke and background. (The latter boundaries are notnecessary to extract the cross ratio.) Second, the above technique still produces spurious boundaries due to noise andoverlooks genuine boundaries.
Incorporation of an FSA is very useful to remedy thosedrawbacks since it can exploit the property of the universal pattern. For designing the FSA, we first consider ten
regions, B0, B1, B2, B3, B+, F1, F2, F+, G1, and G2of Fig. 4 (a). The first five regions correspond to background regions, the next three regions correspond to character stroke regions, and the remaining two regions correspond to the two guides. The region F+ has a different
grayscale value from the regions F1/F2 due to the overlayof the middle stripe of the cross ratio pattern. Similarly, theregion B+ has a different grayscale value from the regions
B0/B1/B2/B3. Figure 4 (b) shows the transition of the regions along the observation line of Fig. 4 (a). It is easy toconfirm that every possible transition like Fig. 4 (b) will be
described as a state transition of the FSA of Fig. 4 (c).
We consider an incorporation of the FSA into the technique of 3.1. By the incorporation, we can assign a state(i.e., a region) to each segment and thus distinguish the necessary boundaries from the unnecessary boundaries. In addition, we can expect far better results as discussed later.
The objective function after the incorporation of the FSA is
defined asN   xnf (x) − f¯xn−1 ,xn  dx
J2 =
n=2

xn−1


+ q(xn , xn−1 | sn , sn−1 ) ,(3)

where sn represents the state to which the segment[xn−1 , xn ] corresponds. The objective function J2 should
be minimized with respect to not only the boundary sequence x1 , . . . , xN but also state sequence s1 , . . . , sN ,where the state transition sn−1 → sn should be allowedby the FSA.
The function q “penalizes” erroneous combinations of
the two consecutive segments [xn−2 , xn−1 ] and [xn−1 , xn ]and the two states sn−1 and sn . Assuming sn−1 = B+
and sn = B2, the two segments should satisfy the condition f¯xn−2 ,xn−1 < f¯xn−1 ,xn . This is because the region oftype B+ should have a lower (darker) grayscale value than
the region of type B2. (See Fig. 4(a).) If the condition does
not hold, the function q returns ∞ to prohibit this segmentation; otherwise q returns 0 to allow the segmentation. Thus,by the incorporation of the function q, we can exclude thesegmentation which does not agree with the property of theuniversal pattern.
It should be noted that the function q checks the relative brightness of two consecutive segments and does notcheck any absolute brightness. The relative brightness is
far more stable against non-uniform lighting and noise than
the absolute brightness. The idea of this relative evaluation

is novel one and cannot be found in the conventional DPbased segmentation algorithms, such as recognition-based
segmentation [6, 7].
The foregoing DP algorithm for the minimization of J1
with respect to {xn } can be extended for the minimizationof J2 with respect to {(xn , sn )}. Simply speaking, this extension can be done by re-organizing the x–n search spaceof Fig. 3(b) to be an (x, s)–n search space. After the optimal sequence of {(xn , sn )} is obtained, l1 , l2 , and l3 are
obtained using xn related to stripe boundaries.
Details of the extended DP algorithm is omitted here
except for the important point that f¯xn−2 ,xn−1 in q is approximated as f¯xn−1 −,xn−1 , where  is a positive constant.
Without this approximation, q depends on xn−2 in addition
to xn−1 and xn . Thus, the minimization of J2 becomes aproblem on a second-order Markovian process and requires
prohibitive computations.

3.3. Estimation of the number of boundaries
The correct number of boundaries, N , is not known inadvance. Thus, all possible N s should be examined; thatis, the above algorithm is performed repeatedly for each N .
Fortunately, the Markovian nature of the DP-algorithm allows us to obtain the optimal solution at N from that at
N − 1 with very few computations. If a certain N gives aboundary detection result which is acceptable by the FSA
and provides the minimum J2 , this N is considered as thecorrect one.

4. Experimental Results
4.1. Experimental setup
The universal patterns of 26 English capital letters(Fig. 5) were printed on a paper. The original intensity values were: 255 for B0/B1/B2/B3, 215 for B+, 0 for F1/F2,
80 for F+, and 175 for G1/G2. Then they were acquired
as grayscale images by a camera from 9 different angles
as shown in Fig. 6. The lighting condition was not controlled with the angles and thus the images underwent the
distortion by non-uniform lighting as well as the projective distortion. The average size of the universal patternimages was 381×291 (pixels). Then, P = 81 observationlines were drawn on each universal pattern image and the
proposed boundary detection algorithm was applied to eachobservation line. Thus, there were 26 × 9 = 234 universal
pattern images and 234 × 81 ∼ 19, 000 observation lines.

Figure 5. Universal patterns used in our experiment.

1

4

2

6

5
7

3

8

9

Figure 6. Camera angles.
solving the minimization problem of J1 . It is observed that
two spurious boundaries were detected and the two boundaries of the lower guide were overlooked. In contrast, theproposed technique provided the result (d) and could avoid
those spurious and overlooked boundaries. This improvement was achieved by the incorporation of the FSA; it could
exclude inadmissible segmentation in (c) where the average grayscale values decreases gradually on five consecutive segments.

4.3. Quantitative evaluation of segmentation result

4.2. Qualitative evaluation of boundary detection result

The ratio of the observation lines whose cross ratio rk
were extracted correctly was 69.2%. The extracted crossratio becomes erroneous even if only a single boundary is
detected wrongly and the remaining N − 1 boundaries aredetected successfully. Thus, the ratio of boundaries detected
correctly will be far higher than 69.2%.
Figure 7 shows the correct detection ratio of each classand Fig. 8 shows the ratio of each camera angle. Both figures reveal that the correct extraction ratio is stable against
character shapes and camera angles. Especially, Fig. 8
proves the invariance of the cross ratio against projective
distortions.
The proposed technique failed to extract correct cross ratios due to the following three reasons.

Figures 2 (c) and (d) show the results of boundary detection on an observation line. The result (c) was obtained by• Failure to estimate the number of boundaries on the observation line. In fact, this failure was found in 19.1%

ratio of observation lines
with wrong cross ratios

ratio of observation lines
not accepted by FSA

were “N” and 26 lines were “O”. As shown in Fig. 5, thecross ratio patterns of “N” and “O” are similar and theirsmall difference caused the misrecognition.

100
(%)
80

5. Conclusion

60
40

ratio of observation lines
with correct cross ratios

200

A B C D E F G H I J K L M N O P Q R S T U V WX Y Z

Figure 7. Extraction accuracy of cross ratios
for each class.
ratio of observation lines
with wrong cross ratios

ratio of observation lines
rejected by FSA

100
(%)
80
60
40

ratio of observation lines
with correct cross ratios

20
0

1

2

3

4
5
6
camera angle ID

7

8

9

Figure 8. Extraction accuracy of cross ratios
for each camera angle. Each angle ID (1∼9)
corresponds to the number in Fig. 6.

of the 19, 000 observation lines.
• Erroneous detection of boundaries. The boundary detected at a slightly different position was sometimes
accepted by the FSA.
• Unexpected f (x). For example, if an observation line
passes a point where a character boundary crosses a
stripe boundary, such an unexpected region change(e.g., B1→ F+) will happen; the FSA will reject thischange. Fortunately, this problem is not serious; asshown in Figs. 7 and 8, most (∼ 98%) observation lines
were accepted by the FSA.

4.4. Recognition accuracy
As noted in 2.2, the final recognition result of a character pattern was determined by the voting of P = 81 extraction results. The overall character recognition rate was
99.6%=233/234, that is, only one universal pattern image
was misrecognized. This near-perfect recognition rate results from the fact that the ratio of the observation lines withcorrect rk was 69.2% (> 50%).
The misrecognized image was “O” whose recognition
result was “N”. Among its 81 observation lines, 27 lines

A practical scheme of recognizing a universal pattern has
been proposed. The universal pattern is a character pattern
printed with a set of horizontal stripes, called cross ratio pattern, for realizing high machine-readability. The cross ratio
calculated from the widths of the stripes represents class information and is invariant to projective distortions. Thus, if
the boundaries of the stripes are detected correctly, we candetermine the character class regardless of projective distortions.
A novel boundary detection technique has been proposed
to recognize the universal pattern. This is an optimizationbased technique with a guide of a finite state automaton(FSA) for stable extraction of class information under heavychange of grayscale values due to non-uniform lighting andnoise. Again, note that this technique is rather general andthus applicable to other tasks.
An experiment of recognizing 234 universal pattern images acquired by a camera in scene was conducted. The obtained recognition rate was 99.6%=233/234, that is, a nearperfect rate. The boundary detection performance was also
very reasonable even though the character patterns wereheavily degraded by non-uniform lighting, noise, and projective distortions.

References[1] The British Computer Society. Character Recognition 1967,
Unwin Brothers Limited, 1966.
[2] J. Liang, D. Doermann and H. Li: “Camera-based analysis oftext and documents: a survey”, International Journal of Document Analysis and Recognition, vol. 7, pp. 84–104, 2005.
[3] S. Uchida, M. Iwamura, S. Omachi and K. Kise, “Data embedding for camera-based character recognition,” Proc. First
Int. Workshop on Camera-Based Doc. Anal. Recog., pp.60–
67, 2005.
[4] S. Uchida, M. Iwamura, S. Omachi and K. Kise, “OCR fonts
revisited for camera-based character recognition,” Proc. 18th
Int. Conf. Pat. Recog., vol. 2 of 4, pp.1134-1137, 2006.
[5] S. Omachi, M. Iwamura, S. Uchida, and K. Kise, “Affine invariant information embedment for accurate camera-based
character recognition,” Proc. 18th Int. Conf. Pat. Recog.,vol. 2 of 4, pp.1098-1101, 2006.
[6] R. G. Casey and E. Lecolinet, “A survey of methods andstrategies in character segmentation,” IEEE Trans. Pat. Anal.
Mach. Intell., vol. 18, no. 7, pp. 690–706, 1996.
[7] H. Ney and S. Ortmanns, “Progress in dynamic programming search for LVCSR,” Proc. IEEE, vol. 88, no. 8,
pp. 1224–1240, Aug. 2000.