A Healthy Revolution		Table of contents		Indexes		XML Query Language (XQL)

Case Study: Boeing Intelligent Graphics for Airplane Operations and Maintenance

Molly L. Robinson

Associate Technical Fellow

The Boeing Company Box 3707 MS 7L-40
Seattle Washington 98124 USA
Email: mollyr@redwood.rt.cs.boeing.com

Biographical notice:

Molly Robinson is part of a team that is researching large-scale airplane maintenance systems. The maintenance systems integrate leading edge electronic capabilities such as: intelligent graphics, intelligent navigation, multimedia and visualization. Her specific areas of expertise include: intelligent graphics recognition, digital data delivery, object-oriented programming and the Standard Generalized Markup Language.

Molly is currently working with Boeing Commercial Airplane Group and the B52 and AWACS programs to develop production Intelligent Graphic systems for deployment in 1999. She is also leading a software project that is building an internet based retrieval system for airplane part and engineering data.

Lawrence S. Baum

Associate Technical Fellow

The Boeing Company Box 3707 MS 7L-44
Seattle Washington 98124 USA
Email: lbaum@redwood.rt.cs.boeing.com

Biographical notice:

Larry Baum's current research involves the development of image recognition technology for converting wiring diagrams, schematics and other engineering drawings into intelligent graphics. He is part of a team developing large-scale airplane information systems, leading to products such as Boeing's Portable Maintenance Aid.

His specialties include intelligent graphics, structured authoring systems, digital data delivery, and distributed artificial intelligence. Larry was the system architect for the Boeing Standards Knowledge and Delivery System, a structured authoring system for Boeing's electrical standards documents. He has published numerous book chapters, journal articles, conference papers, and technical reports.

John H. Boose

Technical Fellow

The Boeing Company Box 3707 MS 7L-44
Seattle Washington 98124 USA
Email: john@redwood.rt.cs.boeing.com

Biographical notice:

John Boose's current work includes projects to acquire knowledge from vector and raster engineering drawings and other airplane documentation using knowledge-based and image processing techniques. He is part of a team that has built a hyper-linked airplane manual system that contains more than four million pages. The results appear in Boeing digital data products such as the Portable Maintenance Aid.

His specialties include knowledge acquisition (from both human experts and graphics), intelligent graphics, digital delivery of Boeing airplane and engineering information, knowledge-based systems, group decision support, and corporate knowledge capture and reuse. John introduced new knowledge acquisition technology that reduces the development and delivery time of knowledge-based systems. These tools contributed to systems used in Boeing and NASA. He contributed to NASA's Design Knowledge Capture Technical Plan for the space station. He has published over 160 book chapters, journal articles, conference papers, and technical reports, including a monograph on knowledge acquisition.

David B. Shema

Associate Technical Fellow

The Boeing Company Box 3707 MS 7L-44
Seattle Washington 98124 USA
Email: dshema@redwood.rt.cs.boeing.com

Biographical notice:

Dave Shema is currently working in the areas of raster and vector graphics symbol recognition as applied to acquiring knowledge from engineering drawings. He is also involved in the production of SGML and XML autotaggers for graphics and for text, with an interest in Quality Checking tools that are built into the autotaggers. Results appear in a number of Boeing digital data products, including the Portable Maintenance Aid and military Interactive Electronic Technical Manuals (IETMs). Dave has written a number of articles and papers on knowledge Acquisition and graphics recognition.

Susan C. Chew

Advanced Computing Technologist

The Boeing Company Box 3707 MS 7L-44
Seattle Washington 98124 USA
Email: schew@redwood.rt.cs.boeing.com

Biographical notice:

Susan Chew is part of the team that is developing an internet-based retrieve system for airplane part and engineering data. She is doing work with intelligent graphics and with the databases behind the graphics. She is knowledgeable on SGML and DTD development, having built tools to automatically generate autotagger programs. Susan's work is being applied to Boeing's digital data products, both on the commercial and military side.

Introduction

The Boeing Company maintains tens of millions of pages of information associated with the manufacture and delivery of its products. Much of this information must be made available electronically. We have developed tools to automatically convert and integrate electronic data into industry standard formats. Some of the technical challenges include

handling a wide variety of source formats,
making sure that the tools scale up to handle millions of pages of information, and
adding functionality to graphics.

Our system contains over four million pages of text including tens of thousands of graphics.

