gt:                 if (points == null){
context: package april.tag;
  
  import java.awt.*;
  import java.awt.event.*;
  import java.awt.image.*;
  import java.io.*;
  import java.util.*;
  import javax.swing.*;
  
  import april.jmat.*;
  import april.jmat.geom.*;
  
  import april.vis.*;
  import april.jcam.*;
  
  import april.image.*;
  import april.util.*;
  
  /** Coordinate system conventions:
  
  Here's a tag, as you might view the png's...
  
  
      ^
      |  Y axis
      |
              Top right corner is (1,1) in tag coordinates
       -----
      |     |
      |     |
      |     |
       -----   ---> X axis
  
     Bottom left corner is (-1,-1) in tag coordinates
  
     Bits will be read off in row-major order from top left to lower
     right, with the top left bit being the MSB and the bottom right bit
     being the LSB.
  
     Note that these conventions are usually "natural", but can be a bit
     confusing with regard to *image* coordinates (of the individual
     tags or camera images), where the top left corner is (0,0).
   **/
  
  public class TagDetector implements AbstractTagDetector
  {
      TagFamily tagFamily;
  
      /** Gaussian smoothing kernel applied to image (0 == no filter)
       * used when sampling bits. Filtering is a good idea in cases
       * where A) a cheap camera is introducing artifical sharpening, B)
       * the bayer pattern is creating artifcats, C) the sensor is very
       * noisy and/or has hot/cold pixels. However, filtering makes it
       * harder to decode very small tags. Reasonable values are 0, or
       * [0.8, 1.5].**/
      public double sigma = 0;
  
      /** Gaussian smoothing kernel applied to image (0 == no filter)
       * used when detecting the outline of the box. It is almost always
       * useful to have some filtering, since the loss of small details
       * won't hurt. Recommended value = 0.8. The case where sigma ==
       * segsigma has been optimized to avoid a redundant filter
       * operation. **/
      public double segSigma = 0.8;
  
      /** Instead of blurring the input image before segmentation, we
       * can achieve similar effects by decimating the image by a factor
       * of two. When enabled, this option applies a block LPF filter of
       * width 2, then decimates the image. With this option, not only
       * can we safely set segSigma = 0, but the slowest part of the
       * algorithm (the segmentation) runs about 4 times faster. The
       * downside is that the position of the targets is determined
       * based on the segmentation: lower resolution will result in more
       * localization error. However, the effect on quality is quite
       * modest, and this optimization is generally recommended (along
       * with segSigma = 0). If segSigma is non-zero, the filtering by
       * segSigma occurs first, followed by the block LPF, and the
       * decimation. **/
      public boolean segDecimate = false;
  
      /** Do not consider pixels whose gradient magnitude is less than
       * minMag. Small values make the detector more sensitive, but also
       * force us to consider many more edges resulting in slower
       * computation time. A value of 0.001 is very sensitive. A value
       * of 0.01 is quite fast. **/
      public double minMag = 0.004;
  
      /** When connecting edges, what is the maximum range allowed for
       * the gradient directions? **/
      public double maxEdgeCost = Math.toRadians(30);
  
      /** When growing components, the intra component variation is
       * allowed to grow when the component is small in size. These two
       * thresholds determine how much. **/
      public double thetaThresh = 100;
      public double magThresh = 1200;
  
      // in pixels. Set based on minimum plausible decoding size for Tag9 family.
      public double minimumLineLength = 4;
  
      // minimum number of pixels in a segment before we'll fit a line to it.
      public double minimumSegmentSize = 4;
  
      // minimum size of tag (in pixels) as measured along edges and diagonals.
      public double minimumTagSize = 6;
  
      /** Early pruning of quads which have insane aspect ratios. **/
      public double maxQuadAspectRatio = 32;
  
      // when stitching a quad together from segments, how far away can
      // one line begin from the end of the other?
      //
      // range = quadSearchRangePix + quadSearchRangeFraction*line_length
      public double quadSearchRangePix = 6;
      public double quadSearchRangeFraction = 0.5;
  
      /** Produce debugging output. If the debugging code annoys you (or
       * makes porting harder) you can delete all of the code in an
       * if(debug) block.
       **/
      public boolean debug = false;
      public BufferedImage   debugInput;         // the input image (after preprocessing)
      public BufferedImage   debugSegInput;      // the input image passed to segmentation.
      public BufferedImage   debugSegmentation;  // segmented image
      public BufferedImage   debugTheta, debugMag;
      public VisWorld.Buffer debugSegments;      // segments fit to clusters
      public VisWorld.Buffer debugQuads;         // quads fit to segments
      public VisWorld.Buffer debugSamples;       // samples taken within a quad.
      public VisWorld.Buffer debugLabels;        // labels drawn for each accepted quad.
  
      /** The optical center of the current frame, which is needed to correctly compute the homography. **/
      double opticalCenter[];
  
      /** During segmentation, the weight of an edge is related to the
       * change in theta between the two pixels. This change is
       * normalized via maxEdgeCost, resulting in a number[0,1]. We then
       * convert this number to fixed-point by multiplying it by
       * WEIGHT_SCALE. The resulting number must fit in the number of
       * bits allocated to it, currently 16 (see Step 3). Large values
       * of WEIGHT_SCALE are good because they lead to better
       * fixed-point approximations. However, small numbers are better,
       * because there are fewer discrete values of edge costs, which
       * means that there is more spatial/temporal coherence when
       * processing the sorted edges. This results in faster
       * processing. Given that these orientations are pretty noisy to
       * begin with, some quantization error is acceptable.
       **/
      public int WEIGHT_SCALE = 100;//10000;
  
      public TagDetector(TagFamily tagFamily)
      {
          this.tagFamily = tagFamily;
      }
  
      final int edgeCost(double theta0, double mag0, double theta1, double mag1)
      {
          if (mag0 < minMag || mag1 < minMag)
              return -1;
  
          double thetaErr = Math.abs(MathUtil.mod2pi(theta1 - theta0));
          if (thetaErr > maxEdgeCost)
              return -1;
  
          double normErr = thetaErr / maxEdgeCost;
  
          return (int) (normErr * WEIGHT_SCALE);
      }
  
      // lousy approximation of arctan function, but good enough for our purposes (about 4 degrees)
      final double arctan2(double y, double x)
      {
          double coeff_1 = Math.PI/4;
          double coeff_2 = 3*coeff_1;
          double abs_y = Math.abs(y)+1e-10;      // kludge to prevent 0/0 condition
  
          double angle;
  
          if (x >= 0) {
              double r = (x - abs_y) / (x + abs_y);
              angle = coeff_1 - coeff_1 * r;
          } else {
              double r = (x + abs_y) / (abs_y - x);
              angle = coeff_2 - coeff_1 * r;
          }
  
          if (y < 0)
              return -angle;     // negate if in quad III or IV
          else
              return angle;
      }
  
  
      /** Sort and return the first vlength values in v[] by the value
       * of v[i]&amp;mask. The maximum value in the array 'v' is maxv
       * (if maxv is negative, maxv will be found). These weights must
       * be small enough to fit in an integer. This implementation is
       * stable.
       **/
      static long[] countingSortLongArray(long v[], int vlength, int maxv, long mask)
      {
          if (maxv < 0) {
              for (int i = 0; i < vlength; i++)
                  maxv = Math.max(maxv, (int) (v[i]&mask));
          }
  
          // For weight 'w', counts[w] will give the output position for
          // the next sample with weight w.  To build this, we begin by
          // counting how many samples there are with each weight. (Note
          // that the initial position for weight w is only affected by
          // the number of weights less than w, hence the +1 in
          // counts[w+1].
          int counts[] = new int[maxv+2];
  
          for (int i = 0; i < vlength; i++) {
              int w = (int) (v[i]&mask);
              counts[w+1]++;
          }
  
          // accumulate.
          for (int i = 1; i < counts.length; i++)
              counts[i] += counts[i-1];
  
          long newv[] = new long[vlength];
          for (int i = 0; i < vlength; i++) {
              int w = (int) (v[i]&mask);
              newv[counts[w]] = v[i];
              counts[w]++;
          }
  
  /*       // test (debugging code)
          for (int i = 0; i+1 < newv.length; i++) {
              int w0 = (int) (newv[i]&mask);
              int w1 = (int) (newv[i+1]&mask);
              assert(w0 <= w1);
          }
  */
  
          return newv;
      }
  
      /** Detect the features in the specified image. We need the
       * optical center, but it is usually fine to pass in (width/2,
       * height/2).
       **/
      public ArrayList<TagDetection> process(BufferedImage im, double opticalCenter[])
      {
          this.opticalCenter = opticalCenter;
  
          // This is a very long function, but it can't really be
          // factored any more simply: it's just a long sequence of
          // sequential operations.
  
          ///////////////////////////////////////////////////////////
          // Step one. Preprocess image (convert to float (grayscale)
          // and low pass if necessary.)
          FloatImage fimOrig = new FloatImage(im);
  
          FloatImage fim = fimOrig;
          if (sigma > 0) {
              int filtsz = ((int) Math.max(3, 3*sigma)) | 1;
              float filt[] = SigProc.makeGaussianFilter(sigma, filtsz);
              fim = fimOrig.filterFactoredCentered(filt, filt);
          }
  
          if (debug) {
              debugInput = fim.makeImage();
          }
  
          ///////////////////////////////////////////////////////////
          // Step two. For each pixel, compute the local gradient. We
          // store the direction and magnitude.
  
          // This step is quite sensitive to noise, since a few bad
          // theta estimates will break up segments, causing us to miss
          // quads. It is helpful to do a Gaussian low-pass on this step
          // even if we don't want it for decoding.
          FloatImage fimseg = fimOrig; // default
          if (segSigma > 0) {
              if (segSigma == sigma) {
                  // reuse the already-filtered image...
                  fimseg = fim;
              } else {
                  // blur anew.
                  int filtsz = ((int) Math.max(3, 3*segSigma)) | 1;
                  float filt[] = SigProc.makeGaussianFilter(segSigma, filtsz);
                  fimseg = fimOrig.filterFactoredCentered(filt, filt);
              }
          }
          if (segDecimate)
              fimseg = fimseg.decimateAvg();
  
          FloatImage fimTheta = new FloatImage(fimseg.width, fimseg.height);
          FloatImage fimMag = new FloatImage(fimseg.width, fimseg.height);
  
          for (int y = 1; y+1 < fimseg.height; y++) {
              for (int x = 1; x+1 < fimseg.width; x++) {
  
                  float Ix = fimseg.get(x+1, y) - fimseg.get(x-1, y);
                  float Iy = fimseg.get(x,y+1) - fimseg.get(x, y-1);
  
                  double mag = Ix*Ix + Iy*Iy;
                  double theta = arctan2(Iy, Ix);
  
                  fimTheta.set(x, y, (float) theta);
                  fimMag.set(x, y, (float) mag);
              }
          }
  
          if (debug) {
              debugTheta = fimTheta.normalize().makeImage();
              debugMag = fimMag.normalize().makeImage();
          }
  
          ///////////////////////////////////////////////////////////
          // Step three. Segment the edges, grouping pixels with similar
          // thetas together. This is a greedy algorithm: we start with
          // the most similar pixels.  We use 4-connectivity.
          UnionFindSimple uf = new UnionFindSimple(fimseg.width*fimseg.height);
  
          if (true) {
              int width = fimseg.width;
              int height = fimseg.height;
  
              long edges[] = new long[width*height*4];
              int nedges = 0;
  
              // for efficiency, each edge is encoded as a single
              // long. The constants below are used to pack/unpack the
              // long.
              final long IDA_SHIFT = 40, IDB_SHIFT = 16, INDEX_MASK = (1<<24) - 1, WEIGHT_MASK=(1<<16)-1;
  
              // bounds on the thetas assigned to this group. Note that
              // because theta is periodic, these are defined such that the
              // average value is contained *within* the interval.
              double tmin[] = new double[width*height];
              double tmax[] = new double[width*height];
  
              double mmin[] = new double[width*height];
              double mmax[] = new double[width*height];
  
              for (int y = 0; y+1 < fimseg.height; y++) {
                  for (int x = 0; x+1 < fimseg.width; x++) {
  
                      double mag0 = fimMag.get(x,y);
                      if (mag0 < minMag)
                          continue;
                      mmax[y*width+x] = mag0;
                      mmin[y*width+x] = mag0;
  
                      double theta0 = fimTheta.get(x,y);
                      tmin[y*width+x] = theta0;
                      tmax[y*width+x] = theta0;
  
                      int edgeCost;
  
                      // 8 connectivity
                      edgeCost = edgeCost(theta0, mag0, fimTheta.get(x+1, y), fimMag.get(x+1,y));
                      if (edgeCost >= 0)
                          edges[nedges++] = (((long) y*width+x)<<IDA_SHIFT) + (((long) y*width+x+1)<<IDB_SHIFT) + edgeCost;
  
                      edgeCost = edgeCost(theta0, mag0, fimTheta.get(x, y+1), fimMag.get(x,y+1));
                      if (edgeCost >= 0)
                          edges[nedges++] = ((long) (y*width+x)<<IDA_SHIFT) + (((long) (y+1)*width+x)<<IDB_SHIFT) + edgeCost;
  
                      edgeCost = edgeCost(theta0, mag0, fimTheta.get(x+1, y+1), fimMag.get(x+1,y+1));
                      if (edgeCost >= 0)
                          edges[nedges++] = (((long) y*width+x)<<IDA_SHIFT) + (((long) (y+1)*width+x+1)<<IDB_SHIFT) + edgeCost;
  
                      edgeCost = (x == 0) ? -1 : edgeCost(theta0, mag0, fimTheta.get(x-1, y+1), fimMag.get(x-1,y+1));
                      if (edgeCost >= 0)
                          edges[nedges++] = (((long) y*width+x)<<IDA_SHIFT) + (((long) (y+1)*width+x-1)<<IDB_SHIFT) + edgeCost;
                  }
              }
  
              // sort those edges by weight (lowest weight first).
              edges = countingSortLongArray(edges, nedges, -1, WEIGHT_MASK);
  
              // process edges in order of increasing weight, merging
              // clusters if we can do so without exceeding the
              // thetaThresh.
              for (int i = 0; i < nedges; i++) {
                  int ida = (int) ((edges[i]>>IDA_SHIFT)&INDEX_MASK);
                  int idb = (int) ((edges[i]>>IDB_SHIFT)&INDEX_MASK);
  
                  ida = uf.getRepresentative(ida);
                  idb = uf.getRepresentative(idb);
  
                  if (ida == idb)
                      continue;
  
                  int sza = uf.getSetSize(ida);
                  int szb = uf.getSetSize(idb);
  
                  double tmina = tmin[ida], tmaxa = tmax[ida];
                  double tminb = tmin[idb], tmaxb = tmax[idb];
  
                  double costa = (tmaxa-tmina);
                  double costb = (tmaxb-tminb);
  
                  // bshift will be a multiple of 2pi that aligns the spans
                  // of b with a so that we can properly take the union of
                  // them.
                  double bshift = MathUtil.mod2pi((tmina+tmaxa)/2, (tminb+tmaxb)/2) - (tminb+tmaxb)/2;
  
                  double tminab = Math.min(tmina, tminb + bshift);
                  double tmaxab = Math.max(tmaxa, tmaxb + bshift);
  
                  if (tmaxab - tminab > 2*Math.PI)  // corner case that's probably not useful to handle correctly. oh well.
                      tmaxab = tminab + 2*Math.PI;
  
                  double mmaxab = Math.max(mmax[ida], mmax[idb]);
                  double mminab = Math.min(mmin[ida], mmin[idb]);
  
                  // merge these two clusters?
                  double costab = (tmaxab - tminab);
                  if (costab <= (Math.min(costa, costb) + thetaThresh/(sza+szb)) &&
                      (mmaxab-mminab) <= Math.min(mmax[ida]-mmin[ida], mmax[idb]-mmin[idb]) + magThresh/(sza+szb)) {
  
                      int idab = uf.connectNodes(ida, idb);
  
                      tmin[idab] = tminab;
                      tmax[idab] = tmaxab;
  
                      mmin[idab] = mminab;
                      mmax[idab] = mmaxab;
                  }
              }
          }
  
          ///////////////////////////////////////////////////////////
          // Step four. Loop over the pixels again, collecting
          // statistics for each cluster. We will soon fit lines to
          // these points.
  
          if (debug) {
              debugSegmentation = new BufferedImage(fimseg.width, fimseg.height, BufferedImage.TYPE_INT_RGB);
          }
  
          HashMap<Integer,ArrayList<double[]>> clusters = new HashMap<Integer,ArrayList<double[]>>();
          for (int y = 0; y+1 < fimseg.height; y++) {
              for (int x = 0; x+1 < fimseg.width; x++) {
                  if (uf.getSetSize(y*fimseg.width+x) < minimumSegmentSize) {
                      if (debug)
                          debugSegmentation.setRGB(x, y, 0);
                      continue;
                  }
  
                  int rep = (int) uf.getRepresentative(y*fimseg.width + x);
                  if (debug)
                      debugSegmentation.setRGB(x, y, rep);
  
                  ArrayList<double[]> points = clusters.get(rep);
  