Content-aware video resizing

 

Content-aware video resizing

 
In het kader van zijn afstudeeronderzoek ontwikkelde Deforce een methode voor het op een intelligente manier aanpassen van de resolutie van videobeelden, zogenaamde content-aware video resizing. Het belangrijkste doel was een algoritme te verkrijgen dat HD-video in real time kan verwerken, dus zonder voorkennis van de video.
 
Content-aware video resizing is een methode om video te verschalen. Indien een video van resolutie moet veranderen, kan dit gedaan worden door de video te verschalen of door de video bij te knippen. Beide methoden hebben echter hun nadelen. Bij het verschalen naar andere verhoudingen zal het beeld vervormen. Als we de video bijsnijden, kunnen we cruciale elementen van het beeld verliezen. In deze masterproef werd een methode ontwikkeld die op een intelligente manier probeert de resolutie van een video aan te passen. Met behulp van de nodige beeldherkenning worden de voorgrondelementen in de video gedetecteerd en vervolgens wordt afhankelijk van deze inhoud een verschaling uitgevoerd. Een algoritme dat kijkt naar de inhoud van het beeld om een verschaling uit te voeren, wordt content-aware genoemd. Het gebruikte algoritme is gebaseerd op seam carving (Avidan & Shamir, 2007); hierbij worden aaneensluitende rijen van pixels gezocht ( seams genaamd) die visueel weinig interessant zijn. Dit gebeurt door aan alle pixels in het beeld een waarde toe te kennen die aanduidt hoe belangrijk de inhoud van elke pixel is. Indien de video wordt verkleind, worden deze pixels verwijderd in volgorde van hun belangrijkheid. Het omgekeerde gebeurt bij een verhoging van de resolutie: hierbij worden deze pixels verdubbeld. Op deze manier blijven de voorgrondelementen ongewijzigd en treedt er weinig zichtbare vervorming op. Enkel de onbelangrijke achtergrondelementen worden gewijzigd. Natuurlijk kunnen niet zomaar pixels aan het beeld toegevoegd of eruit verwijderd worden. Daarom vormen de pixels aaneensluitende ketens die de volledige afbeelding beslaan zodat in elke rij of kolom een enkele pixel gewijzigd wordt. Een voorbeeld hiervan is te zien in figuur 1, waar een afbeelding verkleind werd met 200 pixels in de breedte. Het doel is om dit algoritme dat ontwikkeld werd voor het verschalen van afbeeldingen, uit te breiden naar video en het mogelijk te maken om HD-video in real time te verwerken.
 
Probleemstelling
Seam carving is bedoeld voor statische afbeeldingen. Er zijn verschillende methoden gepubliceerd om seam carving ook uit te breiden naar video. Al deze methoden zijn echter heel traag en kunnen niet in real time uitgevoerd worden op hogere resoluties. De wens was dat video met HD-resoluties (1280 bij 720 pixels of hoger) in real time zouden kunnen worden verwerkt. Bovendien steunen sommige algoritmes op informatie uit toekomstige beelden waardoor de volledige video voorhanden moet zijn. Het belangrijkste doel van deze masterproef is om een algoritme te verkrijgen dat realtime zijn werk kan doen zonder voorkennis van de video. Dit moet het mogelijk maken om een live videostream te verwerken. Hierbij is geen informatie beschikbaar over toekomstige beelden, wat het behalen van een goed resultaat bemoeilijkt.
 
Figuur 1. Seam carving toegepast op een afbeelding
 
Om het algoritme te versnellen zijn er verschillende mogelijkheden die onderzocht moeten worden. Ten eerste kan worden overgeschakeld op andere algoritmes die sneller kunnen worden berekend. Anderzijds kan worden bestudeerd hoe bestaande algoritmes kunnen worden aangepast om gebruik te maken van de parallelle rekenkracht van hedendaagse computers. Om dit te doen werd gekozen voor het gebruik van OpenCL. Dit framework moet het mogelijk maken om zware rekentaken te laten uitvoeren op de processor van een grafische kaart. De moeilijkheid is dat de berekening van sommige algoritmes niet geschikt is voor uitvoering op de architectuur van deze processoren.

Natuurlijk kan niet elke videosequentie efficiënt verkleind worden zonder dat hierbij de beeldinhoud vervormd wordt. Het soort use cases dat we voor ogen hebben bij dit algoritme zijn eerder statische videosequenties. Het doel is om het toe te passen op videoconferencing of ander vergelijkbaar beeldmateriaal. Over het algemeen is er niet al te veel beweging gedurende dergelijke video’s, waardoor deze goed kunnen worden verschaald zonder dat er serieuze vervormingen optreden. Het voorgestelde algoritme is bijgevolg enkel bedoeld voor videosequenties met een vast camerastandpunt. Het moet ook mogelijk zijn om het in de toekomst uit te breiden naar video’s waar de camera beweegt.

