`
`This was produced from a copy of a document sent to us for microfilming. While the
`most advanced technological means to photograph and reproduce this document
`have been used, the quality is heavily dependent upon the quality of the material
`submitted.
`
`The following explanation of techniques is provided to help you understand
`markings or notations which may appear on this reproduction.
`
`1. The sign or "target" for pages apparently lacking from the document
`photographed is "Missing Page(s)". If it was possible to obtain the missing
`page(s) or section, they are spliced into the film along with adjacent pages.
`This may have necessitated cutting through an image and duplicating
`adjacent pages to assure you of complete continuity.
`
`2. When an image on the film is obliterated with a round black mark it is an
`indication that the film inspector noticed either blurred copy because of
`movement during exposure, or duplicate copy. Unless we meant to delete
`copyrighted materials that should not have been filmed, you will find a
`good image of the page in the adjacent frame.
`
`3. When a map, drawing or chart, etc., is part of the material being photo(cid:173)
`graphed the photographer has followed a definite method in "sectioning"
`the material. It is customary to begin filming at the upper left hand corner
`of a large sheet and to continue from left to right in equal sections with
`small overlaps. If necessary, sectioning is continued again-beginning
`below the first row and continuing on until complete.
`
`4. For any illustrations
`that cannot be reproduced satisfactorily by
`xerography, photographic prints can be purchased at additional cost and
`tipped into your xerographic copy. Requests can be made to our
`Dissertations Customer Services Department.
`
`S. Some pages in any document may have indistinct print. In all cases we
`have filmed the best available copy.
`
`Universitv
`Micr6films
`International
`
`31JO N. ZEEB ROAD, ANN ARBOR. Ml 48106
`18 BEDFORD ROW, LONDON WC1 A 4EJ. ENGLAND
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`Page 1 of 117
`
`SAMSUNG EXHIBIT 1006
`Samsung v. Image Processing Techs.
`
`
`
`790947?.
`
`NEW MEXICO STATE UNIVERSITY, PH.O., 1971
`
`Unil.€r.;j(y
`I~
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 2 of 117
`
`
`
`REAL-TIME VIDEO FILTERING
`
`WITH
`
`BIT-SLICE MICROPROGRAMMABLE PROCESSORS
`
`BY
`
`ROBERT BARCLAY ROGERS, B. S. , M. S.
`
`A Dissertation submitted to the Graduate School
`
`in partial fulfillment of the requirements
`
`for the Degree
`
`Doctor of Philosophy
`
`Major Subject: Electrical Engineering
`
`Related Areas: Physics and Computer Science
`
`New Mexico State University
`
`Las Cruces, New Mexico
`
`December 1978
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 3 of 117
`
`
`
`STATEMENT BY AUTHOR
`
`This dissertation has been submitted in partial fulfillment
`of requirements for an advanced degree at New Mexico State Univer(cid:173)
`sity and is deposited in the University Library to be made available
`to borrowers under rules of the Library.
`
`Brief quotations from this dissertation are allowable without
`special permission, provided that accurate acknowledgement of source
`is made. Requests for permission fa?: extended quotation from or
`reproduction of this manuscript in whole or in part may be granted
`by the head of the major department or the Dean of the Graduate
`College when in his judgement the proposed use of the material is in
`the interests of scholarship.
`In all other instances, however,
`permission must be obtained from the author.
`
`SIGNED: ~-ffi?~
`
`i i
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 4 of 117
`
`
`
`1'Real-Time Video Filtering with Bit-Slice Microprogrammable
`
`Processors, 11 a dissertation prepared by Robert Barclay Rogers
`
`in partial fulfillment of the requirements for the degree,
`
`Doctor of Philosophy, has been approved and accepted by the
`
`Dean of the Graduate School
`
`Date
`
`Committee in Charge:
`
`Dr. Gerald M. Flachs, Chairman
`
`Dr. Frank F. Carden
`
`Dr. Javin M. Taylor
`
`Dr. Wiley E. Thompson
`
`Dr, Alan van Heuvelen
`
`Dr. Thomas Puckett
`
`iii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 5 of 117
`
`
`
`ACKNOWLEDGEMENTS
`
`I wish to acknowledge the work of Dr. Ivan Perez-Mendez and
`
`Mr, Steven J. Szymanski, who designed and implemented the bit(cid:173)
`
`slice microprocessor systems and the associated interfaces and
`
`control software, and who offered invaluable assistance in the
`
`implementation and debugging of the video filtering module.
`
`A special vote of thanks goes to my advisor Dr. Gerald M.
`
`Flachs, whose views on hardware implementations and image(cid:173)
`
`processing algorithms were instrumental in guiding my research.
`
`His endless encouragement and assistance during the long and
`
`tedious hours of system verification and testing are most
`
`appreciated.
`
`This research was funded by the Army Research Office and
`
`White Sands Missile Range under contracts DAAD-76-C-0024 and DAAD-
`
`77-C-0046. Much of the material contained herein has been pre(cid:173)
`
`viously published in reports pertaining to those contracts.
`
`In addition, thanks are due to the New Mexico State University
`
`Computer Center for the use of their facilities, and to Mr. John
`
`Vieira of Academic Computer Services for his assistance during the
`
`development of the microcode assembler.
`
`iv
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 6 of 117
`
`
`
`VITA
`
`April 13, 1953 -- Born at China Lake, California
`
`1973 -- B.S. with Highest Honors, Physics, New Mexico Institute
`of Mining and Technology, Socorro, New Mexico
`
`1976 -- M.S.E.E., New Mexico State University, Las Cruces, New
`Mexico
`
`'PROFESSIONAL SOCIETIES
`
`American Geophysical Union
`
`Institute of Electrical and Electronic Engineers
`
`I.E.E.E. Computer Society
`
`PUBLICATIONS
`
`1974 Holmes, C.R., Moore, C. B., Rogers, R., and Szymanski, E.,
`"Radar Study of Precipitation Development in Thunderclouds,"
`Fifth International Conference on Atmospheric Electricity,
`Garmisch-Partenkirchen, Germany, September 1974.
`
`1975 Gutjahr, A. I.., Holmes, C. R., and Rogers, R. B., 11Cross(cid:173)
`Spectral Properties of Thunder," Proceedings of the San
`Francisco Conference of the American Geophysical Union,
`December 1975.
`
`1976 Rogers, R. B., "Algorithm for Computation of Binary Pro(cid:173)
`jections and a Proposed Microprogram-Controlled Implemen(cid:173)
`tation," Research Project Internal Report, New Mexico State
`University, under White Sands Missile Range contract DAAD07-
`76-C-0024, September 1976.
`
`1977
`
`1977
`
`Flachs, G. M., Thompson, W. E., Black, R. J., Taylor, J.M.,
`Cannon, W., Rogers, R., and U, Yee Hsun, 11A Pre-Prototype
`Real-Time Video Tracking System, 11 Final Report for contract
`DAAD07-76-C-0024, submitted to White Sands Missile Range,
`January 1977.
`
`Rogers, R. B., "Specifications for a Two-Pass Symbolic
`Assembler Generating Absolute Microcode for Arbitrary
`Microprogram Control Store Architectures," Interim Report,
`White Sands Missile Range contract DAAD07-76-C-0024, April
`1977.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 7 of 117
`
`
`
`1977 Rogers, R. B., "A Microprogrammed Implementation of the
`Projection Computation Module Using the 3002 Bit-Slice
`Microprocessor," Research Project Internal Report, New
`Mexico State University, under White Sands Missile Range
`contract DAAD07-76-C0024, April 1977.
`
`1977
`
`1977
`
`Flachs, G. M., Thompson, W. E., Black, R. J., Taylor, J.M.,
`Cannon, W., Rogers, R., and U, Yee Hsun, "An Automatic
`Video Tracking System," Proceedings of the 1977 National
`Aerospace and Electronics Conference (NAECON
`'77) , Dayton,
`Ohio, May 1977
`
`Flachs, G. M. , Thompson, W. E. , Cannon, W. , Rogers 1 R. ,
`Perez, I. , and Kitchell, J. , "Mathematical Modeling and
`Simulation in a Programmed Design Methodology," Proceedings
`of the First International Conference on Mathematical
`Modeling, St. Louis, Missouri, 29 August - 1 September 1977.
`
`1977 Rogers, R., "Program Logic and Input Data Formats for an
`Optimizing String-Generating Wiring Program," Interim
`Report for White Sands Missile Range contract DAMJ07-77-
`C0046, December 1977.
`
`1977 Rogers, R. B., 11Translation of a Control Process Algorithm
`into a Hardware/Firmware Realization," presented at the
`Real-Time Video Tracking Symposium, White Sands Missile
`Range, January 1977
`
`1978
`
`1978
`
`Flachs, G. M., Perez, P. I., Rogers, R. B., Szymanski, S. J.,
`Taylor, J. M., and U, Yee Hsun, "A Real-Time Video Tracking
`System, 11 Annual Report for White Sands Missile Range contract
`DAAD07-77-C0046, January 1978.
`
`Flachs, G. M., Perez, P. I., Rogers, R. B., Szymanski, S. J.,
`Taylor, J.M., Thompson, W. E., and U, Yee Hsun, 11Real-Time
`Video Tracking Concepts," Interim Technical Report for Grant
`DAAD-29-76-G-0231, u. S. Army Research Office, Research
`Triangle Park, North Carolina, May 1978.
`
`1978 Rogers, R. B., Szymanski, S. J., Taylor, J. M., and Flachs,
`G. M., "A Tutorial on Distributed Processing using Micro(cid:173)
`programmable Bit-Slice Microprocessors," National Computer
`Conference 1978, Personal Computing Digest, June· 1978.
`
`1978
`
`Perez, P. I., Flachs, G. M., and Rogers. R. B., "Video
`Processing with Microprogrammable Processors," Proceedings
`of the Army-sponsored Workshop on Microprocessors and
`Computer Graphics, July 1978.
`
`vi
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 8 of 117
`
`
`
`1978 Gilbert, A. L,, Giles, M, K., Flachs, G, M., Rogers, R. B.,
`and U, Yee Hsun,
`11A Real-Time Video Tracking System using
`Image Processing Techniques," Proceedings of the Fourth
`International Joint Conference on Pattern Recognition,
`November 1978.
`
`FIELDS OF STUDY
`
`Major Field: Electrical and Computer Engineering
`Real-time image processing, multiprocessing computer
`architectures, microprogram software support systems
`
`Minor Field: Physics and Computer Science
`Thunderstorm electrification and precipitation mechanisms,
`acoustic properties of thunder, real-time data acquisition
`software architectures.
`
`vii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 9 of 117
`
`
`
`ABSTRACT
`
`REAL-TIME VIDEO FILTERING
`
`WITH
`
`BIT-SLICE MICROPROGRAMMABLE PROCESSORS
`
`BY
`
`ROBERT BARCLAY ROGERS, B. S., M.S.
`
`Doctor of Philosophy
`
`in
`
`Electrical and Computer Engineering
`
`New Mexico State University
`
`Las Cruces, New Mexico, 1978
`
`Prof. Gerald M. Flachs, Chairman
`
`Bit-slice microprogrammable processors and algorithms are
`
`developed to perform high-speed reai-time video filtering of arbi(cid:173)
`
`trary scenes as part of a real-time videotheodolite system. Hard(cid:173)
`
`ware and software components are designed to perform intelligent
`
`image discrimination and predictive tracking functions.
`
`A tracking window concept is introduced as the basic image
`
`partitioning tool. Statistics are derived from the observed scene
`
`through histograms of pixel occurrence in the three regions of a
`
`tracking window and are subsequently used to derive thresholding
`
`and Bayesian pixel classification rules on a dynamic basis. A
`
`mathematical technique for calculating the ~ priori probability
`
`viii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 10 of 117
`
`
`
`density functions of superimposed opaque components of an arbitrary
`
`scene is presented.
`
`Digital equipment is designed to implement the data acquisition
`
`and control functions for video filtering applications. Statistics
`
`of the observed scerie are automatically accumulated by a hardware
`
`unit ~hich measures pixel intensity occurrence histograms in real(cid:173)
`
`time. Dynamic control of the tracking window's position and size
`
`are combined with a communications memory technique to implement
`
`the full video filtering system on a sixteen-bit microprogrammable
`
`bit-slice processor.
`
`Support software for the microprogrammable processor system
`
`includes a symbolic macro processor, a microinstruction assembler,
`
`an absolute loader, and telecommunications routines. The symbolic
`
`macro proces.sor provides macro-definition and recursive macro(cid:173)
`
`invocation with metasymbol definition and manipulation facilities
`
`which allow macro-level programming of many micro-level functions.
`
`A symbolic assembler generates absolute microcode for arbitrary
`
`microprogram control store architectures. Absolute loader and
`
`telecommunications routines link the macro-processing and assembly
`
`phases with an interactive microprocessor design and debugging
`
`facility.
`
`ix
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 11 of 117
`
`
`
`TABLE OF CONTENTS
`
`LIST OF TABLES.
`
`LIST OF FIGURES
`
`CHAPTER
`
`1.
`
`INTRODUCTION.
`
`• • • •
`
`, • • • • • •
`
`Video Tracking System Components.
`
`Hardware Considerations .
`
`.
`
`.
`
`The Feature Selection Problem
`
`2.
`
`ANALYTICAL TECHNIQUES
`
`Tracking Window •
`
`.
`
`Feature Histograms
`
`Learned Feature Histograms,
`
`Threshold Classifier.
`
`Image Partitioning.
`
`Bayesian Classifier
`
`3.
`
`HARDWARE ARCHITECTURE
`
`Microprogrammable Processor
`
`Histogram Accumulation Memory
`
`Region Definition Logic .
`
`.
`
`Data Acquisition and Timing
`
`Decision Memory
`
`.
`
`.
`
`.
`
`Communications Memory
`
`Page
`
`. xii
`
`.xiii
`
`10
`
`10
`
`14
`
`18
`
`19
`
`25
`
`29
`
`33
`
`33
`
`40
`
`44
`
`46
`
`52
`
`54
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 12 of 117
`
`
`
`4.
`
`SOFTWARE ARCHITECTURE
`
`Symbolic Assembler.
`
`Symbolic Macro Processor.
`
`System Support Components
`
`s.
`
`SUMMARY
`
`,
`
`SELECTED BIBLIOGRAPHY
`
`Page
`
`57
`
`61
`
`77
`
`87
`
`99
`
`101
`
`xi
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 13 of 117
`
`
`
`LIST OF TABLES
`
`Table
`
`8X02 Next-Address Functions.
`
`TCM Switch Options .
`
`• •
`
`.
`
`.
`
`Page
`
`39
`
`95
`
`xii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 14 of 117
`
`
`
`LIST OF FIGURES
`
`Figure
`
`Tracking Window.
`
`Typical Tracking Window Configuration.
`
`Hypothetical Scene with Tracking Window,
`
`Example of Thresholding Classification Rule.
`
`VP Block Diagram • • • • • • •
`
`74S481 Processor Architecture.
`
`Microinstruction Format.
`
`.
`
`.
`
`.
`
`Histogram Accumulation Memory.
`
`HAM Timing Oiagrcim
`
`RDL Signals •
`
`Sync Stripper Output Signals
`
`Horizontal Timing.
`
`Vertical Retrace Timing.
`
`Pixel Clock Timing
`
`Decision Memory.
`
`Communications Memory.
`
`Microprogram· Design Flow
`
`Microprogram Example
`
`TCM Transfer File.
`
`10
`
`11
`
`12
`
`13
`
`14
`
`15
`
`16
`
`17
`
`18
`
`19
`
`Page
`
`12
`
`15
`
`21
`
`24
`
`34
`
`36
`
`37
`
`42
`
`43
`
`45
`
`48
`
`50
`
`50
`
`51
`
`53
`
`55
`
`62
`
`86
`
`96
`
`xiii
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 15 of 117
`
`
`
`I. INTRODUCTION
`
`The focus of this dissertation is the implementation of the
`
`video filtering functions of a real-time video tracking system
`
`utilizing microprogrammable bit-slice processors. This research
`
`was carried out in parallel with several other investigators as
`
`part of a Real-Time Videotheodolite research program at New
`
`Mexico State University [l] with funding provided by the Depart(cid:173)
`
`ment of the Army through the Army Research Office and White Sands
`
`Missile Range.
`
`Recent developments in the field of digital electronics have
`
`pushed digital data processing speeds up towards the video range,
`
`so that it is not impractical to consider real-time digital manipu(cid:173)
`
`lation of signals whose bit-serial rates are in the hundred-mega(cid:173)
`
`cycle range. The wide use of commercial television equipment led
`
`immediately to the concept of real-time image processing via tele(cid:173)
`
`vision observation. Practical and mathematical limitations required
`
`the use of standard video equipment without enhanced dynamic range
`
`or bandwidth. The digital processing equipment and associated
`
`algorithms that were designed and implemented in this research
`
`effort interface directly with standard video equipment and realize
`
`a bit-serial data rate of approximately 83 megabits per second with
`
`a five-megahertz video bandwidth and a field rate of sixty fields
`
`per second.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 16 of 117
`
`
`
`Video Tracking System Components
`
`There are four main problems to be solved in the implementa(cid:173)
`
`tion of a closed-loop real-time video tracking system as formulated
`
`by Flachs et al. [lJ. Following the flow of video data in the sys(cid:173)
`
`tem, they are video filtering, parameter extraction, structural
`
`analysis, and control processing. All four stages suffer to some
`
`degree from the high data rates and large quantities of data to be
`
`processed in typical video applications.
`
`The video filtering problem is one of image partitioning, in
`
`which an arbitrary scene must be analyzed to decide which elements
`
`of the scene are of interest to the remaining stages in the tracking
`
`system. The anal~sis may use statistical or other techinques to
`
`determine which picture elements (or 11 pixels 11 )
`
`in the scene are
`
`interesting, but, in any case, the classification must be performed
`
`rapidly.
`
`The parameter extraction stage is concerned with reducing the
`
`dimensionality of the incoming data to a level that is tractable,
`
`Based upon the digitally-filtered and pre-emphasized data from the
`
`video filtering module, the parameter extraction algorithm must
`
`compute a handful of vital parameters that contain sufficient in(cid:173)
`
`formation about the objects of interest in the scene to enable
`
`later stages to accurately locate and describe the objects in the
`
`scene. At the same time, the information conveyed
`
`(and ·therefore
`
`the number of parameters) must not be so exhaustive as to entail
`
`prohibitive processing overhead in later analysis.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 17 of 117
`
`
`
`The structure analysis module is the first module that is
`
`capable of intricate data processing functions, simply because it
`
`is the first module in the video data flow path that has a suffi(cid:173)
`
`ciently low data rate to allow in-depth analysis to be performed.
`
`(Typical data rates into the structure analysis module are one
`
`one-thousandth of the original input video's data rate.) The
`
`output from this module is a set of Cartesian coordinates of one
`
`or more objects (or "targets 1' ) along with the pointing angle of
`
`each object. An important auxiliary piece of data which must be
`
`associated with each object is a confidence weight. The purpose
`
`of the confidence weight is to give a quantitative estimate (per(cid:173)
`
`haps based upon qualitative heuristics) of the accuracy and relia(cid:173)
`
`bility of the measurements of the targets' locations and pointing
`
`angles, since the algorithms often do not lend themselves well
`
`to the calculation of statistical confidence parameters such as
`
`variances.
`
`The control processing module is responsible for controlling
`
`the feedback loop which uses the observed objects 1 location and
`
`heading information to generate control correction signals for the
`
`servomechanisms that point the television camera at the scene.
`
`Typical servomechanism controls provide for elevation 1 azimuth,
`
`image rotation, and "zoom" (image magnification) adjustments . . The
`
`control processor also keeps an up-to-date model of the objects 1
`
`dynamic behavior as measured by the tracking system and perhaps by
`
`external data sources (e.g., tracking radars, visual observations),
`
`and attempts to predict the locations of the objects in future
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 18 of 117
`
`
`
`video frames, so t-hat a loss of video track may be recovered from
`
`by extrapolating the targets' positions from the previously
`
`measured data.
`
`Hardware Considerations
`
`The video filtering problem requires the part:t.:.::i.oning of an
`
`arbitrary image based upon feature selection and identification.·
`
`The hardware and software algorithms are· required to separate tar(cid:173)
`
`get, plume, and background regions of a typical target scene by
`
`selecting a set of features which are in some sense optimal, and
`
`then classifying every pixel in the scene in one of the three
`
`categories (target, plume, and background).
`
`Optimality is difficult to define in this context, since the
`
`traditional mathematica.1 criteria of optimality (e.g., least(cid:173)
`
`squared error, minimum error rate, minimum angular tracking error)
`
`are complex functions of the tracking system and the target's
`
`dynamic behavior and are difficult to analyze. The choice of
`
`optimal tracking features is also affected by cost constraints,
`
`both in terms of the effective cost (to the trackability of the
`
`target) of misclassification errors and the economic cost of the
`
`system. Economic cost. limits the processing speed and the tech(cid:173)
`
`nology of the hardware implementation, which in turn limits the
`
`complexity of the image analysis algorithms which may be used.
`
`The functional needs of video filtering at high data rates
`
`place
`
`a severe constraint upon the type of data processing equip(cid:173)
`
`ment that may be employed. The input data rate of 83 megabits
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 19 of 117
`
`
`
`per second is realized by digitizing one eight-bit data word every
`
`96 nanoseconds, which is much faster than the typical instruction
`
`cycle time of commercial computers of reasonable cost, The lack
`
`of efficient input data paths for inserting real-time data into
`
`the arithmetic-logic unit (ALU) or memory data paths of most com(cid:173)
`
`puters slows the effective cycle time still further. Even imple(cid:173)
`
`menting the high-speed data acquisition functions (such as pixel
`
`statistic accumulation) in hardware does not give sufficient time
`
`for a standard computer to perform the real-time processing
`
`required by the algorithms.
`
`The solution is to use a bit-slice microprogrammable micro(cid:173)
`
`processor with a cycle time of approximately 200 nanoseconds. The
`
`bit-slice microprocessor concept has many advantages over the
`
`typical 11microprocessors 11 such· as the. Motorola 6800· and Intel 8000
`
`chips, Bit-slice processors are fabricaced as a vertical "slice"
`
`through the ALU and register sections of a computer and can be
`
`cascaded to obtain almost any word width (subject to speed limita(cid:173)
`
`tions due to carry propagation). Bit-slice processors are usually
`
`made with transistor-transistor logic (TTL) techniques that yield
`
`much faster operation than the 8080-type microprocessors (e.g.,
`
`130 nanoseconds versus 500 nanoseconds). The operating speed dif(cid:173)
`
`ferential is enhanced by the microprogramming technique used in
`
`the bit-slice systems, which bypasses the hard-wired or firmware
`
`emulation of a macro-level instruction set and allows the programmer
`
`to directly manipulate most of the registers, ALU functions, and
`
`data paths in the system. Most bit-slice processors have a multi-
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 20 of 117
`
`
`
`tude of input and output buses, which are useful in optimizing
`
`real-time data manipulations. For example, the ALU input buses
`
`may be externally accessable, so that a real-time data source
`
`can be fed directly into the ALU without having to be routed
`
`through a formal input port in the architecture.
`
`Another constraint on the system design is due to the experi(cid:173)
`
`mental nature of the video filtering algorithms. Although, in
`
`many instances, microprogramming has been shown to be much more
`
`efficient than macroprogramming (an argument for microprogramming
`
`the algorithms), it has also been found that hardwired control for
`
`computers is much more efficient than either macro- or micropro(cid:173)
`
`gramming [21. A sp~cial-purpose hardwired control and arithmetic(cid:173)
`
`logic unit would undoubtedly perform better than the microprogram(cid:173)
`
`med bit-slice system, put would be far more difficult to modify to
`
`accept new algorithms. Since the implementation effort was to be
`
`research-oriented rather than an exercise in design efficiency,
`
`microprogrammed software control of standard bit-slice micropro(cid:173)
`
`cessor components was chosen rather than hardwired control of
`
`special-purpose hardware units. Macro-level software was found to
`
`be impractical due to the large overhead of macro-instruction
`
`fetch and decode cycles, so the final system design employs·
`
`total microprogramming of all algorithms in a read-write program
`
`memory attached to a 16-bit microprogrammable bit-slice micro(cid:173)
`
`processor.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 21 of 117
`
`
`
`The Feature Selection Problem
`
`The performance of any video-filtering algorithm is highly
`
`dependent upon the set of features ·wliich are chosen "as the basis
`
`for image partitioning, Since a primary consideration in image
`
`processing is the reduction of noise in low signal-to-:--noise ratio
`
`situations, it was decided from the start to use statistical
`
`methods of analysis. A second consideration is rejection of back(cid:173)
`
`ground elements in a scene, which is essential when tra.cking
`
`objects against complex variegated backdrops.
`
`The most important statistic of a typical scene is the fre(cid:173)
`
`quency of occurrence of the pixel intensities (digitized values
`
`of the photon flux) in various parts of the picture. Economic
`
`considerations precluded the use of color television equipment
`
`which would have made possible a spectral breakdown of the scene
`
`in terms of color. Monochrome equipment having visual and infra(cid:173)
`
`red response was used instead, and simplified the data processing
`
`problem by reducing the dimensionality of the input data by repre(cid:173)
`
`senting the observed scene as a single function
`
`f(x,y)
`
`f S(x,y,f) R(f) df
`
`where S(x,y,f) is the brightness function of the scene and R(f) is
`
`the camera's spectral response.
`
`[In practice, S(x,y,f) is also
`
`convoluted with a spread function representing optical focus and
`
`internal "smearing 11 effects.] The raster scan of a television
`
`camera converts the above function to a single time-function which
`
`represents a "snapshot" of the scene and which c_an be digitized to
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 22 of 117
`
`
`
`generate a bit-serial representation of the scene at discrete time
`
`intervals.
`
`Another feature which contains significant information about
`.
`.
`the scene is. neighborhood. connectivity or texture. For .example,
`
`the individual squares of color on a checkerboard may be viewed as
`
`disjoint areas of differing colors, but may-.also be seen from a
`
`distance as a single entity, namely, a textured surface. Digital
`
`computation of various texture measures is a straightforward pro-
`
`cedure [3:115] when serial black.:..and-white video data are available,
`
`but economic constraints and lack of time prevented any such imple-
`
`mentation.
`
`It is likely that the addition of texture to the hard-
`
`ware and software algorithms developed in this research would
`
`greatly enhance the filtering capabilities of the system.
`
`Yet another feature which can be used is a linearity measure,
`
`which generates some quantitative estimate of the degree of linear-
`
`ity of a picture. This feature is closely related to edge-detec-
`
`tion techniques [3]. which seek to delineate the boundary of an
`
`obj~ct by detecting the object's edges on the basis of pixel in ten-
`
`sity changes. Unfortunately, edge-detection techniques tend to
`
`be highly sensitive to noise in the picture unless combined with
`
`statistical pre-averaging, median, or thresholding methods, since
`
`edge detection usually requires taking spatial derivatives of the
`
`pixel intensity field in the scene.
`
`The algorithms developed herein use only the pixel intensity
`
`feature of the video picture. This feature is represented by video
`
`data which are generated as approximately one million bits per
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 23 of 117
`
`
`
`vieleo field and which must be processed in one-sixtieth of a second.
`
`The video filtering hardware and software reduce the effective data
`
`rate by a factor of ten by applying statistical histogram methods
`
`to determine the typical pixel intensity distributions in the
`
`scene and then classifying the pixels as being in "don't care"
`
`in "interesting" categories, That part of the scene which is to
`
`be analyzed is defined by the hardware via a "tracking window",
`
`which encloses the general area of interest in the scene and pro(cid:173)
`
`vides additional background clutter rejection.
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 24 of 117
`
`
`
`II. ANALYTICAL TECHNIQUES
`
`10
`
`Real-time video filtering is concerned with the separation
`
`of a target image from the background scene at standard 'video
`
`data rates. The scene in the field-of-view (FOV) of the tele-
`
`vision camera is digitized to form an n-by-m matrix representa-
`
`tion of the pixture P as
`
`p
`
`"
`
`i
`
`== 1, 2'
`
`. n,
`
`j = 1, 2, . . . m,
`
`where pij represents the pixel intensity at the point (i,j). As
`
`the television camera scans the scene, the video is digitized at
`
`m equally-spaced points in time, corresponding to equidistant
`
`points on the horizontal scan of the camera. During each video
`
`field there are n horizontal scans which generate an n-by-m
`
`discrete matrix representation at sixty f~eldS per second. A
`
`resolution m=512 pixels per line results in a pixel rate of
`
`approximately 96 nanoseconds per pixel, and is suitable (by
`
`Nyquist's Theorem· [4:279]) for digitizing a signal which is band-
`
`limited at five megahertz. The video-filtering hardware and soft-
`
`ware receive the digitized video, statistically analyze the target,
`
`plume, and background pixel intensity distributions, and decide
`
`whether a given pixel is to be classified as a part of the target,
`
`the plume, or the background.
`
`Tracking Window
`
`The basic assumption of this video-filtering method is that
`
`the target and plume images have some video intensities not con-
`
`Reproduced with permission of the copyright owner. Further reproduction prohibited without permission.
`
`SAMSUNG EXHIBIT 1006
`Page 25 of 117
`
`
`
`11
`
`tained in the immediate background. A "tracking window" is placed
`
`around the target image, as shown in Figure 1, to sample the back(cid:173)
`
`ground intensities immediately adjacent to the target image. The
`
`window frame is partitioned into two regions, denoted by BR and
`
`PR in the figure. Region BR is used to provide a sample of the
`
`pixel intensities that are contained in the background part of the
`
`scene, and region PR is used to sample the pixel intensities that
`
`thn plume of the target contains.
`
`The window frame is partitioned as above to accomodate the
`
`expected targets, ~hich w~re assumed to be airborne missiles (or
`
`airplanes) that might be expected to have a noticable plume. This
`
`consideration is particularly important