Tutorial

Description

The increasing amount of visual data shared online highlights the importance of organizing and finding related content. However, current efforts to improve visual search and image classification lack support for exploratory image search. Sorting images by similarity offers a solution, allowing users to view and recognize several hundred images at once. This tutorial covers the main principles of image sorting techniques, including visual feature vectors, various sorting algorithms, and metrics used to evaluate sorting results. The workshop also presents a new sorting algorithm (Linear Assignment Sorting) and efficient optimization techniques and coding examples. By the end of the workshop, participants will be able to implement image sorting techniques and address any special requirements related to layout and positioning constraints.

Motivation

As the internet produces and shares more visual data, the task of organizing and finding related content becomes increasingly difficult and important. Despite efforts to improve visual search and image classification, there is a lack of support for exploratory image search.

Humans can easily understand complex images, but have difficulties with a large number of unordered individual images. When searching photo archives or trying to find products online, users are often presented with vast collections of images. However, as human perception is limited, overview is quickly lost when too many images are displayed at once. Typically, only about 10-20 images can be perceived on a single screen, which is a small fraction of the number of available images. Because image archives and e-commerce websites do not offer visual browsing or exploration of their collection, users are left with unstructured lists of images from keyword or similarity searches.

One solution to this problem is sorting/arranging images by similarity, which enables users to view and recognize up to several hundreds of images at once (see example above). Although the sorted images may not be recognized perfectly, users can quickly identify where images of interest are located. Conventional dimensionality reduction schemes that project high-dimensional visual feature vectors to 2D cannot be used for image sorting because they result in unequally distributed and overlapping images. As the number of ways to arrange images in a dense regular grid increases factorially with the grid size, finding the optimal arrangement becomes impractical. However, approximate solutions can be obtained through the use of self-organizing maps (SOMs), self-sorting maps (SSMs), or discrete optimization algorithms.

In this tutorial, participants acquire knowledge of the main principles of image sorting techniques, including the requirements for the visual feature vectors to be used. Various sorting algorithms will be presented, as well as the results of extensive user testing. Also, various metrics used to evaluate the sorting results are presented, and their correlation with human perception is evaluated. In addition, a new sorting algorithm (Linear Assignment Sorting) and efficient optimization techniques and coding examples are presented. By the end of the workshop, participants will be equipped to implement image sorting techniques and address any special requirements related to layout and positioning constraints.

Indicative breakdown and description

• Welcome participants and obtain information on their background and goals for attending the tutorial. Provide an overview of the tutorial’s goals, as well as distribute the necessary tutorial materials such as Jupyter notebooks that serve as supplementary materials for programming.
• Explain the limitations of dimensionality reduction techniques such as PCA, Multidimensional scaling (MDS), Isomap, Local-linear embedding (LLE), t-Distributed Stochastic Neighbor Embedding (t-SNE), and why they are not suitable for organizing and sorting images.
• Introduce the main concepts of image sorting techniques, including Self Organizing Maps (SOM), Self-Sorting Maps (SSM), and Linear Assignment Sorting (LAS), as well as neural networks for learning permutations.
• Provide an overview of which visual feature vectors are best suited for visual image sorting.
• Report on human perception of large image sets and describe evaluation metrics for 2D image arrangements.
• Explain optimization techniques for fast image sorting, including filtering using integral images, fast matching / swapping using a Linear Assignment Problem solver, and other techniques.
• Provide tips and tricks for sorting images, particularly when there are constraints on the layout shape and fixed positioning of specific images.
• Extend image sorting techniques to the visualization of image graphs for continuously changing image sets to enable visual exploration / recommendation of image collections.
• Conclude with a final discussion to answer any remaining questions and reinforce key takeaways from the tutorial.

The tutorial provides content that may be of interest to the following conference topics:

• Multimedia content-based search and retrieval
• Large-scale and web-scale multimedia retrieval
• User intent and human perception in multimedia retrieval
• Interactive recommendation systems
• Multimedia browsing, summarization, and visualization
• Applications of multimedia retrieval

GitHub

Addtional information can be found in GitHub. Further information will be made available on GitHub throughout the conference.

Relevant Publications

1. Kai Uwe Barthel, Nico Hezel, Klaus Jung, and Konstantin Schall. 2023
   Improved Evaluation and Generation of Grid Layouts Using Distance Preservation Quality and Linear Assignment Sorting, Computer Graphics Forum Journal, https://doi.org/10.1111/cgf.14718
2. Kai Uwe Barthel, Nico Hezel, Konstantin Schall, and Klaus Jung. 2022.
   Combining Semantic and Visual Image Graphs for Efficient Search and Exploration of Large Dynamic Image Collections, In Proceedings of the 2nd International Workshop on Interactive Multimedia Retrieval (Lisboa, Portugal) (IMuR ’22). Association for Computing Machinery, New York, NY, USA, pp. 1–8, https://doi.org/10.1145/3552467.3554796
3. Kai Uwe Barthel, Nico Hezel. 2019
   Visually Exploring Millions of Images using Image Maps and Graphs, John Wiley & Sons, Ltd, ch. 11, pp. 289–315, https://doi.org/10.1002/9781119376996.ch11
4. Kai Uwe Barthel, Nico Hezel, and Klaus Jung. 2017.
   Visually Browsing Millions of Images Using Image Graphs, In Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval (Bucharest, Romania), Association for Computing Machinery, New York, NY, USA, pp. 475–479, https://doi.org/10.1145/3078971.3079016

Slides

Contact