Method and apparatus for alerting surface vessels to hazardous conditions

<u>Background of the Invention</u>

This invention relates to the prevention of grounding accidents for marine vessels. Grounding accidents in the global shipping fleet are a major source of property loss, costing the industry an estimated $400MM annually in insurance liability on global shipping trade of more than $200 billion. U.S. Coast Guard data from the years 1996-1997 indicate that each year, 1170 vessels (towed barges and tugs counted individually) are involved in groundings, in a total of 758 annual incidents on U.S. shipping lanes and waterways.

Despite this significant adverse impact on shipping and commercial fleets worldwide, there exist limited systems for prevention of grounding accidents. Most ships are equipped with sonar to monitor the actual depth of the water beneath the hull. However, this device is a reactive system that provides only a current status and does not protect against anticipated conditions present along the instantaneous track of the boat. This device also requires active monitoring by ship's crew to detect a hazardous condition. In military operations, use of the sonar may inadvertently betray the boat's location to enemy vessels.

Vessels may also be equipped with moving map displays that show the vessel's progress relative to a stored nautical chart. These systems also require the crew to actively monitor the vessel's progress against the chart and to proactively identify hazardous conditions.

In the aviation industry, various systems have been developed that provide warnings and advisory indications to the pilot of aircraft approaching hazardous terrain. Among such systems are systems generally known as ground proximity warning systems (GPWS) which monitor the flight conditions of an aircraft and provide a warning if flight conditions are such that inadvertent contact with terrain is imminent. Among the flight conditions normally monitored by such systems are radio altitude and rate, barometric altitude and rate, air speed, flap and gear positions. These parameters are monitored and an advisory signal and/or warning signal is generated when the relationship between the parameters is such that terrain impact is likely to occur. Typical examples of such systems are disclosed in <patcit id="pcit0001" dnum="US3715718A"><text>U.S. Patent Nos. 3,715,718</text></patcit>; <patcit id="pcit0002" dnum="US3936796A"><text>3,936,796</text></patcit>; <patcit id="pcit0003" dnum="US3958218A"><text>3,958,218</text></patcit>; <patcit id="pcit0004" dnum="US3944968A"><text>3,944,968</text></patcit>; <patcit id="pcit0005" dnum="US3947808A"><text>3,947,808</text></patcit>; <patcit id="pcit0006" dnum="US3947810A"><text>3,947,810</text></patcit>; <patcit id="pcit0007" dnum="US3934221A"><text>3,934,221</text></patcit>; <patcit id="pcit0008" dnum="US3958219A"><text>3,958,219</text></patcit>; <patcit id="pcit0009" dnum="US3925751A"><text>3,925,751</text></patcit>; <patcit id="pcit0010" dnum="US3934222A"><text>3,934,222</text></patcit>; <patcit id="pcit0011" dnum="US4060793A"><text>4,060,793</text></patcit>; <patcit id="pcit0012" dnum="US4030065A"><text>4,030,065</text></patcit>; <patcit id="pcit0013" dnum="US4215334A"><text>4,215,334</text></patcit>; and <patcit id="pcit0014" dnum="US4319218A"><text>4,319,218</text></patcit>, all assigned to the same assignee as the assignee of the present invention and hereby incorporated by reference. <patcit id="pcit0015" dnum="US5488563A"><text>US Patent Nos. 5,488,563</text></patcit> and <patcit id="pcit0016" dnum="US5839080A"><text>5,839,080 to Mueller et al.</text></patcit> each disclose a controlled flight into terrain alerting system that utilizes a terrain database in conjunction with aircraft dynamics to alert pilots of dangerous proximity to terrain.

However, such systems are designed for aircraft wherein the escape maneuver chiefly consists of adding full power and pitching the aircraft up to initiate a climb. This type of escape from grounding is not available to a surface vessel. <patcit id="pcit0017" dnum="US5488563A"><text>U.S. Patent No. 5,488,563 to Chazelle </text></patcit>describes a ground proximity warning system for aircraft that suggests a turning maneuver to escape terrain. However, Chazelle does not disclose or suggest how such a system could be applied to ships, submarines or boats. <patcit id="pcit0018" dnum="US4646244A"><text>U.S. Patent No. 4,646,244 to Bateman </text></patcit>discloses a terrain alerting methodology for submarines and aircraft. However, Bateman does not disclose terrain alerts for surface ships or terrain avoidance maneuvers.

<u>Summary of the Invention</u>

The present invention includes recognition of the need to provide marine vessels with an alert of conditions that may lead to an inadvertent grounding and/or impact with obstacles in the vessel's path. The alerts provided according to the present invention may be reactive and/or predictive alerts.

According to one aspect of the present invention, an apparatus for alerting the user of a surface marine vessel of proximity to terrain comprises: an input for receiving signals representative of a position, speed, and a track of the surface marine vessel, and coupled to a database of stored terrain information; an output; a signal processing device coupled to said input and said output, the signal processing device being adapted to define a look ahead distance as a function of speed and distance required to stop the vessel; define a first alert envelope indicative of a first level of terrain proximity alert, wherein boundaries of the first alert envelope are determined as a first function of the track, look ahead distance, and a terrain floor boundary; define a second alert envelope indicative of a second level of terrain proximity alert, wherein boundaries of the second alert envelope are determined as a second function of the track, look ahead distance, and the terrain floor boundary; and output an alert signal when a subset of the stored terrain information is located within the boundaries of at least one of the first and second alert envelopes.

An ocean bottom terrain data base may be provided. The ship's position and anticipated track are compared to the ocean bottom terrain data and an alert is provided when a hazardous condition is detected.

The terrain database may include an obstruction or obstacle data base. The ship maximum height and anticipated track can be compared, for example, with the clearance height required under a bridge obstacle, and an alert provided to the crew if a collision hazard exists.

Ocean bottom hazards may be displayed on a visual display representative of a plan view of the ocean or waterway bottom terrain. Preferably the terrain is displayed in various colors and/or dot pattern densities depending upon the degree of grounding hazard to the vessel and/or to the degree of obstacle collision hazard. In a preferred embodiment of the invention, the terrain that does not present a hazard to the vessel is displayed in a first color, terrain that is a potential hazard to the vessel is displayed as second color and terrain which represents an immediate and actual danger to the vessel is colored a third color.

More specifically, the bottom proximity awareness system may comprise a navigational system configured to determine latitude, longitude, depth, point of intended movement, velocity, acceleration and/or speed of a vessel employing the system. The navigational system generates signals in response to the listed parameters. The system further comprises: a terrain database comprising depth data for underwater terrain and obstacle information as well as for port facilities; a processor configured to identify from the terrain database depth data within a range of the vessel; warning envelope generator; and a warning device. Further advantages and features of the present invention will be described in detail below.

<u>Brief Description of the Drawings</u>

<ul id="ul0001" list-style="none"><li><figref idref="f0001">Fig. 1</figref> is a top level flow chart illustrating operation of a warning system in accordance with a preferred embodiment of the invention;</li><li><figref idref="f0002">Fig. 2</figref> is a block diagram of a warning system according to a preferred embodiment of the invention;</li><li><figref idref="f0003">Figs. 3A and 3B</figref> illustrate a set of coordinates axes and forces useful for understanding ship motions as described in the present application;</li><li><figref idref="f0004">Fig. 4</figref> illustrates a turning maneuver and the nomenclature associated therewith;</li><li><figref idref="f0004">Fig. 5</figref> illustrates a stopping maneuver and the nomenclature associated therewith;</li><li><figref idref="f0005">Fig. 6</figref> illustrates the organization of terrain data into latitude and longitude segments in accordance with a preferred embodiment of the invention;</li><li><figref idref="f0006">Fig. 7</figref> is a graphical representation of the various memory map and resolution sequencing in accordance with the present invention;</li><li><figref idref="f0007">Fig. 8A</figref> is an exemplary representation of the digital header and subsquare mask word for identifying geographical areas in accordance with the present invention;</li><li><figref idref="f0007">Fig. 8B</figref> is a terrain map alternative to <figref idref="f0006">Fig. 7</figref>;</li><li><figref idref="f0008">Fig. 9</figref> is a block diagram illustrating the configuration of a flash ROM for a terrain data base and a RAM used with a preferred embodiment of the present invention;</li><li><figref idref="f0009">Fig.10</figref> is a diagram of the file format of the files in the terrain data base in accordance with a preferred embodiment of the present invention;</li><li><figref idref="f0009">Fig. 11</figref> illustrates an insufficient terrain clearance reactive alerting envelope according to an embodiment of the present invention;</li><li><figref idref="f0009">Fig. 12</figref> illustrates a plan view showing the boundaries of an alert envelope according to an embodiment of the present invention;</li><li><figref idref="f0010">Fig. 13</figref> illustrates a plan view of an alert envelope having both caution and warning boundaries according to an embodiment of the present invention;</li><li><figref idref="f0010">Fig. 14</figref> illustrates a side view showing vertical tolerancing of an alert envelope constructed according to an embodiment of the invention;</li><li><figref idref="f0010">Fig. 15</figref> illustrates a side view showing vertical tolerancing of an alert envelope for shallow water operations constructed according to an embodiment of the present invention;</li><li><figref idref="f0010">Fig. 16</figref> illustrates a plan view of an alert envelope for operating in confined spaces according to an embodiment of the present invention;</li><li><figref idref="f0011">Fig. 17</figref> illustrates a constant time to impact alert envelope constructed according to an embodiment of the present invention;</li><li><figref idref="f0011">Fig. 18</figref> illustrates an alert envelope generated with reference to the marine vessel according to an embodiment of the present invention;</li><li><figref idref="f0011">Fig. 19</figref> illustrates an alert envelope based on projected track according to an embodiment of the present invention;</li><li><figref idref="f0012">Fig. 20</figref> illustrates a look ahead/look down alert envelope according to a preferred embodiment of the invention;</li><li><figref idref="f0012">Fig. 21</figref> illustrates a terrain clearance floor as a function of distance from moorage according to a preferred embodiment of the invention;</li><li><figref idref="f0012">Fig. 22</figref> is a graphical illustration of an alert envelope having a cut off boundary according to an embodiment of the present invention;</li><li><figref idref="f0013">Fig. 23</figref> is a plan view of an array of track vectors useful for defining the internal boundaries of the look ahead/look down/look up alert envelopes according to a preferred embodiment of the invention;</li><li><figref idref="f0014">Fig. 24</figref> illustrates a projected track vector according to an embodiment of the present invention;</li><li><figref idref="f0014">Fig. 25</figref> illustrates an ellipsoid of uncertainty in position according to an embodiment of the present invention;</li><li><figref idref="f0015">Fig. 26</figref> illustrates use of ellipsoids of uncertainty about the projected track to obtain an envelope of probable position according to an embodiment of the present invention;</li><li><figref idref="f0015">Fig. 27</figref> illustrates the progress of vessel along the projected track in the local terrain map according to an embodiment of the present invention;</li><li><figref idref="f0016">Fig. 28A</figref> illustrates an alert logic along a projected track sampling point according to an embodiment of the present invention;</li><li><figref idref="f0016">Fig. 28B</figref> illustrates a plan view of an alert logic along a projected track sampling point according to an embodiment of the present invention;</li><li><figref idref="f0017">Fig. 29A</figref> illustrates calculation of an avoidance maneuver in accordance with an embodiment of the present invention;</li><li><figref idref="f0017">Fig. 29B</figref> illustrates calculation of an avoidance maneuver using projected track alert envelopes in accordance with an embodiment of the present invention;</li><li><figref idref="f0018">Fig. 30</figref> is a block diagram of a display system according to one embodiment of the present invention;</li><li><figref idref="f0019">Fig. 31</figref> is a functional diagram of the display data format in accordance with a preferred embodiment of the invention;</li><li><figref idref="f0020">Fig. 32</figref> is a plan view of a background terrain display illustrating the variable density dot pattern;</li><li><figref idref="f0021">Fig. 33</figref> is similar to <figref idref="f0020">Fig. 32</figref> but additionally illustrates the terrain threat indications;</li><li><figref idref="f0022">Fig. 34</figref> illustrates a wedding-cake configuration for a RAM utilized in the present invention;</li><li><figref idref="f0023">Fig. 35</figref> illustrates data blocks constructed according to a preferred embodiment of the present invention;</li><li><figref idref="f0024">Fig. 36</figref> is a block diagram of the display system in accordance with a preferred embodiment of the present invention illustrating the memory configuration and the data flow;</li><li><figref idref="f0025">Fig. 37</figref> is a block diagram of a configuration alternative to that shown in <figref idref="f0024">Fig. 36</figref>;</li><li><figref idref="f0026">Fig. 38</figref> is a terrain map illustrating the computation of the hazardous terrain;</li><li><figref idref="f0027">Fig. 39</figref> is a diagram of a terrain map superimposed on a display screen illustrating the sweep range and the determination of the incremental range increments;</li><li><figref idref="f0028">Fig. 40</figref> is a diagram of a pixel map of the display;</li><li><figref idref="f0029">Fig.41</figref> is a diagram of the different fractal patterns used to provide the variable density display of non-hazardous display indications;</li><li><figref idref="f0030">Fig. 42</figref> is a diagram illustrating the determination of the X and Y increments of the display screen;</li><li><figref idref="f0030">Fig. 43</figref> is a diagram of the method for superimposing the fractal patterns on the displayed pixel map; and</li><li><figref idref="f0031">Fig. 44</figref> is a diagram of a three dimensional terrain display according to an embodiment of the present invention;</li></ul>

<u>Detailed Description of the Preferred Embodiments</u>

The present invention now will be described more fully hereinafter with reference to the accompanying drawings, in which preferred embodiments of the invention are shown. This invention may, however, be embodied in many different forms and should not be construed as limited to the embodiments set forth herein; rather, these embodiments are provided so that this disclosure will be thorough and complete, and will fully convey the scope of the invention, as defined by the claims, to those skilled in the art. Like numbers refer to like elements throughout.

<i>1.0 Overview</i>

<figref idref="f0001">Fig. 1</figref> contains a flow diagram illustrating the conceptual theory and operation of the present invention. In <figref idref="f0001">Fig. 1</figref>, symbols representative of the depth and velocity/speed of the vessel, the track of the vessel, and the position of the vessel are received in step 1. In step 2, search logic, based on the position of the vessel, retrieves terrain and obstacle data relating to terrain and obstacles that are near the vessel current position. In step 3, based on the position, track, and speed of the marine vessel and the position and depth of terrain and obstacles proximate to the marine vessel, a caution and warning envelope generator generates envelopes either about the vessel or about the surrounding terrain and obstacles. Optionally, and not shown in <figref idref="f0001">Fig. 1</figref>, the alert may be generated by comparing the closure rate of terrain with a predetermined closure rate limit as described more fully below. The envelopes represent a proximity limitation between the surrounding terrain and obstacles and the marine vessel, such that if the region between the marine vessel and the terrain is less than the envelopes, the marine vessel is in danger of colliding with the terrain.

Steps 4, 5 and 6, compare the position of the marine vessel and the position of the terrain and obstacles with the envelopes. If the marine vessel and the terrain are in closer proximity to each other than the area defined by the envelope, either both or one of a aural or a visual indication to the crew is provided that the vessel is in danger of colliding with the terrain. Optionally, step 6 may further include avoidance maneuver guidance. In addition, based on the generated envelopes and the output of the comparison step, appropriate displays may be provided to the crew illustrating the proximity of the marine vessel to the surrounding terrain and obstacles and alerting of any potential dangers. As such, the apparatus, methods, and computer program products of the present invention provide the user of a marine vessel information concerning the proximity of surrounding terrain such that the user may operate the marine vessel with reduced probability of collision or grounding.

<figref idref="f0002">Fig. 2</figref> contains a block diagram of an apparatus for providing terrain proximity alerts to a marine vessel according to one embodiment of the present invention. The apparatus of this embodiment of the present invention includes an alert generator 10 having a caution and warning envelope generator 12 for generating caution and warning envelopes. The apparatus of the present invention also includes a navigation system 14. The navigation system provides the speed/velocity of the marine vessel, the predicted track of the marine vessel, and the position of the marine vessel, (e.g., latitude and longitude) as well as corrections for tides, currents, ship dynamics and keel depth. Apparatus 10 also includes a first memory device 16 containing coordinate positions of terrain and obstacles, as well as the elevation or depth of the terrain for all or a portion of the global positions of the earth. Additionally, the apparatus of the present invention further includes search logic 18 for searching the first memory device and retrieving terrain data for terrain that is in proximity to the marine vessel.

A comparator 20 is coupled to the output of navigation system 14 and the caution and warning envelope generator 12. Comparator 20 receives the caution and warning envelopes generated from the caution and warning envelope generator and the coordinates of the position of the marine vessel from the navigation system. Based on the position of the marine vessel and the envelopes generated by the caution and warning envelope generator, the comparator determines whether the space between the marine vessel and the terrain proximate to the marine vessel is less than the boundaries defined by at least one of the caution and warning envelopes generated by the caution and warning envelope generator.

To notify the user of the proximity of terrain and obstacles to the marine vessel, the apparatus of the present invention further includes a caution and warning alert generator 22 connected to the comparator 20 for indicating to the user either aurally by a speaker 28 and/or visually by a lamp 30 of approaching terrain. Additionally, the apparatus of the present invention may also include a display generator 23 connected to the output of caution and warning envelope generator 12. Display generator 23 generates attitude and map displays that are applied to a display 36. Display generator 23 controls display 26 to display either or both a side view image showing the terrain and obstacles that lie in the path forward of the track of the marine vessel and a top view of the terrain below the marine vessel.

Signals from comparator 20 may also be applied to display generator 23. These signals permit display generator 23 to indicate whether the distance between the marine vessel and terrain is less than the boundaries defined by the caution and warning envelopes. The terrain threat severity is typically illustrated in the displays by changing the color and/or dot pattern density of the terrain displayed by the display to the user. The elements features and operation of the present invention described briefly above, will now be described in detail below.

In addition to providing apparatus and methods, the present invention also provides computer program products for providing a terrain proximity warning system for use in marine vessels. The computer program products have a computer readable storage medium having computer readable program code means embodied in the medium. In <figref idref="f0002">Fig. 2</figref>, the computer readable storage medium may be part of the memory device 16, and the alert generator 10 of the present invention may implement the computer readable program code means to provide a terrain proximity warning system for use in marine vessels as described in the various embodiments above.

