(57)【要約】【課題】  伝送効率及び処理効率が改善されるような、一連のオーバーラップした画像を分割する方法及び装置等を提供する。【解決手段】  コンピュータ上でソフトウェア又はハードウェアにより実施化することができる本画像分割方法は、伝送されるべき複数のオーバーラップした画像の集合を、これら画像の可視部分のみが伝送されるように分割する。基礎となる分割アルゴリズムは、長方形を用いて上記画像集合を反復的に分割する。【選択図】      図４
2004159365.tif 000002
【特許請求の範囲】
【請求項１】
第１の一番下の画像と、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像とを少なくとも含む一群の画像を分割する方法において、
前記第１の画像の非オーバーラップ部分を前記第２の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第１集合を形成するステップと、
前記第１集合の画像要素のみを伝送するステップと、
を有していることを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
前記第１集合の画像要素における部分的にオーバーラップした各画像要素の非オーバーラップ部分を、前記画像の群における該第１集合の画像要素と部分的にオーバーラップする第３の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第２集合を形成するステップと、
前記第１及び第２集合の画像要素のみを伝送するステップと、
を更に有していることを特徴とする方法。
【請求項３】
請求項１または２に記載の方法において、前記第１集合の画像要素が前記第２の画像を含んでいることを特徴とする方法。
【請求項４】
請求項２に記載の方法において、前記第１集合の画像要素が前記第２の画像を含み、前記第２集合の画像要素が前記第３の画像を含んでいることを特徴とする方法。
【請求項５】
請求項１乃至４のいづれか一項に記載の方法において、前記分割するステップが部分的に圧縮されたドメインで実行されることを特徴とする方法。
【請求項６】
請求項１乃至５のいづれか一項に記載の方法において、前記各区域及び画像要素が長方形の形状であることを特徴とする方法。
【請求項７】
少なくとも幾つかが部分的にオーバーラップすると共に、第１の一番下の画像と最後の一番上の画像とを含む一群の画像を分割する方法において、
前記第１の画像の非オーバーラップ部分を、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像の位置に基づき複数の長方形に分割して、長方形の第１集合を形成するステップと、
前記一番上の画像の位置に基づいて長方形の最終的集合が形成されるまで、現集合の長方形を前記画像の群における次の画像に基づいて分割することにより長方形の新たな集合を反復的に形成するステップと、
前記最終的集合の長方形のみを伝送するステップと、
を有していることを特徴とする方法。
【請求項８】
請求項７に記載の方法において、前記第１集合の長方形が前記第２の画像を含み、長方形の各更なる集合が、該更なる集合に対する分割が基づいた画像を含むことを特徴とする方法。
【請求項９】
請求項７または８に記載の方法において、前記分割するステップが部分的に圧縮されたドメインで実行されることを特徴とする方法。
【請求項１０】
第１の一番下の画像と、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像とを少なくとも含む一群の画像を分割する装置において、
前記第１の画像の非オーバーラップ部分を前記第２の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第１集合を形成する手段と、
前記第１集合の画像要素のみを伝送する手段と、
を有していることを特徴とする装置。
【請求項１１】
請求項１０に記載の装置において、
前記第１集合の画像要素における部分的にオーバーラップした各画像要素の非オーバーラップ部分を、前記画像の群における該第１集合の画像要素と部分的にオーバーラップする第３の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第２集合を形成する手段と、
前記第１及び第２集合の画像要素のみを伝送する手段と、
を更に有していることを特徴とする装置。
【請求項１２】
請求項１０または１１に記載の装置において、前記第１集合の画像要素が前記第２の画像を含んでいることを特徴とする装置。
【請求項１３】
請求項１１に記載の装置において、前記第１集合の画像要素が前記第２の画像を含み、前記第２集合の画像要素が前記第３の画像を含んでいることを特徴とする装置。
【請求項１４】
請求項１０乃至１３のいづれか一項に記載の装置において、前記分割する動作が部分的に圧縮されたドメインで実行されることを特徴とする装置。
【請求項１５】
請求項１０乃至１４のいづれか一項に記載の装置において、前記各区域及び画像要素が長方形の形状であることを特徴とする装置。
【請求項１６】
少なくとも幾つかが部分的にオーバーラップすると共に、第１の一番下の画像と最後の一番上の画像とを含む一群の画像を分割する装置において、
前記第１の画像の非オーバーラップ部分を、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像の位置に基づき複数の長方形に分割して、長方形の第１集合を形成する手段と、
前記一番上の画像の位置に基づいて長方形の最終的集合が形成されるまで、現集合の長方形を前記画像の群における次の画像に基づいて分割することにより長方形の新たな集合を反復的に形成する手段と、
前記最終的集合の長方形のみを伝送する手段と、
を有していることを特徴とする装置。
【請求項１７】
請求項１６に記載の装置において、前記第１集合の長方形が前記第２の画像を含み、長方形の各更なる集合が、該更なる集合に対する分割が基づいた画像を含むことを特徴とする装置。
【請求項１８】
請求項１６または１７に記載の装置において、前記分割する動作が部分的に圧縮されたドメインで実行されることを特徴とする装置。
【請求項１９】
第１の一番下の画像と該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像とを少なくとも含む一群の画像を分割する方法を装置に実行させるためのプログラムを記録した、装置により読み取り可能な記録媒体であって、前記命令のプログラムが、
前記第１の画像の非オーバーラップ部分を前記第２の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第１集合を形成する命令と、
前記第１集合の画像要素のみを伝送する命令と、
を有していることを特徴とする記録媒体。
【請求項２０】
請求項１９に記載の装置により読み取り可能な記録媒体において、前記命令のプログラムが、
前記第１集合の画像要素における部分的にオーバーラップした各画像要素の非オーバーラップ部分を、前記画像の群における該第１集合の画像要素と部分的にオーバーラップする第３の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第２集合を形成する命令と、
前記第１及び第２集合の画像要素のみを伝送する命令と、
を更に有していることを特徴とする記録媒体。
【請求項２１】
請求項１９または２０に記載の装置により読み取り可能な記録媒体において、前記第１集合の画像要素が前記第２の画像を含んでいることを特徴とする記録媒体。
【請求項２２】
請求項２０に記載の装置により読み取り可能な記録媒体において、前記第１集合の画像要素が前記第２の画像を含み、前記第２集合の画像要素が前記第３の画像を含んでいることを特徴とする記録媒体。
【請求項２３】
請求項１９乃至２２のいづれか一項に記載の装置により読み取り可能な記録媒体において、前記分割する命令が、部分的に圧縮されたドメインで分割する命令を含んでいることを特徴とする記録媒体。
【請求項２４】
請求項１９乃至２３のいづれか一項に記載の装置により読み取り可能な記録媒体において、前記各区域及び画像要素が長方形の形状であることを特徴とする記録媒体。
【請求項２５】
第１の一番下の画像と該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像とを少なくとも含む一群の画像を分割する方法を装置に実行させるためのプログラムを記録した、装置により読み取り可能な記録媒体であって、前記命令のプログラムが、
前記第１の画像の非オーバーラップ部分を、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像の位置に基づき複数の長方形に分割して、長方形の第１集合を形成する命令と、
一番上の画像の位置に基づいて長方形の最終的集合が形成されるまで、現集合の長方形を前記画像の群における次の画像に基づいて分割することにより長方形の新たな集合を反復的に形成する命令と、
前記最終的集合の長方形のみを伝送する命令と、
を有していることを特徴とする記録媒体。
【請求項２６】
請求項２５に記載の装置により読み取り可能な記録媒体において、前記第１集合の長方形が前記第２の画像を含み、長方形の各更なる集合が、該更なる集合に対する分割が基づいた画像を含むことを特徴とする記録媒体。
【請求項２７】
請求項２５に記載の装置により読み取り可能な記録媒体において、前記分割する命令が、部分的に圧縮されたドメインで分割する命令を含んでいることを特徴とする記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像分割方法及び斯様な方法が実施されるコンピュータのような装置に関する。更に詳細には、本発明は、ダウンロード及び処理効率を改善するための、一連のオーバーラップした画像の分割に関する。オーバーラップした画像は、画像データが伝送（ダウンロード）される場合に、これら画像の可視部分のみがダウンロードされるように分割される。不可視部分は、帯域幅を節約するために伝送されない。
【背景技術】
【０００２】
ユーザが標準的なブラウザを用いてインターネットを介し名刺及びグリーティング・カード等のグラフィックスを作成及び編集することができるようにするような種々のオンライン・ユーティリティが存在する。これらユーティリティの多くは、ユーザが上記グリーティング・カード又は名刺に１以上の画像を追加するのを可能にする。ユーザは、これら画像を移動させたり、大きさを変えたり、回転させたり等をすることができる。
【０００３】
斯かる操作処理中に、ユーザは典型的にはサムネールの大きさの画像のみを扱う。これは、クライアント・マシンへの負担を最小化する。これは、ダウンロード時間も最小化する。原寸大画像のダウンロードは、ユーザが印刷の準備を整えるまで、遅らせることができる。このようにして、ユーザが何れの画像を使用したいかについて気が変わる場合にも、原寸大の画像をダウンロードして時間が浪費されることがない。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
或る場合には、ユーザが、グラフィックス文書に、幾つかのものが部分的にオーバーラップするような複数の画像を組み込みたいと欲する場合がある。オーバーラップの何れの領域においても、一番上の画像の対応する部分のみしか見ることができず、当該重なり（スタック）における、それより下の各画像の対応する部分は遮られる。現状の技術においては、ユーザが画像をダウンロードしようと欲する場合、見えないであろう画像部分のデータであっても、全ての画像データがダウンロードされる。これは時間が掛かり、不必要なことである。
【０００５】
本発明の１つの目的は、オーバーラップした画像の従来の処理の上述した問題点及び欠点を克服することにある。
【０００６】
また、本発明の他の目的は、伝送効率及び処理効率を改善するために一連のオーバーラップした画像を分割するシステムを提供することにある。
【０００７】
また、本発明の更なる目的は、一連のオーバーラップした画像を、これら画像のうちの可視部分のみが伝送されるように分割するシステムを提供することにある。
【０００８】
また、本発明の更に他の目的は、圧縮されたドメインにある一連のオーバーラップした画像を分割すると共に、分割された領域から圧縮されたデータのみを伝送するようなシステムを提供することにある。
【課題を解決するための手段】
【０００９】
本発明の１つの特徴によれば、第１の一番下の画像と、該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像とを少なくとも含む一群の画像を分割する方法が提供される。該方法は、第１の画像の非オーバーラップ部分を第２の画像の位置に基づき少なくとも２つの区域に分割して、画像要素の第１集合を形成するステップと、該第１集合の画像要素のみを伝送するステップとを有する。
【００１０】
必要なら、上記第１集合の画像要素における部分的にオーバーラップした各画像要素の非オーバーラップ部分は、好ましくは、第２の分割段階において前記画像の群における第１集合の画像要素と部分的にオーバーラップする第３の画像の位置に基づき少なくとも２つの区域に更に分割される。この第２の段階の分割の結果、画像要素の第２集合が形成される。この場合、前記第１及び第２集合の画像要素のみが伝送される。
【００１１】
本発明の他の特徴においては、少なくとも幾つかが部分的にオーバーラップすると共に、第１の一番下の画像と最後の一番上の画像とを含む一群の画像を分割する方法が提供される。該方法は、第１の画像の非オーバーラップ部分を該第１の画像の手前の且つ該第１の画像と部分的にオーバーラップする第２の画像の位置に基づき複数の長方形に分割して長方形の第１集合を形成するステップと、上記一番上の画像の位置に基づいて長方形の最終的集合が形成されるまで現集合の長方形を前記画像の群における次の画像に基づいて分割することにより長方形の新たな集合を反復的に形成するステップと、上記最終的集合の長方形のみを伝送するステップとを有する。好ましくは、上記第１集合の長方形は第２の画像を含み、長方形の各更なる集合は、該更なる集合に対する分割が基づいた画像を含むものとする。
【００１２】
好ましくは、前記第１集合の画像要素は第２の画像を含み、前記第２集合の画像要素は第３の画像を含むようにする。
【００１３】
また、好ましくは、前記各区域及び画像要素は長方形の形状であるものとする。
【００１４】
また、好ましくは、前記分割は部分的に圧縮されたドメインで実行されるものとする。
【００１５】
本発明の他の特徴によれば、上述した方法（又は複数の方法）により一連の画像を分割する装置が提供される。該装置は、デジタルコンピュータ、他のプロセッサにより制御される装置又は等価のものとすることができる。
【００１６】
本発明の更に他の特徴においては、上述した方法（又は複数の方法）は、デジタルコンピュータ又は他のプロセッサにより制御される装置により読み取り可能な記録媒体上に記憶される命令のプログラムとして具現化することができる。他の例として、上記方法（又は複数の方法）は、ハードウェアを用いて、又はソフトウェアとハードウェアとの組み合わせを用いて実施化することができる。
【００１７】
本発明の他の目的及び達成事項並びに本発明の完全な理解は、下記の説明及び請求項を添付図面と共に参照することにより明らかとなり且つ理解されるであろう。
【００１８】
尚、添付図面において対応する各部分には同様の符号が付してある。
【発明を実施するための最良の形態】
【００１９】
本発明の画像分割技術の場合、ユーザは、幾つか又は全てが部分的にオーバーラップしているような複数の画像を用いて作業しており、且つ、その画像データが伝送されねばならないようなグラフィックス又は画像処理アプリケーションと共に使用することができる。斯様なアプリケーションとしては、例えば、ユーザが名刺又はグリーティング・カードを作成するのを可能にするようなプログラムを含めることができる。本発明の技術は、上記複数の画像を、これら画像のうちの可視部分のみが伝送されるように分割することにより、伝送及び処理効率を改善する。このように、本発明は、ユーザがネットワークを介してサーバと対話しているクライアント・コンピュータ上で作業しているようなオンライン・グラフィックス又は画像処理アプリケーションと関連させると特に有用である。
【００２０】
図１はネットワークの概念図である。図示を容易にするため、１つのクライアントと１つのサーバのみが示されているが、当業者にとっては、該ネットワークが複数のクライアント及びサーバを含んでもよい（典型的には、そうである）ことは明らかである。ネットワーク・クライアント１１は、ネットワーク・サーバ１２により提供される資源にアクセスするためにネットワーク１３を使用する。ネットワーク・サーバ１２は、多分ハイパーテキスト伝送プロトコル（ＨＴＴＰ）に準拠して動作するハイパーメディア・サーバであることを意図するが、これは本発明を実施するためには必要ではない。ネットワーク・クライアント１１とネットワーク・サーバ１２とを接続する通信経路の性質は、本発明の実施に対しては臨界的なものではない。斯様な経路は、専用及び／又は公衆施設を用いたスイッチされる及び／又はスイッチされない経路として構成することができる。同様に、ネットワーク１３のトポロジも臨界的なものではなく、階層ネットワーク及びピアツーピア・ネットワークを含む種々の方法で構成することができる。ネットワーク・クライアント１１及びネットワーク・サーバ１２は、例えば、互いに局部的に配置されることができ、同一のハードウェア上で実施化することができる。
【００２１】
図２は、ネットワーク・クライアント１１及び／又はネットワーク・サーバ１２を実施化するのに使用することができる典型的なコンピュータシステム２０の機能ブロック図である。図示のように、このコンピュータシステムは、中央処理装置（ＣＰＵ）２２、システム・メモリ２３及び幾つかの装置インターフェースを相互接続するバス２１を含んでいる。バス２１は、システム・バス及びプロセッサの局部バスのような１以上の物理的バスにより構成することができる。ＣＰＵ２２は、マイクロプロセッサのような処理回路を表している。システム・メモリ２３は、ランダムアクセスメモリ（ＲＡＭ）及び読出専用メモリ（ＲＯＭ）のような種々のメモリ構成要素を表している。入力制御部２５は、キーボード、マウス、トラック・ボール又は探針のような１以上の入力装置３５に接続するインターフェース回路を表している。表示制御部２６は、ビデオ表示端末のような１以上の表示装置３６に接続するインターフェース回路を表している。Ｉ／Ｏ制御部２７は、モデム又はネットワーク接続部のような１以上のＩ／Ｏ装置３７に接続するインターフェース回路を表している。記憶制御部２８は、磁気ディスクドライブ、磁気テープドライブ、光ディスクドライブ又は固体記憶装置のような１以上の記憶装置３８に接続するインターフェース回路を表している。プリンタ制御部２９は、レーザプリンタ、インクジェットプリンタ又はプロッタ等の１以上のプリンタ装置３９に接続するインターフェース回路を表している。特別な型式のコンピュータが本発明を実施するのに臨界的となることはない。例えば、図２に示すものとは異なるバスアーキテクチャを備えるコンピュータを使用することもできる。
【００２２】
好ましい実施例においては、コンピュータシステム２０は本発明の画像分割技術を、ＲＯＭ、記憶装置３８から取り込むことができる又はネットワーク・サーバから若しくはＩ／Ｏ装置３７を介して他の資源から得ることができるＲＡＭ内の命令のプログラムをＣＰＵ２２を用いて実行することにより実施する。該命令のプログラム（即ち、ソフトウェア）は、ディスク又はテープのような種々の磁気媒体、コンパクトディスクのような種々の光媒体、及び超音波から紫外周波数までの電磁スペクトルにわたる光、赤外線及びベースバンド若しくは変調された通信経路を含むような、コンピュータ又は他のプロセッサにより制御される装置によって読み取ることが可能な記録媒体により伝送することができる。このように、請求項において用いられた“装置により読み取り可能な記録媒体”なる用語は、上記プログラムの命令を伝送するために符号化された搬送波を含む全ての斯様な媒体を包含することを意図するものである。
【００２３】
他の例として、本発明の画像分割技術は、個別部品、用途固有の集積回路（ASIC）、デジタル信号プロセッサ等を用いてハードウェアにより実施化することもできる。斯様なハードウェアは、例えば、ＣＰＵ２２と物理的に一体化される（図３の（Ａ）参照）か、又は別の構成要素とすることが可能な画像プロセッサ４０において具現化することができる。該画像プロセッサ４０が別の構成要素である場合は、該プロセッサはコンピュータ２０自体（図３の（Ｂ）参照）において又は利用可能なカードスロット４２に挿入することが可能なオプションカード４１（図３の（Ｃ）参照）上で具現化することができる。
【００２４】
本画像分割技術はソフトウェアとハードウェアとの組み合わせを用いて実施化することもできる。基礎となる分割アルゴリズムの種々の特徴はハードウェアで実施化することができる一方、他のものはソフトウェアを使用して実施化される。
【００２５】
このように、請求項における各“〜する手段”なる句は、記載された機能を実施化するための適切なプログラム部分（又は複数の部分）又は機能的に等価なハードウェア装置（又は複数の装置）を含むことを意図するものである。
【００２６】
本発明の基礎となる画像分割アルゴリズムに関しては、一連のオーバーラップした画像は、これら画像のうちの可視部分のみが伝送（即ち、ダウンロード）されるように、小さな断片に分割される。コンピュータのようなデジタル装置は典型的には長方形の形状の図形でもって動作するので、該分割は、好ましくは、長方形を用いて実施される。帯域幅の消費を更に低減させると共に処理効率を更に改善するために、該分割は好ましくは当該画像が部分的に圧縮された（即ち、周波数の）ドメインにある間になされ、その後、分割された領域内のみの圧縮された（即ち、ビットストリームの）データが伝送される。
【００２７】
しかしながら、本発明は如何なる特別な分割手順にも限定されるものではないことに注意すべきである。むしろ、画像データの実際の分割を実施するには、如何なる既知の空間ドメイン又は周波数ドメインの切り取り（cropping）手順も使用することができる。しかしながら、好ましい実施例においては、上記分割は周波数ドメインの切り取り手順を用いて実施され、その後、分割された領域内のみの圧縮されたデータが伝送される。ＪＰＥＧ画像の場合は、画像データは、好ましくは、周波数の又は部分的に圧縮されたドメインにおいてＪＰＥＧ切り取り手順を用いて実施される。
【００２８】
図４は、本発明の反復画像分割アルゴリズムの処理を図示するフローチャートである。該アルゴリズムはステップ４１において開始し、該ステップにおいては、オーバーラップした長方形画像の積み重なり（スタック）における各画像に、当該スタックにおける順番を表す個別のｚ軸順序番号を用いてラベルが付される。例えば、該ｚ軸順序番号は、最小の数（即ち、０）が当該スタックにおける一番下の画像を表し、最大の数（即ち、ｎ−１）が当該スタックにおける一番上の画像を表すように連続的に割り当てることができ、ここで当該スタックにおける画像の数はｎに等しい。この番号付け方法によれば、一層大きなｚ軸順序番号は、通常、一層手前の画像を示す。しかしながら、２つの画像が、直ぐ下の画像とは各々オーバーラップするが、互いにはオーバーラップしないような状況が存在し得る。そのような場合には、一方が他方よりも大きなｚ軸順序番号を有するであろうが、これら２つの画像の何れも他方に対して一層手前にあるというのではないであろう。
【００２９】
各段階において、当該アルゴリズムは、可視長方形の現集合を保持し、該現集合はステップ４２において一番下の画像（ｚ軸順序＝０）を含むように初期化される。この現集合の可視長方形は、本アルゴリズムの心臓部において、次のｚ軸順序の画像により反復的に分割される。この次のｚ軸順序は増加する変数ｉにより示され、該変数はステップ４３において１に初期化される。
【００３０】
次ぎに、現集合の長方形は、ｉなるｚ軸順序を持つ画像と比較され、オーバーラップの領域を判定する。オーバーラップの領域を判定した後、現在の可視集合における全ての長方形の非オーバーラップ部分を分割して、長方形の次の集合を形成する。ｉなるｚ軸順序番号の当該画像も、この集合に追加され、この集合が次の反復のための可視長方形の現集合となるが、該次の反復のためにｉはｉ＋１に増加される。この処理は、全ての画像が考察されるまで、ｚ軸順序における次の画像を、前に生成された（即ち、“現”）可視長方形の集合と比較し、可視長方形の“新たな”集合を生成するようにして継続する。最後の（即ち、一番上の）画像が考察され、最終的分割が完了した後、長方形の最終的集合が生成されるが、該集合は当該画像スタックの可視部分のみを表す。
【００３１】
このように、ステップ４４は、現集合の可視長方形をｉなるｚ軸順序を持つ長方形（即ち、当該スタックにおける次ぎの一番手前の画像）と比較してオーバーラップの領域を判定するものとして概略説明することができる。最初の比較においては、可視長方形の現集合は一番下の画像のみからなっている。一層概略的に説明されたステップ４５は、現集合の可視長方形における部分的にオーバーラップした各長方形の非オーバーラップ部分を分割して、ｉなるｚ軸順序の画像も含む可視長方形の次の集合を形成する処理を含む。
【００３２】
分割の各段階の後、本アルゴリズムは当該分割処理において上記スタック内の全ての画像が考察されたか否かを判断する（ステップ４６）。上記スタック内の全ての画像が考察されていない場合には、ｉがステップ４７において１だけ増加され、当該アルゴリズムはステップ４４に戻って、当該スタックにおける次の最も手前の画像を“現”集合の可視長方形と比較する。該処理は全ての画像／長方形が考察され、分割が完了するまで継続し、完了すると、可視長方形の最終的集合の更なる処理がステップ４８においてなされる。斯かる更なる処理は、例えば、同一の画像に属する隣接する長方形を、そうすることが効率的なら、大きな長方形に統合するような処理を含むことができる。
【００３３】
その後、ステップ４９において、帯域幅を節約し且つ処理効率を改善するために、当該画像のスタックの可視部分のみを表す上記最終的集合の長方形のデータのみが伝送される。前述したように、本分割は好ましくは、当該画像が部分的に圧縮された（即ち、周波数の）ドメインにある間に実行される。このように、好ましい実施例においては、長方形の最終的な集合が生成された後、当該アルゴリズムは上記最終的な集合の長方形により表される切り取られた（即ち、分割された）領域から、圧縮されたデータを取り出す。次いで、該アルゴリズムは、このデータを圧縮された形態で送出する。上記分割を部分的に圧縮されたドメインで実施すると共に、伝送を圧縮されたドメインで実施する結果、帯域幅の付加的な減少及び処理効率の更なる改善が得られる。
【００３４】
オーバーラップした画像の或る集合において、各レベルの分割は、“現”集合の可視長方形を当該スタックにおける次ぎに大きなｚ軸順序を持つ長方形／画像に対してのみ考察する。可視長方形の“現”集合における部分的にオーバーラップした各長方形は、ｚ軸順序ｉを持つ長方形／画像に基づいて一層小さな長方形に分割されて、該ｚ軸順序ｉにより指定される長方形を含むような“新たな”集合の可視長方形を生成する。この“新たな”集合の長方形（ここでは、“現”集合の長方形となる）は、次いで、当該スタックにおける次の長方形／画像と比較される。そして、該“現”集合における部分的にオーバーラップした各長方形の非オーバーラップ部分の更なる分割が、長方形の“新たな”集合を生成する。
【００３５】
“現”集合における“以前の”長方形は、“新たな”長方形が該“以前の”長方形の手前側にあり、且つ、上記“新たな”長方形が該“以前の”長方形と部分的にオーバーラップする場合にのみ、分割する。上記“以前の”長方形は、以前の分割の結果であったかも知れない。本アルゴリズムは、好ましくは、“以前の”長方形の分割に関する決定を逆転することはない。“以前の”長方形が分割されるべき場合は、計算の観点からは、該“以前の”長方形を、結果としての小さな長方形がほぼ等しい面積のものとなるように分割するのが有利である。
【００３６】
前述したように、コンピュータは典型的には画像を長方形で扱うので、長方形は好ましい分割形状である。このように、好ましい実施例においては、長方形は、それらの辺がランダムな線分となるような不規則な多角形断片には分割されない。むしろ、分割された断片の辺は水平又は垂直の何れかとする。長方形Ａ及びＢが与えられ、ＡがＢの手前にある場合、長方形Ｂが分割される断片は、Ａ及び／又はＢの辺の幾つかと整列された辺を有するであろう。また、本アルゴリズムは、長方形が回転されないと仮定している。
【００３７】
図５ないし図２１に図示したように、２つの長方形Ａ及びＢを互いに配置することが可能な１７通りの方法がある。上記２つの長方形がオーバーラップする各ケースにおいて、上側の長方形には陰影が付けられている。本アルゴリズムは、分割の決定を行う際に、これらケースの各々を別々に扱う。これらのケースの幾つかは、類似している（唯一の相違点は、それらが９０度の倍数で回転されている点である）。ケース１及び２（各々、図５及び図６）においては、分割する非オーバーラップ部分が存在しないので、一番下の長方形Ｂは分割されない。ケース１においては交差は存在せず、ケース２の場合は下側の長方形は上側の長方形により完全に覆われている。残りのケース３ないし１７の各々においては、下側の長方形は図７ないし図２１に示すように分割される。上側の長方形が、下側の長方形が２以上の新たな長方形（図７ないし図１１、及び図１６ないし図１９）に分割されるように配置されている場合に関しては、当該分割を示すために破線が付加されている。
【００３８】
Ｎ個の画像の集合が与えられると、この方法は完了するのにＯ(N2)までの演算が掛かる可能性がある。更に、長方形の数はＯ(N2)なる理論上の上限と共に増加し、ここでＮは画像の数、Ｏは計算量理論で使用される標準表記である。斯様な状況は実際には起こりそうもないが、過度に大きな数の長方形を生成するのを防止するために、当該アルゴリズムは好ましくは、一旦長方形の最大数、例えば１００、を越えた場合には、分割を停止するように設計される。事前設定された最大値に一旦到達したら、当該アルゴリズムは分割を停止し、何らかの最終的処理を実行し、次いでデータをそのまま送出する。即ち、それ以上のｚ軸順序の画像は全て、可視長方形の現（この場合は最後の）集合と共に送出される。
【００３９】
上記説明が示すように、本発明の画像分割技術は、ユーザが複数のオーバーラップした画像を用いて作業するオンライン・グラフィックス・アプリケーションに関連した使用に特に適している。前記分割アルゴリズムは、ソフトウェア、ハードウェア又はそれらの組み合わせを用いて実施化することができる。これを心に留めて、本発明の技術を解説するために使用されたブロック図及びフローチャートは、或る特定の性能及びそれらの関係の働きを示すものであると理解されたい。これらの機能ブロックの境界は、ここでは説明の便宜上任意に規定されている。上記特定の機能が果たされ、且つ、これら機能の間の関係が維持される限り、他の境界を規定することもできる。上記図及びそれに付随する説明は、当業者が上記所要の処理を実行するためにシステムを構成するのに必要とするであろう機能上の情報を提供するものである。ブロック図及びフローチャートに示された機能の各々は、例えば、ソフトウェア、機能的に等価なハードウェア又はそれらの組み合わせにより実施化することができる。
【００４０】
本発明の実施例を上述したが、当業者にとっては、上記説明に照らして多くの他の代替え例、修正例及び変形例が明らかとなるであろう。ここで述べた発明は、添付請求項の趣旨及び範囲内に入るであろう全ての斯様な代替え例、修正例、適用例及び変形例を含もうとするものである。
【００４１】
以上説明したように、本発明による一連のオーバーラップした画像を分割する方法及び装置等によれば、伝送効率及び処理効率が大幅に改善される。
【図面の簡単な説明】
【００４２】
【図１】ネットワーク・クライアントとネットワーク・サーバとを相互接続するネットワークの概念図である。
【００４３】
【図２】本発明の種々の特徴を実施化するためにネットワーク・クライアント又はネットワーク・サーバとして使用することができる典型的なコンピュータの機能ブロック図である。
【００４４】
【図３】（Ａ）（Ｂ）及び（Ｃ）は、本発明の画像分割技術の全て又は一部の種々の実施化法を示す図である。
【００４５】
【図４】本発明の画像分割アルゴリズムの処理を図示するフローチャートである。
【００４６】
【図５】２つの長方形／画像を相互に配置することができる、可能性のある態様を示す図である。
【００４７】
【図６】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００４８】
【図７】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００４９】
【図８】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５０】
【図９】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５１】
【図１０】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５２】
【図１１】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５３】
【図１２】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５４】
【図１３】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５５】
【図１４】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５６】
【図１５】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５７】
【図１６】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５８】
【図１７】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００５９】
【図１８】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００６０】
【図１９】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００６１】
【図２０】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【００６２】
【図２１】２つの長方形／画像を相互に配置することができる、可能性のある他の態様を示す図である。
【符号の説明】
【００６３】
１１…ネットワーク・クライアント
１２…ネットワーク・サーバ
１３…ネットワーク
２０…コンピュータシステム
２１…バス
２２…ＣＰＵ
２３…メモリ
４０…画像プロセッサ
【図１】
2004159365.tif 000003
【図２】
2004159365.tif 000004
【図３】
2004159365.tif 000005
【図４】
2004159365.tif 000006
【図５】
2004159365.tif 000007
【図６】
2004159365.tif 000008
【図７】
2004159365.tif 000009
【図８】
2004159365.tif 000010
【図９】
2004159365.tif 000011
【図１０】
2004159365.tif 000012
【図１１】
2004159365.tif 000013
【図１２】
2004159365.tif 000014
【図１３】
2004159365.tif 000015
【図１４】
2004159365.tif 000016
【図１５】
2004159365.tif 000017
【図１６】
2004159365.tif 000018
【図１７】
2004159365.tif 000019
【図１８】
2004159365.tif 000020
【図１９】
2004159365.tif 000021
【図２０】
2004159365.tif 000022
【図２１】
2004159365.tif 000023