JP7120548B2 - SENSING DIRECTION ESTIMATION DEVICE, SENSING DIRECTION ESTIMATION METHOD AND PROGRAM - Google Patents

Description

The present invention relates to a sensing direction estimation device, a sensing direction estimation method, and a program.

In recent years, attempts have been made to scatter small sensors with wireless functions over a monitoring target area, network them, and use them for various applications. In particular, it is desirable to assume a situation in which a low-cost, low-power-consumption, low-function sensor that does not require prior design or registration of the sensor position and does not have a positioning function such as GPS is used.

One example of such sensors is a small distance sensor. A distance sensor has directivity and has a linear sensing area in a certain angular direction (hereinafter referred to as "sensing direction"). When an object enters the sensing area, the distance sensor measures the distance between itself and the object, and transmits the measurement result (hereinafter referred to as "sensing data") to a calculation server or the like on the network.

One of the applications using scattered distance sensors is the shape estimation technology of an object. Non-Patent Document 1 proposes a method of estimating the overall shape of an object such as a car that moves linearly. Since the distance sensors are generally scattered randomly, the position and sensing direction of each distance sensor are unknown. Therefore, in Non-Patent Document 1, by collecting and analyzing sensing data obtained from a large number of distance sensors, first, the sensing direction of each distance sensor is calculated, and shape estimation is performed based thereon. Calculating the sensing direction of a distance sensor is important not only for estimating the shape of an object, but also for other applications such as position identification of distance sensors and time synchronization between sensors.

H. Ikeuchi and H. Saito, "Shape Estimation Using Location-Unknown Distance Sensors: A Curvature Based Approach," in Proc. of DCOSS 2019, 2019.

As mentioned above, the sensing direction of the range sensor is generally unknown, so prior art object shape estimation requires estimation of the sensing direction of the range sensor. However, the method of estimating the sensing direction proposed in Non-Patent Document 1 requires calculation of higher-order differential values with respect to the time of the sensing data obtained from the distance sensor. In fact, even in Non-Patent Document 1, it is mentioned that if the sensing data contains a large amount of noise, the accuracy of estimating the sensing direction is extremely low. becomes.

SUMMARY OF THE INVENTION The present invention has been made in view of the above points, and an object of the present invention is to improve resistance to noise in sensing data in estimating a sensing direction.

Therefore, in order to solve the above problem, a sensing direction estimating device provides a plurality of sensor terminals based on a plurality of measured values of the distance between a moving object and the sensor terminal. an estimating unit for calculating an estimated value of a sensing direction, the estimating unit for each set of a first sensor terminal and each of the other sensor terminals among the plurality of sensor terminals; Repeating the process of non-rigidly transforming the measured value group of the second sensor terminal according to the set of and minimizing the distance between the measured value group after non-rigid transformation and the measured value of the first sensor terminal , compute an estimate of the sensing direction of each of the first sensor terminal and the second sensor terminal.

It is possible to increase the resistance to noise in sensing data for estimation of the sensing direction.

It is a figure which shows the structural example of the sensing direction estimation system in embodiment of this invention. It is a figure for demonstrating the problem setting given in embodiment of this invention. FIG. 10 is a diagram for explaining derivation of an expression that gives a partial shape of the object T; It is a figure which shows the hardware structural example of the sensing direction estimation apparatus 10 in embodiment of this invention. It is a figure which shows the functional structural example of the sensing direction estimation apparatus 10 in embodiment of this invention. 4 is a flowchart for explaining an example of a processing procedure executed by the sensing direction estimation device 10; FIG. 11 is a flowchart for explaining an example of a processing procedure of a non-rigid transformation ICP algorithm; FIG. FIG. 10 is a diagram showing the situation of the object T at the start of the simulation, the number of each sensor terminal d, and the sensing area; It is a figure which shows the result of a simulation.

BEST MODE FOR CARRYING OUT THE INVENTION An embodiment of the present invention will be described below based on the drawings. FIG. 1 is a diagram showing a configuration example of a sensing direction estimation system according to an embodiment of the present invention. The sensing direction estimation system according to the present embodiment comprises a sensing direction estimation device 10, and N ^~ (plural) sensor terminals ^from sensor terminal d1 to sensor terminal dN .) and including. The sensing direction estimation device 10 and each sensor terminal d are connected via a wired or wireless network. It should be noted that N ^~ corresponds to a symbol with "~" added above N in the figure.