The computer-readable program code means includes first computer instruction means for comparing a current coordinate position of the vessel to a prestored coordinate position of terrain proximate to the vessel and second computer instruction means for providing an alert when the vessel is in a potentially hazardous proximity to the terrain as defined by a predetermined criterion to be described in detail below.

In some embodiments, the computer-readable program code means further includes computer instruction means for storing a database containing depth data for different global coordinates of the earth. In this embodiment, the first computer instruction means determines the current coordinate position of the vessel and searches the memory device for the prestored coordinate position of terrain proximate to the vessel. The computer-readable program code means may further include a computer instruction means for generating an envelope relative to at least one of the vessel and the proximate terrain. The first computer instruction means determines if the other of the vessel and the terrain penetrates the envelope, and the second computer instruction means provides an alert if the envelope is penetrated.

<figref idref="f0001">Figs. 1</figref> and <figref idref="f0002">2</figref> are flowchart block diagram and control flow illustrations of methods, systems and program products according to the invention. It will be understood that each block or step of the block diagram, flowchart and control flow illustrations, and combinations of blocks in the block diagram, flowchart and control flow illustrations, can be implemented by computer program instructions. These computer program instructions may be loaded onto a computer or other programmable apparatus to produce a machine, such that the instructions which execute on the computer or other programmable apparatus create means for implementing the functions specified in the block diagram, flowchart or control flow block(s) or step(s). These computer program instructions may also be stored in a computer-readable memory that can direct a computer or other programmable apparatus to function in a particular manner, such that the instructions stored in the computer-readable memory produce an article of manufacture including instruction means which implement the function specified in the block diagram, flowchart or control flow block(s) or step(s). The computer program instructions may also be loaded onto a computer or other programmable apparatus to cause a series of operational steps to be performed on the computer or other programmable apparatus to produce a computer implemented process such that the instructions which execute on the computer or other programmable apparatus provide steps for implementing the functions specified in the block diagram, flowchart or control flow block(s) or step(s).

Accordingly, blocks or steps of the block diagram, flowchart or control flow illustrations support combinations of means for performing the specified functions, combinations of steps for performing the specified functions and program instruction means for performing the specified functions. It will also be understood that each block or step of the block diagram, flowchart or control flow illustrations of <figref idref="f0001">Figs. 1</figref> and <figref idref="f0002">2</figref>, and combinations of blocks or steps in the block diagram, flowchart or control flow illustrations, can be implemented by special purpose hardware-based computer systems which perform the specified functions or steps, or combinations of special purpose hardware and computer instructions

<i>2.0 Navigation System and Ship Dynamics</i>

The present invention receives various inputs and together with stored models of the vessel's characteristics and performance, outputs data useful for computing the bottom proximity alert envelopes. In the block diagram of <figref idref="f0002">Fig. 2</figref>, these operations may be performed by Navigation system 14. The ship's current position may be obtained by reference to onboard navigation systems such as a global positioning system (GPS), inertial navigation system (INS), LORAN, and/or VLF/OMEGA. Optionally, a navigation fix can be manually entered into the ship's navigation system or autopilot by the crew and this information supplied to navigation system 14. Preferably, navigation system 14 retains the vessel's current position as a set of latitude/longitude coordinates.

While GPS is typically the most advantageous to use as it provides the most accurate data, it must be understood that any particular navigation system may be used. This is typically dependent upon the type of marine vessel. For instance, a military grade marine vessel may include a GPS system for navigation, while a privately owned fishing or water sports craft may include less expensive systems such as a Loran. A combination of systems may also be implemented. Kalman filtering may also be employed to obtain A blended navigation solution based on the various navigation inputs.

Navigation system <b>14</b> may also use the time derivatives of position information to obtain information on ship speed and course and current present heading, as well as set and drift due to local currents. Such calculations are well known to those of ordinary skill in the art. Optionally, navigation system <b>14</b> may receive these inputs directly from other onboard systems, for example, the autopilot, GPS +/- INS, that calculate these values.

The position, data and the data described in the previous paragraph are used to develop an estimate of the vessel's anticipated track and/or the vessel's instantaneous heading and velocity vectors. This data is in turn utilized for the computation of alerts in the manner(s) to be described in more detail below.

Navigation system <b>14</b> also stores data or retrieves input from other shipboard systems as needed to compute the maximum hull depth. In the case of ships and other surface operated marine vessels, keel depth will vary as a function of the center of gravity, center of buoyancy, and displacement of the vessel. A pressure sensor(s) or other fathometer may also be employed at the keel or along the hull to directly measure the depth below keel or draft of the surface vessel. Such data may therefore include the nominal keel depth, current weight of vessel, consumables and cargo, and moment of inertia data as well as tide tables. The tide tables may be used in conjunction with clock data obtained from the ship's clock or GPS system to compute changes from mean sea level. These changes may be applied either as a correction to the maximum hull depth/height of the vessel or applied as a correction to the depth/height of terrain features. In a preferred embodiment of the invention, the tide correction is applied to the hull depth/height to avoid the numerous calculations necessary to apply this correction to all terrain features.

The invention may also contain data useful for computing vessel motion and performance characteristics. Typical analysis of vessel motion includes analysis of both "calm water" effects as well the vessel sea keeping characteristics. The "calm water" effects are those that are attributable to forces arising from operation of the vessel's control surfaces and propulsion systems. Sea keeping characteristics analyze the vessel motion due to wave action in the frequency domain.

A preferred embodiment of the invention thus includes a modular six degree of freedom model of vessel behavior. Optionally, a reduced set of equations with fewer degrees of freedom can be used. A reduced set of equations saves computation time and may be sufficient when only the translation and heave motions of the ship need be calculated. For completeness, the complete model may be generically described as given below. <maths id="math0001" num=""><math display="block"><mrow><mtable><mtr><mtd><mi>m</mi><mfenced open="[" close="]"><mtable><mtr><mtd><mover><mi mathvariant="normal">u</mi><mrow><mo>˙</mo></mrow></mover></mtd></mtr><mtr><mtd><mover><mi mathvariant="normal">v</mi><mrow><mo>˙</mo></mrow></mover></mtd></mtr><mtr><mtd><mover><mi mathvariant="normal">r</mi><mrow><mo>˙</mo></mrow></mover></mtd></mtr></mtable></mfenced><mo>=</mo><mi>f</mi><mfenced open="{" close="}" separators=""><mfenced open="[" close="]"><mtable columnalign="left" width="auto"><mtr><mtd><mi>hydrodynamic</mi></mtd></mtr><mtr><mtd><mi>terms</mi></mtd></mtr></mtable></mfenced><mo>+</mo><mfenced open="[" close="]"><mtable columnalign="left" width="auto"><mtr><mtd><mi>propulsion</mi></mtd></mtr><mtr><mtd><mi>terms</mi></mtd></mtr></mtable></mfenced><mo>+</mo><mfenced open="[" close="]"><mtable columnalign="left" width="auto"><mtr><mtd><mi>inertial</mi></mtd></mtr><mtr><mtd><mi>terms</mi></mtd></mtr></mtable></mfenced><mo>+</mo><mfenced open="[" close="]"><mtable columnalign="left" width="auto"><mtr><mtd><mi>wave action and</mi></mtd></mtr><mtr><mtd><mi>environmental terms</mi></mtd></mtr></mtable></mfenced></mfenced></mtd></mtr></mtable></mrow></math><img file="EP1990609B1_D0001.tif" /></maths> where: <ul id="ul0002" list-style="none"><li><i>m</i> is the vessel mass matrix</li><li><b>U</b> is the vessel speed vector</li><li><b>X, Y, Z</b> and the surge, heave and sway forces as shown in <figref idref="f0003">Fig. 3</figref> and</li><li>u̇, v̇, ṙ are the angular rates about the axes of <figref idref="f0003">Fig. 3</figref></li></ul>

Although there are several mathematical models suitable for use with the present invention, the modular approach permits modeling of effects due to propulsion and steering as well as vessel configuration to be easily incorporated. <nplcit id="ncit0001" npl-type="b"><text>Wilson et al. in Modeling and Control of Marine Craft (Elsevier Applied Science, Pourzanjani and Roberts eds</text></nplcit>.), incorporated herein by reference for all purposes, describe one set of models suitable for use with the present invention. Specifically, these equations describe the forces <b>X, Y, Z</b> and corresponding moments <b>K, M, N</b> about the orthogonal axes x, y, z. In the analysis to follow, these equations are written with a coordinate system centered on the vessel center of gravity, however, it is to be understood that the invention is not so limited and as known to those of skill in the art, similar equations may be written about any axis, for example the stability, or equilibrium axes. The generalized equations of motion can thus be written as: <maths id="math0002" num=""><math display="block"><mrow><mi mathvariant="bold">X</mi><mo>=</mo><mi>m</mi><mfenced separators=""><mover><mi>u</mi><mrow><mo>˙</mo></mrow></mover><mo>−</mo><mi mathvariant="italic">rv</mi></mfenced><mspace width="3em" /><mi>surge equation</mi></mrow></math><img file="EP1990609B1_D0002.tif" /></maths><maths id="math0003" num=""><math display="block"><mrow><mi mathvariant="bold">Y</mi><mo>=</mo><mi>m</mi><mfenced separators=""><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><mi mathvariant="italic">ru</mi></mfenced><mspace width="2em" /><mi>sway equation</mi></mrow></math><img file="EP1990609B1_D0003.tif" /></maths><maths id="math0004" num=""><math display="block"><mrow><mi mathvariant="bold">N</mi><mo>=</mo><msub><mi>I</mi><mrow><mo>=</mo></mrow></msub><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover><mspace width="4em" /><mi>yaw equation</mi></mrow></math><img file="EP1990609B1_D0004.tif" /></maths>

Where ṙ is the angular rate of yaw with respect to time, and u, v are the velocity components of the vessel track as shown in <figref idref="f0003">Fig. 3B</figref>.

Direct measurement of the forces <b>X, Y, Z</b> proves difficult in practice and therefore it is customary to expand these equations as set of differential equations written in terms of measurable quantities. These set of equations are sometimes known as the state space equations for the vessel. By way of example, the surge, sway and yaw equations can be expanded to have the form: <maths id="math0005" num=""><math display="block"><mrow><mi>m</mi><mfenced separators=""><mover><mi>u</mi><mrow><mo>˙</mo></mrow></mover><mo>−</mo><mi mathvariant="italic">rv</mi><mo>−</mo><msub><mi>x</mi><mi>G</mi></msub><msup><mi>r</mi><mn>2</mn></msup></mfenced><mo>=</mo><msub><mi>X</mi><mi>u</mi></msub><mover><mi>u</mi><mrow><mo>˙</mo></mrow></mover><mo>−</mo><msub><mi>Y</mi><mrow><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub><mi mathvariant="italic">vr</mi><mo>−</mo><mfrac><mi>u</mi><mfenced open="|" close="|"><mi>u</mi></mfenced></mfrac><msub><mi>Y</mi><mi mathvariant="italic">dotr</mi></msub><msup><mi>r</mi><mn>2</mn></msup><mo>+</mo><msub><mi mathvariant="italic">X</mi><mi mathvariant="italic">vr</mi></msub><mi mathvariant="italic">vr</mi></mrow></math><img file="EP1990609B1_D0005.tif" /></maths><maths id="math0006" num=""><math display="block"><mrow><mi>m</mi><mfenced separators=""><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><mi mathvariant="italic">ru</mi><mo>+</mo><msub><mi>x</mi><mi>G</mi></msub><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover></mfenced><mo>=</mo><msub><mi>Y</mi><mi mathvariant="italic">dotv</mi></msub><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><msub><mi>Y</mi><mi>r</mi></msub><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><msub><mi>Y</mi><mi>v</mi></msub><mi>v</mi><mo>+</mo><mfrac><mi>u</mi><mfenced open="|" close="|"><mi>u</mi></mfenced></mfrac><msub><mi>Y</mi><mi>r</mi></msub><mi>r</mi><mo>+</mo><msub><mi>Y</mi><mrow><mi>v</mi><mfenced open="|" close="|"><mi>v</mi></mfenced></mrow></msub><mi>v</mi><mfenced open="|" close="|"><mi>v</mi></mfenced><mo>+</mo><msub><mi>Y</mi><mrow><mi>v</mi><mfenced open="|" close="|"><mi>r</mi></mfenced></mrow></msub><mi mathvariant="italic">v</mi><mfenced open="|" close="|"><mi>r</mi></mfenced><mo>+</mo><mfrac><mi>u</mi><mfenced open="|" close="|"><mi>u</mi></mfenced></mfrac><msub><mi>Y</mi><mrow><mi mathvariant="italic">r</mi><mfenced open="|" close="|"><mi>r</mi></mfenced></mrow></msub><mi>r</mi><mfenced open="|" close="|"><mi>r</mi></mfenced></mrow></math><img file="EP1990609B1_D0006.tif" /></maths><maths id="math0007" num=""><math display="block"><mrow><msub><mi>I</mi><mrow><mo>=</mo></mrow></msub><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><mi>m</mi><msub><mi>x</mi><mi>G</mi></msub><mfenced separators=""><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><mi mathvariant="italic">ur</mi></mfenced><mo>=</mo><msub><mi>N</mi><mi>v</mi></msub><mover><mi>v</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><msub><mi>N</mi><mrow><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub><mover><mi>r</mi><mrow><mo>˙</mo></mrow></mover><mo>+</mo><msub><mi>N</mi><mi>r</mi></msub><mi mathvariant="italic">r</mi><mo>+</mo><mfrac><mi>u</mi><mfenced open="|" close="|"><mi>u</mi></mfenced></mfrac><msub><mi>N</mi><mi>v</mi></msub><mi>v</mi><mo>+</mo><msub><mi>N</mi><mrow><mi>r</mi><mfenced open="|" close="|"><mi>r</mi></mfenced></mrow></msub><mi>r</mi><mfenced open="|" close="|"><mi>r</mi></mfenced></mrow></math><img file="EP1990609B1_D0007.tif" /></maths>

In the preceding equations all terms with subscripts mean partial differentiation with respect to that variable. Some terms in these equations have absolute values. The absolute value operator ensures that the force contribution acts in the correct direction when the vessel is turning. Derivatives are typically in non-dimensional form, relating performance to design parameters such as block coefficient, draft and beam. The nondimensional matrix of coefficients can be determined empirically or analytically during ship design and sea trials. Alternatively, in the absence of vessel specific data, and as is known to those of skill in the art, the various non-dimensional coefficients have been determined for various classes of vessels and can be applied with minimal error to the vessel of interest. Propulsion and thrust effects may also be considered in terms of dimensionless coefficients in the manner taught by <nplcit id="ncit0002" npl-type="s"><text>Wilson et al. in Pourzanjani and Roberts</text></nplcit>.

Maximum hull depth may also vary as a function of the surface vessel's motion in seas. For this reason, the invention may also contain data useful for computing the vessel motion due to wave action. In Probabilistic

Theory of ship Dynamics by<nplcit id="ncit0003" npl-type="b"><text> Price and Bishop (Wiley and Sons, NY</text></nplcit>), the authors describe methods for determining the resultant vessel motion using a six column vector of state variables. Specifically, for a rigid ship traveling with constant forward speed U at an arbitrary angle to regular sinusoidal waves, the resultant motions in the six degrees of freedom are governed by the set of second order linear differential equations written about the ship's equilibrium axes: <maths id="math0008" num=""><math display="block"><mrow><mfenced separators=""><mi mathvariant="normal">m</mi><mo>+</mo><mi mathvariant="normal">a</mi></mfenced><mover><mi>q</mi><mrow><mo>¨</mo></mrow></mover><mfenced><mi>t</mi></mfenced><mo>=</mo><mi mathvariant="normal">b</mi><mover><mi>q</mi><mrow><mo>˙</mo></mrow></mover><mfenced><mi>t</mi></mfenced><mo>+</mo><mi mathvariant="normal">c</mi><mi>q</mi><mfenced><mi>t</mi></mfenced><mo>=</mo><msub><mi>Q</mi><mn>0</mn></msub><msup><mi>e</mi><mrow><mi>i</mi><msub><mi>w</mi><mi>e</mi></msub><mi>t</mi></mrow></msup></mrow></math><img file="EP1990609B1_D0008.tif" /></maths>

The 6 x 1 column matrices Q₀ and q(<i>t</i>) represent amplitude of input and output respectively: <maths id="math0009" num=""><math display="block"><mrow><msub><mi>Q</mi><mn>0</mn></msub><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi mathvariant="bold">X</mi></mtd></mtr><mtr><mtd><mi mathvariant="bold">Y</mi></mtd></mtr><mtr><mtd><mi mathvariant="bold">Z</mi></mtd></mtr><mtr><mtd><mi mathvariant="bold">K</mi></mtd></mtr><mtr><mtd><mi mathvariant="bold">M</mi></mtd></mtr><mtr><mtd><mi mathvariant="bold">N</mi></mtd></mtr></mtable></mfenced><mspace width="3em" /><mi>q</mi><mfenced><mi>t</mi></mfenced><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi>x</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>y</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>z</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>φ</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>θ</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>ψ</mi><mfenced><mi>t</mi></mfenced></mtd></mtr></mtable></mfenced></mrow></math><img file="EP1990609B1_D0009.tif" /></maths><ul id="ul0003" list-style="none" compact="compact"><li>X, Y, Z = amplitudes of surge, sway and heave forces</li><li>K, M, N = amplitudes of roll, pitch and yaw moments</li><li><i>w_e</i> = frequency of wave encounter and</li><li><i>x(t), y(t),</i> z(t) = surge, sway and heave motions <i>ϕ(t), θ(t),</i> ψ<i>(t)</i> = variations or roll, pitch and yaw orientations with respect to the equilibrium axes.</li></ul>

