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 
SegmentFactory(QGraphicsScene & scene,bool isGnuplot)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 
adjacentRuns(bool * columnBool,int yStart,int yStop,int height)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 
adjacentSegment(SegmentVector & lastSegment,int yStart,int yStop,int height)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 
adjacentSegments(SegmentVector & lastSegment,int yStart,int yStop,int height)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 
fillPoints(const DocumentModelSegments & modelSegments,QList<Segment * > segments)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 
finishRun(bool * lastBool,bool * nextBool,SegmentVector & lastSegment,SegmentVector & currSegment,int x,int yStart,int yStop,int height,const DocumentModelSegments & modelSegments,int * madeLines)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 
loadBool(const ColorFilter & filter,bool * columnBool,const QImage & image,int x)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 
loadSegment(SegmentVector & columnSegment,int height)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 
makeSegments(const QImage & imageFiltered,const DocumentModelSegments & modelSegments,QList<Segment * > & segments,bool useDlg)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 
matchRunsToSegments(int x,int height,bool * lastBool,SegmentVector & lastSegment,bool * currBool,SegmentVector & currSegment,bool * nextBool,const DocumentModelSegments & modelSegments,int * madeLines,int * foldedLines,int * shortLines,QList<Segment * > & segments)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 
removeEmptySegments(QList<Segment * > & segments) const347 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 
removeUnneededLines(SegmentVector & lastSegment,SegmentVector & currSegment,int height,int * foldedLines,int * shortLines,const DocumentModelSegments & modelSegments,QList<Segment * > & segments)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 
scrollBool(bool * left,bool * right,int height)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 
scrollSegment(SegmentVector & left,SegmentVector & right,int height)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 
clearSegments(QList<Segment * > & segments)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 }
454