PROPERTIES OF NETWORKS BUILT ON DIGITAL IMAGES

Oleh Kushnir, Oleksiy Kravchuk, Volodymyr Franiv

Abstract


Background. It is known that some important properties of natural-language texts can be revealed when mapping a text on a network and studying the properties of this network. Here the words of a text are regarded as nodes and their co-occurrences as links.

Materials and Methods. Drawing an analogy between texts and digital images, in this work we study experimentally and analyze phenomenologically the properties of a network built on an image. In this network, the nodes are pixel values and the links are assigned among those pixel values that spatially adjoin each other in an image. The neighborhood of pixels is defined by a radius r (r = 1, 2, ...). We build our networks for a test informative image and the corresponding images obtained from the initial one by adding calibrated portions of white Gaussian noise. Both weighted and non-weighted networks are analyzed and a number of practical methods for building an image network and adding a noise to an image are compared with each other.

Results and Discussion. The main network parameters such as the average clustering coefficient and the average shortest-path length are measured as functions of the relative noise parameter. The main qualitative and quantitative features of the dependences are analyzed. The network characteristics are critically compared with those known for the lexical networks build upon the natural texts and the random texts obtained with randomizing words in the initial natural text. The main similarities and distinctions of the lexical and image networks are scrutinized.

Conclusion. It is shown that the average clustering coefficient and path length for the networks built upon the initial informative image and the corresponding noisy images are essentially small worlds. In spite of this similarity, the above networks reveal a number of distinct features so that the dependences of the image-network parameters on the noise level can be used for distinguishing between these types of images. Finally, we analyze a number of consequences of our empirical results and some data known from the literature. Since both informative and noisy images reveal a small-worldliness, it would hardly be appropriate to associate this effect with the information load of the image.

Keywords: complex networks, analysis and classification of images, image recognition, information and noise detection, semantics, random models.


References


  1. Gonzalez R., Woods R. Digital image processing / Pearson, 2018. – 1020 p.
  2. Clark A., Fox C., Lappin S. The handbook of computational linguistics and natural lan­guage processing / Wiley-Blackwell, 2010, – 802 p.
  3. Meriem H., Farida M. H. Detection of a region of interest in the images based on Zipf laws // In: Proc. 7th Int. Conf. on Signal Image Technol. & Internet-Based Systems. – 2011, – P. 416–421,
  4. Manzanera A. Σ-∆ background subtraction and the Zipf law / In: Progress in Pattern Rec­ognition, Image Analysis and Applications (CIARP’07). – Viña del Mar-Valparaíso, Chile, 2007. – 10 p. URL: https://hal.science/hal-01222660/document
  5. Довгань І. Я., Кушнір О. С., Фургала Ю. М., Паночко Г. І. Аналогії між зображеннями та текстами: явище «спалахів» у текстах і цифрових зображеннях // Елект­роніка та інформаційні технології. – 2022. – Вип. 17. – С. 3–15.
  6. Zhang Z. Image noise: detection, measurement, and removal techniques / Knoxville: Department of Electrical Engineering and Computer Science, 2015. – 10 pp. URL: https://zzutk.github.io/docs/reports/2015.07%20-%20Image%20Noise%20Detection,%20Measurement,%20and%20Removal%20Techniques.pdf
  7. Olsen S. I. Estimation of noise in images: An evaluation // Graphical Models and Image Processing. – 1993. – Vol. 55, No. 4. – P. 319–323.
  8. Newman M. E. J. The structure and function of complex networks // SIAM Rev. – 2003. – Vol. 45. – P. 167–256.
  9. Ferrer i Cancho R., Solé R. V. The small world of human language // Proc. Roy. Soc. Lond. B. – 2001, – Vol. 268. – P. 2261–2265.
  10. Dorogovtsev S. N., Mendes J. F. F. Language as an evolving word web // Proc. Roy. Soc. Lond. B. – 2001, – Vol. 268. – P. 2603–2606.
  11. Matsuo Y., Ohsawa Y., Ishizuka M. KeyWorld: Extracting keywords from a document as a small world / In: Jantke K. P., Shinohara A. (Eds.). Discovery Science, 2001, Lecture Notes in Computer Science, Vol. 2226. – Berlin, Heidelberg: Springer.
  12. Ferrer i Cancho R., Solé R. V., Köhler R. Patterns in syntactic dependency networks // Phys. Rev. E. – 2004. – Vol. 69. – P. 051915 (8 pp.).
  13. Antiqueira L., Nunes M. G. V., Oliveira Jr. O. N., Costa L. da F. Strong correlations bet­ween text quality and complex networks features // Physica A. – 2007. – Vol. 373. – P. 811–820,
  14. Cong J., Liu H. Approaching human language with complex networks // Phys. Life Rev. – 2014. – Vol. 11, – P. 598–618.
  15. Espitia D., Larralde H. Universal and non-universal text statistics: Clustering coefficient for language identification // Physica A. – 2020, – Vol. 553. – P. 123905 (25 рр.).
  16. Masucci A. P., Rodgers G. J. Network properties of written human language // Phys. Rev. E. – 2006. – Vol. 74. – 026102 (8 pp.).
  17. Caldeira S. M. G., Petit Lobão T. C., Andrade R. F. S., Neme A., Miranda J. G. V. The network of concepts in written texts // Eur. Phys. J. B. – 2006. – Vol. 49. – P. 523–529.
  18. Masucci A. P., Rodgers G. J. Differences between normal and shuffled texts: Structural properties of weighted networks // Adv. Complex Syst. – 2009. – Vol. 12. – P. 113–129.
  19. Amancio D. R., Altmann E. G., Rybski D., Oliveira Jr. O. N., Costa L. da F. Probing the statistical properties of unknown texts: Application to the Voynich manuscript // PLOS ONE. – 2013. – Vol. 8. – e67310 (10 pp.).
  20. Carretero-Campos C., Bernaola-Galván P., Ivanov P. Ch., Carpena P. Improving statistical keyword detection in short texts: entropic and clustering approaches // Physica A. – 2013. – Vol. 392. – P. 1481–1492.
  21. Кушнір О. С., Дребот А. С., Д. А. Остріков, Кравчук О. М. Властивості лексичних мереж, побудованих на природних і рандомних текстах // Елект­роніка та інформаційні технології. – 2024 – Вип. 28. – С. 22–37.
  22. Neal Z. P. How small is it? Comparing indices of small worldliness // Network Science. – 2017. – Vol. 5, No. 1 – P. 30–44.
  23. Börner K., Sanyal S., Vespignani A. Network science / In: B. Cronin (Ed.). Annual Review of Information Science & Technology, Vol. 41, Medford, NJ: Information Today / American Society for Information Science and Technology. – Chapter 12. – pp. 537–607.




DOI: http://dx.doi.org/10.30970/eli.29.2

Refbacks

  • There are currently no refbacks.