Systems and methods for identifying printers using Voronoi diagrams

Systems and methods for identifying a printer that generated a printed document. The methods comprise: generating an electronic image of the printed document; obtaining a dot pattern contained on the printed document via an analysis of the electronic image; overlaying the dot pattern on Voronoi diagrams; selecting a first Voronoi diagram from the Voronoi diagrams that has a single dot of the dot pattern in each of at least some cells thereof; and identifying a printer associated with the first Voronoi diagram that was selected from the Voronoi diagrams. The printer associated with the first Voronoi diagram comprises the printer that generated a printed document.

BACKGROUND

This disclosure relates to print systems and in particular to techniques for identifying printers that printed documents and automatedly organizing scanned documents in datastore(s) based on the identified printers.

Identification information may be printed on documents for use in subsequently identifying the printers that printed the documents. The identification information may be in a barcode format. Barcodes require a relatively large amount of ink to print. Barcode matching processes (on a large scale) are relatively resource intensive. Also, errors in barcode matching may occur when (i) a print head is malfunctioning or damaged, (ii) there are variations in barcode placement on printed documents, and/or (iii) printer calibration issues exist.

SUMMARY

Embodiments described in this document concern systems and methods for identifying a printer that generated a printed document. The method comprises performing the following operations by computing device(s), processing device(s) or other electronic device(s): generating an electronic image of the printed document; obtaining a dot pattern contained on the printed document via an analysis of the electronic image; overlaying the dot pattern on Voronoi diagrams; selecting a first Voronoi diagram from the Voronoi diagrams that has a single dot of the dot pattern in each of at least some cells thereof; and identifying a printer associated with the first Voronoi diagram that was selected from the Voronoi diagrams. The printer associated with the first Voronoi diagram comprises the printer that generated a printed document. None of the cells of the first Voronoi diagram has two or more dots of the dot pattern contained therein.

In some scenarios, the Voronoi diagram selection operation may involve: eliminating a second Voronoi diagram from further consideration for selection when the second Voronoi diagram has at least one cell with two or more dots of the dot pattern contained therein; eliminating a second Voronoi diagram from further consideration for selection when the second Voronoi diagram has less than a threshold number of cells with dots of the dot pattern contained therein; and/or eliminating a second Voronoi diagram from further consideration for selection when the second Voronoi diagram has at least one cell without any dot of the dot pattern contained therein or located within a distance from a cell boundary thereof.

In those or other scenarios, the method involves: assigning a different dot pattern to each printer of a plurality of printers; generating the Voronoi diagrams from the different dot patterns; obtaining another dot pattern contained on another printed document; overlaying the another dot pattern on the Voronoi diagrams; selecting a second Voronoi diagram from the Voronoi diagrams based on the another dot pattern; and identifying another printer which is associated with the second Voronoi diagram that was selected from the Voronoi diagrams (wherein this identified printer generated the another printed document).

In those or other scenarios, the method involves: performing operations by the printer to print the first dot pattern on the first document during a first period of time; performing operations by the printer to print another different dot pattern on second documents during a second period of time; identifying when the printer printed the first document based on results from analyzing the Voronoi diagram with the first dot pattern overlaid therein; and/or identifying when the printer printed a second document based on results from analyzing the Voronoi diagram with the another different dot pattern overlaid thereon.

In those or other scenarios, the methods involve autonomously or automatedly controlling operations of an electronic device based on the identifying. The electronic device can include, but is not limited to, a printer, a computing device, a server, a database system, and/or a robotic system. The operations can include, but are not limited to: causing electronic images of the printed documents to be stored in datastore(s) so as to be respectively associated with the identified printer(s) and/or organized in accordance with the identified time(s) when the printed document(s) where generated; causing a database system to re-organize electronic images/documents based on the identified printer(s) and/or identified time(s); causing a software application to generate a presentation (for example, a slide show) or other electronic document comprising contents of the scanned printed document(s) based on the identified printer(s) and/or identified time(s); causing a computing device to generate report(s) or perform analytics based on the identified printer(s) and/or identified time(s); causing the identified printer(s) to perform system checks; recalibrating the identified printer(s); causing the identified printer(s) to be repaired or to enable backup printing heads; and/or cause robotic system(s) to obtain and deliver replacement part(s) to the geographic location(s) of the identified printer(s).

