由下至上递增地构建数据文件

摘要

通过在更新位置附加一组孩子节点来构造数据文件，其中，该组孩子节点是从现有数据文件或文件分段中的节点中选择出来的，而该更新位置是现有数据文件或文件分段中的节点，由导航路径来标识。当更新命令是合并时，文件分段中的一个或多个节点(“合并节点”)被标识为更新位置，而现有数据文件中的节点作为文件分段中合并节点的孩子节点被合并。当更新命令是连接时，现有数据文件中的节点(“连接节点”)被标识为更新位置，有序列表指定现有数据文件中的哪些节点以及文件分段中的哪些节点要被连接作为该连接节点的该组孩子节点。该连接和合并更新命令、导航路径以及文件分段可以作为一系列的分段更新单元发送以便构造该数据文件。

说明书

相关申请

本申请涉及到2001年7月17日提交的序列号为60/306,256的美国临时专利申请的优先权，该申请在此引入作为参考。

发明领域

本发明一般涉及到递增地构建数据文件，更具体地，涉及到包含多媒体内容描述的数据文件。

版权声明/许可

本专利文件公开文本的一部分包含受版权保护的材料。当本专利文件或专利公开文本出现在专利商标局的专利文件或记录中时，版权所有者不反对任何人去复制本专利文件或专利公开文本，否则，保留所有的版权。随后的声明适用于如下面以及附图中所述的软件和数据：Copyright2001，Sony Electronics，Inc.，保留所有权利。

发明背景

数字多媒体信息通过诸如数字电视信号之类的广播传送以及诸如因特网之类的交互式传送变得广为分布。该信息可以是静止图像、音频馈送或者视频数据流。但是，这样大量的信息的可获得性导致很难识别用户特别感兴趣的内容。各种组织已经试图通过提供可用来搜索、过滤和/或浏览以便定位特定内容的信息描述来处理这个问题。运动图像专家组(MPEG)已经发布了通常称之为MPEG-7的多媒体内容描述接口标准来标准化用于多媒体信息的内容描述。与先前诸如MPEG-1和MPEG-2之类的MPEG标准(它们定义音频-视频内容的编码表示)相反，MPEG-7内容描述描述内容的结构和语义，而不是描述内容本身。

用电影作为例子，相应的MPEG-7内容描述将包含“描述符”(D)，它是描述电影特征的组件，例如场景标题、场景内的镜头、该镜头的时间、颜色、形状、运动和音频信息。该内容描述将还包含一个或多个“描述方案”(DS)，它是描述两个或多个描述符和/或描述方案之间的关系的组件，例如使镜头的特征联系起来的镜头描述方案。描述方案也可以描述其它描述方案之间以及描述方案和描述符之间的关系，例如使场景中不同的镜头联系起来并且使场景的标题特征与镜头联系起来的场景描述方案。

MPEG-7使用数据定义语言(DDL)，该数据定义语言规定了用于定义描述工具的标准集(DS，D)以及用于定义新的描述工具的语言，它还提供描述符和描述方案的核心集。一组描述符和描述方案的DDL定义被组织为不同类别内容的“模式”。模式中每个描述符的DDL定义规定了相应的特征的语法和语义。模式中每个描述方案的DDL定义规定了其子部件、描述符和描述方案之间关系的结构和语义。DDL可以被用来修改和扩展现有的描述方案和创建新的描述方案和描述符。

MPEG-7 DDL是基于XML(可扩展标记语言)和XML Schema标准的。描述符、描述方案、语义、语法以及结构都用XML元素和XML属性来表示。某些XML元素和属性是可选的。

特定的一块内容的MPEG-7内容描述被定义为MPEG-7模式的一个实例；也就是说，它包含符合该模式中定义的语法和语义的数据。该内容描述在参考适当模式的“实例文件”中被编码。该实例文件包含在该模式中定义的必需元素和属性以及任何必需的可选元素和/或属性的一组“描述符值”。例如，特定电影的某些描述符值可能规定，该电影有三个场景，场景一具有六个镜头，场景二具有五个镜头，而场景三具有十个镜头。实例文件可以使用XML以文本格式编码，或者以二进制格式编码，例如为MPEG-7数据规定的被称为“BiM”的二进制格式，或者使用上述两种格式的混合进行编码。

