米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> 大日本印刷株式会社

発明の名称 楕円モデル化方法
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2003−16461(P2003−16461A)
公開日 平成15年1月17日(2003.1.17)
出願番号 特願2001−202105(P2001−202105)
出願日 平成13年7月3日(2001.7.3)
代理人 【識別番号】100111659
【弁理士】
【氏名又は名称】金山 聡
【テーマコード(参考)】
5L096
【Fターム(参考)】
5L096 GA32 
発明者 小林 秀章 / 石栗 治郎
要約 課題
対象とするものの略楕円状の輪郭上から拾った点列に、正置き楕円をあてはめることができる方法を提供する。

解決手段
前記略楕円である形状の輪郭線上のいくつかの点を座標として拾い、平面x−y座標表示の点列{xi、yi}(i=1、2、・・・nで、nは正の整数))を得た後、得られた点列に対し、点列から近似的に楕円を抽出する点列近似方法を用いてあてはめる楕円を得るものであり、前記点列近似方法は、平面上の座標(x、y)を5次元空間上の座標(x2 、y2 、x、y、1)に移すことにより、平面上の点列を5次元空間上の点列に移し、得られた点列の座標値からなる行列Dと定数からなる拘束行列Cとから生成される行列Mの固有ベクトルを求め、得られた固有ベクトルから適当なものを選択して、これを(a、b、c、d、e)とする下記(1)式で表される楕円を得る。
特許請求の範囲
【請求項1】 工業製品や自然界に存在するもので、その形状、あるいは断面や投影面での形状が略楕円になっているものに対し、前記略楕円である形状に楕円をあてはめる楕円モデル化方法であって、前記略楕円である形状の輪郭線上のいくつかの点を座標として拾い、平面x−y座標表示の点列{xi、yi}(i=1、2、・・・nで、nは正の整数)を得た後、得られた点列に対し、点列から近似的に楕円を抽出する点列近似方法を用いてあてはめる楕円を得るものであり、前記点列近似方法は、平面上の座標(x、y)を5次元空間上の座標(x2 、y2 、x、y、1)に移すことにより、平面上の点列を5次元空間上の点列に移し、得られた点列の座標値からなる行列Dと定数からなる拘束行列Cとから生成される行列Mの固有ベクトルを求め、得られた固有ベクトルから適当なものを選択して、これを(a、b、c、d、e)とする(1)式で表される楕円、 ax2 +by2 +cx+dy+e=0 (1)
但し、ab>0を得ることを特徴とする楕円モデル化方法。
【請求項2】 請求項1において、拘束行列Cは単位行列であることを特徴とする楕円モデル化方法。
【請求項3】 請求項1において、拘束行列Cは第1行第2列および第2行第1列の成分を1/2とし、残りの成分を0とする行列または、それを定数倍して得られる行列であることを特徴とする楕円モデル化方法。
【請求項4】 請求項1において、行列Mは拘束行列Cの逆行列C-1と行列Dの転置行列Dt と行列Dとの積、即ち、M=C-1t D (2)
であることを特徴とする楕円モデル化方法。
【請求項5】 請求項1において、行列Mは行列Dの転置行列Dt と行列Dとの積の逆行列と、拘束行列Cとの積、即ち、M=(Dt D)-1C (3)
であることを特徴とする楕円モデル化方法。
【請求項6】 請求項1において、行列Mの最小固有値に対応する固有ベクトルを(a、b、c、d、e)として選択することを特徴とする楕円モデル化方法。
【請求項7】 請求項1において、行列Mの最大固有値に対応する固有ベクトルを(a、b、c、d、e)として選択することを特徴とする楕円モデル化方法。
発明の詳細な説明
【0001】
【発明の属する技術分野】本発明は、点列への楕円のあてはめ方法に関し、特に、工業製品や自然界に存在するもので、その形状、あるいは断面や投影面での形状が略楕円になっているものが数多く存在するが、サンプル写真等により、これらの略楕円形状の輪郭線上のいくつかの点を座標として拾い、得られた点列に楕円をあてはめる楕円モデル化方法に関する。
【0002】
【従来の技術】工業製品や自然界に存在するもので、その形状、あるいは断面や投影面での形状が略楕円になっているものが数多く存在し、前記略楕円の形状を楕円でモデル化したい場合がある。例えば、フォトリソ法により、基材表面にレジストが丸形状に開口され、該開口から露出した基材がエッチング加工されて、形成される孔形状等を楕円でモデル化したい場合がある。このような場合、通常、実際にサンプルの断面写真を撮り、輪郭線上のいくつかの点を座標として拾い、得られた点列に楕円をあてはめ、点列から楕円を計算により導き出す方法が採られている。点列から楕円を計算により導き出す方法としては、Maurizio Pilu等による論文、ELLIPSE−SPECIFIC DIRECT LEAST−SQUARE FITTING(IEEE InternationalConference on Image Processing、Lausanne、September 1996)に記載された方法が知られている。この方法は、ある評価基準に基づいた最小2乗近似により、(4)式で表される楕円を得る。
ax2 +bxy+cy2 +dx+ey+f=0 (4)
但し、b2 ー4ac<0楕円の中心位置と2軸の長さだけでなく、軸の傾きも最適に決まる。
【0003】しかしながら、時として、モデル化の都合上、あてはめたい楕円の向きが決まっているときがある。いま、座標軸が楕円の向きに合せてあるものとする場合、つまり、あてはめたい楕円の2軸が、それぞれx軸、y軸に平行である場合、このような楕円を、「正置き楕円」と呼ぶことにするが、与えられたサンプルの略楕円状の輪郭上から拾った点列に、正置き楕円をあてはめようとする場合、上記のMaurizioPilu等による方法は、そのままでは使用できないという問題があった。
【0004】
【発明が解決しようとする課題】上記のように、与えられたサンプル等、対象とするものの略楕円状の輪郭上から拾った点列に、正置き楕円をあてはめようとする場合、上記のMaurizio Pilu等による方法は、そのままでは使用できないという問題があり、この対応が求められていた。本発明は、これに対応するもので、対象とするものの略楕円状の輪郭上から拾った点列に、正置き楕円をあてはめることができる方法を提供しようとするものである。
【0005】
【課題を解決するための手段】本発明の楕円モデル化方法は、工業製品や自然界に存在するもので、その形状、あるいは断面や投影面での形状が略楕円になっているものに対し、前記略楕円である形状に楕円をあてはめる楕円モデル化方法であって、前記略楕円である形状の輪郭線上のいくつかの点を座標として拾い、平面x−y座標表示の点列{xi、yi}(i=1、2、・・・nで、nは正の整数)を得た後、得られた点列に対し、点列から近似的に楕円を抽出する点列近似方法を用いてあてはめる楕円を得るものであり、前記点列近似方法は、平面上の座標(x、y)を5次元空間上の座標(x2 、y2 、x、y、1)に移すことにより、平面上の点列を5次元空間上の点列に移し、得られた点列の座標値からなる行列Dと定数からなる拘束行列Cとから生成される行列Mの固有ベクトルを求め、得られた固有ベクトルから適当なものを選択して、これを(a、b、c、d、e)とする(1)式で表される楕円 ax2 +by2 +cx+dy+e=0 (1)
但し、ab>0を得ることを特徴とするものである。そして、上記において、拘束行列Cは単位行列であることを特徴とするものである。あるいは、上記において、拘束行列Cは第1行第2列および第2行第1列の成分を1/2とし、残りの成分を0とする行列または、それを定数倍して得られる行列であることを特徴とするものである。あるいはまた、上記において、行列Mは拘束行列Cの逆行列C-1と行列Dの転置行列Dt と行列Dとの積、即ち、M=C-1t D (2)
であることを特徴とするものである。あるいはまた、上記において、行列Mは行列Dの転置行列Dt と行列Dとの積の逆行列と、拘束行列Cとの積、即ち、M=(Dt D)-1C (3)
であることを特徴とするものである。あるいはまた、上記において、行列Mの最小固有値に対応する固有ベクトルを(a、b、c、d、e)として選択することを特徴とするものである。あるいはまた、上記において、行列Mの最大固有値に対応する固有ベクトルを(a、b、c、d、e)として選択することを特徴とするものである。
【0006】
【作用】本発明の楕円モデル化方法は、上記のような構成にすることによって、サンプルの対称となる形の輪郭上から拾った座標表示の点列に、正置き楕円をあてはめることができる楕円モデル化方法の提供を可能としている。即ち、あてはめられる楕円の式の形をax2 +by2 +cx+dy+e=0但し、ab>0と定めることによって、正置き楕円に限定し、与えられた点列を5次元空間に投影して得られる行列の固有ベクトルから楕円のパラメータ(a、b、c、d、e)を得ることにより、これを達成している。
【0007】拘束行列Cが単位行列であることは、正置楕円ax2 +by2 +cx+dy+e=0但し、ab>0のパラメータ(a、b、c、d、e)を、[a、b、c、d、e]C[a、b、c、d、e]t =1に制限することを意味し、結局、a2 +b2 +c2 +d2 +e2 =1に制限されることとなる。このとき、(a、b、c、d、e)を求める計算が簡単になるという利点がある。実際、行列MをDt Dとし、Mの最小固有値に対応する固有ベクトルのうち長さが1のものを(a、b、c、d、e)とすれば良い。
【0008】拘束行列Cは第1行第2列および第2行第1列の成分を1/2とし、残りの成分を0とする行列または、それを定数倍して得られる行列であることにより、与えられた点列が楕円のごくわずかな一部分上でしかとられていない場合、結果としてab<0となり、楕円でなく双曲線があてはまってしまうことを防ぐもので、かならず楕円が得られるよう限定するものである。このときCは逆行列が存在しないので、行列Mは、下記のように、行列Dの転置行列Dtと行列Dとの積の逆行列と、拘束行列Cとの積で表し、M=(Dt D)-1C (3)
とすることにより解が得られる。行列Mを、式(3)のように決めたとき、行列Mの最大固有値に対応する固有ベクトルを(a、b、c、d、e)として解を選択する。但し、これに限らない。例えば、Cの決め方により、5つの固有値のうち正のものが1つしかないと分かるときには、それを選べば良い。
【0009】また、拘束行列Cが逆行列を持つとき、行列Mは、下記のように、拘束行列Cの逆行列C-1と行列Dの転置行列Dt と行列Dとの積、M=C-1t D (2)
とすることにより、簡便となり、数値計算的にも安定している。行列Mを、式(2)のように決めたとき、行列Mの最小固有値に対応する固有ベクトルを(a、b、c、d、e)として解を選択する。
【0010】
【発明の実施の形態】本発明の点列近似方法の実施の形態の1例を説明する。図1は、略楕円である形状の輪郭線上のいくつかの点を座標として拾い、平面x−y座標表示の点列{xi、yi}(i=1、2、・・・nで、nは正の整数)と、あてはめる楕円を示した概略図である。本例は、工業製品や自然界に存在するもので、その形状、あるいは断面や投影面での形状が略楕円になっているものに対し、前述の略楕円である形状を楕円にあてはめる楕円モデル化方法で、略楕円である形状の輪郭線上のいくつかの点を座標として拾い、平面x−y座標表示の点列{xi、yi}(i=1、2、・・・nで、nは正の整数)を得た後、得られた点列に対し、点列から近似的に楕円を抽出する点列近似方法を用いてあてはめる楕円を得るものである。以下、本例を説明する。あてはめたい楕円の式の形を、 ax2 +by2 +cx+dy+e=0 (5)
但し、ab>0と決める。楕円の式(5)の係数の並びを5次元の縦ベクトルとして、 A=[a b c d e]t (6)
と表す。ここで、肩のtは転置を示す。また、1つの点(xi、yi)に対して5次元の縦ベクトルを、 Xi=[xi 2 、yi 2 、xi 、yi 、1]t (7)
と定義する。楕円あてはめの誤差Eを、下記(8)式のように決める。
【数1】