In this paper we describe tools that recognize and use information within airplane-related vector and raster images. Such images include troubleshooting charts, fault reporting diagrams, component location diagrams, component index tables, wiring diagrams, system schematics, parts illustrations, standards tables, and structural and tooling drawings. Each airplane requires conversion of over 20,000 graphics, including over 900,000 pieces of cross-referenced information. We are also exploring visual information retrieval strategies, including content-based and similarity-based methods for both vector and raster graphics.

Four Million Pages and Growing

The Boeing Company is committed to Air Transport Association Specification 2100 [1] which requires the use of the Standard Generalized Markup Language (SGML) [2]. To comply with these specifications Boeing has converted millions of document pages to SGML. Document sources include commercial tools (e.g., Microsoft Word, InterLeaf, FrameMaker), internal proprietary tools, and data from external vendors.

Our team built a series of text autotaggers that automatically convert documents into SGML. From 1990 to the present, we developed autotaggers to create a testbed hypermedia system containing data from over four million pages.

Graphic Navigation and Functionality

The autotaggers receive text in various formats. They receive graphics in vector formats (usually CGM) and raster formats (usually TIFF) and originally did little more than pass the graphics to viewers in DynaText. The graphics lacked information for navigation and retrieval. Users often needed to examine many images to find the right one, including multiple panning and zooming operations. Hyperlinking from a text reference in a graphic was not possible, nor was full text search. The graphics also lacked useful functional information -- What is the logic in this troubleshooting diagram? What are the relationships between items in this table? What lines in this wiring diagram represent continuous circuits?

We built a series of graphic recognition tools that use vector and raster graphics to produce navigational and functional information represented in SGML. We then integrated this information into the testbed.

Because each recognizer is unique and depends upon knowledge about how the diagrams are constructed and the constraints they should comply with, each involves algorithms specific to that class of drawings. Thus, the algorithms themselves are not generalizable. However, the methodology has proven successful over a large variety of drawing classes. As a result, we have enabled mechanics and other users of the data to quickly and accurately navigate through and more easily access the technical information embedded in the tens of thousands of illustrations in an on-line document set.

For example, suppose that there is a problem in the air conditioning system in the crew rest area of a 757. The mechanic uses the system to go directly from the fault code for that problem to the fault isolation procedure in the Fault Isolation Manual, via a text hyperlink. The procedure references a four-sheet figure containing a fault isolation decision tree. By clicking on hotspots in the graphic, he quickly gets to the corrective action, which is a removal and installation procedure in the Airplane Maintenance Manual. There is a hotspot on that reference, so he quickly navigates to the correct location in the Maintenance Manual. The procedure requires inspection of a wiring diagram, found in the Wiring Diagram Manual. There is a hyperlink in the Maintenance Manual which takes the mechanic to the correct diagram. Because the graphic viewer traces electrical circuits in the diagram, the mechanic can readily determine the affected components and the associated pin numbers so that removal/installation is done properly. The desired component is not in stock, however, so the mechanic needs to consult the Illustrated Parts Catalog. The component number in the wiring diagram also has a hotspot, so he can go directly from the Wiring Diagram Manual to the desired location in the Illustrated Parts Catalog. The illustrations there are also populated with hotspots so that the mechanic can easily pull up the information as to part number and supplier, so that the part can be obtained as quickly as possible.

This scenario illustrates the enormous benefit of using graphic recognition tools to automatically populate our large data sets with the hundreds of thousands of hotspots. Typically the graphics alone from a single set of manuals contain over 900,000 reference links.

Graphics Recognition Tools

Figure 1. The fault diagram recognizer finds arrows, diamonds, and other information, then uses knowledge about diagram layout to produce the application's flow of logic.

Figure 2. The component location recognizer uses page layout logic to induce groups and attach callouts.

We used a similar approach for each graphic recognition problem:

Develop a tool to reason about vector or raster graphics.
Tune and evaluate the tool for accuracy and the ability to scale up.
Integrate acquired graphic information with text in the testbed.
Evaluate the usability of the results.
Transfer the results to products and services.

Fault reporting diagrams are vector images that pilots use to determine what messages to record in the flight logbook when a malfunction occurs. We have been able to accurately determine the decision networks in these diagrams and generate over 20,000 hot spots in over 1,600 diagrams (Figure 1). To illustrate our methodology, we will discuss the processing of these drawings.

The 2 diagrams in our example are very different so we construct an individual recognizer for each class of drawing we analyze, using heuristic knowledge of how that particular class is constructed. Thus the recognizer for fault reporting diagrams is a different application than that for component location diagrams (Figure 2.) To illustrate our approach, we will outline the basic steps in the recognition of fault reporting diagrams.

