JP2011221603A - Multimedia recognition/retrieval system using dominant feature - Google Patents

Abstract

PROBLEM TO BE SOLVED: To provide means for "translation invariance, shortening of computation time, compression of information quantity, and security of flexibility" using dominant features because an important subject for constructing a multimedia recognition/retrieval system with soft brains rich in flexibility is diversity of multimedia information and enormousness of information quantity and the subject should be overcome.SOLUTION: The multimedia recognition/retrieval system comprises means for expressing a content by using a dominant feature and finding out similarity of the content and means for finding out the similarity of the content by using a feature vector obtained from a cooccurrence matrix.

Description

  The present invention relates to various multimedia recognition / retrieval systems including images.

  Many search engines such as Google and Yahoo! search related web pages after a user issues a search request (query) using a keyword, and present it to the user based on their ranking criteria. In general, the link structure is often used as a ranking standard, but at present, user satisfaction can be improved by presenting it in consideration of other criteria such as web page reliability, popularity, importance, and seasonality. Attempts have been made and will be used practically. On the Internet, so-called multimedia information such as images, videos, and music is being searched and used. However, character-based keywords are still used as search keywords. In order to realize a user-friendly interface, a content-based search technology has been proposed and developed, but has not yet reached the point of widespread practical use.

There are methods such as using learning to automatically determine the dominant color, and sometimes it can be easily obtained from the histogram, but the problem is how to use the determined dominant color and how to recognize it efficiently -Whether to implement a search system or how to generalize it as a general concept and apply it to content. In addition to the search field, other typical applications include ITS (Intelligent Transport System) fields such as pedestrian detection under bad lighting conditions and climatic conditions from the viewpoint of driver assistance, and applications in monitoring and monitoring systems. Can be considered.

