Euler vector for color images

[00002] This patent application is a U.S. Continuation-In-Part patent application of U.S. patent application Ser. No. 09/722,979, filed on Nov. 27, 2000, titled “Computing the Euler Number of a Binary Number,” by Acharya et al., and U.S. patent application Ser. No. 09/722,982, filed on Nov. 27, 2000, titled “Developing A Euler Vector for Images,” filed on Nov. 27, 2000, by Acharya et al., both assigned to the assignee of the current invention and herein incorporated by reference.

[00003] This patent application is related to Euler numbers and vectors and, more particularly, Euler numbers and vectors for images, such as color images.

[00004] Numeric characterization of images for relatively efficient management of an image database is a challenging problem in image processing. Further, it is desirable that the characteristic parameters of the image remain relatively invariant in the presence of various perturbations and/or transformations. Determination of a compact set of parameters for images which is, for example, relatively easy to compute, suitable for database search, and/or is robust against transformations, is, therefore, desirable in the emerging domain of internet technology, for example, to search images on-line.

[00011] In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of the claimed subject matter. However, it will be understood by those skilled in the art that the claimed subject matter may be practiced without these specific details. In other instances, well-known methods, procedures, components and circuits have not been described in detail in order so as not to obscure the claimed subject matter.

[00012] Although the claimed subject matter is not limited in scope in this respect, aforementioned patent application U.S. patent application Ser. No. 09/722,979, titled “Developing an Euler vector for images”, by Acharya et al., filed on Nov. 27, 2000 (attorney docket P10405), describes one or more methodologies to generate a characterization parameter for gray-tone images. Likewise, a characterization parameter for color imagery in order to index and search color images in an image database would also be desirable. Moreover, it would be desirable if such a parameter were relatively invariant to lighting condition, contrast sensitivity and/or color balance for a typical electronically generated digital image. This would make such an approach suitable for indexing and/or searching of color images from a color image database/depository, for example.

[00013] Here, let the binary image be represented by a 0-1 pixel matrix of size (N×M), in which an object or background pixel is denoted as 1 or 0, respectively. For a binary image, a Euler number is a well known geometric feature which is defined as the difference between the number of “connected components” (objects) and the number of “holes”. In FIG. 1, an example is shown of a binary logo image with 12 connected components (black regions, or foreground) and 3 holes (white regions or background). Hence, the Euler Number of the “VLSI Design” logo (as shown in FIG. 1) is 12−3=9.

[00014] In a binary image, a “connected component” refers to a set of object pixels such that any object pixel in the set is in the 8 (or 4) neighborhood of at least one object pixel of the same set, as shown in FIG. A 4 neighborhood of a pixel at location (x, y) in a Cartesian coordinate system refers to the set of pixels at locations {(x−1, y), (x+1, y), (x, y−1), (x, y+1)}. Similarly, an 8 neighborhood of a pixel at location (x, y) refers to the set of pixels at locations {(x−1, y−1), (x−1, y), (x−1, y+1), (x, y−1), (x, y+1), (x+1, y−1), (x+1, y), (x+1 y+1)}.

[00015] On the other hand, a “hole” is a set of background pixels such that any background pixel in the set is in the 4 (or 8) neighborhood of at least one background pixel of the same set and this entire set of background pixels is enclosed by a connected component. A computationally efficient process for generation of a Euler Number of a binary image is described in U.S. patent application Ser. No. 09/722,982, titled “Computing the Euler number of a binary image”, by Acharya et al., filed on Nov. 27, 2000, assigned to the assignee of the present invention. Of course, the claimed subject matter is not limited in scope to the approach described in the foregoing patent application.

[00016] The concept of a Euler vector, as described, for example, in the aforementioned patent applications, may be extended. Therefore, in this particular embodiment, a Euler number may be generated from the gray code representation of the 4 most significant bit planes of the image as described hereinafter, although the claimed subject matter is not limited in scope in this respect. A bit plane comprises 0s and 1s, and hence may form a binary (two-tone) image and its gray code representation may do so as well. A Euler number of the partial image formed by the gray codes of the 4 most significant bit planes may thus be computed to produce 4 Euler numbers. This may generate a 4-tuple of integers which is defined in this context to be the Euler vector of the original gray-tone image.

[00017] A gray-tone image may be represented as an (N×M) matrix, one element of which is an integer in the range [0, 255] (inclusive of 0 and 255), denoting the intensity of the corresponding pixel. Thus, an intensity value of a pixel may be represented by an 8-bit binary vector (b₇, b₆, b₅, b₄, b₃, b₂, b₁, b₀). An image therefore may comprise 8 bit planes, as shown in FIG. 3. FIG. 2 represents a single bit plane.

[00018] To define a Euler vector, the first 4 most significant bit planes (corresponding to (b₇, b₆, b₅, b₄)) are retained. These 4-bit binary vectors are converted to a corresponding reflected gray code (g₇, g₆, g₅, g₄), which, in this particular embodiment may comprise:
g₇=b₇; g₆=b₇/b₆; g₅=b₆/b₅; g₄=b₅/b₄,
where denotes an XOR (modulo-2) operation. It is well known that for any binary vector, the corresponding reflected gray code is unique and vice-versa.

[00021] In this particular context, the Euler vector of a gray-tone image comprises a 4-tuple E={E₇, E₆, E₅, E₄}, where E_i is the Euler number of the partial two-tone image formed by the i-th bit-plane, 7≦i≦4, corresponding to a reflected gray code representation of intensity values. Example: For the image shown in FIG. 5, the Euler vector is E={79, −13, −391, −1624}.