The methods described above may be embodied in a system including a processor and memory containing programming instructions that, when executed, will cause the processor to implement the actions described above. Various embodiments also include a computer program product that contains such programming instructions, and a memory containing the computer program product.

DETAILED DESCRIPTION

This disclosure is not limited to the particular systems, methodologies or protocols described, as these may vary. The terminology used in this description is for describing the particular versions or embodiments only, and is not intended to limit the scope.

As used in this document, any word in singular form, along with the singular forms “a,” “an” and “the,” include the plural reference unless the context clearly dictates otherwise. Unless defined otherwise, all technical and scientific terms used herein have the same meanings as commonly understood by one of ordinary skill in the art. All publications mentioned in this document are incorporated by reference. Nothing in this document is to be construed as an admission that the embodiments described in this document are not entitled to antedate such disclosure by virtue of prior invention. As used herein, the term “comprising” means “including, but not limited to.”

The terms “memory,” “computer-readable medium” and “storage medium” each refer to a non-transitory device on which computer-readable data, programming instructions or both are stored. Unless the context specifically states that a single device is required or that multiple devices are required, the terms “memory,” “computer-readable medium” and “storage medium” include both the singular and plural embodiments, as well as portions of such devices such as memory sectors.

The present solution concerns systems and methods for identifying printers that generated printed documents based on dot patterns and Voronoi diagrams. The present solution is less resource intensive as compared to that of the conventional systems. The present solution can also provide an improved database management system by automating operations for document storage and organization within datastores based on at least the identified printers.

The methods generally comprise: generating an electronic image of the printed document; obtaining a dot pattern contained on the printed document via an analysis of the electronic image; overlaying the dot pattern on Voronoi diagrams; selecting a first Voronoi diagram from the Voronoi diagrams that has a single dot of the dot pattern in each of at least some cells thereof; and identifying a printer associated with the first Voronoi diagram that was selected from the Voronoi diagrams. The printer associated with the first Voronoi diagram comprises the printer that generated a printed document. Some advantages to using the dot patterns instead of traditional barcodes is that the dot patterns use less ink to print and are relatively difficult to see with an unaided eye.

FIG.1provides an illustration of a system100implementing the present solution. System100is generally configured to identify printers102that printed documents120. The printers102can include, but are not limited to, ink jet printers, laser printers, and/or toner printers (for example, a xerographic toner printer). A unique dot pattern108is generated for each printer. The dot patterns108can include, but are not limited to, randomly generated dot patterns and/or halftone screens. An illustrative dot pattern300is shown inFIG.3which comprises dots arranged in a pattern within a given area having a size M×N. M and N each comprise any number greater than zero. Any known or to be known technique for generating random dot patterns can be used here.

A halftone screen comprises an image with dots of the same or different sizes to generate a gradient-like effect to simulate a continuous tone image. Any known or to be known technique for generating halftone screens can be used here. An illustrative method for generating a halftone screen for a printer is described in U.S. Pat. No. 10,079,960. Conventional printers comprise the same halftone screens. In contrast, the printers102of the present solution are assigned different halftone screens which can be used to identify the printers from amongst each other. The dot patterns108can be generated by optional dot pattern generators110,138of the printers102and/or server(s)126. The dot patterns108are stored in non-transitory computer-readable storage mediums116of the printers (for example, a random access memory (RAM), read only memory (ROM) and/or flash memory).

