Abstract

A new technique for determining the distortion parameters (location, orientation, and scale) of general 2-D objects is introduced. It uses the straight-line Hough transform as a feature space. The technique is very efficient and robust, since the dimensionality of the feature space is low and since it uses input images directly (with no preprocessing such as segmentation). Because the feature space allows separation of translation and rotation effects, a hierarchical algorithm to discriminate among objects and to detect object rotation and translation using projections and slices of the Hough space is possible.

© 1988 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. P. V. C. Hough, “Method and Means for Recognizing Complex Patterns,” U.S. Patent3,069,654 (1962).
  2. R. O. Duda, P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Pictures,” Commun. Assoc. Comput. Mach. 15, 11 (1972).
  3. D. H. Ballard, C. M. Brown, Computer Vision (Prentice-Hall, Englewood, NJ, 1982).
  4. C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).
  5. S. Tsuji, F. Matsumoto, “Detection of Ellipses by a Modified Hough Transformation,” IEEE Trans. Comput. COM-27, 777 (1978).
    [CrossRef]
  6. H. Wechsler, J. Sklansky, “Finding the Rib Cage in Chest Radiographs,” Pattern Recognition 9, 21 (1977).
    [CrossRef]
  7. D. H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition 13, 111 (1981).
    [CrossRef]
  8. D. H. Ballard, D. Sabbah, “Viewer Independent Shape Recognition,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 653 (1983).
    [CrossRef]
  9. T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
    [CrossRef]
  10. L. S. Davis, “Hierarchical Generalized Hough Transforms and Line-Segment Based Generalized Hough Transforms,” Pattern Recognition 15, 277 (1982).
    [CrossRef]
  11. C. M. Brown, “Inherent Bias and Noise in Hough Transform,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 493 (1983).
    [CrossRef]
  12. P. M. Merlin, D. J. Farber, “A Parallel Mechanism for Detecting Curves in Pictures,” IEEE Trans. Comput. COM-24, 96 (1975).
    [CrossRef]
  13. H. Li, M. A. Lavin, R. J. LeMaster, “Fast Hough Transform: A Hierarchical Approach,” Comput. Vision Graphics Image Process. 36, 139 (1986).
    [CrossRef]
  14. G. Eichman, B. Z. Dong, “Coherent Optical Production of the Hough Transform,” Appl. Opt. 22, 830 (1983).
    [CrossRef]
  15. G. R. Gindi, A. F. Gmitro, “Optical Feature Extraction via the Radon Transform,” Opt. Eng. 23, 499 (1984).
    [CrossRef]
  16. W. H. Steier, R. K. Shori, “Optical Hough Transform,” Appl. Opt. 25, 2734 (1986).
    [CrossRef] [PubMed]
  17. R. Krishnapuram, D. Casasent, “Optical Associative Processor for General Linear Transformations,” Appl. Opt. 26, 3641 (1987).
    [CrossRef] [PubMed]
  18. P. Ambs, S. H. Lee, Q. Tian, Y. Fainman, “Optical Implementation of the Hough Transform by a Matrix of Holograms,” Appl. Opt. 25, 4039 (1986).
    [CrossRef] [PubMed]
  19. R. Krishnapuram, D. Casasent, “Hough Space Transformations for Discrimination and Distortion Estimation,” Comput. Vision Graphics Image Process. 38, 299 (1987).
    [CrossRef]
  20. D. Casasent, R. Krishnapuram, “Curved Object Location by Hough Transformations and Inversions,” Pattern Recognition 20, 181 (1987).
    [CrossRef]
  21. W. T. Rhodes, “Acousto-Optic Signal Processing: Convolution and Correlation,” Proc. IEEE 69, 65 (1981).
    [CrossRef]

1987

R. Krishnapuram, D. Casasent, “Optical Associative Processor for General Linear Transformations,” Appl. Opt. 26, 3641 (1987).
[CrossRef] [PubMed]

R. Krishnapuram, D. Casasent, “Hough Space Transformations for Discrimination and Distortion Estimation,” Comput. Vision Graphics Image Process. 38, 299 (1987).
[CrossRef]

D. Casasent, R. Krishnapuram, “Curved Object Location by Hough Transformations and Inversions,” Pattern Recognition 20, 181 (1987).
[CrossRef]

