AbstractFastRegions (backup before optimization) [1035890]

// Abstract base class for finding all connected regions of same color
// in an image using flood filling

abstract srecord noeq AbstractFastRegions<Img extends WidthAndHeight>(Img image) is Runnable, IImageRegions<Img> {
  int w, h, runner;
  gettable int size; // =w*h
  
  new IntBuffer stack; // locations as y*w+x
  int[] regionMatrix; // for each pixel: region index (starting at 1)
  new IntBuffer regionPixels; // collect all pixels for regions
  
  settable bool withDiagonals; // also walk diagonally?
  
  // initialize these to use them
  
  new IntBuffer regionFirstPixel; // for each region: index of first pixel found in regionPixels
  new IntBuffer regionSize; // for each region: number of pixels
  new IntBuffer regionBounds; // for each region: bounds (x1, y1, x2, y2)
  
  // index = dual log of region size, value = region index
  new L<IntBuffer> regionsBySize;
  
  int regionCounter;
  bool verbose;
  
  double regionStep = .1; // for rendering in regionsImage
  
  int x(int pos) { ret pos % w; }
  int y(int pos) { ret pos / w; }
  int pos(int x, int y) { ret y*w+x; }
  Pt pt(int pos) { ret Pt(x(pos), y(pos)); }
  bool validPos(int x, int y) { ret x >= 0 && y >= 0 && x < w && y < h; }
  
  abstract int getColor(int pos);
  
  run {
    if (regionMatrix != null) ret;
    
    w = image.getWidth(); h = image.getHeight();
    size = w*h;
    regionMatrix = new int[size];
    
    // 0 entries are unused
    regionFirstPixel?.add(0); 
    regionSize?.add(0);
    
    regionPixels?.setSize(size);
    
    while (runner < size) {
      if (regionMatrix[runner] == 0) {
        // make a new region, get color
        int region = ++regionCounter;
        regionFirstPixel?.add(regionPixels != null ? l(regionPixels) : runner);
        stack.add(runner);
        int color = getColor(runner);
        int rsize = 0, x1 = w, y1 = h, x2 = 0, y2 = 0;
        ifdef FastRegions_debug
          printVars FastRegions(+region, +runner);
        endifdef

        // flood-fill region
        while (nempty(stack)) {
          int pos = stack.popLast();
          if (regionMatrix[pos] != 0) continue; // touching myself (or someone else)
          if (getColor(pos) != color) continue; // wrong color
        
          // new pixel found, mark as ours
          regionMatrix[pos] = region;
          ++rsize;
          regionPixels?.add(pos);
          int x = x(pos), y = y(pos);
          
          ifdef FastRegions_debug
            printVars FastRegions(+x, +y);
          endifdef
          
          if (x < x1) x1 = x;
          if (x > x2) x2 = x;
          if (y < y1) y1 = y;
          if (y > y2) y2 = y;

          // explore neighborhood
          if (x > 0)   stack.add(pos-1);
          if (x < w-1) stack.add(pos+1);
          if (y > 0)   stack.add(pos-w);
          if (y < h-1) stack.add(pos+w);
          
          if (withDiagonals) {
            if (y > 0) {
              if (x > 0)   stack.add(pos-w-1);
              if (x < w-1) stack.add(pos-w+1);
            }
            if (y < h-1) {
              if (x > 0)   stack.add(pos+w-1);
              if (x < w-1) stack.add(pos+w+1);
            }
          }
        }
        
        regionSize?.add(rsize);
        regionBounds?.addAll(x1, y1, x2+1, y2+1);
        if (regionsBySize != null) {
          int iBucket = dualLog(rsize);
          var buffer = listGetOrCreate(regionsBySize, iBucket, -> new IntBuffer);
          buffer.add(region);
        }
      }
      
      ++runner;
    }
  }
  
  IBWImage regionsImage() {
    ret iBWImageFromFunction((x, y) -> {
      var region = regionMatrix[pos(x, y)];
      ret ((region-1)*regionStep) % (1.0+regionStep-0.0001);
    }, w, h);
  }
  
  int regionCount aka nRegions() { ret regionCounter; }
  
  abstract class RegionIterator {
    int pos;
    
    abstract bool next();
    
    int pos() { ret pos; }
    int x() { ret AbstractFastRegions.this.x(pos); }
    int y() { ret AbstractFastRegions.this.y(pos); }
  }
  
  // returns points in no particular order
  class FloodRegionIterator > RegionIterator {
    int region;
    new IntBuffer stack; // locations as y*w+x
    BitSet seen = new(size);
    
    *(int *region) {
      int pos = regionFirstPixel.get(region);
      printVars(+region, +pos);
      seen.set(pos);
      stack.add(pos);
    }
    
    // flood-fill region
    bool next() {
      if (empty(stack)) false;
      
      pos = stack.popLast();

      // explore neighborhood
      int x = x(), y = y();
      if (x > 0)   tryPosition(pos-1);
      if (x < w-1) tryPosition(pos+1);
      if (y > 0)   tryPosition(pos-w);
      if (y < h-1) tryPosition(pos+w);

      true;
    }
    
    private void tryPosition(int p) {
      if (!seen.get(p) && regionMatrix[p] == region) {
        seen.set(p);
        stack.add(p);
      }
    }
  }
  
  class CachedRegionIterator > RegionIterator {
    int i, to;

    *(int region) {
      i = regionFirstPixel.get(region);
      to = region+1 < l(regionFirstPixel) ? regionFirstPixel.get(region+1) : l(regionPixels);
      
      ifdef FastRegions_debug
        printVars CachedRegionIterator(+region, +i, +to);
      endifdef
    }
    
    bool next() {
      if (i >= to) false;
      pos = regionPixels.get(i++);
      true;
    }
  }
  
  int regionSize(int iRegion) { ret regionSize.get(iRegion); }
  
  Pt samplePixel aka firstPixel(int iRegion) {
    ret pt(firstPixelPos(iRegion));
  }
  
  int firstPixelPos(int iRegion) {
    int i = regionFirstPixel.get(iRegion);
    ret regionPixels != null ? regionPixels.get(i) : i;
  }
  
  bool inRegion(int iRegion, int x, int y) {
    ret validPos(x, y) && regionMatrix[pos(x, y)] == iRegion;
  }
  Rect regionBounds(int iRegion) { ret rectFromPoints(
    regionBounds.get((iRegion-1)*4),
    regionBounds.get((iRegion-1)*4+1),
    regionBounds.get((iRegion-1)*4+2),
    regionBounds.get((iRegion-1)*4+3),
  ); }
  
  int regionAt(Pt p) { ret regionAt(p.x, p.y); }
  
  int regionAt(int x, int y) {
    ret !validPos(x, y) ? 0 : regionMatrix[pos(x, y)];
  }
  
  int regionAt(int pos) {
    ret regionMatrix[pos];
  }
  
  RegionIterator regionIterator(int iRegion) {
    ret regionPixels != null
      ? new CachedRegionIterator(iRegion)
      : new FloodRegionIterator(iRegion);
  }
  
  L<Pt> regionPixels(int iRegion) {
    var it = regionIterator(iRegion);
    new L<Pt> l;
    while (it.next())
      l.add(Pt(it.x(), it.y()));
    ret l;
  }
  
  // select extra features before regions are made
  // (not necessary anymore)
  
  void collectFirstPixels { /*regionFirstPixel = new IntBuffer;*/ }
  void collectBounds { /*regionBounds = new IntBuffer;*/ }
  
  BitMatrix regionBitMatrix(int iRegion) {
    ret new AbstractBitMatrix(w, h) {
      public Bool get(int x, int y) {
        ret inRegion(iRegion, x, y);
      }
    };
  }
  
  void markRegionInPixelArray(int[] pixels, int iRegion, int rgba) {
    if (iRegion <= 0) ret;
    for i over pixels:
      if (regionAt(i) == iRegion)
        pixels[i] = rgba;
  }
  
  L<Int> regionIndices() { ret virtualCountList(1, nRegions()+1); }
  
  ItIt<Int> regionsRoughlyByDecreasingSize() {
    ret nestedIterator(countIterator_inclusive_backwards(regionsBySize.size()-1, 0),
      iBucket -> iterator(regionsBySize.get(iBucket)));
  }
  
  IImageRegion<Img> getRegion aka get(int iRegion) {
    ret new ImageRegion(iRegion);
  }
  
  public L<IImageRegion<Img>> regions aka get() {
    run();
    ret listFromFunction(i -> getRegion(i+1), nRegions());
  }
  
  record noeq ImageRegion(int iRegion) is IImageRegion<Img> {
    public int hashCode() { ret iRegion; }
    public bool equals(O o) {
      if (!o instanceof AbstractFastRegions.ImageRegion) false;
      ret ((AbstractFastRegions.ImageRegion) o).creator() == creator()
        && ((AbstractFastRegions.ImageRegion) o).iRegion == iRegion;
    }
    
    public Img image() { ret image; }
    public O creator() { ret AbstractFastRegions.this; }
    public int indexInCreator() { ret iRegion; }
    public Bool createdWithDiagonals() { ret withDiagonals; }
  
    public Rect bounds() { ret regionBounds(iRegion); }
    
    public int numberOfPixels() { ret regionSize(iRegion); }
    
    public Pt firstPixel() { ret pt(firstPixelPos()); }
    public int firstPixelPos() { ret AbstractFastRegions.this.firstPixelPos(iRegion); }
    
    public ItIt<Pt> pixelIterator() {
      var it = regionIterator(iRegion);
      ret iteratorFromFunction(-> it.next() ? pt(it.pos()) : null);
    }
    
    public bool contains(int x, int y) { ret inRegion(iRegion, x, y); }
    
    public Color color() {
      ret toColor(rgbForRegion(this));
    }
    
    public int brightness aka firstPixelLogicalColor() {
      ret getColor(firstPixelPos());
    }
    
    toString {
      ret renderRecordVars("Region", +brightness(), +color(), pixels := numberOfPixels(), +bounds());
    }
  }
  
  abstract RGB rgbForRegion(ImageRegion r);
}

