INTEREST

TECHNICAL FIELD

[0001] Disclosed are embodiments related to detecting a change in an area of interest.

BACKGROUND

[0002] In certain industries it is advantageous to determine whether an area of interest

(AOI) has changed. For instance, it may be advantageous to determine whether new objects were introduced into the AOI since the last time the AOI was scanned. As one example, this could be useful to diagnose problems at base stations: the current state of the area in which the base station is situated could be compared to the previous state of the area, highlighting the differences, which may be the cause of an ongoing problem. A technician, therefore, may scan the area using some kind of sensor that produces images of the area that are then used to produce a digital model of the area, which digital model is then compared to a previous digital model of the area produced as a result of a prior scan of the area to detect changes in the AOI (e.g., detect objects that have been added to the area since the prior scan, objects that have been removed from the area since the prior scan, and/or objects that have changed since the prior scan).

SUMMARY

[0003] One particular way to solve this problem is to build a three-dimensional (3D) model (a pointcloud or a polygon mesh) using 3D reconstruction algorithms such as Structure- from-Motion (SfM) (see reference [1]) if using monocular cameras, or creating a 3D model of the world using a depth camera (e.g. Lidar, stereo) for both states, and find the differences using the models. The challenge is then finding differences that are meaningful for the users. Changes in illumination, different cameras, or even just camera locations while scanning can produce different models when the comparison is naive (e.g. comparing each point in two-pointclouds or each pixel in two depth maps for the same camera location). If the possible changes that interests the users are known beforehand, it is possible to use supervised learning techniques to find out what the current state is given the models. An example of this approach is described in reference [2], where sliding window object detectors are trained to find predefined objects in pointclouds. Other methods try to find which areas in the model have changed in a dense manner (pixel-wise on images (see reference [3]) or voxel-wise on 3D models (see reference [4])) while taking into consideration the effects of unimportant changes (e.g. changes in lightning) in order to ignore them when it is appropriate to do so.

[0004] Certain challenges presently exist. Methods like the ones described in references

[2] and [4] rely on obtaining a highly accurate 3D model of the environment, which in most cases is not possible with the current technology. A pointcloud built using SfM is prone to noise, like lower density of points in describing some objects or holes in the pointcloud. Similar problems also occur when building pointclouds from depth sensors. Moreover, depending on the environmental conditions like lightning, the camera motion, and different view at which images were taken etc, creating two 3D models of the same scene at two different points in time can produce very different 3D models even where the scene has hardly changed. That is, this can result in pointclouds composed of points with different visual features, and the algorithms may, therefore, detect changes in scene even when there is no real change (i.e., the scene change algorithms may produce many false positives).

[0005] To overcome these challenges, this disclosure describes improved methods for detecting a change in an area of interest. In one embodiment, the method includes forming a pointcloud that includes: i) a first set of points derived from a first set of one or more images, wherein each image included in the first set of images was obtained during a first period of time, tl, and each image included in the first set of images is an image of at least a portion of the area of interest and ii) a second set of points derived from a second set of one or more images, wherein each image included in the second set of images was obtained during a second period of time, t2, and each image included in the second set of images is an image of at least a portion of the area of interest, wherein each point of the pointcloud is associated with a location within the area of interest, and tl is different than t2. The method also includes, for each point included in the pointcloud, assigning a similarity score to the point, wherein the similarity score assigned to the point indicates a degree of similarity between the point and points within the first set of points. The method also includes, for at least each point from the pointcloud that is included in a particular set of points, determining a value Nt and a value Nnew, wherein Nt is the total number of points within the pointcloud that are associated with a location that is within a defined geometrical volume in which the location to which said point is associated is also within, and Nnew is the total number of points within the pointcloud that are i) associated with a location that is within the defined geometrical volume and ii) included in second set of points; and adjusting the similarity score assigned to the point based on Nt and Nnew. The method further includes using the adjusted similarity scores to determine whether the area of interest has changed.

[0006] In another aspect there is provided a computer program comprising instructions which when executed by processing circuitry causes the processing circuitry to perform the above described method. In one embodiment, there is provided a carrier containing the computer program wherein the carrier is one of an electronic signal, an optical signal, a radio signal, and a computer readable storage medium.

