System for determining the position of an object on a transport assembly from its boundary points

• US 6,735,332 B1
• Filed: 03/30/2000
• Issued: 05/11/2004
• Est. Priority Date: 03/30/2000
• Status: Expired due to Fees

• Current Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Original Assignee: Xerox Corporation (Xerox Holdings Corp.)
• Inventors: Goldberg, David, Bern, Marshall W.
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US09/539,736
• Time in Patent Office: 1,503 Days
• Field of Search: 382/203, 382/141, 382/151, 382/153, 382/101, 382/291, 382/241, 382/199, 271/4.03, 271/3.13, 271/10.03, 271/111, 271/259, 271/265.02, 271/265.03
• US Class Current: 382/141
• CPC Class Codes: G06T 7/564 from contours
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80

Abstract

A system determines the position of an object located on a transport assembly. Sensor arrays are embedded in the transport assembly for identifying boundary locations of the object. The sensor arrays are spaced apart in an arrangement for detecting the locations at which the object crosses the sensor arrays. These locations provide a set of boundary points. The system computes the equation of a rectangle that identifies the location of the object on the transport assembly by minimizing the deviation of the set of boundary points from the boundary of the equation of the rectangle.

Claims

1. A method for locating a rectangular object on a surface of a transport assembly, comprising:

recording a set of boundary points that identify boundary locations of the rectangular object on the surface of the transport assembly;

the set of boundary points including at least one boundary point that does not lie on the boundary of the rectangular object; and

computing an equation of a rectangle that minimizes deviation of the boundary points in the set of boundary points from the boundary of the rectangular object;

the equation of the rectangle defining a position of the rectangular object on the transport assembly.

2. The method according to claim 1, wherein the set of boundary points are recorded from a set of point sensors arranged in a pattern on the transport assembly that produces boundary information of the rectangular object.

3. The method according to claim 2, wherein the set of point sensors are arranged in arrays of point sensors on the transport assembly.

4. The method according to claim 3, wherein the arrays of point sensors are arranged perpendicular to each other on the transport assembly.

5. The method according to claim 3, wherein the arrays of point sensors are arranged in a herringbone pattern on the transport assembly.

6. The method according to claim 3, wherein the arrays of point sensors are rotated relative to adjacent arrays of point sensors on the transport assembly by a predefined angle.

7. The method according to claim 1, wherein said computing further comprises assigning each point in the set of boundary points to one of four groups of points with each group of points corresponding to one side of the rectangular object.

8. The method according to claim 7, wherein said computing further comprises computing a slope value m defining the equation of a rectangle without using dimensions of the rectangular object.

9. The method according to claim 8, wherein said computing further comprises defining the equation of the rectangle using equations of a line as follows:

y=mx+b, $y=\left(\frac{-1}{m}\right)<br><br>x+\frac{d}{m},$ 

y=mx+c, and $y=\left(\frac{-1}{m}\right)<br><br>x+\frac{e}{m},$

where m is a slope; and

b, c, d, and e are y-intercepts.

10. The method according to claim 9, wherein said computing further comprises computing a slope value m according to the following equation:

$m=\frac{\left(C_2-\frac{\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i}{n_A}+\frac{\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i}{n_B}-\frac{\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i}{n_C}+\frac{\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i}{n_D}\right)}{\left(C_1-\frac{{\left(\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i\right)}^2}{n_A}-\frac{{\left(\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i\right)}^2}{n_B}-\frac{{\left(\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i\right)}^2}{n_C}-\frac{{\left(\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i\right)}^2}{n_D}\right)},$

where;

(x_i, y_i) is a boundary point of the rectangular object,

S_A, S_B, S_C, and S_D, are four groups of boundary points corresponding to each side of the rectangular object, $n_A=\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>1,n_B=\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>1,n_C=\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>1,\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}<br><br>\text{\hspace{1em}<br><br>}<br><br>n_D=\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>1,$

are the number of boundary points (x_i, y_i) in each group of boundary points S_A, S_B, S_C, and S_D, of the rectangular object, respectively, $C_1=\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i^2+\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i^2+\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i^2+\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i^2,\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$C_2=\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i<br><br>x_i-\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>y_i+\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>y_i-\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i<br><br>y_i.$

11. The method according to claim 10, wherein said computing further comprises computing y-intercept values b, c, d, and e with the slope value m according to the following equations:

$b=\frac{\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i-m<br><br>\underset{i\in <br><br>S_A}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i}{n_A},<br><br>c=\frac{\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i-m<br><br>\underset{i\in <br><br>S_C}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i}{n_C},<br><br>d=\frac{m<br><br>\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i+\underset{i\in <br><br>S_B}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i}{n_B},\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$e=\frac{m<br><br>\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>y_i+\underset{i\in <br><br>S_D}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>x_i}{n_D}.$

