RO135778A0 - System and method for saving and retrieving certain user-defined regions or reference points in an n-dimensional data set - Google Patents

Abstract

The invention relates to a system and a method for saving and retrieving user-defined regions or reference points in a set of n-dimensional data that can be used, for example, to display multimedia content associated with an object of interest from a scanned real scene with an augmented reality application, for displaying electronic comments attached to a paragraph in a book, for displaying notes created by a doctor, attached to an area of interest in a set of radiographic images, and the like. According to the invention, the method comprises: obtaining, from an input device, or selecting, from a database, an n-dimensional data set, followed by selecting an area of interest, associating information attached to that area of interest and saving, in another database, a reference element containing meta-information for locating and/or identifying the n-dimensional data set, data in and around the area of interest (from an extended area), features of the extended area and information created/imported by the user, attached to the area of interest. The method also comprises obtaining or selecting another n-dimensional data set and retrieving, in the database with reference elements, the item to be mapped on the new n-dimensional data set and displaying the information attached to that item. The system comprises devices for obtaining data, processing data, storing data and displaying content, intended for the implementation of the method claimed by the invention, where the devices may be individual, for each stage of the method, or combined in the form of physical equipment covering several stages of method.

Description

RO 135778 AO

STATE OFFICE OF PENÎRU INVENTIIS AND APPLE'; Patent application

^ata denozit.....3..0.λ09.~.·Ζ0Ζ1

SYSTEM AND METHOD FOR SAVING AND RETRIEVING USER-DEFINED REGIONS OR REFERENCE POINTS IN AN N-DIMENSIONAL DATA SET

Presentation of the scope

The proposed system (invention) allows saving and retrieving regions or user-defined reference points in an n-dimensional data set. Examples of n-dimensional data are 2D/3D images, 2D/3D videos, sets of images of the same lens taken in different spectra (eg visible spectrum and infrared spectrum), point clouds obtained from depth cameras (eg LIDAR, stereo). Dimensions can be both spatial and temporal. Thus, an example of three-dimensional data can be represented by a stack of CT images containing sections through a body scanned with a Computer Tomograph device. Another example of three-dimensional data can be a video containing 2D frames, the first two dimensions representing image space and the third dimension being time. N-dimensional data can be distributed uniformly (isotropic) or non-uniformly (anisotropic). An example of an anisotropic dataset is a CT dataset, where the distance between pixels of a 2D section is the same on the x and y axes, but differs from the distance between two sections (on the z axis). There may also be regions of missing information in the n-dimensional data set. One such example is a point cloud obtained from a depth video camera, where the distance from the camera to some objects cannot be estimated (due to reflective surfaces or due to strong sunlight) resulting in missing information in the corresponding pixels of the image of depth.

The proposed system has two main functionalities:

1. Creating a reference element corresponding to a user-defined selection (area or point of interest) on an n-dimensional data set (acquired from a device or selected from a database) and saving it to a database benchmark data.

2. Obtaining existing information in the database of reference elements for an n-dimensional data set (acquired from a device or selected from a database) by selecting from the database the element that maps best on the n-dimensional data set. Mapping (the term "matching" in English) refers to matching information from the reference element with the n-dimensional data set or a part of it.

The proposed invention has applicability in several fields. An example usage scenario is displaying multimedia content associated with an object of interest from a real scene scanned with an augmented reality application. Another example is displaying electronic comments attached to a paragraph in a physical book. Another example is the display of physician-created notes attached to an area of interest in a set of radiographic images.

RO 135778 AO

Synthetic description of the invention

The first functionality of the system allows a user to create a reference element for a selected region or point of interest from an n-dimensional data set (acquired from an input device or selected from a database). The reference element, which contains the n-dimensional data in and around the selected area (optionally, features extracted from that area), meta-information locating or identifying the n-dimensional dataset, and user-input information, is saved in a database. Optionally, the system ensures the uniqueness of the reference elements in terms of the content of the selected area and the associated location/identification meta-information. Thus, if a user creates a reference item identical to another item in the database (same area of interest and same location/identification meta-information), the system may not insert a new item, but rather append the new user-created information to the existing element.