Each diagram consists of header art, below which is a series of questions. Beneath each question are the various responses for that question. These answers are connected through a series of horizontal arrows and decision diamonds to comprise a decision tree. A path through the diagram will ultimately lead to a fault code which should be entered in the flight logbook.

We exploit the power of SGML by developing a Document Type Definition (DTD) which reflects the intelligence we are recognizing in the graphics. Because fault reporting diagrams are graphical decision trees, the DTD specifies objects such as decisions, questions, and choices; and since the goal is to enable interactive use of the illustrations, the DTD also specifies hotspots:

Figure 3. Intelligent Graphics DTD

Each decision is linked to the question above it via qid and consists of one or more choices. Each choice links (via refoid) to another decision or an action. All of these have a set of hotspots (i.e. an hslist). Typically an hslist will have a single hotspot in it but occasionally there is a need for multiple disconnected regions for a decision, choice or action. Hence the need for the hslist element.

For the Fault Diagram in Figure 1, the resulting markup includes:

Figure 4. Intelligent Graphics Markup

The recognizer's task, then, is to analyze the graphical primitives in the CGM file to produce such markup. It performs these steps in building a complete and accurate internal representation of the decision tree:

Recognize column separation. Find the vertical dashed lines that partition the drawing. Not all vertical dashed lines are column separators, so we apply heuristics to filter those out: column separators must be of sufficient length and there must be sufficient space between columns.

Recognize decision diamonds and all arrows and their horizontal and vertical shafts. There are no "arrowhead" elements; rather arrowheads are built out of individual line segments that are close enough together, so that when the drawing is printed, the ink will produce a solid arrowhead. In fact, the drawings we analyze have no graphical elements in them other than line segments and text fragments. The recognizer knows the patterns of line segments for arrows and decision diamonds. Significant error handling is needed to detect arrows that deviate from the general case and to filter out objects that erroneously appear to be arrows. The recognizer must then determine from which column an arrow emanates. Thus it follows the individual line segments back from the arrowheads until encountering a vertical shaft line.

Classify text. We analyze individual text fragments to determine if they are pieces of questions, pieces of responses to questions, fault codes, or extraneous to the decision tree. We concatenate question fragments into complete questions and response fragments into coherent responses. This heuristic analysis is non-trivial, since answer fragments can be arbitrarily close to questions and similarly aligned.

Attach response text to arrows. Typically the response that is associated with an arrow lies directly above it, but this is not always the case. Occasionally a response will vertically straddle an arrow (one fragment of the response will be above the arrow, another will be below.) The recognizer must reason about the distributions of interline spacing throughout the diagram to make the correct decisions.

Build the internal decision tree. Starting with the left-most decision diamond, the recognizer follows the arrows to build an acyclic directed graph corresponding to the arrows and diamonds on the drawing. There should be a one-to-one correspondence between terminal nodes in the graph and the fault codes. Because there are occasionally missing arrows due to authoring errors, the recognizer must induce them to build a complete tree. This is typical of the extensive error-correction the recognizer must perform in order to achieve scalability to the large data sets we process.

Using this recognizer, we are able to convert a complete set of drawings for a Fault Reporting Manual into different styles of interactive electronic books. For example, using one style, the system presents the user with each question on a separate screen and, depending on the response, will present the next set of question and responses in the decision tree. Another presents the original graphic with hot spots that are automatically generated. The user can click on the appropriate response and the system will automatically zoom in on the next question/response area.

By devising additional heuristics and recognition algorithms, we have adapted this methodology for many other drawing classes.

Fault trees are vector drawings that provide mechanics with decision trees for fault isolation. One drawing can consist of as many as 30 individual sheets with intersheet connections linked by references. Our software analyzes the layout of the boxes and the arrows connecting them and builds an internal representation of the decision tree. It then generates hot spots so that users can easily navigate within a sheet and among sheets as well as follow links to other information. This manual set contains over 750 charts containing over 16,000 hot spots.

Component location diagrams provide exploded views of aircraft and their components. Typically one diagram consists of multiple sheets, each of which has one or more subpictures (insets) with internal callout references. Our software must reliably subdivide each image into subpictures and generate the hot spots that link the callouts to the correct subpicture, including references to other sheets. In addition, the software generates hot spots around each equipment number, so that mechanics can easily navigate from the picture to information about that piece of equipment. This manual set contains over 650 vector component location diagrams; the system produced over 3200 subpictures containing over 25,000 hot spots (Figure 2).

