System and method for hierarchical image processing

Video processing in general and image processing in particular is a very complex process. This is more so when the analysis is required to extract information from the images for providing of the same directly or indirectly to the users. This additional complexity is due to the direct competition with users who are used to analyzing of the images both syntactically and semantically. One of the ways to contain the complexity of image analysis is to exploit the domain semantics during image processing. A system and method to help in semantics based image processing involves the identification of one or more domain relevant semantic hierarchies and using of the same during image processing.

FIELD OF THE INVENTION

The present invention relates to video processing in general, and more particularly, image processing of images that are part of a video. Still more particularly, the present invention is related to a system and method for semantics based image processing that enhances the overall accuracy of image analysis.

BACKGROUND OF THE INVENTION

Video analysis of, say, a movie typically involves analyzing of a sequence of images contained in the video. The analysis is performed different points of view such as analysis for image/video compression, analysis for image/video annotation, or analysis for spam detection. As can be observed, one kind of video/image analysis is for machine processing while the other kind of video/image analysis is for providing information directly or indirectly to users. Note that video/image compression falls into the first kind while the video/image annotation is of second kind. For example, video/image annotations help in supporting semantics based end user queries on videos and relevance based ad targeting while watching the videos. For a successful annotation of an image, it is necessary to undertake the semantic analysis of the image: the image is analyzed to identify the prominent objects in the image so as provide that annotation based on these recognized objects. Note that both object recognition and identification of prominent objects are a complex and error prone processes there by leading to the not-so-very accurate image annotation. One approach to contain this complexity and enhance the accuracy of image annotation is to exploit the domain semantics during image processing.

DESCRIPTION OF RELATED ART

U.S. Pat. No. 7,426,286 to Kaneko; Toshimitsu (Yokohama, JP), Hori; Osamu (Yokohama, JP), Mita; Takeshi (Yokohama, JP), Yamamoto; Koji (Yokohama, JP) for “Method of describing object region data, apparatus for generating object region data, video processing apparatus and video processing method” (issued on Sep. 16, 2008 and assigned to Kabushiki Kaisha Toshiba (Kawasaki-shi, JP)) provides a region data describing method for describing, over a plurality of frames, region data about the region of an arbitrary object in a video, the method specifying the object region in the video with at least either of an approximate figure approximating the region or characteristic points of the region, approximating a trajectory obtained by arranging position data of the representative points or the characteristic point in a direction in which frames proceed with a predetermined function and describing the parameter of the function as region data.

U.S. Pat. No. 7,424,157 to Pace; Charles Paul (North Chittenden, Vt.) for “Apparatus and method for processing image data” (issued on Sep. 9, 2008 and assigned to Euclid Discoveries, LLC (Concord, Mass.)) provides a representation of video data that can be used to assess agreement between the data and a fitting model for a particular parameterization of the data. This allows the comparison of different parameterization techniques and the selection of the optimum one for continued video processing of the particular data.

U.S. Pat. No. 7,421,154 to Kinjo; Naoto (Kanagawa, JP) for “Image processing method” (issued on Sep. 2, 2008 and assigned to FUJIFILM Corporation (Tokyo, JP)) describes an image searching method that extracts or recognizes specific information for an image that exists in the image which can be used during image searching.

U.S. Pat. No. 7,415,153 to Mojsilovic; Aleksandra (New York, N.Y.) for “Color naming, color categorization and describing color composition of images” (issued on Aug. 19, 2008 and assigned to International Business Machines Corporation (Armonk, N.Y.)) provides methods, systems and apparatus for assigning color names to individual image pixels, and generating verbal description of color composition in images, suitable for a wide variety of information processing applications.

U.S. Pat. No. 7,234,106 to Simske; Steven J. (Fort Collins, Colo.) for “System for and method of generating image annotation information” (issued on Jun. 19, 2007) describes a system for and method of generating image annotation information comprising selecting images to be annotated, analyzing said selected images to identify associated information, generating annotation information from at least one of said selected images using said associated information, and annotating said selected images with the annotation information.

U.S. Pat. Appln. 20060173909 by Carlson; Gerard J.; (Boise, Id.); Ritzenthaler; David; (Boise, Id.) entitled “Automated image annotation” (published on Aug. 3, 2006 and assigned to Hewlett Packard Company (Fort Collins, Colo.)) describes an automatic annotation transmission device that is programmed with information related to a nearby photographic subject, and configured to transmit the information to a properly configured automatic annotation reception device. An electronic image capture device is configured to receive information from an automatic annotation transmission device, correlate the annotation information with one or more captured images and store the annotation information in a memory.

“Image annotation: which approach for realistic databases?” by Herve; Nicolas and Boujemaa; Nozha (appeared in the Proceedings of the CIVR 2007: ACM International Conference on Image and Video Retrieval, University of Amsterdam, Amsterdam, The Netherlands, Jul. 9-11 2007) describes an efficient approach to image annotation based on homogeneous global image descriptors and a pool of support vector machines.

