AUTOMATED DATA EXTRACTION FROM SCATTER PLOT IMAGES

• US 20170351708A1
• Filed: 06/05/2017
• Published: 12/07/2017
• Est. Priority Date: 06/06/2016
• Status: Active Grant

• Current Assignee: think-cell Software GmbH
• Original Assignee: think-cell Software GmbH
• Inventors: Lahmann, Dominik, Schoedl, Arno, Ringenberg, Jordan
• Granted Patent: US 10,496,695 B2
• Time in Patent Office: Days
• CPC Class Codes: G06F 16/5838 using colour
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/20076 Probabilistic image processing
• CPC Class Codes: G06T 2207/30176 Document
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/12 Edge-based segmentation
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/155 involving morphological operators
• CPC Class Codes: G06T 7/74 involving reference images or patches
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 30/1988 Graph matching graphical image representation G06V30/18181
• CPC Class Codes: G06V 30/413 Classification of content, e.g. text, photographs or tables
• CPC Class Codes: G06V 30/422 Technical drawings; Geographical maps

Abstract

The invention relates to a computer-implemented method for automatically extracting data from a scatter plot. The method comprises receiving a digital image of a scatter plot; analyzing the received digital image for identifying a plurality of pixel sets, each pixel set being a group of adjacent pixels; analyzing the pixel sets in the received image or in a derivative of the received image for generating a plurality of templates; comparing the templates with pixels of a target image for identifying matching templates; identifying data points for the identified similar templates; assigning to each identified data point a data series; and returning the identified data points.

Claims

1. A computer-implemented method for automatically extracting data from a scatter plot, the method comprising:

receiving a digital image of a scatter plot;

analyzing the received digital image for identifying a plurality of pixel sets in the received scatter plot image or in a derivative of the received image, each identified pixel set being a group of adjacent pixels;

analyzing the identified pixel sets for generating a plurality of templates, each template being a pixel structure that depicts one single data point symbol, each template representing a respective data series;

comparing each of the templates with pixels of a target image, the target image being the received scatter plot image or the derivative of the received scatter plot image, for identifying positions of matching templates, a matching template being a template whose degree of similarity to pixels of the target image exceeds a similarity threshold;

at each position in the target image where a template match occurred, identifying a data point for the matching template and assigning to the identified data point one of the data series; and

returning the identified data points and the data series to which it is assigned.

2. The method of claim 1, the received image being a binary image.

3. The method of claim 1, wherein the received image is a single-channel grayscale scatter plot image or a multi-channel scatter plot image, the identification of the pixel sets comprising:

generating the derivative of the received scatter plot image by transforming the received scatter plot image into a derivative image, wherein the derivative image is an edge image that depicts contours of graphical objects in the scatter plot image;

performing the identification of the pixel sets by

mapping the identified contour pixels to respective pixels in a template-generation-image, the template-generation-image being the received scatter plot image or a derivative version of the received scatter plot image; and

using all pixels in the template-generation-image to which a contour of a graphical object is mapped or which lie within the mapped contour of said graphical object as one of the identified pixel sets, wherein the comparing of the templates with the pixel sets is performed in the pixels of the template-generation-image;

or

using all pixels in the edge image which are contour pixels of a graphical object or which lie within the contour of said graphical object as one of the identified pixel sets, to be used for generating the templates.

4. The method of claim 1, the identification of the pixel sets comprising:

identifying a plurality of pixel blobs in the received digital image or in the derivative image, each pixel blob being a group of adjacent pixels with similar image features; and

using the identified pixel blobs as the pixel sets.

5. The method of claim 1, wherein the received image is a multi-channel-image and wherein the method further comprising creating a binary image from the multi-channel image, the creation of the binary image comprising:

receiving a multi-channel image of the scatter plot;

decomposing the received multi-channel image into multiple single-channel images;

creating an edge image from each single-channel-image, each edge image selectively comprising pixels being indicative of the contours of graphical objects depicted in the received digital image, if any;

generating a composite grayscale image by determining, at each pixel position in the received digital image, the maximum pixel value of all created edge images, and by storing said determined maximum at the corresponding pixel position;

transforming the composite grayscale image into the binary image, the binary image being an edge image comprising contours of graphical objects.

6. The computer-implemented method of claim 1, the generation of the templates comprising:

analyzing the identified pixel sets for identifying and filtering out pixel sets whose position, coloring, morphology and/or size indicates that said pixel set cannot represent a data point, thereby filtering out plot labels, gridlines and/or axes; and

selectively using the non-filtered out pixel sets for generating template candidates, each template candidate comprising a graphical object that represents a single data point symbol or a combination of data point symbols or other objects other than a single data point symbol.

7. The computer-implemented method of claim 6, further comprising:

determining the occurrence frequency of the graphical object of each template candidate in the scatter plot image;

identifying and filtering out template candidates comprising a graphical object whose occurrence frequency in the scatter plot is below a threshold, thereby filtering out template candidates with a graphical object that represents an overlay of two or more data point symbols and template candidates with other rarely occurring objects;

selectively using the non-filtered out template candidates as the templates, each template comprising one single data point symbol.

8. The computer-implemented method of claim 1, the generation of the templates comprising:

analyzing the identified pixel sets for identifying and filtering out pixel sets whose position, coloring, morphology and/or size indicates that said pixel set cannot represent a data point, thereby filtering out plot labels, gridlines and/or axes; and

selectively clustering the non-filtered out pixel sets by image features into clusters of similar pixel sets, the image features being selected from a group comprising coloring features, morphological features and size,

