古賀 久志
| 情報・ネットワーク工学専攻 | 准教授 |
| Ⅰ類（情報系） | 准教授 |
研究者情報
研究活動情報
受賞
- 受賞日 2024年09月
コンセプトドリフトが想定される環境でのオンラインK-medoidsクラスタリングの代表データ選択
第23回情報科学技術フォーラム FIT奨励賞, 田山凜太郎(修士の指導学生) - 受賞日 2024年09月
類似軌跡探索における高速かつ高精度なスケッチ間類似度
第23回情報科学技術フォーラム FIT奨励賞, 河野大督(修士の指導学生) - 受賞日 2022年09月
画像の追加を許容するDeep Hashingに基づく類似画像検索
第21回情報科学技術フォーラム(FIT2022)FIT奨励賞, Ye Chenyang(修士の指導学生)
国内学会・会議・シンポジウム等の賞 - 受賞日 2019年09月
双対グラフを用いたグラフの分散表現学習
第18回情報科学技術フォーラム(FIT2019)FIT奨励賞
国内学会・会議・シンポジウム等の賞 - 受賞日 2019年09月
ストリーム環境での位置情報を持つテキスト集合に対する類似検索
第18回情報科学技術フォーラム(FIT2019)FIT奨励賞
国内学会・会議・シンポジウム等の賞 - 受賞日 2017年09月
多観点類似度を用いた凝集型階層クラスタリング
第16回情報科学技術フォーラム(FIT2017)FIT奨励賞
国内学会・会議・シンポジウム等の賞
論文
- Fast Concept Drift Detection Exploiting Product Quantization
Taisei Takano; Hisashi Koga
責任著者, Proc. 35th International Conference on Database and Expert Systems Applications(DEXA 2024), Springer LNCS, Springer Nature Switzerland, 14911巻, 掲載ページ 257-271, 出版日 2024年08月17日, 査読付
研究論文（国際会議プロシーディングス）, 英語 - Approximate Similarity Search for Time Series Data Enhanced by Section Min-Hash,
R. Tomoda; H. Koga
Proc. 16th International Conference on Similarity Search and Applications (SISAP 2023), Springer LNCS, 14289巻, 掲載ページ 19-32, 出版日 2023年10月, 査読付
研究論文（国際会議プロシーディングス） - Continuous Similarity Search for Dynamic Text Streams
Y. TSUCHIDA; K. KUBO; H. KOGA
責任著者, IEICE TRANSACTIONS on Information and Systems, E106-D巻, 12号, 出版日 2023年09月, 査読付
研究論文（学術雑誌）, 英語 - Deep Hashing Capable of Adding New Dataset Without Class Labels
Ye Chenyang; Hisashi Koga
Proc. 2023 International Joint Conference on Neural Networks (IJCNN 2023), 掲載ページ 1-9, 出版日 2023年06月, 査読付
研究論文（国際会議プロシーディングス） - IDTWを用いた個別銘柄を対象とした株価予測
中尾友紀,古賀久志
情報処理学会論文誌, Vol. 63巻, 9号, 掲載ページ 1512-1517, 出版日 2022年09月15日, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - Continuous Similarity Search for Text Sets
Y. Tsuchida, K. Kudo and H. Koga
Proc. 33rd International Conference on Database and Expert Systems Applications(DEXA 2022), Springer LNCS, Vol. 13427巻, 掲載ページ 229-234, 出版日 2022年09月, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - Editing Compression Dictionaries toward Refined Compression-Based Feature-Space
H. Koga, S. Ouchi and Y. Nakajima
Information, MDPI, 13巻, 6号, 掲載ページ 301, 出版日 2022年06月15日, 査読付, 国際誌
研究論文（学術雑誌）, 英語 - Exact Algorithm to Solve Continuous Similarity Search for Evolving Queries and Its Variant
T. Yamazaki and H. Koga
IEICE Transactions on Information and Systems, Vol.E105-D巻, 5号, 掲載ページ 898-908, 出版日 2022年05月, 査読付, 国内誌
研究論文（学術雑誌）, 英語 - 多観点類似度を用いた凝集型階層クラスタリング
藤原 勇二,古賀久志
情報処理学会論文誌, Vol. 62巻, 3号, 掲載ページ 936-945, 出版日 2021年03月, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - 非教示なグラフ分散表現のエッジ特徴による改良
陳 宏,古賀久志
情報処理学会論文誌, Vol. 62巻, 1号, 掲載ページ 357-368, 出版日 2021年01月, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - Evaluation of Image Descriptors for Urban-Rural Classification of Aerial Images.
Daniel Cortés; Mariko Nakano; Hisashi Koga; Héctor Pérez 0001
New Trends in Intelligent Software Methodologies, Tools and Techniques - Proceedings of the 16th International Conference(SoMeT), IOS Press, 掲載ページ 204-213, 出版日 2017年, 査読付
研究論文（国際会議プロシーディングス） - ネットワークトポロジー設計のためのパラメトリックな全域木生成
大家 万明; 渡辺 俊典; 古賀 久志
情報処理学会論文誌数理モデル化と応用（TOM）, 9巻, 2号, 掲載ページ 9-19, 出版日 2016年08月10日, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - 時系列圧縮性によるポリシー指向ネットワークモニタリング
大関 潮,古賀 久志,渡辺 俊典
電子情報通信学会論文誌, Vol.J98-A巻, 4号, 掲載ページ 357-368, 出版日 2015年04月01日, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - 滑り現象の映像解析による地震動の推定
横田 有光, 浜本 隆之, 古賀 久志, 渡辺 俊典
土木学会論文集F3(土木情報学), 70巻, 1号, 掲載ページ 29-39, 出版日 2014年10月, 査読付, 国内誌
研究論文（学術雑誌）, 日本語 - Analysis of Internet Traffic Using Time Series Compressibility
U. Ozeki, T. Watanabe and H. Koga
Proc. of 19th International Conference on Systems, Signals and Image Processing (IWSSIP), 掲載ページ 372-375, 出版日 2012年04月, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - An effective Method for Image Matching based on modified LBP and SIFT
Y. Wang, N. Zhang, T. Watanabe and H. Koga
Proc. 7th International Conference on Computer Vision Theory and Applications (VISAPP 2012), 掲載ページ 410-413, 出版日 2012年02月, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - New Application of Graph Mining to Video Analysis
Hisashi Koga, Tomokazu Tsuji, Takanori Yokoyama and Toshinori Watanabe,
Proc. 11th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL’10), springer LNCS, Vol. 6283巻, 掲載ページ 86-93, 出版日 2010年09月, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - パッシブRTT推定法を使用したAQMアルゴリズム
星原 隼人; 古賀 久志; 渡辺 俊典
情報処理学会論文誌, 51巻, 2号, 掲載ページ 466-477, 出版日 2010年02月15日, 査読付, AQMは輻輳制御の技術であり，輻輳状態にあるルータ内のキュー溢れを防ぐため，TCPホストへどの程度の割合で輻輳通知が必要かを輻輳通知確率として計算する．この過程で，TCPコネクションのRTTは輻輳制御の効果に影響を与えるパラメータであるが，これを考慮したAQMはほとんど存在しない．よって，本論文ではルータで利用できるRTT推定法を導入し，得られたRTT値を明示的にアルゴリズムに組み込んだAQMを提案する．さらに，シミュレーションにより提案AQMが既存AQMよりも高い安定性を持つことを示す．AQM is a technique for congestion control such that a router notifies congestion to a TCP sender when congestion occurs. Almost no AQM algorithms ever take the RTT values of TCP connections into account in congestion control, despite they are essential parameters. This paper proposes a new AQM algorithm that exploits them explicitly by introducing a passive RTT estimation technique in a router. The simulation results shows that our AQM stabilizes the queue length better than previous AQM algorithms.
日本語 - 頻出グラフマイニングを利用した動画像解析
辻 智和; 古賀久志; 横山貴紀; 渡辺俊典
情報処理学会論文誌, 51巻, 2号, 掲載ページ 466-477, 出版日 2010年02月, 査読付
研究論文（学術雑誌） - Unsupervised Object Discovery from Images by Mining Local Features Using Hashing
Gibran Fuentes Pineda, Hisashi Koga and Toshinori Watanabe
Proc. 14th Iberoamerican Congress on Pattern Recognition (CIARP 2009), Springer LNCS, Vol. 5856巻, 掲載ページ 978-985, 出版日 2009年10月, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - Dynamic TCP Acknowledgment with Sliding Window.
Hisashi Koga
Theoretical Computer Science, 410巻, 掲載ページ 914-925, 出版日 2009年02月, 査読付, 国際誌
研究論文（学術雑誌）, 英語 - Document Relation Analysis Based on Compressibility Vector
N. Zhang, D. Matsuzaki, T. Watanabe and H. Koga
Proc. of 1st International Conference on Agents and Artificial Intelligence (ICAART09), 掲載ページ 255-260, 出版日 2009年01月, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - MPEGビデオデータの動きベクトルを用いた圧縮領域における移動物体の検出と追跡
岩崎 敏紀; 横山 貴紀; 渡辺 俊典; 古賀 久志
電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 一般社団法人電子情報通信学会, 91巻, 6号, 掲載ページ 1592-1603, 出版日 2008年06月01日, 査読付, MPEGビデオ符号化では,圧縮するために動き補償を用いており,フレーム間における各領域の動き情報を動きベクトルとして生成する.この動きベクトルは動画像解析に役立つ情報と考えられるが,符号化効率を向上させるために生成されるものであり,必ずしも移動物体に沿って発生するものではなく,多くのノイズ的なベクトルも生成するという問題点がある.また,動きベクトルを用いた既存手法の多くでは,移動物体の停止や交差によって動きベクトルが失われるフレームに対して適用することが困難である.本論文では,MPEGビデオデータの動きベクトルから直接得られる特徴画像を用いた,移動物体の検出と追跡手法を提案する.特徴画像は移動領域を記録し,移動物体が停止していると考えられる領域を次フレーム以降も蓄積する.この履歴特性をもつ領域の特徴画像を用いることにより,移動物体が静止した場合やピクチャタイプなどによって動きベクトルが出現しない場合でも,移動物体の検出と追跡が可能となる.MPEG-4カメラで撮影した動画像を用いて実験を行い,提案手法の有効性を示す.
研究論文（学術雑誌）, 日本語 - 近傍集合表現を利用した画像からのオブジェクト自動抽出
古賀 久志; 杉山 英行; 杉内 崇浩; 渡辺 俊典; 横山 貴紀
電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 一般社団法人電子情報通信学会, 91巻, 5号, 掲載ページ 1418-1433, 出版日 2008年05月01日, 査読付, 少数の画像を与えるだけで人手を介さずにオブジェクトを自動抽出する方式を提案する.その基礎として,まず,オブジェクトの部品位置が種々に変化し得る場合でも,同種類のオブジェクトを簡単に認識するためのデータ構造である近傍集合表現を述べる.提案するオブジェクト自動抽出アルゴリズムは,与えられた画像内からいくつかオブジェクト候補を作成し,オブジェクト候補と同種類のオブジェクトを近傍集合表現を利用して抽出する.オブジェクト抽出の良否は,画像内により多く出現しより多くの部品からなるものがオブジェクトとして妥当であるとの直感を画像表現に要するデータ量の圧縮度という評価関数に定式化して計算する.そして,オブジェクト候補を変えてオブジェクト抽出を繰り返し試行し,評価関数値が最大となった場合を,最終的なオブジェクト抽出結果として返す.静止画像と動画像とを用いた実験によって提案の有効性を示す.
日本語 - 超解像処理を用いたブレ画像修復手法
牟田 桂介; 横山 貴紀; 渡辺 俊典; 古賀 久志
電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 一般社団法人電子情報通信学会, 90巻, 6号, 掲載ページ 1532-1541, 出版日 2007年06月01日, 査読付, 移動する被写体をカメラで撮影する場合,被写体像がシャッターの開口時間に応じ移動方向へ多重に露光されるため,撮影画像は静止被写体像に比べて劣化する.そのため,撮影画像からプレの影響を取り除き,静止被写体像を復元するプレ画像修復処理が重要となる.しかし,プレ画像の修復処理とは,移動方向について減衰された被写体像の高周波成分を増幅する処理であるため,画像に含まれる雑音成分まで強調してしまうという問題点がある.本論文では,超解像処理手法を用いたプレ画像修復手法を提案する.複数枚のプレ画像を用いることで雑音を抑制することができ,また入力画像がもつ解像度以上の被写体像の復元も可能となる.各種実験を行い,提案手法の有効性を確認した.
研究論文（学術雑誌）, 日本語 - Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing
Hisashi Koga; Tetsuo Ishibashi; Toshinori Watanabe
Knowledge and Information Systems, 12巻, 1号, 掲載ページ 25-53, 出版日 2007年05月, 査読付, 国際誌
研究論文（学術雑誌）, 英語 - A New Similarity Measure between Trees by Decomposition of Unit-cost Edit Distance
H. Koga; H. Saito; T. Watanabe; Y. Yokoyama
筆頭著者, Proc. 8th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL’07), springer LNCS, Vol. 4881巻, 掲載ページ 643-652, 出版日 2007年, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - A Novel Document Analysis Method Using Compressibility Vector
N. Zhang; T. Watanabe; D. Matsuzaki; H. Koga
Proc 1st International Symposium on Data, Privacy, & E-Commerce (ISDPE'07), IEEE Compuiter Society, 掲載ページ 38-40, 出版日 2007年, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - 投票機構による動作オブジェクトのオンラインリアルタイム学習と認識
吉岡 泰智; 渡辺 俊典; 古賀 久志; 横山 貴紀
電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 一般社団法人電子情報通信学会, 90巻, 1号, 掲載ページ 83-93, 出版日 2007年01月01日, ビデオの内容を自動認識する技術は,監視,圧縮,要約など応用範囲が広い.認識対象を想定してそのモデルを人手や学習によって事前準備しておくというのが伝統的画像認識手法であるが,事前に想定できない多様な内容を含み,かつデータ量も膨大なビデオには十分対応できない.対策として,事前のモデル設定なしにビデオを観測しながらモデルの獲得と認識とを行う機構が望まれる.更にリプレイ時間や記憶のコストを削減するためにはワンパスで実時間性を備えたオンラインリアルタイム処理が理想である.本論文では,このような機能を備えたビデオ内動作オブジェクト自動認識システムを提案する.人の行動を撮影したビデオのみを与えて,歩く,座る,などの基本動作の獲得と認識とが完全自動で行えることを示す.
研究論文（学術雑誌）, 日本語 - A New Stable AQM Algorithm Exploiting RTT Estimation
H. Hoshihara, H. Koga, T. Watanabe
Proc. 31th IEEE Conference on Local Computer Networks (LCN'06), IEEE Computer Society., 掲載ページ pp 143-150, 出版日 2006年, 査読付, 国際誌
研究論文（国際会議プロシーディングス）, 英語 - Locality-Sensitive Hashingを用いた階層的クラスタ分析手法
石橋 徹夫; 古賀 久志; 渡辺 俊典
電子情報通信学会論文誌. D-I, 情報・システム, I-情報処理, 一般社団法人電子情報通信学会, 88巻, 4号, 掲載ページ 852-863, 出版日 2005年04月01日, 査読付, 階層的クラスタ分析は, 各データを一つのクラスタとみなし, 最も近いクラスタ同士を結合していき, 最終的に全データが一つのクラスタに含まれるまで結合を繰り返すという手法である.結合過程を樹形図で表現することで各クラスタ間の距離や包含関係が理解しやすく, 外的基準を必要としない教師なし自動分類であるため, 未知のデータ集合に対して有効である.しかし, データサイズnに対してO(n^2)の時間計算量がかかるため, 大規模なデータ集合に対して適用することは難しい.本論文では, 階層的クラスタ分析手法の一つであるSingle Link法の高速な近似手法を提案する.本手法は, 近似最近接点探索手法Locality-Sensitive Hashingを利用して, 結合すべきクラスタ, つまり近接するクラスタの探索にかかる手間を減らすもので, O(nB)の時間計算量を達成する.ここで, Bはハッシュテーブルの1エントリに格納されるデータ数の上限であり, テーブルサイズを十分大きくとることでnより十分小さくなる.更に実験により, 提案手法がSingle Link法と近似した結果を得られることや, 大規模データに対してより高速に実行できることを示す.
研究論文（学術雑誌）, 日本語 - インターネット通信における新しいスケジューリング問題
古賀 久志
電子情報通信学会論文誌. A, 基礎・境界, 一般社団法人電子情報通信学会, 88巻, 4号, 掲載ページ 447-456, 出版日 2005年04月01日, 査読付, スケジューリングは工場での生産管理などで使われ, 古くから重要な最適化問題として研究されてきた.しかし, インターネット通信の普及に伴い, 従来のスケジューリング理論の枠組みでは取り扱われなかった新しいスケジューリング問題を解く必要がでてきている.インターネット通信におけるスケジューリングは(1)通信プロトコルやスイッチの構造をもとにした問題である, (2)将来到着するパケットが分からない状態でスケジューリングするオンライン問題である, という2点が従来のスケジューリング問題と異なる.インターネット通信におけるスケジューリング問題を, オンラインアルゴリズムの解析手法である競合度解析(competitive analysis)を用いて解析するアプローチが, 近年活発であり, 本論文はその動向を解説する.Competitive analysisは入力をあらかじめ知っている最適オフラインアルゴリズムとのコスト比によりオンラインアルゴリズムの性能を測る手法であり, 待ち行列理論と違って入力にポアソン分布などの確率分布を仮定しない.ネットワーク通信におけるトラヒックは, ポアソン分布で表現するのが難しいことが知られており, その意味でcompetitive analysisはインターネット通信の解析に適している.
研究論文（学術雑誌）, 日本語 - Similarity-Based Retrieval Method for Fractal Coded Images in the Compressed Data Domain
T. Yokoyama, T. Watanabe and H. Koga
Proc. 4th International Conference on Image and Video Retrieval (CIVR2005), 掲載ページ Vol 3568, pp. 385-394, 出版日 2005年, 査読付, 国内誌
研究論文（国際会議プロシーディングス）, 英語 - フラクタル符号のベクトル集合間類似度に基づく検索の高速化手法
横山 貴紀; 渡辺 俊典; 古賀 久志
情報処理学会論文誌データベース（TOD）, 一般社団法人情報処理学会, 45巻, 14号, 掲載ページ 23-29, 出版日 2004年12月15日, 査読付, 私たちは画像をフラクタル圧縮して得られるフラクタル符号の類似検索手法を提案した．この類似検索手法では，フラクタル符号をベクトル集合と見なし，ベクトル集合間に類似定義を与えることで，圧縮符号の直接検索を可能とした．画像の回転や拡大縮小，平行移動などの変動に対してロバストであり，既存のウェーブレット変換を用いた手法よりも良好な検索精度を示したが，実用に際し，類似度計算コストの削減が課題として残っていた．今回，1）ベクトル集合データに索引構造を導入することで類似度計算を高速化し，2）ベクトル集合データの要素数に対する類似度の上限値設定により類似度算出対象の画像数を削減する，という2 つの戦略によって検索速度を大幅に改善した．We have proposed a fractal code retrieval method which decomposes a compressed code to a set of vectors, and exploits the similarity measured by the degree of one-to-one correspondence between two vector sets. This retrieval method is robust for various fluctuation of images. Although the retrieval performance of this method is better than conventional ones based on wavelet transform etc., it requires much retrieval time. In this paper, we propose an acceleration method for the fractal code retrieval to solve this problem. We introduce two following strategies in particular: 1) Retrieval system newly uses an index structure to store a set of vectors in order to perform the similarity computation efficiently. 2) We exploit the upper bound of the similarity easily derived from the cardinal numbers of vector sets to reduce the number of images for which the similarities have to be actually computed. These strategies contribute to the drastic improvement of the retrieval speed.
研究論文（学術雑誌）, 日本語 - Fast Hierarchical Clustering Algorithm Using Locality-Sensitive Hashing
Hisashi Koga; Tetsuo Ishibashi; Toshinori Watanabe
筆頭著者, In Proc. 7th International Conference on Discovery Science, Springer LNCS, Springer Berlin Heidelberg, Vol. 3245巻, 掲載ページ pp. 114-128, 出版日 2004年, 査読付
研究論文（国際会議プロシーディングス） - Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness.
Rudolf Fleischer, Hisashi Koga,
Algorithmica, 38巻, 2号, 掲載ページ 363-376., 出版日 2004年, 査読付, 国内誌
研究論文（学術雑誌）, 英語 - Jitter regulation in an Internet router with delay constraint
H. Koga
Journal of Scheduling, Wiley, Vol 4巻, 6号, 掲載ページ 355-377, 出版日 2001年, 査読付, 国際誌
研究論文（学術雑誌）, 英語 - New On-Line Algorithms for the Page Replication Problem
S. Albers and H.Koga
Journal of Algorithms, Vol27巻, 1号, 掲載ページ 75-96, 出版日 1998年, 査読付, 国際誌
研究論文（学術雑誌）, 英語
MISC
- 異周期カウンタと挿入遅延によるデータストリームに対する頻度クエリの精度向上
山川 竜太郎, 古賀久志
出版日 2025年03月, 第17回データ工学と情報マネジメントに関するフォーラム (DEIM2025) - コンセプトドリフト環境でのオンラインK-medoidsクラスタリングの代表データ選択とクラスタ数の可変化
田山凜太郎; 古賀久志
ラスト(シニア)オーサー, 出版日 2025年03月, 情処研報, 2025-MPS-152巻, 12号, 掲載ページ 1-6, 日本語 - 非更新オートエンコーダを用いた高精度なコンセプトドリフト検出
高野大晴; 古賀久志
ラスト(シニア)オーサー, 出版日 2024年12月, 信学技報, IBISML2024巻, 55号, 掲載ページ 1-8, 日本語 - コンセプトドリフトが想定される環境でのオンラインK-medoidsクラスタリングの代表データ選択
田山凜太郎; 古賀久志
責任著者, 出版日 2024年09月, 第23回情報科学技術フォーラム(FIT2024), 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議） - 異周期カウンタを用いたスライディングウィンドウ型ストリームに対する頻度クエリの精度向上
山川竜太郎,古賀久志
責任著者, 出版日 2024年09月, 第23回情報科学技術フォーラム(FIT2024), 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議） - 部分構造の相対的な位置関係を考慮した順序あり木の類似検索
大高一輝; 古賀久志
責任著者, 出版日 2024年09月, 第23回情報科学技術フォーラム(FIT2024), 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議） - 類似軌跡探索における高速かつ高精度なスケッチ間類似度
河野大督; 古賀久志
責任著者, 出版日 2024年09月, 第23回情報科学技術フォーラム(FIT2024), 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議） - Product Quantization を用いた高速コンセプトドリフト検出
高野大晴; 古賀久志
責任著者, 出版日 2023年12月26日, 情報処理学会研究報告, 2023-DBS-178巻, 2号, 掲載ページ 1-8, 日本語, 研究発表ペーパー・要旨（全国大会，その他学術会議） - 文字位置に着目した Min-Hash ベースの文字列類似検索
古賀久志; 別府直輝; 笠井龍一
出版日 2023年03月, 人工知能学会研究資料, SIG-FPAI-124巻, 掲載ページ 31-36, 研究発表ペーパー・要旨（全国大会，その他学術会議） - 区間Min-Hashを用いた時系列データに対する近似最近傍探索
友田涼太; 古賀久志
出版日 2023年03月, 第15回データ工学と情報マネジメントに関するフォーラム(DEIM2023), 研究発表ペーパー・要旨（全国大会，その他学術会議） - 制約最適化に基づく画像の時間順並び替え
久保拓巳, 戸田貴久, 古賀久志
出版日 2022年12月, 情処研報 2022-MPS, 141巻, 12号 - 画像の追加を許容するDeep Hashingに基づく類似画像検索,"
Ye Chenyang; 古賀久志
出版日 2022年09月, 第21回情報科学技術フォーラム(FIT2022), 研究発表ペーパー・要旨（全国大会，その他学術会議） - 動的なテキスト集合に対する類似検索アルゴリズムALE-Qの評価,
土田祐将; 古賀久志
出版日 2022年03月, 第14回データ工学と情報マネジメントに関するフォーラム(DEIM2022), 研究発表ペーパー・要旨（全国大会，その他学術会議） - データストリームを対象とした動的多重集合に対する Min-hash;の高速計算アルゴリズム
三原寛寿; 古賀久志
出版日 2022年03月, 第14回データ工学と情報マネジメントに関するフォーラム(DEIM2022), 研究発表ペーパー・要旨（全国大会，その他学術会議） - ストリーム環境でのテキスト集合に対する類似検索
久保幸平; 古賀久志
出版日 2020年12月, 情処研報 2020-MPS-131, 2020-MPS-131巻, 11号, 研究発表ペーパー・要旨（全国大会，その他学術会議） - D-4-11 部分構造の類似性を考慮したMin-Hashベースのグラフ類似検索(D-4.データ工学,一般セッション)
宮田 昂充; 古賀 久志; 戸田 貴久
一般社団法人電子情報通信学会, 出版日 2016年03月01日, 電子情報通信学会総合大会講演論文集, 2016巻, 1号, 掲載ページ 30-30, 日本語, 110010036664, AN10471452 - D-12-35 適応的に類似度を選択する類似画像検索方式(D-12.パターン認識・メディア理解A(パターンメディアの認識・理解・生成),一般セッション)
小林 馨; 古賀 久志; 戸田 貴久
一般社団法人電子情報通信学会, 出版日 2016年03月01日, 電子情報通信学会総合大会講演論文集, 2016巻, 2号, 掲載ページ 104-104, 日本語, 110010036409, AN10471452 - 型を重視した通信ネットワークトポロジー設計手法 (インターネットアーキテクチャ)
大家 万明; 渡辺 俊典; 古賀 久志
電子情報通信学会, 出版日 2015年08月25日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115巻, 192号, 掲載ページ 17-22, 日本語, 0913-5685, 40020588969, AA11553608 - 圧縮性に基づくパターン認識手法における特徴空間の改善 (パターン認識・メディア理解)
中島 優次; 古賀 久志; 戸田 貴久
近年,航空画像分類やtwitter分析などの応用領域においてパラメータフリーで計算可能な圧縮性類似度が注目されている.一方で,異なる辞書による圧縮率で構成された圧縮率ベクトルによりデータを特徴表現する枠組みPRDC(Pattern Representation on Data Compression)が存在する.PRDCの精度は特徴空間の軸となる辞書集合に依存する.そこで,本研究では互いに独立性の高い特徴量が得られるような辞書集合を生成することで,PRDCの精度改善を目指す.提案手法では辞書集合を逐次的に構築する.とくに,選択済みの辞書では圧縮されないデータから得られる辞書を選んで,さらに選択済みの辞書との共通単語を削除することで独立性が高い辞書集合を作る.データから得られた辞書をそのまま使わず,精度向上のために修正して用いるというアイデアは本研究の独創的な点である.航空写真を用いた画像分類において提案手法の有用性を確認した., 一般社団法人電子情報通信学会, 出版日 2014年12月11日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 114巻, 356号, 掲載ページ 63-68, 日本語, 0913-5685, 110009977341, AN10541106 - A New Parametric Method for Localized Star Spanning Tree Generation
Kazuaki Oya; Toshinori Watanabe; Hisashi Koga
A typical network topological design problem is to determine link connections and their capacity to achieve high performance, low initial and operational costs, and high reliability under the given traffic and link length data between nodes. Because of the difficulties of this problem, approximate solutions such as probabilistic searches have long been studied. However, the real-world network topologies seem to be more type oriented than the above traditional computer based solutions. In fact, most real network topologies consist of a hierarchical combination of basic types such as the bus, the star, and the ring to avoid the difficulties of the design problem. In this paper, a new parametric method for localized spanning tree (ST) generation is proposed with good experimental results. The method performs node clustering and physical link generation in one step. This is realized by a new idea of the parameterized virtual node distance incorporating both the physical node distance and the traffic gravity between nodes with a parametric weight. A set of localized spanning trees can be generated on traditional MST algorithm, by changing the weight. As the main computational costs are the MST generation and the depth-first shortest-route search, which is not very expensive, so this is a high-speed approximate solver of the network topology design problem. To assist selecting a good solution, a link capacity determination function to achieve the given mean delay time and the monthly cost estimation function are incorporated. Approximate mathematical discussions to prove the existence of a minimum cost solution in the generated candidates is given also.A typical network topological design problem is to determine link connections and their capacity to achieve high performance, low initial and operational costs, and high reliability under the given traffic and link length data between nodes. Because of the difficulties of this problem, approximate solutions such as probabilistic searches have long been studied. However, the real-world network topologies seem to be more type oriented than the above traditional computer based solutions. In fact, most real network topologies consist of a hierarchical combination of basic types such as the bus, the star, and the ring to avoid the difficulties of the design problem. In this paper, a new parametric method for localized spanning tree (ST) generation is proposed with good experimental results. The method performs node clustering and physical link generation in one step. This is realized by a new idea of the parameterized virtual node distance incorporating both the physical node distance and the traffic gravity between nodes with a parametric weight. A set of localized spanning trees can be generated on traditional MST algorithm, by changing the weight. As the main computational costs are the MST generation and the depth-first shortest-route search, which is not very expensive, so this is a high-speed approximate solver of the network topology design problem. To assist selecting a good solution, a link capacity determination function to achieve the given mean delay time and the monthly cost estimation function are incorporated. Approximate mathematical discussions to prove the existence of a minimum cost solution in the generated candidates is given also., 一般社団法人情報処理学会, 出版日 2014年12月02日, 研究報告数理モデル化と問題解決（MPS）, 2014巻, 2号, 掲載ページ 1-5, 英語, 0919-6072, 110009848659, AN10505667 - 顕著特徴領域を利用したBoVWベース類似画像検索の改善方式の検討 (マルチメディア・仮想環境基礎)
鄒 子君; 古賀 久志
類似画像検索でよく使われているBag of Visual Words(BoVW)では全ての特徴点を均等に取り扱うため,画像内における主オブジェクトの重要性を無視している.そこで,本研究では主オブジェクトの類似性に着目したBoVWベースの類似検索手法を提案する.提案手法では,画像の前景位置は顕著特徴領域で近似できると想定し,顕著特徴領域の類似性を調べる.具体的には顕著特徴マップを二値化して前景と背景に分割し,前景領域から前景特徴ヒストグラムを形成する.そして2枚の画像間の類似度は前景ヒストグラムの類似度と画像全体から得たヒストグラムの類似度を合計して求める.この方法により,2枚の画像の前景の類似性を強調できるので類似画像検索の精度向上が期待できる.Caltech101画像データベースを用いた実験により,提案手法が従来のBoVWよりも再現率を改善できることを確認した., 一般社団法人電子情報通信学会, 出版日 2014年01月23日, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 113巻, 403号, 掲載ページ 183-188, 日本語, 0913-5685, 110009825792, AN10476092 - ハッシュを用いた類似検索技術とその応用
古賀 久志
一般に，ハッシュ法と言えば指定されたクエリとキーが同一であるデータを高速探索するための技術であり，実用上，O(1) の時間計算量で動作する．しかし，近年，クエリと完全には一致しない類似したデータを探す類似検索向けのハッシュ法が開発され，画像やテキストに代表されるメディアデータに対するコンテンツベースパターン認識の分野で成功を収めている．本稿では，このようなハッシュを利用した類似検索技術を紹介する．更に，その応用として(1) 階層的クラスタリングの近似高速化，(2) 複数画像からのオブジェクト抽出の二つの事例を紹介する．, 一般社団法人 電子情報通信学会, 出版日 2014年, 電子情報通信学会 基礎・境界ソサイエティ Fundamentals Review, 7巻, 3号, 掲載ページ 256-268, 日本語, 130004554805 - グラフの共起性に着目した複数オブジェクトを含む画像からの自動オブジェクト発見 (パターン認識・メディア理解)
南部 貴之; 古賀 久志; 渡辺 俊典
画像からの自動オブジェクト発見において成功しているBag-of-Features(BoF)の課題として特徴点の空間情報を表現しておらず,与えられた画像群に対して適切なボキャブラリ数を定めるのが難しいという点が挙げられる.これらの課題克服を目的として,Xiaらはグラフベースのオブジェクト発見手法を提案したが,1枚の画像に含まれるオブジェクトが1つであることを仮定していた.そこで,本研究ではグラフベースの複数オブジェクトを含む画像群からのオブジェクト発見手法を提案する.提案手法ではまず画像からSIFT特徴点を抽出し,SIFTマッチングの結果を利用して特徴点のクラスタリングを行う.この際,クラスタ数非教示のクラスタリングアルゴリズムを用いており,ボキャブラリ数を指定する必要はない.そして同種のオブジェクト内には同じグラフパターンが共起することを着目し,オブジェクトモデルを共起辺の集合として獲得する., 一般社団法人電子情報通信学会, 出版日 2013年03月14日, 電子情報通信学会技術研究報告 : 信学技報, 112巻, 495号, 掲載ページ 169-174, 日本語, 0913-5685, 110009713434, AN10541106 - A Novel Image Feature Extraction Approach Using Enhanced Edge Information (ヒューマン情報処理)
王 一男; 張 諾; 渡辺 俊典; 古賀 久志
The Local Binary Pattern (LBP) operator is designed for local feature description. In this study we adapt LBP for image matching. The proposed approach performs a modified LBP to extract enhanced edge information, followed by Scale Invariant Feature Transform (SIFT) which matches extracted features. We validated the proposed approach on data with various photography conditions (scale, rotation, blurring, and illumination). The results showed high performance of the proposed approach., 一般社団法人電子情報通信学会, 出版日 2012年03月22日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 111巻, 499号, 掲載ページ 1-6, 英語, 0913-5685, 110009546496, AN10541106 - A Novel Image Feature Extraction Approach Using Enhanced Edge Information
王 一男; 張 諾; 渡辺 俊典; 古賀 久志
The Local Binary Pattern (LBP) operator is designed for local feature description. In this study we adapt LBP for image matching. The proposed approach performs a modified LBP to extract enhanced edge information, followed by Scale Invariant Feature Transform (SIFT) which matches extracted features. We validated the proposed approach on data with various photography conditions (scale, rotation, blurring, and illumination). The results showed high performance of the proposed approach., 一般社団法人電子情報通信学会, 出版日 2012年03月22日, 電子情報通信学会技術研究報告. HIP, ヒューマン情報処理, 111巻, 500号, 掲載ページ 1-6, 英語, 110009546454, AN10487237 - 時系列の圧縮性を用いたネットワークトラフィックの適応的パターン解析
大関 潮; 渡辺 俊典; 古賀 久志
出版日 2012年01月19日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 111巻, 409号, 掲載ページ 47-52, 日本語, 10031106906, AN10013072 - 分散環境におけるL₁距離ベースLocality-Sensitive Hashingの通信回数削減手法とその実装評価 (データ工学)
古賀 久志; 渡辺 俊典
Locality-Sensitive Hashing(LSH)は高次元データに対する近似最近接点探索アルゴリズムである.LSHは高速な反面,ハッシュテーブルを複数個使用するため空間計算量が非常に大きい.そのため,大規模なデータに適用するには,LSHを複数計算機に分散して実現する技術が必要になる.LSHを分散環境で実現する場合,単純には各ノードにハッシュテーブルを均等に固定数ずつ配置する手法が考えられる.しかし,この方法では検索時に全ハッシュテーブルへアクセスする際に多数のリモートアクセスが発生し,通信がボトルネックとなる分散環境では応答時間が長くなる.本研究ではハッシュバケツの配置を工夫し,同じデータを含む異なるハッシュテーブル上のハッシュバケツをなるべく同じノード上に配置する方式を提案する.提案方式ではクエリ処理時に1回のリモートアクセスで複数のハッシュバケツへアクセスできるので,リモートアクセス回数が削減される., 一般社団法人電子情報通信学会, 出版日 2011年12月16日, 電子情報通信学会技術研究報告 : 信学技報, 111巻, 361号, 掲載ページ 1-6, 日本語, 0913-5685, 110009466683, AN10012921 - SURF特徴点を用いたグラフカットによる動画像からの移動物体自動抽出結果の精度向上
工藤 識実; 古賀 久志; 横山 貴紀; 渡辺 俊典
近年,動画像からグラフカットを用いて自動的に前景を抽出する手法が盛んに研究されている.これらの手法では基本的にフレーム間の動き情報や色情報から前景と背景を識別する.しかし,このような手法では移動物体の停止や照明の変化などにより,動き情報や色が不安定になると抽出の精度が低下する.そこで,本研究では照明変化にロバストで物体の動きによる影響を受けにくいSURF特徴点を利用して,現在のフレームと過去のフレームに含まれるSURF特徴点の前景,背景への分割結果を比較することで抽出結果の安定性を評価し,不安定な場合は過去のSURF特徴点のラベルを基に結果を修正することで,動きベクトルや色が不安定になるような場合でも前景を精度良く抽出する手法を提案する., 一般社団法人電子情報通信学会, 出版日 2011年11月17日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 111巻, 317号, 掲載ページ 141-146, 日本語, 0913-5685, 110009466297, AN10541106 - 背景の分割に対応したグラフマイニングベースの動画像からの背景除去
青木 玄明; 古賀 久志; 渡辺 俊典; 横山 貴紀
当研究室では頻出グラフマイニングを用いた動画像からの背景除去を行う手法GBR(Graph-based Background Removal)を提案している．GBRは，監視カメラ映像のようなカメラの前を移動物体が通過する動画像からの背景除去を行う．GBRでは，各フレームを領域隣接グラフとして表現し，背景を頻出部分グラフとして獲得する．領域単位で背景除去を行うため，カメラの動きによって背景が平行移動した場合においても，背景グラフの構造が変化しなければ背景除去を行うことができる．しかし，GBRでは背景除去を見つけられた頻出部分グラフに対応する領域のみを除去することで行っているため，背景領域が前景により分断され，背景に対応する領域の数が増えてしまった場合，分断された領域のうち一部しか削除することができないという問題がある．そこで本稿では，背景の分断を検知し，背景として認識されなかった領域を背景と認識された領域と関連付け，除去する方法を提案する．Our laboratory has proposed a background subtraction method from videos named GBR (Graph-based Background Removal) which utilizes frequent graph mining. The targets of GBR are videos in which a moving object passes in front of a surveillance camera. After transforming each video frame into a region adjacency graph, GBR discovers the subgraph representing the background as a frequent subgraph. Because GBR realizes the region-based background subtraction, it removes the background well even if the camera moves moderately, unless the camera motion breaks the graph structure. On the other hand, since GBR only removes the regions in the discovered frequent subgraphs, it has the drawback that it only removes the background partially, when some region in the background is separated into multiple pieces due to the overlapping of the foreground. This paper proposes an method which removes the background successfully even under the above background separation. The proposed method first detects the background separation and then associates the separated regions which belong to the same background region originally. Finally, the background subtraction is executed by deleting all of the associated regions., 情報処理学会, 出版日 2011年03月10日, 研究報告コンピュータビジョンとイメージメディア（CVIM）, 2011巻, 25号, 掲載ページ 1-8, 日本語, 2186-2583, 110008584014, AA11131797 - エンドホストでのAQMエミュレーションによるTCPコネクション間のスループット公平性改善
石津 圭太; 古賀 久志; 渡辺 俊典
現在のインターネットでは,輻輳制御はエンドホストでのTCPスタックとルータでのアクティブキュー管理(AQM)により実現される.近年,AQMの機能をエンドホストでエミュレーションして実現するAQMエミュレーションと呼ばれるパラダイムが提案された.本稿の目的はAQMエミュレーションの可能性を探ることである.AQMをエンドホストで実現すると,1つのAQMの処理対象はそのホストからのTCPコネクションのみなので,対象となるコネクション数が非常に少なくなる.従って,ルータでは実現困難なコネクション毎の状態を管理するコネクションステートフルなAQMを実現できる.本研究では,この特性を利用して,輻輳通知確率をTCPコネクションのアグレッシブさに適応して変化させることでスループット公平性を向上させるAQMアルゴリズムを提案する., 一般社団法人電子情報通信学会, 出版日 2011年02月24日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 110巻, 449号, 掲載ページ 359-364, 日本語, 0913-5685, 110008688985, AN10013072 - 頻出グラフマイニングを利用した動画像解析
辻 智和; 古賀 久志; 横山 貴紀; 渡辺 俊典
頻出グラフマイニングとは,大量のグラフから頻出するグラフパターンを有用な知識として抽出する手法である.SUBDUEは頻出グラフマイニングアルゴリズムとして知られており,MDL(Minimum Description Length)原理に基づいた評価式を用いて,頻出グラフパターンを発見する.本論文では,SUBDUEの新しいアプリケーションとして,SUBDUEを動画像解析に適用することを試みる.特に,監視カメラ映像のようなカメラの前を移動物体が通過する動画像から,SUBDUEを用いて背景除去する手法を提案する.このような動画では移動物体の通過前後に背景のみのビデオフレームが十分存在するため,背景を評価値が高い頻出グラフパターンとして抽出できる.具体的には,まず,ビデオフレームを領域分割し,各領域を節点,各領域間の隣接関係を辺とする領域隣接グラフとして表現する.次に,背景を評価値の高い頻出部分グラフとして取り出す.最後に,各フレームを表すグラフから背景を表すグラフを除去して,背景除去を行う.グラフのノードは領域を表すので,提案手法は画素単位ではなく領域単位の背景除去となる.したがって,提案手法ではグラフの構造が変化しない範囲であれば,カメラが動いても背景除去可能である.更に,背景のみのビデオフレーム数が少なくても背景の評価値が高くなるように評価式の変更も行った., 一般社団法人電子情報通信学会, 出版日 2010年02月01日, 電子情報通信学会論文誌. D, 情報・システム = The IEICE transactions on information and systems (Japanese edition), 93巻, 2号, 掲載ページ 86-99, 日本語, 1880-4535, 110007539031, AA12099634 - パッシブRTT推定法を使用したAQMアルゴリズム (特集 サイバーコミュニケーション環境を実現するネットワークサービス) -- (ネットワーク品質・制御)
星原 隼人; 古賀 久志; 渡辺 俊典
情報処理学会, 出版日 2010年02月, 情報処理学会論文誌 論文誌ジャーナル, 51巻, 2号, 掲載ページ 466-477, 日本語, 1882-7837, 40019546003, AA12317677 - グラフカットを用いた動画像からの自動移動物体抽出
松田 彰浩; 古賀 久志; 渡辺 俊典
近年,多くの画像処理の問題をエネルギー最小化問題に帰着し,最小グラフカット抽出アルゴリズムを用いて解く技術が注目されている.この技術の応用の一つに,静止画や動画像から,前景を背景と分離して抽出するインタラクティブセグメンテーションがある.しかし,インタラクティブセグメンテーションでは,前処理で前景と背景のseedを人間が手動で与える必要がある.そこで本研究では,固定カメラで撮影した動画像からの前景抽出を対象とし,seedを自動生成して自動的に動画像から移動物体を抽出する手法を提案する.具体的には,まず動画フレームからSIFT特徴点を抽出する.そしてSIFT特徴点を追跡して移動特徴点と静止特徴点に分類し,移動特徴点を前景seed,静止特徴点を背景seedとする., 一般社団法人電子情報通信学会, 出版日 2010年01月14日, 電子情報通信学会技術研究報告. SP, 音声, 109巻, 375号, 掲載ページ 13-18, 日本語, 0913-5685, 110008000966, AN10013221 - ユークリッド空間内の点分布の外郭を求めるアルゴリズム
小林 郁弥; 渡辺 俊典; 古賀 久志
点分布の外郭とはユークリッド空間で原点からの距離が局所的最大値となる点の集合である.凸集合の場合には1つ以上の任意のベクトルに対する射影長が最も長い点を選出すれば良い.しかし非凸集合の場合にはうまくいかない.本研究では空間を十分に目の細かい複数のブロックに分割し,個々のブロック内で分布が凸になることを仮定することでこの問題を解決する., 一般社団法人電子情報通信学会, 出版日 2010年01月14日, 電子情報通信学会技術研究報告. SP, 音声, 109巻, 375号, 掲載ページ 115-120, 日本語, 0913-5685, 110008000979, AN10013221 - 指向性アンテナを用いた無線アドホックネットワークにおける空間の有効利用を目指したパワーコントロール手法
戦 伝璽; 古賀 久志; 渡辺 俊典
無線ネットワークは物理的な帯域が小さいため,無線チャネルを空間的に分割して複数の通信を同時に行うことが重要である.一方,無線アドホックネットワークでは,無線ノードの消費電力を抑制することも要求される.パケット送信パワーを抑制するパワーコントロール手法は,無線ノードの消費電力を抑制しつつ無線チャネルを有効利用する技術として盛んに研究されている.こうしたパワーコントロール手法では調節された小さいパワーで通信する際に未使用の空間が発生する.本研究では,この未使用空間を有効利用することで無線アドホックネットワークの通信性能を向上させることを目指す.具体的には,各ノードが指向性アンテナを有するIEEE802.11ベースの無線アドホックネットワークを対象とし,既存のパワーコントロールMACプロトコルに空間を有効利用する機能を追加した新しいプロトコルを提案する.Qualnetを用いたシミュレーションによってその有効性を確認した., 一般社団法人電子情報通信学会, 出版日 2009年02月24日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 108巻, 458号, 掲載ページ 481-486, 日本語, 0913-5685, 110007324661, AN10013072 - テキスト化を介した画像分類手法の提案
平井 敦之; 張 諾; 渡辺 俊典; 古賀 久志
情報処理能力の発達に伴い電子化が急速に進行している.中でも増大する一方の画像に関しては人間の処理能力を超え,人手により分類することはもはや不可能であり,画像の自動分類技術への要求が高まっている.本稿では自動的に画像を分類する手法として,テキスト化画像の圧縮率ベクトルに基づいた手法を提案する.テキスト化のステップでは画像を長さL画素の断片に分けアルファベットを与える.分類のステップではテキスト化画像の圧縮率ベクトルの類似性を利用する.双方のステップは文字列の圧縮性に着目している.実験により提案手法の有効性を検証する., 一般社団法人電子情報通信学会, 出版日 2009年01月09日, 電子情報通信学会技術研究報告. AI, 人工知能と知識処理, 108巻, 382号, 掲載ページ 7-12, 日本語, 0913-5685, 110007123235, AN10013061 - 多頻度グラフマイニングを利用した動画の解析
辻 智和; 古賀 久志; 横山 貴紀; 渡辺 俊典
多頻度グラフマイニングとは,大量のグラフ構造から,頻出するグラフパターンを意味のあるものとして抽出する手法である.本研究では,多頻度グラフマイニングを動画像の解析に用いる.本稿では,監視カメラの前を移動物体が通過するような動画を対象に多頻度グラフマイニングを用いてグラフベースの背景除去手法を提案する.具体的には,各ビデオフレームを領域分割し,各領域を節点,各領域間の隣接関係を辺としてグラフ構造を作る.この時,背景部分が頻出パターンとなることを利用して背景除去を行う., 一般社団法人電子情報通信学会, 出版日 2008年12月11日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 108巻, 363号, 掲載ページ 19-24, 日本語, 0913-5685, 110007123819, AN10541106 - MPEG動きベクトルを用いたグローバルモーション推定に基づく移動物体のリアルタイム抽出
大田 修平; 横山 貴紀; 渡辺 俊典; 古賀 久志
本稿では,MPEG動きベクトルから推定されるグローバルモーションに基づく移動物体のリアルタイム抽出手法について報告する.MPEGビデオデータの動きベクトルから,外れ値除去を用いたニュートン・ラフソン法によってグローバルモーションを推定し,その結果に基づいて動きベクトルを分類し,移動物体を抽出する手法である.非固定カメラ等によって得られた動画像では,移動物体でない背景にも見かけ上の動きが生じてしまい,本来の移動物体の動きを抽出することを阻害する.そこで,入力された動きベクトルからグローバルモーションを推定し,そのグローバルモーションを入力された動きベクトルから減算することで,カメラの動きに伴う動きベクトルのグローバルな変動を吸収することができ,非固定カメラによって得られた動画像からでも移動物体を抽出することが可能となる.実際に撮影によって得られたMPEGビデオデータを用いて実験を行い,市販のノートパソコン上でリアルタイム処理が可能なことなどを示す., 一般社団法人電子情報通信学会, 出版日 2008年10月16日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 108巻, 263号, 掲載ページ 19-24, 日本語, 0913-5685, 110007101143, AN10541106 - 映像からの動作オブジェクト自動学習システムAMOR
徳冨 兼太郎; 渡辺 俊典; 古賀 久志; 横山 貴紀
ビデオ内の動作オブジェクトを自動学習し,認識するシステムAMORについて報告する.類似動作それぞれに同一の要素動作ラベルを付与する下位機能と,要素動作ラベル列内の複合動作部分列を抽出する上位機能とで構成した.未知,多様,ノイジーな対象に対応するため多解像処理を導入し,前者を学習機能付き要素動作ラベリング機構,後者を層間制約伝播機能付き要約機構で構成した.細かさの異なる複数動作が混在する人物ビデオに適用し,ビデオ入力のみから,要素動作ラベル付け,複合動作抽出,さらに上位の繰り返し動作パターンなどを抽出できるようになることを確かめた., 一般社団法人電子情報通信学会, 出版日 2008年02月21日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 107巻, 491号, 掲載ページ 31-36, 日本語, 0913-5685, 110006937534, AN10541106 - 異種の高速トランスポートプロトコルへの帯域公平性を考慮したUDTの改良
河野 伸也; 古賀 久志; 渡辺 俊典
近年,ネットワークの広帯域化に伴い,Gridやネットワークストレージシステムなどの長距離高速通信を必要とするアプリケーションが出現してきた.しかし,現在一般的に使用されているTCP(TCF Reno)では,帯域幅遅延積の大きいネットワークで十分に帯域を利用できないことが知られている.そこで,帯域幅遅延積の大きいネットワークで十分に帯域を利用するために,様々な高速トランスポートプロトコルが提案されている.その一つとしてUDTがあるが,他の高速トランスポートプロトコルと共存した場合,帯域を奪ってしまうという問題がある.そこで,他のコネクションとの帯域公平性を考慮し,レートの増加を和らげる機能を追加したmUDT (moderate UDT)の提案する., 一般社団法人電子情報通信学会, 出版日 2007年12月06日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 107巻, 378号, 掲載ページ 13-18, 日本語, 0913-5685, 110006546838, AN10013072 - 高次元圧縮空間の対話的手法による次元縮小
山崎 啓介; 張諾; 渡辺 俊典; 古賀 久志
高次元特徴空間を用いるテキスト分類等において不必要な次元軸を排除することは計算量などの面から重要な問題である．この問題を解決するためには不要と考えられる次元を見出し，類性能を保つ範囲でその次元を削除していくことを繰り返せば良い．本稿では，まずテキストをその圧縮率ベクトルに着目して特徴付ける方式を示し，そこでの次元縮小法と次元縮小に必要なパラメータ設定を支援する指標関数を提案する．指標関数を参考にしながら対話的に次元縮小を行うことで，分類精度を保ったまま約 50 ％の次元縮小が可能となった．When text classification is implemented in high-dimension space, removing unnecessary dimensions becomes important to reduce computation cost. This problem can be solved by finding out unnecessary dimensions and removing them , keeping the classification power of the space. In this paper, we express texts by compression ratio vectors. After introducing it, we propose an interactive dimension reduction method with an index function. The index function is used to judge whether reduction should be continued or not. By removing unnecessary dimensions by using the interactive processing , we clould achieve 50％ dimension reduction while keeping the classification accuracy of the space., 一般社団法人情報処理学会, 出版日 2007年09月25日, 情報処理学会研究報告自然言語処理（NL）, 2007巻, 94号, 掲載ページ 35-40, 日本語, 0919-6072, 110006402896, AN10115061 - マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法
ヒブランフェンテスピネダ; 古賀 久志; 渡辺 俊典
領域分割された画像から，例を教示することなくオブジェクトを自動発見する手法を提案する．提案手法ではオブジェクトを部品の集合体と想定して，さらに各部品は同色の近隣画素群から構成されていると考え，以下の4フェーズを経て画像からオブジェクトを自動的に抽出する．(1) 近くの同色画素同士をクラスタにして部品を決定する．(2)抽出された部品を属性値によって分類してラベル付けする．(3)近接する部品群をクラスタにしてオブジェクト候補を抽出する．(4)複数個出現したオブジェクト候補を意味のあるオブジェクトとみなして抽出する．提案システムでは，上記の4ステップをすべてハッシュ関数を用いて実現する．特に，最初の3フェーズはLSH(locality-sensitive hashing)のようなユークリッド空間におけるハッシュによって実現され，第4フェーズは通常のハッシュによって実現される．このようにオブジェクト発見における基本オペレーションがハッシュ関数のみで実現できる可能性を示した点が提案手法の特徴である．本手法はハッシュ技術しか利用しないため，簡単に実装できる．さらに，第にコンポーネント間の厳密な位置関係を見ないので，第4フェーズでは回転，平行移動に対してロバストに同種オブジェクトを発見できる．実験により提案手法の有効性を示す．This paper proposes a component-based method to discover objects automatically without examples from segmented images. Our approach deems an object as combination of components, where each component consists of near pixels with the same color. The object discovery is realized in four phases: (1) discovery of components by gathering close pixels with the same color, (2) labeling of components by gathering components with similar attribute values, (3) discovery of object candidates by gathering close components, and (4) determination of valid objects among candidates, such that if the same kind of object candidates appear multiple times, they are regarded as meaningful objects. The primary contribution of this approach is to demonstrate that several essential functions in object discovery can be implemented only by hashing techniques. Especially, the first three phases rely on a hashing on Euclidean space like locality-sensitive hashing. The final fourth phase uses standard hashing technique. Since the algorithm only uses hashing techniques, it is easy to implement. Our system is robust against various parameters (rotation, translation, etc). The experimental results under different scenes and patterns present the validness of the method., 一般社団法人情報処理学会, 出版日 2007年09月04日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2007巻, 87号, 掲載ページ 265-270, 英語, 0919-6072, 110006403849, AA11131797 - マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法
ピネダ ヒブラン フェンテス; 古賀 久志; 渡辺 俊典
領域分割された画像から,例を教示することなくオブジェクトを自動発見する手法を提案する.提案手法ではオブジェクトを部品の集合体と想定して,さらに各部品は同色の近隣画素群から構成されていると考え,以下の4フェーズを経て画像からオブジェクトを自動的に抽出する.(1)近くの同色画素同士をクラスタにして部品を決定する.(2)抽出された部品を属性値によって分類してラベル付けする.(3)近接する部品群をクラスタにしてオブジェクト候補を抽出する.(4)複数個出現したオブジェクト候補を意味のあるオブジェクトとみなして抽出する。提案システムでは,上記の4ステップをすべてハッシュ関数を用いて実現する.特に,最初の3フェーズはLSH(locality-sensitive hashing)のようなユークリッド空間におけるハッシュによって実現され,第4フェーズは通常のハッシュによって実現される.このようにオブジェクト発見における基本オペレーションがハリシュ関数のみで実現できる可能性を示した点が提案手法の特徴である.本手法はハッシュ技術しか利用しないため,簡単に実装できる.さらに,第にコンポーネント間の厳密な位置関係を見ないので,第4フェーズでは回転、平行移動に対してロバズトに同種オブジェクトを発見できる.実験により提案手法の有効性を示す., 一般社団法人電子情報通信学会, 出版日 2007年08月27日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 107巻, 206号, 掲載ページ 265-270, 英語, 0913-5685, 110006423324, AN10541106 - マルチフェーズハッシュを利用した部品ベースオブジェクト発見手法
ピネダ ヒブラン フェンテス; 古賀 久志; 渡辺 俊典
領域分割された画像から,例を教示することなくオブジェクトを自動発見する手法を提案する.提案手法ではオブジェクトを部品の集合体と想定して,さらに各部品は同色の近隣画素群から構成されていると考え,以下の4フェーズを経て画像からオブジェクトを自動的に抽出する.(1)近くの同色画素同士をクラスタにして部品を決定する.(2)抽出された部品を属性値によって分類してラベル付けする.(3)近接する部品群をクラスタにしてオブジェクト候補を抽出する.(4)複数個出現したオブジェクト候補を意味のあるオブジェクトとみなして抽出する。提案システムでは,上記の4ステップをすべてハッシュ関数を用いて実現する.特に,最初の3フェーズはLSH(locality-sensitive hashing)のようなユークリッド空間におけるハッシュによって実現され,第4フェーズは通常のハッシュによって実現される.このようにオブジェクト発見における基本オペレーションがハリシュ関数のみで実現できる可能性を示した点が提案手法の特徴である.本手法はハッシュ技術しか利用しないため,簡単に実装できる.さらに,第にコンポーネント間の厳密な位置関係を見ないので,第4フェーズでは回転、平行移動に対してロバズトに同種オブジェクトを発見できる.実験により提案手法の有効性を示す., 一般社団法人電子情報通信学会, 出版日 2007年08月27日, 電子情報通信学会技術研究報告. HIP, ヒューマン情報処理, 107巻, 207号, 掲載ページ 265-270, 英語, 0913-5685, 110006423366, AN10487237 - モバイルアドホックネットワークにおけるマルチパスロードアウェアルーティングを利用した優先制御ベースのQoSフレームワーク
ニヤフ アリ; 古賀 久志; 北村 浩; 渡辺 俊典
無線端末のみから構成されるモバイルアドホックネットワーク(MANET)の利用が進むに連れて、有線ネットワークと同様なビデオ・音声のリアルタイムマルチメディア通信をサポートすることが期待され、通信の品質保証(QoS)が重要になる。本論文では、MANETにおいてリアルタイムアプリケーションに代表される優先度の高い通信とデータ転送に代表される優先度の低い通信が混在する状況において、マルチパスルーティングを使うことで高優先度の通信の自己干渉を効率的に削減し、かつ、パスの混雑具合も選択基準にいれること(ロードアウェアルーティング)でより大きなスループットが得られることをシミュレーションで確認した。また高優先度通信の経路断絶回数を10%以上削減できることを確認した。, 一般社団法人電子情報通信学会, 出版日 2007年03月01日, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 106巻, 578号, 掲載ページ 37-42, 英語, 0913-5685, 110006248547, AN10013072 - スライディングウインドウを考慮したDynamicTCPAclmowledgment問題
古賀 久志
ＴＯＰプロトコルにおける通信では受信者はパケットを受信すると到達確認(acknowledgment 以下ack)を送信者に返して，送信が成功したことを知らせる．受信者は各到着パケットに１度ずつackを返すのではなく，複数の到着パケットに対して１度のackでまとめて到達確認を済ますことが出来る．この機構を使うとａｃｋ回数を減らせるが 逆に送信ホストによる到達確認が遅れ通信が遅滞するという欠点もある．DynamicTCPacknowledgment問題はこのトレードオフに対するオンライン最適化問題である．しかしながら、従来のDynamicTCPAcknowledgement問題の枠組では 受信者がackをなかなか返さない場合に送信者が自主的に送信を抑えるスライディングウインドウの機構を考慮していない．そこで本研究では スライディングウインドウの機構を組み込んだDynamicTCPAcknowledgement問題を定式化して オンラインアルゴリズムの性能を競合比解析を用いて評価する．特にウインドウサイズが固定値Ｗであると仮定して解析を行い 受信者がＷを知らされていれば２－competitiveなオンラインアルゴリズムを構築できるのに対し，Ｗを知らされていない場合には 従来の枠組での最適オンラインアルゴリズムを含むアルゴリズムクラスの競合比の下限値が送信者が送ろうとする単位時間辺りの最大パケット数に依存してしまうことを示す．In TCP protocol, each packet arriving at the receiver must be acknowledged by the receiver in order to notify the sender that the transmission was successful. However, each packet need not be acknowledged individually. Instead, the receiver is allowed to acknowledge multiple packets with a single acknowledgement by postponing the acknowledgement. Though this mechanism is advantageous with respect to reduce the number of acknowledgements, delaying acknowledgements may add excessive latency to the TCP connection. Dooly et al. formulated this trade-off as the dynamic TCP acknowledgement problem. However, their framework does not consider the concept of sliding window that restricts the maximum number of packets that the sender can inject into the network without notified acknowledgements. In this paper, we propose a new problem in which the sliding window is integrated into the dynamic TCP acknowledgement problem realistically. We evaluate the performance of on-line algorithms with competitive analysis, assuming that the window size is a constant integer W>\. We show that there exists a 2-competitive deterministic on-line algorithm if on-line algorithms know the value of W beforehand. By contrast, if they do not know W, the lower bound of the competitive ratio for an algorithm class containing the optimal on-line algorithm for the original framework by Dooly et al. that is 2-competitive now depends on the maximum number of packets that the sender wishes to send per unit time., 一般社団法人情報処理学会, 出版日 2007年01月23日, 情報処理学会研究報告アルゴリズム（AL）, 2007巻, 5号, 掲載ページ 1-8, 英語, 0919-6072, 110006202672, AN1009593X - ピット近似関数を用いた局所解集合探索
肥塚 真由子; 渡辺 俊典; 古賀 久志
評価コストが高く，かつ連続離散混在変数による必ずしもなめらかでない非線形関数の局所解集合の探索的手法を提案する．取り扱い可能な未知パラメータの個数は限定されるが 関数のタイプに限定されることなく利用できる利点を持ち 局所解の集合を探索する能力を持つため 結果的に大域的最適解を探索する能力が高い点などが特徴である．In this paper we propose a search method for local optimum set of a nonlinear cost function with high computation cost, continuous and discrete variables, and non-smoothness. Although the scope of dimensionality is rather modest, it can be applied to a wide class of nonlinear functions. Also, the chance of global optima finding is improved by its set searching property., 一般社団法人情報処理学会, 出版日 2006年12月22日, 情報処理学会研究報告数理モデル化と問題解決（MPS）, 2006巻, 135号, 掲載ページ 69-72, 日本語, 0919-6072, 110006165024, AN10505667 - 圧縮性とオブジェクトらしさ尺度に着目した画像からのオブジェクト自動抽出法
杉山 英行; 古賀 久志; 渡辺 俊典; 横山 貴紀
サンプル画像を与えるだけで人手を介さずにオブジェクトを自動抽出する方式を提案する.その基礎として,先ず,構成する部品の位置関係が変化するオブジェクトを簡単に記述できる近傍集合表現を述べる.次に,画像内により多く出現しより多くの部品から成るものがオブジェクトとして妥当であると考え,画像表現に必要なデータ量の圧縮度という評価関数を定式化する.ここでは,複数個出現する同種オブジェクトインスタンスの面積,縦横比,密度の一様性もオブジェクトらしさ尺度として考慮する.次に,この評価関数値が最大となるようなオブジェクトを画像中から探索するオブジェクト自動抽出アルゴリズムを与える., 一般社団法人電子情報通信学会, 出版日 2006年11月17日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 106巻, 376号, 掲載ページ 183-188, 日本語, 0913-5685, 110005717945, AN10541106 - 輸送問題の解法に基づく動き領域抽出手法
古川 翔; 横山 貴紀; 渡辺 俊典; 古賀 久志
本報告では,輸送問題の解法に基づく移動領域抽出手法を提案する.この手法では,着目するフレームの領域を供給地,移動先を求めたい対象フレームの領域を需要地とし,領域間の距離を輸送コストと考える.総輸送量を最小とする輸送問題を解くことで,領域間の対応関係を求めることができる.対応関係はフローとして表現することができ,対応する領域の組と輸送距離,輸送された画素数の情報を持つ.提案手法はこのフローに基づき移動領域を抽出することができる.各種実験を通じて有効性を確認したので報告する., 一般社団法人電子情報通信学会, 出版日 2006年10月13日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 106巻, 301号, 掲載ページ 59-64, 日本語, 0913-5685, 110004852069, AN10541106 - LZ78の圧縮性を利用した文書検索手法の提案
木村 洋章; 渡辺 俊典; 古賀 久志; 張諾
著者らは情報の圧縮性に着目した新たなマルチメディアデータ解析手法の研究を進めている．PRDC(Pattern Representation Scheme using Data Compression)[1]と呼ぶこの新概念の中では，二つのデータX，Yの類似度を，それらを圧縮辞書D1，D2，…，Dnで圧縮した時の圧縮率ベクトルの類似度で判断する．本論文ではPRDCを用いた新文書検索システムの可能性を探る．部分的ではあるが，文書分類，公知／特異句抽出，文書要約，など将来の高自立・適応文書検索システムの実現に重要な機能を実現できる可能性を提示する．キーワード 文書解析，情報検索，要約，新句抽出，データ圧縮We have been studying a new multimedia data analysis scheme based on the concept of compressibility. In this new concept of PRDC（Pattern Representation Scheme using Data Compression)[1], we consider two data, let them X and Y, are similar if their compressibility vectors under a set of compression dictionaries D1, D2, ..., Dn are similar. Here we investigate the possibility of new document retrieval system using the PRDC. We prove that PRDC has possibilities to solve several fundamental problems including, document classification, common/distinguished phrase extraction, and summary, that should be realized in the future highly autonomous and adaptive document retrieval systems.Key words Document analysis, Retrieval, Summarization, New phrase detection, Data compression, 一般社団法人情報処理学会, 出版日 2006年09月12日, 情報処理学会研究報告自然言語処理（NL）, 2006巻, 94号, 掲載ページ 65-70, 日本語, 110004824260, AN10115061 - 圧縮性に注目した文書の関係分析手法
松崎 大輔; 渡辺 俊典; 古賀 久志; 張諾
文書間の関係を分析する手法として，辞書ベースの形態素解析を用いて，語の出現頻度による類似性や，キーワード抽出を用いる方法が幅広く利用されている．これらの伝統的手法は，日々新しい単語が生まれるインターネットなどの環境には万全とはいえない．その理由は，これらの伝統的解析手法の前提となる，辞書に登録されていない未知語が頻繁に出現するためである．本稿では文書の圧縮率に注目し，人手による解析辞書の事前整備が不要な，文書の関係分析手法を提案する．提案手法について実験を行いその有効性を検討する．キーワード 文書分析，クラスタリング，データ圧縮Dictionary-based morphological analysis is one of the main techniques for document analysis. It is usually used for keyword extraction and classification of similar words. Dictionary-based methods are weak for such environment as the Internet where new words appear that are not contained in the dictionary. In this study, we propose a new document relation analysis method based on the document's compressibility, requiring no dictionary. The effectiveness of our method is examined through some experiments. Key words Document analysis, Clustering, Data compression, 一般社団法人情報処理学会, 出版日 2006年09月12日, 情報処理学会研究報告情報学基礎（FI）, 2006巻, 94号, 掲載ページ 51-56, 日本語, 0919-6072, 110004824211, AN10114171 - 圧縮性に注目した文書の関係分析手法
松崎 大輔; 渡辺 俊典; 古賀 久志; 張諾
文書間の関係を分析する手法として，辞書ベースの形態素解析を用いて，語の出現頻度による類似性や，キーワード抽出を用いる方法が幅広く利用されている．これらの伝統的手法は，日々新しい単語が生まれるインターネットなどの環境には万全とはいえない．その理由は，これらの伝統的解析手法の前提となる，辞書に登録されていない未知語が頻繁に出現するためである．本稿では文書の圧縮率に注目し，人手による解析辞書の事前整備が不要な，文書の関係分析手法を提案する．提案手法について実験を行いその有効性を検討する．キーワード 文書分析，クラスタリング，データ圧縮Dictionary-based morphological analysis is one of the main techniques for document analysis. It is usually used for keyword extraction and classification of similar words. Dictionary-based methods are weak for such environment as the Internet where new words appear that are not contained in the dictionary. In this study, we propose a new document relation analysis method based on the document's compressibility, requiring no dictionary. The effectiveness of our method is examined through some experiments. Key words Document analysis, Clustering, Data compression, 一般社団法人情報処理学会, 出版日 2006年09月12日, 情報処理学会研究報告自然言語処理（NL）, 2006巻, 94号, 掲載ページ 51-56, 日本語, 110004824258, AN10115061 - LZ78の圧縮性を利用した文書検索手法の提案
木村 洋章; 渡辺 俊典; 古賀 久志; 張諾
著者らは情報の圧縮性に着目した新たなマルチメディアデータ解析手法の研究を進めている．PRDC(Pattern Representation Scheme using Data Compression)[1]と呼ぶこの新概念の中では，二つのデータX，Yの類似度を，それらを圧縮辞書D1，D2，…，Dnで圧縮した時の圧縮率ベクトルの類似度で判断する．本論文ではPRDCを用いた新文書検索システムの可能性を探る．部分的ではあるが，文書分類，公知／特異句抽出，文書要約，など将来の高自立・適応文書検索システムの実現に重要な機能を実現できる可能性を提示する．キーワード 文書解析，情報検索，要約，新句抽出，データ圧縮We have been studying a new multimedia data analysis scheme based on the concept of compressibility. In this new concept of PRDC（Pattern Representation Scheme using Data Compression)[1], we consider two data, let them X and Y, are similar if their compressibility vectors under a set of compression dictionaries D1, D2, ..., Dn are similar. Here we investigate the possibility of new document retrieval system using the PRDC. We prove that PRDC has possibilities to solve several fundamental problems including, document classification, common/distinguished phrase extraction, and summary, that should be realized in the future highly autonomous and adaptive document retrieval systems.Key words Document analysis, Retrieval, Summarization, New phrase detection, Data compression, 一般社団法人情報処理学会, 出版日 2006年09月12日, 情報処理学会研究報告情報学基礎（FI）, 2006巻, 94号, 掲載ページ 65-70, 日本語, 0919-6072, 110004824213, AN10114171 - ＭＰＥＧビデオデータの動きベクトルを用いた移動物体追跡手法
岩崎敏紀; 横山 貴紀; 渡辺 俊典; 古賀 久志; 阿部 龍士
MＰＥＧによって圧縮された動画像データから移動物体を追跡する手法を提案する．ＭＰＥＧによって圧縮された動画像データには 動き補償予測のために動きベクトルがすでに記録されている．この動きベクトルの始点終点に基づいた領域と フレーム間を通しての動きベクトルの連続性を用いて，フレーム内を始点終点領域 始点領域 終点領域及び 補間領域に区別する．各領域の属性と動きベクトルを基に移動物体の検出 追跡を行うIn this paper, we propose a method to detect moving objects using motion vectors in MPEG video data. MPEG video data generated by motion compensated prediction contains motion vectors that describe motions of objects. Therefore, it is possible to track and detect moving objects, in the compressed domain, using these vectors. Regions in each frame can also be reconstructed using these vectors. Exploiting the reconstructed regions, we can detect moving objects., 一般社団法人情報処理学会, 出版日 2006年09月09日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2006巻, 93号, 掲載ページ 167-174, 日本語, 0919-6072, 110004820687, AA11131797 - MPEGビデオデータの動きベクトルを用いた移動物体追跡手法
岩崎 敏紀; 横山 貴紀; 渡辺 俊典; 古賀 久志; 阿部 龍士
MPEGによって圧縮された動画像データから移動物体を追跡する手法を提案する.MPEGによって圧縮された動画像データには,動き補償予測のために動きベクトルがすでに記録されている.この動きベクトルの始点終点に基づいた領域と,フレーム間を通しての動きベクトルの連続性を用いて,フレーム内を始点終点領域,始点領域,終点領域及び,補間領域に区別する.各領域の属性と動きベクトルを基に移動物体の検出,追跡を行う, 一般社団法人電子情報通信学会, 出版日 2006年09月02日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 106巻, 230号, 掲載ページ 33-40, 日本語, 0913-5685, 110004849817, AN10541106 - 木編集距離を利用した木データの構造と内容の類似性を反映する分類手法
齋藤 裕明; 古賀 久志; 渡辺 俊典; 横山 貴紀
木は半構造データや遺伝子情報など多様なオブジェクト表現に用いることが出来るデータ構造であり、パターン認識や情報検索を行う為には木間の類似度を求める技術が重要である。木間類似度としては、2つの木をノードの挿入、削除、置換によって一致させる際の木編集距離を非類似度とする方法がある。木編集距離は木の構造の類似性と内容(ラベル)の類似性を含む非類似度であるが,木データを分類する際、構造の類似性と内容の類似性のどちらを重視するかはアプリケーションやデータによって異なる。そこで本論文では、木編集距離を内容非類似度と構造非類似度の2つに分離し、適用対象の特徴やユーザーの目的を適切に反映するクラスタリング結果を得る方法を提案する。, 一般社団法人電子情報通信学会, 出版日 2006年06月08日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 106巻, 99号, 掲載ページ 7-12, 日本語, 0913-5685, 110004748917, AN10541106 - 属性付きグラフマッチングアルゴリズムの効率的な実装
森田 昭広; 古賀 久志; 渡辺 俊典; 横山 貴紀
グラフのマッチング問題は一般に計算量が膨大であるが，問題固有の属性情報などを用いて効率的な探索を実現できる可能性がある．本研究では，グラフマッチング問題が入力2グラフから生成される積グラフの最大クリークを抽出する問題へ還元できることに着目し，その効率化のために2つの属性情報利用アルゴリズムを考案した．1つ目はクリーク抽出の探索過程で属性情報を用いて探索領域を削減する方法，2つ目は積グラフの生成時に属性情報を用いて積グラフの規模自体を抑制する方法である．これらを計算機実験によって比較検証した結果，双方共に有効であるが，特に後者の有効性が顕著であることを確認した．Graph matching problem has a very high computational complexity. But we can reduce it by exploiting domain-specific information such as object's attributes. In this research, where we solve the graph matching problem by reducing it into a maximum clique problem in a product graph generated from the two input graphs, we propose two algorithms, both exploiting attribute information. One is the method of decreasing the search space by using attribute information in the process of maximum clique search. The other is the method of decreasing the size of the product graph by using attribute information during the product graph generation. Through experiments we showed that, although both are effective, the latter dominates the former., 一般社団法人情報処理学会, 出版日 2006年03月17日, 情報処理学会研究報告アルゴリズム（AL）, 2006巻, 30号, 掲載ページ 49-54, 日本語, 0919-6072, 110004687072, AN1009593X - 投票機構を用いた動作モデルのオンライン自動獲得
吉岡 泰智; 古賀 久志; 渡辺 俊典; 横山 貴紀
一般に人の動作を認識する手法は, あらかじめ多数の動作モデルを用意する必要がある.本研究では, 未知の連続動作をオンラインで学習していき, 動作モデルを自動獲得することによって, あらかじめ多数の動作モデルを用意することなく人物の動作を認識する手法を報告する.実験において, 人物の動作を学習, 認識し, 有効性を確認した., 一般社団法人電子情報通信学会, 出版日 2005年09月22日, 電子情報通信学会技術研究報告, 105巻, 302号, 掲載ページ 119-124, 日本語, 0913-5685, 110003275988, AN10541106 - 将来の輻輳状態の予測に基づくアクティブキュー管理手法の提案
星原 隼人; 古賀 久志; 北村 浩; 渡辺 俊典
AQM(Active Queue Management)はルータによる輻輳制御技術として知られている.代表的なものにRED(Random Early Detection)や, パケットマーキングの手法であるECN(Explicit Congestion Notification)を利用したREM(Random Exponential Marking)などがある.TCPコネクションによる既存の輻輳制御はその効果が現れるまでRTT(Round Trip Time)分の遅れを持つが, RTT後の輻輳状態を考慮に入れたものは少ない.本論文では, RTT後の輻輳状態の予測を利用することにより, 入力トラフィックの変化に強くキューの溢れにくいECNマーキングベースのAQM手法を提案する., 一般社団法人電子情報通信学会, 出版日 2005年09月15日, 電子情報通信学会技術研究報告, 105巻, 279号, 掲載ページ 25-30, 日本語, 0913-5685, 110003224923, AN10013072 - クラスタリングアルゴリズム LSH-Link を利用した動画像からのオブジェクト軌跡の自動抽出
草場 洋明; 古賀 久志; 渡辺 俊典
本研究では, ノンパラメトリックで単純なアルゴリズムによる時空間領域でのオブジェクト抽出手法を提案する.本手法では, 代表的な階層的クラスタ解析手法である単結合法(Single-Link)の高速近似アルゴリズムであるLSH-Linkアルゴリズムを用いて, 動画像を色情報と時空間情報の6次元データとみなしクラスタリングを行うことでオブジェクト軌跡を抽出する.更に, 取り出されたオブジェクト軌跡の形状のモーメントを用いて複合オブジェクトの抽出を行う.模擬画像に対しての実験により本手法の効果を確認した., 一般社団法人電子情報通信学会, 出版日 2005年02月24日, 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション, 104巻, 667号, 掲載ページ 37-42, 日本語, 0913-5685, 110003278840, AN10091225 - 木のDPマッチングを利用したDTD類似度の考察
小野里 卓也; 古賀 久志; 渡辺 俊典
木構造はXMLや遺伝子情報など多種多様なオブジェクトを表現するのに用いられる。こうした木として表現されたオブジェクトに対して検索や分類を行うには、木の類似度を求める技術が重要である。木の類似度を計算するアルゴリズムとしては木間でDPマッチングを行う手法が知られている。これは、2つの木をノードの挿入、削除、置換によって変換する際の変換コストを類似度とする手法であるが、実際にアプリケーションに適用するには適切なノードの挿入、削除、置換コストを事前にわかっていなければならない。そこで、本研究では木のDPマッチングにおける適切なノードの挿入、削除、置換コストが不明である場合であってもオブジェクトの類似度を定義する手法も提案する。本手法をXMLのスキーマであるDTDの類似性判定に適用し、有用性を確認する。, 一般社団法人電子情報通信学会, 出版日 2005年02月24日, 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション, 104巻, 667号, 掲載ページ 103-108, 日本語, 0913-5685, 110003278851, AN10091225 - オンライン実時間PCAを用いた動画からの変動背景の推定
杉山 賢治; 古賀 久志; 渡辺 俊典; 横山 貴紀
カメラの振動などによる背景変化を伴う動画から背景を推定する手法を提案する.主成分分析で得られる固有空間を用いて, 変動背景下で背景以外のオブジェクトを検知, 除去することによって背景を抽出する.オンライン実時間PCAを使うことでこの処理を高速化した., 一般社団法人電子情報通信学会, 出版日 2005年02月24日, 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション, 104巻, 667号, 掲載ページ 31-36, 日本語, 0913-5685, 110003278839, AN10091225 - オプティカルフローを用いた複雑背景下における人物領域の抽出
岩崎 敏紀; 横山 貴紀; 古賀 久志; 渡辺 俊典
本報告では、オプティカルフローを用いた複雑背景下における人物領域の抽出手法を提案する。この手法では、複数のフレームを用いてオプティカルフローを生成し、このフローに基づいて人物領域の抽出を行う。複数のフレームを用いてオプティカルフローを生成することで、複雑背景下においても安定したオプティカルフローを抽出することができる。また、オプティカルフローを用いることで背景差分やフレーム間差分では抽出することのできない人物領域の抽出を可能にする。この提案手法を用いて、複雑な背景下においても信頼性の高い人物領域の抽出が可能なことを実験により確認した。, 一般社団法人電子情報通信学会, 出版日 2005年02月24日, 電子情報通信学会技術研究報告. NLC, 言語理解とコミュニケーション, 104巻, 667号, 掲載ページ 73-77, 日本語, 110003278846, AN10091225 - 圧縮率を利用した画像からのオブジェクト自動抽出
杉内 崇浩; 渡辺 俊典; 古賀 久志
近年、オブジェクト認識は、セキュリティ認証、ロボットビジョンなどさまざまな場面で使われるようになってきた。我々は、画像オブジェクトをカラー画像の領域分割により直接得られる領域の集合と考えることにより、オブジェクト定義の自動抽出、認識手法について検討している。本稿では、画像内に複数回出現するオブジェクトを圧縮して得られる圧縮率を利用した自動オブジェクト抽出手法を提案する。In recent years, object recognition has come to be used in various scenes, such as security authentication and robot vision. We study automatic extraction and recognition of objects from images by considering an object as a set of the regions directly obtained by image segmentation. In this paper, the automatic object extraction method using data compression ratio in compressing the objects which appears multiple times in image is proposed., 一般社団法人情報処理学会, 出版日 2004年11月12日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2004巻, 113号, 掲載ページ 133-140, 日本語, 0919-6072, 110002694803, AA11131797 - 骨格線を利用したオブジェクト検索手法
中山 仁; 渡辺 俊典; 古賀 久志
オブジェクトより得られる骨格線を利用したオブジェクト検索手法を提案する．本手法では，階層化されたオブジェクトの骨格を木構造で表現する．木のノードに骨格のトポロジカルな特徴を持たせて，木のマッチングでオブジェクト間の類似度を求め，オブジェクト検索を実現する．トポロジカルな特徴は，オブジェクト形状が多少変形した場合でも変化しないため，ロバストなオブジェクト検索が行える．We propose a method to search objects using skeletons. In this method, the skeletons of objects are expressed by trees. Then the object retrival is realized by associating tree nodes with topological features and calculating the similarities between objects as tree-edit distances. Because topological features do not change against shape transformation to some extent, our object retrival metood has robustness., 一般社団法人情報処理学会, 出版日 2004年11月12日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2004巻, 113号, 掲載ページ 141-146, 日本語, 0919-6072, 110002694804, AA11131797 - 投票機構を用いた人物動作の認識手法
大藤 篤史; 渡辺 俊典; 古賀 久志
人間の胴体・下半身の形状などをシルエット画像から自動抽出し、投票機構を用いてモデル動作データベースとのマッチングをとることによって、動画像から人物の基本動作を自動認識するシステムを構築した。投票機構は、身体スケルトンの特徴ごとで個別にマッチングを行い最後に足し合わせるという手法で認識を行う。時間や画像にノイズが存在していてもロバストな認識を行うことができる特長がある。本システムを用いることにより、人物の基本動作を認識できることを確認した。We built the system which recognizes basic motion of a human automatically from video by extracting the shape of human from silhouette and compareing it to human motion database with voting. The recognition method with voting is performed by summing up calculated votes obtained from the comparison of human body skeletons. It enables robust recognition against noisy condition. We confirmed that our system can recognize the basic behavior of human., 一般社団法人情報処理学会, 出版日 2004年11月12日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2004巻, 113号, 掲載ページ 83-88, 日本語, 0919-6072, 110002694797, AA11131797 - 相互写像に基づくベクトル集合間類似度とその上限値
横山 貴紀; 渡辺 俊典; 古賀 久志
画像をフラクタル圧縮して得られるフラクタル符号の類似検索手法を検討している．この検索手法では，フラクタル符号をベクトル集合と見なし，ベクトル集合間の類似度を用いて検索を行う．ベクトル集合間の類似度計算コストは高く，検索時間に実用上の問題があったが，類似度の上限値を用いて類似度算出の対象数を削減する手法により大幅な改善を実現した．本稿では，この既報告の上限値を拡張し，部分集合に基づく新たな上限値設定法を提案する． この新たな上限値は，既提案の上限値を一般化したものであり，部分集合の取り方によって多様な上限値設定が可能となる．上限値設定法の詳細と，部分集合の扱いを説明した後，画像検索への適用結果を示す．We have proposed a fractal code retrieval method. There, we interpreted a fractal code as a vector set, and introduced a similarity measure between vector sets. This similarity measure required high computation cost. To reduce it, we proposed a method to use upper bounds of the similarity measure. In this report, we further improve the proposed upper bounds by using subsets of the vector sets, and introduce a new upper bound of the similarity measure. This new upper bound is a generalization of the already proposed upper bounds. After discussions on the details of the new upper bound, and we examine its properties through an image retrieval experiment., 一般社団法人情報処理学会, 出版日 2004年09月10日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2004巻, 91号, 掲載ページ 145-150, 日本語, 0919-6072, 110002664192, AA11131797 - 相互写像に基づくベクトル集合間類似度とその上限値
横山 貴紀; 渡辺 俊典; 古賀 久志
画像をフラクタル圧縮して得られるフラクタル符号の類似検索手法を検討している.この検索手法では,フラクタル符号をベクトル集合と見なし,ベクトル集合間の類似度を用いて検索を行う.ベクトル集合間の類似度計算コストは高く,検索時間に実用上の問題があったが,類似度の上限値を用いて類似度算出の対象数を削減する手法により大幅な改善を実現した.本稿では,この既報告の上限値を拡張し,部分集合に基づく新たな上限値設定法を提案する.この新たな上限値は,既提案の上限値を一般化したものであり,部分集合の取り方によって多様な上限値設定が可能となる.上限値設定法の詳細と,部分集合の扱いを説明した後,画像検索への適用結果を示す., 一般社団法人電子情報通信学会, 出版日 2004年09月03日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 104巻, 290号, 掲載ページ 145-150, 日本語, 0913-5685, 110003274084, AN10541106 - LI-010 フラクタル符号のベクトル集合間類似度に基づく画像検索手法(I. 画像認識・メディア理解)
横山 貴紀; 渡辺 俊典; 古賀 久志
FIT(電子情報通信学会・情報処理学会)運営委員会, 出版日 2004年08月20日, 情報科学技術レターズ, 3巻, 掲載ページ 191-192, 日本語, 110007634933, AA1197723X - Locality-Sensitive Hashing を利用した静止画像からのオブジェクト概念発見
古賀 久志; 渡辺 俊典
静止画像に対して、モデルを教示することなく、オブジェクト概念を発見する手法を提案する。本提案手法では、ユークリッド空間内で指定された点に対して最近点を見つける確率的近似アルゴリズムとして注目されているLocality-Sensitive Hashingを利用する。具体的には、まず、領域分割済みの画像の画素を対象としてLSHを適用し、近くの画素同士をクラスタにしてオブジェクトのコンポーネント(部品)として取り出す.次に、コンポーネントに対して、LSHを適用し、近いコンポーネント群をクラスタにしてオブジェクト概念の候補を抽出する。最後に、複数個出現したオプジェクト概念候補を有効なオプジェクト概念として発見する。本手法は、オブジェクト抽出時にコンポーネント間の厳密な位置関係を見ないので、回転、平行移動に対してロバストにオブジェクト概念を発見できる。, 一般社団法人電子情報通信学会, 出版日 2004年02月13日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 103巻, 659号, 掲載ページ 113-118, 日本語, 0913-5685, 110003273960, AN10541106 - Locality-Sensitive Hashing を用いた階層的クラスタ解析手法の近似解法
石橋 徹夫; 古賀 久志; 渡辺 俊典; 菅原 研
階層的クラスタ解析手法は類似度でデータを階層的に分類し、その結果は樹形図で表現することができる。この手法を用いると細かい分類から大まかな分類までクラスタ間の包含関係が理解しやすいが、計算量は大きなものとなるので、高次元・大規模データに対して適用することは難しい。本研究では階層的クラスタ解析の代表的なSingle-Link法に対して、高速な近似手法を提案する。本手法は最近接点の候補を高速に見つけるアルゴリズムであるLocality-Sensitive Hashing において作られるハッシュテーブルを用いることで計算量を減らす。実験の結果、提案手法が(1)Single Link 法と同じく楕円形以外のクラスタでも抽出できること、及び(2)高次元大規模データに対してSingle Link法より高速に動作することを確認した。, 一般社団法人電子情報通信学会, 出版日 2004年02月13日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 103巻, 659号, 掲載ページ 119-124, 日本語, 0913-5685, 110003273961, AN10541106 - 木のDPマッチングによるオブジェクト類似度の解析
小野里 卓也; 古賀 久志; 渡辺 俊典; 菅原 研
オブジェクト間の類似度を新たに提案する.オブジェクトの諸特性をノードとする属性木によってオブジェクトを表現する.次にOommenらの本のDPマッチング手法を用いて計算した2つの木の間の最小エディット距離を木の類似度とする.この類似度が距離公理を満たすことの証明を与え,簡単な例として文房具の類似度解析への応用を示す., 一般社団法人電子情報通信学会, 出版日 2004年02月13日, 電子情報通信学会技術研究報告. PRMU, パターン認識・メディア理解, 103巻, 659号, 掲載ページ 107-112, 日本語, 0913-5685, 110003273959, AN10541106 - 競合度によるオンラインアルゴリズムの解析
古賀 久志
一般社団法人電子情報通信学会, 出版日 2003年12月01日, 電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers, 86巻, 12号, 掲載ページ 972-974, 日本語, 0913-5693, 110003231136, AN1001339X - 画像からのオブジェクト記述の自動抽出
太田 貴彦; 杉内 崇浩; 渡辺 俊典; 菅原 研; 古賀 久志
近年オブジェクト認識は、セキュリティー認証、ロボットビジョンなどさまざまな場面で使われるようになってきた。我々は，画像オブジェクトをカラー画像の領域分割により直接得られる領域の集合と考えることにより、オブジェクト定義の自動抽出、認識手法について検討している。本稿では、オブジェクトの構成要素を検索する範囲を変動させることにより、効率的にオブジェクトの記述を抽出、認識する手法を提案する。In recent years, object recognition has come to be used in various, such as security authentication and robot vision. We are examining automatic extraction of an object definition, and the recognition technique by considering a picture object as a set of the domain directly obtained by domain division of a color picture. the technique which extracts and recognizes the description of an object efficiently by fluctuating the range in which the composition element of an object is searched is proposed in this paper., 一般社団法人情報処理学会, 出版日 2003年11月06日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2003巻, 109号, 掲載ページ 153-158, 日本語, 0919-6072, 110002664018, AA11131797 - 直交する2つの最小全域木（MST）を用いた画像特徴抽出可能性の検討
狩野 哲久; 渡辺 俊典; 古賀 久志; 菅原 研
陰影画像の画素をノードとし、ノード間の輝度値の差を枝の重みとした最小全域木(Minimum Spanning Tree：MST)は画像の領域分割手法として使われている。この場合、MSTは画像オブジェクトの陰影等高線に沿って走るが、ノード間の枝の重みを逆数にとったMSTを作成すると、MSTはオブジェクトの陰影勾配の方向に沿って走る傾向を持つ。本稿では、これら2つのMSTを併用した場合の画像領域特徴抽出の可能性を検討する。The minimum spanning tree of an undirected connected graph is known to be useful for image segmentation in the literatures, where pixels are regarded as nodes and the gaps between pixel values of two pixels are associated with the weights of edges. For gray-scale images, the MST traverses along the shade contour line of image objects. By contrast, if one constructs the MST in which the reciprocal of the gaps between pixel values is defined as the weight of an edge, it tends to traverse along the direction of the shade gradient of the image objects. This paper examines the possibility to extract the domain feature for images when these two types of MSTs are jointly used., 一般社団法人情報処理学会, 出版日 2003年11月06日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2003巻, 109号, 掲載ページ 49-55, 日本語, 0919-6072, 110002664005, AA11131797 - Locality - Sensitive Hashingを用いた階層的クラスタ解析手法の高速化
石橋 徹夫; 古賀 久志; 渡辺 俊典; 菅原 研
階層的クラスタ解析手法は類似度でデータを階層的に分類し、その結果は樹形図で表現することができる。この手法を用いると細かい分類から大まかな分類までクラスタ間の包含関係が理解しやすいが、計算量は大きなものとなるので、高次元・大規模データに対して適用することは難しい。そこで本研究では最近接点の候補を高速に見つけるアルゴリズムであるLocality-Sensitive Hashingによって作られるハッシュテーブルを用いて、計算量を減らし高速な近似階層的クラスタリングを実現する。The hierarchical clustering techniques classify data by similarity and their results are represented by dendrogram. Although the hierarchical clustering makes it easy to understand both the fine and coarse inclusive relations between clusters, it cannot be used for the high-dimension case or for large-scale data because of its large time complexity. This paper realizes a fast approximated hierarchical clustering method with small time complexity which utilizes the hash table made by Locality-Sensitive Hashing that is an algorithm for finding the candidates of the nearest neighbor points., 一般社団法人情報処理学会, 出版日 2003年11月06日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2003巻, 109号, 掲載ページ 57-62, 日本語, 0919-6072, 110002664006, AA11131797 - MSTを用いたアピアランスベース3D物体認識手法の画像スケール変換下での性能分析
平橋 慶一; 渡辺 俊典; 古賀 久志; 菅原 研
我々は画像の最小全域木(MST)の特徴を用いたアピアランスベース3Dオブジェクト認識手法の研究を行っている。画像の局所および全体からこの特徴を抽出して利用する。得られた特徴ベクトルを階層的な最小包囲直方体(MBR)に集約し、それらの間の類似度を定義する。本方式の概要と画像スケール変換の下での性能分析結果を報告する。We are standing a 3D object recognition scheme using the features of the minimum spanning tree (MST) of the image. We use both the local and global features of the image. We aggregate extracted feature vectors into a hierarchical minimum bounding rectangle (MBR) and define a similarity measure between them. Overview of the scheme and it's performance under image scale changes are reported., 一般社団法人情報処理学会, 出版日 2003年11月06日, 情報処理学会研究報告コンピュータビジョンとイメージメディア（CVIM）, 2003巻, 109号, 掲載ページ 145-151, 日本語, 0919-6072, 110002664017, AA11131797 - パケット損失を防止するスケジューリングアルゴリズム
古賀 久志
現在のネットワーク通信におけるパケットロスはルータでバッファが足りなくなるのが原因である。本稿では、ルータでオンラインスケジューラが m 本のキューからパケットをスケジューリングする際に、どれだけバッファがあればパケットロスを防げるかを調べる。少ないバッファ量でパケットロスを防ぐには最大キュー長を小さく抑える必要があり、この新しい問題を我々はBalanced Scheduling Problem (BSP) と名付けた。 BSPは タスクが負のコストを持つことを許す新しい負荷分散問題である。オンラインスケジューリングアルゴリズムの評価は、パケットロスを起こさない最適オフラインアルゴリズムの何倍のバッファがあればパケットロスが起きないかという競合比を使って行った。その結果、(1)いかなる決定的／確率的アルゴリズムも Omega(log m)-competitive より良くない、(2) GREEDYアルゴリズムは O(log m)-competitive を達成し、ほぼ最適となるという結果を得た。Packet losses in the current best-effort networks take place because of buffer shortage in a router. This paper investigates how many buffers should be prepared in a router enough to eliminate packet losses in the context that an on-line scheduling algorithm in the router must decide the order of transmitting packets among m queues each of which corresponds to a single traffic stream. To exclude packet losses with a small amount of buffers, the maximum queue length must be kept low. This new problem is named the balanced scheduling problem (BSP). By competitive analysis, we judge the power of on-line algorithms from how many times the on-line algorithms must prepare as many buffers as the loss-free off-line algorithm to guarantee no packet loss. The BSP is a new on-line load balancing problem which accompanies tasks with negative loads. To solve an on-line problem which admits tasks to have negative costs is our main theoretical contribution. Speicifically we show that no deterministic/randomized on-line algorithm is better than Omega(log m)-competitive. Then we prove a simple greedy algorithm is Theta(log m)-competitive and nearly optimal., 一般社団法人情報処理学会, 出版日 2001年07月27日, 情報処理学会研究報告アルゴリズム（AL）, 2001巻, 79号, 掲載ページ 37-44, 日本語, 0919-6072, 110002812446, AN1009593X - 広域並列分散システムにおける通信特性の評価
水野 裕識; 古賀 久志; 陣崎 明
従来、インターネット通信は通信処理オーバヘッド、伝送距離による遅延が存在するため、並列計算のように高帯域、低遅延を必要とするアプリケーションには向かないと考えられてきた。しかしながら、インターネット伝送速度が向上し、通信プロトコルの高速処理技術が進展している現在、インターネット技術を基盤とした並列分散システムの構築可能性を検討することは重要である。そこで、ATMによる広域インターネットにおいてNAS Parallel Benchmark(NPB)を実行し、通信パターンの観測と並列計算の性能評価を行った。その結果、1)並列計算アルゴリズムによっては有効な結果を得る場合があること、2)広域網の通信品質に問題はないが、性能は帯域や遅延に大きな影響を受けること、3)現在のNPBをそのまま利用する限り台数効果(スケーラビリティ)が制限されることがわかった。, 一般社団法人電子情報通信学会, 出版日 2000年08月27日, 電子情報通信学会技術研究報告. CPSY, コンピュータシステム, 100巻, 249号, 掲載ページ 17-24, 日本語, 0913-5685, 110003180563, AN10013141 - 遅延を考慮したジッタレギュレータの解析
古賀 久志
マルチメディアデータをネットワーク経由で配送して円滑に再生するには個々のパケットの遅延のゆらぎ（ジッタ）を抑えることが大切である。本稿では、配送経路途中にあるルータにおいて、パケットをバッファリングすることによりジッタを吸収するオンラインアルゴリズムを取り扱う。従来研究ではルータ内のバッファ数のみに着目してアルゴリズムを解析していた。本稿ではそれに加えて、通信のリアルタイム性を考慮し、ルータ内にパケットを保持できる時間に上限があるという条件を新規に導入して解析を行った。その結果、オンラインアルゴリズムのcompetitivenessはバッファ数よりもむしろルータ内のパケット存在時間に依存するという結果を得た。また、我々が提案したオンラインアルゴリズムがジッタをどれだけ定量的に吸収するかについても考察を与えた。In order to playback multimedia data smoothly, it is important to keep the jitter, the variability of delay of individual packets, low. This paper examines on-line algorithms in a single router on the distribution path for a given multimedia stream which attempt to regulate jitter by holding packets in an internal buffer. The previous work solved the problem with focusing only on the buffer size in the router. However, for the purpose of providing the stream communication with real-time property, this paper introduces the new condition that a packet can stay in the router at most for a constant time which we name the permitted delay time into the problem besides the conventional constraint about the buffer size. Our analysis of this new version of the problem obtains the result that the competitiveness of on-line algorithms depends on the permitted delay time rather than the buffer size. Finally we investigate quantitatively how much jitter is removed by our on-line algorithm., 一般社団法人情報処理学会, 出版日 2000年03月21日, 情報処理学会研究報告アルゴリズム（AL）, 2000巻, 31号, 掲載ページ 1-8, 日本語, 0919-6072, 110002812378, AN1009593X - 広域並列分散システムのための信頼できるマルチキャスト
下國 治; 古賀 久志; 陣崎 明
数千台の計算機がインターネット経由で接続された広域並列分散システムにおいて、信頼性のあるマルチキャスト(Reliable Multicast)通信を利用して一対多通信機構を実現することを検討する。パケットロス時にパケット配布元から再送するリカバリー時間を短縮するため、配送経路途中にあるルータから再送することを考えた。経路のすべてのルータに再送可能な機構を持たせるのはコストがかかるので、再送の効果が大きな箇所に優先的に再送可能なルータを配置し、再送の効果が大きな箇所とはどのような特性を持つのか、実際のネットワークを基にした通信モデル上で検討した。検討の結果、バックボーンネットワークとローカルネットワークの境界にあるルータにだけ再送させれば十分な効果が得られるとの結論を得た。In this paper, we discusses multicast implementations on wide area parallel and distributed systems which connect large number of computers through the Internet by reliable multicast communication. Since packet retransmisson from the original sender lead to large recovery time, we investigate an approach in which the retransmission is made by intermediate routers on the multicast routes. It would need noticeable cost, if all routers had retransmission ability. Therefore, it is important to place those routers only on effective location. We study characteristics of the effective location on the multicast routings. We examine the above approach on our communication model which reflects the characteristics of the actual networks. And we obtain the result that it is enough to locate routers supporting packet retransmission only on the boundaries between the backbone network and the local area networks., 一般社団法人情報処理学会, 出版日 2000年03月02日, 情報処理学会研究報告ハイパフォーマンスコンピューティング（HPC）, 2000巻, 23号, 掲載ページ 53-58, 日本語, 110004059338, AN10463942 - インターネットでの並列分散処理の方式検討
下國 治; 古賀 久志; 新家 正総; 河合 純; 小林 伸治; 水野 裕識; 陣崎 明; 中村 修; 村井 純
世界中に分散した計算機を、Gbps程度の速度を持つインターネットで接続し、大規模な並列分散システムを構築することを考える。数万台の計算機にパケットを送信する際に、UnicastのTCPでは通信コストが線形に増し、また、MulticastではUDP通信しか一般に行われていないので、通信の信頼性が得られないという問題が生じる。近年、通信の保証を行うMulticast通信(ReliabIe Multicast)通信方式がいくつか提案されている。それらの方式を基に、本稿では特に到達確認、再配布機構に関して並列分散計算に適した方式を議論する。考察の結果、ルータの処理の単純さを保ちつつ、到達確認情報の統合と再配布範囲の制限をルータで行わせる方式が好ましいとの結論を得た。, 一般社団法人電子情報通信学会, 出版日 1999年08月05日, 電子情報通信学会技術研究報告. CPSY, コンピュータシステム, 99巻, 252号, 掲載ページ 43-48, 日本語, 0913-5685, 110003180504, AN10013141 - インターネットでの並列分散処理の実装検討
古賀 久志; 下國 治; 新家 正総; 河合 純; 小林 伸治; 水野 裕識; 陣崎 明
並列計算にはバリア同期、DMSにおけるページ共有などマルチキャストを使うと効率の良い処理が多いが、広域並列分散環境で従来のIP multicastを使うのは信頼性の点で問題がある。最近、信頼性のあるマルチキャストとしてreliable multicast技術が提案されており、それを使用する事を検討する。本論文では、まず並列分散処理向けのreliable multicastの持つべき性質を紹介し、それをベースに実際的なプロトコルを設計する。このプロトコルではACKパケットの統合、無駄な再送の抑制を主にルータでのテーブル管理、探索で実現する。本プロトコルを我々が開発中のネットワークサーバシステムcometで動作させると、1パケットあたり200nsの遅延で処理できるという予測が得られた。, 一般社団法人電子情報通信学会, 出版日 1999年08月05日, 電子情報通信学会技術研究報告. CPSY, コンピュータシステム, 99巻, 252号, 掲載ページ 49-54, 日本語, 0913-5685, 110003180505, AN10013141 - Comet によるIEEE1394を利用した計算機ネットワークの構築
古賀 久志; 陣崎 明
Cometを接続して並列ネットワークサーバを構築するための高速ネットワークとして、我々はIEEE1394に注目している。一方で、IEEE1394は125μ秒毎にデータを遅延なく届けるQoS機能を持つ。今回、Cometのプロトコル処理性能の評価を目的としてIEEE1394同期パケットをIPカプセル化してEthernetとゲートウェイするシステムを構築した(IEEE1394/IP)。従来のネットワーク処理では割り込みオーバーヘッド等で上記プロトコル変換を125μ秒単位で行えないが、Cometではネットワークアダプタにプロトコル処理をオフロードすることにより約40μ秒で1パケットを処理する。IEEE1394/IPを用いて、WIDEバックボーンでのビデオストリーム中継実験および最新ルータで生じるジッタの定量測定を行った。その結果、(1)Cometのみで構成されるネットワークでは125μ秒のパケット間隔を維持できるのに対し、(2)最新の商用ルータでもジッタが2倍(250μ秒)に膨らむ、ことが確認された。, 一般社団法人電子情報通信学会, 出版日 1998年08月05日, 電子情報通信学会技術研究報告. CPSY, コンピュータシステム, 98巻, 234号, 掲載ページ 35-40, 日本語, 110003180269, AN10013141 - Tight Bound on the Competitive Ratio for the Page Replication Problem
アルベルス スザンヌ; 古賀 久志
京都大学, 出版日 1994年05月, 数理解析研究所講究録, 871巻, 掲載ページ 182-189, 英語, 1880-2818, 110004774703, AN00061013 - 分散共有メモリに対するオンラインアルゴリズム
古賀 久志
ローカルメモリを持った複数のプロセッサーからなる分散共有メモリシステムにおいては、各ページはメモリアクセス要求列に対してコストが低くなるように、適宜移動または複写されて適当なプロセッサーに配置される必要がある。本研究では、こうした低いコストのページ配置を実現するオンラインアルゴリズムをコンペティティブ比（最適オフラインアルゴリズムとのコスト比）の面から考える。特に本研究では、ページ移動問題に対しての確率的アルゴリズムをページ複写問題用に改良して木やリングのネットワークに対して既存の決定的アルゴリズムよりコンペティティブ比の面で強い結果が得た。In distributed shared memory system consisting of multiple processor s, each of which has its own local memory, each page needs to be located at a proper processor by migration or replication so at to make the total cost for memory-access lower. In this paper, on-line algorithms attempting to implement this low-cost locating are considered in terms of competitiveness, the ratio of the cost of the on-line algorithms to that of the off-line optimal algorithm. Especially in this paper, we show that the application of algorithms base on randomized algorithms for page migration problem to page replication problem can acquire more powerful result than existing deterministic algorithms about competitive ratio., 一般社団法人情報処理学会, 出版日 1993年05月28日, 情報処理学会研究報告アルゴリズム（AL）, 1993巻, 48号, 掲載ページ 49-55, 日本語, 0919-6072, 110002812074, AN1009593X
共同研究・競争的資金等の研究課題
- 動的に変わる集合に対する類似検索のスケッチを利用した高速化
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本研究課題はデータストリームを対象とする類似検索を取り扱う。その具体的な応用としては、嗜好性が似たユーザの発見が挙げられる。例えば、閲覧したウェブニュース記事の集合が互いに似た2ユーザは、興味がある事柄が似ており、嗜好性が似ていると言える。このようにして、類似ユーザ検索を集合間類似検索に帰着できる。 要素が固定した通常の集合に対しては、Min Hashというハッシュ関数を利用して集合の要約(スケッチ）を事前生成し、スケッチ間で軽量に類似度計算することで、類似検索を高速化できる。しかし、ストリーム環境では新しい要素の追加と古い要素の消滅が起きるため、スケッチを高速更新する必要がある。そこで本研究では、ストリーム環境で集合の要素が入れ替わる状況で、Min Hashを高速計算するアルゴリズムの開発に取り組んだ。 そして2021年度は、多重集合を取り扱えなかったDatarらの既存手法を、多重集合が取り扱えるよう拡張することに成功した。ここで、多重集合とは同じラベルの要素を複数持てる集合のことである。Min Hashは集合の各要素に確率的に値を割り当て、その最小値をハッシュ値とする。既存手法では将来的に最小値になりえない要素を削除して、ハッシュ値再計算のオーバーヘッドを削減している。しかし、多重集合の場合、要素への割り当て値が多重度に依存して動的に変わるため将来的に最小値になりえるかの判定が困難になる。我々の提案手法は、この厳しい条件下で、将来的に最小値にならない要素を判別する。さらに同一ラベルの要素を、提案手法が高々１つだけ保持すればよいことも示せた。集合の要素数をWとすると、提案手法の計算時間は実験的にlog Wに比例し、O(W)かかるベースライン手法より圧倒的に高速に動作することを確認できた。, 21K11901
研究期間 2021年04月 - 2026年03月 - Fast Concept Drift Detection Exploiting Product Quantization
丸文財団, 海外渡航助成
研究期間 2024年07月 - 2024年08月 - Continuous Similarity Search for Text Sets
丸文財団, 海外渡航助成, 研究室学生の海外渡航費用の助成
研究期間 2022年08月 - 2022年09月 - 時間と共に変化する集合を対象とした類似検索
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 今年度は、時間に共に変化する集合を対象とする類似検索に関し、次の2種類の問題設定に取り組んだ。 (1)従来研究ではクエリ集合のみが時間と共に変化し、データベース内の集合は時間に依存しない問題設定を取り扱っていたが、本研究ではクエリ集合が固定でデータベース内の集合が時間と共に変化する問題を取り扱った。この問題設定では、データベース内の集合が変化するため、データベースを転置リストのような静的なインデックス構造を用いて管理することは困難である。そこで、インデックスに頼らずに、類似度の計算回数を削減することで類似検索を高速化する要素技術を実現した。類似度の上限値を軽量に推定し、その値が小さい場合には、類似集合である可能性がないので、類似度計算を省略するのが基本アイデアである。とくに、集合から消失するデータは既知であるという性質を利用し、類似度の上限値をより厳密に求め、類似度計算を省略する頻度を増やすことに成功した。 (2)クエリ集合のみが時間に依って変化する状況において、集合の要素が文字ラベルではなく、多次元データである問題を取り扱った。一般的には、集合は文字ラベルを要素として持つ。しかし、文字ラベルを要素とする集合では表現が困難な問題が現実には多く存在する。例えば、twitterにおいて、ユーザをtweetの集合により特徴付けしようとすると、個々のtweetを文字ラベルで表現するのは適切ではなく、位置情報を持つ単語ベクトルとして表現する方が自然である。このような問題設定において、類似度の上限値が小さい時に類似度計算を省略するアルゴリズムを考案した。, 18K11311
研究期間 2018年04月01日 - 2021年03月31日 - 辞書の類似性に着目した圧縮率ベース特徴空間の最適な構築方法の探求
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 圧縮ベースパターン認識は分析対象に対する事前知識なしに、データ分析を実現する非教示データ分析技術である。その基本は、データ間の類似性を圧縮率から測定することである。とくに本研究では、SVMやk-meansなど既存パターン認識技術を活用するため、データを圧縮率を並べたベクトルとして表現する圧縮率特徴空間を考え、その適切な空間の構築法をテーマとした。そして、特徴空間の軸を定義する圧縮辞書の単語を入れ替えて、軸間の独立性を高めることにより既存手法よりもパターン認識精度を7～8％向上することに成功した。, 15K00148
研究期間 2015年04月01日 - 2019年03月31日 - 構造を持つデータの構造情報ダイジェストを利用した類似検索の高速化
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本研究では、グラフのような構造情報を持つデータを対象とする類似検索問題に取り組んだ。構造を持つデータは複雑度が高く、類似度計算のオーバーヘッドが問題になる。そこで、構造情報を要約する簡潔なデータ構造（ダイジェスト）を導入し、ダイジェストを比較することで、類似検索を高速化する。ここで、検索精度は構造情報をどう要約するかに依存する。本研究では、部分構造同士が似ているという情報をダイジェストに反映させることで、高精度な類似検索を実現した。 また、構造を持つデータに対する類似検索の応用技術として、構造ベースの画像処理についても研究した。, 24500111
研究期間 2012年04月01日 - 2016年03月31日 - 圧縮原理を用いた認識スキームの自律形成手法の研究
渡辺 俊典; 古賀 久志; 張 諾
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 認識対象オブジェクトの統計的モデルを人手で構築した後、モデルと未知対象との統計的類似度を計算してオブジェクトを認識する伝統的方式では、テキスト、音、画像など種々のデータ型や多様な内容オブジェクトへの対応は困難である。本研究では、多様なデータ型を圧縮率特徴ベクトルで汎用的に表現する方式と、認識された下位オブジェクトの共起性から上位オブジェクトを自動発見する方式の可能性、および両者を統合した高度に自律的な認識機構の可能性を探求した。画像を用いた実験でこれらについての肯定的な結果を得た。, 22500122
研究期間 2010年 - 2012年 - 外部からの入力との相互作用を考慮したアルゴリズムの設計
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 複数の計算機が相互作用する環境で発生する2つの問題を取り上げ、効率的に問題を解決するアルゴリズムの設計を行った。まず、インターネットにおいて、複数のTCPコネクション間の転送速度の公平性を改善するアルゴリズムを開発した。このアルゴリズムはルータへの修正を必要とせず、ユーザが持つ計算機のOSを置換するだけで実現できる。次に、複数計算機で構成される分散データベースにおける類似検索に取り組み、既存の単純な実装法より10%程度応答時間を短縮するアルゴリズムを開発した。, 21500008
研究期間 2009年 - 2011年 - 圧縮空間を用いたマルチメディアデータマイニングとそのウェブマイニングへの応用
渡邊 俊典; 古賀 久志; 張 諾; 横山 貴紀
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), インターネットや携帯電話の発展の中で文章、音声、画像などのマルチメディアデータが爆発的に増大している。本研究では、人手介入なしに、計算機によってこれらを分類あるいは検索する方式を検討した。我々が過去検討してきた、圧縮率によるテキストの特徴表現方式を原理としつつ、より高性能な圧縮性特徴空間の構成可能性の検討、文書や画像分類への適用などを試みた。文法知識を事前準備せずに、文章や画像に適用できること、従来方式をしのぐ性能も発揮できることなどを確認できた。なお、EUでの衛星画像利用地球環境管理国際プロジェクト(GEOSS)関係機関より招待され、衛星画像処理への応用可能性について講演も実施した。, 19500076
研究期間 2007年 - 2009年 - スケジューリング理論に基くネットワーク通信品質保証技術の設計に関する研究
古賀 久志
日本学術振興会, 科学研究費助成事業 若手研究(B), 電気通信大学, 若手研究(B), 本年度は、まずTCPのack回数と通信品質(遅延)との関係を昨年度に提案したスライディングウィンドウ機構を考慮した理論モデル上でより厳密に解析を行い、受信者が送信者側の輻輳ウィンドウサイズを知ることができればack頻度を増やさずに遅延の増大を抑えられることを示した。現状のTCPでは輻輳ウィンドウサイズを受信者が知らないので、この点を改良することで性能向上が期待できる。 本結果は国際会議lnternational Workshop on Algorithm and Data Structuresにおいて採択された。また、海外雑誌への論文投稿も完了し、査読中である。 次に、高速トランスポート層プロトコルの公平性に関する研究を実施した。高速トランスポートプロトコルは長距離広帯域ネットワークを効率的に使う目的で開発されたが、異なる種類の高速トランスポート層プロトコルが競合する環境を想定して設計されていない。この結果、aggressiveな高速プロトコルがmoderateな高速プロトコルと競合すると、後者は高速プロトコルであるにもかかわらず低いスループットしか出せないという問題があ。本研究では一番aggressiveな高速プロトコルとして知られているUDTに着目し、UDTをmoderateに改良したmUDTというプロトコルを提案した。mUDTの特徴は、RTTの増加により他のコネクションと競合しているかを検知し、競合発生時のみ送信レート増加を遅くする点である。これにより空き帯域を短時間で埋めるというUDTの長所を残しつつ、他のプロトコルとの公平性を増加させることに成功した。本成果を電子情報通信学会情報ネットワーク研究会で発表した。 また、モバイルアドホックネットワークにおける通信の省電力化に着目し、特に端末に指向性アンテナが装備された環境で、指向性・非指向性の切り替えと送信パワーコントロールをどうスケジューリングすれば、通信性能を劣化させずに省電力化を実現できるかいう研究に取り組んだ。評価にqualnetを使用したが、外部発表できるだけのまとまった成果は得られていない。, 17700054
研究期間 2005年 - 2007年 - 画像オブジェクト定義の自動抽出機構に関する研究
渡邊 俊典; 古賀 久志; 横山 貴紀
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 画像内オブジェクトの自動モデリング機能の実現を目標とし、下記を実施した。 1.静止画像内オブジェクトモデルの獲得方式 (1)画像をより圧縮することができる領域部分集合の自動探索機構に加え、見出した部分集合の密度などで定義されるオブジェクトらしさの尺度を加えることで、自動モデリング性能を高めることができた。 (2)領域色削減機能を付加することで、人工ポンチ絵、動物や人の顔、プラモデルなどの自然画像も処理できることを確認した (3)歩行者を含む動画(ビデオ)の合い続く複数フレームをマージした静止画像に適用し、頭髪、顔、手、胴と足を要素とするオブジェクト(人)のモデルを自動抽出できた。 2.画像(ビデオ)内のオブジェクトモデルの自動獲得方式 (1)単独の動作オブジェクトが出現するビデオを対象とし、背景差分法によるオブジェクト切り出し、オブジェクト輪郭線の特徴量ベクトル化、投票機構によるベクトル時系列の新規性判定と新規物の自動保存、などを特徴とする動作オブジェクト自動抽出システムを実現した。 (2)歩く、お辞儀する、手を上げてとまる、など8種類の人物動作が出現する連続ビデオを提示するのみで、これらの認識能力を自動獲得し、継続ビデオ内の類似動作を自動認識する能力を確認した。 (3)大学研究室の日常生活を撮影したビデオから、人の動作モデルの自動抽出と、それを用いた認識能力が実現できることを確認した。 (4)処理性能は、オンライン・リアルタイムの高速性をもつことを確認した。 3.上記(2)の発展として、次の成果を得た (1)上記(2)は、MPEGなどの圧縮ビデオデータの解凍を必要とするため、応分の手間と記憶が必要となる。対策としてMPEGなどの圧縮データのままで画像内動作オブジェクトの解析を可能化する手法を検討し、歩行する単独人物、逆方向にすれ違う二人の人物の追跡などが可能な手法を実現した。 4.研究発表と報告書作成 (1)期間内で3件の成果発表をおこなった。内訳は、ジャーナル論文1、研究会発表2。 (2)上記の成果を報告書としてまとめた。, 17500061
研究期間 2005年 - 2006年
学術貢献活動
- 国際会議 IJCNN 2025 (International Joint Conference on Neural Networks ) Reviewer
審査・評価, International Neural Network Society, 実施期間 2025年02月02日 - 2025年03月05日 - DEIM2025 コメンテータ
パネル司会・セッションチェア等, 日本データベース学会, 実施期間 2024年12月 - 2025年03月 - CANDAR2024 プログラム委員
学会・研究会等, 審査・評価, 実施期間 2024年08月01日 - 2024年12月29日 - DEIM2024コメンテータ
学会・研究会等, パネル司会・セッションチェア等, 日本データベース学会, 実施期間 2023年12月 - 2024年04月 - CANDAR2023 プログラム委員
大会・シンポジウム等, 審査・評価, 実施期間 2023年08月 - 2023年12月
