System and method for detecting and analyzing a queue

• US 5,953,055 A
• Filed: 03/04/1997
• Issued: 09/14/1999
• Est. Priority Date: 08/08/1996
• Status: Expired due to Fees

• Current Assignee: Nomi Corp.
• Original Assignee: NCR Corporation
• Inventors: Huang, Jianzhong, Florencio, Dinei A. F.
• Primary Examiner(s): Chin, Tommy P.
• Assistant Examiner(s): PHILIPPE, GIMS S
• Application Number:
  US08/811,326
• Time in Patent Office: 924 Days
• Field of Search: 348/150, 348/152, 348/155, 348/142, 348/159, 348/147, 348/218, 348/42, 348/139, 348/143, 382/100, 382/106, 382/154, 359/458, 340/917, 340/934, 340/937
• US Class Current: 348/155
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 2207/20021 Dividing image into blocks, subimages or windows
• CPC Class Codes: G06T 2207/30196 Human being; Person
• CPC Class Codes: G06T 2207/30232 Surveillance
• CPC Class Codes: G06T 7/0002 Inspection of images, e.g. flaw detection
• CPC Class Codes: G06T 7/254 involving subtraction of images
• CPC Class Codes: G06V 20/53 Recognition of crowd images, e.g. recognition of crowd congestion
• CPC Class Codes: G06V 40/161 Detection; Localisation; Normalisation
• CPC Class Codes: G07C 11/00 Arrangements, systems or apparatus for checking, e.g. the occurrence of a condition, not provided for elsewhere
• CPC Class Codes: G07C 2011/04 related to queuing systems
• CPC Class Codes: G07C 9/00 Individual registration on entry or exit
• CPC Class Codes: H04N 7/188 Capturing isolated or intermittent images triggered by the occurrence of a predetermined event, e.g. an object reaching a predetermined position signal generation from motion picture films H04N5/253

Abstract

A system and method are provided for detecting, collecting information about, and analyzing a queue. A video camera is positioned to view the queue, and a sequence of video images from the camera may be processed in order to perform the functionality of the present invention. The present invention may be implemented at checkout lanes in a retail establishment, in a bank, at customer service desks, at self-service kiosks, at banks, or any other location where a queue (line) of people or other objects may form. After detecting the queue, the present invention may collect multi-dimensional information regarding the queue, including the number of people, etc., in the queue, the average service time for each person in the queue, as well as various other types of information regarding the queue. The present invention may thereafter analyze the collected information in various ways, based upon various criteria. For example, a retailer may use the analyzed information to minimize service time for people in a checkout line, in a way which makes economic sense.

Claims

1. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) dividing the digital video image into a plurality of slots, each slot approximately the size of a person within the digital video image;

(2) generating an image difference for each slot;

(3) determining from the image difference whether a slot is occupied by a person; and

(4) determining whether a person overlaps adjacent slots by

(4a) determining whether either adjacent slot is occupied by a person,

(4b) defining an overlapping slot comprising adjacent halves of each of the adjacent slots if it is determined that neither adjacent slot is occupied by a person; and

(4c) detecting whether the overlapping slot is occupied by a person.

2. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) dividing the digital video image into a plurality of slots, each slot approximately the size of d person within the digital video image;

(2) generating an image difference for each slot;

(3) determining from the image difference whether a slot is occupied by a person;

(4) determining whether a person overlaps adjacent slots; and

(5) updating the background image associated with the video image by

(a) monitoring the image difference between the video frame and the background frame;

(b) counting the number of pixels that exceed a preselected threshold; and

(c) capturing a new background image if the count is less than a fixed percentage of the number of pixels for a period longer than a given time threshold.

3. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) dividing the digital video image into a plurality of slots, each slot approximately the size of a person within the digital video image;

(2) generating an image difference for each slot;

(3) determining from the image difference whether a slot is occupied by a person;

(4) determining whether a person overlaps adjacent slots; and

(5) updating the background image associated with the video image by

(a) monitoring the image difference between the video frame and the background frame;

(b) counting the number of pixels that exceed a preselected threshold; and

(c) updating the background image by adding or subtracting a pre-defined fixed step factor to the current background if the count is less than a fixed percentage of the number of pixels for a period longer than a given time threshold.

4. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image,

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) dividing the digital video image into a plurality of slots, each slot approximately the size of a person within the digital video image;

(2) generating an image difference for each slot

(3) determining from the image difference whether a slot is occupied by a person;

(4) determining whether a person overlaps adjacent slots; and

(5) updating the background image associated with the video image for a given slot by adding or subtracting a pre-defined fixed step factor to the current background upon the occurrence of any of the following three conditions;

