Skip to main content
SpringerLink
Log in

Building a Weighted Graph to Avoid Obstacles from an Image of the Environment

  • Conference paper
  • First Online:
Advances in Computer Vision (CVC 2019)

Part of the book series: Advances in Intelligent Systems and Computing ((AISC,volume 944))

Included in the following conference series:

  • 2210 Accesses

Abstract

In robot pathfinding problems, the accuracy and efficiency of the solution path is dependent on the representation of the environment. While many local navigation systems describe pathfinding with limited information, there has been a lack of research on developing a global representation of an environment with image processing techniques. The described algorithm constructs a bidirectional weighted graph representation from an aerial input image designed to not intersect with obstacles in that image. The algorithm is structured as a four-stage pipeline, where each stage uses existing or modified algorithms. To the best of our knowledge, this algorithm is unique in the construction of a well understood representation of an environment from an aerial input image. Future work could improve algorithm runtime and overall accuracy of the output graph.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution
Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 129.00
Price excludes VAT (USA)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 169.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

References

  1. Achanta, R., Estrada, F., Wils, P., Süsstrunk, S.: Salient region detection and segmentation. In: International conference on Computer Vision Systems, pp. 66–75. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-79547-6_7

  2. Algfoor, Z.A., Sunar, M.S., Kolivand, H.: A comprehensive study on pathfinding techniques for robotics and video games. Int. J. Comput. Games Technol. 2015, 1148–1148. Hindawi Publishing Corp. (2015). https://doi.org/10.1155/2015/736138

    Article  Google Scholar 

  3. Andrew, A.: Another efficient algorithm for convex hulls in two dimension. Inf. Process. Lett. 9(5), 216–219. Elsevier (1979). https://doi.org/10.1016/0020-0190(79)90072-3

    Article  Google Scholar 

  4. Chen, D., Wang, H.: A new algorithm for computing visibility graphs of polygonal obstacles in the plane. J. Comput. Geom. 6(1), 316–345 (2015). https://doi.org/10.20382/jocg.v6i1a14

    Article  MathSciNet  MATH  Google Scholar 

  5. Gehrig, K.S., Stein, J.F.: Collision avoidance using elastic bands for an autonomous car. Research Institute DaimlerChrysler AG (2003). http://www.lehre.dhbw-stuttgart.de/~sgehrig/resume/papers/ias.pdf

  6. Liu, L., Fieguth, P., Kuang, G.: Sorted random projections for robust texture classification. In: International Conference on Computer Vision, pp. 391–398. IEEE (2011)

    Google Scholar 

  7. Kiy, K.I.: Segmentation and detection of contrast objects and their application in robot navigation. In: Pattern Recognition and Image Analysis, vol. 25, no. 2, pp. 338–346. Springer, Heidelberg (2015). https://doi.org/10.1134/S1054661815020145

    Article  Google Scholar 

  8. Scharfenberger, C., Chung, A.G., Wong, A., Clausi, D.A.: Salient region detection using self-guided statistical non-redundancy in natural images. In: IEEE Access, vol. 4, pp. 48–60. IEEE (2015). https://doi.org/10.1109/ACCESS.2015.2502842

    Article  Google Scholar 

  9. Shafait, F., Keysers, D., Breuel, T.M.: Efficient implementation of local adaptive thresholding techniques using integral images. In: Proceedings of the SPIE Document Recognition and Retrieval XV, vol. 6815. SPIE (2008). https://doi.org/10.1117/12.767755

  10. Sidorova, V.S.: Global segmentation of textural images on the basis of hierarchical clusterization by predetermined cluster separability. In: Pattern Recognition and Image Analysis, vol. 25, no. 3, pp. 541–546. Springer, Heidelberg (2015). https://doi.org/10.1134/S1054661815030232

    Article  Google Scholar 

  11. Yu. L.: Vehicle extraction using histogram and genetic algorithm based fuzzy image segmentation from high resolution UAV aerial imagery. In: The International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences, vol. 37. Citeseer (2008)

    Google Scholar 

Download references

Acknowledgment

We would like to thank Elmhurst College for the opportunity to conduct this research project.

Author information

Authors and Affiliations

  1. Elmhurst College, Elmhurst, IL, 60102, USA

    Kevin G. Prehn & John M. Jeffrey

Authors
  1. Kevin G. Prehn
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. John M. Jeffrey
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to Kevin G. Prehn or John M. Jeffrey .

Editor information

Editors and Affiliations

  1. Saga University, Saga, Saga, Japan

    Kohei Arai

  2. The Science and Information (SAI) Organization, Bradford, West Yorkshire, UK

    Supriya Kapoor

Rights and permissions

Reprints and permissions

Copyright information

© 2020 Springer Nature Switzerland AG

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Prehn, K.G., Jeffrey, J.M. (2020). Building a Weighted Graph to Avoid Obstacles from an Image of the Environment. In: Arai, K., Kapoor, S. (eds) Advances in Computer Vision. CVC 2019. Advances in Intelligent Systems and Computing, vol 944. Springer, Cham. https://doi.org/10.1007/978-3-030-17798-0_34

Download citation

Publish with us

Policies and ethics

Search

Navigation