Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Recent Advances in Recommender Systems and Future Directions Kapitel lesen Erstes Kapitel lesen

2015 | OriginalPaper | Buchkapitel

Enumeration of Shortest Isothetic Paths Inside a Digital Object

verfasst von : Mousumi Dutt, Arindam Biswas, Bhargab B. Bhattacharya

Erschienen in: Pattern Recognition and Machine Intelligence

Verlag: Springer International Publishing

Einloggen

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

search-config
loading …

Abstract

The computation of a shortest isothetic path (SIP) between two points in an object is important in various applications such as robot navigation and VLSI design. However, a SIP between two grid points in a digital object laid on a uniform 2D isothetic square lattice may not be unique. We assume that each discrete path consists of a sequence of consecutive grid edges that starts from the source point and ends at the sink point. In this paper, we present a novel algorithm to calculate the number of such distinct shortest isothetic paths between two given grid points inside a digital object, with time complexity \(O(S/g^2)\), where S is the total number of pixels in the digital object, and g is the grid size. The number of available SIPs also serves as a metric for shape registration.

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren
Vorheriges Kapitel Fast and Accurate Foreground Background Separation for Video Surveillance
Nächstes Kapitel Modified Exemplar-Based Image Inpainting via Primal-Dual Optimization
Literatur
1.
2.
de Berg, M.: On rectilinear link distance. Comput. Geom. Theor. Appl. 1(1), 13–34 (1991)MATHCrossRef
3.
de Berg, M., van Kreveld, M., Nilsson, B.J., Overmars, M.H.: Finding shortest paths in the presence of orthogonal obstacles using a combined \(L_1\) and link metric. In: Gilbert, J.R., Karlsson, R. (eds.) SWAT 1990. LNCS, vol. 447, pp. 213–224. Springer, Heidelberg (1990)
4.
Biswas, A., Bhowmick, P., Bhattacharya, B.B.: TIPS: on finding a tight isothetic polygonal shape covering a 2D object. In: Kalviainen, H., Parkkinen, J., Kaarna, A. (eds.) SCIA 2005. LNCS, vol. 3540, pp. 930–939. Springer, Heidelberg (2005) CrossRef
5.
Biswas, A., Bhowmick, P., Bhattacharya, B.B.: Construction of isothetic covers of a digital object: a combinatorial approach. J. Vis. Commun. Image Represent. 21(4), 295–310 (2010)CrossRef
6.
7.
Clarkson, K.L., Kapoor, S., Vaidya, P.: Rectilinear shortest paths through polygonal obstacles in \(O(n (\log n)^2)\) time. In: SoCG 1987, pp. 251–257. ACM, NY (1987)
8.
Cohen, D.I.A.: Basic Techniques of Combinatorial Theory. Wiley, NY (2007)
9.
Das, P.P.: An algorithm for computing the number of the minimal paths in digital images. Pattern Recognit. Lett. 9(2), 107–116 (1989)MATHCrossRef
10.
Das, P.P.: Counting minimal paths in digital geometry. Pattern Recognit. Lett. 12(10), 595–603 (1991)CrossRef
11.
Dumitrescu, A., Mitchell, J.S.B.: Approximation algorithms for TSP with neighborhoods in the plane. J. Algorithms 48(1), 135–159 (2003)MATHCrossRefMathSciNet
12.
Dutt, M., Biswas, A., Bhowmick, P., Bhattacharya, B.B.: On finding shortest isothetic path inside a digital object. In: Barneva, R.P., Brimkov, V.E., Aggarwal, J.K. (eds.) IWCIA 2012. LNCS, vol. 7655, pp. 1–15. Springer, Heidelberg (2012) CrossRef
13.
Dutt, M., Biswas, A., Bhowmick, P., Bhattacharya, B.B.: On finding a shortest isothetic path and its monotonicity inside a digital object. Ann. Math. Artif. Intell. (2014, in press)
14.
Dutt, M., Biswas, A., Bhowmick, P., Bhattacharya, B.B.: On the family of shortest isothetic paths in a digital object—an algorithm with applications. Comput. Vis. Image Underst. 129, 75–88 (2014)CrossRef
15.
Klette, R., Rosenfeld, A.: Digital Geometry: Geometric Methods for Picture Analysis. Morgan Kaufmann, San Francisco (2004)
16.
Larson, R.C., Li, V.O.: Finding minimum rectilinear distance paths in the presence of barriers. Networks 11, 285–304 (1981)MATHCrossRefMathSciNet
17.
Li, F., Klette, R.: Finding the shortest path between two points in a simple polygon by applying a rubberband algorithm. In: Chang, L.-W., Lie, W.-N. (eds.) PSIVT 2006. LNCS, vol. 4319, pp. 280–291. Springer, Heidelberg (2006) CrossRef
18.
Lozano-Perez, T., Wesley, M.A.: An algorithm for planning collision-free paths among polyhedral obstacles. CACM 22(10), 560–570 (1979)CrossRef
19.
Metadaten
Titel
Enumeration of Shortest Isothetic Paths Inside a Digital Object
verfasst von
Mousumi Dutt
Arindam Biswas
Bhargab B. Bhattacharya
Copyright-Jahr
2015
Buch
Pattern Recognition and Machine Intelligence

Print ISBN: 978-3-319-19940-5

Electronic ISBN: 978-3-319-19941-2

Copyright-Jahr: 2015

DOI
https://doi.org/10.1007/978-3-319-19941-2_11

Premium Partner

    Bildnachweise