IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 10 TABLE 1 Comparison of 1D scanning and 2D scanning P2 P3 PP Ps Pe PP 1D scanning 2D scanning P6 P7 Ps Pa P7 Pa P3 P Coordinates Height:Average perpendicular distance Method based on localization Depth:Perpendicular points along two orthogonal directions Setup 1D scanning is much easier to deploy and costs less X1 y2 Performance 2D scanning provides more accurate alignment estimation and is more robust (a)Along the X axis (b)Along the Y axis 4.4.3 Determine Package Stacking with 1D Scanning PI P By doing once 1D scanning,we can get the package orien- tation,and due to the known tag layout,the tag separation PE distances of any two tags along axes are determined.Such that,we can leverage the tag array to localize the package X2 with the model proposed in Section 3.5.Considering the ambient noise and the multi-path effect,it is likely that we (c)Split plane (d)Split space cannot solve Eq.(4)with only two tags.So we combine signals from all effective tags and utilize Minimum Mean Fig.18.Illustration of determining the packages'order in the 3D space Squared Error(MMSE)method to get the optimal solution to Eq.(4).Specifically,denote the extracted perpendicular 4.4.2 Determine Package Stacking with 2D Scanning distance of tag Ti from the angle profile as hi,and the theoretical perpendicular distance as hi,which can be easily Through once 1D scanning,after determining the package derived based on Eq.(4).Thus,we aim to find the optimal orientation for each single package,we derive the indicators solution (d,d:)to minimize the difference between the of the packages'centers for the relative positions along the theoretical h;and the extracted hi: scanning direction,so we know their relative orders along that direction.Similarly,by performing the other scanning along the orthogonal direction of the previous one,we can ag∑(h-)2, =1 get the packages'relative positions along the new direction Combining their relative positions along the two directions, where n represents the number of selected tags.We prefer the 3D space is divided into many pieces.For each piece tags with the same orientation or with relatively small linear two dimensions are fixed,the packages in it are lining up, fitting errors for localization. so we can use the perpendicular distances of the packages' With comparison to the 2D scanning (TABLE 1),the 1D centers to determine their orders in the piece.Thus,all the scanning is not as accurate or robust as the 2D scanning. packages'relative positions in the 3D space are determined. The perpendicular point accuracy along the scanning di- Taking the scene in Fig.17 for example,there are eight rection is more accurate than the perpendicular distance packages in total(using the package center to represent the accuracy along the orthogonal direction of the scanning(in corresponding package).The dash lines are parallel to the Section 4.3.2).For the 1D scanning,it uses the perpendicular different axes,respectively.The antenna is above all tags.It distances of tags in a tag array to do the localization,so performs a 2D mobile scanning along the X and Y axes.All the error in the estimated perpendicular distance can be of the tags are always at the same side against the antenna introduced into the height and depth estimation.Mean- plane.For the scanning along the X axis,based on the per- while,it is possible that there is no solution to Eq.(4),in pendicular points of the packages'centers,the packages can which case we cannot determine the package stacking based be split into two sets:{P2,P3,P6,P7}and {P,P,P5,Ps}. on the localization.Whereas,the 2D scanning performs In each set,the X coordinates of the packages are the same, one more mobile scanning along the orthogonal direction, as they share the same perpendicular points projected to the depth depends on the perpendicular point along the the X axis.Similarly,based on the mobile scanning along second scanning direction,which is of high accuracy so as the y axis,the packages can also be split into two sets: to provide the accurate alignment estimation.The space can [Ps,P6,P7,Ps}and [P,P2,P3,Pa}.Combining these two be split by the combination of accurate perpendicular points split results,we have four sets then:[P1,P},{P2,P3), along two directions,and we use the average perpendicular [P:Ps}and [P6,P7}(in Fig.18).In each set,the packages distance of each package in a stack to determine their up- share the same coordinates along the X and Y axes.Then, down relationship,which is usually robust.However,the we just need to determine the packages'orders along the 1D scanning is much easier to deploy and costs less to per- Z axis.By referring to the perpendicular distances of the form.According to our experiment results(in Section 5.2), packages'centers,we can identify the packages'orders in 1D scanning achieves the comparable performance. each piece.As we determine the relative positions of each piece,and the packages'relative positions in each piece,the 4.4.4 Determine Complex Package Stacking stacking situation of these packages are determined,the 3D In the above sections,we simplify the stacking determina- reconstruction for multiple packages is done. tion by taking packages as individual points.However,inIEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 10 Z X Z & ' # ( " % $ ! *" *& (a) Along the X axis Y Z $ # ( ! " & ' % )" )& X X (b) Along the Y axis Y X Y # ( )" )& & ' " % $ ! *" *& (c) Split plane Y Y X Z (d) Split space Fig. 18. Illustration of determining the packages’ order in the 3D space 4.4.2 Determine Package Stacking with 2D Scanning Through once 1D scanning, after determining the package orientation for each single package, we derive the indicators of the packages’ centers for the relative positions along the scanning direction, so we know their relative orders along that direction. Similarly, by performing the other scanning along the orthogonal direction of the previous one, we can get the packages’ relative positions along the new direction. Combining their relative positions along the two directions, the 3D space is divided into many pieces. For each piece, two dimensions are fixed, the packages in it are lining up, so we can use the perpendicular distances of the packages’ centers to determine their orders in the piece. Thus, all the packages’ relative positions in the 3D space are determined. Taking the scene in Fig. 17 for example, there are eight packages in total (using the package center to represent the corresponding package). The dash lines are parallel to the different axes, respectively. The antenna is above all tags. It performs a 2D mobile scanning along the X and Y axes. All of the tags are always at the same side against the antenna plane. For the scanning along the X axis, based on the per￾pendicular points of the packages’ centers, the packages can be split into two sets: {P2, P3, P6, P7} and {P1, P4, P5, P8}. In each set, the X coordinates of the packages are the same, as they share the same perpendicular points projected to the X axis. Similarly, based on the mobile scanning along the Y axis, the packages can also be split into two sets: {P5, P6, P7, P8} and {P1, P2, P3, P4}. Combining these two split results, we have four sets then: {P1, P4}, {P2, P3}, {P5, P8} and {P6, P7} (in Fig. 18). In each set, the packages share the same coordinates along the X and Y axes. Then, we just need to determine the packages’ orders along the Z axis. By referring to the perpendicular distances of the packages’ centers, we can identify the packages’ orders in each piece. As we determine the relative positions of each piece, and the packages’ relative positions in each piece, the stacking situation of these packages are determined, the 3D reconstruction for multiple packages is done. TABLE 1 Comparison of 1D scanning and 2D scanning 1D scanning 2D scanning Method Coordinates based on localization Height: Average perpendicular distance Depth: Perpendicular points along two orthogonal directions Setup 1D scanning is much easier to deploy and costs less Performance 2D scanning provides more accurate alignment estimation and is more robust 4.4.3 Determine Package Stacking with 1D Scanning By doing once 1D scanning, we can get the package orien￾tation, and due to the known tag layout, the tag separation distances of any two tags along axes are determined. Such that, we can leverage the tag array to localize the package with the model proposed in Section 3.5. Considering the ambient noise and the multi-path effect, it is likely that we cannot solve Eq. (4) with only two tags. So we combine signals from all effective tags and utilize Minimum Mean Squared Error (MMSE) method to get the optimal solution to Eq. (4). Specifically, denote the extracted perpendicular distance of tag Ti from the angle profile as hbi , and the theoretical perpendicular distance as hi , which can be easily derived based on Eq. (4). Thus, we aim to find the optimal solution (d ∗ x , d∗ z ) to minimize the difference between the theoretical hi and the extracted hbi : arg min dx,dz Xn i=1  hi − hbi 2 , where n represents the number of selected tags. We prefer tags with the same orientation or with relatively small linear fitting errors for localization. With comparison to the 2D scanning (TABLE 1), the 1D scanning is not as accurate or robust as the 2D scanning. The perpendicular point accuracy along the scanning di￾rection is more accurate than the perpendicular distance accuracy along the orthogonal direction of the scanning (in Section 4.3.2). For the 1D scanning, it uses the perpendicular distances of tags in a tag array to do the localization, so the error in the estimated perpendicular distance can be introduced into the height and depth estimation. Mean￾while, it is possible that there is no solution to Eq. (4), in which case we cannot determine the package stacking based on the localization. Whereas, the 2D scanning performs one more mobile scanning along the orthogonal direction, the depth depends on the perpendicular point along the second scanning direction, which is of high accuracy so as to provide the accurate alignment estimation. The space can be split by the combination of accurate perpendicular points along two directions, and we use the average perpendicular distance of each package in a stack to determine their up￾down relationship, which is usually robust. However, the 1D scanning is much easier to deploy and costs less to per￾form. According to our experiment results (in Section 5.2), 1D scanning achieves the comparable performance. 4.4.4 Determine Complex Package Stacking In the above sections, we simplify the stacking determina￾tion by taking packages as individual points. However, in