Recognizing the Presence of Hidden Visual Markers in Digital Images

ABSTRACT

As the promise of Virtual and Augmented Reality (VR and AR) becomes more realistic, an interesting aspect of our enhanced living environment includes the availability ? indeed the potential ubiquity ? of scannable markers. Such markers could represent an initial step into the AR and VR worlds. In this paper, we address the important question of how to recognise the presence of visual markers in freeform digital photos. We use a particularly challenging marker format that is only minimally constrained in structure, called Artcodes. Artcodes are a type of topological marker system enabling people, by following very simple drawing rules, to design markers that are both aesthetically beautiful and machine readable. Artcodes can be used to decorate the surface of any objects, and yet can also contain a hidden digital meaning. Like some other more commonly used markers (such as Barcodes, QR codes), it is possible to use codes to link physical objects to digital data, augmenting everyday objects. Obviously, in order to trigger the behaviour of scanning and further decoding of such codes, it is first necessary for devices to be aware of the presence of Artcodes in the image.

Although considerable literature exists related to the detection of rigidly formatted structures and geometrical feature descriptors such as Harris, SIFT, and SURF, these approaches are not sufficient for describing freeform topological structures, such as Artcode images. In this paper, we propose a new topological feature descriptor that can be used in the detection of freeform topological markers, including Artcodes. This feature descriptor is called a Shape of Orientation Histogram (SOH). We construct this SOH feature vector by quantifying the level of symmetry and smoothness of the orientation histogram, and then use a Random Forest machine learning approach to classify images that contain Artcodes using the new feature vector. This system represents a potential first step for an eventual mobile device application that would detect where in an image such an unconstrained code appears. We also explain how the system handles imbalanced datasets ? important for rare, handcrafted codes such as Artcodes ? and how it is evaluated. Our experimental evaluation shows good performance of the proposed classification model in the detection of Artcodes: obtaining an overall accuracy of approx. 0.83, F₂ measure 0.83, MCC 0.68, AUC-ROC 0.93, and AUC-PR 0.91.

References

