EXHIBIT 1065
`
`S. HASAN, “A CCD based Image Perception Sensor for Mobile Robots,”
`
`Final Report: U. of Florida Dept. of EE, 1006, 1995: VVL-1070 Evaluation Kit
`
`(1995)
`
`TRW Automotive U.S. LLC: EXHIBIT 1065
`PETITION FOR INTER PARTES REVIEW
`OF U.S. PATENT NUMBER 8,599,001
`IPR2015-00436
`
`

`
`University of FloridaDepartment of Electrical EngineeringEEL 5934Intelligent Machine Design LaboratoryA CCD based Image Perception Sensor for Mobile RobotsSyed Raza Hasan
`
`1065-001
`
`

`
`TABLE OF CONTENTS
`
`TABLE OF CONTENTS .......................................................................................................... ..2
`
`TABLE OF FIGURES .............................................................................................................. ..3
`
`ABSTRACT.............................................................................................................................. ..4
`
`INTRODUCTION ..................................................................................................................... ..5
`
`A CCD BASED IMAGE PERCEPTION SENSOR FOR MOBILE ROBOTS ........................... ..6
`
`1.1 System Overview .............................................................................................................. ..6
`1.1.1 Control Computer ...................................................................................................... ..6
`1.1.2 Vision ........................................................................................................................ ..7
`1.1.3 CCD—Controller Interface ........................................................................................... ..7
`1.1.4 Circuit Schemetics ..................................................................................................... ..8
`
`1.1.5 Mobile platform ......................................................................................................... ..9
`1.2 Possible behaviors for a ‘Seeing Robot’ ............................................................................ ..9
`1.2.1 Collision Avoidance ................................................................................................... ..9
`
`1.2.2 Perception of Motion and Speed Control ................................................................... .. 10
`
`DESIGN AND ASSEMBLY OF CAMERA ............................................................................ ..11
`
`2.1 System Electronics ......................................................................................................... ..11
`2.1.1 CCD Description ..................................................................................................... ..11
`2.1.2 CCD biasing ............................................................................................................ ..11
`2.1.3 Frame grabbing circuitry .......................................................................................... ..11
`2.1.4 Power supply ........................................................................................................... .. 12
`2.1.4.1 Camera electronics performance......................................................................... .. 13
`2.2 Camera Optics ............................................................................................................... .. 13
`
`2TABLE OF CONTENTSTABLE OF CONTENTS............................................................................................................2TABLE OF FIGURES................................................................................................................3ABSTRACT................................................................................................................................4INTRODUCTION.......................................................................................................................5A CCD BASED IMAGE PERCEPTION SENSOR FOR MOBILE ROBOTS.............................61.1 System Overview................................................................................................................61.1.1 Control Computer........................................................................................................61.1.2 Vision..........................................................................................................................71.1.3 CCD-Controller Interface.............................................................................................71.1.4 Circuit Schemetics.......................................................................................................81.1.5 Mobile platform...........................................................................................................91.2 Possible behaviors for a ‘Seeing Robot’..............................................................................91.2.1 Collision Avoidance.....................................................................................................91.2.2 Perception of Motion and Speed Control.....................................................................10DESIGN AND ASSEMBLY OF CAMERA..............................................................................112.1 System Electronics...........................................................................................................112.1.1 CCD Description.......................................................................................................112.1.2 CCD biasing..............................................................................................................112.1.3 Frame grabbing circuitry............................................................................................112.1.4 Power supply.............................................................................................................122.1.4.1 Camera electronics performance...........................................................................132.2 Camera Optics.................................................................................................................13IMAGE PROCESSING.............................................................................................................163.1 Movement recognition......................................................................................................163.1.1 Patch-wise correlation in a single dimension...............................................................163.2 Programming of patch-wise correlation algorithm..............................................................163.2.1 Parameters for patch correlation.................................................................................183.2.1.1 Algorithm performance........................................................................................203.3 Conclusion.......................................................................................................................21SCHEMETICS.............................................................................................................................iREFERENCES..........................................................................................................................V
`
`IMAGE PROCESSING ........................................................................................................... .. 16
`
`3.1 Movement recognition .................................................................................................... .. 16
`3.1.1 Patch—wise correlation in a single dimension ............................................................. .. 16
`3.2 Prograrmning of patch—wise correlation algorithm............................................................ .. 16
`3.2.1 Parameters for patch correlation ............................................................................... .. 18
`3.2.1.1 Algorithm performance ...................................................................................... ..20
`3.3 Conclusion ..................................................................................................................... ..21
`
`SCI-IEMETICS ........................................................................................................................... ..i
`
`REFERENCES ........................................................................................................................ ..V
`
`2
`
`1065-002
`
`1065-002
`
`

