lib/src/jp/nyatla/nyartoolkit/core/labeling/rlelabeling/NyARLabeling_Rle.java

   1 /* \r
   2  * PROJECT: NyARToolkit(Extension)\r
   3  * --------------------------------------------------------------------------------\r
   4  * The NyARToolkit is Java edition ARToolKit class library.\r
   5  * Copyright (C)2008-2009 Ryo Iizuka\r
   6  *\r
   7  * This program is free software: you can redistribute it and/or modify\r
   8  * it under the terms of the GNU General Public License as published by\r
   9  * the Free Software Foundation, either version 3 of the License, or\r
  10  * (at your option) any later version.\r
  11  * \r
  12  * This program is distributed in the hope that it will be useful,\r
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  15  * GNU General Public License for more details.\r
  16  *\r
  17  * You should have received a copy of the GNU General Public License\r
  18  * along with this program.  If not, see <http://www.gnu.org/licenses/>.\r
  19  * \r
  20  * For further information please contact.\r
  21  *      http://nyatla.jp/nyatoolkit/\r
  22  *      <airmail(at)ebony.plala.or.jp> or <nyatla(at)nyatla.jp>\r
  23  * \r
  24  */\r
  25 package jp.nyatla.nyartoolkit.core.labeling.rlelabeling;\r
  26 \r
  27 import jp.nyatla.nyartoolkit.NyARException;\r
  28 import jp.nyatla.nyartoolkit.core.raster.*;\r
  29 import jp.nyatla.nyartoolkit.core.types.*;\r
  30 import jp.nyatla.nyartoolkit.core.types.stack.NyARObjectStack;\r
  31 \r
  32 \r
  33 \r
  34 \r
  35 /**\r
  36  * このクラスは、RLE圧縮を利用した輪郭線エントリポイント検出用のラべリングクラスです。\r
  37  * ラべリング画像を生成せずに、ラベル輪郭へのエントリーポイントの一覧を作ることに注意してください。\r
  38  * <p>コールバック関数\r
  39  * このクラスはいくつかの自己コールバック関数を持つ抽象クラスです。継承クラスでコールバック関数を実装して使います。\r
  40  * <ul>\r
  41  * <li>{@link #onLabelFound}- {@link #labeling}関数が検出したラベルを通知するコールバック関数です。\r
  42  * ここに、発見したラベルを処理するコードを書きます。\r
  43  * </ul>\r
  44  * </p>\r
  45  * <p>ラベル輪郭のエントリーポイント -\r
  46  * このエントリポイントは、ラベルを構成する塊の輪郭を指す１点です。ここから８方位輪郭検出を実行すると、\r
  47  * ラベルの輪郭を一周することができます。\r
  48  * </p>\r
  49  * <p>入力できる画素形式 -\r
  50  * <p>{@link NyARBinRaster}を入力する場合\r
  51  * <ul>\r
  52  * <li>{@link NyARBufferType#INT1D_BIN_8}\r
  53  * </ul>\r
  54  * </p>\r
  55  * <p>{@link NyARGrayscaleRaster}を入力する場合\r
  56  * <ul>\r
  57  * <li>{@link NyARBufferType#INT1D_GRAY_8}\r
  58  * </ul>\r
  59  * </p>\r
  60  * </p>\r
  61  */\r
  62 public abstract class NyARLabeling_Rle\r
  63 {\r
  64         private static final int AR_AREA_MAX = 100000;// #define AR_AREA_MAX 100000\r
  65         private static final int AR_AREA_MIN = 70;// #define AR_AREA_MIN 70\r
  66         \r
  67         private RleInfoStack _rlestack;\r
  68         private RleElement[] _rle1;\r
  69         private RleElement[] _rle2;\r
  70         private int _max_area;\r
  71         private int _min_area;\r
  72         /** 入力ラスタのサイズ*/\r
  73         protected NyARIntSize _raster_size=new NyARIntSize();\r
  74         /**\r
  75          * コンストラクタです。{@link #labeling}に入力するラスタのサイズを指定して、インスタンスを生成します。\r
  76          * @param i_width\r
  77          * 入力画像の幅\r
  78          * @param i_height\r
  79          * 入力画像の高さ\r
  80          * @throws NyARException\r
  81          */\r
  82         public NyARLabeling_Rle(int i_width,int i_height) throws NyARException\r
  83         {\r
  84                 this._raster_size.setValue(i_width,i_height);\r
  85                 this._rlestack=new RleInfoStack(i_width*i_height*2048/(320*240)+32);\r
  86                 this._rle1 = RleElement.createArray(i_width/2+1);\r
  87                 this._rle2 = RleElement.createArray(i_width/2+1);\r
  88                 this._max_area=AR_AREA_MAX;\r
  89                 this._min_area=AR_AREA_MIN;\r
  90 \r
  91                 return;\r
  92         }\r
  93         /**\r
  94          * 検出するラベルのエリア（画素数）範囲を設定します。\r
  95          * この範囲にあるラベルのみが、結果に返されます。\r
  96          * 初期値は、{@link #AR_AREA_MAX},{@link #AR_AREA_MIN}です。\r
  97          * @param i_max\r
  98          * エリアの最大値を指定します。\r
  99          * @param i_min\r
 100          * エリアの最小値を指定します。\r
 101          */\r
 102         public void setAreaRange(int i_max,int i_min)\r
 103         {\r
 104                 assert(i_min>0 && i_max>i_min);\r
 105                 this._max_area=i_max;\r
 106                 this._min_area=i_min;\r
 107                 return;\r
 108         }\r
 109 \r
 110         /**\r
 111          * i_bin_bufのgsイメージをREL圧縮する。\r
 112          * @param i_bin_buf\r
 113          * @param i_st\r
 114          * @param i_len\r
 115          * @param i_out\r
 116          * @param i_th\r
 117          * BINラスタのときは0,GSラスタの時は閾値を指定する。\r
 118          * この関数は、閾値を暗点と認識します。\r
 119          * 暗点<=th<明点\r
 120          * @return\r
 121          */\r
 122         private final int toRel(int[] i_bin_buf, int i_st, int i_len, RleElement[] i_out,int i_th)\r
 123         {\r
 124                 int current = 0;\r
 125                 int r = -1;\r
 126                 // 行確定開始\r
 127                 int x = i_st;\r
 128                 final int right_edge = i_st + i_len - 1;\r
 129                 while (x < right_edge) {\r
 130                         // 暗点(0)スキャン\r
 131                         if (i_bin_buf[x] > i_th) {\r
 132                                 x++;//明点\r
 133                                 continue;\r
 134                         }\r
 135                         // 暗点発見→暗点長を調べる\r
 136                         r = (x - i_st);\r
 137                         i_out[current].l = r;\r
 138                         r++;// 暗点+1\r
 139                         x++;\r
 140                         while (x < right_edge) {\r
 141                                 if (i_bin_buf[x] > i_th) {\r
 142                                         // 明点(1)→暗点(0)配列終了>登録\r
 143                                         i_out[current].r = r;\r
 144                                         current++;\r
 145                                         x++;// 次点の確認。\r
 146                                         r = -1;// 右端の位置を0に。\r
 147                                         break;\r
 148                                 } else {\r
 149                                         // 暗点(0)長追加\r
 150                                         r++;\r
 151                                         x++;\r
 152                                 }\r
 153                         }\r
 154                 }\r
 155                 // 最後の1点だけ判定方法が少し違うの。\r
 156                 if (i_bin_buf[x] > i_th) {\r
 157                         // 明点→rカウント中なら暗点配列終了>登録\r
 158                         if (r >= 0) {\r
 159                                 i_out[current].r = r;\r
 160                                 current++;\r
 161                         }\r
 162                 } else {\r
 163                         // 暗点→カウント中でなければl1で追加\r
 164                         if (r >= 0) {\r
 165                                 i_out[current].r = (r + 1);\r
 166                         } else {\r
 167                                 // 最後の1点の場合\r
 168                                 i_out[current].l = (i_len - 1);\r
 169                                 i_out[current].r = (i_len);\r
 170                         }\r
 171                         current++;\r
 172                 }\r
 173                 // 行確定\r
 174                 return current;\r
 175         }\r
 176         /**\r
 177          * フラグメントをRLEスタックへ追加する。\r
 178          * @param i_rel_img\r
 179          * @param i_nof\r
 180          * @param i_row_index\r
 181          * @param o_stack\r
 182          * @return\r
 183          * @throws NyARException\r
 184          */\r
 185         private final boolean addFragment(RleElement i_rel_img, int i_nof, int i_row_index,RleInfoStack o_stack) throws NyARException\r
 186         {\r
 187                 int l=i_rel_img.l;\r
 188                 final int len=i_rel_img.r - l;\r
 189                 i_rel_img.fid = i_nof;// REL毎の固有ID\r
 190                 NyARRleLabelFragmentInfo v = o_stack.prePush();\r
 191                 if(v==null){\r
 192                         System.err.println("addFragment force recover!");\r
 193                         return false;\r
 194                 }\r
 195                 v.entry_x = l;\r
 196                 v.area =len;\r
 197                 v.clip_l=l;\r
 198                 v.clip_r=i_rel_img.r-1;\r
 199                 v.clip_t=i_row_index;\r
 200                 v.clip_b=i_row_index;\r
 201                 v.pos_x=(len*(2*l+(len-1)))/2;\r
 202                 v.pos_y=i_row_index*len;\r
 203 \r
 204                 return true;\r
 205         }\r
 206         /**\r
 207          * この関数は、2値イメージの{@link NyARBinRaster}ラスタをラベリングします。\r
 208          * 検出したラベルは、自己コールバック関数{@link #onLabelFound}で通知します。\r
 209          * @param i_bin_raster\r
 210          * 入力画像。対応する形式は、クラスの説明を参照してください。\r
 211          * @throws NyARException\r
 212          */\r
 213         public void labeling(NyARBinRaster i_bin_raster) throws NyARException\r
 214         {\r
 215                 assert(i_bin_raster.isEqualBufferType(NyARBufferType.INT1D_BIN_8));\r
 216                 NyARIntSize size=i_bin_raster.getSize();\r
 217                 this.imple_labeling(i_bin_raster,0,0,0,size.w,size.h);\r
 218         }\r
 219         /**\r
 220          * この関数は、2値イメージの{@link NyARBinRaster}ラスタの指定範囲をラベリングします。\r
 221          * 検出したラベルは、自己コールバック関数{@link #onLabelFound}で通知します。\r
 222          * @param i_bin_raster\r
 223          * 入力画像。対応する形式は、クラスの説明を参照してください。\r
 224          * @param i_area\r
 225          * ラべリングする画像内の範囲\r
 226          * @throws NyARException\r
 227          */\r
 228         public void labeling(NyARBinRaster i_bin_raster,NyARIntRect i_area) throws NyARException\r
 229         {\r
 230                 assert(i_bin_raster.isEqualBufferType(NyARBufferType.INT1D_BIN_8));\r
 231                 this.imple_labeling(i_bin_raster,0,i_area.x,i_area.y,i_area.w,i_area.h);\r
 232         }\r
 233         /**\r
 234          * この関数は、2値イメージの{@link NyARBinRaster}ラスタをラベリングします。\r
 235          * 検出したラベルは、自己コールバック関数{@link #onLabelFound}で通知します。\r
 236          * @param i_gs_raster\r
 237          * 入力画像。対応する形式は、クラスの説明を参照してください。\r
 238          * @param i_th\r
 239          * 暗点を判定するための敷居値0から255の数値である事。\r
 240          * @throws NyARException\r
 241          */\r
 242         public void labeling(NyARGrayscaleRaster i_gs_raster,int i_th) throws NyARException\r
 243         {\r
 244                 assert(i_gs_raster.isEqualBufferType(NyARBufferType.INT1D_GRAY_8));\r
 245                 NyARIntSize size=i_gs_raster.getSize();\r
 246                 this.imple_labeling(i_gs_raster,i_th,0,0,size.w,size.h);\r
 247         }\r
 248         /**\r
 249          * この関数は、2値イメージの{@link NyARBinRaster}ラスタの指定範囲をラベリングします。\r
 250          * 検出したラベルは、自己コールバック関数{@link #onLabelFound}で通知します。\r
 251          * @param i_gs_raster\r
 252          * 入力画像。対応する形式は、クラスの説明を参照してください。\r
 253          * @param i_area\r
 254          * ラべリングする画像内の範囲\r
 255          * @param i_th\r
 256          * 暗点を判定するための敷居値0から255の数値である事。\r
 257          * @throws NyARException\r
 258          */\r
 259         public void labeling(NyARGrayscaleRaster i_gs_raster,NyARIntRect i_area,int i_th) throws NyARException\r
 260         {\r
 261                 assert(i_gs_raster.isEqualBufferType(NyARBufferType.INT1D_GRAY_8));\r
 262                 this.imple_labeling(i_gs_raster,i_th,i_area.x,i_area.y,i_area.w,i_area.h);\r
 263         }\r
 264         private void imple_labeling(INyARRaster i_raster,int i_th,int i_left,int i_top,int i_width, int i_height) throws NyARException\r
 265         {\r
 266                 //ラスタのサイズを確認\r
 267                 assert(i_raster.getSize().isEqualSize(this._raster_size));\r
 268                 \r
 269                 RleElement[] rle_prev = this._rle1;\r
 270                 RleElement[] rle_current = this._rle2;\r
 271                 // リセット処理\r
 272                 final RleInfoStack rlestack=this._rlestack;\r
 273                 rlestack.clear();\r
 274 \r
 275                 //\r
 276                 int len_prev = 0;\r
 277                 int len_current = 0;\r
 278                 final int bottom=i_top+i_height;\r
 279                 final int row_stride=this._raster_size.w;\r
 280                 int[] in_buf = (int[]) i_raster.getBuffer();\r
 281 \r
 282                 int id_max = 0;\r
 283                 int label_count=0;\r
 284                 int rle_top_index=i_left+row_stride*i_top;\r
 285                 // 初段登録\r
 286 \r
 287                 len_prev = toRel(in_buf, rle_top_index, i_width, rle_prev,i_th);\r
 288                 for (int i = 0; i < len_prev; i++) {\r
 289                         // フラグメントID=フラグメント初期値、POS=Y値、RELインデクス=行\r
 290                         if(addFragment(rle_prev[i], id_max, i_top,rlestack)){\r
 291                                 id_max++;\r
 292                                 // nofの最大値チェック\r
 293                                 label_count++;\r
 294                         }\r
 295                 }\r
 296                 NyARRleLabelFragmentInfo[] f_array = rlestack.getArray();\r
 297                 // 次段結合\r
 298                 for (int y = i_top + 1; y < bottom; y++) {\r
 299                         // カレント行の読込\r
 300                         rle_top_index+=row_stride;\r
 301                         len_current = toRel(in_buf,rle_top_index, i_width, rle_current,i_th);\r
 302                         int index_prev = 0;\r
 303 \r
 304                         SCAN_CUR: for (int i = 0; i < len_current; i++) {\r
 305                                 // index_prev,len_prevの位置を調整する\r
 306                                 int id = -1;\r
 307                                 // チェックすべきprevがあれば確認\r
 308                                 SCAN_PREV: while (index_prev < len_prev) {\r
 309                                         if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 310                                                 // prevがcurの左方にある→次のフラグメントを探索\r
 311                                                 index_prev++;\r
 312                                                 continue;\r
 313                                         } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 314                                                 // prevがcur右方にある→独立フラグメント\r
 315                                                 if(addFragment(rle_current[i], id_max, y,rlestack)){\r
 316                                                         id_max++;\r
 317                                                         label_count++;\r
 318                                                 }\r
 319                                                 // 次のindexをしらべる\r
 320                                                 continue SCAN_CUR;\r
 321                                         }\r
 322                                         id=rle_prev[index_prev].fid;//ルートフラグメントid\r
 323                                         NyARRleLabelFragmentInfo id_ptr = f_array[id];\r
 324                                         //結合対象(初回)->prevのIDをコピーして、ルートフラグメントの情報を更新\r
 325                                         rle_current[i].fid = id;//フラグメントIDを保存\r
 326                                         //\r
 327                                         final int l= rle_current[i].l;\r
 328                                         final int r= rle_current[i].r;\r
 329                                         final int len=r-l;\r
 330                                         //結合先フラグメントの情報を更新する。\r
 331                                         id_ptr.area += len;\r
 332                                         //tとentry_xは、結合先のを使うので更新しない。\r
 333                                         id_ptr.clip_l=l<id_ptr.clip_l?l:id_ptr.clip_l;\r
 334                                         id_ptr.clip_r=r>id_ptr.clip_r?r-1:id_ptr.clip_r;\r
 335                                         id_ptr.clip_b=y;\r
 336                                         id_ptr.pos_x+=(len*(2*l+(len-1)))/2;\r
 337                                         id_ptr.pos_y+=y*len;\r
 338                                         //多重結合の確認（２個目以降）\r
 339                                         index_prev++;\r
 340                                         while (index_prev < len_prev) {\r
 341                                                 if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 342                                                         // prevがcurの左方にある→prevはcurに連結していない。\r
 343                                                         break SCAN_PREV;\r
 344                                                 } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 345                                                         // prevがcurの右方にある→prevはcurに連結していない。\r
 346                                                         index_prev--;\r
 347                                                         continue SCAN_CUR;\r
 348                                                 }\r
 349                                                 // prevとcurは連結している→ルートフラグメントの統合\r
 350                                                 \r
 351                                                 //結合するルートフラグメントを取得\r
 352                                                 final int prev_id =rle_prev[index_prev].fid;\r
 353                                                 NyARRleLabelFragmentInfo prev_ptr = f_array[prev_id];\r
 354                                                 if (id != prev_id){\r
 355                                                         label_count--;\r
 356                                                         //prevとcurrentのフラグメントidを書き換える。\r
 357                                                         for(int i2=index_prev;i2<len_prev;i2++){\r
 358                                                                 //prevは現在のidから最後まで\r
 359                                                                 if(rle_prev[i2].fid==prev_id){\r
 360                                                                         rle_prev[i2].fid=id;\r
 361                                                                 }\r
 362                                                         }\r
 363                                                         for(int i2=0;i2<i;i2++){\r
 364                                                                 //currentは0から現在-1まで\r
 365                                                                 if(rle_current[i2].fid==prev_id){\r
 366                                                                         rle_current[i2].fid=id;\r
 367                                                                 }\r
 368                                                         }\r
 369                                                         \r
 370                                                         //現在のルートフラグメントに情報を集約\r
 371                                                         id_ptr.area +=prev_ptr.area;\r
 372                                                         id_ptr.pos_x+=prev_ptr.pos_x;\r
 373                                                         id_ptr.pos_y+=prev_ptr.pos_y;\r
 374                                                         //tとentry_xの決定\r
 375                                                         if (id_ptr.clip_t > prev_ptr.clip_t) {\r
 376                                                                 // 現在の方が下にある。\r
 377                                                                 id_ptr.clip_t = prev_ptr.clip_t;\r
 378                                                                 id_ptr.entry_x = prev_ptr.entry_x;\r
 379                                                         }else if (id_ptr.clip_t < prev_ptr.clip_t) {\r
 380                                                                 // 現在の方が上にある。prevにフィードバック\r
 381                                                         } else {\r
 382                                                                 // 水平方向で小さい方がエントリポイント。\r
 383                                                                 if (id_ptr.entry_x > prev_ptr.entry_x) {\r
 384                                                                         id_ptr.entry_x = prev_ptr.entry_x;\r
 385                                                                 }else{\r
 386                                                                 }\r
 387                                                         }\r
 388                                                         //lの決定\r
 389                                                         if (id_ptr.clip_l > prev_ptr.clip_l) {\r
 390                                                                 id_ptr.clip_l=prev_ptr.clip_l;\r
 391                                                         }else{\r
 392                                                         }\r
 393                                                         //rの決定\r
 394                                                         if (id_ptr.clip_r < prev_ptr.clip_r) {\r
 395                                                                 id_ptr.clip_r=prev_ptr.clip_r;\r
 396                                                         }else{\r
 397                                                         }\r
 398                                                         //bの決定\r
 399 \r
 400                                                         //結合済のルートフラグメントを無効化する。\r
 401                                                         prev_ptr.area=0;\r
 402                                                 }\r
 403 \r
 404 \r
 405                                                 index_prev++;\r
 406                                         }\r
 407                                         index_prev--;\r
 408                                         break;\r
 409                                 }\r
 410                                 // curにidが割り当てられたかを確認\r
 411                                 // 右端独立フラグメントを追加\r
 412                                 if (id < 0){\r
 413                                         if(addFragment(rle_current[i], id_max, y,rlestack)){\r
 414                                                 id_max++;\r
 415                                                 label_count++;\r
 416                                         }\r
 417                                 }\r
 418                         }\r
 419                         // prevとrelの交換\r
 420                         RleElement[] tmp = rle_prev;\r
 421                         rle_prev = rle_current;\r
 422                         len_prev = len_current;\r
 423                         rle_current = tmp;\r
 424                 }\r
 425                 //対象のラベルだけを追記\r
 426                 final int max=this._max_area;\r
 427                 final int min=this._min_area;\r
 428                 for(int i=id_max-1;i>=0;i--){\r
 429                         final NyARRleLabelFragmentInfo src_info=f_array[i];\r
 430                         final int area=src_info.area;\r
 431                         if(area<min || area>max){//対象外のエリア0のもminではじく\r
 432                                 continue;\r
 433                         }\r
 434                         //値を相対位置に補正\r
 435                         src_info.clip_l+=i_left;\r
 436                         src_info.clip_r+=i_left;\r
 437                         src_info.entry_x+=i_left;\r
 438                         src_info.pos_x/=area;\r
 439                         src_info.pos_y/=area;\r
 440                         //コールバック関数コール\r
 441                         this.onLabelFound(src_info);\r
 442                 }\r
 443         }\r
 444         /**\r
 445          * この仮想関数は自己コールバック関数です。\r
 446          * {@link #labeling}関数が、検出したラベルを通知するために使います。\r
 447          * @param i_ref_label\r
 448          * 検出したラベルを格納したオブジェクト。値の有効期間は、次の{@link #labeling}が実行されるまでです。\r
 449          * (注)この仕様は変わるかもしれません。\r
 450          * @throws NyARException\r
 451          */\r
 452 \r
 453         protected abstract void onLabelFound(NyARRleLabelFragmentInfo i_ref_label) throws NyARException;\r
 454         \r
 455         /**\r
 456          * クラスの仕様確認フラグです。ラベル配列の参照アクセスが可能かを返します。\r
 457          * このクラスでは、true固定です。\r
 458          */\r
 459         public final static boolean _sf_label_array_safe_reference=true;\r
 460 }\r
 461 \r
 462 /**\r
 463  * このクラスは、{@link NyARLabeling_Rle}が内部的に使うRLEスタックです。\r
 464  * ユーザが使うことはありません。\r
 465  */\r
 466 class RleInfoStack extends NyARObjectStack<NyARRleLabelFragmentInfo>\r
 467 {       \r
 468         public RleInfoStack(int i_length) throws NyARException\r
 469         {\r
 470                 super();\r
 471                 super.initInstance(i_length, NyARRleLabelFragmentInfo.class);\r
 472                 return;\r
 473         }\r
 474 \r
 475         protected NyARRleLabelFragmentInfo createElement()\r
 476         {\r
 477                 return new NyARRleLabelFragmentInfo();\r
 478         }\r
 479 }\r
 480 /**\r
 481  * このクラスは、{@link #RleInfoStack}の要素です。\r
 482  * RLEフラグメントのパラメータを保持します。\r
 483  * ユーザが使うことはありません。\r
 484  */\r
 485 class RleElement\r
 486 {\r
 487         int l;\r
 488         int r;\r
 489         int fid;\r
 490         public static RleElement[] createArray(int i_length)\r
 491         {\r
 492                 RleElement[] ret = new RleElement[i_length];\r
 493                 for (int i = 0; i < i_length; i++) {\r
 494                         ret[i] = new RleElement();\r
 495                 }\r
 496                 return ret;\r
 497         }\r
 498 }\r
 499 \r