Alhoewel seam carving goed werkt bij sommige afbeeldingen, slaagt het er niet altijd in om een zinnige verschaling te berekenen voor elk mogelijk beeld. In een video is er echter meer informatie voorhanden omdat we kunnen kijken naar voorgaande beelden. Om de kwaliteit van het algoritme te verbeteren moet deze informatie gebruikt kunnen worden om het algoritme bij te sturen. Om bij video goede resultaten te krijgen is het niet voldoende dat individuele beelden een acceptabel resultaat opleveren. Daarom moet verzekerd worden dat opeenvolgende beelden in de video een zekere continuïteit behouden. Door de veranderende beeldinhoud kan het immers gebeuren dat er grote verschillen zijn in de berekende verschaling van beelden die elkaar opvolgen in de video. Om de visuele perceptie te verbeteren moet het algoritme ook rekening houden met het resultaat van de voorgaande beelden.
Met seam carving is het niet alleen mogelijk om een video naar een vaste resolutie te verschalen, bij het verkregen resultaat is het ook mogelijk om alle denkbare afmetingen tussen de oorspronkelijke resolutie en de gewenste resolutie te verkrijgen. Dit maakt het mogelijk om ’multi-size’ video’s te maken die de gebruiker interactief kan verschalen naar de gewenste afmeting. Willen we dit op een nuttige manier kunnen gebruiken, dan moet deze informatie efficiënt kunnen worden opgeslagen. Er moet geprobeerd worden deze metadata beperkt te houden in grootte met als doel deze te verkleinen tot de grootte slechts een fractie van de video beslaat.
 
Bereikt resultaat
De verkregen oplossing steunt op een licht gewijzigde vorm van seam carving. Het resultaat is een benaderende oplossing van het probleem, waardoor we de berekening veel sneller kunnen uitvoeren. Hoewel de oplossing niet ideaal is, blijkt de kwaliteit van het resultaat van dit algoritme bijna evenwaardig te zijn aan die van het resultaat van bestaande algoritmes. Enkel bij extreme wijzigingen in resolutie is de kwaliteit minder. In werkelijkheid is dit geen groot probleem omdat het meeste videomateriaal slechts beperkt kan worden verschaald voordat belangrijke beeldinhoud vervormd wordt.
Om het resultaat bij video’s acceptabel te houden waren verschillende aanpassingen nodig. De detectie van voorgrondelementen maakt niet enkel gebruik van algoritmes die naar individuele beelden kijken, zoals de gradiënt of een saliency -algoritme dat vaak gebruikt wordt in methoden voor afbeeldingen. Omdat er met video gewerkt wordt, houdt het algoritme ook rekening met bewegende objecten. Daarom werd gebruikgemaakt van een optical-flowalgoritme om beweging te kunnen detecteren. Door te vermijden dat bewegende objecten worden aangepast bij het verschalen, zal er relatief weinig vervorming merkbaar zijn voor de waarnemer omdat de aandacht getrokken wordt door de bewegende elementen in het beeld.

Een laatste belangrijke stap was het voorkomen van storende discontinuïteiten in opeenvolgende beelden. Door het gebruik van het benaderende algoritme was het moeilijk om dit te behalen. Het resultaat van naburige beelden in de videostroom bleek vaak sterk af te wijken, waardoor een heel schokkerig beeld ontstond. Uiteindelijk werd ervoor gekozen om de maximale afwijking tussen de verschaling van opeenvolgende beelden te beperken tot bepaalde grenzen. De berekende seams in de videosequentie worden zoveel mogelijk constant gehouden en enkel indien nodig verplaatst. Indien ze verplaatst worden, wordt bovendien opgelegd hoe ver ze mogen afwijken. Afhankelijk van de inhoud van de video kan de gebruiker deze grenzen bijstellen. Dankzij deze beperkingen worden schokkerige effecten in de resulterende video geminimaliseerd.

Video met een SD-resolutie kan probleemloos in real time verwerkt worden, iets wat met bestaande implementaties niet mogelijk was. Het doel was echter om dit ook voor HD-resoluties en hoger mogelijk te maken. Voor een testsequentie van 1280 bij 720 pixels groot kan op een moderne CPU ongeveer 12 beelden per seconde gehaald worden. Om dit resultaat te behalen werd voor een gedeelte van het algoritme gebruikgemaakt van multithreading om de meerdere processoren van een CPU te benutten. Het meeste videomateriaal is typisch tussen de 25 à 30 beelden per seconde, met verdere optimalisatie van de implementatie zou het mogelijk moeten zijn om dit doel te behalen. Dit is een versnelling van enkele ordes van grootte ten opzichte van andere systemen die nauwelijks 2 beelden per seconde halen op een video van 400 bij 300 pixels (Grundmann e.a., 2010). De grote verbetering in snelheid is dankzij het eenvoudigere algoritme, waarvan de uitvoeringssnelheid lineair schaalt met het aantal pixels in het beeld. Andere algoritmes daarentegen hebben vaak een hogere complexiteit of worden complexer om te berekenen naarmate de videosequentie langer wordt. Nog hogere resoluties verwerken lijkt ook haalbaar in de toekomst aangezien de benodigde berekeningen maar lineair toenemen.