`
`TABLE OF FIGURES
`
`Figure 1: Proposed system with possible extensions .................................................................... ..8
`Figure 2: Image of a page of text in size 12 font ....................................................................... ..14
`Figure 3: Image of a colored picture ......................................................................................... ..14
`
`3TABLE OF FIGURESFigure 1: Proposed system with possible extensions......................................................................8Figure 2: Image of a page of text in size 12 font.........................................................................14Figure 3: Image of a colored picture...........................................................................................14
`
`3
`
`1065-003
`
`1065-003
`
`

`
`4ABSTRACTThis project investigates the feasibility of application of vision sensing devices likeCCDs to mobile robots. Emphasis is laid upon the simplicity and cost effectiveness ofhardware and software to implement simple image processing onboard the robot. The keyissue to be explored is that ‘what kind of image processing ability is required by a mobilerobot’.The concept of patch-wise correlation[1] has been explored and partiallyimplemented on a micro-controller based system.
`
`1065-004
`
`

`
`5INTRODUCTIONSimple mobile robots have to rely on simple hardware for mobility and perceptionof environment. Limitations imposed by battery life and power available for locomotion,rule out the possibility of using complicated electronics hardware. Therefore a mobilerobot has to depend on the simplest sensors and single chip computers to accomplish thedesired tasks.Depending on the requirements, the robot can have different sensors to ‘feel’ itsenvironment. Vision is considered a very useful tool to perceive the environment. It maynot be necessary in a vast majority of applications to acquire and analyze detailed visualinformation. Most of the tasks expected of mobile robots are very simple. In fact, some ofthe most useful robots are the ones which perform repetitive tasks in a very limitedenvironment. Using an imaging system to gather only the necessary information istherefore a key step in simplifying the system, e.g., for detection of IR emitting objects, asensor which can only detect infra-red radiation can drastically reduce the time and effortrequired to extract the same information from a more elaborate sensor covering a widerradiation spectrum.The purpose of this project however is to try to acquire elaborate visualinformation, screen the information deemed unnecessary for a mobile agent and drawconclusions about different parameters like size, shape, and speed of different objectsrelative to the robot. All this is expected in a package which is inexpensive, light, and has alow power consumption.
`
`1065-005
`
`

`
`6A CCD BASED IMAGE PERCEPTION SENSOR FOR MOBILE ROBOTS1.1 System OverviewThe image sensor’sa electronics consist of two modules:a) The controller to grab and process the image. It can also control actuators on arobot, like motors etc., in short it can act as a brain for the robot.b) The camera board with the CCD and the latching circuitry to interface thedigital signals to the controller.1.1.1 Control ComputerThe controller board is based on the Siemen’s C166 micro-controller. Thiscontroller is powerful enough to grab the images from the CCD and perform simple imageprocessing in real time. It can also simultaneously acquire information from other sensorsattached to it and run motors or other actuators. The controller has a 10 channelmultiplexed 10-bit A/D converter which can be interfaced to a variety of additional sensorslike IR, temperature etc.. The micro-controller board currently has 64Kbytes of RAM forprogram and data storage. It can easily be expanded to 128Kbytes or 256Kbytes ifnecessary. 64Kbytes of RAM is sufficient to store the program and two complete 8-bit160x160 pixel images (25Kbytes).The controller is programmed using a serial link to the PC for downloading anddebugging the program. The debugged program can be burned into an EPROM whichresides on the board. When the program has been burned into the EPROM, the program aThe term sensor will be used throughout to refer to the CCD, and the micro-controller board asone system.
`
`1065-006
`
`

