Linear grouping of recognized items in an image

• US 9,984,451 B2
• Filed: 12/18/2015
• Issued: 05/29/2018
• Est. Priority Date: 12/18/2015
• Status: Active Grant

• Current Assignee: Ricoh Company Limited
• Original Assignee: Ricoh Company Limited
• Inventors: Gormish, Michael, Schwartz, Edward
• Primary Examiner(s): Vu, Kim
• Assistant Examiner(s): VANCHY JR, MICHAEL J
• Application Number:
  US14/975,630
• Publication Number:
  US 20170178310A1
• Time in Patent Office: 893 Days
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06F 18/23 Clustering techniques
• CPC Class Codes: G06F 18/24 Classification techniques
• CPC Class Codes: G06T 2207/30108 Industrial image inspection
• CPC Class Codes: G06T 7/0004 Industrial image inspection
• CPC Class Codes: G06T 7/30 Determination of transform parameters for the alignment of images, i.e. image registration
• CPC Class Codes: G06T 7/60 Analysis of geometric attributes
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/24 Aligning, centring, orientation detection or correction of the image
• CPC Class Codes: G06V 10/42 Global feature extraction by analysis of the whole pattern, e.g. using frequency domain transformations or autocorrelation
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

A system and method that determines multiple linear groups of horizontally placed items in an image is disclosed. The method includes receiving an image including a portion of a shelving unit, identifying a plurality of items in the image, determining a plurality of facings, clustering the plurality of facings, merging a plurality of clusters and determining a list of linear groups in the image.

Claims

1. A method comprising:

receiving an image including a portion of a shelving unit;

identifying a plurality of items in the image;

determining a plurality of facings based on the plurality of items;

determining whether items of adjacent facings in the plurality of facings are positioned within a threshold horizontal distance of each other, the threshold horizontal distance being based on a factor of a maximum dimension of the items in either of the adjacent facings;

responsive to determining that the items of adjacent facings in the plurality of facings are positioned within the threshold distance of each other, grouping the plurality of facings based on position and identification; and

determining a list of linear groups in the image.

2. The method of claim 1, wherein grouping the plurality of facings based on position and identification comprises:

clustering the plurality of facings; and

merging a plurality of clusters.

3. The method of claim 1, wherein determining the plurality of facings comprises:

determining a similarity of items in each one of the plurality of facings; and

categorizing each one of the plurality of facings based on the similarity of items.

4. The method of claim 3, wherein determining the similarity of items comprises:

determining a pair of items;

determining a first list of recognition results for a first item of the pair and a second list of recognition results for a second item of the pair;

determining a first length of the first list of recognition results and a second length of the second list of recognition results;

determining a count of matching recognition results in the first list and the second list of recognition results; and

determining a similarity of the pair of items by dividing the count by a geometric mean of the first length and the second length.

5. The method of claim 1, comprising:

receiving a planogram of the shelving unit;

extracting contextual information from the planogram; and

grouping the plurality of facings based on position and identification using the extracted contextual information.

6. The method of claim 5, wherein grouping the plurality of facings based on position and identification using the extracted contextual information comprises:

determining a plurality of slices in the image;

identifying items in each slice;

estimating locations of shelves based on identified items and aligning the planogram;

determining whether the identified items overlap with one or more linear groups in the planogram; and

assigning the identified items to the one or more linear groups based on criteria.

7. The method of claim 6, wherein estimating locations of shelves based on identified items and aligning the planogram comprises:

estimating a bottom location of a top shelf and a bottom shelf using the identified items in each slice; and

aligning the planogram with the estimated bottom location of the top shelf and the bottom shelf.

8. The method of claim 6, wherein the criteria includes an overlap satisfying a threshold proximity to previously assigned items.

9. The method of claim 5, wherein grouping the plurality of facings based on position and identification using the extracted contextual information comprises:

aligning the planogram with the image;

mapping each cluster spatially to one or more linear groups in the planogram;

determining a similarity of items included within each cluster and the one or more linear groups;

determining a distance of each cluster to the one or more linear groups based on the similarity;

assigning each cluster to a nearest linear group of the one or more linear groups; and

determining the list of linear groups.

10. The method of claim 1, wherein determining the list of linear groups comprises:

identifying a first list of candidate linear groups;

identifying a second list of candidate linear groups;

assigning a score to each of a plurality of candidate linear groups in the first list and the second list;

comparing scores of corresponding pairs of candidate linear groups in the first and the second list to identify linear groups with a highest score; and

aggregating the linear groups with the highest score into a third list of linear groups.

11. A system comprising:

one or more processors; and