The second functionality of the system allows a user to obtain the existing information in the database of reference elements for a new set of n-dimensional data (acquired from a device or selected from a database). The system finds (through a matching algorithm) the reference element in the database that maps to the new data set and displays the information attached to that reference element.

When creating a reference element, there is a possibility that the user selects a small region of the n-dimensional data set that does not sufficiently characterize the area of which it is a part. An example is that in Figure 1, where a search algorithm run exclusively on the user-selected region of interest in the left image returns two images (Figure 1, top-right and bottom-right). To address this problem, the system expands the area selected by the user and saves additional information, depending on certain parameters that can be set in the system. Thus, creating a reference element for the extended area, the matching algorithm will return a single match, between the left image and the upper-right image.

The current stage of development of the field

The presented invention falls within the field of augmented reality and image processing. An example of use is the creation and saving of reference elements, similar to the so-called "cloud anchors" [1], in the ARCore framework [2]. Such an anchor, which represents a position and orientation relative to the coordinate system of a physical location, can be associated with one or more multimedia elements (eg, a 3D model), which are rendered on a user's device when, following a scan, an augmented reality application recognizes the anchor (the position and orientation of the device in the coordinate system of the current location). Finding commonalities from an input data set with other sets in a database is another problem related to the scope of the invention. This problem is intensively studied, especially for data such as 2D/3D images and videos. The common elements sought may be semantic in nature. An example semantic search algorithm can return all images in a database that contain cats, if the input image provided by the user contains a cat. Another example is finding text that contains the word "automobile", if the input data set provided by the user contains the word "vehicle". in other applications, the elements

A

V

RO 135778 Common AOs can be certain subsets of the data set (for example, a certain object or a logo in an image). There are also applications where a search returns only identical datasets, or which represent scans/reconstructions of the same physical object, in which case perspective or rotational transformations of the acquisition device do not influence the search. An example is the exact identification of a paragraph in a book (and not the identification of a text containing words with similar meaning). Another example would be returning from the database a scan (video or image) of the same physical object that is also represented in the input dataset. The presented invention is applied to the last case of use, in which it is desired to find similar reference elements in the database. However, some patent-like ideas and articles were identified in all areas of finding commonalities between multiple input sets. These ideas will be presented, highlighting the similarities, but also the differences compared to the current patent.