Alhoewel het algoritme gebaseerd op seam carving niet echt geschikt is om parallel uit te voeren, werd wel bekeken hoe de beeldverwerkingstaken versneld kunnen worden. Vooral het gebruik van optical flow heeft een grote impact op de uitvoeringstijd. Met OpenCL werd een implementatie van een optical-flowalgoritme gemaakt. Er werd gekozen voor een aangepaste vorm van Lucas-Kanade. Dit algoritme is uiterst geschikt voor uitvoering op een grafische processor omdat de berekening ervan goed gebruikmaakt van de mogelijkheden van de hardware. Jammer genoeg is de kwaliteit van Lucas-Kanade redelijk laag in vergelijking met andere algoritmes voor het berekenen van optical flow. Uit de testresultaten blijkt dat een grafische processor een serieuze snelheidsverbetering kan betekenen, maar om echt bruikbaar te zijn is er een beter algoritme nodig. Omdat programmeren op de processor van een grafische kaart nog relatief nieuw is, wordt er nog volop onderzoek gedaan naar betere algoritmes.

Een voorbeeld van de output van het algoritme is te zien in figuur 2. Dit is het soort scène waarvoor het algoritme voornamelijk bedoeld is: videoconferencing. Alhoewel het ook bruikbaar is voor eender welke video waar gefilmd is vanuit een statisch camerastandpunt. In video waar de beweging beperkt blijft, geeft het algoritme een acceptabel resultaat. Natuurlijk kan niet elke sequentie zonder vervorming verkleind of vergroot worden. Voor het soort inhoud waarvoor het bedoeld is, is het resultaat toereikend. Het grootste nadeel van het resulterende systeem is de beperking van een vast camerastandpunt. Voor de use case die vooropgesteld werd, is dit geen probleem. Veel videomateriaal bestaat juist wel uit scènes met dynamische camerastandpunten, waardoor de toepasbaarheid beperkt blijft. Een mogelijke oplossing hiervoor wordt besproken in de paragraaf ‘Verdere uitwerking’.
Figuur 2. Resultaat van seam carving op een video
 
Ten slotte werd ook een eenvoudig systeem ontwikkeld dat het mogelijk maakt om de video in verschillende resoluties weer te geven. Dit wordt bereikt door het resultaat van het algoritme op te slaan. Met dit resultaat kunnen ook alle tussenliggende resoluties verkregen worden. Bovendien kan de video even ver vergroot worden als verkleind. Deze informatie wordt in een bestand opgeslagen en bijgehouden samen met de video. Door compressie toe te passen op deze gegevens is het mogelijk ze te verkleinen tot ze slechts een fractie van de grootte van de video beslaan. In een applicatie die deze informatie kan interpreteren, is het mogelijk om de video af te spelen en interactief de resolutie te veranderen. Om dit te realiseren werd een eenvoudig bestandsformaat gemaakt en een bijbehorende videospeler die deze bestanden kan interpreteren. De videospeler maakt het mogelijk om de resolutie van de video te veranderen volgens de berekende verschaling. Op deze manier kan de video bekeken worden op beeldschermen met verschillende verhoudingen, waarbij de video binnen de mogelijke grenzen wordt verschaald om zo goed mogelijk te passen in de gewenste verhouding.
 
Toepasbaarheid
Vandaag de dag hebben alle toestellen die video afspelen een videoscaler aan boord. Hiermee kan een video worden verschaald tot de resolutie van het toestel waarop deze wordt weergegeven. Een videoscaler is echter niet in staat om ook de verhoudingen van het beeld aan te passen zonder dat hierbij de inhoud van de video vervormd wordt. Met het voorgestelde algoritme is dit wel mogelijk. Door de video te verkleinen of te vergroten kunnen andere beeldverhoudingen bereikt worden, waarbij zoveel mogelijk geprobeerd wordt de belangrijkste objecten in het beeld onveranderd te houden. Enkel onbelangrijke details worden hierbij vervormd. Het is belangrijk om op te merken dat het hier voorgestelde algoritme niet gebruikt kan worden om bijvoorbeeld de resolutie van een video te verdubbelen. Hiervoor wordt altijd de voorkeur gegeven aan een scaler die de eigenlijke beeldinhoud ongewijzigd laat. Als daarentegen geen uniforme scaling mogelijk is, kan het algoritme gebaseerd op seam carving ingezet worden om de video aan te passen. Bovendien moet de resulterende video niet beperkt zijn tot een enkele resolutie. De video kan verschaald worden naar alle tussenliggende resoluties. Hiervoor zijn enkel wat extra metadata nodig die de verschaling beschrijven. Zo is het bijvoorbeeld mogelijk om een live video samen met de bijbehorende metadata te streamen naar verschillende ontvangers. De ontvanger kan de video dan aanpassen aan de verhoudingvan zijn beeldscherm; hierbij kan de video in de opgegeven dimensie worden verkleind of vergroot tot de gewenste verhouding bereikt is.
 
