Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
1997-11-04
2001-12-18
Au, Amelia (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S187000, C382S203000
Reexamination Certificate
active
06332040
ABSTRACT:
TECHNICAL FIELD
This invention relates to the use of computing devices and systems to classify, manipulate, store, search, and retrieve items of image databases.
BACKGROUND ART
People make all kinds of informal drawings as pictorial notations, from quickly encircling objects of interest to sketching details in scenes, designs, and concept proposals. Descriptive drawings of events and situations may be choreographed as complexes of linear motion paths. Patterns of animal migration or movements of hurricanes are shown and compared through clusters of such lines of movement.
Computing devices increasingly are used to track motions, whether in pen based graphic devices responding to stylus movements or in process monitoring equipment where motion data may be calculated from a complex field of events. Such linear motion analyzers can range from relatively simple hand-held Personal Digital Assistants (PDAs) to large and complex arrays of motion detectors, cameras, and other specialized equipment communicating across computer-mediated networks.
As used herein, glyph means a line drawing or other linear configuration that communicates specific relationships or details as structural factors of the motion paths constituting the configuration itself. It is important to distinguish between the schematic configuration of motion paths and the rendered image of a glyph. Even in simple line drawings the marks laid down by a pen or other implement may vary widely. For instance the characteristic imprint of a given type of implement may result in lines that are extremely broad or very narrow. Or the implement may respond to varying pressure, as with a lettering brush or angled calligraphy pen. Or the moving implement may be bounced along its path to draw dots and dashes instead of a solid line. All of these and other variations may be emulated in a computer graphic input system such that variations in the marks rendering various configurations may confuse and obscure similarities in their underlying pattern of motion paths. During comparison of drawn configurations such incidental mark variations can obscure strong similarities of line path disposition and consequently hinder interpretive methods that are dependent solely upon analysis of sets of local mark features.
Because they are so widely evident in human enterprise, glyphs have great potential for user interfaces in such computer-mediated tasks as pictorially searching image databases and guiding computer controlled processes by means of glyph-structured gestures.
To exploit glyphs in a computing environment requires a method of sorting, comparing, and grouping them in terms of their qualitative features. Evaluating structural similarities among a varied collection of glyphs is fundamental to using them as representative tokens of external entities, as data keys for accomplishing pictorial searches of image databases, or as elements of interface control. Comparison of glyph structures is a necessary part of extracting useful pictorial information from their configurations.
Many different techniques have been devised to use glyphs as part of graphic user interfaces of computer systems to enable direct input of pictorial information and to graphically designate search keys for retrieving items from image databases. To the extent that these and other applications rely upon matching local representational features of visual media with specific conceptual content they may be treated as content-centered search keys, whether in textual, pictorial or other media context.
In the earliest databases image features were described by text synopses so that data operations could be directed in terms of keywords and phrases found in the reference text. Such high-level conceptual content keying introduces ambiguities throughout creation, maintenance, and use of textually keyed databases since there is a need to analyze and interpret pictorial content in terms of a common repertoire adequate to the domain of intended use. For example, an architect probably uses quite different keywords for a database of buildings and structures in a city than those relevant to a military tactician or a social historian. As computing systems gained graphic user interfaces, icons that could be activated by a pointing device such as a mouse, stylus, or trackball displaced keyboard commands. But the fundamental dependence upon retrieval by content features has persisted even into pervasively graphic control systems. Whether searching for key words or for key assemblies of local pictorial elements the same problem persists: where the size of the database is large and each item is a complex structure, the processing cost of exhaustively comparing every member with a key is prohibitive. Some means is needed of low-level structural filtering to quickly eliminate unqualified pretenders and to extract a collection of highly likely match candidates that subsequently can be processed in terms of high-level content based parameters.
Existing drawn figure and handwriting recognition devices typically use a template repertoire of local mark features against which to compare and match manually drawn gestural strokes. For each cluster of input lines interpretive software attempts to determine the presence or absence of known features such as lines extending below a baseline; proximity and connection of angles, curves, straight line segments; and closed loops with protruding line extensions. Each input configuration is tested against such template features to arrive at match candidates. Further processing of contextual information may be made to disambiguate matching probabilities, to interpret, and finally to display the recognized characters or word. Graphic interfaces sometimes isolate and compare geometric features of simple shapes to decipher and characterize circles, ellipses, squares, rectangles, triangles, and even free-form shapes drawn by hand.
Current approaches to interpreting linear gestures generally depend upon one or more of the following approaches to processing local mark feature sets:
derivation of correlation factors from scalar multiplication of vectors representing stroke path segments that are then compared with stored scalar products of template configurations;
isolation of geographical features such as lagoons (closed areas) and bays (open areas) along with directional mark features such as loops, arcs or straight segments found among clustered line strokes that are compared with stored template features;
circumnavigation of the peripheries of a cluster, comparing parameters of height, width, perimeter, area, and waveform with those of stored templates;
manipulation, normalization, and comparison of pen strokes with stored template gesture prototypes; and
classification of shapes by first discerning features such as blockiness, symmetry, convexity, and count of edge-breakthroughs and then calculating by linear transform a parameterized shape class value.
Whether a computer interface is based on entering text by keyboard, pointing and clicking icons with a mouse, or marking a touch sensitive surface with a stylus, there are a number of disadvantages inherent in any comparative control system based upon a template repertoire of local mark features:
Effectiveness of discrimination and matching among candidates is an inverse function of the ambiguity of feature set articulation. The efficiency of any method based on feature matching decreases as the reference repertoire increases in size and variability of its members.
Characterizations of non-textual configurations depend upon formal definitions of geometric features and are difficult to categorize and rank if they vary much from simple geometric figures.
Storing, searching, comparing, and retrieving items of large glyph databases are typically slow and computationally expensive.
Current feature matching methods are not easily extensible to new feature sets, thereby discouraging use of glyph structure sets to provide user customized computing device interfaces.
A list of prior patents currently known to applicant in c
Au Amelia
Dastouri Mehrdad
Pugh C. Emmett
Pugh/Associates, Patent & Trademark Attorneys
LandOfFree
Method and apparatus for sorting and comparing linear... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for sorting and comparing linear..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for sorting and comparing linear... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2593229