印刷体科技文档识别技术实践研究

Size: px

Start display at page:

Download "印刷体科技文档识别技术实践研究"

土齑卓
7 years ago
Views:

1 〇

3 ( ) : ( ),, , , , , : ( ) 2 ( ) 3 ( ) :

6 1. 2. ZZ ZZ YY YY ZZ

9 ( )

15 A Practical Study on Printed Scientific Document Recognition [Abstract] Due to the absent of functionality of mathematical formula recognition and logical layout analysis, the use of optical document recognition in education and scientific fields is limited which is a lost for the spread of advance in science and technology. Therefore, building a complete printed scientific document recognition system is of practical interest. In this paper, key aspects of scientific document recognition are discussed systemically from a practical point of view, applicable algorithms for each stage are given in detail. Accuracy, efficiency and extensibility are considered. By combining all these works, one can outline a design of a real system. A logical layout analysis method based on text line is proposed, it can find out paragraphs, headings, list items and more. A new character recognition framework based on glyph matching is suggested, it can identify character in complicated context, special symbol can also be recognized using dynamically generated template. A mathematical formula detection algorithm based on 2-dimensional structure detection and symbol type, in addition to a structural analysis method for mathematical formula based on symbol adjoin graph is described, scripts, hats, fractions, radical expressions, matrices are supported. An implementation, MathOCR, is available as a free software. Quantitative evaluation shows that the system has achieved impressive performance. Although the system comes with the most essential features, more work is needed before becoming capable for daily use. [Key Words] document recognition; layout analysis; mathematical formula recognition; optical character recognition

18 A 51 B 53 C 55 D 59

19 [1] 1

20 [2] [3] [4] Voronoi [5] [6] [7] [8] [8, 9, 10] [8, 10] [11] [9] [12] [9, 12] [13] [14]

21 : 1.2: 3

22 4

23 2.1 [15] [16] [2] 5

24 [3] ARGB 2.1 m, n Z D : m n (i, j) (A (i, j), R (i, j), G (i, j), B (i, j)) m n (i, j) m n D(i, j) D (i, j) A(i, j) R(i, j) G(i, j) B(i, j) D (i, j) 2.2 m, n Z D : m n 256 m n (i, j) m n D(i, j) D (i, j) 2.3 m, n Z D : m n 2 m n (i, j) m n D(i, j) = 0 (i, j) D (i, j) D D D 6

25 RGB R G B [17] 0.309R G B ARGB RGB D : m n (i, j) (A (i, j), R (i, j), G (i, j), B (i, j)) m n D 0 : m n 256 (i, j) 255 ( 1 ) A(i, j) D gray(d) 316R(i, j) + 624G(i, j) + 84B(i, j) 1024 A(i, j) 255 m n Θ(mn) 2.5 D m n T : m n Z D 0 : m n 2 0 D(i, j) T (i, j) (i, j) 1 D(i, j) > T (i, j) D T threhold T (D) T t threhold T (D) t threhold t (D) m n Θ(mn) 7

26 Otsu [17] [16] Sauvola [18] [19] [19] kfill [20] [21] [3] Hough [22] Hough π 60 π 900 θ θ P (x, y) = r(cos ϕ, sin ϕ) P θ P (x, y ) = r(cos(ϕ θ), sin(ϕ θ)) = r(cos ϕ cos θ + sin ϕ sin θ, sin ϕ cos θ cos ϕ sin θ) = (x cos θ + y sin θ, y cos θ x sin θ) h w x min{0, h sin θ, w cos θ, w cos θ + h sin θ} y min{0, w sin θ, h cos θ, w sin θ + h cos θ} x 0, y 0 P (x, y ) = 8

27 (x x 0, y y 0 ) ( ) ( ) ( ) x cos θ sin θ x = y sin θ cos θ y ( ) ( ) (( ) x cos θ sin θ x = + y sin θ cos θ y ( x0 ) y 0 ( x0 y 0 )) (2.1) (2.2) Sauvola Otsu Sauvola (a) (b) Otsu (c) Sauvola 2.1: 9