Verdere uitwerking
De grootste beperking van het huidige algoritme is dat het enkel goede resultaten levert bij video gefilmd vanuit een vast camerastandpunt. Het moet evenwel mogelijk zijn om het uit te breiden naar andere soorten video’s. Momenteel wordt optical flow gebruikt om bewegende objecten te detecteren, iets wat problemen oplevert als de camera aan het bewegen is. Een betere oplossing is om gebruik te maken van motion estimation zoals dit gebruikt wordt in videocompressie. Door block motion estimation te gebruiken kan voor elk blok pixels bekeken worden waar deze zich naartoe verplaatsen door twee beelden heen. Deze informatie kan gebruikt worden om de verschaling bij te sturen. De seams die gevonden zijn in een beeld, kunnen overeenkomstig met de berekende motion vectors verplaatst worden, zodanig dat dezelfde inhoud wordt weggesneden door de hele video heen. In het verleden is een publicatie verschenen die een mogelijk algoritme voorstelt gebaseerd op motion estimation (Hyeong-Min Nam e.a., 2010). De voorstellen die hierin gedaan werden kunnen, zij het met de nodige aanpassingen, ook toegepast worden op het voorgestelde algoritme. Een voordeel van het gebruik van motion estimation is dat deze al uitgevoerd wordt door een video-encoder. Als de content-aware resizing samen met de compressie van de video gebeurt, kan het resultaat van de motion estimation hergebruikt worden bij het berekenen van een verschaling. Dit zou het algoritme nog verder versnellen aangezien de optical-flowberekening dan overbodig wordt. Voor encodering van video is ook speciale hardware beschikbaar waardoor deze berekening zeker in real time kan gebeuren.
Daarnaast kan ook nog verder worden geëxperimenteerd met andere manieren om voorgrondobjecten te detecteren. Zo kan bijvoorbeeld gezichtsdetectie worden gebruikt om gezichten te detecteren en deze te beschermen tegen vervormingen. Als uitgegaan wordt van videoconferencing, is men er immers zeker van dat de video personen zal bevatten. Dit werd al uitgeprobeerd, maar om goede resultaten te behalen is een systeem nodig dat betrouwbaar gezichten kan volgen door de hele video heen. De implementatie die werd voorgesteld is nog niet helemaal realtime voor HD-resoluties. Verdere optimalisaties zijn nog nodig om ook hogere resoluties te kunnen verwerken. Indien motion estimation gebruikt wordt en voldoende snel kan worden uitgevoerd, verdwijnt al een belangrijke factor van de totale uitvoeringstijd.
Ten slotte kan seam carving ook voor andere doeleinden worden ingezet. In het verleden is al onderzoek gedaan naar het toepassen van seam carving voor compressie van afbeeldingen (Nguyen Thi Nhat Anh e.a., 2009). Er kan nog verder worden bestudeerd hoe dit kan worden uitgebreid tot compressie van video.
 
Literatuur
Avidan, S. & A. Shamir (2007). Seam carving for content-aware image resizing. ACM Transactions on Graphics , Volume 26, Issue 3. Grundmann, M. e.a. (2010). Discontinuous seam-carving for video retargeting. 2010 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) .
Hyeong-Min Nam e.a. (2010). Low complexity content-aware video retargeting for mobile devices. IEEE Transactions on Consumer Electronics , Volume 56, Issue 1, pp. 182-189.
Nguyen Thi Nhat Anh, Wenxian Yang & Jianfei Cai (2009). Seam Carving Extension: A Compression Perspective. MM ‘09 Proceedings of the 17th ACM international conference on Multimedia .
 
Dieter Deforce is afgestudeerd aan de Hogeschool Gent als industrieel ingenieur informatica en is nu Java Software Engineer bij RealDolmen. E-mail: deforcedieter@hotmail.com.

Tag

Onderwerp



Niet gevonden? Vraag het de redactie!

Heeft u het antwoord op uw vraag niet gevonden, of bent u op zoek naar specifieke informatie? Laat het ons weten! Dan zorgen we ervoor dat deze content zo snel mogelijk wordt toegevoegd, of persoonlijk aan u wordt geleverd!

Stel uw vraag