实例文件通过诸如计算机网络之类的通信信道传送到另一个系统，该另一个系统使用包含在该实例文件中的内容描述数据去搜索、过滤和/或浏览相应的内容数据流。典型地，实例文件被压缩以便更快地传送。编码器组件既可以对实例文件进行编码也可以压缩实例文件，或者该功能可以由不同的组件来执行。而且，实例文件可以由一个系统生成并随后由不同的系统来传送。接收系统中的相应的解码器组件使用引用的模式来对实例文件进行解码。该模式可以与该实例文件分离地传送到解码器，作为相同传送的一部分或者由接收系统从另一个源获取。可替换地，特定的模式可以结合到解码器中。

虽然压缩通过减小实例文件的大小缩短了传送时间，但是如果描述很大，则在网络上传送整个内容描述仍然需要太多的时间。因此，只有部分实例文件可以被传送以便节省带宽。通常，内容描述可以被建模为由一组子树或分段组成的树。确定发送哪个分段是取决于应用的。

内容描述可以通过添加、删除或替换描述分段(即，描述分段中的描述符和描述方案和/或属性)来更新。该更新通过一系列分组或者MPEG-7标准中的“访问单元”被传送到接收系统，它们包含一个或多个分段更新单元。接收系统中的解码器通过应用分段更新单元中的信息来更新其现有的内容描述。典型地，分段更新单元由导航路径、更新命令和分段有效负荷组成，所述导航路径指导解码器到描述树中的适当位置以便应用更新，所述更新命令规定要执行的更新的类型，即添加、删除、替换，所述分段有效负荷标识增加或替换命令的更新值。因为每个当前的更新命令都必须规定通向路径位置的正确位置，所以编码器在创建和传送分段更新单元之前必须预先知道存储在编码器中的描述树。因此，当前的分段更新单元只能在解码器中从上向下构造该描述树。

发明内容

通过在更新位置附加一组孩子节点来构造数据文件，其中，该组孩子节点是从现有数据文件或文件分段中的节点中选择出来的，而该更新位置是现有数据文件或文件分段中的节点，由导航路径来标识。当更新命令是合并时，文件分段中的一个或多个节点(“合并节点”)被标识为更新位置，而现有数据文件中的节点作为文件分段中合并节点的孩子节点被合并。当更新命令是连接时，现有数据文件中的节点(“连接节点”)被标识为更新位置，有序列表指定现有数据文件中的哪些节点以及文件分段中的哪些节点要被连接作为该连接节点的该组孩子节点。连接和合并更新命令、导航路径以及文件分段可以作为一系列的分段更新单元发送以便构造该数据文件。

附图说明

图1A-D是图示本发明实施例操作的图；

图2是适合于实施本发明的计算机环境图；

图3A是要被根据图1B的实施例的接收系统来执行的解码方法的流程图；

图3B-C是要结合图1A的方法来执行的方法的流程图；和

图3D是要被根据图1B的实施例的发送系统来执行的编码方法的流程图。

发明详述

在随后对本发明实施例的详细描述中将要参考附图，附图中相同的附图标记表示相同的元件，并且在附图中通过示例的方式示出了本发明可以在其中实施的具体实施例。这些实施例得到足够具体的描述以便使本领域一般技术人员能够实施本发明，但是应该理解，也可以使用其它实施例，并且在不偏离本发明范围的情况下可以作出逻辑的、机械的、电学的、功能性的以及其它修改。因此，随后的详细描述不能以限制的意义来看，并且本发明的范围仅仅由所附权利要求来限定。

可以通过在如这里所述在文件分段中具有节点的现有数据文件中合并和/或连接节点而从下向上来构造具有树结构的数据文件。这种文件的例子包括XML(可扩展标记语言)文件和多媒体内容描述文件，特别是那些包含符合MPEG-7标准的描述的文件。根据多媒体内容描述文件来描述示范实施例，但是本发明并不限于此，本领域一般技术人员会立即认识到本发明到其它类型数据文件的可应用性。

以图1A所示的多媒体内容描述递送系统100的概图来开始，发送系统101上的内容描述113在接收系统105上使用作为访问单元109发送的描述分段来被重建。通过将访问单元109中的分段与接收系统105上的现有内容描述111合并和/或连接，解码器107从下向上构造接收系统上的内容描述113，这将在下面进一步描述。发送系统上的编码器103创建包含合并和/或连接命令和分段的访问单元109，这将在后面结合图1B进行描述。应该理解，虽然“访问单元”是MPEG-7标准所用的术语，但是本发明并不限于此，本发明可以应用于构造任何类型的内容描述。还应该理解的是，本发明不局限于图1A所示的特定组件排列。例如，本领域一般技术人员会立即认识到，发送系统可以从另一系统接收访问单元以便随后进行传送。