Each sensor terminal d is a distance sensor that detects an object (hereinafter referred to as “target object T”) moving within the monitored area and measures the distance to the target object T. FIG. Each sensor terminal d is a distance sensor with sharp directivity, and when the distance to the object T is r _max or less, the distance r (0≦r≦r _max ) to the object T is measured as a result ( hereinafter referred to as “sensing data”), and transmits the sensing data to the sensing direction estimation device 10 . In the present embodiment, the sensing area of each sensor terminal d (the range in which the object T can be detected) has a specific direction (hereinafter referred to as "sensing direction") and has a length of r _max Modeled as a line segment. The arrangement position of each sensor terminal d is random. That is, each sensor terminal d is scattered at a randomly determined arrangement position.

The sensing direction estimating device 10 is one or more computers that execute a process described later including a "non-rigid transformation ICP (Iterative Closest Point) algorithm" to estimate the sensing direction of each sensor terminal d. The sensing direction estimation result is transmitted from the sensing direction estimation device 10 to the user terminal 20 . Alternatively, the estimation result may be used for estimating the shape of the target object T in Non-Patent Document 1.

The user terminal 20 is a terminal that displays the estimation result of the sensing direction estimation device 10 .

FIG. 2 is a diagram for explaining problem setting given in the embodiment of the present invention. Note that the problem setting described below is merely an example, and the applicable problem setting is not limited to this.

The object T is a two-dimensional area surrounded by a simple closed curve ∂T. The object T is parallel-moving in the x-axis direction at a constant speed v (v>0) within a sufficiently wide two-dimensional monitoring target area. In the object T, the point with the smallest y-coordinate value is called the bottom end, and the point with the largest y-coordinate value is called the top end. Below, it is assumed that there is only one lower end and one upper end. A straight line passing through the object T and parallel to the x-axis is appropriately defined, and the area above it is called the upper half-plane, and the area below it is called the lower half-plane.

Assume that a sufficient number of sensor terminals d are randomly scattered within the monitored area. The sensor terminal d has directivity and has a linear sensing area with direction _θε [0, 2π) and length rmax. The position of the sensor terminal d and the sensing direction θ are unknown, and the length _rmax of the sensing region is known. The subscript _i of each variable represents the sensor terminal number (such as θi), but the sensor terminal number may be omitted when discussing one sensor terminal d.

Each sensor terminal d obtains the distance r(t)≦r _max to the object T at each time t. However, when the distance between the sensor terminal d and the object T exceeds _rmax , r(t)=Φ (empty set), and when the sensor terminal d is included in the object T, r(t)=0. do.

In the following, only sensor terminals d whose sensing data satisfy ∀t (r(t)>0 or r(t)=Φ) and ∃t (r(t)≠Φ) will be considered. The sensing data {r _i (t)} _i are transmitted to the sensing direction estimation device 10, and the sensing direction estimation device 10 uses them to obtain {θ _i } _(i=1) ^N based on the processing procedure described later. .

Here, as a preparation, an equation that gives the partial shape of the object T using θ is derived. Let θε[0, π) and consider mainly the estimation of the lower half-plane part of ∂T. Let _t ^* =argmin tr(t) and let ^t (0,0)ε∂T be the lower end of object T. At this time, the following equation (1) holds, as can be easily derived from FIG.

ここで、（Ｘ（ｔ），Ｙ（ｔ））は、時刻ｔにセンサ端末ｄによってセンシングされた対象物Ｔ上の点の座標である。

Here, (X(t), Y(t)) are the coordinates of a point on the object T sensed by the sensor terminal d at time t.

In Non-Patent Document 1, after estimating θ, the partial shape of the target object T is obtained from the sensing data r(t) by using Equation (1). Furthermore, by connecting the partial shapes of ∂T derived from each sensor terminal d, the overall shape of ∂T is estimated.

Next, the sensing direction estimating device 10 that executes the method of estimating the sensing direction θ proposed in this embodiment will be described.

