Engauge Digitizer  2
Pixels.cpp
Go to the documentation of this file.
1 /******************************************************************************************************
2  * (C) 2018 markummitchell@github.com. This file is part of Engauge Digitizer, which is released *
3  * under GNU General Public License version 2 (GPLv2) or (at your option) any later version. See file *
4  * LICENSE or go to gnu.org/licenses for details. Distribution requires prior written permission. *
5  ******************************************************************************************************/
6 
7 #include "Pixels.h"
8 #include <QImage>
9 #include <qmath.h>
10 #include <QRgb>
11 
13 {
14 }
15 
16 int Pixels::countBlackPixelsAroundPoint (const QImage &image,
17  int x,
18  int y,
19  int stopCountAt)
20 {
21  int count = 0;
22  QueuedPoints queuedPoints;
23  HashLookup hashLookup; // Prevents reprocessing of already-processed pixels
24 
25  // First point
26  if (pixelIsBlack (image, x, y)) {
27  queuedPoints.push_back (QPoint (x, y));
28  }
29 
30  while (queuedPoints.count () > 0) {
31 
32  // Pop off queue
33  QPoint p = queuedPoints.front ();
34  queuedPoints.pop_front ();
35 
36  QString hash = hashForCoordinates (p.x(),
37  p.y());
38 
39  // Skip if out of bounds, processed already or not black
40  bool inBounds = (0 <= p.x() &&
41  0 <= p.y() &&
42  p.x() < image.width () &&
43  p.y() < image.height ());
44  if (inBounds &&
45  !hashLookup.contains (hash) &&
46  pixelIsBlack (image, p.x(), p.y())) {
47 
48  // Black pixel. Add to count, and remember to not reprocess later
49  ++count;
50  if (count == stopCountAt) {
51  return count; // Reached limit. Stop immediately (probably for speed)
52  }
53  hashLookup [hash] = true;
54 
55  // Queue neighbors for processing
56  for (int dx = -1; dx <= 1; dx++) {
57  for (int dy = -1; dy <= 1; dy++) {
58  if (dx != 0 || dy != 0) {
59  queuedPoints.push_back (QPoint (p.x() + dx,
60  p.y() + dy));
61  }
62  }
63  }
64  }
65  }
66 
67  return count; // Did not reach limit
68 }
69 
70 void Pixels::fillHole (QImage &image,
71  int row,
72  int col,
73  int thresholdCount) const
74 {
75  // Square of 1 pixel is surrounded by 3x3 box with indexes -1 to +2
76  // 2-4 pixels 4x4 -2 to +2
77  // 5-9 5x5 -2 to +3
78  // 10-16 6x6 -3 to +3
79  int rowStart = qFloor (row - (1 + qSqrt (thresholdCount - 1))); // Inclusive
80  int colStart = qFloor (col - (1 + qSqrt (thresholdCount - 1))); // Inclusive
81  int rowStop = qFloor (row + (1 + qSqrt (thresholdCount))); // Exclusive
82  int colStop = qFloor (col + (1 + qSqrt (thresholdCount))); // Exclusive
83 
84  // First pass is for counting
85  int countWhite = 0;
86  for (int rowIter = rowStart; rowIter < rowStop; rowIter++) {
87  for (int colIter = colStart; colIter < colStop; colIter++) {
88  if (!pixelIsBlack (image,
89  colIter,
90  rowIter)) {
91  ++countWhite;
92  }
93  }
94  }
95 
96  // Second pass fills in the hole
97  if (countWhite < thresholdCount) {
98  for (int rowIter = rowStart; rowIter < rowStop; rowIter++) {
99  for (int colIter = colStart; colIter < colStop; colIter++) {
100  image.setPixel (colIter,
101  rowIter,
102  Qt::black);
103  }
104  }
105  }
106 }
107 
108 void Pixels::fillHoles (QImage &image,
109  int thresholdCount)
110 {
111  int height = image.height();
112  int width = image.width();
113 
114  // 2d matrix, indexed as 1d vector, of pixel states
115  QVector<PixelFillState> states (image.width() * image.height());
116  states.fill (PIXEL_FILL_STATE_UNPROCESSED);
117 
118  // Search for unprocessed pixels
119  for (int col = 0; col < width; col++) {
120  for (int row = 0; row < height; row++) {
121  if (states [indexCollapse (row, col, width)] == PIXEL_FILL_STATE_UNPROCESSED) {
122 
123  // Found an unprocessed pixel so process it
124  if (pixelIsBlack (image, col, row)) {
125 
126  // Black pixel needs no processing
127  states [indexCollapse (row, col, width)] = PIXEL_FILL_STATE_PROCESSED;
128 
129  } else {
130 
131  // Get this pixel and all of its white neighbors
132  int pixelsInRegion = fillPass (image,
133  states,
134  row,
135  col,
138  NO_FILL);
139 
140  FillIt fillIt = (pixelsInRegion < thresholdCount) ? YES_FILL : NO_FILL;
141 
142  fillPass (image,
143  states,
144  row,
145  col,
148  fillIt);
149  }
150  }
151  }
152  }
153 }
154 
156 {
157  const int BORDER = 1;
158  const int HALF_NUMBER_NEIGHBORS = 4; // 8 neighbors in each direction from (col,row)
159 
160  int height = image.height();
161  int width = image.width();
162 
163  // 2d matrix, indexed as 1d vector, of neighbor counts
164  QVector<bool> pixelsAreBlack (image.width() * image.height());
165 
166  // Replace slow QImage addressing by faster QVector addressing
167  for (int col = 0; col < width; col++) {
168  for (int row = 0; row < height; row++) {
169  pixelsAreBlack [indexCollapse (row, col, width)] = pixelIsBlack (image, col, row);
170  }
171  }
172 
173  // Search for white pixels. Black pixels will be ignored, and also pixels along the four
174  // borders are ignored so we do not need to worry about going out of bounds
175  for (int col = BORDER; col < width - BORDER; col++) {
176  for (int row = BORDER; row < height - BORDER; row++) {
177  int count = 0;
178  count += pixelsAreBlack [indexCollapse (row - 1, col - 1, width)] ? 1 : 0;
179  count += pixelsAreBlack [indexCollapse (row - 1, col , width)] ? 1 : 0;
180  count += pixelsAreBlack [indexCollapse (row - 1, col + 1, width)] ? 1 : 0;
181  count += pixelsAreBlack [indexCollapse (row , col - 1, width)] ? 1 : 0;
182  count += pixelsAreBlack [indexCollapse (row , col + 1, width)] ? 1 : 0;
183  count += pixelsAreBlack [indexCollapse (row + 1, col - 1, width)] ? 1 : 0;
184  count += pixelsAreBlack [indexCollapse (row + 1, col , width)] ? 1 : 0;
185  count += pixelsAreBlack [indexCollapse (row + 1, col + 1, width)] ? 1 : 0;
186  if (count > HALF_NUMBER_NEIGHBORS) {
187  image.setPixel (col,
188  row,
189  Qt::black);
190  }
191  }
192  }
193 }
194 
195 int Pixels::fillPass (QImage &image,
196  QVector<PixelFillState> &states,
197  int rowIn,
198  int colIn,
199  PixelFillState stateFrom,
200  PixelFillState stateTo,
201  FillIt fillit)
202 {
203  int height = image.height();
204  int width = image.width ();
205  int count = 0;
206  QList<QPoint> applicablePoints;
207 
208  // Add only applicable points to the running list
209  applicablePoints.append (QPoint (colIn, rowIn));
210 
211  while (applicablePoints.count() > 0) {
212 
213  QPoint p = applicablePoints.front();
214  applicablePoints.pop_front();
215 
216  int col = p.x();
217  int row = p.y();
218 
219  // Double check point is still applicable and that has not changed since added to list
220  PixelFillState stateGot = states [indexCollapse (row, col, width)];
221  if (stateGot == stateFrom &&
222  !pixelIsBlack (image,
223  col,
224  row)) {
225 
226  // Still applicable. Do state-specific stuff here
227  if (stateTo == PIXEL_FILL_STATE_IN_PROCESS) {
228  ++count;
229  } else {
230  if (fillit == YES_FILL) {
231  image.setPixel (col, row, Qt::black);
232  }
233  }
234 
235  // Change state to prevent reprocessing
236  states [indexCollapse (row, col, width)] = stateTo;
237 
238  // "Recurse" using list instead of actual recursion (to prevent stack overflow)
239  for (int dx = -1; dx <= 1; dx++) {
240  int colD = col + dx;
241  if (0 <= colD && colD < width) {
242 
243  for (int dy = -1; dy <= 1; dy++) {
244  int rowD = row + dy;
245  if (0 <= rowD && rowD < height) {
246 
247  if (dx != 0 || dy != 0) {
248 
249  PixelFillState stateGot = states [indexCollapse (rowD, colD, width)];
250  if (stateGot == stateFrom &&
251  !pixelIsBlack (image,
252  colD,
253  rowD)) {
254 
255  // This point is applicable
256  applicablePoints.append (QPoint (colD, rowD));
257  }
258  }
259  }
260  }
261  }
262  }
263  }
264  }
265 
266  return count;
267 }
268 
269 QString Pixels::hashForCoordinates (int x,
270  int y) const
271 {
272  const int FIELD_WIDTH = 6;
273 
274  return QString ("%1/%2")
275  .arg (x, FIELD_WIDTH)
276  .arg (y, FIELD_WIDTH);
277 }
278 
279 int Pixels::indexCollapse (int row,
280  int col,
281  int width) const
282 {
283  return row * width + col;
284 }
285 
286 bool Pixels::pixelIsBlack (const QImage &image,
287  int x,
288  int y)
289 {
290  QRgb rgb = image.pixel (x, y);
291  return qGray (rgb) < 128;
292 }
293 
void fillHole(QImage &image, int row, int col, int thresholdCount) const
Fill white hole encompassing (row,col) if number of pixels in that hole is below the threshold.
Definition: Pixels.cpp:70
QQueue< QPoint > QueuedPoints
Definition: Pixels.h:21
void fillIsolatedWhitePixels(QImage &image)
Fill in white pixels surrounded by more black pixels than white pixels.
Definition: Pixels.cpp:155
PixelFillState
Each pixel transitions from unprocessed, to in-process, to processed.
Definition: Pixels.h:24
QMap< QString, bool > HashLookup
Quick lookup table for pixel coordinate hashes processed so far.
Definition: Pixels.h:16
int countBlackPixelsAroundPoint(const QImage &image, int x, int y, int stopCountAt)
Fill triangle between these three points.
Definition: Pixels.cpp:16
void fillHoles(QImage &image, int thresholdCount)
Fill in white holes, surrounded by black pixels, smaller than some threshold number of pixels.
Definition: Pixels.cpp:108
static bool pixelIsBlack(const QImage &image, int x, int y)
Return true if pixel is black in black and white image.
Definition: Pixels.cpp:286
Pixels()
Single constructor.
Definition: Pixels.cpp:12