[0007] In another aspect there is provided an apparatus for detecting a change in an area of interest. The apparatus is adapted to form a pointcloud. The pointcloud comprises: a first set of points derived from a first set of one or more images, wherein each image included in the first set of images was obtained during a first period of time, tl, and each image included in the first set of images is an image of at least a portion of the area of interest; and a second set of points derived from a second set of one or more images, wherein each image included in the second set of images was obtained during a second period of time, t2, and each image included in the second set of images is an image of at least a portion of the area of interest, wherein each point of the pointcloud is associated with a location within the area of interest, and tl is different than t2. The apparatus is further adapted such that, for each point included in the pointcloud, the apparatus assigns a similarity score to the point, wherein the similarity score assigned to the point indicates a degree of similarity between the point and points within the first set of points. The apparatus is further adapted to, for at least each point from the pointcloud that is included in a particular set of points, determine a value Nt and a value Nnew, wherein Nt is the total number of points within the pointcloud that are associated with a location that is within a defined geometrical volume in which the location to which said point is associated is also within, and Nnew is the total number of points within the pointcloud that are i) associated with a location that is within the defined geometrical volume and ii) included in second set of points. The apparatus is further adapted to adjust the similarity score assigned to the point based on Nt and Nnew. The apparatus is further adapted to use the adjusted similarity scores to determine whether the area of interest has changed. In one embodiment, the apparatus comprises processing circuitry and a storage unit storing instructions for configuring the apparatus to perform any of the processes disclosed herein.

[0008] The embodiments described herein can be applied on top of any 3D scene change detection algorithm to significantly remove false positive proposals. This can act as a post/pre filter stage of a 3D change detection system.

BRIEF DESCRIPTION OF THE DRAWINGS

[0009] The accompanying drawings, which are incorporated herein and form part of the specification, illustrate various embodiments.

[0010] FIG. 1 illustrates a first pointcloud (PCI).

[0011] FIG. 2 illustrates a second pointcloud (PC2).

[0012] FIG. 3 illustrates PCI and PC2 fitted inside a cube.

[0013] FIG. 4 illustrates a volume in space that is divided into many smaller cubic volumes.

[0014] FIG. 5 illustrates similarity scores being assigned to points in a pointcloud.

[0015] FIG. 6 illustrates the removal of false positives.

[0016] FIG. 7 is a flow chart illustrating a process according to some embodiments.

[0017] FIG. 8 is a block diagram of an apparatus for detecting a change in an AOI.

DETAIFED DESCRIPTION

[0018] This disclosure describes improved methods for detecting a change in an area of interest.

[0019] In one embodiment, the method includes obtaining two pointclouds for an area of interest (AOI). A pointcloud may be generated using an algorithm like SFM (see reference [1]) by taking images of the AOI as an input. The first of the two pointclouds (PCI) is built using images taken of the AOI at time tl . The second pointcloud (PC2) is an update of first pointcloud using additional images of the AOI taken at time t2. FIG. 1 illustrate PCI and FIG. 2 illustrates PC2.

[0020] As shown FIG. 1, PCI includes a group of points that correspond to a first object

101 in the AOI, a group of points that correspond to a second object 102 in the AOI, and a group of points that correspond to a third object 103 in the AOI. As shown in FIG. 2, PC2, includes the group of points that correspond to objects 101, 102, and 103, respectively, as well as additional point groupings 202, 204, 206, and 210. Of these additional point groups, only point group 210 corresponds to a new object 212 that was not previously in the AOI.

[0021] In order to detect a change in the AOI, a method similar to the one described in reference [2] can be used. That is, algorithms like SfM calculate and store 2D image feature descriptors which are used during image registration phase. These descriptors can be reused to create visual bag of words (BOW) features using a vocabulary tree as described in references [2] and [5]

[0022] FIG. 3 illustrates PCI and PC2 fitted inside a cube of side a. This cube is further divided into smaller cubes of side a’, each of these smaller cubes will contain a set of 3D points, whose visual appearance is described by corresponding descriptor vectors. One can use these descriptor vector and vocab tree to assign a score (a scalar or a vector) to each of these smaller cubes in space, i.e., a global descriptor, these scores being an indicative of the visual appearance of the cubes.

[0023] In one embodiment, the method to determine whether the AOI has changed

(e.g., whether a new object has been introduced into the AOI) comprises of following steps: 1) pointcloud alignment; 2) pointcloud comparison using a sliding window; 3) calculating visual difference; 4) assigning visual difference scores to points in 3D space; and 5) removal of false positive and post filtering.

[0024] Stepl : Pointcloud Alignment:

[0025] The alignment of the pointclouds can be done using multiple methods like iterative closest point (I CP) (see reference [6]) or global pointcloud alignment methods like the methods disclosed in reference [7] or reference [8] Building 3D model using colmap (reference [1]), one can achieve alignment by registering images taken at time t2 to PCI, which outputs PC2.Thus PC2 will contain 3D points registered from images at times tl and t2.

[0026] Step2: Pointcloud comparison using a sliding window:

[0027] A 3D sliding window (w) (e.g., a cubic volume) can be used to compare the two-pointclouds. This sliding window can be visualized as a volume in space further divided into many smaller cubic volumes as illustrated in FIG. 4. As described in step 1, PC2 contains registered 3D-points from times tl and t2, thus we slide w over PC2 and inside each w find out the points contributed by images taken at times tl and t2.

[0028] 3D-Points registered at tl,

[0029] 3D-Points registered at t2, points _tz = {p^J^ , r _tl and r _tz being any positive integer.

[0030] The center volume of the sliding window is denoted m _center and similarity scores are assigned only to the points inside it. This makes sure that the similarity score assigned to each point in space is based on the visual appearance of 3D points surrounding it.

[0031] Step3: calculating visual difference

[0032] Each point in points _t and points _tz is described by a set of descriptors, reference [4] uses SIFT (see reference [9]) and a descriptor of length 128. The custom vocabulary tree is trained on images similar to the scene. Using the set of descriptors describing each of the 3D points and the trained vocabulary tree a global descriptor is calculated using the BOW approach describing points in points _ti and points _tz , as visual_words _ti , visual_words _tz . Each component in these feature vectors ( visual_words _ti , visual_words _tz ) counts the number of occurrences of a visual word defined in the vocabulary tree.

[0033] The distance between visual_words _ti and visual_words _tz describes how similar the region described by points _ti is to the region described by points _tz. A larger distance implies a larger difference. We call this distance the similarity score and calculate it as follows:

Norm^ Llnorm( visual _wordSt )

Norm ₂ = Llnorm( visual _wordSt ) [0034] Notice that similarity score ranges between 0 (the same words appear in the same relative proportions) and 2 (the two sets of visual words are disjoint).

[0035] Since this expression is only defined when the sets of points are not empty

(Norm ₁ > 0 and Norm ₂ > 0) we extend the definition to include the following: if both sets of points are empty ( Norm ₁ = 0 and Norm ₂ = 0), then similarity_score = 0; and if only one is empty (( Norm ₁ = 0 and Norm ₂ > 0 ) or ( Norm ₁ > 0 and Norm ₂ = 0)), then similarity_score = 1.

[0036] Step4: Assigning visual difference scores to points in 3D space

[0037] The similarity score is assigned to the points inside the a> _center in PC2. The 3D sliding volume is moved by delta ( D _c , D _g , D _z ), and steps 1-4 are repeated until the whole 3D pointcloud is traversed. As a result, similarity scores are assigned to each 3D point in PC2, as shown in FIG. 5, which describes how similar the point is to the points in the same 3D space in PCI. Referring to FIG. 5, the different fill pattern shows how different are the points visually compared to the model built at time tl.

[0038] Step5: Removal of false positive and post filtering:

[0039] A first 3D model of an AOI created based on images obtained during a first time period (tl) can have a different visual appearance and density of registered points than a second 3D model of the AOI created based on images obtained during a subsequent period of time (t2). This may be caused by changes in lightning conditions and also the views at which the images are taken at times tl and t2. Consequently, the above algorithm stated in stepsl-4, might end up assigning higher similarity score (more difference) to points from objects which have not changed at all (see FIG. 5), i.e. false positive points. That is, FIG. 5 illustrates the points that have been assigned a high similarity score and further illustrates which of these high similarity points would produce a false positive under the above algorithm and which are due to a real change in the scene (in this case, the new cylindrical object). The change detection algorithm is improved by suppressing false positives. That is, the points with a high similarity score that would otherwise produce a false positive under the above algorithm are ignored by the change detection processes of this disclosure. This feature is illustrated in FIG. 6, which shows that, except for the points corresponding to the new cylindrical object, the other points assigned a high similarity score are suppressed (i.e., ignored).

[0040] After step4 there is a pointcloud (PC2) with each point having a similarity score which describes its visual similarity to points in PCI. In order to remove the possible false positive, the similarity scores are adjusted and all the points with an adjusted similarity score higher than a threshold 0 are examined to determine whether the AOI has changed. The threshold (0) value indicates how different is the point visually to points in PCI.

[0041] Adjusting the Similarity Scores

[0042] 1. For every point p with similarity score > 0, the other points that are within a volume that includes point p (e.g., a spherical volume of radius r where point p is located at the center of the volume) are categorized as either “new” or “old.” For example, every point that is contributed by the newly registered images (i.e., the images obtained during t2) is categorized as “new,” otherwise the point is categorized as “old.” The total number of “new” points (Nnew) is determined and the total number of “old” points (Nold) is determined.

[0043] 2. Calculate the proportion of new points lying inside the volume as: P =

Nnew/Nt, where Nt = Nnew + Nold.

[0044] 3. If point p is from the old point cloud then we update its similarity score by adjusting it by a certain factor: al or a2, where al > 0, a2 < 1, and al > a2. The idea is, if the point p is surrounded by many new points (e.g., P > 0.5), the probability of changes around this point is high, so we adjust the similarity score for this point p slightly using factor al, on the other hand if P < 0.5 then p’s similarity score is penalized, i.e. adjusted using factor a2, which is less than al. In one embodiment, al=0.8 and a2=0.4. For instance, if point p is an old point and P is greater than or equal to 0.5, then the adjusted similarity score for point p is calculated as adjusted_similarity_score = similarity_score * al, otherwise adjusted_similarity_score = similarity_score * a2.

[0045] 4. If point p is from the new point cloud then we update its similarity score by adjusting it by a certain factor: bl or b2, where bl is greater than 1 and b2 is a positive number less than 1. More specifically, if for this new point p, P is greater than or equal to 0.5, then the similarity score for point p is increased by factor bl (e.g., the adjusted similarity score for point p is calculated as: adjusted similarity score = similarity score * bl), otherwise the similarity score for point p is decreased by factor b2 (e.g., the adjusted similarity score for point p is calculated as: adjusted similarity score = similarity score * b2). In one embodiment, bl = 1.25 and b2 = 0.9.

[0046] With the above algorithm, all the points which are contributed by the newly registered images but from the new object in the scene will get uplift in score while the new points registered around old existing objects will be penalized. Thus, the number of false positive is greatly removed (see FIG. 6, which illustrates the removal of the false positives). To determine whether an object has been removed from the AOI, this can be done by running the algorithm in reverse order.

[0047] FIG. 7 is a flow chart illustrating a process 700, according to an embodiment, for detecting a change in an AOI. Process 700 may begin in step s702.

[0048] Step s702 comprises forming a pointcloud. The pointcloud comprises: i) a first set of points derived from a first set of one or more images, wherein each image included in the first set of images was obtained during a first period of time, tl , and each image included in the first set of images is an image of at least a portion of the area of interest; and ii) a second set of points derived from a second set of one or more images, wherein each image included in the second set of images was obtained during a second period of time, t2, and each image included in the second set of images is an image of at least a portion of the area of interest, wherein each point of the pointcloud is associated with a location within the area of interest, and tl is different than t2. In some embodiments, t2 is after tl, and in other embodiments t2 precedes tl.

