Skip to main content

2012 | OriginalPaper | Buchkapitel

Object Location Using the HOUGH Transform

verfasst von : Prof. E. Roy Davies

Erschienen in: Machine Vision Handbook

Verlag: Springer London

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

This chapter considers how best to locate 2D object shapes in digital images. Simple paradigms such as boundary tracking followed by analysis of centroidal shape profiles lack robustness and are incapable of coping with occlusion, breakage or gross shape distortions, whereas the Hough transform readily overcomes these problems as an integral property of its voting schema. This is an important advantage, especially in practical situations such as those where lighting is non-ideal. In addition, the Hough transform is excellent at locating straight lines, circles, ellipses and other well defined shapes: it can even locate arbitrary shapes that are defined by so-called R-tables. The method also has the advantage of being able to make sense of patterns of point features, and is far less computation intensive than the maximal clique graph matching method often used for this purpose. Being a form of spatial matched filter, the Hough transform has high signal-to-noise sensitivity, and for simple shapes is highly efficient, but when applied to arbitrary shapes of variable orientation, size and individual variability, measures have to be taken to limit its computation. Overall, the Hough transform provides a very useful, robust search technique for locating known types of object in digital images.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
1.
Zurück zum Zitat Davies ER (2005) Machine vision: theory, algorithms, practicalities, 3rd edn. Morgan Kaufmann, San Francisco Davies ER (2005) Machine vision: theory, algorithms, practicalities, 3rd edn. Morgan Kaufmann, San Francisco
2.
Zurück zum Zitat Hough PVC (1962) Method and means for recognising complex patterns. US Patent 3069654 Hough PVC (1962) Method and means for recognising complex patterns. US Patent 3069654
3.
Zurück zum Zitat O’Gorman F, Clowes MB (1976) Finding picture edges through collinearity of feature points. IEEE Trans Comput 25:449–456MATHCrossRef O’Gorman F, Clowes MB (1976) Finding picture edges through collinearity of feature points. IEEE Trans Comput 25:449–456MATHCrossRef
4.
Zurück zum Zitat Davies ER (1986) Image space transforms for detecting straight edges in industrial images. Pattern Recogn Lett 4:185–192CrossRef Davies ER (1986) Image space transforms for detecting straight edges in industrial images. Pattern Recogn Lett 4:185–192CrossRef
5.
Zurück zum Zitat Wallace RS (1985) A modified Hough transform for lines. IEEE international conference on computer vision and pattern recognition, San Francisco (11–13 June), pp 665–667 Wallace RS (1985) A modified Hough transform for lines. IEEE international conference on computer vision and pattern recognition, San Francisco (11–13 June), pp 665–667
6.
Zurück zum Zitat Dudani SA, Luk AL (1978) Locating straight-line edge segments on outdoor scenes. Pattern Recogn 10:145–157CrossRef Dudani SA, Luk AL (1978) Locating straight-line edge segments on outdoor scenes. Pattern Recogn 10:145–157CrossRef
7.
Zurück zum Zitat Kimme C, Ballard D, Sklansky J (1975) Finding circles by an array of accumulators. Comm ACM 18:120–122MATHCrossRef Kimme C, Ballard D, Sklansky J (1975) Finding circles by an array of accumulators. Comm ACM 18:120–122MATHCrossRef
8.
Zurück zum Zitat Davies ER (1988) A modified Hough scheme for general circle location. Pattern Recogn Lett 7:37–43CrossRef Davies ER (1988) A modified Hough scheme for general circle location. Pattern Recogn Lett 7:37–43CrossRef
9.
Zurück zum Zitat Davies ER (1987) A high speed algorithm for circular object location. Pattern Recogn Lett 6:323–333CrossRef Davies ER (1987) A high speed algorithm for circular object location. Pattern Recogn Lett 6:323–333CrossRef
10.
Zurück zum Zitat Davies ER, Barker SP (1990) An analysis of hole detection schemes. In: Proceedings of the British machine vision association conference, Oxford (24–27 September), pp 285–290 Davies ER, Barker SP (1990) An analysis of hole detection schemes. In: Proceedings of the British machine vision association conference, Oxford (24–27 September), pp 285–290
11.
Zurück zum Zitat Davies ER (1989) Finding ellipses using the generalised Hough transform. Pattern Recogn Lett 9:87–96CrossRef Davies ER (1989) Finding ellipses using the generalised Hough transform. Pattern Recogn Lett 9:87–96CrossRef
12.
Zurück zum Zitat Tsuji S, Matsumoto F (1978) Detection of ellipses by a modified Hough transform. IEEE Trans Comput 27:777–781CrossRef Tsuji S, Matsumoto F (1978) Detection of ellipses by a modified Hough transform. IEEE Trans Comput 27:777–781CrossRef
13.
Zurück zum Zitat Yuen HK, Illingworth J, Kittler J (1988) Ellipse detection using the Hough transform. In: Proceedings of the 4th Alvey Vision Conference, Manchester, 31 August–2 September, pp 265–271 Yuen HK, Illingworth J, Kittler J (1988) Ellipse detection using the Hough transform. In: Proceedings of the 4th Alvey Vision Conference, Manchester, 31 August–2 September, pp 265–271
14.
Zurück zum Zitat Davies ER (1998) Rapid location of convex objects in digital images. In: Proceedings of the European Signal Processing Conference (EUSIPCO’98), Rhodes, Greece (8–11 Sept.), pp 589–592 Davies ER (1998) Rapid location of convex objects in digital images. In: Proceedings of the European Signal Processing Conference (EUSIPCO’98), Rhodes, Greece (8–11 Sept.), pp 589–592
15.
Zurück zum Zitat Davies ER (1999) Algorithms for ultra-fast location of ellipses in digital images. In: Proceedings of the 7th IEE international conference on image processing and its applications, Manchester (13–15 July), IEE Conference Publication no. 465, pp 542–546 Davies ER (1999) Algorithms for ultra-fast location of ellipses in digital images. In: Proceedings of the 7th IEE international conference on image processing and its applications, Manchester (13–15 July), IEE Conference Publication no. 465, pp 542–546
16.
Zurück zum Zitat Ballard DH, Brown CM (1981) Generalizing the Hough transform to detect arbitrary shapes. Pattern Recogn 13:111–122MATHCrossRef Ballard DH, Brown CM (1981) Generalizing the Hough transform to detect arbitrary shapes. Pattern Recogn 13:111–122MATHCrossRef
17.
Zurück zum Zitat Davies ER (1993) Electronics, noise and signal recovery. Academic, London Davies ER (1993) Electronics, noise and signal recovery. Academic, London
18.
Zurück zum Zitat Davies ER (1987) A new framework for analysing the properties of the generalised Hough transform. Pattern Recogn Lett 6:1–7CrossRef Davies ER (1987) A new framework for analysing the properties of the generalised Hough transform. Pattern Recogn Lett 6:1–7CrossRef
19.
Zurück zum Zitat Bolles RC, Cain RA (1982) Recognizing and locating partially visible objects: the local-feature-focus method. Int J Robotics Res 1(3):57–82CrossRef Bolles RC, Cain RA (1982) Recognizing and locating partially visible objects: the local-feature-focus method. Int J Robotics Res 1(3):57–82CrossRef
20.
Zurück zum Zitat Davies ER (1991) The minimal match graph and its use to speed identification of maximal cliques. Signal Process 22(3):329–343CrossRef Davies ER (1991) The minimal match graph and its use to speed identification of maximal cliques. Signal Process 22(3):329–343CrossRef
21.
Zurück zum Zitat Davies ER (1991) Alternative to abstract graph matching for locating objects from their salient features. Image Vision Comput 9(4):252–261CrossRef Davies ER (1991) Alternative to abstract graph matching for locating objects from their salient features. Image Vision Comput 9(4):252–261CrossRef
22.
Zurück zum Zitat Rosenfeld A (1969) Picture processing by computer. Academic, New YorkMATH Rosenfeld A (1969) Picture processing by computer. Academic, New YorkMATH
23.
Zurück zum Zitat Duda RO, Hart PE (1972) Use of the Hough transformation to detect lines and curves in pictures. Comm ACM 15:11–15CrossRef Duda RO, Hart PE (1972) Use of the Hough transformation to detect lines and curves in pictures. Comm ACM 15:11–15CrossRef
24.
Zurück zum Zitat Gerig G, Klein F (1986) Fast contour identification through efficient Hough transform and simplified interpretation strategy. In: Proceedings of the 8th international conference on pattern recognition, Paris (27–31 October), pp 498–500 Gerig G, Klein F (1986) Fast contour identification through efficient Hough transform and simplified interpretation strategy. In: Proceedings of the 8th international conference on pattern recognition, Paris (27–31 October), pp 498–500
25.
Zurück zum Zitat Stockman GC, Agrawala AK (1977) Equivalence of Hough curve detection to template matching. Comm ACM 20:820–822MATHCrossRef Stockman GC, Agrawala AK (1977) Equivalence of Hough curve detection to template matching. Comm ACM 20:820–822MATHCrossRef
26.
Zurück zum Zitat Sklansky J (1978) On the Hough technique for curve detection. IEEE Trans Comput 27:923–926MATHCrossRef Sklansky J (1978) On the Hough technique for curve detection. IEEE Trans Comput 27:923–926MATHCrossRef
27.
Zurück zum Zitat Xu L, Oja E (1993) Randomized Hough transform (RHT): basic mechanisms, algorithms, and computational complexities. CVGIP Imag Understanding 57(2):131–154CrossRef Xu L, Oja E (1993) Randomized Hough transform (RHT): basic mechanisms, algorithms, and computational complexities. CVGIP Imag Understanding 57(2):131–154CrossRef
28.
Zurück zum Zitat Tsukune H, Goto K (1983) Extracting elliptical figures from an edge vector field. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington, pp 138–141 Tsukune H, Goto K (1983) Extracting elliptical figures from an edge vector field. In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, Washington, pp 138–141
29.
Zurück zum Zitat Basalamah S, Bharath A, McRobbie D (2004) Contrast marginalised gradient template matching. In: Pajdla T, Matas J (eds) 8th European Conference on Computer Vision (ECCV 2004), Prague, Czech Republic. Springer, Berlin, pp 417–429 Basalamah S, Bharath A, McRobbie D (2004) Contrast marginalised gradient template matching. In: Pajdla T, Matas J (eds) 8th European Conference on Computer Vision (ECCV 2004), Prague, Czech Republic. Springer, Berlin, pp 417–429
30.
Zurück zum Zitat Bolles RC (1979) Robust feature matching via maximal cliques. SPIE, 182. In: Proceedings of the technical symposium on imaging applications for automated industrial inspection and assembly, Washington DC (April), pp 140–149 Bolles RC (1979) Robust feature matching via maximal cliques. SPIE, 182. In: Proceedings of the technical symposium on imaging applications for automated industrial inspection and assembly, Washington DC (April), pp 140–149
31.
Zurück zum Zitat Kasif S, Kitchen L, Rosenfeld A (1983) A Hough transform technique for subgraph isomorphism. Pattern Recogn Lett 2:83–88CrossRef Kasif S, Kitchen L, Rosenfeld A (1983) A Hough transform technique for subgraph isomorphism. Pattern Recogn Lett 2:83–88CrossRef
32.
Zurück zum Zitat Davies ER (1988) An alternative to graph matching for locating objects from their salient features. In: Proceedings of the 4th Alvey Vision Conference, Manchester, 31 August–2 September, pp 281–286 Davies ER (1988) An alternative to graph matching for locating objects from their salient features. In: Proceedings of the 4th Alvey Vision Conference, Manchester, 31 August–2 September, pp 281–286
33.
Zurück zum Zitat Davies ER (1992) Locating objects from their point features using an optimised Hough-like accumulation technique. Pattern Recogn Lett 13(2):113–121CrossRef Davies ER (1992) Locating objects from their point features using an optimised Hough-like accumulation technique. Pattern Recogn Lett 13(2):113–121CrossRef
34.
Zurück zum Zitat Xie Y, Ji Q (2002) A new efficient ellipse detection method. In: Proceedings of the 16th International Conference on Pattern Recognition, Québec, Canada, 11–15 August, vol II, pp 957–960 Xie Y, Ji Q (2002) A new efficient ellipse detection method. In: Proceedings of the 16th International Conference on Pattern Recognition, Québec, Canada, 11–15 August, vol II, pp 957–960
35.
Zurück zum Zitat Lei Y, Wong KC (1999) Ellipse detection based on symmetry. Pattern Recogn Lett 20(1):41–47MATHCrossRef Lei Y, Wong KC (1999) Ellipse detection based on symmetry. Pattern Recogn Lett 20(1):41–47MATHCrossRef
36.
Zurück zum Zitat Toennies K, Behrens F, Aurnhammer M (2002) Feasibility of Hough-transform-based iris localisation for real-time application. In: Proceedings of the 16th international conference on pattern recognition, Québec, Canada, 11–15 August, vol II, pp 1053–1056 Toennies K, Behrens F, Aurnhammer M (2002) Feasibility of Hough-transform-based iris localisation for real-time application. In: Proceedings of the 16th international conference on pattern recognition, Québec, Canada, 11–15 August, vol II, pp 1053–1056
37.
38.
Zurück zum Zitat Wu H, Yoshikawa G, Shioyama T, Lao S, Kawade M (2002) Glasses frame detection with 3D Hough transform. In: Proceedings of the 16th international conference on pattern recognition. Québec, Canada, 11–15 August, vol II, pp 346–349 Wu H, Yoshikawa G, Shioyama T, Lao S, Kawade M (2002) Glasses frame detection with 3D Hough transform. In: Proceedings of the 16th international conference on pattern recognition. Québec, Canada, 11–15 August, vol II, pp 346–349
39.
Zurück zum Zitat Schaffalitsky F, Zisserman A (2000) Planar grouping for automatic detection of vanishing lines and points. Image Vision Comput 18(9):647–658CrossRef Schaffalitsky F, Zisserman A (2000) Planar grouping for automatic detection of vanishing lines and points. Image Vision Comput 18(9):647–658CrossRef
40.
Zurück zum Zitat Tuytelaars T, Turina A, van Gool L (2003) Noncombinatorial detection of regular repetitions under perspective skew. IEEE Trans Pattern Anal Mach Intell 25(4):418–432CrossRef Tuytelaars T, Turina A, van Gool L (2003) Noncombinatorial detection of regular repetitions under perspective skew. IEEE Trans Pattern Anal Mach Intell 25(4):418–432CrossRef
41.
Zurück zum Zitat Davies ER, Atiquzzaman M (eds) (1998) Special issue on projection-based transforms. Image Vision Comput 16:9–10 Davies ER, Atiquzzaman M (eds) (1998) Special issue on projection-based transforms. Image Vision Comput 16:9–10
Metadaten
Titel
Object Location Using the HOUGH Transform
verfasst von
Prof. E. Roy Davies
Copyright-Jahr
2012
Verlag
Springer London
DOI
https://doi.org/10.1007/978-1-84996-169-1_18

Neuer Inhalt