1. Herbert Bay, Andreas Ess, Tinne Tuytelaars, and Luc Van Gool. 2008. Speeded-up robust features (SURF). Computer vision and image understanding Vol. 110, 3 (2008), 346--359.
2. Serge Belongie, Jitendra Malik, and Jan Puzicha. 2001. Matching shapes Computer Vision, 2001. ICCV 2001. Proceedings. Eighth IEEE International Conference on, Vol. 1. IEEE, 454--461.
3. Ross Bencina, Martin Kaltenbrunner, and Sergi Jorda. 2005. Improved topological fiducial tracking in the reactivision system Computer Vision and Pattern Recognition-Workshops, 2005. CVPR Workshops. IEEE Computer Society Conference on. IEEE, 99--99.
4. Steve Benford, Adrian Hazzard, Alan Chamberlain, Kevin Glover, Chris Greenhalgh, Liming Xu, Michaela Hoare, and Dimitrios Darzentas. 2016. Accountable artefacts: the case of the Carolan guitar Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI'16). ACM, San Jose, CA, USA, 1163--1175.
5. Steve Benford, Adrain Hazzard, Alan Chamberlain, and Liming Xu. 2015. Augmenting a Guitar with Its Digital Footprint. In Proceedings of International Conference on New Interfaces for Musical Expression (NIME'15). Louisiana, USA, 303--306.
6. Leo Breiman. 2001. Random forests. Machine learning, Vol. 45, 1 (2001), 5--32.
7. Michael Calonder, Vincent Lepetit, Christoph Strecha, and Pascal Fua. 2010. Brief: Binary robust independent elementary features. Proceedings of the 2010 European Conference on Computer Vision (ECCV'10) Vol. 6314 (2010), 778--792.
8. Nitesh V. Chawla, Kevin W. Bowyer, Lawrence O. Hall, and W. Philip Kegelmeyer. 2002. SMOTE: synthetic minority over-sampling technique. Journal of artificial intelligence research Vol. 16 (2002), 321--357.
9. Nitesh V. Chawla, Aleksandar Lazarevic, Lawrence O. Hall, and Kevin W. Bowyer. 2003. SMOTEBoost: Improving prediction of the minority class in boosting European Conference on Principles of Data Mining and Knowledge Discovery. Springer, 107--119.
10. Corinna Cortes and Vladimir Vapnik. 1995. Support-vector networks. Machine learning, Vol. 20, 3 (1995), 273--297.
11. Enrico Costanza and Jeffrey Huang. 2009. Designable visual markers. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems. ACM, 1879--1888.
12. Navneet Dalal and Bill Triggs. 2005. Histograms of oriented gradients for human detection 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), Vol. 1. IEEE, 886--893.
13. Charles Elkan. 2001. The foundations of cost-sensitive learning. In International joint conference on artificial intelligence, Vol. 17. Lawrence Erlbaum Associates Ltd, 973--978.
14. Wei Fan, Salvatore J. Stolfo, Junxin Zhang, and Philip K. Chan. 1999. AdaCost: misclassification cost-sensitive boosting Proceedings of the Sixteenth International Conference on Machine Learning (ICML'99). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 97--105.
15. Mark Fiala. 2005. ARTag, a fiducial marker system using digital techniques Proceedings of 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR'05), Vol. 2. IEEE, San Diego, CA, USA, 590--596.
16. William T. Freeman and Michal Roth. 1995. Orientation histograms for hand gesture recognition International workshop on automatic face and gesture recognition, Vol. 12. 296--301.
17. Yoav Freund and Robert E Schapire. 1995. A desicion-theoretic generalization of on-line learning and an application to boosting European conference on computational learning theory. Springer, 23--37.
18. Hui Han, Wen-Yuan Wang, and Bing-Huan Mao. 2005. Borderline-SMOTE: a new over-sampling method in imbalanced data sets learning International Conference on Intelligent Computing. Springer, 878--887.
19. Chris Harris and Mike Stephens. 1988. A combined corner and edge detector. In Alvey vision conference, Vol. 15. Manchester, UK, 50.
20. Haibo He and Edwardo A. Garcia. 2009. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering, Vol. 21, 9 (2009), 1263--1284.
21. Hirokazu Kato and Mark Billinghurst. 1999. Marker tracking and hmd calibration for a video-based augmented reality conferencing system. In Augmented Reality, 1999.(IWAR'99) Proceedings. 2nd IEEE and ACM International Workshop on. IEEE, 85--94.
22. David G. Lowe. 2004. Distinctive image features from scale-invariant keypoints. International journal of computer vision Vol. 60, 2 (2004), 91--110.
23. Brian W. Matthews. 1975. Comparison of the predicted and observed secondary structure of T4 phage lysozyme. Biochimica et Biophysica Acta (BBA)-Protein Structure, Vol. 405, 2 (1975), 442--451.
24. Michael W. Maynard. 1993. Classifying apparatus and method. US Patent 5,232,099. (3 Aug.. 1993).
25. Rupert Meese, Shakir Ali, Emily-Clare Thorne, Steve D. Benford, Anthony Quinn, Richard Mortier, Boriana N. Koleva, Tony Pridmore, and Sharon L. Baurley. 2013. From codes to patterns: designing interactive decoration for tableware Proceedings of the SIGCHI Conference on Human Factors in Computing Systems (CHI'13). ACM, Paris, France, 931--940.
26. Krystian Mikolajczyk, Cordelia Schmid, and Andrew Zisserman. 2004. Human detection based on a probabilistic assembly of robust part detectors Proceedings of 2004 European Conference on Computer Vision (ECCV'04). Springer, 69--82.
27. Anuj Mohan, Constantine Papageorgiou, and Tomaso Poggio. 2001. Example-based object detection in images by components. IEEE transactions on pattern analysis and machine intelligence, Vol. 23, 4 (2001), 349--361.
28. Kher Hui Ng and Shazia Paras Shaikh. 2016. Design of a mobile garden guide based on Artcodes. Proceedings of 2016 International Conference on User Science and Engineering (i-USEr'16), IEEE, 23--28.
29. Constantine Papageorgiou and Tomaso Poggio. 2000. A trainable system for object detection. International Journal of Computer Vision Vol. 38, 1 (2000), 15--33.
30. David M. W. Powers. 2011. Evaluation: From precision, recall and f-measure to roc., informedness, markedness & correlation. Journal of Machine Learning Technologies Vol. 2, 1 (2011), 37--63.
31. Edward Rosten and Tom Drummond. 2006. Machine learning for high-speed corner detection. Proceedings of 2006 European Conference on Computer Vision (ECCV'06). Springer, 430--443.
32. Ethan Rublee, Vincent Rabaud, Kurt Konolige, and Gary Bradski. 2011. ORB: an efficient alternative to SIFT or SURF. In Proceedings of 2011 IEEE International Conference on Computer Vision (ICCV'11). IEEE, 2564--2571.
33. Chris Seiffert, Taghi M Khoshgoftaar, Jason Van Hulse, and Amri Napolitano. 2010. RUSBoost: A hybrid approach to alleviating class imbalance. IEEE Transactions on Systems, Man, and Cybernetics-Part A: Systems and Humans, Vol. 40, 1 (2010), 185--197.
34. ISO/IEC International Standard. 2000. QR Code. (2000).
35. Emily-Clare Thorn, Stefan Rennick-Egglestone, Boriana Koleva, William Preston, Steve Benford, Anthony Quinn, and Richard Mortier. 2016. Exploring large-scale interactive public illustrations Proceedings of the 2016 ACM Conference on Designing Interactive Systems. ACM, 17--27.
36. Engin Tola, Vincent Lepetit, and Pascal Fua. 2008. A fast local descriptor for dense matching. In Proceedings of 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'08). IEEE, 1--8.

Index Terms

• Computing methodologies

  • Computer graphics

    • Graphics systems and interfaces

      • Mixed / augmented reality

  • Machine learning

    • Learning paradigms

      • Supervised learning

        • Supervised learning by classification

    • Machine learning algorithms

      • Ensemble methods

        • Bagging

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Mixed / augmented reality

  • Ubiquitous and mobile computing

    • Ubiquitous and mobile computing theory, concepts and paradigms

      • Mobile computing