1986

1984

G. R. Gindi, A. F. Gmitro, “Optical Feature Extraction via the Radon Transform,” Opt. Eng. 23, 499 (1984).
[CrossRef]

T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
[CrossRef]

1983

D. H. Ballard, D. Sabbah, “Viewer Independent Shape Recognition,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 653 (1983).
[CrossRef]

G. Eichman, B. Z. Dong, “Coherent Optical Production of the Hough Transform,” Appl. Opt. 22, 830 (1983).
[CrossRef]

C. M. Brown, “Inherent Bias and Noise in Hough Transform,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 493 (1983).
[CrossRef]

1982

L. S. Davis, “Hierarchical Generalized Hough Transforms and Line-Segment Based Generalized Hough Transforms,” Pattern Recognition 15, 277 (1982).
[CrossRef]

1981

D. H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition 13, 111 (1981).
[CrossRef]

W. T. Rhodes, “Acousto-Optic Signal Processing: Convolution and Correlation,” Proc. IEEE 69, 65 (1981).
[CrossRef]

1978

S. Tsuji, F. Matsumoto, “Detection of Ellipses by a Modified Hough Transformation,” IEEE Trans. Comput. COM-27, 777 (1978).
[CrossRef]

1977

H. Wechsler, J. Sklansky, “Finding the Rib Cage in Chest Radiographs,” Pattern Recognition 9, 21 (1977).
[CrossRef]

1975

C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).

P. M. Merlin, D. J. Farber, “A Parallel Mechanism for Detecting Curves in Pictures,” IEEE Trans. Comput. COM-24, 96 (1975).
[CrossRef]

1972

R. O. Duda, P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Pictures,” Commun. Assoc. Comput. Mach. 15, 11 (1972).

Ambs, P.

Ballard, D.

C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).

Ballard, D. H.

D. H. Ballard, D. Sabbah, “Viewer Independent Shape Recognition,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 653 (1983).
[CrossRef]

D. H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition 13, 111 (1981).
[CrossRef]

D. H. Ballard, C. M. Brown, Computer Vision (Prentice-Hall, Englewood, NJ, 1982).

Brown, C. M.

C. M. Brown, “Inherent Bias and Noise in Hough Transform,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 493 (1983).
[CrossRef]

D. H. Ballard, C. M. Brown, Computer Vision (Prentice-Hall, Englewood, NJ, 1982).

Casasent, D.

R. Krishnapuram, D. Casasent, “Optical Associative Processor for General Linear Transformations,” Appl. Opt. 26, 3641 (1987).
[CrossRef] [PubMed]

R. Krishnapuram, D. Casasent, “Hough Space Transformations for Discrimination and Distortion Estimation,” Comput. Vision Graphics Image Process. 38, 299 (1987).
[CrossRef]

D. Casasent, R. Krishnapuram, “Curved Object Location by Hough Transformations and Inversions,” Pattern Recognition 20, 181 (1987).
[CrossRef]

Davis, L.

T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
[CrossRef]

Davis, L. S.

L. S. Davis, “Hierarchical Generalized Hough Transforms and Line-Segment Based Generalized Hough Transforms,” Pattern Recognition 15, 277 (1982).
[CrossRef]

Dong, B. Z.

Duda, R. O.

R. O. Duda, P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Pictures,” Commun. Assoc. Comput. Mach. 15, 11 (1972).

Eichman, G.

Fainman, Y.

Farber, D. J.

P. M. Merlin, D. J. Farber, “A Parallel Mechanism for Detecting Curves in Pictures,” IEEE Trans. Comput. COM-24, 96 (1975).
[CrossRef]

Gindi, G. R.

G. R. Gindi, A. F. Gmitro, “Optical Feature Extraction via the Radon Transform,” Opt. Eng. 23, 499 (1984).
[CrossRef]

Gmitro, A. F.

G. R. Gindi, A. F. Gmitro, “Optical Feature Extraction via the Radon Transform,” Opt. Eng. 23, 499 (1984).
[CrossRef]

Hart, P. E.

R. O. Duda, P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Pictures,” Commun. Assoc. Comput. Mach. 15, 11 (1972).

Harwood, D.

T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
[CrossRef]