`
`7starts executing upon application of power to the board and the whole setup is referred toas an embedded controller.1.1.2 VisionThe vision system relies upon a VVL1070 CCD chipb to acquire the images. ThisCCD is different from most of the other CCDs in having an 8-bit A/D on board. It also hasautomatic exposure control and variable frame rate controlled by digital inputs.The CCD was purchased from the Optical Systems Division of Marshall Industries(Tel: 310-390-6608). It is packaged as a 44 pin Lead-less Chip Carrier (LCC) in a ceramicpackage (a PQFP version is also available for about $40). The unusual packaging requiresa 44 pin LCC socket which was purchased from Newark Electronics.The remaining hardware like the IDC connectors, capacitors, and resistors werepurchased from JDR Microdevices (Tel: 1-800-538-5000).1.1.3 CCD-Controller InterfaceThe CCD puts out digital data for each pixel. Each pixel value is accompanied by apulse referred to as the pixel clock on a dedicated pin. The pixel clock is used to latch thedata in a latch and is also connected to an input pin on the micro-controller. A pollingroutine has been used to read the data from the latch upon every pulse of the pixel clock.The CCD has a digital input to enable its output, along with other digital inputs tocontrol the frame size and rate. These parameters are controlled by the micro-controllerusing its digital output ports. bVVL1070 from Marshall Industries for $10 in quantities of 10,000 or more. $80 in smallquantities for the ceramic 80 pin LCC version for prototyping.
`
`1065-007
`
`

`
`81.1.4 Circuit SchemeticsEven though the CCD was accompanied by Gerber plot files from MarshallIndustries for an evaluation board, this PCB was designed to have 4 layers. Fabricatingthis kind of a board in IMDL is not possible, therefore the idea to fabricate the evaluationboard was dropped. It is much easier to draw the Schemetic diagram for the evaluationboard from scratch and generate the Gerber files to fabricate a single or two layer PCB.The Schemetic diagram is attached at the end of the report.A block diagram of the system is shown in Figure 1Figure 1: Proposed system with possible extensionsIR SENSORA-+SERVO MOTORA-+SERVO MOTORVVL 1070(CCD)DIGITAL DATAADDITIONAL SENSORS AND ACTUATORSCONTROL LINESSIEMEN'S C166 BASEDCOMPUTER
`
`1065-008
`
`

`
`9An IR sensor is shown in the Figure 1 as it might prove a worthy companion to the CCDby providing distance information to the target being viewed.1.1.5 Mobile platformA mobile platform has not used as the setup has been developed to evaluaterudimentary image processing. The results of the processing can however be used in anyrobot whether it is controlled by the Siemen’s controller board or some other. The wholesetup can act as a smart sensor by informing the main controller board of any impedingobjects, or movements in view. The main controller can use this information in any way toimplement a behavior. A serial link between the image sensor and the main controller willbe ideal to exchange information, especially as the link will not be more than a few incheslong (assuming the sensor and the controller are mounted on the same robot). The sensorsetup is generic enough to be incorporated into any robot to enhance its sensory abilitieswithout modifying the existing control hardware setup.1.2 Possible behaviors for a ‘Seeing Robot’1.2.1 Collision AvoidanceOne of the most important requirements for a mobile robot is to avoid collisionswith obstacles. This is generally accomplished by using infra-red sensors and sonardevices. These devices are already sufficiently developed to provide accurate informationto the robot about impending collisions well ahead of time. This concept can easily beextended to avoiding ‘enemies’ using CCDs. The robot might be able to recognize the‘enemies’ as programmed in its ‘genes’ (the program) or it might be able to recognize‘enemies’ with which it had an unfavorable encounters in the past. The robot can store
`
`1065-009
`
`

`
`10image patterns of different objects and information about their behavior in its memory as asmall data-base as it moves around in its environment. Upon ‘seeing’ an object, it canmatch it to the patterns stored in the memory and the stored information about thatobject’s behavior can be used by the robot to advance or retreat.1.2.2 Perception of Motion and Speed ControlThe robot can be programmed to make use of images to record the speed of itstravel. The concept of Patch-wise Correlation[1] has been used to extract informationabout movement of objects in images. As the algorithm uses changes in the image alongthe direction of travel, the rate of these changes can be used to calculate the velocity of therobot with respect to the observed object.In this case, the distance to the object is an important parameter and the robot canuse IR sensors to measure this distance. Based on the displacement of a certain pattern insuccessive frames and the distance of camera from the object, the robot can calculate itsown speed with respect to that object.The same above technique may be used to steer the robot in certain directionsalong with avoiding obstacles.
`
`1065-010
`
`

