(57)【特許請求の範囲】
【請求項１】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データに所定の処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、処理が依頼された画像データの一部を複製し、複製した画像データの画像処理要求を出力する副画像処理依頼手段と、処理が依頼された画像データに対して所定の処理を行う副画像処理実行手段と、を有する少なくとも１つの副画像処理装置と、を有し、
前記主画像処理装置及び前記副画像処理装置は、それぞれ、前記処理対象画像データを受け取って処理を開始する処理開始時刻から処理結果を返す処理終了時刻までの経過時間が所定の最大処理時間に達するかどうかを管理する時間管理手段を有し、前記時間管理手段で経過時間が所定の最大処理時間を超える前に、前記副画像処理実行手段が処理結果を処理済画像データとして前記主画像処理実行手段に転送し、前記主画像処理実行手段が合成された処理済画像データを画像処理結果データとして出力することを特徴とする画像処理システム。
【請求項２】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データが入力された時から所定の時間が経過するまで前記処理対象画像データに所定の処理を行うとともに、前記処理対象画像データが入力された時から前記所定の時間が経過すると、それまでに受け取った処理済画像データと自己の処理した処理済画像データとを合成し、合成された処理済画像データを画像処理結果データとして出力する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、処理が依頼された画像データの一部を複製し、複製した画像データの画像処理要求を出力する副画像処理依頼手段と、処理が依頼された画像データに対して所定の処理を行い、処理済画像データとして前記主画像処理実行手段に転送する副画像処理実行手段と、を有する複数の副画像処理装置と、
を有することを特徴とする画像処理システム。
【請求項３】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データに所定の処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成し、所定のタイミングで画像処理結果データとして出力する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、処理が依頼された画像データの一部を複製し、複製した画像データの画像処理要求を出力する副画像処理依頼手段と、前記処理対象画像データが入力された時から所定の時間が経過するまで処理が依頼された画像データに対して所定の処理を行い、前記処理対象画像データが入力された時から前記所定の時間が経過すると、その時点で処理されている画像データを、処理済画像データとして前記主画像処理実行手段に転送する副画像処理実行手段と、を有する複数の副画像処理装置と、
を有することを特徴とする画像処理システム。
【請求項４】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの前半部分の複製又は後半部分の複製を生成し、前半部分の画像データの画像処理要求又は後半部分の画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データに所定の処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成し、所定のタイミングで画像処理結果データとして出力する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、処理が依頼された画像データの前半部分の複製又は後半部分の複製を生成し、前半部分の画像データの画像処理要求又は後半部分の画像データの画像処理要求を出力する副画像処理依頼手段と、処理が依頼された画像データに対して所定の処理を行い、処理済画像データとして前記主画像処理実行手段に転送する副画像処理実行手段と、を有する複数の副画像処理装置と、
を有することを特徴とする画像処理システム。
【請求項５】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データのうち、前記主画像処理依頼手段により複製されていない部分から画像処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成し、所定のタイミングで画像処理結果データとして出力する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、処理が依頼された画像データの一部を複製し、複製した画像データの画像処理要求を出力する副画像処理依頼手段と、処理が依頼された画像データのうち、前記副画像処理依頼手段により複製されていない部分の画像処理を行い、処理済画像データとして前記主画像処理実行手段に転送する副画像処理実行手段と、を有する複数の副画像処理装置と、
を有することを特徴とする画像処理システム。
【請求項６】
前記主画像処理依頼手段は、前記処理対象画像データのうち、詳細な画像データが含まれる部分の複製を生成し、複製した画像データの画像処理要求を出力し、
前記副画像処理依頼手段は、処理が依頼された画像データのうち、詳細な画像データが含まれる部分の複製を生成し、複製した画像データの画像処理要求を出力する、
ことを特徴とする請求項５記載の画像処理システム。
【請求項７】
画像データを分散して処理する画像処理システムにおいて、
入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データに所定の処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成し、所定のタイミングで画像処理結果データとして出力する主画像処理実行手段と、を有する主画像処理装置と、
画像処理要求を受け取ると、所定の時間間隔で、処理が依頼された画像データのうちの未処理の部分の一部を複製し、複製した画像データの画像処理要求を繰り返し出力する副画像処理依頼手段と、処理が依頼された画像データに対して所定の処理を行い、処理済画像データとして前記主画像処理実行手段に転送する副画像処理実行手段と、を有する複数の副画像処理装置と、
を有することを特徴とする画像処理システム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像データを処理する画像処理システムに関し、特に画像データを分散して処理する画像処理システムに関する。
【０００２】
【従来の技術】
一般に画像データは、文字データや音声データに比べてデータ量が極めて多く、利用者が処理を要求してからその結果を受け取るまでの処理時間が長くなる傾向にある。フィルタリングなどの画像処理の種類によっては利用者が期待する時間以内に画像処理の結果を得ることができない場合もあった。そこで、処理すべき画像データを複数の計算機を使用して分散処理を行うことによる処理の高速化が検討されている。単一の計算機を使用して処理した場合よりも、処理を分散化した場合の方が、利用者が処理を要求してからその結果を受け取るまでの処理時間が短くなるからである。
【０００３】
例えば、「分散処理環境におけるＣＧシステムの構築」（情報処理学会第４３回全国大会論文集，５Ｕ−１０，２−５１７ページ）では、レイトレーシング法などを利用したソフトウェア・レンダラにより高品位なコンピュータ・グラフィックス画像を生成しようとすると、数時間の時間がかかってしまうことが指摘されている。そこで、ネットワーク上に分散した複数台の計算機に処理を最適に分散し、並列処理させることによって、処理に要する時間を短縮しようとしている。
【０００４】
「クライアント／サーバ型情報処理環境におけるレイトレーシング法による画像生成のモデル化」（情報処理学会第４７回全国大会論文集，７Ｅ−３，１−２２３ページ）によれば、レイトレーシング法による作画は画像データの画素個々を独立に計算しているため一つの画像を分割することが容易であることから、クライアント・サーバ・モデルに基づいてレイトレーシング法による作画処理を分散して並列に行う技術についての研究が行われている。つまり、膨大な処理時間を要するレイトレーシング法による画像生成による時間の短縮を、クライアント・サーバ・モデルに基づき、分散し並列処理することによって、短縮することを試みている。
【０００５】
このような分散処理の実現には、負荷分散の最適化を図る必要がある。そこで、分散処理における負荷分散を最適化するために、一般的にスケジューリングが行われている。そのため、スケジューリング管理を行うためのプロセッサ又はスケジューラなどスケジューリングを行うための機構が特別に必要とされていた。ここで、スケジューリングとは各計算機の負荷を最適にすることである。つまり、最も短時間に利用者が期待する画像処理の結果が得られるように、画像処理を分散させることである。なお、一般的な分散処理システムにおいては各計算機における負荷が最適かどうかは、その計算の目的によって様々であり、例えば使用するメモリ量を小さくすることなどもその一つである。また、平均的に負荷を分散させることが最適化の一つの方法である。
【０００６】
例えば、「情報処理システム」（特開平５−８１１６３号公報）では、通信ネットワーク上のサーバに要求されたサーバ処理をスレッドと呼ばれる実行単位を用いて並列に実行して処理効率を上げようとしている。そのために、このシステムでは、通信ネットワークに分散した複数のコンピュータ上にサービスを要求するクライアント、および複数の種類のサービス要求に対して該当するサービスを選択し実行するサーバを備えている。そして、このサーバにはそれぞれが並列実行することができる四つのスレッドを含んでいる。第１のスレッドはサービス要求の受付を行い、第２のスレッドはサービスを実行し、第３のスレッドはそのサービスの結果の発信（応答）を行い、第４のスレッドは前記三つの各スレッドの実行を制御するとともに、並列実行のためのスケジューリングを行う。
【０００７】
【発明が解決しようとする課題】
しかし、スケジューリングに要する計算量は膨大であり、その計算には非常に長い時間が必要である。
【０００８】
例えば、「 タスク・ブローカ」という方式がある。この方式では、「アンフィニティ」という選択基準を用いて、処理を行わせるのに最適なマシンを選択する。「アンフィニティ」は、ユーザが直接数値を設定するか、あるいはユーザが記述したプログラムにより生成される。この方式では、最適な計算機を選ぼうとしているが、アプリケーション実行時のＣＰＵ負荷及びメモリ使用量並びに計算機のメモリ使用量及びＣＰＵ負荷など様々な要素の兼ね合いから値を決定することは容易ではない。
【０００９】
また、「スケジューリング装置」（特開平５−１６５３９７号公報）では、スケジューリング問題の本質は組み合わせ問題であり、考慮すべき資源（ここでは、例えばＣＰＵ負荷又はメモリ使用量など）の種類等が増えると問題が複雑になることに着目して、スケジューリングに要する時間の短縮を図っている。即ち、このスケジューリング装置では、冗長制約除去部によって、複数の処理タスク相互の先行制約関係の中から、他の複数のタスク間制約関係の組み合わせ代替表現が可能なタスク間制約関係を冗長なタスク間制約関係として検出し除去する。これにより、先行制約関係を持った複数の処理タスクに資源割当を決定する処理の時間を短縮できる。
【００１０】
このように、スケジューリングを短時間で行うための様々な方式が考えられているが、依然としてスケジューリングに多くの時間を必要とすることには変わりはない。
【００１１】
しかも、画像処理によってはある制限時間内又は一定時間内に処理した結果を必要とする処理があり、この場合には、所定の時間以内に必ず画像処理を終了させなければならない。例えば、リアルタイム・アニメーションはその一つの例である。つまり、リアルタイム・アニメーションにおいては均一なフレーム速度で画像を表示することが必要である。一般に静止画像を単純に連続して生成するリアルタイム・アニメーション・システムでは、光景（シーン）の複雑さによってフレーム速度が変動してしまう。そこで、リアルタイム・アニメーションでは、極力画質は高く維持し、さらに指定された目標フレーム時間内に各フレームの静止画像を生成する必要がある。
【００１２】
本発明はこのような点に鑑みてなされたものであり、スケジューリングのような複雑な処理を行わずに、画像データの分散処理を行う画像処理システムを提供することを目的とする。
【００１３】
また、本発明の他の目的は、利用者が所望する時間内に処理した画像の結果を戻すことを可能とする画像処理システムを提供することである。
【００１４】
【課題を解決するための手段】
本発明では上記課題を解決するために、画像データを分散して処理する画像処理システムにおいて、入力された処理対象画像データの一部を複製し、複製した画像データの画像処理要求を出力する主画像処理依頼手段と、前記処理対象画像データに所定の処理を行うとともに、処理済画像データを受け取ると、受け取った処理済画像データと自己の処理した処理済画像データとを合成する主画像処理実行手段と、を有する主画像処理装置と、画像処理要求を受け取ると、処理が依頼された画像データの一部を複製し、複製した画像データの画像処理要求を出力する副画像処理依頼手段と、処理が依頼された画像データに対して所定の処理を行う副画像処理実行手段と、を有する少なくとも１つの副画像処理装置と、を有し、前記主画像処理装置及び前記副画像処理装置は、それぞれ、前記処理対象画像データを受け取って処理を開始する処理開始時刻から処理結果を返す処理終了時刻までの経過時間が所定の最大処理時間に達するかどうかを管理する時間管理手段を有し、前記時間管理手段で経過時間が所定の最大処理時間を超える前に、前記副画像処理実行手段が処理結果を処理済画像データとして前記主画像処理実行手段に転送し、前記主画像処理実行手段が合成された処理済画像データを画像処理結果データとして出力することを特徴とする画像処理システムが提供される。
【００１５】
このような画像処理システムによれば、処理対象画像データが主画像処理装置に入力されると、主画像処理依頼手段により、処理対象画像データの一部が複製され、画像処理要求が出力される。その画像処理要求を副画像処理装置が受け取ると、副画像処理依頼手段により、処理が依頼された画像データの一部が複製され、画像処理要求が出力される。そして、主画像処理実行手段は処理対象画像データの処理を行い、副画像処理実行手段は処理が依頼された画像データの処理を行う。副画像処理実行手段が処理した処理済画像データは主画像処理実行手段に転送され、主画像処理実行手段の処理した画像データと合成され、その後、所定のタイミングで画像処理結果データとして出力される。
【００１６】
これにより、スケジューリング管理のための機構を用いることなく画像データの分散処理を行うことができる。
【００１７】
【発明の実施の形態】
以下、本発明の実施の形態を図面を参照して説明する。
図１は本発明の原理構成図である。本発明の画像処理システムは、一つの主画像処理装置１と、複数の副画像処理装置２，３とで構成されている。
【００１８】
主画像処理装置１内には、主画像処理依頼手段１ａと主画像処理実行手段１ｂとが設けられている。主画像処理依頼手段１ａは、処理対象画像データ４が入力されると、処理対象画像データ４の一部を複製し、それを画像処理要求とともに出力する。主画像処理実行手段１ｂは、処理対象画像データ４の処理を実行するとともに、副画像処理装置からの処理済画像データを受け取ると、自己の処理した画像データと合成する。そして、主画像処理実行手段１ｂは、全ての処理対象画像データ４の処理が終了するか、あるいは所定の制限時間に達したら、画像処理結果データ５を出力する。
【００１９】
副画像処理装置２，３には、それぞれ副画像処理依頼手段２ａ，３ａと副画像処理実行手段２ｂ，３ｂとが設けられている。副画像処理依頼手段２ａ，３ａは、画像処理要求を受け取る。画像処理要求を受けとった副画像処理依頼手段２ａ，３ａは、画像処理要求とともに受け取った画像データの一部を複製し、それを画像処理要求とともに出力する。副画像処理実行手段２ｂ，３ｂは、画像処理要求とともに受け取った画像データの処理を実行する。そして、副画像処理実行手段２ｂ，３ｂは、画像データの処理が終了するか、あるいは所定の制限時間に達したら、処理後の画像データを主画像処理装置１へ送信する。
【００２０】
このような画像処理システムによれば、ユーザが、処理対象画像データ４を主画像処理装置１に入力すると、主画像処理依頼手段１ａにより、処理対象画像データの一部が副画像処理装置２，３のいずれかに渡される。画像データを受けとった副画像処理装置内の副画像処理依頼手段は、さらに画像データの一部を複製し、それを他の副画像処理装置に渡す。これにより、画像データは、次々と複製される。そして、主画像処理装置１と副画像処理装置２，３は、自己が受け取った画像データを処理する。そして、処理が終了するか、あるいは画像処理開始から所定の時間が経過すると、処理済画像データが副画像処理装置２，３から主画像処理装置１に渡される。主画像処理装置１の主画像処理実行手段１ｂは、副画像処理装置２，３から受け取った処理済画像データと、自己が処理した画像データとを合成し、画像処理結果データ５として出力する。
【００２１】
このようにして、スケジューリングを行わずに、複数の装置で分散して画像処理を行うことができる。しかも、画像処理結果データ５は、常に所定の時間内に出力される。
【００２２】
ところで、以上のような画像処理システムは、ネットワークを介して接続された複数の計算機により実現することができる。そこで、ＬＡＮ（ローカル・エリア・ネットワーク）を介して接続された複数台の計算機による本発明を実施の形態を以下に説明する。
【００２３】
図２は本発明の第１の実施の形態の概略構成を示す図である。図に示すように、ネットワーク１１を介して複数の計算機１００，２００，３００が接続されている。ここで、計算機１００内に生成されるプロセスが図１に示す主画像処理装置１となり、計算機２００，３００内に生成されるプロセスが図１に示す副画像処理装置２，３となる。
【００２４】
そして、ネットワーク１１によって接続された複数の計算機において生成されるプロセスを、処理すべき画像処理の実行を担うという意味でサーバと呼ぶことにする。各サーバには各々を識別するために識別番号が付けられる。これをサーバＩＤと呼ぶことにする。サーバＩＤはネットワーク１１によって接続された複数の計算機において一意に決められ、０から始まるものとする。各サーバにサーバＩＤを付加して、例えば、サーバ０号、サーバｎ号などと呼ぶことにする。ここで、ｎはサーバＩＤである。
【００２５】
さらに、サーバの計算機上の生存時間、つまりサーバが生成されてから消滅するまでの時間をライフ・タイムと呼ぶことにする。
図３はサーバの内部構成を示すブロック図である。各計算機１００，２００には、サーバ０号１１０，サーバｎ号２１０が生成される。なお、サーバＩＤの付け方の規則については、後述する。また、他の計算機３００に生成されるサーバの構成は、サーバｎ号２１０と同様の構成である。
【００２６】
サーバ０号１１０は、制御部１１１、利用者インタフェース部１１２、時間管理部１１３、画像処理部１１５、サーバ生成部１１４、画像処理結果受付部１１６から構成される。制御部１１１は、利用者インタフェース部１１２、時間管理部１１３、画像処理部１１５、サーバ生成部１１４及び画像処理結果受付部１１６の動作を制御する。利用者インタフェース部１１２は利用者１２との画像データの受け渡しなどの処理を行う。利用者１２は利用者インタフェース部１１２を通じてサーバ０号１１０と画像データの受け渡しを行う。時間管理部１１３はサーバ０号１１０の存在する計算機１００の時計（システム・クロック）の時刻、または処理時間を管理する。画像処理部１１５は画像データを記憶し、フィルタリングなどの画像処理を行う。サーバ生成部１１４は他の異なる計算機に対してサーバの生成を行う。このサーバの生成は、ＲＰＣ（リモート・プロシジャ・コール）により行われる。画像処理結果受付部１１６はサーバｎ号２１０から戻された画像処理結果を受け付ける。
【００２７】
サーバｎ号２１０は、制御部２１１、時間管理部２１２、画像処理部２１３、サーバ生成部２１４、及び画像処理結果送出部２１５から構成される。制御部２１１は、時間管理部２１２、画像処理部２１３、サーバ生成部２１４、及び画像処理結果送出部２１５の動作を制御する。時間管理部２１２はサーバｎ号２１０の存在する計算機２００の時計（システム・クロック）の時刻、または処理時間を管理する。画像処理部２１３は画像処理部１１５と同様に画像データを記憶し、フィルタリングなどの画像処理を行う。サーバ生成部２１４は他の異なる計算機に対してサーバの生成を行う。画像処理結果送出部２１５は画像処理部２１３で処理した結果をサーバ０号１１０に戻す処理を行う。
【００２８】
なお、前述のサーバ０号１１０の処理手続きにおける処理開始時刻ｔｓ及びライフ・タイムｔｌの設定並びに現在時刻ｔｃの取得は時間管理部１１３が行う。また、サーバｎ号２１０における現在時刻ｔｃの取得は時間管理部２１２が行う。サーバ０号１１０の画像処理結果受付部１１６は画像処理結果データ受付手続きにおいて利用されるキューを持つ。
【００２９】
以上のような構成の画像処理システムにおいて、以下のような手順で画像処理を行う。
図４は第１の実施の形態のサーバ０号１１０の処理手順を示すフローチャートである。この処理は、利用者１２がフィルタリング処理など画像処理をサーバ０号１１０に依頼することにより開始される。以下、処理手順をステップに沿って説明する。
〔Ｓ１１〕利用者インタフェース部１１２は、利用者１２からの画像処理要求を受け付ける。このとき、利用者１２は処理すべき画像データを指定している。
〔Ｓ１２〕時間管理部１１３は、処理開始時刻ｔｓ及び最大ライフ・タイムｔｌを設定する。ここで、最大ライフ・タイムｔｌとは、利用者１２が画像処理のために待つことのできる時間である。処理開始時刻ｔｓと最大ライフ・タイムｔｌとが設定された時間管理部１１３は、処理開始時刻をｔｓとし、処理終了時刻、すなわちサーバ０号１１０が利用者１２に画像を処理した結果を戻す時刻をｔｅとする。また、以後処理開始時刻ｔｓから処理終了時刻ｔｅまでの時間をｔｅｓと表記し（ｔｅｓ＝ｔｅ−ｔｓ）、処理開始時刻ｔｓから現在の時刻ｔｃまでの経過時間をｔｃｓと表記する（ｔｃｓ＝ｔｃ−ｔｓ）。
【００３０】
サーバ０号１１０の実行時のライフ・タイム（実際の結果的なライフ・タイム）はｔｅｓであり、ｔｅｓはｔｌ以下（ｔｌ≧ｔｅｓ＞０）でなければならない。よって、サーバ０号１１０のライフ・タイムは処理時間を保証するものとなる。なお、ｔｌは利用者１２自身がサーバ０号１１０に与えてもよいし、前述した如くサーバ０号１１０自身が規定値を設定してもよい。
〔Ｓ１３〕サーバ生成部１１４は、処理開始時刻ｔｓに直ちに自分と同じ処理をするサーバを他の二つの異なる計算機にそれぞれ生成することを試みる。ただし、そのサーバ生成において、処理すべき画像データの一部しか複製しない。ここで、生成した偶数ＩＤのサーバに対して処理すべきデータの前半部分を複製し、生成した奇数ＩＤのサーバに対して処理すべきデータの後半部分を複製する。なお、サーバ生成に失敗した場合の特別な処理はない。
〔Ｓ１４〕時間管理部１１３は、現在の時刻ｔｃを取得する。
〔Ｓ１５〕時間管理部１１３は、経過時間ｔｃｓ（＝ｔｃ−ｔｓ）と最大ライフ・タイムｔｌとを比較する。経過時間ｔｃｓが最大ライフ・タイムｔｌに達していなければステップＳ１６に進み、達していればステップＳ１８に進む。
〔Ｓ１６〕生存時間あり、すなわちｔｌ≧ｔｃｓの場合、画像処理部１１５は、サーバｎ号から処理した結果のデータが戻されるのを待つ。ここで、サーバｎ号は０以外のサーバＩＤを持つサーバである。この手続きについてはサーバ０号の画像処理結果データ受付手続きとして後述する。画像処理部１１５は、その待ち時間を利用して、処理すべき画像データに対する画像処理を画像データの先頭から処理すべきデータを最小の実行単位分だけ実行する。
【００３１】
なお、サーバｎ号から処理した結果のデータが戻されたとき、画像処理部１１５は、その結果のデータを自己の画像データの一部として複製し、その部分は処理済、つまり処理しないこととする。ここで、最小の実行単位とは、例えば、スキャンライン、ブロック、あるいは画素などの単位である。
〔Ｓ１７〕画像処理部１１５は、処理すべきデータの有無を判断する。処理すべきデータがある場合、ステップＳ１５に戻る。一方、処理すべきデータはない場合、ステップＳ１８に進む。
〔Ｓ１８〕ステップＳ１５において生存時間なしと判断された場合、またはステップＳ１７において処理すべきデータがないと判断された場合、画像処理部１１５は、利用者インタフェース部１１２を介して、直ちに自己の持つ画像処理結果データを利用者に戻す。
【００３２】
図５は第１の実施の形態のサーバｎ号（ここで、ｎは０以外のサーバＩＤである）２１０の処理手順を示すフローチャートである。この処理は、サーバ０号１１０からの画像処理要求を、サーバｎ号２１０が受け取った際に開始される。
〔Ｓ２１〕サーバ生成部２１４は、直ちに自分と同じ処理をするサーバを他の二つの異なる計算機にそれぞれ生成することを試みる。ただし、そのサーバ生成において、処理すべき画像データの一部しか複製しない。ここで、生成した偶数ＩＤのサーバに対して処理すべきデータの前半部分を複製し、生成した奇数ＩＤのサーバに対して処理すべきデータの後半部分を複製する。なお、サーバ生成に失敗した場合の特別な処理はない。
〔Ｓ２２〕画像処理部２１３は、処理すべき画像データに対する画像処理を画像データの先頭から実行する。
〔Ｓ２３〕時間管理部２１２は、現在の時刻ｔｃを取得する。
〔Ｓ２４〕時間管理部２１２は、経過時間ｔｃｓ（＝ｔｃ−ｔｓ）と最大ライフ・タイムｔｌとを比較する。経過時間ｔｃｓが最大ライフ・タイムｔｌに達していなければステップＳ２５に進み、達していれば制御部２１１が自己のプロセスを消滅させ処理を終了する。
〔Ｓ２５〕生存時間あり、すなわちｔｌ≧ｔｃｓの場合、画像処理結果送出部２１５は、直ちに自己の持つ画像処理結果データをサーバ０号１１０に戻す。そして、制御部２１１は自己のプロセスを消滅させる。
【００３３】
以上の様な処理を行うサーバが各計算機内に生成されることより、画像データが、各サーバで分散処理される。
図６は第１の実施の形態におけるサーバＩＤの付け方の規則を示す図である。なお、サーバＩＤの表記された長方形は各サーバが処理すべきデータであることを示す。サーバが生成されるたびに生成されたサーバで処理されるべき画像データは小さくなる。つまり、二つのサーバを生成したサーバは画像データの前半部分を一つのサーバに複製し、その画像データの後半部分を他のサーバに複製する。ここでは、サーバが第４世代まで生成されていることを示している。
【００３４】
サーバ０号３１から生成されるサーバをサーバ００号３２ａ及びサーバ０１号３２ｂとする。サーバ００号３２ａはサーバ０００号３３ａ及びサーバ００１号３３ｂを生成する。また、サーバ０１号３２ｂはサーバ０１０号３３ｃ及びサーバ０１１号３３ｄを生成する。以下同様にして、サーバ００００号３４ａ、サーバ０００１号３４ｂ、サーバ００１０号３４ｃ、サーバ００１１号３４ｄ、サーバ０１００号３４ｅ、サーバ０１０１号３４ｆ、サーバ０１１０号３４ｇ、及びサーバ０１１１号３４ｈが生成される。つまり、サーバは自己のサーバＩＤに０又は１を右から付加した番号をサーバＩＤとするサーバを二つ生成する。これをサーバを生成するごとに繰り返す。
【００３５】
図７はサーバ００１号がサーバの生成に失敗した状況を示す図である。図６と同様に、サーバ０号３１から順にサーバが生成されるが、サーバ００１号３３ｂがサーバの生成に失敗すると、図６に示したサーバ００１０号３４ｃとサーバ００１１号３４ｄとは生成されない。
【００３６】
ところで、あるサーバが別のサーバを生成する場合のサーバを生成する計算機の決定には、ブロードキャストを用いることができる。即ち、サーバ生成部は、先ずサーバを生成したい旨の画像処理要求をネットワーク上の全ての計算機に送信する。その要求を受け取った計算機は、自己にサーバを生成できるか否かを判断する。判断基準としては、例えば、１台の計算機では一つのサーバしか作らないものとし、既にサーバが生成されていればそれ以上生成しないものとする。また、他の情報処理の為に計算機が使用されておりその負荷が大きい場合にも、その計算機はサーバを生成しないものとする。そして、サーバが生成可能であると判断した計算機のみ、要求を出力したサーバに返事を送り返す。
【００３７】
返事を受け取ったサーバは、最初に返事を返した計算機に対して、複製した画像データを送信する。この画像データを受け取った計算機は、内部にサーバｎ号を生成し画像処理を行う。
【００３８】
次に、サーバ０号におけるサーバｎ号からの画像処理結果の受付の手続きについて説明する。一般的な分散処理環境、つまりネットワークで接続された複数の計算機において画像処理を行う環境においては、各計算機の能力が異なることが予想されるので、各サーバｎ号から部分的な画像処理結果が任意の時刻に到達する場合がある。このような場合についての処理手順を以下に示す。
【００３９】
図８はサーバ０号の画像処理結果データ受付状況を示す図である。この図は、サーバ００１号３３ｂ及びサーバ００１０号３４ｃがそれぞれ各サーバで処理した結果をサーバ０号３１に戻す様子を示している。サーバ００１号３３ｂ又はサーバ００１０号３４ｃなどサーバｎ号がサーバ０号３１に各サーバで処理した結果を戻すタイミングによっては、その戻された画像処理結果データとサーバ０号３１で処理した結果が重複する可能性がある。この図では、ハッチ部分が処理された画像データである。
【００４０】
図９は画像処理結果データが重複した場合におけるタイミング・チャートである。サーバ０号３１は、時刻ｔｓで利用者から受け取った画像データの処理を開始する。生成されたサーバ００１号３３ｂ及びサーバ００１０号３４ｃは時刻ｔｃにおいて、それぞれのサーバで処理した結果をサーバ０号３１に戻す。
【００４１】
ここで、サーバ０号３１における各サーバからの画像処理結果データの受付処理については、キュー、すなわち受付データ用の先入れ先出し型のバッファ記憶装置を用いる方法による手続きが考えられる。これは、サーバ００１号３３ｂとサーバ００１０号３４ｃが同じ時刻ｔｃに処理した結果を戻した場合にも、それらの画像処理結果データが前述のキューに配置されると、それらの先後関係が生じることを利用するものである。なお、画像処理結果データのバッファ記憶装置への格納は、サーバ内の画像処理結果受付部が行う。
【００４２】
図１０は画像処理結果データを受け付けたサーバ０号の処理手順を示す図である。この処理は、全てサーバ０号内の画像処理部が行う。
〔Ｓ３１〕受付データ用の先入れ先出し型バッファ記憶装置における画像処理結果データの有無を検査する。画像処理結果データがある場合にはステップＳ３２に進み、画像処理結果データがない場合には処理を終了する。
〔Ｓ３２〕画像処理結果データがある場合、受け付けたデータについて利用者から受け取った時点での配置情報（アドレスあるいは座標）を検査する。
〔Ｓ３３〕ステップＳ３２で得た配置情報から、バッファ記憶装置内の画像処理結果データが処理済のデータであるかどうかを判断する。処理済のデータであれば、この処理を終了する。処理済でないデータが含まれていればステップＳ３４に進む。
〔Ｓ３４〕処理済であるデータ以外の部分（未処理部分のデータ）を自己（サーバ０号）のデータとして複製し、その部分は処理済とする。
【００４３】
以上にようにして、スケジューリングを行わずに処理すべき画像データを複数のサーバで分散処理することができる。しかも、時間管理部が最大ライフ・タイムｔｌを管理しているため、処理途中であっても、一定の時間以内に画像処理結果データを利用者に返すことができる。
【００４４】
次に第２の実施の形態について説明する。第１の実施の形態では、サーバを二つずつ生成する場合の例を示したが、生成するサーバの数は一つであってもよいし、あるいは三つ以上であってもよい。そこで、サーバを一つずつ生成する場合を、第２の実施の形態として以下に説明する。なお、各計算機の接続関係と各サーバ内の基本的は構成は、図２、図３で示した第１の実施の形態のものと同様である。そこで、第２の実施の形態における各構成要素を図２、図３で示したものと同じ名称で呼ぶこととして、第２の実施の形態の処理内容を説明する（以後の他の実施の形態においても同様）。
【００４５】
図１１は第２の実施の形態におけるサーバ０号の処理手順を示すフローチャートである。なお、サーバＩＤの付け方の規則については、後述する。
〔Ｓ４１〕利用者インタフェース部は、利用者からの画像処理要求を受け付ける。このとき、利用者は処理すべき画像データを指定している。
〔Ｓ４２〕時間管理部は、処理開始時刻ｔｓ及び最大ライフ・タイムｔｌを設定する。
〔Ｓ４３〕サーバ生成部は、直ちに自分と同じ処理をするサーバを他の一つの異なる計算機に生成するための処理を行い、その成否を判断する。サーバの生成が失敗すればステップＳ４４に進み、成功すればこのステップＳ４３を繰り返す。従って、サーバが生成できなくなるまで、サーバの生成処理を繰り返すことになる。
【００４６】
サーバの生成に成功した場合、処理すべき画像データの一部しか複製しない。ここで、サーバ０号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバに生成したサーバの処理すべきデータとして複製する。なお、利用者がサーバ０号に与えた処理すべき画像データと、サーバ０号の処理手続きが進むごとに小さくなっていくサーバ０号が処理すべき画像データとの差分（余りの部分）、すなわちサーバｎ号が本来処理すべき部分を処理可能なデータと呼ぶことにする。
〔Ｓ４４〕時間管理部は、現在の時刻を取得する。
〔Ｓ４５〕時間管理部は、経過時間ｔｃｓと最大ライフ・タイムｔｌとを比較する。生存時間あり、すなわちｔｌ≧ｔｃｓの場合ステップＳ４６に進み、生存時間なし、すなわちｔｌ＜ｔｃｓの場合ステップＳ４８に進む。
〔Ｓ４６〕画像処理部は、サーバｎ号から処理した結果のデータが戻されるのを待つ。その待ち時間を利用して、処理すべき画像データ又は処理可能なデータに対する画像処理を画像データの先頭から処理すべきデータを最小の実行単位分だけ実行する。
〔Ｓ４７〕画像処理部は、処理すべきデータ及び処理可能なデータの有無を判断する。処理すべきデータ又は処理可能なデータが有る場合、ステップＳ４５に戻り、処理すべきデータ及び処理可能なデータが無い場合、ステップＳ４８に進む。
〔Ｓ４８〕ステップＳ４５において生存時間なしと判断された場合、またはステップＳ４７において処理すべきデータがなく、かつ処理可能なデータがないと判断された場合、画像処理部は、利用者インタフェース部を介して、直ちに自己の持つ画像処理結果データを利用者に戻す。
【００４７】
サーバｎ号の処理手続き（ここで、ｎは０以外のサーバＩＤである。）は第１の実施の形態と同じであるで説明を省略する。ただし、サーバの生成処理（図５のステップＳ２１に該当）において処理すべき画像データの一部しか複製しない点が異なる。ここで、サーバｎ号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバ（サーバｎ＋１号）に生成したサーバの処理すべきデータとして複製する。
【００４８】
さらに、サーバｎ号のよって作られたサーバは、別のサーバの生成は行わない。即ち、サーバ０号によって作られたサーバｎ号のみが別のサーバを生成することができる。
【００４９】
図１２は第２の実施の形態におけるサーバＩＤの付け方を示す図である。サーバ０号４１から生成されるサーバはサーバ０１号４４とする。サーバ０１号４４を生成したサーバ０号４１はそのサーバＩＤを００に更新する。すなわち、サーバ０号４１はサーバ００号４２となる。サーバ００号４２は、サーバ００１号４７を生成し、サーバ０００号４３となる。また、サーバ０１号４４は、サーバ０１１号４６を生成し、サーバ０１０号４５となる。つまり、生成されたサーバは元のサーバＩＤに１を右から付加した番号がサーバＩＤとなる。一方、サーバを生成したサーバは自己のサーバＩＤに０を右から付加してサーバＩＤを更新する。これをサーバを生成するごとに繰り返す。ここで、サーバ００号４２、サーバ０００号４３など二進記法の読み方で識別番号が０となるものはサーバ０号であるとみなす。
【００５０】
図１３は第２の実施の形態における各サーバ０号の処理すべき画像データ及び処理可能データの両領域の変化を示す図である。この図において、斜線のハッチングの部分はサーバ０号が処理すべき画像データを示しており、クロスハッチの部分はサーバ０号が処理可能な画像データを示している。サーバ０号４１が処理を開始する時点では、サーバ０号４１において利用者から受け取った画像データのすべてが処理すべき画像データとなっている。この時点ではサーバｎ号、つまりサーバ０号４１以外のサーバは存在せず、サーバｎ号が処理すべき画像データはない。次に、サーバ０号４１がサーバ０１号を生成し、自らがサーバ００号４２となった時点で、サーバ０１号に部分的に複製した画像データの部分をサーバ００号４２が処理可能な画像データとする。他の部分がサーバ００号４２が処理すべき部分となる。同様にサーバが生成されるごとにサーバ０号はサーバ０００号４３、サーバ００００号４４となると、処理すべき画像データの領域は小さくなり、処理可能な画像データの領域は大きくなる。
【００５１】
次に第３の実施の形態について説明する。上記の第２の実施の形態は他の異なる計算機に一つのサーバを生成して画像を処理する場合であった。しかしサーバを生成したサーバ０号のＩＤが更新され、さらにそのサーバ０号は他の異なる計算機に一つのサーバを生成する。このとき、直前にサーバ０号により生成されたサーバｎ号も他の異なる計算機に一つのサーバを生成しているため、結局第１の実施の形態と同様に概念的にはサーバを二つずつ生成することを意味していた。そこで、全てのサーバが他の異なる計算機に一つのサーバを生成して画像を処理する場合、つまり実質的に一つずつしかサーバを生成しない場合の例を第３の実施の形態として以下に説明する。
【００５２】
第３の実施の形態におけるサーバ０号、及びサーバｎ号の処理手順は第１の実施の形態の処理手順（図４，図５に示す）とほぼ同じである。そこで、第１の実施の形態における相違点のみを、図４，図５に示すステップ番号を引用して説明する。なお、第３の実施の形態におけるサーバＩＤの付け方の規則については、後述する。
【００５３】
第３の実施の形態のサーバ０号の処理手続きにおける第１の実施の形態との相違点は、図４のステップＳ１３における処理である。これは、サーバ０号が、直ちに自分と同じ処理をするサーバ１号を他の計算機に生成する処理である。この処理において、第３の実施の形態では、他のサーバを一つしか生成せず、その生成されたサーバには処理すべき画像データの一部しか複製しない。ここで、サーバ０号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバ１号にサーバ１号の処理すべきデータとして複製する。
【００５４】
第３の実施の形態のサーバｎ号の処理手続きにおける第１の実施の形態との相違点は、図５のステップＳ２１における処理である。これは、サーバｎ号が、直ちに自分と同じ処理をするサーバｎ＋１号を他の計算機に生成する処理である。この処理において、第３の実施の形態では、他のサーバを一つしか生成せず、その生成されたサーバには処理すべき画像データの一部しか複製しない。ここで、サーバｎ号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバｎ＋１号に処理すべきデータとして複製する。なお、サーバ生成に失敗した場合の特別な処理はなく、次の手続きに進む。
【００５５】
図１４は第３の実施の形態におけるサーバＩＤの付け方の規則を示す図である。サーバ０号５１から生成されるサーバはサーバ１号５２とする。サーバ１号５２はサーバ２号５３を生成する。また、サーバ２号５３はサーバ３号５４を生成する。つまり、生成されたサーバは元のサーバＩＤに１を加えた番号がサーバＩＤとなる。これをサーバを生成するごとに繰り返す。
【００５６】
このようにしてサーバを生成していけば、新たなサーバは一つずつしか生成されない。第２の実施の形態では、サーバ０号はサーバの生成に失敗するまでサーバｎ号を作り続けるため、サーバの生成に失敗しなければ画像処理を行うことができない。ところが、第３の実施の形態では、サーバ０号は１回しかサーバの生成処理を行わないため、サーバの生成処理を１回だけ行った後、直ぐに画像処理を行うことができる。
【００５７】
次に第４の実施の形態について説明する。第１の実施の形態、第２の実施の形態及び第３の実施の形態においては、各計算機におけるサーバの終了（消滅）を単一のライフ・タイムｔｌのみによって制御する場合の手続きを示した。ここでは、各計算機におけるサーバの当該計算機上での生存時間を各々制御する場合を、第４の実施の形態としてその手続きを示す。
【００５８】
ここで、各サーバの計算機上での生存時間を決定するための時間をデッドラインと呼ぶことにして、サーバＩＤとともにｔｄ（０）などと記することにする。つまり、サーバ０号のデッドラインｔｄ（０）はライフ・タイムｔｌと同一である。サーバ１号のデッドラインはｔｄ（１）と示すことにする。
【００５９】
以下に先の第３の実施の形態における各サーバの生存時間制御方式を変更し、かつ、サーバ０号以外のサーバ、つまりサーバｎ号の処理手順を一部変更した場合の手続きについて示す。なお、サーバＩＤの付け方は、第３の実施の形態と同様とする。
【００６０】
図１５は第４の実施の形態におけるサーバ０号の処理手順を示すフローチャートである。
〔Ｓ５１〕利用者インタフェース部は、利用者からの画像処理要求を受け付ける。このとき、利用者は処理すべき画像データを指定している。
〔Ｓ５２〕時間管理部は、処理開始時刻ｔｓ及び最大ライフ・タイムｔｌを設定する。ここで、最大ライフ・タイムｔｌとは、利用者１２が画像処理のために待つことのできる時間である。処理開始時刻ｔｓと最大ライフ・タイムｔｌとが設定された時間管理部は、処理開始時刻をｔｓとし、処理終了時刻、すなわちサーバ０号が利用者に画像を処理した結果を戻す時刻をｔｅとする。また、以後処理開始時刻ｔｓから処理終了時刻ｔｅまでの時間をｔｅｓと表記し（ｔｅｓ＝ｔｅ−ｔｓ）、処理開始時刻ｔｓから現在の時刻ｔｃまでの経過時間をｔｃｓと表記する（ｔｃｓ＝ｔｃ−ｔｓ）。
【００６１】
サーバ０号の実行時のライフ・タイム（実際の結果的なライフ・タイム）はｔｅｓであり、ｔｅｓはｔｌ以下（ｔｌ≧ｔｅｓ＞０）でなければならない。よって、サーバ０号のライフ・タイムは処理時間を保証するものとなる。なお、ｔｌは利用者自身がサーバ０号に与えてもよいし、サーバ０号自身が規定値を設定してもよい。また、ライフ・タイムｔｌはサーバ０号のデッドラインｔｄ（０）と同じ（ｔｌ＝ｔｄ（０））である。
〔Ｓ５３〕サーバ生成部は、直ちに自分と同じ処理をするサーバ１号を他の計算機に生成する。ただし、その生成において処理すべき画像データの一部しか複製しない。ここで、サーバ０号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバ１号にサーバ１号の処理すべきデータとして複製する。また、生成されたサーバ１号のデッドラインｔｄ（１）は、サーバ０号のデッドラインｔｄ（０）の半分であるように設定する。つまり、ｔｄ（１）＝ｔｄ（０）／２とする。なお、サーバ生成に失敗した場合の特別な処理はない。
〔Ｓ５４〕時間管理部は、現在の時刻ｔｃを取得する。
〔Ｓ５５〕時間管理部は、サーバ０号は、経過時間ｔｃｓ（＝ｔｃ−ｔｓ）とデッドラインｔｄ（０）とを比較する。経過時間ｔｃｓがデッドラインｔｄ（０）に達していなければステップＳ５６に進み、達していればステップＳ５８に進む。
〔Ｓ５６〕生存時間あり、すなわちｔｄ（０）≧ｔｃｓの場合、画像処理部は、サーバｎ号から処理した結果のデータが戻されるのを待つ。そして、その待ち時間を利用して、処理すべき画像データに対する画像処理を画像データの先頭から処理すべきデータを最小の実行単位分だけ実行する。
【００６２】
なお、サーバｎ号から処理した結果のデータが戻されたとき、その結果のデータを自己の画像データの一部として複製し、その部分は処理済、つまり処理しないこととする。ここで、最小の実行単位とは、例えば、スキャンライン、ブロック、あるいは画素などの単位である。
〔Ｓ５７〕画像処理部は、処理すべきデータの有無を判断する。処理すべきデータがある場合、ステップＳ５５に戻る。一方、処理すべきデータはない場合、ステップＳ５８に進む。
〔Ｓ５８〕ステップＳ５５において生存時間なしと判断された場合、またはステップＳ５７において処理すべきデータがないと判断された場合、画像処理部は、利用者インタフェース部を介して、直ちに自己の持つ画像処理結果データを利用者に戻す。
【００６３】
図１６は第４の実施の形態におけるサーバｎ号の処理手順を示すフローチャートである。
〔Ｓ６１〕サーバ生成部は、直ちに自分と同じ処理をするサーバｎ＋１号を他の計算機に生成する。ただし、その生成において処理すべき画像データの一部しか複製しない。ここで、サーバｎ号は、処理すべきデータの前半部分を自己の処理すべきデータとし、処理すべきデータの後半部分を生成したサーバｎ＋１号に処理すべきデータとして複製する。また、生成されたサーバｎ＋１号のデッドラインｔｄ（ｎ＋１）は、サーバｎ号のデッドラインｔｄ（ｎ）の半分であるように設定する。つまり、ｔｄ（ｎ＋１）＝ｔｄ（ｎ）／２とする。
〔Ｓ６２〕時間管理部は、現在の時刻ｔｃを取得する。
〔Ｓ６３〕時間管理部は、経過時間ｔｃｓ（＝ｔｃ−ｔｓ）とデッドラインｔｄ（ｎ）とを比較する。経過時間ｔｃｓがｔｄ（ｎ）以下ならばステップＳ６４に進み、ｔｄ（ｎ）を超えていれば制御部は自己のプロセスを消滅させる。
〔Ｓ６４〕生存時間あり、すなわちｔｄ（ｎ）≧ｔｃｓの場合、画像処理部は、処理すべき画像データに対する画像処理を画像データの先頭から実行する。
〔Ｓ６５〕画像処理結果送出部は、直ちに自己の持つ画像処理結果データをサーバ０号に戻す。そして、制御部は自己のプロセスを消滅させる。
【００６４】
ここでは、生成されたサーバｎ＋１号のデッドラインｔｄ（ｎ＋１）は、サーバｎ号のデッドラインｔｄ（ｎ）の半分であるように設定したが、他の規則によって設定してもよい。つまり、生成されたサーバｎ＋１号のデッドラインｔｄ（ｎ＋１）が、サーバｎ号のデッドラインｔｄ（ｎ）の３分の１であるように設定してもよい。
【００６５】
ここで、各サーバの動作と処理に要する時間の関係について説明する。図１７及び図１８は各サーバが生成されるタイミングと当該サーバで画像データが処理される時間について示している。
【００６６】
図１７は理想的な状況における各サーバが生成されるタイミングと当該サーバで画像データが処理される時間示す図である。つまり、サーバの生成及びデータの複製に時間を要しない場合、あるいはサーバの生成及びデータの複製に時間が無限に小さい場合のようすを示している。また、ネットワークには４台の計算機が接続され、その計算機の能力が等しいことが仮定されている。
【００６７】
このような場合において前述した処理手順に従って、まずライフ・タイムｔｌが設定される。このライフ・タイムｔｌとサーバ０号６１のデッドラインは等しい。また、図１７においては利用者から依頼された処理すべき画像を処理するのに必要十分なライフ・タイムｔｌが設定されている場合を示している。つまり、利用者から依頼された処理すべき画像を処理するのに要する時間をサーバ０号６１のサーバＩＤでラベルづけされた四角形の枠で示している。その四角形の横幅とライフ・タイムｔｌの長さは等しい。ここで、サーバ０号６１は直ちにサーバ１号６２を生成する。サーバ０号６１の処理すべきデータを示すハッチ部分、すなわち利用者から指定された画像データの前半部分をサーバ０号６１が処理する。それ以外の部分（ハッチのかかっていない部分）はサーバ１号６２が処理できるように複製される。なお、この部分はサーバ０号６１が処理可能な部分である。また、サーバ１号６２のデッドラインｔｄ（１）はｔｄ（０）の２分の１と等しいように、つまりライフ・タイムｔｌの半分であるように設定される。
【００６８】
サーバ０号６１から生成されたサーバ１号６２は直ちにサーバ２号６３を生成することを試みる。サーバ１号６２から生成されたサーバ２号６３は直ちにサーバ３号６４を生成することを試みる。さらに、サーバ２号６３から生成されたサーバ３号６４は直ちにサーバ４号を生成することを試みる。
【００６９】
図１７においては、ネットワークに４台の計算機しか接続されていないため、サーバ１号６２、サーバ２号６３及びサーバ３号６４の生成には成功したが、サーバ４号の生成には失敗した場合を示している。また、サーバ２号６３のデッドラインはサーバ１号６２のそれの半分に、サーバ３号６４のデッドラインはサーバ２号６３のそれの半分にそれぞれ設定されている。つまり、ｔｄ（２）はｔｄ（１）の２分の１であり、ｔｄ（３）はｔｄ（２）の２分の１である。
【００７０】
さらに、サーバ２号６３の処理すべき画像データは、サーバ１号６２に対してサーバ０号６１から複製された画像データの後半部分である。同様に、サーバ３号６４の処理すべき画像データは、サーバ２号６３に対してサーバ１号６２から複製された画像データの後半部分である。
【００７１】
各サーバは自己の処理すべき画像データ、すなわち図１７において各サーバが処理すべき画像データであることを示すハッチ部分に相当する画像データを処理する。サーバ２号６３及びサーバ３号６４は処理開始時刻ｔｓからそれぞれの処理すべき画像データを処理し、同じ時刻で処理が終了している。つまり、以後サーバＩＤをｎとし、各サーバの処理終了時刻をｔｅ（ｎ）と表記することにすると、時刻ｔｅ（２）でサーバ２号６３が処理を終了し、その同じ時刻ｔｅ（３）でサーバ３号６４が処理が終了している。すなわち、ｔｅ（２）とｔｅ（３）は等しい（ｔｅ（２）＝ｔｅ（３））。ｔｅ（２）又はｔｅ（３）の時点ではサーバ２号６３及びサーバ３号６４はそれぞれ各サーバで処理した画像処理の結果をサーバ０号６１に戻している。また、時刻ｔ（１）の時点ではサーバ１号６２はその結果をサーバ０号６１に戻し処理を終了している。サーバ０号６１は時刻ｔ（０）の時点では、すでに自己の処理すべき画像データの処理を終了し、またサーバ１号６２、サーバ２号６３及びサーバ３号６４からそれぞれ処理した結果を受け取り、さらにすべての部分の画像データを利用者に戻している。なお、この場合サーバ３号６４の処理開始時刻ｔｓから処理修了時刻ｔｅ（３）までの時間とサーバ３号６４のデッドラインｔｄ（３）は等しい。また、サーバ０号６１はライフ・タイムｔｌの半分の時間で利用者に画像を処理した結果を戻している。
【００７２】
図１８は実際的な各サーバが生成されるタイミングと当該サーバで画像データが処理される時間を示す図である。つまり、図１７においてはサーバの生成及びデータの複製に時間を要しない場合、あるいはサーバの生成及びデータの複製に時間が無限に小さい場合のようすを示しているが、図１８はサーバの生成及びデータの複製にある程度の時間を要した場合について、それらの処理に要した時間などを示している。すなわち、図１８において、各サーバの処理すべき画像データを示す領域７１ａ，７２ａ，７３ａ，７４ａの左右に隣接している領域８１〜８６は、サーバの生成及び画像データの部分複製などの処理を示す。図１８は、サーバの生成及び画像データの部分複製に要する時間がフィルタリングなどの実質的な画像処理に要する時間の８分の１である場合を示している。つまり、各サーバの処理すべき画像データを処理するのに要する時間を示す領域７１ａ，７２ａ，７３ａ，７４ａの横幅Ｔｘは、その領域の直ぐ左側に隣接した、各サーバの生成及び画像データの部分複製に要する時間を示す領域８１〜８３の横幅Ｔｙの８倍である。
【００７３】
サーバ０号７１は、サーバ１号７２を生成し画像データを部分複製するのに領域８１の横幅だけ時間を要する。サーバ１号７２は、サーバ２号７３を生成し画像データを部分複製するのに領域８２の横幅だけ時間を要する。サーバ２号７３は、サーバ３号７４を生成し画像データを部分複製するのに領域８３の横幅だけ時間を要する。この例は、図１７の場合と同じく、サーバ４号が生成できなかった場合である。
【００７４】
各サーバはサーバの生成及び画像データの部分複製に要した時間だけ、フィルタリングなどの実質的な画像処理を始める時刻が遅れている。つまり、サーバが生成されるごとに各サーバを生成するのにいくらか時間を要し、さらに画像データを部分的に複製するのに時間を要するため、サーバの実質的な画像処理を始める時刻は、サーバＩＤが大きなサーバほど遅延する。
【００７５】
上述の処理手続きにより、各サーバのデッドラインよりも、サーバ０号７１の処理開始時刻ｔｓから実質的な画像処理を始める時刻までの時間が小さいときには、各サーバはハッチで表現された（領域７１ａ，７２ａ，７３ａ，７４ａに相当する）処理すべき画像データを処理する。よって、サーバ０号７１からサーバ３号７４まですべてのサーバは、それぞれ各サーバの処理すべき画像データの実質的な処理を行い、処理の結果がサーバ０号に戻される。サーバ１号７２が処理した画像データをサーバ０号に戻すのには、領域８４の横幅だけ時間を要する。サーバ２号７３が処理した画像データをサーバ０号に戻すのには、領域８５の横幅だけ時間を要する。サーバ３号７４が処理した画像データをサーバ０号にもどすのには、領域８６の横幅だけ時間を要する。そして、サーバ０号に集められた処理結果が利用者に戻される。
【００７６】
次に第５の実施の形態を説明する。以上は、サーバｎ号は他のサーバの生成について一度しか試みないものであったが、一定量の処理が終了する度に処理すべきデータの未処理部分のデータの処理のために再度サーバの生成を試みる方法も考えられる。例えば、第１の実施の形態の手順の一部を変更して以下のような手順で画像処理を行うことにする。なお、サーバＩＤの付け方はサーバＩＤの付け方の規則１によるものとする。
【００７７】
図１９は第５の実施の形態における各サーバの生成及び画像データの部分複製の様子の示す図である。図１９においては、サーバ０１号９１及びサーバ００１号９２が第１回目のサーバ生成に失敗し、第２回目のサーバ生成には成功した場合の様子を示す。図中のハッチされた部分はサーバ０１号９１及びサーバ００１号９２が処理した画像データであることを示している。サーバ０号の処理手続きについては、第１の実施の形態の手続き（図４に示す）とほぼ同じであるため、相違点のみを説明する。
【００７８】
第５の実施の形態では第１の実施の形態におけるステップＳ１２の処理の内容が異なる。第５の実施の形態ではこのステップにおいて、時間管理部が、処理開始時刻ｔｓ及び最大ライフ・タイムｔｌを設定する。ここで、最大ライフ・タイムｔｌとは、利用者が画像処理のために待つことのできる時間である。処理開始時刻ｔｓと最大ライフ・タイムｔｌとが設定された時間管理部は、処理開始時刻をｔｓとし、処理終了時刻、すなわちサーバ０号が利用者に画像を処理した結果を戻す時刻をｔｅとする。また、以後処理開始時刻ｔｓから処理終了時刻ｔｅまでの時間をｔｅｓと表記し（ｔｅｓ＝ｔｅ−ｔｓ）、処理開始時刻ｔｓから現在の時刻ｔｃまでの経過時間をｔｃｓと表記する（ｔｃｓ＝ｔｃ−ｔｓ）。
【００７９】
サーバ０号の実行時のライフ・タイム（実際の結果的なライフ・タイム）はｔｅｓであり、ｔｅｓはｔｌ以下（ｔｌ≧ｔｅｓ＞０）でなければならない。なお、ｔｌは利用者がサーバ０号に与えてもよいし、サーバ０号自身が規定値を設定してもよい。また、時間管理部は、ｔｌより小さな値をサーバ再生成時間ｔｒとして設定する。つまり、ｔｌ＞ｔｒ＞０とする。
【００８０】
図２０は第５の実施の形態におけるサーバｎ号の処理手順を示すフローチャートである。
〔Ｓ７１〕サーバｎ号内の時間管理部は、現在の時刻ｔｃをサーバｎ号での処理開始時刻ｔｓ（ｎ）として設定する。つまり、ｔｓ（ｎ）＝ｔｃとする。
〔Ｓ７２〕サーバ生成部は、直ちに自分と同じ処理をするサーバを他の二つの異なる計算機にそれぞれ生成することを試みる。ただし、そのサーバ生成において、処理すべき画像データの一部しか複製しない。ここで、生成した偶数ＩＤのサーバに対して処理すべきデータの前半部分を複製し、生成した奇数ＩＤのサーバに対して処理すべきデータの後半部分を複製する。なお、サーバ生成に失敗した場合、次の手続きに進む。
〔Ｓ７３〕画像処理部は、処理すべき画像データに対する画像処理を、画像データの先頭から処理すべきデータを最小の実行単位分だけ実行する。
〔Ｓ７４〕時間管理部は、現在の時刻ｔｃを取得する。
〔Ｓ７５〕時間管理部は、経過時間ｔｃｓ（＝ｔｃ−ｔｓ）と最大ライフ・タイムｔｌとを比較する。経過時間ｔｃｓが最大ライフ・タイムｔｌに達していなければステップＳ７６に進み、達していれば自己のプロセスを消滅させる。
〔Ｓ７６〕生存時間あり、すなわちｔｌ≧ｔｃｓの場合、時間管理部は、現在の時刻ｔｃがｔｓ（ｎ）＋ｔｒの値より小さいか否かを判断する。現在の時刻ｔｃがｔｓ（ｎ）＋ｔｒの値より小さければステップＳ７２に戻り、そうでなければステップＳ７７に進む。
〔Ｓ７７〕生存時間あり、すなわちｔｌ≧ｔｃｓの場合、画像処理結果送出部は、直ちに自己の持つ画像処理結果データをサーバ０号に戻し、自己のプロセスを消滅させる。
【００８１】
このようにして、サーバｎ号が他のサーバを繰り返し生成すると自己の計算機内にトラブルが発生しても、生成した他のサーバが自己の処理すべき画像データと同じデータを処理してくれる。そのため、サーバ０号は確実に処理済の画像データを受け取ることができる。
【００８２】
次に第６の実施の形態について説明する。この実施の形態では、あるサーバが他の計算機にサーバを生成した場合に、子供を生むことに例えて１世代増えたと表現することにする。そうすると、前記の実施の形態１又は実施の形態２のサーバＩＤの付け方の規則においてサーバＩＤの桁は世代を表現していることになる。つまり、サーバＩＤが０号であるサーバは第１世代、サーバＩＤが００号、０１号であるサーバはともに第２世代、サーバＩＤが０００号、００１号、０１０号、０１１号であるサーバはすべて第３世代ということになる。また、第３の実施の形態のサーバＩＤの付け方の規則においては、サーバＩＤに１を加えた数が世代数に相当する。
【００８３】
そして、前述の実施の形態においては世代数に特に制限を設けてはいなかったが、第６の実施の形態では、世代数に制限を設けるようにする。例えば、サーバ自身が自分の世代数をサーバＩＤから判断し、ある世代数の最大値と同じとなった場合には、そのサーバはさらにサーバを生成することはせず、処理すべき画像データをすべて自ら処理するようにする。
【００８４】
ところで、以上の実施の形態においては、その処理すべき画像データが任意の画像データである場合を示した。そこで、画像データの内容がその並び方によって特徴がある場合の例を以下に示す。
【００８５】
例えば、ｓｐｅｃｔｒａｌ  ｓｅｌｅｃｔｉｏｎ方式又はｓｕｃｃｅｓｓｉｖｅ  ａｐｐｒｏｘｉｍａｔｉｏｎ方式でプログレッシブ符号化されたＪＰＥＧ形式の画像データの場合、ＤＣＴ（Ｄｉｓｃｒｅｔｅ  Ｃｏｓｉｎｅ  Ｔｒａｎｓｆｏｒｍ）係数は周波数方向又はビット方向に段階的符号化されている。そこで、以下の実施の形態によれば、解像度又は階調性の低いおおまかな復号画像から画像処理を行うことを期待できる。したがって、処理した結果を順次利用者に提示すれば、利用者は短時間の内におおまかな画像を見ることができる。
【００８６】
第７の実施の形態として、ＤＣＴ係数がｓｐｅｃｔｒａｌ  ｓｅｌｅｃｔｉｏｎ方式で符号化されているときについて説明する。
第７の実施の形態では、第１スキャンから第ｐスキャンまでを画像データの前半部分に配置し、第ｐ＋１スキャンから第ｎスキャンまでを画像データの後半部分に配置する。つまり、全ブロックについてＤＣＴ係数次元の６３から３２までを画像データの前半部分に配置し、全ブロックについてＤＣＴ係数次元の３１から０までを画像データの後半部分に配置する。このように画像データを構成して、第４の実施の形態の方法によって画像処理を行い副画像処理装置から画像処理結果データを受けとるときに、主画像処理装置がそのデータを利用者に戻せば、利用者は、解像度の低い復号画像から画像処理結果を得ることができる。
【００８７】
図２１は第７の実施の形態におけるサーバの生成と画像データの複製状況の例を示す図である。この例では、二つのスキャンで画像データを構成する場合を考える。ここで、画像データ４１０の前半部分は第１スキャン（第１バンド）４１１はＤＣＴ係数次元の６３から３２までのデータで構成され、画像データの後半部分は第２スキャン（第２バンド）４１２はＤＣＴ係数次元の３１から０までのデータで構成される。第４の実施の形態の場合と同じようにサーバが四つ生成された場合、サーバ０号４１３はＤＣＴ係数次元の６３から３２までのデータを処理し、サーバ１号４１４はＤＣＴ係数次元の３１から１６までのデータを処理し、サーバ２号４１５はＤＣＴ係数次元の１５から８までのデータを処理し、サーバ３号４１６はＤＣＴ係数次元の７から０までのデータを処理する。よって、サーバＩＤが大きいサーバほど周波数の低いデータを処理することになる。
【００８８】
また、図１８の実質的な画像処理をする部分を意味するハッチ部分を各サーバで比較すると分かるように、サーバＩＤが大きいサーバほどその処理結果データをサーバに戻す時点は早い。したがって、主画像処理装置が副画像処理装置から画像処理結果データを受け取るときに、それを利用者に戻せば、利用者は解像度の低い画像から見ることができる。
【００８９】
次に第８の実施の形態として、ＤＣＴ係数がｓｕｃｃｅｓｓｉｖｅ  ａｐｐｒｏｘｉｍａｔｉｏｎ方式で符号化されているときの処理を説明する。
第８の実施の形態では、第１スキャンから第ｐスキャンまでを画像データの前半部分に配置し、第ｐ＋１スキャンから第ｎスキャンまでを画像データの後半部分に配置する。つまり、全ブロックについてＬＳＢ側から、すなわち第０ビットから第３までを画像データの前半部分に配置し、全ブロックについて第４ビットから第７ビットまでを画像データの後半部分に配置する。このように画像データを構成して、第４の実施の形態の方法によって画像処理をすれば、階調のあらい復号画像から画像処理を行うことができる。
【００９０】
図２２は第８の実施の形態におけるサーバの生成と画像データの複製状況の例を示す図である。この例では、二つのスキャンで画像データを構成する場合を考える。ここで、画像データ４２０の前半部分は第１スキャン（第１バンド）４２１である第０ビットから第３ビットまで、すなわちＬＳＢ側の下位４ビットのデータで構成され、画像データの後半部分は第２スキャン（第２バンド）４２２で第４ビットから第７ビットまで、すなわちＭＳＢ側の上位４ビットのデータで構成される。第４の実施の形態の場合と同じようにサーバが四つ生成された場合、サーバ０号４２３は第０ビットから第３ビットまでのデータを処理し、サーバ１号４２４は第４ビット及び第５ビットのデータを処理し、サーバ２号４２５は第６ビットのデータを処理し、サーバ３号４２６は第７ビットのデータを処理する。よって、サーバＩＤが大きいサーバほど階調のあらいデータを処理することになる。また、図１８の実質的な画像処理をする部分を意味するハッチ部分を各サーバで比較すると分かるように、サーバＩＤが大きいサーバほどその画像処理結果をサーバ０号４２３に戻す時点は早い。したがって、サーバＩＤが大きいサーバほど早く階調のあらいデータの処理、例えば逆ＤＣＴすなわち復号化などの処理を行った結果を利用者に戻すことができることになる。
【００９１】
以上は、画像データの分割するときにその画像データを二つに分割する場合について説明したが、さらに分割数を増やして、三分割あるいはさらに分割したｎ分割等とすることもできる。例えば、第５の実施の形態の場合においてスキャンラインを３以上とし、各スキャンラインごとに画像データを分割することが考えられる。つまり、画像データとしてＤＣＴ係数がｓｐｅｃｔｒａｌ  ｓｅｌｅｃｔｉｏｎ方式で符号化されているときは、全ブロックについてＤＣＴ係数次元ごとに分割することもできる。このとき、６４個のスキャンラインとなる。一方、画像データとしてＤＣＴ係数がｓｕｃｃｅｓｓｉｖｅ  ａｐｐｒｏｘｉｍａｔｉｏｎ方式で符号化されているときは、全ブロックについて各ビットごとに分割することもできる。このとき、８個のスキャンラインとなる。
【００９２】
なお、上記の説明では、１台の計算機で、サーバを一つだけ生成できる場合について説明したが、サーバは単なるプロセスであるため１台の計算機で複数個生成することも可能である。例えば、マルチＣＰＵの計算機では、ＣＰＵの数だけサーバを生成するようにしてもよい。
【００９３】
【発明の効果】
以上説明したように本発明では、処理対象画像データが主画像処理装置に入力されると、主画像処理依頼手段が処理対象画像データの一部の画像処理要求を出力し、その画像処理要求を受け取った副画像処理装置も、受け取った画像データの一部の画像処理要求を出力する。そして、主画像処理実行手段と副画像処理実行手段とがそれぞれ画像処理を実行する。そのため、スケジューリングを管理する機構を設けることなしに分散して画像処理を行うことができる。
【００９４】
また、副画像処理実行手段は、所定の画像処理を終了するか、あるいは画像処理開始から所定の時間経過した時点で、処理済画像データを主画像処理装置へ転送し、主画像処理実行手段は、処理対象画像データの入力から所定の時間経過した時点で、画像処理結果データを利用者に戻すようにしたため、利用者が期待する応答時間以内に画像処理の結果を戻すことができる。
【図面の簡単な説明】
【図１】本発明の原理構成図である。
【図２】本発明の第１の実施の形態の概略構成を示す図である。
【図３】計算機の内部構成を示すブロック図である。
【図４】第１の実施の形態のサーバ０号の処理手順を示すフローチャートである。
【図５】第１の実施の形態のサーバｎ号の処理手順を示すフローチャートである。
【図６】第１の実施の形態におけるサーバＩＤの付け方の規則を示す図である。
【図７】サーバ００１号がサーバの生成に失敗した状況を示す図である。
【図８】サーバ０号の画像処理結果データ受付状況を示す図である。
【図９】画像処理結果データが重複した場合におけるタイミング・チャートである。
【図１０】画像処理結果データを受け付けたサーバ０号の処理手順を示す図である。
【図１１】第２の実施の形態におけるサーバ０号の処理手順を示すフローチャートである。
【図１２】第２の実施の形態におけるサーバＩＤの付け方を示す図である。
【図１３】第２の実施の形態における各サーバ０号の処理すべき画像データ及び処理可能データの両領域の変化を示す図である。
【図１４】第３の実施の形態におけるサーバＩＤの付け方の規則を示す図である。
【図１５】第４の実施の形態におけるサーバ０号の処理手順を示すフローチャートである。
【図１６】第４の実施の形態におけるサーバｎ号の処理手順を示すフローチャートである。
【図１７】理想的な状況における各サーバが生成されるタイミングと当該サーバで画像データが処理される時間示す図である。
【図１８】実際的な各サーバが生成されるタイミングと当該サーバで画像データが処理される時間を示す図である。
【図１９】第５の実施の形態における各サーバの生成及び画像データの部分複製の様子の示す図である。
【図２０】第５の実施の形態におけるサーバｎ号の処理手順を示すフローチャートである。
【図２１】第７の実施の形態におけるサーバの生成と画像データの複製状況の例を示す図である。
【図２２】第８の実施の形態におけるサーバの生成と画像データの複製状況の例を示す図である。
【符号の説明】
１  主画像処理装置
１ａ  主画像処理依頼手段
１ｂ  主画像処理実行手段
２，３  副画像処理装置
２ａ，３ａ  副画像処理依頼手段
２ｂ，３ｂ  副画像処理実行手段
４  処理対象画像データ
５  画像処理結果データ
【図１】
0003646420.tif 000002
【図２】
0003646420.tif 000003
【図３】
0003646420.tif 000004
【図４】
0003646420.tif 000005
【図５】
0003646420.tif 000006
【図６】
0003646420.tif 000007
【図７】
0003646420.tif 000008
【図８】
0003646420.tif 000009
【図９】
0003646420.tif 000010
【図１０】
0003646420.tif 000011
【図１１】
0003646420.tif 000012
【図１２】
0003646420.tif 000013
【図１３】
0003646420.tif 000014
【図１４】
0003646420.tif 000015
【図１５】
0003646420.tif 000016
【図１６】
0003646420.tif 000017
【図１７】
0003646420.tif 000018
【図１８】
0003646420.tif 000019
【図１９】
0003646420.tif 000020
【図２０】
0003646420.tif 000021
【図２１】
0003646420.tif 000022
【図２２】
0003646420.tif 000023