28 (a) (b) (c) kfill (d) 2.2: Hough 2013 ICDAR DISEC [23] 1550 π 12 π 12 Hough [ π 12, π 12 ] 5 0 AMD Athlon(tm) II Dual-Core M320 2GB Debian GNU/Linux jessie OpenJDK 1.7.0_

29 2.1: % % % % % Hough 99.35% % % (a) (b) (c) (d) 2.3: 11

30 (a) (b) (c) (d) 2.4: 12

31 Hough

32 14

33 3.1 XML 3.1 A A P(A) a A a = A A A A C 3.2 m, n Z + F m n C F F F C F c C f F c f F F 3.3 F Z Z F F f F { } { } R f = min i,..., max i min j,..., max j (i,j) f (i,j) f (i,j) f (i,j) f (3.1) f f 1, f 2 F f 1 f 2 R f1 R f2 = F F 3.4 D m n F F P D P D P F L P L D P L D L 15

34 3.1.1 [5] [5] [5] [5] [24] [25] [6] A, B A B A B A, B A B A, B C A, B A B 16

35 (a) (b) 3.1: Breuel 3.1a 3.1b ABCDA Figure Fig. Table 17

36 [9] [26] k Θ(k) [6] 3.1 k O(k 4 ) O(k 2 ) O(k 4 ) 18

37 3.1: : {R 0,..., R k 1 } : L : A( I k ), d( 0) s 1 /* */ 2 i {0,..., k 1} 3 j {0,..., k 1} 4 R j.left R i.right R i.left R j.right R j.top < R i.top A ji = 0 5 A ji 1, d i d i + 1; 6 u, v {0,..., k 1} 7 A uj = 1 A iv = 1 A uv = 0 8 A uv 1, d v d v + 1; /* */ 9 i {0,..., k 1} 10 j {0,..., k 1} 11 R j.right < R i.left A ij = 0 A ji = 0 12 A ji 1, d i d i + 1; 13 u, v {0,..., k 1} 14 A uj = 1 A iv = 1 A uv = 0 15 A uv 1, d v d v + 1; 16 d i = 0 s.push(i); /* */ 17 s 18 i s.pop(); 19 L.add(R i ); 20 j {0,..., k 1} 21 A ij = 1 22 d j d j 1; 23 d j = 0 s.push(j); 19

38 B T B T 1, T 2 T Pr 1 (T 1 ) Pr 1 (T 2 ) = T B T B b 00 b 01 b 02 b 03 b b 10 b 11 b 12 b 13 b B = b 20 b 21 b 22 b 23 b 24 = b 30 b 31 b 32 b 33 b b 40 b 41 b 42 b 43 b b ij 1 i j 3.2 k Θ(k) 3.6 (P 1,..., P s ) s i = 1,..., s P i i s (P 1,..., P s ) i = 1,..., s P i L i L 1,..., L s L L k l(k < l) L k + 1 l 1 L l 20

39 3.2: : (T 0,..., T k 1 ), w, f : L : B, (t 0,..., t k 1 ) 1 2 i 0; 3 i < k 4 T i 5 curr P aragraph(t i ) 6 T i.text 7 curr Caption(T i ) 8 t i = 0 f 9 curr T itle(t i ), f f 10 t i = 0 L 11 curr Author(T i ) 12 t i = 0 t i = 1 (t i = 2 T i.width < w T 3 i.text ) 13 curr Heading(T i ) 14 T i.text 15 curr Listing(T i ) curr P aragraph(t i ) 18 i + 1 < k (b ti,t i+1 = 1 T i+1 ) 19 i i + 1; 20 curr.addt extline(t i ); 21 i i + 1; 22 L.add(curr); 21

40 k l 3 2 L L Θ( L ) L A TEX HTML 3.3 MediaTeam Oulu [27] ( 59.9%) % 99.3% 3.1: % i j 22

41 3.4 [6] 23

42 24

43 4.1 Tesseract[28] GNU Ocrad[29] [8] [8] [28] 1%[30] 98% 25

