trunk/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.utils.*;\r
  30 \r
  31 class RleInfoStack extends NyObjectStack<RleInfoStack.RleInfo>\r
  32 {\r
  33         public class RleInfo\r
  34         {\r
  35                 //継承メンバ\r
  36                 public int entry_x; // フラグメントラベルの位置\r
  37                 public int area;\r
  38                 public int clip_r;\r
  39                 public int clip_l;\r
  40                 public int clip_b;\r
  41                 public int clip_t;\r
  42                 public long pos_x;\r
  43                 public long pos_y;              \r
  44         }       \r
  45         public RleInfoStack(int i_length)\r
  46         {\r
  47                 super(i_length, RleInfoStack.RleInfo.class);\r
  48                 return;\r
  49         }\r
  50 \r
  51         protected RleInfoStack.RleInfo createElement()\r
  52         {\r
  53                 return new RleInfoStack.RleInfo();\r
  54         }\r
  55 }\r
  56 /**\r
  57  * [strage class]\r
  58  */\r
  59 \r
  60 \r
  61 class RleElement\r
  62 {\r
  63         int l;\r
  64         int r;\r
  65         int fid;\r
  66         public static RleElement[] createArray(int i_length)\r
  67         {\r
  68                 RleElement[] ret = new RleElement[i_length];\r
  69                 for (int i = 0; i < i_length; i++) {\r
  70                         ret[i] = new RleElement();\r
  71                 }\r
  72                 return ret;\r
  73         }\r
  74 }\r
  75 \r
  76 \r
  77 // RleImageをラベリングする。\r
  78 public class NyARLabeling_Rle\r
  79 {\r
  80         private static final int AR_AREA_MAX = 100000;// #define AR_AREA_MAX 100000\r
  81         private static final int AR_AREA_MIN = 70;// #define AR_AREA_MIN 70\r
  82         \r
  83         private RleInfoStack _rlestack;\r
  84         private RleElement[] _rle1;\r
  85         private RleElement[] _rle2;\r
  86         private int _max_area;\r
  87         private int _min_area;\r
  88 \r
  89         public NyARLabeling_Rle(int i_width,int i_height)\r
  90         {\r
  91                 this._rlestack=new RleInfoStack(i_width*i_height*2048/(320*240)+32);\r
  92                 this._rle1 = RleElement.createArray(i_width/2+1);\r
  93                 this._rle2 = RleElement.createArray(i_width/2+1);\r
  94                 setAreaRange(AR_AREA_MAX,AR_AREA_MIN);\r
  95 \r
  96                 return;\r
  97         }\r
  98         /**\r
  99          * 対象サイズ\r
 100          * @param i_max\r
 101          * @param i_min\r
 102          */\r
 103         public void setAreaRange(int i_max,int i_min)\r
 104         {\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 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         private void addFragment(RleElement i_rel_img, int i_nof, int i_row_index,RleInfoStack o_stack) throws NyARException\r
 178         {\r
 179                 int l=i_rel_img.l;\r
 180                 final int len=i_rel_img.r - l;\r
 181                 i_rel_img.fid = i_nof;// REL毎の固有ID\r
 182                 RleInfoStack.RleInfo v = o_stack.prePush();\r
 183                 v.entry_x = l;\r
 184                 v.area =len;\r
 185                 v.clip_l=l;\r
 186                 v.clip_r=i_rel_img.r-1;\r
 187                 v.clip_t=i_row_index;\r
 188                 v.clip_b=i_row_index;\r
 189                 v.pos_x=(len*(2*l+(len-1)))/2;\r
 190                 v.pos_y=i_row_index*len;\r
 191 \r
 192                 return;\r
 193         }\r
 194         //所望のラスタからBIN-RLEに変換しながらの低速系も準備しようかな\r
 195         \r
 196         /**\r
 197          * 単一閾値を使ってGSラスタをBINラスタに変換しながらラベリングします。\r
 198          * @param i_gs_raster\r
 199          * @param i_top\r
 200          * @param i_bottom\r
 201          * @param o_stack\r
 202          * @return\r
 203          * @throws NyARException\r
 204          */\r
 205         public int labeling(NyARBinRaster i_bin_raster, int i_top, int i_bottom,RleLabelFragmentInfoStack o_stack) throws NyARException\r
 206         {\r
 207                 return this.imple_labeling(i_bin_raster,0,i_top,i_bottom,o_stack);\r
 208         }\r
 209         /**\r
 210          * BINラスタをラベリングします。\r
 211          * @param i_gs_raster\r
 212          * @param i_th\r
 213          * 画像を２値化するための閾値。暗点<=th<明点となります。\r
 214          * @param i_top\r
 215          * @param i_bottom\r
 216          * @param o_stack\r
 217          * @return\r
 218          * @throws NyARException\r
 219          */\r
 220         public int labeling(NyARGrayscaleRaster i_gs_raster,int i_th, int i_top, int i_bottom,RleLabelFragmentInfoStack o_stack) throws NyARException\r
 221         {\r
 222                 return this.imple_labeling(i_gs_raster,i_th,i_top,i_bottom,o_stack);\r
 223         }\r
 224         private int imple_labeling(INyARRaster i_raster,int i_th,int i_top, int i_bottom,RleLabelFragmentInfoStack o_stack) throws NyARException\r
 225         {\r
 226                 // リセット処理\r
 227                 final RleInfoStack rlestack=this._rlestack;\r
 228                 rlestack.clear();\r
 229 \r
 230                 //\r
 231                 RleElement[] rle_prev = this._rle1;\r
 232                 RleElement[] rle_current = this._rle2;\r
 233                 int len_prev = 0;\r
 234                 int len_current = 0;\r
 235                 final int width = i_raster.getWidth();\r
 236                 int[] in_buf = (int[]) i_raster.getBufferReader().getBuffer();\r
 237 \r
 238                 int id_max = 0;\r
 239                 int label_count=0;\r
 240                 // 初段登録\r
 241 \r
 242                 len_prev = toRel(in_buf, i_top, width, rle_prev,i_th);\r
 243                 for (int i = 0; i < len_prev; i++) {\r
 244                         // フラグメントID=フラグメント初期値、POS=Y値、RELインデクス=行\r
 245                         addFragment(rle_prev[i], id_max, i_top,rlestack);\r
 246                         id_max++;\r
 247                         // nofの最大値チェック\r
 248                         label_count++;\r
 249                 }\r
 250                 RleInfoStack.RleInfo[] f_array = rlestack.getArray();\r
 251                 // 次段結合\r
 252                 for (int y = i_top + 1; y < i_bottom; y++) {\r
 253                         // カレント行の読込\r
 254                         len_current = toRel(in_buf, y * width, width, rle_current,i_th);\r
 255                         int index_prev = 0;\r
 256 \r
 257                         SCAN_CUR: for (int i = 0; i < len_current; i++) {\r
 258                                 // index_prev,len_prevの位置を調整する\r
 259                                 int id = -1;\r
 260                                 // チェックすべきprevがあれば確認\r
 261                                 SCAN_PREV: while (index_prev < len_prev) {\r
 262                                         if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 263                                                 // prevがcurの左方にある→次のフラグメントを探索\r
 264                                                 index_prev++;\r
 265                                                 continue;\r
 266                                         } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 267                                                 // prevがcur右方にある→独立フラグメント\r
 268                                                 addFragment(rle_current[i], id_max, y,rlestack);\r
 269                                                 id_max++;\r
 270                                                 label_count++;\r
 271                                                 // 次のindexをしらべる\r
 272                                                 continue SCAN_CUR;\r
 273                                         }\r
 274                                         id=rle_prev[index_prev].fid;//ルートフラグメントid\r
 275                                         RleInfoStack.RleInfo id_ptr = f_array[id];\r
 276                                         //結合対象(初回)->prevのIDをコピーして、ルートフラグメントの情報を更新\r
 277                                         rle_current[i].fid = id;//フラグメントIDを保存\r
 278                                         //\r
 279                                         final int l= rle_current[i].l;\r
 280                                         final int r= rle_current[i].r;\r
 281                                         final int len=r-l;\r
 282                                         //結合先フラグメントの情報を更新する。\r
 283                                         id_ptr.area += len;\r
 284                                         //tとentry_xは、結合先のを使うので更新しない。\r
 285                                         id_ptr.clip_l=l<id_ptr.clip_l?l:id_ptr.clip_l;\r
 286                                         id_ptr.clip_r=r>id_ptr.clip_r?r-1:id_ptr.clip_r;\r
 287                                         id_ptr.clip_b=y;\r
 288                                         id_ptr.pos_x+=(len*(2*l+(len-1)))/2;\r
 289                                         id_ptr.pos_y+=y*len;\r
 290                                         //多重結合の確認（２個目以降）\r
 291                                         index_prev++;\r
 292                                         while (index_prev < len_prev) {\r
 293                                                 if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 294                                                         // prevがcurの左方にある→prevはcurに連結していない。\r
 295                                                         break SCAN_PREV;\r
 296                                                 } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 297                                                         // prevがcurの右方にある→prevはcurに連結していない。\r
 298                                                         index_prev--;\r
 299                                                         continue SCAN_CUR;\r
 300                                                 }\r
 301                                                 // prevとcurは連結している→ルートフラグメントの統合\r
 302                                                 \r
 303                                                 //結合するルートフラグメントを取得\r
 304                                                 final int prev_id =rle_prev[index_prev].fid;\r
 305                                                 RleInfoStack.RleInfo prev_ptr = f_array[prev_id];\r
 306                                                 if (id != prev_id){\r
 307                                                         label_count--;\r
 308                                                         //prevとcurrentのフラグメントidを書き換える。\r
 309                                                         for(int i2=index_prev;i2<len_prev;i2++){\r
 310                                                                 //prevは現在のidから最後まで\r
 311                                                                 if(rle_prev[i2].fid==prev_id){\r
 312                                                                         rle_prev[i2].fid=id;\r
 313                                                                 }\r
 314                                                         }\r
 315                                                         for(int i2=0;i2<i;i2++){\r
 316                                                                 //currentは0から現在-1まで\r
 317                                                                 if(rle_current[i2].fid==prev_id){\r
 318                                                                         rle_current[i2].fid=id;\r
 319                                                                 }\r
 320                                                         }\r
 321                                                         \r
 322                                                         //現在のルートフラグメントに情報を集約\r
 323                                                         id_ptr.area +=prev_ptr.area;\r
 324                                                         id_ptr.pos_x+=prev_ptr.pos_x;\r
 325                                                         id_ptr.pos_y+=prev_ptr.pos_y;\r
 326                                                         //tとentry_xの決定\r
 327                                                         if (id_ptr.clip_t > prev_ptr.clip_t) {\r
 328                                                                 // 現在の方が下にある。\r
 329                                                                 id_ptr.clip_t = prev_ptr.clip_t;\r
 330                                                                 id_ptr.entry_x = prev_ptr.entry_x;\r
 331                                                         }else if (id_ptr.clip_t < prev_ptr.clip_t) {\r
 332                                                                 // 現在の方が上にある。prevにフィードバック\r
 333                                                         } else {\r
 334                                                                 // 水平方向で小さい方がエントリポイント。\r
 335                                                                 if (id_ptr.entry_x > prev_ptr.entry_x) {\r
 336                                                                         id_ptr.entry_x = prev_ptr.entry_x;\r
 337                                                                 }else{\r
 338                                                                 }\r
 339                                                         }\r
 340                                                         //lの決定\r
 341                                                         if (id_ptr.clip_l > prev_ptr.clip_l) {\r
 342                                                                 id_ptr.clip_l=prev_ptr.clip_l;\r
 343                                                         }else{\r
 344                                                         }\r
 345                                                         //rの決定\r
 346                                                         if (id_ptr.clip_r < prev_ptr.clip_r) {\r
 347                                                                 id_ptr.clip_r=prev_ptr.clip_r;\r
 348                                                         }else{\r
 349                                                         }\r
 350                                                         //bの決定\r
 351 \r
 352                                                         //結合済のルートフラグメントを無効化する。\r
 353                                                         prev_ptr.area=0;\r
 354                                                 }\r
 355 \r
 356 \r
 357                                                 index_prev++;\r
 358                                         }\r
 359                                         index_prev--;\r
 360                                         break;\r
 361                                 }\r
 362                                 // curにidが割り当てられたかを確認\r
 363                                 // 右端独立フラグメントを追加\r
 364                                 if (id < 0){\r
 365                                         addFragment(rle_current[i], id_max, y,rlestack);\r
 366                                         id_max++;\r
 367                                         label_count++;\r
 368                                 }\r
 369                         }\r
 370                         // prevとrelの交換\r
 371                         RleElement[] tmp = rle_prev;\r
 372                         rle_prev = rle_current;\r
 373                         len_prev = len_current;\r
 374                         rle_current = tmp;\r
 375                 }\r
 376                 //対象のラベルだけ転写\r
 377                 o_stack.reserv(label_count);\r
 378                 RleLabelFragmentInfoStack.RleLabelFragmentInfo[] o_dest_array=o_stack.getArray();\r
 379                 final int max=this._max_area;\r
 380                 final int min=this._min_area;\r
 381                 int active_labels=0;\r
 382                 for(int i=id_max-1;i>=0;i--){\r
 383                         final int area=f_array[i].area;\r
 384                         if(area<min || area>max){//対象外のエリア0のもminではじく\r
 385                                 continue;\r
 386                         }\r
 387                         //\r
 388                         final RleInfoStack.RleInfo src_info=f_array[i];\r
 389                         final RleLabelFragmentInfoStack.RleLabelFragmentInfo dest_info=o_dest_array[active_labels];\r
 390                         dest_info.area=area;\r
 391                         dest_info.clip_b=src_info.clip_b;\r
 392                         dest_info.clip_r=src_info.clip_r;\r
 393                         dest_info.clip_t=src_info.clip_t;\r
 394                         dest_info.clip_l=src_info.clip_l;\r
 395                         dest_info.entry_x=src_info.entry_x;\r
 396                         dest_info.pos_x=src_info.pos_x/src_info.area;\r
 397                         dest_info.pos_y=src_info.pos_y/src_info.area;\r
 398                         active_labels++;\r
 399                 }\r
 400                 //ラベル数を再設定\r
 401                 o_stack.pops(label_count-active_labels);\r
 402                 //ラベル数を返却\r
 403                 return active_labels;\r
 404         }       \r
 405 }\r
 406 \r
 407 \r
 408 \r