Engauge Digitizer  2
SegmentFactory.cpp
1 /******************************************************************************************************
2  * (C) 2014 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 "ColorFilter.h"
8 #include "DocumentModelSegments.h"
9 #include "EngaugeAssert.h"
10 #include "Logger.h"
11 #include <QApplication>
12 #include <QGraphicsScene>
13 #include <qmath.h>
14 #include <QProgressDialog>
15 #include "Segment.h"
16 #include "SegmentFactory.h"
17 #include <vector>
18 
19 using namespace std;
20 
21 SegmentFactory::SegmentFactory(QGraphicsScene &scene,
22  bool isGnuplot) :
23  m_scene (scene),
24  m_isGnuplot (isGnuplot)
25 {
26  LOG4CPP_INFO_S ((*mainCat)) << "SegmentFactory::SegmentFactory";
27 }
28 
29 int SegmentFactory::adjacentRuns(bool *columnBool,
30  int yStart,
31  int yStop,
32  int height)
33 {
34  int runs = 0;
35  bool inRun = false;
36  for (int y = yStart - 1; y <= yStop + 1; y++) {
37  if ((0 <= y) && (y < height)) {
38  if (!inRun && columnBool [y]) {
39  inRun = true;
40  ++runs;
41  } else if (inRun && !columnBool [y]) {
42  inRun = false;
43  }
44  }
45  }
46 
47  return runs;
48 }
49 
50 Segment *SegmentFactory::adjacentSegment(SegmentVector &lastSegment,
51  int yStart,
52  int yStop,
53  int height)
54 {
55  for (int y = yStart - 1; y <= yStop + 1; y++) {
56  if ((0 <= y) && (y < height)) {
57 
58  ENGAUGE_ASSERT (y < height);
59  if (lastSegment [unsigned (y)]) {
60  return lastSegment [unsigned (y)];
61  }
62  }
63  }
64 
65  return nullptr;
66 }
67 
68 int SegmentFactory::adjacentSegments(SegmentVector &lastSegment,
69  int yStart,
70  int yStop,
71  int height)
72 {
73  int adjacentSegments = 0;
74 
75  bool inSegment = false;
76  for (int y = yStart - 1; y <= yStop + 1; y++) {
77  if ((0 <= y) && (y < height)) {
78 
79  ENGAUGE_ASSERT (y < height);
80  if (!inSegment && lastSegment [unsigned (y)]) {
81 
82  inSegment = true;
83  ++adjacentSegments;
84  } else if (inSegment && !lastSegment [unsigned (y)]) {
85  inSegment = false;
86  }
87  }
88  }
89 
90  return adjacentSegments;
91 }
92 
93 QList<QPoint> SegmentFactory::fillPoints(const DocumentModelSegments &modelSegments,
94  QList<Segment*> segments)
95 {
96  LOG4CPP_INFO_S ((*mainCat)) << "SegmentFactory::fillPoints";
97 
98  QList<QPoint> list;
99  QList<Segment*>::iterator itr;
100  for (itr = segments.begin (); itr != segments.end(); itr++) {
101 
102  Segment *segment = *itr;
103  ENGAUGE_CHECK_PTR(segment);
104  list += segment->fillPoints(modelSegments);
105  }
106 
107  return list;
108 }
109 
110 void SegmentFactory::finishRun(bool *lastBool,
111  bool *nextBool,
112  SegmentVector &lastSegment,
113  SegmentVector &currSegment,
114  int x,
115  int yStart,
116  int yStop,
117  int height,
118  const DocumentModelSegments &modelSegments,
119  int* madeLines)
120 {
121  LOG4CPP_DEBUG_S ((*mainCat)) << "SegmentFactory::finishRun"
122  << " column=" << x
123  << " rows=" << yStart << "-" << yStop
124  << " runsOnLeft=" << adjacentRuns (nextBool, yStart, yStop, height)
125  << " runsOnRight=" << adjacentSegments (lastSegment, yStart, yStop, height);
126 
127  // When looking at adjacent columns, include pixels that touch diagonally since
128  // those may also diagonally touch nearby runs in the same column (which would indicate
129  // a branch)
130 
131  // Count runs that touch on the left
132  if (adjacentRuns(lastBool, yStart, yStop, height) > 1) {
133  return;
134  }
135 
136  // Count runs that touch on the right
137  if (adjacentRuns(nextBool, yStart, yStop, height) > 1) {
138  return;
139  }
140 
141  Segment *seg;
142  if (adjacentSegments(lastSegment, yStart, yStop, height) == 0) {
143 
144  // This is the start of a new segment
145  seg = new Segment(m_scene,
146  qFloor (0.5 + (yStart + yStop) / 2.0),
147  m_isGnuplot);
148  ENGAUGE_CHECK_PTR (seg);
149 
150  } else {
151 
152  // This is the continuation of an existing segment
153  seg = adjacentSegment(lastSegment, yStart, yStop, height);
154 
155  ++(*madeLines);
156  ENGAUGE_CHECK_PTR(seg);
157  seg->appendColumn(x, qFloor (0.5 + (yStart + yStop) / 2.0), modelSegments);
158  }
159 
160  for (int y = yStart; y <= yStop; y++) {
161 
162  ENGAUGE_ASSERT (y < height);
163  currSegment [unsigned (y)] = seg;
164  }
165 }
166 
167 void SegmentFactory::loadBool (const ColorFilter &filter,
168  bool *columnBool,
169  const QImage &image,
170  int x)
171 {
172  for (int y = 0; y < image.height(); y++) {
173  if (x < 0) {
174  columnBool [y] = false;
175  } else {
176  columnBool [y] = filter.pixelFilteredIsOn (image, x, y);
177  }
178  }
179 }
180 
181 void SegmentFactory::loadSegment (SegmentVector &columnSegment,
182  int height)
183 {
184  for (int y = 0; y < height; y++) {
185  columnSegment [unsigned (y)] = nullptr;
186  }
187 }
188 
189 void SegmentFactory::makeSegments (const QImage &imageFiltered,
190  const DocumentModelSegments &modelSegments,
191  QList<Segment*> &segments,
192  bool useDlg)
193 {
194  LOG4CPP_INFO_S ((*mainCat)) << "SegmentFactory::makeSegments";
195 
196  // Statistics that show up in debug spew
197  int madeLines = 0;
198  int shortLines = 0; // Lines rejected since their segments are too short
199  int foldedLines = 0; // Lines rejected since they could be into other lines
200 
201  // For each new column of pixels, loop through the runs. a run is defined as
202  // one or more colored pixels that are all touching, with one uncolored pixel or the
203  // image boundary at each end of the set. for each set in the current column, count
204  // the number of runs it touches in the adjacent (left and right) columns. here is
205  // the pseudocode:
206  // if ((L > 1) || (R > 1))
207  // "this run is at a branch point so ignore the set"
208  // else
209  // if (L == 0)
210  // "this run is the start of a new segment"
211  // else
212  // "this run is appended to the segment on the left
213  int width = imageFiltered.width();
214  int height = imageFiltered.height();
215 
216  QProgressDialog* dlg = nullptr;
217  if (useDlg)
218  {
219 
220  dlg = new QProgressDialog("Scanning segments in image", "Cancel", 0, width);
221  ENGAUGE_CHECK_PTR (dlg);
222  dlg->show();
223  }
224 
225  bool* lastBool = new bool [unsigned (height)];
226  ENGAUGE_CHECK_PTR(lastBool);
227  bool* currBool = new bool [unsigned (height)];
228  ENGAUGE_CHECK_PTR(currBool);
229  bool* nextBool = new bool [unsigned (height)];
230  ENGAUGE_CHECK_PTR(nextBool);
231  SegmentVector lastSegment (static_cast<unsigned long> (height));
232  SegmentVector currSegment (static_cast<unsigned long> (height));
233 
234  ColorFilter filter;
235  loadBool(filter, lastBool, imageFiltered, -1);
236  loadBool(filter, currBool, imageFiltered, 0);
237  loadBool(filter, nextBool, imageFiltered, 1);
238  loadSegment(lastSegment, height);
239 
240  for (int x = 0; x < width; x++) {
241 
242  if (useDlg) {
243 
244  // Update progress bar
245  dlg->setValue(x);
246  qApp->processEvents();
247 
248  if (dlg->wasCanceled()) {
249 
250  // Quit scanning. only existing segments will be available
251  break;
252  }
253  }
254 
255  matchRunsToSegments(x,
256  height,
257  lastBool,
258  lastSegment,
259  currBool,
260  currSegment,
261  nextBool,
262  modelSegments,
263  &madeLines,
264  &foldedLines,
265  &shortLines,
266  segments);
267 
268  // Get ready for next column
269  scrollBool(lastBool, currBool, height);
270  scrollBool(currBool, nextBool, height);
271  if (x + 1 < width) {
272  loadBool(filter, nextBool, imageFiltered, x + 1);
273  }
274  scrollSegment(lastSegment, currSegment, height);
275  }
276 
277  if (useDlg) {
278 
279  dlg->setValue(width);
280  delete dlg;
281  }
282 
283  removeEmptySegments (segments);
284 
285  LOG4CPP_INFO_S ((*mainCat)) << "SegmentFactory::makeSegments"
286  << " linesCreated=" << madeLines
287  << " linesTooShortSoRemoved=" << shortLines
288  << " linesFoldedTogether=" << foldedLines;
289 
290  delete[] lastBool;
291  delete[] currBool;
292  delete[] nextBool;
293 }
294 
295 void SegmentFactory::matchRunsToSegments(int x,
296  int height,
297  bool *lastBool,
298  SegmentVector &lastSegment,
299  bool* currBool,
300  SegmentVector &currSegment,
301  bool *nextBool,
302  const DocumentModelSegments &modelSegments,
303  int *madeLines,
304  int *foldedLines,
305  int *shortLines,
306  QList<Segment*> &segments)
307 {
308  loadSegment(currSegment,
309  height);
310 
311  int yStart = 0;
312  bool inRun = false;
313  for (int y = 0; y < height; y++) {
314 
315  ENGAUGE_ASSERT (y < height);
316  if (!inRun && currBool [y]) {
317  inRun = true;
318  yStart = y;
319  }
320 
321  if ((y + 1 >= height) || !currBool [y + 1]) {
322  if (inRun) {
323  finishRun(lastBool,
324  nextBool,
325  lastSegment,
326  currSegment,
327  x, yStart,
328  y,
329  height,
330  modelSegments,
331  madeLines);
332  }
333 
334  inRun = false;
335  }
336  }
337 
338  removeUnneededLines(lastSegment,
339  currSegment,
340  height,
341  foldedLines,
342  shortLines,
343  modelSegments,
344  segments);
345 }
346 
347 void SegmentFactory::removeEmptySegments (QList<Segment*> &segments) const
348 {
349  LOG4CPP_DEBUG_S ((*mainCat)) << "SegmentFactory::removeUnneededLines";
350 
351  for (int i = segments.count(); i > 0;) {
352 
353  --i;
354  Segment *segment = segments.at (i);
355 
356  // False positive warning from scan-build in next line can be ignored - it is a bug in that tool regarding loop unrolling
357  if (segment->lineCount () == 0) {
358 
359  // Remove this Segment
360  delete segment;
361 
362  segments.removeAt (i);
363  }
364  }
365 }
366 
367 void SegmentFactory::removeUnneededLines(SegmentVector &lastSegment,
368  SegmentVector &currSegment,
369  int height,
370  int *foldedLines,
371  int *shortLines,
372  const DocumentModelSegments &modelSegments,
373  QList<Segment*> &segments)
374 {
375  LOG4CPP_DEBUG_S ((*mainCat)) << "SegmentFactory::removeUnneededLines";
376 
377  Segment *segLast = nullptr;
378  for (int yLast = 0; yLast < height; yLast++) {
379 
380  ENGAUGE_ASSERT (yLast < height);
381  if (lastSegment [unsigned (yLast)] && (lastSegment [unsigned (yLast)] != segLast)) {
382 
383  segLast = lastSegment [unsigned (yLast)];
384 
385  // If the segment is found in the current column then it is still in work so postpone processing
386  bool found = false;
387  for (int yCur = 0; yCur < height; yCur++) {
388 
389  ENGAUGE_ASSERT (yCur < height);
390  if (segLast == currSegment [unsigned (yCur)]) {
391  found = true;
392  break;
393  }
394  }
395 
396  if (!found) {
397 
398  ENGAUGE_CHECK_PTR(segLast);
399  if (segLast->length() < (modelSegments.minLength() - 1) * modelSegments.pointSeparation()) {
400 
401  // Remove whole segment since it is too short. Do NOT set segLast to zero since that
402  // would cause this same segment to be deleted again in the next pixel if the segment
403  // covers more than one pixel
404  *shortLines += segLast->lineCount();
405  delete segLast;
406  lastSegment [unsigned (yLast)] = nullptr;
407 
408  } else {
409 
410  // Keep segment, but try to fold lines
411  segLast->removeUnneededLines(foldedLines);
412 
413  // Add to the output array since it is done and sufficiently long
414  segments.push_back (segLast);
415 
416  }
417  }
418  }
419  }
420 }
421 
422 void SegmentFactory::scrollBool(bool *left,
423  bool *right,
424  int height)
425 {
426  for (int y = 0; y < height; y++) {
427  left [y] = right [y];
428  }
429 }
430 
431 void SegmentFactory::scrollSegment(SegmentVector &left,
432  SegmentVector &right,
433  int height)
434 {
435  for (int y = 0; y < height; y++) {
436  left [static_cast<unsigned long> (y)] = right [static_cast<unsigned long> (y)];
437  }
438 }
439 
440 void SegmentFactory::clearSegments (QList<Segment*> &segments)
441 {
442  LOG4CPP_DEBUG_S ((*mainCat)) << "SegmentFactory::clearSegments";
443 
444  QList<Segment*>::iterator itr;
445  for (itr = segments.begin(); itr != segments.end(); itr++) {
446 
447  Segment *segment = *itr;
448 
449  delete segment;
450  }
451 
452  segments.clear ();
453 }
double pointSeparation() const
Get method for point separation.
QList< QPoint > fillPoints(const DocumentModelSegments &modelSegments, QList< Segment * > segments)
Return segment fill points for all segments, for previewing.
void removeUnneededLines(int *foldedLines)
Try to compress a segment that was just completed, by folding together line from point i to point i+1...
Definition: Segment.cpp:421
bool pixelFilteredIsOn(const QImage &image, int x, int y) const
Return true if specified filtered pixel is on.
SegmentFactory(QGraphicsScene &scene, bool isGnuplot)
Single constructor.
double minLength() const
Get method for min length.
Class for filtering image to remove unimportant information.
Definition: ColorFilter.h:20
void clearSegments(QList< Segment * > &segments)
Remove the segments created by makeSegments.
void appendColumn(int x, int y, const DocumentModelSegments &modelSegments)
Add some more pixels in a new column to an active segment.
Definition: Segment.cpp:42
void makeSegments(const QImage &imageFiltered, const DocumentModelSegments &modelSegments, QList< Segment * > &segments, bool useDlg=true)
Main entry point for creating all Segments for the filtered image.
Selectable piecewise-defined line that follows a filtered line in the image.
Definition: Segment.h:21
QList< QPoint > fillPoints(const DocumentModelSegments &modelSegments)
Create evenly spaced points along the segment.
Definition: Segment.cpp:205
int lineCount() const
Get method for number of lines.
Definition: Segment.cpp:380
Model for DlgSettingsSegments and CmdSettingsSegments.
double length() const
Get method for length in pixels.
Definition: Segment.cpp:375