a memory, the memory storing instructions, which when executed cause the one or more processors to;

receive an image including a portion of a shelving unit;

identify a plurality of items in the image;

determine a plurality of facings based on the plurality of items;

determine whether items of adjacent facings in the plurality of facings are positioned within a threshold horizontal distance of each other, the threshold horizontal distance being based on a factor of a maximum dimension of the items in either of the adjacent facings;

responsive to determining that the items of adjacent facings in the plurality of facings are positioned within the threshold distance of each other, group the plurality of facings based on position and identification; and

determine a list of linear groups in the image.

12. The system of claim 11, wherein to determine the plurality of facings, the instructions cause the one or more processors to:

determine a pair of items in each one of the plurality of facings;

determine a first list of recognition results for a first item of the pair and a second list of recognition results for a second item of the pair;

determine a first length of the first list of recognition results and a second length of the second list of recognition results;

determine a count of matching recognition results in the first list and the second list of recognition results;

determine a similarity of the pair of items by dividing the count by a geometric mean of the first length and the second length; and

categorize each one of the plurality of facings based on the similarity of the pair of items.

13. The system of claim 11, wherein to group the plurality of facings based on position and identification, the instructions cause the one or more processors to:

receive a planogram of the shelving unit;

extract contextual information from the planogram;

determine a plurality of slices in the image;

identify items in each slice;

estimate locations of shelves based on identified items and align the planogram;

determine whether the identified items overlap with one or more linear groups in the planogram; and

assign the identified items to the one or more linear groups based on the overlap satisfying a threshold.

14. The system of claim 13, wherein to group the plurality of facings, the instructions cause the one or more processors to:

align the planogram with the image;

map each cluster spatially to one or more linear groups in the planogram;

determine a similarity of items included within each cluster and the one or more linear groups;

determine a distance of each cluster to the one or more linear groups based on the similarity;

assign each cluster to a nearest linear group of the one or more linear groups; and

determine the list of linear groups.

15. The system of claim 11, wherein to determine the list of linear groups, the instructions cause the one or more processors to:

identify a first list of candidate linear groups;

identify a second list of candidate linear groups;

assign a score to each of a plurality of candidate linear groups in the first list and the second list;

compare scores of corresponding pairs of candidate linear groups in the first and the second list to identify linear groups with a highest score; and

aggregate the linear groups with the highest score into a third list of linear groups.

16. A computer program product comprising a non-transitory computer readable medium storing a computer readable program, wherein the computer readable program when executed on a computer causes the computer to:

receive an image including a portion of a shelving unit;

identify a plurality of items in the image;

determine a plurality of facings based on the plurality of items;

determine whether items of adjacent facings in the plurality of facings are positioned within a threshold horizontal distance of each other, the threshold horizontal distance being based on a factor of a maximum dimension of the items in either of the adjacent facings;

responsive to determining that the items of adjacent facings in the plurality of facings are positioned within the threshold distance of each other, group the plurality of facings based on position and identification; and

determine a list of linear groups in the image.

17. The computer program product of claim 16, wherein to group the plurality of facings based on position and identification, the computer readable program causes the computer to:

determine a similarity of items in each one of the plurality of facings;

categorize each one of the plurality of facings based on the similarity of items;

cluster the plurality of facings; and

merge a plurality of clusters.

18. The computer program product of claim 17, wherein to determine the similarity of items, the computer readable program causes the computer to:

determine a pair of items;

determine a first list of recognition results for a first item of the pair and a second list of recognition results for a second item of the pair;

determine a first length of the first list of recognition results and a second length of the second list of recognition results;

determine a count of matching recognition results in the first list and the second list of recognition results; and

determine a similarity of the pair of items by dividing the count by a geometric mean of the first length and the second length.

19. The computer program product of claim 16, wherein to group the plurality of facings, the computer readable program causes the computer to:

receive a planogram of the shelving unit;

extract contextual information from the planogram;

determine a plurality of slices in the image;

identify items in each slice;

estimate locations of shelves based on identified items and align the planogram;

determine whether the identified items overlap with one or more linear groups in the planogram; and

assign the identified items to the one or more linear groups based on the overlap satisfying a threshold.

20. The computer program product of claim 19, wherein to group the plurality of facings, the computer readable program causes the computer to:

align the planogram with the image;

map each cluster spatially to one or more linear groups in the planogram;

determine a similarity of items included within each cluster and the one or more linear groups;

determine a distance of each cluster to the one or more linear groups based on the similarity;

assign each cluster to a nearest linear group of the one or more linear groups; and

determine the list of linear groups.