但し、(X、Y)は内積を表す。Eを最小にするようなAを求めたいのであるが、Aに何の制約もなければ、A=|0 0 0 0 0|のときにE=0という自明解で終わってしまう。
【0011】ここで、Aに関する拘束条件として、 ab=1 (9)
とする。行列Cを、【数2】

とすると、これを拘束条件(9)は、t CA=1 (11)
となる。
【0012】次いで、拘束条件(11)の下で、Eを最小にするようなAを求め、結果としてあてはめたい楕円を求める。即ち、ベクトルの内積の2乗和を最小にするベクトルを求める。ここでは、手順のみを挙げる。先ず、n×5行列Dを、 D=[X1 、X2 、X3 、・・・X5 t (12)
とする。次いで、Cが正則行列であるとき、行列(C-1t D)の最小固有値に対する固有ベクトルの長さを調整し、拘束条件(11)を満たすようにしたものが求めるAである。Cが正則行列でないとき、行列(Dt D)-1Cの最大固有値に対する固有ベクトルの長さを調整し、拘束条件(11)を満たすようにしたものが求めるAである。
【0013】以下、ベクトルの内積の2乗和を最小にするベクトルを求める方法を更に詳しく説明しておく。k次元ベクトル空間V内にn個のベクトルX1 、X2 、X3 、・・・Xn が与えれている。本例の場合はk=5であるが、以下の解法は一般のkについて成り立つものなので、kと表記する。V内の任意ベクトルをXとし、評価関数E(X)を、下記(13)のように決める。
【数3】

但し、(X、Y)は内積を表す。E(X)を最小にするようなXを求めたいのであるが、Xに何の制約もなければ、X=0のときE(X)=0という自明解で終わってしまう。
【0014】ここで、Xに関する拘束条件としては、k×k対称行列C(拘束行列と言う)を用いて、下記(14)式のようにあらわされているものとする。
t CX=1 (14)
ここで、肩のtは転置を示す。よくあるのは、Cが単位行列の場合であり、 ||X||=1 (15)
に制約されることを意味するが、以下では、その場合に限らず一般的なCについて扱う。Cは必ずしも正則行列でなくても良い。
【0015】以下、拘束条件(14)の下で、E(X)を最小にするXを求める。ラグランジュ(Lagrange)乗数法を用いて解く。空間V内の任意のベクトルXを縦ベクトルとして、 X=[x1 、x2 、x3 、・・・xk t (16)
とし、点列の各点xiを縦ベクトルとして、 Xi=[xi1、xi2、xi3、・・・xikt (17)
とし、拘束行列Cを、【数4】

とする。ここで、肩のtは転置を示す。n×k行列Dを、与えられた点列の各点を横ベクトルとして縦に積み重ねた行列として、【数5】

のように定義する。すると、(13)式は、 E(X)=Xt t DX (20)
のように表される。ラグランジュの乗数をλと書き、評価関数E(x)を新たに、 E(X)=Xt t DX−λ(Xt CX-1) (21)
と定義しなおすと、拘束条件(14)の下で、E(X)を最小にするXを求めることは、結局、(k+1)個の未知数λ、x1 、x2 、・・・xk に対して、方程式、 ∂E(X)/∂x1 =0 (22)
∂E(X)/∂x2 =0 (23)
・ ・ ∂E(X)/∂xk =0 (24)
t CX=1 (25)
を解く問題に帰着される。{∂E(X)/∂Xi }は次のように書き下せる。
{∂E(X)/∂Xi }=(∂Xt /∂Xi )Dt DX+Xt t D(∂X/∂Xi )−λ{(∂Xt /∂Xi )CX+Xt C(∂X/∂Xi )}
=Ui t t Dx+xt t DUi −λ{Ui t CX+Xt CUi
ただし、Ui は第i成分が1でその他の成分がすべて0であるような縦ベクトルである。更に、第2項と第4項を転置して、Ct =Cであることを用いると、{∂E(X)/∂Xi }=2Ui t t DX−2λUi t CXとなる。これを縦に積み重ねてベクトルの形で表現すると、方程式(22)〜(25)は、【数6】

となる。ところで、U1t 、U2t 、・・・Ukt を縦に積み重ねた行列は単位行列だから、結局、方程式は、t DX=λCX (27)
となる。Cが正則行列のときは、Cの逆行列C-1を左から掛けて、-1t DX=λX (28)
なので、行列(C-1t D)の固有値がλの候補になり、固有ベクトルがXの候補になる。λとXが方程式(27)と拘束条件(14)を満たすとき、評価関数E(X)は、E(X)=Xt t DX=Xt λCX=λとなる。
【0016】いま、E(X)を最小にしたいのだから、λとして最小固有値を選択すれば良い。最小固有値に対応する固有ベクトルを求め、拘束条件(14)を満たすように固有ベクトルの長さを調整してXとする。Cが正則行列でないときは、もし(Dt D)が正則ならばその逆行列を左から掛けて、 (Dt D)-1CX=(1/λ)X (29)
を得る。したがって、行列{(D-tD)-1C}の最大固有値から、上と同様にλとXが決まる。もし、Cも(Dt D)も正則でないときは、与えられた点列によって張られる空間の次元がkよりも小さくなっているはずなので、点列のすべての点の直交するベクトルが存在するはずである。そのようなベクトルをXとすればE(X)=0にすることができる。このようにして、ベクトルの内積の2乗和を最小にするベクトルを求める。
【0017】
【発明の効果】本発明は、上記のように、与えられたサンプル等、対象とするものの略楕円状の輪郭上から拾った点列に、正置き楕円をあてはめることができる方法の提供を可能とした。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013