Parallel Monte Carlo search for Hough Transform.

Journal article


Lopes, Raul, Franqueira, Virginia N. L., Reid, Ivan D. and Hobson, Peter 2017. Parallel Monte Carlo search for Hough Transform. Journal of Physics: Conference Series. https://doi.org/10.1088/1742-6596/898/7/072052
AuthorsLopes, Raul, Franqueira, Virginia N. L., Reid, Ivan D. and Hobson, Peter
Abstract

We investigate the problem of line detection in digital image processing and in special how state of the art algorithms behave in the presence of noise and whether CPU efficiency can be improved by the combination of a Monte Carlo Tree Search, hierarchical space decomposition, and parallel computing. The starting point of the investigation is the method introduced in 1962 by Paul Hough for detecting lines in binary images. Extended in the 1970s to the detection of space forms, what came to be known as Hough Transform (HT) has been proposed, for example, in the context of track fitting in the LHC ATLAS and CMS projects. The Hough Transform transfers the problem of line detection, for example, into one of optimization of the peak in a vote counting process for cells which contain the possible points of candidate lines. The detection algorithm can be computationally expensive both in the demands made upon the processor and on memory. Additionally, it can have a reduced effectiveness in detection in the presence of noise. Our first contribution consists in an evaluation of the use of a variation of the Radon Transform as a form of improving theeffectiveness of line detection in the presence of noise. Then, parallel algorithms for variations of the Hough Transform and the Radon Transform for line detection are introduced. An algorithm for Parallel Monte Carlo Search applied to line detection is also introduced. Their algorithmic complexities are discussed. Finally, implementations on multi-GPU and multicore architectures are discussed.

We investigate the problem of line detection in digital image processing and in special how
state of the art algorithms behave in the presence of noise and whether CPU efficiency can be
improved by the combination of a Monte Carlo Tree Search, hierarchical space decomposition,
and parallel computing.
The starting point of the investigation is the method introduced in 1962 by Paul Hough for
detecting lines in binary images. Extended in the 1970s to the detection of space forms, what
came to be known as Hough Transform (HT) has been proposed, for example, in the context of
track fitting in the LHC ATLAS and CMS projects. The Hough Transform transfers the problem
of line detection, for example, into one of optimization of the peak in a vote counting process
for cells which contain the possible points of candidate lines. The detection algorithm can
be computationally expensive both in the demands made upon the processor and on memory.
Additionally, it can have a reduced effectiveness in detection in the presence of noise.
Our first contribution consists in an evaluation of the use of a variation of the Radon
Transform as a form of improving theeffectiveness of line detection in the presence of noise. Then, parallel algorithms for variations of the Hough Transform and the Radon Transform for line detection are introduced. An algorithm for Parallel Monte Carlo Search applied to line detection is also introduced. Their algorithmic complexities are discussed. Finally, implementations on multi-GPU and multicore architectures are discussed.

KeywordsImage processing; Parallel computing; Computer performance; Computing
Year2017
JournalJournal of Physics: Conference Series
PublisherIOP Publishing Ltd
ISSN17426588
17426596
Digital Object Identifier (DOI)https://doi.org/10.1088/1742-6596/898/7/072052
Web address (URL)http://hdl.handle.net/10545/621978
hdl:10545/621978
Publication datesNov 2017
Publication process dates
Deposited27 Nov 2017, 09:51
Rights

Archived with thanks to Journal of Physics: Conference Series

ContributorsBrunel University London and University of Derby
File
File Access Level
Open
File
File Access Level
Open
Permalink -

https://repository.derby.ac.uk/item/94qz9/parallel-monte-carlo-search-for-hough-transform

Download files

  • 11
    total views
  • 1
    total downloads
  • 1
    views this month
  • 0
    downloads this month

Export as

Related outputs

