Samenvatting eindverhandeling:
Samenvatting van videosequenties m.b.v. sleutelbeelden Hiˆep Quang Luong
Recente ontwikkelingen in de multimedia compressietechnologie, gekoppeld aan een beduidende groei van computerperformantie en de wereldwijde groei van snellere internetverbindingen (b.v. ADSL of kabel), leiden tot het gebruik en de beschikbaarheid van een enorme hoeveelheid digitaal video- en audiomateriaal. Toepassingen zoals digitale bibliotheken, digitale televisie, video-op-aanvraag en multimediale informatiesystemen genereren en gebruiken grote hoeveelheden aan videomateriaal. Om zijn weg te kunnen vinden in deze informatievloed zou de gebruiker erg gebaat zijn met een inhoudsgebaseerd zoeksysteem: een systeem dat videodatabanken kan beheren om het opzoeken van relevante videosequenties op basis van hun inhoud mogelijk te maken. De gebruiker zou b.v. op zoek kunnen gaan naar alle videobestanden waarin iemand vanaf een brug op een rijdende trein springt, en hoeft enkel de desbetreffende sc`ene van deze bestanden te bekijken (de zogeheten content-based access). Het spreekt vanzelf dat dit voorlopig nog toekomstmuziek is: dit vergt immers het kunnen herkennen van objecten, verhaallijnen, het kunnen interpreteren van de zoekopdracht van de gebruiker en nog veel meer. In dit werk hebben we een eerste stap gezet in deze richting door videofragmenten samen te vatten met behulp van sleutelbeelden. Een eerste doel was om een videostroom in een set van betekenisvolle en bruikbare segmenten (shots) op te splitsen. Deze basisblokken zijn ononderbroken opgenomen segmenten video/audio en kunnen gebruikt worden voor de indexering van het inhoudsgebaseerd zoeksysteem. Een tweede doel was het groeperen van deze verscheidene shots tot sc`enes met een meer zinvolle betekenis (denk b.v. aan dialogen waarbij telkens op de spreker ingezoomd wordt of shots die opgenomen zijn in dezelfde omgeving). De hi¨erarchische structuur van de videosequentie is gegeven op figuur 1. Een laatste doel was het weergeven van sleutelbeelden, die we extraheerden uit sc`enes, op een gebruikersvriendelijke webpagina, waarbij een klik op een beeld ervoor zorgt dat de gewenste beeldsequentie wordt afgespeeld. Het samenvatten van videosequenties in sleutelbeelden verloopt dus hoofdzakelijk in 1
video
scènes
shots
beelden
tijd
Figuur 1: Structurele splitsing van video in sc`enes en shots. drie opeenvolgende fasen: shotdetectie, sc`eneclustering en representatie van de sleutelbeelden. Shotdetectie Om shots onderling te kunnen onderscheiden is het noodzakelijk om de verschillende overgangen tussen de shots te detecteren. Er zijn twee soorten shottransities: abrupte en graduele overgangen. Abrupte overgangen worden ook wel cuts genoemd en ze overspannen slechts ´e´en beeld, zoals aangegeven op figuur 2.
Figuur 2: Een videosequentie met een cut tussen beeld 3 en 4. Daarnaast kunnen cinematografische effecten gebruikt worden om twee shots te combineren. De twee meest gebruikte types van graduele overgangen zijn dissolves en wipes, zoals voorgesteld op figuren 3 en 4. 2
Bij dissolves vloeit het ene beeld langzaam in het andere beeld, door de intensiteit van de beelden te laten vari¨eren.
Figuur 3: Voorbeeld van een dissolve. Wipe is een totaal andere soort van transitie: de nieuwe shot komt tevoorschijn door een bewegende grens in de vorm van een lijn of patroon.
horizontaal
split
Figuur 4: Twee voorbeelden van wipes. In dit werk hebben we tal van verschillende shotdetectiemethoden onderzocht zowel voor ongecomprimeerde videodata als voor gecomprimeerde videosequenties. Opeenvolgende beelden in de sequentie worden met elkaar vergeleken op basis van eigenschappen zoals beeldpuntwaarden, histogrammen, randen, bewegingsvectoren, DCT-co¨effici¨enten, . . . Op basis van de verschillen van deze eigenschappen tussen opeenvolgende beelden, worden shotovergangen gedetecteerd en geclassificeerd. De performantie van de shotdetectie daalt bij aanwezigheid van ruis, snelle belichtingsvariatie (denk b.v. aan bliksemschichten of bij het binnenrijden van een tunnel), grote en snelle objectbewegingen, camerabewegingen, . . . We hebben eveneens tal van methoden onderzocht om deze problemen verhelpen. Shotdetectie wordt niet enkel gebruikt als basisfase voor het generen van samenvattingen, maar wordt onder meer gebruikt in (professionele) videobewerkingsprogramma’s: 3
shots (rechtstreeks ingevoerd vanuit de camera of vanuit een bestand) vormen kant-enklare basissegmenten die gebruikt kunnen worden bij een filmmontage. Shotdetectie kan ook een groot aandeel hebben in de performantie van videocompressie zoals MPEG-4 en daarnaast kan meta-informatie voor elk shot apart verzameld worden voor MPEG-7. Sc` eneclustering Het doel van sc`eneclustering is om shots, die (semantisch) bij elkaar horen, te groeperen op basis van b.v. kleur tot enkele entiteiten, sc`enes. Figuur 5 toont ons het principe van sc`eneclustering. Voor de groepering werden enkele clustertechnieken bestudeerd zoals K-gemiddelden algoritme en iteratieve boomclustering.
Dialoog waarbij ingezoomd wordt op de spreker
Shots die opgenomen zijn in dezelfde omgeving
Figuur 5: Gelijkaardige shots worden gegroepeerd tot sc`enes. Technieken zoals temporele correctie en integratie van domeinkennis kunnen de kwaliteit van de samenvattingen verbeteren. Temporele correctie houdt rekening met het feit dat de waarschijnlijkheid dat twee shots, die temporeel ver uit elkaar liggen, bij elkaar horen echter klein is. Bij integratie van domeinkennis worden verschillende clusters samengevoegd op basis van voorkennis over de type van videosequentie (b.v. de verschillende weerkaarten in een weerbericht). Op een hoger niveau zouden we de verschillende sc`enes in hoofdstukken kunnen groeperen, zoals bij de navigatie van een film op DVD. De computer zou dan echter de verhaallijn van de film moeten herkennen wat nog toekomstmuziek is. Representatie d.m.v. sleutelbeelden In een laatste fase hebben we de samenvatting gepresenteerd op een gebruikersvriendelijke webpagina. De webpagina is in staat om een videosequentie hi¨erarchisch te laten doorzoeken. Hi¨erarchisch doorzoeken van een videosequentie van grote videoarchieven is te verkiezen boven het sequentieel doorzoeken wegens de grote tijdswinst.
4
Het sequentieel doorzoeken kennen we het best uit het dagelijks gebruik met video: bij analoge video (denk b.v. aan een videorecorder) kunnen we als hulp bij het doorzoeken gebruik maken van het versneld afspelen of het vooruit- en achteruitspoelen van de videosequentie. Bij digitale video (denk b.v. aan programma’s die videosequenties kunnen afspelen zoals Windows Media Player of Quicktime Player ) kunnen we in software ook nog gebruik maken van een tijdsbalk. Het grote nadeel hierbij is dat we bij het doorzoeken voorkennis over de videosequentie moeten hebben en dus moeten berusten op het menselijk geheugen. We kunnen de nodige voorkennis sterk beperken door videosequenties hi¨erarchisch te doorzoeken. Naarmate we in hi¨erarchie dalen wordt de zoekruimte kleiner en krijgen we meer details (zoals shots) van de videosequentie. Een typische hi¨erarchie heeft een drietal niveaus: videosequenties, sc`enes en shots. Op 2 a` 3 muisklikken hebben we ons gewenste shot, wat veel sneller is dan wanneer we de videosequentie sequentieel gaan doorzoeken. Om goede samenvattingen te maken is het nodig om de meest representatieve sleutelbeelden te selecteren van elke sc`ene (of shot), dit zijn de sleutelbeelden die de meest relevante informatie bevatten over de desbetreffende sc`ene (of shot). In ons werk hebben we verscheidene methoden besproken om goede sleutelbeelden te kiezen. We kunnen ´e´en of meerdere sleutelbeelden per sc`ene of shot selecteren naargelang de (vari¨erende) inhoud, duur, . . . Toch zijn meerdere sleutelbeelden soms niet genoeg om een shot effici¨ent voor te stellen zoals voorgesteld op figuur 6. Dit probleem komt vaak voor als er camerabewegingen aanwezig zijn. We kunnen de shots dan effici¨enter voorstellen door ´e´en panoramisch beeld.
Figuur 6: Ineffici¨ente voorstelling van een shot met camerabeweging door drie sleutelbeelden.
5
Panoramische beelden Panoramische beelden kennen we het best als langwerpige foto’s of als virtuele 3D-werelden van b.v. VR Quicktime op het internet. Maar panoramische beelden hebben nog tal van andere toepassingen zoals het cre¨eren van hoge resolutiebeelden, videocompressie (MPEG-4 sprite coding), reconstructie van omgevingen onafhankelijk van hun grootte of bereik (b.v. inscannen van heel grote documenten of bij constructie van grote remote-sensing beelden), stabilisatie van schokkende videosequenties, . . . Zo’n panoramisch beeld biedt ons ook veel meer informatie aan dan ´e´en of meerdere sleutelbeelden en wordt daarom gebruikt om een shot met camerabeweging voor te stellen. In figuur 7 wordt het panoramisch beeld gegeven van de shot die voorgesteld werd met behulp van sleutelbeelden in figuur 6.
Figuur 7: Een panoramisch beeld. De ineffici¨ente voorstelling wordt gegeven in figuur 6. De constructie van panoramische beelden verloopt in twee fasen: eerst wordt de camerabeweging ge¨estimeerd door de twee opeenvolgende beelden ten opzichte van elkaar te 6
registreren en vervolgens wordt de beeldpuntinformatie geselecteerd uit de overlappende regio’s om het canvas te vullen. Hiervoor hebben we in ons werk verscheidene methoden voorgesteld om panoramische beelden te genereren uit videosequenties. Interactieve webpagina De samenvatting van een videosequentie is een set van relevante sleutelbeelden vn de sc`enes. Deze sleutelbeelden kunnen opgeslagen worden in een databank en vormen zo de basis voor de indexering van het inhoudsgebaseerd zoeksysteem. Webpagina’s kunnen de sleutelbeelden (in verschillende niveaus van hi¨erarchie) ophalen en aan de gebruiker presenteren. Er zijn tal van mogelijkheden om de samenvatting visueel attractiever te maken voor de gebruiker met betrekking tot de webpagina. In ons werk hebben we een aantal mogelijkheden besproken en sommige ervan zijn ook ge¨ımplementeerd: • bij elke samenvatting moeten we de belangrijkste onderdelen extra accentueren, ook bij samenvattingen van videosequenties. Daarom kennen we aan elke shot of sc`ene een belangrijkheidsfactor toe. De grootte van de sleutelbeelden worden dan geschaald met de belangrijkheidsfactor: belangrijke shots of sc`enes worden dan geaccentueerd en onbelangrijke shots of sc`enes kunnen verwijderd worden of voorgesteld worden door een kleinere sleutelbeeld. De belangrijkheidsfactor kan berekend worden op verschillende manieren en kan zelfs afhangen van de zoekopdracht van de gebruiker: stel b.v. dat een gebruiker een actiesc`ene zoekt, dan kunnen alle sc`enes met veel (object)beweging voorgesteld worden door een grotere sleutelbeeld. Andere mogelijke factoren zijn de duur of lengte van een shot, de repetiviteit of omgekeerd de uniciteit van een shot, . . . • de samenvatting wordt voorgesteld in een ”stripboek”-stijl, waardoor ze geschikt is om op papier uit te printen of op een webpagina te tonen. Daarom wensen we meestal ook dat de layout zo effici¨ent mogelijk is. In ons werk stellen we enkele heuristische algoritmen voor die de sleutelbeelden op een compacte manier voorstellen. Het principe wordt getoond op figuur 8. • de webpagina kan een tijdslijn bevatten die gesynchroniseerd is met de sleutelbeelden: wanneer de gebruiker met de muis over een sleutelbeeld gaat, dan wordt de desbetreffende sc`ene aangeduid op de tijdslijn. Omgekeerd kan de gebruiker op een willekeurige positie van de tijdsbalk klikken en zal de webpagina de sleutelbeelden van de sc`enes tonen die dicht bij de tijdspositie liggen. Hierdoor hebben we een verband met de traditionele tijdsbalken.
7
2
3
1 2
3
4
5
1 4
5 6
6
(a) de na¨ıeve methode
(b) de heuristische methode
Figuur 8: Verschillende geproduceerde indelingen. • de webpagina kan een venster of popup tonen met extra informatie over de sc`enes of shots. De extra informatie kan van syntactische aard zijn, b.v. de duur, bewegingsinformatie, de positie in de sequentie, . . . De informatie kan ook van semantische aard zijn, b.v. de titel, de inhoudsbeschrijving, de namen van eventuele personen of objecten die in de sc`ene voorkomen, . . . De semantische informatie kan manueel ingevoerd worden of door object-, gezichts-, spraak- of tekstherkenning automatisch ingevuld worden. Een voorbeeld van een interactieve webpagina wordt getoond op figuur 9. Toepassingen Samenvattingen van videosequenties kunnen in veel toepassingen gebruikt worden. Zoals eerder vermeld kunnen enorm grote videoarchieven op een veel snellere en gebruikersvriendelijkere manier worden doorzocht naar gewenste shots. We denken hierbij b.v. aan archieven van televisiezenders zoals 50 jaar televisie of bij een bewakingsfirma die op zoek moet gaan naar de cruciale shots. Na een vergadering of conferentie kunnen de deelnemers naast een verslag eveneens een papieren samenvatting krijgen van de opgenomen vergadering. Nieuwssites zoals vrtnieuws.net kunnen automatisch gegenereerd worden. De bijhorende tekst kan b.v. bekomen worden met behulp van spraakherkenning. De kwaliteit van de samenvattingen wordt hierbij beter door de shots met nieuwslezers te detecteren m.b.v. sjablonen, zij vormen immers de ankerpunten in de nieuwsuitzending. Meer details hierover vindt u terug in mijn eindverhandeling.
8
Figuur 9: Een webpagina met de visuele samenvatting van een videosequentie. Enkele eindresultaten en een elektronisch kopij van mijn thesis vindt u terug op de bijgeleverde cd-rom.
9
