Abstract

We describe a new fast, shift-invariant transform, the modified rapid transform (MRT). The MRT combines the well-known rapid transform with preprocessing steps. Computer simulations show that for 1-D binary patterns the MRT with a sufficient number of preprocessing steps may perform shift-invariant one-to-one mapping. The modification is also efficient for 2-D patterns. The MRT can be usefully applied as a preprocessing step in automatic inspection and pattern recognition, where shift invariance, uniqueness, and low computing time is required. As an example, the use of MRT in optical character recognition is discussed.

© 1989 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. H. Reitboeck, T. P. Brody, “A Transformation with Invariance Under Cyclic Permutations for Applications in Pattern Recognition,” Inf. Control 15, 130 (1969).
    [CrossRef]
  2. M. D. Wagh, S. V. Kanetkar, “A Class of Translation Invariant Transforms,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 203 (1977).
    [CrossRef]
  3. A. W. Lohmann, G. P. Weigelt, B. Wirnitzer, “Speckle Masking in Astronomy: Triple Correlation Theory and Applications,” Appl. Opt. 22, 4028 (1983).
    [CrossRef] [PubMed]
  4. H. Burkhardt, “Transformationen zur lageinvarianten Merkmalgewinnung,” Fortschr. -Ber. VDI-Z. Reihe 10 Nr. 7.
  5. MaJunWuCheng-keLuXin-ru, “A Fast Shape Descriptor,” Comput. Vision Graphics Image Process. 34, 282 (1986).
    [CrossRef]
  6. M. K. Hu, “Visual Pattern Recognition by Moment Invariants,” IRE Trans. Inf. Theory IT-8, 179 (1962).
  7. F. L. Alt, “Digital Pattern Recognition by Moments,” in Optical Character Recognition, G. L. Fischer et al., Eds. (Spartan, Washington, DC, 1962), p. 153.
  8. T. E. Southard, “A Method of Recognizing Single Strings of Nontouching Rotated Characters,” M.S. Thesis, Ohio State U., Report AFOSR-TR- 75–0177 (Aug.1974).
  9. G. L. Cash, M. Hatamian, “Optical Character Recognition by the Method of Moments,” Comput. Vision Graphics Image Process. 39, 291 (1987).
    [CrossRef]

1987 (1)

G. L. Cash, M. Hatamian, “Optical Character Recognition by the Method of Moments,” Comput. Vision Graphics Image Process. 39, 291 (1987).
[CrossRef]

1986 (1)

MaJunWuCheng-keLuXin-ru, “A Fast Shape Descriptor,” Comput. Vision Graphics Image Process. 34, 282 (1986).
[CrossRef]

1983 (1)

1977 (1)

M. D. Wagh, S. V. Kanetkar, “A Class of Translation Invariant Transforms,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 203 (1977).
[CrossRef]

1969 (1)

H. Reitboeck, T. P. Brody, “A Transformation with Invariance Under Cyclic Permutations for Applications in Pattern Recognition,” Inf. Control 15, 130 (1969).
[CrossRef]

1962 (1)

M. K. Hu, “Visual Pattern Recognition by Moment Invariants,” IRE Trans. Inf. Theory IT-8, 179 (1962).

Alt, F. L.

F. L. Alt, “Digital Pattern Recognition by Moments,” in Optical Character Recognition, G. L. Fischer et al., Eds. (Spartan, Washington, DC, 1962), p. 153.

Brody, T. P.

H. Reitboeck, T. P. Brody, “A Transformation with Invariance Under Cyclic Permutations for Applications in Pattern Recognition,” Inf. Control 15, 130 (1969).
[CrossRef]

Burkhardt, H.

H. Burkhardt, “Transformationen zur lageinvarianten Merkmalgewinnung,” Fortschr. -Ber. VDI-Z. Reihe 10 Nr. 7.

Cash, G. L.

G. L. Cash, M. Hatamian, “Optical Character Recognition by the Method of Moments,” Comput. Vision Graphics Image Process. 39, 291 (1987).
[CrossRef]

Hatamian, M.

G. L. Cash, M. Hatamian, “Optical Character Recognition by the Method of Moments,” Comput. Vision Graphics Image Process. 39, 291 (1987).
[CrossRef]

Hu, M. K.

M. K. Hu, “Visual Pattern Recognition by Moment Invariants,” IRE Trans. Inf. Theory IT-8, 179 (1962).

Kanetkar, S. V.

M. D. Wagh, S. V. Kanetkar, “A Class of Translation Invariant Transforms,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 203 (1977).
[CrossRef]

Lohmann, A. W.

Reitboeck, H.

H. Reitboeck, T. P. Brody, “A Transformation with Invariance Under Cyclic Permutations for Applications in Pattern Recognition,” Inf. Control 15, 130 (1969).
[CrossRef]

Southard, T. E.

T. E. Southard, “A Method of Recognizing Single Strings of Nontouching Rotated Characters,” M.S. Thesis, Ohio State U., Report AFOSR-TR- 75–0177 (Aug.1974).

Wagh, M. D.

M. D. Wagh, S. V. Kanetkar, “A Class of Translation Invariant Transforms,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 203 (1977).
[CrossRef]

Weigelt, G. P.

Wirnitzer, B.

Appl. Opt. (1)