访问单元121的示范实施例在图1B中图示。访问单元121包含一个或多个分段更新单元123。每个分段更新单元125包含导航路径127、更新命令129和分段有效负荷131。当更新命令129是合并命令133或连接命令135时，导航路径127规定接收系统中的现有内容描述中或描述分段中的更新位置，即节点。分段有效负荷131包含分段或者对于分段的引用。一组一个或多个从现有内容描述中和/或描述分段中选择的子节点被作为子节点附加到更新位置从而构造内容描述。当更新命令120包含连接命令135时，连接源元素137(以剖视图示出)也存在于分段更新单元125中。在一个实施例中，连接源元素137是“源，连接路径”元素对139的有序列表，这将结合图1D进行详细描述。在访问单元121内，合并或连接命令的分段更新单元可以与包含添加、删除、替换和重置命令的分段更新单元共存。

如图1C所示，通过将现有描述树附加到分段中的一个或多个节点，即合并节点，合并命令合并分段更新单元中的分段和接收系统中的现有描述。假设合并命令的分段更新单元125包含分段143作为其有效负荷131，而导航路径127包含将节点B规定为分段143中更新位置的上下文表达式。当执行时，合并命令将分段143设置为描述树的根，并用现有描述树141来替换该描述分段中的节点B，从而产生合并的描述树145。

如图1D所示，连接命令连接分段更新单元中的分段和现有描述树中的节点从而产生连接的描述树。给定现有描述树151和分段更新单元中的分段153，假设现有描述树151中的节点B和分段153要被连接成连接的描述树155中的单个连接节点A’。导航路径127包含将描述树151中的节点B规定为其中连接分段描述153的更新位置的上下文表达式。在分段描述153被连接到节点B以后，结果就是连接的描述树155中的连接节点A’。因为节点A和B中的每一个都可以有属性以及作为孩子的子树，所以分段更新单元125中的连接源元素137规定被连接的两个节点的哪些孩子要被附加作为连接节点A’的孩子节点，以及它们以什么顺序出现。当孩子节点被添加到连接节点时，以该指定孩子为根的完整子树被添加，也就是添加孩子节点包括添加该指定孩子节点的所有后代节点。在最简单的情况下，连接操作可以导致两个节点的孩子以下列顺序串连为连接节点A’的孩子：首先是描述153中指定的连接节点的所有孩子(即，节点B)，然后是节点A的孩子节点。源的有序列表、连接源元素137中的元素对139使得能够进行任意复杂的连接。对的源元素指定现有树151或者分段153是连接节点A’的孩子的源，而连接路径元素指定源的哪些属性或者子树要成为连接节点孩子。因此，如图1D所示，连接源列表包含两个源、规定如何组合现有描述树151中节点B以及分段153中节点A的孩子的孩子路径元素对。第一对指示源是现有描述树151并且孩子路径指向树151中的孩子节点D(相对于其父节点B来指定)。第二对指示源是分段并且孩子路径指向分段153中节点A的孩子节点C。所得到的连接节点A’的孩子节点是以节点D为根的子树(它包括现有描述树151的节点F和G)以及以节点C为根的子树(它包括分段153的节点H)。注意，在这种情况下，树151的节点E没有包括进来，因为它没有被指定在连接源列表中。

因此，所描述的合并和连接命令使将部分数据文件作为分段传送以及从下向上构造新的数据文件成为可能。

对图2的如下说明打算提供对计算机硬件以及其它适合于实现本发明的操作组件的概述，但是并不打算限制应用环境。图2图示了适合于用作图1A的发送和/或接收系统的计算机系统的一个实施例。该计算机系统40包括处理器50、存储器55以及耦合到系统总线65的输入/输出能力60。存储器55被配置用来存储指令，这些指令在被处理器50执行时会执行这里描述的方法。存储器55还存储访问单元。输入/输出60为递送和接收访问单元作准备。输入/输出60还包含各种类型的计算机可读介质、包括可以由处理器50访问的任何类型的存储设备。本领域一般技术人员将会立即认识到，术语“计算机可读介质”还包含对数据信号进行编码的载波。还应该理解，系统40由在存储器55中执行的操作系统软件来控制。输入/输出和相关介质60存储操作系统以及本发明方法的计算机可执行指令以及访问单元。图1A所示的编码器103和解码器107可以是耦合到处理器50的分离组件，它们也可以在由处理器50执行的计算机可执行指令中实现。在一个实施例中，计算机系统40可以是ISP(因特网服务供应商)的一部分，或者通过输入/输出60耦合到ISP，以便在因特网上发送和接收访问单元。显而易见，本发明不局限于因特网接入以及基于因特网web的站点，本发明还包含直接耦合以及专用网。

