US 6,459,809 B1Grant
Searching and filtering content streams using contour transformations
Issue Date:2002-10-01
•16 Claims
•5 Drawing Sheets
Abstract
Methods and systems are provided for locating objects within a content stream, by transforming prospective objects and evaluating the results to identify meaningful semantic values. Transformation is accomplished using various contour transformations, possibly in combination with other tools and techniques. The semantic values produced by contour transformation can be efficiently searched and classified against a dictionary of archetypes to identify objects and object features in the content stream. Contour transformations may be scale-invariant and/or rotationally invariant or otherwise symmetric, so that distinctions between content objects based on their scale or orientation are avoided.
Metadata
Assignee
- Novell, Inc.
Inventors
- Del Jensen
- Stephen R. Carter
Application Information
Application Number:US 09/352,421
Filing Date:1999-07-12
Priority Date:1999-07-12
Art Unit:7
Classifications
IPC:
G06K 946G06K 954G06K 962H04N 100G06F 1730
Field of Search:
382159382170382176382180382181382190382195382199382200382203382206382209382219382224382225382227382241382242382276382305358403707 1707 2707 3707 63752400837524009
Patent Drawings (5 sheets)
Description
Field of the Invention
[0002] The present invention relates to systems and methods for identifying and cataloging objects within a content stream, and more particularly to a novel approach for locating non-textual objects within a content stream and obtaining for each object a meaningful semantic value.
Technical Background of the Invention
[0003] New information is being stored at an ever-increasing rate on the Internet, on proprietary networks, in medical databases, in clip-art databases, in video databases, in art galleries, in civilian and military satellites, and on networks, to mention just a few locations. More and more content is being made available at these locations as they become bigger and more sophisticated. Much of the new content is non-textual, and non-textual content such as images, motion video, animation, simulation, audio, and the like will continue to be stored and used on networks. Thus, tools and techniques for identifying, measuring, filtering, monitoring, and otherwise using non-textual content are needed.
[0004] Current methods of searching, browsing, and retrieving images rely heavily on associated textual information. A picture, for example, will often have one or more words associated it in textual form, as keywords and/or a description of the picture. When someone wishes to find a particular image, a database search is performed with keywords pertaining to the desired image. If the image is not associated with the appropriate textual search terms, it might not be found. This is a problem, because similar images are often indexed under different search terms, even when one person does all the indexing for a given set of images.
[0005] Pictures with no explicit associated textual information are difficult for automated methods to index, sort, and filter, even though these operations are widely desired. For example, many people do not wish to have pornographic pictures displayed on their personal computers, so software has been developed that blocks certain Internet sites. As there are now millions of pages on the web, any blocking software must rely, at least in part, on automated methods. The sites are generally blocked by some combination of human-created filters and keyword searches, so sites that contain words considered objectionable are sometimes blocked inappropriately (e.g., medical or therapeutic sites) and some objectionable sites are not automatically filtered out.
[0006] The need to search image databases based on audio or visual content, as opposed to text labels associated with an image or recording, has been recognized for some time. Existing content-based search tools and techniques include, without limitation, template matching (a pixel level technique), texture comparison, average color comparison, color histogram analysis, shape comparison, image segmentation which interprets an image as a collection of items, characterizations based on bending energy, ellipticity, and/or eccentricity, and combinations of foregoing. One known combination uses a “probability density function” which characterizes an image using a combination of local color, texture, and shape.
[0007] Different approaches to content-based searches have different strengths. The usefulness of a given tool or technique for searching by non-textual context depends on many factors, three of which are rotational invariance, scale invariance, and reliability.
[0008] Computational efficiency is also important, but it tends to become less of a limiting factor as computation devices grow increasingly powerful and less expensive.
[0009] Although some tools and techniques exist, it would be an advancement in the art to provide additional ways to search images according to their content without relying solely on keywords.
[0010] It would also be an advance to provide new search tools and techniques that are invariant as to scale and/or rotation.
[0011] It would also be an advance to provide a novel identification and cataloging method, which extends existing identification and cataloging methods and can be used together with existing identification and cataloging methods.
[0012] In short, it would also be an advance to provide new content-based search tools and techniques for use with images and/or other non-textual content, such as digitized sounds.
[0013] Such tools and techniques are disclosed and claimed herein.
Brief Summary of the Invention
[0014] The present invention provides methods and systems for identifying and cataloging objects within a digital content stream according to recognizable features of the objects. The invention is versatile, in that it may be used on audio and video content streams, as well as non-textual digital data sets of other types. Within a visual content stream, many different image formats may be used such as gif, tiff, RGB, grayscale, and others.
[0015] To characterize content in an image file or other data set, a series of similarly-shaped but different-sized contours are placed concentrically or otherwise nested around an “area” of interest. Conventional filters can be used to locate “areas” of interest. Then the “areas” under the nested contours are transformed using transformations which produce one or more semantic values. Some instances of the invention use a ratio of intermediate transformed values to arrive at the final semantic value. The semantic value may be expressed as a single number, a vector, a series of numbers, or as some other meaningful set of values which characterizes the content according to the contours and transformations used.
[0016] Note that an “area” may be a two-dimensional area because a data set may be a two-dimensional image, but in general the “areas” from which semantic values are derived may have any finite dimensionality. Likewise, contours are not necessarily one-dimensional, since they are grounded in mathematical relationships that may be multi-dimensional. That being understood, for convenience the quotation marks around the word area will be omitted from now on, both in describing the present invention and in claiming it.
[0017] The semantic value(s) provided by contour transformations are used to position the data set area within a dictionary of archetypes. These archetypal semantic values may have textual or database labels such as “nose”, “Upper-Case A”, or “snail”, assigned to them. Semantic values which characterize one or more archetypes are compared with the semantic values derived from the new data set, to assign the data set to an archetype. If none of the archetypes fit the new data set within specified tolerances, a new archetype may be created with assistance from the user.
[0018] A “user” may be an administrator, or a non-administrative “regular” user. In either case, a user may be a person or it may be a software task or agent or other computer process acting legitimately on behalf of a person or a group of people.
[0019] Different content streams may be in different metric spaces, so a metric manager uses a series of metric definitions to characterize the metric space of a given content stream. The archetypes within the dictionary of archetypes are translated into the same metric space as the content stream using an archetype dictionary conversion means based on reverse contour transformation.
[0020] Once the content stream and the dictionary of archetypes are in the same metric space, an object finder is used to locate interesting objects (data set feature(s)), within the content stream. When something of interest is located, an object transformer transforms the data set within the content stream and assigns it a semantically meaningful value (or values). The values are then used to determine the object's identity relative to a dictionary of archetypes. Further refinement of the dictionary of archetypes and of the objects can be done using an object qualifier, which itself contains qualifier characteristics. Other features and advantages of the present invention will become more fully apparent through the following description.
Brief Description of the Drawings
[0021] To illustrate the manner in which the advantages and features of the invention are obtained, a more particular description of the invention will be given with reference to the attached drawings. These drawings only illustrate selected aspects of the invention and thus do not limit the invention's scope. In the drawings:
[0022] FIG. 1 is a diagram illustrating a network of computers which are individually and collectively among the many systems suitable for use with the present invention.
[0023] FIG. 2 is a diagram representing an image to be characterized according to the invention.
[0024] FIG. 3 shows the image of FIG. 2 with contours illustrating a method of the invention.
[0025] FIG. 4 is a diagram illustrating a space of semantic values which can be associated with images and other non-textual data according to the invention.
[0026] FIG. 5 is a flowchart illustrating methods of the present invention.
[0027] FIG. 6 is a diagram illustrating systems of the present invention.
[0028] FIG. 7 is a diagram illustrating a signal according to the present invention for searching or cataloging non-textual objects and object features.
Detailed Description of the Preferred Embodiments
[0029] The present invention provides tools and techniques for identifying and classifying objects within a non-textual content stream. The content stream includes one or more images, audiovisual recordings, or the like, in files, blocks, bitstreams, packets, forming one or more digital data sets. The invention can be used as a substitute for conventional approaches when searching or filtering content streams, or it can be used to supplement conventional approaches. The invention may be used, for instance, in content filters which screen out objectionable materials during use of the Internet/World Wide Web, in search engines which locate images in a database matching specified content constraints, and in vision systems which provide input to manufacturing or other computer-aided processes.
[0030] Data Sets Generally
[0031] Suitable data sets for analysis according to the invention include two-dimensional pixel arrays; three-dimensional pixel sets, color pixels using RGB, HSV, or another color space; grayscale pixels; pixels obtained from an MFI, NMR, or CAT scan; audio stream data, and other digital data sets. Suitable images may be generated from raw data using familiar scientific visualization tools and techniques. Images from still pictures, video images, television images, images broadcast over the internet using video streaming techniques, 35 mm images, 16 mm images, without restriction, can also be utilized.
[0032] As used here, “digital” data sets generally include digitized data sets derived through analog-to-digital conversion. Digitizing involves obtaining samples having a position (in time and/or space) and also having values such as colors or grayscale intensity (for an image), or amplitude and frequency (for audio stream data). These samples are referred to as “pixels” in digitized images. Although digitized images are used as the primary example, other data sets can also be used according to the invention. Many file formats are used to hold digital data sets, including pictures in GIF (Graphic Interchange Format), TIFF (Tag Image File Format), JPEG (Joint Photographic Experts Group), IPX, and other formats. Suitable audio file formats include the MP3, WAV, and other formats. Suitable audiovisual formats include MPEG, AVI (Audio Video Interleaved), MOV, and others. A wide variety of other digital data sets are known to those of skill in the art.
[0033] Images and/or other digital data sets are provided to embodiments of the invention in a content stream. One type of content stream is a communication line sporadically or continually transmitting content from one location to another. A content stream may also consist of a single image such as a photograph, an X-ray, or a single audio file.
[0034] Computers and Networks Generally
[0035] The invention may be used with individual computers, with suitable networks, or both. Suitable networks include local networks, wide area networks, and/or the Internet. “Internet” as used herein includes variations such as a private Internet, a secure Internet, a value-added network, a virtual private network, or an intranet.
[0036] FIG. 1 illustrates a network 100 which is one of the many possible networks suitable for adaptation and use according to the present invention. The network 100 may be connectable to other networks 102, including LANs or WANs or portions of the Internet or an intranet, through a gateway or similar mechanism, thereby forming a larger network which is also suitable for use according to the invention.
[0037] The illustrated network 100 includes a server 104 connected by communication links or network signal lines 106 to one or more network clients 108. Other suitable networks include multi-server networks and peer-to-peer networks. The server(s) 104 and client(s) 108 each include an addressable storage medium such as random access memory.
[0038] Suitable network clients 108 include, without limitation, personal computers; laptops 110, personal digital assistants, and other mobile devices; and workstations 112. The signal lines 106 may include twisted pair, coaxial, or optical fiber cables, telephone lines, satellites, microwave relays, modulated AC power lines, RF connections, a network link, a dial-up link, a portable link such as an infrared link, and/or other data transmission “wires” (communication links) known to those of skill in the art. The links 106 may embody conventional or novel signals, and in particular, may embody novel archetype and/or semantic value signals for cataloging, filtering, and other data set analysis tools and techniques as discussed herein.
[0039] The server(s) 104 and/or client(s) 108 may include a non-volatile program storage medium such as a magnetic or optical disk, ROM, bubble or flash memory. A suitable program storage medium includes a magnetic, optical, or other computer-readable storage device having a specific physical configuration. Suitable storage devices include floppy disks, hard disks, tape, CD-ROMs, PROMs, random access memory, ROM, flash memory, and other computer system storage devices, configured according to the present invention.
[0040] The physical configuration represents data and/or instructions which cause the computer system 100 to operate in a specific and predefined manner as described herein. Thus, the program storage medium tangibly embodies a program, data, functions, and/or instructions that are executable by servers and/or other computers to perform digital data set cataloging, filtering, and/or searching steps of the present invention substantially as described herein. Suitable software and hardware implementations according to the invention are readily provided by those of skill in the art using the teachings presented here and programming languages and tools such as Java, Pascal, C++, C, assembly, firmware, microcode, PROMS, and/or other languages, circuits, or tools.
[0041] Contour Transformations Generally
[0042] As noted, the invention uses contour transformations to obtain semantic values that characterize content in non-textual data sets. The semantic values reside in a metric space. As is well understood in the art, a metric space is a space of points which has an associated metric or distance function that assigns distances to pairs of points in the space. A space may have more than one associated metric, but any given metric function d(x, y) must satisfy conditions known as positivity, symmetry, and the triangle inequality for all points x, y, z in the space. According to positivity, d(x, y) is greater than or equal to 0; d(x, x)=0; and d(x, y) is greater than 0 if x does not equal y. According to symmetry, d(x, y)=d(y, x). According to the triangle inequality, d(x, y) is less than or equal to d(x, z)+d(z, y).
[0043] To determine how “close” two or more entities (points or sets of points) are in a space, a distance function d(x, y) is used as a measure. Closeness might be measured, for instance, to determine where in a dictionary of object archetypes a specific object should be included. “Distance” is a generalized idea of similarity or closeness, which may be implemented in various ways. For example, within the metric space M=R2(the plane) the “Euclidean” distance is defined by dist1((x1,y1),(x2,y2))=((x2−x1)2+(y2−y1)2)½. Another distance function is the “taxicab” or “city block” metric for the plane, which measures distance as if a city block grid were overlaid on the plane. A Hausdorff distance gives a measure of nearness between sets.
[0044] For a vector valued function F with continuous first order partial derivatives defined on R2, the plane, or R3, a three-dimensional space, the Divergence Theorem states that
[0045] where C is a simple closed surface, and V is the volume enclosed by C. This mathematical equality can be used to change a contour integral into a volume integral, or vice versa.
[0046] Formula 1 is used according to the invention for the specific purpose of facilitating calculations to obtain a single number (in this example) or a range or set of numbers that serve as semantic values which can then be used to group images or other non-textual data content into a dictionary of archetypes, perform filtering, and/or perform searching steps as described herein. The shape and orientation of the surface C characterize the semantic values obtained; some embodiments of the invention use spheres and circles, while others use elliptical shapes or other shapes. The Divergence Theorem has many, many other applications in engineering, physical and applied sciences, and other fields, which are outside the scope of the present invention.
[0047] The contour integral on the left of Formula 1 can be very costly to compute directly, but the corresponding volume integral is relatively easy to compute. Thus, the average behavior of F over a suitable boundary can be computed with relative ease. This contour-integral-to-volume-integral transformation (“contour transformation”), as applied in the context of the present invention, provides useful and concrete results in the form of semantic values suitable for partially or fully automatic identification and/or classification of digital data set contents.
[0048] To illustrate how one might make use of the Divergence Theorem according to the specific requirements of the present invention, consider an example in the form of a digitized grayscale image, such as a scanned photograph or a radiological image. As noted, the invention may also be used to identify content in other digital data sets. As a particular example, FIG. 2 shows a line drawing or outline of a letter “A” with X and Y coordinate axes 200, 202 superimposed for reference.
[0049] A grayscale image may be represented as vectors or pixels, but the present discussion assumes for simplicity's sake that the image data set includes a rectangular array of discrete pixels, the pixels uniformly tile the logical view surface, and each pixel specifies a scalar value from a discrete range corresponds to represent the grayscale intensity at the pixel's location. One common grayscale range is the integer range [0-255], which corresponds to grayscale values that can be displayed on most video monitors, but grayscale values in other ranges, such as [0-4095] and [0-65536], may also be used.
[0050] Other color models than the grayscale model may also be used to define images in the content stream. For example, color pixel values can be defined as a composite number containing intensities of three different colors. An RGB scale or basis with basic color components red, green, and blue is commonly used, but other color spaces (such as the CMY scale composed of cyan, magenta, and yellow) also are known and suitable for use according to the invention.
[0051] As a practical matter, the idealized grayscale function
[0052] intensity=f(x,y)
[0053] is generally approximated by a step function, where the intensity is constant over the regions
[0054] x(n−1)≦x<xn, y(m−1)≦y<ym, nε{1, 2, 3, . . . N}, mε{1, 2, 3, . . . M},
[0055] the domain having been uniformly partitioned into N intervals in the X-direction and M intervals in the Y-direction which correspond to uniform pixels. There is no theoretical requirement that the pixels be uniform or rectangular, but in practice uniform and rectangular pixels are most often encountered.
[0056] Given the grayscale step function, one constructs an approximation to the vector field
[0057] F(x,y)=[𝑓x(x,y), 𝑓y(x,y)]
[0058] The vector function F will assume the role of the integrand for the expression on the left of Formula 1.
[0059] FIG. 3 shows the image of FIG. 2, with three contours indicated by concentric circles. Contour C1in Formula 2 below refers to a concentric circle 300, C2refers to a concentric circle 302, and C3refers to a concentric circle 304. For a spherically symmetric surface C, the expression
[0060] is invariant under rotation about the center of C. One can characterize a rotationally invariant object or object feature in an image's content using contour similarity class ratios. The scale-invariant vector [u1, v1], is used where u1=C1(F)/C2(F), and where v1=C2(F)/C3(F).
[0061] The contours shown in FIG. 3 are spherically symmetric, but contours which are otherwise symmetric, and asymmetric contours, may also be used according to the present invention. Different contours provide different semantic values and hence different content characterizations. For example, ellipses with vertical major axes tend to be invariant under 180 degree rotations and vertical reflections, but “blind” in the horizontal direction, and so would be suitable for applications involving images with content having corresponding qualities.
[0062] The space Rn(in this case, the real plane R2) can be used as a metric for semantically ranking neighborhoods in the spatial domain of F against a dictionary of archetypes through the contour transformations
[0063] u(nf)=C1(F)/C2(F),
[0064] and
[0065] v(n𝑓)=C2(F)/C3(F) (formula 3)
[0066] where nfis a connected, closed, bounded neighborhood in the domain of f, and F is the vector-valued derivative of f. A “neighborhood” of a given point x is a set of points within some distance of the point x. A neighborhood is a generalization of the idea of a circle having a radius r and a center at the given point x. That is, the neighborhood of a point x is the set of all points y such that d(x, y)<r for some r>0. A set is “bounded” if the entire set can be enclosed in a neighborhood of sufficiently large radius. A set is “closed” if the set contains all of its limit points. A point x is a “limit point” of a set S if every neighborhood of x contains at least one point of S, regardless of how small the neighborhoods of x become.
[0067] The contour transformation above, applied to a series of images, produces a single number or set of numbers per region of interest in each image. These semantic values can be interpreted to form a group of contour similarity classes when similar images are compared as a group. For example, the semantic values for pictures of “chairs” or “noses” or “X's”, will tend to be grouped together. The contour transformation, therefore, defines contour similarity classes, and more specifically contour similarity classes which depend not only on the contour but also on ratios. Contour similarity classes (with or without ratios) can be used to form a dictionary of archetypes, which includes semantic values and corresponding interpretations in the form of text labels, database keys, or other indicia. For instance, a range of semantic values specified by the dictionary might define “chairs”, while another range defines “noses”, and so on. Regions may generally be used in some embodiments in the role of a range as discussed herein, and sets of semantic values may be used in the role of a single semantic value.
[0068] FIG. 4 illustrates a metric space 400 for a dictionary of archetypes. The space 400 is a u, v space having a V-axis 402 and a U-axis 404. The axes shown are at right angles to one another, but other orthogonal (non-parallel) axes may be used, and they may, of course, be labeled X, Y or otherwise instead of U, V. Although FIG. 4 illustrates a two-dimensional space, metric spaces of one or more dimensions may be used according to the invention.
[0069] When ratios of expressions of the form shown in Formula 3 are used, a dictionary of archetypes is defined according to the relative geometry of the contours, not by their absolute geometry. For example, in the case of the outline “A” shown in FIG. 3, any three concentric contours Cx, Cy, Cz, where Cx/C1=Cy/C2,=Cz/C3, will be compatible with the metric of FIG. 4. The ordered triple (Cx, Cy, Cz) is similar to the triple (C1, C2, C3).
[0070] For example, consider a point (u1, v1) identified at 406 which maps under the u, v transform defined in Formula 3 to an “A”, and a point (u3, v3) identified at 410 which maps to a “B” under the same u, v contour similarity class transform. Suppose a point (u2, v2) identified at 408 is a semantic value obtained from an image under the same u, v contour similarity class transform. Since (u2, v2) is closer to (u1, v1) than it is to (u3, v3), the corresponding content of the image from which (u2, v2) was obtained is more “A-like” than “B-like”. Likewise, any connected, closed, bounded, region of the domain which is closer to the point at 406 than the point at 410 corresponds to image content that is more “A-like” than “B-like”, at least according to the contour similarity class transform involved. Similar results hold when the digital data set involved is not an image.
[0071] Alternative embodiments of the invention use the contour transformation
[0072] u(n𝑓)=C1(F), v(n𝑓)=C2(F), w(n𝑓)=C3(F) (formula 4)
[0073] The (u, v, w) transformation shown in Formula 4 is linear, while the transformation in Formula 3 is not. The transformation in Formula 3 is scale-invariant under contour similarity, but may be less robust with respect to normalizing different non-linearities in the digitizing process to acquire the step-function 𝑓. In some cases and for some classes of digitizers, Formula 3 may be more robust than Formula 4.
[0074] A dictionary of archetypes metric, whether expressed via the transform shown in Formula 3 or the transform shown in Formula 4, is completely characterized by the contour similarity classes. Some similarity classes may be “well-conditioned” in that the dictionary elements are uniformly distributed and well spaced. Others may have non-uniform distribution but be useful nonetheless, with particular types of digital data or particular content objects or object features.
[0075] The three contours 302, 304, 306 may be placed using conventional methods that have been developed to locate the “most important” or “most interesting” parts of pictures. For example, boundary-finding algorithms exist that attempt to differentiate the subject of a picture from the background. Alternatively, the contours could be arranged around pixels chosen according to some predetermined sampling scheme which is used regardless of the content of the specific image being sampled.
[0076] The invention may be used in conjunction with existing neural net methods. For instance, contour transformations and images of starfish could be used to train the neural net to understand the generalized idea of a “starfish”, to learn where the contours 302, 304, 306 should be placed in analyzing images that may contain starfish, and/or to learn what shape of contours work best with such images. The neural net could also be trained to determine when using ratios of contour similarity class functions (Formula 3) is likely to work better than not using them (for example, as with Formula 4).
[0077] Methods
[0078] The invention may be embodied in one or more methods, systems, signals, and/or configured storage media. Those of skill in the art will apply the teachings provided here to various embodiments as appropriate. In particular, unless clearly indicated otherwise the discussion herein of methods applies to systems, configured storage media, and signals according to the invention, and the discussions of systems, configured storage media, and signals also apply to the inventive methods.
[0079] Some methods of the invention are illustrated in FIG. 5. During an area choosing step 500 at least two contour areas are chosen. This involves choosing the shape of the contour and its location relative to the digital data set contents. As used herein, “placing a contour” is synonymous with “choosing an area”; both phrases indicate that a portion of the digital data set has been chosen for contour transformation. As discussed above, each selected contour is connected, closed, and bounded, to permit use of the relationship shown in Formula 1. The contours may be symmetric, as shown in FIG. 3, or asymmetric.
[0080] At least two of the contours are generally nested, in that one is at least partially inside the other. If three contours are placed, then two levels of nesting can be used. For instance, the contours may be concentric circles or ellipses of different sizes. Nested contours may be placed from the inside contour outward, from the outermost contour inward, or in another order.
[0081] The contours are preferably placed around an “interesting” portion of the image or other data set. An interesting portion may be located, using various tools and techniques, including neural nets, texture comparison, average color comparison, color histogram analysis, shape comparison, or a combination of the above. For instance, skin-tones could define areas of interest in a filter designed to filter sexually explicit images according to the invention, and differences between satellite images taken of a given location at different times (indicating potential human or equipment movement) could define areas of interest in a filter designed to search for images of military value. In a facility which uses computer-aided vision tools and techniques to detect flaws in manufactured items, the camera and each item being inspected could be in a predetermined position relative to one another, so that the same portion of the resulting image is normally selected as the area of interest.
[0082] The data in the contour areas is transformed during a step 502 to produce at least one semantic value, as described above. Recall that some methods use contour ratios 514, such as those described in connection with Formula 3, and some methods do not, such as those described in connection with Formula 4. Either type of contour transformation produces at least one semantic value. A semantic value may be a scalar, or it may be a multi-dimensional vector or set.
[0083] During a using step 504, the semantic value(s) obtained with the contour trans- formations are used in one or more ways. For instance, the semantic values may be used to build a dictionary of archetypes during a step 506, to identify and block objectionable content during a step 508, and/or to search for particular content objects or object features in a database or other collection of images or other digital data sets during a step 510.
[0084] During the storing step 506, the semantic value produced by the contour transformation and/or associated information is stored within a dictionary of archetypes. This may involve comparing the new semantic value with semantic values for archetypes previously stored in the dictionary. For instance, if the semantic value is in a range or region of values belonging to an existing archetype (“noses” or “starfish”, for instance) then the corresponding data set content object (or its address) might be added as one more example of that archetype. If the semantic value is more than a predetermined distance from any existing archetype's semantic value(s) then a new archetype could be added.
[0085] Archetype signals are discussed in connection with FIG. 7, but in general they may include one or more semantic values obtained from contour transformations plus a copy of the content object (or a pointer to it); an archetype may also contain a textual description or a list of keywords. The present invention can be used in a process which categorizes content and associates keywords with the content to permit subsequent searches using conventional text-based search engines, conventional relational or hierarchical databases, directory services such as Novell's NDS, or the like.
[0086] During the blocking or removing step 508, the semantic value produced by the contour transformation is used to block or reroute at least a portion of a digital data set. The portion may be an individual file, a record in a database, or an entire digital data set, for instance. This step 508 may use a dictionary of archetypes if several objectionable content objects, or several objectionable combinations of individually innocuous objects or features, are to be blocked or rerouted. For instance, a dictionary of archetypes could be used to identify sexually explicit images. However, in some embodiments a complex dictionary is not needed, because only the semantic values themselves and a fixed set of prohibited values are used. If the semantic value for a given portion of the content stream falls within the fixed set of prohibited semantic values, then that portion of the content is blocked or rerouted in a predefined manner. Conventional tools and techniques for preventing further transmission of data and/or rerouting data may be used.
[0087] During the searching step 510, the semantic value produced by the contour transformation is used to locate portions of the content stream containing objects that tend to give rise to semantic values near a target semantic value under the transformation in question. The relationship between content objects (or object features) and semantic values is not necessarily one-to-one, in that different types of content may map under a contour transformation to nearby semantic values. But a mapping from content to semantic values need not be one-to-one to be useful. By way of an analogy, conventional keyword searches sometimes produce unwanted results and sometimes fail to produce desired results, but they are still helpful and widely used.
[0088] FIG. 5 is meant to assist an understanding of the present invention, not to summarize every aspect of the invention or even every method. The methods, signals, systems, and configured storage media of the invention are defined by the claims, in view of the entire specification, not merely by FIG. 5. In particular, steps may be repeated, as when several portions of content are blocked or rerouted during repeated steps 508. Steps may also be omitted. For example, a filtering embodiment that performs step 508 might reference an existing dictionary of archetypes without performing step 506 to build the dictionary further. Steps may also be reordered or done concurrently, unless one step requires the result of a previous step. Moreover, steps may be grouped differently or renamed. As noted, some embodiments do not use ratios when transforming the data during step 502 while others do; these could be separately named steps in some embodiments. Some or all of these variations may be present in an embodiment, regardless of whether they are expressly described or shown as optional outside the claims.
[0089] Systems
[0090] A system 100 according to the invention is further illustrated in FIG. 6. Such systems use the semantic values produced by contour transformations of images and/or other digital data to “filter” data in various ways, as discussed in connection with step 504. Each system 100 includes one or more computer systems 600 having processor(s) 602, RAM or similar working memory 604 for the processor(s) 602, and nonvolatile storage 606 such as a hard disk. If multiple computer systems 600 are present in the system 100, the computer systems 600 may be individual nodes of a network such as a LAN, or the computer systems 600 may themselves be networks in a larger network, such as the Internet or a portion thereof, such as a LAN connected to the Internet, a virtual private network, and so on.
[0091] In various embodiments, one or more of the components discussed below are also present in the system 100. These components are shown separately for clarity of illustration, but those of skill will appreciate that the components may be implemented as data structures in one or more of the memories 604 and/or storage media 606, as code executable by the processor(s) 602 and stored in one or more of the memories 604 and/or storage media 606, or as a combination of data structures with code and processing hardware.
[0092] A dictionary of archetypes 608 may be used within a cataloging and/or searching system 100 to process content and identify objects. The dictionary of archetypes 608 may begin empty for a given content stream or user or session, and be built as archetypes 610 are added to it. Alternatively, the dictionary of archetypes 608 may already contain archetypes 610, and during a particular use may then be either static (read-only) or modifiable. As discussed, the content objects are not text but rather include some signal-type data that is defined by some n-space (e.g., color may be defined by a 3-space as RGB) and further characterized by being recognizable as objects, nested objects, and/or overlapping objects.
[0093] Each archetype 610 within the dictionary 608 includes a semantic value 612 produced by a contour transformation of content. The archetype 610 may include a single semantic value 612, a range or region of semantic values 612, or a set of discrete semantic values 612. The semantic value(s) from a newly transformed image (or a transformed image being presented to the dictionary of archetypes for the first time) is compared to the archetype 610 semantic values 612 to determine if the data set object(s) represented by the archetype 610 are likely to be present in the image. Comparison need not be done with every archetype 610 in every case, even if no match exists, because the archetypes 610 can be organized in ordered trees or hash lists or otherwise ordered according to their semantic values 612 to permit efficient searches of those semantic values 612.
[0094] For instance, if a semantic value from a given image is in (or within a specified distance of) the region of semantic values 612 belonging to an archetype 610 with a label 614 of “nose”, then a nose is likely to be present in the image. When such a match exists, the archetype 612 may be updated in one or more ways. A counter in the archetype 610 may be incremented. A thumbnail, grayscale version, windowed subset, or other excerpt 616 of the image may be added to the archetype 610. A pointer, address, filename, index or other identifier may be added to help locate the image when the archetype 610 is given (or vice versa). A database key 618 for a relational, hierarchical, directory service, or other database may be used in addition to, or in place of, a textual label 614.
[0095] If comparison of the semantic value from a given image with semantic values 612 belonging to all archetypes 610 determines that no archetype 610 is matched, then a new archetype 610 containing the previously unmatched semantic value 612 may be created. The archetype 610 may be given its values, such as the values 612 through 618, entirely automatically and/or with human assistance.
[0096] An object finder 620 monitors a content stream to find areas of interest. The content stream could be a communication line 106 continually or intermittently holding content which moves from a source to a destination through the line, or the content stream could be some content repository whose data is not in transit (except as needed to feed the content analysis described herein). To find objects in these areas of interest, the object finder 620 uses a metric definition 622 that characterizes the content stream in any given n-space. Some embodiments of the invention contain several object finders 620, each of which corresponds to a different metric space through corresponding metric definitions 622. Metric definitions 622 are managed by a metric manager 624, in a manner analogous to the management of templates, handles, or other resources in conventional systems.
[0097] The object finder 620 is in communication with a DOA converter 626 which transforms prospective content stream objects into the same metric space as the dictionary of archetypes 608. An object comparer 628 is used to compare the semantic values resulting from the transform with the values 612 currently in the dictionary of archetypes 608, to identify objects which match one or more archetypes 610. In some instances of the invention, if no matching archetype 610 is found for an object, a new archetype 610 can be created and used to classify this object. The object finder 620 thus finds and identifies objects; it may also tag an identified object to the content in which it was found. This allows other modules or processes 630 to further analyze and use the content by referencing the tagged content in the context of the identified objects.
[0098] In particular, identified objects may be further manipulated or used by an object qualifier 632 which refines the dictionary of archetypes 608 and object identifications by further processing the identified objects against one or more qualifier characteristics 634. The object qualifier 632 closely scrutinizes the categories that exist and the objects whose values are known. If a better fit is found, then the contents in the dictionary of archetypes 608 can be modified, archetypes 610 can be added or deleted, or the values within the archetypes 610 can be modified. Objects thus qualified may be provided to users 630 and/or be used to discover additional characteristics that would further refine dictionary of archetypes 608 entries, better identify objects, and better define the qualifier characteristics 634. The refinement may be done with human assistance, through neural nets, statistical analysis, or other some process permitting finer distinctions to be made. For instance, an object might be characterized not only as a “nose” but as a “nose with a wart”.
[0099] A given object user 630 can utilize the identified objects in various ways. In a searching system 100, the object user 630 utilizes the information in the dictionary of archetypes 608 to choose objects which have corresponding archetypes 610. For example, if a user desired pictures of seahorses, the object user 630 could choose those images stored within a seahorse archetype 610. If a more specific image was needed, such as a blue seahorse, then the qualifier characteristics 634 could be used.
[0100] FIG. 6 is meant to assist an understanding of the present invention, not to summarize every aspect of the invention or even every system. The systems of the invention are defined by the claims, in view of the entire specification, not merely by FIG. 6. Systems may have more or fewer individual components than are shown in the illustration. For instance, a single system may have many metric definitions 622, even though only one is illustrated. Likewise, at a given point in time a dictionary of archetypes 608 may hold zero or more archetypes 610.
[0101] An illustrated system component may also be omitted. For example, the object qualifier 632 and the qualifier characteristics 634 are not present in some implementations. Moreover, system components may be grouped differently or renamed. These variations may be present in an embodiment regardless of whether they are expressly described or shown as optional outside of the claims.
[0102] Signals
[0103] FIG. 7 illustrates a signal 700 according to the invention. The signal 700 may be embodied in a computer system 600, memory 604, storage 606, in a separate configured program storage medium, and/or in a communication link such as a network signal line 106. The signal may be used in filtering objectionable content, searching for desired content, building or modifying a dictionary of archetypes 608, and/or other non-textual digital data set analysis steps taught herein.
[0104] The illustrated signal 700 includes at least one semantic value 702 that is created when a prospective object in the content stream is transformed according to a method discussed earlier. This semantic value 702 may be a scalar (integer or real), vector or other multi-dimensional number, a set of such values, or in another form known to those of skill in the arts according to the teachings herein.
[0105] The illustrated signal 700 also includes at least one archetype 610 with at least one semantic value 612. The illustrated archetype 610 includes an image excerpt 616 but other signal embodiments may include a text label 614, a database key 618, and/or other fields. For instance, fields such as timestamps, checksums, linked list or similar addresses, and the like may be present.
[0106] The signal 700 components are not necessarily stored contiguous to one another, or even in the same medium, although each necessarily resides somewhere in the system 600 and the components all exist at the time in question. An archetype 610 identifier is used in some signal embodiments to identify a current archetype 610 within the dictionary of archetypes 608 in connection with the transformation value(s) 702. This identifier may include a memory pointer (address) or an index into an array, such as a pointer or index into a list or array of archetypes 610.
[0107] FIG. 7 is meant to assist an understanding of the present invention, not to summarize every aspect of the invention or even every signal. The methods, signals, systems, and configured storage media of the invention are defined by the claims, in view of the entire specification, not merely by FIG. 7. Signal components may be repeated; for example, several archetype objects 610 may be associated with the semantic value(s) 702 in question. Signal components may also be omitted. For instance, one embodiment of the invention does not store an image excerpt 616 within the signal 700. Signal components may be stored in different orders or arrangements than that shown, and may be associated to form the signal by being stored together and/or by links such as pointers or table indices. Moreover, signal components may be grouped differently or renamed. These variations may be present in an embodiment regardless of whether they are expressly described or shown as optional outside the claims.
Summary
[0108] In summary, numerous context-based methods for cataloging or filtering images are known. However, the present invention provides context-based cataloging tools and techniques which supplement or replace other approaches by utilizing contour transformations. This makes it possible to identify objects and features in content streams in previously unknown ways.
[0109] Articles of manufacture within the scope of the present invention include a computer-readable storage medium in combination with the specific physical configuration of a substrate of the computer-readable storage medium. The substrate configuration represents data and instructions which cause the computers to operate in a specific and predefined manner as described herein. Suitable storage devices include floppy disks, hard disks, tape, CD-ROMs, RAM, and other media readable by one or more of the computers. Each such medium tangibly embodies a program, functions, and/or instructions that are executable by the machines to perform digital data set analysis steps substantially as described herein.
[0110] Although particular embodiments of the present invention are expressly illustrated and described herein, it will be appreciated that other embodiments may also be formed according to present invention. Unless otherwise expressly indicated, the descriptions herein of methods, signals, systems, or configured storage media, respectively, of the present invention each extend to corresponding embodiments in the other three forms.
[0111] As used herein, terms such as “a” and “the” and item designations such as “image” and “object” are inclusive of one or more of the indicated item. In particular, in the claims a reference to an item means at least one such item is required. When exactly one item is intended, this document will state that requirement expressly.
[0112] The invention may be embodied in other specific forms without departing from its essential characteristics. The described embodiments are to be considered in all respects only as illustrative and not restrictive. Headings are for convenience only. The scope of the invention is, therefore, indicated by the appended claims rather than by the foregoing description. All changes which come within the meaning and range of equivalency of the claims are to be embraced within their scope.
Claims
What is claimed and desired to be secured by patent is:
1. A method for analyzing digital data, comprising the computer-implemented steps of:
choosing a plurality of data-independent contours;
placing the chosen contours on the digital data, each contour defining a connected, closed, bounded area within the digital data, the contours being nested in that one of the plurality of contours surrounds the other contours; and
transforming the chosen contours of data using a contour similarity class transformation to produce at least one semantic value.
2. The method of claim 1, wherein:
the choosing step chooses three contours of data; and
the placing step places each contour on the digital data to define a connected, closed, bounded area within the digital data, the three contours being nested in that one of the three contours surrounds the other two contours, and the transforming step transforms the three contours of data using a contour similarity class transformation to produce at least one semantic value.
3. The method of claim 1, wherein the contour similarity class transformation uses contour ratios to produce the semantic value.
4. The method of claim 1, wherein the choosing step comprises using an entity finder to choose an area of interest within the digital data.
5. The method of claim 1, further comprising the step of storing the semantic value within a dictionary of archetypes.
6. The method of claim 5, wherein the dictionary of archetypes contains individual archetypes each of which comprises at least one semantic value and a corresponding textual label, and the semantic value produced by the transforming step is stored based on an ordering imposed on the semantic values of the archetypes.
7. The method of claim 1, wherein the transforming step produces a region having a plurality of semantic values.
8. The method of claim 1, wherein each chosen contour is spherically symmetric.
9. The method of claim 1, wherein each chosen contour is elliptically symmetric.
10. The method of claim 1, wherein each chosen contour is circularly symmetric.
11. A computer program storage medium having a configuration that represents data and instructions which will cause at least a portion of a computer system to perform method steps for analyzing non-textual digital data, the method steps comprising the steps of:
choosing at least two data-independent contours;
placing the chosen contours on the non-textual digital data to define areas of data within the non-textual digital data, each area being a connected, closed, bounded area within the non-textual digital data, the areas being nested; and
transforming the areas using a contour similarity class transformation to produce at least one semantic value.
12. The configured storage medium of claim 11, wherein the contour similarity class transformation is scale-invariant.
13. The configured storage medium of claim 11, wherein the contour similarity class transformation is rotationally-invariant.
14. The configured storage medium of claim 11, further comprising the step of accessing a dictionary of archetypes.
15. The configured storage medium of claim 11, wherein the digital data is two-dimensional.
16. The configured storage medium of claim 11, wherein the digital data is multi-dimensional.
Patent Citations (6)
Non-Patent Literature (16)
- Hsu, et al discloses (A Knowledge-Based Approach for Retrieving Images by Content), IEEE, Aug. 1996, pp. 522-532.Applicant
- Ozer, et al (A Graph Based Object Description for Information Retrieval in Digital Image and Video Libraries), IEEE, Jun. 22, 1999, pp. 1-4.Applicant
- Deng discloses (NeTra-V: Toward an Object-Based Video Representation), IEEE, Sep. 1998, pp. 616-627.Applicant
- Smith, et al (Searching for Images and Videos on the Word-Wide Web), pp. 1-20, 1996.Applicant
- Liu, et al (Partial Shape Classification Using Contour Matching in Distance Transformation), IEEE, Nov. 1990, pp. 1072-1080.Applicant
- Saber, et al (Integration of Color, Shape, and Texture for Image Annotation and Retrieval), IEEE, 1996, pp. 851-854.Applicant
- Chu, et al (Knowledge-Based Image Retrieval with Spatial and Temporal Constructs), IEEE, Nov. 1998, pp. 872-888.Applicant
- SurfWatch Allowed Key Patent, pp. 1-3; Nov. 16, 1998.Applicant
- Methodology, pp. 1-5; 1997.Applicant
- Gudivada et al., “Design and Evaluation of Algorithms for Image Retrieval . . . ”, 1995.Applicant
- CANDID Executive Summary, Nov. 19, 1998.Applicant
- “Faulty Filters . . . ”, pp. 1-8, 1997.Applicant
- Smith et al., “Searching for Images and Videos . . . ”, pp. 1-20; 1996.Applicant
- Nes et al., “Region-based Indexing . . . ”, 1997.Applicant
- Han et al., “Image Organization and Retrieval . . . ”, 1996.Applicant
- Method and Apparatus for Semantic Characterization, filed Jul. 2, 1998.Applicant