The origin of the body axis in the ship for the sea keeping equations is usually taken at the point of trisection of the midship section, longitudinal plane of symmetry and the waterplane. In general, this origin does not coincide with the center of mass. However, for simplification, it may be assumed that the ship, with lateral symmetry, has a center of mass coincident with the origin of the body axes at the point of trisection. In this event the symmetric 6 x 6 generalized mass matrix m is: <maths id="math0010" num=""><math display="block"><mrow><mi mathvariant="bold">m</mi><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi>m</mi></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mi>m</mi></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mi>m</mi></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>I</mi><mrow><mi>x</mi><mi>x</mi></mrow></msub></mtd><mtd><mn>0</mn></mtd><mtd><mo>−</mo><msub><mi>I</mi><mrow><mi>x</mi><mi>z</mi></mrow></msub></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>I</mi><mrow><mi>y</mi><mi>y</mi></mrow></msub></mtd><mtd><mn>0</mn></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>−</mo><msub><mi>I</mi><mrow><mi>x</mi><mi>z</mi></mrow></msub></mtd><mtd><mn>0</mn></mtd><mtd><msub><mi>I</mi><mrow><mi>z</mi><mi>z</mi></mrow></msub></mtd></mtr></mtable></mfenced></mrow></math><img file="EP1990609B1_D0010.tif" /></maths> where m is the mass of the ship, <i>I_xx</i>, <i>I_yy,</i> and <i>I_zz</i> are the principal moments of inertia and <i>I_xz</i> is a product of inertia that is zero if the ship has fore- and aft-symmetry.

The elements of 6 x 6 matrix <b>a</b> are a combination of hydrodynamic forces which are in phase with the acceleration of the ship. By analogy with the mass matrix, <b>a</b> is referred to as the 'added mass matrix' with (<b>m</b> + <b>a</b>) is the virtual mass matrix. Physically it may be described very loosely as the quantity of fluid in the vicinity of the ship which is accelerated with the ship. On the other hand, the elements of the 6 x 6 damping matrix <b>b</b> are a combination of hydrodynamic forces which are in phase with the velocity of the ship and are associated with energy dissipation. In an ideal fluid, energy can only be dissipated by the generation and propagation of waves in the free surface.

For a laterally symmetric ship, the added mass and damping matrices have the forms: <maths id="math0011" num=""><img file="EP1990609B1_D0011.tif" /></maths> where, for example, <i>K</i>ϕ̈, <i>K</i>ψ̈ are the added hydrodynamic roll moments associated with the roll angular acceleration ϕ¨<i>(t)</i> and with angular yaw acceleration ψ̈<i>(t)</i> respectively. The quantities Z_ź and Z_θ̇ are the hydrodynamic damping forces associated with the heave velocity <i>ż(t)</i> and with pitch angular velocity θ̇<i>(t)</i>, respectively.

Finally the 6 x 6 restoring matrix c accounts for the hydrostatic contributions, although there may be some small additional dynamic effects if the center of mass and origin of the body axes do not coincide. There then exist restoring moments associated with the center of mass of the ship in an angular displacement of the ship. For a harmonically oscillating ship, it is seen that the total hydrodynamic force in phase with the displacement is (-ω_e²_a + c).

In effect, there therefore exists some arbitrariness in the definitions of the matrices <b>a</b> and <b>c</b>. On the assumption that c is due to hydrostatic effects only, however, the definitions become unique. For the surface ship, the restoring matrix then has the form: <maths id="math0012" num=""><img file="EP1990609B1_D0012.tif" /></maths> where, for example, Z₌ is the heave restoring force associated with a unit heave displacement, <i>z(t)</i> etc. One outcome of the use of equilibrium axes, instead of body axes, is removal of the explicit symbol <i>U</i> from the equations of motion. The quantity <i>U does</i> appear in equations used in the analysis of directional stability and control.

In general, the matrices <b>a</b>, <b>b</b> and c are supposed constant with respect to time but, on the assumption that only the response that is proportional to <i>e^iωe^t</i> is of interest, some elements are dependent on the frequency of wave encounter ω_e. Substituting the foregoing matrices into the initial differential equation yields two sets of coupled equations. One set involves the symmetric motions of surge, heave, pitch and the other involves the antisymmetric motion of roll, sway and yaw. By assuming that the surge motions are an order smaller than the other symmetric motions, a case can be made for simplifying the analysis to the two coupled differential equations involving the pitch and heave motions. In effect, the disturbances of the laterally symmetric ship have been divided into two categories: <ol id="ol0001" compact="compact" ol-style=""><li>1. a) equations of small symmetric departures from a steady reference motion.</li><li>2. b) equations of small antisymmetric departures from a steady reference motion.</li></ol>

The equations describing the coupled motions for heave and pitch due to sea keeping effects are seen to be of the form: <maths id="math0013" num=""><math display="block"><mrow><mfenced open="[" close="]"><mtable><mtr><mtd><mi>m</mi><mo>+</mo><msub><mi>Z</mi><mrow><mover><mi>z</mi><mrow><mo>‾</mo></mrow></mover></mrow></msub></mtd><mtd><msub><mi>Z</mi><mrow><mover><mi>θ</mi><mrow><mo>‾</mo></mrow></mover></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>M</mi><mrow><mover><mi>z</mi><mrow><mo>‾</mo></mrow></mover></mrow></msub></mtd><mtd><msub><mi>I</mi><mi mathvariant="italic">yy</mi></msub><mo>+</mo><msub><mi>M</mi><mrow><mover><mi>θ</mi><mrow><mo>‾</mo></mrow></mover></mrow></msub></mtd></mtr></mtable></mfenced><mfenced open="[" close="]"><mtable><mtr><mtd><mover><mi>z</mi><mrow><mo>¨</mo></mrow></mover><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mover><mi>θ</mi><mrow><mo>¨</mo></mrow></mover><mfenced><mi>t</mi></mfenced></mtd></mtr></mtable></mfenced><mo>+</mo><mfenced open="[" close="]"><mtable><mtr><mtd><msub><mi>Z</mi><mrow><mover><mi>z</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub></mtd><mtd><msub><mi>Z</mi><mrow><mover><mi>θ</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub></mtd></mtr><mtr><mtd><msub><mi>M</mi><mrow><mover><mi>z</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub></mtd><mtd><msub><mi>M</mi><mrow><mover><mi>θ</mi><mrow><mo>˙</mo></mrow></mover></mrow></msub></mtd></mtr></mtable></mfenced><mfenced open="[" close="]"><mtable><mtr><mtd><mover><mi>z</mi><mrow><mo>˙</mo></mrow></mover><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mover><mi>θ</mi><mrow><mo>˙</mo></mrow></mover><mfenced><mi>t</mi></mfenced></mtd></mtr></mtable></mfenced><mo>+</mo><mfenced open="[" close="]"><mtable><mtr><mtd><msub><mi>Z</mi><mi>z</mi></msub></mtd><mtd><msub><mi>Z</mi><mi>θ</mi></msub></mtd></mtr><mtr><mtd><msub><mi>M</mi><mi>z</mi></msub></mtd><mtd><msub><mi>M</mi><mi>θ</mi></msub></mtd></mtr></mtable></mfenced><mfenced open="[" close="]"><mtable><mtr><mtd><mi>z</mi><mfenced><mi>t</mi></mfenced></mtd></mtr><mtr><mtd><mi>θ</mi><mfenced><mi>t</mi></mfenced></mtd></mtr></mtable></mfenced><mo>=</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mi>Z</mi></mtd></mtr><mtr><mtd><mi>M</mi></mtd></mtr></mtable></mfenced><msup><mi>e</mi><mrow><msup><mi mathvariant="italic">iwe</mi><mi>t</mi></msup></mrow></msup></mrow></math><img file="EP1990609B1_D0013.tif" /></maths>

The various coefficients Z_z¨, Z_θ́, <i>M_z̈</i> etc., may be derived from experiment or by analytical means. Table I shows the coefficients as derived from the modified strip theory of Gerritsma and Beukelman and from the velocity potential approach of <nplcit id="ncit0004" npl-type="s"><text>Vugts, and Salvesen, et al. as presented in Price and Bishop</text></nplcit>. In Table I, <i>m(x)</i> is the two dimensional sectional added mass per unit length and N(x) is the two dimensional damping coefficient per unit length for heave while <i>B(x)</i> is the sectional beam at the waterline. The position coordinate <i>x^A</i> added mass <i>m^A</i> and damping coefficient <i>N^A</i> are associated with the ship's aftermost section. <tables id="tabl0001" num="0001"><table frame="all"><title>Table I</title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="21mm" /><colspec colnum="2" colname="col2" colwidth="75mm" /><colspec colnum="3" colname="col3" colwidth="68mm" /><thead><row><entry valign="top">Coefficient</entry><entry valign="top">Modified strip theory of Gerritsma and Beukelman</entry><entry valign="top">Theory of Vugts and Salvesen et al.</entry></row></thead><tbody><row><entry>Z_z</entry><entry>∫ <i>m(x)dx</i></entry><entry><maths id="math0014" num=""><math display="block"><mrow><mo>∫</mo><mi>m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>N</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0014.tif" /></maths></entry></row><row><entry>Z_z</entry><entry>∫ <i>N(x)dx</i> + <i>Um^A</i></entry><entry>∫ <i>N(x)dx</i>+<i>Um^A</i></entry></row><row><entry>Z_z</entry><entry><i>pg</i> ∫ <i>(x)dx</i></entry><entry>same</entry></row><row><entry>Z_θ</entry><entry><maths id="math0015" num=""><math display="block"><mrow><mo>−</mo><mo>∫</mo><mi mathvariant="italic">xm</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>N</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>m</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0015.tif" /></maths></entry><entry><maths id="math0016" num=""><math display="block"><mrow><mo>∫</mo><mi mathvariant="italic">xm</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>N</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>N</mi><mi>A</mi></msup><mo>−</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>m</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0016.tif" /></maths></entry></row><row><entry>Z_θ</entry><entry>- ∫ <i>xN(x)dx</i>+<i>U</i>∫ <i>m(x)dx</i>-<i>Ux^Am^A</i></entry><entry><maths id="math0017" num=""><math display="block"><mrow><mo>−</mo><mo>∫</mo><mi mathvariant="italic">xN</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><mo>∫</mo><mi>m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msup><mi>x</mi><mi>A</mi></msup><msup><mi>m</mi><mi>A</mi></msup><mo>−</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>N</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0017.tif" /></maths></entry></row><row><entry>Z_θ</entry><entry><i>- pg</i> ∫ <i>xB</i>(<i>x</i>)<i>dx</i></entry><entry>same</entry></row><row><entry>M_z</entry><entry>- ∫ <i>xm(x)dx</i></entry><entry><maths id="math0018" num=""><math display="block"><mrow><mo>−</mo><mo>∫</mo><mi mathvariant="italic">xm</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>N</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>N</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0018.tif" /></maths></entry></row><row><entry>M_z</entry><entry>- ∫ <i>sN(x)dx</i>-<i>Ux^Am^A -U</i> ∫ <i>m(x)dx</i></entry><entry>same</entry></row><row><entry>M_z</entry><entry><i>- pg</i> ∫ <i>xB</i>(<i>x</i>)<i>dx</i></entry><entry>same</entry></row><row><entry><i>M</i>_θ</entry><entry><maths id="math0019" num=""><math display="block"><mrow><mtable columnalign="left" width="auto"><mtr><mtd><mo>∫</mo><msup><mi>x</mi><mn>2</mn></msup><mi>m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi mathvariant="italic">xN</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo></mtd></mtr><mtr><mtd><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>m</mi><mi>A</mi></msup></mtd></mtr></mtable></mrow></math><img file="EP1990609B1_D0019.tif" /></maths></entry><entry><maths id="math0020" num=""><math display="block"><mrow><mo>∫</mo><msup><mi>x</mi><mn>2</mn></msup><mi mathvariant="italic">m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>m</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mfenced><msup><mi>x</mi><mi>A</mi></msup></mfenced><mn>2</mn></msup><msup><mi>N</mi><mi>A</mi></msup><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>m</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0020.tif" /></maths></entry></row><row><entry><i>M</i>_θ</entry><entry>∫ <i>x² N</i>(<i>x</i>)<i>dx</i> + <i>U</i> (<i>x^A</i>)<i>² m^A</i></entry><entry><maths id="math0021" num=""><math display="block"><mrow><mo>∫</mo><msup><mi>x</mi><mn>2</mn></msup><mi>N</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><mo>∫</mo><mi>N</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msup><mfenced><msup><mi>x</mi><mi>A</mi></msup></mfenced><mn>2</mn></msup><msup><mi>m</mi><mi>A</mi></msup><mo>+</mo><msup><mrow><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover></mrow><mn>2</mn></msup><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>N</mi><mi>A</mi></msup></mrow></math><img file="EP1990609B1_D0021.tif" /></maths></entry></row><row><entry><i>M</i>_θ</entry><entry><i>ρg</i> ∫ <i>x² B</i>(<i>x</i>)<i>^dx</i></entry><entry>same</entry></row><row><entry>Z</entry><entry><maths id="math0022" num=""><math display="block"><mrow><msub><mi>ζ</mi><mn>0</mn></msub><mo>∫</mo><msup><mi>e</mi><mi mathvariant="italic">ikx</mi></msup><msup><mi>e</mi><mrow><mo>−</mo><mi mathvariant="italic">kT</mi></mrow></msup><mo>*</mo><mfenced open="[" close="]" separators=""><mi mathvariant="italic">ρgB</mi><mfenced><mi>x</mi></mfenced><mo>−</mo><mi>ω</mi><mfenced open="{" close="}" separators=""><msub><mi>ω</mi><mi>e</mi></msub><mi>m</mi><mfenced><mi>x</mi></mfenced><mo>−</mo><mi mathvariant="italic">iN</mi><mfenced><mi>x</mi></mfenced></mfenced></mfenced><mi mathvariant="italic">dx</mi><mo>+</mo><mi mathvariant="italic">iω</mi><msub><mi>ζ</mi><mn>0</mn></msub><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msup><mi>m</mi><mi>A</mi></msup><msup><mi>e</mi><mrow><msup><mi mathvariant="italic">ikx</mi><mi>A</mi></msup></mrow></msup><msup><mi>e</mi><mrow><mo>−</mo><msubsup><mi mathvariant="italic">kT</mi><mrow><mo>*</mo></mrow><mi>A</mi></msubsup></mrow></msup></mrow></math><img file="EP1990609B1_D0022.tif" /></maths></entry><entry><maths id="math0023" num=""><math display="block"><mrow><mi>same</mi><mo>+</mo><msub><mi>ζ</mi><mn>0</mn></msub><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>2</mn></mrow></msubsup><msup><mi>e</mi><mrow><msup><mi mathvariant="italic">ikx</mi><mi>A</mi></msup></mrow></msup><msup><mi>e</mi><mrow><mo>−</mo><msubsup><mi mathvariant="italic">kT</mi><mrow><mo>*</mo></mrow><mi>A</mi></msubsup></mrow></msup></mrow></math><img file="EP1990609B1_D0023.tif" /></maths></entry></row><row><entry>M</entry><entry><maths id="math0024" num=""><math display="block"><mrow><mo>−</mo><msub><mi>ζ</mi><mn>0</mn></msub><mo>∫</mo><msup><mi>e</mi><mi mathvariant="italic">ikx</mi></msup><msup><mi>e</mi><mrow><mo>−</mo><mi mathvariant="italic">kT</mi></mrow></msup><mo>*</mo><mi>x</mi><mfenced open="[" close="]" separators=""><mi mathvariant="italic">ρgB</mi><mfenced><mi>x</mi></mfenced><mo>−</mo><mi>ω</mi><mfenced open="{" close="}" separators=""><msub><mi>ω</mi><mi>e</mi></msub><mi>m</mi><mfenced><mi>x</mi></mfenced><mo>−</mo><mi mathvariant="italic">iN</mi><mfenced><mi>x</mi></mfenced><mo>−</mo><mi mathvariant="italic">i</mi><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><mi mathvariant="italic">m</mi><mfenced><mi>x</mi></mfenced></mfenced></mfenced><mi mathvariant="italic">dx</mi><mo>−</mo><mi mathvariant="italic">i</mi><msub><mi>ζ</mi><mn>0</mn></msub><mi mathvariant="italic">ω</mi><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msup><mi>x</mi><mi>A</mi></msup><msup><mi>m</mi><mi>A</mi></msup><msup><mi>e</mi><mrow><msup><mi mathvariant="italic">ikx</mi><mi>A</mi></msup></mrow></msup><msup><mi>e</mi><mrow><mo>−</mo><msubsup><mi mathvariant="italic">kT</mi><mrow><mo>*</mo></mrow><mi>A</mi></msubsup></mrow></msup></mrow></math><img file="EP1990609B1_D0024.tif" /></maths></entry><entry><maths id="math0025" num=""><math display="block"><mrow><mtable columnalign="left" width="auto"><mtr><mtd><mi>same</mi><mo>−</mo><msub><mi>ζ</mi><mn>0</mn></msub><mo>∫</mo><msup><mi>e</mi><mi mathvariant="italic">ikx</mi></msup><msup><mi>e</mi><mrow><mo>−</mo><msubsup><mi mathvariant="italic">kT</mi><mrow><mo>*</mo></mrow><mi>A</mi></msubsup></mrow></msup><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><mi mathvariant="italic">ωN</mi><mfenced><mi>x</mi></mfenced><mi mathvariant="italic">dx</mi></mtd></mtr><mtr><mtd><mo>−</mo><mi>ω</mi><msub><mi>ζ</mi><mn>0</mn></msub><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><msubsup><mi>ω</mi><mi>e</mi><mrow><mo>−</mo><mn>1</mn></mrow></msubsup><msup><mi>x</mi><mi>A</mi></msup><msup><mi>N</mi><mi>A</mi></msup><msup><mi>e</mi><mrow><msup><mi mathvariant="italic">ikx</mi><mi>A</mi></msup></mrow></msup><msup><mi>e</mi><mrow><mo>−</mo><msubsup><mi mathvariant="italic">kT</mi><mrow><mo>*</mo></mrow><mi>A</mi></msubsup></mrow></msup></mtd></mtr></mtable></mrow></math><img file="EP1990609B1_D0025.tif" /></maths></entry></row></tbody></tgroup></table></tables>