King et al [3] present a system that uses scanned text from a document, and context information, to identify an electronic document that corresponds to the scanned document. The user can access additional material associated with the digital document. Identification of the electronic document is accomplished by both text and context information (eg, a user's recent scan history, a user's reading habits, the user's geographic location). Similar to the current patent, King et al use location meta-information to retrieve reference elements. However, their solution only applies to texts. In addition, the retrieval algorithm searches only the text selected by the user, without expanding the area of interest or the selected text with information of the same nature (for example, words in sentences preceding or following the selected text).

Other patents in the field of text retrieval in a database are proposed by Lee [4] and Corman et al [5]. They expand the reference item (in this case, containing only text), but not by increasing the search area, but by using words that are syntactically related, words that generally occur together (in common expressions), synonyms and acronyms. Another search solution, proposed by Gallant et al. [6], also expands the searched text, but through a multidimensional clustering of word vectors and using semantically similar words. Unlike the methods presented in this paragraph, the present invention aims at exact mapping between an input element and elements in the database. where the present invention is applied to images (or other types of data) containing text, the mapping algorithm returns only an exact match between the selected text and those in the database.

Rahman et al. [7] propose a framework for finding common elements in images, combining global, semi-global and local features. Their method is based on combining descriptors extracted from different levels of image representation. The search method maps both whole images, including background information, and foreground objects. They also use algorithms to map some regions in the images. Similar to the current patent, part of their mapping method is based on features extracted from sub-images. However, they do not search for a minimal set of features, and they do not extend the search area starting from a region of interest, but use the whole image, combining different mapping methods (at the level of the whole image or some areas in the image). Mascarenhas and Volvoikar [8] present a feature generation method from large images with the SIFT detector [9]. The features are then clustered

RO 135778 AO through the k-means algorithm. The output of the k-means algorithm is filtered, resulting in a set of sub-images of the original image. A similarity to the current patent is the extraction of features from subimages for the mapping step. However, they search for similar images by performing a mapping of all sub-images from the original image. Their algorithm for checking the similarity between two sub-images is based on comparing the length of two polylines, each polyline passing through all the SIFT points of one of the two sub-images. Kong et al [10] describe an image mapping algorithm that uses the SIFT detector at both the global (over the entire image) and sub-image levels. They introduce a distance between corresponding key points to evaluate a measure of similarity. The input image is partitioned into 2 ^2s sub-images (^ = 0,1,..4). Similar to Mascarenhas and Volvoikar's method, this solution loops through all sub-images of the original image. Bhattacharya and Gavrilova [11] propose a strategy for automatically selecting regions of interest from images and extracting dense features from those regions. They use a weight given by the frequency of visual words in an image database to determine regions of interest and dense features. For an image, they determine regions of interest that contain points of interest calculated with the Harris-Laplace detector. Then, a maximum of 200 regions of interest are selected for each image. For image mapping, only dense features that lie within regions of interest and have a radius less than half the radius of the region of interest are considered. Unlike the mapping method in the current patent, Bhattacharya and Gavrilova's algorithm goes through all the regions of interest in the image and compares them to the regions of interest in the database (which were previously calculated, in an offline step).

Bryll [12] filed a patent that presents a method for image recognition using multiple templates in the image. This system allows defining a set of conditions for early removal of weakly mapped locations for different templates. A shared correlation map is created to determine the final set of mapping positions and corresponding templates. A similar use case is described in Atsushi's patent [13], where the similarity between a template in an input image and a region in the reference image is calculated. Similarity to non-evaluated positions is calculated by interpolation. Although there are some similarities between the current invention and the patents described in this paragraph, in terms of searching and retrieving parts of the image (patterns, in the case of Bryll and Atsushi, selected regions, in the case of the current patent), the use cases they are different. Thus, the systems presented by Bryll and Atsushi search for one or more templates in a single image without using an image database or other reference elements.

Grauman and Darrell [14] propose several object mapping methods in their patent. The first method consists of detecting interest points inside objects and computing feature descriptors at those interest points, building a multi-resolution histogram over the feature descriptors for each object and computing a weighted intersection based on the histograms. The second method defines multiple centers (called "bins") for multi-resolution histograms and multiple cluster groups. The third method creates a set of features for each object, mapping each set of feature vectors to a multidimensional vector, encoding each constituent vector with a binary hash string. Although, similar to the current patent, the system described by Grauman and Darrell is based on the use of features from h

RO 135778 AO image elements (objects) for the mapping step, they use all the extracted features, and not a minimal set of features. Moreover, they additionally build pyramids around local features and use information from them (weighted by level in the pyramid) to determine the similarity between an object in one image and an object in another image.

Romanik and Mayle are the inventors of several patents related to image mapping and object recognition in images. The first patent [15], more general, is continued by two other patents, one that is based on the use of regions in images [16], and another that uses a minimal set of characteristic points for mapping [17]. In the patent using image regions [16], it is checked whether an input image contains at least a portion of another image. The method divides the input image into regions and determines a set of feature points for each region. Contrary to the scope of the present invention, the system described by Romanik and Mayle does not solve the problem of finding identical images, but only determines whether an image contains identical portions in other images. In the patent that uses a minimal set of characteristic points [17], the image mapping is performed in two stages. In the first step (a filtering process), it is determined whether a single feature point template (from the database) matches the feature points in the input image. in the second stage, an exhaustive search is performed using "nearest neighbors" type algorithms. Similar to the current patent, an attempt is made to find a minimal set of features. However, they use a minimal set of features, but from a single database image template, for mapping to the input image, and not an extensible ROI.

Detailed description of the invention

The current invention has two main functionalities:

1. Create and save a reference item

2. Display information associated with a reference element

1. Create and save a reference item

The system allows the creation and saving of a reference element associated with an n-dimensional data set. Figure 2 illustrates the scheme of how the system works to define and save a reference element. The steps in the workflow are detailed below.

1. A user can use an acquisition device or select from a database an n-dimensional data set. This can consist of images, videos, 3D models, etc.

2. along with the actual data in the n-dimensional dataset, also acquire (or extract from the database) location or identification meta-information of the n-dimensional dataset (eg user location provided by GPS) .

3. The user then selects an area (or point) of interest from the n-dimensional data set. Any mechanism that selects a point in the n-dimensional data set or an area of interest (for example, a rectangular surface or

RO 135778 circular AO in a 2D data set, or a parallelepiped volume in a 3D data set). Examples of n-dimensional dataset selection mechanisms are:

o the "click" on the screen of the acquisition device for the selection of a point of interest, o the "click-drag-release" mechanism to select the top-left corner and the right-hand corner of a rectangular area of interest, o the mechanism to point with the finger/hand using a tracking technique built into a pair of smart glasses, a selection of consecutive words in a document on a reading device (ereader, smart phone, tablet), by pressing a word, and then swiping over the other words.

4. Expanding the area of interest, depending on certain parameters or certain criteria set at the system level. The parameters/criteria govern how far the area of interest extends. Examples of parameters that can be used to control the expansion of the area of interest are:

o reaching a minimum resolution of the extended area, o reaching a minimum number of features within the extended area, o reaching a minimum number of words or letters, if the dataset is searched using texts.

5. Optionally, if the matching algorithm works by feature mapping (such as SIFT/SURF/ORB, etc. in regular images or individual words in images containing text), features are extracted from the extended region. Also, if the region expansion is based on reaching a minimum number of features within the expanded area, this step can be done together with step 4.

6. The user adds information that attaches to the reference item. This information can be any kind of data created (for example, voice/video recordings purchased at that time) or imported by the user from existing databases or other sources. Examples of information associated with a selected area are:

o text comments o images (plain or animated) o audio elements (voice recordings, songs or sounds of any other nature) o videos o 3D models (with or without attached textures, with or without attached animations)

7. A reference element is created, with the following information:

o The n-dimensional data in and around the user-selected area of interest (extended area).

o n-dimensional dataset location or identification meta-information: additional information to the dataset from which the area of interest was selected that can help uniquely identify the reference element. Examples of location/identification metadata are:

• the user's location, obtained through GPS technology • a book's ISBN and page number • the ID of a scan • the user's ID

RO 135778 AO o Information entered by the user, associated with the selected area (defined in step 6)

8. The reference element created is saved in a database. Optionally, the reference database is checked for duplicates. Thus, if a user creates a reference item identical to another item in the database (same area of interest and same location/identification meta-information), the system may not add the new item to the database, but to append the new user-created information to the existing element.

The steps of selecting region of interest, expanding region of interest, extracting features, creating reference element, saving to database can be redone whenever needed for an n-dimensional data set. in this case it is necessary to save the original data (ndimensional data) in a database.

2. Display information attached to a reference element

The system allows the display of information attached to a reference element found in the database. Figure 3 illustrates how the system works when a user selects from a database or purchases a new n-dimensional data set, and the system finds the reference element in the database that maps to the new data set and displays the information attached to that reference element. The steps in the workflow are as follows:

1. A user can use an acquisition device or select from a database an n-dimensional data set. This set can consist of images, videos, 3D models, etc.

2. together with the actual data from the n-dimensional dataset, location/identification meta-information (eg user location, provided by GPS) is acquired (or extracted from the database).

3. if the matching algorithm uses features, features are extracted from the n-dimensional data set.

4. A search element is created, containing the location/identification meta-information and the n-dimensional data or set of features extracted from the n-dimensional data.

5. The reference element database is searched for the element(s) that map to the search element. Any existing matching method can be used, for example methods using SIFT/SURF/ORB descriptors. The matching algorithm will identify the reference element(s) with the highest degree of matching. If it exceeds a certain threshold (eg 95% match), the algorithm returns that reference. otherwise, the algorithm returns no result.

6. The information attached to the reference item identified in step 5 is displayed.

Description of figures

Figure 1 shows the mechanism for expanding the area of interest, in the image on the left. This mechanism ensures the existence of a sufficiently large number of data or characteristics in the extended area, so that when purchasing/selection of a new data set, the matching mechanism finds in the database only reference elements that match the information in the new set data. The top left image shows a data set that matches both the selected area data and the

RO 135778 AO data from the extended area. The lower right image shows a data set that matches the data in the selected area, but does not match the data in the extended area.

Figure 2 shows how the system works for creating benchmarks: acquisition/selection of a data set, selection of an area of interest, expansion of that area, extraction of features from the expanded area (optional), creation/import of information associated with the area of interest, creating and saving a reference element and ensuring the uniqueness of the reference element (optional).

Figure 3 shows how the system works to display existing information for a data set: acquisition/selection of a new data set, extraction of features from that data set (optional), running the matching step between the new data set and the elements of reference from the database and display the information attached to the reference element that maps to the new dataset.

Figures 2 and 3 also show the devices on which the method steps for saving and retrieving user-defined regions/waypoints are run. Thus, the device for acquiring n-dimensional data, selecting the area of interest, processing (for the steps of expanding the area of interest, extracting features, creating the reference element, inserting the reference element into the database, ensuring uniqueness of reference elements, creation of the search element, retrieval of reference elements in the database), the device to define the content attached to an area of interest and the device to display the content attached to an area of interest. It should be noted that these devices can be individual or there can be physical equipment that covers several steps of the proposed method. For example, a pair of smart glasses can be used for data acquisition, a controller for area of interest selection, a laptop for defining content and running some processing steps, and a server for running other processing steps. in contrast, a smart phone can be considered a data acquisition, area of interest selection, processing and content definition device at the same time.

The proposed system is composed of the following devices:

1. Device for acquiring n-dimensional data and meta-information for locating or identifying the n-dimensional data set

2. Processing device used for selection of n-dimensional data from a database and location/identification meta-information

3. N-dimensional data database storage device

4. (optional) Processing device used to insert n-dimensional data and location/identification meta-information into a database - only if it is desired to save the entire n-dimensional data set for further processing (e.g. , redoing the steps of selecting the area of interest, expanding the area, extracting features)

5. (optional) Database with n-dimensional data that stores data purchased by the user or selected from the database (point c)) with n-dimensional data - only if it is desired to save the entire set of n-dimensional data, for further processing (by

RO 135778 AO example, redoing the steps of selecting the area of interest, expanding the area, extracting features)

