hisashi koga
| Department of Computer and Network Engineering | Associate Professor |
| Cluster I (Informatics and Computer Engineering) | Associate Professor |
Researcher Information
Educational Background
Research Activity Information
Award
- Sep. 2024
コンセプトドリフトが想定される環境でのオンラインK-medoidsクラスタリングの代表データ選択
第23回情報科学技術フォーラム FIT奨励賞, 田山凜太郎(修士の指導学生) - Sep. 2024
類似軌跡探索における高速かつ高精度なスケッチ間類似度
第23回情報科学技術フォーラム FIT奨励賞, 河野大督(修士の指導学生) - Sep. 2022
画像の追加を許容するDeep Hashingに基づく類似画像検索
第21回情報科学技術フォーラム(FIT2022)FIT奨励賞, Ye Chenyang(修士の指導学生)
Japan society - Sep. 2019
双対グラフを用いたグラフの分散表現学習
第18回情報科学技術フォーラム(FIT2019)FIT奨励賞
Japan society - Sep. 2019
ストリーム環境での位置情報を持つテキスト集合に対する類似検索
第18回情報科学技術フォーラム(FIT2019)FIT奨励賞
Japan society - Sep. 2017
多観点類似度を用いた凝集型階層クラスタリング
第16回情報科学技術フォーラム(FIT2017)FIT奨励賞
Japan society
Paper
- Fast Concept Drift Detection Exploiting Product Quantization
Taisei Takano; Hisashi Koga
Corresponding, Proc. 35th International Conference on Database and Expert Systems Applications(DEXA 2024), Springer LNCS, Springer Nature Switzerland, 14911, 257-271, 17 Aug. 2024, Peer-reviwed
International conference proceedings, English - 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, Oct. 2023, Peer-reviwed
International conference proceedings - Continuous Similarity Search for Dynamic Text Streams
Y. TSUCHIDA; K. KUBO; H. KOGA
Corresponding, IEICE TRANSACTIONS on Information and Systems, E106-D, 12, Sep. 2023, Peer-reviwed
Scientific journal, English - 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, Jun. 2023, Peer-reviwed
International conference proceedings - IDTWを用いた個別銘柄を対象とした株価予測
中尾友紀,古賀久志
情報処理学会論文誌, Vol. 63, 9, 1512-1517, 15 Sep. 2022, Peer-reviwed, False
Scientific journal, Japanese - 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, Sep. 2022, Peer-reviwed, True
International conference proceedings, English - Editing Compression Dictionaries toward Refined Compression-Based Feature-Space
H. Koga, S. Ouchi and Y. Nakajima
Information, MDPI, 13, 6, 301, 15 Jun. 2022, Peer-reviwed, True
Scientific journal, English - 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, May 2022, Peer-reviwed, False
Scientific journal, English - 多観点類似度を用いた凝集型階層クラスタリング
藤原 勇二,古賀久志
情報処理学会論文誌, Vol. 62, 3, 936-945, Mar. 2021, Peer-reviwed, False
Scientific journal, Japanese - 非教示なグラフ分散表現のエッジ特徴による改良
陳 宏,古賀久志
情報処理学会論文誌, Vol. 62, 1, 357-368, Jan. 2021, Peer-reviwed, False
Scientific journal, Japanese - 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, Peer-reviwed
International conference proceedings - A New Parametric Spanning Tree Generation for Network Topology Design
大家 万明; 渡辺 俊典; 古賀 久志
情報処理学会論文誌数理モデル化と応用（TOM）, 9, 2, 9-19, 10 Aug. 2016, Peer-reviwed, False
Scientific journal, Japanese - 時系列圧縮性によるポリシー指向ネットワークモニタリング
大関 潮,古賀 久志,渡辺 俊典
電子情報通信学会論文誌, Vol.J98-A, 4, 357-368, 01 Apr. 2015, Peer-reviwed, False
Scientific journal, Japanese - 滑り現象の映像解析による地震動の推定
横田 有光, 浜本 隆之, 古賀 久志, 渡辺 俊典
土木学会論文集F3(土木情報学), 70, 1, 29-39, Oct. 2014, Peer-reviwed, False
Scientific journal, Japanese - 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, Apr. 2012, True
International conference proceedings, English - 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, Feb. 2012, Peer-reviwed, True
International conference proceedings, English - 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, Sep. 2010, Peer-reviwed, True
International conference proceedings, English - A New AQM Algorithm Exploiting Passive RTT Estimation
星原 隼人; 古賀 久志; 渡辺 俊典
情報処理学会論文誌, 51, 2, 466-477, 15 Feb. 2010, Peer-reviwed, 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.
Japanese - 頻出グラフマイニングを利用した動画像解析
辻 智和; 古賀久志; 横山貴紀; 渡辺俊典
情報処理学会論文誌, 51, 2, 466-477, Feb. 2010, Peer-reviwed
Scientific journal - 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, Oct. 2009, Peer-reviwed, True
International conference proceedings, English - Dynamic TCP Acknowledgment with Sliding Window.
Hisashi Koga
Theoretical Computer Science, 410, 914-925, Feb. 2009, Peer-reviwed, True
Scientific journal, English - 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, Jan. 2009, Peer-reviwed, True
International conference proceedings, English - Motion Object Detection and Tracking Using MPEG Motion Vectors in the Compressed Domain
IWASAKI Toshiki; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
The IEICE transactions on information and systems, The Institute of Electronics, Information and Communication Engineers, 91, 6, 1592-1603, 01 Jun. 2008, Peer-reviwed, MPEGビデオ符号化では,圧縮するために動き補償を用いており,フレーム間における各領域の動き情報を動きベクトルとして生成する.この動きベクトルは動画像解析に役立つ情報と考えられるが,符号化効率を向上させるために生成されるものであり,必ずしも移動物体に沿って発生するものではなく,多くのノイズ的なベクトルも生成するという問題点がある.また,動きベクトルを用いた既存手法の多くでは,移動物体の停止や交差によって動きベクトルが失われるフレームに対して適用することが困難である.本論文では,MPEGビデオデータの動きベクトルから直接得られる特徴画像を用いた,移動物体の検出と追跡手法を提案する.特徴画像は移動領域を記録し,移動物体が停止していると考えられる領域を次フレーム以降も蓄積する.この履歴特性をもつ領域の特徴画像を用いることにより,移動物体が静止した場合やピクチャタイプなどによって動きベクトルが出現しない場合でも,移動物体の検出と追跡が可能となる.MPEG-4カメラで撮影した動画像を用いて実験を行い,提案手法の有効性を示す.
Scientific journal, Japanese - Automatic Extraction of Objects out of Images Using Neighbor Set Representation
KOGA Hisashi; SUGIYAMA Hideyuki; SUGIUCHI Takahiro; WATANABE Toshinori; YOKOYAMA Takanori
The IEICE transactions on information and systems, The Institute of Electronics, Information and Communication Engineers, 91, 5, 1418-1433, 01 May 2008, Peer-reviwed, 少数の画像を与えるだけで人手を介さずにオブジェクトを自動抽出する方式を提案する.その基礎として,まず,オブジェクトの部品位置が種々に変化し得る場合でも,同種類のオブジェクトを簡単に認識するためのデータ構造である近傍集合表現を述べる.提案するオブジェクト自動抽出アルゴリズムは,与えられた画像内からいくつかオブジェクト候補を作成し,オブジェクト候補と同種類のオブジェクトを近傍集合表現を利用して抽出する.オブジェクト抽出の良否は,画像内により多く出現しより多くの部品からなるものがオブジェクトとして妥当であるとの直感を画像表現に要するデータ量の圧縮度という評価関数に定式化して計算する.そして,オブジェクト候補を変えてオブジェクト抽出を繰り返し試行し,評価関数値が最大となった場合を,最終的なオブジェクト抽出結果として返す.静止画像と動画像とを用いた実験によって提案の有効性を示す.
Japanese - Motion-Blurred Image Restoration Method Using a Super-Resolution Process
MUTA Keisuke; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
The IEICE transactions on information and systems, The Institute of Electronics, Information and Communication Engineers, 90, 6, 1532-1541, 01 Jun. 2007, Peer-reviwed, 移動する被写体をカメラで撮影する場合,被写体像がシャッターの開口時間に応じ移動方向へ多重に露光されるため,撮影画像は静止被写体像に比べて劣化する.そのため,撮影画像からプレの影響を取り除き,静止被写体像を復元するプレ画像修復処理が重要となる.しかし,プレ画像の修復処理とは,移動方向について減衰された被写体像の高周波成分を増幅する処理であるため,画像に含まれる雑音成分まで強調してしまうという問題点がある.本論文では,超解像処理手法を用いたプレ画像修復手法を提案する.複数枚のプレ画像を用いることで雑音を抑制することができ,また入力画像がもつ解像度以上の被写体像の復元も可能となる.各種実験を行い,提案手法の有効性を確認した.
Scientific journal, Japanese - Fast agglomerative hierarchical clustering algorithm using Locality-Sensitive Hashing
Hisashi Koga, Tetsuo Ishibashi and Toshinori Watanabe
Knowledge and Information Systems, 12, 1, 25-53, May 2007, Peer-reviwed, True
Scientific journal, English - A New Similarity Measure between Trees by Decomposition of Unit-cost Edit Distance
H. Koga, H. Saito, T. Watanabe and Y. Yokoyama
Lead, Proc. 8th International Conference on Intelligent Data Engineering and Automated Learning (IDEAL’07), springer LNCS, Vol. 4881, 643-652, 2007, Peer-reviwed, True
International conference proceedings, English - A Novel Document Analysis Method Using Compressibility Vector
N. Zhang, T. Watanabe, D. Matsuzaki and H. Koga
Proc 1st International Symposium on Data, Privacy, & E-Commerce (ISDPE'07), IEEE Compuiter Society, 38-40, 2007, Peer-reviwed, True
International conference proceedings, English - Voting-Based Online Realtime Learning and Recognition of Motion Objects
YOSHIOKA Taichi; WATANABE Toshinori; KOGA Hisashi; YOKOYAMA Takanori
The IEICE transactions on information and systems, The Institute of Electronics, Information and Communication Engineers, 90, 1, 83-93, 01 Jan. 2007, ビデオの内容を自動認識する技術は,監視,圧縮,要約など応用範囲が広い.認識対象を想定してそのモデルを人手や学習によって事前準備しておくというのが伝統的画像認識手法であるが,事前に想定できない多様な内容を含み,かつデータ量も膨大なビデオには十分対応できない.対策として,事前のモデル設定なしにビデオを観測しながらモデルの獲得と認識とを行う機構が望まれる.更にリプレイ時間や記憶のコストを削減するためにはワンパスで実時間性を備えたオンラインリアルタイム処理が理想である.本論文では,このような機能を備えたビデオ内動作オブジェクト自動認識システムを提案する.人の行動を撮影したビデオのみを与えて,歩く,座る,などの基本動作の獲得と認識とが完全自動で行えることを示す.
Scientific journal, Japanese - 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, Peer-reviwed, True
International conference proceedings, English - Hierarchical Clustering Algorithm Using Locality-Sensitive Hashing
ISHIBASHI Tetsuo; KOGA Hisashi; WATANABE Toshinori
The transactions of the Institute of Electronics, Information and Communication Engineers. D-I, The Institute of Electronics, Information and Communication Engineers, 88, 4, 852-863, 01 Apr. 2005, Peer-reviwed, 階層的クラスタ分析は, 各データを一つのクラスタとみなし, 最も近いクラスタ同士を結合していき, 最終的に全データが一つのクラスタに含まれるまで結合を繰り返すという手法である.結合過程を樹形図で表現することで各クラスタ間の距離や包含関係が理解しやすく, 外的基準を必要としない教師なし自動分類であるため, 未知のデータ集合に対して有効である.しかし, データサイズnに対してO(n^2)の時間計算量がかかるため, 大規模なデータ集合に対して適用することは難しい.本論文では, 階層的クラスタ分析手法の一つであるSingle Link法の高速な近似手法を提案する.本手法は, 近似最近接点探索手法Locality-Sensitive Hashingを利用して, 結合すべきクラスタ, つまり近接するクラスタの探索にかかる手間を減らすもので, O(nB)の時間計算量を達成する.ここで, Bはハッシュテーブルの1エントリに格納されるデータ数の上限であり, テーブルサイズを十分大きくとることでnより十分小さくなる.更に実験により, 提案手法がSingle Link法と近似した結果を得られることや, 大規模データに対してより高速に実行できることを示す.
Scientific journal, Japanese - On the New Scheduling Problems in the Internet Communications
KOGA Hisashi
The IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences (Japanese edition) A, The Institute of Electronics, Information and Communication Engineers, 88, 4, 447-456, 01 Apr. 2005, Peer-reviwed, スケジューリングは工場での生産管理などで使われ, 古くから重要な最適化問題として研究されてきた.しかし, インターネット通信の普及に伴い, 従来のスケジューリング理論の枠組みでは取り扱われなかった新しいスケジューリング問題を解く必要がでてきている.インターネット通信におけるスケジューリングは(1)通信プロトコルやスイッチの構造をもとにした問題である, (2)将来到着するパケットが分からない状態でスケジューリングするオンライン問題である, という2点が従来のスケジューリング問題と異なる.インターネット通信におけるスケジューリング問題を, オンラインアルゴリズムの解析手法である競合度解析(competitive analysis)を用いて解析するアプローチが, 近年活発であり, 本論文はその動向を解説する.Competitive analysisは入力をあらかじめ知っている最適オフラインアルゴリズムとのコスト比によりオンラインアルゴリズムの性能を測る手法であり, 待ち行列理論と違って入力にポアソン分布などの確率分布を仮定しない.ネットワーク通信におけるトラヒックは, ポアソン分布で表現するのが難しいことが知られており, その意味でcompetitive analysisはインターネット通信の解析に適している.
Scientific journal, Japanese - 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, Peer-reviwed, False
International conference proceedings, English - A Fast Fractal Code Retrieval Method Exploiting the Similarity of Vector Sets
YOKOYAMA TAKANORI; WATANABE TOSHINORI; KOGA HISASHI
情報処理学会論文誌データベース（TOD）, Information Processing Society of Japan (IPSJ), 45, 14, 23-29, 15 Dec. 2004, Peer-reviwed, 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.
Scientific journal, Japanese - Fast Hierarchical Clustering Algorithm Using Locality-Sensitive Hashing
Hisashi Koga; Tetsuo Ishibashi; Toshinori Watanabe
Lead, In Proc. 7th International Conference on Discovery Science, Springer LNCS, Springer Berlin Heidelberg, Vol. 3245, pp. 114-128, 2004, Peer-reviwed
International conference proceedings - Balanced Scheduling toward Loss-Free Packet Queuing and Delay Fairness.
Rudolf Fleischer, Hisashi Koga,
Algorithmica, 38, 2, 363-376., 2004, Peer-reviwed, False
Scientific journal, English - Jitter regulation in an Internet router with delay constraint
H. Koga
Journal of Scheduling, Wiley, Vol 4, 6, 355-377, 2001, Peer-reviwed, True
Scientific journal, English - New On-Line Algorithms for the Page Replication Problem
S. Albers and H.Koga
Journal of Algorithms, Vol27, 1, 75-96, 1998, Peer-reviwed, True
Scientific journal, English
MISC
- 異周期カウンタと挿入遅延によるデータストリームに対する頻度クエリの精度向上
山川 竜太郎, 古賀久志
Mar. 2025, 第17回データ工学と情報マネジメントに関するフォーラム (DEIM2025) - コンセプトドリフト環境でのオンラインK-medoidsクラスタリングの代表データ選択とクラスタ数の可変化
田山凜太郎; 古賀久志
Last, Mar. 2025, 情処研報, 2025-MPS-152, 12, 1-6, Japanese - 非更新オートエンコーダを用いた高精度なコンセプトドリフト検出
高野大晴; 古賀久志
Last, Dec. 2024, 信学技報, IBISML2024, 55, 1-8, Japanese - コンセプトドリフトが想定される環境でのオンラインK-medoidsクラスタリングの代表データ選択
田山凜太郎; 古賀久志
Corresponding, Sep. 2024, 第23回情報科学技術フォーラム(FIT2024), Japanese, Summary national conference - 異周期カウンタを用いたスライディングウィンドウ型ストリームに対する頻度クエリの精度向上
山川竜太郎,古賀久志
Corresponding, Sep. 2024, 第23回情報科学技術フォーラム(FIT2024), Japanese, Summary national conference - 部分構造の相対的な位置関係を考慮した順序あり木の類似検索
大高一輝; 古賀久志
Corresponding, Sep. 2024, 第23回情報科学技術フォーラム(FIT2024), Japanese, Summary national conference - 類似軌跡探索における高速かつ高精度なスケッチ間類似度
河野大督; 古賀久志
Corresponding, Sep. 2024, 第23回情報科学技術フォーラム(FIT2024), Japanese, Summary national conference - Product Quantization を用いた高速コンセプトドリフト検出
高野大晴; 古賀久志
Corresponding, 26 Dec. 2023, 情報処理学会研究報告, 2023-DBS-178, 2, 1-8, Japanese, Summary national conference - 文字位置に着目した Min-Hash ベースの文字列類似検索
古賀久志; 別府直輝; 笠井龍一
Mar. 2023, 人工知能学会研究資料, SIG-FPAI-124, 31-36, Summary national conference - 区間Min-Hashを用いた時系列データに対する近似最近傍探索
友田涼太; 古賀久志
Mar. 2023, 第15回データ工学と情報マネジメントに関するフォーラム(DEIM2023), Summary national conference - 制約最適化に基づく画像の時間順並び替え
久保拓巳, 戸田貴久, 古賀久志
Dec. 2022, 情処研報 2022-MPS, 141, 12 - 画像の追加を許容するDeep Hashingに基づく類似画像検索,"
Ye Chenyang; 古賀久志
Sep. 2022, 第21回情報科学技術フォーラム(FIT2022), Summary national conference - 動的なテキスト集合に対する類似検索アルゴリズムALE-Qの評価,
土田祐将; 古賀久志
Mar. 2022, 第14回データ工学と情報マネジメントに関するフォーラム(DEIM2022), Summary national conference - データストリームを対象とした動的多重集合に対する Min-hash;の高速計算アルゴリズム
三原寛寿; 古賀久志
Mar. 2022, 第14回データ工学と情報マネジメントに関するフォーラム(DEIM2022), Summary national conference - ストリーム環境でのテキスト集合に対する類似検索
久保幸平; 古賀久志
Dec. 2020, 情処研報 2020-MPS-131, 2020-MPS-131, 11, Summary national conference - D-4-11 Similar Graph Retrieval based on Min-Hash Focusing on Substructure Similarity
Miyata Takamitsu; Koga Hisashi; Toda Takahisa
The Institute of Electronics, Information and Communication Engineers, 01 Mar. 2016, Proceedings of the IEICE General Conference, 2016, 1, 30-30, Japanese, 110010036664, AN10471452 - D-12-35 Adaptive Similarity Selection for Image Retrieval
Kobayashi Kaoru; Koga Hisashi; Toda Takahisa
The Institute of Electronics, Information and Communication Engineers, 01 Mar. 2016, Proceedings of the IEICE General Conference, 2016, 2, 104-104, Japanese, 110010036409, AN10471452 - A New Parametric Method for Localized Star Spanning Tree Generation
大家 万明; 渡辺 俊典; 古賀 久志
電子情報通信学会, 25 Aug. 2015, 電子情報通信学会技術研究報告 = IEICE technical report : 信学技報, 115, 192, 17-22, Japanese, 0913-5685, 40020588969, AA11553608 - Improvement of Feature Space Construction for Pattern Representation on Data Compression
NAKAJIMA Yuji; KOGA Hisashi; TODA Takahisa
Recent years have witnessed an increased interest about compression-based methods, which is basically parameter-free approach and are employed in applications such as remote sensing and twitter-analysis. We have proposed a pattern representation using data compression or PRDC. This framework represents multimedia-data by using a compression ratio vector(CV). The CV is composed of compression ratio that is calculated from each different dictionary. The accuracy of PRDC depends on set of dictionaries that construct a feature space of PRDC. Therefore, this report aim to improve accuracy of PRDC by generating the set of dictionaries that produces highindependent feature. The proposed method constructs sequentially the dictionary set. Especially, our approach sequentially selects a dictionary from the text whitch is hard to compress with pre-selected dictionaries. We also delete the common phrase between the dictionaries. One worth of this method is to modify dictionaries. We confirm a validity of proposed method using classification for aerial image., The Institute of Electronics, Information and Communication Engineers, 11 Dec. 2014, Technical report of IEICE. PRMU, 114, 356, 63-68, Japanese, 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., Information Processing Society of Japan (IPSJ), 02 Dec. 2014, IPSJ SIG Notes, 2014, 2, 1-5, English, 0919-6072, 110009848659, AN10505667 - A BoVW-based similar image Retrieval Supported by Salient Region
ZOU Zijun; KOGA Hisashi
The Bag of Visual Words(BoVW) model is prevailing in the area of image retrieval. However, because the BoVW model treats all feature points equally, the importance of the foreground which represents the semantics of an image well is ignored. This paper proposes a new BoVW-based similar image retrieval method paying attention to the similarity of the foreground. Our method assumes that the foreground location in an image can be approximated by its salient region and examines the similarity between the salient regions of two images. Specifically, we divide the given image into the foreground and the background by binarizing its saliency map and extract the foreground feature histogram from the foreground region. Finally, the similarity between a pair of images is calculated by summing up the similarity of the foreground feature histograms and that of the global feature histograms derived from the entire images. Our method is expected to improve the retrieval accuracy, since the foreground similarity is emphasized. The experiment on the Caltech-101 image database shows that the recall is surely improved by our method as compared with the conventional BoVW method., The Institute of Electronics, Information and Communication Engineers, 23 Jan. 2014, Technical report of IEICE. Multimedia and virtual environment, 113, 403, 183-188, Japanese, 0913-5685, 110009825792, AN10476092 - Hash-based Similar Search Techniques and Their Applications
KOGA Hisash
In general, the hashing method is utilized to search data having the same key as the query. This technique increases the search speed so that it practically works in O(1) time Recently, the hashing method has been extended to a similarity search whose purpose is not to retrieve exactly the same data but to search similar data. This method has achieved great success in content-based multimedia pattern recognition. This article reviews such hash-based similar search methods and introduces two examples of their application: (1) fast approximated hierarchical clustering and (2) object discovery from an image database., The Institute of Electronics, Information and Communication Engineers, 2014, IEICE ESS Fundamentals Review, 7, 3, 256-268, Japanese, 130004554805 - Object Discovery from Images with Multiple Objects based on Co-occurring Graphs
NANBU Takayuki; KOGA Hisashi; WATANABE Toshinori
Although the BoF (Bag-of-Features)model has succeeded in automatic object discovery, it still has some drawbacks: For example, the BoF model does not represent the spatial relation between feature points. Moreover, decision of the proper vocabulary size is difficult. Xia and Hancock propose a graph-based object discovery algorithm in order to overcome these drawbacks. However, their algorithm assumes that each image contains only one object. In this paper, we propose a new graph-based object discovery method which deals with images including multiple objects. Our algorithm classifies the SIFT features out of the images into clusters based on the results of the SIFT matching. Here, because our clustering method does not require the number of the clusters as its input, we do not have to determine the vocabulary size. Then, the object models are acquired as the set of co-occurring edges, relying on the observation that the similar graph patterns occurs frequently in multiple object instances of the same kind., The Institute of Electronics, Information and Communication Engineers, 14 Mar. 2013, Technical report of IEICE. PRMU, 112, 495, 169-174, Japanese, 0913-5685, 110009713434, AN10541106 - A Novel Image Feature Extraction Approach Using Enhanced Edge Information
WANG Yinan; ZHANG Nuo; WATANABE Toshinori; KOGA Hisashi
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., The Institute of Electronics, Information and Communication Engineers, 22 Mar. 2012, Technical report of IEICE. PRMU, 111, 499, 1-6, English, 0913-5685, 110009546496, AN10541106 - A Novel Image Feature Extraction Approach Using Enhanced Edge Information
WANG Yinan; ZHANG Nuo; WATANABE Toshinori; KOGA Hisashi
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., The Institute of Electronics, Information and Communication Engineers, 22 Mar. 2012, Technical report of IEICE. HIP, 111, 500, 1-6, English, 110009546454, AN10487237 - Adaptive Pattern Analysis of Network Traffic Using Time Series Compressibility
OZEKI Ushio; WATANABE Toshinori; KOGA Hisashi
19 Jan. 2012, 電子情報通信学会技術研究報告. IN, 情報ネットワーク, 111, 409, 47-52, Japanese, 10031106906, AN10013072 - A Method to Reduce Remote Accesses in L_1-Distance-based Distributed Locality-Sensitive Hashing and Its Implementation Evaluation
KOGA Hisashi; WATANABE Toshinori
Locality-Sensitive Hashing (LSH) is an approximate nearest-neighbor search algorithm for high-dimensional data. Though LSH processes a query very fast, LSH consumes much space, because it uses multiple hash tables. Therefore, in applying LSH to a large dataset, implementing LSH in distributed environments is crucial. One simple method is to have every node keep the same number of hash tables evenly. However, this method increases remote accesses, because many nodes must be accessed to access all the hash tables. Thus, this simple method suffers from the long query response time, when the communication delay is the bottleneck. This paper proposes to reduce remote accesses by assigning the hash buckets from different hash tables to the same node, if they store the same points. This strategy decreases remote accesses, since multiple hash buckets to be accessed are accessed with a single remote access., The Institute of Electronics, Information and Communication Engineers, 16 Dec. 2011, IEICE technical report. Data engineering, 111, 361, 1-6, Japanese, 0913-5685, 110009466683, AN10012921 - Accuracy Enhancement in Automatic Video Segmentation based on Graph-Cut using the SURF features
KUDO Satomi; KOGA Hisashi; YOKOYAMA Takanori; WATANABE Toshinori
Video segmentation based on the graph-cut has been actively researched recently. Most previous segmentation methods use the motion information between the frames and the color information as the clues to separate the background from the foreground. However, the performance of these methods tends to deteriorate, when the motion information and the color information become unstable, which is caused by the stop of the moving object and the illumination change, for instance. In this paper, we propose a new automatic video segmentation method robust to unstable motion vectors and color information. Our method relies on the SURF features which is robust to the illumination change and the rotation. In particular, our method matches the SURF feature points between two frames and modifies the segmentation result when the labels of the matched feature points are different., The Institute of Electronics, Information and Communication Engineers, 17 Nov. 2011, Technical report of IEICE. PRMU, 111, 317, 141-146, Japanese, 0913-5685, 110009466297, AN10541106 - Graph Mining based Background Removal from Videos Solving Background Separation
青木 玄明; 古賀 久志; 渡辺 俊典; 横山 貴紀
当研究室では頻出グラフマイニングを用いた動画像からの背景除去を行う手法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., 情報処理学会, 10 Mar. 2011, 研究報告コンピュータビジョンとイメージメディア（CVIM）, 2011, 25, 1-8, Japanese, 2186-2583, 110008584014, AA11131797 - Improving Throughput Fairness between TCP Connections by AQM Emulation at End Hosts
ISHIZU Keita; KOGA Hisashi; WATANABE Toshinori
In the current Internet, congestion control is provided by TCP protocol stack in end hosts and AQM (active queue management) in routers. Recently, an innovative technique called AQM Emulation, such that end hosts implements the functions of AQM by emulating it, has been proposed. This paper purposes to pursue the potentiality of the AQM emulation. When AQM functions are realized in end hosts, one AQM entity has only to process a small number of TCP connections associated with the same host. Hence, we may construct connection-stateful AQM at end hosts, which does not suit for AQM in routers. We exploit this property to propose a new AQM method at end hosts. Our AQM improves throughput fairness between TCP connections by changing the congestion notification probability adaptively to the aggressiveness of TCP connections., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2011, IEICE technical report, 110, 449, 359-364, Japanese, 0913-5685, 110008688985, AN10013072 - Movie Analysis Based on Graph Mining
TSUJI Tomokazu; KOGA Hisashi; YOKOYAMA Takanori; WATANABE Toshinori
頻出グラフマイニングとは,大量のグラフから頻出するグラフパターンを有用な知識として抽出する手法である.SUBDUEは頻出グラフマイニングアルゴリズムとして知られており,MDL(Minimum Description Length)原理に基づいた評価式を用いて,頻出グラフパターンを発見する.本論文では,SUBDUEの新しいアプリケーションとして,SUBDUEを動画像解析に適用することを試みる.特に,監視カメラ映像のようなカメラの前を移動物体が通過する動画像から,SUBDUEを用いて背景除去する手法を提案する.このような動画では移動物体の通過前後に背景のみのビデオフレームが十分存在するため,背景を評価値が高い頻出グラフパターンとして抽出できる.具体的には,まず,ビデオフレームを領域分割し,各領域を節点,各領域間の隣接関係を辺とする領域隣接グラフとして表現する.次に,背景を評価値の高い頻出部分グラフとして取り出す.最後に,各フレームを表すグラフから背景を表すグラフを除去して,背景除去を行う.グラフのノードは領域を表すので,提案手法は画素単位ではなく領域単位の背景除去となる.したがって,提案手法ではグラフの構造が変化しない範囲であれば,カメラが動いても背景除去可能である.更に,背景のみのビデオフレーム数が少なくても背景の評価値が高くなるように評価式の変更も行った., The Institute of Electronics, Information and Communication Engineers, 01 Feb. 2010, The IEICE transactions on information and systems, 93, 2, 86-99, Japanese, 1880-4535, 110007539031, AA12099634 - A New AQM Algorithm Exploiting Passive RTT Estimation
星原 隼人; 古賀 久志; 渡辺 俊典
情報処理学会, Feb. 2010, 情報処理学会論文誌 論文誌ジャーナル, 51, 2, 466-477, Japanese, 1882-7837, 40019546003, AA12317677 - Automatic Extraction of Moving Object from Video Frames by Graph Cut
MATSUDA Akihiro; KOGA Hisashi; WATANABE Toshinori
Recently, much attention has been paid to the technology that works effectively for many problems in image processing by reducing them to energy minimization problems that are solved with the minimum graph cut algorithm. Interactive segmentation that separates the foreground from the background for images and videos is known as one of the main applications of this technology. However, in the interactive segmentation, users are responsible for giving foreground seeds and background seeds manually a priori. This paper proposes an algorithm that extracts the foreground automatically from movies taken by a static video camera, where the seeds are generated without human intervention. Our algorithm first derives SIFT feature points from every video frames. Then, it tracks the motion of the feature points and classifies them into two groups, i.e., moving feature points and static feature points. Finally, the former is chosen as the foreground seeds, while the latter becomes the background seeds., The Institute of Electronics, Information and Communication Engineers, 14 Jan. 2010, IEICE technical report, 109, 375, 13-18, Japanese, 0913-5685, 110008000966, AN10013221 - An Algorithm for Getting Border Points lying in Euclidean Space
KOBAYASHI Fumiya; WATANABE Toshinori; KOGA Hisashi
Given a set of points S, we call its outer border points as a border points set B. For convex S, it is easy to get B by choosing points each of which has the biggest projection to randomly chosen vectors. However, this is not the case for non convex S. In this paper, we propose a method that partitions the S into subsets each of which has enhanced convexity and gathers border points of them to get B. Probabilistic LSH-like searching scheme is also adapted to reduce computation cost., The Institute of Electronics, Information and Communication Engineers, 14 Jan. 2010, IEICE technical report, 109, 375, 115-120, Japanese, 0913-5685, 110008000979, AN10013221 - A Power Control Method to Improve Spatial Reuse for Wireless Ad Hoc Networks Using Directional Antennas
ZHAN Chuanxi; KOGA Hisashi; WATANABE Toshinori
Because the physical bandwidth is small in wireless networks, the spatial reuse ability, that is, the ability to pack many simultaneous transmissions without causing a collision is important. On the other hand, as for wireless ad hoc networks, the reduction of power consumption in wireless nodes is essential. Power control methods which decrease the power to transmit packets have been positively studied as a technology that not only suppresses power consumpution but also improves the spatial reuse ability. In power control methods, when a packet is transmitted with a controlled weak power, unused spaces appear. The purpose of this research is to improve communication quality by exploiting these unused spaces efficiently. Specifically, we propose a new power control MAC protocol for IEEE802.11-based wireless ad hoc networks which improves the spatial reuse ability of some previous power control protocol, on condition that each node has a directional antenna. By simulations with Qualnet, the effectiveness of our method is confirmed., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2009, IEICE technical report, 108, 458, 481-486, Japanese, 0913-5685, 110007324661, AN10013072 - Image classification using textized Image
HIRAI Atsushi; ZHANG Nuo; WATANABE Toshinori; KOGA Hisashi
With the development of the information technology, the number of electronic information increases rapidly. In which, for enormous number of digital images the demand of automatic classification technology exceeded human processing capacity. As an automatic classification technique, representing textized image based on data compression is proposed in this paper. In the step of textizing image, image is divided into segments which are replaced as characters. Then, the similarity between compressibility vectors is used in the classification step. In which, we focus on the compressibility of the text string. Finally, the effectivity of the proposed method is verified in our experiments., The Institute of Electronics, Information and Communication Engineers, 09 Jan. 2009, IEICE technical report, 108, 382, 7-12, Japanese, 0913-5685, 110007123235, AN10013061 - Video Image Analysis Exploiting Frequent Graph Mining
TSUJI Tomokazu; KOGA Hisashi; YOKOYAMA Takanori; WATANABE Toshinori
Frequent graph mining is a technique to extract graph patterns which appear frequently in large set of graphs as useful patterns. This paper proposes to apply frequent graph mining to video image analysis. This paper deals with a video in which moving object passes in front of a surveillance camera and devices a graph-based background subtraction method exploiting frequent graph mining. In our method, every video frame is segmented into regions first by some image segmentation. Next, the video frame is converted into a region adjacency graph such that regions correspond to graph nodes and the region adjacency is represented by graph edges. Then, the background removal is performed by discovering the background as a frequent graph., The Institute of Electronics, Information and Communication Engineers, 11 Dec. 2008, IEICE technical report, 108, 363, 19-24, Japanese, 0913-5685, 110007123819, AN10541106 - Real-time object detection based on global motion estimation from MPEG motion vectors
OTA Shuhei; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
In this paper, we propose a approach for real-time object detection based on global motion estimation from MPEG motion vectors. The proposed method extracts moving region uses global motion estimation with Newton-Raphson method to sort out motion vectors. It is difficult to segment video objects from the video sequenses exhibits the camera translates. Because the camera translates causes motion vectors in background region except moving region. The proposed approach estimates the global motion vectors from the input motion vectors, calculates residual motion vectors between the input motion vectors and the global motion vectors to extract moving object in that sequenses. Simulation results and analyses are provided for the proposed method, which show the effectiveness and speed for real-time system on commercial laptop computer., The Institute of Electronics, Information and Communication Engineers, 16 Oct. 2008, IEICE technical report, 108, 263, 19-24, Japanese, 0913-5685, 110007101143, AN10541106 - AMOR : Automatic Moving Object Recognizer from Video
TOKUTOMI Kentarou; WATANABE Toshinori; KOGA Hisashi; YOKOYAMA Takanori
A new video analysis system AMOR that learns and recognizes moving object in a video is proposed. AMOR is composed of two functions: the atomic behavior label sequence generator and the sub-sequence, i.e., compound behavior extractor. To cope with unknown, various, and noisy input, the former is realized by a learning multi-resolution voter and the latter by a multi-layered label sequence analyzer with inter-layer sub-sequence alignment. Through applications to human video, containing behaviors of different coarseness, fully automatic labeling, hierarchical sub-sequence extraction, could be demonstrated., The Institute of Electronics, Information and Communication Engineers, 21 Feb. 2008, IEICE technical report, 107, 491, 31-36, Japanese, 0913-5685, 110006937534, AN10541106 - A new moderate UDT improving throughput fairness with other high-speed transport protocols
KAWANO Shinya; KOGA Hisashi; WATANABE Toshinori
Recently, the application that needs the long distance high speed communications between Grid and the network storage system, etc. has appeared along with the wider bandwidth on the network. However, in TCP (TCP Reno) being generally used now It is known not to be able to use the bandwidth enough on the network where the bandwidth delay product is large. Then, to use the bandwidth enough on the network where the bandwidth delay product is large, various, high-speed transport protocol is proposed. There is UDT in the one, and is a problem of depriving of the band when coexisting with other high-speed transport protocols. Therefore, it evaluates it by proposing and simulating mUDT (moderate UDT) that adds the function to soften an increase in the rate in consideration of the band fairness with other connections., The Institute of Electronics, Information and Communication Engineers, 06 Dec. 2007, IEICE technical report, 107, 378, 13-18, Japanese, 0913-5685, 110006546838, AN10013072 - An Interactive Technique for Feature Space Dimension Reduction
YAMAZAKI Keisuke; ZHANG Nuo; WATANABE Toshinori; KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 25 Sep. 2007, IPSJ SIG Notes, 2007, 94, 35-40, Japanese, 0919-6072, 110006402896, AN10115061 - Component-Based Automatic Object Discovery Using Multiple Phase Hashing
PINEDA Gibran Fuentes; KOGA Hisashi; WATANABE Toshinori
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., Information Processing Society of Japan (IPSJ), 04 Sep. 2007, IPSJ SIG Notes. CVIM, 2007, 87, 265-270, English, 0919-6072, 110006403849, AA11131797 - Component-Based Automatic Object Discovery Using Multiple Phase Hashing
PINEDA Gibran Fuentes; KOGA Hisashi; WATANABE Toshinori
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., The Institute of Electronics, Information and Communication Engineers, 27 Aug. 2007, IEICE technical report, 107, 206, 265-270, English, 0913-5685, 110006423324, AN10541106 - Component-Based Automatic Object Discovery Using Multiple Phase Hashing
PINEDA Gibran Fuentes; KOGA Hisashi; WATANABE Toshinori
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., The Institute of Electronics, Information and Communication Engineers, 27 Aug. 2007, IEICE technical report, 107, 207, 265-270, English, 0913-5685, 110006423366, AN10487237 - A Priority-based QoS Control in Mobile Ad hoc Networks Exploiting Multipath Load-aware Routing
NIAKH Aly; KOGA Hisashi; KITAMURA Hiroshi; WATANABE Toshinori
With the growing interest in Mobile Ad hoc Networks (MANETs) and the rising popularity of interactive real-time multimedia applications (e.g. video or voice conversation applications, etc.), providing Quality-of-Service (QoS) is becoming more and more necessary in MANETs. In this paper we target an environment where coexist, real-time interactive multimedia applications (high-priority flows) and conventional data transfer applications (low-priority flows) and we propose a priority-based QoS control scheme exploiting multipath load-aware routing (SPLIT scheme) that considerably increases the throughput of high-priority flows and at the same time reduces the number of route breaks of more than 10 % compared to the case where the single minimum hop path is used., The Institute of Electronics, Information and Communication Engineers, 01 Mar. 2007, IEICE technical report, 106, 578, 37-42, English, 0913-5685, 110006248547, AN10013072 - Dynamic TCP Acknowledgment with Sliding Window
KOGA Hisashi
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≥1. 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., Information Processing Society of Japan (IPSJ), 23 Jan. 2007, IPSJ SIG Notes, 2007, 5, 1-8, English, 0919-6072, 110006202672, AN1009593X - Nonlinear Local Optima Set Extraction by Pit Approximation Functions
KOEZUKA MAYUKO; WATANABE TOSHINORI; KOGA HISASHI
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., Information Processing Society of Japan (IPSJ), 22 Dec. 2006, IPSJ SIG Notes, 2006, 135, 69-72, Japanese, 0919-6072, 110006165024, AN10505667 - Automatic Extraction of Objects out of Images using Data Compression and Object Likeliness
SUGIYAMA Hideyuki; KOGA Hisashi; WATANABE Toshinori; YOKOYAMA Takanori
We propose a new object generator that can acquire a few sample images without human intervention. First, we introduce a new concept of neighbour set representation of objects which is simple but powerful to represent non-rigid objects. Here, non-rigid means the changeability of parts arrangement. Next, we formulate our following instincts- appropriate objects are such that appear many times and have many parts in the image - into a computable evaluation function of image compressibility gained. This evaluation function also takes into account the uniformity of size, aspect ratio and density among multiple object instances of the same kind. We propose an algorithm that extracts objects automatically by searching for objects that maximizes the value of the evaluation function., The Institute of Electronics, Information and Communication Engineers, 17 Nov. 2006, IEICE technical report, 106, 376, 183-188, Japanese, 0913-5685, 110005717945, AN10541106 - Moving Region Detection Based on Transportation Problem Solving
FURUKAWA Sho; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
In this report, we propose a moving object detection method based on a solution the transportation problem. We regard the regions in the current frame as sources, the regions in the target frame as destinations, and the total distances among regions as the transportation cost. The solution of the transportation problem minimizing the total cost gives the correspondences of regions in the different frames. The correspondences are represented by flows. Each flow carries information about the pair of corresponding regions, the distance between the regions, and the amount of the transported pixels. The proposed method can detect and track the moving regions by using the flows. We demonstrate the effectiveness by means of various experiments., The Institute of Electronics, Information and Communication Engineers, 13 Oct. 2006, IEICE technical report, 106, 301, 59-64, Japanese, 0913-5685, 110004852069, AN10541106 - A New Document Retrieval Method Using LZ78 Compression Function
KIMURA Hiroaki; WATANABE Toshinori; KOGA Hisashi; ZHANG Nuo
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., Information Processing Society of Japan (IPSJ), 12 Sep. 2006, IPSJ SIG Notes, 2006, 94, 65-70, Japanese, 110004824260, AN10115061 - Document Relation Analysis by Data Compression
MATSUZAKI Daisuke; WATANABE Toshinori; KOGA Hisashi; ZHANG Nuo
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., Information Processing Society of Japan (IPSJ), 12 Sep. 2006, IPSJ SIG Notes, 2006, 94, 51-56, Japanese, 0919-6072, 110004824211, AN10114171 - Document Relation Analysis by Data Compression
MATSUZAKI Daisuke; WATANABE Toshinori; KOGA Hisashi; ZHANG Nuo
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., Information Processing Society of Japan (IPSJ), 12 Sep. 2006, IPSJ SIG Notes, 2006, 94, 51-56, Japanese, 110004824258, AN10115061 - A New Document Retrieval Method Using LZ78 Compression Function
KIMURA Hiroaki; WATANABE Toshinori; KOGA Hisashi; ZHANG Nuo
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., Information Processing Society of Japan (IPSJ), 12 Sep. 2006, IPSJ SIG Notes, 2006, 94, 65-70, Japanese, 0919-6072, 110004824213, AN10114171 - Moving Object Detection Using Motion Vectors in MPEG Video Data
IWASAKI Toshiki; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi; ABE Tatsuo
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., Information Processing Society of Japan (IPSJ), 09 Sep. 2006, IPSJ SIG Notes. CVIM, 2006, 93, 167-174, Japanese, 0919-6072, 110004820687, AA11131797 - Moving Object Detection Using Motion Vectors in MPEG Video Data
IWASAKI Toshiki; YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi; ABE Tatsuo
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., The Institute of Electronics, Information and Communication Engineers, 02 Sep. 2006, IEICE technical report, 106, 230, 33-40, Japanese, 0913-5685, 110004849817, AN10541106 - Classification method of tree data reflecting structual similarity and contents similarity
SAITO Hiroaki; KOGA Hisashi; WATANABE Toshinori; YOKOYAMA Takanori
Tree is useful for representing various objects such as semi-structured data and gene data. Thus, computing tree similarity is important in the research area of pattern recognition and information retrieval. Tree edit distance is one of the most known dissimilarity measures for trees and defined as the minimum value of the total costs associated with node edit operations (i.e, deletion, insertion and relabeling) incurred in the conversion between two trees. Tree edit distance contains both tree structural dissimilarity and label contents dissimilarity. However, the significance of the two dissimilarity depends on the application and the data. Therefore, in this paper, we propose a new method which can get a clustering result which reflects the characteristics of the target application and the users' purpose properly by splitting the tree edit distance into contents dissimilarity and structural dissimilarity., The Institute of Electronics, Information and Communication Engineers, 08 Jun. 2006, IEICE technical report, 106, 99, 7-12, Japanese, 0913-5685, 110004748917, AN10541106 - An Efficient Implementation of Attribute-Graph Matching Algorithm
MORITA Akihiro; KOGA Hisashi; WATANABE Toshinori; YOKOYAMA Takanori
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., Information Processing Society of Japan (IPSJ), 17 Mar. 2006, IPSJ SIG Notes, 2006, 30, 49-54, Japanese, 0919-6072, 110004687072, AN1009593X - Online Automatic Acquisition of Human Motion Models with Voting
YOSHIOKA Taichi; KOGA Hisashi; WATANABE Toshinori; YOKOYAMA Takanori
In general, to recognize human motions, we need to prepare a lot of known motion models beforehand. In this research, we propose system that acquires the motion models automatically from the input stream in an on-line fashion and, therely, recognizes human motions without prepareing known motion models. By experimentes, effectiveness was confirmed., The Institute of Electronics, Information and Communication Engineers, 22 Sep. 2005, Technical report of IEICE. PRMU, 105, 302, 119-124, Japanese, 0913-5685, 110003275988, AN10541106 - Active Queue Management using Congestion Estimation
HOSHIHARA Hayato; KOGA Hisashi; KITAMURA Hiroshi; WATANABE Toshinori
An Active Queue Management (AQM) is a technique for congestion control in routers. Random Early Detection(RED) and Random Exponential Marking(REM) that relies on Explicit Congestion Notification (ECN) marking are famous examples of AQMs. TCP congestion control scheme accompanies the delay whose size reaches Rount Trip Time (RTT), till its effect works. However, the AQMs which have been proposed so far does not take this delay into account explicitly. In this paper, we propose a new AQM algorithm which is robust against the change of the input traffic and prevents the queue overflow well by estimating the future econgestion state after the time of RTT., The Institute of Electronics, Information and Communication Engineers, 15 Sep. 2005, IEICE technical report. Information networks, 105, 279, 25-30, Japanese, 0913-5685, 110003224923, AN10013072 - Automatical Extraction of Object-tracks from Videos using LSH-Link Clusterling Algorithm
KUSABA Hiroaki; KOGA Hisashi; WATANABE Toshinori
This paper proposes a non-parametric simple algorithm to extract objects from the spatio-temporal region. Our algorithm regards a pixel in movies as a 6-dimensional data containing color, space and time information and extract objects by classifying them with LSH-Link which approximates the famous Single-Link algorithm. Then, combinatorial objects are discovered by gathering the objects which have similar locuses. We verify that our algorithm works well for artificial experimental images., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2005, IEICE technical report. Natural language understanding and models of communication, 104, 667, 37-42, Japanese, 0913-5685, 110003278840, AN10091225 - An Investigation on Similarities between DTD Data Exploiting the Tree DP Matching
ONOZATO Takuya; KOGA Hisashi; WATANABE Toshinori
Tree structure is useful for representing various objects such as XML and gene data. To retrieve and classify objects described as trees, it is important to obtain similarities between trees. Though the tree DP matching algorithm can compute these similarites, one must set proper cost associated with insertion, deletion and replacement of nodes before applying this algorithm to real applications. This paper proposes the method to define similarities, even if proper cost associated with insertion, deletion and replacement of nodes are unknown. This method is proved to be useful by experiments with DTD data, the schema for XML data., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2005, IEICE technical report. Natural language understanding and models of communication, 104, 667, 103-108, Japanese, 0913-5685, 110003278851, AN10091225 - Estimation of changing background from moving picture using online realtime PCA
SUGIYAMA Kenji; KOGA Hisashi; WATANABE Toshinori; YOKOYAMA Takanori
In this paper, we proposed the technique which presumes the background from the movie affected by the background change due to vibration. The background is extracted by detecting and removing the object from the changing background using the eigenspace obtained with the principal component analysis. We adopt the online to accelerate this processing., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2005, IEICE technical report. Natural language understanding and models of communication, 104, 667, 31-36, Japanese, 0913-5685, 110003278839, AN10091225 - Human Extraction Using Optical Flow in Complex Background
IWASAKI Toshiki; YOKOYAMA Takanori; KOGA Hisashi; WATANABE Toshinori
We propose a human extraction method using optical flow. This method uses plural frames to detect optical flow and extracts human's regions by using this flow. The use of plural frames enables us to obtain stable optical flow under complex background. Then, the use of the optical flow makes it possible to extract reliable human's region which can not be detected with background subtraction or inter-frame differences. This paper shows the effectiveness of the proposed method experimentally., The Institute of Electronics, Information and Communication Engineers, 24 Feb. 2005, IEICE technical report. Natural language understanding and models of communication, 104, 667, 73-77, Japanese, 110003278846, AN10091225 - Automatic Extraction of Objects from Images Using Data Compression Ratio
SUGIUCHI Takahiro; WATANABE Toshinori; KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 12 Nov. 2004, IPSJ SIG Notes. CVIM, 2004, 113, 133-140, Japanese, 0919-6072, 110002694803, AA11131797 - Object retrieval using skeleton lines
NAKAYAMA Hitoshi; WATANABE Toshinori; KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 12 Nov. 2004, IPSJ SIG Notes. CVIM, 2004, 113, 141-146, Japanese, 0919-6072, 110002694804, AA11131797 - Human Motion Recognition With Voting
OFUJI Atsushi; WATANABE Toshinori; KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 12 Nov. 2004, IPSJ SIG Notes. CVIM, 2004, 113, 83-88, Japanese, 0919-6072, 110002694797, AA11131797 - A Vector Set Similarity Measure based on Bi - directional Mapping and Its Upper Bounds
YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 10 Sep. 2004, IPSJ SIG Notes. CVIM, 2004, 91, 145-150, Japanese, 0919-6072, 110002664192, AA11131797 - A Vector Set Similarity Measure based on Bi-directional Mapping and Its Upper Bounds
YOKOYAMA Takanori; WATANABE Toshinori; KOGA Hisashi
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., The Institute of Electronics, Information and Communication Engineers, 03 Sep. 2004, Technical report of IEICE. PRMU, 104, 290, 145-150, Japanese, 0913-5685, 110003274084, AN10541106 - LI-010 Image Retrieval Exploiting the Similarity of Vectorized Fractal Code Sets
Yokoyama Takanori; Watanabe Toshinori; Koga Hisashi
Forum on Information Technology, 20 Aug. 2004, 情報科学技術レターズ, 3, 191-192, Japanese, 110007634933, AA1197723X - Discovery of Objects from Static Images based on Locality-Sensitive Hashing
KOGA Hisashi; WATANABE Toshinori
This paper proposes a method to discover objects from static images without teaching models. Our method utilizes Locality-Sensitive Hashing(LSH) known as a probabilistic algorithm that finds the approximate nearest neighbor points in Euclidean space. First, the proposed method extracts object components by gathering near image pixels by LSH. Then, the candidates for objects are discovered as the result of applying LSH again to the extracted object components. Finally we regard the candidates as the valid objects, in case the same kind of candidates appear in the static image multiple times. As our method does not check the rigorous location relation between object components, image objects can be discovered robustly against rotation and slide operations., The Institute of Electronics, Information and Communication Engineers, 13 Feb. 2004, Technical report of IEICE. PRMU, 103, 659, 113-118, Japanese, 0913-5685, 110003273960, AN10541106 - Approximate Hirarchical Clustering Algorithm using Locality-Sensitive Hashing
ISHIBASHI Tetsuo; KOGA Hisashi; WATANABE Toshinori; SUGAWARA Ken
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 proposes a fast approximation method for the Single-Link clustering algorithm that is a typical hierarchical clustering algorithm. Our method reduces its time complexity by utilizing the hash table made by Locality-Sensitive Hashing known as an algorithm for finding the candidates of the nearest neighbor points. By experiment, we show that (1) the proposed method has the ability to extract non-ellipse clusters like the Single-Link algorithm and that (2) it runs faster for multi-dimensional large data than the Single-Link algorithm., The Institute of Electronics, Information and Communication Engineers, 13 Feb. 2004, Technical report of IEICE. PRMU, 103, 659, 119-124, Japanese, 0913-5685, 110003273961, AN10541106 - Analysis of Object Similarity by Danamic Programming Matching of Trees
ONOZATO Takuya; KOGA Hisashi; WATANABE Toshinori; SUGAWARA Ken
In this paper, we propose a new similarity measure between two objects. We express an object as an attribute tree with nodes representing various properties of the object. We use the edit distance of two trees recently proposed by Oommen as the objects' similarity. After proving the distance properties of the proposed measure, an application to writing tool similarity analysis is given., The Institute of Electronics, Information and Communication Engineers, 13 Feb. 2004, Technical report of IEICE. PRMU, 103, 659, 107-112, Japanese, 0913-5685, 110003273959, AN10541106 - Competitive Analysis of On-line Algorithms
KOGA Hisashi
The Institute of Electronics, Information and Communication Engineers, 01 Dec. 2003, The Journal of the Institute of Electronics, Information and Communication Engineers, 86, 12, 972-974, Japanese, 0913-5693, 110003231136, AN1001339X - Automatic Extraction of Image Object Definition From Sample Images
OHTA Takahiko; SUGIUCHI Takahiro; WATANABE Toshinori; SUGAWARA Ken; KOGA Hisashi
In recent years, object recognition has come to be used in various scenes, such as security authentication and robot vision. We are examining automatic extraction of an object definition, and the recognition techniue 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., Information Processing Society of Japan (IPSJ), 06 Nov. 2003, IPSJ SIG Notes. CVIM, 2003, 109, 153-158, Japanese, 0919-6072, 110002664018, AA11131797 - A Study on the Possibility of Extracting the Feature of Images using two types of Orthogonal Minimum Spanning Trees (MSTs)
KANO Norihisa; WATANABE Toshinori; KOGA Hisashi; SUGAWARA Ken
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 grayscale 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., Information Processing Society of Japan (IPSJ), 06 Nov. 2003, IPSJ SIG Notes. CVIM, 2003, 109, 49-55, Japanese, 0919-6072, 110002664005, AA11131797 - Approximate Hierarchical Clustering Algorithm Using Locality - Sensitive Hashing
ISIBASHI Tetsuo; KOGA Hisashi; WATANABE Toshinori; SUGAWARA Ken
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., Information Processing Society of Japan (IPSJ), 06 Nov. 2003, IPSJ SIG Notes. CVIM, 2003, 109, 57-62, Japanese, 0919-6072, 110002664006, AA11131797 - Appearance based 3D Object Recognition exploiting MST and its performance analysis for image scale change.
HIRAHASHI Keiichi; WATANABE Toshinori; KOGA Hisashi; SUGAWARA Ken
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 Derformance under image scale changes are reported., Information Processing Society of Japan (IPSJ), 06 Nov. 2003, IPSJ SIG Notes. CVIM, 2003, 109, 145-151, Japanese, 0919-6072, 110002664017, AA11131797 - Balanced Scheduling toward Loss - Free Packet Queuing
KOGA Hisashi
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 maximun 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. Specifically we show that no deterministic/randomized on-line algorithm is better than Ω(log m)-competitive. Then we prove a simple greedy algorithm is ⊝(log m)-competitive and nearly optimal., Information Processing Society of Japan (IPSJ), 27 Jul. 2001, IPSJ SIG Notes, 2001, 79, 37-44, Japanese, 0919-6072, 110002812446, AN1009593X - An Evaluation of Communication Property in Wide Area Parallel-Distributed Systems
MIZUNO Hironori; KOGA Hisashi; JINZAKI Akira
Parallel applications which require high bandwidth and low delay are not suitable because of communication processing overhead and absolute delay of long distance. At the other hand, as internet protocol processing is improved and the transferring speed is higher, it's important to think of the possibility of parallel-distributed systems in wide-area. From this point of view, to examine the practicality of parallel computing on the Internet, we observe the traffic patterns and make performance evaluation when the NAS parallel benchmarks are run on the wide-area lnternet connceted by 90kmATM lines. As the results, we obtain the following three results, i.c. 1) wide-area parallel -distributed systems can work effectively depending the parallel algorithm used, 2) the performance is influenced by delay and bandwidth or the wide-area network, though its communication quality is sufficient, and 3) the scalability in terms or the number of processors which participate Parallel computing is restricted., The Institute of Electronics, Information and Communication Engineers, 27 Aug. 2000, IEICE technical report. Computer systems, 100, 249, 17-24, Japanese, 0913-5685, 110003180563, AN10013141 - An Analysis for Jitter Regulators with Delay Consideration
KOGA Hisashi
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., Information Processing Society of Japan (IPSJ), 21 Mar. 2000, IPSJ SIG Notes, 2000, 31, 1-8, Japanese, 0919-6072, 110002812378, AN1009593X - A Reliable Multicast for Wide - Area Parallel and Distributed Systems
Shimokuni Osamu; Koga Hisashi; Jinzaki Akira
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 thouse 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., Information Processing Society of Japan (IPSJ), 02 Mar. 2000, IPSJ SIG Notes, 2000, 23, 53-58, Japanese, 110004059338, AN10463942 - A Study on the Internet Protocol for Parallel and Distributed Processing
SHIMOKUNI Osamu; KOGA Hisashi; NIINOMI Tadafusa; KAWAI Jun; KOBAYASHI Shinji; MIZUNO Hironori; JINZAKI Akira; NAKAMURA Osamu; MURAI Jun
To construct a parallel and distributed system, connecting large number of commodity computers distributed in world-wide area using the Gigabit-speed Internet. The Intemet Protocol, however, has an problem in sending a packet to thousands of member computers of the system. Using unicast TCP, its cost is linear increment as rising of the number of computers. Using multicast UDP, this protocol supports no reliable communication. Recently, several Reliable Mtulticast Protocols, for a network whiteboard, for a live video communication and for a distributed Web servers, are proposed. In this paper, we investigated several properties of the reliable multicast protocol for a parallel and distributed computation with reference of those protocols. We focused on two properties:the confirmation of packet arrival and the retransmission. As the result, we got the prospect that we need an aggregation mechanism of the Acknowledgement packet and the limited scope retransmission mechanism for the network router functions with keeping its simplicity, The Institute of Electronics, Information and Communication Engineers, 05 Aug. 1999, IEICE technical report. Computer systems, 99, 252, 43-48, Japanese, 0913-5685, 110003180504, AN10013141 - An Implementation Design on the Internet Protocol for Parallel and Distributed Processing
KOGA Hisashi; SHIMOKUNI Osamu; NIINOMI Tadafusa; KAWAI Jun; KOBAYASHI Shinji; MIZUNO Hironori; JINZAKI Akira
In parallel-distributed computing, many processings such as barrier synchronization and page sharing in DSM can be handled efficiently by multicasting. However, current IP multicast does never provide reliability. Recently, a technology named "reliable multicast" is proposed and we attempt to apply it to parallel-distributed computing. In this paper, the properties which reliable multicast must have in order to operate in a parallel-distributed computing environment are mentioned first. Then, a practical protocol is designed according to the properties. This protocol reduces redundant packet retransmissions and unifies several ACK packets into one ACK packet mainly by the table management and the table search. We obtain the estimatiion result that one packet will be processed within 200ns delay if the protocol is implemented on the network-server Comet which we are currently developing., The Institute of Electronics, Information and Communication Engineers, 05 Aug. 1999, IEICE technical report. Computer systems, 99, 252, 49-54, Japanese, 0913-5685, 110003180505, AN10013141 - IEEE1394 Is Intergrated into Computer Networks by Comet
KOGA Hisashi; JINZAKI Akira
We consider IEEE1394 as a high speed network to connect Comets and form them into parallel network servers. Apart from that, IEEE1394 provides QoS function in which all data arrive at the destination without any delay. To evaluate the protocol processing performance of Comet, we construct a system which transforms IEEE1394 isochronous packets to IP packets and forwarded them to Ethernet(IEEE1394 over IP). While the previous network processing mechanism cannot process this protocol conversion every 125 micro-seconds due to the interruption overhead, Comet can process it at 40 micro-seconds by offloading it onto a network adapter. With the use of this IEEE1394 over IP function, we made DV-stream relay experiments on the WIDE backbone network. We also measured how much jitter is generated when a packet passes a router. As the result of these experiments, the following two facts are obtained.(1)When the network consists only of Comet machines, the 125 micro-second packet intervals are maintained.(2)Even the latest commercial router expands the jitter two times(i.e.250 micro-seconds)., The Institute of Electronics, Information and Communication Engineers, 05 Aug. 1998, IEICE technical report. Computer systems, 98, 234, 35-40, Japanese, 110003180269, AN10013141 - Tight Bound on the Competitive Ratio for the Page Replication Problem
Albers Susanne; Koga Hisashi
Kyoto University, May 1994, RIMS Kokyuroku, 871, 182-189, English, 1880-2818, 110004774703, AN00061013 - On - line Algorithms for Distributed Shared Memory
Koga Hisashi
In a distributed shared memory system consisting of multiple processors, each of which has its own local memory, each page needs to be located at a proper processor by migration or replication so as 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 based on randomized algorithms for page migration problem to page replication problem can acquire more powerful result than existing deterministic algorithms about competitive ratio., Information Processing Society of Japan (IPSJ), 28 May 1993, IPSJ SIG Notes, 1993, 48, 49-55, Japanese, 0919-6072, 110002812074, AN1009593X
Research Themes
- 動的に変わる集合に対する類似検索のスケッチを利用した高速化
古賀 久志
日本学術振興会, 科学研究費助成事業 基盤研究(C), 電気通信大学, 基盤研究(C), 本研究課題はデータストリームを対象とする類似検索を取り扱う。その具体的な応用としては、嗜好性が似たユーザの発見が挙げられる。例えば、閲覧したウェブニュース記事の集合が互いに似た2ユーザは、興味がある事柄が似ており、嗜好性が似ていると言える。このようにして、類似ユーザ検索を集合間類似検索に帰着できる。 要素が固定した通常の集合に対しては、Min Hashというハッシュ関数を利用して集合の要約(スケッチ）を事前生成し、スケッチ間で軽量に類似度計算することで、類似検索を高速化できる。しかし、ストリーム環境では新しい要素の追加と古い要素の消滅が起きるため、スケッチを高速更新する必要がある。そこで本研究では、ストリーム環境で集合の要素が入れ替わる状況で、Min Hashを高速計算するアルゴリズムの開発に取り組んだ。 そして2021年度は、多重集合を取り扱えなかったDatarらの既存手法を、多重集合が取り扱えるよう拡張することに成功した。ここで、多重集合とは同じラベルの要素を複数持てる集合のことである。Min Hashは集合の各要素に確率的に値を割り当て、その最小値をハッシュ値とする。既存手法では将来的に最小値になりえない要素を削除して、ハッシュ値再計算のオーバーヘッドを削減している。しかし、多重集合の場合、要素への割り当て値が多重度に依存して動的に変わるため将来的に最小値になりえるかの判定が困難になる。我々の提案手法は、この厳しい条件下で、将来的に最小値にならない要素を判別する。さらに同一ラベルの要素を、提案手法が高々１つだけ保持すればよいことも示せた。集合の要素数をWとすると、提案手法の計算時間は実験的にlog Wに比例し、O(W)かかるベースライン手法より圧倒的に高速に動作することを確認できた。, 21K11901
Apr. 2021 - Mar. 2026 - Fast Concept Drift Detection Exploiting Product Quantization
丸文財団, 海外渡航助成
Jul. 2024 - Aug. 2024 - Continuous Similarity Search for Text Sets
丸文財団, 海外渡航助成, 研究室学生の海外渡航費用の助成
Aug. 2022 - Sep. 2022 - Continuously Similarity Search for Evolvingi Sets
Koga HIsashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research, The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), This research studied similarity search for data streams. In particular, we regard the latest data in a data stream as an evolving set whose elements can change dynamically. Then, we realized the similarity search for data streams by reducing the problem to the set similarity search. In particular, we developed several fast similarity search algorithms that measure the similarity between two data just enough to determine the search results, avoiding unnecessary similarity computations. It is also our research contribution that we formulated two similarity search problems for data streams., 18K11311
01 Apr. 2018 - 31 Mar. 2021 - Optimal Construction of Compression-based Feature Space
Koga Hisashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Compression based pattern recognition is an unsupervised data analysis technique which realizes data analysis without prior knowledge about the data to be analyzed. Its primary point is to measure the similarity between two data based on the compression rate. In particular, in order to exploit the standard pattern recognition algorithms such as SVM and k-means, this research deals with compression-based feature spaces in which an object is represented as a compression vector consisting of multiple compression ratios and studies their effective construction. As the main result, by exchanging the words among the compression dictionaries each of which is responsible for one dimension so that they may be more independent one another, we succeeded in improving the pattern recognition accuracy by 7 to 8% as compared with the previous method in literatures., 15K00148
01 Apr. 2015 - 31 Mar. 2019 - Fast Similarity Search for Structural Data using Structural Digests
Koga Hisashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), This project studied the similarity search for structural data such as graphs. Because structural data are complex, the overhead to compute the similarity between two data tends to be enormous. Therefore, we generate a small data structure called "digest" for an individual graph and measure the similarity between two data in a short time by comparing their digests. Here, the search accuracy depends on how to summarize the structural information of a graph onto its digest. By embedding the similarity information regarding substructures into the digests, we succeeded in realizing the similarity search with a high retrieval accuracy.
We also studied the structure-based image processing which is a promising application of similarity search for structural data., 24500111
01 Apr. 2012 - 31 Mar. 2016 - Compression-based self-organizing Recognizer Design
WATANABE Toshinori; KOGA Hisashi; CHO Daku
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), Traditional object recognition schemes have been the statistical one wherein target objects’ statistical models are prepared manually and applied to unknown task data. Due to the heavy human intervention, this approach becomes weak for multi-media data with variety of target objects. In this research, a new autonomous object model acquisition scheme is investigated. For this, we investigate the possibility of data’s compressibility vector as a general feature, the possibility of co-occurrence-based object discovery and the possibility of highly autonomous recognition scheme based oh them. Promising experimental results are reported., 22500122
2010 - 2012 - Algorithm Design Considering Interaction with External Inputs
KOGA Hisashi
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), We studied the two problems which arise in the environment where multiple computers interact with one another and designed effective algorithms for the problems. First, we constructed an algorithm which alleviates the throughput unfairness among different TCP connections. To deploy our algorithm, we have only to replace the operating systems in the end-hosts without modifying the routers. Next, we dealt with the similarity search in the distributed database composed by multiple computers and devised an algorithm which makes the query response shorter by 10% than the known simple method., 21500008
2009 - 2011 - Compression feature space based data mining and its application to web mining
WATANABE Toshinori; KOGA Hisashi; ZHANG Nuo; YOKOYAMA Takanori
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (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 - Fully automatic modeling of image-objects out of example images
WATANABE Toshinori; KOGA Hisashi; YOKOYAMA Takanori
Japan Society for the Promotion of Science, Grants-in-Aid for Scientific Research Grant-in-Aid for Scientific Research (C), The University of Electro-Communications, Grant-in-Aid for Scientific Research (C), The possibility of an automatic image-object modeling is studied and affirmative results are attained as follows. 1.Object model extraction out of still images Suppose we can compress the original image largely by giving a new name to a set of clustered color regions, we may consider the region set as an object. Using a few object plausibility measures side by side with this principle, we could succeed in extracting, fully automatically, structural descriptions of cartoons, faces, and playthings out of color images. The structural human model could also be extracted out of a still image made up of a few frames of a human walking video. 2.Object model extraction out of a video Se developed an algorithm composed of, the moving object extraction by background elimination, the border curve feature vector extraction, and the novelty analysis by voting from learned vectors to the incoming vector. Novel one is stored as a new model, otherwise only a model label (= recognition result) is output. Primitive human actions, i. e., walking and nodding, etc., could be extracted and used for further recognition in online real-time mode. 3.Additional outcome of 1. Finding a set of clustered color regions in a segmented image is one of the most important tasks in 1 above. We reduced this problem into a graph matching problem, i. e., a maximum clique problem and proposed two efficient algorithms to solve it, both exploiting graph attribute information. One uses them in the process of maximum clique search and the other uses them for original graph reduction. Both are effective, but the latter dominates the former. 4.Additional outcome of 2. The system in 2 above requires a melted video streams. So we need the decompression of a compressed video data. We examined a new possibility of video analysis directly in a compressed data domain and succeeded to track a walking person in MPEG compressed video., 17500061
2005 - 2006
Academic Contribution Activities
- 国際会議 IJCNN 2025 (International Joint Conference on Neural Networks ) Reviewer
Review, International Neural Network Society, 02 Feb. 2025 - 05 Mar. 2025 - DEIM2025 コメンテータ
Panel chair etc, 日本データベース学会, Dec. 2024 - Mar. 2025 - CANDAR2024 プログラム委員
Academic society etc, Review, 01 Aug. 2024 - 29 Dec. 2024 - DEIM2024コメンテータ
Academic society etc, Panel chair etc, 日本データベース学会, Dec. 2023 - Apr. 2024 - CANDAR2023 プログラム委員
Competition etc, Review, Aug. 2023 - Dec. 2023