“Natural scene classification and retrieval using Ridgelet-based Image Signatures” by Borgne; Herve Le and O'Connor; Noel (appeared in the Proceedings of the ACIVS 2005: Advanced Concepts for Intelligent Vision Systems, 7th International Conference, Antwerp, Belgium, Sep. 20-23, 2005) describes a method based on ridgelet representation by defining both global and local signatures that are specifically designed for semantic classification and content based retrieval.

“Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes” by Murphy; Kevin, Torralba; Antonio, and Freeman; William (appeared in the Proceedings of the NIPS 2003: Neural Information Processing Systems, Vancouver, Whistler, Canada, Dec. 8-13, 2003) proposes to use the scene context (image as a whole) as an extra source of (global) information to help resolve local ambiguities.

“Automatic Image Annotation and Retrieval using Cross-Media Relevance Models” by Jeon; J., Lavrenko; V., and Manmatha; R. (appeared in the Proceedings of SIGIR 2003: The 26th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval, Jul. 28-Aug. 1, 2003, Toronto, Canada) describes an automatic approach to annotating and retrieving images based on a training set of images. It is assumed that regions in an image can be described using a small vocabulary of blobs and the blobs are generated from image features using clustering.

The known systems perform syntactic and semantic analyses of the images in an isolated manner to address the issues related to the processing complexity. The present invention provides a system and method to enhance the overall image recognition accuracy by building on top of the well known proposed systems by exploiting the hierarchical domain semantics.

SUMMARY OF THE INVENTION

The primary objective of the invention is to enhance the accuracy of recognition of a set of objects possibly present in an image.

One aspect of the invention is to exploit the well known classifiers for the objects under consideration. That is, use of a best suited classifier for the recognition of an object for each of the objects.

Another aspect of the invention is to use the semantic relationships among the labels of the set of classifiers associated with the set of objects.

Yet another aspect of the invention is to form a set of hierarchies of classifiers based on the semantic relationships among the labels of the classifiers.

Another aspect of the invention is to define a plurality of factors for identifying an optimal set of hierarchies.

Yet another aspect of the invention is to use a near optimal set of hierarchies to perform hierarchical image processing of an input image.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

Image processing is a complex process especially when the processing requirements are to identify the objects present in an input image. It is an open problem to identify all the objects that are present in the input image at a level of granularity that is of significant interest to human beings. A way to contain the image processing complexity at one level is not to look for all the objects present in the input image: just look for whether the objects of interest are present in the input image or not. A lot of work has gone on to build classifiers, each one of which is specialized to recognize an object of interest, say, a building, an airport, or a beach. The second level of image processing complexity reduction is to use these classifiers by identifying a hierarchical relationship among these classifiers. The third level of complexity reduction is achieved when the image processing is performed using the identified hierarchies: this step not only leads to the reduction in computational complexity but also enhances the overall object recognition accuracy. A theoretical result based on Bayes theorem indeed supports this fact.

FIG. 1depicts an overview of a video analysis system. A content retrieval system (100) obtains a content to be annotated from the content database (110). The content is typically a multimedia video and a multi-modal analysis is performed to extract as much of information as possible with an end objective of annotating of the content. Text-oriented analysis (120) obtains the textual information that is part of the content and as much of possible information is extracted to provide one dimension to the annotation. Note that textual processing is relatively easier (although it posses its own challenges) as compared with video-oriented and audio-oriented analyses. Audio processing (130) processes both speech and non-speech sounds to obtain the information for annotation. Video-oriented analysis (140) involves analyzing of the sequence of frames that are part of the content. Such frames are extracted and a hierarchical image processing is performed (150) based on the database of domain hierarchical semantics (160). Finally, the content is annotated based on the text-oriented, video-oriented, and audio-oriented analyses at the level of granularity of interest (170), and the annotations are stored in a database (180).

FIG. 2provides an overview of Hierarchical Image Processing (HIP).Given a set of classifiers C:Each classifier Ci of C is a specialist classifier to analyze an image to recognize a particular kind of object in the image;Ci has a semantic label Li;Each Li has multiple semantic relationships with other class labels;Each Ci has a feature vector Vi that is used in the object recognition process;Summarizing, each class has a semantic characterization and a feature vector characterization;Note that the feature vector of each Ci is independent of the feature vectors of the other classes; And there is a semantic dependence among the semantic characterization of the class labels;One of the objectives of HIP is to exploit semantic dependence and feature independence;Class characterization Ci: <Li, Ri, Vi> whereinLi is the semantic label of class Ci,Ri is a set of semantic relationships involving Li and other class labels, andVi is a feature vector;C is a set of classes {C1, C2, . . . , Ci, . . . }L is a set of labels {L1, L2, . . . , Li, . . . }V is a set of feature vectors {V1, V2, Vi, . . . }R is a set of set of semantic relationships {R1, R2, Ri, . . . }Illustrative labels: Indoor, Sky, Structural, Stadium, . . . .Illustrative feature vectors: Wavelet features, Moment invariant features, Gabor features, Pogio features, . . . .Illustrative semantic relationships: Parent, Child, Sibling, Near, Far, . . . .A second objective of HIP is to determine the best possible set of hierarchies given C, L, and R;