[0049] Step s704 comprises, for each point included in the pointcloud, assigning a similarity score to the point, wherein the similarity score assigned to the point indicates a degree of similarity between the point and points within the first set of points.

[0050] For each point in the pointcloud that is included in a particular set of points (e.g., for each point of the pountcloud that is assigned a similarity score that exceeds a threshold (e.g. 0)), step s706 is performed.

[0051] Step s706 comprises determining a value Nt and a value Nnew and adjusting the similarity score assigned to the point based on Nt and Nnew. Nt is the total number of points within the pointcloud that are associated with a location that is within a defined geometrical volume in which the location to which said point is associated is also within, and Nnew is the total number of points within the pointcloud that are i) associated with a location that is within the defined geometrical volume and ii) included in second set of points. In some embodiments, the defined geometrical volume has a center and the center of the defined geometrical volume is the location to which said point is associated. In some embodiments, the defined geometrical volume is a sphere. In some embodiments, adjusting the similarity score assigned to the first point, similarity_score, based on Nt and Nnew comprises: calculating P = Nnew/Nt; and calculating adjusted similarity score = (a) x (similarity score), where a is a function of P. In some embodiments, a = al if P is greater than T, a = a2 if P is less than T, al is a first predetermined value, a2 is a second predetermined value, and T is a third predetermined value. [0052] Step s708 comprises using the adjusted similarity scores to determine whether the area of interest has changed. In some embodiments, using the adjusted similarity scores to determine whether the area of interest has changed comprises determining that the area of interest has changed as a result of detecting a cluster of points that have an adjusted similarity score that is above a threshold.

