1  // Copyright (c) Microsoft Corporation
  2  // The Microsoft Corporation licenses this file to you under the MIT license.
  3  // See the LICENSE file in the project root for more information.
  4  
  5  using System;
  6  using System.Collections.Generic;
  7  using System.Drawing;
  8  using System.Linq;
  9  using System.Text;
 10  using System.Windows;
 11  using System.Windows.Controls;
 12  using System.Windows.Media;
 13  
 14  using PowerOCR.Helpers;
 15  using Windows.Media.Ocr;
 16  
 17  using Rect = System.Windows.Rect;
 18  
 19  namespace PowerOCR.Models;
 20  
 21  public class ResultTable
 22  {
 23      public List<ResultColumn> Columns { get; set; } = new();
 24  
 25      public List<ResultRow> Rows { get; set; } = new();
 26  
 27      public Rect BoundingRect { get; set; }
 28  
 29      public List<int> ColumnLines { get; set; } = new();
 30  
 31      public List<int> RowLines { get; set; } = new();
 32  
 33      public Canvas? TableLines { get; set; }
 34  
 35      public ResultTable(ref List<WordBorder> wordBorders, DpiScale dpiScale)
 36      {
 37          int borderBuffer = 3;
 38          var leftsMin = wordBorders.Select(x => x.Left).Min();
 39          var topsMin = wordBorders.Select(x => x.Top).Min();
 40          var rightsMax = wordBorders.Select(x => x.Right).Max();
 41          var bottomsMax = wordBorders.Select(x => x.Bottom).Max();
 42  
 43          Rectangle bordersBorder = new()
 44          {
 45              X = (int)leftsMin - borderBuffer,
 46              Y = (int)topsMin - borderBuffer,
 47              Width = (int)(rightsMax + borderBuffer),
 48              Height = (int)(bottomsMax + borderBuffer),
 49          };
 50  
 51          bordersBorder.Width = (int)(bordersBorder.Width * dpiScale.DpiScaleX);
 52          bordersBorder.Height = (int)(bordersBorder.Height * dpiScale.DpiScaleY);
 53  
 54          AnalyzeAsTable(wordBorders, bordersBorder);
 55      }
 56  
 57      private void ParseRowAndColumnLines()
 58      {
 59          // Draw Bounding Rect
 60          int topBound = 0;
 61          int bottomBound = topBound;
 62          int leftBound = 0;
 63          int rightBound = leftBound;
 64  
 65          if (Rows.Count >= 1)
 66          {
 67              topBound = (int)Rows[0].Top;
 68              bottomBound = (int)Rows[Rows.Count - 1].Bottom;
 69          }
 70  
 71          if (Columns.Count >= 1)
 72          {
 73              leftBound = (int)Columns[0].Left;
 74              rightBound = (int)Columns[Columns.Count - 1].Right;
 75          }
 76  
 77          BoundingRect = new()
 78          {
 79              Width = (rightBound - leftBound) + 10,
 80              Height = (bottomBound - topBound) + 10,
 81              X = leftBound - 5,
 82              Y = topBound - 5,
 83          };
 84  
 85          // parse columns
 86          ColumnLines = new();
 87  
 88          for (int i = 0; i < Columns.Count - 1; i++)
 89          {
 90              int columnMid = (int)(Columns[i].Right + Columns[i + 1].Left) / 2;
 91              ColumnLines.Add(columnMid);
 92          }
 93  
 94          // parse rows
 95          RowLines = new();
 96  
 97          for (int i = 0; i < Rows.Count - 1; i++)
 98          {
 99              int rowMid = (int)(Rows[i].Bottom + Rows[i + 1].Top) / 2;
100              RowLines.Add(rowMid);
101          }
102      }
103  
104      public static List<WordBorder> ParseOcrResultIntoWordBorders(OcrResult ocrResult, DpiScale dpi)
105      {
106          List<WordBorder> wordBorders = new();
107          int lineNumber = 0;
108  
109          foreach (OcrLine ocrLine in ocrResult.Lines)
110          {
111              double top = ocrLine.Words.Select(x => x.BoundingRect.Top).Min();
112              double bottom = ocrLine.Words.Select(x => x.BoundingRect.Bottom).Max();
113              double left = ocrLine.Words.Select(x => x.BoundingRect.Left).Min();
114              double right = ocrLine.Words.Select(x => x.BoundingRect.Right).Max();
115  
116              Rect lineRect = new()
117              {
118                  X = left,
119                  Y = top,
120                  Width = Math.Abs(right - left),
121                  Height = Math.Abs(bottom - top),
122              };
123  
124              StringBuilder lineText = new();
125              ocrLine.GetTextFromOcrLine(true, lineText);
126  
127              WordBorder wordBorderBox = new()
128              {
129                  Width = lineRect.Width / dpi.DpiScaleX,
130                  Height = lineRect.Height / dpi.DpiScaleY,
131                  Top = lineRect.Y,
132                  Left = lineRect.X,
133                  Word = lineText.ToString().Trim(),
134                  LineNumber = lineNumber,
135              };
136              wordBorders.Add(wordBorderBox);
137  
138              lineNumber++;
139          }
140  
141          return wordBorders;
142      }
143  
144      public void AnalyzeAsTable(ICollection<WordBorder> wordBorders, Rectangle rectCanvasSize)
145      {
146          int hitGridSpacing = 3;
147  
148          int numberOfVerticalLines = rectCanvasSize.Width / hitGridSpacing;
149          int numberOfHorizontalLines = rectCanvasSize.Height / hitGridSpacing;
150  
151          Canvas tableIntersectionCanvas = new();
152  
153          List<int> rowAreas = CalculateRowAreas(rectCanvasSize, hitGridSpacing, numberOfHorizontalLines, tableIntersectionCanvas, wordBorders);
154          List<ResultRow> resultRows = CalculateResultRows(hitGridSpacing, rowAreas);
155  
156          List<int> columnAreas = CalculateColumnAreas(rectCanvasSize, hitGridSpacing, numberOfVerticalLines, tableIntersectionCanvas, wordBorders);
157          List<ResultColumn> resultColumns = CalculateResultColumns(hitGridSpacing, columnAreas);
158  
159          Rect tableBoundingRect = new()
160          {
161              X = columnAreas.FirstOrDefault(),
162              Y = rowAreas.FirstOrDefault(),
163              Width = columnAreas.LastOrDefault() - columnAreas.FirstOrDefault(),
164              Height = rowAreas.LastOrDefault() - rowAreas.FirstOrDefault(),
165          };
166  
167          CombineOutliers(wordBorders, resultRows, tableIntersectionCanvas, resultColumns, tableBoundingRect);
168  
169          Rows.Clear();
170          Rows.AddRange(resultRows);
171          Columns.Clear();
172          Columns.AddRange(resultColumns);
173  
174          ParseRowAndColumnLines();
175          DrawTable();
176      }
177  
178      private static List<ResultRow> CalculateResultRows(int hitGridSpacing, List<int> rowAreas)
179      {
180          List<ResultRow> resultRows = new();
181          int rowTop = 0;
182          int rowCount = 0;
183          for (int i = 0; i < rowAreas.Count; i++)
184          {
185              int thisLine = rowAreas[i];
186  
187              // check if should set this as top
188              if (i == 0)
189              {
190                  rowTop = thisLine;
191              }
192              else if (i - 1 > 0)
193              {
194                  int prevRow = rowAreas[i - 1];
195                  if (thisLine - prevRow != hitGridSpacing)
196                  {
197                      rowTop = thisLine;
198                  }
199              }
200  
201              // check to see if at bottom of row
202              if (i == rowAreas.Count - 1)
203              {
204                  resultRows.Add(new ResultRow { Top = rowTop, Bottom = thisLine, ID = rowCount });
205                  rowCount++;
206              }
207              else if (i + 1 < rowAreas.Count)
208              {
209                  int nextRow = rowAreas[i + 1];
210                  if (nextRow - thisLine != hitGridSpacing)
211                  {
212                      resultRows.Add(new ResultRow { Top = rowTop, Bottom = thisLine, ID = rowCount });
213                      rowCount++;
214                  }
215              }
216          }
217  
218          return resultRows;
219      }
220  
221      private static List<int> CalculateRowAreas(Rectangle rectCanvasSize, int hitGridSpacing, int numberOfHorizontalLines, Canvas tableIntersectionCanvas, ICollection<WordBorder> wordBorders)
222      {
223          List<int> rowAreas = new();
224  
225          for (int i = 0; i < numberOfHorizontalLines; i++)
226          {
227              Border horizontalLine = new()
228              {
229                  Height = 1,
230                  Width = rectCanvasSize.Width,
231                  Opacity = 0,
232                  Background = new SolidColorBrush(Colors.Gray),
233              };
234              Rect horizontalLineRect = new(0, i * hitGridSpacing, horizontalLine.Width, horizontalLine.Height);
235              _ = tableIntersectionCanvas.Children.Add(horizontalLine);
236              Canvas.SetTop(horizontalLine, i * 3);
237  
238              CheckIntersectionsWithWordBorders(hitGridSpacing, wordBorders, rowAreas, i, horizontalLineRect);
239          }
240  
241          return rowAreas;
242      }
243  
244      private static void CheckIntersectionsWithWordBorders(int hitGridSpacing, ICollection<WordBorder> wordBorders, List<int> rowAreas, int i, Rect horizontalLineRect)
245      {
246          foreach (WordBorder wb in wordBorders)
247          {
248              if (wb.IntersectsWith(horizontalLineRect))
249              {
250                  rowAreas.Add(i * hitGridSpacing);
251                  break;
252              }
253          }
254      }
255  
256      private static void CombineOutliers(ICollection<WordBorder> wordBorders, List<ResultRow> resultRows, Canvas tableIntersectionCanvas, List<ResultColumn> resultColumns, Rect tableBoundingRect)
257      {
258          // try 4 times to refine the rows and columns for outliers
259          // on the fifth time set the word boundary properties
260          for (int r = 0; r < 5; r++)
261          {
262              int outlierThreshold = 2;
263              List<int> outlierRowIDs = FindOutlierRowIds(wordBorders, resultRows, tableIntersectionCanvas, tableBoundingRect, r, outlierThreshold);
264  
265              if (outlierRowIDs.Count > 0)
266              {
267                  MergeTheseRowIDs(resultRows, outlierRowIDs);
268              }
269  
270              List<int> outlierColumnIDs = FindOutlierColumnIds(wordBorders, tableIntersectionCanvas, resultColumns, tableBoundingRect, outlierThreshold);
271  
272              if (outlierColumnIDs.Count > 0 && r != 4)
273              {
274                  MergeTheseColumnIDs(resultColumns, outlierColumnIDs);
275              }
276          }
277      }
278  
279      private static List<int> FindOutlierRowIds(
280          ICollection<WordBorder> wordBorders,
281          ICollection<ResultRow> resultRows,
282          Canvas tableIntersectionCanvas,
283          Rect tableBoundingRect,
284          int r,
285          int outlierThreshold)
286      {
287          List<int> outlierRowIDs = new();
288  
289          foreach (ResultRow row in resultRows)
290          {
291              int numberOfIntersectingWords = 0;
292              Border rowBorder = new()
293              {
294                  Height = row.Bottom - row.Top,
295                  Width = tableBoundingRect.Width,
296                  Background = new SolidColorBrush(Colors.Red),
297                  Tag = row.ID,
298              };
299              tableIntersectionCanvas.Children.Add(rowBorder);
300              Canvas.SetLeft(rowBorder, tableBoundingRect.X);
301              Canvas.SetTop(rowBorder, row.Top);
302  
303              Rect rowRect = new(tableBoundingRect.X, row.Top, rowBorder.Width, rowBorder.Height);
304  
305              foreach (WordBorder wb in wordBorders)
306              {
307                  if (wb.IntersectsWith(rowRect))
308                  {
309                      numberOfIntersectingWords++;
310                      wb.ResultRowID = row.ID;
311                  }
312              }
313  
314              if (numberOfIntersectingWords <= outlierThreshold && r != 4)
315              {
316                  outlierRowIDs.Add(row.ID);
317              }
318          }
319  
320          return outlierRowIDs;
321      }
322  
323      private static List<int> FindOutlierColumnIds(
324          ICollection<WordBorder> wordBorders,
325          Canvas tableIntersectionCanvas,
326          List<ResultColumn> resultColumns,
327          Rect tableBoundingRect,
328          int outlierThreshold)
329      {
330          List<int> outlierColumnIDs = new();
331  
332          foreach (ResultColumn column in resultColumns)
333          {
334              int numberOfIntersectingWords = 0;
335              Border columnBorder = new()
336              {
337                  Height = tableBoundingRect.Height,
338                  Width = column.Right - column.Left,
339                  Background = new SolidColorBrush(Colors.Blue),
340                  Opacity = 0.2,
341                  Tag = column.ID,
342              };
343              tableIntersectionCanvas.Children.Add(columnBorder);
344              Canvas.SetLeft(columnBorder, column.Left);
345              Canvas.SetTop(columnBorder, tableBoundingRect.Y);
346  
347              Rect columnRect = new(column.Left, tableBoundingRect.Y, columnBorder.Width, columnBorder.Height);
348              foreach (WordBorder wb in wordBorders)
349              {
350                  if (wb.IntersectsWith(columnRect))
351                  {
352                      numberOfIntersectingWords++;
353                      wb.ResultColumnID = column.ID;
354                  }
355              }
356  
357              if (numberOfIntersectingWords <= outlierThreshold)
358              {
359                  outlierColumnIDs.Add(column.ID);
360              }
361          }
362  
363          return outlierColumnIDs;
364      }
365  
366      private static List<ResultColumn> CalculateResultColumns(int hitGridSpacing, List<int> columnAreas)
367      {
368          List<ResultColumn> resultColumns = new();
369          int columnLeft = 0;
370          int columnCount = 0;
371          for (int i = 0; i < columnAreas.Count; i++)
372          {
373              int thisLine = columnAreas[i];
374  
375              // check if should set this as top
376              if (i == 0)
377              {
378                  columnLeft = thisLine;
379              }
380              else if (i - 1 > 0)
381              {
382                  int prevColumn = columnAreas[i - 1];
383                  if (thisLine - prevColumn != hitGridSpacing)
384                  {
385                      columnLeft = thisLine;
386                  }
387              }
388  
389              // check to see if at last Column
390              if (i == columnAreas.Count - 1)
391              {
392                  resultColumns.Add(new ResultColumn { Left = columnLeft, Right = thisLine, ID = columnCount });
393                  columnCount++;
394              }
395              else if (i + 1 < columnAreas.Count)
396              {
397                  int nextColumn = columnAreas[i + 1];
398                  if (nextColumn - thisLine != hitGridSpacing)
399                  {
400                      resultColumns.Add(new ResultColumn { Left = columnLeft, Right = thisLine, ID = columnCount });
401                      columnCount++;
402                  }
403              }
404          }
405  
406          return resultColumns;
407      }
408  
409      private static List<int> CalculateColumnAreas(Rectangle rectCanvasSize, int hitGridSpacing, int numberOfVerticalLines, Canvas tableIntersectionCanvas, ICollection<WordBorder> wordBorders)
410      {
411          List<int> columnAreas = new();
412          for (int i = 0; i < numberOfVerticalLines; i++)
413          {
414              Border vertLine = new()
415              {
416                  Height = rectCanvasSize.Height,
417                  Width = 1,
418                  Opacity = 0,
419                  Background = new SolidColorBrush(Colors.Gray),
420              };
421              _ = tableIntersectionCanvas.Children.Add(vertLine);
422              Canvas.SetLeft(vertLine, i * hitGridSpacing);
423  
424              Rect vertLineRect = new(i * hitGridSpacing, 0, vertLine.Width, vertLine.Height);
425  
426              foreach (WordBorder wb in wordBorders)
427              {
428                  if (wb.IntersectsWith(vertLineRect))
429                  {
430                      columnAreas.Add(i * hitGridSpacing);
431                      break;
432                  }
433              }
434          }
435  
436          return columnAreas;
437      }
438  
439      private static void MergeTheseColumnIDs(List<ResultColumn> resultColumns, List<int> outlierColumnIDs)
440      {
441          for (int i = 0; i < outlierColumnIDs.Count; i++)
442          {
443              for (int j = 0; j < resultColumns.Count; j++)
444              {
445                  ResultColumn column = resultColumns[j];
446                  if (column.ID == outlierColumnIDs[i])
447                  {
448                      if (j == 0)
449                      {
450                          // merge with next column if possible
451                          if (j + 1 < resultColumns.Count)
452                          {
453                              ResultColumn nextColumn = resultColumns[j + 1];
454                              nextColumn.Left = column.Left;
455                          }
456                      }
457                      else if (j == resultColumns.Count - 1)
458                      {
459                          // merge with previous column
460                          if (j - 1 >= 0)
461                          {
462                              ResultColumn prevColumn = resultColumns[j - 1];
463                              prevColumn.Right = column.Right;
464                          }
465                      }
466                      else
467                      {
468                          // merge with closet column
469                          ResultColumn prevColumn = resultColumns[j - 1];
470                          ResultColumn nextColumn = resultColumns[j + 1];
471                          int distanceToPrev = (int)(column.Left - prevColumn.Right);
472                          int distanceToNext = (int)(nextColumn.Left - column.Right);
473  
474                          if (distanceToNext < distanceToPrev)
475                          {
476                              // merge with next column
477                              nextColumn.Left = column.Left;
478                          }
479                          else
480                          {
481                              // merge with prev column
482                              prevColumn.Right = column.Right;
483                          }
484                      }
485  
486                      resultColumns.RemoveAt(j);
487                  }
488              }
489          }
490      }
491  
492      public static void GetTextFromTabledWordBorders(StringBuilder stringBuilder, List<WordBorder> wordBorders, bool isSpaceJoining)
493      {
494          List<WordBorder>? selectedBorders = wordBorders.Where(w => w.IsSelected).ToList();
495  
496          if (selectedBorders.Count == 0)
497          {
498              selectedBorders.AddRange(wordBorders);
499          }
500  
501          List<string> lineList = new();
502          int? lastLineNum = 0;
503          int lastColumnNum = 0;
504  
505          if (selectedBorders.FirstOrDefault() != null)
506          {
507              lastLineNum = selectedBorders.FirstOrDefault()!.LineNumber;
508          }
509  
510          selectedBorders = selectedBorders.OrderBy(x => x.ResultColumnID).ToList();
511          selectedBorders = selectedBorders.OrderBy(x => x.ResultRowID).ToList();
512  
513          int numberOfDistinctRows = selectedBorders.Select(x => x.ResultRowID).Distinct().Count();
514  
515          foreach (WordBorder border in selectedBorders)
516          {
517              if (lineList.Count == 0)
518              {
519                  lastLineNum = border.ResultRowID;
520              }
521  
522              if (border.ResultRowID != lastLineNum)
523              {
524                  if (isSpaceJoining)
525                  {
526                      stringBuilder.Append(string.Join(' ', lineList));
527                  }
528                  else
529                  {
530                      stringBuilder.Append(string.Join(string.Empty, lineList));
531                  }
532  
533                  stringBuilder.Replace(" \t ", "\t");
534                  stringBuilder.Replace("\t ", "\t");
535                  stringBuilder.Replace(" \t", "\t");
536                  stringBuilder.Append(Environment.NewLine);
537                  lineList.Clear();
538                  lastLineNum = border.ResultRowID;
539              }
540  
541              if (border.ResultColumnID != lastColumnNum && numberOfDistinctRows > 1)
542              {
543                  string borderWord = border.Word;
544                  int numberOfOffColumns = border.ResultColumnID - lastColumnNum;
545                  if (numberOfOffColumns < 0)
546                  {
547                      lastColumnNum = 0;
548                  }
549  
550                  numberOfOffColumns = border.ResultColumnID - lastColumnNum;
551  
552                  if (numberOfOffColumns > 0)
553                  {
554                      lineList.Add(new string('\t', numberOfOffColumns));
555                  }
556              }
557  
558              lastColumnNum = border.ResultColumnID;
559  
560              lineList.Add(border.Word);
561          }
562  
563          stringBuilder.Append(string.Join(string.Empty, lineList));
564      }
565  
566      private static void MergeTheseRowIDs(List<ResultRow> resultRows, List<int> outlierRowIDs)
567      {
568      }
569  
570      private void DrawTable()
571      {
572          // Draw the lines and bounds of the table
573          SolidColorBrush tableColor = new(System.Windows.Media.Color.FromArgb(255, 40, 118, 126));
574  
575          TableLines = new Canvas()
576          {
577              Tag = "TableLines",
578          };
579  
580          Border tableOutline = new()
581          {
582              Width = this.BoundingRect.Width,
583              Height = this.BoundingRect.Height,
584              BorderThickness = new Thickness(3),
585              BorderBrush = tableColor,
586          };
587          TableLines.Children.Add(tableOutline);
588          Canvas.SetTop(tableOutline, this.BoundingRect.Y);
589          Canvas.SetLeft(tableOutline, this.BoundingRect.X);
590  
591          foreach (int columnLine in this.ColumnLines)
592          {
593              Border vertLine = new()
594              {
595                  Width = 2,
596                  Height = this.BoundingRect.Height,
597                  Background = tableColor,
598              };
599              TableLines.Children.Add(vertLine);
600              Canvas.SetTop(vertLine, this.BoundingRect.Y);
601              Canvas.SetLeft(vertLine, columnLine);
602          }
603  
604          foreach (int rowLine in this.RowLines)
605          {
606              Border horizontalLine = new()
607              {
608                  Height = 2,
609                  Width = this.BoundingRect.Width,
610                  Background = tableColor,
611              };
612              TableLines.Children.Add(horizontalLine);
613              Canvas.SetTop(horizontalLine, rowLine);
614              Canvas.SetLeft(horizontalLine, this.BoundingRect.X);
615          }
616      }
617  
618      public static string GetWordsAsTable(List<WordBorder> wordBorders, DpiScale dpiScale, bool isSpaceJoining)
619      {
620          List<WordBorder> smallerBorders = new();
621          foreach (WordBorder originalWB in wordBorders)
622          {
623              WordBorder newWB = new()
624              {
625                  Word = originalWB.Word,
626                  Left = originalWB.Left,
627                  Top = originalWB.Top,
628                  Width = originalWB.Width > 10 ? originalWB.Width - 6 : originalWB.Width,
629                  Height = originalWB.Height > 10 ? originalWB.Height - 6 : originalWB.Height,
630                  ResultRowID = originalWB.ResultRowID,
631                  ResultColumnID = originalWB.ResultColumnID,
632              };
633              smallerBorders.Add(newWB);
634          }
635  
636          ResultTable resultTable = new(ref smallerBorders, dpiScale);
637          StringBuilder stringBuilder = new();
638          GetTextFromTabledWordBorders(
639              stringBuilder,
640              smallerBorders,
641              isSpaceJoining);
642          return stringBuilder.ToString();
643      }
644  }