FIG. 3depicts illustrative hierarchies.300depicts the best possible set of hierarchies wherein all the class labels are so tightly related resulting in a single chain. On the other hand,310depicts a worst case scenario: there is absolutely no relationship among the class labels. The result of using disparate classes is the there is nothing much gained to improve upon computational and recognition efficiency. Finally,320depicts a typical set of hierarchies.

In order to characterize a set of hierarchies, the following four factors are defined:(A) Sibling Factor (SF): Let. S={S1, S2, . . . , Si, . . . } be the set of sibling sets wherein Si is the Ith sibling set with Ni as the number of labels in Si, and Ns is the number of elements in S;Let N be the total number of unique labels in S;SF is based on the number of hierarchies across which siblings are distributed;Consider Sj: Determine Kj the number of hierarchies in which Sj is distributed;Note that Kj=1 indicates the all of Sj are in one hierarchies and Kj=K indicates that the labels of Sj are distributed across all of the hierarchies;Define SF as Sum(1<=J<=Ns)((Kj/K)*(Nj/N));Observe that a higher value of SF is better for a given set of hierarchies;(B) Redundancy Factor (RF): Let NI be the total number of Labels;Let Mi be the number of hierarchies in which Ith label is replicated; The typical value of Mi is 1.Define RF as NI/(Sum(1<=I<=NI)Mi);The values of RF close to 1 are better for a given set of hierarchies;

FIG. 4aprovides additional HIP factors.(C) Near-Far Factor (NFF): It is required that in a given set of hierarchies, the labels that are near must far from each other and those that are far must be near each other;Given L and R, define NF(L1, L2) as close to 1 if L1 and L2 are semantically far from each other; and the value is close to 0 if L1 and L2 are semantically near each other;Given K hierarchies, defineNFH(L1, L2) as 1 if L1 and L2 are in different hierarchies;Else NFH-L1, L2)=Alpha*(Dist(L1, L2)/MaxPathLength),wherein, Dist(L1, L2) denotes the path length between L1 and L2 in a hierarchy and MaxPathLength is the path length between two labels that are farthest from each other in the hierarchy;Alpha is a pre-defined value with a typical value of 0.8;Let P be the number of possible label pairs;Compute NFF as Sum (Over all pairs Li, Lj) (INF(Li, Lj)−NFH(Li, Lj)|)/P;The value of NFF close to 1 is better for a given set of hierarchies;(D) Conflict Factor (CF): The preferred set of hierarchies must have more number of hierarchies with each hierarchy having more depth and less breadth:Let each label have an initial weight of unity;Add unity to the weight for each level down in a hierarchy;That is, Let Di denote the depth of the Ith label in a hierarchy;If a label is duplicated, consider Di based on the minimum of the depths of the duplicated label;Let NI be the total number of labels in L;Compute CF as (2*Sum(Over all labels)Di)/(NI*(NI−1));Note that the best case is when labels form a chain; In this case, Sum (Di) is (NI*(NI−1))/2;The worst case is when the labels remain independent forming NI single node hierarchies; In this case, Sum (Di) is NI;

FIG. 4bprovides an illustrative measure of a set of hierarchies.

Given a set of K hierarchies,Compute SF, RF, NFF, and CF based on the set of hierarchies;Let W1 be the weight associated with SF;W2 be the weight associated with RF;W3 be the weight associated with NFF; andW4 be the weight associated with CF;Compute H-Measure as W1*SF+W2*RF+W3*NFF+W4*CF;

Note that H-Measure of a set of hierarchies defines the utility of the set of hierarchies in enhancing the recognition accuracy of a given set of objects in an input image. The value of H-Measure close to 1 indicates higher utility.

FIG. 5depicts an approach for hierarchy formation. The formation of hierarchies involves the identification of a near optimal set of hierarchies and one approach is based on the use of a stochastic optimization technique such as genetic algorithms.

Step 1:Form a population of P sets of hierarchies based on C, L, and R, wherein each of the P sets has up to K hierarchies and covers entire of L;Compute H-Measure for each of the P sets of hierarchies;