应该理解的是，计算机系统40是许多具有不同结构的可能的计算机系统中的一个例子。典型的计算机系统通常至少包括处理器、存储器以及将存储器耦合到处理器的总线。本领域一般技术人员将会马上理解的是，本发明可以用其它计算机系统配置来实施，包括多处理器系统、微型计算机、大型计算机等等。本发明也可以在分布式计算环境中实施，在分布式计算环境中，任务是由通过通信网链接起来的远程处理设备来执行的。

接下来将参照图3A-D的一系列流程图并按照计算机软件来描述本发明的特定方法。该方法构成了由计算机可执行指令组成的计算机程序(在图3A-D中被图示为方框(动作))。通过参照流程图来描述该方法可以使本领域一般技术人员能够开发出包括这样的指令的这种程序以便在适当配置的计算机上(计算机的处理器执行来自包括存储器的计算机可读介质的指令)执行该方法。该计算机可执行指令可以以计算机编程语言来编写或者在固件逻辑中实现。如果用符合公认标准的编程语言来编写，这种指令就可以在多种硬件平台上执行并且用于到多种操作系统的接口。此外，本发明并没有参照任何特定的编程语言来描述。应该理解，多种编程语言可以用来实现本发明如这里所述的教导。而且，在本领域中以一种形式或另一种形式(例如，程序、过程、进程、应用、模决、逻辑......)来提及采取某种动作或导致某种结果的软件是公知的。这些表达方式仅仅是下述说法的简写方式：计算机执行软件将导致计算机的处理器执行动作或产生结果。应该理解，或多或少的处理器可以结合到如图(流程图)所示的方法中来而不偏离本发明的范围，并且如图所示以及这里描述的框图的排列并没不意味着特定的顺序。

图3A图示了由接收系统执行的用来处理合并或连接命令的分段更新单元的解码方法300。该方法300可以由接收系统中的解码器执行或者在分离模块中操作。该方法300打算与对包含其它更新命令(例如，添加、删除、替换和重置等)的分段更新单元进行解码的其它方法协力操作，并且这样的方法在此没有作进一步的描述。分段更新单元中的命令在方框301中检查。如果更新是合并命令(方框303)，则如图3B所示的合并方法被执行(方框305)。否则，如图3C所示的连接方法被执行(方框307)。

现在回到图3B，当合并方法310被调用时，它在接收系统(X)中保存现有描述树(方框311)并且将分段有效负荷设置为当前树(Y)(方框313)。从方框315开始到方框321结束，合并方法310为Y中的每个节点执行节点循环。在方框317，合并方法310确定节点是否与在分段更新单元中的导航路径中指定的上下文表达式相匹配，并在方框319将匹配节点添加到节点列表中。一旦评估了Y中所有的节点，保存描述树X的拷贝就替换节点列表彰的每一个节点(及其子树，如果存在的话)(方框323)。

如图3C所示的连接方法330用连接节点(E)替换导航路径中指定的节点(以及其任一子树)(方框331)。连接节点的元素和模式类型也就是该分段的根节点的元素和模式类型。对于连接源元素中的有序列表中的每一对，连接方法330从方框333开始到方框345结束执行一个对循环。在该对循环中，源元素被用来确定当前源是现有描述树还是该分段，并且当前源的每个孩子节点在从方框335开始到方框341结束的子循环中被评估。在方框337，如果孩子节点与连接路径元素相匹配，该孩子节点在方框339被添加到列表Q。当当前源的所有孩子节点已经被评估时，列表Q中的孩子节点被附加到连接节点E，每一个都作为最后的孩子被附加(方框343)。如果相同的孩子属性在连接进程中出现多于一次，则第一孩子属性被附加而随后的复制孩子属性被忽略。当最后一对被评估时，该连接节点的所有孩子节点已经被附加并且该连接进程结束。

在没有图示的实施例中，如果连接源元素137是空的，就使用缺省有序列表。该缺省有序列表包含首先指定现有描述树的所有孩子节点第一对以及指定分段根节点所有孩子节点的第二队。该缺省有序列表导致所有的孩子节点在连接节点下以第一和第二对的顺序串联起来。