[00022] Gray code representation of intensity values offers a potential advantage over standard binary representation in this particular context. A Euler vector may be relatively insensitive to noise and other changes, if a gray code is used. In many instances, for example, a small change in intensity values in an image will not affect all 4 bit planes in a gray representation.

[00023] As is well known, a color pixel, in a display quality color image, has three primary color components—Red (R), Green (G), and Blue (B). Hence, a color image may be considered as composition of three color planes R, G, B and a color component, such as these, may be considered or treated as a gray-tone image. A technique, therefore, to represent a color image is to define three 4-tuples E_R, E_G, E_B corresponding to the three color planes. This would involve a computation of 12 Euler numbers (4 for each of E_R, E_G, E_B). This may be computationally undesirable as it may involve an excessive computational burden. Moreover, the color balance of the query image and the image stored in the database may not be identical. More to the point, generating the Euler vectors by this approach may produce divergent values for (E_R, E_G, E_B) for images with substantially identical content at different lighting conditions and possibly a different color appearance. This may therefore undesirably affect search results with a query image from an image database.

[00024] Alternatively, the color image may be converted into a Luminance-Chrominance space, such as Y-Cb-Cr space, for example. Then, applying dynamic stretching to rescale the luminance (Y) space over the dynamic range to 0-255 values, for example, may allow the more significant information to reside in the most significant 4 bit planes. For example, an image may appear dark if captured under poor lighting condition. Assume that all the pixel values in this image belong to the range [0-30] as an example. If the image is represented by 8 bit pixels, most significant 3 bits of the pixels will likely be 0s and changes will be observed in the least 5 significant bits. As a result, the Euler vector generated from the 4 most significant bit planes will become impractical. On the other hand, dynamic stretching may be applied, such as by using a linear scale, so that the pixel values are stretched to [0-255]. Hence the most significant 4 bit information will likely contain meaningful information. One simple technique to linearly scale is transforming every pixel x by the formula x′=255*(x-min)/(max-min), where ‘max’ and ‘min’ are the maximum and minimum values of the pixels in the image, although, of course, the claimed subject matter is not limited in scope in this respect. However, if this particular scaling technique is applied, the pixel with a maximum value will be transformed to 255 and the pixel with minimum value will be transformed to 0 and other pixels will be scaled proportionately. Hence the four most significant bit plane will have potentially meaningful values, irrespective of any lighting condition. A Euler vector using these 4 bit planes to represent the color image may then be stored as the index of the image in the database.

[00025] Below is an embodiment of a process for producing a Euler vector for a color image, although the claimed subject matter is not limited to this particular embodiment. In this embodiment, the input data or signal information capable of being represented in electronic form, for example, comprises a color image, I_C. Likewise, the output data produced or signal information capable of being represented in electronic form, for example, comprises a Euler vector. The color space of the input image I_C is converted to Luminance-Chrominance (Y-Cb-Cr) space. The color space conversion from R-G-B pixels at pixel location (m,n) to Y-Cr-Cb is typically done using the following transformation, although, again, the claimed subject matter is not limited in scope in this respect. Other potential color transformations may be applied and remain within the scope of the claimed subject matter. Here, R(m,n), G(m,n) and B(m,n) represent the values of Red, Green and Blue color components of a full color pixel at location (m,n) whereas Y(m,n) represents the corresponding luminance component and Cr(m,n) and Cb(m,n) represent the two corresponding chrominance components at location (m,n).
Y(m,n)=0.299*R(m,n)+0.587*G(m,n)+0.114*B(m,n)
Cr(m,n)=−0.169*R(m,n)−0.331*G(m,n)+0.500*B(m,n)
Cb(m,n)=0.500*R(m,n)−0.419*G(m,n)−0.081*B(m,n)

[00029] “The Luminance (Y) plane of the color converted image may be extracted by forming the pixel matrix using the Y values for the (m,n) locations. In order to remove or reduce noise present in the image, some noise filtering may be applied before adjusting the dynamic range of the Y plane. Typically, median filtering followed by mean filtering is applied to reduce most of the common types of noise components present, although, again, the claimed subject matter is not limited in scope in this respect. Noise filtering is not restricted to these two filtering techniques. Any low-pass filter type noise filtering technique may be applied and provide adequate results. The dynamic range of the Y plane may then be linearly rescaled to [0-255] to yield output data or signal information Y′. The first 4 most significant binary bit planes of Y′ may then be employed to generate a Euler Vector for the color image. The 4-bit vectors may then be converted to corresponding reflected gray codes. The Euler numbers B₇, E₆, E₅, E₄ for the 7, 6, 5 and 4^th bit plane respectively, may be computed. The Euler Vector E_y={E₇, E₆, E₅, E₄} may then be produced.”

[00030] It will, of course, be understood that, although particular embodiments have just been described, the claimed subject matter is not limited in scope to a particular embodiment or implementation. For example, one embodiment may be in hardware, such as implemented to operate on an integrated circuit chip, for example, whereas another embodiment may be in software. Likewise, an embodiment may be in firmware, or any combination of hardware, software, or firmware, for example. Likewise, although the claimed subject matter is not limited in scope in this respect, one embodiment may comprise an article, such as a storage medium. Such a storage medium, such as, for example, a CD-ROM, or a disk, may have stored thereon instructions, which when executed by a system, such as a computer system or platform, or an imaging or video system, for example, may result in an embodiment of a method in accordance with the claimed subject matter being executed, such as an embodiment of a method of producing a Euler vector for a color image, for example, as previously described. For example, an image or video processing platform or another processing system may include a video or image processing unit, a video or image input/output device and/or memory.

[00031] While certain features of the claimed subject matter have been illustrated and described herein, many modifications, substitutions, changes and equivalents will now occur to those skilled in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the claimed subject matter.