Image change detection

• US 9,396,552 B1
• Filed: 06/12/2015
• Issued: 07/19/2016
• Est. Priority Date: 06/12/2015
• Status: Active Grant

• Current Assignee: Intergraph Corporation (Hexagon AB)
• Original Assignee: Intergraph Corporation (Hexagon AB)
• Inventors: Kloer, Brian R.
• Primary Examiner(s): Alavi, Amir
• Application Number:
  US14/738,374
• Time in Patent Office: 403 Days
• US Class Current: 1/1
• CPC Class Codes: G06Q 40/10 Tax strategies
• CPC Class Codes: G06T 11/60 Editing figures and text; Combining figures or text
• CPC Class Codes: G06T 2207/10024 Color image
• CPC Class Codes: G06T 2207/30184 Infrastructure
• CPC Class Codes: G06T 7/20 Analysis of motion motion estimation for coding, decoding, compressing or decompressing digital video signals H04N19/43, H04N19/51
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods
• CPC Class Codes: G06V 20/13 Satellite images

Abstract

A system, method, and computer program product compare images of a physical activity or object. Pixel data from first and second registered color images defined in an N-dimensional color model are concatenated to form an image in a 2N-dimensional color model. Principal component analysis is performed on the composite image and those components representing a change rather than a correlation are identified. In the composite image, coordinates for each pixel are determined along the principal components representing change, and a normalized pixel change value is computed. Pixels in the composite image may be segmented according to their respective normalized pixel change values, where segments do not cross pre-defined geospatial parcel boundaries. Parcel change probabilities are calculated as a function of segment change probabilities, themselves functions of the normalized pixel change values. Finally, parcels are ranked by their change probabilities and highlighted in a graphical user interface.

Claims

1. A method of comparing first and second digital color images having registered pixels, each pixel having data for N colors, the first digital color image having an appearance of a physical activity or object at a first time, the second digital color image having an appearance of the physical activity or object at a second time, the method comprising:

forming a composite image having pixels in a 2N-dimensional color model by defining color data for each pixel in the composite image as a concatenation of the color data for a pixel in the first digital color image with the color data for a registered pixel in the second digital color image;

determining a set of principal components of the composite image using a principal component analysis, the set of principal components defining a coordinate system in the 2N-dimensional color model;

selecting a subset of principal components in the coordinate system as those principle components that each represent a difference, rather than a correlation, between the first digital color image and the second digital color image; and

for each pixel in the composite image, computing a normalized pixel change value as a function of the coordinates of the pixel color data along each principal component in the subset, the normalized pixel change values collectively defining a change image having a one-dimensional color model, the computed normalized pixel change value for each pixel measuring a change in the physical activity or object between the first time and the second time.

2. A method according to claim 1, wherein N=3 and each pixel has red, green, and blue (RGB) color data.

3. A method according to claim 1, wherein N=4 and each pixel has red, green, blue, and infrared (RGB IR) color data.

4. A method according to claim 1, wherein selecting the subset of principal components comprises, for each principal component of the composite image, (a) forming an N-dimensional difference vector by subtracting a first N-dimensional portion of the principal component that represents the first digital color image from a second N-dimensional portion of the principal component that represents the second digital color image, and (b) selecting the principal component for inclusion in the subset if and only if the N-dimensional length of the difference vector is greater than a given length.

5. A method according to claim 1, wherein the normalized pixel change value for each pixel is computed to be the maximum of the coordinates of the color data of the pixel along each principal component in the subset.

6. A method according to claim 1, further comprising, prior to determining the set of principal components of the composite image, removing from the composite image those pixels having a brightness that is less than a shadow threshold value.

7. A method according to claim 1, wherein the physical activity or object is a municipality, the first digital color image represents an appearance of the municipality at a first time, the second digital color image represents an appearance of the municipality at a second time, and the municipality is divided into a plurality of parcels, the method further comprising:

dividing the change image into a plurality of segments, wherein (a) each given segment in the plurality of segments is formed from contiguous pixels and lies entirely within a parcel in the plurality of parcels, and (b) membership, in the given segment, of each pixel is determined as a function of its normalized pixel change value;

computing, for each segment in the plurality of segments, a segment change probability as a function of the normalized pixel change values of the pixels that form it;

computing, for each parcel in the plurality of parcels, a parcel change probability as a function of the segment change probabilities of the segments that lie within it; and

ranking the parcels in the plurality of parcels according to their respective parcel change probabilities.

8. A method according to claim 7, wherein the first digital color image and the second digital color image represent appearances of the municipality that are approximately a whole number of years apart.

9. A method according to claim 7, wherein the segment change probability for each segment in the plurality of segments is computed to be the average of the normalized pixel change values of the pixels that form it.

10. A method according to claim 7, further comprising, prior to computing the parcel change probability, eliminating segments that have a segment change probability below a segment change threshold value.

11. A method according to claim 7, further comprising, prior to computing the parcel change probability, eliminating segments that consist of a number of pixels representing an area having a number of square feet below a segment size threshold value.

12. A method according to claim 7, wherein the parcel change probability for each parcel in the plurality of parcels is computed as the sum, over each segment that lies within the given parcel, of the product of the segment change probability of the given segment and the ratio between the number of pixels in the given segment and the number of pixels in the parcel that contains the given segment.

13. A method according to claim 7, further comprising providing a graphical user interface (GUI) for a computer system, the GUI displaying a portion of the first digital color image next to a corresponding portion of the second digital color image to permit visual comparison of the portions by a user of the computer system.

14. A method according to claim 13, further comprising simultaneously displaying in the GUI (a) a distinctive outline of a parcel within the portion of the first digital color image, (b) a distinctive outline of the parcel within the corresponding portion of the second digital color image, and (c) a control for receiving a selection indicating that the parcel has meaningfully changed, has not meaningfully changed, or requires further analysis.

15. A method according to claim 13, further comprising providing in the GUI a control that permits the user to adjust a shadow threshold value, a segment change threshold value, or a segment size threshold value.

16. A non-transitory, tangible computer readable storage medium on which is stored computer program code for comparing first and second digital color images having registered pixels, each pixel having data for N colors, the first digital color image having an appearance of a physical activity or object at a first time, the second digital color image having an appearance of the physical activity or object at a second time, the storage medium including program code for:

forming a composite image having pixels in a 2N-dimensional color model by defining color data for each pixel in the composite image as a concatenation of the color data for a pixel in the first digital color image with the color data for a registered pixel in the second digital color image;

determining a set of principal components of the composite image using a principal component analysis, the set of principal components defining a coordinate system in the 2N-dimensional color model;

selecting a subset of principal components in the coordinate system as those principle components that each represent a difference, rather than a correlation, between the first digital color image and the second digital color image; and

for each pixel in the composite image, computing a normalized pixel change value as a function of the coordinates of the pixel color data along each principal component in the subset, the normalized pixel change values collectively defining a change image having a one-dimensional color model, the computed normalized pixel change value for each pixel measuring a change in the physical activity or object between the first time and the second time.

17. A storage medium according to claim 16, wherein the program code for selecting the subset of principal components comprises program code for, for each principal component of the composite image, (a) forming an N-dimensional difference vector by subtracting a first N-dimensional portion of the principal component that represents the first digital color image from a second N-dimensional portion of the principal component that represents the second digital color image, and (b) selecting the principal component for inclusion in the subset if and only if the N-dimensional length of the difference vector is greater than a given length.

18. A storage medium according to claim 16, wherein the program code for computing the normalized pixel change value for each pixel comprises program code for selecting the maximum of the coordinates of the color data of the pixel along each principal component in the subset.

19. A storage medium according to claim 16, wherein the program code for computing the normalized pixel change value for each pixel comprises program code for averaging the coordinates of the color data of the pixel along each principal component in the subset.

20. A storage medium according to claim 16, wherein the program code further comprises program code for, prior to determining the set of principal components of the composite image, removing from the composite image those pixels having a brightness that is less than a shadow threshold value.

