Easy To Use Patents Search & Patent Lawyer Directory

At Patents you can conduct a Patent Search, File a Patent Application, find a Patent Attorney, or search available technology through our Patent Exchange. Patents are available using simple keyword or date criteria. If you are looking to hire a patent attorney, you've come to the right place. Protect your idea and hire a patent lawyer.


Search All Patents:



  This Patent May Be For Sale or Lease. Contact Us

  Is This Your Patent? Claim This Patent Now.



Register or Login To Download This Patent As A PDF




United States Patent 10,055,853
Fisher ,   et al. August 21, 2018

Subject identification and tracking using image recognition

Abstract

Systems and techniques are provided for tracking multi joint subjects in real space having a plurality of cameras. The field of view of each camera overlaps with at least one other camera. The plurality of cameras produce respective sequences of images of corresponding fields of view in the real space. A processing system is coupled to the plurality of cameras. In one embodiment, the processing system comprises image recognition engines receiving sequence of images from the plurality of cameras and generating corresponding arrays of joint data structures. A tracking engine is configured to receive the arrays of joint data structures and generate candidate joints having coordinates in the real space. The processing system includes the logic to identify sets of candidate joints having coordinates in the real space as multi-joint subjects in the real space.


Inventors: Fisher; Jordan (Palo Alto, CA), Valdman; David (Palo Alto, CA), Novak; John (Palo Alto, CA), Ogle; Brandon (Palo Alto, CA)
Applicant:
Name City State Country Type

STANDARD COGNITION, CORP

San Francisco

CA

US
Assignee: STANDARD COGNITION, CORP (San Francisco, CA)
Family ID: 63144698
Appl. No.: 15/847,796
Filed: December 19, 2017


Related U.S. Patent Documents

Application NumberFiling DatePatent NumberIssue Date
62542077Aug 7, 2017

Current U.S. Class: 1/1
Current CPC Class: H04N 13/243 (20180501); H04N 13/211 (20180501); G06T 7/292 (20170101); G06K 9/00718 (20130101); G06T 7/248 (20170101); G06K 9/20 (20130101); G06K 2009/2045 (20130101); G06T 2207/10021 (20130101); G06T 2207/10024 (20130101); G06T 2207/30196 (20130101)
Current International Class: G06T 7/292 (20170101); G06K 9/20 (20060101); H04N 13/00 (20180101); G06T 7/246 (20170101); G06K 9/00 (20060101)

References Cited [Referenced By]

U.S. Patent Documents
6154559 November 2000 Beardsley
7050624 May 2006 Dialameh et al.
9449233 September 2016 Taylor
9536177 January 2017 Chalasani et al.
9582891 February 2017 Geiger et al.
9881221 January 2018 Bala
9911290 March 2018 Zalewski
2003/0107649 June 2003 Flickner et al.
2008/0159634 July 2008 Sharma
2012/0159290 June 2012 Pulsipher
2013/0156260 June 2013 Craig
2014/0282162 September 2014 Fein et al.
2015/0019391 January 2015 Kumar et al.
2015/0039458 February 2015 Reid
2017/0116473 April 2017 Sashida et al.
2017/0278255 September 2017 Shingu et al.
2017/0309136 October 2017 Schoner
2017/0323376 November 2017 Glaser et al.
Foreign Patent Documents
104778690 Jun 2017 CN
1574986 Jul 2008 EP
2013196199 Sep 2013 JP
201489626 May 2014 JP
0021021 Apr 2000 WO
02059836 May 2003 WO
2017151241 Sep 2017 WO

Other References

Zhang "A Flexible New Technique for Camera Calibration," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, No. 11, Nov. 2000, 22 pages. cited by applicant .
Longuet-Higgens, "A computer algorithm for reconstructing a scene from two projections," Nature 293, Sep. 10, 1981, pp. 133-135. cited by applicant .
Harville, "Stereo person tracking with adaptive plan-view templates of height and occupancy statistics," Image and Vision Computing, vol. 22, Issue 2, Feb. 1, 2004, pp. 127-142. cited by applicant .
Huang, et al. "Driver's view and vehicle surround estimation using omnidirectional video stream," IEEE IV2003 Intelligent Vehicles Symposium. Proceedings (Cat. No. 03TH8683), Jun. 9-11, 2003, pp. 444-449. cited by applicant .
Rossi et al., "Tracking and Counting Moving People," IEEE Int'l Conf. on Image Processing, ICIP-94, Nov. 13-16, 1994, 5 pages. cited by applicant .
Vincze, "Robust tracking of ellipses at frame rate," Pattern Recognition, vol. 34, Issue 2, Feb. 2001, pp. 487-498. cited by applicant .
Black et al., "Multi View Image Surveillance and Tracking," IEEE Proceedings of the Workshop on Motion and Video Computing, 2002, pp. 1-6. cited by applicant .
Zhang "A Flexible New Technique for Camera Calibration," IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 22, No. 11, Nov. 2000, 5 pages. cited by applicant.

Primary Examiner: Holder; Anner N
Attorney, Agent or Firm: Haynes Beffel & Wolfeld LLP

Parent Case Text



PRIORITY APPLICATION

This application claims the benefit of U.S. Provisional Patent Application No. 62/542,077 filed 7 Aug. 2017; which application is incorporated herein by reference.
Claims



What is claimed is:

1. A system for tracking multi joint subjects in an area of real space, comprising: a plurality of cameras, cameras in the plurality of cameras producing respective sequences of images of corresponding fields of view in the real space, the field of view of each camera overlapping with the field of view of at least one other camera in the plurality of cameras; a processing system coupled to the plurality of cameras, the processing system including: image recognition engines, receiving the sequences of images from the plurality of cameras, which process images to generate corresponding arrays of joint data structures, the arrays of joint data structures corresponding to particular images classifying elements of the particular images by joint type, time of the particular image, and coordinates of the element in the particular image; a tracking engine configured to receive the arrays of joint data structures corresponding to images in sequences of images from cameras having overlapping fields of view, and translate the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in real space; and logic to identify sets of candidate joints having coordinates in real space as multi-joint subjects in the real space.

2. The system of claim 1, wherein the image recognition engines comprise convolutional neural networks.

3. The system of claim 1, wherein image recognition engines process images to generate confidence arrays for elements of the image, where a confidence array for a particular element of an image includes confidence values for a plurality of joint types for the particular element, and to select a joint type for the joint data structure of the particular element based on the confidence array.

4. The system of claim 1, wherein the logic to identify sets of candidate joints comprises heuristic functions based on physical relationships among joints of subjects in real space to identify sets of candidate joints as multi-joint subjects.

5. The system of claim 4, including logic to store the sets of joints identified as multi-joint subjects, and wherein the logic to identify sets of candidate joints includes logic to determine whether a candidate joint identified in images taken at a particular time corresponds with a member of one of the sets of candidate joints identified as multi-joint subjects in preceding images.

6. The system of claim 1, wherein cameras in the plurality of cameras are configured to generate synchronized sequences of images.

7. The system of claim 1, wherein the plurality of cameras comprise cameras disposed over and having fields of view encompassing respective parts of the area in real space, and the coordinates in real space of members of a set of candidate joints identified as a multi-joint subject identify locations in the area of the multi-joint subject.

8. The system of claim 1, including logic to track locations of a plurality of multi-joint subjects in the area of real space.

9. The system of claim 8, including logic to determine when multi joint subjects in the plurality of multi-joint subjects leave the area of real space.

10. The system of claim 1, including logic to track locations in the area of real space of multiple candidate joints that are members of a set of candidate joints identified as a particular multi joint subject.

11. A method for tracking multi-joint subjects in an area of real space, comprising: using a plurality of cameras to produce respective sequences of images of corresponding fields of view in the real space, the field of view of each camera overlapping with the field of view of at least one other camera in the plurality of cameras; processing images in the sequences of images to generate corresponding arrays of joint data structures, the arrays of joint data structures corresponding to particular images classifying elements of the particular images by joint type, time of the particular image, and coordinates of the element in the particular image; translating the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in the real space; and identifying sets of candidate joints having coordinates in real space as multi-joint subjects in the real space.

12. The method of claim 11, wherein said processing images includes using convolutional neural networks.

13. The method of claim 11, wherein said processing images includes generating confidence arrays for elements of the image, where a confidence array for a particular element of an image includes confidence values for a plurality of joint types for the particular element, and selecting a joint type for the joint data structure of the particular element based on the confidence array.

14. The method of claim 11, wherein identifying sets of candidate joints comprises applying heuristic functions based on physical relationships among joints of subjects in real space to identify sets of candidate joints as multi-joint subjects.

15. The method of claim 14, including storing the sets of joints identified as multi-joint subjects, and wherein the identifying sets of candidate joints includes determining whether a candidate joint identified in images taken at a particular time corresponds with a member of one of the sets of candidate joints identified as a multi-joint subject in a preceding image.

16. The method of claim 11, wherein the sequences of images are synchronized.

17. The method of claim 11, wherein the plurality of cameras comprise cameras disposed over and having fields of view encompassing respective parts of the area in real space, and the coordinates in real space of members of a set of candidate joints identified as a multi-joint subject identify locations in the area of the multi-joint subject.

18. The method of claim 11, including tracking locations of a plurality of multi-joint subjects in the area of real space.

19. The method of claim 18, including determining when a multi-joint subject in the plurality of multi-joint subjects leaves the area of real space.

20. The method of claim 11, including tracking locations in the area of real space of multiple candidate joints that are members of a set of candidate joints identified as a particular multi joint subject.

21. A computer program product, comprising: a computer readable memory comprising a non-transitory data storage medium; computer instructions stored in the memory executable by a computer to track multi-joint subjects in an area of real space by a process including: using sequences of images from a plurality of cameras having corresponding fields of view in real space, the field of view of each camera overlapping with the field of view of at least one other camera in the plurality of cameras; processing images in the sequences of images to generate corresponding arrays of joint data structures, the arrays of joint data structures corresponding to particular images classifying elements of the particular images by joint type, time of the particular image, and coordinates of the element in the particular image; translating the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in the real space; and identifying sets of candidate joints having coordinates in real space as multi-joint subjects in the real space.

22. The product of claim 21, wherein said processing images includes using convolutional neural networks.

23. The product of claim 21, wherein said processing image includes generating confidence arrays for elements of the image, where a confidence array for a particular element of an image includes confidence values for a plurality of joint types for the particular element, and selecting a joint type for the joint data structure of the particular element based on the confidence array.

24. The product of claim 21, wherein identifying sets of candidate joints comprises applying heuristic functions based on physical relationships among joints of subjects in real space to identify sets of candidate joints as multi-joint subjects.

25. The product of claim 24, including storing the sets of joints identified as multi-joint subjects, and wherein the identifying sets of candidate joints includes determining whether a candidate joint identified in images taken at a particular time corresponds with a member of one of the sets of candidate joints identified as a multi-joint subject in a preceding image.

26. The product of claim 21, wherein the sequences of images are synchronized.

27. The product of claim 21, wherein the plurality of cameras comprise cameras disposed over and having fields of view encompassing respective parts of the area in real space, and the coordinates in real space of members of a set of candidate joints identified as a multi-joint subject identify locations in the area of the multi-joint subject.