identifying and filtering out clusters having a number of member pixel sets below a threshold, thereby filtering out clusters representing a graphical object that represents an overlay of two or more data point symbols or that represents another rarely occurring object;

selectively for each of said non-filtered out clusters, creating a graphical object that represents a data point symbol that is most similar to all pixel sets within said cluster and creating a template, the template comprising said graphical object as the one single data point symbol depicted in the template.

9. The computer-implemented method of claim 1, the comparing of the templates with the target image being implemented as a sliding window method, the sliding window method comprising moving the template across the target image, thereby comparing the pixels of the template with the pixels of each currently covered patch of the target image, each patch being an image region of the target image being currently covered by the template.

10. The method of claim 1, the comparing of the templates with the target image comprising:

mapping the identified pixel sets used for generating the templates to respective pixels in the target image; and

comparing the templates selectively with image patches in the target regions comprising at least one pixel to which the identified pixel sets were mapped.

11. The method of claim 1, the comparison of the templates with the pixels of the target image being performed by a comparison function, wherein the comparison is configured such that in case one of the template matches at least a minimum fraction of the pixels of one of the patches in the target image, the comparison function returns at least the degree of similarity of the template and the patch, and whereby after one of the templates was found to match with an image patch, at least one further one of the templates is compared with a copy of the image patch that lacks the pixels of the matching template for identifying also partially matching templates.

12. The method of claim 11, the minimum fraction being in a range of 10%-40% of the pixels of the patch.

13. The method of claim 11,

wherein the comparison identifies at least two templates which respectively have a degree of similarity to the pixels of the same image patch that exceeds the similarity threshold, wherein a data point is created and returned for each of said at least two templates, each of the at least two data points having assigned a different data series represented by the template for which the data point was created.

14. The method of claim 1, the comparing of the pixels of the template with the pixels of each currently covered image patch of the target image comprising:

calculating the correlation coefficient or normalized correlation coefficient between the image patch pixels and the template pixels;

or

calculating the cross-correlation or normalized cross-correlation between the image patch pixels and the template pixels;

or

calculating the sum of squared differences or normalized sum of squared differences between the image patch pixels and the template pixels.

15. The method of claim 1, the comparing of the templates with the image patches in the target image comprising:

generating downsized versions of the templates;

generating a downsized version of the target image;

performing a first comparison operation, the first comparison operation comprising comparing patches of the downsized target image with the downsized template versions for identifying image regions of interest in the downsized target image which are similar to one or more of the downsized templates;

performing a second comparison operation selectively for the identified digital image regions of interest, the second comparison operation comprising comparing patches of the original target image with the original version of the one or more templates being similar to the region of interest, wherein the degree of similarity is determined for said patch of the original target image and the one or more templates being similar to the region of interest identified in the first comparison operation.

16. The method of claim 15, the generation of the downsized versions of the templates comprising:

checking if the dimensions of the templates are within a predefined dimension range;

if the templates are larger than the predefined dimension range, creating downsized template versions which fit into the predefined dimension range;

the generation of the downsized version of the digital image comprising;

the generation of the downsized versions of the templates comprising downscaling the received digital image by the same scaling factor used for downscaling the templates.

17. The method of claim 1, the assigning of the data series to the identified data points comprising clustering data points in dependence on their size, morphology and/or coloring into clusters of data points having similar appearance.

18. The method of claim 1, the assigning of the data series to the identified data points comprising assigning to each identified data point the data series represented by the matching template for which the data point was created.

19. The method of claim 1, further comprising:

exporting the position and the associated data series of all identified data points to a receiving software application; and

/or

storing the position and the associated data series of all identified data points to a storage medium; and

/or

displaying the position and the associated data series of all identified data points in tabular form on a screen; and

/or

displaying the identified data points as a newly generated chart having a customized design on a screen.

20. The method of claim 1 being implemented as a plug-in, add-on or add-in of a spreadsheet application, an office application or of an application for generating electronic presentations.

21. A tangible non-volatile storage medium comprising computer-interpretable instructions stored thereon, the instructions, when executed by a processor, causing the processor to perform a method for extracting data from a scatter plot, the method comprising:

receiving a digital image of a scatter plot;

analyzing the received digital image for identifying a plurality of pixel sets in the received scatter plot image or in a derivative of the received image, each identified pixel set being a group of adjacent pixels;

analyzing the identified pixel sets for generating a plurality of templates, each template being a pixel structure that depicts one single data point symbol, each template representing a respective data series;

comparing each of the templates with pixels of a target image, the target image being the received scatter plot image or the derivative of the received scatter plot image, for identifying positions of matching templates, a matching template being a template whose degree of similarity to pixels of the target image exceeds a similarity threshold;

at each position in the target image where a template match occurred, identifying a data point for the matching template and assigning to the identified data point one of the data series; and

returning the identified data points and the data series to which it is assigned.

22. A computer system comprising one or more processors and memory comprising instructions stored thereon, the processors being configured for extracting data from a scatter plot, the extraction of the data comprising:

receiving a digital image of a scatter plot;

analyzing the received digital image for identifying a plurality of pixel sets in the received scatter plot image or in a derivative of the received image, each identified pixel set being a group of adjacent pixels;

analyzing the identified pixel sets for generating a plurality of templates, each template being a pixel structure that depicts one single data point symbol, each template representing a respective data series;

comparing each of the templates with pixels of a target image, the target image being the received scatter plot image or the derivative of the received scatter plot image, for identifying positions of matching templates, a matching template being a template whose degree of similarity to pixels of the target image exceeds a similarity threshold;

at each position in the target image where a template match occurred, identifying a data point for the matching template and assigning to the identified data point one of the data series; and

returning the identified data points and the data series to which it is assigned.