12. The method according to claim 7, wherein said computing further comprises computing a slope value m defining the equation of a rectangle using dimensions of the rectangular object.

13. The method according to claim 12, wherein said computing further comprises computing a slope value m defining the equation of a rectangle using an estimate of the orientation θ

of the rectangular object on the transport assembly.

14. The method according to claim 13, wherein said computing further comprises defining the equation of the rectangle using equations of a line as follows:

15. The method according to claim 14, wherein said computing further comprises approximating 1/cos(O) with a linear approximation as follows:

$\sqrt{m^2+1}=\frac{1}{\cos <br><br>\left(\mathrm{\theta <br><br>}\right)}\approx <br><br>k_e+k_e<br><br>m_e<br><br>m,$

where;

θ

_e is an estimate of the orientation of the rectangular object relative to the transport assembly,

k_e=cos(θ

_e), and

m=tan(θ

).

16. The method according to claim 15, wherein said computing further comprises computing a slope value m according to the following equation:

$m=\frac{D_3-\left(D_1+D_2\right)<br><br>\left(n_B+n_D\right)}{D_4+\left(D_5+D_6\right)<br><br>\left(n_B+n_D\right)},$

where;

17. The method according to claim 16, wherein said computing further comprises computing y-intercept values b and d with the slope value m according to the following equations:

$b=\frac{\left({\mathrm{hk}}_e<br><br>n_C+{\mathrm{hk}}_e<br><br>m<br><br>\text{\hspace{1em}<br><br>}<br><br>m_e<br><br>n_C+{\mathrm{mx}}_0+{\mathrm{mx}}_C-y_A-y_C\right)}{\left(n_A+n_D\right)},\text{\hspace{1em}<br><br>}<br><br>\mathrm{and}$$d=\frac{\left(k_e<br><br>n_D<br><br>w+h_e<br><br>m<br><br>\text{\hspace{1em}<br><br>}<br><br>m_e<br><br>n_D<br><br>w-x_B+x_D-{\mathrm{my}}_B-{\mathrm{my}}_C\right)}{\left(n_B+n_D\right)}.$

18. The method according to claim 1, wherein said computing assigns each point in the set of boundary points to one of four groups of points by:

locating a bounding rectangle that bounds all the points in the set of boundary points; and

forming a line through opposing pairs of corners of the bounding rectangle.

19. The method according to claim 1, wherein said computing further comprises:

computing a centroid using the set of boundary points;

sorting points in the set of boundary points by angle about the computed centroid;

selecting a pair of adjacent points from the sorted set of boundary points;

computing a line through the selected pair of adjacent points; and

computing a rectangle bounding box with the computed line that includes all of the points in the set of boundary points.

20. An apparatus for locating a rectangular object on a transport assembly, comprising:

sensors for recording a set of boundary points that identify boundary locations of the rectangular object on the surface of the transport assembly;

the set of boundary points including at least one boundary point that does not lie on the boundary of the rectangular object; and

a transport controller coupled to the sensors for computing an equation of a rectangle that minimizes deviation of the boundary points in the set of boundary points from the boundary of the rectangular object;

the equation of the rectangle defining a position of the rectangular object on the transport assembly.

21. The apparatus according to claim 20, wherein the sensors further comprises point sensors arranged in arrays of point sensors on the transport assembly.

22. The apparatus according to claim 21, wherein the arrays of point sensors are arranged perpendicular to each other on the transport assembly.

23. The apparatus according to claim 21, wherein the arrays of point sensors are arranged in a herringbone pattern on the transport assembly.

24. The apparatus according to claim 21, wherein the arrays of point sensors are rotated relative to adjacent arrays of point sensors on the transport assembly.

25. The apparatus according to claim 20, wherein said transport controller assigns each point in the set of boundary points to one of four groups of points, with each group of points corresponding to one side of the rectangular object.

26. The apparatus according to claim 20, wherein said transport controller further comprises:

means for locating a bounding rectangle that bounds all the points in the set of boundary points; and

means for forming a line through opposing pairs of corners of the bounding box.

27. The apparatus according to claim 20, wherein said transport controller performs the operations of:

means for computing a centroid using the set of boundary points;

means for sorting points in the set of boundary points by angle about the computed centroid;

means for selecting a pair of adjacent points from the sorted set of boundary points;

means for computing a line through the selected pair of adjacent points; and

means for computing a rectangle bounding box with the computed line that includes all of the points in the set of boundary points.

28. The apparatus according to claim 20, further comprising actuators coupled to the transport controller for moving the rectangular object on the transport assembly.