The quantity T. in the force and moment amplitudes in Table I is defined as: <maths id="math0026" num=""><math display="block"><mrow><msub><mi>T</mi><mrow><mo>*</mo></mrow></msub><mo>=</mo><mfrac><mn>1</mn><mi>k</mi></mfrac><mn>1</mn><mi>n</mi><mfenced open="{" close="}" separators=""><mn>1</mn><mo>−</mo><mfrac><mrow><mn>2</mn><mi>k</mi></mrow><mrow><mi>B</mi><mfenced><mi>x</mi></mfenced></mrow></mfrac><munderover><mrow><mo>∫</mo></mrow><mrow><mo>−</mo><mi>T</mi></mrow><mn>0</mn></munderover><mi>y</mi><msup><mi mathvariant="italic">e</mi><mi mathvariant="italic">kz</mi></msup><mi mathvariant="italic">dz</mi></mfenced></mrow></math><img file="EP1990609B1_D0026.tif" /></maths>

While T is the draught of the ship. A simplification to this expression is made by equating T. the mean draught at each section, i.e. <maths id="math0027" num=""><math display="block"><mrow><msub><mi>T</mi><mrow><mo>*</mo></mrow></msub><mfrac><mrow><mi>Area of cross</mi><mo>−</mo><mi>section</mi></mrow><mi>sectional waterline beam</mi></mfrac></mrow></math><img file="EP1990609B1_D0027.tif" /></maths>

This approximation holds for sections with regular shaped hulls, but care must be taken when considering, for example, a bulbous bow, sine otherwise errors may be introduced in the evaluated wave exciting force and moments.

The actual amplitude and frequency of the waves experienced by the vessel when underway, can be calculated iteratively using numerical analysis. In particular, changes in the measured GPS altitude and the time period between such changes may be used to approximate the wave motion for input in to the state equations. As an alternative the vertical accelerations may be measured directly from the INS unit to obtain the wave approximation.

The complete set of calm water and sea keeping performance equations can thus be solved numerically by the present invention to describe vessel motion and performance and to predict an anticipated track or path if desired. In one preferred embodiment of the invention, navigation system 14 is utilized for performance of these calculations. The vessel unique data required to obtain the matrices of calm water and sea keeping state space coefficients may be directly input into system 10 at the time of installation aboard the ship. Optionally, system 10 may be loaded with a set of data for various classes and/or designs of vessels with this data stored in a look up table memory within system 10 and accessible by navigation system 14. When system 10 is installed aboard as a line replaceable unit or other hardware device, the category of vessel can then be selected by a programming pin.

Those of ordinary skill in the art will also recognize that the state equations may be integrated over a relatively longer period of time to obtain the kinematics of the ship and obtain a projected track and other predictions of ship performance. Those of skill in the art will further recognize that other formulations of equations describing vessel motion, may also be utilized with the present invention and the invention is not limited to the specific state space models described above. In addition many commercial software packages exist that model ship performance and may be adapted for use with the present invention. One such package called, SIMAN, offered by MARINTEK (<u>www.marintek.sintef.no</u>) of Norway can predict all International Marine Organization (IMO) maneuvers and operational capabilities for single screw/single rudder and twin screw/twin rudder common merchant monohull displacement ships. In addition, SIMAN can calculate crabbing, station keeping, under the influence of wind, wave and current forces.

Any of the methods described above for predicting the ship motion may also be used to predict ship performance, for example, in a turning maneuver and or stopping distances under various speed, rudder, and screw configurations. The turning performance and stopping distance data can further be utilized to calculate an avoidance maneuver as will also be described below.

The International Marine Organization (IMO) has also developed a set of standards for turning and stopping based on ship length. These performance standards may be used to ascribe nominal valves to ship performance based on ship length when the actual values are not known. <figref idref="f0004">Figs. 4 and 5</figref> illustrates the displacements for the standard IMO maneuvers. Specifically <figref idref="f0004">Fig. 4</figref> illustrates a turning circle and <figref idref="f0004">Fig. 5</figref> illustrates a stopping maneuver. The coordinate systems are as given in <figref idref="f0003">Figs. 3A and 3B</figref>. Specifically, the IMO resolution A.571(18) states that the maneuverability of a ship will be considered satisfactory if the following criteria are met: <ul id="ul0004" list-style="bullet" compact="compact"><li><i>Turning ability:</i> the advance should not exceed 4.5 ship lengths and the tactical diameter should not exceed 5 ship lengths in the turning circle maneuver.</li><li><i>Stopping ability:</i> the track reach in the aster stopping test should not exceed 15 ship lengths.</li></ul>

Thus in the absence of ship specific performance data useful for solving the equations of motion provided above, the maximum expected displacements for collision avoidance can generically be assumed to be as follows: <ul id="ul0005" list-style="bullet" compact="compact"><li>Along G-X - distance to full stop = 15L;</li><li>Along G-Y - tactical diameter at 180 degrees change of heading during a turn = 5L</li></ul>

For large vessels, wind may have an impact on vessel performance characteristics especially when turning. The influence of wind on ship performance can be incorporated into the state space equations as additional environmental terms in the manner taught by Wilson et al.

Optionally, each ship typically has a set of advance and transfer tables that describe the forward and lateral distances traveled by the ship in a 90° turn at various speeds. These values are usually determined during sea trials of the vessel by performing turning circles at various speeds. The advance and transfer values for each vessel may be loaded into system 10 at time of installation for later access by navigation system <b>14</b>.

<i>3.0 Coastal, Waterway and Port Data Bases</i>

The present invention, for example in system <b>10</b> memory, stores information concerning the position, depth and height of terrain and obstacles for different locations on earth. In this application terrain is used interchangeably to mean both geographic and man made features and obstacles. This information is usually stored in the first memory device as a latitude and longitude with an associated depth or clearance height referenced to mean sea level. There are many different ways and formats in which the position and depth information for the terrain and obstacles could be stored in the first memory device. Data from which to create these databases may be obtained from a variety of sources including NOAA Bathametrics data and/or from digitizing nautical charts.

In one embodiment, in order to save storage space, the terrain and obstacles may be represented by geometric shapes, such as cones, that are superimposed over the terrain and obstacles. These geometric shapes have a height that corresponds approximately to the height of obstacle. As such, each terrain feature or obstacle in the memory device may be defined by a position, height, and width. For example, a mountain or mountain range may be represented by a cone or series of cones illustrating the peak of the mountain or the base of the cone represents the base of the mountain. This method of data storage is described in greater detail in <patcit id="pcit0019" dnum="US4646244A"><text>U.S. Patent No. 4,646,244 to Bateman et al.</text></patcit>, "Terrain Advisory System" incorporated herein by reference. As illustrated in the Bateman '244 patent, this method of data storage allows for compaction of the data such that smaller storage devices may be utilized.

In a preferred embodiment of the invention, however, the port data and coastal/waterway data are separated into two different data bases <b>26</b> and <b>24</b>, respectively, as illustrated in <figref idref="f0005 f0006 f0007">Figs. 6-8</figref>. Such a configuration allows either of the data bases <b>24</b> or <b>26</b> to be updated without the need to update the other.

Port data base <b>26</b> contains various types of information relating to ports, such as channel approaches, buoys, docks, underwater features and obstructions, tides and designation data. Data base <b>24</b> is preferably structured to provide varying resolutions of terrain data as a function of the topography of the terrain, as well as water depth. For example, a relatively high resolution can be provided close to port and to shore while in deeper water, a coarser resolution is sufficient.

Data bases <b>24</b> and <b>26</b> may be formed from semiconductor storage devices well known to those of skill in the art such as, for example: flash erasable programmable read only memory (ROM) devices, such as a flash EEPROM; or mini hard disk drives, and/or PCMCIA cards which could take advantage of known data compression techniques to reduce the amount of storage space required and also promote easy data retrieval by search algorithm <b>29.</b>

<figref idref="f0005 f0006 f0007">Figs. 6 through 8</figref> illustrate the organization of data bases <b>24</b> and <b>26.</b> In <figref idref="f0005">Fig. 6</figref> the world is divided into a plurality of latitude bands <b>50,</b> for example each about 4° wide around the equator such that each longitudinal segment 52 is about 256 x 256 nautical miles. In order to maintain a relatively constant segment size, the number of longitudinal segments <b>52</b> per latitude band <b>50</b> are reduced closer to the poles.

Since the number of latitude bands <b>50</b> and the number of longitudinal segments <b>52</b> per latitude band 50 is fixed, determination of the particular segment corresponding to the current vessel position is readily determined. For example, the vessel current latitude X is used to determine the latitude band number. Next, the number of longitudinal segments <b>52</b> associated with that band <b>50</b> is determined either by way of a LOOK-UP table or by calculation. Once the number of longitudinal segments <b>52</b> in the particular latitude band <b>50</b> of interest is determined, the current longitudinal position Y of the vessel can be used to readily determine the longitudinal segment number.

The minimum data associated with each longitudinal segment <b>52</b> corresponds to the point closest to the surface as defined by the mean sea level within that segment. As mentioned above, each of the segments <b>52</b> is approximately 256 x 256 nautical miles. As shown in <figref idref="f0006">Fig. 7</figref>, longitudinal segments <b>52</b> are broken down into various subsquares to provide varying levels of resolution. For example, each segment <b>52</b> may be broken down into a plurality of subsquares <b>54,</b> each subsquare <b>54</b> being 64 x 64 nautical miles to provide a very coarse resolution. The subsquares <b>54,</b> can, in turn, be further subdivided into a number of subsquares <b>56,</b> for example, each 16x16 nautical miles, to provide a coarse resolution. These subsquares <b>56,</b> in turn, can be subdivided into a plurality of subsquares <b>58,</b> for example each 4 x 4 nautical miles, to provide a medium resolution. The subsquare <b>58</b> can also be broken down into a plurality of subsquares <b>60,</b> for example 1 x 1 nautical miles, to provide a fine resolution. In the vicinity around ports, it may even be desirable to break down the subsquares <b>60</b> down into smaller subsquares <b>62</b> to provide even finer resolution, for example % x % nautical miles. These segments may be further subdivided as needed to provide the desired resolution.

As shown in <figref idref="f0007">Fig. 8A</figref>, the data associated with each longitudinal segment <b>52</b> comprises a header <b>65</b> which includes a multiple data byte <b>66</b> which includes the reference depth which corresponds to the point of least depth for all the subsquares within the segment, which assumes that the highest point in a square is representative of the entire square elevation. Multiple data byte <b>66</b> may also include a flag to indicate when no further subdividing is required for certain geographical areas, for example, deep water areas. To facilitate updating the data base on a piecewise basis, multiple data bye <b>66</b> may also contain a flag bit or code indicating that data corresponding to further subdivisions does not exist for a particular segment <b>52</b> containing a code indicating that no map data exists in the segment.

For areas having significant underwater terrain and areas in the vicinity of a port, the longitudinal segments <b>52</b> are subdivided as discussed above. In such a situation, the stored data would include a 2-byte mask word <b>68,</b> which points to the subsquares having different depth data. For example, as shown in <figref idref="f0007">Fig. 8A</figref>, the 2-byte mask word <b>68</b> is illustrated with a pointer in the box <b>15</b> within the subsquare <b>54</b> within the longitudinal segment <b>52,</b> which represents a different depth which points to the next finer layer of resolution as discussed above. The subsquares each include a header <b>70</b> including a mask as described above to enable a pointer for each subsquare having a different depth to point to the next finer layer until the finest resolution level desired is reached as shown.

The data base structure provides for flexibility as to resolution required and can be constructed on a piecewise basis at different times. As such, the structure contains the entire framework necessary to add new data or modify existing data without changing any of the software. The size of the data base is proportional to the resolution and the size of the area to be covered.

Alternatively, the world may be divided into a plurality of, for example, 1° x 1° map files or cells <b>51</b> as shown in <figref idref="f0007">Fig. 8B</figref>. The various map files <b>51</b> may be formed with variable resolution. More particularly, each of the map files may be subdivided into a plurality of subcells <b>53</b> with the most significant terrain depth in each subcell indicated, with the resolution of all of the subcells within a particular map file being of the same resolution.

The size of the subcells <b>53</b> is varied to provide varying degrees of resolution. For example, for relatively high resolution, the size of the subcells <b>53</b> may be selected as either 15 x15 arc seconds or 30 x 30 arc seconds. The size of the subcells <b>53</b> may also be varied as a function of the terrain in particular coastal or waterway areas. The size of the subcells <b>53</b> may also be varied as a function of the distance to the nearest port or shoreline.

As discussed below and as illustrated in <figref idref="f0008">Fig. 9</figref>, the data base may be compressed by a compression algorithm and stored in a flash read only memory (ROM). Various compression algorithms already known to those of skill in the art are suitable for this application. The compression algorithm does not form a part of the present invention.

In order to simplify computation, each of the map files includes a header <b>55,</b> which includes, <i>inter alia,</i> the resolution of the particular map file <b>51</b> as well as the location of one or more corners, for example, the northwest and southwest corners. The headers <b>55</b> as well as the map files <b>51</b> are discussed in more detail below and illustrated in more detail in <figref idref="f0009">Fig. 10</figref>.

<i>4.0 Alerting Envelope Logic</i>/<i>Avoidance Logic</i>

Information about the ship position and dynamics as described in Section 2.0 are compared to the terrain and obstacle information according to an alert logic designed to alert the crew to potential collision hazards. The alert logic can take one of several forms as described in greater detail in the following sections. Use of the various alert logic schemes is not necessarily mutually exclusive, and can coexist. In alternative embodiments of the invention, the present invention may further include an avoidance guidance logic that advises the crew what actions to take once a potential collision hazard has been detected by the alert logic. The avoidance logic is also described in greater detail below.

The general basis for the design of the grounding/obstacle avoidance logic is to provide sufficient information to the vessel's crew to avoid groundings or collisions. The alerting logic is preferably consistent with the following objectives: <ol id="ol0002" compact="compact" ol-style=""><li>1. (a) Sufficient lateral and under-keel clearance is maintained between <i>current</i> vessel position and surrounding obstacles;</li><li>2. (b) <i>Short-term</i> lateral and vertical clearances will remain acceptable;</li><li>3. (c) The <i>initial</i> position at which clearance becomes unacceptable is evident (should the vessel be heading towards a potential obstacle); and</li><li>4. (d) The <i>last</i> position at which a standard maneuver would prevent grounding if the path remains unchanged in condition (c) is identified above.</li></ol>

Condition (a) is preferably satisfied with reactive system modes, whereas (b)-(d) can be satisfied by predictive modes. These modes are discussed in greater detail below. Human factors data from collision avoidance studies has shown that predictive type information improves operator performance with respect to averting collisions.

<i>4.1 Reactive Alerting</i>

A first embodiment of the invention utilizes a sonar device to sense the depth of underwater obstructions beneath the vessel. The invention evaluates the time rate of change of the depth soundings and does not require input from the terrain database. When the time rate of change exceeds a predetermined value, an alert is provided to the crew. The alert may be aural, visual or both.

Such a device as a tool to avoid groundings is mostly applicable to submarines and is less applicable to large surface vessels since the time rate of change of the terrain below a surface going vessel may be far in excess of the surface vessel's ability to conduct a turn for avoidance. Furthermore, terrain such as shallow sand bars and other uncharted obstacles may appear suddenly supplying little time for avoidance. Grounding avoidance may be further complicated when operations in narrow channels compromises maneuverability. While it may appear pointless to alert the crew to an inevitable grounding, the alert may have a significant positive impact on damage control, crew preparedness and other proactive management of the grounding incident.

<figref idref="f0009">Fig. 11</figref> shows a warning envelope based on insufficient terrain clearance when the vessel is moving in shallow or coastal waters, for example when in a river channel or approaching a port or harbor. In the curve of <figref idref="f0009">Fig. 11</figref> an audible "TOO CLOSE GROUNDING" warning is given when the vessel enters region 150 of the graph. A warning light or other visual warning indication may also be provided.

<i>4.2 Predictive Alerting</i>

In the previous section, the alerting scheme is reactive and detects encroaching terrain. Predictive alerts are possible when the position of the vessel is known relative to the position of the proximate terrain. The following sections detail various predictive alerting schemes which can be utilized with the present invention.

<i>4.2.1 Predictive Alerts Based On Standard Maneuvers</i>

In one embodiment of the invention, a predictive alert envelope has dimensions based on the displacements required to execute an evasive maneuver. The terrain data is compared to the boundaries of this envelope and if any terrain data is found to be located within the boundaries of the envelope, an alert warning is given of a potential hazard.

This embodiment of a predictive alerting scheme constructs protection envelopes in the direction of travel of the vessel based upon the last position from which a standard IMO maneuver can be executed to prevent grounding or collision with obstacles. This alerting scheme, while applicable to all cases, has the advantage of being readily constructed for all vessels since only the ship length need be known to define the envelope dimensions. Based on the IMO standard maneuvers as described in Section 2.0 and <figref idref="f0004">Figs. 4 and 5</figref>, the maximum expected displacements for collision avoidance are: (1) the distance required for a full stop along axis G-X of <figref idref="f0003">Fig 3</figref>; and (<figref idref="f0002">2</figref>) the distance equal to the tactical diameter for 180° change of heading.

The hatched portion of <figref idref="f0009">Fig. 12</figref> defines the resulting lateral dimensions of the alerting. The semi-circular path that is not cross-hatched represents the path followed during a turn where the diameter is equivalent to the maximum allowable tactical diameter and is therefore excluded from the alerting envelope. Note that a slightly higher safety margin may be achieved if the latter semicircular areas adopted a diameter equal to the IMO upper limit of 4.5 for the advance at 90 degrees heading.

One potential mechanism to provide two levels of alerting, namely caution and warning, is depicted in <figref idref="f0010">Fig. 13</figref>. The first alert (caution) is provided at the <i>initial</i> position when clearance becomes unacceptable if the vessel is heading towards a potential obstacle. The second alert (warning) is provided at a distance that is equivalent to at least twice the advance at 90 degrees change of heading, and it therefore allows for a safe turn away from obstacles. Note that increasing the magnitude of the entire look-ahead distance may increase the probability of false/nuisance alerts.

<figref idref="f0010">Figs.14-15</figref> describe the dimensioning of the protection envelope in the vertical plane. As known to those of skill in the art, in some ports an under-keel clearance on the order of 2 ft is permissible. The minimum permissible clearance thus has a minimum of 2 feet and increases linearly in the longitudinal direction as depicted in <figref idref="f0010">Figure <b>14</b></figref>.

