(57)【要約】      （修正有）【課題】レイアウト解析により抽出された各領域に対する処理を複数の演算リソースに効率的に割り当てることができる技術を提供する。【解決手段】並列で動作する複数のプロセッサにより画像データを処理する画像形成装置であって、入力された画像データを受け付ける画像データ受付部と、画像データ受付部により受け付けられた画像データに基づいて、所定の領域からなるレイアウト構造を解析するレイアウト解析部２０１と、レイアウト解析部２０１により解析された画像データのレイアウト構造における所定の領域に対する処理量を算出する処理量算出部２０５と、レイアウト解析部２０１により解析されたレイアウト構造における全ての領域に対する処理において、処理量算出部２０５により算出された処理量に基づいて、複数のプロセッサのいずれかのプロセッサに所定の領域に対する処理を割り振る処理プロセッサ決定部２０５とを備える。【選択図】図２
2009110499.tif 000002
【特許請求の範囲】
【請求項１】
並列で動作する複数のプロセッサにより画像データを処理する画像形成装置であって、
入力された画像データを受け付ける画像データ受付部と、
前記画像データ受付部により受け付けられた画像データに基づいて、所定の領域からなるレイアウト構造を解析するレイアウト解析部と、
前記レイアウト解析部により解析された前記画像データのレイアウト構造における所定の領域に対する処理量を算出する処理量算出部と、
前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理量算出部により算出された処理量に基づいて、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振る処理プロセッサ決定部と
を備える画像形成装置。
【請求項２】
請求項１に記載の画像形成装置において、
前記処理量算出部は、前記所定の領域のパラメータに基づいて、前記所定の領域に対する処理量を算出することを特徴とする画像形成装置。
【請求項３】
請求項１に記載の画像形成装置において、
前記処理プロセッサ決定部は、前記複数のプロセッサ間の処理量の差が最小となるように前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振ることを特徴とする画像形成装置。
【請求項４】
請求項２に記載の画像形成装置において、
前記所定の領域のパラメータに対する重み付け係数である重要度を変更する重要度変更部をさらに備える画像形成装置。
【請求項５】
請求項４に記載の画像形成装置において、
前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理プロセッサ決定部により前記複数のプロセッサに割り振られた全ての領域に対する処理の前記複数のプロセッサのそれぞれのプロセッサにおける処理時間を測定する処理時間測定部をさらに備え、
前記重要度変更部は、前記重要度の変更前に前記処理時間測定部により測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である過去差分値と、前記重要度の変更後に前記処理時間測定部により測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である現在差分値とを比較し、前記過去差分値が前記現在差分値より大きい場合、変更後の重要度を重要度とし、前記過去差分値が前記現在差分値以下である場合、変更前の重要度を重要度とする画像形成装置。
【請求項６】
請求項１に記載の画像形成装置において、
前記所定の領域の種類は文字または画像であることを特徴とする画像形成装置。
【請求項７】
並列で動作する複数のプロセッサにより画像データを処理する画像処理装置であって、
入力された画像データを受け付ける画像データ受付部と、
前記画像データ受付部により受け付けられた画像データに基づいて、所定の領域からなるレイアウト構造を解析するレイアウト解析部と、
前記レイアウト解析部により解析された前記画像データのレイアウト構造における所定の領域に対する処理量を算出する処理量算出部と、
前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理量算出部により算出された処理量に基づいて、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振る処理プロセッサ決定部と
を備える画像処理装置。
【請求項８】
請求項７に記載の画像処理装置において、
前記処理量算出部は、前記所定の領域のパラメータに基づいて、前記所定の領域に対する処理量を算出することを特徴とする画像処理装置。
【請求項９】
請求項７に記載の画像処理装置において、
前記処理プロセッサ決定部は、前記複数のプロセッサ間の処理量の差が最小となるように前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振ることを特徴とする画像処理装置。
【請求項１０】
請求項８に記載の画像処理装置において、
前記所定の領域のパラメータに対する重み付け係数である重要度を変更する重要度変更部をさらに備える画像処理装置。
【請求項１１】
請求項１０に記載の画像処理装置において、
前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理プロセッサ決定部により前記複数のプロセッサに割り振られた全ての領域に対する処理の前記複数のプロセッサのそれぞれのプロセッサにおける処理時間を測定する処理時間測定部をさらに備え、
前記重要度変更部は、前記重要度の変更前に前記処理時間測定部により測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である過去差分値と、前記重要度の変更後に前記処理時間測定部により測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である現在差分値とを比較し、前記過去差分値が前記現在差分値より大きい場合、変更後の重要度を重要度とし、前記過去差分値が前記現在差分値以下である場合、変更前の重要度を重要度とする画像処理装置。
【請求項１２】
請求項７に記載の画像処理装置において、
前記所定の領域の種類は文字または画像であることを特徴とする画像処理装置。
【請求項１３】
並列で動作する複数のプロセッサにより画像データを処理する画像処理方法であって、
入力された画像データを受け付け、受け付けた画像データに基づいて、所定の領域からなるレイアウト構造を解析し、解析した前記画像データのレイアウト構造における所定の領域に対する処理量を算出し、算出した処理量に基づいて、解析されたレイアウト構造における全ての領域に対する処理において、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振る画像処理方法。
【請求項１４】
請求項１３に記載の画像処理方法において、
前記所定の領域に対する処理量は、前記所定の領域のパラメータに基づいて算出されることを特徴とする画像処理方法。
【請求項１５】
請求項１３に記載の画像処理方法において、
前記所定の領域に対する処理は、前記複数のプロセッサ間の処理量の差が最小となるように前記複数のプロセッサのいずれかのプロセッサに割り振られることを特徴とする画像処理方法。
【請求項１６】
請求項１４に記載の画像処理方法において、
さらに、前記所定の領域のパラメータに対する重み付け係数である重要度を変更する画像処理方法。
【請求項１７】
請求項１６に記載の画像処理方法において、
解析したレイアウト構造における全ての領域に対する処理において、前記複数のプロセッサに割り振られた全ての領域に対する処理の前記複数のプロセッサのそれぞれのプロセッサにおける処理時間を測定し、前記重要度の変更前に測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である過去差分値と、前記重要度の変更後に測定された前記複数のプロセッサにおいて、処理時間が最小であるプロセッサと処理時間が最大であるプロセッサとの処理時間の差である現在差分値とを比較し、前記過去差分値が前記現在差分値より大きい場合、変更後の重要度を重要度とし、前記過去差分値が前記現在差分値以下である場合、変更前の重要度を重要度とする画像処理方法。
【請求項１８】
請求項１３に記載の画像処理方法において、
前記所定の領域の種類は文字または画像であることを特徴とする画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、レイアウト解析における複数のプロセッサのスケジューリング技術に関するものである。
【背景技術】
【０００２】
従来、ＭＦＰのスキャニング機能により紙文書をスキャニングし、電子文書を作成する機能において、スキャニングした画像データをレイアウト解析することによって、文字領域、背景領域、イメージ領域などを抽出し、抽出した各領域に最も適した圧縮方法を選択することで、スキャニングデータの圧縮効率と視認性の向上を同時に実現する技術が知られている。この技術は、例えば、レイアウト解析により文字領域として抽出された領域に対しては、文字の形状をＭＭＲ、ＪＢＩＧ、ＪＢＩ２等の２値圧縮技術を用いて圧縮し、レイアウト解析により背景領域、または写真や絵図などの画像領域として抽出された領域に対しては、ＪＰＥＧ、ＪＰＥＧ２０００、ＨＤ  Ｐｈｏｔｏ等の圧縮技術を用いて圧縮するものである。これらの異なる圧縮方式で圧縮された各領域がマージされることで、文字領域がＪＰＥＧなどの圧縮による高周波部分の画像の視認性の悪化を防ぐことができる。また、全体的に圧縮効率が高い画像を生成することができる。
また、文字領域として抽出された領域に対してＯＣＲなどを行い、文字領域のみを文書に変換する技術が知られている。
【０００３】
また、本発明に関連する技術として文字領域に対し複数色を割当てる画像処理装置、画像処理方法並びにその記憶媒体（特開２００３−００８９０９号公報）が知られている。
【特許文献１】特開２００３−００８９０９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかし、上述したようなレイアウト解析、各領域に対する画像処理、ＯＣＲなどの処理は、負荷が大きく時間が掛かる処理である。加えて、レイアウト解析や文字認識の正確性、作成される電子文書の画質を向上させることにより、さらに処理量が増えることになり、結果として電子文書を得るまでにかなりの時間を要する。
【０００５】
このような問題に対して、これらの処理を逐次的に処理するのではなく、複数プロセッサ、またはマルチコアプロセッサを用いて、領域ごとの処理をそれぞれのプロセッサに割り振り、処理を並列化することで処理時間を短縮する技術が知られている。
【０００６】
しかしながら、領域ごとの処理の並列化において、各領域に対する処理時間はそれぞれ異なっており、一定ではない。また、複数の演算リソースを効率的に使用するためには、各演算リソースに対する処理の負荷をバランスよくスケジューリングする必要がある。
【０００７】
本発明は上述した問題点を解決するためになされたものであり、レイアウト解析により抽出された各領域に対する処理を複数の演算リソースに効率的に割り当てることができる技術を提供することを目的とする。
【課題を解決するための手段】
【０００８】
上述した課題を解決するため、本発明の一態様に係る画像形成装置は、並列で動作する複数のプロセッサにより画像データを処理する装置であって、入力された画像データを受け付ける画像データ受付部と、前記画像データ受付部により受け付けられた画像データに基づいて、所定の領域からなるレイアウト構造を解析するレイアウト解析部と、前記レイアウト解析部により解析された前記画像データのレイアウト構造における所定の領域に対する処理量を算出する処理量算出部と、前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理量算出部により算出された処理量に基づいて、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振る処理プロセッサ決定部とを備えてなることを特徴とする構成としている。
【０００９】
また、本発明の一態様に係る画像処理装置は、並列で動作する複数のプロセッサにより画像データを処理する装置であって、入力された画像データを受け付ける画像データ受付部と、前記画像データ受付部により受け付けられた画像データに基づいて、所定の領域からなるレイアウト構造を解析するレイアウト解析部と、前記レイアウト解析部により解析された前記画像データのレイアウト構造における所定の領域に対する処理量を算出する処理量算出部と、前記レイアウト解析部により解析されたレイアウト構造における全ての領域に対する処理において、前記処理量算出部により算出された処理量に基づいて、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振る処理プロセッサ決定部とを備えてなることを特徴とする構成としている。
【００１０】
また、本発明の一態様に係る画像処理方法は、並列で動作する複数のプロセッサにより画像データを処理する方法であって、入力された画像データを受け付け、受け付けた画像データに基づいて、所定の領域からなるレイアウト構造を解析し、解析した前記画像データのレイアウト構造における所定の領域に対する処理量を算出し、算出した処理量に基づいて、解析されたレイアウト構造における全ての領域に対する処理において、前記複数のプロセッサのいずれかのプロセッサに前記所定の領域に対する処理を割り振ることを特徴とする構成としている。
【発明の効果】
【００１１】
以上に詳述したように本発明によれば、レイアウト解析により抽出された各領域に対する処理を複数の演算リソースに効率的に割り当てることができる技術を提供することができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明の実施の形態について図面を参照しつつ説明する。
【００１３】
（第１の実施の形態）
図１は、第１の実施の形態に係るコントローラを示すブロック図である。また、図２は、第１の実施の形態に係るプロセッサにおける機能ブロック図である。また、図３は、第１の実施の形態において解析される画像データである。また、図４は、第１の実施の形態における画像データの解析結果である。また、図５は、パラメータに対する評価値の算出例を示す表である。また、図６は、処理のスケジューリングの一例を示す図である。
【００１４】
図１に示すように、コントローラ１は、ＭＦＰ（Ｍｕｌｔｉｆｕｎｃｔｉｏｎ  Ｐｒｉｎｔｅｒ、画像形成装置）を制御するためのコントローラ（画像処理装置）であり、プロセッサ１０（複数のプロセッサ）、ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）２０、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）３０、Ｓｃａｎ  ＩＦ（Ｉｎｔｅｒｆａｃｅ）４０（画像データ受付部）を備える。プロセッサ１０は画像処理及びＭＦＰの制御に係る処理を行うものである。また、ＨＤＤ２０は、画像処理及びＭＦＰの制御に係る設定、プログラムなどを保存するものである。また、ＲＡＭ３０は、プロセッサ１０の処理に係るデータ、プログラムを一時的に格納するものである。また、Ｓｃａｎ  ＩＦ４０は、ＭＦＰのスキャナから取り込まれた画像データをコントローラ１に入力するためのインターフェイスである。
【００１５】
また、プロセッサ１０は、４つの同等なＰＥ（Ｐｒｏｃｅｓｓｏｒ  Ｅｌｅｍｅｎｔ）１０１〜１０４からなる対称型マルチプロセッサである。なお、このプロセッサ１０は、マルチコアプロセッサでも良く、またこのマルチコアプロセッサの構成はヘテロジニアスであっても、ホモジニアスであっても構わない。また、このプロセッサ１０は、非対称型マルチプロセッサであっても構わない。また、このプロセッサ１０のＰＥの数は複数であればいくつであっても構わない。
【００１６】
さらに、プロセッサ１０は、図２に示すレイアウト解析部２０１（処理量算出部）、画像処理部２０２、ＯＣＲ処理部２０３、処理時間測定部２０４、処理決定部２０５（処理プロセッサ決定部）を備える。具体的には、レイアウト解析部２０１、画像処理部２０２、ＯＣＲ処理部２０３、処理時間測定部２０４、処理決定部２０５はプログラムであり、ＨＤＤ２０や、例えばフラッシュＲＯＭなどの記憶媒体に格納されており、必要に応じてＲＡＭ３０上にロードされ、プロセッサ１０により実行されるものである。なお、上述したプログラムの実行において、図２に示す各部はＰＥ１０１〜１０４上で、それぞれ独立して実行される。以下、図２に示す各部について説明する。
【００１７】
まず、レイアウト解析部２０１について説明する。レイアウト解析部２０１は、Ｓｃａｎ  ＩＦ４０により入力された画像データのレイアウト構造を解析するものである。具体的には図３に示すような文章や画像による領域により構成された画像データを解析し、図４に示すように各領域が文字、画像、グラフィックスのいずれの領域であるか、そのタイプを判別する。例えば、レイアウト解析部２０１は、ある領域が画像領域かグラフィックス領域かを判別する際、写真のような矩形状の領域を画像とし、グラフのような矩形状ではない領域をグラフィックスとする。また、レイアウト解析部２０１は、領域内の色数に基づいて、ある領域が画像かグラフィックスかを判別しても構わない。
【００１８】
以下、レイアウト解析部２０１による具体的な文字領域の解析の一例を示す。まず、レイアウト解析部２０１は、画像データを輝度変換したものに対してヒストグラムをとり、このヒストグラムから閾値を算出する。次に、レイアウト解析部２０１は、この閾値に基づいて２値化を施し、２値化された画像データに対して輪郭線の抽出、ラベリング処理を用いて文字を識別し、抽出する。最後に、レイアウト解析部２０１は、この抽出された文字同士の間隔に基づいて文字領域を判別する。
【００１９】
また、レイアウト解析部２０１は、上述したような領域のタイプを判別した後、さらに各領域を解析し、各領域に対するパラメータ値をそれぞれ算出する。算出されるパラメータとしては、図５に示すように、面積（領域の面積／画像データの面積）、カラーモード（領域の階調数／ＭＦＰにおいて扱うことできる最大階調数）、領域タイプ（領域のタイプの処理量／最も重いタイプの処理量）、処理量（領域に対して実行する処理量の総和／最も重い処理の総和）、文字数（領域内の文字数／最大許容文字数）、文字列数（領域内の文字列数／最大許容文字列数）がある。なお、領域タイプにおける領域のタイプの処理量、最も重いタイプの処理量、また処理量における領域に対して実行する処理量の総和、最も重い処理の総和は、処理時間測定部２０４により算出されるものであり、これらの算出方法については後述する。
【００２０】
上述したこれらのパラメータ値は、図５の備考に示すように０〜１の間で正規化された値となる。なお、文字数及び文字列に関しては、領域が文字領域でない場合は無条件に値は１となる。レイアウト解析部２０１は、これら全ての値を乗算することで領域に対する評価値を算出する。よって、領域が文字領域ではない場合に文字数及び文字列のパラメータ値を１とすることにより、これらの値は評価値に影響しない。レイアウト解析部２０１により算出された領域に対する評価値もまた、０〜１の間で正規化されたパラメータ値の乗算の結果である為、０〜１の間で正規化された値となることによって、領域の処理重みに係る処理の負担を軽減することができる。なお、この評価値は、その値が高い程、対象とする領域に対する処理が重いことを示し、値が低い程、対象とする領域に対する処理が軽いことを示すものである。
【００２１】
次に、画像処理部２０２及びＯＣＲ処理部２０３について説明する。画像処理部２０２は、レイアウト解析部２０１により解析された各領域に対して、画像処理を行うものである。具体的には、あてがわれた領域の視認性を損なわない方式による圧縮及びフィルタ処理を実行する。例えば、領域のタイプが画像である場合はＪＰＥＧで圧縮し、領域のタイプがグラフィックスである場合はＧＩＦで圧縮し、領域のタイプが文字であり、且つＯＣＲを実行しない場合は、ＭＭＲなどの２値圧縮技術で圧縮する。また、ＯＣＲ処理部２０３は、文字領域に対してＯＣＲを実行するものである。なお、画像処理部２０２及びＯＣＲ処理部２０３は、処理決定部２０５の指示に基づいて上述した処理を実行する。また、画像処理部２０２は、画像データにおける全ての領域に対する処理が完了すると、全ての領域を最終的にマージする。
【００２２】
次に、処理時間測定部２０４について説明する。処理時間測定部２０４は、画像処理部２０２及びＯＣＲ処理部２０３による処理時間を測定し、測定した処理時間、つまりそれぞれのＰＥ１０１〜１０４における処理量をＨＤＤ２０に保存するものである。なお、本実施の形態において、ＰＥ１０１〜１０４は同様のＰＥであるため、処理時間測定部は、処理負荷を測定しても構わないが、プロセッサ１０が異なるＰＥにより構成される場合は、処理時間を測定する必要がある。
【００２３】
また、処理時間測定部２０４は、測定し保存した処理量から、図５に示した“対象領域の重み”、“領域タイプの最大重み”、“対象領域の処理の重みの総和”、“処理の最大重みの総和”を算出し、ＨＤＤ２０に保存するものである。“対象領域の重み”及び“領域タイプの最大重み”は、領域（文字、画像、グラフィックス）別に過去の処理量の平均が求められることで算出される。例えばパラメータ値が算出される対象が画像領域であり、最も処理量の平均値が高い領域が文字領域である場合、“対象領域の重み”は画像領域の処理量の平均値となり、“領域タイプの最大重み”は文字領域の処理量の平均値となる。また、“対象領域の処理の重みの総和”及び“処理の最大重みの総和”は、各種圧縮処理、ＯＣＲ処理別に過去の処理量の総和が求められることで算出される。例えばパラメータ値が算出される対象が画像領域であり、最も処理量の総和が高い処理がＯＣＲ処理である場合、“対象領域の処理の重みの総和”はＪＰＥＧ圧縮の処理量の総和となり、“処理の最大重みの総和”はＯＣＲ処理の処理量の総和となる。
【００２４】
次に処理決定部２０５について説明する。処理決定部２０５は、処理のスケジューリングを行うものであり、具体的には、各種圧縮処理、ＯＣＲ処理を各ＰＥ１０１〜１０４に割り振るものである。以下、処理のスケジューリングについて図６を用いて説明する。なお、図６における異なるスケジューリング処理である処理Ａ及び処理Ｂにおいて、１〜１０で示される各種処理はＰＥ１及びＰＥ２の２つのＰＥによりなされているものとする。また、図６において、処理１は１秒掛かる処理であり、処理２〜１０は、０．１秒掛かる処理であるものとする。
【００２５】
図６に示す処理Ａは、それぞれの処理１〜１０に掛かる処理時間を考慮せずに、各処理１〜１０に対して、処理１をＰＥ１、処理２をＰＥ２、処理３をＰＥ１…というように交互に割り振っている。しかし、処理１は処理２〜１０とは掛かる時間が異なるため、最終的にはＰＥ１における処理時間の総和は１．４秒となり、ＰＥ２における処理時間の総和は０．５秒となり、結果としてＰＥ１とＰＥ２における処理時間の総和には０．９秒の差が生じることとなる。この差により、ＰＥ２はＰＥ１における処理が終了するまで何も処理をせずに待つことになる。このようにＰＥ１とＰＥ２の処理時間の総和の差が開く程、処理１〜１０に対する処理時間は増大してしまう。
【００２６】
これに対して処理Ｂは、処理１〜１０それぞれの処理時間を考慮し、ＰＥ１とＰＥ２の処理時間の総和の差が最小となるように、処理１〜１０が割り振られたスケジューリング処理である。このように処理１〜１０をＰＥ１及びＰＥ２に割り振ることにより、処理Ａに比べて全体的な処理時間を０．４秒短縮することができる。
【００２７】
処理決定部２０５は、上述した処理Ｂのように、処理１〜１０のそれぞれの処理時間を加味することで、ＰＥ１０１〜１０４間の処理時間の差が最小になるようにスケジューリングを行うものである。
【００２８】
次に、本実施の形態に係る割り当て処理について説明する。図７は、割り当て処理の動作を示すフローチャートである。なお、図７において、画像データのレイアウト構造はすでに解析されているものとする。また、図７において、領域は、領域に係る処理を示すものとする。
【００２９】
まず、処理決定部２０５は、全ての領域がＰＥ１０１〜１０４に割り当てられたかを判断する（Ｓ１０１）。
【００３０】
ＰＥ１０１〜１０４に割り当てられていない領域（未割り当て領域）がある場合（Ｓ１０１，ＮＯ）、処理決定部２０５は、未割り当て領域のうち、いずれかの領域を選択する（Ｓ１０２）。
【００３１】
処理決定部２０５により未割り当て領域が選択されると、レイアウト解析部２０１は、処理決定部２０５により選択された未割り当て領域の評価値を算出する（Ｓ１０３）。
【００３２】
レイアウト解析部２０１により未割り当て領域の評価値が算出されると、処理決定部２０５は、ＰＥ１０１〜１０４のうち、既に割り当てられた領域の評価値の総和が最小であるＰＥを選択し（Ｓ１０４）、選択したＰＥに対して未割り当て領域を割り当て（Ｓ１０５）、選択したＰＥに既に割り当てられた領域の評価値の総和に割り当てた領域の評価値を加え（Ｓ１０６）、再度、全ての領域がＰＥ１０１〜１０４のいずれかに割り当てられたかを判断する（Ｓ１０１）。
【００３３】
また、ステップＳ１０１において、全ての領域がＰＥ１０１〜１０４のいずれかに割り当てられている場合（Ｓ１０１，ＹＥＳ）、処理決定部２０５は、画像データに係る割り当て処理を終了する。
【００３４】
上述したように、本実施の形態に係るコントローラ１は、画像データの各領域に係る処理負荷を算出し、算出した処理負荷を加味して各領域に係る処理をＰＥ１０１〜１０４間の処理負荷の総和の差が最小となるようにＰＥ１０１〜１０４に割り当てることにより、各領域に係る処理を高速に処理することができる。
【００３５】
（第２の実施の形態）
続いて、本発明の第２の実施の形態について説明する。
【００３６】
本実施の形態は、各領域の圧縮やＯＣＲ処理に係る各パラメータに対する重み付け係数である重要度を付加し、この重要度を加味して領域に係る処理の評価値を算出する点が第１の実施の形態とは異なる。また、この第１の実施の形態との相違に伴って、処理プロセッサ１０上で実行される機能の構成及び動作が第１の実施の形態とは異なる。以下、第１の実施の形態とは異なる構成及び動作について説明する。図８は、第２の実施の形態に係るコントローラにおける機能ブロック図である。また、図９は、各パラメータに付加された重要度の例を示す図である。
【００３７】
図８に示すように、プロセッサ１０は、レイアウト解析部２０１、画像処理部２０２、ＯＣＲ処理部２０３、処理時間測定部２０４、処理決定部２０５に加えて、重要度決定部２０６（重要度変更部）を備える点が第１の実施の形態とは異なる。重要度決定部２０６は、図９に示すような、各領域の圧縮やＯＣＲ処理に係る各パラメータに対して付加されている重要度を決定するものである。
【００３８】
ここで、重要度について説明する。重要度は、各パラメータに対して付加されており、評価値と同様に０〜１に正規化された値である。この重要度は、０〜１で示される全てのパラメータに対して、重み付けを行うための値である。この重要度は、重要度決定部２０６により画像データに対する処理毎に決定されるものであり、その値が調整されることにより、より適切な各領域に対する処理の評価値を算出するためのものである。
【００３９】
また、本実施の形態において、画像処理部２０２、ＯＣＲ処理部２０３、処理時間測定部２０４、処理決定部２０５に関しては第１の実施の形態と同様の動作であるが、レイアウト解析部２０１の動作が第１の実施の形態とは異なる。具体的には、各領域に対する処理の評価値を算出する際に、処理に係るパラメータに重要度を乗算し、重要度を乗算したパラメータを乗算する点が第１の実施の形態とは異なる。
【００４０】
次に、本実施の形態に係る重要度決定処理について説明する。図１０は、重要度決定処理の動作を示すフローチャートである。
【００４１】
まず、重要度決定部２０６は入力された画像データが全て処理されたかどうかを判断する（Ｓ２０１）。
【００４２】
入力された画像データが全て処理されていない場合（Ｓ２０１，ＮＯ）、重要度決定部２０６は、各領域に対する処理に係るパラメータのうち、いずれかのパラメータを選択し、選択したパラメータの重要度を変更する（Ｓ２０２）。なお、ここで選択されるパラメータはランダムに選択されても良いし、所定の順序に従って選択されても良い。
【００４３】
重要度が変更され、画像処理部２０２、ＯＣＲ処理部２０３により画像データを構成する各領域に対する処理がなされると、重要度決定部２０６は、処理時間測定部２０４によりＰＥ１０１〜１０４において測定された、この処理において最も処理負荷が大きいＰＥと、最も処理負荷が小さいＰＥのそれぞれの処理量を取得し、この処理量の差分を差分値として算出する（Ｓ２０３）。
【００４４】
差分値を算出した重要度決定部２０６は、直前に入力された画像データの処理における差分値（過去差分値）と、ステップＳ２０３により算出された差分値（現在差分値）とを比較し、過去差分値が現在差分値よりも大きいかどうかを判断する（Ｓ２０４）。なお、この判断における過去差分値は、直前に入力された画像データの処理における差分値でなくても良く、さらに前に入力された画像データの処理における差分値であっても良く、過去の記録を参照することにより、重要度決定部２０６は、より良い重要度の組み合わせを選択することができる。
【００４５】
過去差分値が現在差分値よりも大きい場合（Ｓ２０４，ＹＥＳ）、重要度決定部２０６は、現在の重要度の組み合わせを選択する（Ｓ２０５）。
【００４６】
一方、過去差分値が現在差分値以下である場合（Ｓ２０４，ＮＯ）、重要度決定部２０６は、直前の画像データの処理における重要度の組み合わせを選択する（Ｓ２０６）。
【００４７】
以上説明したように画像データを構成する領域の処理に係る各パラメータに対して重要度を付加し、画像データに対する処理毎に重要度を変更し、よりＰＥ間の処理時間の差分が低い重要度の組合せを選択することによって、例えば、同じレイアウト構成の画像データが連続して入力されることで、徐々にスケジューリングが最適化され、より効率的に画像データに対する処理を実行することができる。
【００４８】
なお、上述した各実施の形態において、画像データに対する処理時間がスケジューリングのための処理時間を下回るような場合は、スケジューリングを行わなくても良い。また、ＰＥ１０１〜１０４は、それぞれ二値画像、カラー画像、ビット演算など、特定の処理を行うために特化されたＰＥを用いても良い。また、１つの領域に対する処理を複数のＰＥ１０１〜１０４により分担しても良い。また、本実施の形態において、上述した動作はＭＦＰにおいて実行されることを想定したが、例えばマルチプロセッサを備え、スキャナと接続されたパーソナルコンピュータ上で実行されても良い。
【００４９】
本発明を特定の態様により詳細に説明したが、本発明の精神および範囲を逸脱しないかぎり、様々な変更および改質がなされ得ることは、当業者には自明であろう。
【００５０】
以上に詳述したように本発明によれば、レイアウト解析により抽出された各領域に対する処理を複数の演算リソースに効率的に割り当てることができる技術を提供することができる。
【図面の簡単な説明】
【００５１】
【図１】第１の実施の形態に係るコントローラを示すブロック図である。
【図２】第１の実施の形態に係るプロセッサにおける機能ブロック図である。
【図３】第１の実施の形態において解析される画像データである。
【図４】第１の実施の形態における画像データの解析結果である。
【図５】パラメータに対する評価値の算出例を示す表である。
【図６】処理のスケジューリングの一例を示す図である。
【図７】割り当て処理の動作を示すフローチャートである。
【図８】第２の実施の形態に係るプロセッサにおける機能ブロック図である。
【図９】各パラメータに付加された重要度の例を示す図である。
【図１０】重要度決定処理の動作を示すフローチャートである。
【符号の説明】
【００５２】
１  コントローラ、１０  プロセッサ、２０  ＨＤＤ、３０  ＲＡＭ、４０  Ｓｃａｎ  ＩＦ、１０１〜１０４  ＰＥ、２０１  レイアウト解析部、２０２  画像処理部、２０３  ＯＣＲ処理部、２０４  処理時間測定部、２０５  処理決定部。
【図１】
2009110499.tif 000003
【図２】
2009110499.tif 000004
【図３】
2009110499.tif 000005
【図４】
2009110499.tif 000006
【図５】
2009110499.tif 000007
【図６】
2009110499.tif 000008
【図７】
2009110499.tif 000009
【図８】
2009110499.tif 000010
【図９】
2009110499.tif 000011
【図１０】
2009110499.tif 000012