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

   1 /* このソースは実験用のソースです。\r
   2  * 動いたり動かなかったりします。\r
   3  * \r
   4  */\r
   5 package jp.nyatla.nyartoolkit.core.labeling.rlelabeling;\r
   6 \r
   7 import jp.nyatla.nyartoolkit.NyARException;\r
   8 import jp.nyatla.nyartoolkit.core.raster.*;\r
   9 \r
  10 \r
  11 \r
  12 /**\r
  13  * [strage class]\r
  14  */\r
  15 \r
  16 \r
  17 class RleElement\r
  18 {\r
  19         int l;\r
  20         int r;\r
  21         int fid;\r
  22         public static RleElement[] createArray(int i_length)\r
  23         {\r
  24                 RleElement[] ret = new RleElement[i_length];\r
  25                 for (int i = 0; i < i_length; i++) {\r
  26                         ret[i] = new RleElement();\r
  27                 }\r
  28                 return ret;\r
  29         }\r
  30 }\r
  31 \r
  32 // RleImageをラベリングする。\r
  33 public class NyARLabeling_Rle\r
  34 {\r
  35         private RleElement[] _rle1;\r
  36 \r
  37         private RleElement[] _rle2;\r
  38 \r
  39         public NyARLabeling_Rle(int i_width)\r
  40         {\r
  41                 this._rle1 = RleElement.createArray(i_width/2+1);\r
  42                 this._rle2 = RleElement.createArray(i_width/2+1);\r
  43                 return;\r
  44         }\r
  45 \r
  46         /**\r
  47          * i_bin_bufのbinイメージをREL圧縮する。\r
  48          * \r
  49          * @param i_bin_raster\r
  50          */\r
  51         private int toRel(int[] i_bin_buf, int i_st, int i_len, RleElement[] i_out)\r
  52         {\r
  53                 int current = 0;\r
  54                 int r = -1;\r
  55                 // 行確定開始\r
  56                 int x = i_st;\r
  57                 final int right_edge = i_st + i_len - 1;\r
  58                 while (x < right_edge) {\r
  59                         // 暗点(0)スキャン\r
  60                         if (i_bin_buf[x] != 0) {\r
  61                                 x++;\r
  62                                 continue;\r
  63                         }\r
  64                         // 暗点発見→暗点長を調べる\r
  65                         r = (x - i_st);\r
  66                         i_out[current].l = r;\r
  67                         r++;// 暗点+1\r
  68                         x++;\r
  69                         while (x < right_edge) {\r
  70                                 if (i_bin_buf[x] != 0) {\r
  71                                         // 明点(1)→暗点(0)配列終了>登録\r
  72                                         i_out[current].r = r;\r
  73                                         current++;\r
  74                                         x++;// 次点の確認。\r
  75                                         r = -1;// 右端の位置を0に。\r
  76                                         break;\r
  77                                 } else {\r
  78                                         // 暗点(0)長追加\r
  79                                         r++;\r
  80                                         x++;\r
  81                                 }\r
  82                         }\r
  83                 }\r
  84                 // 最後の1点だけ判定方法が少し違うの。\r
  85                 if (i_bin_buf[x] != 0) {\r
  86                         // 明点→rカウント中なら暗点配列終了>登録\r
  87                         if (r >= 0) {\r
  88                                 i_out[current].r = r;\r
  89                                 current++;\r
  90                         }\r
  91                 } else {\r
  92                         // 暗点→カウント中でなければl1で追加\r
  93                         if (r >= 0) {\r
  94                                 i_out[current].r = (r + 1);\r
  95                         } else {\r
  96                                 // 最後の1点の場合\r
  97                                 i_out[current].l = (i_len - 1);\r
  98                                 i_out[current].r = (i_len);\r
  99                         }\r
 100                         current++;\r
 101                 }\r
 102                 // 行確定\r
 103                 return current;\r
 104         }\r
 105 \r
 106         private void addFragment(RleElement i_rel_img, int i_nof, int i_row_index, int i_rel_index,RleLabelFragmentInfoStack o_stack) throws NyARException\r
 107         {\r
 108                 int l=i_rel_img.l;\r
 109                 final int len=i_rel_img.r - l;\r
 110                 i_rel_img.fid = i_nof;// REL毎の固有ID\r
 111                 RleLabelFragmentInfoStack.RleLabelFragmentInfo v = o_stack.prePush();\r
 112                 v.entry_x = l;\r
 113                 v.area =len;\r
 114                 v.clip_l=l;\r
 115                 v.clip_r=i_rel_img.r-1;\r
 116                 v.clip_t=i_row_index;\r
 117                 v.clip_b=i_row_index;\r
 118                 v.pos_x+=(len*(2*l+(len-1)))/2;\r
 119                 v.pos_y+=i_row_index*len;\r
 120 \r
 121                 return;\r
 122         }\r
 123 \r
 124         //\r
 125         public int labeling(NyARBinRaster i_bin_raster, int i_top, int i_bottom,RleLabelFragmentInfoStack o_stack) throws NyARException\r
 126         {\r
 127                 // リセット処理\r
 128                 o_stack.clear();\r
 129                 //\r
 130                 RleElement[] rle_prev = this._rle1;\r
 131                 RleElement[] rle_current = this._rle2;\r
 132                 int len_prev = 0;\r
 133                 int len_current = 0;\r
 134                 final int width = i_bin_raster.getWidth();\r
 135                 int[] in_buf = (int[]) i_bin_raster.getBufferReader().getBuffer();\r
 136 \r
 137                 int id_max = 0;\r
 138                 int label_count=0;\r
 139                 // 初段登録\r
 140 \r
 141                 len_prev = toRel(in_buf, i_top, width, rle_prev);\r
 142                 for (int i = 0; i < len_prev; i++) {\r
 143                         // フラグメントID=フラグメント初期値、POS=Y値、RELインデクス=行\r
 144                         addFragment(rle_prev[i], id_max, i_top, i,o_stack);\r
 145                         id_max++;\r
 146                         // nofの最大値チェック\r
 147                         label_count++;\r
 148                 }\r
 149                 RleLabelFragmentInfoStack.RleLabelFragmentInfo[] f_array = o_stack.getArray();\r
 150                 // 次段結合\r
 151                 for (int y = i_top + 1; y < i_bottom; y++) {\r
 152                         // カレント行の読込\r
 153                         len_current = toRel(in_buf, y * width, width, rle_current);\r
 154                         int index_prev = 0;\r
 155 \r
 156                         SCAN_CUR: for (int i = 0; i < len_current; i++) {\r
 157                                 // index_prev,len_prevの位置を調整する\r
 158                                 int id = -1;\r
 159                                 // チェックすべきprevがあれば確認\r
 160                                 SCAN_PREV: while (index_prev < len_prev) {\r
 161                                         if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 162                                                 // prevがcurの左方にある→次のフラグメントを探索\r
 163                                                 index_prev++;\r
 164                                                 continue;\r
 165                                         } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 166                                                 // prevがcur右方にある→独立フラグメント\r
 167                                                 addFragment(rle_current[i], id_max, y, i,o_stack);\r
 168                                                 id_max++;\r
 169                                                 label_count++;\r
 170                                                 // 次のindexをしらべる\r
 171                                                 continue SCAN_CUR;\r
 172                                         }\r
 173                                         id=rle_prev[index_prev].fid;//ルートフラグメントid\r
 174                                         RleLabelFragmentInfoStack.RleLabelFragmentInfo id_ptr = f_array[id];\r
 175                                         //結合対象(初回)->prevのIDをコピーして、ルートフラグメントの情報を更新\r
 176                                         rle_current[i].fid = id;//フラグメントIDを保存\r
 177                                         //\r
 178                                         final int l= rle_current[i].l;\r
 179                                         final int r= rle_current[i].r;\r
 180                                         final int len=r-l;\r
 181                                         //結合先フラグメントの情報を更新する。\r
 182                                         id_ptr.area += len;\r
 183                                         //tとentry_xは、結合先のを使うので更新しない。\r
 184                                         id_ptr.clip_l=l<id_ptr.clip_l?l:id_ptr.clip_l;\r
 185                                         id_ptr.clip_r=r>id_ptr.clip_r?r-1:id_ptr.clip_r;\r
 186                                         id_ptr.clip_b=y;\r
 187                                         id_ptr.pos_x+=(len*(2*l+(len-1)))/2;\r
 188                                         id_ptr.pos_y+=y*len;\r
 189                                         //多重結合の確認（２個目以降）\r
 190                                         index_prev++;\r
 191                                         while (index_prev < len_prev) {\r
 192                                                 if (rle_current[i].l - rle_prev[index_prev].r > 0) {// 0なら8方位ラベリング\r
 193                                                         // prevがcurの左方にある→prevはcurに連結していない。\r
 194                                                         break SCAN_PREV;\r
 195                                                 } else if (rle_prev[index_prev].l - rle_current[i].r > 0) {// 0なら8方位ラベリングになる\r
 196                                                         // prevがcurの右方にある→prevはcurに連結していない。\r
 197                                                         index_prev--;\r
 198                                                         continue SCAN_CUR;\r
 199                                                 }\r
 200                                                 // prevとcurは連結している→ルートフラグメントの統合\r
 201                                                 \r
 202                                                 //結合するルートフラグメントを取得\r
 203                                                 final int prev_id =rle_prev[index_prev].fid;\r
 204                                                 RleLabelFragmentInfoStack.RleLabelFragmentInfo prev_ptr = f_array[prev_id];\r
 205                                                 if (id != prev_id){\r
 206                                                         if(prev_ptr.area==0){\r
 207                                                                 System.out.println("ERRRR");\r
 208                                                         }\r
 209                                                         label_count--;\r
 210                                                         //prevとcurrentのフラグメントidを書き換える。\r
 211                                                         for(int i2=index_prev;i2<len_prev;i2++){\r
 212                                                                 //prevは現在のidから最後まで\r
 213                                                                 if(rle_prev[i2].fid==prev_id){\r
 214                                                                         rle_prev[i2].fid=id;\r
 215                                                                 }\r
 216                                                         }\r
 217                                                         for(int i2=0;i2<i;i2++){\r
 218                                                                 //currentは0から現在-1まで\r
 219                                                                 if(rle_current[i2].fid==prev_id){\r
 220                                                                         rle_current[i2].fid=id;\r
 221                                                                 }\r
 222                                                         }\r
 223                                                         \r
 224                                                         //現在のルートフラグメントに情報を集約\r
 225                                                         id_ptr.area +=prev_ptr.area;\r
 226                                                         id_ptr.pos_x+=prev_ptr.pos_x;\r
 227                                                         id_ptr.pos_y+=prev_ptr.pos_y;\r
 228                                                         //tとentry_xの決定\r
 229                                                         if (id_ptr.clip_t > prev_ptr.clip_t) {\r
 230                                                                 // 現在の方が下にある。\r
 231                                                                 id_ptr.clip_t = prev_ptr.clip_t;\r
 232                                                                 id_ptr.entry_x = prev_ptr.entry_x;\r
 233                                                         }else if (id_ptr.clip_t < prev_ptr.clip_t) {\r
 234                                                                 // 現在の方が上にある。prevにフィードバック\r
 235                                                         } else {\r
 236                                                                 // 水平方向で小さい方がエントリポイント。\r
 237                                                                 if (id_ptr.entry_x > prev_ptr.entry_x) {\r
 238                                                                         id_ptr.entry_x = prev_ptr.entry_x;\r
 239                                                                 }else{\r
 240                                                                 }\r
 241                                                         }\r
 242                                                         //lの決定\r
 243                                                         if (id_ptr.clip_l > prev_ptr.clip_l) {\r
 244                                                                 id_ptr.clip_l=prev_ptr.clip_l;\r
 245                                                         }else{\r
 246                                                         }\r
 247                                                         //rの決定\r
 248                                                         if (id_ptr.clip_r < prev_ptr.clip_r) {\r
 249                                                                 id_ptr.clip_r=prev_ptr.clip_r;\r
 250                                                         }else{\r
 251                                                         }\r
 252                                                         //bの決定\r
 253 \r
 254                                                         //結合済のルートフラグメントを無効化する。\r
 255                                                         prev_ptr.area=0;\r
 256                                                 }\r
 257 \r
 258 \r
 259                                                 index_prev++;\r
 260                                         }\r
 261                                         index_prev--;\r
 262                                         break;\r
 263                                 }\r
 264                                 // curにidが割り当てられたかを確認\r
 265                                 // 右端独立フラグメントを追加\r
 266                                 if (id < 0){\r
 267                                         addFragment(rle_current[i], id_max, y, i,o_stack);\r
 268                                         id_max++;\r
 269                                         label_count++;\r
 270                                 }\r
 271                         }\r
 272                         // prevとrelの交換\r
 273                         RleElement[] tmp = rle_prev;\r
 274                         rle_prev = rle_current;\r
 275                         len_prev = len_current;\r
 276                         rle_current = tmp;\r
 277                 }\r
 278                 //ソートする。\r
 279                 o_stack.sortByArea();\r
 280                 //ラベル数を再設定\r
 281                 o_stack.reserv(label_count);\r
 282                 //posを計算\r
 283                 for(int i=0;i<label_count;i++){\r
 284                         final RleLabelFragmentInfoStack.RleLabelFragmentInfo tmp=f_array[i];\r
 285                         tmp.pos_x/=tmp.area;\r
 286                         tmp.pos_y/=tmp.area;\r
 287                 }\r
 288                 //ラベル数を返却\r
 289                 return label_count;\r
 290         }       \r
 291 }\r
 292 \r
 293 \r
 294 \r