`
`11DESIGN AND ASSEMBLY OF CAMERA2. 2.1 System Electronics2.1.1 CCD DescriptionThe VVL1070 CCD is a 160x160 pixel area CCD. It can be read out in anycombination of 160 pixels and 120 pixels, i.e., it can be read as a 160x120, 120x120,120x160 or 160x160 pixel CCD. Only the pixels which lie in the specified combination areread out.The CCD has an analog as well as a digital output. The digital output can be readin parallel as well as serial format. The maximum frame rate is 22.7 fps with a 12 MHzclock, configurable down to 2.8 fps.All the above mentioned parameters can be configured with digital inputs. Furtherdetails can be obtained from the data sheet provided by Marshall Industries (Tel: 310-390-6608) who are the distributors of VVL products.2.1.2 CCD biasingThe CCD needs some external components to bias different parameters such asblack and white pixel thresholds. The circuit diagram in Schemetic section shows all thecomponents with their values.2.1.3 Frame grabbing circuitryA Siemen’s 80C166 based single board computer has been used to grab andprocess the image. The 16-bit architecture of this processor makes it more suitable for
`
`1065-011
`
`

`
`12processing the image, though with careful design an 8-bit controller like a 68HC11 or an8051 can be made to perform the same functions albeit a little slowly.The pixel data from the CCD is accompanied by a pulse on the PCLK (pixel clock)pin. The data is valid for a short time and is therefore latched into buffers so that the u-Controller can read it even after the CCDs internal data buffers have been disabled. Thiscircuitry is shown in the Schemetic section at the end of the report.Initially, it was planned to map the CCD in the memory of the u-Controller. Thisidea was dropped because the u-Controller has sufficient ports available for a directinterface. The latching circuitry utilizes a 74LS373 latch. The data is latched into thebuffer by a 35ns pulse which is generated by the PCLK. The reason for generating thispulse is to ensure that even the slowest TTL 74LS373 can be used as the PCLK itself canbe very short depending on the clock input of the CCD (Half of 74LS123 was availableanyway). The PCLK is also used to generate a 800ns pulse for the controller because thecounter input port which polls for the pixel clock has to have a pulse valid for at least400ns to be recognized.A PAL has been used in the design even though currently it is only being used as asingle inverter. It was included in case any more logic functionality was required. Its logicdescription is shown on the Schemetic. It can be replaces by a single inverter as is evidentfrom the Schemetic.2.1.4 Power supplyIt is essential to run the u-controller and the camera off a single supply as there isno GND pin on the interfacing connector between the controller and the camera. Thecamera has two power connectors - one for regulated 5V, the other for unregulated 10V.
`
`1065-012
`
`

`
`13If it is supplied with unregulated 10V, the 5V connector can be used as a regulated 5Voutput to power the u-controller board. If the 5V connector is used as input, nothing otherthan a regulated 5V should be connected to it.2.1.4.1 Camera electronics performanceThe u-controller board worked without missing any pixel data upto 5.7 fps. Forhigher frame rates, it might be possible to use DMA to grab the image. Even though noreal-time processing is currently being performed, it is possible to perform image additionsor subtractions at frame rates upto 5.7 fps.2.2 Camera OpticsThe camera optics proved to be a much bigger problem than initially anticipatedfor the following reasons:a) The camera electronics were prototyped with wire-wrapping. The size of thecircuit board was therefore much larger than a well designed PCB would havebeen. Thus it was impossible to fix the circuitry in any suitable housing - likethat of a disposable camera.b) The CCD is packaged as a 44 pin LCC and therefore needed a socket with 100mil spaced leads suitable for prototyping boards. Most of the sockets availablehad 50 mil zip type footprint for the dual rows on each side which is notsuitable for 100 mil spaced holes of a prototyping board. The socket whichwas finally used dictated against the use of pin-hole lenses supplied by MarshallElectronics.
`
`1065-013
`
`