(a) the slot is empty;

(b) no motion has been detected in the slot for a period exceeding a predefined time threshold;

or

(c) it is taking too long for either (a) or (b) to take place.

5. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interests the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) extracting a region of interest from the video image;

(2) generating an image difference by subtracting the value of each pixel in a background image associated with the extracted region of interest from its associated pixel in the extracted region of interest, and assigning a value of 1 for each difference that exceeds or is equal to a difference threshold and assigning a value of 0 for each difference that is less than the difference threshold;

(3) detecting the presence of edges in the region of interest by computing a gradient between adjacent pixels and determining whether the gradient exceeds an edge difference threshold;

(4) setting all detected edges to 0;

(5) performing a region labeling operation on the image difference in order to group adjacent pixels with a value of 1 into objects;

(6) counting the number of objects to determine the number of persons in the region of interest.

6. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) extracting a region of interest from the video image;

(2) generating an image difference by subtracting the value of each pixel in a background image associated with the extracted region of interest from its associated pixel in the extracted region of interest, and assigning a value of 1 for each difference that exceeds or is equal to a difference threshold and assigning a value of 0 for each difference that is less than the difference threshold;

(3) detecting the presence of edges in the region of interest;

(4) setting all detected edges to 0;

(5) performing a region labeling operation on the image difference in order to group adjacent pixels with a value of 1 into objects;

(6) defining a pixel distance as a system parameter;

(7) grouping as a single object those regions that are separated by less than the defined pixel distance; and

(8) counting the number of objects to determine the number of persons in the region of interest.

7. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) extracting a region of interest from the video image;

(2) generating an image difference by subtracting the value of each pixel in a background image associated with the extracted region of interest from its associated pixel in the extracted region of interest, and assigning a value of 1 for each difference that exceeds or is equal to a difference threshold and assigning a value of 0 for each difference that is less than the difference threshold;

(3) detecting the presence of edges in the region of interest;

(4) setting all detected edges to 0;

(5) performing a region labeling operation on the image difference in order to group adjacent pixels with a value of 1 into objects;

(6) determining the pixel size of each grouped object;

(7) filtering the grouped objects by discarding objects that are too small to be a person; and

(8) counting the number of objects to determine the number of persons in the region of interest.

8. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber for converting the video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) extracting a region of interest from the video image;

(2) generating an image difference by subtracting the value of each pixel in a background image associated with the extracted region of interest from its associated pixel in the extracted region of interest, and assigning a value of 1 for each difference that exceeds or is equal to a difference threshold and assigning a value of 1 for each difference that is less than the difference threshold;

(3) detecting the presence of edges in the region of interest;

(4) setting all detected edges to 0;

(5) performing a region labeling operation on the image difference in order to group adjacent pixels with a value of 1 into objects;

(6) counting the number of objects to determine the number of persons in the region of interest;

(7) dividing the region of interest into several small slots; and

(8) updating the background image associated with the video image.

9. A system for detecting persons standing in a queue, comprising:

(a) a video camera positioned to view a selected area of interest, the video camera providing a video signal output;

(b) a frame grabber For converting thc video signal output into a digital video image;

(c) a processing system for analyzing the digital video image, the processing system performing the following steps;

(1) extracting a region of interest from the video image;

(2) generating an image difference by subtracting the value of each pixel in a background image associated with the extracted region of interest from its associated pixel in the extracted region of interest, and assigning a value of 1 for each difference that exceeds or is equal to a difference threshold and assigning a value of 0 for each difference that is less than the difference threshold;

(3) detecting the presence of edges in the region of interest;

(4) setting all detected edges to 0;

(5) performing a region labeling operation on the image difference in order to group adjacent pixels with a value of 1 into objects;

(6) counting the number of objects to determine the number of persons in the region of interest;

(7) updating the background image associated with the video image as follows;

(a) monitoring the time at which each object background area is updated;

(b) updating each object background area whenever the time interval between the current time and the last background update time exceeds a predetermined time threshold;

(c) calculating the absolute value of the frame difference between the current frame and the previous frame for each segmented object area;

(d) counting the number of pixels that have an absolute frame difference value greater than a predetermined amplitude threshold of frame difference within the object area;

(e) using a larger update factor to update an object background area if the percentage of pixels having an absolute frame difference value greater than the predetermined amplitude threshold of frame difference within the object area exceeds a given object percentage;

(f) using a smaller update factor to update an object background area if the percentage of pixels having an absolute frame difference value greater than the predetermined amplitude threshold of frame difference within the object area is less than a given object percentage.