[0053] FIG. 8 is a block diagram of an apparatus 800, according to some embodiments, for performing the methods disclosed herein. As shown in FIG. 8, apparatus 800 may comprise: processing circuitry (PC) 802, which may include one or more processors (P) 855 (e.g., a general purpose microprocessor and/or one or more other processors, such as an application specific integrated circuit (ASIC), field-programmable gate arrays (FPGAs), and the like), which processors may be co-located in a single housing or in a single data center or may be geographically distributed (i.e., apparatus 800 may be a distributed computing apparatus); at least one network interface 848 comprising a transmitter (Tx) 845 and a receiver (Rx) 847 for enabling apparatus 800 to transmit data to and receive data from other nodes connected to a network 110 (e.g., an Internet Protocol (IP) network) to which network interface 848 is connected (directly or indirectly) (e.g., network interface 848 may be wirelessly connected to the network 110, in which case network interface 848 is connected to an antenna arrangement); and a storage unit (a.k.a., “data storage system”) 808, which may include one or more non-volatile storage devices and/or one or more volatile storage devices. In embodiments where PC 802 includes a programmable processor, a computer program product (CPP) 841 may be provided. CPP 841 includes a computer readable medium (CRM) 842 storing a computer program (CP)

843 comprising computer readable instructions (CRI) 844. CRM 842 may be a non-transitory computer readable medium, such as, magnetic media (e.g., a hard disk), optical media, memory devices (e.g., random access memory, flash memory), and the like. In some embodiments, the CRI 844 of computer program 843 is configured such that when executed by PC 802, the CRI causes apparatus 800 to perform steps described herein (e.g., steps described herein with reference to the flow charts). In other embodiments, apparatus 800 may be configured to perform steps described herein without the need for code. That is, for example, PC 802 may consist merely of one or more ASICs. Hence, the features of the embodiments described herein may be implemented in hardware and/or software. In other embodiments, CP 843 is contained in an electronic signal, an optical signal, a radio signal, or other carrier.

[0054] While various embodiments are described herein, it should be understood that they have been presented by way of example only, and not limitation. Thus, the breadth and scope of this disclosure should not be limited by any of the above-described exemplary embodiments. Moreover, any combination of the above-described elements in all possible variations thereof is encompassed by the disclosure unless otherwise indicated herein or otherwise clearly contradicted by context.

[0055] Additionally, while the processes described above and illustrated in the drawings are shown as a sequence of steps, this was done solely for the sake of illustration. Accordingly, it is contemplated that some steps may be added, some steps may be omitted, the order of the steps may be re-arranged, and some steps may be performed in parallel.

[0056] References

[0057] [1] Schonberger, Johannes Luts and Frahm, Jan-Michael, Structure-from-

Motion Revisitied, Conference on Computer Vision and Pattern Recognition (CVPR),2016. [0058] [2] N. Gunji, H. Niigaki, K. Tsutsuguchi, T. Kurozumi and T. Kinebuchi, "3D object recognition from large-scale pointclouds with global descriptor and sliding window," in 23rd International Conference on Pattern Recognition (ICPR), Cancrtn, 2016.

[0059] [3] A. O. Ulusoy and J. L. Mundy, "Image-Based 4-D Reconstruction Using 3-D

Change Detection," in Computer Vision - ECCV 2014, Zurich, 2014. [0060] [4] K. Sakurada, T. Okatani and K. Deguchi, "Detecting Changes in 3D

Structure of a Scene from Multi -view Images Captured by a Vehicle-Mounted Camera," in IEEE Conference on Computer Vision and Pattern Recognition, Portland, Oregon, 2013. [0061] [5] D. Nister and H. Stew'enius. “Scalable Recognition with a Vocabulary

Tree”. In: Conference on Computer Vision and Pattern Recognition (CVPR). 2006.

[0062] [6] P. J. Besl and N. D. McKay. A method for registration of 3-D shapes.

TP AMI, 14(2): 239-256, 1992.

[0063] [7] N. Gelfand, N. J. Mitra, L. J. Guibas, and H. Pottmann. Robust global registration. In Symposium on Geometry Processing, volume 2, page 5, 2005.

[0064] [8] Straub, T, Campbell, T., How, J.P. and Fisher, J.W., 2017. Efficient global point cloud alignment using Bayesian nonparametric mixtures. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (pp. 2941-2950).

[0065] [9] Lowe, D.G., 2004. Distinctive image features from scale-invariant keypoints. International journal of computer vision, 60(2), pp.91-110.