Method and apparatus for determining image content

A method and apparatus of processing image data comprises correlating received image data. Image statistics are computed based upon the correlated image and eccentricity is estimated based upon the computed image statistics. An entropy metric of the correlated received image data is determined. An interpretation based upon the image statistics, estimated eccentricity, and entropy metric is performed and a report including the content of the processed image data is generated.

FIELD OF INVENTION

The present invention is directed to data processing. More particularly, the present invention is directed to a method and apparatus for processing image data.

BACKGROUND

In image processing, discerning the structure of an image is often a challenging undertaking. The structure of an image may be characterized by many attributes, such as fractal, aliased, noisy, flat or featureless, periodic, and the like. Each of these characteristics poses a challenge to analyzing the structure.

Periodic patterns, for example, can assume almost any shape, at almost any scale, may range widely in frequency of occurrence, and may occur at any location in the image. Accordingly, detecting the presence of periodic patterns with these degrees of freedom may be difficult. In particular, it may be a more difficult problem than detecting a harmonic such as a pure tone at 20 kHz. Therefore, a simple Fourier transform will not easily reveal many of the essential properties of a periodic pattern. Additionally, content structure and content spectra should not be confused, despite the fact that the mappings may be one-to-one.

Since periodic patterns range from totally featureless, (i.e., flat content having zero period), all the way up to the Nyquist frequency and beyond where they can degenerate into essentially chaotic content, examining the fully normalized phase plane correlation surface for periodicity is often not useful. Additionally, a combination or super-positioning of two or more types of periodic patterns can appear simultaneously when they are spatially co-located. Accordingly, normalized phase plane correlation can mask characteristics in the content structure.

Many attempts have been made to determine the content of image structure. However, the vast majority of these attempts focus on using the spectrum of the Fourier transform for this purpose, which is not very effective. Accordingly, it would be beneficial to provide a method and apparatus for processing image data that aids in effectively determining the content of an image.

SUMMARY

A method and apparatus of processing image data is disclosed. The method comprises correlating received image data. Image statistics are computed based upon the correlated image and eccentricity is estimated based upon the computed image statistics. An entropy metric of the correlated received image data is determined. An interpretation based upon the computed image statistics, estimated eccentricity, and entropy metric is performed and a report including the content of the processed image data is generated.

DETAILED DESCRIPTION

The present invention relates to a method and apparatus to infer the structure of an image content. The method, in one example, computes an autocorrelation function and interprets the computed autocorrelation. Some of the metrics to interpret the computed autocorrelation include estimating the content of an image, computing measures of confidence, estimating content periodicity, estimating content flatness, estimating content frequency, estimating content noisiness, and estimating content entropy. These metrics may then be combined utilizing a pre-defined set of rules to provide an estimate of the overall image surface content characteristics.

FIG. 1is a functional block diagram of an apparatus100for processing data including a processor110and a display120. As shown inFIG. 1, the processor110is configured to receive data in and produce a processed data out. This processed data out may be forwarded to the display120where it may be viewed and utilized.

FIG. 2is a functional block diagram of the processor110ofFIG. 1. The processor110includes a correlation block111, a property computation block112, an eccentricity estimator113, a contour analysis block114, an entropy metric determination block115, an interpretation block116, and a generation block117. Data is received by the correlation block111. For example, the data in to the correlation block111may be image data.

Although the steps performed by each functional block of the processor110will be described in more detail below, briefly, the correlation block111performs a correlation on the data in after receiving it. The property computation block112computes properties related to the correlated data and the eccentricity estimator block113performs an estimation of eccentricity on the data. A contour analysis is performed by the contour analysis block114and the entropy metric determination block115performs a determination of entropy. Rules are applied at the interpretation block116to interpret the metrics measured or computed and a report is generated at the generation block117. The generation block117is also capable of outputting the report as data out, which may be forwarded to, for example, the display120ofFIG. 1.

FIG. 3is a method300for processing image data in accordance with the present invention.FIG. 3is described in connection withFIGS. 4-12to more clearly illustrate an example implementation of method300. In step310, a received image is correlated. For purposes of example,FIG. 4is an example image400for processing in accordance with the method300ofFIG. 3.