The envelope of <figref idref="f0010">Figs. 13 and <b>14</b></figref> are especially useful when cruising or for operations in unconfined areas. For port/harbor type operations the under-keel clearance envelope is preferably modified as shown in <figref idref="f0010">Fig. 15</figref>. The condition of being in a port/harbor operation can be determined by comparing the ship's position to known ports/harbors or riverways stored in the terrain data base.

In those areas (including ports) where the vessel is constrained to maneuver in narrow channels, the possibility may not exist to execute a full turning circle to avoid potential obstacles. This condition implies that it may be desirable to reduce the width of the lateral warning envelope presented in <figref idref="f0010">Fig. 13</figref> in those instances. For initial turn and full stop maneuvers the side reach magnitude is generally less than one ship length. The lateral alerting envelope is thus modulated accordingly and is as depicted in <figref idref="f0010">Figure 16</figref>. Note that the as the ability to perform a full turn does not exist in a narrow channel, the entire envelope is based on a stopping maneuver and only a single alert (warning) is generated by this envelope. In cases where the channel width is close to or less than 2L, a further reduction of envelope width is preferable, the exact requirements being dictated by local considerations.

The envelopes described in <figref idref="f0009 f0010">Figs. 12-16</figref> above can also be applied to verify clearance beneath overhead obstruction such as bridges. In such an application the envelope retains the plan view dimensions for the given location as discussed in connection with <figref idref="f0009">Figs. 12</figref> , <figref idref="f0010">13 and 16</figref>. The envelope vertical profile, however, can be set at some fixed, nominal value, for example 0.5 feet and need not be reconfigured as a function of location.

<i>4.2.2 Geometric Envelope Predictive Alerts</i>

In an alternative embodiment of the invention the predictive envelope is based on a constant time to impact. The envelope can be defined around each terrain feature, or optionally, with reference to the marine vessel itself. In this instance, whenever the marine vessel track or marine vessel envelope contacts the surface defining the terrain feature a caution and/or warning alert is given. Such a system has the advantage that any warning time could be selected. For purposes of illustration, depiction of the terrain is described with reference to the teaching of the Bateman 4,646,244 patent. The Bateman 4,646,244 patent is incorporated herein by reference for all purposes. Furthermore, in some instances, it has been found that a constant time to impact envelope is too sensitive and may cause nuisance warnings. Consequently, it has been found advantageous to modify the constant time to impact to make it more sensitive when the vessel is heading directly at terrain and less sensitive when the vessel is merely passing by the terrain.

<figref idref="f0011">Figs. 17, 18 and 19</figref> illustrate the creation of a constant time to impact envelope according to oneembodiment of the present invention. Specifically, <figref idref="f0011">Fig. 17</figref> illustrates a cone <b>244</b> defining a terrain feature or obstacle that is being approached by the marine vessel <b>100.</b> The distance that the protection envelope extends is governed by the desired warning time to impact. In one embodiment the envelope may be constructed about the terrain feature as represented by cone <b>244.</b> For example, for a marine vessel traveling at a high speed, the boundary <b>244</b> of the envelope surrounding the terrain extends further from the terrain than for a marine vessel traveling at low speeds. In addition, the direction of the extension of envelope <b>244</b> from the terrain is also determined by the position and heading of the marine vessel.

The envelope <b>238</b> may also be centered on the marine vessel itself as shown in <figref idref="f0011">Figs. 18 and 19</figref>. In theembodiment of <figref idref="f0011">Figs. 17 and 18</figref>, the envelope <b>244</b> surrounding the terrain remains of fixed geometry and does not vary as a function of distance from the approaching vessel. In <figref idref="f0011">Fig. 17</figref>, envelope <b>239</b> is substantially planar and extends out from vessel <b>100</b> at a depth equivalent to the maximum keel depth. The width of envelope <b>239</b> can be defined by the transfer distance required to complete a turn away from the terrain obstacle.

In <figref idref="f0011">Fig. 18</figref>, envelope <b>239</b> is centered on the vessel track <b>240</b> and extends out to a distance <b>242</b> based on constant time to impact. Boundaries <b>246</b> of envelope 239 expand with distance from the vessel to account for navigation uncertainties in vessel projected position. One possible method of defining side <b>246</b> utilizes the inaccuracies in the prediction of the travel path by differentiating the track signal of the marine vessel to provide a rate of change of track direction over time. Using the rate of change in track and the desired warning time to impact, defines the sides <b>246</b> of the envelope. Envelope <b>239</b> is also planar and centered on the vessel in the direction of travel at a depth equivalent to the maximum keel depth.

The envelopes of <figref idref="f0011">Figs. 17 and 18</figref> may also be anchored to the mast height of the vessel to check for overhead obstruction clearance in a manner similar to that described for underwater terrain. A protection envelope 244 is also constructed about the obstacle. The boundaries of this envelope may also be configured to operate as described in <figref idref="f0011">Fig. 19</figref>.

The desired warning reaction time used to define the envelope length may be based on a distance for the marine vessel to come to a complete stop before colliding with the terrain. This distance is then used as the boundary of the envelope generated about the terrain. Similarly, the desired warning reaction time may be based on the distance required for the marine vessel to make an evasive maneuver with respect to the terrain. In this embodiment, the stored ship performance characteristics are used to define such a maneuver and calculate the warning time. Based on this warning time data, a minimum distance between the terrain and the marine vessel needed to perform an evasive action is ascertained. This minimum distance is used as the boundary of the envelope generated about the terrain.

The protection envelope and the position of the vessel are then compared. If the marine vessel and the terrain are in closer proximity to each other than the area defined by the envelope either both or one of an aural or a visual indication is provided to the crew. The envelopes may also be provided to the display generator. The display illustrates to the crew illustrating the proximity of the marine vessel to the surrounding terrain and alerting visually to the crew of any potential dangers.

<i>4.2.3 Look</i> Ahead/Look <i>Down Predictive Alerts</i>

In an additional embodiment of the invention the alert envelopes are constructed to look down as well as ahead of the vessel. As in the embodiment of Section 4.2.1 the protection envelopes described herein have a configurable dimension in the vertical plane and thus define a volume.

<figref idref="f0012">Fig. 20</figref> illustrates caution and warning envelopes obtained using a look-ahead/look-down envelope. Specifically, the apparatus, methods, and computer program products of the present invention according to this embodiment generate both a caution and a warning envelope, <b>250</b> and <b>252,</b> respectively. The caution warning envelope <b>250</b> is typically generated to provide initial caution alerts to the user of the marine vessel concerning terrain that is proximate to the marine vessel, while the warning envelope <b>252</b> is typically generated to provide a more critical indication to the user that the marine vessel is in immediate danger of colliding with the terrain and obstacles and evasive action is required. An alert is provided to the crew when terrain/obstacles are located within the boundaries of the caution or warning envelopes.

The envelopes generated according to this embodiment of the invention eliminate or reduce the number of nuisance alarms likely to occur. For instance, as illustrated in <figref idref="f0012">Fig. 20</figref>, the caution and warning envelopes typically have a predefined look ahead distances, <b>254</b> and <b>256,</b> that define the distance ahead of the path of the marine vessel in which terrain is analyzed and caution and warning alerts are generated. Furthermore, the caution and warning envelopes also include lower boundaries or terrain clearance floor boundaries respectively that define the depth below the marine vessel for which caution and warning alerts are generated. Further detail on the construction of these boundaries is provided below.

As illustrated in <figref idref="f0012">Fig. 20</figref>, the caution and warning envelopes each have an associated look ahead distance boundary, <b>254</b> and <b>256,</b> respectively, past which caution and warning alerts are not generated. The determination of these look ahead distance boundaries is typically based on the operational characteristics of the marine vessel. Specifically, the look ahead distance values for the caution and warning envelopes are typically selected such that the user of the marine vessel will have sufficient time to note the alert and perform an evasive maneuver. The look ahead distance values are also typically restricted in length to avoid generation of nuisance alarms.

In a preferred embodiment of the invention, the look-ahead distance is equal to 15 ship lengths or the stopping distance of the vessel as discussed in Section 4.2.1. Optionally, the look ahead distance value (LAD) for the caution envelope may be defined as two times the time needed for the vessel to perform a turn at present speed plus an added reaction time (nominally 10 seconds) for the user to note the alert and initiate the turn, each multiplied by the speed of the vessel. <maths id="math0028" num=""><math display="block"><mrow><mi>LAD</mi><mo>=</mo><mover><mi>U</mi><mrow><mo>‾</mo></mrow></mover><mfenced open="[" close="]" separators=""><mfenced separators=""><mn>2</mn><mo>×</mo><mi>turn time</mi></mfenced><mo>+</mo><mi>react time</mi></mfenced><mo>+</mo><mi mathvariant="normal">C</mi></mrow></math><img file="EP1990609B1_D0028.tif" /></maths> where C is a fixed distance constant, e.g. C = 0

The stopping time and turning characteristics of the vessel for use in the calculation of the look ahead distance can be obtained in the manner described in Section 2.0. The LAD may also be provided with a configurable upper and lower limit. For example, for large vessels the limit may be set, for example, at 0.5nm at low speeds (&lt;2kts) and 4nm at cruising speed.

As detailed above, the caution and warning envelopes of the present invention may thus include look ahead distance values based on either the time required to turn the marine vessel or the time required to stop the marine vessel. In some embodiments, however, it may be advantageous to generate separate look ahead distance values, one based on the time to turn the marine vessel and one based on the time to stop the marine vessel. Specifically, depending on the operational parameters of the marine vessel it may take less time to stop the marine vessel than to turn the marine vessel to miss the terrain. For example, if the marine vessel is traveling at a slow speed, turning effectiveness is reduced and it may take less time or distance to stop the marine vessel. As such, in this embodiment, the caution and warning generator generates look ahead distance values based on both the time to turn the marine vessel and to stop the marine vessel and then selects the smaller respective look ahead distance values for both the caution and warning envelopes.

In a preferred embodiment, the look ahead distances <b>254</b> and <b>256</b> of <figref idref="f0012">Fig. 20</figref> extend vertically from a lower value defined by a terrain clearance floor <b>258, 260</b> referenced from hull maximum depth to a height above the water surface. The extent of boundaries <b>254, 256</b> above the surface is at least equivalent to the maximum ship height or similar value to ensure clearance beneath overhead obstacles. As shown in <figref idref="f0012">Fig. 20</figref>, terrain clearance floors, <b>258</b> and 260 are referenced from the hull maximum depth as obtained according to Section 2.0 to provide clearance from underwater terrain and obstructions. The terrain clearance floors relate to a distance ΔH below the marine vessel for which caution and warning alerts concerning underlying terrain are generated.

For marine vessels, the terrain clearance floor may be defined with reference to the shoreline or a closest shallow geographic point. Specifically, when the marine vessel is a considerable distance from the shoreline or a shallow geographic point, the depth of the terrain clearance floor below the marine vessel may be deeper, as there is typically less terrain closer to the bottom of the marine vessel that would create nuisance alarms. However, as the marine vessel approaches a known port or moorage contained in the terrain data base, if the depth ΔH of the terrain clearance floor is not decreased, the approaching terrain near the shoreline or shallow point will create nuisance alarms. As such, the depth of the terrain clearance floor envelopes may be dynamically varied with respect to the marine vessel's proximity to the port such that adequate protection is provided in open waters and channels where collision with terrain is less expected, while nuisance alarms are reduced in moorages and ports where there ocean bottom is rising to meet the land, but where the vessel must nonetheless make way. For example, the terrain clearance floor may be in terms of 5 to 10 feet of clearance when the marine vessel is offshore and decreases from 5 to 2 feet as the marine vessel nears port.

<figref idref="f0012">Fig. 21</figref> illustrates graphically an example of the terrain clearance floor for a caution warning envelope for different distances from port. The horizontal axis of the graph represents the distance from stored moorage, while the vertical axis represents depth ΔH of the terrain clearance floor. As illustrated, there is typically an initial offset distance <b>266</b> between the beginning of the envelope and the moorage. This offset is an added distance that accounts for inaccuracies in the position data associated with the stored position for the moorage and the position data indicated by the navigation system as the current position of the marine vessel. Further, the graph for the terrain clearance floor of this embodiment, includes a first segment <b>268</b> that extends from the offset distance <b>266</b> out to a distance <b>D.</b> Beyond the distance <b>D,</b> the terrain clearance floor has a constant depth ΔH of 10 feet.

In some embodiments of the present invention, the caution and warning envelopes may further include cut-off boundaries to avoid spurious warnings when the marine vessel passes terrain or obstacles at a relatively close distance. Without the cut-off boundaries, alerts would be generated although the terrain is below the marine vessel and no terrain is ahead of the marine vessel. In <figref idref="f0012">Fig. 22</figref>, the cut-off boundary <b>278</b> begins at a predetermined envelope cut-off offset <b>280</b> below the marine vessel and extends in a direction in front of the marine vessel at a predetermined envelope cut-off angle <b>282.</b> The cut-off angle is equal to the angle of the marine vessel plus a configurable predetermined cut-off angle <b>282.</b> For surface operation of a marine vessel, as shown in <figref idref="f0012">Fig. 22</figref>, the cut-off boundary <b>278</b> extends from the cut-off offset <b>280</b> in the direction of the cut-off angle <b>282</b> in the direction of travel of the marine vessel to a point <b>284</b> where it intersects either a caution or warning envelope boundary <b>286.</b> For surface travel, γ is zero. Thus, the cut-off boundary <b>278</b> illustrated in <figref idref="f0012">Fig. 22</figref> extends from the cut-off offset <b>280</b> along an angle equal to the cut-off angle. The boundary for the caution or warning envelope is selected to be the higher of the boundary <b>286</b> or cut-off boundary <b>278.</b> Thus, as illustrated in <figref idref="f0012">Fig. 22</figref>, the envelope comprises the cut-off boundary <b>278</b> to the point <b>284,</b> where the cut-off boundary intersects the envelope boundary <b>286.</b> From the point <b>284,</b> the boundary is envelope boundary <b>286.</b> Thus, if either a caution or warning envelope is below the cut-off boundary, cut-off boundary becomes the new boundary for the envelope.

In the discussion above, the caution and warning envelopes are discussed in terms of a single vector along the track of the marine vessel. The single vector provides acceptable results because the relatively crude resolution of the terrain database stored in the first memory device is based upon the shallowest depth per cell and the natural noisiness of the heading and position information. However, the single vector approach does not take into account various errors, due to, for example, the terrain database, GPS longitude and latitude errors, as well as the heading accuracy. As such, the single vector along the track of the marine vessel may be substituted with an array of vectors, as generally shown in <figref idref="f0013">Fig. 23</figref>, which takes such errors into account. In particular, the track vector is identified with the reference numeral <b>2100</b> originating at the instantaneous position X₀, Y₀. A pair of vectors 2120 and 2140 are disposed at a configurable distance D_OFF, for example 0.2 nm, along a segment <b>2216,</b> perpendicular to the vector <b>2100</b> at points X₁ Y₁ and X_r, Y_r. A pair of outside vectors <b>2150</b> and <b>2200,</b> originating at points X₁, Y₁ and X_r, Y_r, respectively, are directed at a configurable angle D_ALPHA, relative to the vectors 2212 and <b>2214.</b> The configurable angle D_ALPHA may be selected as 3 °, equivalent to the track accuracy of the GPS.

The coordinates X₁, Y, and X₁, Y, for the vectors <b>2150</b> and <b>2200,</b> respectively, are determined. More particularly, the incremental X and Y vectors, DX_OFF and DY_OFF, are determined as set forth in the equations below: <maths id="math0029" num=""><math display="block"><mrow><msub><mi mathvariant="normal">DX</mi><mi mathvariant="normal">OFF</mi></msub><mo>=</mo><mfenced open="{" close="}" separators=""><msub><mi mathvariant="normal">D</mi><mi mathvariant="normal">OFF</mi></msub><mo>/</mo><mi mathvariant="normal">Cos</mi><mfenced><mi mathvariant="normal">Latitude</mi></mfenced></mfenced><mo>*</mo><mi mathvariant="normal">Cos</mi><mfenced><mi mathvariant="normal">Track</mi></mfenced><mo>,</mo></mrow></math><img file="EP1990609B1_D0029.tif" /></maths> where D_OFF is a configurable distance between X₀, Y₀ and X₁ Y₁, for example 0.2 nm and the factor 1/cos(Latitude) is used to convert DX_OFF to nautical miles when DX_OFF, DY_OFF is in minutes and D_OFF is in nautical miles. <maths id="math0030" num=""><math display="block"><mrow><msub><mi mathvariant="normal">DY</mi><mi mathvariant="normal">OFF</mi></msub><mo>=</mo><msub><mi mathvariant="normal">D</mi><mi mathvariant="normal">OFF</mi></msub><mo>*</mo><mi mathvariant="normal">Sin</mi><mfenced><mi mathvariant="normal">Track</mi></mfenced></mrow></math><img file="EP1990609B1_D0030.tif" /></maths>

The coordinates X_r, Y, can be determined in a similar manner. Optionally copending attorney docket no. 543-99-006 Serial No. <patcit id="pcit0020" dnum="WO09496297A"><text>09/496,297</text></patcit> incorporated herein by reference describes a method of trident width expansion which can be adapted to marine applications to obtain the array of vectors. In addition, the width of the caution and warning envelopes may be defined with reference to the displacements required to complete IMO standard maneuvers as discussed in Section 4.2.1. This dimension can be further modified to account for narrow channels and confined operations as also previously described in Section 4.2.1.

<i>4.2.4 Predicted Track Alerts</i>

Another alternate embodiment of the invention utilizes predictions of the vessel's position at future points in time to obtain a projected track of the vessel. This embodiment differs from the previous embodiments described in that it is based on the predicted position vector rather than defining a dynamic protection envelope based on the vessel's current heading and speed. In this embodiment, an unsafe condition is detected when any point along the predicted track intersects the terrain or obstruction.

The projected track of the vessel is defined by a certain number of points A to F starting from its actual position, as illustrated in <figref idref="f0014">Fig. 24</figref>. This track is established form the current position of the vessel and its velocity and acceleration vectors in the manner previously described in Section 2.0.

