Image-guided abstraction of building facades

• US 8,238,651 B2
• Filed: 06/20/2008
• Issued: 08/07/2012
• Est. Priority Date: 06/05/2008
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Adabala, Neeharika, Loya, Aniruddha, Das, Amitava, Mishra, Pragyana K.
• Primary Examiner(s): Sherali, Ishrat I
• Application Number:
  US12/142,806
• Publication Number:
  US 20090304297A1
• Time in Patent Office: 1,509 Days
• Field of Search: 382162-167, 382/154, 382/284, 345419-420, 345/426, 345/582, 345/589, 345/473, 345/469, 701/438
• US Class Current: 382/162
• CPC Class Codes: H04N 19/60 using transform coding
• CPC Class Codes: H04N 19/94 Vector quantisation

Abstract

To reduce the amount of storage space and computing power required to render image data, particularly building image data, primary and secondary colors may be extracted from the image data. The image data may be re-rendered using only the primary and secondary colors. The re-rendered image may be evaluated for patterns, the patterns thresholded to bi-level data and a Discrete Fourier Transform (DFT), or equivalent, may be performed on the bi-level data. Low order coefficients may be discarded depending on level accuracy desired. DFT coefficients and color data for the primary and secondary colors may then be used to construct an abstraction of the original image data, using data that is, in some cases, three or four orders of magnitude smaller than the original image data.

Claims

1. A method of modeling image data performed by a computing device comprised of a processor and storage storing the image data, the method comprising:

determining, by the processor, a first and second dominant color and storing in the storing information identifying the first and second dominant colors;

identifying, by the processor, a structural feature of the image data and storing information identifying the structural feature in the storage;

extracting, by the processor, modeling parameters from the structural feature and stroing the modeling parameters in the storing; and

generating by the processor a model of the image data for generating a representation of the image data and storing the model in the storage.

2. The method of claim 1, wherein determining the first and second dominant colors comprises:

defining at least two color classifications;

selecting a color range for each of the at least two color classifications;

sorting each color present in the image data into one of the at least two color classifications;

selecting the first dominant color as a first color associated with a color classification from the at least two color classifications having a highest number of occurrences from the sorting of each color present; and

selecting the second dominant color as a second color associated with another of the at least two color classifications having a second highest number of occurrences from the sorting of each color present.

3. The method of claim 2, wherein the sorting each color present in the image data comprises hashing color values into the at least two color classifications.

4. The method of claim 3, further comprising selecting a first color classification using a mean color value of the image data.

5. The method of claim 4, further comprising selecting a second color classification according to a standard deviation of the mean color value of the image data.

6. The method of claim 1, wherein the image data comprises pixels, and wherein the determining the first and second dominant color comprises:

calculating a set of centroids from a centroid for each pixel of the image data using pixel color values;

performing a histogram analysis on the set of centroids; and

selecting the first and second dominant color from the histogram analysis.

7. The method of claim 1, wherein the identifying the structural feature of the image data comprises:

reconstructing the image data using the first and second dominant colors;

developing a first waveform from a horizontal projection of the first and second dominant colors;

developing a second waveform from a vertical projection of the first and second dominant colors;

selecting a first and second threshold value for the first and second waveforms, respectively;

generating a first square wave corresponding to a horizontal structural feature by digitizing the first waveform around the first threshold value; and

generating a second square wave corresponding to a vertical structural feature by digitizing the second waveform around the second threshold value.

8. The method of claim 7, wherein the developing the first waveform and the developing the second waveform further comprise:

developing a series of first waveforms from a series of horizontal projections at varying angles;

selecting the first waveform using one of the horizontal projections with an angle having a maximum difference between high and low first waveform values;

developing a series of second waveforms from a series of vertical projections at varying angles;

selecting the second waveform using one of the vertical projections with an angle having a maximum difference between high and low second waveform values.

9. The method of claim 7, wherein the extracting modeling parameters from the structural feature comprises:

performing a Discrete Fourier Transform (DFT) on the first square wave to create a first DFT result;

performing another Discrete Fourier Transform on the second square wave to create a second DFT result;

retaining a selected number of coefficients of the first and second DFT results to create first and second trimmed DFT results;

performing Inverse Discrete Fourier Transforms on the first and second trimmed DFT results; and

determining a mean threshold and digitizing each of the first and second trimmed DFT results to create modeling parameters from the structural feature.

10. The method of claim 9, further comprising:

computing a maximum length for which each of the first and second square waves have a value of 1 and 0 to determine a period for each square wave, respectively; and

performing the DFT on the first square wave over one period of the first square wave to allow reduction of the selected number of coefficients;

performing the other DFT on the second square wave over one period of the second square wave to allow reduction of the selected number of coefficients.

11. The method of claim 9, further comprising:

creating modeling parameters for one period of each of the first and second square waves representing a tile of the image data; and

generating the representation of the image data using successive tiles of the image data.

12. The method of claim 7, further comprising:

determining one or more secondary colors;

reconstructing the image data using the first and second dominant colors and the one or more secondary colors;

developing a third waveform from another horizontal projection of the first and second dominant colors and the one or more secondary colors;

developing a fourth waveform from another vertical projection of the first and second dominant colors and the one or more secondary colors;

subtracting the first waveform from the third waveform to identify a secondary horizontal structural feature of the image data; and

subtracting the second waveform from the fourth waveform to identify a secondary vertical structural feature of the image data.

13. The method of claim 7, wherein extracting modeling parameters from the structural feature comprises:

performing a first Haar wavelet transform on the first square wave;

performing a second Haar wavelet transform on the second square wave; and

selecting a number of coefficients of the first and second Haar wavelets corresponding to a desired resolution of the model of the image data.

14. The method of claim 1, further comprising:

adjusting the first and second dominant colors according to a lighting condition when generating a representation of the image data.

15. A method of constructing an image abstraction comprising pixels, the method performed by a computing device comprised of storage and a processor, the method comprising:

receiving and storing in the storage color information for at least two primary colors;

receiving and storing in the storage algorithm coefficients;

reconstructing, by the processor, horizontal and vertical binary projection waveforms using the algorithm coefficients;

assigning, by the processor, and storing the storage, color information for the at least two primary colors to the binary projection waveforms;

assigning, by the processor, and storing in the storage, color values to each pixel in the image abstraction using the horizontal and vertical projection waveforms; and

saving in the storage each pixel in the image abstraction.

16. The method of claim 15, wherein receiving algorithm coefficients comprises receiving Discrete Fourier Transform coefficients.

17. The method of claim 15, further comprising:

applying the image abstraction to a building model.

18. The method of claim 15, further comprising:

receiving color information for a third primary color; and

assigning the third primary color information to the binary projection waveforms.

19. The method of claim 15, wherein the reconstructing horizontal and vertical binary projection waveforms is performed using a Haar wavelet transform.