FIG. 4shows an image400of the flag of the United States of America. The image400, and particularly the flag itself, includes portions that are highly periodic. The portion410identified by the rectangle in the image400may be considered for purposes of example of the method300. The portion410identified includes a 64 by 128 block containing the stars from the flag.

FIG. 5is a graph500of an adjusted autocorrelation surface of the portion410of the example image400ofFIG. 4. As shown inFIG. 5, the adjusted autocorrelation surface is non-normalized and includes a phase plane correlation (PPC) alpha equal to zero (0).FIG. 6is a graph600of a normalized autocorrelation surface of the portion510of the image400ofFIG. 4. As shown in the graph600, the normalized autocorrelation surface has a PPC alpha equal to one (1). It should be noted that either an autocorrelation or cross-correlation surface may be utilized when checking for periodic patterns in an image sequence.

Normalization is performed with respect to an area in an analysis window and a maximum grey scale. Accordingly, the correlation surface resides in the range of 0 to 1. Additionally, the autocorrelation surface is symmetric and contains an odd number of peaks.

Referring again toFIG. 3, in step320, image properties are computed and inferred from the autocorrelation or cross-correlation surfaces. Table 1 below shows example properties that may be inferred and their relationship to the properties that are computed.

TABLE 1Estimates PropertiesItemNo.Estimated PropertyRelated to1Degree of periodicitynumber of peaks, peak support2Direction ofpeak eccentricity, ridge lines radiatingpreponderate similarityfrom peakof content3Size of the structuresequal to approximately ½ width ofin the analysis windowpeak support4Distance betweendistance between peaks, average distanceperiodic structuresbetween peaks.5Eccentricity ofratio of maximum and minimum raysstructures of interestradiating from peak until a valley isreached6Geometric relationshipthe geometric relationship between peaks,between periodicsubject to similarity in peak support, andstructuresrelative peak strength7TextureOne peak-very narrow - content is(is the surface is noisyessentially flat and/or is uncorrelatedor not, or essentiallynoise.featureless, or flat)If difference between peak and minimumvalue in the correlation surface (CS) issmall, the content is essentiallyfeatureless.If max(CS) − min(CS) small but max(CS)and min(CS) closer to 1, then content hashigh luminance.If max(CS) − min(CS) small but max(CS)and min(CS) close to 0, then content haslow luminance.If the traced ray between two peakscrosses a valley then the content isrelatively distinct. Further, if the valley isdeep, similar content is separated bydissimilar content.8Relative luminanceif CS surface is high (>0.5), periodicorientation of periodicelements are darker thanstructurebackground.if CS surface is low (<0.5), periodicelements are brighter thanbackground.

Some example techniques that may be used to analyze the surfaces depicted inFIGS. 5 and 6include ridge filtering, peak extraction, valley extraction, and sink extraction. Additionally, a radon transform may be performed to determine whether there is a linear trend in the data under analysis.

FIG. 7is a graphical representation700of peaks, ridges, valleys, and sinks of the portion410of the image400ofFIG. 4. Eccentricity may be estimated for each peak, its support, and the direction of preponderate similarity.

In order to identify energy along one or more of the angular projections, a radon transform may be utilized.FIG. 8is a graphical representation800of a radon transform of the portion410of the image400. The radon surface can be parsed for peaks in the same way as either of the correlation surfaces500and600. Additionally, the radon transform of either correlation surface may be used to estimate directions of preponderate similarity.FIG. 9is a graph900of a surface map of the radon transform800ofFIG. 8.

Referring again toFIG. 3, in step330, eccentricity is estimated. Peak eccentricity suggests the direction and relative strength of the similarity of the content in the image400. For example, if a peak is highly eccentric, (i.e., has a non-circular footprint and may resemble an elongated ellipse), the image content is likely more similar in the direction of a major axis and less similar in the direction of a minor axis.

Some of the ways to estimate peak eccentricity include fitting an ellipse about a peak or paraboloid, and obtaining a non-parametric estimate based on maximum and minimum chord lengths. Since the methods of fitting an ellipse about a peak or paraboloid may involve potential numerical instabilities, these methods may not be optimal methods in which to estimate peak eccentricity.