Uncertainty in position along the projected track may be accounted for by defining a volume around the vessel having the following axes: an uncertainty margin in latitude LAT_e, an uncertainty margin in longitude LONG_e, and a vertical uncertainty margin Z_e (optionally <i>Z_ed</i> and <i>Z_eh</i>) to account for uncertainties in the keel depth and optionally the height of the ship. Preferably the magnitude of Z_e is based upon the ship's response to waves presently being encountered by the ship as governed by the ship's sea keeping state equations and that all uncertainty margins account for errors in the measurement/navigation system.

The volume of uncertainty resulting therefrom is an ellipsoid of revolution as shown in <figref idref="f0014">Fig. 25</figref> whose half axes a, b and c are not necessarily equal. Thus, as illustrated in <figref idref="f0015">Fig. 26</figref>, an uncertainty range is associated with each point along the projected track of the vessel. In the explanation to follow, the simplifying assumption is made that LAT_e = LONG_e. Thus, the vertical projection in the horizontal plane of <figref idref="f0015">Fig. 26</figref>,results in an uncertainty circle of navigation N (an ellipse in the general case). The envelope of these circles in turn defines a projected track envelope EV round the predicted tack PT.

The length of predicted track PT for purposes of detecting unsafe clearances is configurable, but in an embodiment may be determined using the look ahead distance calculations defined in any of the previous sections and/or by the vessel stopping or turning time.

<figref idref="f0015">Fig. 27</figref> schematically illustrates the progress of the position of the vessel in relation to the grids contained in the local memory. The updating of the local memory may be effected by retaining the region wherein the vessel is situated and by updating the three adjoining regions as illustrated in <figref idref="f0015">Fig. 27</figref> by a dashed line.

<figref idref="f0016">Figs. 28A and 28B</figref> show the square uncertainty surface with maximum dimensions of m x m grids. All the depths are read and only the value of the shallowest depth Z, is retained and added to the uncertainty margin <i>Z_ed</i> defined above. The resulting sum, ZTM, is illustrated in dashes. The set of values ZTM on the map will give the theoretical profile beneath the ship, and the alert logic compares this theoretical profile beneath the ship with the anticipated track of the ship. Optionally, as described above in Section 2.0 the uncertainty marge Z_e may be added to the keel depth valve to save on computation.

In yet another embodiment of the invention, the alert logic also checks for clearance with obstacles, such as a bridge, under which the vessel must pass. In this embodiment, a second set of values ZTM2 is obtained and comprises the uncertainty warning in <i>Z_eh'</i> representing the height of the ship summed with the clearance height Z of the obstacle. The alert logic compares the anticipated track of the ship with this overhead theoretical profile and outputs a warning signal when a collision possibility is detected. In an embodiment of the invention, both a caution and a warning logic are associated with the curves of <figref idref="f0016">Fig. 28A</figref> dn 28B. A warning is given when a point of the terrain intersects a sampling point in close proximity to the vessel such that the helmsman must intervene to avoid grounding the vessel or colliding with an overhead obstacle. The location of this sampling point can be determined by reference to the point at which a turning or stopping maneuver can be executed. A caution is given to forewarn the helmsman that projected track will encounter an obstacle if it is continued as it is and that he must consider an avoidance maneuver. The look-ahead distances for the caution and warning sampling points can be determined as described in any of the preceding sections.

<i>4.3 Avoidance Maneuver Logic</i>

When a possible collision with underwater terrain or overhead obstacles is detected then the present invention may optionally be provided with a device and or logic for calculating an avoidance law.

The invention constructed in accordance with this embodiment may optionally further include an avoidance logic which alerts the crew to a new heading to steer and/or engine setting to avoid collisions. Specifically when a potential conflict is detected using one of the predictive alerting schemes in the manner described above in Sections 4.2, the invention next checks for an available collision free pathway having an origin point at the present position of the vessel. <figref idref="f0017">Figs. 29A and 29B</figref> illustrate operation of this feature. By way of example, <figref idref="f0017">Fig. 29A</figref> illustrates operation of the avoidance logic when one of the envelope based methods of Section 4.2.1, 4.2.2, or 4.2.3. is used. <figref idref="f0017">Fig. 29A</figref> shows a plan view wherein the ship's heading is incremented by a nominal step size dΨ. A protective envelope is constructed as indicated by the boundaries 2180', 2200', LAD', X₁', Y₁', and X₂', Y₂'. This envelope is checked for terrain clearance in accordance with the methods described in the aforesaid sections.

<figref idref="f0017">Fig 29B</figref> illustrates operation of the avoidance logic when the alerting scheme of Section 4.2.4 is used. In <figref idref="f0017">Fig.29B</figref>, an alternate track PT' is first generated by incrementing the ship's current heading by nominal step size d_ψ. Alternate track PT' as surrounded by envelope EV' is then checked for terrain clearance in accordance with the method described in Section 4.2.4.

When selecting alternate track candidates the routine may preferably also consider the performance parameters of the ship. A genetic algorithm or other optimization routine well known to those of skill in the art may be used to refine the initial heading guess dψ. The optimization routine can be constrained if desired by eliminating non practical or illegal maneuvers. For example, if the data base contains shipping lane information and the avoidance manoeuver places the vessel in the oncoming sea lane, this guess may be eliminated as a valid candidate from the alternate track choices. Such tracks, which represent an illegal maneuver but do not themselves represent an immediate grounding hazard, may be retained, however, when it proves to comprise the entire set of alternative tracks. Candidate tracks that themselves, present a grounding or obstruction hazard are also removed as a candidate track option. Preferably, the optimization routine selects a track with a constraint of minimizing changes in the ship's current heading. This constraint avoids major course corrections and deviations from the intended course of the vessel. If no safe alternate heading can be found during calculation, or if the solution heading approaches 90°, the avoidance logic defaults to recommending a stopping maneuver, course reversal or other operational procedure.

Use of the avoidance logic in conjunction with the predictive alerting schemes may be of benefit not only in suggesting evasion maneuvers, but also in reducing nuisance alarms. For example, if the vessel is operating in confined areas such as a river bend or canyon, the alerting envelope area can be reduced and need not take into account the area of a pre-assumed stopping or turning response to an alert. The alerting envelope internal area to each side of the ship can therefore be reduced or eliminated. Terrain and obstacles located within the region of the pre-assumed standard evasive maneuver which may have previously generated an erroneous, or nuisance, alert is thereby no longer a factor.

<i>4.4 Strategic Alerting</i>

The reactive and predictive alerts of Sections 4.1 and 4.2 provides tactical information to the ship's crew useful for avoiding potential grounding hazards or collisions. The predictive logic of Section 4.2 can also be additionally used in a strategic manner for route proving. In such an embodiment, the intended course or points of intended movement are received as input and any of the logic of Section 4.2 can be used to check for sufficient terrain clearance along the plotted course. The invention can further refine the robustness of this check by including the tide data and any known currents (set and drift data) for the estimated time of arrival at points along the route. In this manner, the crew can be alerted to any errors in navigation plotting and/or to areas along the intended course that may present an increased collision hazard. The crew can then make a course correction or will alternatively maintain heightened vigilance when traversing these high risk areas.

<i>5.0 Display System</i>

A display system, generally identified with the reference numeral 4000, is illustrated in <figref idref="f0018 f0019 f0020 f0021 f0022 f0023 f0024 f0025 f0026 f0027 f0028 f0029 f0030 f0031">Figs. 30-44</figref>. The display system 4000 is used to provide a visual indication of the terrain advisory and terrain warning indications discussed above as a function of the current position of the vessel. Background terrain/obstacles information is also provided which provides an indication of significant terrain relative to the current position of the vessel.

In order to declutter the display, background information may be displayed in terms of predetermined dot patterns whose density varies as a function of the elevation of the terrain relative to the altitude of the vessel. Terrain advisory and terrain warning indications may be displayed in solid colors, such as yellow and red, relative to the anticipated track of the vessel.

The terrain background information as well as the terrain advisory and warning indications may be displayed on a navigational or weather display, normally existing on the bridge, which reduces the cost of the system and obviates the need for extensive modifications to existing displays, such as a navigational and weather radar type display. The terrain and obstacle display can be toggled from the existing displays or superimposed on the existing weather/radar display. In particular, the terrain data is converted to a weather radar format in accordance with any standard digital bus protocol used aborad commercial shipping vessels. The terrain data, masked as weather data, can then be easily displayed on an existing navigational or a dedicated weather radar display.

As shown in <figref idref="f0018">Fig. 30</figref>, display system 4000 includes a weather radar display or navigational display 36 connected to a control bus 4040 conforming to a predetermined bus standard and a terrain data bus switch <b>4060.</b> The terrain data bus switch <b>4060</b> enables selection between terrain data and weather radar data for display. More particularly, data bus switch <b>4060</b> includes a common pole <b>4080</b> connected to the display <b>36</b> by way of a serial display bus <b>4100.</b> One contact <b>4120</b> on the data bus switch <b>4060</b> is connected to a serial weather data bus <b>414</b> and, in turn, to a weather radar R/T unit <b>4160,</b> which transmits weather radar data over the weather data bus <b>4140.</b>

An antenna <b>4180</b> provides weather radar data to weather radar R/T unit <b>4160.</b> Weather radar R/T unit <b>4160</b> is also connected to control bus <b>4040,</b> which is used for range and mode data.

To facilitate compatibility with existing radar displays, which sweep out data over an arc, the terrain advisory and terrain warning indications, as well as the background information discussed above, may be converted to "RHO/THETA" format. The converted terrain data is then applied to a terrain data serial bus <b>4200</b> and connected to a contact <b>4220</b> on the data bus switch <b>4060</b> to enable selective display of either weather radar or terrain data on display <b>36.</b>

<figref idref="f0019">Fig. 31</figref>, illustrates a preferred embodiment of the invention in which each word <b>4250</b> is 1600 bits long and represents one spoke or radial <b>4260</b> of the display <b>36.</b> Normally, 512 spokes or radials <b>4260</b> are transmitted for each complete sweep of the display <b>36.</b> At a transmission rate of, for example, 1 megahertz (MHz), each word <b>4250</b> takes about 1.6 milliseconds (msec) to transmit. For 512 spokes, one complete sweep will thus take about 4 seconds.

The 1600-bit words <b>4250</b> include a header <b>4280</b> and 512 range bins <b>4300.</b> The header <b>4208</b> includes the control data on the control bus <b>4040</b> and also includes a 12-bit code representing the antenna scan angle; the angle of the spoke relative to the vessel heading equivalent to an indicator UP direction. The range bins <b>4300</b> cover the distance from the antenna <b>4180</b> to the maximum selected. Each of the 512 range bins includes three intensity bits, encoded into colors as indicated in Table II below. <tables id="tabl0002" num="0002"><table frame="all"><title><u>TABLE II</u></title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="35mm" /><colspec colnum="2" colname="col2" colwidth="21mm" /><thead><row><entry align="center" valign="top"><b>3-BIT RANGE CODE</b></entry><entry valign="top"><b>COLOR</b></entry></row></thead><tbody><row><entry align="center">000</entry><entry>BLACK</entry></row><row><entry align="center">100</entry><entry>GREEN</entry></row><row><entry align="center">010</entry><entry>YELLOW</entry></row><row><entry align="center">110</entry><entry>RED</entry></row><row><entry align="center">001</entry><entry>----</entry></row><row><entry align="center">101</entry><entry>CYAN</entry></row><row><entry align="center">011</entry><entry>MAGENTA</entry></row><row><entry align="center">111</entry><entry>-----</entry></row></tbody></tgroup></table></tables>

As will be discussed in more detail below, display system <b>4000</b> is capable of displaying background terrain information as well as terrain threat indications as a function of the current position of the vessel. For convenience, where a specific example is desirable to illustrate the display of tactical terrain/obstacle alerts according to the invention, the predictive algorithm of 4.2.3 is used as an example. The threat detection algorithm is run along the projected track of the vessel. Thus, terrain threat indications are typically displayed along the projected track while background terrain is displayed relative to the heading of the vessel.

In <figref idref="f0020">Fig. 32</figref>, the terrain background information is shown on the display <b>36.</b> As will be discussed in more detail below, the depth of the terrain most proximate to the ship is shown as a series of dot patterns whose density varies as a function of the distance between the vessel and the terrain. For example, a relatively dense dot pattern <b>4320</b> may be used to indicate terrain that is, for example, 2 feet or less below the vessel. A medium dense dot pattern <b>4340</b> may be used to represent terrain that is 5 feet or less below the vessel, while a lightly dotted pattern 4360 may be used to indicate terrain 10 feet or less below the vessel. In order to declutter the display 4020. terrain more than, for example, 20 feet below the vessel, is not shown. The dots may be displayed in one of the colors indicated in Table II above, for example, yellow (amber). In addition, in the vicinity of a port or known waterway, port structures <b>4380</b> and/or a shipping channel pathway <b>4389,</b> for example, in green, may also be provided. The apparent display resolution may be increased by using more than one color along with the variable density dot patterns, for example, as shown in Table III below. <tables id="tabl0003" num="0003"><table frame="all"><title><u>TABLE III</u></title><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="42mm" /><colspec colnum="2" colname="col2" colwidth="19mm" /><colspec colnum="3" colname="col3" colwidth="17mm" /><colspec colnum="4" colname="col4" colwidth="19mm" /><thead><row><entry align="center" valign="top">DOT DENSITY PATTERN</entry><entry align="center" valign="top">HIGH</entry><entry align="center" valign="top">3000</entry><entry align="center" valign="top">0</entry></row></thead><tbody><row><entry align="center" /><entry align="center">MEDIUM</entry><entry align="center">4000</entry><entry align="center">1000</entry></row><row><entry align="center" /><entry align="center">LOW</entry><entry align="center">5000</entry><entry align="center">2000</entry></row><row><entry align="center">COLOR</entry><entry align="center" /><entry align="center">GREEN</entry><entry align="center">YELLOW</entry></row></tbody></tgroup></table></tables>

The display of a terrain threat indication is illustrated in <figref idref="f0021">Fig. 33</figref>. As shown, the terrain threat indication may be displayed contemporaneously with the background terrain information. Terrain advisory and terrain warning indications are displayed in solid shapes <b>4400</b> and <b>4420,</b> respectively, for example, "squares"; the displayed terrain map cells which represent a threat painted solid yellow or red. More particularly, at an aspect ratio for the display of, for example, 3 x 4 (vertical to horizontal), the terrain cells will appear "square", particularly at relatively low-range settings. Colors are used to distinguish between terrain advisory and terrain warning indications. For example, red may be used to represent a terrain warning indication <b>4420</b> while yellow or amber is used to represent a terrain advisory indication <b>4400.</b> By using colored shapes for terrain threat indications and dot patterns of variable density for the terrain background information, clutter of the display <b>4020</b> is minimized.

The terrain data from the terrain data base 24, for example, as illustrated in <figref idref="f0007">Fig. 8</figref>, is used to compute the terrain threat indications as well as background information for the display <b>36.</b> As discussed above, the terrain data base <b>24</b> may be stored in a flash ROM <b>4440</b> (<figref idref="f0008">Fig. 9</figref>) for convenience of updates. In order to facilitate update of the display 36 as a function of the position of the vessel, terrain data from the flash ROM <b>4440</b> is transferred to a random access memory (RAM) A, identified with the reference numeral <b>4460.</b> As will be discussed in more detail below, the RAM A is mapped with terrain data from the flash ROM <b>4440,</b> centered about the current position of the vessel, as illustrated in <figref idref="f0008">Fig. 9</figref>.

In order to provide a relatively large display range, while minimizing processing time as well as the size of the RAM A, the RAM A is configured as a "wedding cake" as generally illustrated in <figref idref="f0022">Fig. 34</figref> and configured such that the finest terrain resolution is near the position of the vessel and the terrain farthest from the vessel position has the lowest resolution. For example, the RAM A may be provided with four (4) layers. As shown, the instantaneous vessel position is shown generally centered in layer 1, having the highest resolution. The resolution of layer 2 lies between the resolution of layer 3 and layer 1. Layer 4 (not shown) is provided with a relatively coarse resolution for use in a cruising mode.

Such a variable resolution display, configured as a layered wedding cake, minimizes the memory size of RAM A as well as the processing time. In order to improve the performance of the system, the flash ROM <b>4440</b> may also be configured similar to a "wedding cake", as generally illustrated in <figref idref="f0008">Fig. 9</figref>.

As discussed above, the terrain data base <b>24</b> may be provided with variable resolution. Relatively coarse resolution can be formed by combining finer resolution maps. With such a resolution, the configuration of RAM A may be selected, for example, in accordance with Table IV. Finer resolutions layers may be used if desired, such as near ports. <tables id="tabl0004" num="0004"><table frame="all"><title><u>TABLE IV</u></title><tgroup cols="3"><colspec colnum="1" colname="col1" colwidth="17mm" /><colspec colnum="2" colname="col2" colwidth="43mm" /><colspec colnum="3" colname="col3" colwidth="41mm" /><thead><row><entry align="center" valign="top"><b>LAYER</b></entry><entry align="center" valign="top"><b>RESOLUTION (MINUTES)</b></entry><entry align="center" valign="top"><b>LAYER SIZE (MINUTES)</b></entry></row></thead><tbody><row><entry align="center">1</entry><entry align="center">1/2 x 1/2</entry><entry align="center">32 x 32</entry></row><row><entry align="center">2</entry><entry align="center">1 x 1</entry><entry align="center">64 x 64</entry></row><row><entry align="center">3</entry><entry align="center">2 x 2</entry><entry align="center">128 x 128</entry></row><row><entry align="center">4</entry><entry align="center">5 x 5</entry><entry align="center">REMAINING AREA</entry></row></tbody></tgroup></table></tables>

Each layer is generally centered relative to the vessel position as shown in <figref idref="f0022">Fig. 34</figref> at the time of the update of RAM A. Each layer of the "wedding cake" has its own update boundary. For example, layer 1 of the RAM A includes an update boundary <b>4480.</b> As the vessel passes through the update boundary <b>4480,</b> the RAM A is updated with new terrain data from the flash ROM <b>4440</b> (<figref idref="f0008">Fig. 9</figref>) as will be discussed in more detail below.

