手写字符识别的进展与几何变换方法

需积分: 10 153 浏览量更新于2024-07-19 收藏 11.61MB PDF 举报

"《Advances in Character Recognition》是由Xiaoqing Ding编辑的一本书，集结了多位贡献者在字符识别领域的研究成果。这本书探讨了在模式识别，特别是手写字符识别中的挑战，以及如何设计有效的分类函数来区分同一类别内的不相关变异性，并识别不同类别的有意义差异。书中提到了两种方法，一种是存储大量原型实例进行匹配，另一种是使用几何变换生成单一原型的变形实例以适应输入的数字模式，其中Lie算子的概念被应用到几何变换中。这本书的开放访问章节允许用户下载、复制和基于文章内容进行构建，只要作者和出版社得到适当引用，这有助于知识的广泛传播和影响。" 字符识别是一种在图像处理和机器学习领域中的关键技术，它涉及将手写或打印的字符转化为计算机可理解的数字形式。在《Advances in Character Recognition》中，作者们深入讨论了这个主题，特别是在手写数字识别方面的挑战。一个关键问题是如何构建一个高效的分类系统，这个系统能够对同一类别的字符进行归类，同时能够识别出不同类别的特征。传统的字符识别方法可能需要存储每个类别的多种实例（如不同大小、角度、倾斜等）作为原型，然后通过某种距离度量标准去匹配输入的字符模式。这种方法虽然直观，但可能导致存储需求过大，从而影响系统的效率和实用性。为了解决这个问题，书中提出了使用单个原型并利用几何变换的方法。这种方法仅需一个代表性的模板，通过Lie算子执行如加粗、旋转等操作，生成各种变形的实例，以便最优化地匹配输入的字符模式。Lie算子是一种数学工具，它允许对连续群（如旋转、缩放）进行线性化处理，使得字符的变形能够更灵活地被建模和匹配。此外，书中还涵盖了其他贡献者的工作，包括但不限于神经网络、深度学习模型、特征提取技术以及在实际应用中的字符识别算法。这些研究可能涉及提高识别准确性、降低错误率、减少计算复杂度等方面，以推动字符识别技术的进步。《Advances in Character Recognition》为读者提供了当前字符识别领域的前沿理论和实践方法，对于研究人员和工程师来说，是一份宝贵的参考资料，有助于他们理解并解决字符识别中的复杂问题，推动相关技术的发展。

8 Character Recognition

Transformation

Transformation matrix T

Lie operator and

(adapted from [18]) the transformed image

Rotation (R)



cos θ,

−

sin θ

sin θ, cos θ



∂

∂x

−

∂

∂y

(

)

Scaling (S)



θ,0

0, 1



∂

∂x

∂

∂y

(

)

Scaling (S

)



θ,0

0, 1



∂

∂x

(

)

Scaling (S

)



1, 0

0, 1



∂

∂y

(

)

Parallel Deformation ( P)



θ,0

0, 1

−



∂

∂x

−

∂

∂y

(

)

Diagonal Deformation (D)



1, θ

θ,1



∂

∂x

∂

∂y

(

)

Table 1. Six types of transformation and their associated Lie operators (θ is the degree of the

transformations).

We can see from (32) that only simple subtractions and multiplications are involved in

applying the Lie operator to o btain L

(

)

, which needs to be calculated just once, since a

different transformed version I

corresponding to a different degree of transformation (θ) can

be obtained by using the same L

(

)

. Therefore, the implementation of Lie operators has

fairly low computational complexity.

2.4. Li e operators for transformation estimation

Lie operators were p roposed in [18] as an effective method for handling transform ation

invariance in handwritten digit pattern recognition [19]. In order for an automatic method to

“recognize” a handwritten digit, the inco ming digit pattern needs to be accurately classiﬁed

into one out of ten possible categories. one method is to use an only one prototype image (I)

for each category, with different “deform ed” instances, s

(

I, Θ), of the same prototype image