Integration and evaluation of QUIC and TCP-BBR in longhaul science data transfers
Lopes, Raul H. C., Franqueira, Virginia N. L. and Duncan, Rand 2019. Integration and evaluation of QUIC and TCP-BBR in longhaul science data transfers. EPJ Web of Conferences. 214, p. 08026. https://doi.org/10.1051/epjconf/201921408026
Privacy verification of photoDNA based on machine learning
Nadeem, Muhammad Shahroz, Franqueira, Virginia N. L. and Zhai, Xiaojun 2019. Privacy verification of photoDNA based on machine learning. in: The Institution of Engineering and Technology (IET).
Behavioural Digital Forensics Model: Embedding Behavioural Evidence Analysis into the Investigation of Digital Crimes
Al Mutawa, Noora, Bryce, Joanne, Franqueira, Virginia N.L., Marrington, Andrew and Read, Janet C. 2018. Behavioural Digital Forensics Model: Embedding Behavioural Evidence Analysis into the Investigation of Digital Crimes. Digital Investigation. https://doi.org/10.1016/j.diin.2018.12.003
Analytical tools for blockchain: review, taxonomy and open challenges.
Balaskas, Anastasios and Franqueira, Virginia N. L. 2018. Analytical tools for blockchain: review, taxonomy and open challenges. IEE Explore. https://doi.org/10.1109/CyberSecPODS.2018.8560672
Blockchain-Based Distributed Marketplace.
Kabi, Oliver R. and Franqueira, Virginia N. L. 2019. Blockchain-Based Distributed Marketplace. in: Springer Nature.
A survey of deep learning solutions for multimedia visual content analysis.
Nadeem, Muhammad Shahroz, Franqueira, Virginia N. L., Zhai, Xiaojun and Kurugollu, Fatih 2019. A survey of deep learning solutions for multimedia visual content analysis. IEEE Access. https://doi.org/10.1109/ACCESS.2019.DOI
A tutorial introduction to IoT design and prototyping with examples.
Meruje, Manuel, Sumaila, Musa, Franqueira, Virginia N. L., Freire, Mario M. and Inacio, Pedro R. M. 2018. A tutorial introduction to IoT design and prototyping with examples. in: Wiley-IEEE Press.
Cloud forensics and security
Franqueira, Virginia N. L., Lopes, Raul, Jones, Andrew and Storer, Tim 2017. Cloud forensics and security. SpringerOpen.
On Locky ransomware, Al Capone and Brexit
MacRae, John and Franqueira, Virginia N. L. 2018. On Locky ransomware, Al Capone and Brexit. in: Springer.
Man-In-The-Middle attacks in Vehicular Ad-Hoc Networks: Evaluating the impact of attackers’ strategies.
Ahmad, F., Adnane, Asma, Franqueira, Virginia N. L., Kurugollu, Fatih and Liu, Lu 2018. Man-In-The-Middle attacks in Vehicular Ad-Hoc Networks: Evaluating the impact of attackers’ strategies. Sensors. 18 (11), p. 4040. https://doi.org/10.3390/s18114040
TEAM: A trust evaluation and management framework in context-enabled vehicular ad-hoc networks.
Ahmad, F., Franqueira, Virginia N. L. and Adnane, Asma 2018. TEAM: A trust evaluation and management framework in context-enabled vehicular ad-hoc networks. IEEE Access. https://doi.org/10.1109/ACCESS.2018.2837887
Investigation of indecent images of children cases: Challenges and suggestions collected from the trenches.
Franqueira, Virginia N. L., Bryce, Joanne, Al Mutawa, Noora and Marrington, Andrew 2017. Investigation of indecent images of children cases: Challenges and suggestions collected from the trenches. Digital Investigation. https://doi.org/10.1016/j.diin.2017.11.002
Verifiable public key encryption scheme with equality test in 5G networks
Xu, Yan, Wang, Ming, Zhong, Hong, Cui, Jie, Liu, Lu and Franqueira, Virginia N. L. 2017. Verifiable public key encryption scheme with equality test in 5G networks. IEEE Access. https://doi.org/10.1109/ACCESS.2017.2716971
Special issue on cyberharassment investigation: Advances and trends
Bryce, Joanne, Franqueira, Virginia N. L. and Marrington, Andrew 2016. Special issue on cyberharassment investigation: Advances and trends. Journal of Digital Forensics, Security and Law (JDFSL).
Faith in vehicles: A set of evaluation criteria for trust management in vehicular ad-hoc network
Ahmad, F., Hall, Jordan, Adnane, Asma and Franqueira, Virginia N. L. 2017. Faith in vehicles: A set of evaluation criteria for trust management in vehicular ad-hoc network. IEEE.
Forensically-sound analysis of security risks of using local password managers
Gray, Joshua, Franqueira, Virginia N. L. and Yu, Yijun 2016. Forensically-sound analysis of security risks of using local password managers. IEEE Computer Society. https://doi.org/10.1109/REW.2016.034
Forensic investigation of cyberstalking cases using Behavioural Evidence Analysis
Al Mutawa, Noora, Bryce, Joanne, Marrington, Andrew and Franqueira, Virginia N. L. 2016. Forensic investigation of cyberstalking cases using Behavioural Evidence Analysis. Digital Investigation. https://doi.org/10.1016/j.diin.2016.01.012
To flip or not to flip: a critical interpretive synthesis of flipped teaching
Franqueira, Virginia N. L. and Tunnicliffe, Peter 2015. To flip or not to flip: a critical interpretive synthesis of flipped teaching. in: Springer International Publishing.
Factors influencing digital forensic investigations: Empirical evaluation of 12 years of Dubai police cases
Al Awadhi, Ibtesam, Read, Janet C., Marrington, Andrew and Franqueira, Virginia N. L. 2015. Factors influencing digital forensic investigations: Empirical evaluation of 12 years of Dubai police cases. Journal of Digital Forensics, Security and Law (JDFSL).
A systematic approach for cyber security in vehicular networks
Ahmad, F., Adnane, Asma and Franqueira, Virginia N. L. 2016. A systematic approach for cyber security in vehicular networks. Journal of Computer and Communications. https://doi.org/10.4236/jcc.2016.416004
Introduction to special issue on risk and trust in embedded critical systems
Rossebø, Judith E. Y., Houmb, Siv H., Georg, Geri, Franqueira, Virginia N. L. and Serpanos, Dimitrios 2014. Introduction to special issue on risk and trust in embedded critical systems. ACM Transactions on Embedded Computing Systems. https://doi.org/10.1145/2659008
Efficient computation of hashes
Lopes, Raul, Franqueira, Virginia N. L. and Hobson, Peter 2014. Efficient computation of hashes. Journal of Physics: Conference Series. https://doi.org/10.1088/1742-6596/513/3/032042
Behavioural evidence analysis applied to digital forensics: An empirical analysis of child pornography cases using P2P networks
Mutawa, Noora Al, Bryce, Joanne, Franqueira, Virginia N. L. and Marrington, Andrew 2015. Behavioural evidence analysis applied to digital forensics: An empirical analysis of child pornography cases using P2P networks. IEEE Computer Society. https://doi.org/10.1109/ARES.2015.49
Challenges of data provenance for cloud forensic investigations
Katilu, Victoria M., Franqueira, Virginia N. L. and Angelopoulou, Olga 2015. Challenges of data provenance for cloud forensic investigations. IEEE Computer Society. https://doi.org/10.1109/ARES.2015.54
Automated analysis of security requirements through risk-based argumentation
Yu, Yijun, Franqueira, Virginia N. L., Than Tun, Thein, Wieringa, Roel J. and Nuseibeh, Bashar 2015. Automated analysis of security requirements through risk-based argumentation. Journal of Systems and Software. https://doi.org/10.1016/j.jss.2015.04.065