ISSN:
1436-6304
Schlagwort(e):
Graph partitioning
;
local search
;
real timevideo signal processing
;
Graphen-Partitionierung
;
Lokale Suche
;
Real-time Videosignalverarbeitung
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Wirtschaftswissenschaften
Beschreibung / Inhaltsverzeichnis:
Zusammenfassung Videoalgorithmen transformieren Videosignale, also die zur Bilderzeugung notwendigen Informationseinheiten, um Bildqualität oder die Möglichkeiten spezieller Features, wie Teletext oder Bild-in-Bild-Wiedergabe, zu erhöhen. Eigene, anwendungsspezifische und häufig nur einem Videoalgorithmus zuteilbare, schnelle Videosignalprozessoren sind für die Ausführung von Videoalgorithmen verantwortlich. Die Zuordnung der Algorithmen und Prozessoren ist, aufgrund der großen Zahl zu beachtender Restriktionen, ein NP-schweres Problem, so daß eine Aufspaltung in die drei Teilprobleme Terminierung, Partitionierung und Scheduling von Operationen sinnvoll wird. In der vorliegenden Arbeit werden das Partitionierungsproblem und die Beschreibung von Videoalgorithmen mittels Signalflußgraphen betrachtet. Ein auf lokaler Suche basierendes Lösungsverfahren erzeugt rekursiv Bipartitionen des Graphen, die komplexe Nachbarschaften variabler Tiefe generieren. Rechenergebnisse zeigen, daß die vielzitierte Universalität und Flexibilität lokaler Suchverfahren erfolgreich zur Lösung schwieriger, stark restringierter Probleme genutzt werden können.
Notizen:
Abstract We discuss the use of local search techniques for mapping video algorithms onto programmable high-performance video signal processors. The mapping problem is very complex due to many constraints that need to be satisfied in order to obtain a feasible solution. The complexity is reduced by decomposing the mapping problem into three subproblems, namely delay management, partitioning, and scheduling. We present the partitioning problem and the representation of video algorithms by signal flow graphs. Furthermore, we propose a solution strategy that is based on recursive bipartitioning of these graphs. The bipartitions are generated using a variable-depth search algorithm. The results demonstrate that the frequently cited flexibility of local search techniques can be successfully exploited in handling complicated problems.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01719261
Permalink