Comput. Vision Graphics Image Process. (2)

MaJunWuCheng-keLuXin-ru, “A Fast Shape Descriptor,” Comput. Vision Graphics Image Process. 34, 282 (1986).
[CrossRef]

G. L. Cash, M. Hatamian, “Optical Character Recognition by the Method of Moments,” Comput. Vision Graphics Image Process. 39, 291 (1987).
[CrossRef]

Fortschr. -Ber. VDI-Z. (1)

H. Burkhardt, “Transformationen zur lageinvarianten Merkmalgewinnung,” Fortschr. -Ber. VDI-Z. Reihe 10 Nr. 7.

IEEE Trans. Acoust. Speech Signal Process. (1)

M. D. Wagh, S. V. Kanetkar, “A Class of Translation Invariant Transforms,” IEEE Trans. Acoust. Speech Signal Process. ASSP-25, 203 (1977).
[CrossRef]

Inf. Control (1)

H. Reitboeck, T. P. Brody, “A Transformation with Invariance Under Cyclic Permutations for Applications in Pattern Recognition,” Inf. Control 15, 130 (1969).
[CrossRef]

IRE Trans. Inf. Theory (1)

M. K. Hu, “Visual Pattern Recognition by Moment Invariants,” IRE Trans. Inf. Theory IT-8, 179 (1962).

Other (2)

F. L. Alt, “Digital Pattern Recognition by Moments,” in Optical Character Recognition, G. L. Fischer et al., Eds. (Spartan, Washington, DC, 1962), p. 153.

T. E. Southard, “A Method of Recognizing Single Strings of Nontouching Rotated Characters,” M.S. Thesis, Ohio State U., Report AFOSR-TR- 75–0177 (Aug.1974).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (10)

Fig. 1
Fig. 1

Signal flow graph of the rapid transform (RT) with four input components.

Fig. 2
Fig. 2

Empirically determined number of binary patterns separable by RT.

Fig. 3
Fig. 3

Signal flow graph of the modified rapid transform (MRT).

Fig. 4
Fig. 4

Empirically determined number of binary patterns separable by RT, MRT, and the Fourier amplitude spectrum |F|.

Fig. 5
Fig. 5

Signal flow graph of the modified rapid transform MRT(k), with k identical preprocessing steps.

Fig. 6
Fig. 6

Empirically determined number of binary patterns separable by MRT with k preprocessing steps [MRT(k)].

Fig. 7
Fig. 7

Four Original binary patterns (first column) and their MRT transforms using three different neighbor operators. In the second column operator b x . is used. The first two patterns are identical because the operator b x can only destroy symmetry in the x direction, whereas the operator b y destroys symmetry only in the y direction, as shown in the third column. The patterns in the fourth column illustrate that the operator b x y can destroy the symmetry in both directions.

Fig. 8
Fig. 8

Set of 126 characters used for computer simulation of character recognition.

Fig. 9
Fig. 9

Histogram of cross responses with a feature matrix (16 × 8): (a) using RT and (b) using MRT.

Fig. 10
Fig. 10

Histogram of cross responses with reduced feature vector: (a) using RT and (b) using MRT. In (a) eleven pairs of characters could not be distinguished [H(0) = 22]. In (b) all the characters could be separated [H(0) = 0].

Equations (12)

Equations on this page are rendered with MathJax. Learn more.

a m + 2 n s ( r ) = | a m + 2 n s ( r 1 ) + a m + ( 2 n + 1 ) s   ( r 1 ) |   ,
a m + ( 2 n + 1 ) s ( r ) = | a m + 2 n s ( r 1 ) a m + ( 2 n + 1 ) s   ( r 1 ) |   ,
a 0 a 1 a 2 a 3 a 4 a 5 a 6 a 7 ( a 0 a 1 a 2 a 3 ) ( a 2 a 1 a 0 a 3 ) ( a 0 a 3 a 2 a 1 ) ( a 2 a 3 a 0 a 1 ) ( a 1 a 0 a 3 a 2 ) ( a 3 a 0 a 1 a 2 ) ( a 1 a 2 a 3 a 0 ) ( a 3 a 2 a 1 a 0 )   .
( a n ) RT ( a ˜ n ) ;
( a n + k ) RT ( a ˜ n ) .
[ a n   ( j i ) ] RT ( a ˜ n )
a i = b ( a i , a i + 1 , a i + 2 )   .
( a n )   b ( a n ) RT   ( a ˜ n ) , ( a n + k ) b ( a n + k ) RT   ( a ˜ n ) , [ a n ( i j ) ]   b ( a n ) RT   ( a ˜ n ) .
a i = b ( a i , a i + 1 , a i + 2 ) = a i + | a i + 1 a i + 2   | .
b x : a ij = a i j + | a i + 1 , j a i + 2 , j   |   , b y : a ij = a i j + | a i , j + 1 a i , j + 2   |   , b x + y : a ij = a i j + | a i + 1 , j a i + 2 , j   | + | a i , j + 1 a i , j + 2   |   , b x y : a ij = a i j + | a i + 1 , j a i , j + 1   |   .
d k l = i = 1 8 j = 1 16   | M k ( i , j ) M 1 ( i , j )   |   ,
d k l = i = 1 6   | V k   ( i ) V l   ( i )   |   .

Metrics