6. Selection device for selecting the area of interest

7. Processing device for expanding the area of interest

8. (optional) Processing device for extracting features from the extended area

9. Content definition device for creating/importing information attached to the area of interest

10. Processing device for creating the reference element

11. Processing device for inserting the reference element into the database

12. Device for storing the database with reference elements

13. (optional) Processing device for ensuring the uniqueness of reference elements (checking for duplicates and combining information from similar reference elements)

14. Processing device for creating the search element

15. Processing device for running the matching algorithm (which searches the database for the reference element(s) that map to a new data set acquired or selected from a database)

16. Content display device attached to the reference element identified by the matching algorithm.

RO 135778 AO

Bibliographical references

[1] “Cloud anchors.” https://developers.google.com/ar/develop/java/cloud-anchors/overviewandroid (accessed Oct. 12, 2020).

[2] “ARCore homepage.” https.7/developers.google.com/ar (accessed Nov. 01, 2019).

[3] M. T. King, D. L. Grover, C. A. Kushler, and J. Q. Stafford-fraser, “Adding Value to a Rendered Document,” Jun. 2008.

[4] W. S. Lee, "Method and device for indexing plural granularities and supporting expansion of query while effectively using query processing," JP2000137738A, 2000.

[5] J. M. Corman et al., "Method and system for universal querying of distributed databases," US6523028B 1, 2003.

