Not logged in.  Login/Logout/Register | List snippets | | Create snippet | Upload image | Upload data

292
LINES

< > BotCompany Repo | #1034983 // G22RegionThinner_v2 - thin a region to 1 pixel wide [OK]

JavaX fragment (include) [tags: use-pretranspiled]

Transpiled version (13958L) is out of date.

srecord noeq G22RegionThinner_v2<Img extends WidthAndHeight>(IImageRegion<Img> originalRegion) is Steppable {
  Rect bounds;
  IImageRegion<Img> region;
  bool phase1done;
  
  settable bool debug;
  settable bool doFinalStep = true;
  settable int lastPhaseThreshold1 = 2;
  settable int lastPhaseThreshold = 5;
  
  settable byte[] lookupTable;
  
  // 0 = outside of region
  // 1 = inner pixel
  // 2 = border pixel
  // index is in bounds coordinates
  byte[] pixels;
  
  int idx(int x, int y) {
    ret (y-bounds.y)*bounds.w+x-bounds.x;
  }
  int idx(Pt p) { ret idx(p.x, p.y); }
  
  Pt idxToPt(int idx) {
    ret pt(bounds.x+(idx % bounds.w), bounds.y+idx/bounds.w);
  }
  
  byte getPixel(long p) {
    ret getPixel(firstIntFromLong(p), secondIntFromLong(p));
  }
  
  byte getPixel(Pt p) {
    ret !containsPt(bounds, p) ? 0 : pixels[idx(p)];
  }
  
  byte getPixel(int x, int y) {
    ret !containsPt(bounds, x, y) ? 0 : pixels[idx(x, y)];
  }
  
  bool contains(int x, int y) {
    ret getPixel(x, y) != 0;
  }
  
  bool clearPixel(int x, int y) {
    if (!region.contains(x, y)) false;
    pixels[idx(x, y)] = 0;
    true;
  }
  
  void init {
    if (bounds != null) ret;
    bounds = originalRegion.bounds();
    pixels = new byte[area(bounds)];
    for (Pt p : originalRegion.pixelIterator())
      pixels[idx(p.x, p.y)] = 1;
      
    region = new ThinnedRegion;
  }
  
  class ThinnedRegion is IImageRegion<Img> {
    public Img image() { ret originalRegion.image(); }
    public Rect bounds() { ret bounds; }
  
    public bool contains(int x, int y) {
      ret containsPt(bounds, x, y) && pixels[idx(x, y)] > 0;
    }
    
    public ItIt<Pt> pixelIterator() {
      ret iff_null(new IF0<Pt> {
        int idx = 0;
        
        public Pt get() {
          for (; idx < pixels.length; idx++)
            if (pixels[idx] > 0)
              ret idxToPt(idx++);
          null;
        }
      });
    }
  }
  
  public bool step() {
    init();
    
    if (phase1done)
      ret finalStep();
    
    L<PtBuffer> traces = g22_allBorderTraces_withDiagonals(region);
    for (points : traces)
      for (p : points)
        pixels[idx(p)] = 2;
        
    new PtBuffer toDelete;

    for (points : traces) {
      int nPoints = l(points);
      BitSet deletable = emptyBitSet(nPoints);
      for i to nPoints: {
        bool del = deletableBorderPoint(points, i);
        /*bool del2 = deletableBorderPoint_old(points, i);
        if (del != del2)
          failWithVars("deletableBorderPoint", +i, +nPoints, +del);*/
        if (del)
          deletable.set(i);
      }

      // handle special cases
      // (preventing single isolated pixels from being left standing)
      
      for i to nPoints:
        if (cyclicGet(deletable, nPoints, i-1)
          && !deletable.get(i)
          && cyclicGet(deletable, nPoints, i+1)) {
          Pt p = points.get(i);
          Pt prev = ptMinus(cyclicGet(points, i-1), p);
          Pt next = ptMinus(cyclicGet(points, i+1), p);
          int dir1 = onePathLookupDirection(prev);
          int dir2 = onePathLookupDirection(next);
          int diff = mod(dir2-dir1, 8);
          if (debug) printVars("special case", +p, +prev, +next, +dir1, +dir2, +diff);
          if (diff == 1 || diff == 7)
            deletable.set(i);
        }

      for i to nPoints:
        if (deletable.get(i))
          toDelete.add(points.get(i));
    }

    for (p : toDelete)
      pixels[idx(p)] = 0;

    if (empty(toDelete))
      set phase1done;
    true;
  }
  
  bool deletableBorderPoint(PtBuffer points, int i) {
    //L<Pt> range = cyclicSubList_incl(points, i-3, i+3);
    LongBuffer pointsBuf = points.buf;
    long p_long = pointsBuf.get(i);
    
    // special case (sharp corner)
    
    if (p_long == cyclicGet(pointsBuf, i-2)
      || p_long == cyclicGet(pointsBuf, i+2)) {
      printVars ifdef G22RegionThinner_debug("special case", p := ptFromLong(p_long));
      false;
    }
    
    // Basic logic:
    // a pixel is deletable if at least one inner pixel is next to it
    // and no "foreign" border pixels are next to it.
    
    // This leaves diagonal lines two pixels wide though
    // which can lead to them eventually shrinking down to nothing
    // (the "k" problem).
    // Idea to fix: Ignore foreign border pixels in certain directions
    
    int /*surroundingBorderPixels = 0,*/ surroundingInnerPixels = 0;
    int foreignBorderPixels = 0;
    for (int dir = 1; dir <= 8; dir++) {
      long p2_long = onePathDirection_long(p_long, dir);
      byte value = getPixel(p2_long);
      if (value == 2 && !rangeContains(pointsBuf, i, p2_long)) {
        // found a "foreign" border pixel
        //surroundingBorderPixels++;
        
        bool fix = dir == 5 || dir == 7;
        
        printVars ifdef G22RegionThinner_debug("surroundingBorderPixel", p := ptFromLong(p_long), +dir, p2 := ptFromLong(p2_long), +fix);
        // FIX (dev.)
        //if (dir < 4) false;
        if (!fix) false;
        ifdef G22RegionThinner_debug
          foreignBorderPixels |= 1 << dir;
        endifdef
      } else if (value == 1) {
        printVars ifdef G22RegionThinner_debug("surroundingInnerPixel", p := ptFromLong(p_long), +dir, p2 := ptFromLong(p2_long));
        surroundingInnerPixels++;
      }
    }

    bool deletable = /*foreignBorderPixels == 0 &&*/ surroundingInnerPixels > 0;
    
    // Fixes for certain problems follow.
    // Generally, if it's a certain pattern, the pixel must not be deleted.
    int imgPattern = neighborhoodPattern(firstIntFromLong(p_long), secondIntFromLong(p_long));
    if (imgPattern == 0b10011100 // "E" problem
     || imgPattern == 0b01000111 // "ae" problem
     || imgPattern == 0b00111001 // "a" problem
     || imgPattern == 0b00111111 // "a" problem 2
     || imgPattern == 0b10111101 // "k" problem
      ) deletable = false;
      
    // These are fixes to delete a pixel.
    else if (imgPattern == 0b11010110 // "&" problem (2x3 block)
      ) deletable = true;

    printVars ifdef G22RegionThinner_debug(p := ptFromLong(p_long), +foreignBorderPixels, +surroundingInnerPixels, +deletable,
      imgPattern := ubyteToBinary(imgPattern));
    // FIX v2
    /*if (foreignBorderPixels == ((1 << 4) | (1 << 5) | (1 << 6)))
      true;*/
      
    ret deletable;
  }
  
  bool rangeContains(LongBuffer pointsBuf, int i, long p2_long) {
    for (int j = i-3; j <= i+3; j++)
      if (cyclicGet(pointsBuf, j) == p2_long)
        true;
    false;
  }
  
  bool deletableBorderPoint_old(PtBuffer points, int i) {
    L<Pt> range = cyclicSubList_incl(points, i-3, i+3);
    Pt p = points.get(i);
    
    // special case
    if (eq(range.get(1), p) || eq(range.get(5), p)) false;
    
    int surroundingBorderPixels = 0, surroundingInnerPixels = 0;
    for (int dir = 1; dir <= 8; dir++) {
      Pt p2 = ptPlus(p, onePathDirection(dir));
      byte value = getPixel(p2);
      if (value == 2 && !range.contains(p2))
        surroundingBorderPixels++;
      else if (value == 1)
        surroundingInnerPixels++;
    }
    
    bool deletable = surroundingInnerPixels > 0 && surroundingBorderPixels == 0;
      
    printVars ifdef G22RegionThinner_debug(+p, +surroundingInnerPixels, +surroundingBorderPixels, +deletable, +range);
    ret deletable;
  }
  
  IImageRegion region aka get() { ret or(region, originalRegion); }
  
  // go from 2 pixels wide to 1 pixel wide (TODO)
  bool finalStep() {
    if (!doFinalStep) false;
    
    if (lookupTable == null)
      lookupTable = new G22RegionThinner_LookupTable()
        .lastPhaseThreshold(lastPhaseThreshold)
        .lastPhaseThreshold1(lastPhaseThreshold1)!;
    
    bool change;
    int x1 = bounds.x, x2 = bounds.x2();
    int y1 = bounds.y, y2 = bounds.y2();
    printVars ifdef G22RegionThinner_lastPhase_debug("finalStep", +x1, +y1, +x2, +y2);
    
    var pingSource = pingSource();
    
    for (int y = y1; y < y2; y++) {
      ping(pingSource);
      for (int x = x1; x < x2; x++) {
        // need a set pixel
        if (!contains(x, y)) continue;
        
        int imgPattern = neighborhoodPattern(x, y);

        // check if this pixel is essential to hold the structure
        // together by doing a floodfill in the 3x3 neighborhood
        // (simulating the pixel being cleared already)
        
        bool delete = getBit(lookupTable, imgPattern);
        
        printVars ifdef G22RegionThinner_lastPhase_debug(
          +x, +y, +imgPattern, +pixels, +delete);
        
        if (delete)
          change |= clearPixel(x, y);
      }
    }
    ret change;
  }

  int neighborhoodPattern(int x, int y) {  
    ret ubyteFromBits(
      contains(x-1, y-1),
      contains(x,   y-1),
      contains(x+1, y-1),
      contains(x-1, y),
      contains(x+1, y),
      contains(x-1, y+1),
      contains(x,   y+1),
      contains(x+1, y+1));
  }
}

Author comment

Began life as a copy of #1034965

download  show line numbers  debug dex  old transpilations   

Travelled to 4 computer(s): bhatertpkbcr, ekrmjmnbrukm, mowyntqkapby, mqqgnosmbjvj

No comments. add comment

Snippet ID: #1034983
Snippet name: G22RegionThinner_v2 - thin a region to 1 pixel wide [OK]
Eternal ID of this version: #1034983/94
Text MD5: 451e5ad93e87b23fd3ed325d33be5823
Author: stefan
Category: javax
Type: JavaX fragment (include)
Public (visible to everyone): Yes
Archived (hidden from active list): No
Created/modified: 2022-04-30 21:06:05
Source code size: 9152 bytes / 292 lines
Pitched / IR pitched: No / No
Views / Downloads: 227 / 612
Version history: 93 change(s)
Referenced in: [show references]