Hough, P. V. C.

P. V. C. Hough, “Method and Means for Recognizing Complex Patterns,” U.S. Patent3,069,654 (1962).

Kimme, C.

C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).

Krishnapuram, R.

R. Krishnapuram, D. Casasent, “Optical Associative Processor for General Linear Transformations,” Appl. Opt. 26, 3641 (1987).
[CrossRef] [PubMed]

R. Krishnapuram, D. Casasent, “Hough Space Transformations for Discrimination and Distortion Estimation,” Comput. Vision Graphics Image Process. 38, 299 (1987).
[CrossRef]

D. Casasent, R. Krishnapuram, “Curved Object Location by Hough Transformations and Inversions,” Pattern Recognition 20, 181 (1987).
[CrossRef]

Lavin, M. A.

H. Li, M. A. Lavin, R. J. LeMaster, “Fast Hough Transform: A Hierarchical Approach,” Comput. Vision Graphics Image Process. 36, 139 (1986).
[CrossRef]

Lee, S. H.

LeMaster, R. J.

H. Li, M. A. Lavin, R. J. LeMaster, “Fast Hough Transform: A Hierarchical Approach,” Comput. Vision Graphics Image Process. 36, 139 (1986).
[CrossRef]

Li, H.

H. Li, M. A. Lavin, R. J. LeMaster, “Fast Hough Transform: A Hierarchical Approach,” Comput. Vision Graphics Image Process. 36, 139 (1986).
[CrossRef]

Matsumoto, F.

S. Tsuji, F. Matsumoto, “Detection of Ellipses by a Modified Hough Transformation,” IEEE Trans. Comput. COM-27, 777 (1978).
[CrossRef]

Merlin, P. M.

P. M. Merlin, D. J. Farber, “A Parallel Mechanism for Detecting Curves in Pictures,” IEEE Trans. Comput. COM-24, 96 (1975).
[CrossRef]

Rhodes, W. T.

W. T. Rhodes, “Acousto-Optic Signal Processing: Convolution and Correlation,” Proc. IEEE 69, 65 (1981).
[CrossRef]

Sabbah, D.

D. H. Ballard, D. Sabbah, “Viewer Independent Shape Recognition,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 653 (1983).
[CrossRef]

Shori, R. K.

Silberberg, T. M.

T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
[CrossRef]

Sklansky, J.

H. Wechsler, J. Sklansky, “Finding the Rib Cage in Chest Radiographs,” Pattern Recognition 9, 21 (1977).
[CrossRef]

C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).

Steier, W. H.

Tian, Q.

Tsuji, S.

S. Tsuji, F. Matsumoto, “Detection of Ellipses by a Modified Hough Transformation,” IEEE Trans. Comput. COM-27, 777 (1978).
[CrossRef]

Wechsler, H.

H. Wechsler, J. Sklansky, “Finding the Rib Cage in Chest Radiographs,” Pattern Recognition 9, 21 (1977).
[CrossRef]

Appl. Opt.

Commun. Assoc. Comput. Mach.

C. Kimme, D. Ballard, J. Sklansky, “Finding Circles by an Array of Accumulators,” Commun. Assoc. Comput. Mach. 18, 120 (1975).

R. O. Duda, P. E. Hart, “Use of the Hough Transform to Detect Lines and Curves in Pictures,” Commun. Assoc. Comput. Mach. 15, 11 (1972).

Comput. Vision Graphics Image Process.

R. Krishnapuram, D. Casasent, “Hough Space Transformations for Discrimination and Distortion Estimation,” Comput. Vision Graphics Image Process. 38, 299 (1987).
[CrossRef]

H. Li, M. A. Lavin, R. J. LeMaster, “Fast Hough Transform: A Hierarchical Approach,” Comput. Vision Graphics Image Process. 36, 139 (1986).
[CrossRef]

IEEE Trans. Comput.

P. M. Merlin, D. J. Farber, “A Parallel Mechanism for Detecting Curves in Pictures,” IEEE Trans. Comput. COM-24, 96 (1975).
[CrossRef]

S. Tsuji, F. Matsumoto, “Detection of Ellipses by a Modified Hough Transformation,” IEEE Trans. Comput. COM-27, 777 (1978).
[CrossRef]

