(57)【要約】【課題】  マークが付けられた製品の画像中の画像区画の認識性能を向上させる。【解決手段】  マークアップを構成するカスタマイズ可能な製品の入力画像が、色または色差に基づいて、異なる領域に分けられる。分割処理は、入力画像内の複数の位置に色差値を割り当てる。さらに、分割処理は、複数の位置のそれぞれに複数の画像領域のうち１つの画像領域を割り当て、割り当ては特定の順番で行われる。特定の順番は、複数の位置に関連する色差値の少なくとも一部に基づくものである。分割処理に基づいて、入力画像のマークアップの特定の少なくとも一部を表すデータが特定される。マークアップの特定の少なくとも一部を表すデータがカスタマイズ可能な製品を視覚化するためや、カスタマイズ可能な製品に関する製造制御を行うために用いられる。【選択図】  図４
2014179090.tif 000002
【特許請求の範囲】
【請求項１】
コンピューター実装方法において、
１以上のコンピューター装置で実行する方法であり、
入力画像を受信するステップと、
コンピューターを用いて、前記入力画像を色に基づいて複数の画像領域に分割処理を行なうステップと、
前記入力画像の項目に関する情報を決定するために分割処理に基づいて決定された情報を用いるステップと、
を備え、
前記分割処理が、
特定の位置に割り当てられる特定の色差値が前記入力画像の一部に基づいて決定されるとともに、該特定の色差値が前記特定の位置の色が前記特定の位置に近くにある他の位置の色とどの程度違うかを表すものである色差値を、前記入力画像の複数の位置のそれぞれに割り当てるステップと、
前記複数の位置に関連する少なくとも一部の色差値に対応する特定の順番に従って、前記複数の位置の各位置を前記複数の画像領域のうちの１つの画像領域に割り当てるステップと、
前記入力画像の少なくとも一部に基づいて決定された前記特定の位置の色の少なくとも一部に基づいて、特定の位置に割り当てられる画像領域を選択するステップと、
を有することを特徴とするコンピューター実装方法。
【請求項２】
前記複数の位置のうち所定の位置の近傍にある位置にいずれの領域を割り当てるかを決定するステップと、
前記決定の少なくとも一部に基づいて、前記所定の位置を前記複数の画像領域のうちの１つの所定の画像領域に割り当てるステップと、
をさらに備えたことを特徴とする請求項１記載のコンピューター実装方法。
【請求項３】
所定の位置の近傍にある位置にいずれの領域が関連するかの決定には、前記所定の位置の近傍の前記位置に関連する領域がないことを決定することを含むことを特徴とする請求項２に記載のコンピューター実装方法。
【請求項４】
所定の位置に隣接する第１の位置に第１の領域を割り当て、前記所定の位置に隣接する第２の位置に第２の領域を割り当てることを決定するステップと、
前記第１の領域と前記第２の領域のうち選択されていない領域を代表する色よりも選択された色を代表する色が前記所定の位置の色により類似していると判定されると、前記所定の位置に、前記第１の領域と前記第２の領域のうち前記選択した領域を割り当てるステップと、
をさらに備えることを特徴とする請求項１記載のコンピューター実装方法。
【請求項５】
所定の近傍位置を、所定の位置の近傍の位置であって領域が割り当てられた複数の位置のうちの１つの位置に決定するステップと、
前記決定に応じて、前記所定の位置に前記所定の近傍位置に割り当てられた領域を割り当てるステップと、
をさらに備えることを特徴とする請求項１記載のコンピューター実装方法。
【請求項６】
所定の位置に隣接する第１の位置に第１の領域を割り当て、所定の位置に隣接する第２の位置に前記第１の領域とは異なる第２の領域を割り当てることを決定するステップと、
前記第１の領域と前記第２の領域を併合するか否かを決定するステップと、
をさらに備え、
前記第１の領域を代表する色と前記第２の領域を代表する色を比較することにより前記第１の領域と前記第２の領域を併合するか否かを決定することを特徴とする請求項１記載のコンピューター実装方法。
【請求項７】
前記入力画像は、マークアップが付されたカスタマイズ可能な製品のデジタル写真画像であることを特徴とする請求項１記載のコンピューター実装方法。
【請求項８】
複数の分かれたデータ構造で、前記複数の画像領域を記述した情報を記憶するステップをさらに備え、
前記複数のデータ構造は、前記複数の画像領域の各画像領域について、
（ａ）前記画像領域を代表する色を示す代表色の値
（ｂ）前記画像領域の大きさ、および
（ｃ）前記画像領域に割り当てられた１つの位置
を特定する第１のデータ構造を有することを特徴とする請求項１記載のコンピューター実装方法。
【請求項９】
前記複数の分かれたデータ構造は、複数の項目を備える第２のデータ構造を有し、
該複数の項目のうちの各項目は、前記複数の位置のうちの１つの対応位置を表し、
前記対応位置に関連して対応する次の位置であって、前記対応位置とは異なる位置であり、該対応位置と同じ画像領域に割り当てられる対応する次の位置、または
前記対応位置に関連する次の位置がないことを示す値、
のいずれかを特定することを特徴とする請求項８記載のコンピューター実装方法。
【請求項１０】
前記分割処理に基づいて、前記入力画像のマークアップの少なくとも特定の部分を表すデータを特定するステップと、
前記データに基づいて、カスタマイズ可能な製品の視覚化を行うための命令を決定するステップ、または
前記カスタマイズ可能な製品の前記視覚化を行なうための命令をウェッブサーバに送信するステップ、
をさらに備えたコンピューター実装方法。
【請求項１１】
前記入力画像に基づいて、値に応じて前記画像の位置の色を示す値を色値配列に設定するステップと、
前記色値配列を１回辿って、前記入力画像の各位置に色差値を割り当てるステップと、
をさらに備えたことを特徴とする請求項１記載のコンピューター実装方法。
【請求項１２】
第１の位置に割り当てる第１の画像領域を選択するステップと、
所定の位置に対応する領域リストの項目に、前記第１の画像領域を示す第１の値を記憶するステップと、
前記第１の画像領域に関する色と第２画像領域に関する色との比較に基づいて、前記第１の画像領域と前記第２の画像領域を併合することを決定するステップと、
前記第１の画像領域と前記第２の画像領域を併合することが決定すると、前記領域リストの前記項目の前記第１の値を前記第２の画像領域を表す第２の値に更新するステップと、
をさらに備えたことを特徴とする請求項１記載のコンピューター実装方法。
【請求項１３】
前記第１の値と前記第２の値を比較するステップをさらに備え、
前記第１の値と第２の値は、数値であり、
前記第１の値と前記第２の値の比較に応じて、前記領域リストの項目の前記第１の値を前記第２の値に更新することを特徴とする請求項１２記載のコンピューター実装方法。
【請求項１４】
前記第１の値が前記第２の値より小さいと少なくとも判定されたことに基づいて、前記第１の値が前記第２の値に更新されることを特徴とする請求項１３記載のコンピューター実装方法。
【請求項１５】
前記入力画像の各位置を対応する画像領域に割り当てた後に、前記第１の値が設定されている前記領域リストの１以上の項目を特定するステップと、
前記第１の値が設定されている前記領域リストの１以上の項目のうち各特定の項目に対して、前記特定の項目の前記第１の値を前記第２の値に更新するステップと、
をさらに備えたことを特徴とする請求項１２記載のコンピューター実装方法。
【請求項１６】
１以上のプロセッサにより実行されることにより、１以上の処理を実行させる１以上の命令が記憶された非一時的なコンピューター読み取り可能な記録媒体を備えたコンピューターシステムであって、
入力画像を受信するステップと、
コンピューターを用いて、前記入力画像を色に基づいて複数の画像領域に分割処理を行なうステップと、
前記入力画像の項目に関する情報を決定するために分割処理に基づいて決定された情報を用いるステップと、
を実行するコンピューターシステムであり、
前記分割処理が、
特定の位置に割り当てられる特定の色差値が前記入力画像の一部に基づいて決定されるとともに、該特定の色差値が前記特定の位置の色が前記特定の位置に近くにある他の位置の色とどの程度違うかを表すものである色差値を、前記入力画像の複数の位置のそれぞれに割り当てるステップと、
前記複数の位置に関連する少なくとも一部の色差値に対応する特定の順番に従って、前記複数の位置の各位置を前記複数の画像領域のうちの１つの画像領域に割り当てるステップと、
前記入力画像の少なくとも一部に基づいて決定された前記特定の位置の色の少なくとも一部に基づいて、特定の位置に割り当てられる画像領域を選択するステップと、
を有することを特徴とするコンピューターシステム。
【請求項１７】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
前記複数の位置のうち所定の位置の近傍にある位置にいずれの領域を割り当てるかを決定するステップと、
前記決定の少なくとも一部に基づいて、前記所定の位置を前記複数の画像領域のうちの１つの所定の画像領域に割り当てるステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項１８】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、所定の位置の近傍にある位置にどの領域が関連するかを、該所定の位置の近傍の該位置に関連する領域がないことを決定することによって決定する一連の命令が記憶されたことを特徴とする請求項１７記載のコンピューターシステム。
【請求項１９】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
所定の位置に隣接する第１の位置に第１の領域を割り当て、前記所定の位置に隣接する第２の位置に第２の領域を割り当てることを決定するステップと、
前記第１の領域と前記第２の領域のうち選択されていない領域を代表する色よりも選択された色を代表する色が前記所定の位置の色により類似していると判定されると、前記所定の位置に、前記第１の領域と前記第２の領域のうち前記選択した領域を割り当てるステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２０】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
所定の近傍位置を、所定の位置の近傍の位置であって領域が割り当てられた複数の位置のうちの１つの位置に決定するステップと、
前記決定に応じて、前記所定の位置に前記所定の近傍位置に割り当てられた領域を割り当てるステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２１】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、
所定の位置に隣接する第１の位置に第１の領域を割り当て、所定の位置に隣接する第２の位置に前記第１の領域とは異なる第２の領域を割り当てることを決定するステップと、
前記第１の領域と前記第２の領域を併合するか否かを決定するステップであって、前記第１の領域を代表する色と前記第２の領域を代表する色を比較することを含むステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２２】
前記入力画像は、マークアップが付されたカスタマイズ可能な製品のデジタル写真画像であることを特徴とする請求項１６記載のコンピューターシステム。
【請求項２３】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
複数の分かれたデータ構造で、前記複数の画像領域を記述した情報を記憶するステップをさらに実行させる一連の命令が記憶されており、
前記複数のデータ構造は、前記複数の画像領域の各画像領域について、
（ａ）前記画像領域を代表する色を示す代表色の値
（ｂ）前記画像領域の大きさ、および
（ｃ）前記画像領域に割り当てられた１つの位置
を特定する第１のデータ構造を有することを特徴とする請求項１６記載のコンピューターシステム。
【請求項２４】
前記複数の分かれたデータ構造は、複数の項目を備える第２のデータ構造を有し、
該複数の項目のうちの各項目は、前記複数の位置のうちの１つの対応位置を表し、
前記対応位置に関連して対応する次の位置であって、前記対応位置とは異なる位置であり、該対応位置と同じ画像領域に割り当てられる対応する次の位置、または
前記対応位置に関連する次の位置がないことを示す値、
のいずれかを特定することを特徴とする請求項１６記載のコンピューターシステム。
【請求項２５】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
前記分割処理に基づいて、前記入力画像のマークアップの少なくとも特定の部分を表すデータを特定するステップと、
前記データに基づいて、カスタマイズ可能な製品の視覚化を行うための命令を決定するステップ、または
前記カスタマイズ可能な製品の前記視覚化を行なうための命令をウェッブサーバに送信するステップ、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２６】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
前記入力画像に基づいて、値に応じて前記画像の位置の色を示す値を色値配列に設定するステップと、
前記色値配列を１回辿って、前記入力画像の各位置に色差値を割り当てるステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２７】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
第１の位置に割り当てる第１の画像領域を選択するステップと、
所定の位置に対応する領域リストの項目に、前記第１の画像領域を示す第１の値を記憶するステップと、
前記第１の画像領域に関する色と第２画像領域に関する色との比較に基づいて、前記第１の画像領域と前記第２の画像領域を併合することを決定するステップと、
前記第１の画像領域と前記第２の画像領域を併合することが決定すると、前記領域リストの前記項目の前記第１の値を前記第２の画像領域を表す第２の値に更新するステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項１６記載のコンピューターシステム。
【請求項２８】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
前記第１の値と前記第２の値を比較するステップ、
をさらに実行させる一連の命令が記憶されており、
前記第１の値と第２の値は、数値であり、
前記第１の値と前記第２の値の比較に応じて、前記領域リストの項目の前記第１の値を前記第２の値に更新することを特徴とする請求項２７記載のコンピューターシステム。
【請求項２９】
前記第１の値が前記第２の値より小さいと少なくとも判定されたことに基づいて、前記第１の値が前記第２の値に更新されることを特徴とする請求項２８記載のコンピューターシステム。
【請求項３０】
前記記録媒体に、一連の命令であって、１以上のプロセッサにより実行されると、該１以上のプロセッサに、
前記入力画像の各位置を対応する画像領域に割り当てた後に、前記第１の値が設定されている前記領域リストの１以上の項目を特定するステップと、
前記第１の値が設定されている前記領域リストの１以上の項目のうち各特定の項目に対して、前記特定の項目の前記第１の値を前記第２の値に更新するステップと、
をさらに実行させる一連の命令が記憶されたことを特徴とする請求項２７記載のコンピューターシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、製品のマークアップ画像を、色および複数の色間の違いに基づいて領域に分ける技術に関連する。
【背景技術】
【０００２】
この項目に記述されている手法は、達成することが可能であるが、必ずしも以前に着想または達成された手法ではない。したがって、別段の指定がない限り、この項目で記述されている手法のうちのいずれかが、この項目に含まれていることで単に先行技術であると仮定されるべきではない。
【０００３】
デジタル画像中の特定のオブジェクトの位置や形などのデジタル画像に関する情報は、デジタル画像に対してセグメンテーションを行うことにより抽出することができる。画像セグメンテーションは、デジタル画像を複数の異なる領域に分ける処理である。例えば、Ｚａｚｚｌｅ社などのカスタマイズ製品の製造業者や提供者は、身に付けた時の衣類やアクセサリーなどのカスタマイズする製品の形状を理解するために、製品に付けられたマークアップの位置と形を抽出したいと思っている。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
画像分割に関する一手法では、画像がフルカラーで表されたものを、各ピクセルの濃淡がオリジナル画像のピクセルの輝度値を表す白黒の輝度画像に変換する。領域の区画は、画像内のピクセルの輝度に基づいて決定される。しかし、このような手法は、正確に領域の区画を決定するために必要な色情報のいくつかが白黒の輝度画像に変換する際に失われるので、しばしば結果が不正確になる。マークが付けられた製品の画像中の画像区画の認識を向上させる手法が必要とされている。
【課題を解決するための手段】
【０００５】
添付のクレームが本発明の要約となる。
【図面の簡単な説明】
【０００６】
図について
【図１】複数の画像領域に分けた入力画像の一例を示す。
【図２】分割処理に従って決定された領域情報を利用するカスタマイズ画像レンダリングシステムの一例を示す。
【図３】図２に示すカスタマイズ画像レンダリングシステムのようなカスタマイズ画像レンダリングシステムに実装される処理の一例を示す。
【図４】画像を領域に分割し分割処理の結果決定された領域情報を利用する処理の一例を示す。
【図５】入力画像を色と色差の一部に基づいて複数の画像領域に分ける処理の一例を示す。
【図６】中心位置に対する色差値を決定するために分析される色の位置を表す図の一例を示す。
【図７】各位置に関連する色差値に基づいて位置をソートするために用いられる色差データの一例と、ソートリストおよびソート処理から結果を得るために用いられる色差配列の一例を示す。
【図８】色差値に基づいた画像位置をソートする処理の一例を示す。
【図９】図８に示す処理に従って、色差配列に記憶された色差値に基づいて一部にデータが設定されたソートリストと連結領域配列の内容を示す。
【図１０】領域に対して画像位置を割り当てる処理の一例を示す。画像処理システム２０４によって処理が実行される。
【図１１】分割処理の結果決定された領域情報の一例を示す。
【図１２】図１に描かれた入力画像を分割することによって特定された領域情報の一部に基づいて決定されたマークアップのグリッド画像を描画したものである。
【図１３】ここに記載の技術を実装したコンピューターシステムを示すブロック図である。
【発明を実施するための形態】
【０００７】
以下の記載は、例示を目的とし、多数の詳細な形態は本発明を十分に理解するために提供される。しかしながら、本発明は、このような詳細な形態でなくとも実施されることは明らかである。他の例では、本発明を必要以上に不明瞭にしないために、既知の構成と装置がブロック図に示されている。
【０００８】
以下の概要に従って、実施形態をここに記載する。
【０００９】
１．総括
２．構成と機能の概要
２．１  カスタマイズ画像レンダリングシステムの例
２．２  領域情報利用処理の例
２．３  マークアップ画像の分割処理の例
２．４  他の形態および拡張
３．実装の仕組み―ハードウェアの概要
４．分割命令の一例
【００１０】
１．総括
色と色差に基づいた製品のマークアップ画像のセグメンテーション技術について記載されている。本開示の読み手は米国特許出願第１３／７３６，８４４号明細書についての知識があり理解しているものとみなされる。一実施形態では、製品マークアップ画像はマークアップを構成するカスタマイズ可能な製品の画像である。製品画像は一部分の色差に基づいて、異なる領域に分けられてもよい。特に、製品のマークアップ画像入力画像の各位置は、色の観点で近傍の位置からその位置がどのくらい違うかの指標となる色差値が割り当てられてもよい。各位置は複数の画像領域の１つの画像領域に割り当てられ、少なくとも一部はピクセルに割り当てられた色差値に基づいた順番に従って、複数の位置が領域の割当について検討されてもよい。例えば、色差値の小さい位置が色差値の大きい位置より前に領域が割り当てられてもよい。
【００１１】
画像処理システムは、カスタマイズ可能な製品を視覚化、または、カスタマイズ可能な製品に関する製造の制御に、決定された領域情報を利用するようにしてもよい。例えば、画像処理システムは、領域情報に基づいて特定のマークアップ部分の位置を決定するようにしてもよい。決定された位置情報に基づいて、画像処理システムは、コンピューターでカスタマイズされた製品を視覚化するレンダリング命令で構成されるカスタマイズ画像レンダリングアセットを決定してもよい。領域情報は、カスタマイズされた製品が製造された後に、カスタマイズされた製品の品質を確かめるためにも利用されてもよい。
【００１２】
２．構成と機能の概要
２．１  カスタマイズ画像レンダリングシステムの例
図１に複数の画像領域に分けた入力画像の一例を示す。シャツ１０４は、注文したテキストまたは画像が付けられるカスタマイズ可能な製品である。マークアップ１０２は、無地の四角で構成された２色の市松模様であり、各四角が単一の色で、それぞれ隣接した四角は反対色になる。ここに記載された処理は、少なくとも入力画像のマークアップの部分を１組の領域群に分け、領域群のそれぞれがマークアップの中の対応する四角の１つを表す。他の実施形態では、マークアップは異なるパターン、形状、または色で構成されてもよい。
【００１３】
画像分割処理は、例えば、見つけられた各領域に対して、その領域が属する画像位置、各領域の範囲、および／または、領域の代表色などを特定する領域情報を結果として得る。ある実施形態では、各画像位置は離れたピクセルである。他の実施形態では、各画像位置はピクセル群である。
【００１４】
一実施形態では、結果として得られた領域情報は、顧客が提供したパラメータに従ってカスタマイズされた注文（カスタマイズ）製品を自動的に視覚化するために用いられる。図２に、分割処理に従って決定された領域を利用するカスタマイズ画像生成およびレンダリングシステムの一例を示す。
【００１５】
１以上のカメラ２０２が、マークアップが刷られた（imprinted）あるいは他の方法で付けられた（embellished）カスタマイズ可能な製品の写真を取得する。画像処理システム２０４はカメラ２０２から生のデジタル画像２０６を受け取って記憶する。画像処理システム２０４は、１以上の記憶されたコンピュータープログラム、スクリプト、または他のソフトウェア要素として実装されたカスタマイズ画像レンダリングアセット生成命令２０８を備える。画像処理システム２０４の１以上の処理が、カスタマイズ画像レンダリングアセット生成命令２０８を実行して、カスタマイズ画像レンダリング命令を生成するようにしてもよい。カスタマイズ画像レンダリングアセット生成命令２０８には、入力画像を分析して分割された画像領域を特定して、領域の代表色、領域の範囲、および領域に含まれる１組の画像位置群などの画像領域について情報を集めるマークアップ領域特定命令２１０が含まれる。カスタマイズ画像レンダリングアセット命令の生成は、領域情報に基づいてカスタマイズ画像のレンダリングを生成するための命令を決定することで行われる。カスタマイズ画像レンダリングアセットには、コンピューターで生成したカスタマイズ製品を視覚化したカスタマイズ画像をレンダリングするための命令が含まれる。
【００１６】
画像処理システム２０４は、生成されたカスタマイズ画像レンダリングアセットを、カスタマイズ画像レンダリングアセット２１４を記憶して利用するウェッブサーバ２１２などのウェッブサーバ２１２に送信する。ウェッブサーバ２１２は、カスタマイズ画像レンダリングアセット２１４などの１以上のカスタマイズ画像レンダリングアセットを受信し記憶する。また、ウェッブサーバ２１２は、ＨＴＭＬおよび／または他のウェッブページコンテンツを決定するウェッブページ生成部２１６で構成される。ウェッブサーバ２１２は、ユーザシステム２２０などのユーザシステムからウェッブページの要求を受け取る。それに応じて、ウェッブサーバ２１２は、ユーザシステムで表示するためにウェッブページを送信し、カスタマイズ画像レンダリングアセットに含まれる命令を実行して生成されたカスタマイズ画像がウェッブサーバ２１２におかれる。ウェッブサーバ２１２は、オンライン小売店ウェッブサイトを生成するために、オンライン小売店によって操作される。
【００１７】
ユーザシステム２２０は、顧客がオンライン小売店のウェッブサイトを閲覧し、カスタマイズする製品を選択し、製品をどのようにカスタマイズするかを特定して、カスタマイズ画像を受信するためのシステムである。ユーザシステム２２０は、ネットワーク２１８（Ｗｏｒｌｄ  Ｗｉｄｅ  Ｗｅｂ（ＷＷＷ）であってもよい）を介して、ウェッブサーバ２１２からウェッブページとウェッブコンテンツを要求する。
【００１８】
図２に示すシステムは、カスタマイズ画像レンダリングシステムの一例を示したに過ぎない。他の実施形態のシステムでは、図２に示すコンポーネントおよびサブコンポーネントのそれぞれを含めないようにしてもよい。さらに、例を明確に説明するために、図２は上記の様々な機能要素の個々の例を示すが、様々な実施形態において、各機能要素は、１以上のローカルなまたは分散したコンピューター、プロセッサ、ソフトウェア要素、あるいは他のロジックとして組み込まれてもよい。
【００１９】
２．２  領域情報利用処理の例
図３に、図２に示すカスタマイズ画像レンダリングシステムのようなカスタマイズ画像レンダリングシステムに実装される処理の一例を示す。図３に従うと、カスタマイズ画像を生成するための命令を含むカスタマイズ画像レンダリングアセットが、分割処理に従って決定された領域情報の一部に基づいて決定される。図３の処理は、画像処理システム２０４によって実行される。
【００２０】
ブロック３０２で、製品の写真が撮影される。撮影された製品は視覚的に見えるようにマークアップが刷られる、あるいは、他の方法で付けられる。ある実施形態では、撮影される製品は、人や動物がモデルになって撮影される。写真は、カメラ１０２のような１以上のカメラで撮影される。ブロック３０４で、図２の写真収集および処理システム２０４のような写真収集および処理システムが、製品を撮影した写真を受信する。ブロック３０６で、写真収集および処理システムでカスタマイズ画像レンダリングアセット生成命令が実行される。カスタマイズ画像レンダリングアセット生成命令が実行されると、カスタマイズ画像レンダリングアセットが生成される。
【００２１】
ブロック３０８で、カスタマイズ画像レンダリングアセットが、ウェッブサーバに送信される。複数の製品が個々に写真に取られ、写真収集および処理システムで、様々なカスタマイズ画像レンダリングアセットが複数の製品のそれぞれに対して生成されて、各カスタマイズ画像レンダリングアセットがウェッブサーバに送信される。
【００２２】
ブロック３１０で、カスタマイズ画像レンダリングアセットが、ウェッブサーバ１１２などのウェッブサーバで受信されて記憶される。ウェッブサーバは、様々なカスタマイズ画像レンダリングアセットを記憶する。ブロック３１２で、ウェッブサーバは、顧客のカスタマイズ仕様を受信する。顧客は、ユーザシステムで表示されたウェッブページ上にあるグラフィカルインターフェースを用いてインタラクティブに仕様を設定する。ユーザのカスタマイズ仕様は、カスタマイズ可能な製品に付ける（imprint）ユーザ向けのデザイン、特定のカスタマイズを入れる位置を特定する位置情報、縁飾りの色などの製品の細部の色、製品全体の色、および、他のカスタマイズ仕様の情報が含まれる。
【００２３】
ブロック３１４で、特定のカスタマイズ画像レンダリングアセットの命令が実行される。ウェッブサーバは、各カスタマイズ可能な製品に対するカスタマイズ画像レンダリングアセットを記憶する。ウェッブサーバは、受信したカスタマイズ仕様に基づいて、カスタマイズ画像レンダリングアセットの命令を実行するために、自動的に特定のカスタマイズ画像レンダリングアセットを選択する。例えば、顧客が特定のカスタマイズ可能な製品をカスタマイズするための選択を決定したのに応じて、ウェッブサーバは、特定のカスタマイズ可能な製品に対応する特定のカスタマイズ画像レンダリングアセットを選択する。情報はユーザによって設定され、受信したユーザのカスタマイズ仕様が含まれ、カスタマイズ画像レンダリングアセットに対する入力を自動的に決定するために用いられる。例えば、顧客が特定のシャツの色を選択して、カスタマイズ画像レンダリングアセットの命令が実行されると、選択された色（または選択された色に対応する色曲線）が、カスタマイズ画像レンダリングアセット命令の入力として与えられる。カスタマイズ画像レンダリングアセットの命令が実行されると、顧客の仕様に従ってカスタマイズした顧客が選択した製品を描いたカスタマイズ画像が得られる。
【００２４】
ブロック３１６で、ウェッブサーバはカスタマイズ仕様を提供するウェッブページをユーザシステム（ユーザシステム１２０であってもよい）に送信する。カスタマイズ画像レンダリングアセットの命令が実行された結果として決定された画像、または、その画像の変形バージョンが、ウェッブページのコンテンツに含められる。ブロック３２０で、受信したカスタマイズ画像を含むウェッブページがユーザシステムで表示される。
【００２５】
図３は、カスタマイズ画像レンダリングシステムに組み込まれる処理の一例を示したに過ぎない。他の実施形態では、異なるステップが実行されても、ステップの順番が変えられても、所定のステップがなくてもよく、あるいは、図３に示すステップに加えて追加のステップがあってもよい。
【００２６】
図４に、カスタマイズ可能な製品の視覚化において、分割処理の結果決定された領域情報を利用する処理の一例を示す。図４の処理は、画像処理システム２０４によって実行される。ブロック４０２で、マークアップを構成するカスタマイズ可能な製品の入力画像を受信する。画像処理システム２０４は、改良されたセグメンテーションを行う分割処理を開始する前に、入力画像を変形する。例えば、画像処理システム２０４は分割を行う前に入力画像から輝度情報を除くようにしてもよい。
【００２７】
ブロック４０４で、入力画像を色と色差の一部に基づいて複数の画像領域に分ける。図５に、入力画像を色と色差の一部に基づいて複数の画像領域に分ける処理の一例を示す。
【００２８】
図１１に、分割処理の結果、決定された領域情報の一例を示す。領域リスト１１０８には決定された各領域の領域レコードが含まれる。各領域に対して、領域リスト１１０８は、領域に割り当てられた画像の位置である位置ＩＤ１１１０、画像領域の代表色（領域の平均色、または、その領域に割り当てられた最初の位置の色であってもよい）である領域の色値１１１２、および、領域の範囲である領域範囲の値１１１４を特定するものである。別の実施形態では、領域レコードには、領域のエッジ上の位置であるエッジ位置が領域内に含まれる位置の数などの追加のあるいは異なるタイプの情報が含まれてもよい。特定の領域に対応するＩＤは、領域リスト中の特定の領域に対応する枠（項目）の位置に基づいて決定される。例えば、領域リスト１１０８の最初の項目は、領域ＩＤ「１」で識別される領域に対応する。
【００２９】
領域リスト１１０８は、複数のデータ構造の何れであってもよく、これに限定するものではないが、連結リスト、配列、あるいは、連結リストの配列が含まれる。
【００３０】
連結領域配列１１０２に、一実施形態に従う連結された領域の配列の最終的な形式の一例を示す。連結領域配列１１０２の各連結領域配列項目では、領域ＩＤフィールドが、連結領域配列の項目に対応する位置に割り当てられた領域を示し、次の位置フィールドが、連結領域配列の項目に対する位置と同じ領域に割り当てられた入力画像の次の位置を示す。例えば、領域ＩＤフィールド１１０４は、入力画像の２番目の位置に対応し、領域ＩＤフィールド１１０４に含まれる値「７」は、入力画像の２番目の位置に領域７が割当てられることを示す。次の位置フィールド１１０６も入力画像の２番目の位置に対応し、次の位置フィールドに設定されている値「３」は、入力画像の３番目の位置が入力画像の２番目と同じ領域が割り当てられていることを示す。
【００３１】
ブロック４０６で、分割に基づいて、少なくとも入力画像のマークアップの特定の部分を表すデータが特定される。マークアップの複数の部分を表すデータは、マークアップの特定の部分内にある１組の画像位置群である。連結領域配列１１０２や領域リスト１１０８などの決定された領域情報に基づいて、データが決定される。
【００３２】
画像処理システム２０４は、領域リスト１１０８に含まれる領域レコード情報に基づいて、特定の部分に対応する特定の画像領域を特定する。例えば、マークアップが黄と紫の市松模様であれば、画像処理システム２０４は、領域の色が黄色に近い全ての領域を特定し、それらの領域が配置される位置を特定して、効率よくマークアップの黄色の部分の位置を全て見つける。画像処理システム２０４は、領域リストに表された各領域の色差値を計算することで、領域の色の値が黄色に近い全ての領域を特定する。ここで、領域の色差値は、領域リスト１１０８に示されるように、領域の代表色が黄色からどのくらい違うかを示す。領域に対応する色差値が閾値の量よりも小さい各領域が、黄色の領域として特定され、その領域が属する各位置が黄色であると判定される。
【００３３】
特定の領域に属する全ての組みの画像位置群が、領域リスト１１０８の対応する位置ＩＤフィールドにある最初の位置の位置ＩＤを探すことで効率的に決定され、残りの位置が、領域リスト１１０８に設定された位置ＩＤが指す位置にある次の位置フィールドから始めて、連結領域配列１１０２の次の位置フィールドを辿っていくこと（traversing）で決定される。例えば、領域７が属する各位置は、領域リスト１１０８の位置ＩＤ１１１０の値を見つけることで決められ、その値は「２」である。領域７が属する次の領域は、２番目の画像位置に対する次の位置フィールドを見つけることで決められ、次の位置フィールド１１０６は、その値は「３」である。領域７が属する次の領域は、３番目の画像位置に対する次の位置フィールドを見つけることで決められ、次の位置フィールド１１０６は、その値が「０」である。一実施形態では、「０」のような値は、領域が属する追加の画像位置がないことを示すために用いられる。
【００３４】
少なくとも特定の部分を表すデータが、入力画像中のマークアップパターンの特定の部分の色などの他の情報を示す。例えば、一旦、画像処理システム２０４は、マークアップの特定の部分に属する入力画像の位置を決定し、画像処理システム２０４は、決定された位置の色情報を決定するためにオリジナルの入力画像にアクセスするようにしてもよい。
【００３５】
ブロック４０８で、マークアップの少なくとも一部を表すデータを用いて、カスタマイズ可能な製品の視覚化や、カスタマイズ可能な製品に関する製造制御が行われる。カスタマイズ可能な製品を視覚化する際にマークアップの少なくとも一部を表すデータを用いるようにすることは、データに基づいてカスタマイズ画像をレンダリングする命令を構成するカスタマイズ画像レンダリングアセットを決定することで行われる。ここで、カスタマイズ画像レンダリングアセットは、続いてウェッブサーバで使用されるために、ウェッブサーバへ送られる。カスタマイズ可能な製品を視覚化する際にマークアップの少なくとも一部を表すデータを用いるようにすることには、データに基づいてカスタマイズ画像を決定することも含まれる。
【００３６】
一実施形態では、カスタマイズ画像レンダリングアセット２１４は、使用されるとカスタマイズされた製品を自然な輪郭や形になるように視覚化したカスタマイズ画像をレンダリングする。例えば、カスタマイズ画像のカスタマイズされた製品の色および／または形は、カスタマイズされた製品をモデルが着用したときに折り目や輪郭が自然になるように描く。画像処理システム２０４は、図１に描かれた入力画像などの入力画像の分析に基づいて、カスタマイズ画像などを生成するカスタマイズ画像レンダリングアセットを決定する。
【００３７】
画像処理システム２０４は、入力画像の特定の部分と同じマークアップが描かれたサンプルの参照画像の同じ特定の部分が、色または位置に関してどのように違うのかを決定するために、分割処理によって決定された領域の情報を利用する。例えば、サンプルの参照画像では、マークアップ１０２の各四角の線は、真直ぐで互いに平行に現れるが、カスタマイズ可能な製品が捻じれたり折れたりしているような区間では、入力画像の中の区間で傾いたり分離したりして現れている。サンプルの参照画像は、平面画像である点を除くと、入力画像に描かれたものと同じマークアップが描かれている。画像処理システム２０４は、サンプルの参照画像中の位置を入力画像の位置にマッピングして、２つの画像で２箇所の位置と色がどのように違うかを比較する。画像処理システム２０４は、入力画像とサンプルの参照画像がどのように違うかを分析した結果に基づいてカスタマイズ画像レンダリングアセット２１４を生成する。
【００３８】
カスタマイズ画像レンダリングアセット２１４は、カスタマイズ可能な製品に適用されるカスタマイズを描いた平面のカスタマイズ仕様画像に基づいて、カスタマイズ画像をレンダリングする。カスタマイズ仕様は、カスタマイズ可能な製品に付けるために顧客がアップロードした画像、デザイン、またはテキストである。カスタマイズ画像レンダリングアセット２１４は、入力画像に描かれた折り目や輪郭を描くためにカスタマイズ仕様の画像を変形することによって、一部にカスタマイズ画像を生成する。
【００３９】
一実施形態では、画像処理システム２０４は、領域情報に基づいてマークアップのグリッド画像を決定する。ここで、マークアップのグリッド画像は異なるマークアップ部分間のエッジを特定するものである。例えば、画像処理システム２０４は、入力画像を分割することによって特定された領域情報の一部に基づいてマークアップのグリッド画像を決定する。図１２は、図１に描かれた入力画像を分割することによって特定された領域情報の一部に基づいて決定されたマークアップのグリッド画像を描画したものである。画像処理システム２０４は、マークアップのグリッド画像の一部に基づいて、カスタマイズ画像レンダリングアセット２１４を決定する。
【００４０】
カスタマイズ画像レンダリングアセットを決定するためにマークアップのグリッド画像を利用する処理の例が、米国特許出願第１３／７３６，８４４号、米国特許出願第１３／３４２，１０３号、米国特許出願第１２／７９０，７１１号と、米国特許第８，１７４，５２１号、米国特許第８，１７５，９３１号、米国特許第８，０９０，４６１号の各明細書に、さらに記載されているが、他の処理が異なる実施形態で用いられる。この段落に記載された全ての特許出願および特許の内容が参照されて、ここに説明されたものとして、あらゆる目的のために、そのまま援用される。
【００４１】
マークアップのグリッドの線は、色分け画像のマークアップの四角間の境の形状に対応する。マークアップの線の形状がデザイン領域の製品の形状を示している。例えば、斜めになった線は、対応する位置で製品が傾いていることを示す。このような情報は、注文したデザインが カスタマイズ可能な製品のデザイン領域にプリントしたときにどのように現れるかを示すものである。一実施形態では、複数のデザイン領域があれば、デザインの形状情報が、各デザイン領域に対して決定される。図１２のマークアップのグリッド画像は、粗い平行線であるが、他の実施形態では、マークアップのグリッド画像は、マークアップに基づいて決定されたものであれば、様々な異なる形状および／またはパターンであってもよい。一実施形態では、平面のデザイン画像に基づいて決定されたグリッドを、マークアップのグリッド画像に基づいて、決定されたグリッドにマッピングして、画像の様々な位置で、２つの画像で位置および／または色がどのように異なるかを比較する命令を決定する。
【００４２】
図１２のマークアップのグリッド画像を分析して、カスタマイズ画像レンダリングアセットを決定する。カスタマイズ画像レンダリングアセットは、ユーザの仕様に従ってカスタマイズした製品を描いた画像をレンダリングするための命令で構成される。ユーザが製品に付けるユーザの画像を提供すると、カスタマイズ画像レンダリングアセットが、製品に付けられる画像が製品にどのように現れるのかを描く。カスタマイズ画像レンダリングアセットによって生成されたカスタマイズ画像に、入力画像の例と同じ形状と輪郭が描かれる。例えば、カスタマイズ画像は、入力画像の例に描かれたように同じ位置に折り目があるシャツが描かれるかもしれない。
【００４３】
図４は、領域情報を特定して利用する処理の一例を示したに過ぎない。一実施形態では、異なるステップが実行されても、ステップの順番が変えられても、所定のステップがなくてもよく、あるいは、図４に示すステップに加えて追加のステップがあってもよい。
【００４４】
他の実施形態では、決定された領域情報がカスタマイズされた製品の製造の制御に利用されてもよい。ここで、用いられる「製造」は、製造される前の製品上に特定のカスタマイズを付けることをいう。例えば、領域情報は、カスタマイズされた製品の特定のカスタマイズ部分の位置を決定し、特定のカスタマイズ部分の色と位置が期待される範囲内の色と位置になるために利用される。
【００４５】
他の例では、注文用の製品の提供者は、注文用の製品に顧客が指定した仕様でカスタマイズした製品を製造するメーカーに提供する。注文されたインプリント用に新しい製品を取り入れる際、メーカーは製品のインプリントのレイアウトを特定する。ここで、インプリントのレイアウトとは、デザインを付ける製品の位置を特定するものである。例えば、携帯電話ケースのメーカーは、携帯電話ケースのカメラ穴に対応する携帯電話のケースの特定の領域には、注文されたデザインが入らない領域であることを指定する。インプリントのレイアウトでは、カメラの穴より下が注文されたデザインを入れる領域として指定される。
【００４６】
メーカーから製品に付けるレイアウトを受信すると、提供者は注文用の製品にマークアップ画像を付けるためにメーカーに送信する。メーカーは、製品にマークアップ画像を付けて、カスタマイズされた製品を提供者に送信する。提供者は、製品の特徴に対して注文用のデザインを付けて見た目がよいかを確認するために、注文したインプリントされた製品を目で見て検査する。提供者は、検査結果に応じて付けられたレイアウトを調整するようにしてもよい。例えば、メーカーは、注文されたデザインを携帯電話のカメラの穴に対応する位置には付けないように指定したにもかかわらず失敗することがある。注文したインプリントされた製品を受信したときに、提供者は、デザインの一部がカメラの穴にかかるところにあるようなデザイン部分はよくないので、携帯電話のケースのデザインの配置は見た目がよくないと判断する。提供者はカメラの穴の領域にデザイン領域がかからないようにサイズを変えたり、カメラの他の場所にデザイン領域を移動させたりする。一実施形態では、提供者は、メーカーによる検討および承認のために別のインプリントのレイアウトをメーカーに提案するようにしてもよい。
【００４７】
２．３  マークアップ画像分割処理の例
図５に画像分割処理の一例を示す。図５の処理は、画像処理システム２０４によって実行される。ブロック５０２で、色差値は入力画像内の複数の位置の各位置に割当てられる。ある実施形態では、各位置は、入力画像の別個のピクセルであり、入力画像の各ピクセルに色差値が割り当てられる。色差値は対応する位置の色が隣接した位置の色とどのくらい違うかを示すものである。
【００４８】
一実施形態では、特定の位置の色差値は、特定の位置の色と２，４，および６個分位置が離れている位置の色を比較して決定される。色差値は、それぞれの距離に応じて計算され、３つの色値（それぞれが異なる距離の関連する）が平均されて、最終的な色差値を決定する。色差値の平均をとることには、距離が近い色差値より距離が離れている色差値の重みを大きくする重み付けが含まれてもよい。中心のピクセルの色と、ある距離離れたところにある異なる位置でサンプリングされた色の平均値がどのくらい違うかを決定することで、距離に対する色差値が計算される。２つの位置の色差値は、２つの色間の違いの内積を計算することで算出される。
【００４９】
図６に、中心位置に対する色差値を決定するために分析される色の位置を表す図の一例を示す。一実施形態では、中心位置６０２に対する色差値を、式１を用いて計算する。
【００５０】
【数１】
2014179090.tif 000003
【００５１】
他の実施形態では、色差値の決定は、より多くまたはより少ない位置でサンプリングしたもの、異なる距離の位置でサンプリングしたもの、および／または、決定された色差値に対して異なる重みを割り当てたもので構成してもよい。
【００５２】
ブロック５０４で、色差値間の変動が減少するように色差値を平滑化する。一実施形態では、相対的に高い色差値および相対的に低い色差値がそれぞれ、より低くおよびより高くなるように変える。例えば、最も高い色差値の上位１０パーセント、または、最も低い色差値の１０パーセントにある色差値のみが変更される。一実施形態では、モノクロ画像が入力画像に基づいて生成され、各ピクセルの色はそのピクセルの色差値を表す。色差値の平滑化には、モノクロの色差値画像に対してガウシアンフィルターを適用する手法が含まれる。領域を割り当てる前に色差値の平滑化を行うことで、入力画像を必要以上に分割しないようにすることができる。
【００５３】
ブロック５０６で、位置をその位置に関する色差値に基づいてソートする。ソートには、その位置に関する色差値に基づいて、画像位置を異なるグループに分けることが含まれてもよい。図８に、色差値に基づいて画像位置をソートする処理の一例を示す。ブロック５０８で、位置が領域に割り当てられ、領域に対する位置の割り当てが、少なくとも一部はソート順に基づいて発生する。図１０に、領域に対して画像位置を割り当てる処理の一例を示す。
【００５４】
画像処理システム２０４は、分析して入力画像の一部を領域に分けたり、分析して全ての入力画像を複数の画像領域に分けたりする。画像処理システム２０４は分析して入力画像の一部を領域に分ける実施形態では、色差値と領域割り当てが、入力画像の領域の一部分の位置に対してのみ決定される。
【００５５】
図５は、画像分割処理の一例を示したに過ぎない。他の実施形態では、異なるステップが実行されても、ステップの順番が変えられても、所定のステップがなくてもよく、あるいは、図５に示すステップに加えて追加のステップがあってもよい。
【００５６】
図７に、それぞれの位置に関連する色差値に基づいて位置をソートするために用いられる色差データの一例と、ソート処理の結果を得るために用いられるソートリストおよび色差配列の一例を示す。ソートリスト７１２と連結領域配列７０６は、色差配列７０２に基づいてデータが設定される。
【００５７】
色差配列７０２は、入力画像の各位置に対して決定された色差値を示す。色差配列７０２の各枠（項目）は入力画像の特定の位置に対応し、枠（項目）の値が入力画像の対応する位置の色差値を示す。
【００５８】
ソートリスト７１２には、色差配列７０２に含まれる各色差値の大きさに応じた項目を設ける。例えば、色差配列７０２の色差値が１−５の範囲であれば、ソートリスト７１２は５つの項目で構成される。一実施形態では、ソートリスト７１２に全てデータが設定されると、ソートリスト７１２の各項目は、特定の大きさに関連づけられ、（１）特定の色差値の画像位置、および／または、特定の色差値の画像位置に対応する連結領域配列の項目を指す値、または、（２）入力画像に特定の大きさの色差値の位置がないことを示す値（例えば、値が「０」）、のどちらかが含まれる。例えば、ソートリスト７１２の最初の項目であるソートリストの項目７１４に色差値の大きさ「１」に関連付けられる。ソートリストの項目７１４に「１２」が設定されていると、それは、入力画像の１２番目の位置だけでなく、連結領域配列７０６の１２番目の位置（連結領域配列の項目７１２）を指す。色差値７０４の値「１」によって示されるように、入力画像の１２番目の位置が、色差値７０４が「１」であることに関連付けられる。
【００５９】
連結領域配列７０６には、入力画像の各位置に対して項目が設けられ、各項目は特定の位置に対応する。各項目は領域ＩＤフィールドと次の位置フィールドで構成される。連結領域配列７０６の領域ＩＤフィールドに全てデータが設定されると、各領域ＩＤフィールドには、対応する位置に割当られた領域を示す値が設定される。例えば、領域ＩＤフィールド７０８は入力画像の２番目の位置に対応し、領域ＩＤフィールド７０８に設定されている値「７」は、入力画像の２番目の位置が領域７に割り当てられたことを示している。領域割当処理が起動されるまでは、連結領域配列７０６の領域ＩＤフィールドが空のままで残っていたり、０や他の値で初期化されていたりする。
【００６０】
ソート処理に従って連結領域配列７０６の次の位置フィールドに全てデータが設定された後、特定の次の位置フィールドの値は、（１）特定の「次の位置」に関連する入力画像の位置と同じ色差値に関する他の画像位置を指す、および／または  特定の次の位置フィールドに関連する入力画像の位置と同じ色差値に関する他の位置に対応する他の連結領域配列の項目を指す、または、（２）特定の次の位置フィールドに対応する入力画像位置と同じ色差値を持つ画像位置に対応する連結領域の項目がこれ以上ないことを示す。
【００６１】
一実施形態では、画像処理システム２０４は、各画像位置に対して、入力画像の位置に対応する連結領域配列の項目と色差配列の項目を特定するためのマッピングを保持する。他の実施形態では、単一の位置ＩＤが色差配列７０２の特定の色差配列項目、連結領域配列７０６の特定の連結領域配列項目、および、特定の画像位置を指すように、連結領域配列７０６と色差配列７０２におけるデータの並び順が画像位置の並び順に対応する。例えば、ソートリストの項目７１４の値「１２」は、色差配列７０２の１２番目の項目と、連結領域配列７０６の１２番目の項目の両方を指し、両方が入力画像の１２番目の位置に対応する。ソートリストの項目７１４の値「１２」は、入力画像の１２番目の位置も指す。
【００６２】
ソートリスト７１２と連結領域配列７０６が、領域割当処理を行っているときに用いられ、特定の色差値および／またはそれに対応する連結領域配列の項目に関連する全ての画像位置を効率的に配置する。同じ色差値を持つ画像位置に対応する様々な連結領域配列の項目が、連結領域配列の次の位置フィールドを介して連結される。色差値に対応する画像位置を指すソートリスト７１２の中から特定の色差値に対応するソートリストの項目を最初に検索することで、特定の色差値に関連する各位置が効率的に特定される。特定の色差値に関連付けられる残りの画像位置は、続く連結領域配列７０６の次の位置フィールドによって特定され、連結領域配列のそれぞれは特定の色差値に関連付けられる次の画像位置、または、特定の色差値に関連付けられる次の画像位置に対応する次の連結領域配列の位置を指す。
【００６３】
例えば、色差値「１」に対応する各入力画像の位置が、値「１」に対応するソートリストの項目（ソートリスト７１２の最初の項目であるソートリストの項目７１４）にアクセスすることで特定される。ソートリストの項目７１４は、色差値「１」の最初の画像位置を特定する。ソートリストの項目７１４の値には「１２」が設定されているので、画像処理システム２０４は、入力画像の１２番目の位置が色差値「１」に関連付けられていると判定する。色差値「１」に関連付けられる次の画像位置は、連結領域配列７０６の１２番目の位置に対する「次の位置フィールド」である次の位置フィールド７１０にアクセスすることによって決められる。次の位置フィールド７１０には、色差値「１」に関連付けられるそれ以上の位置がないことを示す「０」などの値が設定されている。他の実施形態では、１２番目の位置に対する次の位置フィールドが、色差値「１」に関連付けられる他の画像位置、または色差値「１」に関連付けられる画像位置に対応した他の連結領域配列の項目を指すようにしてもよい。
【００６４】
図８に、色差値に基づく画像位置のソート処理の一例を示す。処理は、色差値に基づいて、ソートリストと連結領域配列にデータを設定するように構成する。処理は、画像処理システム２０４によって実行される。画像処理システム２０４は、対応する画像位置にそれぞれ関連付けられた色差配列の値の初めから終わりまで繰り返し処理を行い、ソートリストまたは連結領域配列のどちらかに、対応する画像位置を示す位置識別子を記憶する。ソートには、例えば、特定の位置の位置識別子を同じ色差値の他の位置を示す位置識別子のリストに追加することで、同じ色差値を持つ画像位置のグループにまとめることが含まれる。
【００６５】
図９に、図８に示す処理に従って、色差配列７０２に記憶された色差値に基づいて一部にデータが設定されたソートリストと連結領域配列の内容を示す。ソートリスト９０２Ａ、９０２Ｂと連結領域配列９０６Ａ、９０６Ｂは、同じソートリストと連結領域配列の異なる状態を示しているが、図８の処理に従って、色差配列７０２に基づいてデータが設定される。ソートリスト９０２Ａと連結領域配列９０６Ａは、図８に示す処理を１回だけ行った時のソートリストと連結領域配列を示す。ソートリスト９０２Ｂと連結領域配列９０６Ｂは、図８の処理を２回繰り返した時のソートリストと連結領域配列を示す。図８の処理を開始する前は、ソートリスト９０２Ａと連結領域配列は初期値のみが入っている。例えば、ソートリスト９０２Ａと連結領域配列９０６Ａは図４の処理が開始する前は、値は何も入っていない、あるいは、全てに値「０」が入っていてもよい。
【００６６】
ブロック８０２で、画像処理システム２０４は現在位置の色差値を決定する。処理の開始時は、現在位置は入力画像の最初の位置である。現在位置の色差値は、現在位置に対応する色差配列の項目の値にアクセスして決定する。ある実施形態では、色差配列の色差値は、色差値に対応する位置の順にしたがって並べられる。例えば、最初の画像位置に対する色差値が、色差配列の最初の項目の値になる。
【００６７】
次のブロック８０４で、画像処理システム２０４は、決定された色差値に対応するソートリストの項目に既に位置ＩＤが設定されているかを判定する。決定された色差値に対応するソートリストの項目に位置ＩＤが設定されているかの判定は、ソートリストの項目に初期値とは異なる色差値が設定されているかを判定することで行われる。例えば、ソートリスト９０２Ａは「０」の値で初期化され、決定された色差値に対応するソートリストの項目に位置ＩＤ設定されているかの判定は、ソートリストの項目に「０」以外の値が設定されているかを判定することで行われる。
【００６８】
画像処理システム２０４が、決定された色差値に対応するソートリストの項目に位置ＩＤが設定されていないと判定した時は、処理はブロック８０６に進んで、決定された色差値に対応するソートリストの項目に現在位置の位置ＩＤが記憶される。ソートリストと連結領域配列のデータ設定処理が行われている間に、以前に現在位置と同じ色差値を持つ位置が検討されていなければ、ソートリストには位置ＩＤが設定されない。例えば、１回目の処理が行われると、画像処理システム２０４は、色差配列７０２の最初の値（その値が「４」である）を捜して、最初の画像位置の色差値を決定する。これに応じて、ソートリスト９０２Ａの４番目の項目であるソートリスト項目９０４Ａを更新して、最初の画像の位置ＩＤの値「１」を記録する。ソートリスト９０４Ａは、前もって「０」または他の初期値が設定されている。
【００６９】
ブロック８１２で、画像処理システム２０４は、現在位置が入力画像の最後の位置であるかを判定する。現在位置が入力画像の最後の位置でなければ、処理はブロック８１４に進み、現在位置を入力画像の次の位置まで増やす。例えば、１回目の処理が完了した後で、現在位置を入力画像の２番目の位置に増やして、入力画像の２番目の位置を入力画像の現在位置として、図８の処理が繰り返される。
【００７０】
ブロック８０２で、新たな現在位置の色差値が、色差配列７０２の色差値７１６を探して「４」に決定される。ブロック８０４で、処理は、決定された色差値に対応するソートリストの項目に位置ＩＤが既に設定されているかを判定する。値「４」に対応するソートリストの項目、ソートリスト項目９０４Ａには、位置ＩＤ「１」が設定されている。このように、決定された色差値に対応するソートリストの項目に位置ＩＤが既に設定されていれば、処理がブロック８０８に進められる。
【００７１】
ブロック８０８で、ソートリストの項目に既に記録された位置ＩＤを、連結領域リストの現在位置に対する次の位置フィールドに移動する。例えば、ソートリストの項目９０４Ａに記録された値「１」を、連結領域配列９０６Ｂの２番目の画像位置に対する次の位置フィールドである次の位置フィールド９０８Ｂに移動する。ブロック８１０で、現在位置の位置ＩＤを、ソートリストの配列のうち決定された色差値に対応するソートリストの項目に記憶する。例えば、入力画像の２番目の位置の位置ＩＤの値「２」を、色差値「４」に対応するソートリストの項目であるソートリストの項目、ソートリスト項目９０４Ｂに記録する。
【００７２】
ブロック８１２で、画像処理システム２０４は、現在位置が入力画像の最後の位置であるかを判定する。現在位置が入力画像の最後の位置である場合は、ブロック８１６で処理は終了する。現在位置が入力画像の最後の位置でない場合は、処理はブロック８１４に進み、現在位置が入力画像の次の位置まで増やされる。分析する画像位置がなくなるまで、各位置で処理が繰り返される。図８の処理が完了すると、ソートリストと連結領域配列の次の位置フィールドの全てに入力画像の各位置の位置ＩＤが入れられる。
【００７３】
各位置の情報を辿って領域割当処理が行われている間は、連結領域配列とソートリストが用いられ、位置の色差値に基づいた順番にしたがってその位置が検討される。一実施形態では、色差値が小さい位置、すなわち、その位置の近くの位置の色がとても似ているような位置が、色差値が大きい位置より先に領域が割り当てられる。例えば、決定された色差値の範囲が１−５の画像に対して、画像処理システム２０４は、最初に色差値が１の各位置に領域が割り当てられ、続いて色差値が２の各画像位置に対して領域が割り当てられ、全ての位置に領域が割り当てられるまで続けられる。
【００７４】
一実施形態では、画像位置に割り当てられた領域が比較的少ない場合は、他の画像位置が割り当てられていない新しい領域が、画像位置に割り当てられる可能性が高い。例えば、検討中の入力画像の位置に隣接する１以上の画像位置に領域が既に割り当てられている場合は、検討中の入力画像の位置に対する領域は隣接する領域の１つから選択される。検討中の入力画像の位置に、領域が割り当てられてない画像位置だけが隣接している場合には、入力画像の位置に、画像位置が割り当てられてない新しい画像領域が割り当てられる。このような処理に従って、最初に領域の割り当てが検討された入力画像の位置は、決定された領域の中心にあり、他の領域との境界の位置では無い可能性が高い。つまり、その色差値に基づいて位置に領域を割り当てることにより、色差値が小さい位置（すなわち、その周囲にある位置ととても似ている位置）は、決定された領域の中心、または、他の領域との境界ではない位置にある可能性が高い。このような画像分割手法の結果として、他の手法に従って決定された領域よりさらに均一な色の領域に分けられた分割画像が得られる。
【００７５】
図８は、色差値に基づいて画像位置の並び替えを行う処理の一例を示したに過ぎない。他の実施形態では、異なるステップが実行されても、ステップの順番が変えられても、所定のステップがなくてもよく、あるいは、図８に示すステップに加えて追加のステップがあってもよい。
【００７６】
図１０は、画像位置を領域に割り当てる処理の一例である。処理は、画像処理システム２０４で実行される。ブロック１００２で、入力画像の位置が現在の位置として選択される。一実施形態では、現在位置の決定は、最初または次の画像位置を決定するためにソートリストの項目または連結領域配列の項目のいずれかにアクセスすることで行われる。図１０の処理が１回行われる間に、色差値が見つけられた全ての中で最も色差値の大きさが小さいものに対応するソートリストの項目にアクセスして、最初の現在位置を決定する。ソートリストの項目に設定された値は、入力画像の中の最も小さい色差値を持つ画像位置を指す。例えば、ソートリスト７１２のソートリストの項目７１４にアクセスして、最初の現在位置を決定する。ソートリストの項目７１４に設定された位置ＩＤ「１２」に基づいて、画像処理システム２０４は入力画像の１２番目の位置を、最初の現在位置として決定する。
【００７７】
ブロック１００４で、現在位置に隣接する領域群が特定される。現在位置に隣接する領域群には、現在位置に隣接している１つ以上の位置が割り当てられた領域が全て含まれる。例えば、１つの位置が４つの他の位置に隣接し、そのうちの１つに領域「１」が割り当てられ、そのうちの２つに領域「２」が割り当てられる場合、現在位置に隣接する領域群には「１」と「２」が含まれる。隣接する位置として検討される特定の位置は、様々な実施形態に従って変えてもよい。例えば、隣接している位置には、現在位置の直ぐ上、下、左側、右側の４つの位置を全て含むようにしてもよい。他の実施形態では、隣接する位置は、さらに、現在位置の斜めに隣接する４つの位置を含むようにしてもよい。
【００７８】
次に、ブロック１００６で、画像処理システム２０４は異なる隣接領域の数が０に等しいか判定する。その場合は、画像処理システム２０４は、ブロック１００８の動作を実行し、他の位置が割り当てられていない新しい領域を現在位置に割り当てる。画像処理システム２０４は、異なる隣接領域の数が０でない場合は、ブロック１０１０で、画像処理システム２０４は異なる隣接領域の数が１に等しいか判定する。その場合は、ブロック１０１２で、画像処理システム２０４は、１つだけの隣接領域を現在位置に割り当てる。
【００７９】
画像処理システム２０４は、異なる隣接領域の数が０でも１でもない場合には、画像処理システム２０４は、ブロック１０１４で、異なる隣接領域の数が２に等しいか判定する。その場合は、ブロック１０１６で、画像処理システム２０４は、２つの隣接領域が十分に類似していて併合することができるか判定する。２つの隣接領域が十分に類似していて併合することができるかの判定は、一方の領域の代表色と他方の領域の代表色を比較することで行われる。
【００８０】
一実施形態に従えば、２つの色の差の内積が特定の差分量の閾値よりも小さい場合には、２つの色が十分に類似していて併合することができる。例えば、２つの領域の代表色が（Ａ，Ｂ，Ｃ）と（Ｘ，Ｙ，Ｚ）であるとすると、下の表記１が真であれば併合することができる。
【００８１】
［表記１］
((A-X),(B-Y),(C-Z))・((A-X),(B-Y),(C-Z)) < 閾値
ある実施形態では、画像の色は３次元で表される。例えば、色は３つの色値で構成されるＲＧＢモデルを用いて表される。他の実施形態では、画像の色が別の数の次元で表されてもよい。例えば、色が４次元のＣＭＹＫ色モデルで表されてもよい。つまり、ここに記載される処理は、特定の次元の色で表される画像に限定される必要はない。
【００８２】
様々な実施形態によれば、代表色は、これまでの領域に割り当てられた位置の色の平均であってもよく、領域に割り当てられた最初の位置の色であってもよい。領域の代表色は、新しい位置を領域に追加するたびに更新される領域の領域レコードにアクセスすることによって決定される。
【００８３】
画像処理システム２０４は、２つの領域が十分に類似しているので併合できると判定すると、ブロック１０２２で、画像処理システム２０４は、２つの領域の一方の領域を２つの領域の他方の領域へ併合する。一実施形態では、２つのうち後で見つけた領域を、２つのうちの先に見つけた領域に併合する。
【００８４】
一実施形態では、位置を領域に割り当てるということは、その位置に対応する領域リストの項目にその領域を示す値を記憶することである。領域が割り当てられた最初の領域は、領域ＩＤ「１」の領域に割り当てられる。次にくる位置は、以前にどの位置にも割り当てられたことがない新しい領域に割り当てられ、新しい領域の領域ＩＤとして領域ＩＤ「２」が選択される。つまり、新たに割り当てられる各領域は、既に１以上の位置に割り当てられた領域よりも大きい数値が割り当てられる。この手法に従うと、２つの領域の領域ＩＤを比較することで、２つの領域のうち新しい領域が特定される。
【００８５】
一実施形態では、２つのうちの後に見つけられた領域が、常に２つのうちの先に見つけられた領域に入れられ、併合する２つの領域を特定する領域ＩＤの値を比較して併合した後に、特定の領域がその領域ＩＤを維持する領域として選択される。小さい数値の領域ＩＤを持っている領域が、その領域ＩＤを維持する領域として選択される。選択された領域を指す領域ＩＤで置き換えられた領域リスト中の領域ＩＤの各インスタンスによって、他の領域が選択された領域に「併合される」。
【００８６】
例えば、２つの領域が併合され、１番目の領域が領域ＩＤ「１０」に関連付けられ、他の領域が領域ＩＤ「１４」に関連付けられている場合は、領域ＩＤ「１４」に対応する領域が領域ＩＤ「１０」に対応する領域に併合される。領域リストの値「１４」が発生する度に、値「１０」に置き換えられる。
【００８７】
他の実施形態では、新しい領域のそれぞれに番号を増やしながら割り当てられ、より大きい番号の領域ＩＤを持つ領域が他の領域に併合される領域として選択される。
【００８８】
一実施形態では、１つの隣接位置の領域を他の隣接位置の領域に併合することが決定したのに応じて、他の領域を併合するために選択された領域（「選択領域」）を現在の位置に割り当てる。ある実施形態では、位置に領域を割り当てるということは、領域を示す値をその位置に対応する領域リストの項目に記憶することであり、選択領域を示す値が、現在位置に対応する項目に記憶される。一実施形態では、２つの領域の併合が決定したのに応じて、領域リスト内の選択領域でないことを示す他の値が全て、選択領域を指す値に即座に置き換えられる。この文脈で「即座」とは、値が更新されるまで、他の値が領域を割り当てるために検討されることがないことをいう。
【００８９】
他の実施形態では、現在位置に対応する項目だけが、決定に応じて即座に更新される。他の領域に併合される領域がどれであるかの印が記録され、画像中の各位置に領域ＩＤが割り当てられた後に、選択領域でないことを示す領域ＩＤが入っている領域リストの残りの項目が更新され、選択領域を指す領域ＩＤを設定する。
【００９０】
一実施形態では、領域ＩＤの値が大きい領域は、領域ＩＤの値が小さい領域の領域ＩＤを一貫して採用する、あるいは、一貫して逆であってもよい。併合された領域の領域ＩＤの更新は、各位置の領域ＩＤが記憶されているリストを１回辿ることで完了する。
【００９１】
ブロック１０２４で、２つの領域が併合されると、他の領域が併合された領域に現在の位置が割り当てられる。
【００９２】
画像処理システム２０４は２つの領域が併合できるほど十分に類似していないと判断した時は、ブロック１０１８で、画像処理システム２０４は、現在位置の色と隣接する領域の代表色を比較して、現在位置に色が最も類似している領域に現在位置を割り当てる。一実施形態では、２つの色差の量、現在位置の色と１つの領域の代表色とを比較した１つの色差の量と、現在位置の色と他の領域の代表色とを比較した他の色差の量とが、計算される。２つの色を比較した色差の量は、２つの色の差の内積を計算することにより決定される。色に関して現在位置とは違いが最も少ない領域が、選択領域として特定される。
【００９３】
画像処理システム２０４が隣接する領域の数が０，１，または２と等しくないと判定したときは、画像処理システム２０４はブロック１０２０に進む。この場合、現在位置が少なくとも３つの異なる領域に隣接する。ブロック１０２０で、画像処理システム２０４が、隣接する領域群のうち現在位置の色に最も似ている代表色をもつ領域に現在位置を割り当てる。そのような領域は、３つの領域それぞれについて色差値を計算することで特定され、領域のダイバージェンス（divergence）値が領域の代表色が現在位置の色とどのくらい違うかを示す。色差値が最も小さい領域が現在位置に割り当てられる割当領域として選択される。
【００９４】
領域が現在位置に割り当てられると、ブロック１０２６で、画像処理システム２０４は、現在位置に割り当てられた領域の領域レコードを更新する。１つの領域に対して保持される領域レコードは、領域に割り当てられた最初の色、領域に割り当てられた色の平均値、および／または領域の範囲を特定する。
【００９５】
ブロック１０２８で、検討する位置がさらにある場合は、現在位置を次のソートされた位置まで増やす。現在位置に対する次の位置にアクセスすることによって、少なくとも一部では次のソートされた位置が特定される。例えば、現在位置が入力画像の１２番目の位置である場合は、入力画像の１２番目の位置に対応する次の位置フィールドは、次のソート位置を指す。入力画像に現在位置と同じ色差値の他のすべての位置に既に領域に割り当てられていれば、次の位置フィールドは０のような初期値が設定される。この場合、次のソートされた位置が、色差値の大きさが次に大きいソートリストの項目にアクセスすることによって決定される。例えば、ソートリストの項目７１８は色差値の大きさ「２」に対応し、値「７」が設定されている。従って、次のソート位置は入力画像の７番目の位置である。例えば、現在位置の色差値が「１」であれば、色差値が「２」のソートリストの項目にアクセスすることによって、次の位置を決定する。ソートリストに検討されていない項目がない場合には、さらに検討する位置はなく、図１０の処理には終了する。
【００９６】
図１０は、画像位置を領域に割り当てる処理の一例を示したに過ぎない。他の実施形態では、異なるステップが実行されても、ステップの順番が変えられても、所定のステップがなくてもよく、あるいは、図１０に示すステップに加えて追加のステップがあってもよい。
【００９７】
一実施形態では、領域割当処理が完了した後に、連結領域配列７０６の次の位置フィールドに設定された位置ＩＤの少なくともいくつかが、別の位置ＩＤに置き換えられる。置き換え前は、特定の画像位置に対応する次の位置フィールドに記憶された位置ＩＤが他の画像位置、または、他の画像位置に対応する連結領域配列の項目を示すが、他の画像位置は、特定の位置と同じ色差値に関連するものである。置き換え後は、特定の画像位置に対応する次の位置フィールドに記憶されている位置ＩＤは、他の画像位置、または他の画像位置に対応する連結領域配列の項目を指すが、他の画像位置は、特定の位置と同じ領域に割り当てられたものになる。つまり、置き換え後、連結領域配列の次の位置フィールドが、同じ色差値に関連する他の位置に変わって同じ領域の他の位置につながる。連結領域配列１１０２は変更後の連結領域配列に記録された値を示す連結領域配列の一例である。
【００９８】
２．４  他の形態および拡張
明確に例を示すために、上記のように、図７、９、および１１に個々のデータ構造を示す。しかし、様々な実施形態において、各データ構造が複数のデータ構造で構成されていてもよい。さらに、他の実施形態では、ここに記載の色差値、次の位置情報、領域ＩＤ、および位置ＩＤなどのデータのそれぞれは、どのような種類のデータ構造で記憶されていてもよく、配列や連結されたリストに限定されるものではない。
【００９９】
前記の記載のあらゆる場所に、および、実施形態の内容を理解するのに最も容易にする位置に、別の実施形態が記載されている。さらに、発明は、それらの特定の実施形態を参照しながら記載される。しかしながら、より広い発明の概念から離れることなく、様々な修正や変更が発明に入れられることは明らかであろう。従って、明細書および図面は、それに応じて、限定的する趣旨ではなく実例として見なされる。
【０１００】
さらに、この記載において、いくつかの処理ステップが、特定の順番、アルファベットの順番で説明され、英数字のラベルがいくつかのステップを特定するために用いられる。記載中に特に決められてない場合は、そのようなステップを実行する特定の順番に実施形態を限定する必要はない。特に、ラベルは便宜上ステップを特定するために用いられるだけであって、そのようなステップを実行する特定の順番を特定し、あるいは要求することを意図するものではない。
【０１０１】
ここに記載された様々な実施形態の関数の実装は、ハードウェア、ソフトウェア、ファームウェア、および／または、利用可能な他の機能部品または構成要素で、同等に組み込まれる。特定の装置またはプログラムの順番に限定されることを意図するものではない。他の変更や実施形態が、上記の技術に照らして利用可能である。
【０１０２】
３．実装の仕組み―ハードウェアの概要
一実施形態に従えば、ここに記載の技術は、１以上の専用コンピューター装置によって実施される。専用コンピューター装置は、この技術を実行するハードウェアであっても、または、この技術を実行するためのプログラムを永久的に記憶する１以上の特定用途向け集積回路（ＡＳＩＣ）やＦＰＧＡ（ｆｉｅｌｄ  ｐｒｏｇｒａｍｍａｂｌｅ  ｇａｔｅ  ａｒｒａｙｓ）などのデジタル電子装置を設けるようにしても、または、ファームウェア、メモリ、他の記憶部、あるいは、これらの組み合わせに記憶されたプログラム命令に従って、この技術を実行するようにプログラムされた汎用のハードウェアの処理部を設けるようにしてもよい。このような専用コンピューター装置は、技術を達成するために、カスタマイズされたハードウェアロジック、ＡＳＩＣ、または、プログラムをカスタマイズしたＦＰＧＡを組み合わせたものであってもよい。専用コンピューター装置は、デスクトップコンピューターシステム、ポータブルコンピュータシステム、ハンドヘルド装置、ネットワークデバイス、または、技術を実装するためのハードウェア論理回路および／またはプログラム論理回路が組み込まれた他の装置であってもよい。
【０１０３】
例えば、図１３は、本発明の実施形態を実装したコンピューターシステム１３００を示すブロック図である。コンピューターシステム１３００には、情報を通信するためのバス１３０２、または、他の通信機構と、情報を処理するためにバス１３０２に接続されたハードウェアプロセッサ１３０４とを備える。ハードウェアプロセッサ１３０４は、例えば、汎用のマイクロプロセッサであってもよい。
【０１０４】
コンピューターシステム１３００には、ランダムアクセスメモリ（ＲＡＭ）または動的記憶装置などのメインメモリ１３０６を備え、情報、および、プロセッサ１３０４で実行される命令を格納するためにバス１３０２に接続される。メインメモリ１３０６は、プロセッサ１３０４で実行される命令の実行中は、一時的な変数や他の中間情報を記憶するためにも用いられる。このような命令がプロセッサ１３０４でアクセス可能な記憶媒体に格納されると、コンピューターシステム１３００が、命令で特定されたオペレーションを実行してカスタマイズされた専用マシンとして機能する。
【０１０５】
コンピューターシステム１３００はさらに読み出し専用メモリ（ＲＯＭ）１３０８またはバス１３０２に接続された他の静的記憶装置が設けられ、静的な情報とプロセッサ１３０４の命令が格納される。磁気ディスクや光ディスクのような記憶装置１３１０が提供され、情報と命令とを格納するためにバス１３０２に接続される。
【０１０６】
コンピューターシステム１３００は、コンピューターユーザに情報を表示するために、陰極線管（ＣＲＴ）などディスプレイ１３１２がバス１３０２を介して接続される。入力装置１３１４は、アルファベットキー、数字キー、および他のキーが設けられ、情報とコマンドの選択をプロセッサ１３０４に通信するためにバス１３０２に接続される。他のタイプのユーザ入力装置は、マウス、トラックボール、または、カーソル方向キーなどの方向の情報とコマンドの選択をプロセッサに伝えるカーソル制御装置１３１６であり、ディスプレイ１３１２上のカーソルの動きを制御する。この入力装置は、通常、第１軸（例えば、Ｘ）と第２軸（例えば、Ｙ）の２軸の２自由度があり、この装置で平面上の位置を指定する。
【０１０７】
コンピューターシステム１３００は、カスタマイズしたハードウェア論理回路、１以上のＡＳＩＣまたはＦＰＧＡ、ファームウェアおよび／またはプログラム論理回路を用いて、コンピューターシステム１３００を専用機として機能させるために、これらをコンピューターシステムと組み合わせて、または、コンピューターシステム１３００をプログラムすることで、ここに記載された技術を実装する。一実施形態に従えば、メインメモリ１３０６に含まれる１以上の命令の１以上のシーケンスをプロセッサ１３０４が実行することで、ここに記載された技術がコンピューターシステム１３００によって機能する。このような命令が、記憶装置１３１０などの他の記憶媒体からメインメモリ１３０６に読み込まれる。メインメモリ１３０６に組み込まれた命令のシーケンスの実行することで、プロセッサでここに記載された処理ステップを実行する。他の実施形態では、ハードウェア回路が、ソフトウェア命令の代わりに、または、ソフトウェア命令と組み合わせて用いられる。
【０１０８】
ここで用いられる「記憶媒体」は、機械を特定の手法で操作するデータおよび／または命令を格納するあらゆる媒体を指す。このような記憶媒体は、不揮発性媒体および／または揮発性媒体で構成される。不揮発性媒体には、例えば、記憶装置１３１０のような光ディスクまたは磁気ディスクが含まれる。揮発性媒体には、メインメモリ１３０６などのダイナミックメモリが含まれる。記憶媒体の通常の形式には、例えば、フロッピーディスク（登録商標）、フレキシブル（登録商標）ディスク、ハードディスク、ソリッドステートドライブ、磁気テープ、または他の磁気データ記憶装置や、ＣＤ−ＲＯＭまたは他の光データ記憶装置や、あらゆる穴のパターンがある物理的な媒体や、ＲＡＭ、ＰＲＯＭ、ＥＰＲＯＭ、ＦＬＡＳＨ−ＥＰＲＯＭ、ＮＶＲＡＭ、他のメモリチップ、またはメモリカートリッジが含まれる。
【０１０９】
記憶媒体は、伝送媒体とは別のものであるが、伝送媒体と一緒に用いられてもよい。伝送媒体は、記憶媒体間の情報の転送に関するものである。例えば、伝送媒体には、同軸ケーブル、銅線、および、光ファイバーであり、バス１３０２を構成する線が含まれる。また、伝送媒体には、電波や赤外線のデータ通信中に生成される音波または光波の形式をとるものがある。
【０１１０】
媒体の様々な形式には、プロセッサ１３０４で実行される１以上の命令の１以上のシーケンスを搬送するものが含まれる。例えば、命令は、開始時に、離れて置かれるコンピューターの磁気ディスクやソリッドステートドライブ上に運ばれる。離れて置かれたコンピューターはダイナミックメモリ上に命令をロードして、モデムを用いた電話回線で命令を送信する。コンピューターシステム１３００にローカル接続されたモデムで電話回線からデータを受信することができ、データを赤外線信号に変換するために赤外線送信器を用いる。赤外線検出器は赤外線信号で運ばれたデータを受信し、適切な回路でデータをバス１３０２に載せることができる。バス１３０２は、メインメモリ１３０６にデータを運び、プロセッサ１３０４がメインメモリから命令を取り出して実行する。メインメモリ１３０６で受信された命令は、プロセッサ１３０４で実行する前または実行した後に記憶装置１３１０に任意に格納してもよい。
【０１１１】
コンピューターシステム１３００は、バス１３０２に接続された通信インターフェース１３１８を備える。通信インターフェース１３１８は、ローカルネットワーク１３２２に接続するネットワーク回線１３２０に接続している双方向のデータ通信を提供する。例えば、通信インターフェース１３１８は、サービス総合デジタル網（ＩＳＤＮ）カード、ケーブルモデム、衛星モデム、またはモデムであってもよく、電話回線のタイプに対応したデータ通信接続を提供する。他の一例として、通信インターフェース１３１８はローカルエリアネットワーク（ＬＡＮ）カードであってもよく、互換性のあるＬＡＮにデータ通信接続を提供する。また、無線回線が実装されてもよい。このようなあらゆる実装において、通信インターフェース１３１８は、様々なタイプの情報を表すデータの流れを運ぶ電気信号、電磁気信号、または光信号を送受信する。
【０１１２】
ネットワーク回線１３２０は、通常は、１以上のネットワークを通じて他の装置とのデータ通信を提供する。例えば、ネットワーク回線１３２０は、ローカルネットワークを通じてホストコンピュータ１３２４、または、インターネットサービスプロバイダー（ＩＳＰ）１３２６によって操作されるデータ機器に対する接続を提供する。同様に、ＩＳＰ１３２６は、一般的には「インターネット」１３２８といわれるワールド ワイドパケットデータ通信ネットワークを介したデータ通信サービスを提供する。ローカルネットワーク１３２２とインターネット１３２８の両方は、デジタルデータの流れを運ぶ電気信号、電磁気信号、光信号を用いる。様々なネットワークを介した信号と、ネットワーク回線１３２０上の通信インターフェース１３１８を介した信号は、デジタルデータをコンピューターシステム１３００とやり取りするものであり、伝送媒体の形態の一例である。
【０１１３】
コンピューターシステム１３００は、ネットワーク、ネットワーク回線１３２０、および通信インターフェース１３１８を介して、プログラムコードを含むメッセージを送信したり、データを受信したりする。インターネットの例では、サーバ１３３０がインターネット１３２８、ＩＳＰ１３２６、ローカルネットワーク１３２２、および通信インターフェース１３１８を介して、アプリケーションプログラムに要求コードを転送する。
【０１１４】
受信したコードは、受信されると、プロセッサ１３０４で実行され、後で実行するために、記憶装置１３１０あるいは他の不揮発性記憶に記憶される。
【０１１５】
前述の明細書において、本発明の実施形態が、実装から実装へと変わる様々な多数の詳細な形態を参照しながら記載された。従って、明細書と図面は、これに限定されることなく実際の例としてみなされるべきである。本発明の範囲の唯一かつ排他的な指標は、出願人が意図する本発明の範囲であって、本出願で公表された請求項の文言およびその均等物の範囲であり、あらゆる後の補正も含まれる。
【０１１６】
４．分割処理の命令の一例
以下は、画像を複数の領域に分割する命令の一例である。命令の少なくとも一部が、マークアップ領域特定命令２１０の一実施形態において含まれる。
【０１１７】
Initialization
Take the ColorImageInput, BucketSortList, LinkedRegionImage and ColorDistanceThreshold as inputs.
Allocate output Objects
aRegionList = new RegionList(); 
aRegionList.Init()
Allocate temporary variables
Uint32 array pointer LinkedPixelBuffer
Uint16 array pointer ColorPixelBuffer
Uint32 currentPixelIndex
Uint32 array pointer CurrentLinkedPixel
Uint16array pointer CurrentColorPixel
Uint32 currentRegionID.
Uint32 nextRegionID.
Uint32 aRegionFound
Uint32 currentRegionFoundCount.
Uint64 minDifference
Uint64 currentDifference
Set LinkedPixelBuffer = AddressOf(LinkedRegionImage[0][0])
Set ColorPixelBuffer = AddressOff(ColorImageInput[0][0]))
Allocate temporary static arrays
tempRegionRecord Array
Neighborhood Array
FoundRegions
FoundCount
Number of regions found
Fields
Uint32 RegionID
Size
Neighborhood.Size
For each non zero value, n, in the BucketSortList // traverse the bucket sort list
Set currentPixelIndex = n
While currentPixelIndex != 0 // traverse the linked list in LinkedPixelBuffer
Set CurrentLinkedPixel to LinkedPixelBuffer+ currentPixelIndex
Set CurrentColorPixel to ColorPixelBuffer + (currentPixelIndex*2)
Set FoundRegions. FoundCount = 0
Set aRegionFound = 0 
For each element, k, of the NeighboorHood Array
Set currentRegionID = CurrentLinkedPixel[NeighboorHood[k]-1] 
If currentRegionID != 0)
currentRegionID = tempRegionRecord[currentRegionID]. RegionTag
For each element, j, of the FoundRegions Array where (j < FoundRegions .FoundCount)
If currentRegionID = FoundRegions[k]. RegionID
Set aRegionFound = currentRegionID
If aRegionFound != 0
Set FoundRegions[FoundRegions .FoundCount] . RegionID = aRegionFound
Increment FoundRegions .FoundCount
If FoundRegions.FoundCount = 0
Set currentRegionID = tempRegionRecord.RegionCount
Copy CurrentColorPixel to tempRegionRecord[currentRegionID].AccumulatedColor
Set tempRegionRecord[currentRegionID].RegionArea = 1
Set tempRegionRecord[currentRegionID].CalcAverageDone = FALSE
Copy CurrentColorPixel to tempRegionRecord[currentRegionID].FirstFoundColor
Set tempRegionRecord[currentRegionID].RegionTag = currentRegionID
Increment tempRegionRecord.RegionCount
Set CurrentLinkedPixel[-1] = currentRegionID.
if FoundRegions.FoundCount = 1
Set currentRegionID = FoundRegions[0]. RegionID
Add CurrentColorPixel to tempRegionRecord[currentRegionID].AccumulatedColor
Increment tempRegionRecord[tempRegionRecord.RegionCount].RegionArea.
Set tempRegionRecord[currentRegionID].CalcAverageDone = FALSE
Set CurrentLinkedPixel[-1] = currentRegionID.
If FoundRegions.FoundCount = 2
Set currentRegionID = FoundRegions[0]. RegionID
Set nextRegionID = FoundRegions[1]. RegionID
If currentRegionID > nextRegionID
Swap currentRegionID, nextRegionID 
UpdateAverageColor(currentRegionID)
UpdateAverageColor(nextRegionID)
If ColorDifference(tempRegionRecord[currentRegionID].averageColor, tempRegionRecord[nextRegionID].averageColor) < ColorDistanceThreshold
tempRegionRecord[nextRegionID]. RegionTag = currentRegionID.
Add tempRegionRecord[nextRegionID].AccumulatedColor to tempRegionRecord[currentRegionID].AccumulatedColor
Add tempRegionRecord[nextRegionID].RegionArea to tempRegionRecord[currentRegionID].RegionArea
Set tempRegionRecord[currentRegionID].CalcAverageDone = FALSE
Set CurrentLinkedPixel[-1] = currentRegionID.
Else (set CurrentLinkedPixel region to closest Match)
If (ColorDifference(tempRegionRecord[currentRegionID].averageColor, CurrentColorPixel ) < ColorDifference(tempRegionRecord[nextRegionID].averageColor, CurrentColorPixel)
Set CurrentLinkedPixel[-1] = currentRegionID.
Else
Set CurrentLinkedPixel[-1] = nextRegionID.
If FoundRegions.FoundCount > 2
Set minDifference to hex 0x7fffffffffffffff
Set currentRegionID = 0
For (j = 0, j < FoundRegions.FoundCount, j = j+1) 
currentDifference = ColorDifference(tempRegionRecord[j].averageColor, CurrentColorPixel)
if (currentDifference < minDifference)
Set minDifference = currentDifference
Set currentRegionID = j
If (currentRegionID != 0)
Set CurrentLinkedPixel[-1] = currentRegionID
Set currentPixelIndex = CurrentLinkedPixel[0]
For each record, n, in tempRegionRecord, where n is Less than tempRegionRecord.RegionCount
If tempRegionRecord[n].RegionTag = n // this region is the root of the merged regions
tempRegionRecord[n].RegionTag = aRegionList.AddElement(tempRegionRecord[n].FirstFoundColor, tempRegionRecord[n]. RegionArea, 0) // create an output region for this one 
Else // this is not a root region
tempRegionRecord[n].RegionTag = tempRegionRecord[tempRegionRecord[n].RegionTag]. RegionTag // set tag to the output region index
For Each Pixel, CurrentLinkedPixel, in LinkedPixelBuffer
Increment currentPixelIndex to the offset for CurrentLinkedPixel
currentRegionID = tempRegionRecord[CurrentLinkedPixel.regionLabelIndex].RegionTag
CurrentLinkedPixel.regionLabelIndex = currentRegionID // set tag to the output region index
CurrentLinkedPixel.nextSortIndex = aRegionList [currentRegionID].pixelListOffset
aRegionList [currentRegionID].pixelListOffset = currentPixelIndex+1
Output the modified LinkedRegionImage and aRegionList, 
■
【図３】
2014179090.tif 000004
【図４】
2014179090.tif 000005
【図５】
2014179090.tif 000006
【図６】
2014179090.tif 000007
【図７】
2014179090.tif 000008
【図８】
2014179090.tif 000009
【図９】
2014179090.tif 000010
【図１０】
2014179090.tif 000011
【図１１】
2014179090.tif 000012
【図１３】
2014179090.tif 000013
【図１】
2014179090.tif 000014
【図２】
2014179090.tif 000015
【図１２】
2014179090.tif 000016
【外国語明細書】
2014179090000001.pdf