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