【手続補正書】
【提出日】平成17年4月25日(2005.4.25)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】特許請求の範囲
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とする線分近似方法。
【請求項２】
前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分の両端の２頂点間にそれ以降に生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする請求項１に記載の線分近似方法。
【請求項３】
前記選択された最大距離が前記所定の閾値を越えなかった線分の両端の２頂点間に、前記新たな頂点が発生した場合には、該頂点によって増えた新たな近似線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率の値を小さくすることを特徴とする請求項１に記載の線分近似方法。
【請求項４】
前記選択された最大距離が前記所定の閾値を越えた線分については、該線分の両端の２頂点間にそれ以降生じる線分に対して予め設定される前記確率を所定の値に戻すことを特徴とする請求項２または３に記載の線分近似方法。
【請求項５】
前記確率は、当該線分の両端で挟まれる、前記部分点列の各点までの距離が大きいほど大きい値になるように設定されることを特徴とする請求項１に記載の線分近似方法。
【請求項６】
前記確率は、一様に発生する乱数と、当該線分の両端で挟まれる、前記部分点列の各点までの距離および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に応じて設定されることを特徴とする請求項５に記載の線分近似方法。
【請求項７】
前記関数は、前記距離および揺らぎの大きさを決めるパラメタ各々に関して単調変化することを特徴とする請求項６に記載の線分近似方法。
【請求項８】
前記揺らぎの大きさを決めるパラメタは前記各線分毎に設定されることを特徴とする請求項６に記載の線分近似方法。
【請求項９】
前記選択された最大距離が前記所定の閾値を越えなかった線分については、該線分に対して設定される前記揺らぎの大きさを決めるパラメタの値を減少させることを特徴とする請求項８に記載の線分近似方法。
【請求項１０】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とする線分近似方法。
【請求項１１】
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記確率の値を小さくすることを特徴とする請求項１０に記載の線分近似方法。
【請求項１２】
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えず、かつ、前の階層で新たな頂点が発生したときには、前記確率の値を小さくすることを特徴とする請求項１０に記載の線分近似方法。
【請求項１３】
次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率を所定の値に戻すことを特徴とする請求項１１または１２に記載の線分近似方法。
【請求項１４】
前記所定の値は、当該線分近似を開始するときに設定した初期値であることを特徴とする請求項１３に記載の線分近似方法。
【請求項１５】
次の階層で、前記選択された、前記各線分毎の最大距離のうちいずれかが前記所定の閾値を越えたときには、前記確率の値を近似線分本数が増加するに従って小さくすることを特徴とする請求項１１または１２に記載の線分近似方法。
【請求項１６】
前記確率は、前記選択された、前記各線分毎の最大距離のうちの最大値が大きいほど大きい値に設定されることを特徴とする請求項１０に記載の線分近似方法。
【請求項１７】
前記確率は、一様に発生する乱数と、前記選択された、前記各線分毎の最大距離のうちの最大値および揺らぎの大きさを決めるパラメタで決まる関数との大小関係に基づいて決定されることを特徴とする請求項１０に記載の線分近似方法。
【請求項１８】
前記関数は、前記最大値および前記揺らぎの大きさを決めるパラメタ各々に関して単調変化し、
連続した階層に亘って、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えないときには、前記揺らぎの大きさを決めるパラメタの値を変化させることにより、前記確率の値を変化させることを特徴とする請求項１７に記載の線分近似方法。
【請求項１９】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、
前記線分近似方法は、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とするプログラム。
【請求項２０】
データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、
前記線分近似方法は、
前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、
該算出された各距離のうち最大のものを選択し、
該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加する
ことを特徴とするプログラム。
【請求項２１】
データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、
前記データ記憶手段に格納された頂点列に対応する線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出する算出手段と、
該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、
該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段と
を有することを特徴とする線分近似装置。
【請求項２２】
データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、
前記データ記憶手段に格納された頂点列に対応する線分列の、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列Ａ内の部分点列の各点までの各距離を算出する算出手段と、
該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、
該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段と
を有することを特徴とする線分近似装置。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】００９６
【補正方法】変更
【補正の内容】
【００９６】
【課題を解決するための手段】
上記目的を達成するため、請求項１に記載の線分近似方法は、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０１０５
【補正方法】変更
【補正の内容】
【０１０５】
上記目的を達成するため、請求項１０に記載の線分近似方法は、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法において、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】０１１４
【補正方法】変更
【補正の内容】
【０１１４】
上記目的を達成するため、請求項１９に記載のプログラムは、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、前記線分近似方法は、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、当該線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】０１１５
【補正方法】変更
【補正の内容】
【０１１５】
上記目的を達成するため、請求項２０に記載のプログラムは、データ記憶部に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似する線分近似方法を実行するプログラムであって、前記線分近似方法は、前記近似によって得られた線分列の頂点列を前記データ記憶部に格納しておき、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出し、該算出された各距離のうち最大のものを選択し、該選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶部に格納された頂点列に追加する一方、前記選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶部に格納された頂点列に当該新たな頂点を追加することを特徴とする。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】０１１６
【補正方法】変更
【補正の内容】
【０１１６】
上記目的を達成するため、請求項２１に記載の線分近似装置は、データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、前記データ記憶手段に格納された頂点列に対応する線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列内の部分点列の各点までの各距離を算出する算出手段と、該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された最大距離が前記所定の閾値を越えなかったときには、該線分に対して予め設定された確率で、前記部分点列内の点を新たな頂点として発生させ、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段とを有することを特徴とする。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】０１１７
【補正方法】変更
【補正の内容】
【０１１７】
上記目的を達成するため、請求項２２に記載の線分近似装置は、データ記憶手段を備え、該データ記憶手段に初期データとして格納されている連結した座標点列を、基準直線からの距離に基づいて、前記座標点列の部分集合を頂点列とする線分列によって近似し、当該頂点列を前記データ記憶手段に格納する線分近似装置において、前記データ記憶手段に格納された頂点列に対応する線分列の、ある階層の線分列の各線分毎に、該線分から、該線分の両端で挟まれる、前記座標点列Ａ内の部分点列の各点までの各距離を算出する算出手段と、該算出手段によって算出された各距離のうち最大のものを選択する選択手段と、該選択手段によって選択された最大距離が所定の閾値を越えたときには、該最大距離を与える、前記部分点列内の点を新たな頂点として、前記データ記憶手段に格納された頂点列に追加する一方、前記選択手段によって選択された、前記各線分毎の最大距離がいずれも前記所定の閾値を越えなかったときには、前記選択された、前記各線分毎の最大距離のうちの最大値に基づいた確率で新たな頂点を発生させて、前記データ記憶手段に格納された頂点列に当該新たな頂点を追加するように制御する制御手段とを有することを特徴とする。