 |
Claims  |
|
|
What is claimed is:
1. In a broadcast system, a method for performing broadcast operations,
comprising the steps of:
specifying an instance of a first broadcast constituent;
specifiying an instance of a second broadcast constituent;
specifying an instance of a third broadcast constituent that is of an order
higher than the first and second broadcast constiutent;
specifying an association in the context of the third broadcast constituent
that identifies a relative temporal relationship between the first and
second broadcast constituents;
for each constituent of the first and second broadcast constituents,
specifying at least one corresponding material that represents the
broadcast constituent, said material identifying a signal which represents
the broadcast constituent;
for each material, specifying at least one corresponding media that
represents the material, said media identifying a media from where the
signal is transferred; and
for a particular broadcast constituent, identifying the media that
manifests the broadcast element based upon the material and media
specified, such that the media representative of the first and second
broadcast constituents are played in sequence.
2. The method of claim 1, wherein the context is a unique context for the
media representatives of at least one subordinate element of the third
broadcast constituent.
3. The method of claim 1, wherein a structural change made to the broadcast
constituent will be reflected in all uses of the broadcast constituent.
4. The method of claim 1, further comprising the steps of:
relating each constituent of the first and second broadcast constituents to
the first and second broadcast constituents through proxy relations;
specifying a plurality of alternative constituents for each of the
broadcast constituents using proxy relations; and
broadcasting at least one of the plurality of alternative constituents
according to a set of selection rules associated with the proxy relations.
5. The method of claim 4, wherein the proxy relations allow the
specification of a plurality of alternative constituents executing in
parallel, wherein the proxy relation causes a broadcast of one of the
plurality of alternative constituents executing in parallel.
6. The method of claim 4, wherein the first broadcast constituent is of
indeterminate duration, said first broadcast constituent followed by the
second broadcast constituent, said second broadcast constituent having a
prespecified start time, a fourth broadcast constituent being in sequence
between the first and second broadcast constituents, the method further
comprising the step of using said proxy relations to cause the broadcast
of at least one of a plurality of alternative constituents comprising the
fourth broadcast constituent, such that the fourth broadcast constituent
completely fills the time between the end of the first broadcast
constituent and the start of the second broadcast.
7. The method of claim 6, further comprising the step of using a set of
selection rules to cause the selection of the at least one of a plurality
of alternative constituents for broadcast based on an actual ending time
of the first broadcast constituent and a duration of the at least one of a
plurality of alternative constituents for the fourth constituent and the
prespecified start time of the second broadcast constituent.
8. The method of claim 7, further comprising the step of automatically
eliminating as alternative constituents any of the plurality of
alternative constituents that cannot be executed in the time remaining
between the actual ending time of the first broadcast constituent and the
prespecified start time of the second broadcast constituent.
9. The method of claim 4, further comprising the step of using the proxy
relations to allow the specification of a plurality of alternative
representations for each of the broadcast constituents, said proxy
relations containing a plurality of selection rules which determine an
appropriate representation, the selection rules causing a temporally
latest alternative of the at least one possible alternative
representations to be the appropriate representation.
10. The method of claim 4, wherein the proxy relations enable at least one
alternate constituent to execute in parallel with a preferred constituent.
11. The method of claim 4, wherein the proxy relations enable at least one
alternate constituent to execute following a live broadcast event.
12. The method of claim 1, wherein each instance of a broadcast constituent
contains a different one of the at least one corresponding material that
represents the broadcast constituent.
13. The method of claim 4, wherein the proxy relations specify a backup
resource for the at least one corresponding material.
14. The method of claim 4, wherein the proxy relations enable a constituent
to be scheduled multiple times with different material and media
representations playing at different times.
15. The method of claim 1, wherein the broadcast constituents are used
repetitively in a plurality of broadcast patterns.
16. The method of claim 1, further comprising the step of substituting a
variable element for a plurality of constituents.
17. The method of claim 1, further comprising the step of using the
association to control the relative ordering of constituents and broadcast
elements in the context of the association, the association being
independent of time.
18. The method of claim 17, wherein the association defines a temporal
relationship between scheduling elements.
19. The method of claim 1, wherein playing the first and second broadcast
constituents in sequence comprises the steps of:
defining the broadcast elements in terms of time-independent interval
relationships;
organizing the intervals into a constraint matrix;
producing a relationship matrix by solving the constraint matrix;
reducing the relationship matrix to a sequence of start and end points of
the broadcast elements;
using the start and end points to constrain broadcast constituent
programming.
20. The method of claim 19, further comprising the step of defining the
interval relationships using thirteen atomic relationships, the interval
relationships being encoded as binary numbers where each bit represents
one of the thirteen atomic relations.
21. The method of claim 19, further comprising the step of adding temporal
constraints by instantiating some of the endpoints of the elements, the
temporal constraints specified as hard time constraints and variable
durations and offsets.
22. The method of claim 19, wherein some members of the sequence of end
points may be a cluster of endpoints denoting simultaneity.
23. The method of claim 19, wherein the step of reducing the relationship
matrix to a sequence of start and end points comprises the step of
creating the sequence of end points by converting the relationship matrix
to a matrix of end point relations by a look-up process on each entry and
then topologically sorting the end point relations.
24. The method of claim 19, further comprising the step of identifying
violations of element ordering constraints by false values in the
relationship matrix, the violations of element ordering constraints
indicating a conflict between pairs of intervals.
25. The method of claim 1, further comprising the step of generating a log
reflective of the actual material broadcast, said log comprising fully
constructed material and media compositions, said log comprising all
associations and relations between material and media at every level of
composition.
26. The method of claim 1, wherein the associations and proxy relations
enable a recording of new media from an incoming signal, said recording
synchronized with the re-broadcast of the incoming signal, said recording
later serving as a broadcast constituent.
27. The method of claim 1, wherein a recursive descent through the
broadcast composition structure results in finding a constituent with a
valid representation and a lateral search across representations finds the
best media to play in response to the scheduling needs of the constituent.
28. A broadcast system comprising:
a processor;
a plurality of media devices coupled to the processor;
an instance of a first broadcast constituent;
an instance of a second broadcast constituent;
an instance of a third broadcast constituent that is of an order higher
than the first and second broadcast constituent;
an association in the context of the third broadcast constituent that
identifies a relative temporal relationship between the first and second
broadcast constituents;
at least one corresponding material specified for each constituent of the
first and second broadcast constituents, said at least one corresponding
material representing the broadcast constituent, said material identifying
a signal which represents the broadcast constituent;
at least one corresponding media specified for each material, said at least
one corresponding media representing the material, said media identifying
a media from where the signal is transferred, said media manifesting the
broadcast element based upon the material and media specified, such that
the media representative of the first and second broadcast constituents
are played in sequence.
29. The broadcast system of claim 28, further comprising:
proxy relations that relate each constituent of the first and second
broadcast constituents to the first and second broadcast constituents;
a plurality of alternative constituents specified for each of the broadcast
constituents using proxy relations; and
a set of selection rules associated with the proxy relations that control
the broadcast of at least one of the plurality of alternative
constituents.
30. The broadcast system of claim 29, wherein the proxy relations are used
to specify a plurality of alternative representations for each of the
broadcast constituents, said proxy relations containing a plurality of
selection rules which determine an appropriate representation, the
selection rules causing a temporally latest alternative of the at least
one possible alternative representations to be the appropriate
representation.
31. The broadcast system of claim 29, wherein the proxy relations are used
to enable a constituent to be scheduled multiple times with different
material and media representations playing at different times.
32. The broadcast system of claim 28, wherein each instance of a broadcast
constituent contains a different one of the at least one corresponding
material that represents the broadcast constituent.
33. The broadcast system of claim 28, wherein the association is used to
control the relative ordering of constituents and broadcast elements.
34. The broadcast system of claim 28, further comprising:
broadcast elements defined in terms of time-independent interval
relationships;
a constraint matrix containing the time-independent interval relationships;
a relationship matrix that is a solution to the constraint matrix;
a sequence of start and end points of the broadcast elements formed by
reducing the relationship matrix;
a constraint in programming broadcast constituents, said constraint based
on the start and end points.
35. The broadcast system of claim 34, further comprising thirteen atomic
relationships that define the interval relationships, the interval
relationships being encoded as binary numbers.
36. The broadcast system of claim 34, further comprising temporal
constraints added by instantiating some of the endpoints of the elements.
37. The broadcast system of claim 34, further comprising:
a sequence of start and end points reduced from the relationship matrix by
creating the sequence of end points by converting the relationship matrix
to a matrix of end point relations by a look-up process on each entry and
then topologically sorting the end point relations;
an identification of violations of element ordering constraints by false
values in the relationship matrix, the violations of element ordering
constraints indicating a conflict between pairs of intervals.
38. The broadcast system of claim 28, further comprising associations and
proxy relations that enable a synchronized recording and rebroadcast of
new media from an incoming signal, said recording serving as a broadcast
constituent.
39. A computer readable medium containing executable instructions which,
when executed in a processing system, causes the system to perform the
steps performing broadcast operations comprising the steps of:
specifying an instance of a first broadcast constituent;
specifying an instance of a second broadcast constituent;
specifying an instance of a third broadcast constituent that is of an order
higher than the first and second broadcast constituent;
specifying an association in the context of the third broadcast constituent
that identifies a relative temporal relationship between the first and
second broadcast constituents;
specifying at least one corresponding material for each constituent of the
first and second broadcast constituents, said at least one corresponding
material representing the broadcast constituent, said material identifying
a signal which represents the broadcast constituent;
specifying at least one corresponding media for each material, said at
least one corresponding media representing the material, said media
identifying a media from where the signal is transferred; and
for a particular broadcast constituent, identifying the media that
manifests the broadcast element based upon the material and media
specified, such that the media representative of the first and second
broadcast constituents are played in sequence.
40. The computer readable medium of claim 39, wherein the instructions
cause the system to perform the steps performing broadcast operations
further comprising the steps of:
relating each constituent of the first and second broadcast constituents to
the first and second broadcast constituents through proxy relations;
specifying a plurality of alternative constituents for each of the
broadcast constituents using proxy relations; and
broadcasting at least one of the plurality of alternative constituents
according to a set of selection rules associated with the proxy relations.
41. The computer readable medium of claim 40, wherein the instructions
cause the system to perform the steps performing broadcast operations
further comprising the step of using the proxy relations to allow the
specification of a plurality of alternative representations for each of
the broadcast constituents, said proxy relations containing a plurality of
selection rules which determine an appropriate representation.
42. The computer readable medium of claim 40, wherein the instructions
cause the system to enable a constituent to be scheduled multiple times
with different material and media representations playing at different
times.
43. The computer readable medium of claim 39, wherein the instructions
cause the system to perform the steps performing broadcast operations
further comprising the step of using the association to control the
relative ordering of constituents and broadcast elements in the context of
the association.
44. The computer readable medium of claim 39, wherein the instructions
cause the system to perform the step of playing the first and second
broadcast constituents in sequence comprising the steps of:
defining the broadcast elements in terms of time-independent interval
relationships;
organizing the intervals into a constraint matrix;
producing a relationship matrix by solving the constraint matrix;
reducing the relationship matrix to a sequence of start and end points of
the broadcast elements;
using the start and end points to constrain broadcast constituent
programming.
45. The computer readable medium of claim 44, wherein the instructions
cause the system to perform the steps performing broadcast operations
further comprising the step of defining the interval relationships using
thirteen atomic relationships, the interval relationships being encoded as
binary numbers.
46. The computer readable medium of claim 44, wherein the instructions
cause the system to perform the step of reducing the relationship matrix
to a sequence of start and end points comprising the steps of:
creating the sequence of end points by converting the relationship matrix
to a matrix of end point relations using a look-up process;
topologically sorting the end point relations; and
identifying violations of element ordering constraints by false values in
the relationship matrix, the violations of element ordering constraints
indicating a conflict between pairs of intervals. |
|
 |