A Voronoi diagram is also generated for each dot pattern by an optional Voronoi diagram generator112,140of the printer and/or server. Any known or to be known technique for generating Voronoi diagrams can be implemented by the Voronoi diagram generators112,140. An illustrative Voronoi diagram400is shown inFIG.4. The Voronoi diagram400comprises a plurality of cells402. A Voronoi diagram cell structure130defines the sizes, shapes and relative locations of the cells402with a given area having size M×N.

The Voronoi diagram cell structures130are stored in datastore(s)128which is(are) accessible to the server(s)126and/or scanner(s)132. Each Voronoi diagram cell structure is stored so as to be associated with a printer identifier, a geographic location, day information and/or time information. The printer identifier can include a sequence of number, letters and/or symbols. The geographic location can include, but is not limited to, the location where the printer resides. The day information can include, but is not limited to, the day when calendar day when the Voronoi diagram was generated. The time information can include, but is not limited to, a time of day when the Voronoi diagram was generated, and/or a duration of time that the Voronoi diagram is valid for the printer. With regard to the last type of listed time information, a different dot pattern and/or Voronoi diagram can be generated for a printer each hour, day, week, month, year or other time period (e.g., X hours, where X is any number greater than zero). Such a configuration allows the system to not only identify the printer that printed a document, but also the day/time that the document was printed thereby.

The scanner(s)132may be separate from the printer(s)102as shown inFIG.1. Alternatively, the scanner(s)132may be provided with the printer(s)102. The combination of a scanner and a printer is referred to herein as a multi-functional device.

During operation, a processing device106of the printer102performs operations to cause each printed document120to be marked with the dot pattern108. The document120can be printed via a print engine104controlled by the processing device106. The print engine104may be a laser engine or an ink jet engine. The marking is achieved by printing the dot pattern108at a particular location on the printed document120. The particular location can include any location on the printed document120. For example, the dot pattern108is printed at the top left corner, the top right corner, the bottom left corner or the bottom right corner of the printed document120. The present solution is not limited in this regard. The printed document120can be a hard copy of an electronic document received from a user device118and/or stored in the storage medium116of the printer. The electronic document can include, but is not limited to, a digital image.

Status of the print job may be communicated from the printer102to the server126and/or user device118via communication peripheral114. The communication peripheral114may be wired, such as via a universal serial bus (USB) interface, a parallel or serial port, or an Ethernet port. The communication peripheral114may also be wireless, configured to communicate with proximate devices via protocols such as via Wi-Fi, Bluetooth, near-field communication (NFC), infrared or other wireless communication protocols known or later developed.

At some later time, a scanner132is used to scan the printed document120to obtain an electronic image134. The scanner132analyzes the electronic image134to detect the dot pattern108and extract the dot pattern therefrom. The extracted dot pattern152may be stored in a storage medium of the scanner132and/or communicated to the server(s)126via a network124(for example, the Intranet or Internet) for further processing.

The extracted dot pattern152is overlaid on the Voronoi diagram cell structures130for identifying the printer that printed the document120which was scanned by the scanner132. A printer is identified when the following criteria is met: (i) each cell in a Voronoi diagram has only one dot of the dot pattern152entirely or at least partially located therein; and/or (ii) a certain number of cells of the Voronoi diagram have a dot of the dot pattern (entirely or at least partially) located therein or proximate thereto. The term proximate as used here means that the dot is within a pre-defined distance from boundary of a cell in the Voronoi diagram. The pre-defined distance can be selected to account for variations in locations of a dot on printed documents and/or known printing tolerances of the printer.

When a printer is identified, the electronic image134may be automatedly or autonomously stored in a datastore128so as to be associated with the printer's identifier. For example, the electronic image is stored in a file along with other scanned documents having the same dot pattern contained thereon. The electronic image may also be stored with geographic location information specifying the location where the printer resides, date information specifying the day that the printer printed the document120which is associated with the electronic image134, and/or time information specifying the time that the printer printed the document120which is associated with the electronic image134. The electronic images may be organized in the file or datastore according to the printer identifiers, geographic locations, dates and/or times associated therewith.