[6] M. Gallant, H. Isah, F. Zulkemine, and S. Khan, “Xu: An Automated Query Expansion and Optimization Tool,” in 2019 IEEE 43rd Annual Computer Software and Applications Conference (COMPSAC), 2019, vol. 1, pp. 443^-52, doi: 10.1109/COMPSAC.2019.00070.

[7] M. M. Rahman, B. C. Desai, and P. Bhattacharya, "A Feature Level Fusion in Similarity Matching to Content-Based Image Retrieval," in 2006 9th International Conference on Information Fusion, 2006, pp. 1-6, doi: 10.1109/ICIF .2006.301664.

[8] M. Mascarenhas and A. T. Volvoikar, "An efficient method to match large images," in 2016 International Conference on Advanced Communication Control and Computing Technologies (ICACCCT), 2016, pp. 318-321, doi: 10.1109/ICACCCT.2016.7831654 .

[9] D. G. Lowe, "Object recognition from local scale-invariant features," in Proceedings of the Seventh IEEE International Conference on Computer Vision, 1999, vol. 2, pp. 11501157 vol.2, doi: 10.1109/ICCV.1999.790410.

[10] B. Li, X. Kong, Z. Wang, and H. Fu, “SIFT-Based Image Retrieval Combining the Distance Measure of Global Image and Sub-Image,” in 2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing, 2009, pp. 706-709, doi: 10.1109/IIH-MSP.2009.180.