|
 |
Claims |
|
|
|
Description |
|
|
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of broadcasting. More
particularly, the present invention relates to computer control of
broadcasts.
2. Art Background
When broadcast technology was in its infancy, the process of scheduling of
broadcasts and control of the equipment to generate the broadcasts were
quite simple and typically were done manually. However, as broadcast
systems have become more sophisticated, the problem of managing broadcasts
and scheduling events which form broadcasts have become quite significant.
Regarding management of broadcasts, the technology today provides broadcast
events (e.g. programs) from a variety of sources. For example, feeds may
originate from a satellite receiver, from a videotape, from a television
camera, from an internal line from a computer, etc. The same event
broadcast in two different time zones may use a live feed from a satellite
for a broadcast in one time zone and a videotape of the earlier live feed
for a later broadcast in a second time zone.
Scheduling of broadcasts have become complex too. The organization and
broadcast of commercials during programming typically have many broadcast
constraints that must be followed. Some events are of unknown duration,
making it extremely difficult to program subsequent to that event. Some
events are programmed in parallel with other events, the operator of the
broadcast, at time of broadcast, deciding which event to broadcast.
In addition, the management of live broadcasts have become complex. This
type of program, such as a news program, is difficult to schedule in
advance as the timing of information received, the amount of time taken
for different portions of the broadcast and the broadcast resources
change. For example, the duration of lead ins provided by the news anchor
can vary. The live feed showing the news reporter at the story location
may not be available. The importance of certain stories may change. To
address such issues, a news program director will have story segments of
varying lengths available and will typically dynamically modify the news
broadcast based on the various timing requirements and known available
resources.
Therefore, it is desirable to have a multiple channel shared resource,
broadcast capability that handles various activities such as editing, news
and commercial insertion, including live events, definition of schedule
patterns that apply across several channels, mapping output channels to
different uplink channels at different times, and integration of digital
data and control with the uplinked video signals.
Computer controlled equipment is already an integral element in today's
broadcast industry. Automation systems provide frame-accurate control of
equipment; non-linear editors assemble material without the restrictions
of tape-based linear systems; traffic systems deal with the complexities
of scheduling commercial and spot play; computer graphics systems create
new video effects and illustrations; news systems edit scripts, tie them
to clips, and provide searchable archives.
However, the increasing prevalence of these independently designed
computer-based systems does not automatically guarantee the smooth
integration of these systems into a coherent, unified broadcast operation.
To the contrary, these systems typically cannot "talk" to each other
without creation of specialized "gateways" which attempt to perform a
translation between systems. A customer's only alternative to this problem
is to purchase "single-vendor" systems which require the user to discard
their investments in pre-existing systems and use equipment that does not
always meet all of their needs.
Compounding this problem is the need for enhanced capabilities while
maintaining a simple operational structure. For example, it is desirable
to generalize programming, e.g., of particular commercial breaks, such
that they can be used a number of times, varying the commercials that form
the break. Prior art structures, e.g., Open Media Framework Interchange
(OMFI), created by AVID Technologies, provides a unified data structure
which maintains as a combined entity the programming and the material used
to implement the programming.
In addition, the broadcast industry generally uses simple time-based
techniques for specifying the order of events, such as program events,
commercials, run-downs and edit lists. These techniques define some
combination of exact or approximate values for the start and duration of
each event, and typically add some constraints, such as auto-follow, hard
start or manual trigger. The list is then sorted by time. Ripple rules,
complex, specialized rules which adjust start times of subsequent events
based on the change of start time or duration of an event, are applied to
adjust the timing of events when needed.
While this approach works satisfactorily when the start or duration of each
event are known, the increasing prevalence of untimed or live events place
difficult burdens on the definition of timing and the processing of
complex ripple rules for any such system. The term origination refers to
when video transmission begins at the facility. Multi-channel origination
occurs, for example, when the signal representative of video to be
broadcast comes from a tape, a disk drive, or be a live event being shot
at the facility. Turnaround is used when the video signal originates
somewhere else, is brought into the facility and immediately
retransmitted. Multichannel origination also complicates the definition of
a broadcast. Furthermore, non-linear, disk-based playout, which refers to
the current technology of disk drives which have both sufficient capacity
and sufficient bandwidth to support the recording and real time playback
of video, also causes problems as it is not sequential or linear as any
frame of video can be directly accessed much as an individual record in a
computer database. Thus significant problems can occur, particularly when
there are live events with no duration and when there are subsequent
events the start times of which cannot be changed. These systems fail to
capture the basic time independent ordering constraints among the set of
events to be defined for a broadcast or portion of a broadcast.
SUMMARY OF THE INVENTION
The present invention provides an innovative system and method of operating
the same which provides broadcast personnel who schedule broadcasts,
editors who edit all or portions of a broadcast, and operators who control
the broadcast equipment or resources used to generate a broadcast,
information and guidance regarding the broadcast schedule, constraints
regarding timing and resource availability, and identification of
resources to be used to generate broadcasts.
The system utilizes a data structure which separates broadcast information
into three constituent types: a scheduling segment (when to play), a
material segment (what to play), and a media segment (how to play) and
three types of relationships among the constituents: composition (how to
create), representation (how to manifest) and association (how to order).
Using the three basic constituents and three basic relationships most any
broadcast situation can be modeled. This integrated data structure, and
process utilizing the same, supports the management of events, material,
media and playback resources. The structure supports any number of levels
of abstraction for dealing with the complexities of modern broadcast,
editing and news room applications. The structure separates the
compositional aspects of broadcast operations (the pieces that make up the
compositional pieces, e.g., a program or story) from the representational
aspects (the material that manifests the specified compositional pieces).
As such, it differs significantly from other industry attempts to provide
a unified data structure which do not separate the programmatic intent
from the actual material which implements that intent.
In one embodiment, the data structure is a simple, recursive, two-level
information structure that is easily conformed to the commonly accepted
abstractions of the industry such as rundown, event, story, program, pod,
schedule and channel, as well as new abstractions that meet the needs of
an increasingly complex industry. Sequencing constraints may be applied to
elements in a time-independent manner. In addition, this two-level
recursive structure is independently applied to both the compositional and
representational aspects, supporting a rich expressiveness for planning,
operating and reporting the actions of a complete broadcast operation.
The model generated can then be used a variety of ways across varying
pieces of equipment. For example, the model can be used to control access
to broadcast equipment to insure that certain equipment, e.g., VTRS,
satellite receivers, etc., are available when needed during a broadcast.
The system can also provide the operator of the broadcast equipment
programming guidance by identifying applicable parallel programming and
eliminating parallel programming that was scheduled but can not be
utilized. In addition, last minute changes that conflict with preexisting
scheduling requirements can be immediately identified.
Furthermore, the scheduling process is simplified, by enabling the
scheduler to reuse standard programming sequences, e.g., nightly news
programs, certain commercial spot sequences, varying simply the material
and/or media used to embodied the particular instance. In addition, the
model can identify scheduling conflicts. In addition, the structure can be
used in an editing system to enable the edit to immediately determine the
effects of edits and whether certain edits can be implemented. Finally,
the structure can be used to track what is actually broadcasted, a feature
that is important for tracking costs and income generated.
In addition to the data structure, it is preferred that the system utilizes
techniques which overcome the limitation of time-based solutions of event
scheduling in broadcast programming. Thus, each event, for example,
commercial, television program, public service announcement or news story,
is defined relative to other events to be programmed. More particularly,
each event is defined as either an instantiated or uninstantiated start
point and end point. Once each event is defined, the relationships among
the different events are generated. The resultant information provides a
set of instructions regarding the order of the programming of the
broadcast.
BRIEF DESCRIPTION OF THE DRAWINGS
The objects, features and advantages of the present invention will be
apparent to one skilled in the art from the following detailed description
in which:
FIG. 1 illustrates an exemplary system which operates in accordance with
the teachings of the present invention.
FIG. 2 is a flow chart illustrating one embodiment of the present
invention.
FIG. 3 is a table illustrating atomic interval relationships that can be
used to define the ordering of events.
FIGS. 4a, 4b, 4c, 4d, 4e, 4f, 4g, 4h, 4i, 4j, 4k, 4l, 4m, 4n, 4o, 4p, 4q,
4r, 4s 4t, 4u, 4v, 4w, 4x, 4y, 4z list the subset of 868 interval
relations.
FIG. 5 illustrate an example of a constraint matrix and a corresponding
relationship matrix.
FIGS. 6a and 6b illustrate a simplified example of a constraint matrix and
relationship matrix for a pod.
FIGS. 7a, 7b, 7c illustrates a portion of an exemplary table used to
generate SOM and EOM for two intervals based upon interval relationships.
FIG. 8 illustrates a scheduling hierarchy that operates in accordance with
the teachings of the present invention.
FIG. 9 illustrates the representations that can be provided in accordance
with the teachings of the present invention.
FIGS. 10a and 10b illustrate the constituents and their relations in one
embodiment utilizing object oriented technology and FIGS. 10c, 10d, 10e,
10f, 10g provide illustrative object oriented structures.
FIGS. 11a, 11b, 11c, 11d and 11e illustrate one example of processes
performed in accordance with the teachings of the present invention.
FIGS. 12a and 12b illustrate another example of processes performed in
accordance with the teachings of the present invention.
FIG. 13 illustrates a broadcast pattern implemented in accordance with the
teachings of the present invention.
FIG. 14 illustrates the example of the handling of live events in
accordance with the teachings of the present invention.
FIG. 15 illustrates the example of using alternates in accordance with the
teachings of the present invention.
FIGS. 16a, 16b, 16c and 16d illustrate the process of generating an as run
log n accordance with the teachings of the present invention.
FIG. 17 is a flow chart illustrating an exemplary process for generating a
schedule.
FIGS. 18a, 18b, 18c and 18d is an example illustrating the process of FIG.
17.
FIG. 19 sets forth an alternate process for generating a schedule in
accordance with the teachings of the present invention.
FIGS. 20a, 20b, 20c and 20d illustrate the building of a program.
FIG. 21 is a flow diagram illustrating one embodiment of a process for
identifying inconsistencies in a schedule.
FIG. 22a is a flow diagram illustrating another embodiment of a process for
identifying inconsistencies in a schedule and FIG. 22b provides an example
of a directive graph of orderings of endpoints.
FIG. 23 is a simplified flow diagram illustrating one embodiment of the
broadcast process in accordance with the teachings of the present
invention.
FIGS. 24a and 24b set forth exemplary pseudo code illustrating one
embodiment of the broadcast process.
FIG. 25 illustrates the automated recording of live events for subsequent
playback.
DETAILED DESCRIPTION
The system and method of the present invention provides an innovative
structure that provides enhanced capabilities for different portions of
the broadcasting process and easily lends itself to be implemented across
varying platforms. More particularly, the system and method of the present
invention utilizes an innovative structure that permits a flexible but
definable schedule of broadcasts and the physical entities and devices
used to generate the broadcasts. As the structure separates the
compositional aspects of broadcast operations from the material that
manifests the pieces of the composition, the structure supports multiple
levels of abstraction and definition. In the following description, for
purposes of explanation, numerous details are set forth, in order to
provide a thorough understanding of the present invention. However, it
will be apparent to one skilled in the art that these specific details are
not required in order to practice the present invention. In other
instances, well known electrical structures and circuits are shown in
block diagram form in order not to obscure the present invention
unnecessarily.
The system of the present invention and its operation is discussed in part
in the context of object oriented technology. However, the present
invention is not limited as such and can be implemented using other
programming and data structure technologies and can be implemented as a
series of procedures that embodied the relationships and functions
described herein.
One example of a system that operates in accordance with the teaching of
the present invention is illustrated in FIG. 1. The system illustrated in
FIG. 1 is a simplified system so as to not obscure the discussion of the
present invention. It is readily apparent to one skilled in the art that a
variety of different systems may be used. For example, the system that
will be described includes a number of video terminal recorders (VTR), a
satellite receiver and the like. However, the teachings may be
incorporated in a system without these devices. In particular, the
configuration of the system utilized will be adapted to the end user. For
example, the system may be an editing system, a control panel used by a
news program director, a control system used by a broadcast operator, or
an accounting system utilized by accountants and billing personnel for a
particular station. The system is configured in accordance with the
teachings of the present invention to provide guidance as to the
constraints of the programming of a broadcast, and, subsequent to the
broadcast, exactly what was broadcasted.
Furthermore, the teachings of the present invention may be incorporated
into a complex broadcast system that.is typically found in broadcast
centers today. Such systems may include additional equipment such as
editing equipment, switchers, and equipment used to support other media
not discussed herein. In addition, it is contemplated that the system
functions as a computer server wherein broadcast specific equipment or
other computing devices access the server for broadcast information.
Referring to FIG. 1, the system includes a computer system 105, for
example, a general purpose computer system or specially configured
computer system. The system 105 includes memory 110 and a processor 115,
as well as supporting peripheral devices. In addition, the system 105 is
coupled to a display 120, which in the present embodiment displays the
output generated by the system 105. An input/output device 125 also is
provided to enable the user of the system to input information. Examples
of such a device 125 include a keyboard, a mouse or other input device.
In the present embodiment, the system 105 is coupled to a variety of media
devices that provide video output and video recording features. For
example, a satellite receiver 130 receives programming for broadcast. VTRs
135, 140, can function to provide programming for broadcast, as well as
record programming received through the satellite receiver 130 for later
broadcast. A video display 145 may be coupled to the computer system 105
to generate a video display of programming provided by satellite receiver
130 or VTRs 135, 140. Using a system, the user can perform a variety of
broadcast related operations.
The system described herein preferably includes an innovative system and
method for sequencing complex and untimed events across broadcast
activities, such as editing, programming of broadcasts, spot insertion and
scheduling of events during news programs. In addition, it is preferred
that the system includes a basic data structure that readily adapts itself
to a variety of computing platforms and portions of the broadcasting
process, including the scheduling, editing, broadcasting and accountings
performed related to programs and broadcasts. However, it is contemplated
that the system and method for sequencing complex and untimed events does
not have to operate using the innovative data structure and associated
processes described herein. Similarly, the data structure and associated
processes described herein can utilize other techniques for specifying
temporal relationships between scheduling constituents.
The process for sequencing complex and untimed events is described with
reference to FIG. 2. At step 210 the broadcast events are defined in terms
of interval relationships between intervals (an interval, unless otherwise
noted consists of start points and end points). At step 215, the intervals
are organized in a matrix. At step 220 the transitive closure of the
constraint matrix is performed to produce a relationship matrix consisting
of a full set of interval relationships from the interval relationships
defined. At step 230, the relationship matrix is reduced to a sequence of
start and end points of the different events. These start and end points
can be used to assist or constrain a user in performing programming of
broadcasts. In addition, this information can be used to determine
availability of the necessary equipment used to perform the actual
broadcast, or to control the equipment needed to perform the broadcast.
Thus, the first step is to define the broadcast events and atomic interval
relationships. An interval is a term given to a finite segment of time
regardless of whether the interval specifies exact time values. Intervals
without exact time values are identified to be uninstantiated. For
example, an interval can be defined as a pair of end points (i.e., start
point and end point) which can have real values. Intervals are
instantiated by citing time values that correspond to the end points of
the interval. For example, with respect to video that may be part of a
broadcast, video clips are bound in segments containing one or more
frames. The first frame of a clip is the start of message (SOM); the last
frame is the end of message (EOM). In the present illustration in order
that the matrix operates properly and to account for the peculiarities in
which video frames are counted, the EOM is set to a value equal to EOM+1.
There are thirteen possible atomic relationships between any two intervals.
These thirteen atomic relationships define most of the usual
specifications of event sequencing of a broadcast. These atomic
relationships are shown in FIG. 3. For example, with respect to
broadcasting, the relationship can be used to define an auto-follow
function, which is a function in which one program automatically follows a
prior program broadcast, or the relationship can be used to trigger a
broadcast of a certain program.
Some functions, such as alternate or parallel playlists of programming to
be broadcast, must be expressed using disjunctive combinations of the
atomic relations. To meet these requirements, a maximal subset consisting
of 868 relations is used. This subset is referred to in published
literature as the ORD-Horn Clause Set and is set forth in FIGS. 4a-4s.
This subset of 868 relations is a subset of a total 8192 such combinations
of the basic thirteen atomic relations. This subset enables the solution
of the matrix subsequently solved to be performed in polynomial real time.
Thus, given any set of video clips, the user need only specify pair wise
relationships among the members of the set. For example, a commercial
break can be specified by the clip that starts the break, the one which
ends it, and the sequence of clips in between. In order to correctly and
completely specify the endpoint sequence which results from this
organization of clips, it is necessary to determine all unspecified
relationships as well. The unspecified relations in the present example
are the relationships between non-adjacent clips in the sequence.
Using a simple algorithm referred to as binary constraint propagation
(BCP), these unspecified relationships can be determined. BCP is known in
the computer art. For details on BCP, see, for example, Ladkin, P. and
Maddux, R. "On Binary Constraint Problems", Journal of the Association for
Computing Machinery, 41(3): 435-469 (1994).
To utilize BCP, the intervals defined are organized into a constraint
matrix wherein the matrix entries are the interval relations between pairs
of intervals. Thus one entry may be specified, for example, as "A meets
B". Some interval relations may be unspecified. Any entry that is
unspecified is set to "true" to indicate that the relation could be any
one of the atomic relations and can also be used to state that one
interval has no relation to the other interval.
The constraint matrix has certain properties that make it possible to use a
simple algorithm to close or solve for the unspecified interval relations.
The matrix lists the intervals relations across the rows and down the
columns, wherein each entry defines the relationship between a pair of
intervals. Entries on the diagonal therefore define how an interval
relates to itself. Thus, the diagonal entries are equality (e.g., interval
x=interval x), and the entry for any given row or column is the converse
of the entry for the corresponding column or row (e.g., interval x follows
interval y implies interval y precedes interval x). Thus, the constraint
matrix is triangular with equality on the diagonal. Given these
conditions, the constraint matrix can be closed in polynomial time by
repeatedly squaring the matrix until the entries cease to change. An
example of a constraint matrix and a corresponding relationship matrix are
illustrated in FIG. 5.
FIG. 6a and FIG. 6b illustrate the following simplified example. A
commercial pod P is defined as a group of three elements A, B, C which
play in a back to back sequence starting at the beginning of a commercial
break of a broadcast. The break is triggered by a GPI, G. By definition,
each element has an interval which is identified by appending I to the
name. The constraint matrix therefore looks like that shown in FIG. 6a,
where = represents the equal relationship, s represents the starts
relationship, m represents the meets relationship and f represents the
finishes relationship. Those entries in the matrix not filled in default
to the true relationship (true indicates that any relation is possible).
As stated above and as shown in FIG. 6a, the diagonal is always set to the
equality relationship.
FIG. 6b illustrates the relationship matrix generated using BCP, wherein si
represents the started by relationship, d represents the during
relationship, fi represents the finished by relationship, p represents the
precedes relationship, pi represents the follows relationship, mi
represents the met by relationship and di represents the includes
relationship. A few things of note. This illustration shows the diagonal
symmetry of the matrix where the transposed values are the converse of
each other (e.g., meets and met by). In addition, there are three possible
relations between GI and AI. GI either starts AI (GI is shorter than AI),
is started by AI (GI is longer than AI) or is equal to AI (GI and AI are
the same length). Similarly, although not illustrated in FIG. 6b, the p
relations (for GI-CI) are really composed of p, m and o (precedes, meets
or overlaps). However, as it is known the a GPI is the shortest element,
the specification can be changed to state that GI starts AI and eliminate
other possibilities. Similarly, the GI-CI relationship is simplified. Even
if the specification was not performed to eliminate the other relations,
the endpoint sequences specified for the pod are unambiguous and capture
the autofollow relations intended.
Preferably, a table lookup is performed in place of an arithmetic
application and the results are intersected instead of arithmetically
added. For further information on closing the matrix using table lookup,
see, Allen, J., Temporal Reasoning and Planning, in Allen, Kautz, Pelavin
and Teneberg, eds, Reasoning about Plans pp 1-67 (Morgan-Kaufmann 1991)
and Ladkin, P and Maddux, R., On Binary Constraint Problems, Journal of
the Association for Computing Machinery, 41(3):435-469 (1994) (see in
particular the equations on page 439 and Table II). As noted above, due to
the nature of the matrix, the closure process is guaranteed terminate.
Furthermore, due to the subset chosen, the process executes in polynomial
time, thereby providing a realistic implementation of the process for
providing broadcast programming and operat | | |