IEEE Trans. Pattern Anal. Mach. Intell.

D. H. Ballard, D. Sabbah, “Viewer Independent Shape Recognition,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 653 (1983).
[CrossRef]

C. M. Brown, “Inherent Bias and Noise in Hough Transform,” IEEE Trans. Pattern Anal. Mach. Intell. PAMI-5, 493 (1983).
[CrossRef]

Opt. Eng.

G. R. Gindi, A. F. Gmitro, “Optical Feature Extraction via the Radon Transform,” Opt. Eng. 23, 499 (1984).
[CrossRef]

Pattern Recognition

D. Casasent, R. Krishnapuram, “Curved Object Location by Hough Transformations and Inversions,” Pattern Recognition 20, 181 (1987).
[CrossRef]

T. M. Silberberg, L. Davis, D. Harwood, “An Iterative Hough Procedure for Three Dimensional Object Recognition,” Pattern Recognition 17, 621 (1984).
[CrossRef]

L. S. Davis, “Hierarchical Generalized Hough Transforms and Line-Segment Based Generalized Hough Transforms,” Pattern Recognition 15, 277 (1982).
[CrossRef]

H. Wechsler, J. Sklansky, “Finding the Rib Cage in Chest Radiographs,” Pattern Recognition 9, 21 (1977).
[CrossRef]

D. H. Ballard, “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition 13, 111 (1981).
[CrossRef]

Proc. IEEE

W. T. Rhodes, “Acousto-Optic Signal Processing: Convolution and Correlation,” Proc. IEEE 69, 65 (1981).
[CrossRef]

Other

P. V. C. Hough, “Method and Means for Recognizing Complex Patterns,” U.S. Patent3,069,654 (1962).

D. H. Ballard, C. M. Brown, Computer Vision (Prentice-Hall, Englewood, NJ, 1982).

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 (5)

Fig. 1
Fig. 1

Block diagram of the proposed hierarchical processor.

Fig. 2
Fig. 2

Images of the five aircraft types used in their reference orientation: (a) DC10; (b) B57; (c) Mig; (d) F105; (e) Mirage.

Fig. 3
Fig. 3

Hough transform of the Mirage (a) centered at the origin, (b) shifted upward by 60 pixels, and (c) rotated about the origin by 120°.

Fig. 4
Fig. 4

(a) Hough transform of the centered Mirage after thresholding at 5; (b) projection of the transform in (a); (c) thresholded HT of the Mirage shifted upward by 60 pixels; (d) projection of the HT in (c); (e) thresholded HT of the Mirage rotated about the origin by 120°; and (f) projection of the HT in (e).

Fig. 5
Fig. 5

Optical processor to evaluate the dot product (vector inner product) of the Hough transform H(θ,p) and the distorted Hd(θ,p) for different distortion parameter combinations.

Tables (3)

Tables Icon

Table I Selected Intraclass Multiple-Distortion Test Results

Tables Icon

Table II Selected Multiclass Multiple-Distortion Recognition Test Results

Tables Icon

Table III Selected Intraclass Multiple-Distortion Test Results with Noise with σn = 0.2 Added

Equations (9)

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

p = x cos θ + y sin θ ,
H s ( θ , p / s ) = H ( θ , p ) .
H r ( θ , p ) = H ( θ - ϕ , p ) ,
H ( θ , p ) = { H t [ θ , p + t cos ( θ - α ) ] if p + t cos ( θ - α ) 0 , H t [ θ + π , - p - t cos ( θ - α ) ] if p + t cos ( θ - α ) < 0 ,
t = x 0 2 + y 0 2 ;             α = tan - 1 ( y 0 / x 0 ) .
H ( θ , p ) = { H d { θ + ϕ , ( 1 / s ) [ p + t cos ( θ - α ) ] } if p + t cos ( θ - α ) 0 , H d { α + ϕ + π , ( 1 / s ) [ - p - t cos ( θ - α ) ] } if p + t cos ( θ - α ) < 0.
t i = t cos ( θ i + ϕ 0 - α ) ]             i = 1 , 2 ,
t i = x 0 cos ( θ i + ϕ ) + y 0 sin ( θ i + ϕ )             i = 1 , 2.
SNR = N b N n 1 + N n 2 ,

Metrics