A histogram-based applied for object-based query-by-shape-and-colorin image and video database Image and Vision Computing, Nov. 2005, Vol. 13, p. 23. A Novel Regions-of-Interest Based Image Retrieval Usable Multiple Features, 12th Intl.Multimedia Modeling Conf.Beijing, China, Jan 2006, pp. 377-380. Dominant Color Region Based Indexing Technique for CBIR, In Proc of the Intl. Conf. On Image Analysis and Processing (ICIAP'99). Venice, Italy.

  One of the problems in building a multimedia recognition / retrieval system is the diversity of multimedia and the huge amount of information. There are major issues in the content representation method, information amount compression, reduction of calculation time due to conversion invariance, ensuring flexibility, and the like. The point is to search for “similar” things instead of “same” things, and similarity is an important concept. The realization of such a flexible recognition / retrieval system will become increasingly important in the future. The problem lies in how to use dominant features in multimedia recognition and search, and how to efficiently realize a recognition and search system. Technology is also under development.

On the other hand, the response to multimedia contents that will increase in demand in the future is also insufficient. In order to recognize and search for a robust and flexible object, labeling is often performed as preprocessing. However, if a label is uniquely determined at that time, errors increase under bad conditions, and robustness is lost. In addition, flexible matching, which is indispensable for classifying and identifying non-uniform objects such as human postures and movements, is difficult to realize in terms of calculation time and accuracy with conventional methods. In addition to the search field, the development of robust detection methods in the ITS (Intelligent Transport System) field such as pedestrian detection under bad lighting conditions and climatic conditions and monitoring / monitoring systems is required from the viewpoint of driver assistance. Yes.

Extraction means for extracting dominant features from content, expression means for expressing content using the dominant features extracted by the extraction means and the relationship between the features, and input for inputting input content to be processed Means, a recognizing means for recognizing the input content by using the expression means, and a search means for searching the multimedia database for content similar to the input content.

The representation means obtains the relationship in the original space corresponding to the dominant feature extracted by the extraction means or the space where the dominant feature is separately arranged (hereinafter referred to as the dominant feature area) and its relationship, An expression means for providing a parameter that is a basis for obtaining a similarity between contents is provided.

The expression means includes expression means for obtaining a parameter reflecting the existence of the dominant feature region and providing a parameter as a basis for obtaining a similarity between contents using the parameter.

The representation means vote to the ballot box at a predetermined relative position from the position in the original space corresponding to each dominant feature extracted by the extraction means, and the dominant necessary to construct the object Recognizing means for recognizing that there is an object at the position of the ballot box if there is a ballot box that collects votes from the features.

In the above dominant feature region, assign a discrete state to the dominant feature, find a co-occurrence matrix, convert it to a probability matrix, find an initial probability vector and a stationary probability vector, and obtain from these two Recognizing means for recognizing input content by obtaining similarity or distance between contents using feature vectors is provided. The similarity obtained here can also be used for searching.

A feature characterized by using dominant features, and means for expressing content by assigning discrete states to the dominant features, and the relationship between the region features and regions on the content corresponding to the dominant feature region (for example, the center of gravity And means for obtaining the similarity of the content using the relative relationship of

Regardless of the number of dimensions of the input data, a one-dimensional feature vector F with a reduced order is finally obtained, and the calculation time is overwhelming compared to block matching because the order can be reduced because it can be recognized and searched using F. Faster, can be executed with less memory capacity, have various conversion invariance, provide tolerance, and increase flexibility.
Here, block matching is a method in which a region having a certain size is used as a template block, the entire image is searched, and a point that minimizes the value of the difference evaluation function from the block of interest is used as a corresponding point. If there is no block below the predetermined threshold, it is determined that there is no corresponding block.

Configuration diagram and processing flow diagram of entire system including processing means in this embodiment Explanatory drawing of the means for expressing content (image) using dominant features in this embodiment The figure which illustrated how to choose some dominant characteristics and dominant characteristics in this embodiment The figure which illustrated how to choose one-dimensional dominant feature and dominant feature in this embodiment Example when selecting dominant features from lateral HOG for pedestrian detection in this embodiment Explanatory drawing of the object recognition technique by the voting method which gave pedestrian detection in this embodiment as an example Diagram showing co-occurrence matrix obtained from dominant feature region The figure which showed the process sequence which calculates | requires a dominant feature vector from the dominant feature area | region in this embodiment. The figure which illustrated the procedure which calculates | requires a feature vector from two dominant feature area | regions in this embodiment An example of how to obtain the length of the boundary line in this embodiment The figure which illustrated the image database search result using the dominant feature (color) in this embodiment

  Hereinafter, embodiments of the present invention will be described based on the drawings and mathematical expressions. FIG. 1A is a configuration diagram of the entire system including processing means in the present embodiment. This system includes an input unit 101 for inputting content to be processed, a multimedia database 102 for search, and a processing unit 103 for recognizing and searching for input content.

The processing means 103 includes processing means for analyzing the content (image, sound, signal, etc.) acquired from the input means 101, extracting features, recognizing and searching. Specifically, these means include, for example, CPU (Central Processing Unit), RAM (Random Access Memory), ROM (Read Only Memory), keyboard (operation unit), display (display unit), HDD (Hard Disk Drive, The function as each means is fulfilled when the CPU executes a program stored in a ROM, HDD, or the like. Here, the content means multimedia content.

Before describing each means, the flow of the entire system in the multimedia recognition / search system using the dominant feature of this embodiment will be briefly described first. FIG. 1B is a processing flow diagram of the entire system in the present embodiment. As shown in the figure, before starting the processing, content is input from the input means 200A (S201A), converted into a feature space (S202A), the content is analyzed, and dominant features are extracted (S203A).

Further, a corresponding area in the original space or a space where another dominant feature is arranged is constructed (S204A), and the relationship between the extracted dominant features is obtained (S205A). The contents and attributes of the content are expressed together (S206A). Similar processing is performed on the contents of the multimedia database (200B, S201B to S204B). Further, in order to compare the results of S206A and S206B obtained in the above process, the similarity is calculated (S207). If the similarity is higher than a predetermined threshold, it is judged as “similar” and the search result is adopted. (S208) If it is low, it is determined that it is not similar, and the search result is rejected (S209). Although a series of processing is completed by these procedures (S210), the above processing is repeated during the multimedia recognition / search time.

Input devices used as input means are “0 dimension: GPS for position measurement, temperature, humidity”, “1 dimension: accelerometer (3 axes), angular accelerometer (3 axes), inclinometer (3 directions, angular accelerometer , Microphone (sound) ”,“ 2D: normal visible light camera, near infrared camera, far infrared camera, thermography ”,“ 3D: 3D data (range sensor, 3D position sensor, 3D Motion sensor, three-dimensional distance measuring sensor), etc. Here, the description will be made mainly using images for intuitive understanding, but the present invention can be similarly applied even when other media (such as three-dimensional data) are used.

As a multimedia database to be searched, the Internet can also be considered as a huge database, and can be a search target of this system, so that it can be applied regardless of access means.

2 to 9 are explanatory diagrams of recognition and retrieval means in addition to the dominant feature extraction means and expression means in one embodiment. FIG. 2 exemplarily shows a dominant feature extraction method and a result of image representation by a dominant feature region. In this example, on the basis of the total number, luminance values 1 and 2 are selected as dominant features, and pixels having luminance values 1 and 2 on the original image are set as dominant feature regions. Since the number of items other than 1 and 2 is small, it is determined that they are not dominant features. A certain threshold value is determined depending on how much detail is desired to be detected and how much calculation time is allowed.

In this example, the region origin (OC: Operating Center: hereinafter abbreviated as OC) is not used. In other words, the pixel position corresponds to the region origin, and the co-occurrence matrix can be calculated directly with this representation. . Here, the area origin means a point that represents the area. For example, in the case of a circle, it can be set at the center, but it is not limited to the center but is set to one point on the circumference or any other arbitrary point. be able to. Further, these two centroids can be considered as parameters reflecting the position of the dominant feature region. Alternatively, the position of each pixel having the value 1 or 2 can be considered as a parameter reflecting the position where the dominant feature region exists. In the same figure, the centroids of the two regions DFR1 and DFR2 can be obtained, using them as the region origin, and the vector connecting them as the relevance of the dominant feature region.

In addition, the dominant feature among the features that represent the content is called the dominant feature (DF: Dominant Feature) in the meaning of the feature that represents the content, and is generally a feature that is superior in terms of number and numerical value. Point to. For example, if the red region is large on the original image, red can be selected as the dominant feature. Dominant Feature Region (DFR) is a region in the original space corresponding to the dominant feature or a space where a separate dominant feature is placed, and is used to calculate the similarity between contents. It is done. For example, taking an area on the original content corresponding to the dominant feature as an example, if red is the dominant feature, it indicates a red portion on the original image. Next, an example in which the region origin is explicitly used will be shown. Thus, if a plurality of colors occupy most of a certain image, these colors are called dominant colors, and pixels having these colors can be treated as dominant feature regions. Texture, shape, edge direction / inclination intensity, distance image, and the like can also be used as features. Here, since content means content such as images, audio, and three-dimensional data, there are various dominant features. A statistical collection of local dominant features can be called a dominant feature again.

FIG. 3 is an example of how dominant features are selected and dominant features in the present embodiment. As shown in this example, there are several ways to select the dominant feature, so the selection is made according to the target content. Choose so that discrimination ability and generalization ability become high. Here, the white part is excluded from the object as a background. In Fig. 3 (a), first, the triangle and ellipse, which are dominant features, are detected from the original image, and three OCs of the triangle and one OC of the ellipse are detected, and recognition is performed using their positional relationship. Do. The dominant feature can be detected by performing a morphological operation using the triangle and the ellipse as a structuring element (SE).

Here, the morphological operation is a basic process used for various image processing such as image feature extraction and noise removal. The basic morphological operators are Dilation and Erosion. Used for isolated point removal, expansion, contraction, opening, closing, exclusive expansion, contraction, thinning, hole filling, skeleton, contour, reconstruction, circular separation, etc. At that time, a structuring element (SE: Structuring Element) indicating the range in which the operation is performed is necessary, but the structuring element may be a circular disk or any other figure. . However, invariance can be ensured, such as rotation invariance with a circular disk and rotation with 90 ° invariance with a square. When using a structuring element, it is necessary to specify the origin. Here, the area origin (OC: Operating
Center). Setting a set of images and structuring elements need not be restricted to a two-dimensional plane. The difference between the expansion and erosion calculation results represents the contrast intensity. Here, a morphological operation is given as an example, but other operations reflecting the existing position can also be used. For example, a maximum value (representing that it exists in the region) and a minimum value (representing not existing in the region) can be used in combination. Optical flow refers to the apparent movement of the brightness pattern of an image.

In the example of FIG. 3B, the texture is selected as the dominant feature, and the small area in the upper right is removed as noise, but it may be left if it is important. Which one to select can be determined according to the application.

In the example of Fig. 3 (c), when the corresponding part on the original image is obtained from two dominant features (black and gray), each connected region is small, but many regions with the same dominant feature are close to each other. There are a lot. Therefore, a common OC is set to easily detect the two dominant feature regions. In this example, the disk SE and the ring SE can be used for simple detection by morphological calculation, and the rotation is invariant. As seen in this example, the dominant feature regions may overlap.

FIG. 4 is a one-dimensional example. The dominant feature region can be easily detected by morphological operation (expansion-degeneration). There are two ways to handle noise in this case, leaving the small area or removing it. In this example, each dominant feature is expressed using two upper and lower thresholds. It is also possible to divide by size using dispersion within the area.

FIG. 5 is an example in which the dominant feature is selected from the lateral HOG for pedestrian detection in the present embodiment. In this figure, the magnitude of the horizontal vector of the histogram obtained from the horizontal HOG is represented by the size of the arrow. However, using the histogram as a dominant feature as it is is inefficient, so the histogram is discrete. It may be converted into a label and used. At that time, the average value, the maximum value, the median value, and the like are used to further discretize those values by classifying them into a plurality of bins (dividing them into classes). Given the labels at each position, a co-occurrence matrix can be calculated and the process can proceed to the next step. In the omnidirectional HOG, a direction vector having the maximum value may be used as a dominant feature. Here, HOG (Histgrams of Oriented Gradients) is a gradient-based feature quantity for object recognition.

FIG. 6 is an explanatory diagram of a voting method taking as an example a case where pedestrian detection is performed in the present embodiment, and shows a state where each feature is voted to a central point. In this figure, the arrows indicate the predetermined relative positions from the positions in the original space corresponding to the dominant features. As a result of voting, the voting from the dominant features necessary for composing the object is performed. If there is a collected ballot box, it is determined that there is an object at the position of the ballot box. For example, if features corresponding to the head, torso, and legs are gathered, it is determined that a pedestrian has been detected. If it is limited to the characteristics of the head and torso, or limited to the torso and leg, detection can be performed separately for the upper body and the lower body. Voting from one feature is not limited to one place, and it may be spread over a certain range and voted in a plurality of ballot boxes.

FIGS. 7 and 8 are examples of processing procedures for obtaining a co-occurrence matrix from dominant features and further obtaining dominant feature vectors in one embodiment. Represents an object by assigning discrete states to dominant features (color, HOG features, edge direction / tilt intensity, distance image, etc.), and the similarity between the dominant feature vectors obtained from the co-occurrence matrix of the features ( Or distance) is used as the similarity (or distance) between contents. Here, images are used for intuitive understanding, but if dominant characteristics are obtained, the input does not necessarily have to be an image. One-dimensional signals and three-dimensional data from music, acceleration sensors, etc. It can also be applied to content such as In addition to pixel values, this is an integrated method for uniformly handling block information such as gradient values of optical blocks and optical flows, as represented by HOG, and is used in flexible recognition and search systems. The aims. Labels assigned to discrete states may be uniquely determined, but a set of labels assigned probabilities or weights may be set as one state of the dominant feature region, or for each label. A plurality of co-occurrence matrices may be obtained separately.

A discrete state is assigned to a dominant feature, and a co-occurrence matrix is obtained from a set of dominant features at a certain distance r and a certain angle θ. In the simplest case, two sets of co-occurrence matrices are often used, but three or more sets may be used. There are several types of co-occurrence matrices. In FIG. 2, if bi-directional selection is performed (for example, θ = 0 °, 180 °), the co-occurrence matrix becomes a symmetric matrix, and invariance is maintained with respect to enlargement / reduction, up / down / left / right inversion, and the like. This property is very important for the construction of a recognition system. These invariances are kept strictly on continuous space, but are affected by sampling errors on discrete space. Nevertheless, it is approximately established when the number of regions is sufficiently large. In addition, if r is large, the directionality becomes remarkable.

In general, a two-dimensional density histogram in image processing means a statistic of pixel values of two points that are relatively in the same positional relationship (separated by a distance (r) in a certain direction (θ)). Pixel value histogram), which here extends to the dominant feature region rather than the pixel value. Not only the statistics between the two regions but also more (generally n sets (n ≧ 2)) can be used. For example, when using a set of three like the following equation 1, the frequency can be calculated using r ₂ , θ _2, r ₃ , and θ ₃ as parameters and converted into a probability. Here, various representation formats such as scalars, vectors, and matrices can be used as region features.

FIG. 9 is a specific example for explaining a procedure for obtaining a dominant feature vector in one embodiment. Obtain a co-occurrence matrix from a dominant region to which discrete states are assigned, convert it to a probability matrix, obtain an initial probability vector and a stationary probability vector, and obtain a similarity between feature vectors obtained from these two (or Distance). Figure X ₁ and Figure X ₂ are similar and not like that of FIG. X _3. Here, D ₁ and D ₂ in the uppermost stage mean dominant region features obtained from the original image. A blank is a portion having no dominant region feature. The second row is a co-occurrence matrix obtained from the frequency of two sets (0 °, 180 °), and the third row is a probability converted for each row. The fourth line is a dominant feature vectors corresponding to FIG X ₁ to X ₃ obtained from the third line. Next, a description will be given step by step.
The following expression represents the frequency of the label D _i of each dominant feature and the frequency of the region having no dominant feature by c _i (i = 1,..., R) and c ₀ , respectively.

Further, the following equation is converted into probabilities (two types).

Next, a co-occurrence matrix is obtained.
c _ij denotes the number of degrees D _j is present from the position of D _i to the distance r, angle θ away position. Since c _ii matches the number of grid points included in the region having the label D _i excluding both ends, c _ii substantially matches the size of the region. Further, c _ij (i ≠ j) at θ = 0 °, 90 °, 180 °, and 270 ° represents the length of the boundary line, and therefore is approximately rotation invariant. Because of this property, c _ii can be the size of the region containing D _i , and c _ij can be the length of the boundary line of the region, but in that case, the co-occurrence matrix excludes sampling errors. Rotation invariant. At the same time, due to the original nature of the feature vector, the feature vector becomes invariant to enlargement / reduction and up / down / left / right inversion, thereby increasing the flexibility of search capability. Although it is difficult to strictly determine the length of the boundary line on the discrete space, a simple method as shown in FIG. 10 may be used for the diagonal line.

Next, the co-occurrence matrix obtained above is converted into a probability matrix.

Once the probability matrix P is obtained, the number of dimensions can be reduced through the following processing to increase flexibility.

The feature vector F is defined as follows using d and s in the above equation.

Further, F is used as a feature of the content (image), the distance (or similarity) between F is defined, and the content (image) is more similar as the value is smaller (closer to 1). s can be chosen to have rotation, left / right upside down, scaling invariant properties, and F can be chosen to have rotation, left / right upside down, scaling invariant properties, so it is robust against deformation, so it is a robust pattern recognition system. Can be realized. Here, the distances ED and CD and the similarity CC between the two feature vectors F ₁ and F ₂ are defined by the following equation (9). The smaller the ED and the CD and the closer the CC is to 1 (the larger), the more similar content (image) is judged. The results are not always the same, but they tend to be very similar.

The result calculated along the above equation (9) is shown in the following equation (10). From this result, it can be seen that F ₁ and F ₂ are similar and not similar to F ₃ regardless of which index is used.
In addition to the above feature vector F, a relative positional relationship between the centroids of the dominant feature regions, or a shape feature such as a moment may be used as a measure of similarity. At that time, each measure may be weighted.

FIG. 11 shows a search result of an image database using a dominant color as a dominant feature in one embodiment. FIG. 4A shows the result of determining the dominant color from the histogram as the dominant feature region, extracting pixels having the dominant color, and extracting the corresponding dominant feature region (DCR). Since color is used here, it is expressed as DCR (Dominant Color Region) instead of DFR (Dominant Feature Region). FIG. 5B shows the result retrieved from the image database. For the query (processing request (inquiry) to the database management system), a photograph taken with a mobile phone is used.

If the shape of the feature vector is the same, F is the same, and it does not depend on the ID number of the dominant feature, so the same result can be obtained even if the ID number is replaced. That is, since it does not depend on labeling, it has a high ability to search for objects having the same shape and different colors, or searching for similar images. For example, the same result is obtained even if D ₁ and D ₂ (dark and light colors) in FIG. 9 and DCR ₁ and DCR ₂ (yellow and red) in FIG. 11 are interchanged. On the other hand, since each color as the dominant feature is known, it is possible to identify the replaced color, and it is sufficient to use it appropriately according to the occasional request. Moreover, since it calculates | requires from a probability, it can set so that the same result may be obtained from what expanded the figure and rotated. Also, it is resistant to deformation and works robustly even if there are some missing parts, so it is effective for recognizing objects and searching for similar ones.

The object may be anything such as color, shape, density gradient, optical flow, etc., but it must be dominant. In general, it is not a problem because some dominant feature exists.

101 input means 102 multimedia database 103 processing means 200A input means 200B multimedia database

Claims (5)

An extraction means for extracting dominant dominant features from the multimedia content;
Expression means for expressing multimedia content using the dominant feature extracted by the extraction means and the relationship between the features;
Input means for inputting multimedia content to be processed (hereinafter referred to as input content);
Recognizing means for recognizing the input content by obtaining the similarity between the multimedia contents using the expression means;
Search means for searching multimedia content similar to input content from a multimedia database;
Multimedia recognition and retrieval system using dominant features. The representation means obtains the relationship in the original space corresponding to the dominant feature extracted by the extraction means or the space where the dominant feature is separately arranged (hereinafter referred to as the dominant feature area) and its relationship, The multimedia recognition / retrieval system using dominant features according to claim 1, wherein a parameter as a basis for obtaining a similarity between multimedia contents is provided. 3. The expression unit according to claim 1 or 2, wherein the expression means obtains a parameter reflecting the existence of the dominant feature region and provides a parameter as a basis for obtaining a similarity between multimedia contents using the parameter. A multimedia recognition and retrieval system using dominant features. The recognizing means is required for voting to a ballot box at a predetermined relative position from the position in the original space corresponding to each dominant feature extracted by the extracting means, and to construct the object. The multimedia recognition / retrieval system using dominant features according to claim 1 or 2, wherein if there is a ballot box in which votes from features are collected, an object is located at the position of the ballot box. The recognition means assigns a discrete state to the dominant feature in the dominant feature region, obtains a co-occurrence matrix, converts it into a probability matrix, obtains an initial probability vector and a stationary probability vector, The multimedia recognition / retrieval system using dominant features according to claim 1 or 2, wherein the input content is recognized by obtaining the similarity or distance between the contents using the feature vector obtained from the two.