Stereo vision system for counting items in a queue

Abstract

A number of items present in a substantially linear queue are counted by examining two images of a scene including the queue that are taken from vantage points offset relative to each other. Depth information for portions of the scene is obtained by correlating equal sized patches in the images at a predetermined number of offsets, since closer objects will require more of an offset to align one image relative to the other than objects further away from video cameras creating the two images. A match score is determined at each offset. The best offset and the number of offsets to achieve it are stored for each patch. A plot is then created for offsets versus the number of patches at each offset having the best match. Peaks in the plot indicate the number of objects in the queue.

I claim: 
     
       1. A method for counting a plurality of objects currently present in a substantially linear queue, comprising: obtaining a stereo image of a scene including said substantially linear queue from a vantage point area in close proximity to one end of said substantially linear queue, wherein said stereo image comprises a first image and a second image, each of said plurality of objects in said first image being shifted relative to said second image;   obtaining depth information from said stereo image for portions of said scene relative to said vantage point, comprising correlating patches in said first image with patches in said second image; and   interpreting said depth information to determine areas of said stereo image substantially corresponding to a given depth range, each of said plurality of objects corresponding to a particular determined area, wherein said step of interpreting comprises: creating a depth map for said correlated patches,   interpreting said depth map to identify one or more regions corresponding to said given depth range, each of said plurality of objects corresponding to one of said one or more regions, and   filtering out said depth information for objects in said scene other than said plurality of objects.     
     
     
       2. The method of claim 1, wherein said step of creating a depth map comprises creating a plot of depth frequency for said correlated patches, and wherein said step of interpreting said depth map comprises determining relative peaks in said plot, each of said plurality of objects corresponding to one of said relative peaks. 
     
     
       3. The method of claim 2, wherein said step of filtering comprises: storing reference depth information for said scene without said plurality of objects therein; and   eliminating relative peaks corresponding to said reference depth information.   
     
     
       4. The method of claim 1 wherein said step of filtering comprises filtering out said depth information corresponding to objects in said scene beyond a predetermined depth. 
     
     
       5. The method of claim 4 wherein said step of filtering comprises filtering out said depth information corresponding to objects in said queue beyond said predetermined depth when said depth information indicates an absence of said plurality of objects in a depth range of said substantially linear queue between said one end and said predetermined depth. 
     
     
       6. A method for counting a plurality of objects currently present in a substantially linear queue, comprising: obtaining a stereo image of a scene including said substantially linear queue from a vantage point area in close proximity to one end of said substantially linear queue, comprising obtaining said stereo image from a pair of video cameras, said stereo image comprising a first image and a second image, wherein said pair of video cameras are separated such that each of said plurality of objects in said first image appears at an offset relative to said second image, wherein said pair of video cameras are parallel such that said offset is horizontal, wherein each said image comprises pixels arranged in rows and columns, and wherein said separation of said cameras is a function of a predetermined maximum length for said substantially linear queue, an expected spacing between each of said plurality of objects, a common field of view for each of said pair of video cameras and a number of pixels in a row of said stereo image;   obtaining depth information from said stereo image for portion of said scene relative said vantage point; and   interpreting said depth information to determine areas of said stereo image substantially corresponding to a given depth range, each of said plurality of objects corresponding to a particular determined area.   
     
     
       7. The method of claim 6 wherein said separation is obtained from the following equation:   s=(F*d*(d-δ))/(p*δ),     wherein:   s=said separation of said cameras, in a given linear unit;   F=said common field of view, in radians;   d=said predetermined maximum length, in said given linear unit;   δ=said expected spacing, in said given linear unit; and   p=said number of pixels.   
     
     
       8. A method for counting a plurality of objects currently present in a substantially linear queue, comprising: (a) obtaining a stereo image of a scene including said substantially linear queue from a vantage point area in close proximity to one end of said substantially linear queue, wherein said stereo image comprises a first image and a second image offset from said first image;   (b) initializing a shift counter for counting a number of shifts of said first image relative to said second image;   (c) correlating a patch of predetermined size from said first image with a patch of said predetermined size from said second image to determine a correlation indicator therefor;   (d) storing said determined correlation indicator of step (c) as a maximum indicator for said patch from said first image and storing said initialized shift counter as a corresponding shift indicator for said maximum indicator;   (e) shifting said first image relative to said second image;   (f) incrementing said shift counter;   (g) correlating said patch from said first image with a different patch of said predetermined size from said second image to determine a correlation indicator therefor;   (h) comparing said determined correlation indicator of step (g) with said maximum indicator and replacing both said maximum indicator with said determined correlation indicator of step (g) and said corresponding shift number with said incremented shift counter if said determined correlation indicator of step (g) indicates a greater correlation than said maximum indicator;   (i) repeating steps (e) through (h) for a predetermined number of shifts;   (j) repeating steps (b) through (i) for a predetermined number of different patches from said first image;   (k) creating a plot of depth frequency information, said plot plotting for each possible shift counter number a match indicator indicating a number of maximum indicators with a corresponding shift number equal thereto; and   (l) determining relative peaks in said plot, each of said plurality of objects corresponding to a particular relative peak.   
     
     
       9. The method of claim 8 wherein step (k) comprises thresholding said plot at a predetermined minimum match indicator. 
     
     
       10. The method of claim 8 wherein said plurality of objects comprises a plurality of people. 
     
     
       11. The method of claim 10 wherein step (l) comprises determining an elongated relative peak corresponding to more than one of said plurality of people. 
     
     
       12. The method of claim 10 wherein step (k) comprises filtering out said depth frequency information corresponding to objects in said scene other than said plurality of people. 
     
     
       13. The method of claim 12 wherein said step of filtering comprises: storing reference depth frequency information for said scene without said plurality of people therein; and   eliminating relative peaks from said plot corresponding to said reference depth frequency information.   
     
     
       14. The method of claim 12, wherein said step of filtering comprises eliminating relative peaks in said plot corresponding to people beyond a predetermined depth. 
     
     
       15. The method of claim 14, wherein said step of filtering comprises eliminating relative peaks corresponding to people beyond a predetermined depth when no relative peaks indicate a person present within a depth range of said substantially linear queue between said one end and said predetermined depth. 
     
     
       16. The method of claim 10 wherein said vantage point area is angled relative to said substantially linear queue and in close proximity to an average human eye level. 
     
     
       17. The method of claim 8 wherein step (a) comprises obtaining said first image from a first video camera and said second image from a second video camera parallel with and separated from said first video camera by a separation distance. 
     
     
       18. The method of claim 17, wherein each said image comprises pixels arranged in rows and columns, and wherein said separation distance is a function of a predetermined maximum length for said substantially linear queue, an expected spacing between each of said plurality of objects, a common field of view for each of said pair of video cameras and a number of pixels in a row of said stereo image. 
     
     
       19. The method of claim 18, wherein said separation distance is obtained from the following equation:   s=(F*d*(d-δ))/(p*δ),     wherein:   s=said separation of said cameras, in a given linear unit;   F=said common field of view, in radians;   d=said predetermined maximum length, in said given linear unit;   δ=said expected spacing, in said given linear unit; and   p=said number of pixels.   
     
     
       20. The method of claim 8, wherein each said image comprises a plurality of pixels arranged in rows and columns, wherein each pixel has a brightness value associated therewith and wherein said correlation indicator is a function of an average brightness for each said patch, a standard deviation for brightness values for each said patch and an average brightness for a theoretical patch of said predetermined size, each pixel in said theoretical patch having a brightness equal to a brightness of a corresponding pixel in each said patch multiplied together. 
     
     
       21. The method of claim 20, wherein each pixel has an X cartesian coordinate and a Y cartesian coordinate, wherein each said patch comprises an h by v pixel patch centered on a pixel with coordinates x, y, said correlation indicator being a score obtained according to the following equation: ##EQU2## 
     
     
       22. Apparatus for counting a plurality of objects currently present in a substantially linear queue, comprising: means for obtaining a stereo image comprising a pair of images of a scene including said substantially linear queue;   means for correlating patches of said pair of images to determine depths for corresponding areas of said scene relative to said obtaining means;   means for providing depth frequency information for said correlated patches from which said plurality of objects is counted; and   means for filtering out said depth frequency information corresponding to portions of said scene other than said plurality of objects.   
     
     
       23. The apparatus of claim 22, wherein said filtering means comprises: means for storing reference depth frequency information corresponding to said scene without said plurality of objects therein; and   means for comparing said provided depth frequency information to said reference depth frequency information.   
     
     
       24. The apparatus of claim 22 wherein said filtering means comprises means for filtering out depth frequency information corresponding to objects in said scene beyond a predetermined depth. 
     
     
       25. The apparatus of claim 24, wherein said obtaining means is located in close proximity to one end of said linear queue, and wherein said filtering means comprises means for filtering out depth frequency information corresponding to objects in said queue beyond said predetermined depth when said depth frequency information indicates an absence of said plurality of objects in a depth range of said substantially linear queue between said one end and said predetermined depth. 
     
     
       26. Apparatus for counting a plurality of objects currently present in a substantially linear queue, comprising: means for obtaining a stereo image of a scene including said substantially linear queue from a vantage point area in close proximity to one end of said substantially linear queue, wherein said stereo image comprises a first image and a second image, each of said plurality of objects in said first image being shifted relative to said second image;   means for obtaining depth information from said stereo image for portions of said scene relative to said vantage point, comprising means for correlating patches in said first image with patches in said second image; and   means for interpreting said depth information to determine areas of said stereo image substantially corresponding to a given depth range, each of said plurality of objects corresponding to a particular determined area, wherein said interpreting means comprises: means for creating a depth map for said correlated patches,   means for interpreting said depth map to identify one or more regions corresponding to said given depth range, each of said plurality of objects corresponding to one of said one or more regions, and   means for filtering out said depth information for objects in said scene other than said plurality of objects.     
     
     
       27. The apparatus of claim 26, wherein said means for creating a depth map comprises means for creating a plot of depth frequency for said correlated patches, and wherein said means for interpreting said depth map comprises means for determining relative peaks in said plot, each of said plurality of objects corresponding to one of said relative peaks. 
     
     
       28. The apparatus of claim 27, wherein said filtering means comprises: means for storing reference depth information for said scene without said plurality of objects therein; and   means for eliminating relative peaks corresponding to said reference depth information.   
     
     
       29. The apparatus of claim 27 wherein said filtering means comprises means for filtering out said depth information corresponding to objects in said scene beyond a predetermined depth. 
     
     
       30. The apparatus of claim 29 wherein said filtering means comprises means for filtering out said depth information corresponding to objects in said queue beyond said predetermined depth when said depth information indicates an absence of said plurality of objects in a depth range of said substantially linear queue between said one end and said predetermined depth.