being generated by ge ometric transformations dur ing the matching proc ess so as to best ﬁt

the incom ing digit pattern. As mentioned in the section 1, when the set of transformations

is parameterized by m parameters θ

∈

Θ (rotation, scaling, etc.), the transformed image

(

I, Θ) is a surface (manifold) with intrinsic dimension of at most m. In general, such a

manifold is not linear. Matching a defo rmable prototype to an incoming pattern now amounts

to ﬁnding the po int on the manifold that is at a minimum d istance from the point in the

pixel space correspond ing to the inco ming pattern. Be cause the manifold has no analytical

expression, the matching process can be very difﬁcult. However, if the set of transformations

happens to be linear in the pixel space, then the manifold is a linear subspace (a plane).

The matching procedure is then reduced to ﬁnding the shortest distance between a point

(vector) and a plane, or between two tangent planes corresponding to their original manifolds,

which is the idea of tangent distance in [18]. While the tangent d istance is able to capture the

transformation invariance, it involves solving of a complicated least-square problem, which is

not only computationally ex pensive, but also prone to numerical instability issues associated

with solving linear systems. The refore , conventional Euclidean distance between patterns,

Advances in Character Recognition

Efﬁcient Transformation Estimation Using Lie Operators: Theory, Algorithms, and Computational Efﬁciencies 9

due to its fast and easy calculation, was also used in conjunction with the tangent distance in

actual implementation.

On the other hand, for many pattern recognition tasks, e.g., character recognition, a set of

allowable deformations of the prototype might have been known a priori. Therefore, one can

generate on-the-ﬂy a set of varying transformed versions of the same prototype I, by using the

Lie operators associated with the transforms, in a computationally efﬁcient way. For example,

a set of rotated images I

(

)

, where i

1,2,...,n, can be readily obtained by

(

)

, (35)

where L

(

)

can be pre-computed and shared by calculatio ns of different I

(

)

Thus, transformation estimation refer s to matching an incoming pattern imag e P to the “closest”

(

)

, which has the shortest distance with P. For simplicity, the Euclidean distance could be

used.

In transformation estimation, we search for a value for θ that best matches the degree of

transformation the prototype has undergone in relation to the incoming pattern. If the best θ

value is found to be zero in the case of rotation, then the resultant rotate d version will be the

same as the original prototype. If θ has a larger search range, then the probability of ﬁnding a

better match may be increased; however, the complexity of searching will be increased as we

have to examine mo re candidates. On the other hand, the step size of θ is al so an important

parameter that controls the “granularity” of the searching. By de creasing the step size, we

may be able to enl arge the searching range of θ without increasi ng the search complexi ty. We

can further lower the searching complexity by using variable step sizes. For example, we can

employ ﬁner-granular searching by taking s maller step sizes for small θ values, whereas the

step size increases as the search drifts away from the centers of the range of allowable θ value s

[11].

Transformation estimation can be viewed as a generali zed operation of the translation

motion estimation. In the following, we present a case study to illustrate the design of

computationally efﬁcient trans formation estimation algorithms based on L ie operators, by

selecting the subject of local motion estimation in video coding, where both accur ate and

fast motion estimation is critical [12]. We then discuss several methods in which multi ple

Lie operators can be combined to detect smaller degrees of object motions in video frames

such as scaling, rotations and deformations, with varying co mputational complexities. We

then provide both analytical and empirically obtained results regarding the trad eoffs between

estimation accuracies and computational complexities for these methods [13].

3. Transformation estimation in video coding

Motion estimation is a critical component of almost every video coding system [10][17][23].

Most compression techniques exploit the temporal redundancy that exists between the

succeeding frames. In motion estimation, we search for any object in the previous frame that

provides a good match of an object in the current frame within a sequence of images (frames).

Motion compensation refers to represe nting objects in the current frame by their match objects

in the previous frame. Conventional motion estimation algorithms in video coding consider