Step 2:Order P sets of hierarchies in the non-increasing order of their H-Measures;Get the H-Measure of the top-most hierarchy set;If there is not much of a change in the H-Measure as compared with a pre-defined number of past iterations, Go To Step 3;If number of iterations exceeds a pre-defined threshold, Go To Step 3;Select P/2 sets of hierarchies as to be part of the next population;Randomly mutate the remaining P/2 sets of hierarchies based on the genetic operators:Operator 1: Delete a sub-tree in the hierarchy;Operator 2: insert a sub-tree in the hierarchy;Operator 3: Swap a sub-tree of one hierarchy with another sub-tree of another hierarchy;Operator 4: Delete a hierarchy;Operator 5: Insert a hierarchyCompute H-Measures for each of the P/2 mutated sets of hierarchies;Add these P/2 sets of hierarchies to the original P/2 sets of hierarchies;Go To Step 2;

Step 3:Select the set of hierarchies in the top of the order as the Formed Hierarchies for Image Processing;End;

FIG. 6provides an approach for hierarchical image processing.

Hierarchical Image processing:

Given:An input Image I;A set of K Formed Hierarchies;

With respect to each hierarchy H,Traverse down from the root;

Step 1:At each node, apply the associated classifiers;For each associated classifier,Obtain the recognition accuracy;Update the node with the obtained accuracy;If the obtained accuracy exceeds a pre-defined threshold,Mark the corresponding child node for further traversal;If no more nodes remain for traversal, Go to Step 2:Go to Step 1;

With respect to each hierarchy H,Traverse down from the root;With respect to each node,If the associated accuracy exceeds a pre-defined threshold,Add the associated label to the set of Image annotations associated with H;

Obtain the set of set of image annotations associated with the various hierarchies;

Identify a maximal consistent subset and form the annotations for the input image.

Note that a maximal consistent subset of image annotations is a largest subset of annotations based on the set of set of image annotations and R, the set of set of semantic relationships.

FIG. 7depicts illustrative results of HIP.700depicts an input image and is obtained from the web source: http://gimp-savvy.com/PHOTO-ARCHIVE

The objective is to perform HIP on this input image to identify the various of the objects of interest.

710provides a table depicting the class hierarchy. Note that this class hierarchy is based on semantic relationships among the labels associated with the classes. Each node in the hierarchy has a Class ID and is bound with one or more classifiers. For example, Class ID 1 is bound with two classifiers: C-Day and C-Night. C-Day is a specialist classifier to analyze an input image to recognize whether the input image is a day time image. Similarly, the other classifiers are also specialist classifiers. In particular, note that most of the classifiers may have some sort of pre-processing, say regionalization, as part of their classification process. Further, as part of the post-processing in some of the classifiers, the context, say, as defined by the path in the hierarchy, gets used in reducing the ambiguity, and thereby enhancing the recognition accuracy. Observer this aspect in the C-SeaShore classifier.

FIG. 7adepicts additional illustrative results of HIP. In particular, the figure depicts an illustrative classifier hierarchy that is used in an experiment to demonstrate the utility of HIP. The input image is analyzed using the various classifiers associated with the various nodes in the hierarchy and a brief description is as follows:Step 1: Initially, the image is analyzed by using two classifiers: C-Day and C-Night; the recognition accuracy obtained using C-Day is 0.997 (730) leading to the traversal of the hierarchy through node2.Step 2: Two more classifiers are used in the analysis: C-Indoor and C-Outdoor; the recognition accuracy obtained with C-Outdoor is 0.997 leading to the traversal through node3.Step 3: Further analysis is performed using the two classifiers: C-NaturalEnvironment and C-ManmadeEnvironment; the recognition accuracy obtained with C-NaturalEnvironment is 0.997 (740).Step 4: Analysis is performed at node4using the three classifiers, C-NaturalBlue, C-NaturalGreen, and C-OtherColors; The recognition accuracy obtained with C-NaturalBlue is 1.0 based on the fact that the obtained percentage measure is much greater than a pre-defined threshold (750); Similarly, the recognition accuracy obtained with C-OtherColors is 1.0.Step 5: Analysis is performed at node5using the two classifiers, C-WaterBodies and C-Sky leading to the identification of “Sea Shore” (760) and “Normal Sky;”Step 6: Similarly, the analysis at node7leads to the identification of “Sand” (770).

FIG. 7bdepicts further additional illustrative results of HIP. The image gets annotated based on the recognition accuracy obtained by the various classifiers that are part of the classifier hierarchy.790depicts the annotations of the input image. Note that some of the class labels may not get directly used in the annotation process.

Thus, a system and method for hierarchical image processing is disclosed. Although the present invention has been described particularly with reference to the figures, it will be apparent to one of the ordinary skill in the art that the present invention may appear in any number of systems that need to exploit the hierarchical semantics in order to improve the performance. It is further contemplated that many changes and modifications may be made by one of ordinary skill in the art without departing from the spirit and scope of the present invention.