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