FIG.2provides a functional block diagram200for operations of the system100. In block202, a dot pattern (for example, dot pattern108ofFIGS.1and/or300ofFIG.3) is generated that is to be used for identifying a printer (for example, printer102ofFIG.1) that prints an electronic document (for example, electronic document150ofFIG.1). A Voronoi diagram (for example, Voronoi diagram400ofFIG.4) is generated in block204from the dot pattern. The Voronoi diagram is stored in a datastore (for example, datastore128ofFIG.1), as shown by block206. In block208, the Voronoi diagram is used to identify the printer generated a printed document (for example, printed document120ofFIG.1).

The operations of block208can involve: overlaying the dot pattern on one or more Voronoi diagrams; determining whether all or a certain percentage of the cells of each Voronoi diagram have a single dot of the dot pattern contained therein (entirely or at least partially) or located in proximity thereto; selecting a Voronoi diagram from the Voronoi diagrams based on the determining; and obtaining a printer identifier associated with the selected Voronoi diagram. The selected Voronoi diagram can include the Voronoi diagram that has all or a certain percentage of the cells which each have a single dot of the dot pattern contained therein (entirely or at least partially) or located in proximity thereto. Block208can also involve obtaining day and/or time information associated with the selected Voronoi diagram. The day and/or time information indicates when the printed document was generated by the printer.

An illustration is provided inFIG.5showing the dot pattern300ofFIG.4overlaid on the Voronoi diagram400ofFIG.4. Each cell402of the Voronoi diagram has a single point302of the dot pattern300contained therein. Accordingly, the system considers a match to exist between the dot pattern300and the Voronoi diagram400. In effect, the system identifies the printer associated the Voronoi diagram400and concludes that the identified printer printed the electronic document from which the dot pattern300was obtained.

An illustration is provided inFIG.6showing another dot pattern600overlaid on the Voronoi diagram400ofFIG.4. Some of the cells402of the Voronoi diagram400have two or more dots602of the dot pattern600contained therein. Accordingly, the system concludes that a match does not exist between the dot pattern600and the Voronoi diagram400. In effect, the system does not identify the printer associated the Voronoi diagram400as being the printer that printed the electronic document from which the dot pattern600was obtained.

FIG.7provides a flow diagram of an illustrative method700for identifying a printer (for example, printer102ofFIG.1) that generated a printed document (for example, printed document120ofFIG.1). All or a portion of method700can be performed by the printer, server(s) (for example, server(s)126ofFIG.1), scanner(s) (for example, scanner(s)132ofFIG.1), processing device(s) (for example, processing device106ofFIG.1), and/or computing device(s) (for example, computing device800ofFIG.8). Method700can also include more or less operations than those shown inFIG.7. For example, the operations of block716-724,728can be removed from method700in some scenarios. Alternatively or additionally, the operations may be performed in a different order than that shown inFIG.7.

As shown inFIG.7A, method700begins with702and continues with704where a different dot pattern is assigned to each printer of a plurality of printers. The printers may be part of a fleet of printers owned and/or operated by a business entity. Voronoi diagrams are generated in706from the different dot patterns. The Voronoi diagrams may be stored in a datastore (for example, datastore128ofFIG.1).

Subsequently in706, a first dot pattern (for example, dot pattern108ofFIGS.1and/or300ofFIG.3) is obtained from a first printed document (for example, printed document120ofFIG.1). This can be achieved using a scanner (for example, scanner132ofFIG.1) that scans the first printed document to generate an electronic image (for example, electronic image134ofFIG.1) thereof. A dot pattern detector (for example, dot pattern detector136ofFIG.1) then analyzes the electronic image to detect the dot pattern therein. The detected dot pattern is then extracted or otherwise obtained from the electronic image.

