sample/toys/jp/nyatla/nyartoolkit/toys/vertexdetect/NyARQrCodeDetector.java

   1 /* \r
   2  * PROJECT: NyARToolkit\r
   3  * --------------------------------------------------------------------------------\r
   4  * This work is based on the original ARToolKit developed by\r
   5  *   Hirokazu Kato\r
   6  *   Mark Billinghurst\r
   7  *   HITLab, University of Washington, Seattle\r
   8  * http://www.hitl.washington.edu/artoolkit/\r
   9  *\r
  10  * The NyARToolkit is Java version ARToolkit class library.\r
  11  * Copyright (C)2008 R.Iizuka\r
  12  *\r
  13  * This program is free software; you can redistribute it and/or\r
  14  * modify it under the terms of the GNU General Public License\r
  15  * as published by the Free Software Foundation; either version 2\r
  16  * of the License, or (at your option) any later version.\r
  17  * \r
  18  * This program is distributed in the hope that it will be useful,\r
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of\r
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the\r
  21  * GNU General Public License for more details.\r
  22  * \r
  23  * You should have received a copy of the GNU General Public License\r
  24  * along with this framework; if not, write to the Free Software\r
  25  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA\r
  26  * \r
  27  * For further information please contact.\r
  28  *      http://nyatla.jp/nyatoolkit/\r
  29  *      <airmail(at)ebony.plala.or.jp>\r
  30  * \r
  31  */\r
  32 package jp.nyatla.nyartoolkit.toys.vertexdetect;\r
  33 import jp.nyatla.nyartoolkit.NyARException;\r
  34 import jp.nyatla.nyartoolkit.core.labeling.*;\r
  35 import jp.nyatla.nyartoolkit.core.raster.*;\r
  36 import jp.nyatla.nyartoolkit.core.types.*;\r
  37 import jp.nyatla.nyartoolkit.core.param.*;\r
  38 import jp.nyatla.nyartoolkit.core.*;\r
  39 import jp.nyatla.nyartoolkit.toys.x2.*;\r
  40 \r
  41 /**\r
  42  * 矩形座標をPCAではなく、頂点座標そのものからSquare位置を計算するクラス\r
  43  *\r
  44  */\r
  45 public class NyARQrCodeDetector implements INyARSquareDetector\r
  46 {\r
  47         private static final double VERTEX_FACTOR = 1.0;// 線検出のファクタ\r
  48 \r
  49         private static final int AR_AREA_MAX = 100000;// #define AR_AREA_MAX 100000\r
  50 \r
  51         private static final int AR_AREA_MIN = 70;// #define AR_AREA_MIN 70\r
  52         private final int _width;\r
  53         private final int _height;\r
  54 \r
  55         private final NyARLabeling_ARToolKit_X2 _labeling;\r
  56 \r
  57         private final NyARLabelingImage _limage;\r
  58 \r
  59         private final OverlapChecker _overlap_checker = new OverlapChecker();\r
  60         private final NyARCameraDistortionFactor _dist_factor_ref;\r
  61 \r
  62         /**\r
  63          * 最大i_squre_max個のマーカーを検出するクラスを作成する。\r
  64          * \r
  65          * @param i_param\r
  66          */\r
  67         public NyARQrCodeDetector(NyARCameraDistortionFactor i_dist_factor_ref,NyARIntSize i_size) throws NyARException\r
  68         {\r
  69                 this._width = i_size.w;\r
  70                 this._height = i_size.h;\r
  71                 this._dist_factor_ref = i_dist_factor_ref;\r
  72                 this._labeling = new NyARLabeling_ARToolKit_X2();\r
  73                 this._limage = new NyARLabelingImage(this._width, this._height);\r
  74                 this._labeling.attachDestination(this._limage);\r
  75 \r
  76                 // 輪郭の最大長は画面に映りうる最大の長方形サイズ。\r
  77                 int number_of_coord = (this._width + this._height) * 2;\r
  78 \r
  79                 // 輪郭バッファは頂点変換をするので、輪郭バッファの２倍取る。\r
  80                 this._max_coord = number_of_coord;\r
  81                 this._xcoord = new int[number_of_coord * 2];\r
  82                 this._ycoord = new int[number_of_coord * 2];\r
  83         }\r
  84 \r
  85         private final int _max_coord;\r
  86         private final int[] _xcoord;\r
  87         private final int[] _ycoord;\r
  88 \r
  89         private void normalizeCoord(int[] i_coord_x, int[] i_coord_y, int i_index, int i_coord_num)\r
  90         {\r
  91                 // vertex1を境界にして、後方に配列を連結\r
  92                 System.arraycopy(i_coord_x, 1, i_coord_x, i_coord_num, i_index);\r
  93                 System.arraycopy(i_coord_y, 1, i_coord_y, i_coord_num, i_index);\r
  94         }\r
  95 \r
  96         private final int[] __detectMarker_mkvertex = new int[5];\r
  97 \r
  98         /**\r
  99          * ARMarkerInfo2 *arDetectMarker2( ARInt16 *limage, int label_num, int *label_ref,int *warea, double *wpos, int *wclip,int area_max, int area_min, double\r
 100          * factor, int *marker_num ) 関数の代替品 ラベリング情報からマーカー一覧を作成してo_marker_listを更新します。 関数はo_marker_listに重なりを除外したマーカーリストを作成します。\r
 101          * \r
 102          * @param i_raster\r
 103          * 解析する２値ラスタイメージを指定します。\r
 104          * @param o_square_stack\r
 105          * 抽出した正方形候補を格納するリスト\r
 106          * @throws NyARException\r
 107          */\r
 108         public final void detectMarker(NyARBinRaster i_raster, NyARSquareStack o_square_stack) throws NyARException\r
 109         {\r
 110                 final INyARLabeling labeling_proc = this._labeling;\r
 111                 final NyARLabelingImage limage = this._limage;\r
 112 \r
 113                 // 初期化\r
 114 \r
 115                 // マーカーホルダをリセット\r
 116                 o_square_stack.clear();\r
 117 \r
 118                 // ラベリング\r
 119                 labeling_proc.labeling(i_raster);\r
 120 \r
 121                 // ラベル数が0ならここまで\r
 122                 final int label_num = limage.getLabelStack().getLength();\r
 123                 if (label_num < 1) {\r
 124                         return;\r
 125                 }\r
 126 \r
 127                 final NyARLabelingLabelStack stack = limage.getLabelStack();\r
 128                 final NyARLabelingLabel[] labels = (NyARLabelingLabel[])stack.getArray();\r
 129                 \r
 130                 \r
 131                 // ラベルを大きい順に整列\r
 132                 stack.sortByArea();\r
 133 \r
 134                 // デカいラベルを読み飛ばし\r
 135                 int i;\r
 136                 for (i = 0; i < label_num; i++) {\r
 137                         // 検査対象内のラベルサイズになるまで無視\r
 138                         if (labels[i].area <= AR_AREA_MAX) {\r
 139                                 break;\r
 140                         }\r
 141                 }\r
 142 \r
 143                 final int xsize = this._width;\r
 144                 final int ysize = this._height;\r
 145                 final int[] xcoord = this._xcoord;\r
 146                 final int[] ycoord = this._ycoord;\r
 147                 final int coord_max = this._max_coord;\r
 148                 final int[] mkvertex = this.__detectMarker_mkvertex;\r
 149                 final OverlapChecker overlap = this._overlap_checker;\r
 150                 int coord_num;\r
 151                 int label_area;\r
 152                 NyARLabelingLabel label_pt;\r
 153 \r
 154                 //重なりチェッカの最大数を設定\r
 155                 overlap.reset(label_num);\r
 156 \r
 157                 for (; i < label_num; i++) {\r
 158                         label_pt = labels[i];\r
 159                         label_area = label_pt.area;\r
 160                         // 検査対象サイズよりも小さくなったら終了\r
 161                         if (label_area < AR_AREA_MIN) {\r
 162                                 break;\r
 163                         }\r
 164                         // クリップ領域が画面の枠に接していれば除外\r
 165                         if (label_pt.clip_l == 1 || label_pt.clip_r == xsize - 2) {// if(wclip[i*4+0] == 1 || wclip[i*4+1] ==xsize-2){\r
 166                                 continue;\r
 167                         }\r
 168                         if (label_pt.clip_t == 1 || label_pt.clip_b == ysize - 2) {// if( wclip[i*4+2] == 1 || wclip[i*4+3] ==ysize-2){\r
 169                                 continue;\r
 170                         }\r
 171                         // 既に検出された矩形との重なりを確認\r
 172                         if (!overlap.check(label_pt)) {\r
 173                                 // 重なっているようだ。\r
 174                                 continue;\r
 175                         }\r
 176 \r
 177                         // 輪郭を取得\r
 178                         coord_num = limage.getContour(i, coord_max, xcoord, ycoord);\r
 179                         if (coord_num == coord_max) {\r
 180                                 // 輪郭が大きすぎる。\r
 181                                 continue;\r
 182                         }\r
 183                         //頂点候補のインデクスを取得\r
 184                         final int vertex1 = scanVertex(xcoord, ycoord, coord_num);\r
 185 \r
 186                         // 頂点候補(vertex1)を先頭に並べなおした配列を作成する。\r
 187                         normalizeCoord(xcoord, ycoord, vertex1, coord_num);\r
 188 \r
 189                         // 領域を準備する。\r
 190                         NyARSquare square_ptr = (NyARSquare)o_square_stack.prePush();\r
 191 \r
 192                         // 頂点情報を取得\r
 193                         if (!getSquareVertex(xcoord, ycoord, vertex1, coord_num, label_area, mkvertex)) {\r
 194                                 o_square_stack.pop();// 頂点の取得が出来なかったので破棄\r
 195                                 continue;\r
 196                         }\r
 197                         //頂点情報からライン情報を作っちゃう\r
 198                         getSquare(mkvertex, xcoord, ycoord, square_ptr);\r
 199                         \r
 200                         // 検出済の矩形の属したラベルを重なりチェックに追加する。\r
 201                         overlap.push(label_pt);\r
 202                 }       \r
 203                 return;\r
 204         }\r
 205         /**\r
 206          * ２つの頂点座標を結ぶ直線から、NyARLinearを計算する。\r
 207          * @param i_v1\r
 208          * @param i_v2\r
 209          * @param o_line\r
 210          */\r
 211         final private void getLine(NyARDoublePoint2d i_v1,NyARDoublePoint2d i_v2,NyARLinear o_line)\r
 212         {\r
 213                 final double x=i_v1.x-i_v2.x;\r
 214                 final double y=i_v1.y-i_v2.y;\r
 215                 final double x2=x*x;\r
 216                 final double y2=y*y;\r
 217                 final double rise_=Math.sqrt(x2/(x2+y2));\r
 218                 o_line.rise=rise_;\r
 219                 o_line.run=Math.sqrt(y2/(x2+y2));\r
 220                 if(x<0){\r
 221                         if(y<0){\r
 222                                 o_line.rise=-o_line.rise;\r
 223                         }else{\r
 224                                 o_line.rise=-o_line.rise;\r
 225                                 o_line.run=-o_line.run;\r
 226                         }\r
 227                 }else{\r
 228                         if(y<0){\r
 229                                 o_line.rise=-o_line.rise;\r
 230                                 o_line.run=-o_line.run;\r
 231                         }else{\r
 232                                 o_line.rise=-o_line.rise;\r
 233                         }                       \r
 234                 }\r
 235                 o_line.intercept=(i_v1.y+(o_line.run/o_line.rise)*(i_v1.x))*rise_;\r
 236                 \r
 237         }\r
 238 \r
 239         private void getSquare(int[] i_mkvertex, int[] i_xcoord, int[] i_ycoord, NyARSquare o_square)\r
 240         {\r
 241                 final NyARCameraDistortionFactor dist_factor=this._dist_factor_ref;             \r
 242                 final NyARDoublePoint2d[] vertex=o_square.sqvertex;\r
 243                 //歪み補正\r
 244                 for(int i=0;i<4;i++)\r
 245                 {\r
 246                         final int idx=i_mkvertex[i];\r
 247                         o_square.imvertex[i].x=i_xcoord[idx];\r
 248                 o_square.imvertex[i].y=i_ycoord[idx];\r
 249                         dist_factor.observ2Ideal(i_xcoord[idx], i_ycoord[idx],vertex[i]);\r
 250                 }\r
 251                 //ライン計算\r
 252                 getLine(vertex[1],vertex[0],o_square.line[0]);\r
 253                 getLine(vertex[2],vertex[1],o_square.line[1]);\r
 254                 getLine(vertex[3],vertex[2],o_square.line[2]);\r
 255                 getLine(vertex[0],vertex[3],o_square.line[3]);  \r
 256                 return;\r
 257         }\r
 258 \r
 259         /**\r
 260          * 辺からの対角線が最長になる点を対角線候補として返す。\r
 261          * \r
 262          * @param i_xcoord\r
 263          * @param i_ycoord\r
 264          * @param i_coord_num\r
 265          * @return\r
 266          */\r
 267         private int scanVertex(int[] i_xcoord, int[] i_ycoord, int i_coord_num)\r
 268         {\r
 269                 final int sx = i_xcoord[0];\r
 270                 final int sy = i_ycoord[0];\r
 271                 int d = 0;\r
 272                 int w, x, y;\r
 273                 int ret = 0;\r
 274                 for (int i = 1; i < i_coord_num; i++) {\r
 275                         x = i_xcoord[i] - sx;\r
 276                         y = i_ycoord[i] - sy;\r
 277                         w = x * x + y * y;\r
 278                         if (w > d) {\r
 279                                 d = w;\r
 280                                 ret = i;\r
 281                         }\r
 282                         // ここでうまく終了条件入れられないかな。\r
 283                 }\r
 284                 return ret;\r
 285         }\r
 286 \r
 287         private final NyARVertexCounter __getSquareVertex_wv1 = new NyARVertexCounter();\r
 288 \r
 289         private final NyARVertexCounter __getSquareVertex_wv2 = new NyARVertexCounter();\r
 290 \r
 291         /**\r
 292          * static int arDetectMarker2_check_square( int area, ARMarkerInfo2 *marker_info2, double factor ) 関数の代替関数 OPTIMIZED STEP [450->415] o_squareに頂点情報をセットします。\r
 293          * \r
 294          * @param i_x_coord\r
 295          * @param i_y_coord\r
 296          * @param i_vertex1_index\r
 297          * @param i_coord_num\r
 298          * @param i_area\r
 299          * @param o_vertex\r
 300          * 要素数はint[4]である事\r
 301          * @return\r
 302          */\r
 303         private boolean getSquareVertex(int[] i_x_coord, int[] i_y_coord, int i_vertex1_index, int i_coord_num, int i_area, int[] o_vertex)\r
 304         {\r
 305                 final NyARVertexCounter wv1 = this.__getSquareVertex_wv1;\r
 306                 final NyARVertexCounter wv2 = this.__getSquareVertex_wv2;\r
 307                 final int end_of_coord = i_vertex1_index + i_coord_num - 1;\r
 308                 final int sx = i_x_coord[i_vertex1_index];// sx = marker_info2->x_coord[0];\r
 309                 final int sy = i_y_coord[i_vertex1_index];// sy = marker_info2->y_coord[0];\r
 310                 int dmax = 0;\r
 311                 int v1 = i_vertex1_index;\r
 312                 for (int i = 1 + i_vertex1_index; i < end_of_coord; i++) {// for(i=1;i<marker_info2->coord_num-1;i++)\r
 313                         // {\r
 314                         final int d = (i_x_coord[i] - sx) * (i_x_coord[i] - sx) + (i_y_coord[i] - sy) * (i_y_coord[i] - sy);\r
 315                         if (d > dmax) {\r
 316                                 dmax = d;\r
 317                                 v1 = i;\r
 318                         }\r
 319                 }\r
 320                 final double thresh = (i_area / 0.75) * 0.01 * VERTEX_FACTOR;\r
 321 \r
 322                 o_vertex[0] = i_vertex1_index;\r
 323 \r
 324                 if (!wv1.getVertex(i_x_coord, i_y_coord, i_vertex1_index, v1, thresh)) { // if(get_vertex(marker_info2->x_coord,marker_info2->y_coord,0,v1,thresh,wv1,&wvnum1)<\r
 325                                                                                                                                                                         // 0 ) {\r
 326                         return false;\r
 327                 }\r
 328                 if (!wv2.getVertex(i_x_coord, i_y_coord, v1, end_of_coord, thresh)) {// if(get_vertex(marker_info2->x_coord,marker_info2->y_coord,v1,marker_info2->coord_num-1,thresh,wv2,&wvnum2)\r
 329                         // < 0) {\r
 330                         return false;\r
 331                 }\r
 332 \r
 333                 int v2;\r
 334                 if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {// if(wvnum1 == 1 && wvnum2== 1) {\r
 335                         o_vertex[1] = wv1.vertex[0];\r
 336                         o_vertex[2] = v1;\r
 337                         o_vertex[3] = wv2.vertex[0];\r
 338                 } else if (wv1.number_of_vertex > 1 && wv2.number_of_vertex == 0) {// }else if( wvnum1 > 1 && wvnum2== 0) {\r
 339                         //頂点位置を、起点から対角点の間の1/2にあると予想して、検索する。\r
 340                         v2 = (v1-i_vertex1_index)/2+i_vertex1_index;\r
 341                         if (!wv1.getVertex(i_x_coord, i_y_coord, i_vertex1_index, v2, thresh)) {\r
 342                                 return false;\r
 343                         }\r
 344                         if (!wv2.getVertex(i_x_coord, i_y_coord, v2, v1, thresh)) {\r
 345                                 return false;\r
 346                         }\r
 347                         if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {\r
 348                                 o_vertex[1] = wv1.vertex[0];\r
 349                                 o_vertex[2] = wv2.vertex[0];\r
 350                                 o_vertex[3] = v1;\r
 351                         } else {\r
 352                                 return false;\r
 353                         }\r
 354                 } else if (wv1.number_of_vertex == 0 && wv2.number_of_vertex > 1) {\r
 355                         //v2 = (v1-i_vertex1_index+ end_of_coord-i_vertex1_index) / 2+i_vertex1_index;\r
 356                         v2 = (v1+ end_of_coord)/2;\r
 357 \r
 358                         if (!wv1.getVertex(i_x_coord, i_y_coord, v1, v2, thresh)) {\r
 359                                 return false;\r
 360                         }\r
 361                         if (!wv2.getVertex(i_x_coord, i_y_coord, v2, end_of_coord, thresh)) {\r
 362                                 return false;\r
 363                         }\r
 364                         if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {\r
 365                                 o_vertex[1] = v1;\r
 366                                 o_vertex[2] = wv1.vertex[0];\r
 367                                 o_vertex[3] = wv2.vertex[0];\r
 368                         } else {\r
 369                                 return false;\r
 370                         }\r
 371                 } else {\r
 372                         return false;\r
 373                 }\r
 374                 o_vertex[4] = end_of_coord;\r
 375                 return true;\r
 376         }\r
 377 }\r
 378 \r
 379 /**\r
 380  * get_vertex関数を切り離すためのクラス\r
 381  * \r
 382  */\r
 383 final class NyARVertexCounter\r
 384 {\r
 385         public final int[] vertex = new int[10];// 5まで削れる\r
 386 \r
 387         public int number_of_vertex;\r
 388 \r
 389         private double thresh;\r
 390 \r
 391         private int[] x_coord;\r
 392 \r
 393         private int[] y_coord;\r
 394 \r
 395         public boolean getVertex(int[] i_x_coord, int[] i_y_coord, int st, int ed, double i_thresh)\r
 396         {\r
 397                 this.number_of_vertex = 0;\r
 398                 this.thresh = i_thresh;\r
 399                 this.x_coord = i_x_coord;\r
 400                 this.y_coord = i_y_coord;\r
 401                 return get_vertex(st, ed);\r
 402         }\r
 403 \r
 404         /**\r
 405          * static int get_vertex( int x_coord[], int y_coord[], int st, int ed,double thresh, int vertex[], int *vnum) 関数の代替関数\r
 406          * \r
 407          * @param x_coord\r
 408          * @param y_coord\r
 409          * @param st\r
 410          * @param ed\r
 411          * @param thresh\r
 412          * @return\r
 413          */\r
 414         private boolean get_vertex(int st, int ed)\r
 415         {\r
 416                 int v1 = 0;\r
 417                 final int[] lx_coord = this.x_coord;\r
 418                 final int[] ly_coord = this.y_coord;\r
 419                 final double a = ly_coord[ed] - ly_coord[st];\r
 420                 final double b = lx_coord[st] - lx_coord[ed];\r
 421                 final double c = lx_coord[ed] * ly_coord[st] - ly_coord[ed] * lx_coord[st];\r
 422                 double dmax = 0;\r
 423                 for (int i = st + 1; i < ed; i++) {\r
 424                         final double d = a * lx_coord[i] + b * ly_coord[i] + c;\r
 425                         if (d * d > dmax) {\r
 426                                 dmax = d * d;\r
 427                                 v1 = i;\r
 428                         }\r
 429                 }\r
 430                 if (dmax / (a * a + b * b) > thresh) {\r
 431                         if (!get_vertex(st, v1)) {\r
 432                                 return false;\r
 433                         }\r
 434                         if (number_of_vertex > 5) {\r
 435                                 return false;\r
 436                         }\r
 437                         vertex[number_of_vertex] = v1;// vertex[(*vnum)] = v1;\r
 438                         number_of_vertex++;// (*vnum)++;\r
 439 \r
 440                         if (!get_vertex(v1, ed)) {\r
 441                                 return false;\r
 442                         }\r
 443                 }\r
 444                 return true;\r
 445         }\r
 446 }\r
 447 \r
 448 /**\r
 449  * ラベル同士の重なり（内包関係）を調べるクラスです。 ラベルリストに内包するラベルを蓄積し、それにターゲットのラベルが内包されているか を確認します。\r
 450  */\r
 451 class OverlapChecker\r
 452 {\r
 453         private NyARLabelingLabel[] _labels = new NyARLabelingLabel[32];\r
 454 \r
 455         private int _length;\r
 456 \r
 457         /**\r
 458          * 最大i_max_label個のラベルを蓄積できるようにオブジェクトをリセットする\r
 459          * \r
 460          * @param i_max_label\r
 461          */\r
 462         public void reset(int i_max_label)\r
 463         {\r
 464                 if (i_max_label > this._labels.length) {\r
 465                         this._labels = new NyARLabelingLabel[i_max_label];\r
 466                 }\r
 467                 this._length = 0;\r
 468         }\r
 469 \r
 470         /**\r
 471          * チェック対象のラベルを追加する。\r
 472          * \r
 473          * @param i_label_ref\r
 474          */\r
 475         public void push(NyARLabelingLabel i_label_ref)\r
 476         {\r
 477                 this._labels[this._length] = i_label_ref;\r
 478                 this._length++;\r
 479         }\r
 480 \r
 481         /**\r
 482          * 現在リストにあるラベルと重なっているかを返す。\r
 483          * \r
 484          * @param i_label\r
 485          * @return 何れかのラベルの内側にあるならばfalse,独立したラベルである可能性が高ければtrueです．\r
 486          */\r
 487         public boolean check(NyARLabelingLabel i_label)\r
 488         {\r
 489                 // 重なり処理かな？\r
 490                 final NyARLabelingLabel[] label_pt = this._labels;\r
 491                 final int px1 = (int) i_label.pos_x;\r
 492                 final int py1 = (int) i_label.pos_y;\r
 493                 for (int i = this._length - 1; i >= 0; i--) {\r
 494                         final int px2 = (int) label_pt[i].pos_x;\r
 495                         final int py2 = (int) label_pt[i].pos_y;\r
 496                         final int d = (px1 - px2) * (px1 - px2) + (py1 - py2) * (py1 - py2);\r
 497                         if (d < label_pt[i].area / 4) {\r
 498                                 // 対象外\r
 499                                 return false;\r
 500                         }\r
 501                 }\r
 502                 // 対象\r
 503                 return true;\r
 504         }\r
 505 }