[11] P. Bhattacharya and M. L. Gavrilova, "Combining dense features with interest regions for efficient part-based image matching," in 2014 International Conference on Computer Vision Theory and Applications (VISAPP), 2014, vol. 2, pp. 68-75.

[12] R. K. Bryll, "Fast multiple template matching using a shared correlation map," US20080025616A1, 2006.

[13] H. Atsushi, "Template matching method and device, and recording medium where program therefore is recorded," WO2006075594A1, 2006.

[14] K. Grauman and T. Darrell, “Pyramid match kemel and related techniques,” US7949186B2, 2007.

[15] P. B. Romanik and N. L. Mayle, "Systems, methods, and devices for image matching and object recognition in images," US20160012311A1, 2015.

r i' \ \

RO 135778 AO

[16] P. B. Romanik and N. L. Mayle, "Systems, methods, and devices for image matching and object recognition in images using image regions," 14/745422, 2015.

[17] N. L. Mayle and P. B. Romanik, "Systems, methods, and devices for image matching and object recognition in images using minimal feature points," US9330329B2, 2015.

λ \\

Claims (4)

RO 135778 AO demand 1. System and method for saving and retrieving user-defined regions or reference points in an n-dimensional data set, characterized in that it allows the acquisition or selection from a database of an n- dimensions, selection of a point or area of interest from the dataset, and creation/import of information attached to the area of interest. The system creates and saves in a database a reference element containing the location/identification meta-information associated with the n-dimensional data, the data in and around the area of interest (extended area), the features extracted from the extended area (optional ) and the information attached by the user to the area of interest. 2. System and method for saving and retrieving user-defined regions or reference points in an n-dimensional data set, according to claim 1, characterized in that it allows the acquisition or selection from one database of another n-dimensional data set (different from that mentioned in claim 1) and displaying the information attached to the reference item in the database that matches the new n-dimensional data set. 3. System and method for saving and retrieving user-defined regions or reference points in an n-dimensional data set, according to claim 1, characterized in that it allows a method of expanding a user-selected area of interest in an n-dimensional data set acquired or selected from a database, ensuring a sufficient number of data for a correct match between the created reference element and other data sets acquired by the same or another user. 4. System and method for saving and retrieving regions or reference points defined by a user in an n-dimensional data set, according to claim 1, characterized in that the method of creating and saving a reference element allows the association user-created/imported information with an area of interest selected from the n-dimensional dataset, the reference element containing: o The n-dimensional data in and around the selected area (extended area) o Meta-information to locate or identify the n-dimensional data o User-created/imported information attached to the area of interest 5: System and method for saving and retrieving user-defined regions or reference points in an n-dimensional data set, according to claim 1, characterized in that the method of displaying information attached to a reference element allows the acquisition or selection from a database of a new n-dimensional data set, searches the datum database for that datum that maps to the new dataset, and displays the information attached to that datum.