Eﬃ cient Transformation Estimation Using Lie Operators: Theory, Algorithms, and Computational Eﬃ ciencies

10 Character Recognition

only translations as an approximation to a combination of potential motions of objects in a

video scene, including scaling, rotation, deformations and so on.

3.1. Block-based translation motion estimation

Bloc k-based motion estimation [10][23] has been adopted in international standards for vi deo

coding such as MPE Gs and H. 264, where each frame is partiti oned evenly into square blocks.

Motion estimation is applied on a block-by-block basis so that each block is associated with

a motion vector. Motion vectors are used to produce a motion-compensated prediction of

a frame to be transmitted from a prev iously transmitted reference frame [1][7]. Motio n

estimation enables us to transmit the frame difference as an update between the current frame

and the motion-compensated prediction of the current frame from the previous fram e, rather

than the entire current frame, thereby achieving compression by user fewer bits to code the

current frame.

In bloc k-base d motion estimation, each frame is divided into evenly partitioned square blocks

4, 8

8, . . ., etc.). We attempt to predict the current frame (F

) from the previous frame

). The prediction is obtained by taking the best match of each block of F

within the

searching window of F

. The match criterion is typically based on mean square e rror (MSE ).

The block with the minimum MSE is considered to be the best match, and its associated

motion vector

(

dx, dy

)

is given by

