# US 10,504,000 B2 · Methods, systems, and computer readable media for image overlap detection > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 10,504,000 B2 - Document ID: US10504000B2 - Status: Granted - Kind: B2 - Application number: 15/561,195 - Filed: 2016-03-24 - Published: 2018-03-22 - Granted: 2019-12-10 - Earliest claimed: 2015-03-25 - Assignees: The University of North Carolina at Chapel Hill - Applicants: The University of North Carolina at Chapel Hill - Inventors: Jared Scott Heinly; Johannes Lutz Schoenberger; Enrique Dunn; Jan-Michael Frahm - Web page: https://patentgrep.com/patent/US10504000B2 ## CPC - G06T 7/33: using feature-based methods - G06F 16/00: Information retrieval; Database structures therefor; File system structures therefor - G06F 16/51: Indexing; Data structures therefor; Storage structures - G06F 16/5838: {using colour} - G06F 18/23: Clustering techniques - G06V 10/462: {Salient features, e.g. scale invariant feature transforms [SIFT]} - G06V 20/30: in albums, collections or shared content, e.g. social network photos or video - G06V 20/64: Three-dimensional [3D] objects - G06T: IMAGE DATA PROCESSING OR GENERATION, IN GENERAL - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) - G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING ## Abstract Methods, systems, and computer readable media for image overlap detection. An example method includes identifying, by one or more computers, a collection of images; streaming, by the one or more computers, each image from the collection of images so that, in one or a limited number of passes through the collection of images, each image is loaded only once from an input source and each image is discarded after a processing time for the image is exceeded; and during the streaming, for each image in at least a first subset of the images in the collection, determining whether the image overlaps with at least one other image in the at least a first subset of the images. ## Claims ### Claim 1 A method of image pair overlap detection, the method comprising: identifying, by one or more computers, a collection of images; streaming, by the one or more computers, each image from the collection of images so that, in one or a limited number of passes through the collection of images, each image is loaded into memory only once from an input source and each image is discarded from the memory after a processing time for the image is exceeded; and during the streaming, for each image in at least a first subset of the images in the collection, determining whether the image overlaps with at least one other image in the at least a first subset of the images, including determining that a first image loaded into the memory overlaps a second image not loaded into the memory; wherein streaming each image and determining whether the image overlaps with at least one other image comprises executing an initial pass through at least a first batch of the collection of images and establishing a plurality of iconic images, each iconic image representing a scene depicted in the collection of images; and wherein determining that the first image loaded into the memory overlaps the second image not loaded into the memory comprises matching, while streaming each image from the collection of images and when the first image is loaded into the memory during stream, the first image and the second image to one of the iconic images. ### Claim 2 (depends on 1) The method of claim 1, wherein executing the initial pass through the collection of images comprises: determining whether a given image matches one or more nearest neighbor iconic images. ### Claim 3 (depends on 2) The method of claim 2, comprising, in response to determining that the given image matches one or more nearest neighbor iconic images, assigning the given image to an image cluster associated with one or more best matching nearest neighbor iconic images. ### Claim 4 (depends on 3) The method of claim 3, wherein assigning the given image to the image cluster comprises adding one or more visual words of inlier features of the given image to a set of visual words for the best matching nearest neighbor iconic image. ### Claim 5 (depends on 2) The method of claim 2, wherein executing the initial pass through the collection comprises, for at least a first image in the collection of images: determining that the first image does not match any of the nearest neighbor iconic images; and establishing a new iconic image based on the first image. ### Claim 6 (depends on 2) The method of claim 2, wherein executing the initial pass through the collection comprises, for at least a first image in the collection of images: determining that the first image matches two or more nearest neighbor iconic images; and merging image clusters associated with the two or more nearest neighbor iconic images. ### Claim 7 (depends on 2) The method of claim 2, wherein determining whether the given image matches the one or more nearest neighbor iconic images comprises determining one or more visual words for the given image and querying an index for the one or more nearest neighbor iconic images. ### Claim 8 (depends on 2) The method of claim 2, comprising performing geometric verification on the given image with respect to the nearest neighbor iconic images. ### Claim 9 (depends on 1) The method of claim 1, comprising building a 3D model of a scene depicted in the collection of images using results of the determining. ### Claim 10 A system comprising: at least one processor; and at least one computer readable medium storing instructions that, when executed by the at least one processor, causes the at least one processor to perform operations comprising: identifying a collection of images; streaming each image from the collection of images so that, in one or a limited number of passes through the collection of images, each image is loaded into memory only once from an input source and each image is discarded from the memory after a processing time for the image is exceeded; and during the streaming, for each image in at least a first subset of the images in the collection, determining whether the image overlaps with at least one other image in the at least a first subset of the images, including determining that a first image loaded into the memory overlaps a second image not loaded into the memory; wherein streaming each image and determining whether the image overlaps with at least one other image comprises executing an initial pass through at least a first batch of the collection of images and establishing a plurality of iconic images, each iconic image representing a scene depicted in the collection of images; and wherein determining that the first image loaded into the memory overlaps the second image not loaded into the memory comprises matching, while streaming each image from the collection of images and when the first image is loaded into the memory during stream, the first image and the second image to one of the iconic images. ### Claim 11 (depends on 10) The system of claim 10, wherein executing the initial pass through the collection of images comprises: determining whether a given image matches one or more nearest neighbor iconic images. ### Claim 12 (depends on 11) The system of claim 11, the operations comprising, in response to determining that the given image matches one or more nearest neighbor iconic images, assigning the given image to an image cluster associated with one or more best matching nearest neighbor iconic images. ### Claim 13 (depends on 12) The system of claim 12, wherein assigning the given image to the image cluster comprises adding one or more visual words of inlier features of the given image to a set of visual words for the best matching nearest neighbor iconic image. ### Claim 14 (depends on 11) The system of claim 11, wherein executing the initial pass through the collection comprises, for at least a first image in the collection of images: determining that the first image does not match any of the nearest neighbor iconic images; and establishing a new iconic image based on the first image. ### Claim 15 (depends on 11) The system of claim 11, wherein executing the initial pass through the collection comprises, for at least a first image in the collection of images: determining that the first image matches two or more nearest neighbor iconic images; and merging image clusters associated with the two or more nearest neighbor iconic images. ### Claim 16 (depends on 11) The system of claim 11, wherein determining whether the given image matches the one or more nearest neighbor iconic images comprises determining one or more visual words for the given image and querying an index for the one or more nearest neighbor iconic images. ### Claim 17 (depends on 11) The system of claim 11, the operations comprising performing geometric verification on the given image with respect to the nearest neighbor iconic images. ### Claim 18 (depends on 11) The system of claim 11, the operations comprising building a 3D model of a scene depicted in the collection of images using results of the determining. ### Claim 19 A non-transitory computer readable medium having stored thereon executable instructions that when executed by a processor of a computer control the computer to perform steps comprising: identifying a collection of images; and streaming each image from the collection of images so that, in one or a limited number of passes through the collection of images, each image is loaded into memory only once from an input source and each image is discarded from the memory after a processing time for the image is exceeded; and during the streaming, for each image in at least a first subset of the images in the collection, determining whether the image overlaps with at least one other image in the at least a first subset of the images, including determining that a first image loaded into the memory overlaps a second image not loaded into the memory; wherein streaming each image and determining whether the image overlaps with at least one other image comprises executing an initial pass through at least a first batch of the collection of images and establishing a plurality of iconic images, each iconic image representing a scene depicted in the collection of images; and wherein determining that the first image loaded into the memory overlaps the second image not loaded into the memory comprises matching, while streaming each image from the collection of images and when the first image is loaded into the memory during stream, the first image and the second image to one of the iconic images.