(This recognizer also populates a graphics database with all the subpictures. This database provides the testbed for the visual information retrieval research mentioned at the end of this paper.)

Component index tables are vector drawings that tell the mechanic where to go to find the maintenance procedures for the equipment illustrated in the component location drawings. The index table recognizer determines the individual table cells and relationships among cell contents. It generates over 14,000 hot spots in over 300 tables linking the drawings to component location diagrams, other component index tables and to maintenance procedures.

Wiring diagrams are vector drawings extracted from computer-aided design data sets. The intelligent graphics software analyzes both the vector image and the data set to determine how wires are laid out in the drawings so that circuit tracing is enabled in the hypermedia viewer. In addition, there are hot spots providing hyperlinks to equipment lists and wire lists as well as other diagrams. This manual set contains over 1400 diagrams with over 135,000 hot spots (Figures 3, 4).

Figure 5. A wiring diagram recognizer finds connected circuits and links references together.

Figure 6. Users follow hotlinks to retrieve equipment information.

System Schematics are similar in functionality and recognition requirements to wiring diagrams. This manual set contains over 1300 system schematics with over 461,000 hot spots.

Parts illustrations are raster images that provide exploded views of the airplane much like component location diagrams. They contain callouts and item numbers that must be linked to other pages. Because they are raster images we must perform more complex analysis than with the vector images. We have developed routines to quickly process callouts and item numbers with high accuracy. This manual set contains over 13,000 sheets with more than 241,000 hot spots (Figure 7).

Figure 7. A raster parts illustration recognizer finds callouts and reference numbers, using symbol finding and optical character recognition.

Standards tables contain information about Boeing engineering practices. The sources for many of these tables are paper copies that were several generations old, made with typewriters and ruled with ball point pens. The conversion team scanned these images for on-line use and was planning to manually re-enter the information. We developed recognition software to extract the logic in the tables. Together with a commercial optical character recognition package we automatically converted over 6600 tables to InterLeaf format (Figures 8, 9). Later these will also be converted to SGML.

Figure 8. This original standards table was made using a typewriter and ball-point pen.

Figure 9. After scanning the table in Figure 8, the table recognizer automatically finds cells, performs character recognition, then produces standard mark-up files.

Evaluating Recognition Results

To evaluate the results of text tagging our team used commercial SGML verifiers and specialized custom systems. We developed tools that analyze the text output for consistency and completeness, including statistical measures and link verification. Often these tools find authoring errors as well as tagging errors.

Figure 10. Custom graphics analysis tool.

It is more difficult to build such tools to check graphic recognition accuracy. We built a custom graphic analysis tool that simultaneously shows recognized objects and the corresponding SGML (Figure 8). For example, if the recognizer finds a reference, the viewer displays the hot spot along with the information as to what type of reference it is and to what it refers. Using this viewer we manually sampled thousands of images to assess recognition accuracy. Recognition accuracy ranged from about 97% for component location graphics to 99.9% for troubleshooting charts. These results exceeded our performance goals.

We can also find some types of graphics authoring errors. For example we can automatically detect incorrect references that point to non-existent locations. Previously, such errors could only be found by manual inspection.

Future Challenges - Work in Progress

We are currently working with Boeing's library of millions of structural and tooling raster drawings. These drawings have been scanned from aperture cards and placed on-line. We would like to recognize objects such as title blocks, part numbers, dimension lines, materials lists, and parts tables. Much of the text is hand written and many of the scanned images are skewed or noisy, making this work very challenging (Figure 11).

Figure 11. Legacy raster structural and tooling drawings

We are also working on visual information retrieval strategies, including content-based and similarity-based methods (Figure 12). Our prototype visual search engine finds similar vector images in a database of over 6,000 drawings.

Figure 12. Visual Information Retrieval

Summary

We have successfully added functionality to tens of thousands of vector and raster graphics, integrating them with text in on-line navigation systems, addressing the problems of scale and accuracy. We hope to continue to add functionality to graphics to enhance the overall utility of Boeing's digital data.

References

[1] ATA (1995). Air Transport Association Specification 2100 - Digital Data Standards for Aircraft Support, 1995, Order code A090

[2] Goldfarb, Charles F. (1990). The SGML Handbook, Oxford University Press, ISBN 0-19-853737-9


A Healthy Revolution		Table of contents		Indexes		XML Query Language (XQL)