`
`14c) The active area of the CCD is 1.7mm x 1.7mm, thus making it very difficult toalign lenses on top of the CCD at the exact spot. A basic pin-hole setup willnot work as the hole has to be small enough to create an image but should notbe too far from the CCD for an acceptable angle of view thus making the taskof aligning even more difficult for a prototyping design assembled in a piece ofsanitary pipe fitting (the fitting houses the camera). Images were grabbed usingthis setup but angle of view was very smallc and the view was not straighteither. The final optic setup consisted of a Fujinon 1:1.4/50 lens which is moreof a telephoto lens than a wide angle lens. The angle of vision is not very widebut fairly decent images can be obtained with this setup. A wide angle lens isstill desirable for use on an autonomous agent.Following images of a portion of a page of text were grabbed using the Fujinon lens:Figure 2: Image of a page of text in size 12 fontFigure 3: Image of a colored picture cA similar project undertaken by Andrew S. Gavin[4] used a 3mm wide-angle CCD lens afterevaluating several asepheric and pin-hole lenses. Gavin’s lens provides a 60-70 degrees angle ofview.
`
`1065-014
`
`

`
`15These objects were placed at a distance of 36 inches from the camera lens. It is clear fromthe images that a wide angle lens will certainly solve the optical problems.
`
`1065-015
`
`

`
`16IMAGE PROCESSING3. 3.1 Movement recognitionDifferent people have tried different approaches to detect movement using imagesequences. Most of these techniques however are computation-intensive and therefore notsuitable for a u-controller based system on a small robot. The technique of singledimension patch correlation is fast and easier to implement on a u-controller and hastherefore been tested in this project.3.1.1 Patch-wise correlation in a single dimensionThe concept of patch-wise correlation is covered in detail by Ancona[2] andMubeen[1]. The basic idea is to take a single dimensional patch from an image which hasbeen averaged vertically, and to move it horizontally across the second image at about thesame vertical position where it was originally created in the first image and try to find theregion which most closely matches the patch. This is accomplished by using the followingequation:min|(,)(,)|D D
`
`(cid:229)where i0 and j0 are the co-ordinates of one corner of the patch in the first image. The bestmatch is the horizontal co-ordinate of the region in the second image most closely matchesthe patch.3.2 Programming of patch-wise correlation algorithmThe concept of patch-wise correlation seems simple from the above equation andits implementation is relatively much easier on powerful computers with huge memory
`
`x
`
`A i
`i
`j
`B i
`i
`x j
`+ +
`+
`000001
`
`=-
`iN
`
`1065-016
`
`-
`

`
`17spaces. To implement it on a 286-class u-controller with only 64K of RAM without anyhigher level language is easier said than done. Assembly language routines had to becreated even for such simple operations as accessing array elements. All the routines hadto written for 2-dimensional arrays considering the application on hand.Following is a brief description of the routines written to accomplish the mostfundamental of tasks:Setup_exp: This routine is executed during initialization. It looks at the central 16x16pixel region of an image and adjusts the exposure settings of the CCD until this regionshows medium brightness.Exp_low: This routine lowers the exposure by a specified amount.Exp_hi: This routine raises the exposure by a specified amount.Grab_one: This routine waits until the start of a frame and then grabs and stores an imagein the region specified to the routine.Send_image: This routine sends the image to the computer through an RS-232 link. Thisroutine is necessary for debugging.Get_Pixel: This routine gets the value of a pixel from the image by using the base addressof the image, the width of the image, the x-coordinate , and the y-coordinate of the pixel.Put_Pixel: This routine writes the value of a pixel in the image by using the base addressof the image, the width of the image, the x-coordinate , and the y-coordinate of the pixel.Create_Patch: This routine reads a specified region in the image and creates a new arrayto store this data. This data is treated as a ‘patch’ in the image.
`
`1065-017
`
`