FIG. 4 is a diagram showing a hardware configuration example of the sensing direction estimation device 10 according to the embodiment of the present invention. The sensing direction estimating device 10 of FIG. 4 includes a drive device 100, an auxiliary storage device 102, a memory device 103, a CPU 104, an interface device 105, etc., which are connected to each other via a bus B, respectively.

A program for realizing processing in the sensing direction estimation device 10 is provided by a recording medium 101 such as a CD-ROM. When the recording medium 101 storing the program is set in the drive device 100 , the program is installed from the recording medium 101 to the auxiliary storage device 102 via the drive device 100 . However, the program does not necessarily need to be installed from the recording medium 101, and may be downloaded from another computer via the network. The auxiliary storage device 102 stores installed programs, as well as necessary files and data.

The memory device 103 reads out and stores the program from the auxiliary storage device 102 when a program activation instruction is received. CPU 104 executes functions related to sensing direction estimation device 10 according to a program stored in memory device 103 . The interface device 105 is used as an interface for connecting to a network.

FIG. 5 is a diagram showing a functional configuration example of the sensing direction estimation device 10 according to the embodiment of the present invention. In FIG. 5 , the sensing direction estimation device 10 has a receiving section 11 and an estimating section 12 . Each of these units is implemented by one or more programs installed in sensing direction estimation device 10 causing CPU 104 to execute processing. The sensing direction estimation device 10 also uses the data storage unit 13 . The data storage unit 13 can be implemented using, for example, the auxiliary storage device 102 or a storage device that can be connected to the sensing direction estimation device 10 via a network.

The receiving unit 11 receives sensing data from each sensor terminal d and stores the sensing data in the data storage unit 13 . The data storage unit 13 stores sensing data of each sensor terminal d in chronological order.

The estimation unit 12 estimates the sensing direction θ of each sensor terminal d based on the time-series sensing data of each sensor terminal d stored in the data storage unit 13 .

A processing procedure of a method for estimating the sensing direction θ, which is executed by the sensing direction estimation device 10, will be described below. FIG. 6 is a flowchart for explaining an example of a processing procedure executed by the sensing direction estimation device 10. As shown in FIG. At the start of FIG. 6, sensing data {r _i (t)} _i=1 ^N are stored in time series in the data storage unit 13 (where N is the number of valid sensor terminals). Also, in FIG. 6, it is assumed that the sensor terminal d1 belongs to the lower half-plane (θ ₁ ε[0, π)). However, in this method, it is not possible to distinguish whether it belongs to the lower half plane or the upper half plane due to the reflection symmetry of θ with respect to the x-axis direction, so this assumption is not essential.

In step S101, the estimation unit 12 sets _each pair of (r ₁ , r ₂ ), ( _{r 1} , r ₃ ), . ), estimation of θ ₁ (calculation of an estimated value θ̂ ₁ of θ ₁ ) is performed based on a later-described “non-rigid transformation ICP (Iterative Closest Point) algorithm”.

If an appropriate threshold value α is used, generally about half of the total N-1 solutions obtained from each pair fall within the range [θ^ ₁ -α, θ^ ₁ +α] (θ^ ₁ and almost the same value), and the rest are less than θ^ ₁ -α or greater than θ^ ₁ +α, or empty sets.

Therefore, the estimating unit 12 assigns the group of sensor terminals d that gave a solution in the range of [θ^ ₁ -α, θ^ ₁ +α] (almost the same value as θ^ ₁ ) to the lower half plane, and the other sensor terminals d Groups are classified into the upper half plane (S102). The estimated value of the sensing direction θ of each sensor terminal d group belonging to the lower half plane has already been obtained as _a pair of θ̂1 in the above process.

Subsequently, the estimating unit 12 obtains an estimated value of the sensing direction θ of each sensor terminal d belonging to the upper half plane by applying the “non-rigid transformation ICP algorithm” to the sensor terminals d belonging to the upper half plane ( S103). That is, the estimating unit 12 positions one sensor terminal d in the group of sensor terminals d belonging to the upper half plane in the same position as the sensor terminal d1 in step S101, and sets the sensing data of the sensor terminal d and A “non-rigid transformation ICP algorithm” is applied to pairs of sensing data of other sensor terminals d belonging to to calculate an estimated value of the sensing direction θ of each sensor terminal d.

