IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 RF-3DScan:RFID-based 3D Reconstruction on Tagged Packages Yanling Bu,Student Member,IEEE,Lei Xie,Member,IEEE,Yinyin Gong,Jia Liu,Member,IEEE, Bingbing He,Jiannong Cao,Fellow,IEEE,Baoliu Ye,Member,IEEE,and Sanglu Lu,Member,IEEE Abstract-Currently,the logistic industry has introduced 3D reconstruction to monitor the package placement in the warehouse. Previous 3D reconstruction solutions mainly utilize computer vision or sensor-based methods,which are restricted to the line-of-sight or the battery life.Therefore,we propose a passive RFID-based solution,called RF-3DScan,to perform 3D reconstruction on tagged packages,including the package orientation and the package stacking.The basic idea is that a moving antenna can obtain RF-signals from the tags attached on packages with the 1D linear mobile scanning.Through extracting phase differences to build angle profiles for each tag,RF-3DScan derives their relative positions,further determines the package orientation and the coarse-grained package stacking.By simply performing the 2D scanning,RF-3DScan can provide the fine-grained package stacking determination.We implement a prototype system of RF-3DScan and evaluate its performance in real settings.Our experiment results show that RF-3DScan can achieve about 92.5%identification accuracy of the bottom face,and average error about 4.08 of the rotation angle. For the package stacking,1D scanning can achieve the comparable performance in comparison with 2D scanning. Index Terms-RFID,3D reconstruction,package orientation,package stacking. INTRODUCTION URRENTLY,in the logistic industry,traditional applica- tions like the warehouse management and the logistic transportation,are emerging with brand new requirements. For instance,considering the safety and space utilization Package <right Tag issues,packages are required to be placed based on specified Stacking left Tagged Package regulations.Specifically,with regard to a single package,if it contains orientation-sensitive objects,i.e.,chemical reagents, precision instruments,it is protected from getting rollover or upside down.While with regard to multiple packages,to Antenna ensure the package safety during the transportation process, Package unaligned Orientation rollover Linear Mobile Scanning they are required to be precisely arranged in order,i.e., Linear Track heavy packages are placed on the bottom and light ones are on the top.To satisfy the above requirements,3D reconstruc- Fig.1.3D reconstruction on tagged packages via linear mobile scanning tion has been introduced to handle these issues for monitor- ing the package placement.Generally,3D reconstruction is Previous 3D reconstruction solutions mainly utilize com- a process of capturing the shape and appearance of a single puter vision or sensor-based methods.Computer vision- or multiple real objects.Fig.1 shows the principle of 3D based solutions capture the appearance of objects with cam- reconstruction on packaged objects:1)Package orientation eras,and then build 3D profiles of objects [1,2].They can of a single object,which means determining the relative reconstruct objects in a vivid way.However,they suffer from orientation of each object,i.e.,pinpointing the bottom/top the line-of-sight constraint,easily leading to blind angles face and estimating angles of vertical sides of the object in when capturing images.Sensor-based approaches attach the specified coordinate system.2)Package stacking of mul- inertial sensors onto items so as to monitor the orientation tiple objects,which means determining the relative stacking variation of targets [3,4].However,the main disadvantages situation of multiple packages,i.e.,figuring out the up- of them are the high hardware cost and the limited battery down,front-back or left-right relationships among objects. life of sensors.Thankfully,the promising RFID technology has brought great chances for the 3D reconstruction on packaged objects in the logistic industry.Nowadays,passive Yanling Bu,Lei Xie,Yinyin Gong,Jia Liu,Bingbing He,Baoliu Ye, and Sanglu Lu are with the State Key Laboratory for Novel Software RFID tags have been broadly used to label packages with Technology,Nanjing University,China. detailed logistics information.Compared to the above two E-mail: yanling@smail.nju.edu.cn, Ixie@nju.edu.cn, yy- approaches,the passive RFID tag is battery-free and cheap. gong@dislab.nju.edu.cn,jialiu@nju.edu.cn, hebb@dislab.nju.edu.cn, yebl@nju.edu.cn,sanglu@nju.edu.cn Also,RFID technology uses the backscatter communication, Jiannong Cao is with the Department of Computing,The Hong Kong so it has no requirement of the line of sight or the light Polytechnic University,Hong Kong,China. condition.Most importantly,in order to scan and identify E-mail:csjcao@comp.polyu.edu.hk. packages,RFID systems have been already widely deployed Lei Xie and Baoliu Ye are the co-corresponding authors. in the sites for most logistic applications in our daily life
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 1 RF-3DScan: RFID-based 3D Reconstruction on Tagged Packages Yanling Bu, Student Member, IEEE, Lei Xie, Member, IEEE, Yinyin Gong, Jia Liu, Member, IEEE, Bingbing He, Jiannong Cao, Fellow, IEEE, Baoliu Ye, Member, IEEE, and Sanglu Lu, Member, IEEE Abstract—Currently, the logistic industry has introduced 3D reconstruction to monitor the package placement in the warehouse. Previous 3D reconstruction solutions mainly utilize computer vision or sensor-based methods, which are restricted to the line-of-sight or the battery life. Therefore, we propose a passive RFID-based solution, called RF-3DScan, to perform 3D reconstruction on tagged packages, including the package orientation and the package stacking. The basic idea is that a moving antenna can obtain RF-signals from the tags attached on packages with the 1D linear mobile scanning. Through extracting phase differences to build angle profiles for each tag, RF-3DScan derives their relative positions, further determines the package orientation and the coarse-grained package stacking. By simply performing the 2D scanning, RF-3DScan can provide the fine-grained package stacking determination. We implement a prototype system of RF-3DScan and evaluate its performance in real settings. Our experiment results show that RF-3DScan can achieve about 92.5% identification accuracy of the bottom face, and average error about 4.08◦ of the rotation angle. For the package stacking, 1D scanning can achieve the comparable performance in comparison with 2D scanning. Index Terms—RFID, 3D reconstruction, package orientation, package stacking. ✦ 1 INTRODUCTION C URRENTLY, in the logistic industry, traditional applications like the warehouse management and the logistic transportation, are emerging with brand new requirements. For instance, considering the safety and space utilization issues, packages are required to be placed based on specified regulations. Specifically, with regard to a single package, if it contains orientation-sensitive objects, i.e., chemical reagents, precision instruments, it is protected from getting rollover or upside down. While with regard to multiple packages, to ensure the package safety during the transportation process, they are required to be precisely arranged in order, i.e., heavy packages are placed on the bottom and light ones are on the top. To satisfy the above requirements, 3D reconstruction has been introduced to handle these issues for monitoring the package placement. Generally, 3D reconstruction is a process of capturing the shape and appearance of a single or multiple real objects. Fig. 1 shows the principle of 3D reconstruction on packaged objects: 1) Package orientation of a single object, which means determining the relative orientation of each object, i.e., pinpointing the bottom/top face and estimating angles of vertical sides of the object in the specified coordinate system. 2) Package stacking of multiple objects, which means determining the relative stacking situation of multiple packages, i.e., figuring out the updown, front-back or left-right relationships among objects. • Yanling Bu, Lei Xie, Yinyin Gong, Jia Liu, Bingbing He, Baoliu Ye, and Sanglu Lu are with the State Key Laboratory for Novel Software Technology, Nanjing University, China. E-mail: yanling@smail.nju.edu.cn, lxie@nju.edu.cn, yygong@dislab.nju.edu.cn, jialiu@nju.edu.cn, hebb@dislab.nju.edu.cn, yebl@nju.edu.cn, sanglu@nju.edu.cn. • Jiannong Cao is with the Department of Computing, The Hong Kong Polytechnic University, Hong Kong, China. E-mail: csjcao@comp.polyu.edu.hk. • Lei Xie and Baoliu Ye are the co-corresponding authors. Tag Package Orientation Package Stacking Linear Mobile Scanning Antenna Linear Track Tagged Package above below left right rollover unaligned Fig. 1. 3D reconstruction on tagged packages via linear mobile scanning Previous 3D reconstruction solutions mainly utilize computer vision or sensor-based methods. Computer visionbased solutions capture the appearance of objects with cameras, and then build 3D profiles of objects [1, 2]. They can reconstruct objects in a vivid way. However, they suffer from the line-of-sight constraint, easily leading to blind angles when capturing images. Sensor-based approaches attach inertial sensors onto items so as to monitor the orientation variation of targets [3, 4]. However, the main disadvantages of them are the high hardware cost and the limited battery life of sensors. Thankfully, the promising RFID technology has brought great chances for the 3D reconstruction on packaged objects in the logistic industry. Nowadays, passive RFID tags have been broadly used to label packages with detailed logistics information. Compared to the above two approaches, the passive RFID tag is battery-free and cheap. Also, RFID technology uses the backscatter communication, so it has no requirement of the line of sight or the light condition. Most importantly, in order to scan and identify packages, RFID systems have been already widely deployed in the sites for most logistic applications in our daily life
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 Therefore,in this paper,we propose a passive RFID- This paper presents the first study of using RFID to based 3D reconstruction approach,called RF-3DScan.As perform the 3D reconstruction on tagged packages.We shown in Fig.1,RF-3DScan aims at performing the 3D make three contributions.First,for the 3D reconstruction reconstruction on packaged objects attached with passive on packages,we attach a set of passive RFID tags onto RFID tags,including the package orientation and the pack- packages,and respectively handle issues of the package age stacking.The basic idea is that by attaching multiple orientation and the package stacking through angle profiles tags onto the surface of packages,we are capable of obtain- of tags.We build an angle-profile-based model to depict ing the orientation of each single package and the stacking the relationship between RF-signals of tags and the orien- status of multiple packages based on the backscattered RF- tation/stacking status of packages.Second,we propose a signals from these tags.RF-3DScan works as follows.We mobile scanning approach to perform the 3D reconstruction attach a set of passive RFID tags onto the package surface, of tagged packages via RFID.Generally,with the 1D mobile and leverage one mobile RFID antenna to move along the scanning,we can determine the package orientation and straight line to continuously scan the tagged packages.With coarse-grained package stacking;while with the 2D mobile the mobile scanning,we collect RF-signals from tags when scanning,we can determine the fine-grained package stack- the antenna is at different positions.Then,we extract phase ing.Third,We implement a prototype system of RF-3DScan differences of tags at different time points,and build angle to evaluate its performance.Our experiment results in real profiles for each tag to depict the geometry angle variation settings show that RF-3DScan can achieve about 92.5% between antenna-tag pairs during the moving process.Re- identification accuracy of the bottom face,and average error ferring to the angle profiles of tags,we can derive their about 4.08 of the rotation angle.The 1D scanning is much relative positions,and further determine the package place- easier to perform than the 2D scanning,while achieving the ment status,including the package orientation for each single comparable performance in terms of the package stacking. package and the package stacking for multiple packages. To realize the 3D reconstruction via RFID systems,there 2 RELATED WORK are three key challenges.The first challenge is that the 2.1 Computer Vision and Sensor-based Approach uncertain tag direction is easy to create dead zones of RFID communication.How to optimize the layout of multiple Computer-vision-based solutions mainly leverage the depth tags for avoiding dead zones and achieving the robust 3D camera to perform 3D reconstruction of multiple objects reconstruction is a key problem.To tackle this challenge,we [1,2].To avoid the blind angles in 3D reconstruction for deploy tags along three mutual orthogonal orientations,so specified objects,usually multiple depth cameras are de- that there are always some tags that can be collected by the ployed at different positions to perform multi-view recon- reader easily,which guarantees the high sampling rate and struction for their 3D models [2],or a moving depth camera reliable 3D reconstruction.The second challenge is that the is used to build the 3D models in a mobile approach [1].In existing work can only derive the 2D relative localization a word,these approaches suffer from the line-of-sight(LOS) of tag objects via once mobile scanning.How to locate the constraint in 3D perception,and they are vulnerable to the package and determine the package placement in the 3D limitation of the light intensity.Sensor-based solutions [3,4] space is still under-investigated.To tackle this challenge,we mainly attach the battery-powered sensors(such as inertial build an angle-profile model and combine this model with sensors or GPS modules)to the surface of the objects,and the priori knowledge of tag layout to sense the package continuously monitor the 3D placement of specified objects placement in the 3D space.Through once mobile linear scan- so as to track the orientation variation [3],or the stacking ning,we can extract angle profiles from phase differences to situation among multiple objects.However,they suffer from obtain position indicators and further determine the pack- the high hardware cost of sensors,as well as the limited age orientation with the known tag layout.By performing battery life of the sensor. one more scanning along the direction orthogonal to the previous one,we can combine the twice position indicators 2.2 RFID-based Approach to accurately estimate the package stacking.Although the Orientation tracking:By attaching RFID tags onto the spec- 2D scanning is a fine-grained solution for the package stack- ified object,it is possible to track the orientation variation ing,it requires the extra mobile scanning,so we propose of the object according to the variation of the corresponding a coarse-grained solution by the 1D scanning.With the RF-signals [5-10].Tagball [5]is proposed as a 3D human- known tag layout,we can localize the package via only computer interaction system,where multiple passive tags once scanning to determine the package stacking.The third are attached to a controlling ball,such that the motions challenge is that the RF-signal is likely to be distorted due of the ball from users can be detected from the phase to the tag orientation or the multi-path effect.How to select changes of multiple tags.Tagyro [6]attaches an array of effective data to ensure the performance is to be studied.To passive RFID tags as orientation sensors on the objects, tackle this challenge,we leverage phase differences to derive by transforming the runtime phase offsets between tags angle profiles,so as to eliminate the phase variation caused into the orientation angle.Compared with our RF-3DScan by the changing tag's orientation relative to the antenna system,these approaches track the orientation variation of during the mobile scanning.Furthermore,at the start or end the dynamically moving objects,whereas our approach aims of the scanning,as the antenna is relatively far from the tag, to determine the orientation of statically placed packages. the RF-signal is more seriously distorted,so we propose an Localization:RFID localization generally falls into two adaptive algorithm to automatically filter outliers and keep categories:absolute localization [11-17]and relative local- remaining data for the later estimation. ization [18-25].By attaching multiple tags and pinpointing
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 2 Therefore, in this paper, we propose a passive RFIDbased 3D reconstruction approach, called RF-3DScan. As shown in Fig. 1, RF-3DScan aims at performing the 3D reconstruction on packaged objects attached with passive RFID tags, including the package orientation and the package stacking. The basic idea is that by attaching multiple tags onto the surface of packages, we are capable of obtaining the orientation of each single package and the stacking status of multiple packages based on the backscattered RFsignals from these tags. RF-3DScan works as follows. We attach a set of passive RFID tags onto the package surface, and leverage one mobile RFID antenna to move along the straight line to continuously scan the tagged packages. With the mobile scanning, we collect RF-signals from tags when the antenna is at different positions. Then, we extract phase differences of tags at different time points, and build angle profiles for each tag to depict the geometry angle variation between antenna-tag pairs during the moving process. Referring to the angle profiles of tags, we can derive their relative positions, and further determine the package placement status, including the package orientation for each single package and the package stacking for multiple packages. To realize the 3D reconstruction via RFID systems, there are three key challenges. The first challenge is that the uncertain tag direction is easy to create dead zones of RFID communication. How to optimize the layout of multiple tags for avoiding dead zones and achieving the robust 3D reconstruction is a key problem. To tackle this challenge, we deploy tags along three mutual orthogonal orientations, so that there are always some tags that can be collected by the reader easily, which guarantees the high sampling rate and reliable 3D reconstruction. The second challenge is that the existing work can only derive the 2D relative localization of tag objects via once mobile scanning. How to locate the package and determine the package placement in the 3D space is still under-investigated. To tackle this challenge, we build an angle-profile model and combine this model with the priori knowledge of tag layout to sense the package placement in the 3D space. Through once mobile linear scanning, we can extract angle profiles from phase differences to obtain position indicators and further determine the package orientation with the known tag layout. By performing one more scanning along the direction orthogonal to the previous one, we can combine the twice position indicators to accurately estimate the package stacking. Although the 2D scanning is a fine-grained solution for the package stacking, it requires the extra mobile scanning, so we propose a coarse-grained solution by the 1D scanning. With the known tag layout, we can localize the package via only once scanning to determine the package stacking. The third challenge is that the RF-signal is likely to be distorted due to the tag orientation or the multi-path effect. How to select effective data to ensure the performance is to be studied. To tackle this challenge, we leverage phase differences to derive angle profiles, so as to eliminate the phase variation caused by the changing tag’s orientation relative to the antenna during the mobile scanning. Furthermore, at the start or end of the scanning, as the antenna is relatively far from the tag, the RF-signal is more seriously distorted, so we propose an adaptive algorithm to automatically filter outliers and keep remaining data for the later estimation. This paper presents the first study of using RFID to perform the 3D reconstruction on tagged packages. We make three contributions. First, for the 3D reconstruction on packages, we attach a set of passive RFID tags onto packages, and respectively handle issues of the package orientation and the package stacking through angle profiles of tags. We build an angle-profile-based model to depict the relationship between RF-signals of tags and the orientation/stacking status of packages. Second, we propose a mobile scanning approach to perform the 3D reconstruction of tagged packages via RFID. Generally, with the 1D mobile scanning, we can determine the package orientation and coarse-grained package stacking; while with the 2D mobile scanning, we can determine the fine-grained package stacking. Third, We implement a prototype system of RF-3DScan to evaluate its performance. Our experiment results in real settings show that RF-3DScan can achieve about 92.5% identification accuracy of the bottom face, and average error about 4.08◦ of the rotation angle. The 1D scanning is much easier to perform than the 2D scanning, while achieving the comparable performance in terms of the package stacking. 2 RELATED WORK 2.1 Computer Vision and Sensor-based Approach Computer-vision-based solutions mainly leverage the depth camera to perform 3D reconstruction of multiple objects [1, 2]. To avoid the blind angles in 3D reconstruction for specified objects, usually multiple depth cameras are deployed at different positions to perform multi-view reconstruction for their 3D models [2], or a moving depth camera is used to build the 3D models in a mobile approach [1]. In a word, these approaches suffer from the line-of-sight (LOS) constraint in 3D perception, and they are vulnerable to the limitation of the light intensity. Sensor-based solutions [3, 4] mainly attach the battery-powered sensors (such as inertial sensors or GPS modules) to the surface of the objects, and continuously monitor the 3D placement of specified objects, so as to track the orientation variation [3], or the stacking situation among multiple objects. However, they suffer from the high hardware cost of sensors, as well as the limited battery life of the sensor. 2.2 RFID-based Approach Orientation tracking: By attaching RFID tags onto the specified object, it is possible to track the orientation variation of the object according to the variation of the corresponding RF-signals [5–10]. Tagball [5] is proposed as a 3D humancomputer interaction system, where multiple passive tags are attached to a controlling ball, such that the motions of the ball from users can be detected from the phase changes of multiple tags. Tagyro [6] attaches an array of passive RFID tags as orientation sensors on the objects, by transforming the runtime phase offsets between tags into the orientation angle. Compared with our RF-3DScan system, these approaches track the orientation variation of the dynamically moving objects, whereas our approach aims to determine the orientation of statically placed packages. Localization: RFID localization generally falls into two categories: absolute localization [11–17] and relative localization [18–25]. By attaching multiple tags and pinpointing
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 each tag's 3D coordinates,the absolute localization can be 45 tailored to our problem for 3D reconstruction.However,this approach suffers from the complicated system deployment or the high computational complexity.For example,the state-of-the-art absolute localization schemes Tagoram [13] and RFind [15]are able to achieve the cm-level localization accuracy,however,they require either high computation overhead or dedicated device calibration,which are unfit 60120180240300360 Rotation (deg.) for estimating many packages concurrently.In addition,the localization work focuses on pinpointing only a single tag, (a)Rotate along the Z axis (b)Phase change during rotation how to estimate the package placement with the tag array Fig.2.Measured phase of a single tag rotating along the Z axis is still under-investigated.Rather than the absolute localiza- tion of a single tag,our approach utilizes the tag array to provide the localization result,which can achieve the com- parable performance without the above limits.Moreover, the relative localization investigates the relative locations of objects as opposed to absolute coordinates.STPP [19]is the first work to tackle the 2D relative localization.It investi- △d≈ △ds gates the spatial-temporal dynamics with phase profiles.A d x cosa d x cosa Moving V-zone (comprised of phase sequences)based solution is direction proposed to determine the relative localization of tagged A1 d P2 objects in the 2D plane.However,STPP cannot always get Fig.3.Angle-of-Arrival in static Fig.4.Angle-of-Arrival in mobile a V-zone in practice,especially when the sampling rate of scanning scanning per tag is low (due to many tags)or there are some dead zones of the RFID communication.Unlike STPP,regardless Fig.2 plots the phase change when a tag rotates along the of the V-zone,our work takes full advantages of all phase Z axis.It shows that the phase varies continuously over the measurements for localization and 3D reconstruction. rotation.Next,we discuss how to use the angle-of-arrival approach to overcome above three challenges,and benefit ANGLE-PROFILE-BASED MODELING our system design in the sequel. In this section,we first discuss the limitations of directly using phase values,and introduce how to use the phase dif- 3.2 Angle Profile ference to model the angle profile for the 3D reconstruction. Angle-of-Arrival (AoA)is one of the most popular RF-based localization measurements using phase difference.The basic idea of our approach is that by moving the antenna to scan 3.1 Limitations of Phase-based Measurement the tags,we extract phase differences from the specified tags The RF phase is a widely used attribute of the wireless at different time points,then we derive the geometry angles signal that reflects the phase offset between the received between the tag and the mobile antenna when the antenna electromagnetic wave and the emitted one,ranging from is at different positions,which is called angle profile. 0 to 2m.Due to the ultra-high working frequency in RFIDs and fine-grained measurement resolution of phase values by 3.2.1 Angle in Static Scanning COTS readers,the phase is very sensitive to the distance be- As shown in Fig.3,a tag is set at T,A and A2 are two tween the antenna and the tag,which gives us the potential antennas separated by d,M is the middle point of A1A2.V chance to achieve the accurate 3D reconstruction.Suppose is the projected point of T on the antenna pair line A1A2, s is the distance between the antenna and the tag.Since the the perpendicular distance is h.The included angle between backscatter communication of RFID is round-trip,the signal line TM and line MV is the AoA for tag T at position M, totally traverses a distance of 2s in each communication. denoted as a.Let dr.A and dr.A2 represent the distances Besides the distance,some hardware characteristics will also between T and the antennas,the antennas collect the phases distort the phase value.Hence,the phase6 reported by the as 0A:and 0A2,respectively.0A1,0A2 E [0,2). reader can be expressed as: The phase difference is related to the distance difference 2π from the tag to the antennas.When h>d,the relationship ×2s+7 mod2π between the phase difference (A0=0A:-0A2+n,0n means the phase offset caused by the hardware characteristics of A where A is the wavelength,n represents the phase offset and A2)and the distance difference (Ad dr.A:-dr.A2 caused by the hardware characteristics. dcosa)can be approximated as: Although the phase accurately reflects the distance,we face three challenges before putting it into use:1)The distort 2dcosaA0 (1) 入 2π +n, factor n caused by the physical hardware is unknown;2)The phase value repeats periodically,it is not feasible to use it wherencan be any integer in【-头-尝，装-L,its directly;3)In addition to s and n,our extensive experiments range isd.Whend<,the value range ofn is smaller than show that the tag orientation influences the phase value 6. 1,which means n has a unique value,so a is deterministic
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 3 each tag’s 3D coordinates, the absolute localization can be tailored to our problem for 3D reconstruction. However, this approach suffers from the complicated system deployment or the high computational complexity. For example, the state-of-the-art absolute localization schemes Tagoram [13] and RFind [15] are able to achieve the cm-level localization accuracy, however, they require either high computation overhead or dedicated device calibration, which are unfit for estimating many packages concurrently. In addition, the localization work focuses on pinpointing only a single tag, how to estimate the package placement with the tag array is still under-investigated. Rather than the absolute localization of a single tag, our approach utilizes the tag array to provide the localization result, which can achieve the comparable performance without the above limits. Moreover, the relative localization investigates the relative locations of objects as opposed to absolute coordinates. STPP [19] is the first work to tackle the 2D relative localization. It investigates the spatial-temporal dynamics with phase profiles. A V-zone (comprised of phase sequences) based solution is proposed to determine the relative localization of tagged objects in the 2D plane. However, STPP cannot always get a V-zone in practice, especially when the sampling rate of per tag is low (due to many tags) or there are some dead zones of the RFID communication. Unlike STPP, regardless of the V-zone, our work takes full advantages of all phase measurements for localization and 3D reconstruction. 3 ANGLE-PROFILE-BASED MODELING In this section, we first discuss the limitations of directly using phase values, and introduce how to use the phase difference to model the angle profile for the 3D reconstruction. 3.1 Limitations of Phase-based Measurement The RF phase is a widely used attribute of the wireless signal that reflects the phase offset between the received electromagnetic wave and the emitted one, ranging from 0 to 2π. Due to the ultra-high working frequency in RFIDs and fine-grained measurement resolution of phase values by COTS readers, the phase is very sensitive to the distance between the antenna and the tag, which gives us the potential chance to achieve the accurate 3D reconstruction. Suppose s is the distance between the antenna and the tag. Since the backscatter communication of RFID is round-trip, the signal totally traverses a distance of 2s in each communication. Besides the distance, some hardware characteristics will also distort the phase value. Hence, the phase θ reported by the reader can be expressed as: θ = 2π λ × 2s + η mod 2π, where λ is the wavelength, η represents the phase offset caused by the hardware characteristics. Although the phase accurately reflects the distance, we face three challenges before putting it into use: 1) The distort factor η caused by the physical hardware is unknown; 2) The phase value repeats periodically, it is not feasible to use it directly; 3) In addition to s and η, our extensive experiments show that the tag orientation influences the phase value θ. ͵Ͳι Ͳι Ͳ ι ͻͲι Ͳ ι ͵Ͳι Ͳι ͻͲι (a) Rotate along the Z axis 0 60 120 180 240 300 360 Rotation (deg.) 1 1.5 2 2.5 3 3.5 4 4.5 Phase (rad.) (b) Phase change during rotation Fig. 2. Measured phase of a single tag rotating along the Z axis 1 2 -. 3 . × cos2 )" )& 4 5 6 . Fig. 3. Angle-of-Arrival in static scanning ) 1 2 -. 3 . × cos2 " & 4 5 . 6789:; direction Fig. 4. Angle-of-Arrival in mobile scanning Fig. 2 plots the phase change when a tag rotates along the Z axis. It shows that the phase varies continuously over the rotation. Next, we discuss how to use the angle-of-arrival approach to overcome above three challenges, and benefit our system design in the sequel. 3.2 Angle Profile Angle-of-Arrival (AoA) is one of the most popular RF-based localization measurements using phase difference. The basic idea of our approach is that by moving the antenna to scan the tags, we extract phase differences from the specified tags at different time points, then we derive the geometry angles between the tag and the mobile antenna when the antenna is at different positions, which is called angle profile. 3.2.1 Angle in Static Scanning As shown in Fig. 3, a tag is set at T, A1 and A2 are two antennas separated by d, M is the middle point of A1A2. V is the projected point of T on the antenna pair line A1A2, the perpendicular distance is h. The included angle between line TM and line MV is the AoA for tag T at position M, denoted as α. Let dT ,A1 and dT ,A2 represent the distances between T and the antennas, the antennas collect the phases as θA1 and θA2 , respectively. θA1 , θA2 ∈ [0, 2π). The phase difference is related to the distance difference from the tag to the antennas. When h d, the relationship between the phase difference (∆θ = θA1−θA2+θη, θη means the phase offset caused by the hardware characteristics of A1 and A2) and the distance difference (∆d = dT ,A1 − dT ,A2 ' d cos α) can be approximated as: 2d cos α λ = ∆θ 2π + n, (1) where n can be any integer in − 2d λ − ∆θ 2π , 2d λ − ∆θ 2π , its range is 4d λ . When d < λ 4 , the value range of n is smaller than 1, which means n has a unique value, so α is deterministic.
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 Perpendicular cota distance T2 Equal angle point T 0 T Perpendkcular point Ty Moving a Moving distance OEqual angle Perpendicular A distance Fig.6.Model of the angle profile point point Fig.5.Metrics of the angle profile 3.4 Model of Angle Profile To depict the angle-profile-based measurement metrics in 3.2.2 Angle in Mobile Scanning mathematics,we build a linear model to derive the metrics As for multiple antennas,the phase offsets related to their from the angle profile automatically.Considering Fig.4,the own hardware characteristics are different,so it is hard to angle-of-arrival can be expressed as: determine 0n.Hence,we prefer a mobile antenna to multiple static antennas,in which case can be canceled. cot a= V-A (2) h For a mobile antenna,the angle-of-arrival is a little different.Without the loss of generality,we redefine the AoA where cot means the cotangent function,h is the perpen- in a mobile case,as shown in Fig.4.Similarly,T is the tag dicular distance between the tag and the antenna moving position and V is its projected point on the antenna moving trace.yA and yv represent the coordinates of point A and line,its perpendicular distance is h.Let the mobile antenna V along the antenna moving direction.Assume there is an be at position A,then the included angle of line TA and the antenna starting point S,the distance from S to V is lo,the antenna moving direction is just the angle-of-arrival (a)for antenna moved distance is l.Thus,(lo-l)represents the the tag when the antenna is at position A. distance from the antenna to the perpendicular point(same To estimate the angle at position A,we only need the as (yv -yA)),the angle can be rewritten as: phases collected at the two nearby positions(P and P2), 1 centered on the antenna(P1A AP2).Thus,the phase cota=L+b,k=-6s场 h (3) difference at position P and P2 can be used to estimate where the slope k is related to the minus reciprocal of h,the a with Eq.(1).By combining the angles at different antenna intercept b depends on the ratio of lo and h. positions,we can derive an angle profile for a specified tag. Taking the tags in Fig.5,the transformed angle expres- sion based on Eg.(3)should look like the lines shown 3.3 Metrics of Angle Profile in Fig.6.As l increases continuously during the moving process,a increases as well.When the antenna reaches the Suppose there are two tags and one antenna in the same perpendicular point,a is equal to /2,so cot a=0.The line plane (Fig.5).The antenna moves linearly from O to A, of T reaches 0 earlier than T2.Thus,the order of such zero so it passes through Ti first,followed by T2.When the points are corresponding to the tags'perpendicular points, antenna passes through the tag(corresponding to point V and the spacing between two zero points just reflects the in Fig.4),the angle-of-arrival (a)of that tag reaches /2, separation of tags'perpendicular points.In addition,the naming this point as the perpendicular point.Similarly,we call intersection of the two lines represents the position where the distance from the tag to the perpendicular point perpen- the tags are projected on the same line with the antenna, dicular distance,the direction perpendicular to the antenna corresponding to the equal angle point.Specifically,the moving direction as perpendicular direction.As T is on the smaller h is,the larger is,and the sharper the line is. left along the antenna moving direction,its perpendicular As the h of Ti is smaller than T2,the of Ti is larger,so point shows earlier than T2.Hence,the perpendicular point the line of n decreases faster than T2. is the key metric for the tags'relative positions along the For a certain tag,its angle profile records its angles moving direction. at different positions,as {(cot ai,li)},i=1,2,...,n,n Besides the perpendicular point,there is the other special represents the amount of samples.As described in Section point:equal angle point.The equal angle point is where the 3.2.2,it is easy to obtain cot a;at a specific position with the antenna and the two tags are in the same line,so Ti and separation distance and the phase difference of two nearby T2 share the same angle.Before equal point,the angle of positions,here comes a new question,how to determine T1 is smaller than the angle of T2.On the contrary,the the location of the antenna during the moving process? angle of Ti changes to be bigger than that of T2 after the Actually,we only care about the relative position of the equal angle point.No matter for Ti or T2,its angle increases antenna along the linear scanning direction when it collects continuously during the antenna moving process,so it is data,we need not the absolute position of the antenna in obvious that the angle of Ti changes faster than that of the 3D space,but we require to know the relative moving T2.Such phenomenon is due to the smaller perpendicular distance along the scanning direction so as to determine the distance of T1.Thus,according to the angle change rate, value of li in the angle profile.Note that,it is the relative we can determine the tags'relative positions along the positions among tags that matters,so we can randomly set perpendicular direction. a position along the linear scanning direction as the starting
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 4 ܶଵ ߙ ߙ ߙ ᇱ ᇱᇱ ଵߙ ଶߙ ଵߙ Ԣ ଶߙ Ԣ ݄ଶ ݄ଵ ܶଶ ܶଵ ܣ ܱ ܶଶ ܶଵ ߙ Ͳ Fig. 5. Metrics of the angle profile 3.2.2 Angle in Mobile Scanning As for multiple antennas, the phase offsets related to their own hardware characteristics are different, so it is hard to determine θη. Hence, we prefer a mobile antenna to multiple static antennas, in which case θη can be canceled. For a mobile antenna, the angle-of-arrival is a little different. Without the loss of generality, we redefine the AoA in a mobile case, as shown in Fig. 4. Similarly, T is the tag position and V is its projected point on the antenna moving line, its perpendicular distance is h. Let the mobile antenna be at position A, then the included angle of line T A and the antenna moving direction is just the angle-of-arrival (α) for the tag when the antenna is at position A. To estimate the angle at position A, we only need the phases collected at the two nearby positions (P1 and P2), centered on the antenna (P1A = AP2). Thus, the phase difference at position P1 and P2 can be used to estimate α with Eq. (1). By combining the angles at different antenna positions, we can derive an angle profile for a specified tag. 3.3 Metrics of Angle Profile Suppose there are two tags and one antenna in the same plane (Fig. 5). The antenna moves linearly from O to A, so it passes through T1 first, followed by T2. When the antenna passes through the tag (corresponding to point V in Fig. 4), the angle-of-arrival (α) of that tag reaches π/2, naming this point as the perpendicular point. Similarly, we call the distance from the tag to the perpendicular point perpendicular distance, the direction perpendicular to the antenna moving direction as perpendicular direction. As T1 is on the left along the antenna moving direction, its perpendicular point shows earlier than T2. Hence, the perpendicular point is the key metric for the tags’ relative positions along the moving direction. Besides the perpendicular point, there is the other special point: equal angle point. The equal angle point is where the antenna and the two tags are in the same line, so T1 and T2 share the same angle. Before equal point, the angle of T1 is smaller than the angle of T2. On the contrary, the angle of T1 changes to be bigger than that of T2 after the equal angle point. No matter for T1 or T2, its angle increases continuously during the antenna moving process, so it is obvious that the angle of T1 changes faster than that of T2. Such phenomenon is due to the smaller perpendicular distance of T1. Thus, according to the angle change rate, we can determine the tags’ relative positions along the perpendicular direction. ܶଵ ߙ ߙ ߙ ᇱ ᇱᇱ ଵߙ ଶߙ ଵߙ Ԣ ଶߙ Ԣ ݄ଶ ݄ଵ ܶଶ ܶଵ ܣ ܱ ܶଶ ܶଵ ߙ Ͳ Fig. 6. Model of the angle profile 3.4 Model of Angle Profile To depict the angle-profile-based measurement metrics in mathematics, we build a linear model to derive the metrics from the angle profile automatically. Considering Fig. 4, the angle-of-arrival can be expressed as: cot α = yV − yA h , (2) where cot means the cotangent function, h is the perpendicular distance between the tag and the antenna moving trace. yA and yV represent the coordinates of point A and V along the antenna moving direction. Assume there is an antenna starting point S, the distance from S to V is l0, the antenna moved distance is l. Thus, (l0 − l) represents the distance from the antenna to the perpendicular point (same as (yV − yA)), the angle can be rewritten as: cot α = kl + b, k = − 1 h , b = l0 h , (3) where the slope k is related to the minus reciprocal of h, the intercept b depends on the ratio of l0 and h. Taking the tags in Fig. 5, the transformed angle expression based on Eq. (3) should look like the lines shown in Fig. 6. As l increases continuously during the moving process, α increases as well. When the antenna reaches the perpendicular point, α is equal to π/2, so cot α = 0. The line of T1 reaches 0 earlier than T2. Thus, the order of such zero points are corresponding to the tags’ perpendicular points, and the spacing between two zero points just reflects the separation of tags’ perpendicular points. In addition, the intersection of the two lines represents the position where the tags are projected on the same line with the antenna, corresponding to the equal angle point. Specifically, the smaller h is, the larger kkk is, and the sharper the line is. As the h of T1 is smaller than T2, the kkk of T1 is larger, so the line of T1 decreases faster than T2. For a certain tag, its angle profile records its angles at different positions, as {(cot αi , li)}, i = 1, 2, ..., n, n represents the amount of samples. As described in Section 3.2.2, it is easy to obtain cot αi at a specific position with the separation distance and the phase difference of two nearby positions, here comes a new question, how to determine the location of the antenna during the moving process? Actually, we only care about the relative position of the antenna along the linear scanning direction when it collects data, we need not the absolute position of the antenna in the 3D space, but we require to know the relative moving distance along the scanning direction so as to determine the value of li in the angle profile. Note that, it is the relative positions among tags that matters, so we can randomly set a position along the linear scanning direction as the starting
EEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 point.Then based on the moving distance from the starting Moving point,we get the value of li at any time ti.After extracting direction h2 the angle profile,referring to Eq.(3),we are able to estimate T2 the two unknown parameters h and lo through the linear fitting method.Specifically,h depends on the perpendicular h distance between the tag and the antenna moving trace. lo is related to the projected position where the antenna passes through the tag,the larger lo is,the later that line reaches 0,and the tag is more ahead along the antenna moving direction.Thus,by leveraging these properties,we Fig.7. Localization based on the tag array can determine tags'relative positions with the following two principles: Preprocess Determine Determine 1) The value of reflects the perpendicular distance package orientation package stacking Angle computation h from the tag to the antenna moving trace:the RF (single) (multiple) larger,the smaller the perpendicular distance. Signals Angle smoothing 2) The value of lo determines the projected position ·Bottom/top face Linear fitting Relative stacking of the corresponding tag along the antenna moving ·Rotation angle situation direction.The difference of lo between two tags indi- Fig.8.Architecture of RF-3DScan cates their interval in the antenna moving direction. Product Code (EPC)of each attached tag.Based on the 3.5 Localization based on Angle Profile with Tag Array tag's EPC from RF-signals,it is easy to obtain the extensive corresponding package information.Specially,the tagged With angle profiles of each tag,we obtain the perpendicular packages ought to be produced by machines in the real distance and projected position along the scanning direction logistic industry,that is,the priori knowledge is determined of each tag.The perpendicular distance is related to the position of the tag,including the height difference and the by the designer,so it is easy to obtain such priori knowledge without extra labors for acquisition.Aiming at using as depth of the tag from the antenna.Although it is hard to fewer tags as possible to depict the package uniquely,accu- decompose the perpendicular distance to get the height rately and conveniently,the tag deployment should obey the difference and depth of each tag,we can localize each tag two design rules in Section 4.3.1.Meanwhile,we make the by taking these tags as a whole,which has the known tag following assumptions:1)The antenna moves at a constant separation distances along each axes in a certain coordinate speed;2)Each package is a standard cube,and they are fully system.Specifically,taking a tag array with two tags for on the ground or parallel to the ground (on the ground is a example,if the separation distances of two tags along the special case of parallel to the ground). orthogonal directions of the antenna scanning direction are Fig.8 illustrates the architecture of RF-3DScan.RF- known,the positions of the two tags can be obtained based 3DScan takes RF-signals from the tags as input,then out- on their perpendicular distances.As shown in Fig.7,the puts 3D profiles for multiple packages.The whole system antenna moves along the Y axis,the tag separation distances consists of three components:1)Preprocess:With RF-signals of Ti and T2 along the X and Z axes are△rand△z, from the tags,RF-3DScan builds angle profiles by using and the perpendicular distances of Ti and T2 are hi and the phase differences at different time points for each tag, h2,respectively.Assume the depth and height difference and extracts position indicators from angle profiles for the from Ti to the antenna moving trace are d and d:,the relative localization among tags by linear fitting.2)Deter- perpendicular distances can be represented as: mine package orientation for a single package:By comparing h好=d+d, the relative positions of tags on a specified package,RF- (4) 3DScan can determine which side of the package is on the h=(d+△x)2+(d2-△z)2, ground,and then evaluates the angle of the vertical sides in where hi and h2 are extracted from angle profiles of each a specified coordinate system.3)Determine package stacking tag,Ax and Az are known according to the tag array layout for multiple packages:After deriving the orientation of a single and the package orientation,so (dr,d=)can be computed package,the centers of the packages are also determined using Eq.(4).Meanwhile,as the projected point of the tag along the scanning direction.By performing a 2D mobile along the scanning direction is extracted from the angle pro- scanning,RF-3DScan combines the results from the two file,its position along the Y axis is obtained,so the relative orthogonal scanning,so the accurate relative positions of position of the tag in the 3D space is totally determined. these packages in the 3D space can be determined.Note that,based on the tag array localization,using only 1D scanning can also achieve the comparable performance. SYSTEM DESIGN 4.1 System Overview 4.2 Data Preprocess RF-3DScan is a 3D reconstruction system for tagged pack-With raw RF-signals,we need to process the collected data ages via RFID.In RF-3DScan,the information of each pack- and build angle profiles of tags.The preprocessing can be age is priori and stored in the database individually,includ-divided into three steps:angle computation,angle smooth- ing the package size,the position and unique Electronic ing and linear fitting
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 5 point. Then based on the moving distance from the starting point, we get the value of li at any time ti . After extracting the angle profile, referring to Eq. (3), we are able to estimate the two unknown parameters h and l0 through the linear fitting method. Specifically, h depends on the perpendicular distance between the tag and the antenna moving trace. l0 is related to the projected position where the antenna passes through the tag, the larger l0 is, the later that line reaches 0, and the tag is more ahead along the antenna moving direction. Thus, by leveraging these properties, we can determine tags’ relative positions with the following two principles: 1) The value of kkk reflects the perpendicular distance h from the tag to the antenna moving trace: the larger kkk, the smaller the perpendicular distance. 2) The value of l0 determines the projected position of the corresponding tag along the antenna moving direction. The difference of l0 between two tags indicates their interval in the antenna moving direction. 3.5 Localization based on Angle Profile with Tag Array With angle profiles of each tag, we obtain the perpendicular distance and projected position along the scanning direction of each tag. The perpendicular distance is related to the position of the tag, including the height difference and the depth of the tag from the antenna. Although it is hard to decompose the perpendicular distance to get the height difference and depth of each tag, we can localize each tag by taking these tags as a whole, which has the known tag separation distances along each axes in a certain coordinate system. Specifically, taking a tag array with two tags for example, if the separation distances of two tags along the orthogonal directions of the antenna scanning direction are known, the positions of the two tags can be obtained based on their perpendicular distances. As shown in Fig. 7, the antenna moves along the Y axis, the tag separation distances of T1 and T2 along the X and Z axes are ∆x and ∆z, and the perpendicular distances of T1 and T2 are h1 and h2, respectively. Assume the depth and height difference from T1 to the antenna moving trace are dx and dz, the perpendicular distances can be represented as: ( h 2 1 = d 2 x + d 2 z , h 2 2 = (dx + ∆x) 2 + (dz − ∆z) 2 , (4) where h1 and h2 are extracted from angle profiles of each tag, ∆x and ∆z are known according to the tag array layout and the package orientation, so (dx, dz) can be computed using Eq. (4). Meanwhile, as the projected point of the tag along the scanning direction is extracted from the angle pro- file, its position along the Y axis is obtained, so the relative position of the tag in the 3D space is totally determined. 4 SYSTEM DESIGN 4.1 System Overview RF-3DScan is a 3D reconstruction system for tagged packages via RFID. In RF-3DScan, the information of each package is priori and stored in the database individually, including the package size, the position and unique Electronic Moving direction Y X Z 01 02 ℎ2 ∆4 ℎ1 67 68 ∆9 Fig. 7. Localization based on the tag array ݄ ݈ Preprocess Angle computation Linear fitting Angle smoothing RF Signals Determine package orientation (single) Determine package stacking (multiple) • Bottom / top face • Rotation angle Relative stacking situation Fig. 8. Architecture of RF-3DScan Product Code (EPC) of each attached tag. Based on the tag’s EPC from RF-signals, it is easy to obtain the extensive corresponding package information. Specially, the tagged packages ought to be produced by machines in the real logistic industry, that is, the priori knowledge is determined by the designer, so it is easy to obtain such priori knowledge without extra labors for acquisition. Aiming at using as fewer tags as possible to depict the package uniquely, accurately and conveniently, the tag deployment should obey the two design rules in Section 4.3.1. Meanwhile, we make the following assumptions: 1) The antenna moves at a constant speed; 2) Each package is a standard cube, and they are fully on the ground or parallel to the ground (on the ground is a special case of parallel to the ground). Fig. 8 illustrates the architecture of RF-3DScan. RF- 3DScan takes RF-signals from the tags as input, then outputs 3D profiles for multiple packages. The whole system consists of three components: 1) Preprocess: With RF-signals from the tags, RF-3DScan builds angle profiles by using the phase differences at different time points for each tag, and extracts position indicators from angle profiles for the relative localization among tags by linear fitting. 2) Determine package orientation for a single package: By comparing the relative positions of tags on a specified package, RF- 3DScan can determine which side of the package is on the ground, and then evaluates the angle of the vertical sides in a specified coordinate system. 3) Determine package stacking for multiple packages: After deriving the orientation of a single package, the centers of the packages are also determined along the scanning direction. By performing a 2D mobile scanning, RF-3DScan combines the results from the two orthogonal scanning, so the accurate relative positions of these packages in the 3D space can be determined. Note that, based on the tag array localization, using only 1D scanning can also achieve the comparable performance. 4.2 Data Preprocess With raw RF-signals, we need to process the collected data and build angle profiles of tags. The preprocessing can be divided into three steps: angle computation, angle smoothing and linear fitting
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 6 4.2.1 Angle Computation Algorithm 1 Linear Fitting to Extract Position Indicators. As the antenna collects phases at different time points dur- Input: ing its mobile scanning,we can extract the phase differences The angle profile of a certain tag,{(cot i,li)}; for a tag at different positions.Using these phase differences, The threshold of angle difference,6m; we compute the angle-of-arrivals with Eq.(1).To get a The threshold of separation interval,lm; deterministic angle,as mentioned above,the distance of the The threshold of sample length,Lmi positions among two phases should be within A/4. Output: Position indicators,h and lo; 4.2.2 Angle Smoothing 1:Do the linear fitting with the angle profile {(cot ai,li) Although using the phase difference from two positions based on Eq.(3),and get the fitted angle profile with small separation can get a unique angle,the noise like {(cot i,li)).For each sample i,compute the absolute the multi-path effect would influence the phase measure- angle differences 6;cot ai-cot ill; ment,there would exist the large fluctuation among angles, 2:while the maximum value of f>m do so the angle smoothing is required.Usually,the phase 3 Calculate the temporary angle difference threshold: collected by the antenna is not uniform,so is the angle dis- 6:max(om,the biggest decile of foi); tribution,thus it is not suitable to use the common smooth Remove all outliers with i>6t in the angle profile; algorithms,e.g.,low-pass filter.Taking the noise u into 5: onr:cosa=a驶+2，whendis very smal山4 Check the continuity of the angle profile,if the sep- aration interval between two neighbor samples is larger has much influence on cosa.While when d increases,such than lm,split samples and keep the major continuous distortion effect decreases,but there exist redundant angles part; in the results,only one of them is the true value.Hence,we 6: Redo the linear fitting with the remaining samples, can derive two sets of angles from two phase separations:a and compute the new angle differences [} small one and a large one,then use the unique angles from 7:end while the small separation to filter the several angle candidates 8:if the length of remaining samples >Lm then from the large separation,hence,we get a relative accurate 9: Calculate position indicators h and lo according to angle profile with less fluctuation [18].Note that,too large the final linear fitting result based on Eq.(3); separation will bring too much environmental change and 10 return h and lo; break the restraint of the angle estimation method.Thus, 11:else we set the small separation around 5-8cm and the large 12: Abandon this angle profile; separation within 15cm empirically when the antenna is in 13: return front of the packages about 1m. 14:end if 4.2.3 Linear Fitting With smoothed angles at different positions from an angle profile for a certain tag,we can use the linear model as Eq.(3)to fit them iteratively,then derive the two important position indicators(h and lo)of that tag for the later 3D reconstruction,details are depicted in Algorithm 1. Due to the ambient noise in the environment,the angle ◆-Original data profile contains outliers which may mislead the linear fitting Original linear fitting result,thus we need to figure out these outliers and elimi- Processed data -Processed linear fitting nate them to extract accurate position indicators.Denote the angle profile of a certain tag as {(cot i,li)},the fitted angle 0.5 1 15 2.5 profile based on Eq.(3)as {(coti,i)}.If the absolute angle Distance(m) difference of sample i,i.e.,cot a;-cot ill,is larger than Fig.9.Linear fitting with original data and final processed data angle difference threshold 6m,we take sample i as an outlier candidate.Considering that outliers affect the linear fitting no outliers.After the linear fitting process,if there are not result,some normal samples may be identified as outliers enough remaining samples,which means angles fluctuate due to the inaccurate fitting line,thus we automatically seriously all the time,we abandon such an angle profile set the temporary angle difference threshold based on the of the tag to improve the whole accuracy.Otherwise,we distribution of angle differences.Empirically,we select the calculate the position indicators h and lo from the final linear larger value between 6m and the biggest decile of the angle fitting result,where h represents the perpendicular distance difference [as the temporary angle difference threshold from the tag to the antenna mobile trace and lo reflects 6t,and om is set to 0.12 in our experiments.Hence,we re- the projected tag position along the scanning direction.In move all outliers whose angle differences are larger than our experiments,we set the separation interval threshold as Due to the outliers elimination,the origin sample sequence 0.6m under the moving speed of 0.12m/s and the sample can be noncontinuous,i.e.,the separation interval between length threshold as 200.Taking Fig.9 for example,the two neighbor samples is larger than a separation interval blue original angles contain several outliers and using our threshold Im.In this situation,we only keep the central algorithm can effectively eliminate them at both ends,the major part of the continuous samples,and use these remain- remaining yellow angles are much more smoother.The ing samples to redo the linear fitting process until there are position indicators (h,lo)from the original data and the
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 6 4.2.1 Angle Computation As the antenna collects phases at different time points during its mobile scanning, we can extract the phase differences for a tag at different positions. Using these phase differences, we compute the angle-of-arrivals with Eq. (1). To get a deterministic angle, as mentioned above, the distance of the positions among two phases should be within λ/4. 4.2.2 Angle Smoothing Although using the phase difference from two positions with small separation can get a unique angle, the noise like the multi-path effect would influence the phase measurement, there would exist the large fluctuation among angles, so the angle smoothing is required. Usually, the phase collected by the antenna is not uniform, so is the angle distribution, thus it is not suitable to use the common smooth algorithms, e.g., low-pass filter. Taking the noise µ into consideration: cos α = λ 2d ∆θ+µ 2π + nλ 2d , when d is very small, µ has much influence on cos α. While when d increases, such distortion effect decreases, but there exist redundant angles in the results, only one of them is the true value. Hence, we can derive two sets of angles from two phase separations: a small one and a large one, then use the unique angles from the small separation to filter the several angle candidates from the large separation, hence, we get a relative accurate angle profile with less fluctuation [18]. Note that, too large separation will bring too much environmental change and break the restraint of the angle estimation method. Thus, we set the small separation around 5-8cm and the large separation within 15cm empirically when the antenna is in front of the packages about 1m. 4.2.3 Linear Fitting With smoothed angles at different positions from an angle profile for a certain tag, we can use the linear model as Eq. (3) to fit them iteratively, then derive the two important position indicators (h and l0) of that tag for the later 3D reconstruction, details are depicted in Algorithm 1. Due to the ambient noise in the environment, the angle profile contains outliers which may mislead the linear fitting result, thus we need to figure out these outliers and eliminate them to extract accurate position indicators. Denote the angle profile of a certain tag as {(cot αi , li)}, the fitted angle profile based on Eq. (3) as {(cotdαi , li)}. If the absolute angle difference of sample i, i.e., k cot αi − cotdαik, is larger than angle difference threshold δm, we take sample i as an outlier candidate. Considering that outliers affect the linear fitting result, some normal samples may be identified as outliers due to the inaccurate fitting line, thus we automatically set the temporary angle difference threshold based on the distribution of angle differences. Empirically, we select the larger value between δm and the biggest decile of the angle difference {δi} as the temporary angle difference threshold δt, and δm is set to 0.12 in our experiments. Hence, we remove all outliers whose angle differences are larger than δt. Due to the outliers elimination, the origin sample sequence can be noncontinuous, i.e., the separation interval between two neighbor samples is larger than a separation interval threshold lm. In this situation, we only keep the central major part of the continuous samples, and use these remaining samples to redo the linear fitting process until there are Algorithm 1 Linear Fitting to Extract Position Indicators. Input: The angle profile of a certain tag, {(cot αi , li)}; The threshold of angle difference, δm; The threshold of separation interval, lm; The threshold of sample length, Lm; Output: Position indicators, h and l0; 1: Do the linear fitting with the angle profile {(cot αi , li)} based on Eq. (3), and get the fitted angle profile {(cotdαi , li)}. For each sample i, compute the absolute angle differences δi = k cot αi − cotdαik; 2: while the maximum value of {δi} > δm do 3: Calculate the temporary angle difference threshold: δt = max(δm, the biggest decile of {δi}); 4: Remove all outliers with δi > δt in the angle profile; 5: Check the continuity of the angle profile, if the separation interval between two neighbor samples is larger than lm, split samples and keep the major continuous part; 6: Redo the linear fitting with the remaining samples, and compute the new angle differences {δi}; 7: end while 8: if the length of remaining samples > Lm then 9: Calculate position indicators h and l0 according to the final linear fitting result based on Eq. (3); 10: return h and l0; 11: else 12: Abandon this angle profile; 13: return ; 14: end if 0 0.5 1 1.5 2 2.5 Distance (m) -4 -2 0 2 cot Original data Original linear fitting Processed data Processed linear fitting Fig. 9. Linear fitting with original data and final processed data no outliers. After the linear fitting process, if there are not enough remaining samples, which means angles fluctuate seriously all the time, we abandon such an angle profile of the tag to improve the whole accuracy. Otherwise, we calculate the position indicators h and l0 from the final linear fitting result, where h represents the perpendicular distance from the tag to the antenna mobile trace and l0 reflects the projected tag position along the scanning direction. In our experiments, we set the separation interval threshold as 0.6m under the moving speed of 0.12m/s and the sample length threshold as 200. Taking Fig. 9 for example, the blue original angles contain several outliers and using our algorithm can effectively eliminate them at both ends, the remaining yellow angles are much more smoother. The position indicators (h, l0) from the original data and the
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 (a)Rulel (b)Rule2 (c)Possible solution Linear Scanning Fig.10.Rules of deploying tags Fig.11.Experiment setup of linear fitting accuracy with different tag orientations final processed data are (1.4m,1.42m)and (1.23m,1.47m), respectively.Compared to ground-truth (1.3m,1.46m),the 15 accuracy improves a lot with the outliers elimination. 4.3 Determine Package Orientation for Each Single Package To reconstruct a single package,it makes the same sense to determine the package orientation,so we just need to iden- T1-T2T3-T4T5-T6T1-T3T3-T5 TI T2 T3 T4 T5 T6 tify the bottom face of this package,and estimate the relative rotation angle of the vertical sides against the antenna Fig.12.Accuracy along scanning Fig.13.Accuracy along orthogo- direction nal direction of scanning plane in a specified coordinate system.Here,the "antenna plane"refers to the extended plane of the antenna's front Fig.10(c),the results are plotted in Fig.12 and Fig.13. surface,which should be perpendicular to the ground in our We observe that the accuracy of projected position lo along settings.When the antenna performs the mobile scanning the scanning direction keeps stable with different orientations, linearly,it is just in the antenna plane. while the perpendicular distance h does not have the same high accuracy as lo.Fig.12 plots the accuracy of lo along the 4.3.1 Tag Layout antenna scanning direction,i.e.,the absolute separation Aiming at determining the package orientation only by once error between two tags along the scanning direction.Most 1D mobile scanning,we need to deploy tags in an efficient of the absolute separation errors of different tag pairs are and robust way.The design principle of tag deployment is to below 1.8cm,even in the worst case,the separation achieves use as fewer tags as possible to depict the package uniquely, around 92.3%accuracy.Fig.13 plots the accuracy of the accurately and conveniently.Specifically,as the package perpendicular distance h along the orthogonal direction to can be with any orientation in the 3D space,we should the scanning.The error is much larger than the separation pay attention to ensuring there are always enough effective error along the scanning direction.For tags with the same tags reflecting the signals to the antenna.Meanwhile,as for orientation,the near-far relationships between tags and the identifying the bottom face of the package,it is the same to antenna are reliable,but for tags with different orientations, find which tags are along the vertical axis and what order the error may incur the wrong near-far relationship,i.e.,T3 these tags are with.Therefore,we make two rules as follows. has the smaller h than T2,but T3 has the larger estimated h. 1) The orientations of tags should be along different orthog- Therefore,when using position indicators,we can leverage onal axes(in Fig.10(a)).With this rule,tags along one the projected positions of tags with different orientations, direction at most are in the blind direction,so other and prefer the perpendicular distances of tags with the same tags can response to the antenna successfully. orientation for comparison or calculation. 2) Tags should be deployed along different orthogonal axes (in Fig.10(b)).With this rule,whatever the orienta- 4.3.3 Determine Package Orientation tion of the package is,there is always one tag pair To determine the package orientation,it demands to identify along the vertical axis. the bottom face of the package and the relative angle of the Combining the above two rules,Fig.10(c)illustrates vertical sides in a specified coordinate system.Considering a possible tag deployment satisfying these two rules.No our assumption that one side of the cube package must be matter what orientation the package is,there are four tags parallel to the ground,when we deploy tags like the solution at least to avoid the signal blind direction.Also,there is described in Fig.10(c),we can identify which tag pair is always one tag pair along the Z axis.By determining the along the Z axis and what order the tag pair is in fact.In tags'order of this tag pair,we can derive which side of the this case,let the antenna do the mobile scanning along the package is on the ground then. X or Y axis only once,we can determine the orientation for a single package.Note that,the antenna should be above 4.3.2 Linear Fitting of Tags with Different Orientations or below all the tags,and the package is at the same side Considering that tags in the layout as Fig.10(c)have against the antenna plane during the scanning process different orientations,we carry out experiments to check For simplicity,suppose the antenna is above all the tags whether different orientations among tags have effects on and ahead of all the tags along the X axis positive direction, the accuracy of the linear fitting.As shown in Fig.11,it moves along the y axis,then the tag pair along the Z we arrange six tags with three orientations as required in axis is perpendicular to the antenna scanning direction,so
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 7 X Z Y X (a) Rule1 Y X Z Y X (b) Rule2 Y X Z Y ! " # $ % & (c) Possible solution Fig. 10. Rules of deploying tags final processed data are (1.4m, 1.42m) and (1.23m, 1.47m), respectively. Compared to ground-truth (1.3m, 1.46m), the accuracy improves a lot with the outliers elimination. 4.3 Determine Package Orientation for Each Single Package To reconstruct a single package, it makes the same sense to determine the package orientation, so we just need to identify the bottom face of this package, and estimate the relative rotation angle of the vertical sides against the antenna plane in a specified coordinate system. Here, the “antenna plane” refers to the extended plane of the antenna’s front surface, which should be perpendicular to the ground in our settings. When the antenna performs the mobile scanning linearly, it is just in the antenna plane. 4.3.1 Tag Layout Aiming at determining the package orientation only by once 1D mobile scanning, we need to deploy tags in an efficient and robust way. The design principle of tag deployment is to use as fewer tags as possible to depict the package uniquely, accurately and conveniently. Specifically, as the package can be with any orientation in the 3D space, we should pay attention to ensuring there are always enough effective tags reflecting the signals to the antenna. Meanwhile, as for identifying the bottom face of the package, it is the same to find which tags are along the vertical axis and what order these tags are with. Therefore, we make two rules as follows. 1) The orientations of tags should be along different orthogonal axes (in Fig. 10(a)). With this rule, tags along one direction at most are in the blind direction, so other tags can response to the antenna successfully. 2) Tags should be deployed along different orthogonal axes (in Fig. 10(b)). With this rule, whatever the orientation of the package is, there is always one tag pair along the vertical axis. Combining the above two rules, Fig. 10(c) illustrates a possible tag deployment satisfying these two rules. No matter what orientation the package is, there are four tags at least to avoid the signal blind direction. Also, there is always one tag pair along the Z axis. By determining the tags’ order of this tag pair, we can derive which side of the package is on the ground then. 4.3.2 Linear Fitting of Tags with Different Orientations Considering that tags in the layout as Fig. 10(c) have different orientations, we carry out experiments to check whether different orientations among tags have effects on the accuracy of the linear fitting. As shown in Fig. 11, we arrange six tags with three orientations as required in 0.5 m 0.3 m 0.5 m 0.3 m 1 m Linear Scanning !" !# !$ !% !& !' Fig. 11. Experiment setup of linear fitting accuracy with different tag orientations T1-T2 T3-T4 T5-T6 T1-T3 T3-T5 0 1 2 3 4 Error (cm) Fig. 12. Accuracy along scanning direction T1 T2 T3 T4 T5 T6 0 5 10 15 Error (cm) Fig. 13. Accuracy along orthogonal direction of scanning Fig. 10(c), the results are plotted in Fig. 12 and Fig. 13. We observe that the accuracy of projected position l0 along the scanning direction keeps stable with different orientations, while the perpendicular distance h does not have the same high accuracy as l0. Fig. 12 plots the accuracy of l0 along the antenna scanning direction, i.e., the absolute separation error between two tags along the scanning direction. Most of the absolute separation errors of different tag pairs are below 1.8cm, even in the worst case, the separation achieves around 92.3% accuracy. Fig. 13 plots the accuracy of the perpendicular distance h along the orthogonal direction to the scanning. The error is much larger than the separation error along the scanning direction. For tags with the same orientation, the near-far relationships between tags and the antenna are reliable, but for tags with different orientations, the error may incur the wrong near-far relationship, i.e., T3 has the smaller h than T2, but T3 has the larger estimated h. Therefore, when using position indicators, we can leverage the projected positions of tags with different orientations, and prefer the perpendicular distances of tags with the same orientation for comparison or calculation. 4.3.3 Determine Package Orientation To determine the package orientation, it demands to identify the bottom face of the package and the relative angle of the vertical sides in a specified coordinate system. Considering our assumption that one side of the cube package must be parallel to the ground, when we deploy tags like the solution described in Fig. 10(c), we can identify which tag pair is along the Z axis and what order the tag pair is in fact. In this case, let the antenna do the mobile scanning along the X or Y axis only once, we can determine the orientation for a single package. Note that, the antenna should be above or below all the tags, and the package is at the same side against the antenna plane during the scanning process. For simplicity, suppose the antenna is above all the tags and ahead of all the tags along the X axis positive direction, it moves along the Y axis, then the tag pair along the Z axis is perpendicular to the antenna scanning direction, so
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 case2 (Fig.14(b)):h1>h3,h3 h5 and for the possible case3(Fig.14(c)):h1 >h3,h3>h5.There are multiple tag pairs for the comparison,here we list part of them for ex- planation.Then,by comparing the relationships of different tag pairs,we vote for the possible cases,and select the case with the highest score as our estimation result.Considering (a)Possible casel (b)Possible case2 (c)Possible case3 that different tags have different credibilities as they are Fig.14.Possible cases for the special package orientation influenced by the ambient noise to different extents,when voting for the relationships,we tend to allocate the heavier their perpendicular points should be the same.That is,the weight to the tag pair with the better linear fitting,such that, spacing of their perpendicular points equals 0 in theory. we set the voting weight of a tag pair with the reciprocal Hence,if the spacing of the perpendicular points for a tag average linear fitting error of the two tags.Moreover,if the pair is 0,it is probable that the tag pair is along the Z linear fitting error is large than the given threshold,that tag axis now,except for some special cases where there is a will be abandoned in the following analysis.Through the tag pair along the X axis,then there are two tag pairs that weighted voting,we can effectively avoid the ambiguous their perpendicular points spacings are equal to 0,we will situation that several relationships get the same scores so as discuss it later.After identifying which tag pair is along to improve the accuracy of the orientation estimation,the the Z axis,we can determine the tags'order by comparing corresponding experiments are referred to Fig.28. their perpendicular distances extracted from their angle profiles.As the antenna is above all the tags,the tag with 4.3.4 Discussion the smaller perpendicular distance of the vertical tag pair 1.There must be a side of the package parallel to the ground. should be above the other along the Z axis.However,such As we assume that there must be a side of the package comparison ignores the relationships of the perpendicular parallel to the ground(which means the package is on the distances for other tags,it is easy to make a wrong decision ground or on other packages,not tilted),thus the state of with only one comparison results.Note that,the spacings of the package is limited,the angle estimation is restricted to the perpendicular points of the tags should stay the same along the Z axis.If not,the searching space of finding the when the package is upside down,as the package rotates optimal angle expands,the simple solution is to add one around the y axis by 180.So we can estimate the relative more mobile scanning along the direction different from the angle of the package first,then use the relationships of the previous one,the 3D reconstruction can be realized as well. perpendicular distances among different tag pairs to vote 2.There may exist serious coupling effect and interrogation for the tags'order of the vertical tag pair,then determine failure when packages are stacked closely.As packages are the bottom face of the package.When selecting the tag stacked closely in the warehouse,the large amounts of tags pairs among all the tags on the package,it is significant and small separations between tags from different packages to avoid the tags in the blind direction by filtering the tags may cause serious coupling effect or interrogation failure with relative weak RSS compared with other tags on the problems [26-30].Such problems can have great influence package.The angle estimation is based on the spacings of on the robustness of our proposed solution,which are really the perpendicular points for different tag pairs,as: difficult to deal with only through the advanced algorithms, the improvement of physical tag design is fundamental and arg min>‖6-d(p)l: (5) plays a more important role in solving these problems.The =1 advanced algorithms can mitigate these problems,but it is where N is the number of tag pairs,is the measured nearly impossible to solve the problems thoroughly.The spacing between the perpendicular points of a tag pair,6i() goal of this paper is to propose a scheme for 3D reconstruc- represents the spacing at relative angle o theoretically. tion on tagged packages,so we do not put much effort into Now,considering the case shown in Fig.10(c),we il- dealing with these problems,instead we design a prototype lustrate how to deal with the special cases where there are system to show the idea with the relative ideal environment, two tag pairs whose perpendicular point spacings are both where the coupling effect and multi-path are not so serious. equal to 0.As the antenna moves along the y axis,the Moreover,we still try to explore the effect of coupling effect perpendicular points of the tag pair on the same surface due to the small tag separation on the robustness,details are [T3,T4}or [T5,T6}are at the same point.With the relative shown in Section 5.2.2 and Fig.24.Previous work Tagyro [6] order of the tag pair [T1,T2),as the tag T is on the left of T2 does researches on the coupling effect between neighboring along the antenna moving direction,there are four possible tags,and finds that when there exists strong coupling effect, cases of the package orientation,as shown in Fig.10(c)and the actual tag separation to the antenna is not the same as Fig.14.Any of these possible cases can transform into an- the physical tag separation,so it is necessary to measure other case by rotating along the Y axis,but the relationships the actual tag separation for the following processing.They of their perpendicular distances differ,so we can use these provides the measurement of the actual tag separation to the relationships to vote for which case is the most possible case. antenna,which is likely to be utilized in our scenario.With As we assume that the antenna is above all the tags and the actual tag separation,the performance of our solution ahead of all the tags along the X axis positive direction, can be improved obviously. let the perpendicular distances for T1,T3,Ts be h1,h3,h5, 3.The difference of the perpendicular distances for the tag then for the case as Fig.10(c):h1<h3,h3 h5,for the pair parallel to the antenna plane may be much smaller than possible casel(Fig.14(a)):h<ha,h3<hs,for the possible that for the tag pair perpendicular to the antenna plane with
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 8 ! " X Z Y # $ % & Y X (a) Possible case1 �" �# X Z Y �' �( �) �* �' �( X Z Y �* �) �# �" X Z Y �' �( �" �# �) �* �' �( �# X �" Z Y �* �) (b) Possible case2 # $ X Z Y & % " Y ! (c) Possible case3 Fig. 14. Possible cases for the special package orientation their perpendicular points should be the same. That is, the spacing of their perpendicular points equals 0 in theory. Hence, if the spacing of the perpendicular points for a tag pair is 0, it is probable that the tag pair is along the Z axis now, except for some special cases where there is a tag pair along the X axis, then there are two tag pairs that their perpendicular points spacings are equal to 0, we will discuss it later. After identifying which tag pair is along the Z axis, we can determine the tags’ order by comparing their perpendicular distances extracted from their angle profiles. As the antenna is above all the tags, the tag with the smaller perpendicular distance of the vertical tag pair should be above the other along the Z axis. However, such comparison ignores the relationships of the perpendicular distances for other tags, it is easy to make a wrong decision with only one comparison results. Note that, the spacings of the perpendicular points of the tags should stay the same when the package is upside down, as the package rotates around the Y axis by 180◦ . So we can estimate the relative angle of the package first, then use the relationships of the perpendicular distances among different tag pairs to vote for the tags’ order of the vertical tag pair, then determine the bottom face of the package. When selecting the tag pairs among all the tags on the package, it is significant to avoid the tags in the blind direction by filtering the tags with relative weak RSS compared with other tags on the package. The angle estimation is based on the spacings of the perpendicular points for different tag pairs, as: arg min φ X N i=1 kδ 0 i − δi(φ)k, (5) where N is the number of tag pairs, δ 0 i is the measured spacing between the perpendicular points of a tag pair, δi(φ) represents the spacing at relative angle φ theoretically. Now, considering the case shown in Fig. 10(c), we illustrate how to deal with the special cases where there are two tag pairs whose perpendicular point spacings are both equal to 0. As the antenna moves along the Y axis, the perpendicular points of the tag pair on the same surface {T3, T4} or {T5, T6} are at the same point. With the relative order of the tag pair {T1, T2}, as the tag T1 is on the left of T2 along the antenna moving direction, there are four possible cases of the package orientation, as shown in Fig. 10(c) and Fig. 14. Any of these possible cases can transform into another case by rotating along the Y axis, but the relationships of their perpendicular distances differ, so we can use these relationships to vote for which case is the most possible case. As we assume that the antenna is above all the tags and ahead of all the tags along the X axis positive direction, let the perpendicular distances for T1, T3, T5 be h1, h3, h5, then for the case as Fig. 10(c): h1 h5, for the possible case1 (Fig. 14(a)): h1 h3, h3 h3, h3 > h5. There are multiple tag pairs for the comparison, here we list part of them for explanation. Then, by comparing the relationships of different tag pairs, we vote for the possible cases, and select the case with the highest score as our estimation result. Considering that different tags have different credibilities as they are influenced by the ambient noise to different extents, when voting for the relationships, we tend to allocate the heavier weight to the tag pair with the better linear fitting, such that, we set the voting weight of a tag pair with the reciprocal average linear fitting error of the two tags. Moreover, if the linear fitting error is large than the given threshold, that tag will be abandoned in the following analysis. Through the weighted voting, we can effectively avoid the ambiguous situation that several relationships get the same scores so as to improve the accuracy of the orientation estimation, the corresponding experiments are referred to Fig. 28. 4.3.4 Discussion 1. There must be a side of the package parallel to the ground. As we assume that there must be a side of the package parallel to the ground (which means the package is on the ground or on other packages, not tilted), thus the state of the package is limited, the angle estimation is restricted to along the Z axis. If not, the searching space of finding the optimal angle expands, the simple solution is to add one more mobile scanning along the direction different from the previous one, the 3D reconstruction can be realized as well. 2. There may exist serious coupling effect and interrogation failure when packages are stacked closely. As packages are stacked closely in the warehouse, the large amounts of tags and small separations between tags from different packages may cause serious coupling effect or interrogation failure problems [26–30]. Such problems can have great influence on the robustness of our proposed solution, which are really difficult to deal with only through the advanced algorithms, the improvement of physical tag design is fundamental and plays a more important role in solving these problems. The advanced algorithms can mitigate these problems, but it is nearly impossible to solve the problems thoroughly. The goal of this paper is to propose a scheme for 3D reconstruction on tagged packages, so we do not put much effort into dealing with these problems, instead we design a prototype system to show the idea with the relative ideal environment, where the coupling effect and multi-path are not so serious. Moreover, we still try to explore the effect of coupling effect due to the small tag separation on the robustness, details are shown in Section 5.2.2 and Fig. 24. Previous work Tagyro [6] does researches on the coupling effect between neighboring tags, and finds that when there exists strong coupling effect, the actual tag separation to the antenna is not the same as the physical tag separation, so it is necessary to measure the actual tag separation for the following processing. They provides the measurement of the actual tag separation to the antenna, which is likely to be utilized in our scenario. With the actual tag separation, the performance of our solution can be improved obviously. 3. The difference of the perpendicular distances for the tag pair parallel to the antenna plane may be much smaller than that for the tag pair perpendicular to the antenna plane with
IEEE TRANSACTIONS ON MOBILE COMPUTING,VOL.XX,NO.XX,2019 9 Moving direction Fig.15.The distance differences are differ- ent for the equal tag separation along differ- ent directions Fig.16.Different kinds of package stacking Fig.17.Determining package stacking in 3D space the same tag separation.As shown in Fig.15,the tag pair with a constant speed,so in our work,we assume that the [T1,T2}is perpendicular to the antenna plane,while the antenna can perform the mobile scanning with a constant tag pair [T2,T3}is parallel to the antenna plane.Their tag speed v.As a result,it is easy to get the moving distance separation distances are the same,as Adh=Adu,but their I during the time difference At,as:I =v x At.It would perpendicular distance differences are not similar.Suppose be better that the antenna can localize itself accurately,but the distance from Ti to the antenna is 1m,the tag separation our assumption is more economical and convenient to be is 0.2m,so the perpendicular distance difference between satisfied in practice. T2 and T3 is only 1.65cm,which is much smaller than that between T and T2(20cm).Since the distance difference is 4.4 Determine Package Stacking for Multiple Packages so small,the relationship of such tag pair is probably to be wrong.So,besides the fitting effect,it is better to take into 4.4.1 Limitations of Position Indicators for Determining Package Stacking account the perpendicular distance differences of a tag pair when setting weights for voting package orientations. When we determine the package orientation,we derive the indicators for the relative positions among the tags on a 4.The rule of deploying tags in Section 4.3.1 is a simple single package.As the geometry relationships of these tags solution but not a unique solution.The rule that the orien- are known,we can combine these indicators(perpendicular tations of tags should be along different orthogonal axes distance and perpendicular point)from different tags to (in Fig.10(a))is to ensure the high probability of acquiring estimate the indicators of the package's center point.Then, sufficient effective backscattered signals.Actually,it is not necessary to restrict the tag orientations along axes,any similarly,we compare the indicators of the center points of different packages to determine their stacking situation. tag orientation is fine as long as ensuring the probability Note that,these indicators extracted from once 1D scanning of successful tag interrogation regardless of the package may not support the package stacking determination due to placement.Meanwhile,as mentioned in Section 4.3.2,the the 3-DoF in the 3D space.As shown in Fig.16,suppose tag orientation has impacts on the linear fitting result,espe- the antenna is above all the packages and is in front of the cially for the perpendicular distances of tags with different orientations.If two tags should have the same orientation packages along the X axis,it moves along the Y axis.It is easy to determine the package orders along the y axis in design but have different orientations in reality caused by referring to their perpendicular points,but it may be a by the poor tag attachment,it is probable to degrade the problem to determine their orders in the XZ plane.If the performance.What's worse,if the tag array is wrongly stored in the database,i.e.,the EPC of a tag is wrongly packages line up,that is,the packages are along the Z axis or along the X axis,as the left two cases shown in Fig.16,we recorded,or the tag array is attached to the wrong box, can determine their orders along their lining up direction by such bad situations are beyond the ability of our solution. comparing their perpendicular distances of their centers.For However,if applied to the practical industry,the tagged instance,the perpendicular distance of package A should be boxes should be automatically produced by machines,the smaller than others,so package A is ahead of other packages tag attachment ought to satisfy the production standards,so along the X/Z axis.If not,however,as the 2 x 2 package in this paper,we do not bring in the poor tag attachment or stacking of the right case in Fig.16,we cannot identify the other exceptions deliberately. orders of the packages exactly along the X and Z axes at the 5.The antenna has to move along an absolutely straight line same time only through the position indicators.To solve this and knows its real-time moving distance.Our angle-profile- problem,our basic solution is to perform one more mobile based model has a basic requirement that the antenna has scanning along the orthogonal direction of the previous to move along a straight line,such that we can build the scanning direction,so as to limit the number of the free angle profile and then use it to extract position indicators dimensions in the 3D space.The more times of the mobile by referring to Eq.(3).If it happens that the antenna does scanning is,the much more the cost will be,thus we adopt not move along an absolutely straight line,it would cause the mobile scanning twice as the least needed times.Such estimation errors of the antenna's moving distance and that,the package stacking can be determined in the 3D space further degrade the performance.To handle with such a with a 2D mobile scanning.Note that,it is much easier and practical problem,one possible solution is to fix the antenna costs less to perform the 1D scanning than the 2D scanning, on a linear mobile track as shown in Fig.1.Also,it is likely to and in some circumstances,we are only able to perform the design solutions to compensating the location error because 1D scanning,so based on the localization of the tag array, of the imperfect linear movement in the future.Note that,it we also propose a contemporary solution to determining the will cost much more to localize an antenna than to move it package stacking with only once 1D scanning
IEEE TRANSACTIONS ON MOBILE COMPUTING, VOL. XX, NO. XX, 2019 9 -./ -.0 1" 1& 1' Fig. 15. The distance differences are different for the equal tag separation along different directions ) * + , ) * + , ) * + , Y X Z Fig. 16. Different kinds of package stacking Moving direction Y X Z ! " # $ % & ' ( Fig. 17. Determining package stacking in 3D space the same tag separation. As shown in Fig. 15, the tag pair {T1, T2} is perpendicular to the antenna plane, while the tag pair {T2, T3} is parallel to the antenna plane. Their tag separation distances are the same, as ∆dh = ∆dv, but their perpendicular distance differences are not similar. Suppose the distance from T1 to the antenna is 1m, the tag separation is 0.2m, so the perpendicular distance difference between T2 and T3 is only 1.65cm, which is much smaller than that between T1 and T2 (20cm). Since the distance difference is so small, the relationship of such tag pair is probably to be wrong. So, besides the fitting effect, it is better to take into account the perpendicular distance differences of a tag pair when setting weights for voting package orientations. 4. The rule of deploying tags in Section 4.3.1 is a simple solution but not a unique solution. The rule that the orientations of tags should be along different orthogonal axes (in Fig. 10(a)) is to ensure the high probability of acquiring sufficient effective backscattered signals. Actually, it is not necessary to restrict the tag orientations along axes, any tag orientation is fine as long as ensuring the probability of successful tag interrogation regardless of the package placement. Meanwhile, as mentioned in Section 4.3.2, the tag orientation has impacts on the linear fitting result, especially for the perpendicular distances of tags with different orientations. If two tags should have the same orientation in design but have different orientations in reality caused by the poor tag attachment, it is probable to degrade the performance. What’s worse, if the tag array is wrongly stored in the database, i.e., the EPC of a tag is wrongly recorded, or the tag array is attached to the wrong box, such bad situations are beyond the ability of our solution. However, if applied to the practical industry, the tagged boxes should be automatically produced by machines, the tag attachment ought to satisfy the production standards, so in this paper, we do not bring in the poor tag attachment or other exceptions deliberately. 5. The antenna has to move along an absolutely straight line and knows its real-time moving distance. Our angle-profilebased model has a basic requirement that the antenna has to move along a straight line, such that we can build the angle profile and then use it to extract position indicators by referring to Eq. (3). If it happens that the antenna does not move along an absolutely straight line, it would cause estimation errors of the antenna’s moving distance and further degrade the performance. To handle with such a practical problem, one possible solution is to fix the antenna on a linear mobile track as shown in Fig. 1. Also, it is likely to design solutions to compensating the location error because of the imperfect linear movement in the future. Note that, it will cost much more to localize an antenna than to move it with a constant speed, so in our work, we assume that the antenna can perform the mobile scanning with a constant speed v. As a result, it is easy to get the moving distance l during the time difference ∆t, as: l = v × ∆t. It would be better that the antenna can localize itself accurately, but our assumption is more economical and convenient to be satisfied in practice. 4.4 Determine Package Stacking for Multiple Packages 4.4.1 Limitations of Position Indicators for Determining Package Stacking When we determine the package orientation, we derive the indicators for the relative positions among the tags on a single package. As the geometry relationships of these tags are known, we can combine these indicators (perpendicular distance and perpendicular point) from different tags to estimate the indicators of the package’s center point. Then, similarly, we compare the indicators of the center points of different packages to determine their stacking situation. Note that, these indicators extracted from once 1D scanning may not support the package stacking determination due to the 3-DoF in the 3D space. As shown in Fig. 16, suppose the antenna is above all the packages and is in front of the packages along the X axis, it moves along the Y axis. It is easy to determine the package orders along the Y axis by referring to their perpendicular points, but it may be a problem to determine their orders in the XZ plane. If the packages line up, that is, the packages are along the Z axis or along the X axis, as the left two cases shown in Fig. 16, we can determine their orders along their lining up direction by comparing their perpendicular distances of their centers. For instance, the perpendicular distance of package A should be smaller than others, so package A is ahead of other packages along the X/Z axis. If not, however, as the 2 × 2 package stacking of the right case in Fig. 16, we cannot identify the orders of the packages exactly along the X and Z axes at the same time only through the position indicators. To solve this problem, our basic solution is to perform one more mobile scanning along the orthogonal direction of the previous scanning direction, so as to limit the number of the free dimensions in the 3D space. The more times of the mobile scanning is, the much more the cost will be, thus we adopt the mobile scanning twice as the least needed times. Such that, the package stacking can be determined in the 3D space with a 2D mobile scanning. Note that, it is much easier and costs less to perform the 1D scanning than the 2D scanning, and in some circumstances, we are only able to perform the 1D scanning, so based on the localization of the tag array, we also propose a contemporary solution to determining the package stacking with only once 1D scanning
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,in
IEEE 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 perpendicular 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 orientation, 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 direction 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. Meanwhile, 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 updown relationship, which is usually robust. However, the 1D scanning is much easier to deploy and costs less to perform. 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 determination by taking packages as individual points. However, in