(57)【特許請求の範囲】
【請求項１】
複数のオブジェクトの位置属性に関する情報と位置属性以外の属性に関する情報とを保持し、ベクター形式で表わされる選択側画像データと既存画像データ間の類似度を評価する、コンピュータが実行する画像情報処理方法であって、
既存デザインＤＢに、類似度の評価対象となるデザインを蓄積・記録するステップ、
ユーザがオブジェクトを操作した際にOS、アプリケーションから生じるイベント情報を基に、選択された画像データにおいて検索キーとなる複数のオブジェクトの属性を取得する選択オブジェクト属性取得部が、前記選択した検索キーとなるオブジェクトについて位置属性以外の各属性を取得するステップ、
オブジェクトの属性間の距離、オブジェクト間の距離、デザイン間の距離を計算して部分的なデザイン間の類似度を評価する類似度算出部が、
これら各属性間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の距離の総和を表わす割当によるコストを定式化するステップ、
前記既存画像データ中のオブジェクトについて位置属性を取得するステップ、
前記位置属性を取得したオブジェクト間の位置ズレによるコストを定式化するステップ、
前記オブジェクトの割当によるコストと前記オブジェクト間の位置ズレによるコストの和の最小値を数理計画問題として最適解を算出するステップ、
前記最適解の各変数値から前記画像データ間の特徴量の差を表わす距離を算出するステップ、
表示制御部が、前記類似度順の情報に基づいて前記デザインおよびオブジェクトを表示装置に表示するステップ
とからなる画像情報処理方法。
【請求項２】
複数のオブジェクトの位置属性に関する情報と位置属性以外の属性に関する情報とを保持し、ベクター形式で表わされる選択側画像データと既存画像データ間の類似度を評価するための、コンピュータが実行する画像情報処理方法であって、
既存デザインＤＢに、類似度の評価対象となるデザインを蓄積・記録するステップ、
ユーザがオブジェクトを操作した際にOS、アプリケーションから生じるイベント情報を基に、選択された画像データにおいて検索キーとなる複数のオブジェクトの属性を取得する選択オブジェクト属性取得部が、前記選択した検索キーとなるオブジェクトに対して位置属性以外の各属性を取得するステップ、
オブジェクトの属性間の距離、オブジェクト間の距離、デザイン間の距離を計算して部分的なデザイン間の類似度を評価する類似度算出部が、
これら各属性間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の距離の総和を表わす割当によるコストを定式化するステップ、
前記既存画像データ中のオブジェクトについて位置属性を取得するステップ、
前記選択側画像データから、１つの検索キーとなるオブジェクトを取り出して、前記既存画像データの全オブジェクト（総数＝ｎ）との組み合わせPair(１，１), Pair(１，２), ・・・, Pair(１，ｎ)に対して、
前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)に対する位置ずれで、前記選択側画像データを平行移動するステップ、
前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定して、残りのオブジェクトの組み合わせを求めるステップ、
前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定した組み合わせの中で、最も類似する組み合わせを近似解とし、
前記近似解から前記画像データ間の特徴量の差を表わす距離を算出するステップ、
表示制御部が、前記類似度順の情報に基づいて前記デザインおよびオブジェクトを表示装置に表示するステップ
とからなる画像情報処理方法。
【請求項３】
複数のオブジェクトの位置属性に関する情報と位置属性以外の属性に関する情報とを保持し、ベクター形式で表わされる選択側画像データと既存画像データ間の類似度を評価するための、コンピュータが実行する画像情報処理方法であって、
既存デザインＤＢに、類似度の評価対象となるデザインを蓄積・記録するステップ、
ユーザがオブジェクトを操作した際にOS、アプリケーションから生じるイベント情報を基に、選択された画像データにおいて検索キーとなる複数のオブジェクトの属性を取得する選択オブジェクト属性取得部が、前記選択した検索キーとなるオブジェクトについて位置属性以外の各属性を取得するステップ、
して、これら各属性間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の特徴量の差を表わす距離を算出するステップ、
前記検索キーとなるオブジェクト間の距離の総和を表わす割当によるコストを定式化するステップ、
前記既存画像データ中のオブジェクトについて位置属性を取得するステップ、
前記位置属性を取得したオブジェクト間の位置ズレによるコストを定式化するステップ、
前記選択側画像データから、１つの検索キーとなるオブジェクトを取り出して、前記既存画像データの全オブジェクト（総数＝ｎ）との組み合わせPair(１，１), Pair(１，２), ・・・, Pair(１，ｎ)に対して、
前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)に対する位置ずれで、前記選択側画像データを平行移動するステップ、
前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定して、残りのオブジェクトの組み合わせを求め、前記Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定した組み合わせの中で最も類似する組み合わせを求めるステップ、
前記オブジェクトの割当によるコストと、前記オブジェクト間の位置ズレによるコストの和の最小値を数理計画問題として、最適解を算出するステップ、
前記最適解の各変数値から前記画像データ間の特徴量の差を表わす距離を算出するステップ、
表示制御部が、前記類似度順の情報に基づいて前記デザインおよびオブジェクトを表示装置に表示するステップ
とからなる画像情報処理方法。
【請求項４】
前記選択したオブジェクトを検索キーとし、既存画像データ中のオブジェクトに対する類似度の検索結果を、類似度の降順に提示するステップを有する請求項１乃至請求項３のいずれか1項に記載の画像情報処理方法。
【請求項５】
前記検索キーとして選択したオブジェクトを、前記降順に提示した前記既存画像データの中からユーザに選択されたオブジェクトに置換する請求項４記載の画像情報処理方法。
【請求項６】
前記置換処理に際し、オブジェクトが持ついずれの属性に重み付けがされたかを、プロファイルを作成して管理する請求項５記載の画像情報処理方法。
【請求項７】
前記置換処理に際し、類似度の降順で上位のオブジェクトでなく、低位の類似度のオブジェクトが選択された場合、前記検索キーとして選択したオブジェクトと前記置換に選択されたオブジェクトとの距離を小さくするように重み付けを修正し、前記検索キーとして選択したオブジェクトと前記上位のオブジェクトとの距離を大きくするように重み付けを修正する請求項６記載の画像情報処理方法。
【請求項８】
前記位置属性以外の属性は、オブジェクトの種類、オブジェクトの色、テキストの文字列のいずれかである請求項１乃至請求項３のいずれか1項に記載の画像情報処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像情報処理方法に関する。
【背景技術】
【０００２】
現在、多種のオブジェクトやオブジェクトのレイアウト情報を保持した画像データが取り扱われ、画像データとしては、ベクター形式の画像データが多用されている。ベクター形式の画像データ間で、類似しているか否かの評価を必要とする場合がある。
【０００３】
例えば、ベクター形式の画像データに対して、オブジェクトの関係を「隣接」、「包含」、「排他」に分けてグラフを作成し、グラフのマッチングによって類似度を計算することが提案されている（例えば、特許文献１参照。）。
【０００４】
画像データ間の類似度を評価する場合に、評価対象となる画像データ上の場所が異なっていたり、評価対象となる画像データに余分な部分を含んでいたりする場合、正しく類似度を評価することができない。特に、画像データ間の一部分同士の類似度を評価することは容易ではない。すなわち、オブジェクトを配置するような画像データに対して、複数のオブジェクトを検索キーとして選択し、割り当てるオブジェクト間の配置関係を考慮して、類似度を測定するには、検索キーとして選択できるオブジェクトは、包含（親子）関係にあるものに限られる、割り当てるオブジェクト間の配置属性とその他の属性（色, オブジェクトの種類, テキストの文字列等）の重要度を自由に変更できない、正確に取得できる位置（やサイズ）情報を直接利用できず、精度が落ちる、という問題があった。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特開２００５−１４１７７６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００６】
本発明が解決しようとする課題は、部分的な画像データ間の類似度を正しく評価することのできる画像情報処理方法を提供することである。
【課題を解決するための手段】
【０００７】
実施形態の画像情報処理方法は、複数のオブジェクトの位置属性に関する情報と位置属性以外の属性に関する情報とを保持し、ベクター形式で表わされる選択側画像データと既存画像データ間の類似度を評価する、コンピュータが実行する画像情報処理方法であって、既存デザインＤＢに、類似度の評価対象となるデザインを蓄積・記録するステップ、ユーザがオブジェクトを操作した際にOS、アプリケーションから生じるイベント情報を基に、選択された画像データにおいて検索キーとなる複数のオブジェクトの属性を取得する選択オブジェクト属性取得部が、前記選択した検索キーとなるオブジェクトについて位置属性以外の各属性を取得するステップ、オブジェクトの属性間の距離、オブジェクト間の距離、デザイン間の距離を計算して部分的なデザイン間の類似度を評価する類似度算出部が、これら各属性間の特徴量の差を表わす距離を算出するステップ、前記検索キーとなるオブジェクト間の特徴量の差を表わす距離を算出するステップ、前記検索キーとなるオブジェクト間の距離の総和を表わす割当によるコストを定式化するステップ、前記既存画像データ中のオブジェクトについて位置属性を取得するステップ、前記位置属性を取得したオブジェクト間の位置ズレによるコストを定式化するステップ、前記オブジェクトの割当によるコストと前記オブジェクト間の位置ズレによるコストの和の最小値を数理計画問題として最適解を算出するステップ、前記最適解の各変数値から前記画像データ間の特徴量の差を表わす距離を算出するステップ、表示制御部が、前記類似度順の情報に基づいて前記デザインおよびオブジェクトを表示装置に表示するステップとからなる。
【図面の簡単な説明】
【０００８】
【図１】本実施形態に係る画像情報処理方法が適用される画像情報処理装置の構成例を示す図である。
【図２】第１の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。
【図３】オブジェクトの組み合わせを説明する図である。
【図４】各属性の取得を説明する図である。
【図５】検索キーとなるオブジェクトと既存の画像データ上のオブジェクトの比較を説明する図である。
【図６】属性間の距離を計算する組み合わせを説明する図である。
【図７】オブジェクト間の距離を計算する組み合わせを説明する図である。
【図８】オブジェクトの組み合わせを変数としたときの一例を示す図である。
【図９】デザイン間の位置ズレによるコストの算出を説明する図である。
【図１０】オブジェクトの割当コストを説明する図である。
【図１１】重み付けの反映を説明する図である。
【図１２】ユーザ別の重み管理テーブルの一例である。
【図１３】重み付けの学習の処理の流れを示すフローチャートである。
【図１４】本実施形態による検索機能及び置換機能を模式的に示した図である。
【図１５】第２の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。
【図１６】オブジェクトの取り出しを説明する図である。
【図１７】オブジェクトの組み合わせを説明する図である。
【図１８】デザインＱの平行移動を説明する図である。
【図１９】残りのオブジェクトの組み合わせを説明する図である。
【図２０】最も類似する組み合わせPair(１，２)が解となることを説明する図である。
【図２１】第３の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。
【発明を実施するための形態】
【０００９】
以下、本発明の一実施の形態について、図面を参照して説明する。尚、各図において同一箇所については同一の符号を付すとともに、重複した説明は省略する。
【００１０】
（第１の実施形態）
まず、本実施形態で用いる主要な用語について説明する。
【００１１】
「デザイン」とは、オブジェクトやオブジェクトのレイアウト情報を保持する画像データをいう。本実施形態で対象とするデザインは、ベクター形式の画像データである。ベクター形式では、図形の情報（色やカタチ、位置情報など）をすべて数値（数式）によって管理している。ベクター形式の画像データを扱うソフトウエアとしては、例えば、Illustrator（登録商標）, Fireworks（登録商標）, Flash（登録商標）といったグラフィックソフトがある。また、資料のプレゼンテーション用のソフトウエアとして、PowerPoint（登録商標）がある。したがって、デザインの典型例が、PowerPoint（登録商標）のスライドや、Illustrator（登録商標）, Fireworks（登録商標）のページ等のオブジェクトやレイアウト情報を保持する画像データである。また、ビットマップ形式の画像データであっても、OCRのレイアウト解析等によって、オブジェクトを認識できれば、本発明は適応できる。
【００１２】
「距離」とは、パターン認識の分野で特徴量の差を表す概念であり、距離が小さいほど類似度は大きい。
【００１３】
本実施形態は、デザイン上のある部分を選択したとき、選択部分と既存デザインの任意の対応部分間の類似度を評価する、すなわち、部分一致を評価するものである。したがって、部分的なデザインと既存デザインの対応部分は、デザイン上で場所が異なっていても、影響を受けない。また、既存デザインに余分な部分を含んでも、影響を受けない。
【００１４】
さらに、部分的なデザインと既存のデザイン間の類似度の評価者（画像情報処理方法のユーザ）の操作状況に合わせたパラメータを学習させ、評価をより正確に実行させることもできる。例えば、部分的なデザインの配置のパラメータを重視する場合や、オブジェクトの種類や色のパラメータを重視する場合がある。
【００１５】
さらに、本実施形態に係る画像情報処理方法は、検索機能と置換機能を実行させることができる。検索機能では、デザイン中から任意の箇所を検索キーとして選択し、既存デザインに対して、検索を実行し、類似度順に候補となるデザインを出力し、操作者（ユーザ）が出力されたデザインを選択することにより、類似デザインを獲得する。置換機能では、操作者（ユーザ）が類似デザインを選択し、置換指示が行なわれた場合に、選択部分のみを類似デザインに置換する。
【００１６】
図1は、本実施形態に係る画像情報処理方法が適用される画像情報処理装置の構成例を示す図である。
【００１７】
画像情報処理装置１００は、入力装置１０、選択オブジェクト属性取得部２０、ユーザ操作情報データベース(以下、ユーザ操作情報ＤＢという)３０、既存デザインデータベース(以下、既存デザインＤＢという)４０、類似度算出部５０、重み付け学習部６０、表示制御部７０、表示装置８０から構成されている。このうち、選択オブジェクト属性取得部２０、類似度算出部５０、重み付け学習部６０、表示制御部７０の各部は、例えば各処理プログラムの形態として構築することができる。また、画像情報処理装置１００を例えば、情報端末装置として組み立てる場合には、図示しない記憶部やプロセッサを具備させることもできる。
【００１８】
まず、各部を簡潔に説明する。入力装置１０は、例えばマウスやキーボードで構成され、ユーザがデザインや、デザイン中のオブジェクトを操作する際の操作指令を入力するものである。
【００１９】
選択オブジェクト属性取得部２０は、ユーザがオブジェクトを操作した際にOS、アプリケーションから生じるイベント情報を基に、選択されたオブジェクトの属性を取得するものである。属性については、後述する。
【００２０】
ユーザ操作情報ＤＢ３０は、選択オブジェクト属性取得部２０で取得されたユーザ操作履歴をユーザ毎にデータベースとして記録するものである。
【００２１】
既存デザインＤＢ４０は、類似度の評価対象となるデザインを蓄積して記録するものである。
【００２２】
類似度算出部５０は、オブジェクトの属性間の距離、オブジェクト間の距離、デザイン間の距離を計算して部分的なデザイン間の類似度を評価するものである。類似度評価の詳細は、後述する。
【００２３】
重み付け学習部６０は、ユーザの嗜好や状況に合わせたパラメータを学習させるものである。重み付けの詳細は、後述する。
【００２４】
表示制御部７０は、入力装置１０からの指令、類似度算出部５０で算出した類似度順の情報に基づいて、表示装置８０に表示させるように出力情報を制御するものである。
【００２５】
表示装置８０は、例えばPCや携帯端末装置のディスプレイなどで、表示制御部７０の制御によりデザインやオブジェクトを表示する。
【００２６】
次に、以上のように構成された画像情報処理装置による画像情報処理方法について説明する。図２は、第１の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。まず初めに、検索キーとなる複数のオブジェクトと既存の画像データ上のオブジェクトに対して、以下のステップＳ２０１以降を実行する。ここで、用語を説明する。検索キーとなる（複数の）オブジェクトとは、任意のデザインを一枚選び、その中で、ユーザが選択した複数個のオブジェクトのこと（１，２，・・・，ｍ）である。既存デザインとは、Ｘ枚のデザインから１枚づつ取り出したデザインをいう。既存デザイン上のオブジェクトとは、既存デザインｘ (１≦ｘ≦Ｘ)上の全オブジェクトのこと（１，２，・・・，ｎ）である。また、組み合わせは、ユーザが選択した複数個のオブジェクトと既存デザインx上の全てのオブジェクトの総当たり（ｎ×ｍの組み合わせ）に対して行う。図３は、オブジェクトの組み合わせを説明する図である。
【００２７】
上述のことを前提として、処理の流れを説明する。まず、検索キーとなるオブジェクトと既存の画像データ上のオブジェクトについて、位置属性を除く各属性を取得する（ステップＳ２０１）。次に、位置属性を除く各属性間の距離を計算する（ステップＳ２０２）。
【００２８】
次いで、オブジェクト間の距離を計算する（ステップＳ２０３）。次いで、オブジェクトの割当によるコストを定式化する（ステップＳ２０４）。
【００２９】
一方、検索キーとなるオブジェクトと既存の画像データ上のオブジェクトについて、位置属性を取得する（ステップＳ２０５）。位置属性は、全てのオブジェクトについて取得する。次に、位置ズレ（トポロジーの非類似度）によるコストを定式化する（ステップＳ２０６）。次に、Min｛オブジェクトの割当によるコスト＋Ｗ×位置ズレ（トポロジーの非類似度）によるコスト｝を数理計画問題として解くことで全ての組み合わせを計算することなく最適解を計算する（ステップＳ２０７）。尚、Ｗは位置属性による重みを示す。そして、数理計画問題の解から、デザイン間の距離を算出する（ステップＳ２０８）。
【００３０】
以下に、それぞれのステップについて詳述する。
【００３１】
まず、オブジェクトの属性について説明する。オブジェクトの持つ属性の種類としては、例えば、オブジェクトの種類（ｂ）, 幅高さ（ａ）, 位置（ｃ）がある。尚、（ａ）は数値の属性を示し、（ｂ）は数値以外の属性を示し，（ｃ）は例外的な計算をする属性を示すが詳細は後述する。これらの属性は、いずれのオブジェクトも共通的に備えるものである。オブジェクト独自（独特）の属性としては、テキストオブジェクトは、例えば、文字の色（ｃ）, フォントサイズ（ａ）, 文字列（ｂ）の属性を備えている。矩形オブジェクトは、例えば、枠の色（ｃ）, 塗潰し色（ｃ）, 枠の幅（ａ） の属性を備えている。パスオブジェクトは、線の色（ｃ）, 線の太さ（ａ） の属性を備えている。
【００３２】
オブジェクトの種類が複数ある場合は、オブジェクトの種類属性を最低限取得する。図４は、各属性の取得を説明する図である。
【００３３】
次に、距離について説明する。距離は、上述のように定義できるが、本実施形態では、（１）属性間の距離、（２）オブジェクト間の距離、（３）デザイン間の距離を取り扱う。
【００３４】
＜属性間の距離＞
属性間の距離を計算するには、例えば、数値の属性（ａ），数値以外の属性（ｂ），例外的な計算をする属性（ｃ）を考慮することができる。数値の属性（ａ）は、数値間の差の絶対値である。数値以外の属性（ｂ）は、例えば, 一致すれば０, 一致しなければ1で表わす。例外的な計算をする属性（ｃ）には、特別な測定が必要である。例えば、色関連では、色相、彩度、明度の３成分からなるＨＳＶ成分に分解して、各要素の数値差の絶対値の和を考慮する。尚、ＨＳＶからＲＧＢへ変換して取り扱ってもよい。
【００３５】
尚、属性の種類，属性間の距離は上述のものに限られず、あくまでも一例である。
【００３６】
図５は、検索キーとなるオブジェクトと既存の画像データ上のオブジェクトの比較を説明する図である。図５において、左側のオブジェクト（色は青色とする）は、オブジェクトの種類：矩形、幅高さ：（５，１０）、色：（０，０，２５５)である。一方、右側のオブジェクト（色は緑色とする）は、オブジェクトの種類：矩形、幅高さ：（５，８）、色：（０，２５５，０)である。このような場合、比較するオブジェクトに対する各属性の距離は、次のようになる。
【００３７】
オブジェクトの種類：０、
幅高さ：|５−５|＋|１０−８|＝２、
色：|０−０|＋|０−２５５|＋|２５５−０|＝５００
属性間の距離は、検索キーとなるオブジェクトと既存デザイン上のオブジェクトの全て組み合わせに対して計算する。図６は、属性間の距離を計算する組み合わせを説明する図である。
【００３８】
＜オブジェクト間の距離＞
オブジェクト間の距離を算出するには、 比較する各デザイン上からオブジェクトを一つずつ選び距離を定義する。オブジェクト間の距離は、オブジェクトの各属性間の距離の重み付け線形和（重み付け平均）で表わされる（式１参照）。
【数１】
0005550533.tif 000002
【００３９】
各属性の重み付けは、学習により算出することができる（後述する）。また、比較するオブジェクト間において、片方のみのオブジェクトしか持たない属性は無視する。
【００４０】
オブジェクト間の距離の計算例を次に示す。重み付けが、オブジェクト種類：０．３、 幅高さ：０．４９９２、 色：０．０００８であり、比較するオブジェクトに対する各属性の距離が、オブジェクトの種類：０, 幅高さ：２、 色：５００であるとき、オブジェクト間の距離は、０．３×０＋０．４９８２×２ ＋０．０００８×５００＝１．３９８４となる。
【００４１】
オブジェクト間の距離も、検索キーとなるオブジェクトと既存デザイン上のオブジェクトの全て組み合わせに対して計算する。図７は、オブジェクト間の距離を計算する組み合わせを説明する図である。
【００４２】
＜オブジェクトの割当によるコスト＞
0005550533.tif 000003
【００４３】
定式化の段階では、オブジェクトの組み合わせ（割当） は未だ決まらない。 変数は、オブジェクトｉとオブジェクトｊが対応している場合１とし、対応していない場合は０とする。
【００４４】
例えば、検索キーとなるオブジェクトの総数ｍ＝３、が既存デザインのオブジェクトの総数ｎ＝４とすると、変数の値は、図８のようになる。
【００４５】
＜デザイン間の位置ズレによるコスト＞
次に、デザイン間の位置ズレによるコスト（トポロジーの非類似）について説明する。ここで、デザイン間とは、「選択部分のデザイン（Ｑ）」と「既存デザイン（Ｒ）」を指している。「選択部分のデザイン（Ｑ）」は、 ユーザ等が検索キーとしてデザインの中の複数オブジェクトを選択するが、これが「選択部分のデザイン（Ｑ）」である。また、 検索対象の画像データの任意の一枚（全体）を「既存デザイン（Ｒ）」という。選択部分のデザイン（Ｑ）や既存デザイン（Ｒ）は、複数のオブジェクトから構成されている。
【００４６】
オブジェクトの割当が分かっている場合、以下のようにコストを算出する。
【００４７】
まず、比較する２つのデザイン上に存在するオブジェクトの位置を中心座標で表す。次いで、選択部分のデザイン（Ｑ）を適当に平行移動し、既存デザイン（Ｒ）（の一部）のオブジェクトに重ね合わせる。選択部分のデザイン（Ｑ）と既存デザイン（Ｒ）(の一部)が完全に重ね合わされば、位置ズレのコストは０となる。ズレが生ずれば、そのズレの総和が位置ズレのコストの値になる。つまり、重ね合わせたオブジェクト同士の座標値のズレの合計を位置ズレによるコスト（トポロジーの非類似度）と定める。
【００４８】
図９は、デザイン間の位置ズレによるコストの算出を説明する図である。図９に示すように、選択部分のデザイン（Ｑ）と既存デザイン（Ｒ）間において、位置ズレのコストは、次式で示される。
【数２】
0005550533.tif 000004
ここで、（ｘ，ｙ）は平行移動量である。
尚、平行移動量とオブジェクトの割当は、後述の数理計画問題から最適値を算出し、最適組み合わせを決定する。
【００４９】
＜デザイン間の距離＞
デザイン間の距離は、選択部分のデザインと既存デザインとの「位置ズレによるコスト」と選択部分のデザインと既存デザインとのオブジェクトの「割当コスト」として表わされる２つの距離の重み付け線形和の最小値として定義することができる。「位置ズレによるコスト」は、選択部分のデザインと既存デザインとのトポロジーの非類似度である。また、「割当コスト」は、割り当てたオブジェクト間の距離の合計である。デザイン間の距離は、割り当てるオブジェクト数で正規化する。
【００５０】
図１０（ａ）は、オブジェクトの割当コストが大きい場合を説明する図で、図１０（ｂ）は、オブジェクトの割当コストが最小の場合を説明する図である。
【００５１】
0005550533.tif 000005
【数３】
0005550533.tif 000006
式４は、選択部分のデザイン（Ｑ）と既存のデザイン（Ｒ）との距離を定式化したものである。ここでは、デザインＱ，Ｒの少なくとも一方のオブジェクトを完全に割り当てる。
【００５２】
従来、オブジェクトの割当、すなわちオブジェクトの最適な対応関係を判定する手法として、各オブジェクトの座標やサイズの違いがなるべく小さくなるように、オブジェクトを割り当て、割り当てたオブジェクト間の差異の総和をデザイン間の距離とする（デザイン間の距離をオブジェクトの割当問題として解く）ことが提案されている。例えば、International Conference on Document Image Analysis for Libraries (DIAL 2006)において、Joost van Beusekom 他によって、“Distance Measures for Layout-Based Document Image Retrieval”として提案されている。これは、論文のレイアウトを対象コンテンツとし、オブジェクトが持つ属性として、座標値とサイズのみを仮定して、オブジェクトの割当をベースにした類似度を幾つか定義し、性能を評価するものである。係る手法では、定義された距離のいずれも、レイアウトの部分一致は考慮していない。すなわち、従来手法では、上述の式４において、Ｂで示されるオブジェクトの位置ズレによるコストが考慮されていない。
【００５３】
次いで、式４で示される数理計画問題を以下の手順で、混合整数線形計画問題（ＭＩＬＰ）へ変形する。
【数４】
0005550533.tif 000007
【００５４】
式４中の条件（２）に注意して、制約式(4’’),(5’’)が線形になるように更に変形する。ここで、Ｌは十分大きい正数である。
【数５】
0005550533.tif 000008
さらに、目的関数も線形になるように変形する。
【数６】
0005550533.tif 000009
【００５５】
以上の手順で、混合整数線形計画問題（ＭＩＬＰ）に変形した式をまとめると以下のようになる。
【数７】
0005550533.tif 000010
ここでは、デザインＱ，Ｒの少なくとも一方のオブジェクトを完全に割当る。
【００５６】
次に、混合整数線形計画問題（ＭＩＬＰ）の最適解の各変数値から、デザイン間の距離は、次式で定義することができる。
【数８】
0005550533.tif 000011
平行移動距離は、次式で求めることができる。
【数９】
0005550533.tif 000012
ｆｉ，ｊからオブジェクトの対応関係も得られる。
【００５７】
以上説明してきた本実施形態に係る画像情報処理方法による部分的なデザイン間の類似度評価手法は、次のような応用展開ができる。
【００５８】
デザイン中からあるオブジェクトを検索キーとして選択し、既存のデザインに対して検索を実行する。検索の結果、類似度の降順に既存デザインを提示する。選択部分のみを、提示された類似する既存デザインの中からユーザが選択したデザインに置換処理することができる。
【００５９】
＜重み付け＞
オブジェクト間の距離で使用する各属性の重みは、ユーザの嗜好や時々の状況によって変化する。そこで、ユーザの嗜好や時々の状況を反映させるように重み付けを行うことが好適である。ユーザの嗜好としては、例えば、オブジェクトの種類重視なのか、あるいはオブジェクトの色重視なのか，あるいはオブジェクトの配置重視なのかがある。オブジェクトｉ，ｊの属性ｐによる距離は、次式で表わされる。
【数１０】
0005550533.tif 000013
【００６０】
以降の説明では、ｐは位置属性及び位置属性以外の他の属性も表わすこととする。図１１は、重み付けの反映を説明する図である。尚、図１１中で、Rectは、矩形を表わしている。
【００６１】
また、ユーザや状況の切り替え時に不適切なパラメータ設定が起こらないように、ユーザや状況ごとにプロファイルを作成し、重みを別々に管理することも好適である。図１２は、ユーザ別の重み管理テーブルの一例である。
【００６２】
図１３は、重み付けの学習の処理の流れを示すフローチャートである。重み付けの学習は、例えば、図１３に示すように行うことができる。まず、デザイン間の類似度計算結果を表示する（ステップＳ１３１）。ユーザの操作から正解情報を抽出し、既存のデザインが類似度の降順にＡ，Ｂ，Ｃ，Ｄ，Ｅ・・・と得られたとき、Ａ，Ｂ，Ｃ，Ｄ，Ｅ・・・の順に表示する。次に、ユーザが所望の検索結果を選択する（ステップＳ１３２）。ユーザがあるデザイン（例えばＤ）を選択した時、以下のように学習させる。次に、学習モデルを実行する（ステップＳ１３３）。ユーザがＤを選択した場合、デザイン選択部分とＤとの距離を小さくするように重み付けを修正する。逆に、上位の候補でありながら、ユーザが選択しなかった場合（この例ではＡ，Ｂ，Ｃが該当）、デザイン選択部分とＡ，Ｂ，Ｃとの距離を大きくするように重み付けを修正する。
【００６３】
重み付けの学習モデルについて説明する。
0005550533.tif 000014
【数１１】
0005550533.tif 000015
【００６４】
本実施形態によれば、デザインデータ間の類似度を評価する場合、検索キーとして任意の複数オブジェクトを選択可能であり、割り当てるオブジェクト間の配置関係を考慮することができる。また、配置（やサイズ）の正確な情報を類似度に反映させ、割り当てるオブジェクト間の配置関係やその他の属性の重要度を柔軟に変更することができる。また、置換機能を実現することができる。
【００６５】
図１４は、本実施形態による検索機能及び置換機能を模式的に示した図である。
【００６６】
（第２の実施形態）
第２の実施形態は、近似アルゴリズムを使用してデザイン間の距離を算出するものである。図１５は、第２の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。まず初めに、検索キーとなる複数のオブジェクトと既存の画像データ上のオブジェクトに対して、以下のステップＳ１５０１以降を実行する。
【００６７】
検索キーとなるオブジェクトと既存の画像データ上のオブジェクトについて、位置属性を除く各属性を取得する（ステップＳ１５０１）。次に、位置属性を除く各属性間の距離を計算する（ステップＳ１５０２）。次いで、オブジェクト間の距離を計算する（ステップＳ１５０３）。尚、第１の実施形態と同様に、オブジェクト間の距離は、総当たりで計算する。
【００６８】
次いで、オブジェクトの割当によるコストを定式化する（ステップＳ１５０４）。ここのオブジェクトの割当は、総当たりではなく、以下詳述するように近似的に行う。
【００６９】
一方、検索キーとなるオブジェクトと既存の画像データ上のオブジェクトについて、位置属性を取得する（ステップＳ１５０５）。次に、近似アルゴリズムを使用してデザイン間の類似度の近似解を求める（ステップＳ１５０６）。そして、近似解をデザイン間の距離とする（ステップＳ１５０７）。
【００７０】
次に、近似アルゴリズムを説明する。上述した図２の方法では、オブジェクトの割当によるコストと位置ズレによるコストの数理計画問題（最小化問題）を解くことで、オブジェクトの最適な割当を導出して、デザイン間の距離を計算した。係る厳密なアルゴリズムによる場合には、かなりの処理時間を要する。そこで、オブジェクトの割当を最適に近い割当として求め、それを利用してデザイン間の距離を計算する手法が近似アルゴリズムである。
【００７１】
近似アルゴリズムは、以下の流れで行われる。
【００７２】
１．検索キーとなる選択部分のデザインＱから、オブジェクトを１つ取り出す（Ｑの1番目のオブジェクトを取り出すことにする）。図１６は、オブジェクトの取り出しを説明する図である。
【００７３】
２．取り出したオブジェクトと、既存のデザインＲの全オブジェクトとの組み合わせPair(１，１, Pair(１，２), ・・・, Pair(１，ｎ) に対して、以下を実行する（Ｒのオブジェクトの総数をｎとする）。図１７は、オブジェクトの組み合わせを説明する図である。
【００７４】
３．Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)に対する位置ずれで、Ｑを平行移動する。図１８は、デザインＱの平行移動を説明する図である。
【００７５】
４．Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定して、残りのオブジェクトの組み合わせをGreedy Algorithmや線形計画法(LP)等で求める（各オブジェクトの座標は直接計算可能である）。Greedy Algorithmは、全ての組み合わせの中で、最も類似度が高いペアから順に選んでいくアルゴリズムである。図１９は、残りのオブジェクトの組み合わせを説明する図である。図１９では、赤色のオブジェクトのペアは固定し、まず青色のオブジェクトのペアを、次に緑色のオブジェクトのペアを順にGreedyに選んだ場合を表している。
【００７６】
５．Pair(１，ｉ), (ｉ＝１，２，・・・ｎ)を固定した組み合わせの中で、最も類似する組み合わせを解とする。図２０は、最も類似する組み合わせPair(１，２)が解となることを説明する図である。オブジェクトの組み合わせが分かると、（式９）によりデザイン間の距離が計算できる。
【００７７】
第２の実施形態によれば、オブジェクトの割当に近似解を利用することで評価処理を高速化することができる。
【００７８】
（第３の実施形態）
第３の実施形態は、最適化問題を解く際に、近似解の情報を加えるものである。図２１は、第３の実施形態に係る画像情報処理方法の処理の流れを示すフローチャートである。まず初めに、選択部分のデザイン上の検索キーとなる複数のオブジェクトと既存デザイン上のオブジェクトに対して、以下のステップＳ２１０１以降を実行する。
【００７９】
検索キーとなるオブジェクトと既存デザイン上のオブジェクトについて、位置属性を除く各属性を取得する（ステップＳ２１０１）。次に、位置属性を除く各属性間の距離を計算する（ステップＳ２１０２）。次いで、オブジェクト間の距離を計算する（ステップＳ２１０３）。次いで、オブジェクトの割当によるコストを定式化する（ステップＳ２１０４）。一方、検索キーとなるオブジェクトと既存デザイン上のオブジェクトについて、位置属性を取得する（ステップＳ２１０５）。次に、位置ズレ（トポロジーの非類似度）によるコストを定式化する（ステップＳ２１０６）。次に、近似アルゴリズムを使用してデザイン間の最も類似する組み合わせを求める（ステップＳ２１０７）。尚、ここでの近似アルゴリズムは、第２の実施形態における近似アルゴリズムと同じである。
【００８０】
次に、Min｛オブジェクトの割当によるコスト＋W×位置ズレ（トポロジーの類似度）によるコスト｝を数理計画問題として解くことで全ての組み合わせを計算することなく最適解を計算する（ステップＳ２１０８）。最小化問題を解く場合、厳密解が真の最小値なので、近似アルゴリズムにより求めたデザイン間の距離は、デザイン間の厳密な距離より小さくならないという性質がある。そこで、厳密解に近い値が分かっており、その値より厳密解が大きくならないことを使って、不要な計算を避けることにより、高速化できる。尚、ステップＳ２１０８で厳密解を計算する際は、例えば、Branch-and-cutという一般的なアルゴリズムを使用することができる。
【００８１】
そして、数理計画問題の解から、デザイン間の距離を算出する（ステップＳ２１０９）。第３の実施形態によれば、数理計画問題の計算を高速化することができる。
【００８２】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【００８３】
１００・・・画像情報処理装置、１０・・・入力装置、２０・・・選択オブジェクト属性取得部、３０・・・ユーザ操作情報ＤＢ、４０・・・既存デザインＤＢ、５０・・・類似度算出部、６０・・・重み付け学習部、７０・・・表示制御部、８０・・・表示装置。
【図１】
0005550533.tif 000016
【図２】
0005550533.tif 000017
【図３】
0005550533.tif 000018
【図４】
0005550533.tif 000019
【図５】
0005550533.tif 000020
【図６】
0005550533.tif 000021
【図７】
0005550533.tif 000022
【図８】
0005550533.tif 000023
【図９】
0005550533.tif 000024
【図１０】
0005550533.tif 000025
【図１１】
0005550533.tif 000026
【図１２】
0005550533.tif 000027
【図１３】
0005550533.tif 000028
【図１５】
0005550533.tif 000029
【図１６】
0005550533.tif 000030
【図１７】
0005550533.tif 000031
【図１８】
0005550533.tif 000032
【図１９】
0005550533.tif 000033
【図２０】
0005550533.tif 000034
【図２１】
0005550533.tif 000035
【図１４】
0005550533.tif 000036