Because of the refresh rates required for the display <b>36,</b> the terrain data may be stored in files alternative to the format illustrated in <figref idref="f0007">Fig. 8A</figref>. For example, the file format of the terrain data may include an index file or header <b>55,</b> stored in one or more 128 K byte storage blocks and a plurality of data files <b>51,</b> as generally shown in <figref idref="f0009">Fig.10</figref>.

As shown, each index file <b>55</b> may include pointers to specific data files <b>51,</b> the length of the map file, as well as the position of one or more of the corner boundaries of the file <b>51,</b> for example, northwest and southeast corners of each map file <b>51,</b> which facilitates updates of the display <b>36</b> as a function of the current vessel position. The index file <b>55</b> may contain information regarding the length of the map file <b>51,</b> a start of file or altitude offset, the resolution of the map file <b>51,</b> and whether and how the file <b>51</b> is compressed to enable use of various compression algorithms.

The data files <b>51</b> may include a file header <b>4540</b> as well as data blocks 4560 shown in <figref idref="f0023">Fig. 35</figref>, which, as shown, can be grouped according to resolution size. The file header <b>4540</b> indicates various information about the file. The format of the header <b>4540</b> may be structured as follows: <ul id="ul0006" list-style="none"><li>&lt;MAJOR VERSION BYTE&gt;&lt;MINOR VERSION BYTE&gt;&lt;FILE STATUS BYTE&gt;&lt;ATTRIB BYTE&gt;</li><li>&lt;FILE NAME (8 CHARACTERS)&gt;&lt;EXTENSION (4 CHARACTERS)&gt;</li><li>&lt;FILE LENGTH LONGWORD&gt;</li><li>&lt;TIME STAMP LONGWORD&gt;</li><li>&lt;CRC LONGWORD&gt;</li><li>&lt;SPME LONGWORD&gt;</li></ul>

The major and minor version bytes relate to the revision status of the data in the data files 51. The minor version is set as the inverse of the byte value of the major version such that a default erase will indicate a zero version. The file status byte <b>4570</b> provides various information regarding the status of the file as discussed below, while the attribute byte is reserved. The file name, extension file length, and spare data are self-explanatory. The time stamp relates to the operational time of the system (i.e. length of time in use) while the CRC data relates to the data files <b>51.</b> The status byte may be used to provide the following information regarding the data blocks <b>4560,</b> for example, as set forth in Table V below: <tables id="tabl0005" num="0005"><table frame="all"><title><u>TABLE 6</u></title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="34mm" /><colspec colnum="2" colname="col2" colwidth="32mm" /><thead><row><entry align="center" valign="top"><b>FLAG BYTE VALUE</b></entry><entry align="center" valign="top"><b>INFORMATION</b></entry></row></thead><tbody><row><entry align="center">FF</entry><entry align="center">EMPTY</entry></row><row><entry align="center">FE</entry><entry align="center">DOWNLOADING</entry></row><row><entry align="center">FO</entry><entry align="center">VALID</entry></row><row><entry align="center">EO</entry><entry align="center">READY TO ERASE</entry></row><row><entry align="center">.</entry><entry align="center">RESERVED</entry></row><row><entry align="center">.</entry><entry align="center">RESERVED</entry></row><row><entry align="center">00</entry><entry align="center">RESERVED</entry></row></tbody></tgroup></table></tables>

The EMPTY status (FF) is set by erasing the data blocks <b>4560,</b> while the DOWNLOADING status (FE) is set as part of the image. The VALID status (FO) is set when the file is loaded. The READY TO ERASE (EO) is set by the file system for obsolete blocks.

As indicated below, various corrections of the data files <b>51</b> may be required in areas near ports and shorelines. The depths, as discussed above, are generally selected to be the shallowest depths within the cells, rounded up to the next highest resolution increment, for example 2 or 54 feet. While such a system provides useful and conservative terrain data for use with the terrain data base <b>24,</b> such a system in the vicinity of a port or shoreline can cause the elevations of critical features to be too high or too low. Such errors in feature depth can degrade system performance, and, in particular, cause improper performance of the terrain advisory and terrain warning cut-off boundaries.

In order to solve this problem, the actual depth below mean sea level of the terrain feature, rounded to the nearest resolution, is used for cells <b>4550</b> around a perimeter of the terrain feature.

<figref idref="f0024">Fig. 36</figref> represents a simplified block diagram for implementation for the display system <b>4000</b> in accordance with the present invention. Display system <b>4000</b> may include a microprocessor, for example, an Intel type 80486, 25 MHz type microprocessor ("486") and an Analog Devices type digital signal processor (DSP). The DSP is primarily used for calculating the RHO/THETA conversions to off load the <b>4860.</b>

Display system <b>4000</b> may have a normal mode and a cruise mode. In a normal mode, display system <b>4000</b> displays terrain out to, for example, 10 minutes sailing time, while in cruise mode out to about ½ hour of sailing time. In the cruise mode, it is contemplated that the background terrain display levels can be lowered by the crew such that terrain, for example 100 feet or 200 feet below the vessel, can be displayed. Alternatively, the display level could automatically be adjusted to the highest terrain within the selected display range; the value of this level set forth in amber, for example.

The 486 runs a "file picker" routine which searches terrain data base <b>24</b> for terrain data covering the area relative to the current position of the vessel. For example, in a normal mode, the file picker routine searches the terrain data base <b>24</b> for terrain data covering a given area relative to the current position of the vessel. As indicated above, the terrain data base 24 includes index files <b>55</b> (<figref idref="f0007">Figs. 8B</figref> and <figref idref="f0009">10</figref>) which may include the northwest and southeast corners of each map file <b>51</b> in order to facilitate the search. A list of files covering the area is assembled and maintained.

Index file <b>55</b> also includes information as to whether and how data files <b>51</b> are compressed. The files may be compressed/decompressed by a modified Huffman code, or techniques known to those of ordinary skill in the art.

If data files <b>51</b> are compressed, the files are decompressed in the background because of the relatively long decompression time and stored in a decompressed file RAM (DFR) <b>4760,</b> for example 256 words. The decompressed files are then transferred to RAM A, identified with the reference number <b>4460.</b> On power-up, one or two files around the vessel are decompressed and displayed to allow immediate display of a limited range, relative to the position of the vessel. As more terrain data files are decompressed, the additional range is displayed.

The RAM A may be configured in a plurality of cells <b>4790,</b> as shown in <figref idref="f0024">Fig. 36</figref>, representative of a terrain area 15 arc seconds x 15 arc seconds, with true north appearing at the top of RAM A as shown. Each cell <b>4790</b> is two bytes wide and includes data regarding the shallowest depth in the cell as well as the identity of each cell <b>4790.</b> As such, the RAM A is addressable by X and Y coordinates and thus represents a map with a depth in each cell <b>4790.</b> The identity of the cell may be used to distinguish between terrain data, for example, from terrain data base <b>24</b> and obstacle data. In some applications, an obstacle data base indicating underwater obstructions may be utilized.

As indicated above, the RAM A may be configured as a wedding cake with various layers, as generally shown in <figref idref="f0022">Fig. 34</figref> with the top layer (i.e. layer 1) having the highest resolution. Terrain data is loaded into the RAM A such that the vessel is roughly centered in the top layer, where the terrain advisory and warning detection algorithms are run. Once the vessel moves outside the update boundary <b>4480</b> of <figref idref="f0022">Fig. 34</figref>, the top layer of the RAM A is reloaded with terrain data with the vessel centered. The lower layers may also be provided with update boundaries, which enable the lower layers to be updated independently and less frequently than the top layer.

As discussed above and illustrated in <figref idref="f0008">Fig. 9</figref>, the flash ROM <b>4440</b> for terrain data base <b>24</b> may also be configured as a wedding cake as illustrated in <figref idref="f0022">Fig. 34</figref>. In such an implementation, the highest resolution is provided near ports and shorelines while coarser resolutions are provided elsewhere. For example, as illustrated in <figref idref="f0025">Fig. 37</figref>, the terrain data base <b>24</b> may be configured with 1 °x 1°, 2°x2° or 10°x10 ° map files. Some of the map files may overlap, similar to a "wedding cake." Maps further away from the port may be provided with resolutions of, for example, 1 x 1 minute or 2 x 2 minutes while a coarse resolution (i.e. 5N x 5N or 10N x 10N) may be provided even further from the port.

An upload routine may be used to upsample or downsample terrain or obstacle data into the RAM A from the DFR RAM <b>4760</b> as shown in <figref idref="f0028">Fig.40</figref>. Such a routine is well within the ordinary skill in the art. The top three layers (i.e. layers 1, 2 and 3) of the RAM A of <figref idref="f0026">Fig. 38</figref> are updated from the map file source from the flash ROM <b>4440</b> for terrain data base 24 having the highest resolution, except for the 5 x 5 minute layer, which is updated only from a 5 x 5 minute file source to reduce processing time.

Alternatively, as shown in <figref idref="f0025">Fig. 37</figref>, an additional RAM A*, identified with the reference numeral <b>4770,</b> may be provided and structured similar to the RAM A <b>4460,</b> forming a "ping-pong" memory arrangement. In this embodiment, one terrain data file <b>51</b> is decompressed one file at a time and loaded into the DFR RAM <b>4760</b> and then upsampled to either the RAM A or RAM A*. For example, while the RAM A is being loaded with additional decompressed files, the terrain threat and display algorithms are executed from the RAM A*. Once the RAM A is updated, the RAM A is then used for the computations while the other RAM A* is updated with new data from the DFR RAM <b>4760</b> to account for changes in the vessel position.

The 5 x 5 minute resolution layer is primarily intended for use in a cruise mode to provide a look-ahead range of about a half hour. As was illustrated in <figref idref="f0009">Fig. 10</figref>, each file includes an index file <b>55</b> which contains data relative to the resolution of the terrain data in a particular map file <b>51</b>. Such information can be used to vary the resolution of the map files as a function of longitude and latitude position. For example, the latitude resolutions of the map files can be decreased at higher latitudes in a northward direction. Moreover, longitude resolution in the RAM A can be varied and provided with, for example, a one degree latitude hysteresis to prevent flipping back and forth as a vessel cruises northwardly. Once the terrain data from terrain data base 24 is loaded into the RAM A, the terrain advisory and warning algorithms ("detection algorithms") are run, for example, at once per second.

Whenever the threat detection algorithm detects terrain along, for example, the look-ahead vector arrays 2100 and <b>2120</b> (<figref idref="f0013">Fig. 23</figref>), the offending terrain is painted in an expanded cone around the groundtrack as shown in <figref idref="f0026">Fig. 38</figref>. In particular, the expanded cone includes a plurality of vectors, spaced, for example, 4° apart (configurable value), for 90° (configurable value) on each side of the groundtrack. For an expanded terrain warning, the cone may be expanded out distances, for example as set forth in Table VI below. <tables id="tabl0006" num="0006"><table frame="all"><title><u>TABLE VI</u></title><tgroup cols="5"><colspec colnum="1" colname="col1" colwidth="32mm" /><colspec colnum="2" colname="col2" colwidth="48mm" /><colspec colnum="3" colname="col3" colwidth="19mm" /><colspec colnum="4" colname="col4" colwidth="48mm" /><colspec colnum="5" colname="col5" colwidth="19mm" /><thead><row><entry namest="col1" nameend="col5" align="center" valign="top">(For an expansion factor of 2)</entry></row><row><entry align="center" valign="top" /><entry align="center" valign="top"><b>NORMAL</b></entry><entry align="center" valign="top" /><entry align="center" valign="top"><b>EXPANDED</b></entry><entry align="center" valign="top" /></row><row><entry align="center" valign="top">TYPE OF THREAT</entry><entry align="center" valign="top">LOOK-AHEAD/ LOOK-DOWN</entry><entry align="center" valign="top">LOOK-UP</entry><entry align="center" valign="top">LOOK-AHEAD/ LOOK-DOWN</entry><entry align="center" valign="top">LOOK-UP</entry></row></thead><tbody><row><entry align="center">ADVISORY</entry><entry align="center">1.0*</entry><entry align="center">2.0*</entry><entry align="center">2.0*</entry><entry align="center">4.0*</entry></row><row><entry align="center" /><entry align="center">LAD</entry><entry align="center">LAD</entry><entry align="center">LAD</entry><entry align="center">LAD</entry></row><row><entry align="center">WARNING</entry><entry align="center">0.5*</entry><entry align="center">1.5*</entry><entry align="center">1.0 *</entry><entry align="center">3.0*</entry></row><row><entry align="center" /><entry align="center">LAD</entry><entry align="center">LAD</entry><entry align="center">LAD</entry><entry align="center">LAD</entry></row></tbody></tgroup></table></tables>

The terrain threat is painted on the display 36 by calculating the starting vector angle DISPA as set forth in equation (29) when a terrain threat along the track has been detected. <maths id="math0031" num="(29)"><math display="block"><mrow><mi>DISPA</mi><mo>=</mo><mi>ANTICIPATED TRACK</mi><mo>+</mo><mn>30</mn><mspace width="1em" /><mi>degrees</mi></mrow></math><img file="EP1990609B1_D0031.tif" /></maths>

The range increments are then determined as set forth in equations (30) and (31). <maths id="math0032" num="(30)"><math display="block"><mrow><mi mathvariant="normal">DELTA</mi><mspace width="1em" /><msub><mi mathvariant="normal">X</mi><mi mathvariant="normal">NS</mi></msub><mo>=</mo><mi mathvariant="normal">DISPLAY STEP SIZE</mi><mo>*</mo><mi mathvariant="normal">SIN</mi><mfenced><mi mathvariant="normal">DISPA</mi></mfenced><mo>*</mo><mn mathvariant="normal">1</mn><mo>/</mo><mi mathvariant="normal">COS</mi><mfenced><mi mathvariant="normal">LATITUDE</mi></mfenced></mrow></math><img file="EP1990609B1_D0032.tif" /></maths><maths id="math0033" num="(31)"><math display="block"><mrow><mi mathvariant="normal">DELTA</mi><mspace width="1em" /><msub><mi mathvariant="normal">Y</mi><mi mathvariant="normal">NS</mi></msub><mo>=</mo><mi mathvariant="normal">DISPLAY STEP SIZE</mi><mo>*</mo><mi mathvariant="normal">COS</mi><mfenced><mi mathvariant="normal">DISPA</mi></mfenced><mo>,</mo></mrow></math><img file="EP1990609B1_D0033.tif" /></maths> where the display step size is a configurable constant, for example 1/2 unit.

After the range increments DELTA X_NS and DELTA Y_NS are determined, the instantaneous position of the vessel X₀, Y₀ is incremented by the same and the range is incremented by the step size. The DEPTH is then determined for the current position on the terrain map. Subsequently, the threat detection algorithms are run for the distances as discussed above. Should a threat be detected, a color is loaded into a RAM B, identified with the reference numeral <b>5040</b> as shown in <figref idref="f0024">Fig. 36</figref>. At the end of the yellow and red threat vectors <b>4960</b> and <b>5000,</b> the vector angle DISPA is incremented by 4 degrees with the above steps being repeated until all vectors are done.

In addition to the terrain detection and display algorithms, a background terrain algorithm is also executed relative to the terrain data in RAM A of <figref idref="f0024">Fig. 36</figref> once every screen update, about 4 seconds. The background terrain algorithm simply compares the current altitude of the vessel with the various terrain altitude data in the RAM A. Any of the dot patterns <b>4320, 4340</b> and <b>4306</b> shown in <figref idref="f0020">Fig. 32</figref> resulting from the computation are stored in the RAM B organized in a wedding-cake configuration according to <figref idref="f0022">Fig. 34</figref>, similar to the RAM A. In addition, the RAM B is organized in single byte cells containing the color/dot pattern as discussed above.

The color/dot pattern in the RAM B is transferred to the DSP memory RAM B*, identified with the reference numeral <b>5060,</b> once per screen update (i.e. 4 sec) and synchronized to the DSP screen painting period. If a threat is detected as discussed above, a new RAM B image is transferred to the DSP RAM B* <b>5060</b> immediately. The image transfer time typically fits between two spokes. If not, the DSP will send an old spoke stored in its spoke memory <b>5080, 5100</b> twice.

The DSP then performs the RHO/THETA conversion on the data in RAM B* <b>5060</b> using the updated position, selected range and heading data from the 486, as discussed below. Changes in the selected range are implemented on the fly (i.e. the next spoke) without restarting the sweep.

One possible weather radar format includes 512 spokes covering a configurable scan range of typically 90 degrees and a range selected, for example, on a weather data control panel. In a preferred embodiment, each spoke is calculated twice, once for the left selected range and once for the right selected range. The spokes are then transmitted by way of a serial port <b>5120,</b> interleaved left spoke and right spoke to bus switch <b>4060</b> by way of a pair of drivers <b>5140</b> and <b>5160</b>.

The resolution of the scan conversion is 256 range bins; each range bin actually being a double range bin per the ARINC 708/453 standard format. Such a resolution is sufficient for the dot patterns illustrated in <figref idref="f0020">Figs. 32</figref> and <figref idref="f0021">33</figref>.

The RHO/THETA conversion is best understood with reference to <figref idref="f0027">Fig. 39</figref>. In particular, once per sweep (i.e. every 4 seconds) the range increment R1 is determined. The range increment is the selected range divided by 256. After the range increment is determined, the starting spoke angle is determined (e.g.., the vessel true heading plus 90 degrees). The incremental spoke angle DELTA ALPHA is determined. The incremental spoke angle DELTA ALPHA is the sweep range divided by 512; the total number of spokes per sweep.

Once per spoke (i.e. 512 times per 4 second sweep), the incremental range coordinates DELTA X_ns, DELTA Y_ns are computed and the spoke angle is incremented by DELTA ALPHA, as discussed above. The incremental range increment coordinates X_ns and Y_ns are computed in accordance with equations (32) and (33), respectively. <maths id="math0034" num="(32)"><math display="block"><mrow><mi mathvariant="normal">DELTA</mi><mspace width="1em" /><msub><mi mathvariant="normal">X</mi><mi mathvariant="normal">ns</mi></msub><mo>=</mo><mi mathvariant="normal">RI</mi><mo>*</mo><mi mathvariant="normal">SIN</mi><mfenced><mi>SPOKE ANGLE</mi></mfenced><mo>*</mo><mn>1</mn><mo>/</mo><mi mathvariant="normal">COS</mi><mfenced><mi mathvariant="normal">LATITUDE</mi></mfenced></mrow></math><img file="EP1990609B1_D0034.tif" /></maths><maths id="math0035" num="(33)"><math display="block"><mrow><mi mathvariant="normal">DELTA</mi><mspace width="1em" /><msub><mi mathvariant="normal">Y</mi><mi mathvariant="normal">ns</mi></msub><mo>=</mo><mi mathvariant="normal">RI</mi><mo>*</mo><mi mathvariant="normal">COS</mi><mfenced><mi mathvariant="normal">SPOKE ANGLE</mi></mfenced></mrow></math><img file="EP1990609B1_D0035.tif" /></maths>

