src/jp/nyatla/nyartoolkit/core/squaredetect/SquareContourDetector.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 edition ARToolKit class library.\r
  11  * Copyright (C)2008-2009 Ryo Iizuka\r
  12  *\r
  13  * This program is free software: you can redistribute it and/or modify\r
  14  * it under the terms of the GNU General Public License as published by\r
  15  * the Free Software Foundation, either version 3 of the License, or\r
  16  * (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 program.  If not, see <http://www.gnu.org/licenses/>.\r
  25  * \r
  26  * For further information please contact.\r
  27  *      http://nyatla.jp/nyatoolkit/\r
  28  *      <airmail(at)ebony.plala.or.jp> or <nyatla(at)nyatla.jp>\r
  29  * \r
  30  */\r
  31 package jp.nyatla.nyartoolkit.core.squaredetect;\r
  32 \r
  33 import jp.nyatla.nyartoolkit.NyARException;\r
  34 import jp.nyatla.nyartoolkit.core.param.NyARCameraDistortionFactor;\r
  35 import jp.nyatla.nyartoolkit.core.param.NyARObserv2IdealMap;\r
  36 import jp.nyatla.nyartoolkit.core.pca2d.INyARPca2d;\r
  37 import jp.nyatla.nyartoolkit.core.pca2d.NyARPca2d_MatrixPCA_O2;\r
  38 import jp.nyatla.nyartoolkit.core.types.NyARDoublePoint2d;\r
  39 import jp.nyatla.nyartoolkit.core.types.NyARIntPoint2d;\r
  40 import jp.nyatla.nyartoolkit.core.types.NyARIntSize;\r
  41 import jp.nyatla.nyartoolkit.core.types.NyARLinear;\r
  42 import jp.nyatla.nyartoolkit.core.types.matrix.NyARDoubleMatrix22;\r
  43 \r
  44 public class SquareContourDetector\r
  45 {\r
  46         private static final double VERTEX_FACTOR = 1.0;// 線検出のファクタ     \r
  47         private final double[] _xpos;\r
  48         private final double[] _ypos;   \r
  49         private final int[] __detectMarker_mkvertex = new int[5];\r
  50         private final NyARVertexCounter __getSquareVertex_wv1 = new NyARVertexCounter();\r
  51         private final NyARVertexCounter __getSquareVertex_wv2 = new NyARVertexCounter();\r
  52         private final INyARPca2d _pca;\r
  53         private final NyARDoubleMatrix22 __getSquareLine_evec=new NyARDoubleMatrix22();\r
  54         private final double[] __getSquareLine_mean=new double[2];\r
  55         private final double[] __getSquareLine_ev=new double[2];\r
  56         private final NyARObserv2IdealMap _dist_factor;\r
  57         public SquareContourDetector(NyARIntSize i_size,NyARCameraDistortionFactor i_distfactor_ref)\r
  58         {\r
  59                 //歪み計算テーブルを作ると、8*width/height*2の領域を消費します。\r
  60                 //領域を取りたくない場合は、i_dist_factor_refの値をそのまま使ってください。\r
  61                 this._dist_factor = new NyARObserv2IdealMap(i_distfactor_ref,i_size);\r
  62 \r
  63 \r
  64                 // 輪郭バッファは頂点変換をするので、輪郭バッファの２倍取る。\r
  65                 this._pca=new NyARPca2d_MatrixPCA_O2();\r
  66                 this._xpos=new double[i_size.w+i_size.h];//最大辺長はthis._width+this._height\r
  67                 this._ypos=new double[i_size.w+i_size.h];//最大辺長はthis._width+this._height\r
  68                 return;\r
  69         }\r
  70 \r
  71         public boolean coordToSquare(int[] i_xcoord,int[] i_ycoord,int i_coord_num,int i_label_area,NyARSquare o_square) throws NyARException\r
  72         {\r
  73 \r
  74                 final int[] mkvertex = this.__detectMarker_mkvertex;\r
  75                 int vertex_1=getFarPoint(i_xcoord,i_ycoord,i_coord_num,0);\r
  76                 // 頂点情報を取得\r
  77                 if (!getSquareVertex(i_xcoord, i_ycoord, vertex_1, i_coord_num-1, i_label_area, mkvertex)) {\r
  78                         // 頂点の取得が出来なかったので破棄\r
  79                         return false;\r
  80                 }\r
  81                 // マーカーを検出\r
  82                 if (!getSquareLine(mkvertex, i_xcoord, i_ycoord,i_coord_num-1, o_square)){\r
  83                         // 矩形が成立しなかった。\r
  84                         return false;\r
  85                 }\r
  86                 return true;\r
  87         }\r
  88         \r
  89         private boolean getSquareLine(int[] i_mkvertex, int[] i_xcoord, int[] i_ycoord,int i_cood_num, NyARSquare o_square) throws NyARException\r
  90         {\r
  91                 final NyARLinear[] l_line = o_square.line;\r
  92                 final NyARDoubleMatrix22 evec=this.__getSquareLine_evec;\r
  93                 final double[] mean=this.__getSquareLine_mean;\r
  94                 final double[] ev=this.__getSquareLine_ev;\r
  95         \r
  96                 double w1;              \r
  97                 for (int i = 0; i < 4; i++){\r
  98                         int n,st,ed;\r
  99                         //探索区間の決定\r
 100                         if(i_mkvertex[i + 1]>=i_mkvertex[i]){\r
 101                                 //頂点[i]から頂点[i+1]までの輪郭が、1区間にあるとき\r
 102                                 w1 = (double) (i_mkvertex[i + 1] - i_mkvertex[i] + 1) * 0.05 + 0.5;\r
 103                                 //探索区間の決定\r
 104                                 st = (int) (i_mkvertex[i]+w1);\r
 105                                 ed = (int) (i_mkvertex[i+1] - w1);\r
 106                         }else{\r
 107                                 //頂点[i]から頂点[i+1]までの輪郭が、2区間に分かれているとき\r
 108                                 w1 = (double) (i_mkvertex[i + 1]+i_cood_num-i_mkvertex[i]+1)%i_cood_num * 0.05 + 0.5;\r
 109                                 //探索区間の決定\r
 110                                 st = (int) (i_mkvertex[i]+w1)%i_cood_num;\r
 111                                 ed = (int) (i_mkvertex[i+1]+i_cood_num-w1)%i_cood_num;\r
 112                         }\r
 113                         //探索区間数を確認\r
 114                         if(st<=ed){\r
 115                                 //探索区間は1区間\r
 116                                 n = ed - st + 1;\r
 117                                 this._dist_factor.observ2IdealBatch(i_xcoord, i_ycoord, st, n,this._xpos,this._ypos,0);\r
 118                         }else{\r
 119                                 //探索区間は2区間\r
 120                                 n=ed+1+i_cood_num-st;\r
 121                                 this._dist_factor.observ2IdealBatch(i_xcoord, i_ycoord, st,i_cood_num-st,this._xpos,this._ypos,0);\r
 122                                 this._dist_factor.observ2IdealBatch(i_xcoord, i_ycoord, 0,ed+1,this._xpos,this._ypos,i_cood_num-st);\r
 123                         }\r
 124                         //要素数の確認\r
 125                         if (n < 2) {\r
 126                                 // nが2以下でmatrix.PCAを計算することはできないので、エラー\r
 127                                 return false;\r
 128                         }\r
 129                         //主成分分析する。\r
 130                         this._pca.pca(this._xpos,this._ypos,n,evec, ev,mean);\r
 131                         final NyARLinear l_line_i = l_line[i];\r
 132                         l_line_i.dy = evec.m01;// line[i][0] = evec->m[1];\r
 133                         l_line_i.dx = -evec.m00;// line[i][1] = -evec->m[0];\r
 134                         l_line_i.c = -(l_line_i.dy * mean[0] + l_line_i.dx * mean[1]);// line[i][2] = -(line[i][0]*mean->v[0] + line[i][1]*mean->v[1]);\r
 135                 }\r
 136 \r
 137                 final NyARDoublePoint2d[] l_sqvertex = o_square.sqvertex;\r
 138                 final NyARIntPoint2d[] l_imvertex = o_square.imvertex;\r
 139                 for (int i = 0; i < 4; i++) {\r
 140                         final NyARLinear l_line_i = l_line[i];\r
 141                         final NyARLinear l_line_2 = l_line[(i + 3) % 4];\r
 142                         w1 = l_line_2.dy * l_line_i.dx - l_line_i.dy * l_line_2.dx;\r
 143                         if (w1 == 0.0) {\r
 144                                 return false;\r
 145                         }\r
 146                         l_sqvertex[i].x = (l_line_2.dx * l_line_i.c - l_line_i.dx * l_line_2.c) / w1;\r
 147                         l_sqvertex[i].y = (l_line_i.dy * l_line_2.c - l_line_2.dy * l_line_i.c) / w1;\r
 148                         // 頂点インデクスから頂点座標を得て保存\r
 149                         l_imvertex[i].x = i_xcoord[i_mkvertex[i]];\r
 150                         l_imvertex[i].y = i_ycoord[i_mkvertex[i]];\r
 151                 }\r
 152                 return true;\r
 153         }       \r
 154         \r
 155 \r
 156         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
 157         {\r
 158                 final NyARVertexCounter wv1 = this.__getSquareVertex_wv1;\r
 159                 final NyARVertexCounter wv2 = this.__getSquareVertex_wv2;\r
 160                 int prev_vertex_index=(i_vertex1_index+i_coord_num)%i_coord_num;\r
 161                 int v1=getFarPoint(i_x_coord,i_y_coord,i_coord_num,i_vertex1_index);\r
 162                 final double thresh = (i_area / 0.75) * 0.01 * VERTEX_FACTOR;\r
 163 \r
 164                 o_vertex[0] = i_vertex1_index;\r
 165 \r
 166                 if (!wv1.getVertex(i_x_coord, i_y_coord,i_coord_num, i_vertex1_index, v1, thresh)) {\r
 167                         return false;\r
 168                 }\r
 169                 if (!wv2.getVertex(i_x_coord, i_y_coord,i_coord_num, v1,prev_vertex_index, thresh)) {\r
 170                         return false;\r
 171                 }\r
 172 \r
 173                 int v2;\r
 174                 if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {// if(wvnum1 == 1 && wvnum2== 1) {\r
 175                         o_vertex[1] = wv1.vertex[0];\r
 176                         o_vertex[2] = v1;\r
 177                         o_vertex[3] = wv2.vertex[0];\r
 178                 } else if (wv1.number_of_vertex > 1 && wv2.number_of_vertex == 0) {// }else if( wvnum1 > 1 && wvnum2== 0) {\r
 179                         //頂点位置を、起点から対角点の間の1/2にあると予想して、検索する。\r
 180                         if(v1>=i_vertex1_index){\r
 181                                 v2 = (v1-i_vertex1_index)/2+i_vertex1_index;\r
 182                         }else{\r
 183                                 v2 = ((v1+i_coord_num-i_vertex1_index)/2+i_vertex1_index)%i_coord_num;\r
 184                         }\r
 185                         if (!wv1.getVertex(i_x_coord, i_y_coord,i_coord_num, i_vertex1_index, v2, thresh)) {\r
 186                                 return false;\r
 187                         }\r
 188                         if (!wv2.getVertex(i_x_coord, i_y_coord,i_coord_num, v2, v1, thresh)) {\r
 189                                 return false;\r
 190                         }\r
 191                         if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {\r
 192                                 o_vertex[1] = wv1.vertex[0];\r
 193                                 o_vertex[2] = wv2.vertex[0];\r
 194                                 o_vertex[3] = v1;\r
 195                         } else {\r
 196                                 return false;\r
 197                         }\r
 198                 } else if (wv1.number_of_vertex == 0 && wv2.number_of_vertex > 1) {\r
 199                         //v2 = (v1+ end_of_coord)/2;\r
 200                         if(v1<=prev_vertex_index){\r
 201                                 v2 = (v1+prev_vertex_index)/2;\r
 202                         }else{\r
 203                                 v2 = ((v1+i_coord_num+prev_vertex_index)/2)%i_coord_num;\r
 204                                 \r
 205                         }\r
 206                         if (!wv1.getVertex(i_x_coord, i_y_coord,i_coord_num, v1, v2, thresh)) {\r
 207                                 return false;\r
 208                         }\r
 209                         if (!wv2.getVertex(i_x_coord, i_y_coord,i_coord_num, v2, prev_vertex_index, thresh)) {\r
 210                                 return false;\r
 211                         }\r
 212                         if (wv1.number_of_vertex == 1 && wv2.number_of_vertex == 1) {\r
 213                                 o_vertex[1] = v1;\r
 214                                 o_vertex[2] = wv1.vertex[0];\r
 215                                 o_vertex[3] = wv2.vertex[0];\r
 216                         } else {\r
 217                                 \r
 218                                 return false;\r
 219                         }\r
 220                 } else {\r
 221                         return false;\r
 222                 }\r
 223                 o_vertex[4] = prev_vertex_index;\r
 224                 return true;\r
 225         }\r
 226 \r
 227         /**\r
 228          * i_pointの輪郭座標から、最も遠方にある輪郭座標のインデクスを探します。\r
 229          * @param i_xcoord\r
 230          * @param i_ycoord\r
 231          * @param i_coord_num\r
 232          * @return\r
 233          */\r
 234         private static int getFarPoint(int[] i_coord_x, int[] i_coord_y,int i_coord_num,int i_point)\r
 235         {\r
 236                 //\r
 237                 final int sx = i_coord_x[i_point];\r
 238                 final int sy = i_coord_y[i_point];\r
 239                 int d = 0;\r
 240                 int w, x, y;\r
 241                 int ret = 0;\r
 242                 for (int i = i_point+1; i < i_coord_num; i++) {\r
 243                         x = i_coord_x[i] - sx;\r
 244                         y = i_coord_y[i] - sy;\r
 245                         w = x * x + y * y;\r
 246                         if (w > d) {\r
 247                                 d = w;\r
 248                                 ret = i;\r
 249                         }\r
 250                 }\r
 251                 for (int i = 0; i < i_point; i++) {\r
 252                         x = i_coord_x[i] - sx;\r
 253                         y = i_coord_y[i] - sy;\r
 254                         w = x * x + y * y;\r
 255                         if (w > d) {\r
 256                                 d = w;\r
 257                                 ret = i;\r
 258                         }\r
 259                 }               \r
 260                 return ret;\r
 261         }       \r
 262 }