Artifacts of Memory blogpost № 2/5 (voortgang okt — nov 2020)
Zoeken in digitaal erfgoed op basis van visuele metadata
Het Stimuleringsfonds Creatieve Industrie biedt Superposition door middel van financiële ondersteuning de kans om het project Artifacts of Memory te ontwikkelen tot een volwaardige smartphone applicatie. Meer over de subsidieregeling genaamd “Digital Heritage x Public” leest u hier. Door middel van deze blog stellen wij geïnteresseerden graag op de hoogte van de voortgang die wij de komende maanden zullen maken.
Binnen Artifacts of Memory onderzoekt Superposition hoe gedistribueerde audiovisuele erfgoedobjecten door middel van de cinematische overeenkomsten aan elkaar gekoppeld kunnen worden. Met Artifacts of Memory kan de gebruiker op een taal- overstijgende manier zoekopdrachten uitvoeren in zijn of haar eigen omgeving en zelf nieuwe narratieven samen stellen door objecten uit uiteenlopende, erfgoedinstellingen aaneen te schakelen.
In navolging op onze eerdere post bieden wij in deze nieuwe post een inkijk in de stappen die we vanaf oktober 2020 hebben gezet. In de laatste weken van september 2020 heeft Nanne van Noord (Beeld en Geluid en tevens verbonden aan de UvA) een goede start gemaakt met het detecteren van lijnen uit een selectie video’s die beschikbaar werd gesteld door René Duursma (Groninger Archieven).
Introducing: Błażej Mańczak
Omdat Nanne de komende periode druk zal zijn met een ander project hebben we de hulp ingeschakeld van Błażej Mańczak. Błażej is één van Nanne’s talentvolle studenten uit het eerste jaar van het masterprogramma Artificial Intelligence van de Universiteit van Amsterdam.
Gedurende zijn bachelorstudie Data Science aan de TU in Eindhoven ontwikkelde Błażej een sterke interesse voor Computer Vision. Zelf schreef Błażej: “I enjoy working on computer vision projects immensely so I simply could not pass on the opportunity to work on the AoM project!”
In tegenstelling tot het doorzoeken van audiovisuele archieven op basis van een tekstuele zoektermen streeft Superposition een ervaring na waarbinnen de eindgebruiker in staat wordt gesteld digitale audiovisuele archieven te doorzoeken op visuele metadata. Denk bij visuele metadata aan bijvoorbeeld lijnen en vormen die te zien zijn in de oorspronkelijke archiefitems. Om dit streven te realiseren is het noodzakelijk deze visuele metadata eerst uit de archiefitems te extraheren.
In het kader van deze uitdaging heeft Błażej de afgelopen weken binnen Artifacts of Memory gewerkt aan een line matching system. Błażej heeft zich gefocust op het efficiënt detecteren, extraheren, en filteren van lijnen uit de video frames van Groninger Archieven. De resulterende software — vrij beschikbaar onder de open-source Apache licentie — vindt u hier. We zullen nu dieper ingaan op de werking en achterliggende systematiek.
De pipeline
De pipeline bestaat uit twee hoofdonderdelen. Het eerste deel betreft het verwerken van de video-archieven en het tweede deel het matchen van de gevonden lijnen uit een zoekbeeld met de overeenkomende lijnen uit het archief. In het kort betekent dit:
Stap 1: Verwerking van de video-archieven in een formaat waaruit we lijnen extraheren. Dit hoeft maar één keer te gebeuren.
- Extraheer frames van video’s om met statische gegevens te kunnen werken
- Voer voor elk frame een lijnextractie uit samen met extra features zoals lijnhoek en -lengte
- Gooi de frames zonder gedetecteerde lijnen weg en filter zwakke (korte) en sterk gelijkende lijnen weg (verminder ruis en dimensionaliteit voor gebruik in stap 2)
- Bewaar de informatie over de gefilterde gegevens in een formaat dat gemakkelijk opvraagbaar is (we kozen voor het Pandas dataframe)
Stap 2: Extraheer lijnen uit een zoekbeeld en match deze aan de database met kandidaat-overeenkomsten uit het archief. Dit gebeurt in (semi-)real-time op het apparaat van de gebruiker.
- Voer het lijnextractie- en filteralgoritme uit op de queryafbeelding
- Kies de lijn(en) die gematched moeten worden. Hoe? We geven de voorkeur aan lange, niet-horizontale lijnen.
- Voer de matchingsprocedure uit
- Haal de beste overeenkomst op en leg deze over de zoekafbeelding
Dat is alles! Hier volgt een uitgebreidere beschrijving van elke stap, met implementatiedetails.
Stap 1
Om de lijnen in de afbeeldingen te vinden, gebruiken we een methode genaamd Hough-transformatie. Het werkt op basis van een lijnrepresentatie in de vorm van (ρ, θ)-paren, waarbij ρ staat voor een afstand vanaf het nulpunt en θ voor de hoek tussen de lijn en de x-as. Merk op dat de lijn die met deze parameters wordt weergegeven, kan worden weergegeven als een punt in de Hough-space. De punten die op de lijn liggen die wordt gekenmerkt door (ρ, θ), moeten elkaar per definitie kruisen in de Hough-space. Daar maken we gebruik van, dus we scannen de Hough-space op kruispunten.
Meer over Hough-lijnen is te vinden in dit artikel. Een uitbreiding van de Hough-transformatie die we daadwerkelijk gebruiken, wordt Probabilistic Hough-transform genoemd, die geometrische eigenschappen van curves in de Hough Space gebruikt om het hele proces efficiënter te maken. Meer daarover hier.
Deze methode heeft een aantal parameters die bepalen hoeveel lijnen worden gedetecteerd. Tijdens het proces gaan we met deze parameters spelen om de ervaring te vormen: moeten er minder maar betere lijnen getoond worden, of verkiezen we juist kwantiteit boven kwaliteit? Gaan we voor langere lijnen of kortere lijnen? Meer horizontaal, of meer verticaal?
Om te voorkomen dat er zwakke lijnen voorkomen in de resultaten, vervagen we het beeld enigszins. Aangezien Hough-lijnen binaire invoer verwachten (het beeld moet zijn opgebouwd uit pixels die óf zwart óf wit zijn), laten we de afbeelding eerst door een Canny Edge-detector lopen. Zie hieronder de stadia van het detecteren van een lijn:
Merk op dat we niet alle lijnen hebben verkregen. En dat is oké. Door de parameters aan te passen, zouden we meer lijnen kunnen retourneren, maar tegen een prijs: we zouden valse lijnen vinden. Maar we geven meer om precisie (hoeveel geretourneerde artikelen zijn relevant) dan recall (verhouding van geretourneerde relevante lijnen tot het totale aantal relevante lijnen). Een hoog percentage valse positieven zou onze matches later verpesten.
We voeren deze hele procedure uit voor alle frames die we uit het archief hebben gesampled, samen met extra lengte- en hoekinformatie per regel.
Soms retourneert ons algoritme veel overlappende lijnen op dezelfde plaats, waardoor de database met onze matches kunstmatig groter wordt. We moeten deze regels eruit filteren. Dat doen we door vergelijkbare lijnen te vinden op basis van lijnhoek, en vervolgens alleen de langste lijn te kiezen uit die set.
Nu de dubbele en overlappende lijnen uit de frames zijn gefilterd kunnen we een lijst samenstellen van alle gevonden lijnen in onze set frames. Deze lijst bestaat uit dataframes die elk de begin- en eindpositie van een lijn op één videoframe bevatten, samen met de hoek en de lengte van die lijn.
Als we een plot maken van de distributie van hoeken en lengtes van alle gevonden lijnen uit de huidige set videoframes kunnen we enkele interessante conclusies trekken. Zo zijn er relatief veel horizontale en verticale lijnen (0 graden en -90/+90 graden) en zijn verreweg de meeste lijnen tussen de 200 en 300 pixels lang.
Stap 2
Nu kunnen we aan de slag met onze zoekafbeelding.
We zoeken eerst naar een lijn met een hoek die in de buurt komt van de lijn in de queryafbeelding, en vervolgens nemen we de lijn die de dichtstbijzijnde lengte heeft. Zodra die overeenkomst is gevonden, willen we elke lijn een score geven op hoe “goed” deze is. Daarvoor ontwikkelden we een scoremethode die aan elke lijn een score toekent op basis van hoek en lengte (geeft de voorkeur aan lange, niet-horizontale lijnen). Bovendien introduceren we enige willekeur in de keuze van de lijn, zodat niet altijd de regel met de hoogste score wordt gekozen. Nu we de lijnen in de queryafbeelding hebben gedetecteerd en de overeenkomsten in ons archief hebben gevonden, kunnen we de overeenkomst over de afbeelding leggen.
Vervolg
Als volgende stap kunnen we aan de presentatie van de lijn gaan werken. Nu wordt een uitsnede van het beeld getoond, zodat de lijn duidelijk is. Het nadeel is dat de “visuele context” van de lijn zo enigszins verloren gaat. We kunnen dus gaan spelen met andere uitsneden en presentaties.