Once per range increment (i.e. 512 x 256 times per 4 second sweep), the instantaneous position X₀, Y₀ is incremented by DELTA X_ns and DELTA Y_ns. The color/pattern for the new position is looked up and output to the display 36. These steps are repeated for the rest of the spoke.

With the use of the DSP, two computations can be done in parallel. In particular, the color/pattern of each range bin including the conversion of the longitude to nautical miles (i.e. multiplication by 1/COS (LAT)). With reference to <figref idref="f0027">Fig. 39</figref>, this computation is performed relative to the true north map coordinate system with the vessel true heading pointing up and the spoke angles referenced to it. The second computation addresses each display indicator pixel in order to paint the required dot pattern, relative to the display screen coordinate system.

The generation of dot pattern is illustrated in <figref idref="f0029 f0030">Figs. 41-43</figref>. In general, the scan conversion is simulated by overlaying each RHO/THETA range bin over a calculated indicator pixel map which includes corrections for display aspect ratio using fractal 8 x 8 dot patterns.

The fractal patterns corresponding to the variable density dot patterns 4320, 4340 and <b>4360</b> of <figref idref="f0020">Fig. 32</figref> are illustrated in <figref idref="f0029">Fig. 41</figref>. The fractal pattern size is selected to be 8 x 8 pixels. The densest pattern <b>4320</b> includes 1/2, or 32, of the 64 pixels are filled. In the medium density pattern <b>4340,16,</b> or 1/4, of the pixels are filled. In the least dense pattern <b>4364, 4</b> or 1/16, of the pixels are filled.

As illustrated in <figref idref="f0028">Fig. 40</figref>, the display screen is divided into a pixel map, having for example, 256 x 256 pixels <b>5200.</b> As mentioned above, the 8 x 8 fractal patterns are overlaid onto the pixel map to provide the variable density dot patterns <b>4320, 4340</b> and <b>4360</b> illustrated in <figref idref="f0020">Fig. 32</figref>.

The computation of the dot patterns is best understood with reference to <figref idref="f0028">Figs. 40</figref>, <figref idref="f0030">42 and 43</figref>. Using an X-Y coordinate system, each spoke is determined at the bottom center of the display <b>36.</b> For a 256 x 256 pixel display, the starting point corresponds to 120, 0. Next, the incremental X and Y coordinates relative to the scan angle ALPHA are determined according to equations (34) and (35). <maths id="math0036" num="(34)"><math display="block"><mrow><mi>DELTA X</mi><mo>=</mo><mi>RI</mi><mo>*</mo><mi>SIN</mi><mfenced><mi>ALPHA</mi></mfenced></mrow></math><img file="EP1990609B1_D0036.tif" /></maths><maths id="math0037" num="(35)"><math display="block"><mrow><mi>DELTA Y</mi><mo>=</mo><mi>RI</mi><mo>*</mo><mi>COS</mi><mfenced><mi>ALPHA</mi></mfenced><mo>,</mo></mrow></math><img file="EP1990609B1_D0037.tif" /></maths> where RI = a double range increment and ALPHA = the scan angle. These increments are added to the starting point 128, 0. After each increment, the selected fractal pattern is looked up in the RAM B * to determine whether to send the last range increment as either block or colored.

In <figref idref="f0030">Fig. 43</figref>, the increments DELTA X and DELTA Y are applied to a pair of adders <b>5220</b> and <b>5240,</b> which, in turn, are applied to an X-counter <b>5260</b> and a Y-counter <b>5280.</b> The X counter <b>5260</b> starts at 128 and counts up if DELTA X &gt; 0. If DELTA X &lt; 0, the X-counter counts down, indicating a pixel on the left (<figref idref="f0028">Fig. 40</figref>) of the starting position. Since the starting pixel is at the bottom of the display, the Y-counter <b>5280</b> starts at zero and always counts up. A range counter <b>5280</b> counts up to 256; the maximum number of double range bins. The range counter <b>5280</b> is driven by an increment clock such that the pattern/color is painted once per range increment. The output indicates whether the pixel is to be painted or left blank.

The background terrain algorithm determines the particular fractal pattern to be used. This data is applied to the DSP to enable the pixels on the pixel map (<figref idref="f0009">Fig.10</figref>) to be painted or left blank. In particular, the three least significant bits from the X counter <b>5260</b> and Y counter <b>5280</b> are used to select the fractal pattern as shown.

The scan conversion simulation is performed in parallel with the RHO/THETA conversion which determines the color/dot pattern of the range bin to be transmitted. The color/dot pattern provided by the RHO/THETA conversion is then overlaid with the fractal dot pattern to determine whether the range bin color should be black or painted to provide the proper dot pattern on the display.

In an alternate embodiment of the invention, display <b>36</b> may also show the terrain/obstacles in a three dimensional view in the in lieu of, or in addition to the plan view described above. <figref idref="f0031">Fig. 44</figref> shows one embodiment of display <b>36</b> on which terrain <b>6000</b> and overhead obstacles <b>6001</b> are shown in profile view, color coded to show degree of threat and depicted relative to the position of vessel <b>100,</b> indicated by a vessel or other suitable symbol.

<u>APPENDIX 1</u>

TERRAIN DATA STRUCTURE

The terrain data format is made up of four distinct parts, the file indirection table, the group index, the data index, and the compressed elevation data itself. Notes: All multi-byte numbers are stored Little Endian (LSB...MSB)

File Indirection Table

A file indirection table is provided at the top of the index file block. The file index field is each data index is used to index into this table to get the ASCII filename for file system usage. This filename is then mapped be the file system to the correct 128kbyte physical memory block. A time stamp is provided for each file, this can be used to match to the time stamp in the file header for each file. This helps check for consistency between the index files and the data files. <tables id="tabl0007" num="0007"><table frame="none"><title><u>Group Index</u></title><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="27mm" /><colspec colnum="2" colname="col2" colwidth="102mm" /><tbody><row><entry>SIZE:</entry><entry>16-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>  Number of filenames defined:</entry></row><row>&lt;entry /&gt;<entry>  Repeated for each filename</entry></row><row><entry>FILENAME:</entry><entry>16-bytes - ASCII</entry></row><row>&lt;entry /&gt;<entry>  ASCII filename with the extension included</entry></row><row>&lt;entry /&gt;<entry>  &lt;Drive&gt;:&lt;File 8&gt;.&lt;Ext 3&gt;</entry></row><row><entry>TIME STAMP:</entry><entry>  32 bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>  The number of seconds since January 1, 1980 (DOS's time base).</entry></row></tbody></tgroup></table></tables>

The group index is used to reduce the number of data indexes which must be searched to find the area of interest. The group indexes are built by dividing the earth into TBD bands or geographic areas of 5° latitude by 10° longitude. These bands need not be of equal size. The group index points to the corresponding data index block to use for this area. The area covered by the group is preferably a rectangle. Note: the group index and data index occupy the same file.

Definitions:

<tables id="tabl0008" num="0008"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="16mm" /><colspec colnum="2" colname="col2" colwidth="30mm" /><tbody><row><entry>SIZE:</entry><entry>16-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>Number of groups</entry></row></tbody></tgroup></table></tables>

The following is repeated for each group defined: <tables id="tabl0009" num="0009"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="27mm" /><colspec colnum="2" colname="col2" colwidth="83mm" /><tbody><row><entry>INDEX:</entry><entry>32-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry><img file="EP1990609B1_D0038.tif" /></entry></row><row>&lt;entry /&gt;<entry>| 12 - bits |  20 - bits    |</entry></row><row>&lt;entry /&gt;<entry>| File Index | offset |</entry></row><row>&lt;entry /&gt;<entry>File Index: Always 0 for group index</entry></row><row>&lt;entry /&gt;<entry>  offset: offset in bytes to start of index file for this group</entry></row><row><entry>LAT MAX:</entry><entry>24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>NW corner latitude</entry></row><row>&lt;entry /&gt;<entry>Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>Sign: (+) = North, (-) = South</entry></row><row><entry>LAT MIN:</entry><entry>24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>SE corner latitude</entry></row><row>&lt;entry /&gt;<entry>Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>Sign: (+) = North, (-) = South</entry></row><row><entry>LON MIN:</entry><entry>24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>NW corner longitude</entry></row><row>&lt;entry /&gt;<entry>Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>Sign: (+) = East, (-) = West</entry></row><row><entry>LON MAX</entry><entry>24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>SE corner longitude</entry></row><row>&lt;entry /&gt;<entry>Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>Sign: (+) = East, (-) = West</entry></row><row><entry>Memory Usage:</entry><entry>16 bytes per group</entry></row><row>&lt;entry /&gt;<entry>Assume 648 groups worst case = 10,368 bytes</entry></row></tbody></tgroup></table></tables>

Data Index

The data index contains information defining the coverage, resolution and storage location of each individual terrain data file. The data indexes are grouped together per the group index defined above (i.e. group 2's data indexes immediately follow group 1's data indexes).

Definitions:

<tables id="tabl0010" num="0010"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="14mm" /><colspec colnum="2" colname="col2" colwidth="38mm" /><tbody><row><entry>SIZE:</entry><entry>16-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>  Number of indexes</entry></row></tbody></tgroup></table></tables>

The following is repeated for each index defined: <tables id="tabl0011" num="0011"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="28mm" /><colspec colnum="2" colname="col2" colwidth="91mm" /><tbody><row><entry>INDEX:</entry><entry>  32-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry><img file="EP1990609B1_D0039.tif" /></entry></row><row>&lt;entry /&gt;<entry>  | 12 - bits |  20 - bits    |</entry></row><row>&lt;entry /&gt;<entry>  | File Index | offset |</entry></row><row>&lt;entry /&gt;<entry>  File Index: Filename index for data</entry></row><row>&lt;entry /&gt;<entry>    offset: offset in bytes to start of index file for this group</entry></row><row><entry>LAT MAX:</entry><entry>  24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>  NW corner latitude</entry></row><row>&lt;entry /&gt;<entry>  Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>  Sign: (+) = North, (-) = South</entry></row><row><entry>LAT RES:</entry><entry>  8-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>  Number of rows per 1 degree</entry></row><row><entry>LAT MIN:</entry><entry>  24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>  SE corner latitude</entry></row><row>&lt;entry /&gt;<entry>  Scaling: LSB = 180 / 2^23</entry></row><row><entry>LON MIN:</entry><entry>  24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>  NW corner longitude</entry></row><row>&lt;entry /&gt;<entry>  Scaling: LSB = 180 / 2^23</entry></row><row>&lt;entry /&gt;<entry>  Sign: (+) = East, (-) = West</entry></row><row><entry>LON RES:</entry><entry>8-bits - unsigned</entry></row><row>&lt;entry /&gt;<entry>  Number of columns per 1 degree</entry></row><row><entry>LON MAX:</entry><entry>  24-bits - signed</entry></row><row>&lt;entry /&gt;<entry>  SE corner longitude</entry></row><row>&lt;entry /&gt;<entry>  Scaling: LSB = 180 / 2^23</entry></row><row><entry>Memory Usage:</entry><entry>  18 bytes index (terrain file)</entry></row></tbody></tgroup></table></tables><maths id="math0038" num=""><math display="block"><mrow><mi>Assume</mi><mspace width="1em" /><mn>8000</mn><mspace width="1em" /><mi>files</mi><mo>=</mo><mn>144</mn><mi mathvariant="normal">k</mi><mo>−</mo><mi>bytes</mi></mrow></math><img file="EP1990609B1_D0040.tif" /></maths>

Data

The following defines the format for the actual depth (aka elevation) data. The index files above are used to locate the desired elevation file, and also contain information on the location, resolution etc.

Note: for all data types below, the return depth values at 16 bit singed values.

First value is always compression type as defined below: <ul id="ul0007" list-style="none" compact="compact"><li>COMPRESSION TYPE:8 bits - unsigned <ul id="ul0008" list-style="none" compact="compact"><li>Compression: <ul id="ul0009" list-style="none" compact="compact"><li>0 = no compression</li><li>1 = HUFFCODE - type 1</li><li>2 = RLE - BYTE</li><li>3 = Run length word</li><li>4 = constant elevation (RLE-single)</li><li>5 = RLE - DYNAMIC</li></ul></li></ul></li></ul> For type 0, no compression, the uncompressed depth/elevation values are stored directly.

The following definition is for the HUFFCODE compressed data format: <ul id="ul0010" list-style="none" compact="compact"><li>The top of the data contains the decode tables needed to uncompress the terrain data.</li><li>Note: Decompression needs the Number of X and Y values of decoded file (from index file).</li></ul>

Decode tables:

<tables id="tabl0012" num="0012"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="47mm" /><colspec colnum="2" colname="col2" colwidth="94mm" /><tbody><row><entry>FIRSTCODE SIZE:</entry><entry>1 byte - unsigned</entry></row><row>&lt;entry /&gt;<entry>Size in bytes of firstcode and symbol pointer tables (max 32 bytes)</entry></row><row><entry>FIRSTCODE TAB:</entry><entry>n bytes - unsigned</entry></row><row>&lt;entry /&gt;<entry>Firstcode table</entry></row><row><entry>SYMBOL POINTER TABLE:</entry><entry>n words - unsigned</entry></row><row>&lt;entry /&gt;<entry>  Used with Firstcode table to index into symbol table.</entry></row><row><entry>SYMBOL SIZE:</entry><entry>1 word - unsigned</entry></row><row>&lt;entry /&gt;<entry>Size in bytes of symbol table (max 256 words)</entry></row><row><entry>SYMBOL TAB:</entry><entry>n words - signed</entry></row><row>&lt;entry /&gt;<entry>Symbol table. Contains decoded symbol</entry></row><row><entry>FIRSTVALUE:</entry><entry>1 word - signed</entry></row><row>&lt;entry /&gt;<entry>First elevation value. Used by linear predictor</entry></row></tbody></tgroup></table></tables> Note: typical words decode table size is less than 150 bytes. <tables id="tabl0013" num="0013"><table frame="none"><tgroup cols="2" colsep="0" rowsep="0"><colspec colnum="1" colname="col1" colwidth="27mm" /><colspec colnum="2" colname="col2" colwidth="72mm" /><tbody><row><entry>ELEVATIONS:</entry><entry>Compressed elevation values in binary</entry></row><row>&lt;entry /&gt;<entry>Note: padded to align on byte boundary currently.</entry></row></tbody></tgroup></table></tables>

For Compression type 4, (water/same elevation value), only 3 bytes are needed. The compression type byte defined above, and the 16 bit elevation value. This is used for files that contain only one elevation value. This will typically be used for "no-elevation" areas.

Build System

<figref idref="f0024">Figures 36</figref> and <figref idref="f0025">37</figref> show a preliminary look at the steps to build the Terrain database from the original source data. <ol id="ol0003" compact="compact" ol-style=""><li>1. Currently basic input file is 1 degree at 30 arc-seconds. This matches NOAA data. System should be built to handle any file size.</li><li>2. Build system uses a control file automatically generated from a port database and a NOAA provided worldwide terrain file. Control file contains a list of every 1 degree quad, and what the desired resolution of that 1 degree file should be. Resolution is determined by proximity to a port or shoreline and the minimum depth value of that file. 1 of 3 resolutions are currently output, 30, 60, and 120 arc-seconds. In addition, the control file will indicate which 1 degree quads can be combined into one file. This is done for lower resolution quads in an attempt to keep the file sizes even and reduce the number of files.</li><li>3. Some files will need a special extrusion run on them. This will be defined in a separate control file.</li></ol>

Grouping and packaging control files are needed to ensure that the build system groups the files into the correct structure.

Notes on "Terrain Data Embedded Format"

Maps are read from the file system, decompressed, and then used to update "RAM A" as the vessel moves across it. Due to the slow speed of the decompression, two RAM As are used. The detection and display algorithm uses one RAM A while the file picker updates the other RAM A with the latest maps. After the file picker has updated its RAM A, the RAMs are swapped and the process starts over.

The file picker process starts by the TAD asking the file system to open a file with a known, fixed name ("TERRAIN.BMI"). This file contains the file indirection table, the group index table, and the data index tables. The TAD then periodically scans the group index table to find map groups that cover the general vicinity of the aircraft. This step quickly reduces the number of maps that need to be considered for decompression from several thousand down to a few hundred. It identifies candidate groups by comparing the group bounding box stored in the group index table entry against the vessel's current position. The number of group index table entries is stored at the top of the table, and all the entries immediately follow.

When a candidate group is found, the TAD uses the &lt;fileindex&gt; in the group index table entry to locate the file containing the data index tables. If the number is zero (the usual case), it indicates that the data is in the main index file (the one we are already reading). A future option would be to make the number non-zero. It would then identify a secondary index file named in the file indirection table. Once the file containing the data index table is opened, the TAD seeks to the &lt;offset&gt; in the group index table entry and starts reading the data index table for that group.

Each data index table begins with its number of entries. The TAD scans each of the data index table entries looking for any of the maps needed for the current vessel position.

If a data index table entry is found to describe one of the maps we need, the TAD uses the &lt;fileindex&gt; to get the name of the map package file from the file indirection table. A map package file is a concatenation of a couple hundred compressed maps. From there it reads the compression type and calls the correct decompression algorithm to decompress the file. The decompressed data is then up-sampled or down-sampled into the appropriate tiers of RAM A. When up-sampling (filing higher resolution tiers with lower resolution data), the highest resolution data is used. To support this TAD must keep track of the current resolution used to fill each cell of RAM A. For down-sampling the shallowest elevation is always used. The enroute tier of RAM A is always filled with only enroute data. When all map files within the vessel's area have been processed RAM A is released.