On the other hand, using the non-parametric approach infers parameters empirically from direct measurements of raw data, without assuming a mathematical model having estimated parameters. In one example, the non-parametric approach to estimating eccentricity includes computing, or analyzing, contours (step340), using a watershed algorithm or by a ridge and valley method. The rays that emanate from peaks outward to an edge are computed. The rays are swept through 180 degrees while retaining maximum and minimum ray values. The ratio of these quantities may be used to estimate eccentricity.

The watershed transform, or algorithm, is utilized to identify the mass about the peaks in the autocorrelation surface. The mass, which may include the mean support or peak footprint at various watermarks, provides information about the image content.

FIG. 10is a graphical representation1000of a watershed transform of the portion410of the image400ofFIG. 4. The graphical representation1000shows a decomposition of the watershed transform.FIG. 11is a graph1100of a surface map of the watershed transform1000ofFIG. 10. In particular, the graph1100shows a level set surface map. In order to collect the points that form the contour inFIGS. 10 and 11, a contour parsing is performed. Table 2 below shows an example “state-machine” that may be utilized to parse the boundary of an object that is determined from a watershed algorithm.

Referring now to Table 2 above, since it is possible for each of the two-by-two tables depicted in the “Pattern” column of the table to be the result of a logical expression, different types of contours may be efficiently followed. Also, it should be noted that although a two dimensional object is used as an example, this concept may be extended to an arbitrary number of dimensions.

FIG. 12is a graph1200of a level set of the autocorrelation surface of the portion410of the image400ofFIG. 4. As shown inFIG. 12, four objects, (designated1201,1202,1203, and1204), are shown. Each object corresponds to a specific level set of the autocorrelation surface and parsed perimeter, respectively. In the present example, the content is shifted by (10,10) pixels. Accordingly, the principal peak does not occur at the center of the autocorrelation surface.

One way to estimate area of an object that is enclosed by curves that do not cross over themselves is Green's Theorem, which by way of example is shown in the equation below:

Alternatively to using equation (1) above, the area may be computed by extracting the area surrounding an object and computing the number of non-zero pixels. However, this method may require foreknowledge of the shape of objects.

In addition to estimating the periodicity of the content in the image, it may be beneficial to estimate the size of the structures. One way to accomplish this estimation is by parsing the perimeter of an object level set projection. Another way is to estimate the eccentricity of the object.

One way to estimate an object's size is to determine the peak support of the object. For example, an ellipse may be fitted around the major and minor axes of rays determined from an object in order to determine the size and orientation of the structures that led to the rays. The area of the ellipse may be used as an estimate for the object's size. However, if the major or minor axes are limited by the size of the analysis window, it may be assumed that the structures in the image extend beyond the analysis window. This could be indicated by asserting a “spillover” flag.

In step350, the entropy metric is determined. The entropy metric is a local measure that is utilized to estimate the orientation and scale of structures in the image by first applying an anisotropic decomposition of the image and then computing a measure defined by the following equation:

c⁡(Ω)=1-∫Ω⁢v⁡(x,y)∫Ω⁢v⁡(x,y),Equation⁢⁢(2)
where v(x, y) is the anisotropic orientation vector adjusted to lie in the range [0, π] and Ω is the region over which the entropy is computed. In the discrete domain, the entropy measure becomes:

c⁡(i,j)=1-∑i=-⌊h/2⌋⌈h/2⌉⁢∑j=-⌊w/2⌋⌈w/2⌉⁢v⁡(i,j)∑i=-⌊h/2⌋⌈h/2⌉⁢∑j=-⌊w/2⌋⌈w/2⌉⁢v⁡(i,j),Equation⁢⁢(3)
where w and h are the block height and block width. This measure lies in the interval [0, 1]. It is also possible to define a variant of this measure that takes into account the magnitude of the anisotropic vectors. This is done so that relatively flat regions are given less importance. In flat regions, there is often no structure present, so the anisotropic vectors can become confused due to having many haphazard orientations depending on noise. It may not be desirable to consider these as important. To facilitate this variant, the entropy measure may therefore be modified in accordance with the following equation:

In one respect, the entropy matrix is an indication of the lack of uniformity of direction of the gradients in a local part of the image. If the c(i, j) is close to 1, then there are a great deal of changes in direction in the analysis window which could be indicative of very small, but defined, structures. Alternatively, if it is close to zero, there is a great deal of uniformity in direction and so there is well defined homogeneous directional structures in the analysis window. An example entropy metric is shown inFIG. 13, which is a graph1300of an entropy surface of the portion410the image400ofFIG. 4.

With the entropy measure, it becomes possible to make some determinations regarding the nature of the content within the analysis window. For example, if the correlation surface contains a large number of peaks, and the entropy measure is small, then the content is directionally structured with high periodicity. An example of this would be a zone plate below the Nyquist frequency.

If the correlation surface contains a large number of peaks, and the entropy measure is large, then the content is directionally unstructured with high periodicity. An example of this would be a highly textured surface such as a checkerboard pattern. Also, if the correlation surface contains one peak with small support, and the Entropy measure is large, then the content is probably best approximated by uncorrelated noise. An example of this would be a speckled background.

Another measure of image content that can be derived from the autocorrelation function is the noisiness, which may be determined in accordance with the following equation:

n=1-p2-p_p1-p_,Equation⁢⁢(5)
where p1, p2andpare the largest, second largest and average peak heights derived from the autocorrelation surface. This measure is in the interval [0, 1] and is applicable when there is more than one peak, both are greater than the average, and when the peak support of the largest peak is small. So the ‘noisier’ the content, the closer the noise metric is to 1. In recognition that the noisiness measure is only applicable when the peak support is small, the noisiness measure can be modified to take this into account in accordance with the following equation:
n′=n×(1−ps),  Equation (6)
where psis the peak support.

Another measurement that is useful to know is how similar images are to one another. A similarity measure is a number between 0 and 1 that is intended to capture image similarity. It is based on the PPC (alpha=1) cross correlation, and may be defined in accordance with the following equation:

s=p1×hw(h-Δ⁢⁢h)⁢(w-Δ⁢⁢w),Equation⁢⁢(7)
where p1is the amplitude of the largest peak Δh and Δw are the vertical and horizontal displacement from the origin of the largest peak, respectively.

In addition, whenever it is necessary to make a decision based on analogue, (i.e., continuous), inputs and represent the decision with a few discrete categories, there is often a need to apply interpretive rules (see step360ofFIG. 3). Whether a surface is noisy or not is a question of degree. It may be very noisy, slightly noisy, completely noise-free, or somewhere in between. To deal with this reality, rules are required that build some flexibility into the final outcome. The framework developed by “Fuzzy logic” that combines a membership function and logical operators may be utilized to construct these interpretive rules, that will combine the various inputs and come up with an overall estimate of surface structure.

In step370, a report, (e.g., data is output or data is stored in memory), is generated from the analysis performed in the previous steps. In one example, the report may be split into two parts. The first is a factual reporting of the computed statistics, and the second is the interpretive portion that uses rules to qualify the content. The statistics generated in this report may aid in determining the nature of the content of the image. This report may then be utilized to determine the structure and content of the image for display or further processing. For example, the report may contain information relating to the structure such as the periodicity, eccentricity, fractal attributes, aliased attributes, noisiness, and the like. In addition, attributes such as the flatness or featurelessness of the image may be included.

Although the features and elements of the present invention are described in the example embodiments in particular combinations, each feature or element can be used alone without the other features and elements of the example embodiments or in various combinations with or without other features and elements of the present invention. The present invention may be implemented in a computer program or firmware tangibly embodied in a computer-readable storage medium having machine readable instructions for execution by a machine, a processor, and/or any general purpose computer for use with or by any non-volatile memory device. Suitable processors include, by way of example, both general and special purpose processors.

Typically, a processor will receive instructions and data from a read only memory (ROM), a RAM, and/or a storage device having stored software or firmware. Storage devices suitable for embodying computer program instructions and data include all forms of non-volatile memory, including by way of example semiconductor memory devices, read only memories (ROMs), magnetic media such as internal hard disks and removable disks, magneto-optical media, and optical media such as CD-ROM disks and digital versatile disks (DVDs). Types of hardware components, processors, or machines which may be used by or in conjunction with the present invention include Application Specific Integrated Circuits (ASICs), Field Programmable Gate Arrays (FPGAs), microprocessors, or any integrated circuit.