(

dx, dy

arg min

(

du,dv

)∈[−

R,R

]

{

MSE

m, n

−

∑

i,j

[

(

x, y

) −

(

du, y

)

]

}

, (36)

where B is the block size,

[−

R, R

]

is the searching window, and x

i, and y

j for the block

(

m, n

)

. Note that the motion vector for a still block is

(

0, 0

)

After ﬁnding in F

the best match block of each block in F

, the prediction frame (P

) of F

can

then be constructed. To determine the accuracy of the prediction, the PSNR between F

and

P1 is calculated as

PSNR

10 log

255

MSE

avg

, (37)

where MSE

avg

is the average mean square error between F

and P

as given by

MSE

avg

∑

MSE

m, n

. (38)

Note that MSE

m, n

is deﬁned in (36), and M

N is the total number of blocks in a frame.

Conventional motion estimation algorithms in video coding consider only translations as an

approx imation to a variety of object motions; therefore, they have limitations in capturing

potential motions such as scaling, rotations and defo rmations in a video scene other than

the translation. T he reason for the widespread use of the translation model lies partly in its

simplicity - translation model can be readily characterized by displacement motion vectors

and can thus be implemented with much lower complexity than other non-linear motion

models used to describe non-tr anslation motions. Nonetheless, the accuracy of the motion

estimati on would be sacriﬁced by considering the translation mode l alone.

Advances in Character Recognition

Efﬁcient Transformation Estimation Using Lie Operators: Theory, Algorithms, and Computational Efﬁciencies 11

3.2. Block-based transformation estimation

Non-translational transformati on estimation can be introduced into video coding to further

increase the ove rall motion estimation accuracy. More speciﬁcally, the conventional

(translation) motion estimation is applied on the previous frame (F

) based on the current

frame (F

). We can construct a predicted frame P (of the current fram e) from the previous

frame by using the resulting motion vecto rs associated with each block in the current frame

(see Fig. 4). The accuracy of the pre dicted frame P (relative to the current frame F

) can be

represented by PSNR

. Next, transformation estimation based on the Lie operators is applied

on the match blocks (B

) in the predicted frame P to further improve the motion estimation

accuracy. For each block B

in P, we search for the best parameter θ from the set of candidate

parameters that yields the smallest mean square error between the transformed version B

and the corresponding block (B

) in the current frame F

. Consequently, a new predicted

frame P

can be formed by the resulting blocks of B

. The accuracy of the newly predicted

frame P

can be represented as PSNR

. As expected, P

will become a better prediction of

the current frame than P, thereby achieving an increased accuracy in motion estimation and

prediction. The accuracy of the motion estimation can be measured by the PSNR between the

Figure 1. The transformation estimation system using a Lie operator: We search for the best θ in the set

of candidates [θ

, θ

,...,θ

] such that the transformed block B

of the block B

in the prediction frame

P will have the smallest MSE compared to the corresponding block B

in F

current frame and the predicted frame. The improved accuracy due to the motion models is

calculated as (PSNR

−

PSNR

). The accuracy of the motion estimation can be improved by

considering other types of transformations as well.

4. Computational efﬁciencies of transformatio n estimation using multiple

Lie operators

We ﬁrst examine the full search method that exhaustively searches for the best combi nation

of four types of Lie operators (R, S, P and D). In order to reduce the high computational

complexity associated with the full search method , we then consider the following three

Eﬃ cient Transformation Estimation Using Lie Operators: Theory, Algorithms, and Computational Eﬃ ciencies

12 Character Recognition

parameter-search methods: dynamic programming (DP)-like search, iterative search, and serial

search. They combine the Lie operators in different ways, with varying accuracy-complexity

trade offs [13].

4.1. Full search

Fig. 2 illustrates all possible combinations of the Lie operators for rotation, scaling, parallel

deformation, and diagonal deformation. The highlighted path shows one combination (D

→

R), which means that block B

will be ﬁrst diagonally deformed, and then the

deformed block will go through the parallel deformation. The resultant block will be scaled

and then rotate d to obtain B

. The degree of motions (θ) associated with each participating

operator is optimized by the searching procedure illustrated in Fig. 1. The full search is the

R R R

Figure 2. The trellis structure of the combined Lie operators. The output block B

is expected to provide

more accurate prediction than the input block B

most straightforward and yet the most computati onally exp ensive method. In this method,

we search through all possible (4

256) paths that start from block B

(of the predicted

frame P) and end on the transformed block B

(of a more accurately predicted fr ame than P),

and select the path (i.e., the combination of the four Lie ope rators) whose output block B

the most accurately predicted version of block B

in the current frame.

Assume that x is the computational complexity of motion estimation for a single Lie operator.

Thus the complexity associated with any path of four operators from B

to B

in Fig. 2 is 4x.

Since we need to search all 256 possible paths, the overall complexity of the full search me thod

will be 1024x.

We can reduce the complexity of this brute-force search approach by dividing the estimation

process into four stages, with each stage corresponding to one column of operators in Fig. 2.

In the ﬁrst stage, there will be four estimation oper ations for R, S, P, and D, respectively, with

complexity being 4x. In the second stage, we will apply the same fo ur operators on one of

the four candidate transformed blocks g enerated by one of the four operators in stage one.

For example , starting with R in the ﬁrst stage, we will examine R

→

R (R in the ﬁrst stage,

followed by R in the second stage), R

→

S, R

→

P, and R

→

D. Note that app lying the

R ope rator again on a block already rotated by the best θ value as found in the ﬁrst stage

of estimation would not be beneﬁcial in general. However, further gains in the estimation

accuracy might be achievable by considering other combinations such as R

→

S, R

→

P, and

→

D. Therefore, the total complexity of the second stage will be 4

16x. Likewise,

the complexity of the third s tage will be 4

16x

64x. In the last stage, the complexity will

amount to 4

64x

256x. Therefore, the overall complexity of the reduced-complexity full

Advances in Character Recognition

剩余239页未读，继续阅读

mxyzptlk

粉丝: 0
资源: 10

手写字符识别的进展与几何变换方法

声音识别语音识别资料Advances In Speech Recognition (2010).zip

Hexagonal Image Processing: A Practical Approach (Advances in Pattern Recognition)六角网格图像处理

写几篇关于ocr的文献综述

advances in financial machine learning

advances in neural information processing systems

advances in financial machine learning pdf

advances in microstrip and printed antennas.pdf

recent advances in deep learning for object detection

ieee icassp recent advances in nonnegative matrix factorization

最新资源