In708, the first dot pattern is overlaid on the Voronoi diagrams. The Voronoi diagrams may be analyzed in parallel or sequentially.FIG.7illustrates the sequential process for Voronoi diagram analysis. Thus, a Voronoi diagram (with the overlaid dot pattern) is analyzed in710. This analysis is performed to detect or determine whether at least one cell of the Voronoi diagram has two or more dots therein. If so [712:YES], then method700continues with714where the system returns to710so that a next Voronoi diagram can be analyzed. The present Voronoi diagram under analysis may be eliminated or otherwise removed from further consideration by the system for identifying the printer that generated the first printed document.

If not [712:NO], then the system further analyzes the Voronoi diagram in716to detect or determine whether a threshold number of cells thereof have a dot therein (or overlaid thereon). If so [716:YES], then the Voronoi diagram is selected by the system in718. Method700then continues to block730ofFIG.7Bwhich will be discussed below.

If not [716:NO], then method700continues with operations of blocks720-724. These operations involve: computing a first total number of cells of the Voronoi diagram which have a dot therein; compute a second total number of cells of the Voronoi diagram which do not have a dot therein but do have a dot located a distance from the cell boundary; and determining whether the sum of the first and second total numbers of cells is greater than a threshold total number of cells. If not [724:NO], then method700continues with728where the system returns to710so that a next Voronoi diagram can be analyzed. The present Voronoi diagram under analysis may be eliminated or otherwise removed from further consideration by the system for identifying the printer that generated the first printed document. If so [724:YES], then the Voronoi diagram is selected in726. Method700then continues to730ofFIG.7B.

As shown inFIG.7B, the operations of block730involve identifying a printer associated with the selected Voronoi diagram. This identification can be made by accessing a datastore (for example, datastore128ofFIG.1) to obtain a printer identifier (for example, printer identifier158ofFIG.1) that is stored therein so as to be associated with the selected Voronoi diagram. The identified printer is considered by the system as comprising the printer that generated the first printed document, as shown by732.

The system may obtain a second dot pattern from a second printed document in734. The second dot pattern is overlaid on the Voronoi diagrams in736. The Voronoi diagrams (with the overlaid second dot pattern) are analyzed in738. One of the Voronoi diagrams is selected as a result of this analysis. Another printer is identified in740which is associated with the Voronoi diagram selected in738. This identified printer is considered by the system as comprising the printer that generated the second printed document, as shown by742.

In744, a third printed document is generated by the printer that produced the first printed document. A third dot pattern is provided on the third printed document, rather than the first dot pattern. In some scenarios, a printer may employ a different dot pattern each hour, day, week, year or other specified time period.

The third dot pattern is obtained from the third printed document in746. In748, the third dot pattern is overlaid on the Voronoi diagrams. The operations of blocks710-726are repeated to select the Voronoi diagram. The printer is identified in752. The system may determine a time when the third printed document was generated by the printer based on time information (for example, time information160ofFIG.1) stored in the datastore so as to be associated with the Voronoi diagram selected in750. The time information can include, but is not limited to, a day of a week, a hour of a day, and/or a minute of an hour.

In optional756, the system may perform operations to automatedly or autonomously control operations of a device and/or datastore system based on the identified printer(s) and the identified time. The device can include, but is not limited to, printer(s) (for example, printer(s)102ofFIG.1), a computing device (for example, computing device800ofFIG.8), a server (for example, server126ofFIG.1), a database system (for example, components126,128ofFIG.1), and/or a robotic system (for example, robotic system170ofFIG.1). The operations can include, but are not limited to: causing electronic images of the printed documents to be stored in datastore(s) (for example, datastore(s)128ofFIG.1) so as to be respectively associated with the identified printer(s) and/or organized in accordance with the identified time(s) when the printed document(s) where generated; causing a database system to re-organize scanned documents based on the identified printer(s) and/or identified time(s); causing a software application (for example, software application172ofFIG.1) to generate a presentation (for example, a slide show) or other electronic document comprising contents of the scanned printed document(s) based on the identified printer(s) and/or identified time(s); causing a computing device to generate report(s) or perform analytics based on the identified printer(s) and/or identified time(s); causing the identified printer(s) to perform system checks; recalibrating the identified printer(s); causing the identified printer(s) to be repaired or to enable backup printing heads; and/or cause robotic system(s) to obtain and deliver replacement part(s) to the geographic location(s) of the identified printer(s). The robotic system(s) can include, but is(are) not limited to, an unmanned vehicle (ground or aerial).

