This work presents the algorithm for detecting elongated boundaries in an image. The case where boundary can be
approximated by polyline with restricted maximum curvature angle is considered. The task of detecting such boundaries
arises, for instance, during the detection of road markings, construction of a road map by analyzing Earth satellite
images, and detection of crystal dislocations in a single X-ray topo-tomography projection. To find polyline segments an
image is processed by a sliding window and for each window position, a straight line is detected by calculating Fast
Hough transform (FHT). Further, detected segments are grouped by relative position in the image. Segments groups,
covering desired boundaries, are approximated by polylines. The proposed algorithm was used in the problem of road
marking detection to determine the ego-position of an unmanned vehicle on a given vector road map. The algorithm was
tested on real data collected from the front-looking camera of the unmanned vehicle driving at the experimental area
“Kalibr” (Moscow). The precision of road markings lines detector was evaluated as 43%, and the recall as 73%. The mean
absolute positioning error in an experimental run with road marking detection was 0.2 m (Euclidean distance), which is 8
times less than localization error without road marking detection. The algorithm was also tested on remote sensing
images and topo-tomograms.
Key words:
boundary detection, lane detection, elongated dislocations, fast Hough transform, window image analysis
DOI: 10.31857/S0235009220030075
Cite:
Panfilova E. I., Kunina I. A.
Ispolzovanie okonnogo preobrazovaniya khafa dlya poiska protyazhennykh granits na izobrazhenii
[Using window hough transform for detecting elongated boundaries in an image].
Sensornye sistemy [Sensory systems].
2020.
V. 34(4).
P. 340–353 (in Russian). doi: 10.31857/S0235009220030075
References:
- Abramov M.P., Shipitko O.S., Lukoyanov A.S., Panfilova E.I., Kunina I.A., Grigorev A.S. Sistema pozicionirovaniy vnutri zdanii mobilynoi robototechnicheskoi platformu na osnove detekcii kraev [Edge detection based mobile robot indoor localization.] Sensornye systemy [Sensory systems]. 2019. V. 33. № 1. P. 30–43. (in Russian). https://doi.org/10.1134/S0235009219010025
- Kotov A.A., Konovalenko I.A., Nikolaev D.P. Proslezhivanie obektov v videopotoke, optimizirovannoe s pomoschyu bystrogo preobrazovaniya KHafa [Tracking of objects containing multiple concentric arcs in a video stream, optimized with Fast Hough transform] ITiVS. 2015. № 1. P. 56–68 (in Russian).
- Tropin D.V., Shemyakina Y.A., Konovalenko I.A., Faradzhev I.A. O lokalizacii ploskich objektov na izobra zeniych so sloznoi strukturoi proektivnuch iskazenii [Localization of planar objects on the images with complex structure of projective distortion]. Informatsionnye protsessy. 2019. V. 19. № 2. P. 208–229 (in Russian).
- Aliev M., Ershov E.I., Nikolaev D.P. On the use of FHT, its modification for practical applications and the structure of Hough image. ICMV 2018. 2019. V. 11041. https://doi.org/10.1117/12.2522803
- Anil P.N., Natarajan S. A novel approach using active contour model for semi-automatic road extraction from high resolution satellite imagery. 2010 Second International Conference on Machine Learning and Computing. 2010. P. 263–266.
- Bezmaternykh P.V., Nikolaev D.P. A document skew detection method using fast Hough transform. ICMV 2019. 2020. V. 11433. P. 1–6. https://doi.org/10.1117/12.2559069
- Brady M.L., Yong W. Fast parallel discrete approximation algorithms for the Radon transform. Proceedings of the fourth annual ACM symposium on Parallel algorithms and architectures. 1992. P. 91–99.
- Bulatov K.B., Chukalina M.V., Nikolaev D.P. Fast x-ray sum calculation algorithm for computed tomography. Bulletin SUSU MMCS. 2020. V. 13. № 1. P. 95–106. https://doi.org/10.14529/mmp200107
- Canny J. A computational approach to edge detection. IEEE Transactions on pattern analysis and machine intelligence. 1986. № 6. P. 679–698.
- Ding Y., Xu Z., Zhang Y., Sun K. Fast lane detection based on bird’s eye view and improved random sample consensus algorithm. Multimedia Tools and Applications. 2017. V. 76. № 21. P. 22979–22998.
- Ershov E., Terekhin A., Nikolaev D., Postnikov V., Karpen-ko S. Fast Hough transform analysis: pattern deviation from line segment. ICMV 2015. 2015. V. 9875. P. 1–5. https://doi.org/10.1117/12.2228852
- Fan S., Shui P., Zhang Z., Sun Y. SAR image edge detection via directional Bhattacharyya coefficient with its application on image segmentation. Eleventh International Conference on Machine Vision (ICMV 2018). 2019. V. 11041. P. 1104107.
- Hough P.V.C. Machine analysis of bubble chamber pictures. Conf. Proc. 1959. T. 590914. P. 554–558.
- Hough P.V.C. Method and means for recognizing complex patterns. Patent USA. No 3069654. 1962.
- Khanipov T.M. Computational complexity lower bounds of certain discrete Radon transform approximations. arXiv preprint arXiv:1801.01054. 2018.
- Kirthika A., Mookambiga A. Automated road network extraction using artificial neural network. 2011 International Conference on Recent Trends in Information Technology (ICRTIT). 2011. P. 1061–1065.
- Korobov N., Shipitko O., Konovalenko I., Grigoryev A., Chukalina M. SWaP-C based comparison of onboard computers for unmanned vehicles. Proceedings of 14th International Conference on Electromechanics and Robotics “Zavalishin’s Readings”. 2019. Singapore. Springer. V. 154. P. 573–583. https://doi.org/10.1007/978-981-13-9267-2_47
- Kunina I., Panfilova E., Gladkov A. Matching of SAR and optical images by independent referencing to vector map. Eleventh International Conference on Machine Vision (ICMV 2018). 2019. V. 11041. P. 1104102.
- Li Y., Chen L., Huang H., Li X., Xu W., Zheng L., Huang J. Nighttime lane markings recognition based on Canny detection and Hough transform. 2016 IEEE International Conference on Real-time Computing and Robotics (RCAR). 2016. P. 411–415.
- Limonova E.E., Bezmaternykh P.V., Nikolaev D.P., Arlazarov V.V. Slant Rectification in Russian Passport OCR System Using Fast Hough Transform. ICMV 2016. SPIE, July 2017. 2017. V. 10341. ISSN 0277-786X. ISBN 978-15-10611-31-3. P. 1–5. https://doi.org/10.1117/12.2268725
- Limonova E.E., Tropin D.V., Savelev B.I., Mamay I.B., Nikolaev D.P. Mobile and Embedded Fast High Resolution Image Stitching for Long Length Rectangular Monochromatic Objects with Periodic Structure. IC-MV 2017. SPIE, Apr. 2018. 2018. V. 10696. ISBN 978-15-10619-41-8. P. 1–8. https://doi.org/10.1117/12.2310093
- Lopez A., Canero C., Serrat J., Saludes J., Lumbreras F., Graf T. Detection of Lane Markings based on Ridgeness and RANSAC. Proceedings 2005 IEEE Intelligent Transportation Systems. 2005. P. 254–259.
- Ma R., Wang W., Liu S. Extracting roads based on Retinex and improved Canny operator with shape criteria in vague and unevenly illuminated aerial images. Journal of applied remote sensing. 2012. V. 6. № 1. C. 063610.
- Mousavi S.M.H., Lyashenko V., Prasath S. Analysis of a robust edge detection system in different color spaces using color and depth images. Компьютерная оптика. 2019. V. 43. № 4.
- Mukhopadhyay P., Chaudhuri B.B. A survey of Hough Transform. Pattern Recognition. 2015. V. 48. № 3. P. 993–1010.
- Radon J. Uber die Bestimmung von Funktionen durch ihre Integralwerte langs gewisser Mannigfaltigkeiten. Berichte Sachsische Acadamie der Wissenschaften, Leipzig, Math.-Phys. Kl. 1917. V. 69. P. 262–267.
- Shipitko O., Grigoryev A. Ground Vehicle Localization With Particle Filter Based On Simulated Road Marking Image. ECMS 2018. 2018. https://doi.org/10.7148/2018-0341
- Soshin K.V., Nikolaev D.P., Gladilin S.A., Ershov E.I. Acceleration of Summation Over Segments Using the Fast Hough Transformation Pyramid. Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming & Computer Software. 2020. V. 13. № 1. P. 129–140. https://doi.org/10.14529/mmp200110
- Sheshkus A., Ingacheva A., Arlazarov V., Nikolaev D. HoughNet: neural network architecture for vanishing points detection. ICDAR 2019. IEEE Feb. 2020. ISSN 1520-5363. ISBN 978-17-28130-15-6. P. 844–849. https://doi.org/10.1109/ICDAR.2019.00140
- Wang Y., Teoh E.K., Shen D. Lane detection and tracking using B-Snake. Image and Vision computing. 2004. V. 22. № 4. P. 269–280.
- Xiao L., Li C., Zhao D., Chen T., Dai B. Road marking detection based on structured learning. 12th World Congress on Intelligent Control and Automation (WCICA). 2016. P. 2047–2051.
- Zolotov D.A., Asadchikov V.E., Buzmakov A.V., D’yachkova I.G., Krivonosov Y.S., Chukhovskii F.N., Suvorov E.V. X-ray Diffraction Tomography Using Laboratory Sources for Studying Single Dislocations in a Low Absorbing Silicon Single Crystal. Optoelectronics, Instrumentation and Data Processing. 2019. V. 55. № 2. P. 126–132.