44 [31] [31] [10] [10] [9] [9] [9] [9] 1 [32] ( ) [ ] { } {}}{ }{{} G G G 26

45 G h G G h G i Z c i = {j Z (i, j) G (i, j + 1) / G} (4.1) (c i ) i= G G c G G c G C ar(c) = max (i,j) C i min (i,j) C i + 1 max (i,j) C j min (i,j) C j + 1) (4.2) { G G 4 5 ar(g) ar(g ) 5 } 4 ar(g) mn m = n = 3 i = 1,, m; j = 1,, n (i, j) G N ij A ij d ij = N ij A ij (4.3) d ij = m r=1 d ij n s=1 d rs (4.4) mn D(G) = 1 mn (d 11,..., d 1n,..., d m1,..., d mn) (4.5) { G G 1 D(G) D(G ) 1 > 9 10 ( )} 1 min D(G) G G D(G ) 1 27

46 [17] i Z p i = {j Z (i, j) G} (4.6) (p i ) i= G [33], 90% % π Hausdorff Hausdorff Hausdorff Hausdorff 28

47 4.3 AMSFonts[34] CMB10 CMBSY10 CMEX10 CMMI10 CMMIB10 CMR10 CMSY10 EUFB10 MSAM10 MSBM10 RSFS Sauvola : % 42.53% 54.64% 99.20% 61.27% 20.69% 75.42% 85.94% 99.20% 93.72% 13.97% 76.75% 86.91% 99.29% 94.25% 16.89% 78.78% 88.15% 99.20% 93.55% % 77.72% 87.44% 99.20% 94.96% % 77.90% 88.15% 99.20% 94.61% % 76.22% 86.74% 99.20% 93.99% % 77.90% 87.62% 99.20% 94.25% % 78.34% 87.62% 99.20% 94.96% % 64.46% 80.11% 99.20% 89.83% % 42.53% 54.47% 99.20% 61.63% 29

48 4.2:

49 [30] [9] [35] [12] 31

50 Parzen [12] [35] [14] 32

51 [36] [9] [37] [38]

52 5.2.2., 60 [39] 1. e = (u, v) u 1 v 1 u v u v u v 2. 2 u v w 1 v w 0 1 u v w v w 3. 34

