Laboratory of Data Intensive Systems and Applications DISA Faculty of Informatics, Masaryk University, Brno Pavel Zezula - presenter Content of the talk •Similarity in our lives and digital data processing • •The metric space model of similarity • •Content based similarity search and feature extraction • •DISA contribution – research, results, awards • • Applied multidisciplinary research • •SWOT a future research directions • Meeting with the research evaluation panel, September 6-7, 2022 2 DISA members •Staff: •Michal Batko •Petra Budikova •Vlastislav Dohnal •Vladimir Mic •Jan Sedmidubsky •Pavel Zezula •Former members: Petr Elias, Filip Nálepa, David Novak, Jakub Valcik •Current PhD students: •Miriama Janosova •Iris Kico •Jakub Peschel •Terezia Slaninakova • •Plus, about 10 bachelor and master students Meeting with the research evaluation panel, September 6-7, 2022 3 Similarity in our Lives quotations from the social psychology literature •Any event in the history of organism is, in a sense, unique. • •Recognition, learning, and judgment presuppose an ability to categorize stimuli and classify situations by similarity. • •Similarity (proximity, resemblance, communality, representativeness, psychological distance, ...) is fundamental to theories of perception, learning, judgment, etc. • •Similarity is subjective and context-dependent Meeting with the research evaluation panel, September 6-7, 2022 4 Real-life Similarity •Are they similar? http://html.slidesharecdn.com/similarity-120222193728-phpapp02/output009.png?1329961814 Meeting with the research evaluation panel, September 6-7, 2022 5 Real-life Similarity •Are they similar? http://html.slidesharecdn.com/similarity-120222193728-phpapp02/output001.png?1329961814 Meeting with the research evaluation panel, September 6-7, 2022 6 Real-life Similarity •Are they similar? http://html.slidesharecdn.com/similarity-120222193728-phpapp02/output004.png?1329961814 Meeting with the research evaluation panel, September 6-7, 2022 7 Real-life Similarity •Are they similar? http://html.slidesharecdn.com/similarity-120222193728-phpapp02/output010.png?1329961814 Meeting with the research evaluation panel, September 6-7, 2022 8 Prototypicality or Centrality not symmetric Meeting with the research evaluation panel, September 6-7, 2022 9 Context/Data/Environment Dependent circumstances alter similarities Meeting with the research evaluation panel, September 6-7, 2022 10 Contemporary Networked Media The digital data view •Almost everything that we see, read, hear, write, measure, or observe can be digital. •Users autonomously contribute to production of global media and the growth is exponential. •Sites like Flickr, YouTube, Facebook host user contributed content for a variety of events. •The elements of networked media are related by numerous multi-facet links of similarity. • • •Majority of current data is unstructured •possibly only structured on display Meeting with the research evaluation panel, September 6-7, 2022 11 Challenge •Networked media database is getting close to the human “fact-bases” –the gap between physical and digital world has blurred • •Similarity data management is needed to connect, search, filter, merge, relate, rank, cluster, classify, identify, or categorize objects across various collections. • •WHY? •It is the similarity which is in the world revealing. Meeting with the research evaluation panel, September 6-7, 2022 12 We learned from School •GEOMETRY: •Two polygons are similar to each other, if: 1)Their corresponding angles are congruent •∠A = ∠E; ∠B = ∠F; ∠C = ∠G; ∠D = ∠H, and 2)The lengths of their corresponding sides are proportional •AB/EF = BC/FG = CD/GH = DA/HE • B C A D E F H G Meeting with the research evaluation panel, September 6-7, 2022 13 Similarity & Geometry •If one polygon is similar to a second polygon, and the second polygon is similar to the third polygon, the first polygon is also similar to the third polygon. •In any case: • •Two geometric figures are either similar or they are not similar at all • Meeting with the research evaluation panel, September 6-7, 2022 14 Metric Space: A Geometric Model of Similarity •Metric space: M = (D,d) –D – domain –distance function d(x,y) •"x,y,z Î D •d(x,y) > 0 - non-negativity •d(x,y) = 0 Û x = y - identity •d(x,y) = d(y,x) - symmetry •d(x,y) ≤ d(x,z) + d(z,y) - triangle inequality Meeting with the research evaluation panel, September 6-7, 2022 15 Examples of Distance Functions •Lp Minkovski distance (for vectors) •L1 – city-block distance » •L2 – Euclidean distance • •L¥ – infinity » •Edit distance (for strings) •minimal number of insertions, deletions and substitutions •d(‘application’, ‘applet’) = 6 » •Jaccard’s coefficient (for sets A,B) • Meeting with the research evaluation panel, September 6-7, 2022 16 Examples of Distance Functions •Mahalanobis distance –for vectors with correlated dimensions •Hausdorff distance –for sets with elements related by another distance •Earth movers distance –primarily for histograms (sets of weighted features) •and many others – Meeting with the research evaluation panel, September 6-7, 2022 17 Content-Based Search Objectives •Content-based search in images 1806 1040158 1045791 984761 1042473 Image base Meeting with the research evaluation panel, September 6-7, 2022 18 Content-Based Search Implementation •Extracting features 1806 Image level R B G Feature level Meeting with the research evaluation panel, September 6-7, 2022 19 MPEG-7 •Multimedia Content Descriptors Standard ~ 2000 •Global feature descriptors: –Color, shape, texture, … – – – – –One high-dimensional vector per image and feature –Minkovski distance used • – Meeting with the research evaluation panel, September 6-7, 2022 20 Meeting with the research evaluation panel, September 6-7, 2022 Visual Similarity - Local feature descriptors – SIFT, SURF, etc. - Invariant to image scaling, small viewpoint change, rotation, noise, illumination IMG_2088_sifts_thick 21 Meeting with the research evaluation panel, September 6-7, 2022 Visual Similarity - finding correspondence 22 Biometrics: Fingerprint •Minutiae detection: –Detect ridges (endings and branching) –Represented as a sequence of minutiae •P=( (r1,e1,θ1), …, (rm,em,θm) ) •Point in polar coordinates (r,e) and direction θ •Matching of two sequences: –Align input sequence with database one –Compute weighted edit distance •wins,del=620 •wrepl=[0;26] - depending on similarity of two minutiae Meeting with the research evaluation panel, September 6-7, 2022 fingerprint1.png fingerprint1.png 23 Points in the sequence are ordered in an increasing order of radial angle (e). Multiple Visual Aspects • Meeting with the research evaluation panel, September 6-7, 2022 tovarna 25 Contemporary Approaches to Feature Extraction – Metric Learning •Neural networks technology –Convolutional Neural Networks (CNN) –Recurrent Neural Networks (RNN) Meeting with the research evaluation panel, September 6-7, 2022 Classified dataset Training data Validation data Výsledek obrázku pro neural network Training (Fine-tuning) Validation Neural network model Data split 26 Similarity Search Problem •For X ÍD in metric space M, •pre-process X so that the similarity queries •are executed efficiently. • •Implementation problems: -How to partition the data to reduce search space -How to ask questions - definition of queries –- How to execute queries – to achieve required performance •The challenge: –In metric space, no total ordering exists! • Meeting with the research evaluation panel, September 6-7, 2022 27 [USEMAP] MESSIF - Metric Similarity Search Implementation Framework Infrastructure independent Metric space (D,d) Operations Storage Centralized index structures Distributed index structures Communication Net Vectors • Lp and quadratic form Strings • (weighted) edit and protein sequence Insert, delete, range query, k-NN query, Incremental k-NN Volatile memory Persistent memory Performance statistics Meeting with the research evaluation panel, September 6-7, 2022 28 DISA Contribution – grants and partners •Large spectrum of contributing grants: §Academic vs. Industrial §National vs. European §Focused research vs. Network of Excellence •Significant cooperating partners: – academic (including Max Plant Institute, ETH Zurich, CNR Italy, NII Tokyo, University of St. Andrews, University of Bologna, plus tens of other universities in Europe within networks of excellence) –industrial (including IBM Research, Telenor, Telecom Spain, Bull, Athena Security Israel, XEROX SAS Grenoble, Konica-Minolta) • – Meeting with the research evaluation panel, September 6-7, 2022 29 Scientific Achievements •Most cited works: –M-tree 2550; Metric book 1250 •Advanced publication platforms: –VLDB, ACM SIGMOD-PODS, ACM SIGIR, ACM TODS, ACM TOIS, VLDB Journal •Tutorials: –ACM SAC, ACM Multimedia, ICMR, ESMAC •Invited talk and key-notes: –ACM SIGIR, ADBIS, MMM, IEEE ISM, SOFSEM, SEDB •Best paper awards: –DEXA, IEEE ISM, SISAP Meeting with the research evaluation panel, September 6-7, 2022 30 Textbooks on Metric Searching technology book Foundations of Multidimensional and Metric Data Structures (The Morgan Kaufmann Series in Computer Graphics) Hanan Samet Foundation of Multidimensional and Metric Data Structures Morgan Kaufmann, 2006 P. Zezula, G. Amato, V. Dohnal, and M. Batko Similarity Search: The Metric Space Approach Springer, 2005 Teaching material: http://www.nmis.isti.cnr.it/amato/similarity-search-book/ Meeting with the research evaluation panel, September 6-7, 2022 31 SISAP International Conferences SISAP (Similarity Search and Applications) International conference series (http://sisap.org/) 2008 Cancun Mexico Výsledek obrázku pro cancun 2012 Toronto Canada 2016 Tokyo Japan 2018 Lima Peru 2009 Prague Czechia 2010 Istanbul Turkey 2011 Lipari Italy 2013 A Coruña Spain 2017 Munich Germany 2015 Glasgow UK 2014 Los Cabos Mexico Výsledek obrázku pro prague Výsledek obrázku pro istanbul Výsledek obrázku pro lipari SouvisejÃcà obrázek Výsledek obrázku pro la coruna Výsledek obrázku pro los cabos Výsledek obrázku pro glasgow Výsledek obrázku pro tokyo fudzi Výsledek obrázku pro munich Výsledek obrázku pro lima peru Meeting with the research evaluation panel, September 6-7, 2022 2019 Newark NJ USA by _skynet (CC BY-SA 3.0) 32 XIMILAR – Image Recognition and Visual Search https://www.ximilar.com/ Obsah obrázku text, osoba Popis byl vytvořen automaticky MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 33 Appreciation - Awards §IBM SUR (Shared University Research) Award for “Web-scale Similarity Search in Multimedia Data” § §Top 27 IT Personalities in Czech Republic – Computerworld Magazine § §MU Brno Rector’s price 2X MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 34 Application Research §Face Retrieval § §Image annotation § §Motion data management § §Improving Treatments in Cerebral-Palsy § §Protein Similarity Search § §Dyslexia detection MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 35 http://disa.fi.muni.cz/FaceMatch/image/215920 http://disa.fi.muni.cz/FaceMatch/image/215920 Preprocessing Retrieval http://disa.fi.muni.cz/FaceMatch/image/215920 Face detection with several technologies Merge of detected faces <13.9, 9.5, -6.0, 712.1, …> <17.9, 12.1, -9.1, 692.0, …> <8.8, 7.7, -3.5, 570.8, …> <14.4, 8.2, -8.4, 704.0, …> <10.1, 5.8, 40.6, 99.6, …> <5.4, 1.2, -60.4, 88.0, …> <45.1, 64.8, 90.6, 78.6, …> Face description with several technologies Similarity Search in Collections of Faces http://upload.wikimedia.org/wikipedia/commons/8/88/Cameron_Diaz_WE_2012_Shankbone_3.JPG <13.9, 9.5, -6.0, 712.1, …> <10.6, 78.9, -45.6, 101.3, …> 0.12 0.17 0.18 0.23 Fused features DB Features indexing by one technique > Face Detection Features Extraction Candidates filtering Index Fused features saving Candidate faces Query image Meeting with the research evaluation panel, September 6-7, 2022 36 Slide ‹#› Search-based annotation principles https://encrypted-tbn0.gstatic.com/images?q=tbn:ANd9GcRSpxVqEaSo5HgnpQLjkP44gtENLw8eHm8jhsO6LnM98BS eIzNt Annotated image collection Content-based image retrieval Similar annotated images Yellow, bloom, pretty Meadow, outdoors, dandelion Mary’s garden, summer Candidate keyword processing Semantic resources Final candidate keywords with probabilities Plant 0.3 Flower 0.3 Garden 0.15 Sun 0.05 Human 0.1 Park 0.1 d = 0.2 d = 0.6 d = 0.5 ? Slide ‹#› Example http://disa.fi.muni.cz/profimedia/imagesJpeg/0077128591 Candidate keywords after CBIR church, architecture, travel, europe, building, religion, germany, buildings, north, churches, christianity, america, religious, exterior, st, historic, world, tourism, united, usa, … 1.Retrieve 100 similar images from Profiset 2.Merge their keywords, compute frequencies 3.Build the semantic network using WordNet 4.Compute the ConceptRank 5.Apply post-processing & return 20 most probable keywords ConceptRank scores building (2.53), structure (2.41), LANDSCAPE (2.10), BUILDINGS (1.87), OBJECT (1.84), NATURE (1.78), place_of_worship (1.75), church (1.74), Europe (1.68), religion (1.64), continent (1.51), … Final keywords building, structure, church, religion, continent, group, travel, island, sky, architecture, tower, person, belief, locations, chapel, christianity, tourism, regions, country, district Semantic network 4 relationships: hypernym (dog → animal), hyponym (animal → dog), meronym (leaf → tree), holonym (tree → leaf) 270 network nodes, 471 edges Skeleton-data representation •Simplified spatio-temporal representation of human motion –Sequence of 3D skeletons ~ a set of 3D trajectories of body joints •Better structured and easier to store than video-based representation Digitization of Human Motion Source: https://blog.usejournal.com/3d-human-pose-estimation-ce1259979306 Meeting with the research evaluation panel, September 6-7, 2022 Video-based representation Skeleton-based representation 39/37 A wide variety of possible applications •Sports – digital referees assessing the quality of performance •Virtual reality – recognizing player movements in real time •Smart-cities – detecting falls of persons crossing a street •Healthcare – evaluating the rehabilitation progress remotely Great Application Potential Source: https://blog.usejournal.com/3d-human-pose-estimation-ce1259979306 Meeting with the research evaluation panel, September 6-7, 2022 Source: https://www.youtube.com/watch?v=5cI-JibDEMA 40/37 The skeleton data have a great potential to be utilized in a wide variety of application domains. For example, in: -Sports – to automatically assess the quality of a figure-skating performance; -Virtual reality – to recognize movement actions of players to enable real-time interactions, e.g., like playing a football with a virtual ball; -Smart cities – to detect falls of elderly people, or to detect suspicious events like kicking or punching somebody else; -Telemedicine – to evaluate how well a given patient performs in rehabilitation after some surgery. Such great application potential together with the fact that the skeleton representation can now be extracted from ordinary videos indicates that very large volumes of skeleton data can be generated in the near future. Query-by-example searching •Transforming complex motions to fixed-size vectors and indexing them by metric-space search methods 1) 1) 1) 1) – – Content-based Processing Meeting with the research evaluation panel, September 6-7, 2022 [Sedmidubsky, J., Elias, P., Zezula, P.: Effective and Efficient Similarity Searching in Motion Capture Data. Mult. Tools and Apps. 2018] 41/37 right leg right hand left hand left leg torso Time <…, 0.5, 1.1, 9.6, …> <…, 0.1, 3.4, 6.8, …> <…, 0.6, 2.9, 7.7, …> https://www.ittia.com/html/ittia-db-docs/users-guide/images/t-tree.png Deep feature extraction Indexing database features Fixed-size features Slide ‹#›/12 Motion Words – idea §Cut motion into short, overlapping segments §Quantize the segment space §Represent original sequence by identifiers § of quantized segments § § § § § § § § … … … A, A, B, O, M, M, P, D, … … … A B C E D F G Comparison of speed-climbing performances Content-based Analysis Source: https://www.youtube.com/watch?v=tdxMo11KJGk&t=258s Meeting with the research evaluation panel, September 6-7, 2022 43/37 Similarity Search in Protein Chains Each protein consists of 1 or more subparts – protein chains Approx. 500,000 chains are known – Protein Data Bank (PDB) 3D models of protein chains are used to define their pairwise similarity ◦Similarity evaluation time strongly depends on the size of compared chains ◦Distance evaluation time ranges from ms to min. ◦ ◦ Model of a protein chain: balls ≈ atoms, sticks ≈ bonds between atoms. Green ribbon ≈ simplification of the main atoms MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 44 Recent Applied Research Project #1 Meeting with the research evaluation panel, September 6-7, 2022 •Project scope: •Improving Treatments in Cerebral-Palsy Children using Artificial Intelligence (2020–2022) •Cooperation with Children Hospital Brno •Main objective – estimate whether a given treatment is suitable for a new child patient suffering from the cerebral-palsy disease •Solution – searching for similar gait cycles recorded in the pre-surgery phase and comparing the quality of walking between the pre-surgery and post-surgery phases The stages of musculoskeletal pathology (MSP) in children with spastic... | Download Scientific Diagram 45/37 Phases of the normal gait cycle | Download Scientific Diagram Recent Applied Research Project #2 Meeting with the research evaluation panel, September 6-7, 2022 •Project scope: •Diagnosis of Dyslexia using Eye-Tracking and Artificial Intelligence (2021–2023) •Cooperation with the Faculty of Arts (Masaryk University) and psychological clinics •Main objective – estimate how prone the individual is to the dyslexia disease •Solution – classifying spatio-temporal eye-tracking data (and their derived features) of dyslexia/intact patients on text-reading tasks How can I help my child with Dyslexia? - ScanMarker 46/37 SWOT Strengths Similarity plays a central role in processing contemporary digital data. We have a leading position in this research - most cited papers and the first monograph in the similarity search domain, organize a conference, spin-off We teach corresponding courses (even abroad) and have many successful PhD graduates (including foreigners), Received prestigious awards (e.g. IBM SUR, Computerworld magazine, rector’s price), Participated in many prestigious national and international projects (e.g. European research – Scholnet, Sapir -, European networks of Excellence – DELOS 2X -, GACR Network of Excellence CEMI), Cooperated with many academic and industrial institutions Delivered invited and key-note speeches at important conferences (e.g. ACM SIGIR, SMAC, ADBIS, MMM, IEEE ISM, SEBD), based on our similarity search technology a spinoff XIMILAR was created by the group’s PhD students, we organize SISAP International conference (recently received the CORE B grade). MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 47 SWOT - Weaknesses The group is rather small with most researchers exclusively supported from external resources. The researchers are overloaded with teaching and often must leave the actual research to students - this typically results in routine work, not the best quality. The endless fight for grants consumes too much time and mental capacity of highly qualified researchers. Not very efficient communication with the faculty management. MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 48 SWOT - Opportunities Many open questions/problems remain in the similarity search domain thus additional fundamental research is needed – e.g., context dependent, subjective, and adaptable similarity search or explainable similarity data models for AI. The potential application area is huge and opens additional research areas – in medicine, sports, security, game industry, etc. We can capitalize on our previous results in the motion data processing and similarity management in general. MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 49 SWOT - Threats To bring up qualified researchers takes years, but you can lose a skilled person very fast when you do not get grant support in time. Such a system repeatedly alternates periods of too much money for available staff and not enough money for existing staff - making qualified researchers redundant. With the increasing quantity and importance of evaluation indicators, the danger is that researchers will concentrate more on complying with required indicators rather than the quality of their research work. Students are not motivated to study PhD – it is easy to get a high paid job without a PhD degree. MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 50 Our Vision - Future Research Challenges Challenge No.1 (adaptability): Respecting continuously changing distance metric – searched collection size as well as up to date collection of known samples – continuously adapt the search indexing mechanisms. Challenge No. 2 (explainability): Respecting an application domain – e.g. motion capture data – provide explanation tools that might be requested on demand. Similarity cracks the code of explainable AI. MEETING WITH THE RESEARCH EVALUATION PANEL, SEPTEMBER 6-7, 2022 51 Research Projects Meeting with the research evaluation panel, September 6-7, 2022 •Selected basic-research projects: •Center of Excellence on Multi-modal Data Interpretation on a Very Large Scale (GBP103/12/G084); Czech Science Foundation (GAČR); 2012–2018 •Searching, Mining, and Annotating Human Motion Streams (GA19-02033S); Czech Science Foundation (GAČR); 2019–2021 • •Selected applied-research (application-oriented) projects: •Efficient Searching in Large Biometric Data (VG20122015073); Ministry of the Interior of the Czech Republic; 2012–2015 •Improving Treatments in Cerebral-Palsy Children using Artificial Intelligence (MUNI/G/1585/2019); GAMU (Interdisciplinary projects); 2020–2022 •Diagnosis of Dyslexia using Eye-Tracking and Artificial Intelligence (TL05000177); Technology Agency of the Czech Republic (TAČR); 2021–2023 52/37