28. The product of claim 21, including tracking locations of a plurality of multi-joint subjects in the area of real space.

29. The product of claim 28, including determining when multi-joint subjects in the plurality of multi-joint subjects leave the area of real space.

30. The product of claim 21, including tracking locations in the area of real space of multiple candidate joints that are members of a set of candidate joints identified as a particular multi joint subject.
Description



COPYRIGHT NOTICE

A portion of the disclosure of this patent document contains material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.

REFERENCE TO COMPUTER PROGRAM LISTING APPENDIX

A computer program listing appendix (Copyright, Standard Cognition, Inc.) submitted electronically via the EFS-Web in ASCII text accompanies this application and is incorporated by reference. The name of the ASCII text file is "STCG_Computer_Program_Appx" created on 14 Nov. 2017 and is 16,755 bytes.

BACKGROUND

Field

The present invention relates to systems that identify and track multi-joint subjects in real space.

Description of Related Art

A difficult problem in image processing arises when images from multiple cameras disposed over large spaces are used to identify and track movement of subjects. One approach to this problem is described in United States Patent Application Publication No.: US 2017/02782 by Shingu et al.

Tracking multiple subjects within an area of real space, such as a shopping store, presents many technical problems. For example, consider such an image processing system deployed in a shopping store with multiple customers moving in aisles between the shelfs and in other open spaces within the shopping store. At any moment in time, a single customer can be present in images from multiple cameras with overlapping fields of view. In a typical shopping store, different portions of the customer will be occluded in images from different cameras because of the presence of other customer, shelves, and product displays, etc. Also, there can be many customers in the store at any given time, making it difficult to identify and track individuals over time.

It is desirable to provide a system that can more effectively and automatically identify and track subjects in large spaces.

SUMMARY

A system, and method for operating a system, are provided for tracking multi-joint subjects, such as persons, in real space. The system uses a plurality of cameras to produce respective sequences of images of corresponding fields of view in the real space. The field of view of each camera overlaps with the field of view of at least one other camera in the plurality of cameras. The system processes images in the sequences of images to generate arrays of joint data structures corresponding to each image. The arrays of joint data structures corresponding to particular images classify elements of the particular images by the joint type, time of the particular image, and coordinates of the element in the particular image. The system then translates the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in the real space. Finally, the system identifies constellations of candidate joints, where the constellations include respective sets of candidate joints having coordinates in real space, as multi-joint subjects in the real space.

In one embodiment, the image recognition engines comprise convolutional neural networks. The processing of images by image recognition engines includes generating confidence arrays for elements of the image. A confidence array for a particular element of an image includes confidence values for a plurality of joint types for the particular element. The confidence arrays are used to select a joint type for the joint data structure of the particular element based on the confidence array.

In one embodiment of the system for tracking multi joint subjects, identifying sets of candidate joints comprises applying heuristic functions based on physical relationships among joints of subjects in real space to identify sets of candidate joints as multi joint subjects. The processing includes storing the sets of joints identified as multi-joint subjects. Identifying sets of candidate joints includes determining whether a candidate joint identified in images taken at a particular time corresponds with a member of one of the sets of candidate joints identified as multi-joint subjects in a preceding image.

In one embodiment, the sequences of images are synchronized so that images in each of the sequences of images captured by the plurality of cameras represent the real space at a single point in time on the time scale of the movement of subjects through the space.

The coordinates in real space of members of a set of candidate joints identified as a multi-joint subject identify locations in the area of the multi-joint subject. In some embodiments, the processing includes simultaneous tracking of the locations of a plurality of multi-joint subjects in the area of real space. In some embodiments, the processing includes determining when a multi-joint subject in the plurality of multi-joint subjects leaves the area of real space. In some embodiments, the processing includes determining a direction in which the multi-joint subject is facing at a given point in time.

Other aspects and advantages of the present invention can be seen on review of the drawings, the detailed description and the claims, which follow.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 illustrates an architectural level schematic of a system in which a tracking engine tracks multi-joint subjects using joint data generated by image recognition engines.

FIG. 2 is a side view of an aisle in a shopping store illustrating a camera arrangement.

FIG. 3 is a top view of the aisle of FIG. 2 in a shopping store illustrating a camera arrangement.

FIG. 4 is a camera and computer hardware arrangement configured for hosting an image recognition engine of FIG. 1.

FIG. 5 illustrates a convolutional neural network illustrating identification of joints in an image recognition engine of FIG. 1.

FIG. 6 shows an example data structure for storing joint information.

FIG. 7 illustrates the tracking engine of FIG. 1 with a global metric calculator.

FIG. 8 shows an example data structure for storing a multi-joint subject including the information of associated joints.

FIG. 9 is a flowchart illustrating process steps for tracking multi-joint subjects by the system of FIG. 1.

FIG. 10 is a flowchart showing more detailed process steps for a camera calibration step of FIG. 9.

FIG. 11 is a flowchart showing more detailed process steps for a video process step of FIG. 9.

FIG. 12A is a flowchart showing a first part of more detailed process steps for the scene process of FIG. 9.

FIG. 12B is a flowchart showing a second part of more detailed process steps for the scene process of FIG. 9.

FIG. 13 is an illustration of an environment in which an embodiment of the system of FIG. 1 is used.

FIG. 14 is an illustration of video and scene processes in an embodiment of the system of FIG. 1.

FIG. 15 is an illustration of region proposals--"What CNN" model in an embodiment of the system of FIG. 1.

FIG. 16 is an illustration of region proposals--"When CNN" model in an embodiment of the system of FIG. 1.

DETAILED DESCRIPTION

The following description is presented to enable any person skilled in the art to make and use the invention, and is provided in the context of a particular application and its requirements. Various modifications to the disclosed embodiments will be readily apparent to those skilled in the art, and the general principles defined herein may be applied to other embodiments and applications without departing from the spirit and scope of the present invention. Thus, the present invention is not intended to be limited to the embodiments shown but is to be accorded the widest scope consistent with the principles and features disclosed herein.

System Overview

A system and various implementations for tracking multi-joint subjects are described with reference to FIGS. 1-16. The system and processes are described with reference to FIG. 1, an architectural level schematic of a system in accordance with an implementation. Because FIG. 1 is an architectural diagram, certain details are omitted to improve the clarity of the description.

The discussion of FIG. 1 is organized as follows. First, the elements of the system are described, followed by their interconnections. Then, the use of the elements in the system is described in greater detail.

FIG. 1 provides a block diagram level illustration of a system 100. The system 100 includes cameras 114, network nodes hosting image recognition engines 112a, 112b, and 112n, a tracking engine 110 deployed in a network node (or nodes) on the network, a calibrator 120, a subject database 140, a training database 150, a joints heuristics database 160, a calibration database 170, and a communication network or networks 181.

As used herein, a network node is an addressable hardware device or virtual device that is attached to a network, and is capable of sending, receiving, or forwarding information over a communications channel to or from other network nodes. Examples of electronic devices which can be deployed as hardware network nodes include all varieties of computers, workstations, laptop computers, handheld computers, and smartphones. Network nodes can be implemented in a cloud-based server system. More than one virtual device configured as a network node can be implemented using a single physical device.

For the sake of clarity, only three network nodes hosting image recognition engines are shown in the system 100. However, any number of network nodes hosting image recognition engines can be connected to the tracking engine 110 through the network(s) 181. Also, an image recognition engine, a tracking engine and other processing engines described herein can execute using more than one network node in a distributed architecture.

The interconnection of the elements of system 100 will now be described. Network(s) 181 couples the network nodes 101a, 101b, and 101c respectively hosting image recognition engines 112a, 112b, and 112n, the network node 102 hosting the tracking engine 110, the calibrator 120, the subject database 140, the training database 150, the joints heuristics database 160, and the calibration database 170. Cameras 114 are connected to the tracking engine 110 through network nodes hosting image recognition engines 112a, 112b, and 112n. In one embodiment, the cameras 114 are installed in a shopping store (such as a supermarket) such that sets of cameras 114 (two or more) with overlapping fields of view are positioned over each aisle capture images of real space in the store. In FIG. 1, two cameras are arranged over aisle 116a, two cameras are arranged over aisle 116b, and three cameras are arranged over aisle 116n. The cameras 114 are installed over aisles with overlapping fields of view. In such an embodiment, the cameras are configured with the goal that customers moving in the aisles of the shopping store are present in the field of view of two or more cameras at any moment in time.

Cameras 114 can be synchronized in time with each other, so that images are captured at the same time, or close in time, and at the same image capture rate. The cameras 114 can send respective continuous streams of images at a predetermined rate to network nodes hosting image recognition engines 112a to 112n. Images captured in all the cameras covering an area of real space at the same time, or close in time, are synchronized in the sense that the synchronized images can be identified in the processing engines as representing different views of subjects having fixed positions in the real space. For example, in one embodiment, the cameras send image frames at the rates of 30 frames per second (fps) to respective network nodes hosting image recognition engines 112a to 112n. Each frame has a timestamp, identity of the camera (abbreviated as "camera_id"), and a frame identity (abbreviated as "frame_id") along with the image data.

Cameras installed over an aisle are connected to respective image recognition engines. For example, in FIG. 1, the two cameras installed over the aisle 116a are connected to the network node 101a hosting an image recognition engine 112a. Likewise, the two cameras installed over aisle 116b are connected to the network node 101b hosting an image recognition engine 112b. Each image recognition engine 112a to 112n hosted in a network node or nodes 101a to 101n, separately processes the image frames received from one camera each in the illustrated example.

In one embodiment, each image recognition engine 112a, 112b, and 112n is implemented as a deep learning algorithm such as a convolutional neural network (abbreviated CNN). In such an embodiment, the CNN is trained using a training database 150. The training database 150 has a large collection of images for each of the different types of joints for the multi-joint subjects. In the example embodiment of a shopping store, the multi joint subjects are the customers moving in the aisles between the shelves. In an example embodiment, during training of the CNN, the system 100 is referred to as a "training system". After training the CNN using the training database 150, the CNN is switched to production mode to process images of customers in the shopping store in real time. In an example embodiment, during production, the system 100 is referred to as a runtime system (also referred to as an inference system). The CNN in each image recognition engine produces arrays of joint data structures for images in its respective stream of images. In an embodiment as described herein, an array of joints data structures is produced for each processed image, so that each image recognition engine 112a to 112n produces an output stream of arrays of joints data structures.

The cameras 114 are calibrated before switching the CNN to production mode. The calibrator 120 calibrates the cameras and stores the calibration data in the calibration database 170.

The tracking engine 110, hosted on the network node 102, receives continuous streams of arrays of joints data structures for the multi-joint subjects from image recognition engines 112a to 112n. The tracking engine 110 processes the arrays of joints data structures and translates the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in the real space. For each set of synchronized images, the combination of candidate joints identified throughout the real space can be considered for the purposes of analogy, to be like a galaxy of candidate joints. For each succeeding point in time, movement of the candidate joints is recorded so that the galaxy changes over time. The output of the tracking engine 110 is stored in the subject database 140.

