(57)【特許請求の範囲】
【請求項１】
それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される第１の個体を示す情報と、前記第１の個体に基づく画像処理の実行過程で前記第１の個体の各ノードで出力される処理結果とを記憶する記憶部と、
前記第１の個体に基づき、遺伝的プログラミングにおける次世代の個体の候補として第２の個体を生成し、前記第２の個体を示す木構造と前記第１の個体を示す木構造との間で同一内容かつ末端ノードを含む部分木を特定し、前記第２の個体に基づく画像処理の実行結果に基づいて前記第２の個体の適応度を算出する際に、前記第２の個体に含まれる前記部分木に基づく画像処理の実行結果として、前記記憶部に記憶された、前記第１の個体に含まれる前記部分木の先頭ノードに対応する処理結果を設定する演算部と、
を有し、
前記部分木の特定は、
前記第２の個体のノードの中から、交叉が行われた領域の先頭である第１のノードと突然変異が行われた第２のノードを特定し、
前記第２の個体のノードのうち、前記第１のノードおよび前記第２のノードより上位のノードを第３のノードとして特定し、
前記第２の個体のノードのうち前記第１、第２、第３のノード以外の第４のノードの中から、上位側に前記第１、第２、第３のノードのいずれかが接続されている第５のノードを特定し、
前記第２の個体を示す木構造のうち、前記第５のノードをルートとした領域を前記部分木として、前記第１の個体を示す木構造から前記部分木を探索する、
処理を含む、
情報処理装置。
【請求項２】
前記演算部は、さらに、
母集団に含まれる複数の個体を生成して前記記憶部に登録し、
前記複数の個体それぞれの適応度を算出して前記記憶部に格納するとともに、前記複数の個体それぞれについて、適応度の算出過程で各ノードから出力された処理結果を前記記憶部に格納し、
前記第２の個体の生成は、前記母集団から前記第１の個体を選択する処理を含む、
請求項１記載の情報処理装置。
【請求項３】
前記演算部は、
前記第２の個体の生成処理、前記部分木の特定処理、および、前記第２の個体の適応度の算出処理と、
前記第１の個体と前記第２の個体の各適応度に基づいて、前記第１の個体と前記第２の個体の中から生存個体を選択し、前記生存個体として前記第２の個体が選択された場合、前記母集団から選択された選択個体を前記第２の個体によって入れ替えるとともに、前記記憶部に記憶された、前記選択個体の各ノードでの処理結果を、前記第２の個体の適応度の算出過程で出力された、前記第２の個体の各ノードでの処理結果によって入れ替える世代交代処理と、
を繰り返し実行する、
請求項２記載の情報処理装置。
【請求項４】
前記世代交代処理は、前記第１の個体と前記第２の個体のうち、前記生存個体として選択されなかった第３の個体を、前記母集団とは別の個体集団に登録するとともに、前記第３の個体の適応度の算出過程で前記第３の個体の各ノードから出力された処理結果を、前記記憶部に保存する処理を含み、
前記部分木の特定処理では、前記部分木を、前記母集団および前記個体集団に含まれる個体の中から特定し、
前記第２の個体の適応度の算出処理では、前記母集団および前記個体集団に含まれる個体のうち、前記部分木が特定された個体に含まれる前記部分木の先頭ノードでの処理結果を、前記記憶部から読み出し、読み出した処理結果を、前記第２の個体に含まれる前記部分木に基づく画像処理の実行結果として設定する、
請求項３記載の情報処理装置。
【請求項５】
コンピュータが、
それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される第１の個体に基づき、遺伝的プログラミングにおける次世代の個体の候補として第２の個体を生成し、
前記第２の個体を示す木構造と前記第１の個体を示す木構造との間で同一内容かつ末端ノードを含む部分木を特定し、
前記第２の個体に基づく画像処理の実行結果に基づいて前記第２の個体の適応度を算出する際に、前記第１の個体に基づく画像処理の実行過程で前記第１の個体の各ノードで出力される処理結果を記憶する記憶部を参照し、前記第２の個体に含まれる前記部分木に基づく画像処理の実行結果として、前記記憶部に記憶された、前記第１の個体に基づく画像処理の実行過程で前記第１の個体の各ノードで出力される処理結果のうち、前記第１の個体に含まれる前記部分木の先頭ノードに対応する処理結果を設定する、
処理を実行し、
前記部分木の特定は、
前記第２の個体のノードの中から、交叉が行われた領域の先頭である第１のノードと突然変異が行われた第２のノードを特定し、
前記第２の個体のノードのうち、前記第１のノードおよび前記第２のノードより上位のノードを第３のノードとして特定し、
前記第２の個体のノードのうち前記第１、第２、第３のノード以外の第４のノードの中から、上位側に前記第１、第２、第３のノードのいずれかが接続されている第５のノードを特定し、
前記第２の個体を示す木構造のうち、前記第５のノードをルートとした領域を前記部分木として、前記第１の個体を示す木構造から前記部分木を探索する、
処理を含む、
情報処理方法。
【請求項６】
コンピュータに、
それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される第１の個体に基づき、遺伝的プログラミングにおける次世代の個体の候補として第２の個体を生成し、
前記第２の個体を示す木構造と前記第１の個体を示す木構造との間で同一内容かつ末端ノードを含む部分木を特定し、
前記第２の個体に基づく画像処理の実行結果に基づいて前記第２の個体の適応度を算出する際に、前記第１の個体に基づく画像処理の実行過程で前記第１の個体の各ノードで出力される処理結果を記憶する記憶部を参照し、前記第２の個体に含まれる前記部分木に基づく画像処理の実行結果として、前記記憶部に記憶された、前記第１の個体に基づく画像処理の実行過程で前記第１の個体の各ノードで出力される処理結果のうち、前記第１の個体に含まれる前記部分木の先頭ノードに対応する処理結果を設定する、
処理を実行させ、
前記部分木の特定は、
前記第２の個体のノードの中から、交叉が行われた領域の先頭である第１のノードと突然変異が行われた第２のノードを特定し、
前記第２の個体のノードのうち、前記第１のノードおよび前記第２のノードより上位のノードを第３のノードとして特定し、
前記第２の個体のノードのうち前記第１、第２、第３のノード以外の第４のノードの中から、上位側に前記第１、第２、第３のノードのいずれかが接続されている第５のノードを特定し、
前記第２の個体を示す木構造のうち、前記第５のノードをルートとした領域を前記部分木として、前記第１の個体を示す木構造から前記部分木を探索する、
処理を含む、
情報処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、情報処理装置、情報処理方法および情報処理プログラムに関する。
【背景技術】
【０００２】
所望の画像処理を実行するための画像処理プログラムを、遺伝的プログラミングによって自動生成する技術が注目されている。この技術では、画像処理プログラムを示す個体は、それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される。また、ある世代の親個体に基づいて子個体が生成され、学習データとして与えられた入力画像を用いて、生成された子個体に基づく画像処理が実行される。そして、その処理結果と、学習データとして与えられた目標となる処理結果（例えば、目標画像）との比較によって、子個体の適応度が算出される。適応度に基づいて世代交代の際に入れ替える個体が選択されることで、画像処理プログラムが最適化されていく。【０００３】
また、遺伝的プログラミングに関する技術として、次のような提案がある。例えば、遺伝子間の連結関係を記述する表現型個体構造情報を生成する際に、連結数を満たすように連結先のノードとなる遺伝子を特定するようにした進化計算システムが提案されている。また、サイズ依存型交叉が導入された、遺伝的プログラミングによる並列型画像フィルタ自動生成システムも提案されている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特開２００７−８７０５５号公報
【特許文献２】特開２０１１−１７９８７４号公報
【非特許文献】
【０００５】
【非特許文献１】青木紳也、長尾智晴、「木構造画像変換の自動構築法ＡＣＴＩＴ」、情報メディア学会誌Ｖｏｌ．５３，Ｎｏ．６、１９９９年６月２０日、ｐ．８９０−８９２
【発明の概要】
【発明が解決しようとする課題】
【０００６】
遺伝的プログラミングによる画像処理プログラムの生成過程では、世代交代のたびに子個体の適応度が算出される。ここで、最終的に高性能の画像処理プログラムを得るためには多くの世代交代が行われるが、世代交代の回数が多くなるほど、適応度の算出処理にかかる全体の時間が長くなるという問題がある。また、高機能の画像処理プログラムを生成するために個体の木構造が複雑になるほど、木構造に基づく画像処理も複雑になり、それに伴って個々の子個体の適応度を算出する時間も長くなる。このように適応度算出にかかる時間が長くなると、最適な個体が得られるまでの時間が増大してしまう。【０００７】
１つの側面では、本発明は、子個体の適応度の算出時間を短縮可能な情報処理装置、情報処理方法および情報処理プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００８】
１つの案では、記憶部と演算部とを有する情報処理装置が提供される。この情報処理装置において、記憶部は、それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される第１の個体を示す情報と、第１の個体に基づく画像処理の実行過程で第１の個体の各ノードで出力される処理結果とを記憶する。演算部は、第１の個体に基づき、遺伝的プログラミングにおける次世代の個体の候補として第２の個体を生成し、第２の個体を示す木構造と第１の個体を示す木構造との間で同一内容かつ末端ノードを含む部分木を特定し、第２の個体に基づく画像処理の実行結果に基づいて第２の個体の適応度を算出する際に、第２の個体に含まれる部分木に基づく画像処理の実行結果として、記憶部に記憶された、第１の個体に含まれる部分木の先頭ノードに対応する処理結果を設定する。【０００９】
また、１つの案では、上記の情報処理装置と同様の処理が実行される情報処理方法が提供される。
さらに、１つの案では、上記の情報処理装置と同様の処理をコンピュータに実行させる情報処理プログラムが提供される。
【発明の効果】
【００１０】
１つの側面では、子個体の適応度の算出時間を短縮できる。
本発明の上記および他の目的、特徴および利点は本発明の例として好ましい実施の形態を表す添付の図面と関連した以下の説明により明らかになるであろう。
【図面の簡単な説明】
【００１１】
【図１】第１の実施の形態に係る情報処理装置の構成例および処理例を示す図である。
【図２】画像処理プログラムの生成処理手順の比較例を示す図である。
【図３】画像処理装置のハードウェア構成例を示す図である。
【図４】画像処理装置が備える処理機能の構成例を示すブロック図である。
【図５】木構造情報記憶部に記憶される情報の構成例を示す図である。
【図６】子個体の生成例を示す図である。
【図７】子個体の適応度の算出処理例を示す図である。
【図８】照合対象の部分木を特定するための具体的な処理手順の例を示す図である。
【図９】プログラム生成処理手順の例を示すフローチャート（その１）である。
【図１０】プログラム生成処理手順の例を示すフローチャート（その２）である。
【図１１】第３の実施の形態に係る画像処理装置におけるプログラム生成処理手順の例を示すフローチャートである。
【図１２】交叉ポイントおよび突然変異のポイントに基づく照合対象の部分木の特定処理の例を示す図である。
【発明を実施するための形態】
【００１２】
以下、本発明の実施の形態について図面を参照して説明する。
〔第１の実施の形態〕
図１は、第１の実施の形態に係る情報処理装置の構成例および処理例を示す図である。第１の実施の形態に係る情報処理装置１は、画像処理プログラムを遺伝的プログラミングによって生成する装置である。この情報処理装置１は、記憶部１ａおよび演算部１ｂを有する。記憶部１ａは、例えば、ＲＡＭ（Random Access Memory）などの揮発性記憶装置、あるいはＨＤＤ（Hard Disk Drive）、フラッシュメモリなどの不揮発性記憶装置として実装される。演算部１ｂは、例えば、プロセッサである。
【００１３】
記憶部１ａは、第１の個体１０を示す個体情報２と、第１の個体１０の各ノードに対応する処理結果３ａ，３ｂ，・・・とを記憶する。第１の個体１０は、遺伝的プログラミングの進化過程において親個体として選択され得る個体であり、それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される。図１の例では、第１の個体１０は、６個のノード１１〜１６を有する木構造で表現される。
【００１４】
なお、図１では、ノード１１〜１６をそれぞれ示す丸印に、プログラム要素の種類に応じたハッチングを施して示している。この点は、後述する第２の個体２０についても同様である。
【００１５】
個体情報２は、例えば、第１の個体１０の構成を示す情報であり、ノード間の接続関係や各ノードに組み込まれたプログラム要素の種類などを示す。処理結果３ａ，３ｂ，・・・は、第１の個体１０に基づく画像処理の実行過程でノード１１〜１６のそれぞれで出力される処理結果を示す。なお、処理結果３ａ，３ｂ，・・・は、例えば、第１の個体１０の適応度を算出する過程で得られる。
【００１６】
演算部１ｂは、第１の個体１０に基づき、遺伝的プログラミングにおける次世代の個体の候補、すなわち子個体として、第２の個体２０を生成する（ステップＳ１）。例えば、演算部１ｂは、第１の個体１０と図示しない他の個体との交叉処理や、第１の個体１０のいずれかのノードに対する突然変異処理によって、第２の個体２０を生成する。第２の個体２０は、第１の個体１０と同様に、それぞれが画像処理のプログラム要素に対応する１以上のノードを有する木構造で表現される。図１の例では、第２の個体２０は、７個のノード２１〜２７を有する木構造で表現される。
【００１７】
次に、演算部１ｂは、第２の個体２０を示す木構造と第１の個体１０を示す木構造との間で、同一内容かつ末端ノードを含む部分木を特定する（ステップＳ２）。ここで、部分木が互いに同一内容であるとは、ノードの接続関係や、各ノードに組み込まれたプログラム要素の種類が互いに同一であることを示す。図１の例では、第１の個体１０に含まれる部分木１０ａと、第２の個体２０に含まれる部分木２０ａとが特定される。
【００１８】
なお、部分木１０ａは末端のノード１１を含んでおり、部分木２０ａは末端のノード２１を含んでいる。それぞれ末端ノードを含む部分木が特定される理由は、各部分木の出力データが同一であることを保証するために、各部分木に入力されるデータが同じである必要があるからである。
【００１９】
次に、演算部１ｂは、生成された第２の個体２０を次世代に残すか否かを評価するために、第２の個体２０の適応度を算出する（ステップＳ３）。ここで、適応度は、第２の個体２０に基づく画像処理が実行され、その実行結果に基づいて算出される。しかし、本実施の形態において、演算部１ｂは、第２の個体２０に含まれる部分木２０ａに基づく画像処理の実行結果として、記憶部１ａに記憶されている処理結果３ａ，３ｂ，・・・のうち、部分木２０ａと同一の部分木１０ａにおける先頭のノード１２に対応する処理結果を設定する（ステップＳ３ａ）。
【００２０】
これにより、部分木２０ａに基づく画像処理の実行が省略され、部分木２０ａに基づく画像処理の実行結果として、部分木１０ａに基づく画像処理の実行結果が流用される。このように、第２の個体２０に基づく画像処理の一部の実行が省略されることで、第２の個体２０の適応度の算出にかかる時間を短縮できる。
【００２１】
〔第２の実施の形態〕
次に、第２の実施の形態に係る画像処理装置について説明する。第２の実施の形態に係る画像処理装置は、図１に示した情報処理装置１と同様の処理機能と、この処理機能によって生成された画像処理プログラムを実行して画像処理を行う機能とを備える。
【００２２】
以下の説明では、まず、図２を用いて、遺伝的プログラミングによる画像処理プログラムの生成処理の比較例を示し、この比較例における問題点について説明した後、第２の実施の形態に係る画像処理装置の詳細について説明する。
【００２３】
＜画像処理プログラム生成処理の比較例＞
図２は、画像処理プログラムの生成処理手順の比較例を示す図である。
画像処理プログラムの生成処理の前に、１つ以上の学習データ５０が用意される。学習データ５０には、入力画像５１と、入力画像５１に対して画像処理を施したときの目標画像５２とが含まれる。入力画像５１は、例えば、カメラによって被写体を撮像することにより得られる。
【００２４】
遺伝的プログラミングによる画像処理プログラムの生成処理では、個体は、１つ以上の部分プログラムを組み合わせて構成される。例えば、図２の左上に示すように、個体は木構造で定義される。そして、木構造の各ノードに部分プログラムが組み込まれる。
【００２５】
また、個体に組み込むことが可能な複数の部分プログラムも、あらかじめ用意される。以下、個体に組み込まれる部分プログラムの例として、画像フィルタを想定するが、部分プログラムは画像フィルタに限るものではなく、他の種類の画像処理を行うプログラムを用いることもできる。なお、図２の左上において、“Ｆ”はノードに組み込まれた画像フィルタを示し、“Ｉ”は入力端子を示し、“Ｏ”は出力端子を示す。
【００２６】
遺伝的プログラミングによる画像処理プログラムの生成処理は、例えば、次のように実行される。まず、母集団６１に含められる複数の初期個体が生成される（ステップＳ１１）。各初期個体のノードには、あらかじめ用意された複数の画像フィルタの中から画像フィルタがランダムに選択されて組み込まれる。
【００２７】
また、生成された各初期個体について、適応度が算出される。この処理では、各初期個体を用いた画像処理が、学習データ５０の各入力画像５１に対して実行され、実行後の画像と対応する目標画像５２とが比較されることで適応度が計算される。複数の学習データ５０が存在する場合、初期個体のそれぞれについて、複数の学習データ５０を用いて得られた適応度の平均値が算出される。
【００２８】
次に、母集団６１の中から、ランダムに一定数の親個体が選択される（ステップＳ１２）。以下、例として２つの親個体が選択されるものとする。
次に、選択された２つの親個体に対して進化過程の処理が施されることで、２以上の一定数の子個体が生成される（ステップＳ１３）。進化過程では、２つの親個体に対して交叉処理および突然変異処理が行われる。２つの親個体に対して、それぞれ異なる交叉処理や突然変異処理が行われることで、３つ以上の子個体が生成されてもよい。すなわち、生成される子個体の数は、母集団６１から選択される親個体の数以上とされる。
【００２９】
次に、生成された各子個体について、適応度が計算される（ステップＳ１４）。この処理では、初期個体の適応度算出と同様、各子個体を用いた画像処理が、学習データ５０の各入力画像５１に対して実行され、実行後の画像と対応する目標画像５２とが比較されることで適応度が計算される。
【００３０】
ここで、生成された子個体および元の親個体のうちのいずれかの適応度が所定の閾値以上であった場合には、その個体が最終的な画像処理プログラムとして出力され、プログラム生成処理が終了する。一方、これらすべての個体の適応度が所定の閾値未満であった場合には、生成された各子個体および元の２つの親個体を含む個体群６２の中から、生存選択が行われる（ステップＳ１５）。この生存選択では、個体群６２の中から、算出された適応度が最大の個体が選択される。さらに、個体群６２内の残りの個体の中から、所定の方法で個体が１つ選択される。例えば、残りの個体の中から、適応度に応じた確率で個体が選択される。
【００３１】
このような生存選択によって選択された２つの個体は、母集団６１に含まれる個体のうち、親個体として選択された２つの個体と入れ替えられる（ステップＳ１６）。これにより、母集団６１に含まれる個体が次世代の個体へ変更される。そして、適応度が所定の閾値以上となる個体が出現するまで、同様の処理が繰り返される。
【００３２】
以上の比較例のような手順によって生成される画像処理プログラムの用途としては、例えば、ＦＡ（Factory Automation）分野において、製品を撮像した画像に画像処理を施して所望の効果を得るという用途が考えられる。例えば、製品の外観を撮像した画像に画像処理を施して、欠陥が生じた箇所を抽出する、位置合わせを行う箇所を抽出するといった用途が考えられる。
【００３３】
このような用途では、被写体となる製品の変更や改良、それに伴う撮像環境の変化などに応じて、画像処理アルゴリズムの再構築の必要が生じる場合がある。このため、画像処理アルゴリズムの構築の容易性が求められている。また、照明条件の変化や被写体の形状、位置姿勢のバラツキなどの撮像環境の変化に対するロバスト性が高い画像処理アルゴリズムを構築することが求められている。
【００３４】
遺伝的プログラミングを利用することで、入力画像５１とこれに対応する目標画像５２とをあらかじめ用意しておくだけで、このような用途で使用可能な画像処理プログラムを容易に生成することができる。また、それぞれ撮像環境が異なる入力画像５１と目標画像５２とのペア（学習データ５０）を複数用意しておくことで、撮像環境の変化に対するロバスト性が高い画像処理アルゴリズムを自動生成することもできる。
【００３５】
＜比較例における問題点＞
上記の比較例では、親個体を基に生成された子個体の適応度を算出する処理が、子個体が生成されるたびに実行される。このため、子個体の適応度の算出回数は膨大な数となり、算出処理全体にかかる時間が長くなるという問題がある。また、子個体の木構造が複雑になるほど、木構造が示す画像処理プログラムを用いた入力画像の処理時間が長くなり、適応度の算出にかかる時間も増大する。さらに、入力画像の画像サイズが大きくなるほど、同様に適応度の算出にかかる時間が増大する。特に、ＦＡ分野では、高解像度カメラを用いてより大きな撮影視野で微細な欠陥を検出するケースが多く、それによって適応度の算出時間が長くなる傾向にある。
【００３６】
このように適応度算出にかかる時間が長いことは、画像処理プログラムの生成が完了するまでの時間を増大させる原因となる。このため、適応度算出の処理時間を短縮することが課題となる。
【００３７】
＜第２の実施の形態に係る画像処理装置の詳細＞
上記の課題に対して、第２の実施の形態に係る画像処理装置は、初期個体の適応度の算出時に各ノードで得られた中間処理結果を保存しておく。そして、画像処理装置は、子個体の適応度を算出する際に、親個体の木構造の中から、子個体に含まれる部分木と一致する部分木を特定する。画像処理装置は、保存された中間処理結果の中から、特定された親個体の部分木によって得られた中間処理結果を読み込み、その中間処理結果を子個体の部分木の処理結果として流用することで、子個体の部分木を用いた画像処理の実行を回避する。これにより、子個体の適応度算出処理に含まれる画像処理の一部をスキップすることができ、その結果、適応度算出処理にかかる時間を短縮できる。
【００３８】
以下、第２の実施の形態に係る画像処理装置の詳細について説明する。
図３は、画像処理装置のハードウェア構成例を示す図である。本実施の形態に係る画像処理装置１００は、例えば、図３に示すようなコンピュータとして実現される。
【００３９】
画像処理装置１００は、プロセッサ１０１によって装置全体が制御されている。プロセッサ１０１は、マルチプロセッサであってもよい。プロセッサ１０１は、例えばＣＰＵ（Central Processing Unit）、ＭＰＵ（Micro Processing Unit）、ＤＳＰ（Digital Signal Processor）、ＡＳＩＣ（Application Specific Integrated Circuit）、またはＰＬＤ（Programmable Logic Device）である。また、プロセッサ１０１は、ＣＰＵ、ＭＰＵ、ＤＳＰ、ＡＳＩＣ、ＰＬＤのうちの２以上の要素の組み合わせであってもよい。
【００４０】
プロセッサ１０１には、バス１０９を介して、ＲＡＭ１０２と複数の周辺機器が接続されている。
ＲＡＭ１０２は、画像処理装置１００の主記憶装置として使用される。ＲＡＭ１０２には、プロセッサ１０１に実行させるＯＳ（Operating System）プログラムやアプリケーションプログラムの少なくとも一部が一時的に格納される。また、ＲＡＭ１０２には、プロセッサ１０１による処理に必要な各種データが格納される。
【００４１】
バス１０９に接続されている周辺機器としては、ＨＤＤ１０３、グラフィック処理装置１０４、入力インタフェース１０５、読み取り装置１０６、通信インタフェース１０７およびネットワークインタフェース１０８がある。
【００４２】
ＨＤＤ１０３は、画像処理装置１００の補助記憶装置として使用される。ＨＤＤ１０３には、ＯＳプログラム、アプリケーションプログラム、および各種データが格納される。なお、補助記憶装置としては、ＳＳＤ（Solid State Drive）などの他の種類の不揮発性記憶装置を使用することもできる。
【００４３】
グラフィック処理装置１０４には、表示装置１０４ａが接続されている。グラフィック処理装置１０４は、プロセッサ１０１からの命令にしたがって、画像を表示装置１０４ａの画面に表示させる。表示装置１０４ａとしては、液晶ディスプレイや有機ＥＬ（ElectroLuminescence）ディスプレイなどがある。
【００４４】
入力インタフェース１０５には、入力装置１０５ａが接続されている。入力インタフェース１０５は、入力装置１０５ａから出力される信号をプロセッサ１０１に送信する。入力装置１０５ａとしては、キーボードやポインティングデバイスなどがある。ポインティングデバイスとしては、マウス、タッチパネル、タブレット、タッチパッド、トラックボールなどがある。
【００４５】
読み取り装置１０６には、可搬型記録媒体１０６ａが脱着される。読み取り装置１０６は、可搬型記録媒体１０６ａに記録されたデータを読み取ってプロセッサ１０１に送信する。可搬型記録媒体１０６ａとしては、光ディスク、光磁気ディスク、半導体メモリなどがある。
【００４６】
通信インタフェース１０７は、接続された外部デバイスとの間でデータの送受信を行う。本実施の形態では、通信インタフェース１０７には、外部デバイスとしてカメラ１０７ａが接続され、通信インタフェース１０７は、カメラ１０７ａから送信された画像データをプロセッサ１０１に送信する。
【００４７】
ネットワークインタフェース１０８は、ネットワーク１０８ａを介して他の装置との間でデータの送受信を行う。
以上のようなハードウェア構成によって、画像処理装置１００の処理機能を実現することができる。
【００４８】
図４は、画像処理装置が備える処理機能の構成例を示すブロック図である。画像処理装置１００は、画像取得部１１１、画像処理部１１２、プログラム生成部１２０、プログラム記憶部１３０、フィルタセット記憶部１４１、学習データ記憶部１４２および木構造情報記憶部１４３を有する。
【００４９】
画像取得部１１１、画像処理部１１２およびプログラム生成部１２０の処理は、例えば、画像処理装置１００のプロセッサ１０１が所定のプログラムを実行することで実現される。また、画像処理部１１２の処理の一部は、プログラム記憶部１３０に保存された画像処理プログラムを、画像処理装置１００のプロセッサ１０１が実行することで実現される。プログラム記憶部１３０、フィルタセット記憶部１４１および学習データ記憶部１４２は、例えば、画像処理装置１００のＨＤＤ１０３の記憶領域として実現される。木構造情報記憶部１４３は、例えば、画像処理装置１００のＲＡＭ１０２の記憶領域として実現される。
【００５０】
画像取得部１１１は、カメラ１０７ａによって撮像された画像のデータをカメラ１０７ａから取得し、プログラム生成部１２０または画像処理部１１２に出力する。
プログラム生成部１２０は、遺伝的プログラミングにより画像処理プログラムを生成し、生成された画像処理プログラムをプログラム記憶部１３０に保存する。なお、プログラム生成部１２０の内部構成については後述する。
【００５１】
画像処理部１１２は、カメラ１０７ａによって撮像された画像のデータを画像取得部１１１を介して取得する。画像処理部１１２は、プログラム記憶部１３０に保存された画像処理プログラムにしたがって、取得した画像に画像処理を施す。処理後の画像は、例えば、表示装置１０４ａに表示される。
【００５２】
プログラム記憶部１３０は、プログラム生成部１２０によって生成された画像処理プログラムを記憶する。
フィルタセット記憶部１４１は、プログラム生成部１２０によって生成される各個体のノードに組み込むことが可能な画像フィルタのプログラムを、複数記憶する。
【００５３】
学習データ記憶部１４２は、それぞれ入力画像および目標画像の各データを含む学習データを、１つ以上記憶する。学習データに含まれる入力画像は、例えば、画像処理装置１００に接続されたカメラ１０７ａによって撮像された画像であってもよい。
【００５４】
なお、本実施の形態では、例として、生成される画像処理プログラムを用いた処理の結果として、画像が出力されるものとするが、処理の結果として画像以外の情報が出力されるようにしてもよい。そのような処理の結果としては、例えば、入力画像における領域を示す位置情報、入力画像の分類結果や評価結果などが考えられる。このように処理の結果が画像でない場合、学習データには、目標となる処理結果を示す、画像以外の情報が、目標画像の代わりに含まれていてもよい。
【００５５】
木構造情報記憶部１４３は、母集団６１に含まれる各個体の情報を記憶する。
ここで、図５は、木構造情報記憶部に記憶される情報の構成例を示す図である。木構造情報記憶部１４３には、個体情報リスト１４３ａと木構造情報リスト１４３ｂとが記憶される。
【００５６】
個体情報リスト１４３ａには、母集団６１に含まれる各個体に対応するレコードが登録される。各レコードには、個体を識別するための個体ＩＤと、個体の適応度と、木構造情報リスト１４３ｂ内の対応するレコードを指し示すポインタとが登録される。
【００５７】
一方、木構造情報リスト１４３ｂは、個体に関する情報のうち、個体の木構造に関する情報を独立して保持する。木構造情報リスト１４３ｂには、各個体の木構造に対応するレコードが登録される。本実施の形態では、個体情報リスト１４３ａ内のレコードと木構造情報リスト１４３ｂ内のレコードとが、ポインタを用いて一対一で対応付けられる。
【００５８】
木構造情報リスト１４３ｂ内の各レコードには、木構造ＩＤ、ノード構成情報、フィルタ情報および中間データセットが登録される。木構造ＩＤは、木構造を識別するための識別情報である。ノード構成情報は、木構造に含まれるノード間の接続関係を示す。フィルタ情報は、各ノードに組み込まれた画像フィルタの種別を示す。
【００５９】
中間データセットは、各ノードに対応する中間データを含む。中間データは、木構造に対応する画像処理プログラムを用いて入力画像５１を処理する過程において、各ノードに組み込まれている画像フィルタの処理によって出力される処理結果を示すデータである。例えば、画像フィルタの処理結果が画像である場合、中間データには画像データが登録される。また、画像フィルタの処理結果が数値である場合、中間データにはその数値が登録される。
【００６０】
後述するように、中間データは、入力画像５１を用いて対応する個体の適応度が算出される処理の過程で出力され、木構造情報リスト１４３ｂのレコードに登録される。また、複数の入力画像５１が用いられる場合、中間データセットは、入力された入力画像５１ごとに生成され、レコードに登録される。
【００６１】
なお、以上の木構造情報記憶部１４３におけるデータ構造はあくまで例であり、例えば、木構造情報リスト１４３ｂ内のレコードが個体情報リスト１４３ａ内の対応するレコードと一体となって記憶されていてもよい。
【００６２】
以下、図４に戻って説明する。
プログラム生成部１２０は、学習制御部１２１、適応度算出部１２２および木構造分析部１２３を有する。
【００６３】
学習制御部１２１は、プログラム生成部１２０でのプログラム生成処理全体を統括的に制御する。例えば、学習制御部１２１は、母集団６１に含める初期個体の生成、個体の進化処理、適応度に基づく生存選択および最終的な画像処理プログラムの出力、生存選択された個体による母集団６１の更新などの処理を実行する。また、学習制御部１２１は、初期個体や子個体の適応度の算出過程で生成された中間データを木構造情報リスト１４３ｂのレコードに登録する処理も実行する。
【００６４】
適応度算出部１２２は、個体を評価するための適応度を算出する。具体的には、適応度算出部１２２は、個体の木構造に基づいて構築される画像処理プログラムにしたがって、学習データ５０に含まれる入力画像５１に画像処理を施す。適応度算出部１２２は、画像処理によって得られた画像と、入力画像に対応付けられた目標画像との類似度を、個体の適応度として算出する。
【００６５】
木構造分析部１２３は、進化過程で生成された子個体の適応度を算出する前に、子個体の木構造を分析し、親個体の木構造の中から、子個体に含まれる部分木と構成が一致する部分木を特定する。木構造分析部１２３は、木構造情報リスト１４３ｂから、特定された部分木から出力された中間データを読み出し、読み出した中間データを子個体の部分木の出力データとして適応度算出部１２２に渡す。この場合、適応度算出部１２２は、子個体の部分木についての画像処理を実行せずに、木構造分析部１２３から渡された中間データをその部分木の出力データとして利用して、子個体の適応度の算出処理を実行する。
【００６６】
ここで、図６〜図８を用いて、子個体の適応度算出処理の具体例について説明する。
図６は、子個体の生成例を示す図である。この図６では、親個体７１，７２を用いて子個体を生成する例を示す。なお、図６では、例として８種類の画像フィルタＦ１〜Ｆ８を用いて個体が生成されるものとする。また、「Ｉ」は、末端ノードに入力画像を入力するための入力端子であり、「Ｏ」は、先頭ノードの処理結果を出力するための出力端子である。
【００６７】
まず、親個体７１のノードＮ１１と、親個体７２のノードＮ２１とがそれぞれ交叉ポイントとして指定されたとする。この場合、親個体７１におけるノードＮ１１をルートとした下位側（入力側）の部分木７１ａと、親個体７２におけるノードＮ２１をルートとした下位側の部分木７２ａとが置き換えられる。これにより、親個体７１における部分木７１ａが部分木７２ａに置き換えられた子個体７３が生成される。なお、実際には、親個体７２における部分木７２ａが部分木７１ａに置き換えられた子個体も生成されるが、ここでは図示を省略する。
【００６８】
さらに、生成された子個体７３のノードＮ３１が突然変異を行うポイントとして指定され、ノードＮ３１のフィルタＦ５がフィルタＦ８に置き換えられたとする。これにより、子個体７４が生成される。そして、次の図７に示す手順で、子個体７４の適応度が算出される。
【００６９】
図７は、子個体の適応度の算出処理例を示す図である。木構造分析部１２３は、親個体７１，７２の木構造の中から、子個体７４に含まれる部分木と構成が一致する部分木を特定する。
【００７０】
ここで、一致するか否かが互いに照合される照合対象の部分木は、親個体と子個体のいずれにおいても、木構造の末端に位置する部分的な木構造（すなわち、入力端子を含む部分的な木構造）とされる。また、構成が一致する部分木とは、ノード間の接続関係が同じであり、各ノードに組み込まれた画像フィルタの種類も同じであり、末端ノード以外のノードについてはその下位側ノードに組み込まれた画像フィルタの種類も同じである部分木を示す。図７の例では、照合の結果、子個体７４の部分木７４ａが親個体７２の部分木７２ｂと一致し、子個体７４の部分木７４ｂが親個体７１の部分木７１ｂと一致すると判定される。
【００７１】
この場合、木構造分析部１２３は、木構造情報リスト１４３ｂに登録された親個体７１に対応するレコードから、親個体７１のノードＮ１２に対応する中間データＤｎ１２を読み出す。また、木構造分析部１２３は、木構造情報リスト１４３ｂに登録された親個体７２に対応するレコードから、親個体７２のノードＮ２２，Ｎ２３にそれぞれ対応する中間データＤｎ２２，Ｄｎ２３を読み出す。
【００７２】
適応度算出部１２２は、部分木７４ａを用いた入力画像５１に対する画像処理を実行しない。その代わり、適応度算出部１２２は、部分木７４ａの上位側（出力側）のノードＮ３２，Ｎ３３の各出力データとして、親個体７２のノードＮ２２，Ｎ２３にそれぞれ対応する中間データＤｎ２２，Ｄｎ２３を利用する。これにより、ノードＮ３４には、中間データＤｎ２２が入力され、ノードＮ３５には、ノードＮ３４での処理による出力データと中間データＤｎ２３とが入力される。
【００７３】
また、適応度算出部１２２は、部分木７４ｂを用いた入力画像５１に対する画像処理を実行しない。その代わり、適応度算出部１２２は、部分木７４ｂの出力側のノードＮ３６の出力データとして、親個体７１のノードＮ１２に対応する中間データＤｎ１２を利用する。これにより、ノードＮ３７には、ノードＮ３５での処理による出力データと中間データＤｎ１２とが入力される。
【００７４】
以上のように、適応度算出部１２２は、部分木７４ａ，７４ｂにおける画像処理の実行を省略することができる。これにより、子個体７４を利用した画像処理にかかる時間を短縮でき、その結果、子個体７４の適応度の計算にかかる時間を短縮できる。なお、図７の木構造７４−１は、中間データが入力されるノードがわかりやすくなるように子個体７４の木構造を変形して表したものである。木構造７４−１と子個体７４の元の木構造との比較でわかるように、元の木構造では画像フィルタによる処理ステップ数が１２であるのに対し、中間データを利用することで処理ステップ数が５となり、処理ステップ数が大幅に削減されている。
【００７５】
図８は、照合対象の部分木を特定するための具体的な処理手順の例を示す図である。本実施の形態において、木構造分析部１２３は、子個体の各ノードにフラグを付加することで、子個体の木構造から親個体との照合を行う照合対象の部分木を特定する。図８では、図７に示した子個体７４から照合対象の部分木を特定する場合について例示する。
【００７６】
木構造分析部１２３は、まず、子個体７４の全ノードのフラグを０に設定して初期化する。なお、このフラグは、対応する画像フィルタを用いた画像処理の実行が必要か否かを示すものであり、画像処理の実行が必要なノードに対して１が設定される。
【００７７】
次に、木構造分析部１２３は、子個体７４のノードの中から交叉ポイントおよび突然変異のポイントとして指定されたノードを特定する。図８の上側に示すように、交叉ポイントとして指定されたノードとしてノードＮ３５が特定され、突然変異のポイントとして指定されたノードとしてノードＮ３４が特定される。木構造分析部１２３は、特定されたノードＮ３４，Ｎ３５のフラグを１に変更する。
【００７８】
次に、木構造分析部１２３は、フラグを１に変更したノードより上位側（出力側）のすべてのノードについて、フラグを１に変更する。これにより、図８の下側に示すように、ノードＮ３７〜Ｎ３９のフラグが１に変更される。
【００７９】
この状態で、木構造分析部１２３は、フラグが０のノードのうち、上位ノード（出力側ノード）のフラグが１であるノードを特定する。図８の例では、このようなノードとしてノードＮ３２，Ｎ３３，Ｎ３６が特定される。木構造分析部１２３は、特定したノードをルートとした下位側（入力側）のすべての木構造を、照合対象の部分木として特定する。図８の例では、ノードＮ３２をルートとする部分木７４ａ１と、ノードＮ３３をルートとする部分木７４ａ２と、ノードＮ３６をルートとする部分木７４ｂとが、照合対象の部分木として特定される。
【００８０】
木構造分析部１２３は、親個体７１，７２における下位側の部分木（入力端子を含む部分木）の中から、特定された部分木７４ａ１，７４ａ２，７４ｂとそれぞれ一致する部分木を探索する。木構造分析部１２３は、木構造情報リスト１４３ｂから、探索された各部分木のルートノードに対応する中間データを読み出す。適応度算出部１２２は、読み出された中間データを、部分木７４ａ１，７４ａ２，７４ｂの各ルートノードの出力データとして利用する。
【００８１】
以上の処理により、木構造分析部１２３は、親個体の部分木と照合する照合対象の部分木を簡単な処理によって確実に特定することができる。
次に、画像処理装置１００における画像処理プログラムの生成処理について、フローチャートを用いて説明する。
【００８２】
図９、図１０は、プログラム生成処理手順の例を示すフローチャートである。
［ステップＳ２１］学習制御部１２１は、学習データの設定のための入力操作を受け付ける。例えば、学習データ記憶部１４２に記憶された学習データの中から、本処理で使用される学習データが指定される。あるいは、本処理で使用される学習データが学習データ記憶部１４２に登録される。
【００８３】
［ステップＳ２２］学習制御部１２１は、母集団６１に含める所定個数の初期個体を生成する。各初期個体は、木構造の各ノードに対して、フィルタセット記憶部１４１に登録された画像フィルタをランダムに選択して組み合わせることで生成される。また、各初期個体の木構造は、例えば、あらかじめ決められた複数の木構造の中からランダムに選択される。あるいは、木構造自体がランダムに決定されてもよい。
【００８４】
学習制御部１２１は、生成した各初期個体に関する情報を木構造情報リスト１４３ｂに登録する。具体的には、学習制御部１２１は、生成した初期個体の木構造に対応するレコードを、木構造情報リスト１４３ｂに新たに登録し、このレコードに木構造ＩＤ、ノード構成情報およびフィルタ情報を登録する。また、学習制御部１２１は、生成した初期個体に対応するレコードを個体情報リスト１４３ａに新たに登録し、このレコードに個体ＩＤを登録するとともに、このレコードに、木構造情報リスト１４３ｂに新たに登録したレコードを指し示すポインタを登録する。
【００８５】
［ステップＳ２３］学習制御部１２１は、母集団６１から個体を１つ選択し、選択された個体の適応度の算出を適応度算出部１２２に依頼する。
［ステップＳ２４］適応度算出部１２２は、ステップＳ２３で選択された個体の適応度を算出する。具体的には、適応度算出部１２２は、選択された個体に対応する画像処理プログラムにしたがって、学習データに含まれる入力画像に画像処理を施す。なお、適応度算出部１２２は、画像処理の実行過程で各ノードから出力された中間データを、ＲＡＭ１０２に一時的に保存しておく。適応度算出部１２２は、画像処理によって得られた画像と、入力画像に対応付けられた目標画像との類似度を、選択された個体の適応度として算出する。なお、学習データが複数登録されている場合には、適応度算出部１２２は、例えば、各学習データを用いて類似度を算出し、それらの類似度の平均値を個体の適応度とする。
【００８６】
［ステップＳ２５］学習制御部１２１は、ステップＳ２４で算出された適応度を、個体情報リスト１４３ａのレコードのうち選択された個体に対応するレコードに登録する。また、学習制御部１２１は、選択された個体に基づく画像処理の実行過程で各ノードから出力された中間データを、木構造情報リスト１４３ｂのレコードのうち選択された個体に対応するレコードの中間データセットの項目に登録する。
【００８７】
［ステップＳ２６］学習制御部１２１は、母集団６１に含まれるすべての個体を選択済みか否かを判定する。未選択の個体がある場合、学習制御部１２１は、ステップＳ２３の処理を実行する。一方、すべての個体を選択済みの場合、学習制御部１２１は、図１０のステップＳ３１の処理を実行する。
【００８８】
［ステップＳ３１］学習制御部１２１は、母集団６１に含まれる個体の中から、２つの親個体をランダムに選択する。
［ステップＳ３２］学習制御部１２１は、選択された２つの親個体の間で交叉を行うことで、２つ以上の所定数の子個体を生成する。さらに、学習制御部１２１は、生成された子個体のいずれかのノードに突然変異を発生させ、元の子個体のノードに組み込まれていた画像フィルタを、フィルタセット記憶部１４１に登録されている他の画像フィルタのいずれかに置き換える。なお、学習制御部１２１は、子個体における交叉ポイントのノードおよび突然変異が行われたノードの位置を、ＲＡＭ１０２に一時的に記録しておく。
【００８９】
［ステップＳ３３］木構造分析部１２３は、生成された子個体のそれぞれの木構造から、照合対象の部分木を特定する。
［ステップＳ３４］木構造分析部１２３は、生成された子個体のそれぞれについて次のような処理を実行する。木構造分析部１２３は、ステップＳ３１で選択された２つの親個体の木構造から、子個体から特定された照合対象の部分木と一致する部分木を探索する。なお、２つの親個体の木構造は、木構造情報リスト１４３ｂのレコードのうち、各親個体に関連付けられたレコードから特定される。換言すると、ステップＳ３４の処理では、木構造情報リスト１４３ｂのレコードのうち、２つの親個体にそれぞれ関連付けられた２つのレコードのみが参照される。
【００９０】
［ステップＳ３５］木構造分析部１２３は、生成された子個体のそれぞれについて次のような処理を実行する。木構造分析部１２３は、ステップＳ３４で親個体から探索された部分木のルートノードに対応する中間データを、木構造情報リスト１４３ｂのレコードのうちこの親個体に関連付けられたレコードから読み出す。なお、入力画像が複数用いられた場合、中間データは入力画像ごとに読み出される。
【００９１】
［ステップＳ３６］適応度算出部１２２は、生成された子個体のそれぞれについての適応度を算出する。
子個体の適応度の算出では、学習データに含まれる入力画像を入力として、子個体に対応する画像処理プログラムにしたがって画像処理が実行され、その処理結果として画像が出力される。しかし、その画像処理の実行過程では、図７、図８で説明したように、適応度算出部１２２は、ステップＳ３３で子個体から特定された照合対象の部分木の最上位ノードからの出力として、ステップＳ３５で読み出された中間データを設定する。これにより、この部分木に基づく画像処理の実行が省略される。
【００９２】
適応度算出部１２２は、出力された画像と、入力画像に対応付けられた目標画像との類似度を、子個体の適応度として算出する。なお、ステップＳ２４と同様に、学習データが複数登録されている場合には、適応度算出部１２２は、例えば、各学習データを用いて類似度を算出し、それらの類似度の平均値を個体の適応度とする。
【００９３】
［ステップＳ３７］学習制御部１２１は、ステップＳ３１で選択された各親個体の適応度を個体情報リスト１４３ａから取得する。学習制御部１２１は、各親個体の適応度、およびステップＳ３６で算出された各子個体の適応度の中から、最大適応度を特定し、最大適応度が所定の閾値より大きいか否かを判定する。学習制御部１２１は、最大適応度が閾値より大きい場合、ステップＳ４０の処理を実行し、最大適応度が閾値以下の場合、ステップＳ３８の処理を実行する。
【００９４】
［ステップＳ３８］学習制御部１２１は、ステップＳ３１で選択された各親個体、およびステップＳ３２で生成された各子個体の中から、適応度が最大の個体を生存させる個体として選択する。さらに、学習制御部１２１は、残りの個体の中から生存させる個体を１つ選択する。この選択では、残りの個体それぞれの適応度に応じた確率で生存させる個体が選択される。
【００９５】
［ステップＳ３９］学習制御部１２１は、母集団６１に含まれる個体のうちステップＳ３１で選択された親個体を、ステップＳ３８で選択された２つの個体に入れ替える。これによって、母集団６１の世代が更新される。
【００９６】
この処理では、学習制御部１２１は、個体情報リスト１４３ａおよび木構造情報リスト１４３ｂから親個体に対応するレコードを削除する。学習制御部１２１は、生存させる個体に対応するレコードを個体情報リスト１４３ａに追加し、そのレコードに個体ＩＤと適応度を登録する。さらに、学習制御部１２１は、生存させる個体の木構造に対応するレコードを木構造情報リスト１４３ｂに追加し、そのレコードに木構造ＩＤ、ノード構成情報、フィルタ情報および中間データセットを登録する。中間データセットには、生存させる個体についての適応度の算出過程でその個体の各ノードから出力された中間データが登録される。ただし、照合対象の部分木に含まれるノードについての中間データとしては、親個体の同一部分木に含まれるノードに対応する中間データが流用されればよい。また、学習制御部１２１は、木構造情報リスト１４３ｂに追加したレコードを指し示すポインタを、個体情報リスト１４３ａに追加したレコードに登録する。
【００９７】
なお、生存させる個体として親個体が選択された場合には、個体情報リスト１４３ａおよび木構造情報リスト１４３ｂに含まれる、その親個体に対応するレコードについては、削除されずにそのまま残されてもよい。
【００９８】
［ステップＳ４０］学習制御部１２１は、ステップＳ３７で適応度が閾値より大きいと判定された個体に対応する画像処理プログラムをプログラム記憶部１３０に格納して、処理を終了する。なお、ステップＳ３７で適応度が閾値より大きい個体が複数存在した場合、学習制御部１２１は、これらの個体の中から適応度が最大の個体に対応する画像処理プログラムを、プログラム記憶部１３０に格納する。
【００９９】
以上の第２の実施の形態によれば、子個体の適応度の算出の際に、子個体の木構造のうち親個体との間で同一内容の部分木については、保存されている中間データが利用されることで、その部分木に対応する画像処理の実行が省略される。これにより、子個体の適応度の算出にかかる時間を短縮できる。その結果、最適な画像処理プログラムが生成されるまでの時間を短縮できる。
【０１００】
〔第３の実施の形態〕
次に、第３の実施の形態に係る画像処理装置について説明する。第３の実施の形態に係る画像処理装置は、第２の実施の形態に係る画像処理装置１００の処理の一部を次のように変形したものである。なお、以下の説明では、第３の実施の形態に係る画像処理装置の構成要素については、第２の実施の形態と同様の符号を用いる。
【０１０１】
第２の実施の形態では、世代交代の際、木構造情報記憶部１４３には、生成された子個体のうち生存させる子個体についての情報のみが登録された。これにより、木構造情報記憶部１４３には、母集団６１に含まれる個体についての情報のみが登録され、中間データについても、母集団６１に含まれる個体に対応するデータのみが登録された。
【０１０２】
これに対して、第３の実施の形態では、生成された子個体のうち生存しなかった子個体に対応する中間データについても、木構造情報記憶部１４３に登録される。より具体的には、木構造情報リスト１４３ｂには、生存しなかった子個体についてのレコードも登録される。この子個体については、個体情報リスト１４３ａには対応するレコードが登録されない。すなわち、個体情報リスト１４３ａには、母集団６１に含まれる個体についてのレコードのみが登録されるが、木構造情報リスト１４３ｂには、母集団６１に含まれる個体に加え、生存しなかった子個体の木構造についてのレコードも登録される。
【０１０３】
そして、第３の実施の形態では、子個体の部分木と同一内容の部分木が、親個体だけでなく、木構造情報リスト１４３ｂに登録されたすべての木構造の中から探索される。すなわち、木構造情報リスト１４３ｂは、子個体の部分木と同一内容の部分木を探索するための木構造のデータベースとして使用される。さらに、第３の実施の形態では、子個体の木構造のうち、照合対象の部分木として特定される範囲が、第２の実施の形態よりも拡張される。これにより、子個体の適応度の算出の際に画像処理の実行が省略され得る範囲を拡大し、処理時間の短縮効果が大きくなるようにする。
【０１０４】
図１１は、第３の実施の形態に係る画像処理装置におけるプログラム生成処理手順の例を示すフローチャートである。第３の実施の形態に係る画像処理装置１００は、図９と同様の処理を実行した後、図１１の処理を実行する。図１１では、処理内容が同じ処理ステップについては図１０と同じステップ番号を付して示している。
【０１０５】
画像処理装置１００は、ステップＳ３１，Ｓ３２の処理を実行した後、次のステップＳ３４ａの処理を実行する。
［ステップＳ３４ａ］木構造分析部１２３は、生成された子個体それぞれについて、次のような処理を実行する。
【０１０６】
木構造分析部１２３は、木構造情報リスト１４３ｂに登録された木構造の中から、子個体に含まれる部分木と一致する部分木を探索する。この処理では、子個体の木構造のうち、照合対象の部分木として特定される範囲が、第２の実施の形態よりも拡張される。
【０１０７】
例えば、第３の実施の形態では、木構造分析部１２３は、まず、子個体の木構造の先頭ノードを選択し、そのノードをルートノードとする部分木（この場合は木構造全体）を照合対象とする。そして、木構造分析部１２３は、木構造情報リスト１４３ｂに登録された木構造の中から、照合対象とした部分木と一致する部分木を下位側に有する木構造を探索する。このような木構造が見つからなかった場合、木構造分析部１２３は、子個体の木構造から１段だけ下位のノードを選択し、そのノードをルートノードとする部分木を照合対象とする。そして、木構造分析部１２３は、上記と同様に、木構造情報リスト１４３ｂに登録された木構造の中から、照合対象とした部分木と一致する部分木を下位側に有する木構造を探索する。このようにして、木構造分析部１２３は、子個体の木構造のノードを先頭から順次選択していって、照合対象の部分木を少しずつ縮小していきながら、照合対象の部分木と一致する部分木を探索していく。
【０１０８】
また、子個体の先頭ノードから順次選択していく上記処理では、探索処理の負荷が高い。そこで、例えば、次の図１２に示す方法により、照合対象の部分木を特定する範囲を制限して、探索処理負荷を軽減してもよい。
【０１０９】
図１２は、交叉ポイントおよび突然変異のポイントに基づく照合対象の部分木の特定処理の例を示す図である。この図１２では、例として、図８に示した子個体７４から照合対象の部分木を特定する場合について説明する。
【０１１０】
木構造分析部１２３は、まず、子個体７４の全ノードのフラグを０に設定して初期化する。次に、木構造分析部１２３は、子個体７４のノードの中から、突然変異のポイントとして指定されたノードＮ３４と、交叉ポイントとして指定されたノードＮ３５とを特定する。ここまでの処理は、図８の例と同様である。
【０１１１】
次に、木構造分析部１２３は、図８の例とは異なり、突然変異のポイントとして指定されたノードＮ３４と、交叉ポイントとして指定されたノードＮ３５のうち、上位側のノードＮ３５を特定する。そして、木構造分析部１２３は、特定したノードＮ３５より上位側に位置するすべてのノードＮ３７〜Ｎ３９のフラグを、１に変更する。
【０１１２】
次に、木構造分析部１２３は、フラグが０のノードのうち、上位ノードのフラグが１であるノードＮ３５，Ｎ３６を特定する。そして、図１２の下側に示すように、木構造分析部１２３は、特定したノードＮ３５，Ｎ３６をそれぞれルートとする部分木７４ｃ，７４ｄを、初期の照合対象の部分木として特定する。
【０１１３】
木構造分析部１２３は、部分木７４ｃ，７４ｄと一致する部分木を有する木構造を、木構造情報リスト１４３ｂに登録された木構造の中から探索する。また、例えば、部分木７４ｃと一致する部分木を有する木構造が見つからなかった場合、木構造分析部１２３は、ノードＮ３５の下位側のノードＮ３３，Ｎ３４をそれぞれノードとする部分木を、新たに照合対象の部分木として特定する。そして、木構造分析部１２３は、これらの部分木と一致する部分木を有する木構造を、木構造情報リスト１４３ｂに登録された木構造の中から探索する。
【０１１４】
図８の例では、交叉ポイントや突然変異のポイントとして指定されたノードより下位側の位置する部分木だけが、照合対象の部分木として特定された。これに対して、図１２の例では、ルートノードがより上位側に位置して、より多くのノードを有する部分木が、照合対象の部分木として特定される。このような多くのノードを有する部分木と一致する部分木が、登録された木構造の中から見つかった場合、適応度算出部１２２は、図８の例と比較してより多くのノードでの画像処理の実行を省略できる。その結果、適応度の算出にかかる時間を短縮できる。さらに、初期の照合対象の部分木のルートノードを子個体の先頭ノードとする場合より、照合対象の部分木に含まれるノード数や、照合対象の部分木の再特定回数を減少させることができるので、探索処理の負荷を軽減できる。
【０１１５】
以下、図１１に戻って説明する。
［ステップＳ３５ａ］木構造分析部１２３は、生成された子個体のそれぞれについて次のような処理を実行する。木構造分析部１２３は、木構造情報リスト１４３ｂのレコードのうち、ステップＳ３４ａで照合対象の部分木と一致する部分木が見つかった木構造に対応するレコードを参照する。木構造分析部１２３は、参照先のレコードから、一致する部分木のルートノードに対応する中間データを読み出す。なお、入力画像が複数用いられた場合、中間データは入力画像ごとに読み出される。
【０１１６】
［ステップＳ３６ａ］適応度算出部１２２は、生成された子個体のそれぞれについての適応度を算出する。この算出処理手順は、ステップＳ３５ａで読み出された中間データが利用される点と、利用される中間データが親個体のものに限らない点とを除けば、図１０のステップＳ３６と同様である。
【０１１７】
［ステップＳ３６ｂ］学習制御部１２１は、ステップＳ３２で生成された各子個体の木構造に対応するレコードを、木構造情報リスト１４３ｂに登録する。このとき、子個体の算出過程で各ノードから得られた中間データが、中間データセットの項目に登録される。
【０１１８】
以上の処理が終了すると、学習制御部１２１は、ステップＳ３７の処理を実行する。ステップＳ３７でＮｏと判定された場合、学習制御部１２１は、ステップＳ３８の処理を実行した後、ステップＳ３９ａの処理を実行する。
【０１１９】
［ステップＳ３９ａ］学習制御部１２１は、母集団６１に含まれる個体のうちステップＳ３１で選択された親個体を、ステップＳ３８で選択された２つの個体に入れ替える。これによって、母集団６１の世代が更新される。
【０１２０】
このステップＳ３９ａでは、学習制御部１２１は、生存させる個体に対応するレコードを個体情報リスト１４３ａに登録し、そのレコードに個体ＩＤ、適応度およびポインタを登録する。ポインタは、ステップＳ３６ｂで木構造情報リスト１４３ｂに登録されたレコードのうち、生存させる個体の木構造に対応するレコードを指し示すように設定される。
【０１２１】
ここで、ステップＳ３６ｂでは、新たに生成されたすべての子個体の木構造を示す情報が、木構造情報リスト１４３ｂに登録される。一方、ステップＳ３９ａでは、生存させる個体を示す情報のみが個体情報リスト１４３ａに登録されるので、個体情報リスト１４３ａは母集団６１に含まれる個体のレコードのみを保持するようになる。
【０１２２】
以上の第３の実施の形態では、子個体が有する部分木と一致する部分木の探索範囲が、親個体だけでなく生成済みのすべての個体の木構造に拡張される。また、子個体に照合対象として設定される部分木の自由度も高まる。これにより、第２の実施の形態と比較して、子個体の適応度を算出する際に画像処理の実行が省略されるノード数が多くなる可能性が高まり、その結果、適応度の算出にかかる時間が短縮される可能性も高まる。
【０１２３】
なお、上記の各実施の形態に示した装置（情報処理装置１および画像処理装置１００）の処理機能は、コンピュータによって実現することができる。その場合、各装置が有すべき機能の処理内容を記述したプログラムが提供され、そのプログラムをコンピュータで実行することにより、上記処理機能がコンピュータ上で実現される。処理内容を記述したプログラムは、コンピュータで読み取り可能な記録媒体に記録しておくことができる。コンピュータで読み取り可能な記録媒体としては、磁気記憶装置、光ディスク、光磁気記録媒体、半導体メモリなどがある。磁気記憶装置には、ハードディスク装置（ＨＤＤ）、フレキシブルディスク（ＦＤ）、磁気テープなどがある。光ディスクには、ＤＶＤ（Digital Versatile Disc）、ＤＶＤ−ＲＡＭ、ＣＤ−ＲＯＭ（Compact Disc-Read Only Memory）、ＣＤ−Ｒ（Recordable）／ＲＷ（ReWritable）などがある。光磁気記録媒体には、ＭＯ（Magneto-Optical disk）などがある。
【０１２４】
プログラムを流通させる場合には、例えば、そのプログラムが記録されたＤＶＤ、ＣＤ−ＲＯＭなどの可搬型記録媒体が販売される。また、プログラムをサーバコンピュータの記憶装置に格納しておき、ネットワークを介して、サーバコンピュータから他のコンピュータにそのプログラムを転送することもできる。
【０１２５】
プログラムを実行するコンピュータは、例えば、可搬型記録媒体に記録されたプログラムまたはサーバコンピュータから転送されたプログラムを、自己の記憶装置に格納する。そして、コンピュータは、自己の記憶装置からプログラムを読み取り、プログラムに従った処理を実行する。なお、コンピュータは、可搬型記録媒体から直接プログラムを読み取り、そのプログラムに従った処理を実行することもできる。また、コンピュータは、ネットワークを介して接続されたサーバコンピュータからプログラムが転送されるごとに、逐次、受け取ったプログラムに従った処理を実行することもできる。
【０１２６】
上記については単に本発明の原理を示すものである。さらに、多数の変形、変更が当業者にとって可能であり、本発明は上記に示し、説明した正確な構成および応用例に限定されるものではなく、対応するすべての変形例および均等物は、添付の請求項およびその均等物による本発明の範囲とみなされる。
【符号の説明】
【０１２７】
１  情報処理装置
１ａ  記憶部
１ｂ  演算部
２  個体情報
３ａ，３ｂ  処理結果
１０  第１の個体
１０ａ，２０ａ  部分木
１１〜１６，２１〜２７  ノード
２０  第２の個体
【図１】
0006703289.tif 000002
【図２】
0006703289.tif 000003
【図３】
0006703289.tif 000004
【図４】
0006703289.tif 000005
【図５】
0006703289.tif 000006
【図６】
0006703289.tif 000007
【図７】
0006703289.tif 000008
【図８】
0006703289.tif 000009
【図９】
0006703289.tif 000010
【図１０】
0006703289.tif 000011
【図１１】
0006703289.tif 000012
【図１２】
0006703289.tif 000013