53 4. ( [ { 2 5. n m Θ((m + n)α(m + n)) α [33] 5.1 ( V, E ) 35

54 5.1: : G = (V, E) k : G : changed 1 2 changed true; 3 changed 4 changed false; 5 i {1,..., k} 6 i 7 changed true; 8 break; 5.3 Infty InftyCDB-2 [40] : % % % % % %

55 PDF 37

56 38

57 6.1 Sauvola Otsu Hausdorff 39

58 MathOCR JPEG PNG GIF BMP PNM L A TEX HTML MathOCR MathOCR MathOCR MathOCR Java MathOCR

59 41

60 42

61 0 = n N n + 1 = n {n} 43

62 44

63 [1] SIMONE M. Introduction to document analysis and recognition[a]. Machine learning in document analysis and recognition[m], Berlin: Springer, 2008:1 20. [2] FARAHMAND A, SARRAFZADEH A, SHANBEHZADEH J. Document Image Noises and Removal Methods[A]. Proceedings of International MultiConference of Engineers & Computer Scientists 2013[C], Hong Kong: Newswood Limited, 2013:1 5. [3] REZAEI S B, SARRAFZADEH A, SHANBEHZADEH J. Skew Detection of Scanned Document Images[A]. Proceedings of the International MultiConference of Engineers and Computer Scientists Vol I.[C], Hong Kong: Newswood Limited, 2013:1 6. [4] SHAFAIT F, KEYSERS D, BREUEL T M. Performance Comparison of Six Algorithms for Page Segmentation[A]. DOCUMENT ANALYSIS SYSTEMS VII, PROCEEDINGS[C], Berlin: SPRINGER-VERLAG, 2006: [5] KEYSERS D, SHAFAIT F, BREUEL T M. DOCUMENT IMAGE ZONE CLASSIFICA- TION[A]. Proceedings of International Conference on Computer Vision Theory and Applications[C], Barcelona: INSTICC, 2007: [6] BREUEL T M. High Performance Document Layout Analysis[A]. Proceedings of the Symposium on Document Image Understanding Technology[C], Greenbelt: University of Maryland, 2003: [7] KAMOLA G, SPYTKOWSKI M, PARADOWSKI M, et al. Image-based logical document structure recognition[j]. Pattern Analysis and Applications, 2014:1 15. [8] MOHAMED C, NAWWAF K, LIU C L, et al. Character recognition systems[m]. Hoboken: Wiley- Interscience, [9],. [M]. :, [10] TRIER D, TAXT T, JAIN A K. Feature extraction methods for character recognition - A survey[j]. Pattern Recognition, 1996, 29(4): [11] BREUEL T M. The OCRopus open source OCR system[a]. Proceedings of SPIE 6815, Document Recognition and Retrieval XV[C], San Jose: SPIE-IS&T, 2008:68150F 68150F 15. [12],,. :MatheReader[J]., 2006, 29(11): [13],,. [A]. [C], :, 2002: [14] CHAN K F, YEUNG D Y. Mathematical expression recognition: a survey[r]. Hong Kong: HKUST,

64 [15] SHAFAIT F, VAN BEUSEKOM J, KEYSERS D, et al. Document cleanup using page frame detection[j]. International Journal on Document Analysis and Recognition, 2008, 11(2): [16] SAUVOLA J, PIETIKäINEN M. Adaptive document image binarization[j]. Pattern Recognition, 2000, 33(2): [17] BURGER W, BURGE M J. : Java [M]. :, [18] SHAFAITA F, KEYSERSA D, BREUEL T M. Efficient Implementation of Local Adaptive Thresholding Techniques Using Integral Images[A]. Proceedings of The International Society for Optical Engineering, Document Recognition and Retrieval XV[C], San Jose: SPIE-IS&T, 2008: [19]. [D]. :, [20] O GORMAN L. Image and Document Processing Techniques for the RightPages Electronic Library System[A]. Proceedings of the International Conference on Pattern Recognition[C], Los Alimitos: IEEE, 1992: [21] GATOS B, PRATIKAKIS I, PERANTONIS S. Adaptive degraded document image binarization[j]. Pattern Recognition, 2006, 39(3): [22] ALAEI A, NAGABHUSHAN P, PAL U, et al. A Painting Based Technique for Skew Estimation of Scanned Documents[A]. Proceedings of the International Conference on Document Analysis and Recognition[C], Washington: IEEE, 2011: [23] Computer Vision Lab of Vienna University of Technology. Skew Estimation Datasets[DB/OL] [24] SUZUKI M, TAMARI F, FUKUDA R, et al. INFTY An Integrated OCR System for Mathematical Documents[A]. Proceedings of the 2003 ACM Symposium on Document Engineering[C], Grenoble: Elsevier B.V., 2003: [25]. [D]. :, [26] KIENINGER T, DENGEL A. The T-Recs Table Recognition and Analysis System[A]. Proceedings of the Third IAPRWorkshop on Document Analysis Systems[C], London: Springer-Verlag, 1998: [27] SAUVOLA J, KAUNISKANGAS H. MediaTeam Oulu Document Database[DB/OL] [28] SMITH R. An Overview of the Tesseract OCR Engine[A]. Proceedings of the International Conference on Document Analysis and Recognition[C], Curitiba: IEEE, 2007: [29] DIAZ A D. GNU Ocrad Manual[EB/OL]. manual.html, [30] UCHIDA S, NOMURA A, SUZUKI M. Quantitative Analysis of Mathematical Documents[J]. International Journal on Document Analysis and Recognition, 2005, 7(4): [31] SMITH R. History of the Tesseract OCR Engine: What Worked and What Didn t[a]. Proc. of SPIE-IS&T Electronic Imaging, Document Recognition and Retrieval XX[C], Burlingame: SPIE- IS&T, 2013:

65 [32] KNUTH D E. The TEXbook[M]. Reading: Addison-Wesley, [33] CORMEN T H, LEISERSON C E, RIVEST R L,. [M]. :, [34] American Mathematical Society. AMSFonts 3.04[CP/DK] [35] ZANIBBI R, BLOSTEIN D. Recognition and retrieval of mathematical expressions[j]. International Journal on Document Analysis and Recognition, 2012, 15(4): [36] RAJA A, RAYNER M, SEXTON A, et al. Towards a parser for mathematical formula recognition[a]. Mathematical Knowledge Management, Proceedings[C], Berlin: SPRINGER-VERLAG, 2006: [37] ETO Y, SUZUKI M. Mathematical formula recognition using virtual link network[a]. Proceedings of Sixth International Conference on Document Analysis & Recognition[C], Washington: IEEE Computer Society, 2001: [38],,,. [J]., 2008, 44(16): [39] BLOSTEIN D, GRBAVEC A. Recognition of Mathematical Notation[A]. Handbook on Optical Character Recognition and Document Image Analysis[M], Singapore: World Scientific, 1997: [40] SUZUKI M. Character and Symbol Image Database InftyCDB[DB/OL]. inftyproject.org/en/database.html,

66 48

68 50

69 A Otsu Sauvola A.1 D m n t 256 m n A (t) 1 = {(i, j) m n D(i, j) t} (A.1) A (t) 2 = {(i, j) m n D(i, j) > t} (A.2) n (t) 1 = A (t) 1, n (t) 2 = A (t) 2 µ (t) 1 = (i,j) A (t) 1 t D(i, j) max(n (t) 1, 1) σ 2 t =, µ (t) 2 = (i,j) A (t) 2 max(n (t) 2, 1) D(i, j), µ = (i,j) m n m n D(i, j) (A.3) n (t) 1 (µ (t) n (t) 1 + n (t) 1 µ) 2 n (t) 2 + (µ (t) 2 n (t) 1 + n (t) 2 µ) 2 (A.4) 2 σt 2 0 = max t 256 σ2 t, t 0 D Otsu (A.5) Otsu m n Otsu Θ(mn) A.2 D m n ω k [0.2, 0.5] (i, j) m n (D(y, x)) i ω 2 <y i+ ω 2,j ω 2 <x j+ ω 2 m(i, j) s(i, j) ( ( )) s(i, j) T (i, j) = m(i, j) 1 + k T D Sauvola Sauvola ω,k (D) (A.6) 51

70 Sauvola ω ω 2 [18] Θ(mn) 52

71 B Sauvola B.1 D : m n Z D I : Z Z Z (k, l) i k j l D(i, j) 4 B.1 I D : m n Z x 1, x 2, y 1, y 2 Z x 1 < x 2, y 1 < y 2 D(i, j) = x 1 <j x 2 y 1 <i y 2 D(i, j) = I(y 2, x 2 ) I(y 2, x 1 ) I(y 1, x 2 ) + I(y 1, x 1 ) x 1 <j x 2 y 1 <i y 2 x 1 <j x 2 i y 2 = D(i, j) D(i, j) j x 2 i y 2 = D(i, j) j x 2 i y 2 (B.1) 1 D(i, j) (B.2) x 1 <j x 2 i y D(i, j) D(i, j) D(i, j) j x 1 j x 2 j x 1 i y 2 i y 1 i y 1 D(i, j) j x 1 i y 2 D(i, j) + j x 2 i y 1 D(i, j) j x 1 i y 1 (B.3) (B.4) = I(y 2, x 2 ) I(y 2, x 1 ) I(y 1, x 2 ) + I(y 1, x 1 ) (B.5) 53

72 i < 0 j < 0 I(i, j) = 0 Θ(mn) m n B.1 I D : m n Z i m, j n I(i, j) = I(i, j 1) + I(i 1, j) + D(i, j) I(i 1, j 1) (B.6) D(i, j) = I(i, j) I(i, j 1) I(i 1, j) + I(i 1, j 1) 54

73 C C.1 F P(Z Z) (x 0, y 0 ),..., (x n, y n ) F (x 0, y 0 ) = (x, y), (x n, y n ) = (z, w) i = 1,..., n x i x i 1 1, y i y i 1 1 (C.1) (x, y) (z, w) F (x 0, y 0 ),..., (x n, y n ) (x, y) (z, w) = {((x, y), (z, w)) F F (x, y) (z, w) } (C.2) F C.1 F P(Z Z) F (x, y) F (x, y) (x, y) (x, y) (x, y) (x, y) (x, y) (x, y) (x, y) (z, w) (x, y) (z, w) (x 0, y 0 ),..., (x n, y n ) (x n, y n ),..., (x 0, y 0 ) (z, w) (x, y) (z, w) (x, y) (z, w) (x, y) (x, y) (z, w), (z, w) (u, v) (x, y) (z, w) (x 0, y 0 ),..., (x n, y n ) (z, w) (u, v) (z 0, w 0 ),..., (z m, w m ) (x 0, y 0 ),..., (x n, y n ) = (z 0, w 0 ),..., (z m, w m ) (x, y) (u, v) (x, y) (u, v) (x, y) (u, v) C.2 m, n Z + F m n F F F F / F 55

74 C.2 m, n Z + F m n F (i, j) m n (i, j) = (m, 0) D i,j = {(y, x) F (y, x) (i, j)} (C.3) C i,j = D i,j / i,j (C.4) E i,j = {C C i,j {(i 1, j 1), (i 1, j), (i 1, j + 1), (i, j 1)} C = } (C.5) i,j D i,j C 0,0 = (i, j) m n (i + 1, 0), j = n 1 (k, l) = (i, j + 1), j n 1 E i,j { {(i, j)} C Ci,j \E i,j C } C k,l = C i,j, (i, j) F (C.6), (i, j) / F D 0,0 = C 0,0 = (i, j) / F D k,l = D i,j C k,l = C i,j (i, j) F D k,l = D i,j {(i, j)} (y, x) D i,j D k,l (i, j) (y, x) (i, j) {(i 1, j 1), (i 1, j), (i 1, j+1), (i, j 1)} (y, x) {(i 1, j 1), (i 1, j), (i 1, j + 1), (i, j 1)} D i,j (i 1, j 1), (i 1, j), (i 1, j + 1), (i, j 1) D i,j D i,j D k,l (i, j) D k,l (i, j) {(i, j)} C Ci,j,{(i 1,j 1),(i 1,j),(i 1,j+1),(i,j 1)} C C D k,l (y, x) (i, j) D i,j \ {(i 1, j 1), (i 1, j), (i 1, j + 1), (i, j 1)} (y, x) D k,l D i,j C m,0 F C.1 makeset((i, j, k j)) C {(i, j),..., (i, k 1)} union(c 1, C 2 ) C C 1 C 2 [33] Ω(mn) O (mnα (mn)) α [33] 56

75 C.1: : F m n : F C : lastlt last 1 2 C ; 3 i m 4 lastlt ; 5 j n 6 (i, j) / F 7 lastlt last[j], last[j] ; 8 9 c lastlt; 10 k j; 11 k < n (i, k) F 12 i 0 last[k] 13 c = 14 c last[k]; union(c, last[k]); 17 k k + 1; 18 i 0 k n last[k] 19 c = 20 c last[k]; union(c, last[k]); 23 c 24 union(c, makeset((i, j, k j))); c makeset((i, j, k j)); 27 l {j,..., k 1} 28 last[l] c; 29 j k 1; 57

76 58

77 D MathOCR MathOCR GNU GPL Subversion svn checkout svn :// svn.code.sf.net/p/mathocr/code/ mathocr - code Git git clone https :// github.com/chungkwong/mathocr.git 59

78 60

79 61

图片中印刷体数学公式的自动识别

图片中印刷体数学公式的自动识别 L A TEX 1968 [1] InftyReader[2] [3] [4] 5 10 [4, 5] [6] [7] [7] [7] [7] [7] Zernike [7] [1] [1] [1] [7] [7] [8] [6] [1] [9] [10] [11] [12] : Y = 0.309R + 0.609G + 0.082B R G B Y Y = 316R + 624G + 84B 1024