The tracking engine 110 uses logic to identify sets of candidate joints having coordinates in real space as multi joint subjects in the real space. For the purposes of analogy, each set of candidate points is like a constellation of candidate joints at each point in time. The constellations of candidate joints can move over time.

The logic to identify sets of candidate joints comprises heuristic functions based on physical relationships amongst joints of subjects in real space. These heuristic functions are used to identify sets of candidate joints as multi joint subjects. The heuristic functions are stored in joints heuristics database 160. The output of the tracking engine 110 is stored in the subject database 140. Thus, the sets of candidate joints comprise individual candidate joints that have relationships according to the heuristic parameters with other individual candidate joints and subsets of candidate joints in a given set that has been identified, or can be identified, as an individual subject.

The actual communication path through the network 181 can be point-to-point over public and/or private networks. The communications can occur over a variety of networks 181, e.g., private networks, VPN, MPLS circuit, or Internet, and can use appropriate application programming interfaces (APIs) and data interchange formats, e.g., Representational State Transfer (REST), JavaScript.TM. Object Notation (JSON), Extensible Markup Language (XML), Simple Object Access Protocol (SOAP), Java.TM. Message Service (JMS), and/or Java Platform Module System. All of the communications can be encrypted. The communication is generally over a network such as the LAN (local area network), WAN (wide area network), telephone network (Public Switched Telephone Network (PSTN), Session Initiation Protocol (SIP), wireless network, point-to-point network, star network, token ring network, hub network, Internet, inclusive of the mobile Internet, via protocols such as EDGE, 3G, 4G LTE, Wi-Fi, and WiMAX. Additionally, a variety of authorization and authentication techniques, such as username/password, Open Authorization (OAuth), Kerberos, SecureID, digital certificates and more, can be used to secure the communications.

The technology disclosed herein can be implemented in the context of any computer-implemented system including a database system, a multi-tenant environment, or a relational database implementation like an Oracle.TM. compatible database implementation, an IBM DB2 Enterprise Server.TM. compatible relational database implementation, a MySQL.TM. or PostgreSQL.TM. compatible relational database implementation or a Microsoft SQL Server.TM. compatible relational database implementation or a NoSQL.TM. non-relational database implementation such as a Vampire.TM. compatible non-relational database implementation, an Apache Cassandra.TM. compatible non-relational database implementation, a BigTable.TM. compatible non-relational database implementation or an HBase.TM. or DynamoDB.TM. compatible non-relational database implementation. In addition, the technology disclosed can be implemented using different programming models like MapReduce.TM., bulk synchronous programming, MPI primitives, etc. or different scalable batch and stream management systems like Apache Storm.TM., Apache Spark.TM., Apache Kafka.TM., Apache Flink.TM. Truviso.TM., Amazon Elasticsearch Service.TM., Amazon Web Services.TM. (AWS), IBM Info-Sphere.TM., Borealis.TM., and Yahoo! S4.TM..

Camera Arrangement

The cameras 114 are arranged to track multi-joint entities in a three-dimensional (abbreviated as 3D) real space. In the example embodiment of the shopping store, the real space can include the area of the shopping store where items for sale are stacked in shelves. A point in the real space can be represented by an (x, y, z) coordinate system. Each point in the area of real space for which the system is deployed is covered by the fields of view of two or more cameras 114.

In a shopping store, the shelves can be arranged in a variety of manners, such as along the walls of the shopping store, or in rows forming aisles or a combination of the two arrangements. FIG. 2 shows an arrangement of shelves, forming an aisle 116a, viewed from one end of the aisle 116a. Two cameras, camera A 206 and camera B 208 are positioned over the aisle 116a at a predetermined distance from a roof 230 and a floor 220 of the shopping store. The cameras 114 comprise cameras disposed over and having fields of view encompassing respective parts of the floor area in the real space, and the coordinates in real space of members of a set of candidate joints, identified as a multi-joint subject, identify locations in the floor area of the multi-joint subject. In the example embodiment of the shopping store, the real space can include all of the floor 220 in the shopping store. Cameras 114 are placed and oriented such that areas of the floor 220 and shelves can be seen by at least two cameras. The cameras 114 also cover floor space in front of the shelves 202 and 204. Camera angles are selected to have both steep perspective, straight down, and angled perspectives that give more full body images of the customers. In one example embodiment, the cameras 114 are configured at an eight (8) foot height or higher throughout the shopping store. FIG. 13 presents an illustration of such an embodiment.

In FIG. 2, the cameras 206 and 208 have overlapping fields of view, covering the space between a shelf A 202 and a shelf B 204 with overlapping fields of view 216 and 218, respectively. A location in the real space is represented as a (x, y, z) point of the real space coordinate system. "x" and "y" represent positions on a two-dimensional (2D) plane which can be the floor 220 of the shopping store. The value "z" is the height of the point above the 2D plane at floor 220 in one configuration.

FIG. 3 illustrates the aisle 116a viewed from the top. FIG. 2, further showing an example arrangement of the positions of cameras 206 and 208 over the aisle 116a. The cameras 206 and 208 are positioned closer to opposite ends of the aisle 116a. The camera A 206 is positioned at a predetermined distance from the shelf A 202 and the camera B 208 is positioned at a predetermined distance from the shelf B 204. In another embodiment, in which more than two cameras are positioned over an aisle, the cameras are positioned at equal distances from each other. In such an embodiment, two cameras are positioned close to the opposite ends and a third camera is positioned in the middle of the aisle. It is understood that a number of different camera arrangements are possible.

Camera Calibration

The camera calibrator 120 performs two types of calibrations: internal and external. In internal calibration, the internal parameters of the cameras 114 are calibrated. Examples of internal camera parameters include focal length, principal point, skew, fisheye coefficients, etc. A variety of techniques for internal camera calibration can be used. One such technique is presented by Zhang in "A flexible new technique for camera calibration" published in IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 22, No. 11, November 2000.

In external calibration, the external camera parameters are calibrated in order to generate mapping parameters for translating the 2D image data into 3D coordinates in real space. In one embodiment, one multi joint subject, such as a person, is introduced into the real space. The multi-joint subject moves through the real space on a path that passes through the field of view of each of the cameras 114. At any given point in the real space, the multi-joint subject is present in the fields of view of at least two cameras forming a 3D scene. The two cameras, however, have a different view of the same 3D scene in their respective two-dimensional (2D) image planes. A feature in the 3D scene such as a left-wrist of the multi joint subject is viewed by two cameras at different positions in their respective 2D image planes.

A point correspondence is established between every pair of cameras with overlapping fields of view for a given scene. Since each camera has a different view of the same 3D scene, a point correspondence is two pixel locations (one location from each camera with overlapping field of view) that represent the projection of the same point in the 3D scene. Many point correspondences are identified for each 3D scene using the results of the image recognition engines 112a to 112n for the purposes of the external calibration. The image recognition engines identify the position of a joint as (x, y) coordinates, such as row and column numbers, of pixels in the 2D image planes of respective cameras 114. In one embodiment, a joint is one of 19 different types of joints of the multi-joint subject. As the multi-joint subject moves through the fields of view of different cameras, the tracking engine 110 receives (x, y) coordinates of each of the 19 different types of joints of the multi-joint subject used for the calibration from cameras 114 per image.

For example, consider an image from a camera A and an image from a camera B both taken at the same moment in time and with overlapping fields of view. There are pixels in an image from camera A that correspond to pixels in a synchronized image from camera B. Consider that there is a specific point of some object or surface in view of both camera A and camera B and that point is captured in a pixel of both image frames. In external camera calibration, a multitude of such points are identified and referred to as corresponding points. Since there is one multi-joint subject in the field of view of camera A and camera B during calibration, key joints of this multi-joint subject are identified, for example, the center of left wrist. If these key joints are visible in image frames from both camera A and camera B then it is assumed that these represent corresponding points. This process is repeated for many image frames to build up a large collection of corresponding points for all pairs of cameras with overlapping fields of view. In one embodiment, images are streamed off of all cameras at a rate of 30 FPS (frames per second) or more and a resolution of 720 pixels in full RGB (red, green, and blue) color. These images are in the form of one-dimensional arrays (also referred to as flat arrays).

The large number of images collected above for a multi joint subject are used to determine corresponding points between cameras with overlapping fields of view. Consider two cameras A and B with overlapping field of view. The plane passing through camera centers of cameras A and B and the joint location (also referred to as feature point) in the 3D scene is called the "epipolar plane". The intersection of the epipolar plane with the 2D image planes of the cameras A and B defines the "epipolar line". Given these corresponding points, a transformation is determined that can accurately map a corresponding point from camera A to an epipolar line in camera B's field of view that is guaranteed to intersect the corresponding point in the image frame of camera B. Using the image frames collected above for a multi joint subject, the transformation is generated. It is known in the art that this transformation is non-linear. The general form is furthermore known to require compensation for the radial distortion of each camera's lens, as well as the non-linear coordinate transformation moving to and from the projected space. In external camera calibration, an approximation to the ideal non-linear transformation is determined by solving a non-linear optimization problem. This non-linear optimization function is used by the tracking engine 110 to identify the same joints in outputs (arrays of joint data structures) of different image recognition engines 112a to 112n, processing images of cameras 114 with overlapping fields of view. The results of the internal and external camera calibration are stored in the calibration database 170.

A variety of techniques for determining the relative positions of the points in images of cameras 114 in the real space can be used. For example, Longuet-Higgins published, "A computer algorithm for reconstructing a scene from two projections" in Nature, Volume 293, 10 Sep. 1981. This paper presents computing a three-dimensional structure of a scene from a correlated pair of perspective projections when spatial relationship between the two projections is unknown. Longuet-Higgins paper presents a technique to determine the position of each camera in the real space with respect to other cameras. Additionally, their technique allows triangulation of a multi-joint subject in the real space, identifying the value of the z-coordinate (height from the floor) using images from cameras 114 with overlapping fields of view. An arbitrary point in the real space, for example, the end of a shelf in one corner of the real space, is designated as a (0, 0, 0) point on the (x, y, z) coordinate system of the real space.

In an embodiment of the technology, the parameters of the external calibration are stored in two data structures. The first data structure stores intrinsic parameters. The intrinsic parameters represent a projective transformation from the 3D coordinates into 2D image coordinates. The first data structure contains intrinsic parameters per camera as shown below. The data values are all numeric floating point numbers. This data structure stores a 3.times.3 intrinsic matrix, represented as "K" and distortion coefficients. The distortion coefficients include six radial distortion coefficients and two tangential distortion coefficients. Radial distortion occurs when light rays bend more near the edges of a lens than they do at its optical center. Tangential distortion occurs when the lens and the image plane are not parallel. The following data structure shows values for the first camera only. Similar data is stored for all the cameras 114.

{

1: { K: [[x, x, x], [x, x, x], [x, x, x]], distortion coefficients: [x, x, x, x, x, x, x, x] }, . . . }

The second data structure stores per pair of cameras: a 3.times.3 fundamental matrix (F), a 3.times.3 essential matrix (E), a 3.times.4 projection matrix (P), a 3.times.3 rotation matrix (R) and a 3.times.1 translation vector (t). This data is used to convert points in one camera's reference frame to another camera's reference frame. For each pair of cameras, eight homography coefficients are also stored to map the plane of the floor 220 from one camera to another. A fundamental matrix is a relationship between two images of the same scene that constrains where the projection of points from the scene can occur in both images. Essential matrix is also a relationship between two images of the same scene with the condition that the cameras are calibrated. The projection matrix gives a vector space projection from 3D real space to a subspace. The rotation matrix is used to perform a rotation in Euclidean space. Translation vector "t" represents a geometric transformation that moves every point of a figure or a space by the same distance in a given direction. The homography_floor_coefficients are used to combine images of features of subjects on the floor 220 viewed by cameras with overlapping fields of views. The second data structure is shown below. Similar data is stored for all pairs of cameras. As indicated previously, the x's represents numeric floating point numbers.

{

1: { 2: { F: [[x, x, x], [x, x, x], [x, x, x]], E: [[x, x, x], [x, x, x], [x, x, x]], P: [[x, x, x, x], [x, x, x, x], [x, x, x, x]], R: [[x, x, x], [x, x, x], [x, x, x]], t: [x, x, x], homography_floor_coefficients: [x, x, x, x, x, x, x, x] } }, . . . } Network Configuration

FIG. 4 presents an architecture 400 of a network hosting image recognition engines. The system includes a plurality of network nodes 101a-101n in the illustrated embodiment. In such an embodiment, the network nodes are also referred to as processing platforms. Processing platforms 101a-101n and cameras 412, 414, 416, . . . 418 are connected to network(s) 481.

FIG. 4 shows a plurality of cameras 412, 414, 416, . . . 418 connected to the network(s). A large number of cameras can be deployed in particular systems. In one embodiment, the cameras 412 to 418 are connected to the network(s) 481 using Ethernet-based connectors 422, 424, 426, and 428, respectively. In such an embodiment, the Ethernet-based connectors have a data transfer speed of 1 gigabit per second, also referred to as Gigabit Ethernet. It is understood that in other embodiments, cameras 114 are connected to the network using other types of network connections which can have a faster or slower data transfer rate than Gigabit Ethernet. Also, in alternative embodiments, a set of cameras can be connected directly to each processing platform, and the processing platforms can be coupled to a network.

Storage subsystem 430 stores the basic programming and data constructs that provide the functionality of certain embodiments of the present invention. For example, the various modules implementing the functionality of image recognition engines of the invention may be stored in storage subsystem 430. The storage subsystem 430 is an example of a computer readable memory comprising a non-transitory data storage medium, having computer instructions stored in the memory executable by a computer to track multi joint subjects in an area of real space by processes as described herein. In other examples, the computer instructions can be stored in other types of memory, including portable memory, that comprise a non-transitory data storage medium or media, readable by a computer.

These software modules are generally executed by a processor subsystem 450. A host memory subsystem 432 typically includes a number of memories including a main random access memory (RAM) 434 for storage of instructions and data during program execution and a read-only memory (ROM) 436 in which fixed instructions are stored. In one embodiment, the RAM 434 is used as a buffer for storing video streams from the cameras 114 connected to the platform 101a.

A file storage subsystem 440 provides persistent storage for program and data files. In an example embodiment, the storage subsystem 440 includes four 120 Gigabyte (GB) solid state disks (SSD) in a RAID 0 (redundant array of independent disks) arrangement identified by a numeral 442. In the example embodiment, in which CNN is used to identify joints of multi-joint subjects, the RAID 0 442 is used to store training data. During training, the training data which is not in RAM 434 is read from RAID 0 442. Similarly when images are being recorded for training purposes, the data which is not in RAM 434 is stored in RAID 0 442. In the example embodiment, the hard disk drive (HDD) 446 is a 10 terabyte storage. It is slower in access speed than the RAID 0 442 storage. The solid state disk (SSD) 444 contains the operating system and related files for the image recognition engine 112a.

In an example configuration, three cameras 412, 414, and 416, are connected to the processing platform 101a. Each camera has a dedicated graphics processing unit GPU 1 462, GPU 2 464, and GPU 3 466, to process images sent by the camera. It is understood that fewer than or more than three cameras can be connected per processing platform. Accordingly, fewer or more GPUs are configured in the network node so that each camera has a dedicated GPU for processing the image frames received from the camera. The processor subsystem 450, the storage subsystem 430 and the GPUs 462, 464, and 466 communicate using the bus subsystem 454.

A number of peripheral devices such as a network interface subsystem, user interface output devices, and user interface input devices are also connected to the bus system 454 forming part of the processing platform 101a. These subsystems and devices are intentionally not shown in FIG. 4 to improve the clarity of the description. Although bus subsystem 454 is shown schematically as a single bus, alternative embodiments of the bus subsystem may use multiple busses.

In one embodiment, the cameras 412 can be implemented using Chameleon3 1.3 MP Color USB3 Vision (Sony ICX445), having a resolution of 1288.times.964, a frame rate of 30 FPS, and at 1.3 MegaPixels per image, with Varifocal Lens having a working distance (mm) of 300-.infin., a field of view field of view with a 1/3'' sensor of 98.2.degree.-23.8.degree..

Convolutional Neural Network

The image recognition engines 112a to 112n in the processing platforms 101a-101n receive a continuous stream of images at a predetermined rate. In one embodiment, the image recognition engines comprise convolutional neural networks (abbreviated CNN). FIG. 5 illustrates processing of image frames by a CNN referred to by a numeral 500. The input image 510 is a matrix consisting of image pixels arranged in rows and columns. In one embodiment, the input image 510 has a width of 1280 pixels, height of 720 pixels and 3 channels red, blue, and green also referred to as RGB. The channels can be imagined as three 1280.times.720 two-dimensional images stacked over one another. Therefore, the input image has dimensions of 1280.times.720.times.3 as shown in FIG. 5.

A 2.times.2 filter 520 is convolved with the input image 510. In this embodiment, no padding is applied when the filter is convolved with the input. Following this, a nonlinearity function is applied to the convolved image. In the present embodiment, rectified linear unit (ReLU) activations are used. Other examples of nonlinear functions include sigmoid, hyperbolic tangent (tan h) and variations of ReLU such as leaky ReLU. A search is performed to find hyper-parameter values. The hyper-parameters are C.sub.1, C.sub.2, . . . , C.sub.N where C.sub.N means the number of channels for convolution layer "N". Typical values of N and C are shown in FIG. 5. There are twenty five (25) layers in the CNN as represented by N equals 25. The values of C are the number of channels in each convolution layer for layers 1 to 25. In other embodiments, additional features are added to the CNN 500 such as residual connections, squeeze-excitation modules, and multiple resolutions.

In typical CNNs used for image classification, the size of the image (width and height dimensions) is reduced as the image is processed through convolution layers. That is helpful in feature identification as the goal is to predict a class for the input image. However, in the illustrated embodiment, the size of the input image (i.e. image width and height dimensions) is not reduced, as the goal is to not only identify a joint (also referred to as a feature) in the image frame, but also identify its exact location in the image so it can be mapped to a coordinates in the real space. Therefore, as shown FIG. 5, the width and height dimensions of the image remain unchanged as the processing proceeds through convolution layers of the CNN.

In one embodiment, the CNN 500 identifies one of the 19 possible joints of the multi-joint subjects at each element of the image. The possible joints can be grouped in two categories: foot joints and non-foot joints. The 19.sup.th type of joint classification is for all non-joint features of the multi joint subject (i.e. elements of the image not classified as a joint).

Foot Joints: Ankle joint (left and right)

Non-Foot Joints: Neck Nose Eyes (left and right) Ears (left and right) Shoulders (left and right) Elbows (left and right) Wrists (left and right) Hip (left and right) Knees (left and right)

Not a Joint

As can be seen, a "joint" for the purposes of this description is a trackable feature of a subject in the real space. A joint may correspond to physiological joints on the subjects, or other features such as the eye, or nose.

The first set of analyses on the stream of input images identifies trackable features of multi joint subjects in real space. In one embodiment, this is referred to as "joints analysis". In such an embodiment, the CNN used for joints analysis is referred to as "joints CNN". In one embodiment, the joints analysis is performed thirty times per second. The analysis is synchronized in time i.e., at 1/30.sup.th of a second, images from all cameras 114 are analyzed to identify joints of all multi-joint subjects in the real space. The results of this analysis is stored as a "snapshot".

A snapshot can be in the form of a dictionary containing arrays of joint data structures from images of all cameras 114 at a moment in time, representing a constellation of candidate joints within the area of real space covered by the system. In one embodiment, the snapshot is stored in the subject database 140.

In this example CNN, a softmax function is applied to every element of the image in the final layer of convolution layers 530. The softmax function transforms a K-dimensional vector of arbitrary real values to a K-dimensional vector of real values in the range [0, 1] that add up to 1. In one embodiment, an element of an image is a single pixel. The softmax function converts the 19-dimensional array (also referred to a 19-dimensional vector) of arbitrary real values for each pixel to a 19-dimensional confidence array of real values in the range [0, 1] that add up to 1. The 19 dimensions of a pixel in the image frame correspond to the 19 channels in the final layer of the CNN which further correspond to 19 types of joints of the multi joint subjects.

A large number of picture elements can classified as one of each of the 19 types of joints in one image depending on the number of multi-joint subjects in the field of view of the source camera for that image.

The image recognition engines 112a to 112n process images to generate confidence arrays for elements of the image. A confidence array for a particular element of an image includes confidence values for a plurality of joint types for the particular element. Each one of the image recognition engines 112a to 112n, respectively, generates an output matrix 540 of confidence arrays per image. Finally, each image recognition engine generates arrays of joint data structures corresponding to each output matrix 540 of confidence arrays per image. The arrays of joint data structures corresponding to particular images classify elements of the particular images by joint type, time of the particular image, and coordinates of the element in the particular image. A joint type for the joint data structure of the particular elements in each image is selected based on the values of the confidence array.

Each joint of the multi joint subjects can be considered to be distributed in the output matrix 540 as a heat map. The heat map can be resolved to show image elements having the highest values (peak) for each joint type. Ideally, for a given picture element having high values of a particular joint type, surrounding picture elements outside a range from the given picture element will have lower values for that joint type, so that a location for a particular joint having that joint type can be identified in the image space coordinates. Correspondingly, the confidence array for that image element will have the highest confidence value for that joint and lower confidence values for the remaining 18 types of joints.

In one embodiment, batches of images from each camera 114 are processed by respective image recognition engines. For example, six contiguously timestamped images are processed sequentially in a batch to take advantage of cache coherence. The parameters for one layer of the CNN 500 are loaded in memory and applied to the batch of six image frames. Then the parameters for the next layer are loaded in memory and applied to the batch of six images. This is repeated for all convolution layers 530 in the CNN 500. The cache coherence reduces processing time and improves performance of the image recognition engines.

In one such embodiment, referred to as three dimensional (3D) convolution, a further improvement in performance of the CNN 500 is achieved by sharing information across image frames in the batch. This helps in more precise identification of joints and reduces false positives. For examples, features in the image frames for which pixel values do not change across the multiple image frames in a given batch are likely static objects such as a shelf. The change of values for the same pixel across image frames in a given batch indicates that this pixel is likely a joint. Therefore, the CNN 500 can focus more on processing that pixel to accurately identify the joint identified by that pixel.

Joints Data Structure

The output of the CNN 500 is a matrix of confidence arrays for each image per camera. The matrix of confidence arrays is transformed into an array of joint data structures. A joint data structure 600 as shown in FIG. 6 is used to store the information of each joint. The joint data structure 600 identifies x and y positions of the element in the particular image in the 2D image space of the camera from which the image is received. A joint number identifies the type of joint identified. For example, in one embodiment the values range from 1 to 19. A value of 1 indicates that the joint is a left-ankle, a value of 2 indicates the joint is a right-ankle and so on. The type of joint is selected using the confidence array for that element in the output matrix 540. For example, in one embodiment, if the value corresponding to the left-ankle joint is highest in the confidence array for that image element, then the value of the joint number is "1".

A confidence number indicates the degree of confidence of the CNN 500 in predicting that joint. If the value of confidence number is high, it means the CNN is confident in its prediction. An integer-Id is assigned to the joint data structure to uniquely identify it. Following the above mapping, the output matrix 540 of confidence arrays per image is converted into an array of joint data structures for each image.

The image recognition engines 112a to 112n receive the sequences of images from cameras 114 and process images to generate corresponding arrays of joint data structures as described above. An array of joint data structures for a particular image classifies elements of the particular image by joint type, time of the particular image, and the coordinates of the elements in the particular image. In one embodiment, the image recognition engines 112a to 112n are convolutional neural networks CNN 500, the joint type is one of the 19 types of joints of the multi-joint subjects, the time of the particular image is the timestamp of the image generated by the source camera 114 for the particular image, and the coordinates (x, y) identify the position of the element on a 2D image plane.

In one embodiment, the joints analysis includes performing a combination of k-nearest neighbors, mixture of Gaussians, various image morphology transformations, and joints CNN on each input image. The result comprises arrays of joint data structures which can be stored in the form of a bit mask in a ring buffer that maps image numbers to bit masks at each moment in time.

Tracking Engine

The tracking engine 110 is configured to receive arrays of joint data structures generated by the image recognition engines 112a to 112n corresponding to images in sequences of images from cameras having overlapping fields of view. The arrays of joint data structures per image are sent by image recognition engines 112a to 112n to the tracking engine 110 via the network(s) 181 as shown in FIG. 7. The tracking engine 110 translates the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate joints having coordinates in the real space. The tracking engine 110 comprises logic to identify sets of candidate joints having coordinates in real space (constellations of joints) as multi-joint subjects in the real space. In one embodiment, the tracking engine 110 accumulates arrays of joint data structures from the image recognition engines for all the cameras at a given moment in time and stores this information as a dictionary in the subject database 140, to be used for identifying a constellation of candidate joints. The dictionary can be arranged in the form of key-value pairs, where keys are camera_ids and values are arrays of joint data structures from the camera. In such an embodiment, this dictionary is used in heuristics-based analysis to determine candidate joints and for assignment of joints to multi joint subjects. In such an embodiment, a high-level input, processing and output of the tracking engine 110 is illustrated in table 1.

TABLE-US-00001 TABLE 1 Inputs, processing and outputs from tracking engine 110 in an example embodiment. Inputs Processing Output Arrays of joint Create joints dictionary List of data structures Reproject joint positions multi-joint per image and in the fields of view of subjects in for each joint cameras with the real space data structure overlapping fields of at a moment Unique ID view to candidate joints in time Confidence number Joint number (x, y) position in image space

Grouping Joints into Candidate Joints

The tracking engine 110 receives arrays of joint data structures along two dimensions: time and space. Along the time dimension, the tracking engine receives sequentially timestamped arrays of joint data structures processed by image recognition engines 112a to 112n per camera. The joint data structures include multiple instances of the same joint of the same multi-joint subject over a period of time in images from cameras having overlapping fields of view. The (x, y) coordinates of the element in the particular image will usually be different in sequentially timestamped arrays of joint data structures because of the movement of the multi-joint subject to which the particular joint belongs. For example, twenty picture elements classified as left-wrist joints can appear in many sequentially timestamped images from a particular camera, each left-wrist joint having a position in real space that can be changing or unchanging from image to image. As a result, twenty left-wrist joint data structures 600 in many sequentially timestamped arrays of joint data structures can represent the same twenty joints in real space over time.

Because multiple cameras having overlapping fields of view cover each location in the real space, at any given moment in time, the same joint can appear in images of more than one of the cameras 114. The cameras 114 are synchronized in time, therefore, the tracking engine 110 receives joint data structures for a particular joint from multiple cameras having overlapping fields of view, at any given moment in time. This is the space dimension, the second of the two dimensions: time and space, along which the tracking engine 110 receives data in arrays of joint data structures.

The tracking engine 110 uses an initial set of heuristics stored in the joints heuristics database 160 to identify candidate joint data structures from the arrays of joints data structures. The goal is to minimize a global metric over a period of time. A global metric calculator 702 calculates the global metric. The global metric is a summation of multiple values described below. Intuitively, the value of the global metric is minimum when the joints in arrays of joint data structures received by the tracking engine 110 along the time and space dimensions are correctly assigned to respective multi-joint subjects. For example, consider the embodiment of the shopping store with customers moving in the aisles. If the left-wrist of a customer A is incorrectly assigned to a customer B, then the value of the global metric will increase. Therefore, minimizing the global metric for each joint for each customer is an optimization problem. One option to solve this problem is to try all possible connections of joints. However, this can become intractable as the number of customers increases.

A second approach to solve this problem is to use heuristics to reduce possible combinations of joints identified as members of a set of candidate joints for a single subject. For example, a left-wrist joint cannot belong to a multi-joint subject far apart in space from other joints of the multi-joint subject because of known physiological characteristics of the relative positions of joints. Similarly, a left-wrist joint having a small change in position from image to image is less likely to belong to a multi joint subject having the same joint at the same position from an image far apart in time, because the multi-joint subjects are not expected to move at a very high speed. These initial heuristics are used to build boundaries in time and space for constellations of candidate joints that can be classified as a particular subject. The joints in the joint data structures within a particular time and space boundary are considered as "candidate joints" for assignment to sets of candidate joints as multi-joint subjects present in the real space. These candidate joints include joints identified in arrays of joint data structures from multiple images from a same camera over a period of time (time dimension) and across different cameras with overlapping fields of view (space dimension).

Foot Joints

The joints can be divided for the purposes of a procedure for grouping the joints into constellations, into foot and non-foot joints as shown above in the list of joints. The left and right-ankle joint type in the current example, are considered foot joints for the purpose of this procedure. The tracking engine 110 can start identification of sets of candidate joints of particular multi-joint subjects using foot joints. In the embodiment of the shopping store, the feet of the customers are on the floor 220 as shown in FIG. 2. The distance of the cameras 114 to the floor 220 is known. Therefore, when combining the joint data structures of foot joints from arrays of data joint data structures corresponding to images of cameras with overlapping fields of view, the tracking engine 110 can assume a known depth (distance along z axis). The value depth for foot joints is zero i.e. (x, y, 0) in the (x, y, z) coordinate system of the real space. Using this information, the image tracking engine 110 applies homographic mapping to combine joint data structures of foot joints from cameras with overlapping fields of view to identify the candidate foot joint. Using this mapping, the location of the joint in (x, y) coordinates in image space is converted to the location in the (x, y, z) coordinates in the real space, resulting in a candidate foot joint. This process is performed separately to identify candidate left and right foot joints using respective joint data structures.

Following this, the tracking engine 110 can combine a candidate left foot joint and a candidate right foot joint (assigns them to a set of candidate joints) to create a multi-joint subject. Other joints from the galaxy of candidate joints can be linked to the multi joint subject to build a constellation of some or all of the joint types for the created multi-joint subject.

If there is only one left candidate foot joint and one right candidate foot joint then it means there is only one multi-joint subject in the particular space at the particular time. The tracking engine 110 creates a new multi-joint subject having the left and the right candidate foot joints belonging to its set of joints. The multi joint subject is saved in the subject database 140. If there are multiple candidate left and right foot joints, then the global metrics calculator 702 attempts to combine each candidate left foot joint to each candidate right foot joint to create multi-joint subjects such that the value of the global metric is minimized.

Non-Foot Joints

To identify candidate non-foot joints from arrays of joint data structures within a particular time and space boundary, the tracking engine 110 uses the non-linear transformation (also referred to as a fundamental matrix) from any given camera A to its neighboring camera B with overlapping fields of view. The non-linear transformations are calculated using a single multi-joints subject and stored in the calibration database 170 as described above. For example, for two cameras A and B with overlapping fields of view, the candidate non-foot joints are identified as follows. The non-foot joints in arrays of joint data structures corresponding to elements in image frames from camera A are mapped to epipolar lines in synchronized image frames from camera B. A joint (also referred to as a feature in machine vision literature) identified by a joint data structure in an array of joint data structures of a particular image of camera A will appear on a corresponding epipolar line if it appears in the image of camera B. For example, if the joint in the joint data structure from camera A is a left-wrist joint, then a left-wrist joint on the epipolar line in the image of camera B represents the same left-wrist joint from the perspective of camera B. These two points in images of cameras A and B are projections of the same point in 3D scene in real space and are referred to as a "conjugate pair".

Machine vision techniques such as the technique by Longuet-Higgins published in the paper, titled, "A computer algorithm for reconstructing a scene from two projections" in Nature, Volume 293, 10 Sep. 1981, are applied to conjugate pairs of corresponding points to determine height of joints from the floor 220 in the real space. Application of the above method requires predetermined mapping between cameras with overlapping fields of view. That data is stored in the calibration database 170 as non-linear functions determined during the calibration of the cameras 114 described above.

The tracking engine 110 receives the arrays of joint data structures corresponding to images in sequences of images from cameras having overlapping fields of view, and translates the coordinates of the elements in the arrays of joint data structures corresponding to images in different sequences into candidate non-foot joints having coordinates in the real space. The identified candidate non-foot joints are grouped into sets of multi-joint subjects having coordinates in real space using the global metric calculator 702. The global metric calculator 702 calculates the global metric value and attempts to minimize the value by checking different combinations of non-foot joints. In one embodiment, the global metric is a sum of heuristics organized in four categories. The logic to identify sets of candidate joints comprises heuristic functions based on physical relationships among joints of subjects in real space to identify sets of candidate joints as multi joint subjects. Examples of physical relationships among joints are considered in the heuristics as described below.

First Category of Heuristics

The first category of heuristics includes metrics to ascertain similarity between two proposed multi joint subject-joint locations in the same camera view at the same or different moments in time. In one embodiment, these metrics are floating point values, where higher values mean two lists of joints are likely to belong to the same multi-joint subject. Consider the example embodiment of the shopping store, the metrics determine the distance between a customer's same joints in one camera from one image to the next image along the time dimension. Given a customer A in the field of view of the camera 412, the first set of metrics determines the distance between each of person A's joints from one image from the camera 412 to the next image from the camera 412. The metrics are applied to joint data structures 600 in arrays of joints data structures per image from cameras 114.

In one embodiment, two example metrics in the first category of heuristics are listed below: 1. The inverse of the Euclidean 2D coordinate distance (using x, y coordinate values for a particular image from a particular camera) between the left ankle-joint of two multi-joint subjects on the floor and the right ankle-joint of the two multi-joint subjects on the floor summed together. 2. The sum of the inverse of Euclidean 2D coordinate distance between every pair of non-foot joints of multi-joint subjects in the image frame. Second Category of Heuristics

The second category of heuristics includes metrics to ascertain similarity between two proposed multi-joint subject-joint locations from the fields of view of multiple cameras at the same moment in time. In one embodiment, these metrics are floating point values, where higher values mean two lists of joints are likely to belong to the same multi-joint subject. Consider the example embodiment of the shopping store, the second set of metrics determines the distance between a customer's same joints in image frames from two or more cameras (with overlapping fields of view) at the same moment in time.

In one embodiment, two example metrics in the second category of heuristics are listed below: 1. The inverse of the Euclidean 2D coordinate distance (using x, y coordinate values for a particular image from a particular camera) between the left ankle-joint of two multi-joint subjects on the floor and the right ankle-joint of the two multi-joint subjects on the floor summed together. The first multi joint subject's ankle joint locations are projected to the camera in which the second multi-joint subject is visible through homographic mapping. 2. The sum of all pairs of joints of inverse of Euclidean 2D coordinate distance between a line and a point, where the line is the epipolar line of a joint of an image from a first camera having a first multi-joint subject in its field of view to a second camera with a second multi joint subject in its field of view and the point is the joint of the second multi-joint subject in the image from the second camera. Third Category of Heuristics

The third category of heuristics include metrics to ascertain similarity between all joints of a proposed multi-joint subject-joint location in the same camera view at the same moment in time. Consider the example embodiment of the shopping store, this category of metrics determines distance between joints of a customer in one frame from one camera.

Fourth Category of Heuristics

The fourth category of heuristics includes metrics to ascertain dissimilarity between proposed multi-joint subject-joint locations. In one embodiment, these metrics are floating point values. Higher values mean two lists of joints are more likely to not be the same multi joint subject. In one embodiment, two example metrics in this category include:

1. The distance between neck joints of two proposed multi-joint subjects.

2. The sum of the distance between pairs of joints between two multi joint subjects.

In one embodiment, various thresholds which can be determined empirically are applied to the above listed metrics as described below:

1. Thresholds to decide when metric values are small enough to consider that a joint belongs to a known multi-joint subject.

2. Thresholds to determine when there are too many potential candidate multi-joint subjects that a joint can belong to with too good of a metric similarity score.

3. Thresholds to determine when collections of joints over time have high enough metric similarity to be considered a new multi-joint subject, previously not present in the real space.

4. Thresholds to determine when a multi-joint subject is no longer in the real space.

5. Thresholds to determine when the tracking engine 110 has made a mistake and has confused two multi-joint subjects.

The tracking engine 110 includes logic to store the sets of joints identified as multi-joint subjects. The logic to identify sets of candidate joints includes logic to determine whether a candidate joint identified in images taken at a particular time corresponds with a member of one of the sets of candidate joints identified as multi-joint subjects in preceding images. In one embodiment, the tracking engine 110 compares the current joint-locations of a multi-joint subject with previously recorded joint-locations of the same multi joint subjects at regular intervals. This comparison allows the tracking engine 110 to update the joint locations of multi-joint subjects in the real space. Additionally, using this, the tracking engine 110 identifies false positives (i.e., falsely identified multi-joint subjects) and removes multi-joint subjects no longer present in the real space.

Consider the example of the shopping store embodiment, in which the tracking engine 110 created a customer (multi-joint subject) at an earlier moment in time, however, after some time, the tracking engine 110 does not have current joint-locations for that particular customer. It means that the customer was incorrectly created. The tracking engine 110 deletes incorrectly generated multi-joint subjects from the subject database 140. In one embodiment, the tracking engine 110 also removes positively identified multi joint subjects from the real space using the above described process. Consider the example of the shopping store, when a customer leaves the shopping store, the tracking engine 110 deletes the corresponding customer record from the subject database 140. In one such embodiment, the tracking engine 110 updates this customer's record in the subject database 140 to indicate that "customer has left the store".

In one embodiment, the tracking engine 110 attempts to identify multi-joint subjects by applying the foot and non-foot heuristics simultaneously. This results in "islands" of connected joints of the multi joint subjects. As the tracking engine 110 processes further arrays of joint data structures along the time and space dimensions, the size of the islands increase. Eventually, the islands of joints merge to other islands of joints forming multi-joint subjects which are then stored in the subject database 140. In one embodiment, the tracking engine 110 maintains a record of unassigned joints for a predetermined period of time. During this time, the tracking engine attempts to assign the unassigned joint to existing multi-joint subjects or create new multi-joint entities from these unassigned joints. The tracking engine 110 discards the unassigned joints after a predetermined period of time. It is understood that, in other embodiments, different heuristics than the ones listed above are used to identify and track multi joint subjects.

In one embodiment, a user interface output device connected to the node 102 hosting the tracking engine 110 displays position of each multi joint subject in the real spaces. In one such embodiment, the display of the output device is refreshed with new locations of the multi-joint subjects at regular intervals.

Multi-Joint Subject Data Structure

The joints of the multi-joint subjects are connected to each other using the metrics described above. In doing so, the tracking engine 110 creates new multi joint subjects and updates the locations of existing multi joint subjects by updating their respective joint locations. FIG. 8 shows the multi-joint subject data structure 800 to store the multi-joint subject. The data structure 800 stores the subject related data as a key-value dictionary. The key is a frame_number and value is another key-value dictionary where key is the camera_id and value is a list of 18 joints (of the multi joint subject) with their locations in the real space. The subject data is stored in the subject database 140. Every new multi-joint subject is also assigned a unique identifier that is used to access the subject's data in the subject database 140.

In one embodiment, the system identifies joints of a multi-joint subject and creates a skeleton of the multi joint subject. The skeleton is projected into the real space indicating the position and orientation of the multi-joint subject in the real space. This is also referred to as "pose estimation" in the field of machine vision. In one embodiment, the system displays orientations and positions of multi joint subjects in the real space on a graphical user interface (GUI). In one embodiment, the image analysis is anonymous, i.e., a unique identifier assigned to a multi-joint subject created through joints analysis does not identify personal identification details (such as names, email addresses, mailing addresses, credit card numbers, bank account numbers, driver's license number, etc.) of any specific multi-joint subject in the real space.

Process Flow of Multi-Joint Subject Tracking

A number of flowcharts illustrating logic are described herein. The logic can be implemented using processors configured as described above programmed using computer programs stored in memory accessible and executable by the processors, and in other configurations, by dedicated logic hardware, including field programmable integrated circuits, and by combinations of dedicated logic hardware and computer programs. With all flowcharts herein, it will be appreciated that many of the steps can be combined, performed in parallel, or performed in a different sequence, without affecting the functions achieved. In some cases, as the reader will appreciate, a rearrangement of steps will achieve the same results only if certain other changes are made as well. In other cases, as the reader will appreciate, a rearrangement of steps will achieve the same results only if certain conditions are satisfied. Furthermore, it will be appreciated that the flow charts herein show only steps that are pertinent to an understanding of the embodiments, and it will be understood that numerous additional steps for accomplishing other functions can be performed before, after and between those shown.

FIG. 9 is a flowchart illustrating process steps for tracking multi-joint subjects. The process starts at step 902. The cameras 114 having field of view in an area of the real space are calibrated in process step 904. Video processes are performed at step 906 by image recognition engines 112a to 112n. In one embodiment, the video process is performed per camera to process batches of image frames received from respective cameras. The output of all video processes from respective image recognition engines 112a to 112n are given as input to a scene process performed by the tracking engine 110 at step 908. The scene process identifies new multi-joint subjects and updates the joint locations of existing multi joint subjects. At step 910, it is checked if there are more image frames to be processed. If there are more image frames, the process continues at step 906, otherwise the process ends at step 914. In one embodiment, FIG. 14 presents an illustration of the video processes and the scene process.

More detailed process steps of the process step "calibrate cameras in real space" 904 are presented in a flowchart in FIG. 10. The calibration process starts at step 1002 by identifying a (0, 0, 0) point for (x, y, z) coordinates of the real space. At step 1004, a first camera with the location (0, 0, 0) in its field of view is calibrated. More details of camera calibration are presented earlier in this application. At step 1006, a next camera with overlapping field of view with the first camera is calibrated. At step 1008, it is checked whether there are more cameras to calibrate. The process is repeated at step 1006 until all cameras 114 are calibrated.

In a next process step 1010, a multi joint subject is introduced in the real space to identify conjugate pairs of corresponding points between cameras with overlapping fields of view. Some details of this process are described above. The process is repeated for every pair of overlapping cameras at step 1012. The process ends if there are no more cameras (step 1014).

A flowchart in FIG. 11 shows more detailed steps of the "video process" step 906. At step 1102, k-contiguously timestamped images per camera are selected as a batch for further processing. In one embodiment, the value of k=6 which is calculated based on available memory for the video process in the network nodes 101a to 101n, respectively hosting image recognition engines 112a-112n. In a next step 1104, the size of images is set to appropriate dimensions. In one embodiment, the images have a width of 1280 pixels, height of 720 pixels and three channels RGB (representing red, green and blue colors). At step 1106, a plurality of trained convolutional neural networks (CNN) process the images and generate arrays of joint data structures per image. The output of the CNNs are arrays of joint data structures per image (step 1108). This output is sent to a scene process at step 1110.

FIG. 12A is a flowchart showing a first part of more detailed steps for "scene process" step 908 in FIG. 9. The scene process combines outputs from multiple video processes at step 1202. At step 1204, it is checked whether a joint data structure identifies a foot joint or a non-foot joint. If the joint data structure is of a foot-joint, homographic mapping is applied to combine the joint data structures corresponding to images from cameras with overlapping fields of view at step 1206. This process identifies candidate foot joints (left and right foot joints). At step 1208 heuristics are applied on candidate foot joints identified in step 1206 to identify sets of candidate foot joints as multi-joint subjects. It is checked at step 1210 whether the set of candidate foot joints belongs to an existing multi-joint subject. If not, a new multi-joint subject is created at step 1212. Otherwise, the existing multi joint subject is updated at step 1214.

A flowchart FIG. 12B illustrates a second part of more detailed steps for the "scene process" step 908. At step 1240, the data structures of non-foot joints are combined from multiple arrays of joint data structures corresponding to images in the sequence of images from cameras with overlapping fields of view. This is performed by mapping corresponding points from a first image from a first camera to a second image from a second camera with overlapping fields of view. Some details of this process are described above. Heuristics are applied at step 1242 to candidate non-foot joints. At step 1246 it is determined whether a candidate non-foot joint belongs to an existing multi-joint subject. If so, the existing multi-joint subject is updated at step 1248. Otherwise, the candidate non-foot joint is processed again at step 1250 after a predetermined time to match it with an existing multi joint subject. At step 1252 it is checked whether the non-foot joint belongs to an existing subject. If true, the multi-joint subject is updated at step 1256. Otherwise, the joint is discarded at step 1254.

In an example embodiment, the processes to identify new multi joint subjects, track multi-joint subjects and eliminate multi-joint subjects (who have left the real space or were incorrectly generated) are implemented as part of an "entity cohesion algorithm" performed by the runtime system (also referred to as the inference system). An entity is a constellation of joints referred to as multi joint subject above. The entity cohesion algorithm identifies entities in the real space and updates locations of the joints in real space to track movement of the entity.

Particular Implementations

In various embodiments, the system for tracking multi joint subjects described above also includes one or more of the following features.

1. Region Proposals

Region proposal is the frame image of hand location from all different cameras covering the person. Region proposal is generated by every camera in the system. It includes empty hands as well as hands carrying store items.

1.1 the "What" CNN Model

Region proposal is important because it is used as input to image classification using a deep learning algorithm. This is called "What CNN" model. It is an in-hand classification model. It classifies the things that are in hands. In-hand image classification is much trickier because parts of the object are occluded by the hand. Smaller items may be occluded up to 90% by the hand. The region for image analysis by What CNN model is intentionally kept small because it is computationally expensive. Each camera has a dedicated GPU. This is performed for every hand image from every camera for every frame. In addition to the above image analysis by What CNN model, a confidence weight is also assigned to that image (one camera, one point in time). The classification algorithm outputs logits over the entire list of stock keeping units (SKUs) to produce a product and service identification code list of the store for n items and one additional for empty hand (n+1).

The scene process now communicates back its results to each video process by sending a key-value dictionary to each video. Here keys are unique joint IDs and values are unique person IDs with which the joint is associated. If no person was found associated with the joint, then it is not included in the dictionary.

Each video process receives the key-value dictionary from the scene process and stores it into a ring buffer that maps frame numbers to the returned dictionary.

Using the returned key-value dictionary, the video selects subsets of the image at each moment in time that are near hands associated with known people. These regions are numpy slices. We also take a similar slice around foreground masks and the raw output feature arrays of the Joints CNN. These combined regions are concatenated together into a single multidimensional numpy array and stored in a data structure that holds the numpy array as well as the person ID the region is associated with and which hand from the person the region came from.

All proposed regions are then fed into FIFO queue. This queue takes in regions and pushes their numpy array into memory on the GPU.

As arrays arrive on the GPU they are fed into a CNN dedicated to classification, referred to as What CNN. The output of this CNN is a flat array of floats of size N+1, where N is the number of unique SKUs in the store, and the final class represents the nil class, or empty hand. The floats in this array are referred to as logits.

The results of What CNN are stored back into the region data structure.

All regions for a moment in time are then sent from each video process back to the scene process.

The scene process receives all regions from all videos at a moment in time and stores the results in a key-value dictionary, where the key is a person ID and the value is a key-value dictionary, where the key is a camera ID and the value is a region's logits.

This aggregated data structure is then stored in a ring buffer that maps frame numbers to the aggregated structure for each moment in time. FIG. 15 presents an illustration of the "What CNN" model.

1.2 The "When" CNN Model

The images from different cameras processed by the What CNN model are combined over a period of time (multiple cameras over a period of time). An additional input to this model is hand location in 3D space, triangulated from multiple cameras. Another input to this algorithm is the distance of a hand from a planogram of the store. The planogram will identify if the hand is close to a shelf containing a particular item (e.g. cheerios boxes). Another input to this algorithm is the foot location on the store.

In addition to object classification using SKU, the second classification model uses time series analysis to determine whether the object was picked up from the shelf or placed on the shelf. The images are analyzed over a period of time to make the determination of whether the object that was in the hand in earlier image frames has been put back in the shelf or has been picked up from the shelf.

For a one second time (30 frames per second) period and three cameras, the system will have 90 classifications outputs for the same hand plus confidences. This combined image analysis dramatically increases the probability of correctly identifying the object in the hand. The analysis over time improves the quality of output despite some very low confidence level outputs of individual frames. This step can take the output confidence from for example, 80% accuracy to 95% accuracy.

This model also includes output from the shelf model as its input to identify what object this person has picked.

The scene process waits for 30 or more aggregated structures to accumulate, representing at least a second of real time, and then performs a further analysis to reduce the aggregated structure down to a single integer for each person ID-hand pair, where the integer is a unique ID representing a SKU in the store. For a moment in time this information is stored in a key-value dictionary where keys are person ID-hand pairs, and values are the SKU integer. This dictionary is stored over time in a ring buffer that maps frame numbers to each dictionary for that moment in time.

An additional analysis is then performed looking at how this dictionary changes over time in order to identify at what moments a person grabs or takes something and what it is they grab or take. This model (When CNN) emits SKU logits as well as logits for each Boolean question: was something taken? was something placed?

The output of When CNN is stored in a ring buffer that maps frame numbers to a key-value dictionary where keys are person IDs and values are the extended logits emitted by When CNN.

A further collection of heuristics is then run on the stored results of both When CNN and the stored joint locations of people, as well as a precomputed map of items on the store shelf. This collection of heuristics determines where takes and puts result in items being added to or removed from. For each take/put the heuristics determine if the take or put was from or to a shelf, from or to a basket, or from or to a person. The output is an inventory for each person, stored as an array where the array value at a SKU's index is the number of those SKUs a person has.

As a shopper nears the exit of a store the system can send the inventory list to the shopper's phone. The phone then displays the user's inventory and asks for confirmation to charge their stored credit card information. If the user accepts, their credit card will be charged. If they do not have a credit card known in the system, they will be asked to provide credit card information.

Alternatively, the shopper may also approach an in-store kiosk. The system identifies when the shopper is near the kiosk and will send a message to the kiosk to display the inventory of the shopper. The kiosk asks the shopper to accept the charges for the inventory. If the shopper accepts, they may then swipe their credit card or insert cash to pay. FIG. 16 presents an illustration of the "When CNN" model for region proposals.

2. Misplaced Items

This feature identifies misplaced items when they are placed back by a person on a random shelf. This causes problems in object identification because the foot and hand location with respect to the planogram will be incorrect. Therefore, the system builds up a modified planogram over time. Based on prior time series analysis, the system is able to determine, if a person has placed an item back in the shelf. Next time, when an object is picked up from that shelf location, the system knows that there is at least one misplaced item in that hand location. Correspondingly, the algorithm will have some confidence that the person can pick up the misplaced item from that shelf. If the misplaced item is picked up from the shelf, the system subtracts that item from that location and therefore, the shelf does not have that item anymore. The system can also inform a clerk to about a misplaced item on an app so that the clerk can move that item to its correct shelf.

3. Semantic Diffing (Shelf Model)

Background subtraction algorithm to identify changes to items (items removed or placed) on the shelves. This is based on changes at the pixel level. If there are persons in front of the shelf, then the algorithm stops so that it does not take into account pixel changes due to presence of persons. Background subtraction is a noisy process. Therefore, a cross camera analysis is conducted. If enough cameras agree that there is a "semantically meaningful" change in the shelf, then the system records that there is a change in that part of the shelf.

Next step is to identify whether that change is a "put" or a "get" change. For this, the time series analysis of the second classification model is used. A region proposal for that particular part of the shelf is generated and passed through the deep learning algorithm. This is easier than in-hand image analysis because the object is not occluded inside a hand. A fourth input is given to the algorithm in addition to the three typical RGB inputs. The fourth channel is the background information. The output of the shelf or semantic diffing is input again to the second classification model (time-series analysis model).

Semantic diffing includes the following steps: 1. Images from a camera are compared to earlier images from the same camera. 2. Each corresponding pixel between the two images is compared via a Euclidean distance in RGB space. 3. Distances above a certain threshold are marked, resulting in a new image of just marked pixels. 4. A collection of image morphology filters are used to remove noise from the marked image. 5. We then search for large collections of marked pixels and form bounding boxes around them. 6. For each bounding box we then look at the original pixels in the two images to get two image snapshots. 7. These two image snapshots are then pushed into a CNN trained to classify whether the image region represents an item being taken and an item being placed and what item it is.

4. Store Audit

An inventory of each shelf is maintained by the system. It is updated as items are picked up by the customers. At any point in time, the system is able to generate an audit of store inventory.

5. Multiple Items in Hand

Different images are used for multiple items. Two items in the hand are treated differently as compared to one. Some algorithms can predict only an item but not multiple numbers of an item. Therefore, the CNNs are trained so the algorithms for "two" quantities of the items can be executed separately from a single item in the hand.

6. Data Collection System

Predefined shopping scripts are used to collect good quality data of images. These images are used for training of algorithms.

6.1 Shopping Scripts

Data collection includes the following steps: 1. A script is automatically generated telling a human actor what actions to take. 2. These actions are randomly sampled from a collection of actions including: grab item X, place item X, hold item X for Y seconds. 3. While performing these actions the actors move and orient themselves in as many ways as possible while still succeeding at the given action. 4. During the sequences of actions a collection of cameras record the actors from many perspectives. 5. After the actors have finished the script, the camera videos are bundled together and saved along with the original script. 6. The script serves as an input label to machine learning models (such as the CNNs) that train on the videos of actors.

7. Product Line

The system and parts thereof can be used for cashier-less checkout, supported by the following apps.

7.1 Store App

The Store App has several main capabilities; providing data analytic visualizations, supporting loss prevention, and providing a platform to assist customers by showing the retailer where people are in the store and what merchandise they have collected. Permission levels and app access to employees can be dictated at the retailer's discretion.

7.1.1 Standard Analytics

Data is collected by the platform and can be used in a variety of ways. 1. The derivative data is used to perform various kinds of analytics on stores, the shopping experiences they provide, and customer interactions with products, environment, and other people. a. The data is stored and used in the background to perform analyses of the stores and customer interactions. The Store App will display some of the visualizations of this data to retailers. Other data is stored and queried when the data point is desired.

2. Heat Maps:

The platform visualizes a retailer's floor plan, shelf layouts, and other store environments with overlays showing levels of various kinds of activity.

1. Examples

1. Maps for places people walk past, but don't handle any of the products.

2. Maps for where on the floor people stand when interacting with products.

3. Misplaced Items:

The platform tracks all of a store's SKUs. When an item gets put in the incorrect place, the platform will know where that item is and build a log. At some threshold, or immediately, store employees may be alerted to the misplaced item. Alternatively, the staff may access the Misplaced Item Map in the Store App. When convenient, staff can then quickly locate and correct misplaced items.

7.1.2 Standard Assist The Store App will display a store's floor plan. It will display a graphic to represent each person in the store. When the graphic is selected, via touch, click, or other means, pertinent information to store employees will be displayed. For example: Shopping Cart items (items they have collected) will appear in a list. If the platform has a confidence level below a predetermined threshold for a particular item(s) and for a period of time that is in a person's possession (Shopping Cart), their graphic (currently a dot) will indicate the difference. The app uses a color change. Green indicates high confidence and yellow/orange indicates lower confidence. Store employees with the Store App can be notified of the lower confidence. They can go make sure the customer's Shopping Cart is accurate. Through the Store App, employees of the retailer adjust a customer's Shopping Cart items (add or delete).

7.1.3 Standard LP If a shopper is using the Shopper App, they simply exit the store and are charged. However, if they are not, they will need to use the Guest App to pay for the items in their Shopping Cart. If the shopper bypasses the Guest App on their way out of the store, their graphic indicates they must be approached before exiting. The App uses a change of color to red. Staff also receive a notification of potential loss. Through the Store App, employees of the retailer adjust a customer's Shopping Cart items (add or delete).

7.2 Non-Store App

The following analytic features represent additional capabilities of the platform.

7.2.1 Standard Analytics

1. Product Interactions:

Granular breakdown of product interactions such as:

a. Interaction time to conversion ratios for each product. b. AB comparisons (color, style, etc.). Some of the smaller products on display have multiple options like colors, flavors, etc. Is the rose gold handled more than the silver? Do blue cans attract more interactions than red ones? 2. Directional Impressions: Know the difference between a location based impression and where the shopper's gaze is. If they are looking at a product that is 15 feet away, for 20 seconds, the impression should not count for where they are, but for where they are looking. 3. Customer Recognition: Remember repeat shoppers and their associated email address (collected in a variety of ways by the retailer) and shopping profiles. 4. Group Dynamics: Decide when a shopper is watching someone else interact with a product. Answer whether that person interacts with the product afterwards? Did those people enter the store together, or are they likely strangers? Do individuals or groups of people spend more time in the store? 5. Customer Touchback: Offer customers targeted information, post store experience. This feature may have a slightly different implementation with each retailer depending on particular practices and policies. It may require integration and/or development from the retailer to adopt the feature. Shoppers would be asked if they wished to receive notifications about products they might be interested in. That step may be integrated with the store's method of collecting emails. After leaving the store, a customer may receive an email with the products they spent time with at the store. An interaction threshold for duration, touch, and sight (direction impressions) will be decided. When the threshold is met, the products would make it to her list and be sent to her soon after leaving the store.

Additionally, or alternatively, the shopper could be sent an email a period of time later that offered product(s) on sale or other special information. These products will be items they expressed interest in, but did not purchase.

7.3 Guest App

The Shopper App to automatically checks people out when they exit the store. However, the platform does not require shoppers to have or use the Shopper App to use the store.

When a shopper/person does not have or use the Shopper App they walk up to a kiosk (an iPad/tablet or other screen) or they walk up to a pre-installed self-checkout machine. The display, integrated with the platform, will automatically display the customer's Shopping Cart.

The shopper will have the opportunity to review what is displayed. If they agree with the information on the display they can either enter cash into the machine (if that capability is built into the hardware (e.g. self-checkout machines)) or they swipe their credit or debit card. They can then exit the store.

If they disagree with the display, store staff is notified by their selection to challenge through a touch screen, button, or other means. (see the Store Assist under the Store App)

7.4 Shopper App

Through use of an app, the Shopper App, the customer can exit the store with merchandise and automatically be charged and given a digital receipt. The shopper must open their app at any time while within the store's shopping area. The platform will recognize a unique image that is displayed on the shopper's device. The platform will tie them to their account (Customer Association), and regardless if they keep the app open or not, will be able to remember who they are throughout their time in the store's shopping area.

As the shopper gathers items, the Shopper App will display the items in shopper's Shopping Cart. If the shopper wishes, they can view product information about each item they pick up (i.e. gets added to their shopping cart). Product information is stored either with the store's systems or added to platform. The ability for updating that information, such as offering product sales or displaying prices, is an option the retailer can request/purchase or develop.

When a shopper puts an item down, it is removed from their Shopping Cart on the backend and on the Shopper App.

If the Shopper App is opened, and then closed after Customer Association is completed, the Platform will maintain the shopper's Shopping Cart and correctly charge them once they exit the store.

The Shopper App also has mapping information on its development roadmap. It can tell a customer where to find items in the store if the customer requests the information by typing in the item being sought. At a later date, we will take a shopper's shopping list (entered into the app manually or through other intelligent systems) and display the fastest route through the store to collect all the desired items. Other filters, such as `Bagging Preference` may be added. The Bagging Preference filter allows a shopper to not follow the fastest route, but to gather sturdier items first, then more fragile items later.

8. Types of Customers

Member customer--First type of customer logs into the system using an app. The customer is prompted with a picture and when s/he clicks on it, the system links that to the internal id of that customer. If the customer has an account, then the account is charged automatically when the customer walks out of the store. This is the membership based store.

Guest customer--Not every store will have membership, or customers may not have a smartphone or a credit card. This type of customer will walk up to a kiosk. The kiosk will display the items that the customer has and will ask the customer to put in the money. The kiosk will already know about all the items that the customer has bought. For this type of customer, the system is able to identify if the customer has not paid for the items in the shopping card, and prompt the checker at the door, before the customer reaches there, to let the checker know about unpaid items. The system can also prompt for one item that has not been paid for, or the system having low confidence about one item. This is referred to as predictive pathfinding.

The system assigns color codes (green and yellow) to the customers walking in the store based on the confidence level. The green color coded customers are either logged into the system or the system has a high confidence about them. Yellow color coded customers have one or more items that are not predicted with high confidence. A clerk can look at the yellow dots and click on them to identify problem items, walk up to the customer and fix the problem.

9. Analytics

A host of analytics information is gathered about the customer such as how much time a customer spent in front of a particular shelf. Additionally, the system tracks the location where a customer is looking (impression on the system), and the items which a customer picked and put back on the shelf. Such analytics are currently available in ecommerce but not available in retail stores.

10. Functional Modules

The following is a list of functional modules: 1. System capturing array of images in store using synchronized cameras. 2. System to identify joints in images, and sets of joints of individual persons. 3. System to create new persons using joint sets. 4. System to delete ghost persons using joint sets. 5. System to track individual persons over time by tracking joint sets. 6. System to generate region proposals for each person present in the store indicating the SKU number of item in the hand (What CNN). 7. System to perform get/put analysis for region proposals indicating if the item in the hand was picked up or placed onto the shelf (When CNN). 8. System to generate inventory array per person using region proposals and get/put analysis (Outputs of When CNN combined with heuristics, stored joint locations of persons, and precomputed map of items on the store shelves). 9. System to identify, track and update locations of misplaced items on shelves. 10. System to track changes (get/put) to items on shelves using pixel-based analysis. 11. System to perform inventory audit of store. 12. System to identify multiple items in hands. 13. System to collect item image data from store using shopping scripts. 14. System to perform checkout and collect payment from member customers. 15. System to perform checkout and collect payment from guest customers. 16. System to perform loss-prevention by identifying un-paid items in a cart. 17. System to track customers using color codes to help clerks identify incorrectly identified items in a customer's cart. 18. System to generate customer shopping analytics including location-based impressions, directional impressions, AB analysis, customer recognition, group dynamics etc. 19. System to generate targeted customer touchback using shopping analytics. 20. System to generate heat map overlays of the store to visualize different activities.

The technology described herein can support Cashier-free Checkout. Go to Store. Get Things. Leave.

Cashier-free Checkout is a pure machine vision and deep learning based system. Shoppers skip the line and get what they want faster and easier. No RFID tags. No changes to store's backend systems. Can be integrated with 3.sup.rd party Point of Sale and Inventory Management systems.

Real time 30 FPS analysis of every video feed.

On-premise, cutting edge GPU cluster.

Recognizes shoppers and the items they interact with.

No internet dependencies in example embodiment.

Multiple state-of-the-art deep learning models, including proprietary custom algorithms, to resolve gaps in machine vision technology for the first time.

Techniques & Capabilities include the following:

1. Standard Cognition's machine learning pipeline solves: a) People Detection. b) Entity Tracking. c) Multicamera Person Agreement. d) Hand Detection. e) Item Classification. f) Item Ownership Resolution.

Combining these techniques, we can: 1. Keep track of all people throughout their shopping experience in real time. 2. Know what shoppers have in their hand, where they stand, and what items they place back. 3. Know which direction shoppers are facing and for how long. 4. Recognize misplaced items and perform 24/7 Visual Merchandizing Audits.

Can detect exactly what a shopper has in their hand and in their basket.

Learning Your Store:

Custom neural networks trained on specific stores and items. Training data is reusable across all store locations.

Standard Deployment:

Ceiling cameras must be installed with double coverage of all areas of the store. Requires between 2 and 6 cameras for a typical aisle.

An on-premise GPU cluster can fit into one or two server racks in a back office.

Example systems can be integrated with or include Point of Sale and Inventory Management systems.

A first system, method and computer program product for capturing arrays of images in stores using synchronized cameras.

A second system, method and computer program product to identify joints in images, and sets of joints of individual persons.

A third system, method and computer program product to create new persons using joint sets.

A fourth system, method and computer program product to delete ghost persons using joint sets.

A fifth system, method and computer program product to track individual persons over time by tracking joint sets.

A sixth system, method and computer program product to generate region proposals for each person present in the store indicating the SKU number of item in the hand (What CNN).

A seventh system, method and computer program product to perform get/put analysis for region proposals indicating if the item in the hand was picked up or placed onto the shelf (When CNN).

An eighth system, method and computer program product to generate an inventory array per person using region proposals and get/put analysis (e.g. Outputs of When CNN combined with heuristics, stored joint locations of persons, and precomputed map of items on the store shelves).

A ninth system, method and computer program product to identify, track and update locations of misplaced items on shelves.

A tenth system, method and computer program product to track changes (get/put) to items on shelves using pixel-based analysis.

An eleventh system, method and computer program product to perform inventory audit of store.

An twelfth system, method and computer program product to identify multiple items in hands.

A thirteenth system, method and computer program product to collect item image data from store using shopping scripts.

A fourteenth system, method and computer program product to perform checkout and collect payment from member customers.

A fifteenth system, method and computer program product to perform checkout and collect payment from guest customers.

A sixteenth system, method and computer program product to perform loss-prevention by identifying un-paid items in a cart.

A seventeenth system, method and computer program product to track customers using for example color codes to help clerks identify incorrectly identified items in a customer's cart.

An eighteenth system, method and computer program product to generate customer shopping analytics including one or more of location-based impressions, directional impressions, AB analysis, customer recognition, group dynamics etc.

A nineteenth system, method and computer program product to generate targeted customer touchback using shopping analytics.

A twentieth system, method and computer program product to generate heat map overlays of the store to visualize different activities.

A twenty first system, method and computer program for Hand Detection.

A twenty second system, method and computer program for Item Classification.

A twenty third system, method and computer program for Item Ownership Resolution.

A twenty fourth system, method and computer program for Item People Detection.

A twenty fifth system, method and computer program for Item Entity Tracking.

A twenty sixth method and computer program for Item Multicamera Person Agreement.

A twenty seventh system, method and computer program product for cashier-less checkout substantially as described herein.

Combinations of any of systems 1-26 with any other system or systems in systems 1-26 listed above.

* * * * *

File A Patent Application

  • Protect your idea -- Don't let someone else file first. Learn more.

  • 3 Easy Steps -- Complete Form, application Review, and File. See our process.

  • Attorney Review -- Have your application reviewed by a Patent Attorney. See what's included.