Referring now toFIG.8, there is provided an illustration of an illustrative architecture for a computing device800. The printer(s)102ofFIG.1, processing device(s)106ofFIG.1, user device118ofFIG.1, server(s)126ofFIG.1and/or scanner(s)132ofFIG.1is/are the same as or similar to computing device800. As such, the discussion of computing device800is sufficient for understanding the devices102,106,118,126,132ofFIG.1.

Computing device800may include more or less components than those shown inFIG.8. However, the components shown are sufficient to disclose an illustrative solution implementing the present solution. The hardware architecture ofFIG.8represents one implementation of a representative computing device configured to identify printers that generated printed documents, as described herein. As such, the computing device800ofFIG.8implements at least a portion of the method(s) described herein.

Some or all components of the computing device800can be implemented as hardware, software and/or a combination of hardware and software. The hardware includes, but is not limited to, one or more electronic circuits. The electronic circuits can include, but are not limited to, passive components (e.g., resistors and capacitors) and/or active components (e.g., amplifiers and/or microprocessors). The passive and/or active components can be adapted to, arranged to and/or programmed to perform one or more of the methodologies, procedures, or functions described herein.

As shown inFIG.8, the computing device800comprises a user interface802, a central processing unit (CPU)806, a system bus810, a memory812connected to and accessible by other portions of computing device800through system bus810, a system interface822, an optional wireless communication device864, and hardware entities814connected to system bus810. The user interface can include input devices and output devices, which facilitate user-software interactions for controlling operations of the computing device800. The input devices include, but are not limited to, a physical and/or touch keyboard. The input devices can be connected to the computing device800via a wired or wireless connection (e.g., a Bluetooth® connection). The output devices include, but are not limited to, a speaker, a display, and/or light emitting diodes.

System interface822is configured to facilitate wired and/or wireless communications to and from external devices (e.g., network nodes such as access points, etc.). In some scenarios, the wireless communication device864is provided in addition to the system interface822for facilitating wireless communications to and from external devices. If both components822and864are wireless communication enabled, then they may employ different wireless communication technology.

At least some of the hardware entities814perform actions involving access to and use of memory412, which can be a RAM, a disk drive, flash memory, a compact disc ROM (CD-ROM) and/or another hardware device that is capable of storing instructions and data. Hardware entities814can include a disk drive unit816comprising a computer-readable storage medium818on which is stored one or more sets of instructions820(e.g., software code) configured to implement one or more of the methodologies, procedures, or functions described herein. The instructions820can also reside, completely or at least partially, within the memory812and/or within the CPU806during execution thereof by the computing device800. The memory812and the CPU806also can constitute machine-readable media. The term “machine-readable media”, as used here, refers to a single medium or multiple media (e.g., a centralized or distributed database, and/or associated caches and servers) that store the one or more sets of instructions820. The term “machine-readable media”, as used here, also refers to any medium that is capable of storing, encoding or carrying a set of instructions820for execution by the computing device800and that cause the computing device800to perform any one or more of the methodologies of the present disclosure.

The features and functions disclosed above, as well as alternatives, may be combined into many other different systems or applications. Various presently unforeseen or unanticipated alternatives, modifications, variations or improvements may be made by those skilled in the art, each of which is also intended to be encompassed by the disclosed embodiments.