21. A storage medium according to claim 16, wherein the physical activity or object is a municipality, the first digital color image represents an appearance of the municipality at a first time, the second digital color image represents an appearance of the municipality at a second time, and the municipality is divided into a plurality of parcels, the storage medium further including program code for:

dividing the change image into a plurality of segments, wherein (a) each given segment in the plurality of segments is formed from contiguous pixels and lies entirely within a parcel in the plurality of parcels, and (b) membership, in the given segment, of each pixel is determined as a function of its normalized pixel change value;

computing, for each segment in the plurality of segments, a segment change probability as a function of the normalized pixel change values of the pixels that form it;

computing, for each parcel in the plurality of parcels, a parcel change probability as a function of the segment change probabilities of the segments that lie within it; and

ranking the parcels in the plurality of parcels according to their respective parcel change probabilities.

22. A storage medium according to claim 21, wherein the program code for computing the segment change probability for each segment in the plurality of segments comprises program code for computing the average of the normalized pixel change values of the pixels that form it.

23. A storage medium according to claim 21, further comprising program code for, prior to computing the parcel change probability, eliminating segments that have a segment change probability below a segment change threshold value.

24. A storage medium according to claim 21, further comprising program code for, prior to computing the parcel change probability, eliminating segments that consist of a number of pixels representing an area having a number of square feet below a segment size threshold value.

25. A storage medium according to claim 21, wherein the program code for computing the parcel change probability for each parcel in the plurality of parcels comprises program code for computing the sum, over each segment that lies within the given parcel, of the product of the segment change probability of the given segment and the ratio between the number of pixels in the given segment and the number of pixels in the parcel that contains the given segment.

26. A storage medium according to claim 21, further comprising program code for providing a graphical user interface (GUI) for a computer system, the GUI displaying a portion of the first digital color image next to a corresponding portion of the second digital color image to permit visual comparison of the portions by a user of the computer system.

27. A storage medium according to claim 26, further comprising program code for simultaneously displaying in the GUI (a) a distinctive outline of a parcel within the portion of the first digital color image, (b) a distinctive outline of the parcel within the corresponding portion of the second digital color image, and (c) a control for receiving a selection indicating that the parcel has meaningfully changed, has not meaningfully changed, or requires further analysis.

28. A storage medium according to claim 26, further comprising program code for providing in the GUI a control that permits the user to adjust a shadow threshold value, a segment change threshold value, or a segment size threshold value.

29. A computer system for comparing first and second digital color images having registered pixels, each pixel having data for N colors, the first digital color image having an appearance of a physical activity or object at a first time, the second digital color image having an appearance of the physical activity or object at a second time, the computer system comprising:

a volatile memory having stored within it computer program code for;

forming a composite image having pixels in a 2N-dimensional color model by defining color data for each pixel in the composite image as a concatenation of the color data for a pixel in the first digital color image with the color data for a registered pixel in the second digital color image;

determining a set of principal components of the composite image using a principal component analysis, the set of principal components defining a coordinate system in the 2N-dimensional color model;

selecting a subset of principal components in the coordinate system as those principle components that each represent a difference, rather than a correlation, between the first digital color image and the second digital color image; and

for each pixel in the composite image, computing a normalized pixel change value as a function of the coordinates of the pixel color data along each principal component in the subset, the normalized pixel change values collectively defining a change image having a one-dimensional color model, the computed normalized pixel change value for each pixel measuring a change in the physical activity or object between the first time and the second time;

a microprocessor, coupled to the volatile memory, configured to execute the computer code stored in the volatile memory;

one or more output interfaces, coupled to the microprocessor, for providing a graphical user interface that displays a portion of the first digital color image next to a corresponding portion of the second digital color image to permit visual comparison of the portions by a user of the computer system; and

one or more input interfaces, coupled to the microprocessor, for receiving a selection indicating that the displayed portions have meaningfully changed, have not meaningfully changed, or require further analysis.