对合并和连接命令的分段更新单元进行编码的编码方法350在图3D中图示。当需要在接收系统中构造新的内容描述时，就在系统中调用方法350。方法350可以并入编码器或者作为分离模块来操作，并且也可以由发送系统或将编码的访问单元转移到发送系统的另一个系统来执行。方法300可以由接收系统中的解码器执行或者在分离模块中操作。方法300打算与对其它更新命令(例如，添加、删除、替换和重置等)的分段更新单元编码的其它方法协作操作，并且这样的方法在此不作进一步的描述。

对于要在访问单元中发送的每一个合并或连接分段更新单元，方法350执行由方框351到365所表示的处理循环。分段有效负荷用要合并或连接的分段或者分段的引用来格式化(方框353)。如果更新命令是连接(方框355)，则指定新描述树中连接节点位置的上下文表达式被确定下来并存储在导航路径中(方框357)。指定连接节点的孩子的对的有序列表被创建并存储在连接源元素中(方框359)。如果更新命令是合并，那么分段中附加节点的上下文表达式被确定下来并存储在导航路径中(方框361)。当存在时，导航路径、分段有效负荷以及连接源用合并/连接命令组合起来从而创建分段更新单元(方框363)。

当内容描述以XML编码时，例如MPEG-7内容描述，在一个实施例中，导航路径和连接路径是XML路径语言(XPath)中的位置路径表达式。XPath位置路径由一组通过树结构中节点的位置步距组成。每一个步距与由前一步距指定的一组上下文节点相关。位置步距由三个部分组成：

1.指定由该步距选定的节点以及上下文节点之间在树中的关系(例如，父亲、孩子、祖先、兄弟、属性等)的轴；

2.指定由该步距选定的节点的节点类型(例如，文本、属性、元素等)的节点测试；

3.被用来过滤由该步距选定的节点的零个或多个断言，例如*(全选)、文本、@属性名、顺序号等。

在另一个具体到对MPEG-7访问单元进行BiM编码的实施例中，该路径与对应于分段类型的XML模式类型相关。

此外，合并和连接命令的分段更新单元可以被规定为用于访问单元的现有MPEG-7语法的扩展，具体如下：

<complexType name＝“FragmentUpdateUnitType”>

   <element name＝“Navigation″type＝“mpeg7：XpathType”

       minOccurs＝“1”/>

   <element name＝“JoinSource”minOccurs＝“0”maxOccurs＝“unbounded”>

       <simpleContent>

          <simpleType>

             <extension base＝“mpeg7：XpathType”/>

             <attribute name＝“source”>

                <simpleType>

                   <restriction base＝“string”>

                      <enumeration value＝“current”/>

                      <enumeration value＝“fragment”/>

                   </restriction>

                </simpleType>

             </attribute>

         </simpleType>

      </simpleContent>

   </element>

   <element name＝“UpdateCommand”

      type＝“mpeg7：UpdateCommandType”minOccurs＝“1”/>

   <element name＝“FragmentPayload”type＝“mpeg7：FragmentPayloadType”

      <minOccurs＝“0”maxOccurs＝“1”/>

</complexType>

其中，Navigation元素对应于图1B中的导航路径127，而JoinSource元素对应于连接源元素137。JoinSource元素的source部分的值“current”指定接收系统中的现有描述树，而值“fragment”指定包含在分段有效负荷中的分段。

UpdateCommand元素的语法可以作如下修改以便包括合并和连接命令：

 <simpleType name＝“UpdateCommandType”>

    <restriction base＝“string”>    

      <enumeration value＝“AddFragment”/>

      <enumeration value＝“DeleteFragment”/>

      <enumeration value＝“ReplaceFragment”/>

      <enumeration value＝“Reset”/>

      <enumeration value＝“MergeFragment”/>

      <enumeration value＝“JoinFragment”/>

   </restriction>

</simpleType>

其中，“MegeFragment”和“JoinFragment”表示更新命令129的合并和连接命令133、135。

用于分段有效负荷的MPEG-7语法不需要为了适应合并和连接命令而修改。

上面已经描述了发送和从下向上构造内容描述的多媒体内容描述系统。虽然已经图示了具体的实施例并在这里对它们作了描述，但是本领域一般技术人员应该理解，打算实现相同目的的任何安排可以替换这里示出的实施例。本申请打算覆盖对本发明的任何改编和修改。

本申请中参照MPEG-7所用的术语打算包括提供内容描述的所有环境。因此，非常清楚，本发明仅仅由所附的权利要求书及其等价物来限定。