(57)【特許請求の範囲】
【請求項１】
一連の複数のデータをｋ個のセグメントにセグメント化する方法であって、（ａ）第１と第２の一連の数（以後”第１と第２のストリング”と呼ぶ）を夫々生成するステップであって、前記第１と第２のストリングが夫々前記複数のデータを表し且つｋ−１個の境界を有する、該第１と第２のストリングを生成するステップと、（ｂ）前記第１と第２のストリングによって表される前記データに対する第１と第２の適応度関数値を夫々計算するステップと、（ｃ）前記第１と第２の適応度関数値に基づいて、第３と第４の一連の数（以後”第３と第４のストリング”と呼ぶ）を夫々生成するステップであって、前記第３と第４のストリングが夫々前記複数のデータを表し且つｋ−１個の境界を有する、該第３と第４のストリングを生成するステップと、（ｄ）前記第３と第４のストリング中のパーティションポイント（以後”交叉”と呼ぶ）を選択するステップであって、前記交叉が（１）前記第３のストリングを前部の一連の数と後部の一連の数とに区分し、且つ（２）第４のストリングを前部の一連の数と後部の一連の数とに区分するステップと、（ｅ）前記第３のストリングの後部の一連の数を前記第４のストリングの後部の数と交換して第５と第６の一連の数（以後”第５と第６のストリング”と呼ぶ）を形成するステップと、（ｆ）前記第５と第６のストリング中の数を等しいｋ‐１個の境界に調節するステップと、（ｇ）前記第５と第６のストリングによって表される前記データに対して第３と第４の適応度関数値を計算するステップと、（ｈ）前記第１、第２、第３、及び第４の適応度関数値の比較し、適応度関数値が最も高いストリングのｋ‐１個の境界に基づいてｋ個のセグメントを供給するステップと、を備える複数のデータのセグメント化方法。
【請求項２】
前記複数のデータは、複数の画像を含む、請求項１に記載の方法。
【請求項３】
前記複数のデータは、複数のビデオフレームを含む、請求項１に記載の方法。
【請求項４】
前記複数のデータは、複数のプレゼンテーションスライドを含む、請求項１に記載の方法。
【請求項５】
前記複数のデータは、ノートの頁を含む、請求項１に記載の方法。
【請求項６】
前記複数のデータは、複数の非画像データを含む、請求項１に記載の方法。
【請求項７】
前記方法は、更に前記複数のデータを減少するステップを含む、請求項１に記載の方法。
【請求項８】
前記複数のデータを減少するステップは、複数の画像をサブサンプリングすることを含む、請求項７に記載の方法。
【請求項９】
前記複数のデータを減少するステップは、標準偏差測定に基づく、請求項７に記載の方法。
【請求項１０】
前記適応度関数は、画像類似度、重要度及び優先順位に基づく、請求項１に記載の方法。
【請求項１１】
前記適応度関数は、隣接するデータ間のヒストグラム差に基づく、請求項１に記載の方法。
【請求項１２】
前記適応度関数は、下記の数式に等しい、請求項１に記載の方法。
【数１】
0003921967.tif 000019
【請求項１３】
前記適応度関数は、下記の数式に等しい、請求項１に記載の方法。
【数２】
0003921967.tif 000020
【請求項１４】
前記適応度関数は、優先順位に基づく、請求項１に記載の方法。
【請求項１５】
前記適応度関数は、重要度に基づく、請求項１に記載の方法。
【請求項１６】
（ｉ）追加のデータを前記複数のデータに追加するステップを更に備える、請求項１に記載の方法。
【請求項１７】
（ｉ）ｋ個のセグメントを変化するステップを更に備える、請求項１に記載の方法。
【請求項１８】
前記適応度関数は、下記の数式に等しい、請求項１に記載の方法。
【数３】
0003921967.tif 000021
【請求項１９】
前記適応度関数は、下記の数式に等しい重要度ファクタを含む、請求項１に記載の方法。
【数４】
0003921967.tif 000022
【請求項２０】
前記第１と第２のストリングは、セグメント境界を表すｋ−１個の１を含む、請求項１に記載の方法。
【請求項２１】
一連の複数のデータをｋ個のセグメントにセグメント化する情報システムであって、（ａ）プロセッサと、（ｂ）前記プロセッサに接続され、前記複数のデータをセグメント化するためのソフトウエアプログラムを格納するためのメモリと、を備え、前記複数のデータは、一連の０と１とで符号化され、且つ境界セグメンテーションポイントとして使用されるｋ−１個の１があり、前記ソフトウエアプログラムは、前記複数のデータを表し且つｋ−１個の１を有するストリングの前記複数のデータに対する適応度関数値を得るための適応度関数を含み、（Ａ）夫々前記複数のデータを表し且つｋ−１個の１を有する第１と第２の一連の０と１からなる数（以後”第１と第２のストリング”と呼ぶ）を夫々生成するステップと、（Ｂ）前記第１と第２のストリングによって表される前記複数のデータに対する前記第１と第２の適応度関数値に基づいて、夫々前記複数のデータを表し且つｋ−１個の１を有する第３と第４の一連の０と１からなる数（以後”第３と第４のストリング”と呼ぶ）を夫々生成するステップと、（Ｃ）前記第３と第４のストリング中のパーティションポイント（以後”交叉”と呼ぶ）を選択するステップであって、前記交叉が（１）前記第３のストリングを前部の一連の数と後部の一連の数とに区分し、且つ（２）第４のストリングを前部の一連の数と後部の一連の数とに区分する、前記選択するステップと、（Ｄ）前記第３のストリングの後部の一連の数を前記第４のストリングの後部の数と交換して第５と第６の一連の数（以後”第５と第６のストリング”と呼ぶ）を形成するステップと、（Ｅ）前記第５と第６のストリング中の１の数をいずれもｋ−１個に調節するステップと、（Ｆ）前記第１、第２の適応度関数値、前記第５と第６のストリングによって表される前記データに対する第３、第４の適応度関数値の比較し、適応度関数値が最も高いストリングの境界セグメンテーションポイントに基づいてｋ個のセグメントを供給するステップとをコンピュータに実行させる、前記情報システム。
【請求項２２】
一連の複数のデータをｋ個のセグメントにセグメント化するための手順をコンピュータに実行させるためのプログラムであって、（ａ）前記一連の複数のデータに対応する第１のストリングと第２のストリングを形成するための第１のソフトウエアプログラム部分であって、前記第１と第２のストリングはｋ−１個の境界ポイントを有することと、（ｂ）前記第１と第２のストリングによって表される前記複数のデータに対して第１と第２の適応度関数値を計算するための第２のソフトウエアプログラム部分と、（ｃ）前記第１と第２の適応度関数値と遺伝子操作に基づいて前記複数のデータに対応する第３と第４のストリングを生成するための第３のソフトウエアプログラム部分であって、前記遺伝子操作は、前記第３のストリングと前記第４のストリング中のパーティションポイントで互いの後部を交換する交叉操作と、前記第３と第４のストリング中の境界ポイントを等しくｋ−１個の数に調整する突然変異操作とを含み、前記第２のソフトウエアプログラムは、前記第３と第４のストリングによって表される前記複数のデータに対して第３と第４の適応度関数値を計算することと、（ｄ）前記第１、第２、第３、及び第４の適応度関数値を比較し、適応度関数値が最も高いストリングのｋ‐１個の境界ポイントに基づいてｋ個のセグメントを選択するための第４のソフトウエアプログラム部分と、を備えるプログラム。
【発明の詳細な説明】
【０００１】
【発明の利用分野】
本発明は、マルチメディアデータのセグメント化に関し、詳細には、画像データストリームのセグメント化に関する。
【０００２】
【従来の技術】
マルチメディアデータのセグメント化は、基本的な問題である。セグメンテーションは、データストリームを有意なセグメント又は部分に分割することを必要とする。適切にセグメント化されたデータストリームは、より良好に編成及び再使用される事が可能である。セグメント化されたデータストリームは、ブラウジングや検索を容易にするアクセスポイントを提供する。益々多くのマルチメディアデータが生成されると共に利用可能とされると、セグメンテーション方法は、この大量の材料を要約することを助ける重要な機能を果たす事が可能となる。
【０００３】
複数の画像ドキュメントをシーケンシャル順序で有する画像ドキュメントストリームは、一タイプのマルチメディアデータストリームである。例えば、ビデオは、複数のフレームよりなる画像ドキュメントストリームを含む。このビデオは、カメラの変化によって画定される有意な部分やセグメント、又は意味的に関連するショットによって画定されるシーンを有する場合がある。これは、意味を抽出することが困難であるために、これはマシンにとって（人間にとってでさえ）困難なセグメンテーションの問題である。
【０００４】
ＡＣＭ  Ｐｒｅｓｓ社の１９９６年の出版のＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ’９６の議事録の１６３頁から１７４頁のＭ．Ｍｉｌｌｓ氏、Ｊ．Ｃｏｈｅｎ氏、及びＹ．Ｙ．Ｗｏｎｇ氏による、”Ａ  ｍａｇｎｉｆｉｅｒ  ｔｏｏｌ  ｆｏｒｖｉｄｅｏ  ｄａｔａ”で記述されているように、一つの方法は、定まった時間間隔で単純に画像データストリームを区分することが出来る。
【０００５】
他の方法は、カラーヒストグラム及びクラスタリングを使用する。これらは、以下の文献に記述されている。１９９６年のＳＰＩＥ２６７０の議事録の１７０頁から１７９頁のＪ．Ｓ．Ｂｏｒｅｃｚｋｙ氏とＬ．Ａ．Ｒｏｗｅ氏によるＳｔｏｒａｇｅ  ａｎｄ  Ｒｅｔｒｉｅｖａｌ  ｆｏｒ  Ｓｔｉｌｌ  Ｉｍａｇｅｓａｎｄ  Ｖｉｄｅｏ  Ｄａｔａｂａｓｅｓ  ＩＶでの”Ｃｏｍｐａｒｉｓｏｎｏｆ  ｖｉｄｅｏ  ｓｈｏｔ  ｂｏｕｎｄａｒｙ  ｄｅｔｅｃｔｉｏｎ  ｔｅｃｈｎｉｑｕｅｓ”（以下”Ｂｏｒｅｃｚｋｙ”と呼ぶ）；１９９９年のＩＥＥＥ  Ｃｏｍｐｕｔｅｒ  Ｓｏｃｉｅｔｙの第１巻７５６乃至７６１頁のＩＥＥＥＩｎｔｅｒｎａｔｉｏｎａｌ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍｕｌｔｉｍｅｄｉａ  Ｃｏｍｐｕｔｉｎｇ  ａｎｄ  Ｓｙｓｔｅｍｓの議事録のＡ．Ｇｉｒｇｅｎｓｏｈｎ氏とＪ．Ｂｏｒｅｃｚｋｙ氏による”Ｔｉｍｅ−ｃｏｎｓｔｒａｉｎｅｄ  ｋｅｙｆｒａｍｅ  ｓｅｌｅｃｔｉｏｎ  ｔｅｃｈｎｉｑｕｅ”：１９９９年のＩＣＡＳＳＰ’９９の第６巻の３０４１頁から３０４４頁のＳ．Ｕｃｈｉｈａｓｈｉ氏とＪ．Ｆｏｏｔｅ氏による”Ｓｕｍｍａｒｉｚｉｎｇ  ｖｉｄｅｏ  ｕｓｉｎｇ  ａ  ｓｈｏｔ  ｉｍｐｏｒｔａｎｃｅ  ｍｅａｓｕｒｅ  ａｎｄｆｒａｍｅ−ｐａｃｋｉｎｇ  ａｌｇｏｒｉｔｈｍ”（以下”Ｕｃｈｉｈａｓｈｉ”と呼ぶ）：１９９７年のＩＥＥＥ  会報のＣｉｒｃｕｉｔｓ  ａｎｄ  Ｓｙｓｔｅｍｓ  ｆｏｒ  Ｖｉｄｅｏ  Ｔｅｃｈｎｏｌｏｇｙの第７巻の７７１乃至７８５頁のＭ．Ｍ．Ｙｅｕｎｇ氏とＢ．Ｌ．Ｙｅｏ氏による”Ｖｉｄｅｏ  ｖｉｓｕａｌｉｚａｔｉｏｎ  ｆｏｒ  ｃｏｍｐａｃｔ  ｐｒｅｓｅｎｔａｔｉｏｎ  ａｎｄ  ｆａｓｔ  ｂｒｏｗｓｉｎｇ  ｏｆ  ｐｉｃｔｏｒｉａｌ  ｃｏｎｔｅｎｔ”：及び１９９５年のＡＣＭ  Ｐｒｅｓｓ社のＭｕｌｔｉｍｅｄｉａ’９５の議事録の１５頁から２４頁のＨ．Ｊ．Ｚｈａｎｇ氏、Ｃ．Ｙ．Ｌｏｗ氏、Ｓ．Ｗ．Ｓｍｏｌｉａｒ氏及びＪ．Ｈ．Ｗｕ氏による”Ｖｉｄｅｏ  ｐａｒｓｉｎｇ，ｒｅｔｒｉｅｖａｌ  ａｎｄ  ｂｒｏｗｓｉｎｇ：Ａｎ  ｉｎｔｅｇｒａｔｅｄ  ａｎｄ  ｃｏｎｔｅｎｔ−ｂａｓｅｄ  ｓｏｌｕｔｉｏｎ”。
【０００６】
画像データストリームは、多くのタイプとフォームであり得る。ビデオタイプは、プロデュースされたビデオと生のビデオを含む。プロデュースされたビデオの例は、ニュース、映画及びトレーニングビデオである。生ビデオの例は、ミーティングのビデオ、監視記録、及び携帯出来る個人のビデオカメラのビデオである。ＡＣＭ  Ｐｒｅｓｓ社の１９９６年発刊のＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ’９６の議事録の１６３頁乃至１７４頁のＳ．Ｍａｎｎ氏の”Ｓｍａｒｔ  Ｃｌｏｔｈｉｎｇ’：Ｗｅａｒａｂｌｅ  ｍｕｌｔｉｍｅｄｉａ  ｃｏｍｐｕｔｉｎｇａｎｄ’ｐｅｒｓｏｎａｌ  ｉｍａｇｉｎｇ’ｔｏ  ｒｅｓｔｏｒｅ  ｔｈｅｔｅｃｈｎｏｌｏｇｉｃａｌ  ｂａｌａｎｃｅ  ｂｅｔｗｅｅｎ  ｐｅｏｐｌｅ  ａｎｄ  ｔｈｅｉｒ  ｅｍｖｉｒｏｎｍｅｎｔｓ”を参照。
【０００７】
プレゼンテーションスライドを含む、スライドショーは、粒度のより粗いレベルでの画像データストリームでもある。プレゼンテーションスライドの例は、ＡＣＭ，Ｎｅｗ  ＹｏｒｋでのＭｕｌｔｉｍｅｄｉａ’９９の議事録の１４９頁から１５８頁のＰ．Ｃｈｉｕ氏、Ａ．Ｋａｐｕｓｋａｒ氏、Ｓ．Ｒｅｉｔｍｅｉｅｒ氏及びＬ．Ｗｉｌｃｏｘ氏による”ＮｏｔｅＬｏｏｋ：Ｔａｋｉｎｇ  ｎｏｔｅｓ  ｉｎ  ｍｅｅｔｉｎｇｓ  ｗｉｔｈ  ｄｉｇｉｔａｌ  ｖｉｄｅｏ  ａｎｄ  ｉｎｋ”で記述されるように、ＮｏｔｅＬｏｏｋ（ノートルック）システムでプロデュースされたような、ＰｏｗｅｒＰｏｉｎｔ（パワーポイント）スライドと画像を有するノートの頁を含む。
【０００８】
従って、検索及びブラウジングのためにデータを有意なセクションにセグメント化するためのセグメンテーション方法、情報システム及びコンピュータ読取可能媒体を提供することが望まれる。例えば、画像データストリームをセグメント化して冗長な画像データストリームを要約する要約画像データが提供され得る方法を提供することが望まれる。
【０００９】
【発明が解決しようとする課題】
本発明は、マルチメディアデータ、特に画像ドキュメントストリームのような、複数のデータをセグメント化するための方法、情報システム及びコンピュータ読取可能媒体を提供することを課題とする。
【００１０】
本発明の態様によれば、本方法は、一連の複数のデータをｋ個のセグメントにセグメント化する。前記複数のデータを表す、第１と第２の一連の数（”第１と第２のストリング”と呼ぶ）が夫々生成される。前記第１と第２のストリングは、夫々ｋ−１個の境界を有する。第１と第２の適応度関数値は、夫々前記第１と第２のストリングによって表されるデータに対して計算される。前記複数のデータを夫々表し、ｋ−１個の境界を有する第３と第４の一連の数（”第３と第４のストリング”と呼ぶ）が前記第１と第２の適応度関数値に基づいて生成される。前記第３と第４のストリング中のパーティションポイント（”交叉”と呼ぶ）が選択される。この交叉は、前記第３のストリングを前部の一連の数と後部の一連の数とに区分する。第４のストリングもまた前部の一連の数と後部の一連の数とに区分される。第３のストリングの後部の一連の数は、第４のストリングの後部の一連の数と交換されて第５と第６の一連の数（”第５と第６のストリング”と呼ぶ）を形成する。第５と第６のストリングの数は、等しいｋ−１個の境界へ調節される。次に、第５と第６のストリングによって表されるデータに対する第３と第４の適応関数値が計算される。ｋ個のセグメントは、第１、第２、第３、及び第４の適応度関数値を比較し、適応度関数値が最も高いストリングのｋ‐１個の境界に基づいて提供される。
【００１１】
本発明の一態様に従って、前記複数のデータは、複数の画像を含む。
【００１２】
本発明の一態様に従って、前記複数のデータは、複数のビデオフレームを含む。
【００１３】
本発明の一態様に従って、前記複数のデータは、複数のプレゼンテーションスライドを含む。
【００１４】
本発明の一態様に従って、前記複数のデータは、ノートの頁を含む。
【００１５】
本発明の一態様に従って、前記複数のデータは、複数の非画像データを含む。
【００１６】
本発明の一態様に従って、前記方法は、更に前記複数のデータを減少するためのステップを含む。
【００１７】
本発明の一態様に従って、前記複数のデータは、前記複数の画像をサブサンプリングし及び／又は標準偏差測定を使用して減少される。
【００１８】
本発明の一態様に従って、前記適応度関数は、画像の類似度、重要度及び優先順位に基づく。
【００１９】
本発明の一態様に従って、前記適応度関数は、隣接するデータ同士間のヒストグラム差に基づく。
【００２０】
本発明の一態様に従って、前記適応度関数は、下記の数式に等しい。
【数５】
0003921967.tif 000002
【００２１】
本発明の一態様に従って、前記適応度関数は、下記の数式に等しい。
【数６】
0003921967.tif 000003
【００２２】
本発明の一態様に従って、前記適応度関数は、下記の数式に等しい。
【数７】
0003921967.tif 000004
【００２３】
本発明の一態様に従って、前記方法は、更に追加のデータを前記複数のデータへ追加するためのステップを含む。
【００２４】
本発明の一態様に従って、前記方法は、更にｋ個のセグメントを変化するためのステップを備える。
【００２５】
本発明の一態様に従って、前記適応度関数は、下記の数式に等しい重要度ファクタを含む。
【数８】
0003921967.tif 000005
【００２６】
本発明の一態様に従って、一連の複数のデータをｋ個のセグメントへセグメント化するための情報システムが提供される。このシステムは、メモリに結合されるプロセッサを備える。メモリは、複数のデータをセグメント化するためのソフトウエアプログラムを格納する。前記複数のデータは、一連の０と１で符号化され、境界セグメンテーションポイントとしてｋ−１個の１が使用される。前記ソフトウエアプログラムは、前記複数のデータを表し且つｋ−１個の１を有するストリングの前記複数のデータに対する適応度関数値を得るための適応度関数を含み、（Ａ）夫々前記複数のデータを表し且つｋ−１個の１を有する第１と第２の一連の０と１からなる数（以後”第１と第２のストリング”と呼ぶ）を夫々生成するステップと、（Ｂ）前記第１と第２のストリングによって表される前記複数のデータに対する前記第１と第２の適応度関数値に基づいて、夫々前記複数のデータを表し且つｋ−１個の１を有する第３と第４の一連の０と１からなる数（以後”第３と第４のストリング”と呼ぶ）を夫々生成するステップと、（Ｃ）前記第３と第４のストリング中のパーティションポイント（以後”交叉”と呼ぶ）を選択するステップであって、前記交叉が（１）前記第３のストリングを前部の一連の数と後部の一連の数とに区分し、且つ（２）第４のストリングを前部の一連の数と後部の一連の数とに区分する、前記選択するステップと、（Ｄ）前記第３のストリングの後部の一連の数を前記第４のストリングの後部の数と交換して第５と第６の一連の数（以後”第５と第６のストリング”と呼ぶ）を形成するステップと、（Ｅ）前記第５と第６のストリング中の１の数をいずれもｋ−１個に調節するステップと、（Ｆ）前記第１、第２の適応度関数値、前記第５と第６のストリングによって表される前記データに対する第３、第４の適応度関数値の比較し、適応度関数値が最も高いストリングの境界セグメンテーションポイントに基づいてｋ個のセグメントを供給するステップとをコンピュータに実行させる。
【００２７】
本発明の一態様に従って、一連の複数のデータをｋ個のセグメントにセグメント化するための手順をコンピュータに実行させるためのプログラムが提供される。第１のソフトウエアプログラム部分は、夫々各複数のデータに対応する第１のストリングと第２のストリングを形成する。第１と第２のストリングは、ｋ−１個の境界ポイントを有する。第２のソフトウエアプログラム部分は、夫々前記第１と第２のストリングによって表される複数のデータに対して第１と第２の適応度関数値を計算する。第３のソフトウエアプログラム部分は、前記第１と第２の適応度関数値と遺伝子操作に基づいて前記複数のデータに対応する第３と第４のストリングを生成する。前記遺伝子操作は、前記第３のストリングと前記第４のストリング中のパーティションポイントで互いの後部を交換する交叉操作と、前記第３と第４のストリング中の境界ポイントを等しくｋ−１個の数に調整する突然変異操作とを含む。また、第２のソフトウエアプログラムは、前記第３と第４のストリングによって表される複数のデータに対して第３と第４の適応度関数値を計算する。第４のソフトウエアプログラムは、前記第１、第２、第３及び第４の適応度関数値を比較し、適応度関数値が最も高いストリングのｋ‐１個の境界ポイントに基づいてｋ個のセグメントを選択する。
【００２８】
本発明は、生物学的技術、特にデータストリームをセグメント化する遺伝的方法における教示を利用する。クラスタリング方法のような現在のセグメント化方法に比較して遺伝的方法には幾つかの利点がある。第１に、遺伝的方法は、指定された評価関数とは独立しており、ジャンル、ドメイン、ユーザタイプ等に依存する発見に基づいて種々の特徴をするように調節され得る。第２に、遺伝的方法は、増分的セグメンテーションを行なうのに本来適し、これは、ビデオのストリーミング（例えば、ウエブ上のビデオ）に適用され得る。第３に、遺伝的方法は、ユーザパターンに適するダイナミックに更新されたセグメンテーションを支援出来る。以下で記述されるように、本発明の一実施の形態は、しばしばアクセスされる画像がセグメント境界として現れる可能性を増加する。
【００２９】
Ｉ．評価セグメンテーション
ビデオのセグメンテーションを特徴付け且つ評価する時、特定のアプリケーションが留意される事が必要である。ブラウジングと要約作成（概略作成）のために、我々は、複雑さの度合いが変化する類似度隣接関数（ｓｉｍｉｌａｒｉｔｙａｄｊａｃｅｎｃｙ  ｆｕｎｃｔｉｏｎｓ）を定義する。最も単純なフォームでは、これらの関数は、画像の差を考慮するだけである。より複雑なフォームでは、情報検索アイデアが使用される。
【００３０】
当業者が評価しているように、本発明の実施の形態は、非画像データストリーム及び画像データストリームのセグメント化を含む。遺伝的セグメンテーション方法は、異なる適応度関数がその媒体の適切な特性とこの媒体を処理するためのソフトウエアを考慮すべきである場合を除いて、非画像データストリームに対して同じままである。
【００３１】
Ａ．事前処理
ビデオは、数千のフレームを備えることが可能であり、多くの隣接するフレームは、類似している傾向がある。複数の画像は、唯あまり類似しない画像を見ることによって減少され得る。非ビデオ画像ドキュメントストリームに対しては、この事前処理ステップがスキップされてもよい。一実施の形態において、ビデオは、減少されたセットの画像ドキュメント又はフレームＦを得るためにサブサンプリングされてもよい。例えば、一分間に３０個のフレームで記録されたビデオは、一分間に１フレームでサブサンプリングされる。この減少されたセットＦから、Ｂｏｒｅｃｚｋｙにおいて記述されているように、より少ない類似画像ドキュメントがカラーヒストグラムを使用してそれらの差を測定することによって選択される。任意の二つの画像ｉとｊに対して、
ｈ（ｉ，ｊ）＝ｉとｊとの間のヒストグラム差、
ｄｈ（０）＝ｈ（１，０）の場合、ｄｈ（ｉ）＝ｈ（ｉ‐１，ｉ）
が定義される。
Ｆ中のフレームの数は、平均
【数９】
0003921967.tif 000006
から一標準偏差よりも大きなｄｈを有するフレームのみを取ることによって更に減少される。
【００３２】
減少量は、ビデオのジャンルによって変化する。
【００３３】
この減少されたセットＦ’に関して、長さ、即ち、
δ（ｉ）＝ｉからＦ’中の次の要素までのＦ中のフレームの数
が定義される
Ｆ’に関して、ｄｈ（ｉ）に類似するｄＨ（ｉ）を定義する。
ここで、ｄＨ（ｉ）＝Ｆ’中の（ｉ−１）番目の要素とｉ番目の要素との間のヒストグラム差である。
【００３４】
Ｂ．評価関数
本発明の種々の実施の形態は、異なる評価関数を使用する。当業者には理解されているように、評価関数は、ジャンル、ドメイン、ユーザタイプ等に依存する発見に基づき得る。ブラウジングのためのビデオの要約作成とインデックス付けの実施の形態に対して、評価関数は、画像類似度、重要度及び優先順位に基づく。
【００３５】
実施の形態において、最も高いｄｈ（Ｉ）又はｄＨ（ｉ）を有するｋ個の画像がセグメント境界として使用される。これらのｋ個の画像が画像データストリームに対するアクセスポイントであるブラウジングと要約作成アプリケーションに対して、これは、最も目立った画像が互いに類似するかもしれず（それらがそれらの直ぐ隣に類似しない場合でも）且つあまりにも多くの繰返しが結果に発生するので、あまり良好なセグメンテーションを生成しない。
【００３６】
選択された画像同士間での相対的差を考慮するために、類似度隣接関数が以下のように定義される。
ＳｋがＦ’中のｋ個の選択された画像のサブセットであるとすると、
【数１０】
0003921967.tif 000007
が定義される。ここでα（ｉ，ｊ）は、ヒストグラム差を重み付けする関数である。
【００３７】
実施の形態において、α（ｉ，ｊ）は、１であってもよい。他の実施の形態では、より小さい重みが
α（ｉ，ｊ）＝  １／|ｉ−ｊ|2（ｉ≠ｊに対して）、そうでない場合は、０をセットすることによって更に離れた画像に配される。
【００３８】
一セット中のｋ個のサブセットの大きな属性の共有に起因して、順当なサイズのセットに対してでさえ、式１を最適化するための効率的な標準的方法はない。遺伝的方法を使用する場合の一利点は、この空間を有効にサーチすることが可能なことである。
【００３９】
また、情報検索アイデアは、その重要度で画像形成を重み付けすることに使用されてもよい。重要度を定義する一つの方法は、Ｕｃｈｉｈａｓｈｉで述べられているように、属性の共有を有する要素の長さを計算に入れる関数を使用することであり、それによってより長く且つより少ない共通フレームがより大きな重要度を有する。Ｕｃｈｉｈａｓｈｉとは異なり、本発明の実施の形態は、画像のクラスタリングに依存することなくこれを行う。
【００４０】
第１に、セットＣiは、ｉに類似する要素であると定義される。
ここで、
【数１１】
0003921967.tif 000008
である。
【数１２】
0003921967.tif 000009
とすると、
下記の数式によって長さと属性の共有に基づき重要度を定義する。
【数１３】
0003921967.tif 000010
【００４１】
Ｕｃｈｉｈａｓｈｉとは異なり、本発明の実施の形態は、δ（ｉ）が大きなばらつきを有するので、長さの対数を使用する。ビデオでは、Ｆ’中の要素の複数の長さは、１００のオーダー（ファクタ）で異なってもよい。
【００４２】
更に、フレームの優先順位に関連する他のファクタを提供することによって重要度のこの概念を拡張し、それによってより早く表れるフレームが同じ類似度クラスにおけるより遅いものに比較してより重く重み付けされる。基準として優先順位を使用する幾つかの理由がある。ビデオの場合、ビデオ再生使用での学習で、より早い出現する事象はより多くアクセスされるということに気付いた。人々の画像やスライドの場合、より早いものは、より遅いものを参照する物を導入又は定義し得る。監視や携帯のパーソナルビデオカメラの場合、フレームは、興味ある事象の内の最近の発生にスポットライトを当てるために後方へ処理され得る（又は、我々の優先順位定義を逆転する）。
【数１４】
0003921967.tif 000011
とすると、
下記の数式によって優先順位ファクタが定義される。
【数１５】
0003921967.tif 000012
【００４３】
長さ、属性の共有、及び優先順位を共に配すると、重要度
【数１６】
0003921967.tif 000013
が得られる。
【００４４】
一実施の形態では、重要度Ｉiは、平均重要度で各項を重み付けすることによって評価関数、例えば式１、と共に使用される。即ち、
α（ｉ，ｊ）＝  （Ｉi+Ｉj）／|ｉ−ｊ|2（ｉ≠ｊに対して）、そうでない場合は、０がセットされる。
【００４５】
一実施の形態では、評価関数は、下記の数式である。
【数１７】
0003921967.tif 000014
【００４６】
質的に、この類似度隣接関数の効果は、より密接な画像をより非類似にしており、ビデオのリズムを捕獲するために全体のサマリー中である量の繰返しが可能となる。
【００４７】
上述のように、本発明の他の実施の形態は、セグメンテーションの望ましい性質を特徴付ける異なる適応度関数や評価関数を有し、以下に記述される方法と共に働く。
【００４８】
ＩＩ．遺伝的セグメンテーション方法
第１に、遺伝的セグメンテーション方法の入力と出力が記述される。入力は、ビデオであり、望ましい数のセグメント境界に対する整数ｋである。例えば、図５は、遺伝的セグメンテーション方法へ入力されるべきビデオの５秒毎にサンプリングされた複数のビデオフレームを示す。同様に、図８は、遺伝的セグメンテーション方法へ入力され得る複数のプレゼンテーションスライドを示す。遺伝的セグメンテーション方法の出力は、インデックス付けし且つ要約作成するためのアクセスポイントとしての境界画像である。換言すれば、出力は、ｋ個の境界画像のシーケンスとそれらの重要度スコアである。例えば、図３と図４は、図５に示される境界ビデオフレームの出力を示す。同様に、図６と図７は、図８のスライドを遺伝的セグメンテーション方法へ入力することによって出力される境界プレゼンテーションスライドを示す。また、ｋを変化する実施の形態は以下に記述される。重要度スコアは、Ｕｃｈｉｈａｓｈｉに記述されているように、レイアウト目的のために使用されてもよい。
【００４９】
本発明の実施の形態は、遺伝的方法で使用されているように、符号化、適応度関数、交叉及び突然変異操作を指定することによって記述され得る。当業者が理解しているように、個体の母集団（又は、画像ドキュメントストリームのような、複数のデータを表す複数のストリング）が発生され、評価プロセスが１度に１世代反復的に実行される。終りに、最も高い適応度関数を有する個体（又はストリング）は、境界セグメント（又は境界画像）を得るために復号化される。
【００５０】
Ａ．符号化
データ又は画像ドキュメントに対応するストリングの又は一連の０（複数）と１（複数）は、遺伝的方法におけるように構成される。このストリングは、染色体と呼ばれる。ビデオデータストリーム構造は、それ自体が連続するグループに分割されて、ストリングが十分である。対照的に、他の方法は、セットを使用する。例えば、１９９１年のシンガポールにおける、Ｗｏｒｌｄ  Ｓｃｉｅｎｔｉｆｉｃ  Ｐｕｂｌｉｓｈｉｎｇ  Ｃｏ．のＲ．Ｇｕｔｉｅｒｒｅｚ氏とＭ．Ｍ．Ｖａｌｄｅｒｒａｍａ氏（編集者）によるＡｐｐｌｉｅｄ  Ｓｔｏｃｈａｓｔｉｃ  Ｍｏｄｅｌ  ａｎｄ  Ｄａｔａ  Ａｎａｌｙｓｉｓにおける第５回国際シンポジュームの会報の１９８頁から２０６頁の（１９９８）Ｅ．Ｆａｌｋａｎａｕｓｅｒ氏による”Ｇｅｎｅｔｉｃ  Ａｌｇｏｒｉｔｈｍｓ  ａｎｄ  Ｇｒｏｕｐｉｎｇ  Ｐｒｏｂｌｅｍｓ”における（１９９１）Ｅ．Ｆａｌｋａｎａｅｒ氏のＡ  ｇｅｎｅｔｉｃ  ａｌｇｏｒｉｔｈｍ  ｆｏｒ  ｇｒｏｕｐｉｎｇ．
【００５１】
染色体ストリングのビット位置は、左から右に読まれる、データストリームの要素（例えば、Ｆ’におけるビデオフレーム）のインデックスである。このストリングの長さは、画像の数（即ち、｜Ｆ'｜である。一実施の形態において、１（複数）グループの境界を示すために使用される。例えば、００１０００１００１０は、グループ００．１０００、１００、及び１０に分解される。フレームに関して、Ｆ’＝｛ｉ0，ｉ1，ｉ2，．．．ｉ10｝に対する対応するグループは、｛ｉ0，ｉ1｝、｛ｉ2，ｉ3，ｉ4，ｉ5｝、｛ｉ6，ｉ7，ｉ8｝、及び｛ｉ9，ｉ10｝である。一実施の形態では、セグメントの数は、固定の定数であるように設定される。他の実施の形態において、ユーザは、セグメントの数を選択出来る。一実施の形態において、１の数は、境界画像の望ましい数を表す。他の実施の形態において、符号化は、全てのセグメントに対して１への最も左のビットへ設定されることが出来る。
【００５２】
Ｂ．適応度関数
本発明の一実施の形態において、式２が適応度関数として使用される。他の実施の形態において、他の評価関数が使用されてもよい。
【００５３】
Ｃ．交叉及び突然変異
遺伝的方法は、次の世代に対する再生のためにランダムに選択した対の個体染色体を使用する。選択されるべき染色体の確率は、同じ世代の他の染色体に相対するその適応度関数値に比例する。再生するために、交叉手順が定義される。遺伝的方法において、二つの染色体ストリングはクロシング（交叉）サイトに対してランダムのビットを選択することによって再生し、且つそれらのストリングは、そのサイトでスライスされ、この二つの後部片がスワップされ、前部片と再結合されて二つの子孫を生成する。例えば、第２番目のサイトでクロスされた１０００００１００１１と１１１１０００００００が１１００００１００１１と１０１１０００００００を生成する。
【００５４】
データストリームは、本発明の方法が遺伝的方法のようにストリング構造を使用することを可能とするが、任意のビットでクロシングする代わりに、クロシングがセグメント境界で発生する。セグメントは、ランダムに選択される、即ち、各インデックスに対して等しい確率を有する
【外１】
0003921967.tif 000015
が選択される。このインデックスは、クロシングサイトとして使用される。染色体ストリングは、遺伝的方法と同様にクロスされ、更に得られたストリングを変更する追加のステップによって、それらは、固定された数のセグメントを維持するように、正確にｋ個の１を有する。
【００５５】
ストリング中のセグメントの数を減少することは、交叉手順によってスライスされた部分的片を隣接セグメントと併合することによって行なわれ、この方法では、より早い世代からのセグメント境界が保持される。次に、隣接するセグメントは、ｋ個の１が残るまで、一緒に併合される。
【００５６】
ストリング中のセグメントの数を増加することは、より早い世代から継承されない新たな境界を導入することが必要である。一実施の形態では、クロシングサイト近くのセグメントが選択され、その最も弱い点で、例えば、最も小さなｄＨを有する点でスプリットされる。他の実施の形態では、演算量は、突然変異処理を使用してグループをスプリットすることによって減少され、これは、スプリットされる場所をランダムに選択することを意味する。以下で述べられる例は、この演算量の減少の実施の形態を使用する。
【００５７】
一般に、ストリング中のランダムなフリッピングによる突然変異は、セグメントを行なうためには好ましくない。理由は、この突然変異がセグメントをむしろ不安定にするからである。ゆえに、本発明の実施の形態は、交叉手順におけるセグメントの数を増加するためにその使用を越えて追加の突然変異を行わない。
【００５８】
以下では、交叉及び突然変異の例が記述される。以下のストリングは、４個のグループを有し、１が１の左側にセグメント境界をマークする：
０００１００１００１０
０１０００１００１００
【００５９】
第１のストリングの第２のセグメントの後のポイントでのクロシングにおいて、サイト６で、
０００１００｜００１００
０１０００１｜１００１０
【００６０】
第１のストリングにおいて、ランダムなビット（ｉ＝２）は、１に突然変異されて、セグメントの数を４へ増加する。第２のストリングにおいて、第３番目の１がフリップされてセグメントの数を４へ減少する。最終結果は、
００１００００１００
０１００００１００１０
【００６１】
符号化、適応度関数、交叉及び突然変異（交叉の一部として）操作の記述において、遺伝的セグメント方法が指定される。
【００６２】
Ｄ．セグメントフェア‐交叉
遺伝的方法における交叉と本発明の実施の形態における交叉との間のキーとなる違いは、遺伝的方法において、交叉サイトが各ビットに対して等しい確率を有するように選択され、他方、本発明の実施の形態において、交叉サイトは、各セグメントに対して等しい確率を有するように選択される。これは、セグメントフェア‐交叉と呼ばれる。
【００６３】
１が二つの親の染色体をラインアップし交叉を実行する時、このように二つの親の連続遺伝子座での対立遺伝子が０である短いサブストリング及び長いサブストリングある。
【外２】
0003921967.tif 000016
【００６４】
どの交叉サイトが［ａ，ｂ］及び［ｃ，ｄ］において選択されようと、結果となる子孫が同じになる。一般に、二つの親の染色体においてｋ個のオーバーラップしない１がある時、２ｋ+１個の異なる交叉の結果の可能性がある。各セグメント毎に等しい確率を有する交叉サイトを選択することによって、本発明のセグメントフェア‐交叉は、２ｋ+１個の可能な交叉の結果から均一にサンプリングを行なう。遺伝子的方法は、可能な交叉の結果のこの均一なサンプリングから外れる。理由は、０の交差するサブストリングが短くなればなる程、交叉サイトを選択する可能性が一層少なくなる。
【００６５】
ＩＩＩ．遺伝的方法のフローチャート
当業者には理解されるように、図１と図２は、指定の機能を実行するための論理ブロック図を示す。他の実施の形態において、より多くの或いはより少ない数の論理ブロックが使用されてもよい。本発明の一実施の形態において、論理ブロックは、ソフトウエアプログラム、ソフトウエアオブジェクト、ソフトウエア関数（機能）、コードフラグメント、ハードウエアオペレーション、ユーザオペレーションを単独で或いはこれらの組合せを表す。
【００６６】
図１と図２は、本発明の実施の形態に従って、画像データをセグメント化するためのフロー図を示す。本発明の一実施の形態において、複数のシーケンシャルなドキュメント画像が論理ブロック１０１に示されるように得られる。
【００６７】
図３は、本発明のビデオの実施の形態における複数のドキュメント画像を示す。本発明の他の実施の形態において、他の非画像データが得られてもよい。
【００６８】
望ましい数のセグメント境界画像ｋが論理ブロック１０２に示されるように得られる。本発明の一実施の形態において、セグメント境界画像の数はユーザによって提供される。
【００６９】
複数のストリングの母集団は、論理ブロック１０３によって示されるように得られる。このストリングの母集団は、複数のランダムに選択された１と０で画像データストリームを符号化することによって得られる。本発明の一実施の形態において、各ストリングは、境界ポイント又は画像を表すために使用されるｋ個のランダムに選択された１を含む。
【００７０】
本発明の他の実施の形態では、他の数値がデータ及び／又は境界ポイントを表すように使用され得る。
【００７１】
ストリングは、論理ブロック１０４によって示されるように、母集団中で選択される。
【００７２】
適応度関数値は、論理ブロック１０５によって示されるように、選択されたストリングに対応して得られる複数の画像に対して計算される。本発明の一実施の形態において、適応度関数は、式１または式２であり得る。本発明の他の実施の形態において、適応度関数は、非画像データに対して使用され得る。
【００７３】
次に、計算された適応度関数値は、論理ブロック１０６によって示されるように、最も高い先に計算された適応度関数値に比較される。一実施の形態において、初期の適応度関数値は０である。
【００７４】
計算された適応度関数が先に計算された適応度関数よりも大きい場合、現在計算された適応度関数値が、論理ブロック１０７に示されるように、画像のセグメントと共に格納される。
【００７５】
決定ブロック１０８によって示されるように、母集団が評価されたか否か、或いは換言すれば、母集団中の全てのストリングが対応する適応度関数値を有するか否かについての決定がなされる。１が母集団の終りに無い場合、制御は、論理ブロック１０４に移行して、そこで論理ブロック１０４から１０７までに記述される機能が次に選択されたストリングに対して繰返される。そうでない場合は、制御は、論理ブロック１０９へ移行し、そこで母集団中の一対のストリングがそれらの夫々の適応度関数値に基づいて選択される。本発明の一実施の形態において、論理ブロック１０９から１１２は、上述の交叉と突然変異操作を実行する。
【００７６】
交叉は、論理ブロック１１０によって示されるように、セグメント境界ポイントで第１のストリング中で選択される。
【００７７】
次に、論理ブロック１１１に示されるように、交叉後の第１のストリングのセクション、即ち第１の後部が第２のストリング中の対応するセクション、即ち第２の後部とスワップされる。
【００７８】
一実施の形態において、論理ブロック１１２に示されるように、第１と第２のストリングは、両方のストリング中にｋ個の１を得るために１（複数）を加算又は減算することによって突然変異される。
【００７９】
決定ブロック１１３に示されるように、一世代が完了されたか否かが決定される。一世代が完了されていない場合、論理はブロック１０９に移行し、そこで論理ブロック１０９から１１２によって示される機能が繰返される。例えば、第２の対のストリングが世代を形成するために選択される。そうでない場合は、制御が決定ブロック１１４に移行し、そこで新たな母集団が評価されるべきか否かが決定される。そうである場合、制御が論理ブロック１０４乃至１１３に移行する。そうでない場合は、制御は、論理ブロック１１５に移行する。論理ブロック１１５では、最も高い適応度関数値を有するストリング中の１（複数）によって表されるｋ枚のドキュメント画像が提供される。これらのドキュメント画像は、図９に示されるように、ユーザＩ／Ｏ８２０或いはそれと等価物へ提供され得る。
【００８０】
ＩＶ．他の実施の形態
以下に本発明の他の実施の形態が記述される。特に、他の実施の形態は、増分的セグメンテーションを扱い且つそのセグメンテーション中の選択された境界画像の数ｋを変化するための類似度隣接関数を含む。画像がブラウジング及び要約作成のために使用される実施の形態において、セグメンテーションがユーザアクセスパターンに対してダイナミックに適用される一実施の形態が記述される。
【００８１】
Ａ．増分的要約作成
本発明の実施の形態は、進化的であり、要約作成を可能とする増分的セグメンテーションに適する。ストリーミングビデオと累積画像のデータベースは、増分的セグメンテーションが使用される例である。本発明の一実施の形態は、母集団を維持し、且つ新たな画像が追加されるとこの母集団を進化（発展）させる。見つけられた良好な画像セグメント境界は、存続し続ける可能性がより大きい。各世代毎に、最も高い適応度関数値を有する画像のセグメントやコレクションは、そのセグメンテーションを決定するために使用される。
【００８２】
世代間で、新たな画像が追加される。一実施の形態において、上述のように、新たな画像は、ｄＨの実行平均を維持することによって事前処理される。新たな画像が追加された時に、境界付けられる染色体長を維持するために、古いものは、低い重要度又は低いｄＨを有するものを捨てる事に用って除去されてもよい。これは可能である。理由は、式２の”優勢”（ビット位置が適応度関数に影響を及ぼす方法）が非常に良好に作用するからである。低いレートの画像をドロップすることは、式２の適応度関数値への影響は殆どない。ｋを一定に保つために、染色体が一つの１によってマークされたビット位置を失うと、新たなビット位置の一つがランダムに１にセットされる。新たなビット位置の多くは、０に設定されるが、場合によっては（その染色体の長さ分の１の確率を有する）ビット位置が１に設定され、且つランダムなセグメントがｋを一定に維持するように併合される。
【００８３】
Ｂ．  ｋの変化
一実施の形態において、セグメント境界画像の数ｋは変化してもよい。これは、評価関数、式２の評価関数を指定されたターゲットｋ0に正規化し且つｋを一定に維持しないように交叉を単純化することによって達成される。
【数１８】
0003921967.tif 000017
この実施の形態において、画像の数は、正確にはｋ0ではなく、よりよい可能性のセグメンテーションを提供する約ｋ0のある数である。
【００８４】
Ｃ．ユーザアクセスパターンへの適用
一実施の形態において、セグメンテーションは、ユーザアクセスパターンを反映するようにダイナミックに更新され得る。ユーザによって最もしばしばアクセスされる画像は、式２の重要度の項に関してより重く重み付けされ、かつセグメンテーションは、増分的に更新される。一実施の形態において、更新スケジュールは、日々、週単位或いはそれより長い単位であってもよい。
【００８５】
ａiは画像がアクセス又はユーザによって見られた回数とすると、アクセス頻度ファクタは、Ａｉ＝１+ｌｏｇ（１+ａi）で定義される。次に、以下は式２の重要度に対して使用される。
【数１９】
0003921967.tif 000018
【００８６】
Ｖ．実施例
本発明の実施の形態を実施する二つの実施例が以下に記述される。
【００８７】
Ａ．ビデオ
初めに、本発明の実施の形態は、図５に示される長時間のビデオテープの要約作成のために使用された。図３と４は、ｋが５の場合と１１の場合でセグメント化されたビデオ及び第１のセグメントの第１の画像を示す。６枚と１２枚の画像が選択された。理由は、こららの数は、幾つかの除数を有し、且つ異なるレイアウト（例えば、６は、６ｘ１，２ｘ３，３ｘ２，６ｘ１を与える）を生成できるからである。見られるように、ブラウジング及び検索のために要約作成やインデックス付けするために使用され得る非常に異なる画像は、図５に示される大量のフレームから図３と図４に示されるようにディスプレイされる。
【００８８】
ビデオの例では、１００世代に亘る２，０００ランの母集団サイズが使用された。ビデオの長さは約１時間であり、かつサブサンプリングと減少は、|F|＝７７６５と|F'|＝１４９を与えた。事前処理は約２分掛かり、セグメント画像を得るための方法は、約３分掛かった。
【００８９】
ビデオテープのセミナーの三つのトピックスは、”Ａｃｔｉｖｅ  Ｍｅｓｓｅｎｇｅｒ"、”ｃｏｍＭｏｔｉｏｎ”及び”Ｎｏｍａｄｉｃ  Ｒａｄｉｏ”であり、これらのトピックスを導入するビデオテープスライドのビデオフレームは、話者の二つのピクチャーと部屋のピクチャーと共に選択された。
【００９０】
Ｂ．プレゼンテーションスライド
第２の実施例は、図８に示される注釈付プレゼンテーションスライド画像とピクチャーを含む１セットのノート頁を使用する。ノート頁は、ＦＸＰＡＬ  ＮｏｔｅＬｏｏｋ  Ｓｙｓｔｅｍによって提供される。このシステムは、ニューヨークのＡＣＭ社のＡＣＭ  Ｍｕｌｔｉｍｅｄｉａ’９９の論文の１４９頁から１５８頁のＰ．Ｃｈｉｕ氏、Ａ．Ｋａｐｕｓｋａｒ氏、Ｓ．Ｒｅｉｔｍｅｉｅｒ氏、及びＬ．Ｗｉｌｃｏｘ氏の”Ｔａｋｉｎｇ  ｎｏｔｅｓ  ｉｎ  ｍｅｅｔｉｎｇｓ  ｗｉｔｈ  ｄｉｇｉｔａｌ  ｖｉｄｅｏ  ａｎｄ  ｉｎｋ”に示されており、ここには、種々のビジュアル画像、プレゼンテーションスライド画像、ピクチャー及びインク注釈を含む。図６と図７は、本発明の実施の形態から出力される複数のセグメントノート頁を示す。図６は、ｋが５の場合のセグメント化された６枚のノート頁を示し、図７は、第１のセグメントの第１の画像と共に、ｋが１１の場合のセグメント化された１２枚のプレゼンテーションスライドを示す。上記のビデオの実施例では、ノート頁は、明瞭に異なる。
【００９１】
他の実施の形態では、本方法は、プレゼンテーションスライドのコレクション（例えば、ＰｏｗｅｒＰｏｉｎｔ  ｓｌｉｄｅｓ）のようなより単純な画像データストリームを使用する。
【００９２】
ノート頁の実施例では、１００世代に亘る１，０００ランの母集団が使用された。上記のビデオの実施例では、図６と図７は、図８に示されるノート頁からの明瞭に異なるデータを示す。
【００９３】
Ｃ．パラメータ
上記実施例のパラメータは、遺伝的操作の１００％に対して交叉を含む。突然変異は、上記に定義されるように交叉セグメントをスプリットする間のみに導入された。エリート主義は使用されなかった。式２の適応度関数は、提供された実施例において使用された。
【００９４】
ＶＩ．ハードウエアとソフトウエアアーキテクチャの実施の形態
図９は、本発明の一実施の形態に従う、データをセグメント化するために適する例示の情報システムのハードウエアとソフトウエア要素を示す。図９のシステム７９９は、コネクション８２９のような一つ或いはそれより多くの通信パスウエイによってローカルエリアネットワーク（ＬＡＮ）８４０及びここではインターネット８８０として描かれているワイドエリアネットワークへ接続される処理デバイス８００を含む。ＬＡＮ８４０を介して、処理デバイス８００は、スキャナ８４１及びカメラ８５１のような他の処理デバイスと通信出来る。他の実施の形態では、スキャナ８４１とカメラ８５１は、物理的にＬＡＮ８４０には接続されていない。インターネット８８０を介して、処理デバイス８００がウエブクライアント８８１のような、局所にあり且つ遠くにある他の処理デバイスと通信出来る。理解されるように、処理デバイス８００からインターネット８８０への接続は、種々の方法、例えば、コネクション８２９（配線又は無線）を介して直接に、或いはローカルエリアネットワーク８４０を介して、又はモデム（図示せず）によって行われ得る。
【００９５】
本発明の実施の形態における処理デバイス８００は、パーソナル又はオフィスコンピュータである。例示の実施の形態は、Ｄｅｌｌ（登録商標）Ｄｉｍｅｎｓｉｏｎ（登録商標）ＸＰＳ  Ｂ  Ｓｅｒｉｅｓ  Ｄｅｓｋｔｏｐ  ｃｏｍｐｕｔｅｒ（Ｄｅｌｌ  Ｃｏｍｐｕｔｅｒ  Ｃｏｍｐａｎｙ，Ｒｏｕｎｄ  Ｒｏｃｋ，ＴＸ）である。他の実施の形態において、処理デバイス８００は、パーソナルデジタルアシスタント（ＰＤＡ）、携帯コンピュータ、”Ｓｍａｒｔ”テレフォン、情報アプリケーション、或いはそれらと同等物である。説明のために、処理デバイス８００は、便利なように、ハードウエア構成要素８０１とソフトウエア構成要素８０２に分割されてもよいが、当業者は、この分割が概念的あり、幾分任意であり、且つハードウエアとソフトウエアとの間のラインは、硬くて固定したものではない事を理解している。更に、ホストコンピュータとそれに取付けられた周辺機器との間のラインは、硬くて固定したものではないこと、及び特に、幾つかのコンピュータの周辺機器であると考えられる構成要素は、他のコンピュータの統合された部分であると考えられることを理解している。
【００９６】
ハードウエア構成要素８０１は、プロセッサ（ＣＰＵ）８０５、メモリ８０６、持続的記憶装置８０８、ユーザＩ／Ｏ８２０、及びネットワークインターフェース８２５を含む。これらの構成要素は、当業者には周知であり、従ってここでは簡単な説明を行なう。
【００９７】
プロセッサ８０５は、例えば、マイクロプロセッサ又はマルチプロセッシングを行なうように構成されたマイクロプロセッサの集合体である。本発明の一実施の形態において、カリフォルニア州、サンタクララのＩｎｔｅｌ（登録商標）社によって提供される単一のＰｅｎｔｉｕｍ（登録商標）３５０プロセッサが使用される。幾つかの実施の形態においては、共に動作する複数のコンピュータ（分散演算）によって処理デバイス８００の役割が果たされてもよい事を理解すべきである。このような実施の形態において、図９のシステムの処理デバイス８００の機能性は、これらの処理デバイスの組み合わせによって発揮され、プロセッサ８０５の処理能力は、複数のコンピュータの組み合わせプロセッサによって提供される。
【００９８】
メモリ８０６は、リードオンリメモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、仮想メモリ、又は他のメモリテクノロジーのようなコンピュータ可読媒体を、単独又は組合せで含むことが出来る。持続性記憶装置８０８は、例えば、磁気ハードデスク、フロピーデスク、又は他の持続性読出し・書き込みデータ記憶テクノロジーのようなコンピュータ可読媒体を、単独で又は組合せで含むことが出来る。更に、それは、ＣＤ−ＲＯＭや他の大容量記憶テクノロジーによって提供され得るような、大量の又は保管記憶装置を含んでもよい。（ウエブクライアント８８１は、類似するソフトウエアとハードウエア構成要素を備えてもよい事を留意すべきである）。一実施の形態において、持続性記憶装置８０８は、プレゼンテーションスライド８６１、ビデオファイル２００及びデータファイル８６５を記憶する。
【００９９】
ユーザＩ／Ｏ（入／出力）ハードウエア８２０は、一般的に、ＣＲＴやフラットパネルディスプレイのようなビジュアルディスプレイ、英数字キーボード、及びマウスや他のポインティングデバイスを含み、且つ任意ではあるが、更に、プリンタ、光学スキャナ、又は他のユーザ入力及び出力用デバイスを含んでもよい。一実施の形態では、ユーザＩ／Ｏ８２０は、セグメンテーションソフトウエア８８８によって提供されるビデオファイル２００のセグメント、プレゼンテーションスライド８６１又はデータファイル８６５の再生を選択するために使用される。
【０１００】
ネットワークＩ／Ｏハードウエア８２５は、処理デバイス８００と外部の世界とのインターフェースを提供する。具体的には、ネットワークＩ／Ｏ８２５は、プロセッサ８０５にコネクション８２９を介してＬＡＮ８４０とインターネット８８０を介する他のプロセッサとデバイスと通信させる。
【０１０１】
ソフトウエア構成要素８０２は、オペレーティングシステム９００及びこのオペレーティングシステム９００の制御下の一セットのタスクを含む。当業者には公知のように、オペレーティングシステム９００は、プロセッサ８０５が持続性記憶装置８０８、ユーザＩ／Ｏ８２０及びネットワークインターフェース８２５のような種々のデバイスを制御することを可能とする。プロセッサ８０５は、オペレーティングシステム９００のソフトウエア、及びメモリ８０６とコンピュータシステム７９９の他の構成要素と協力してそのタスクを実行する。
【０１０２】
一実施の形態では、ソフトウエア８０２は、ブラウザ８６２とビデオファイル２００を再生するためのビデオプレーヤ９０１を含む。一実施の形態では、ビデオプレーヤ９０１は、Ｍｏｖｉｎｇ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ（ＭＰＥＧ）プレーヤやＲｅａｌＶｉｄｅｏプレーヤである。本発明の一実施の形態では、ブラウザ８６２は、カリフォルニア州のマウンテンビューにあるＮｅｔｓｃａｐｅ（登録商標）Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｒｐｏｒａｔｉｏｎによって提供されるＮｅｔｓｃａｐｅ（登録商標）６．０ブラウザであってもよい。
【０１０３】
本発明の一実施の形態において、セグメンテーションソフトウエア８８８は、磁気ハードデスク、フロピーデスク、ＣＤ−ＲＯＭ、又は他の書き込み可能データ記憶テクノロジーのようなコンピュータ可読媒体である製品単独に或いは製品の組合せに記憶される。本発明の他の実施の形態において、ソフトウエア８８８は、図１と図２の方法１００で示される論理を実行する。
【０１０４】
当業者は、図９のシステムは例示のためであり、本発明を制限するなく、広範な演算デバイス、通信デバイス、及び情報とドキュメント処理デバイスが図８に示されているもの代わりに、或いはそれと共に使用され得ることを理解している。例えば、インターネット８８０を介するコネクションは、一般に、中間ルータコンピュータ（図示せず）を介するパケットスイッチングを含み、処理デバイス８００は、スキャナ８４１とカメラ８５１（本発明をこれらに限定する意図は無い）を含む任意の数の処理デバイスへアクセス可能である。
【０１０５】
本発明の好適な実施の形態の前述の記述は、例示及び説明目的で提供された。本発明をここで開示された正確な形態に制限する意図はない。当業者にとって明らかなごとく、多くの変更やバリエーションが可能である。本発明の実施の形態は、本発明の原理とその実際の用途を最良に説明するために選択及び記述され、それによって当業者が種々の実施の形態に対して及び意図された特定の使用に適する種々の変更を有する発明を理解出来る。本発明の範囲は、特許請求の範囲とそれと等価範囲によって定義される事が意図される。
【図面の簡単な説明】
【図１】本発明の実施の形態に従って、画像データをセグメント化するためのフロー図を示す。
【図２】本発明の実施の形態に従って、画像データをセグメント化するためのフロー図を示す。
【図３】本発明の実施の形態に従って、図５に示される複数のビデオフレームの内の６個にセグメント化されたフレームを示す。
【図４】本発明の実施の形態に従って、図５に示される複数のビデオフレームの内の１２個にセグメント化されたフレームを示す。
【図５】本発明の実施の形態に従って、セミナーの複数のビデオフレームを示す。
【図６】本発明の実施の形態に従って、図８に示される複数の頁の内の６個にセグメント化されたノートの頁を示す。
【図７】本発明の実施の形態に従って、図８に示される複数の頁の１２個にセグメント化されたノートの頁を示す。
【図８】本発明の実施の形態に従って、冗長なミーティングで使用される複数のノートの頁を示す。
【図９】本発明の実施の形態に従って、単純化されたソフトウエアとハードウエアのブロック図を示す。
【図１】
0003921967.tif 000023
【図２】
0003921967.tif 000024
【図３】
0003921967.tif 000025
【図４】
0003921967.tif 000026
【図５】
0003921967.tif 000027
【図６】
0003921967.tif 000028
【図７】
0003921967.tif 000029
【図８】
0003921967.tif 000030
【図９】
0003921967.tif 000031