Produce recognition system and method

• US 6,529,855 B1
• Filed: 07/28/1999
• Issued: 03/04/2003
• Est. Priority Date: 07/28/1999
• Status: Expired due to Term

• Current Assignee: NCR Voyix Corporation
• Original Assignee: NCR Corporation
• Inventors: Gu, Yeming
• Primary Examiner(s): Hoff, Marc S.
• Assistant Examiner(s): KIM, PAUL L
• Application Number:
  US09/362,488
• Time in Patent Office: 1,315 Days
• Field of Search: 702/128, 702/155, 702/159, 382/190, 382/110, 356/328
• US Class Current: 702/155
• CPC Class Codes: G06F 18/24137 Distances to cluster centroïds
• CPC Class Codes: G06F 2218/12 Classification; Matching
• CPC Class Codes: G06V 20/68 Food, e.g. fruit or vegetables

Abstract

A produce recognition system and method which use a distance measure of likeness calculation to identify a produce item. The system includes a produce data collector, a library, and a computer. The produce data collector collects first data from the produce item. The library contains second data associated with classes of produce items. The computer reads the second data from a library, determines a distance measure of likeness value between the first data and each of the second data, determines third data and a corresponding class of produce items from the second data which produces a smallest distance measure of likeness value, and identifies the produce item to be within the corresponding class of produce items.

Claims

1. A method of identifying an item comprising the steps of:

obtaining first data describing the item;

reading a number of second data associated with a plurality of items from a library;

determining a Distance Measure of Likeness value, D_j, between the first data and each of the second data, wherein the Distance Measure of Likeness value is defined by a first equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a second equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

determining third data and a corresponding item name from the second data which produces a smallest Distance Measure of Likeness value; and

identifying the item to be the corresponding item.

2. A method of recognizing a produce item comprising the steps of:

collecting first data from the produce item;

reading a number of second data associated with a plurality of produce items from a library;

determining a Distance Measure of Likeness value, D_j, between the first data and each of the second data, wherein the Distance Measure of Likeness value is defined by a first equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij def ined by a second equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

determining third data and a corresponding produce item from the second data which produces a smallest Distance Measure of Likeness value; and

identifying the produce the item to be the corresponding item.

3. The method as recited in claim 2, wherein the step of identifying comprises the substeps of:

ordering the Distance Measure of Likeness values by size;

displaying a list of the ordered Distance Measure of Likeness values and corresponding names of produce items to an operator; and

recording an operator choice for a produce item from the list.

4. A method of recognizing a produce item comprising the steps of:

collecting first data from the produce item;

reading a number of second data associated with classes of produce items from a library;

determining a Distance Measure of Likeness value, D_j, between the first data and each of the second data, wherein the Distance Measure of Likeness value is defined by a first equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a second equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

determining third data and a corresponding class of produce items from the second data which produces a smallest Distance Measure of Likeness value; and

identifying the produce item to be within the corresponding class of produce items.

5. A method of recognizing a produce item comprising the steps of:

reading a library of reference produce data, including typical produce data for a plurality of different produce items;

initiating operation of a produce data collector;

collecting first data from the produce item;

performing data reduction on the first data to produce second data;

determining Distance Measure of Likeness values, D_j, between the second data and typical produce data,

wherein the Distance Measure of Likeness values are defined by a first equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}};<br><br>$

wherein the Distance Measure of Likeness values, D_j, are distance measures between instances P(x₁, x₂, . . . , x_N) in the second data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the typical produce data and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

sorting the Distance Measure of Likeness values by size;

building a list including a predetermined number of smallest Distance Measure of Likeness values and corresponding names of produce items;

displaying the list; and

recording an operator choice for one of the names from the list.

6. A produce recognition system comprising:

a produce data collector which collects first data from a produce item;

a library containing second data associated with classes of produce items; and

a computer which reads the second data from a library, determines a Distance Measure of Likeness value, D_j, between the first data and each of the second data, determines third data and a corresponding class of produce items from the second data which produces a smallest Distance Measure of Likeness value, and identifies the produce item to be within the corresponding class of produce items;

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tN) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is defined by a second equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}}.$

7. The produce recognition system as recited in claim 6, wherein the second data comprises:

produce data for produce items in the classes;

typical produce data for the classes; and

typical distance scale data for typical produce data.

8. A produce recognition system comprising:

a produce data collector which collects first data from a produce item;

a library containing second data associated with classes of produce items;

a computer which reads the second data from a library, determines a Distance Measure of Likeness value, D_j, between the first data and each of the second data, determines third data and a corresponding class of produce items from the second data which produces a smallest Distance Measure of Likeness value, sorts the Distance Measure of Likeness values by size, builds a list including a predetermined number of smallest Distance Measure of Likeness values and corresponding classes of produce items, displays the list, and records an operator choice for one of the classes from the list;

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is defined by an equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}}.$

9. A produce recognition system comprising:

collecting means for collecting first data from a produce item;

storage means containing second data associated with classes of produce items; and

means for reading the second data from the storage means, determining a Distance Measure of Likeness value, D_j, between the first data and each of the second data, determining third data and a corresponding class of produce items from the second data which produces a smallest Distance Measure of Likeness value, and identifying the produce item to be within the corresponding class of produce items;

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance F(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is defined by an equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}}.$

10. A method of building a library of item data for use in recognizing unknown items comprising the steps of:

defining classes for describing the items;

collecting instance samples from known items in each class;

determining typical instances for each class;

determining distance scales for the typical instances;

storing the typical instances and the distance scales in a library for later use in calculating Distance Measure of Likeness values, D_j, between the typical instances and instances associated with the unknown items;

wherein the Distance Measure of Likeness values, D_j, are distance measures between the instances P(x₁, x₂, . . . , x_N) associated with the unknown item and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is defined by an equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}}.$

11. The method as recited in claim 10, wherein the items are produce items.

12. A method of identifying an unknown item comprising the steps of:

obtaining first multiple dimensional data describing the unknown item;

reading second multiple dimensional data associated with a plurality of typical instances of a plurality of classes of known items from reference item data;

determining a Distance Measure of Likeness value, D_j, between the first data and each of the second data;

wherein the Distance Measure of Likeness value, D_j, is a distance measure between an instance P(x₁, x₂, . . . , x_N) in the first data and one class j of a total number n_j of the classes;

wherein the one class j is defined by a typical instance P_tj(x_t1j, x_t2j, . . . , x_tNj) in N-dimensional space in the second data and corresponding distance scales d_ij defined by a first equation $d_{\mathrm{ij}}=\sqrt{\frac{\underset{k=1}{\overset{n_j}{\sum <br><br>}}<br><br>{\left(x_{\mathrm{ijk}}-x_{\mathrm{tik}}\right)}^2}{n_j}};<br><br>$

wherein the Distance Measure of Likeness value, D_j, is defined by a second equation $D_j=\sqrt{\underset{i=1}{\overset{N}{\sum <br><br>}}<br><br>\frac{{\left(x_i-x_{\mathrm{tij}}\right)}^2}{d_{\mathrm{ij}}^2}};<br><br>$

determining third multiple dimensional data and a corresponding item identifier from the second multiple dimensional data which produces a smallest Distance Measure of Likeness value; and

identifying the unknown item to be the corresponding item.