Next, the "non-rigid transformation ICP algorithm" will be described. This is an algorithm that uses sensing data r _m (t _m ) and r _n (t _n ) from two sensor terminals dm and dn to obtain the estimated values (θ^ _m , θ^ _n ) of the sensing direction. .

Now suppose that the sensor terminals dm and dn both belong to the lower half plane.
t _i ^* =argmin _{t i} (t) (i=m, n)
year,
t ^~ _i = t _i ^- t _i ^* , r ^~ _i (t _i ) = r _i (t _i ) - r _i (t _i ^* )
and At this time, Equation (1) can be rewritten as Equation (2) below.

すなわち、（ｔ^～，ｒ^～）→（Ｘ，Ｙ）は、行列Ａ（θ）によって表現される線形変換である。以下では、表記を簡単にするため、ｔ^～ _ｉを改めてｔ_ｉと書き、ｒ^～ _ｉを改めてｒ_ｉと書くことにする。また、センサ端末ｄｉによる測定値（ｔ_ｉ，ｒ_ｉ）が属する空間を、センサ端末ｄｉの測定値空間といい、座標系（Ｘ，Ｙ）が与えられた、対象物Ｔが存在する空間を実空間という。

That is, (t ^∼ , r ^∼ )→(X, Y) is a linear transformation represented by the matrix A(θ). In the following, for simplicity of notation, t ^to _i will be rewritten as t _i , and r ^to _i will be rewritten as r _i . The space to which the measured values (t _i , r _i ) of the sensor terminal di belong is called the measured value space of the sensor terminal di, and the space in which the object T exists, given the coordinate system (X, Y), is called real space.

Here, the measured value group (sensing data group) of the sensor terminal dm {q ^j } _j = {(t _m ^j , r _m ^j )} _j and the measured value group (sensing data group) of the sensor terminal dn {p ^k } _k = {(t _n ^k , r _n ^k )} _k is obtained (actually, the sensor terminal d cannot perform sensing in continuous time, and the measured value (sensing data) is discretized There are a finite number of points, and the subscripts j and k are indices for distinguishing the measurements).

FIG. 7 is a flowchart for explaining an example of the processing procedure of the non-rigid transformation ICP algorithm.

In step S201, the estimation unit 12 determines appropriate initial values (θ _m , θ _n ) for the respective sensing directions of the two sensor terminals dm and dn.

Subsequently, the estimating unit 12 transforms (non-rigid transformation) each measured value p ^k of the sensor terminal dn by R(θ _m , θ _n ) p ^k using (θ _m , θ _n ) (S202). where R(θ _m , θ _n )≡A(θ _m ) ⁻¹ A _n (θ _n ). As a result, each measurement value (sensing data) of the sensor terminal dn is mapped to the measurement value space of the sensor terminal dm.