`
`18V_av_image: This routine averages the image vertically over a specified number of lines,i.e., the image is divided into a specified number of horizontal patches and then each patchis vertically averaged.Match_patch: This routine takes a patch stored in memory and matches it across thespecified image in memory. It returns the level of match and the location of match. Highervalues indicate bad matches.In addition to these routines, a variety of other routines were written to debugthese routines. A ‘C’ program was developed for DOS to receive the image from the serialport of the PC, store it as a raw data file and display itd. This image transfer is very slowbecause of the 9600 baud rate used. A 160x120 pixel image consists of 19200 bytes ofdata and it takes about 20 seconds to transfer it to the PC.3.2.1 Parameters for patch correlationPatch correlation in horizontal direction requires averaging the image vertically,creating a suitable patch, getting the next image, averaging it as well and finding a matchfor the patch in the vicinity of the location of original patch. Size of averaged strips andpatch are critical to the performance of the algorithm. A small program utilizing theaforementioned routines was executed and performed differently depending on the stripsize and patch size.Strip size: To perform patch-wise correlation, some parameters have to be specifieddepending on the image size, quality, and the kind of objects being viewed. As mentioned,an image has to be averaged vertically over horizontal strips for a horizontal patch search.
`
`1065-018
`
`

`
`19The size of the strips is very important to the performance of the algorithm. If the stripsize is too small, a suitable match might not be found because the image region containingthe patch might move slightly in the vertical direction, or the lightening conditions mightchange slightly. The strip size should also take into consideration the angle of view as aCCD without a very wide angle lens (like the case in this project) will result in largechanges in the image corresponding to small movements in the scene.Another issue is that of the averaging of strips themselves. If a certain number ofstrips are averaged and the next lower strip is averaged independently of the one above it,there will be a boundary between the two strips which may be undesirable. It should bepossible to overcome this problem by using taller strips with the selected patch in themiddle of a strip in the image. This should make the algorithm more robust in the presenceof vibrations.Patch selection and size: Selection of the patch is critical to the success of this algorithm.Depending on the objects in view, different patches will perform differently in similarenvironments. A small patch might work well in a cluttered environment but will probablyfail in a sparse environment as it will find false matches. Similarly, a large patch will workwell in sparse environments but might not find a match in cluttered environments. It mightbe possible to make the patch size a variable and adjust it depending on the kind ofenvironment, e.g., a patch may be created between two vertical edges for horizontalmatching. If two edges are found far apart in the image indicating a sparse environment, alarge patch will be created and vice versa. dThis routine can be used to transfer the image to the PC from the robot through some kind of awire-less link for some kind of an application even though the robot will not be able to do anythingelse during this time.
`
`1065-019
`
`

`
`203.2.1.1 Algorithm performanceExtensive testing has not been done using a variety of combinations of the abovetwo parameters but horizontal strip sizes of four rows of pixels were used with a fixedpatch size of 48 pixels. The sensor found small horizontal movements fairly well whichwas expected due to the small angle of view of the sensor. Also, as patch re-creation uponthe patch’s going out of view has not been implemented yet, the sensor keeps looking forthe same patch even after the scene has changed drastically finding extremely ‘non-matches’ as matches. Patch re-creation may be implemented before the demonstration ofthe project.Edge detection in a single dimension is a feature which might be extremely usefulto the algorithm as it will enable intelligent selection of patches.
`
`1065-020
`
`

`
`213.3 ConclusionThis project changed from implementation of image processing algorithms todevelopment of an image sensor. Some unforeseen problems delayed the implementationof actual image processing to the very end of the semester. It will be continued in the nextsemester to gather some experimental data and program refinement. A PCB will bedeveloped to reduce the size, cost, and weight of the camera so that others interested inusing a $100 digital camera will not have to through the trouble of assembling anddebugging the hardware.Implementation of the basic patch correlation algorithm is just scratching thesurface of possibilities. It might be possible to implement patch correlation in fourdirections with four different patches to detect looming of objects.This experiment provides a test-bed for implementation of various algorithms forrobot-vision. The results from the brief experimentation have been encouragingconsidering that the sensor is small, light weight, has low power consumption, and can bepowered by a battery pack. More experimentation and effort in software will certainlyimprove the performance of the sensor to the point where it can control different functionsof the robot itself (the 10 inputs of the A/D port and 12 digital I/O lines are available forinterfacing to sensors and switches). With suitable visual capabilities along with IR andbump sensors, this should make a fairly powerful platform to implement complicatedbehaviors for robots.
`
`1065-021
`
`

`
`SCHEMETICS
`
`iSCHEMETICS
`
`1065-022
`
`1065-022
`
`

`
`ii
`
`1065-023
`
`1065-023
`
`ii
`

`
`ii