Snippet ID:	#1035890
Snippet name:	AbstractFastRegions (backup before optimization)
Eternal ID of this version:	#1035890/1
Text MD5:	9361a1f6ee5ef5241097c01f69510d56
Author:	stefan
Category:	javax / imaging
Type:	JavaX fragment (include)
Public (visible to everyone):	Yes
Archived (hidden from active list):	No
Created/modified:	2022-08-07 20:06:38
Source code size:	9238 bytes / 311 lines
Pitched / IR pitched:	No / No
Views / Downloads:	126 / 131
Referenced in:	[show references]

< > BotCompany Repo | #1035890 // AbstractFastRegions (backup before optimization)

JavaX fragment (include)

Author comment

1	// Abstract base class for finding all connected regions of same color
2	// in an image using flood filling
3
4	abstract srecord noeq AbstractFastRegions<Img extends WidthAndHeight>(Img image) is Runnable, IImageRegions<Img> {
5	int w, h, runner;
6	gettable int size; // =w*h
7
8	new IntBuffer stack; // locations as y*w+x
9	int[] regionMatrix; // for each pixel: region index (starting at 1)
10	new IntBuffer regionPixels; // collect all pixels for regions
11
12	settable bool withDiagonals; // also walk diagonally?
13
14	// initialize these to use them
15
16	new IntBuffer regionFirstPixel; // for each region: index of first pixel found in regionPixels
17	new IntBuffer regionSize; // for each region: number of pixels
18	new IntBuffer regionBounds; // for each region: bounds (x1, y1, x2, y2)
19
20	// index = dual log of region size, value = region index
21	new L<IntBuffer> regionsBySize;
22
23	int regionCounter;
24	bool verbose;
25
26	double regionStep = .1; // for rendering in regionsImage
27
28	int x(int pos) { ret pos % w; }
29	int y(int pos) { ret pos / w; }
30	int pos(int x, int y) { ret y*w+x; }
31	Pt pt(int pos) { ret Pt(x(pos), y(pos)); }
32	bool validPos(int x, int y) { ret x >= 0 && y >= 0 && x < w && y < h; }
33
34	abstract int getColor(int pos);
35
36	run {
37	if (regionMatrix != null) ret;
38
39	w = image.getWidth(); h = image.getHeight();
40	size = w*h;
41	regionMatrix = new int[size];
42
43	// 0 entries are unused
44	regionFirstPixel?.add(0);
45	regionSize?.add(0);
46
47	regionPixels?.setSize(size);
48
49	while (runner < size) {
50	if (regionMatrix[runner] == 0) {
51	// make a new region, get color
52	int region = ++regionCounter;
53	regionFirstPixel?.add(regionPixels != null ? l(regionPixels) : runner);
54	stack.add(runner);
55	int color = getColor(runner);
56	int rsize = 0, x1 = w, y1 = h, x2 = 0, y2 = 0;
57	ifdef FastRegions_debug
58	printVars FastRegions(+region, +runner);
59	endifdef
60
61	// flood-fill region
62	while (nempty(stack)) {
63	int pos = stack.popLast();
64	if (regionMatrix[pos] != 0) continue; // touching myself (or someone else)
65	if (getColor(pos) != color) continue; // wrong color
66
67	// new pixel found, mark as ours
68	regionMatrix[pos] = region;
69	++rsize;
70	regionPixels?.add(pos);
71	int x = x(pos), y = y(pos);
72
73	ifdef FastRegions_debug
74	printVars FastRegions(+x, +y);
75	endifdef
76
77	if (x < x1) x1 = x;
78	if (x > x2) x2 = x;
79	if (y < y1) y1 = y;
80	if (y > y2) y2 = y;
81
82	// explore neighborhood
83	if (x > 0) stack.add(pos-1);
84	if (x < w-1) stack.add(pos+1);
85	if (y > 0) stack.add(pos-w);
86	if (y < h-1) stack.add(pos+w);
87
88	if (withDiagonals) {
89	if (y > 0) {
90	if (x > 0) stack.add(pos-w-1);
91	if (x < w-1) stack.add(pos-w+1);
92	}
93	if (y < h-1) {
94	if (x > 0) stack.add(pos+w-1);
95	if (x < w-1) stack.add(pos+w+1);
96	}
97	}
98	}
99
100	regionSize?.add(rsize);
101	regionBounds?.addAll(x1, y1, x2+1, y2+1);
102	if (regionsBySize != null) {
103	int iBucket = dualLog(rsize);
104	var buffer = listGetOrCreate(regionsBySize, iBucket, -> new IntBuffer);
105	buffer.add(region);
106	}
107	}
108
109	++runner;
110	}
111	}
112
113	IBWImage regionsImage() {
114	ret iBWImageFromFunction((x, y) -> {
115	var region = regionMatrix[pos(x, y)];
116	ret ((region-1)*regionStep) % (1.0+regionStep-0.0001);
117	}, w, h);
118	}
119
120	int regionCount aka nRegions() { ret regionCounter; }
121
122	abstract class RegionIterator {
123	int pos;
124
125	abstract bool next();
126
127	int pos() { ret pos; }
128	int x() { ret AbstractFastRegions.this.x(pos); }
129	int y() { ret AbstractFastRegions.this.y(pos); }
130	}
131
132	// returns points in no particular order
133	class FloodRegionIterator > RegionIterator {
134	int region;
135	new IntBuffer stack; // locations as y*w+x
136	BitSet seen = new(size);
137
138	(int region) {
139	int pos = regionFirstPixel.get(region);
140	printVars(+region, +pos);
141	seen.set(pos);
142	stack.add(pos);
143	}
144
145	// flood-fill region
146	bool next() {
147	if (empty(stack)) false;
148
149	pos = stack.popLast();
150
151	// explore neighborhood
152	int x = x(), y = y();
153	if (x > 0) tryPosition(pos-1);
154	if (x < w-1) tryPosition(pos+1);
155	if (y > 0) tryPosition(pos-w);
156	if (y < h-1) tryPosition(pos+w);
157
158	true;
159	}
160
161	private void tryPosition(int p) {
162	if (!seen.get(p) && regionMatrix[p] == region) {
163	seen.set(p);
164	stack.add(p);
165	}
166	}
167	}
168
169	class CachedRegionIterator > RegionIterator {
170	int i, to;
171
172	*(int region) {
173	i = regionFirstPixel.get(region);
174	to = region+1 < l(regionFirstPixel) ? regionFirstPixel.get(region+1) : l(regionPixels);
175
176	ifdef FastRegions_debug
177	printVars CachedRegionIterator(+region, +i, +to);
178	endifdef
179	}
180
181	bool next() {
182	if (i >= to) false;
183	pos = regionPixels.get(i++);
184	true;
185	}
186	}
187
188	int regionSize(int iRegion) { ret regionSize.get(iRegion); }
189
190	Pt samplePixel aka firstPixel(int iRegion) {
191	ret pt(firstPixelPos(iRegion));
192	}
193
194	int firstPixelPos(int iRegion) {
195	int i = regionFirstPixel.get(iRegion);
196	ret regionPixels != null ? regionPixels.get(i) : i;
197	}
198
199	bool inRegion(int iRegion, int x, int y) {
200	ret validPos(x, y) && regionMatrix[pos(x, y)] == iRegion;
201	}
202	Rect regionBounds(int iRegion) { ret rectFromPoints(
203	regionBounds.get((iRegion-1)*4),
204	regionBounds.get((iRegion-1)*4+1),
205	regionBounds.get((iRegion-1)*4+2),
206	regionBounds.get((iRegion-1)*4+3),
207	); }
208
209	int regionAt(Pt p) { ret regionAt(p.x, p.y); }
210
211	int regionAt(int x, int y) {
212	ret !validPos(x, y) ? 0 : regionMatrix[pos(x, y)];
213	}
214
215	int regionAt(int pos) {
216	ret regionMatrix[pos];
217	}
218
219	RegionIterator regionIterator(int iRegion) {
220	ret regionPixels != null
221	? new CachedRegionIterator(iRegion)
222	: new FloodRegionIterator(iRegion);
223	}
224
225	L<Pt> regionPixels(int iRegion) {
226	var it = regionIterator(iRegion);
227	new L<Pt> l;
228	while (it.next())
229	l.add(Pt(it.x(), it.y()));
230	ret l;
231	}
232
233	// select extra features before regions are made
234	// (not necessary anymore)
235
236	void collectFirstPixels { /regionFirstPixel = new IntBuffer;/ }
237	void collectBounds { /regionBounds = new IntBuffer;/ }
238
239	BitMatrix regionBitMatrix(int iRegion) {
240	ret new AbstractBitMatrix(w, h) {
241	public Bool get(int x, int y) {
242	ret inRegion(iRegion, x, y);
243	}
244	};
245	}
246
247	void markRegionInPixelArray(int[] pixels, int iRegion, int rgba) {
248	if (iRegion <= 0) ret;
249	for i over pixels:
250	if (regionAt(i) == iRegion)
251	pixels[i] = rgba;
252	}
253
254	L<Int> regionIndices() { ret virtualCountList(1, nRegions()+1); }
255
256	ItIt<Int> regionsRoughlyByDecreasingSize() {
257	ret nestedIterator(countIterator_inclusive_backwards(regionsBySize.size()-1, 0),
258	iBucket -> iterator(regionsBySize.get(iBucket)));
259	}
260
261	IImageRegion<Img> getRegion aka get(int iRegion) {
262	ret new ImageRegion(iRegion);
263	}
264
265	public L<IImageRegion<Img>> regions aka get() {
266	run();
267	ret listFromFunction(i -> getRegion(i+1), nRegions());
268	}
269
270	record noeq ImageRegion(int iRegion) is IImageRegion<Img> {
271	public int hashCode() { ret iRegion; }
272	public bool equals(O o) {
273	if (!o instanceof AbstractFastRegions.ImageRegion) false;
274	ret ((AbstractFastRegions.ImageRegion) o).creator() == creator()
275	&& ((AbstractFastRegions.ImageRegion) o).iRegion == iRegion;
276	}
277
278	public Img image() { ret image; }
279	public O creator() { ret AbstractFastRegions.this; }
280	public int indexInCreator() { ret iRegion; }
281	public Bool createdWithDiagonals() { ret withDiagonals; }
282
283	public Rect bounds() { ret regionBounds(iRegion); }
284
285	public int numberOfPixels() { ret regionSize(iRegion); }
286
287	public Pt firstPixel() { ret pt(firstPixelPos()); }
288	public int firstPixelPos() { ret AbstractFastRegions.this.firstPixelPos(iRegion); }
289
290	public ItIt<Pt> pixelIterator() {
291	var it = regionIterator(iRegion);
292	ret iteratorFromFunction(-> it.next() ? pt(it.pos()) : null);
293	}
294
295	public bool contains(int x, int y) { ret inRegion(iRegion, x, y); }
296
297	public Color color() {
298	ret toColor(rgbForRegion(this));
299	}
300
301	public int brightness aka firstPixelLogicalColor() {
302	ret getColor(firstPixelPos());
303	}
304
305	toString {
306	ret renderRecordVars("Region", +brightness(), +color(), pixels := numberOfPixels(), +bounds());
307	}
308	}
309
310	abstract RGB rgbForRegion(ImageRegion r);
311	}