Subsequently, the estimating unit 12 selects the measured value with the smallest predetermined distance from each R(θ _m , θ _n )p ^k from among the measured value group {q ^j } _j of the sensor terminal dm (which is q ^{j ( k)} (denoted as )) is specified (S203). As a definition of the predetermined distance, for example, Euclidean distance d ((t, r), (t', r')) ≡ √ ((vt-vt' ) ⁿ + (r−r′) ⁿ ) or the like may be used.

Subsequently, the estimation unit 12 calculates the error function 1/ _M ( _Σkd (R(θm, θn) ^{pk, qj(k))n ) (} _M is the number of data in the measured value group of the sensor terminal dn ) is minimized with respect to θ _m and θ _n by an arbitrary optimization method such as the stochastic gradient method (S204). However, when moving θ _m and θ _n to minimize the error function, the correspondence relationship between p ^k and q ^j(k) determined in step S203 is maintained.

Subsequently, the estimating unit 12 calculates the value of the error obtained in the current loop (current error) 1/ _M ( _Σkd (R(θm, θn) ^pk , qj( ^{k )} ) _n ) Then, it is determined whether or not the difference from the error obtained in the previous loop (previous error) is equal to or less than the threshold value β (S205). If the difference is greater than the threshold β (No in S205), the estimation unit 12 repeats steps S202 to S204 using (θ _m , θ _n ) obtained (updated) by the minimization procedure.

On the other hand, if the difference between the current error and the previous error is equal to or less than the threshold value β (Yes in S205), the estimating unit 12 replaces (θ _m , θ _n ) at that point with the estimated value (θ^ _m , _θ̂n ) (S206).

Thus, in this algorithm, a plurality of sensing data of one sensor terminal d are subjected to non-rigid transformation, and the distance between the sensing data group after non-rigid transformation and the sensing data of the other sensor terminal d is minimized. are sequentially repeated, the sensing directions of these two sensor terminals d are estimated.

Unlike the θ estimation method in Non-Patent Document 1, this algorithm does not require calculation of higher-order differentials of sensing data r(t). High estimation accuracy can be maintained.

The widely used ICP algorithm proposed in "PJ Besl, ND McKay, "A method for registration of 3D shapes," IEEE Trans. Pattern Analysis and Machine Intelligence vol. 14, no. 2, 1992." , as a transformation (corresponding to R(θ ₁ , θ ₂ ) mentioned above) for bringing two point groups (corresponding to {q ^j } _j , {p ^k } _k mentioned above) closer together, a rigid transformation (Rotation and translation) are considered. Since R(θ ₁ , θ ₂ ) in this algorithm is not a rigid transformation, it is called a non-rigid transformation ICP algorithm.

The convergence of the non-rigid transformation ICP algorithm (that the error converges to a local minimum value by repeating the loop and the algorithm stops) is guaranteed by proof similar to that of the normal ICP algorithm.

In addition, in step S204, instead of using all the measured value groups, d(R(θ ₁ , θ ₂ ) p ^k , q ^j(k) ) ² is separated by a certain value or more. It may not be included in _Σk . In this case, M is the number of _k included in Σk.

In addition, in the normal ICP algorithm, various variants (for example, as a method of associating R(θ ₁ , θ ₂ )p ^k and q ^j(k) corresponding to step S203 above, instead of using the distance between points, the vertical distance ( Use the distance of the perpendicular drawn from the point R (θ ₁ , θ ₂ ) p ^k to the tangent line formed by the point group {q ^k } _k )”, “As the error function in step S204, a different weight is assigned to each k ("S. Rusinkiewicz and M. Levoy, "Efficient variants of the ICP algorithm," in Proc. of 3DIM 2001, 2001."). may be applied.

Next, the results of numerical simulation using an elliptical object using the present embodiment will be described.

The velocity v=1 of the object is known, and the positions and directions of the two sensor terminals d are given as shown in Table 1.

但し、センシング方向推定装置１０はこれらのセンサ端末ｄの位置及び方向の情報は利用しない。各センサ端末ｄは、ｒ_ｍａｘ＝１００とし、Δｔ＝０．０５刻みでセンシングデータｒ（ｔ）を取得していく。楕円形の対象物Ｔは、右端を^ｔ（０，７５）につけた状態からｖ＝１でｘ軸方向へ平行移動していく。シミュレーションにおける対象物Ｔのスタート時点での状況及び各センサ端末ｄの番号、及びセンシング領域を図８に示す。

However, the sensing direction estimation device 10 does not use information on the position and direction of these sensor terminals d. Each sensor terminal d sets r _max =100 and acquires sensing data r(t) at intervals of Δt=0.05. The elliptical object T moves parallel to the x-axis direction at v=1 from the state where the right end is at ^t (0, 75). FIG. 8 shows the situation of the object T at the start of the simulation, the number of each sensor terminal d, and the sensing area.

When the target object T leaves the rectangular area (monitoring target area) indicated by broken lines, the measurement is terminated. Sensing data {r _i (t)} _i (i=1, 2) obtained with such settings have an average of 0, standard deviations of 10 ⁻⁷ , 10 ⁻⁶ , 10 ⁻⁵ , 10 ⁻⁴ , 10 ⁻ Data including ³ , 10 ⁻² , 10 ⁻¹ , 2×10 ⁻¹ and 5×10 ⁻¹ noise were prepared. For each case, θ ₁ and θ ₂ were estimated by the methods of Non-Patent Document 1 and the “non-rigid transformation ICP algorithm” of this embodiment.

FIG. 9 is a diagram showing simulation results. In FIG. 9, the horizontal axis indicates the standard deviation of noise, and the vertical axis indicates the sensing direction (θ). A plot of ♦ indicates θ ₁ obtained by the present embodiment (non-rigid transformation ICP algorithm), and a plot of □ indicates θ ₂ obtained by this embodiment (non-rigid transformation ICP algorithm). On the other hand, the plot of Δ indicates θ ₁ obtained by the method of Non-Patent Document 1 (prior art), and the plot of ● indicates θ ₂ obtained by the method of Non-Patent Document 1 (prior art). Furthermore, the dashed line indicates the true (noiseless) θ ₁ and the dash-dotted line indicates the true (noiseless) θ ₂ .

According to FIG. 9, if the noise is 10 ⁻⁴ or less, both methods can obtain θ ₁ and θ ₂ with a maximum deviation of about 0.3. However, when the noise was larger than 10 ⁻⁴ , the method of Non-Patent Document 1 could not even estimate θ ₁ and θ ₂ , so the results could not be plotted in FIG. On the other hand, it can be seen that θ ₁ and θ ₂ are still obtained with high accuracy when the “non-rigid transformation ICP algorithm” of the present embodiment is used. This result indicates that the sensing direction can be estimated with high accuracy by using the present embodiment even if the sensing data contains noise.

As described above, according to the present embodiment, by accumulating and analyzing the sensing data of the sensor terminal d with respect to the object T moving within the monitoring target area, even if the sensing data contains noise, However, it is possible to estimate the sensing direction with high accuracy. That is, unlike the prior art, calculation of higher-order differentials is not required, so that it is possible to increase the resistance to noise in sensing data in estimating the sensing direction. As a result, highly accurate object shape estimation, position identification of the sensor terminal d, time synchronization of the sensor terminal d, and the like become possible.

Although the embodiments of the present invention have been described in detail above, the present invention is not limited to such specific embodiments, and various modifications can be made within the scope of the gist of the present invention described in the claims. Transformation and change are possible.

10 sensing direction estimation device 11 reception unit 12 estimation unit 13 data storage unit 20 user terminal 100 drive device 101 recording medium 102 auxiliary storage device 103 memory device 104 CPU
105 interface device B bus d sensor terminal

Claims (5)

an estimating unit that calculates an estimate of the sensing direction of each sensor terminal based on a plurality of measurements of the distance between a moving object and the sensor terminal, measured by each of the sensor terminals;
For each set of a first sensor terminal and each of the other sensor terminals among the plurality of sensor terminals, the estimation unit measures a group of measured values of a second sensor terminal related to the set with the first sensor terminal. By repeating the process of non-rigid transformation and minimizing the distance between the measured value group after non-rigid transformation and the measured value of the first sensor terminal, the first sensor terminal and the second sensor Compute an estimate of the sensing direction for each terminal,
A sensing direction estimation device characterized by: The estimating unit repeats the process for a group of sensor terminals in which the estimated value is not within a threshold with respect to the estimated value of the first sensor terminal among the plurality of sensor terminals, calculating an estimate of the sensing direction of each sensor terminal of the group of sensor terminals;
The sensing direction estimating device according to claim 1, characterized in that: A computer performs an estimation procedure for calculating an estimate of the sensing direction of each sensor terminal based on a plurality of measurements of the distance between a moving object and the sensor terminal, measured by each of the sensor terminals. death,
The estimation procedure includes, for each set of a first sensor terminal and other sensor terminals among the plurality of sensor terminals, a group of measured values of a second sensor terminal associated with the set of the first sensor terminal. By repeating the process of non-rigid transformation and minimizing the distance between the measured value group after non-rigid transformation and the measured value of the first sensor terminal, the first sensor terminal and the second sensor Compute an estimate of the sensing direction for each terminal,
A sensing direction estimation method characterized by: In the estimation procedure, for a sensor terminal group in which the estimated value is not within a threshold value of the estimated value of the first sensor terminal among the plurality of sensor terminals, the process is repeated for the sensor terminal group, calculating an estimate of the sensing direction of each sensor terminal of the group of sensor terminals;
4. The sensing direction estimation method according to claim 3, wherein: A program for causing a computer to execute the sensing direction estimation method according to claim 3 or 4.

Images