System for performing virtual colonoscopy

SYSTEM FOR PERFORMING VIRTUAL COLONOSCOPY

This application is a divisional application of IL 145516.

SPECIFICATION

TECHNICAL FIELD

The present invention relates to a system for performing virtual colonoscopy.

BACKGROUND OF THE INVENTION

Colon cancer continues to be a mqjor cause of death throughout the world. !Early detection of cancerous growths, which in the human colon initially manifest themselves as polyps, can greatly improve a patients chance Of recovery. Presently, there are two conventional ways of detecting polyps or other masses in the colon of a patient The first method is a colonoscopy procedure, which uses a flexible fiber-optic tube ealled a colonoscqpe to visually examine the colon by way of physical

1$ rectal entry with the scope. The doctor can manipulate the tube to search for airy abnormal growths in the colon. The colonoscopy, although reliable, is both relatively costly in money and time, and is an invasive, uncomfortable painful procedure for the patient

The second detection technique is the use of a barium enema and two20 dimensional X-ray imaging of the colon. The barium enema is used to coat the colon with barium, and a two-dimensional X-ray image is taken to capture an image of the colon. However, barium enemas may not always provide a view of the entire colon, require extensive pretreatmant and patient manipulation, is often operator-dependent when performing the operation, exposes the patient to excessive radiation and can be less sensitive than a colonoscopy. Due to deficiencies in the conventional practices described above, a more reliable, less intrusive and less expensive way to check the colon for polyps is desirable, A method to examine other human organs, such as the lungs, for masses in a reliable, cost eflfective way and with less patient discomfort is also desirable.

Two-dimensional (2D) visualization of human organs employing currently available medical imaging devices, such as computed tomography and MRI (magnetic resonance imaging), has been widely used for patient diagnosis. Threedimensional images can be formed by stacking and interpolating between twodimensional pictures produced from the scanning machines. Imaging an organ and visualizing its volume in three-dimensional space would be beneficial due to its lack of physical imtusion and the ease of data manipulation. However, the _of the three-dimensional volume image must be properly performed in order to folly exploit the advantages of virtually viewing an organ from the inside.

When viewing the three dimensional C3Dⁿ) volume virtual magA _of an environment, a functional model must be used to explore the virtual space. One possible model is a virtual camera which can be used as a point of reference for the viewer to explore the virtual space. Camera control in the context of navigation within a general 3D virtual environment has been previously studied. There are two conventional types of camera control offered for navigation of virtual space. The first gives the operator full control of foe camera which allows foe operator to manipulate the camera in different positions and orientations to achieve the view desired. The operator will in effect pilot the camera. This allows foe operator to explore a particular section of interest while ignoring other sections. However, complete control of a camera in a large domain would be tedious and tiring, and an operator might not view all the important features between foe start and finishing point of the exploration. The camera could also easily get ״Josf in remote areas or he .'crashed׳. into one of the walls by an inattentive operator or by numerous unexpected obstacles. The second technique of camera control is a planned navigat»™ method, which assigns foe camera a predetermined path to take and which changed by foe operator. Ulis is akin to having an engaged autopilof. This allows foe operator to concentrate on the virtual space being viewed, and not have to wony about steering into walls of foe environment being examined. However, this second technique docs not give the viewer the flexibility to alter the course or investigate an interesting area viewed along the flight path.

It would be desirable to use a combination of the two navigation techniques described above to realize the advantages of both techniques while minimizing their respective drawbacks. It ־would be desirable to apply a flexible navigation technique to the examination of human or animal argans which are represented in virtual 3D space in order to perform a non-intrusive painless thorough *vaminatian. The desired navigation technique would further allow for a complete »*amination of a virtual organ in 3D space by an operator allowing flexibility while ensuring a smooth path and complete examination through and around the organ. It would be additionally desirable to be able to display the exploration of the organ in a real time setting by using a technique which minimizes the computations necessary for viewing the organ. The desired technique should also be equally applicable to exploring any virtual object

SUMMARY

The present invention relates to a system for performing virtual colonoscopy comprising: an imaging scanner for acquiring image data of a colon;

a processor, said processor receiving the image data and identifying the interior of the colon, generating a centerline for navigating through the interior of foe colon, detecting a collapsed region of foe interior cf the colon, and extending foe centerline through the collapsed region a display unit operatively coupled to the processor for displaying a representation of foe colon.

The invention generates a three-dimensional visualization image of an object such a$ a human organ using volume visualization techniques and explores foe virtual image using a guided navigation system which allows the operator to travel along a predefined flight path and to adjust both foe position and viewing angle to a particular portion of interest in foe image away from the predefined path in order to identify polyps, cysts or other abnormal features in foe organ.

The inventive technique for three-dimensional virtual examination of an object includes producing a discrete representation of foe object in volume elements, defining the portion of foe object which is to be examined, performing a navigation operation in the virtual object and displaying foe virtual object in real time during the navigation.

3a

The inventive technique for a three-dimensional virtual examination as applied to an organ of a patient includes preparing the organ for scanning, if necessary, scanning the organ and converting the data into volume elements, defining the portion of the organ which is to be examined, performing a guided navigation operation in the virtual organ and displaying the virtual organ in real time during the guided navigation.

™Tod examinuion, il is often desirable to view a ייי*-*«**-»,*..!,,,,.,!, _ToP^a®^Mmsuc*^la10P^edtioa,a1a«hodfordearooicdlydeaasmga11in1ageBaal» P־rf־_m4־l_v0־־^_{tbtilmi־diaBapl}^_rfTO^_d^^^

N־xt,.־_teiWopeM^_{ij|J־־fcm1)־}

*.w* o־־־d־־d_i־a,«_tera־d_{usteofTOtae־le}^_[!fflremoved from fee image data.

^^1e־'^>ss’^^llS^oP^erationsanbo_Perfbnaed byevaluadagaphnali^of damm.ate.faermiaa.ndgbbmi.aad aMtajty vd^teaeyoj^. ____ ™'^“^^^^dby.pplyiasaa.ixWprntaHU״.

more than one material type.

A־d«n₁־iv־daWta8«p־»\m^^ non-colomc tissue. ’ ^11h“^ob*^a°^f^״«^ data can be visualized at a later time.

It is another object of the invention to generate 3D volume representations of an object, such as an organ, where regions of the object can be using potential fields.

described herein.

^ItlS!^‘^tal“^r,,t’^w״^tll»»™»<iMWl_Jsea_m<>_di&_dZtaffaW»^<».d״_imf_־־_ft־._{umte־fowmniW]Sre(11]fa1J&t8}viewing screen. * ^,,b“^te״^bJ־“<>f״»wv_rai_t»_toKrignop8ci^_mffld־nBto«k vote־ Otarn m the _{to ordcr M} ״Λ*,,*,, ““^״='״־rfeft־.״.r._Sf_fc»_bjMk3ivi!,״_{d Aeatarfd}, also be composited using the opacity coefficients.

BRIEF Ρξ?ς?ρ_ΙΡΤ[ηΝ PETTIE DRAWINGS ־P»™ S»m the ft;;»«־ _{dettaed dKajp״OT b MbkSm} ־־»W־־״־־ «ρ», ־״«, .

F>i 1 »״ is > flow d»n rftl» _Λρ, , perfonns guided navigation in the virtual organ;

^F'^^3i>“^al'^“^f“P״־^»m_Imdto»odd_pl_Ich_Md״_Bof the submarine camera; ™^10I sub-

F,₈m4־ volumetric colon which identifies two blocking walls* *⁰^”*¹^“¹kn which shows a discrete suh-vahnneeiKiosed by the biMkmgwaUj and the colon surface; **^5 ^F1J^ ⁷’⁵*dkfircniinustrating a two dimensional cross-section of a volumetnc colon which has multiple layers peeled away;

Figure 8 is a diagram illustrating a two dimensional cross-section of a volumetrio colon which contains the remai^ng flight _path;^F’^Eurc ’^{s a} chart of the steps of generating a volume visualization of the scanned organ;

Figure 10 is an illustration of a virtual co divided into cells;

FignreliBb.^ieni^״״,,^^^^^ depicting the organ in Fig. 11 A;

^F1eure HCisa farther graphical depiction of a stab tree generated while depicting the organ in Fig. 1 1a;

objects within certain cells ofthe scene;

.....

depicting the scene in Fig. 12A־ . Figures 12C-12E are farther graphical depictions of stab trees generated while depicting the image in Fig. J2A;

_ . ¹³ i®³ two dimensional representation ofa virtual colon

Gaining a polyp whose layers can be removed;

MO a human organ in attendance with the invention;

method;

Figure 17 is a perspective view diagram of an lung region in the image slice of Figure JfiA;

bone; ^reglon1ncIud^g a portion of the coion and

DETAH FT) npscRtimnjj

While the methods and systems described in this annh>־>t .

־ ־־»™ץ.™_s (he patiM koft^ _ω physical prob_e. Other examples ofo™ _{wWc}1 fc} * °^f

^״1 /siem, me nean and blood vessels.

ΙΟ ״ώ« volm־ vtatalon

-**י ־«!־־«»־»י.

*.“.«*.».***«cOie.tataMta!,* , '¹.׳ג¹“⁰”‘⁴* י “‘^k־*^־c«tan״_ai־rio_Sc_ul«_w1_a(Min־ Thftft “ “ ⁰*r » expand ft to «»«- th־ «too. Depending ο™ _Λ־L™ ״ «״ “״־ i״P־d־־_t.־d״n_k־c01״«_sul^_i^_B^^'״^m״^te“^ ״״derftdfttftgnftbtbo״^ .

Ah־™ev_dy,_lh־^_{ftrritMJya!mi]}^ ־»״־llttbemteivs. waste prior מ or duing the ^{6 e 00} מס c® remove the virtual

StepW^oesuotZtobeX^ lineinFig. 1. ^X“^^{,OI1S 35} ^«ted by the da^

Step 103 _SCans the Orga״ _{which is t0 e}^anaPP^aratus_weUk_n0w_niflth_eartjSuch_asa__i._CT¹*⁶«־annex can be oraZeaitaMRimachinef ., ⁵⁰““®¹י^forsca™ing a colon ume xorscannmg a lung labeled _for .

nerantermoftbeaUntn^״,^ ” thx־־on_gB.

.*י*“—&lt;—.

ha.־ necessaty for tte ״-־tath. _1:.

»rth־־pl״־i־_fl־xu_re־_ftan₁־on_t»₁₁₁־_TOm¹־.־*.-״'»־™™'״P ־« ־»־״־־־de, b, dotodb^^'X ^^J 7 ζ “™h *־ “־ nfCoovnnfagcnn^^^^^ . ⁰“ ’ ־«I Method ^c Sepeaentanonsin» ^־nelVoxt,.־^^^

1«.t^ohftbtrtb,i״^^. W26.

$ «MOtaie.

eaamd d ‘j“'* °^{f 512} *^,512׳^p1M1>⁷*“ . ’β® »mb« of 2D slices are zr?^3Dr^1s״״»״‘’״«’*״׳“^ ׳«.ι.-«

J2^D ״»־ bopcrfonoed by 6־ sc״^ _nKhh ־»ץ «» b £» U.S. Pa No. 4,585,85¢ entitled _{Mahod Appara״JJ}

551,fi)edN0v. 11, 1588; which Ulmbyio״^^,־־^^ ““^^^Wbeioterestedina^^^^ to- 7 Τ’”” ¹’®‘”“^,“™.י dimensional slice overview _ΑΜ0νχ ״׳״ '““'׳ה ^toM“ <־‘ .־.־ybored, mouse ot spaeebaii) ־״ be _M־d ״ ^“^’^^“Woooperaionisdeaiedas ®⁸⁴¹®^4101,Sb an envnwuneat along a Redefined or amomaticallvDredrt .^ a8btpaa,whi_Cb_cmttmm,11״_>._J,״״._J. _1il ™-^eanresaX^Z^^Z^⁶“.^ ration With the camera, so that the camera can navigate through a virtual allowth־opemt_wmn»nip_ldat_־theeam־n₁wb₀,_1)־ce_!JKy. The prefab “‘»^*.^«IM.m^b^^ described in detail in Figs. 2 and 3.

Step 109, which can be performed ״״,״״״,,;. _!ttp4e metde of 0» fctm th־ viewpota ?־*«vo_;-tl-,_S־pid־dn,״P_E,_t,_onoperd,״_n.

8^^^031001^01111191100^^1110110.11010^8451)0111181116011800111^04^ ‘*¹”³»ני!™ *י^,*''¹*®⁰י the vast number ofcompetarionsofdataneccssaiy for the display of the virtual organ. Fig. 9 describe this display ־tap in mote detail.

Tlte method deaedbed in Fignm 1 cm also be applied tn scanning ™oltiple organs in a body at the same time. For ־*־־»־ pah״־, ma, be examined ⁸¹⁰d’F“¹*⁰⁸®“^ O'® areas ofhnerest In nep !03 and to select the eurrent wgan ao be exammed in step 103. Forexamplc, thephysidan/opemmr mayinitjaO-select too Felon to vimndlyexpiora and later explore the lung, Alt־m־tiv־ly, !wedMemm doctors with different specialties may virtually «plemdUtecntmo.wu^. ־»»«-&lt;־׳«»lr«_W־_atW^_Wlte. Following nep 109, the^norgmtoh. ״™־ned״s_Sl־a«da11di_Kpo_ni־nwillbedelm־d₁״d«_tp|or_־d. MeeonOnnes until all organs which need examination have been processed.

^^^^“'»»“aiooMIhFigmeleanJmte^^(״ «wle. ־» ״־hnecruml ״»״ «inmin»« 0«־־. can be ־״ρρ״־^ _ explored in the same manner.

the״,xu ⁸'^m־‘^'^,'‘^^K'^,^^>’”»'l־l״hiehp_־rfclma ^״^»™*״״m^iOZ When them ™_pmtw »־.־»״mn^dbeodthce^^^^^^^^^^ . the colon to another. Bmingtheplannedadgata^^^^.^ c־־taof_th־eotan_fcr־buluh«b־_to™״s_of_th־_Mlo_ricsurf־(!s. ft״ interesting region is encountered, the operator of the virtual camera using guided navigation can interactively bring the camera dose to a specific region and direct the motion and angle of the camera to study the interesting area in detail, without unwillingly colliding with the walls of the colon. The operator can control the camera 5 with a standard interface device such as a keyboard, mouse or non-standard device such as a spacebalJ, In order to fully operate a camera in a virtual environment, six degrees of freedom for the camera is required. The camera must be able to move in the horizontal, vertical, and Z direction (axes 217), as well as being able to rotate in another three degrees of freedom (axes 219) to allow the camerato move and scan all 10 sides and angles of a virtual environment The camera model for guided navigation includes an inextensible, weightless rod 201 connecting two particles x, 203 and Xj 205, both particles being subjected to a potential field 215. The potential field is defined to be highest at the walls of the organ in order to push the camera away from the walls

The positions of the panicles are given by x! and x!, and they are assumed to have the same mass m. A camera is attached al the head of the submarine X, 203, whose viewing direction coincides with xpc,. The submarine can perform translation and rotation around the center of mass x of the model as the two particles are affected by the forces from the potential field V(x) which is defined below, any friction forces, and any simulated external force. The relations between x״ x₂, and x are as follows:

X = (xwJ, r - (ΓίίηθεΜφ,ηΙηθήπφ,κύίθ), x, = x + n x□ - x-r, (1) where r, Θ and φ are the polar coordinates of the vector xx!.

The kinetic energy of the model, T, is defined as the summation of the kinetic energies of the movements of x, and x,:

ί = Τ(*ϊ + *ί) &amp;

5־ mx² + τηί’ = 171( έ¹ + ע* + i*} + + φ’βίη’ί), (2)

Then the equations for the motion of the submarine model are obtained by using LaGrange's equation:

s(F>־F’£⁽״‘^,B;). <*>

it'd# dy Ξί where the QjS are the generalized coordinates of the model and can be considered as the variables of time t as:

⁼ — (»?ן96«54י93י«21,5) with ψ denoting the roll angle of our camera system, which will be explained later. The F,s are called the generalized forces. The control of the submarine is performed by applying a simulated external force to x,, i*e®t ⁵⁵ (isj ^ws and it is assumed that both x, and x, are affected by the forces from the potential fidd 10 and the frictions which act in the opposite direction of each particle's velocity. Consequently, the generalized forces are formulated as follows:

F! = -mVV(xi) - λχι + F«b

F₂ = -mVV(Xi) - kij, (5) where k denotes the friction coefficient of the system. The external force is applied by the operator by simply clicking the mouse button in the desired direction 207 in the generated image, as shown in־ Figure 2. This camera model would then be moved in that direction. This allows the operator to control at least five degrees of freedom of the camera with only a single click of the mouse button. From Equations (2), (3) and (S), it can be derived that the accelerations of the five parameters of our submarine model as!

־ Wfe). ^ki^F.

2' 6a Ba 5 1זזm'

<img file="IL178769A_D0001.tif" />

. Wfo), Η Λ .2 6* Qx m 2m' Φ’sinicosi i . 1 ־^ + :—(F.easf cos φ + F״ cos ί sin φ — F ππat Fft 2mt* ^[-2^wi fc * 1 ——φύα.9 + -—(-F,an d + F_v cos 0)1, 2 יוזזmr (¢) where x and x denote the first and the second derivative of x, respectively, anj ί dV(xl fiV(x) ) ( 3x * 3y ' fir J denotes the gradient of the potential at a point x.

׳Theterms φ’δίηθοοβθ of g and - ^CosS of φ are called the sin© centrifugal force and die Coriolis force, respectively, and they are concerned with the exchange of angular velocities of the submarine. Since the model does not have the moment of inertia defined for the rod of the submarine, these terms tend to an overflow of the numeric calculation of φ. Fortunately, these terms become rignififfant only when the angular velocities of the submarine model are agnifmant which essentially means that the camera moves too fast. Since it is meaningless to allow the camera to move so fast because the Organ could not be properly viewed, these terms are minimized in our implementation to avoid the overflow problem.

From the first three formulas of Equation (6), it is known that the submarine cannot be propelled by the external force against the potential field if the following condition is satisfied!

ΐννίχΟ+νηχΟ^Μ.

זח

Since the velocity of file submarine and the external force F_ta have upper limits in our implementation, by assigning sufficiently high potential values at the boundary of foe objects, it can be guaranteed that the submarine never bumps against the objects or walls in the environment.

As mentioned previously, the roll angle ψ of the camera system ת feds to be considered. One possible option allows the operator full control of foe angle φ. However, although the operator can rotate the camera freely around the rod of foe model, he or she can easily become disoriented. The preferred technique mimrs foa! the upper direction of the camera is connected to a pendulum with m»« m,301, which rotates freely around the rod of the submarine, as shown in Figure 3. The direction of the pendulum, rj, is expressed as;

rj ז :=׳!(«» δ cos gin ψ + sin^cos^.cosfsin^Ka^ — cos ψεοβψ,-־ sin fem ψ).

although it is possible to calculate the accurate movement of this pendulum along with the movement of the submarine, it makes the system equations too complicated.

Therefore, it is assumed that all the generalized Coordinates except the roll angle ψ are constants, and thus define the independent kinetic energy for the pendulum system as: τ - Zi®i» ₌ ”wP-ii T, - yrs = — 4 5 This simplifies the model for the toll angle. Since it is assumed in this model that the gravitational force

Fj = Tftjg — (τπ2^_ζ, ntg&lt;7y)7n.a£*) acts at the mass point the acceleration of ψ can be derived using T^nrang«׳; equation as:

ψ ~ — {&amp;(cos 6 cos^cos^ — sin. ^irin 1b)

2־ז +g_v(cos &amp; sin 4 cos ψ 4־ cos sin u .

+^(-sin 0 cos ψ)}--ψ. (7ן nij » ׳

From Equations (6) and (7), the generalized coordinates q(t) and their derivatives q(t) arc calculated asymptotically by using

Taylor series as:

q(t+k) - qW + Aq^ + yqW + O^’), q(t + fc) = q(f) + fcq(t) + O(fc’), to freely move the submarine. To smooth foe submarine's motion, foe time step h is selected as an equilibrium value between being as small as possible to smooth the motion but as large as necessary to reduce computation cost.

Definition of the Potential Field

The potential field in the submarine model in Figure 2 defines the boundaries (walls or other matter) in the virtual organ by assigning a high potential to . the boundary tn order to ensure that the submarine camera does not collide with the walls or other boundary. If the camera model is attempted to be moved into a high potential area by foe operator, the camera model will be restrained from doing so unless the operator wishes to examine the organ behind flic boundary or inside a polyp, for example. In foe case of performing a virtual colonoscopy, a potential field value is assigned to each piece of volumetric colon data (volume element), a particular region of interest is designated in step 105 of Fig. 1 with a start and finish point, the voxels within the selected area of the scanned colon are identified using conventional blocking operations. Subsequently, a potential value is assigned to every voxel x of the selected volume based cm the following three distance values: the distance from the finishing point dt(x), the distance from the colon surface ds(x) and the distance from the center-line of the colon space dc[x). dt(x) is calculated by !!«»ng a conventional growing strategy. The distance from the colon surface, ds(x), is computed using a conventional technique of growing from the surface voxels inwards. To determine dc(x), foe center-line of the colon from the voxel is first extracted, and then dc(x) is computed using the conventional growing strategy from foe center-line of the colon.

To calculate the center-line of the selected colon area defined by the user-specified start point and the user-specified finish point, the maximum value of ds(x) is located and denoted dtnax. Then for each voxel inside the area of interest, a cost value of dmax - ds(x) is assigned. Thus the voxels which are close to the colon surface have high cost values and the voxels close to the center line have relatively low cost values. Then, based on the cost assignment, tee single-source shortest path technique which is well known in the art is applied to efficiently compute a minimum cost path from the source point to the finish point. Ulis low cost line indicates the center-line or skeleton of the colon section whieh is desired to be explored. This technique for determining the center-line is the preferred technique of the invention.

To compute the potential value V(x) for a voxel x inside the area of interest, the following formula is employed:

^v« = ^c-^w+c‘(<(^))״ W where C_|t 0_נ> μ and v are constants chosen for the task. In order to avoid any collision between the virtual camera and the virtual colonic surface, a sufficiently large potential value is assigned for all points outside the colon. The gradient of the potential field will therefore become so significant that the submarine model camera will never collide with the colonic wall when being nm

Another technique to determine the center-line of the path in the colon is called the peel-layer technique and is shown in Figure 4 through Figure 8.

Figure 4 shows a 2D cross-section of the volumetric colon, with the two side walls 401 and 403 of the colon being shown. Two blocking walk are selected by the operator in order to define tee section of tee colon which is of interest to examine. Nothing can be viewed beyond the blocking walls. This helps reduce the number of computations when displaying the virtual representation. The bilking walls together with side walls identify a contained volumetric shape of the colon which is to be explored.

Figure 5 shows two end points of the flight path of the virtual examination, the start volume element 501 and the finish volume elament 503. The start and finish points are selected by the operator in step 105 of Fig. 1. The voxels between the start and finish points and the colon sides are identified and as indicated by the area designated with x״s in fig. 6. The voxels arc three-dimensional representations of the picture element.

The peel-layer technique is then applied to the identified and marked voxels in Fig. 6. The outermost layer of all the voxels (closest to the colon walls) is peeled off step-by-step, until there is only one inner layer of voxels remaining, stmaH differently, each voxel furthest away from a center point is removed if the removal does not lead to a disconnection of the path between the start voxel and the voxel. Figure 7 shows the intermediate result after a number of iterations of peeling the voxels in the virtual colon are complete. The voxels closest to the walls of the colon have been removed. Fig. 8 shows the final flight path for the camera model down the center of the colon after all the peeling iterations are complete. This produces essentially a skeleton at the center of the colon and becomes the desired flight path for the camera model.

Z- Buffer assisted visibility

Figure 9 describes a real time visibility technique to display of virtual images seen by the camera model in the virtual three-dimensional volume representation of an organ. Figure 9 shows a display technique using a modified Z buffer which corresponds to step 109 in Fig. 1. The number of voxels which could be possibly viewed from the camera model is extremely large. Unless the total number of elements (or polygons) which must be computed and visualized is reduced from an entire set of voxels in the scanned environment, the overall number of computations will make the visualisation display process exceedingly slow for a large internal area. However, in the present invention only those images which are visible on the colon surface need to be computed for display. The scanned environment can be subdivided into smaller sections, orcelk TheZ buffer technique then renders only a portion of the cells Which are visible from the camera. The Z buffer technique is also used for three-dimensional voxel representations. The use of a modified Z buffer _Λε number of visible voxels to be computed and allows for the real time examination of the virtual colon by a physician or medical technician.

The area of interest from which the center-line has been calculated in step 107 is subdivided into cells before the display technique is applied. Cells are collective groups of voxels which become a visibility unit. The voxels in each cell will be displayed as a group. Each cell contains a number of portals through which the other cells can be viewed. The colon is subdivided by beginning at the selected start point and moving along the center-line 1001 towards the point. The colon is then partitioned into ceils (for example, cells 1003,1005 and 1007 in Fig. 10) when a predefined threshold distance along the center-path is reached. The threshold distance is based upon the specifications of the platform upon which the visualization technique is performed and its capabilities of storage and processing. The cell size is directly related to the number of voxels which can be stored and processed by the platform. One example of a threshold distance is 5cm, although the distance can greatly vary. Each cell has two cross-sections as portals for viewing outside of the cell as shown in Fig. 10.

Step 901 in Fig. 9 identifies the cell within the selected organ which currently contains the camera. The current cell will be displayed as well as all other cells which are visible given the orientation of the camera. Step 903 builds a stab tree (tree diagram) of hierarchical data of potentially visible cells from the ™יזז^ (through defined portals), as will be described in further detail hereinbelow. The stab tree contains a node for every cell which may be visible to the camera. Some of ־the cells may be transparent without any blocking bodies present so that more than one cell will be visible in a single direction. Step 90S stores a subset of the voxels from a cell which include the intersection of adjoining cell edges and stores them at the outside edge of the stab tree in order to more efficiently determine which cells are visible.

Step 907 checks if any loop nodes are present in the stab tree. A loop node occurs when two or more edges of a single cell both border on the same nearby cell. This may occur when a single cell is surrounded by another cell. If a loop node is identified in the stab tree, the method continues with step 909. If there is no loop node, the process goes to step 911.

Step 909 collapses the two cells making up the loop node into one large node. The stab tree is then corrected accordingly. This eliminates the problem of viewing the same cell twice because of a loop node. The step is performed on all identified loop nodes. The process then continues with step 911.

Step 911 then initiates the Z-buffer with the largest 2 value. The Z value defines the distance away from the camera along the skeleton path. The tree is then traversed to first check the intersection values at each node. If a node intersection is covered, meaning that the current portal sequence is occluded (which is determined by the Z buffer test), then the traversal of the current branch in the tree is stopped. Step 913 traverses each of the branches to check if the nodes are covered and displays them if they are not

Step 915 then constructs the image to be displayed on the operator's screen from the volume elements within the visible cells identified in step 913 using one of a variety of techniques known in the art, such as volume rendering by compositing. The only cells shown are those which are identified as potentially visible. This technique limits the number of cells which requires calculations in order ׳. to achieve a real time display and correspondingly increases the speed of the display for better performance. This technique is an improvement over prior which calculate all the possible visible data points whether or not they are actually viewed.

Figure 11A is a two dimensional pictorial representation of an organ which is being explored by guided navigation and needs to be displayed to an operator. Organ 1101 shows two side walls 1102 and an object 1 IOS in die center of the pathway. The organ has been divided into four ceDs A 1151. B 1153, c tl55ar«i D 1157. The camera 1103 is feeing towards cell D1157 and has a field of vision defined by vision vectors 1107,1108 which can identify a cone-shaped field. The cells which can be potentially viewed are cells B 1153, C1155 and D 1157. Cell C 1155 is completely surrounded by Cell B and thus constitutes a node loop,

Fig. 1 IB is a representation of a stab tree built from the cells in Fig. 11A. Node A1109 which contains the camera is at the root of the tree. Asightline or sight cone, which is a visible path without being blocked, is drawn to node B1110. Node B has direct visible sight lines to both node C1112 and node D 1114 and which is shown by the connecting arrows. The sight line of node C 1112 in the direction of the viewing camera combines with node B 1110. Node C1112 and node B 1110 will thus be collapsed into one large node B' 1122 as shown in Fig. 11C.

Fig. 11C shows node A1109 containing the camera adjacent to node B¹1122 (containing both nodes B and node C) and node D1114. The nodes A, B¹ and D will be □splayed at least partially to the operator.

Figs 12A - 12E illustrate the use of the modified Z buffer with cells that contain objects which obstruct the views. An object could be some waste material in a portion of the virtual colon. Fig. 12A shows a virtual space with 10 potential cells: A 1251, B 1253, C1255, D 1257, E1259, F1261, G 1263, H 1265, 11267 and J1269. Some of the cells contain objects. If the camera 1201 is positioned in cell 11267 and is facing toward cell F1261 as indicated by the vision vectors 1203, then a stab tree is generated in accordance with the technique illustrated by the flow diagram in Fig. 9. Fig. 12B shows the stab tree generated with the intersection nodes showing for the virtual representation as shown in Fig. 12A. Fig. 12B shows cell 11267 as the root node of the tree because it contain st!», camera 1201. Nodel 1211 is pointing to nodeF 1213 (as indicated with an armw), cell F is directly connected to the sight line of the camera. Node F 1213 is painting to both node B 1215 tod node E1219. Node B1215 is pointing to node.A 1217. Node C 1202 is completely blocked from the line of sight by camera 1201 50 is not included in the stab tree.

Fig. 12C shows the stab tree after node 11211 is rendered on the display for the operator. Node 11211 is then removed from the stab tree because it has already been displayed and node F 1213 becomes the root Fig. 12D shows that node F 1213 is now rendered to join node 11211. The next nodes in the tree connected by arrows are then checked to sec if they are already covered (already processed). In this example, all of the intersected nodes from the camera positioned in cell 11267 has been covered so that node B 515 (and therefore dependent node A) do not need to be rendered on the display.

Fig. 12E shows node E 515 being checked to determine if its intersection has been covered. Since it has, the only rendered nodes in this **.ample of Figure 12A-12E arc nodes I and F while nodes A, B and E are not visible and do not need to have their cells prepared to be displayed.

The modified Z buffer technique described in Figure 9 allows for fewer computations and can be applied to an object which has been represented by voxels or other data elements, such as polygons.

Figure 13 shows a two dimensional virtual view of a colon with a large 5 polyp present along one of its walls. Figure 13 shows a selected section of a patient’s colon which is to be examined further. The view shows two colon walls 1301 and 1303 with the growth indicated as 1303. Layers 1307,1309, and 1311 show inner layers of the growth. It is desirable for a physician to be able to peel the layers of the polyp or tumor away to look inside of the mass for any cancerous or other harmful 10 material. This process would in effect perform a virtual biopsy of the mass without actually cutting into the mass. Once the colon is represented virtually by voxels, the process of peeling away layers of an object is easily performed in a similar manner as described in conjunction with Figs. 4 through 8. The mass can also be sliced so that a particular cross-section can be examined. In Fig. 13, a planar cut 1313 can be made 15 $0 that a particular portion of the growth can be examined. Additionally, a userdefined slice 1319 can be made in any manner in the growth. The voxels 1319 can either be peeled away or modified as explained below.

A transfer function can he performed to each voxel in the area of interest which can make the object transparent, semi-transparent or opaque by altering 20 coefficients representing the translucently for each voxel. An opacity coefficient is assigned to each voxel based on its density. A mapping function then transforms the density value to a coefficient representing its translucency. A high density scanned voxel will indicate either a wall or other dense matter besides simply open space. An operator or program routine could then change the opacity coefficient of a voxel or 25 group of voxels to make them appear transparent or semi-transparent to the submarine camera model. For example, an operator may view a tumor within or outside of an entire growth. Or a transparent voxel will be made to appear as if it is not present for the display step of Figure 9. A composite of a section of the object can be created using a weighted average of the opacity coefficients of the voxels in that section.

If a physician desires to view the various layers of a polyp to look for a cancerous areas, this can be performed by removing the outer layer of polyp 1305 yielding a first layer 1307. Additionally, the first inner layer 1307 can be stripped back to view second inner layer 1309. The second inner layer can be stripped back to vigw third inner layer 1311, etc. The physician could also slice the polyp 1303 and view only those voxels within a desired section. The slicing area can be completely user-defined.

Adding an opacity coefficient can also he used in other ways to aid in the exploration of a virtual system. If waste material is present and has a density as other properties within a certain known range, the waste can be made transparent to the virtual camera by changing its opacity coefficient during the examination. This will allow the patient to avoid ingesting a bowel cleansing agent before the procedure 10 and make the examination faster and easier. Other objects can be similarly made to disappear depending upon the actual application. Additionally, some objects like polyps could be enhanced electronically by a contrast agent followed by a use of an appropriate transfer function.

Figure 14 shows a system for performing the virtual examination of an 15 object such as a human organ using the techniques described in this specification.

Patient 1401 lies down on a platform 1402 while scanning device 1405 scans the area that contains the organ or organs which are to be examined. The scanning device 1405 contains a scanning portion 1403 which actually takes images of the patient and an electronics portion 1406. Electronics portion 1406 comprises an interface 1407, a 20 central processing unit 1409, amemoiy 1411 for temporarily storing the scanning data, and a second interface 1413 for sending data to the virtual navigation platform. Interface 1407 and 1413 could be included in a single interface component or could be the same component. The components in portion 1406 are connected together with conventional connectors.

In system 1400, the data provided from the scanning portion of device

1403 is transferred to portion 1405 for processing and is stored in memory 1411. Central processing unit 1409 converts the scanned 2D data to 3D voxel data and stores the results in another portion of memory 1411. Alternatively, the converted data could be directly sent to interface unit 1413 to be transferred to the virtual navigation 30 terminal 1416. The conversion of the 2D data could also take place at the virtual navigation terminal 1416 after being transmitted from interface 1413. In the preferred embodiment, the converted drta is transmitted over carrier 1414 to the virtual navigation terminal 1416 in order for an operator to perform the virtual examinattan The data could also be transported in other conventional ways such as storing the data on a storage medium and physically transporting it to terminal 1416 or by ting satellite transmissions.

The scanned data may not be converted to its 3D represantetian ™til the visualization rendering engine requires it to be in 3D form. This saves computational steps and memory storage space.

Virtual navigation tetminal 1416 includes a screen for viewing the virtual organ or other scanned image, an electronics portion 1415 and interface control 1419 such as a keyboard, mouse or spaceball. Electronics portion 1415 comprises a interface port 1421, a central processing unit 1423, other components 1427 necessary to run the terminal and a memory 1425. The components in terminal 1416 axe connected together with conventional connectors. Tbe converted voxel data is received in interface port 1421 and stored in memory 1425. The central praees.»nr unit 1423 then assembles the 3D voxels into a virtual representation and runs the submarine camera model as described in Figures 2 and 3 to perform the virtual examination. As the submarine camera travels through the virtual organ, the visibility technique as described in Figure 9 is used to compute only those areas which are visible from the virtual camera and displays them on screen 1417. A graphic» accelerator can also be used in generating the representations. The operator can use interface device 1419 to indicate which portion of the scanned body i$ desired to be explored. The interface device 1419 can further be used to control and move the submarine camera as desired as discussed in Figure 2 and its accompanying description. Terminal portion 1415 can be the Cube-4 dedicated system box, generally available from the Department of Computer Science al the State University of New York at Stony Brook.

Scanning device 1405 and terminal 1416, or parts thereof, can be part Of the same unit A single platform would be used to receive the scan imaga data, connect it to 3D voxels if necessary and perform the guided navigation,

An important feature in system 1400 is that the virtual organ can be examined at a later time without the presence of the patient Additionally, the virtual examination could take place while the patient is being seamed !he scan data can also be sent to multiple terminals which would allow more than one doctor to view the inside of the organ simultaneously. Thus a doctor in New York could be looking at the same portion of a patient's organ at the same time with a doctor in California while discussing the case. Alternatively, the data can be viewed at different times. Two or more doctors could perform their own examination of the same data in a difficult case. Multiple virtual navigation terminals could be used to view the same scan data. By reproducing the organ as a virtual organ with a discrete set of data, there are a multitude of benefits in areas such as accuracy, cost and possible data manipulations. The above described techniques can be further enhanced in virtual colonoscopy applications through the use of an improved electronic colon cleansing technique which employs modified bowel preparation operations followed by image segmentation operations, such that fluid and stool remaining in the colon during a computed tomographic (CT) or magnetic resonance imaging (MR!) scan can be detected and removed from the virtual colonoscopy images. Through the use of such techniques, conventional physical washing of the colon, and its associated inconvenience and discomfort, is minimized or completely avoided.

Referring to Figure 15, the first step in electronic colon cleansing is bowel preparation (step 1510), which takes place prior to conducting the CT or magnetic TR^nnance imaging (MRI) scan and )5 intended to create a condition where residual stool and fluid remaining in the colon present significantly different image properties from that of the gas-filled colon interior and colon wall. An exemplary bowel preparation operation includes ingesting three 250 cc doses of Barium Sulfate suspension of 2.1 % W/V, such as manufactured by E-Z-EM, Inc .,of Westbury, New Yoik, during the day prior the CT or MRI scan. The three doses should be spread out over the course Of the day and can be ingested along with three meals, respectively. The Barium Sulfate serves to enhance the images of any stool which remains in the colon. In addition to the intake of Barium Sulfate, fluid intake is preferably increased during the day prior to the CT or MRI scan. Cranberry juice is known to provide increased bowel fluids and is preferred, although water can also be ingested. In both the evening prior to the CT scan and the morning of the CT scan, 60 ml of a Diatrizoate Meglumine and Diaztrizoate Sodium Solution, which is commercially available as MD-Gastrovicw, manufactured by Mallinckrodt, Inc. □f St. Louis,

Missouri, can be consumed to enhance image properties of the colonic fluid. Sodium phn^phate can also be added to the solution to liquilize the stool in the colon, which provides for more uniform enhancement ofthe colonic fluid and residual stool The above described exemplary preliminary bowel preparation 5 operation can obviate the need for conventional colonic washing protocols, which can call for the ingestion of a gallon of Golytely solution prior to a CT scan.

Just prior to conducting the CT scan, an intravenous injection Of 1 ml of Glucagon, manufactured by Ely Lily and Company, of Indianapolis, Indiana can be administered to minimize colon collapse. Then, the colon can be inflated using 10 approximately 1 OOOcc of compressed gas, such as CO_1־ or room air, which can be introduced through a rectum tube. At this point, a conventional CT scan is performed to acquire data from the region of the colon (step 1520). For example, data can be acquired using a GE/CTI spiral mode scanner operating in a helical mode of 5mm,

1.5-2.0:1 pitch, where the pitch is adjusted based upon the patient's height in a known 15 manner. A routine imaging protocol of 120 kVp and 200-280 ma can be utilized for this operation. The data can be acquired and reconstructed as 1mm thick slice images having an array size of 512x512 pixels in the field of view, which varies from 34 to 40 cm depending on the patient's size, the number of such slices generally varies under these conditions from 300 to 450, depending on the patient’s height The image data 20 set is converted to volume elements or voxels (step 1530).

Image segmentation can be performed in a number of ways. In one present method of image segmentation, a local neighbor technique is used to classify voxels of the image data in accordance with similar intensity values. In this method, each voxel of an acquired image is evaluated with respect to a group of neighbor 25 voxels. Hie voxel Of interest is referred to as the central voxel and has an associated intensity value. A classification indicator for each voxel is established by comparing the value of the central voxel to each of its neighbors. If the neighbor has the same value as the central voxel, the value of the classification indicator is incremented. However, if the neighbor has a different value from the central voxel, the

0 classification indicator for the centra) voxel is decremented. The central voxel is then classified to that category which has the maximum indicator value, which indicates the most uniform neighborhood among the local neighbors. Each classification is indicative of a particular intensity range, which in turn is representative of one or more material types being imaged, *The method can bc further enhanced by employing a mixture probability function to the similarity classifications derived.

An alternate process of image segmentation is performed as two major operations: low level processing and high level feature extraction. During low level processing, regions outside the body contour are eliminated from further processing and voxels within the body contour are roughly categorized in accordance with well defined classes of intensity characteristics. For example, a CT scan of the abdominal region generates a data set which tends to exhibit a well defined intensity distribution.

The graph of Figure 16 illustrates such an intensity distribution as an exemplary histogram having four, well defined peaks, 1602,1604,1606,1608, which can be classified according to intensity thresholds.

The voxels of the abdominal CT data set are roughly classified as four clusters by intensity thresholds (step 1540). For example, Cluster 1 can include voxels whose intensities are below 140. This cluster generally corresponds to the lowest density regions within the interior of the gas filled colon. Cluster 2 can include voxels which have intensity values in excess of2200. These intensity values correspond to the enhanced stool and fluid within the colon as well as bone. Cluster 3 can include voxels with intensities in the range of about 900 to about 1080. This intensity range generally represents soft tissues, such as fat and muscle, which are unlikely to be associated with the colon. The remaining voxels can then be grouped together as cluster 4, which are likely to be associated with the colon wall (Including mucosa and partial volume mixtures around the colon wall) as well as lung tissue and soft bones.

Clusters 1 and 3 are not particularly valuable in identifying the colon wall and, therefore are not subject to substantial processing during image segmentation procedures for virtual colonoscopy. The voxels associated with cluster 2 are important for segregating stool and fluid from the colon wall and are processed further during the high-level feature extraction operations. Low level processing is concentrated on the fourth cluster, which has the highest likelihood of corresponding to colon tissue (step 1550).

For each voxel in the fourth duster, an intensity vector is generated !King itself and its neighbors. The intensity vector provides an indication of the change in intensity in the neighborhood proximate a given voxel The number of neighbor voxels which are used to establish the intensity vector is not critical, but involves a tradeoff between processing overhead and accuracy. For example, a simple voxel intensity vector can be established with seven (7) voxels, which includes the voxel of interest, its front and back neighbors, its left and right neighbors and its top and bottom neighbors, all surrounding the voxel of interest on three mutually perpendicular axes. Figure 17 is a perspective view illustrating an exemplary intensity vector in the fotm of a 25 voxel intensity vector model, which includes the selected voxel 1702 as well as its first, second and third order neighbors. The selected voxel 1702 is the central point of this model and is referred to as the fixed voxel, A planar slice of voxels, which includes 12 neighbors on the same plane as the fixed voxel, is referred to as the fixed slice 1704. On adjacent planes to the fixed slice are two nearest slices 1706, having five voxels each. Adjacent to the first nearest slices 1706 are two second nearest slices 1708, each having a single voxel. The collection of intensity vectors for each voxel in the fourth cluster is referred to as a local vector series.

Because the data set for an abdominal image generally includes more than 300 slice images, each with a 512 x 512 voxel array, and each voxel having an associated 25 voxel local vector, it is desirable to perform feature analysis (step 1570) on the local vector series to reduce the computational burden, One such feature analysis is a principal component analysis (PCA), which can be applied to the bed vector series to determine the dimension of a feature vector series and an orthogonal transformation matrix for the voxels of duster 4.

It has been found that the histogram (Figure 16) of the CT image intensities tends to be fairly constant from patient to patient for a particular scanner, given equivalent preparation and scanning parameters. Relying on this observation, an orthogonal transformation matrix can be established which is a predetermined matrix determined by using several sets of training data acquired using the same scanner under similar conditions. From this data, a transformation matrix, such as a Karlhunen-Lodve (K-L) transformation, can be generated in a known manner The ^ta—l°the _of the feature vectors. In deitoe toe^-itlm,le.(X,elf:l-1 A?,- W * ״^ηοώ״־^^ _F0,_־^_cl־_iS,etepr־»»i״^d““^t“^^'⁷’^h''^li°ⁿ'¹“ ‘י“'־ _Isp־s־^e־:־r.־rf

The algorithm can then be outlined as;

Set n₁=l: Κ=1ί

1.

2. obtain the class number £ and class parameters (¾, nJ for(i=l; W;

for U־l;j&lt;^d⁺⁺) calculate d_} = dist (X_x» 3^1;

end for

1Mdex=arc min 4;

if (id. &lt;T}³or (K=K)) ^u ' ' indejt update class parameters:

.³indoz’T^'Tl^ ^(r,lndfiX’“^ind״index ⁿXn«x^-n43e*⁺^' end if else generate new class ־iu^sXr ^״i./ ^1;

K e K*!׳ end else end for

3. label feature vector to a class according to the nearest neighbor rule for (1-1; i&lt;N; i*♦) for j ⁺ *l calculate d_J=dist(X₁,a_jl;

end for index = arc min d^ label voxel i to class index.

end for

In this algorithm, ettstfcy) is the Euclidean distance between vector x and 3׳ and arc min d_; gives the integer j which realizes the miniminn value of The above described algorithm is dependent only on the parameters T and K. However, the value of K, which relates to the number of classes within each voxel cluster, is not critical and can be set to a constant value, such as K=18. However, T, which is the vector similarity threshold, greatly influences the classification results. If the selected value of T is too large, only a single class will be generated. On the cither hand if the value of T is too small, the resulting classes will exhibit undesirable redundancy. By setting the value of T to be equal to the maximum component variance of the feature vector series, the maximum number of distinct classes results.

As a result of the initial classification process, each voxel within the selected cluster is assigned to a class (step 1570). In the exemplary case of virtual colonoscopy, there are several classes within cluster 4. Thus, the next task is to determine which of the several classes in cluster 4 corresponds to the colon wall. The first coordinate of the feature vector, which is that coordinate of the feature vector exhibiting the highest variance, reflects the information of the average of the 3D local voxel intensities. The remaining coordinates of the feature vector contain the information of directional intensity change within the local neighbors. Because the colon wall voxels for the interior of the colon are generally in close proximity to foe gas voxels of cluster 1, a threshold interval can be determined by data samples selected from typical colon wall intensities of a typical CT data set to roughly distinguish colon wall voxel candidates. The particular threshold value is selected for each particular imaging protocol and device. This threshold interval can then applied to all CT sets (acquired from the same machine, using the same imaging protocol). If the first coordinate of the representative element is located to the threshold interval, the corresponding class is regarded as the colon wall class and all voxels in that class are labeled as colon wall-Iikc voxels.

Each colon walblike voxel is a candidate to be a colon wall voxel. There are three possible outcomes of not belonging to the colon wall. The first case relates to voxels which are close to the stooWiquid inside the colon. The second case occurs when voxels are in the lung tissue regions. The third case represents mucosa voxels. Clearly then, low level classification carries a degree of classification uncertainty. The causes of the low-level classification uncertainty vary. For example, a partial-volume effect resulting from voxels containing more than one material type (i.e., fluid and colon wall) leads to the first case of uncertainty. The second and the third cases of uncertainty are due to both the partial volume effect as well as the low contrast of CT images. To resolve the uncertainty, additional information is needed. Thus, a high-level feature extraction procedure is used in the present method to further distinguish candidates for the colon wall from other colon wall-like voxels, based on a priori anatomical knowledge of the CT images (step 1580).

An initial Step of the high-level feature extraction procedure can be to eliminate the region of lung tissue from the low-level classification results. Figure 18A is an exemplary slice image clearly illustrating the lung region 1802. The lung region 1802 is identifiable as a generally contiguous three dimensional volume enclosed by colon wall-like voxels, as illustiated in Figure 18B. Given this characteristic, the lung region can be identified using a region growing strategy. The first step in this technique is to find a seed voxel within the region of growing. Preferably, the operator performing the CT imaging scan sets the imaging range such that the top most slice of the CT scan does not contain any colon voxels. As the interior of lung should be filled with air, the seed is provided by the low-level classification simply by selecting an air voxel. Once the lung region outline of Figure

BS is determined, the lung volume can be removed from the image slice (Figure 18C).

Λ next step in performing high-level feature extraction can be to separate the bone voxels from enhanced stool/fluid voxels in cluster 2. The bone tissue voxels 1902 are generally relatively for away from the colon wall and resides outside the colon volume. To the contrary, the residual stool 1906 and fluid 1904 are enclosed inside die colon volume. Combining the a priori proximity information and the colon wall information obtained from the low-level classification process, a rough colon wall volume is generated. Any voxel separated by more than a predetermined number (e.g., 3) of voxel units from the colon wall, and outside the colon volume, will be labeled as bone and then removed from the image. The remaining voxels in cluster 2 can be assumed to represent stool and fluid within the colon volume (see Figures 19A-C).

The voxels within the colon volume identified as stool 1906 and fluid 1904 can be removed from the image to generate a clean colon lumen and colon wall image. In general, there are two kinds of stool/fluid regions. One region type is small residual areas of stool 1906 attached to the colon wall. The other region type is large volumes of fluid 1904, which collect in basin-like colonic folds (see Figures 19A-C).

The attached residual stool regions 1906 can be identified and removed because they are inside the rough colon volume generated during the low-level classification process. The fluid 1906 in the basin-like colon fold usually has a horizontal surface 1908 due to the effect of gravity. Above the surface is always a gas region, which exhibits a very high contrast to the fluid intensity. Thus, the surface interface of the fluid regions can be easily marked.

Using a region growing strategy, foe contour of the attached stool regions 1906 can be outlined, and the part which is away from the colon wall volume can be removed. Similarly, foe contour of the fluid regions 1904 can also be outlined. After eliminating the horizontal surfaces 1908, the colon wall contour is revealed and foe dean colon wall is obtained.

It is difficult to distinguish the tntieosa voxels from the colon wall voxels. Even though the above three dimensional processing can remove some mucosa voxels, it is difficult to remove all mucosa voxels. In optical colonoscopy, physicians directly inspect the colonic mucosa and search for lesions based on the color and texture of the mucosa In virtual colonoscopy, most mucosa voxels on the colon wall can be left intact in Order to preserve more information. ׳Ibis can be very usefbl for three dimensional volume rendering,

From the segmented colon wall volume, the inner surface, the outer surface and the wall itself of the colon can be extracted and viewed as a virtual object This provides a distinct advantage over conventional optical colonoscopy in that the exterior wall of the colon can be examined as well as the interior wall. Furthermore, the colon wall and the colon lumen can be obtained separately from the segmentation.

Because the colon is substantially evacuated prior to imaging, a commonly encountered problem is that the colon lumen collapses in spots. While the inflation of the colon with compressed gas, such as air or CO₂, reduces the frequency of collapsed regions, such areas still occur. In performing a virtual colonoscopy, it is desirable to automatically maintain a flight path through the collapsed regions and it is also desirable to use the scanned image data to at least partially recreate the colon lumen in the collapsed regions. Since the above described image segmentation methods effectively derive both the interior and exterior of the colon wall, this information can be used to enhance the generation of the fly path through the collapsed regions.

In extending the flight .path through collapsed regions of the colon or expanding a collapsed region of the colon, the first step is to detect a collapsed region. Using the premise that the grayscale values of the image data from around the outside of the colon wall change much more dramatically than the greyscale values within the colon wall itself, as well as in other regions such as fat, muscle and other kinds of tissue, an entropy analysis can be used to detect areas of colon collapse.

The degree of change in greyscale value, for example along the centerline, can be expressed and measured by an entropy value. To calculate an entropy value, voxels on the outer surface of the colon wall are selected. Sueh points are identified from the above described image segmentation techniques. A 5x5x5 cubic window can be applied to the pixels, centered an foe pixel of interest Prior to calculating the entropy value, a smaller (3x3x3) window can be applied to foe pixels of interest in order to filter out noise from the image data. The entropy value of a selected window about the pixel can then be determined by the equation:

E־־£c(i)ln(C(i)) X where E is the entropy and C(i) is the number of points in the window with the grayscale of i (HUA . 255 ,־). The calculated entropy values for each window are then compared against a predetermined threshold value. For regions of air, the entropy values will be fairly low, when compared to regions of tissue. Therefore, along the centerline of the colon lumen, when the entropy values increase and exceed the predetermined threshold value, a collapsed region is indicated. The exact value of the threshold is not critical and will depend in part on the imaging protocol and particulars of the imaging device.

Once a collapsed region is detected, the previously determined centerline flight path can be extended through the region by piercing through the center of the collapse with a one voxel wide navigation line.

In addition to automatically continuing the flight path of the virtual camera through die colon lumen, the region of colon Collapse can be virtually opened using a physical modeling technique to recover some of the properties of the collapsed region. In this technique, a model of the physical properties of the colon wall is developed, From this model, parameters of motion, mass density, dumping density, stretching and bending coefficients are estimated for a Lagrange equation. Then, an expanding force model (i.e., gas or fluid, such as air, pumped into the colon) is formulated and applied in accordance with the elastic properties of the colon, as defined by the Lagrange equation, such that the collapsed region of the colon image is restored to its natural shape,

To model the colon, a finite-element model can be applied to the collapsed or obstructed regions of the colon lumen. This can be performed by sampling the elements in a regular grid, such as an 8 voxel brick, and thm applying traditional volume rendering techniques. Alternatively, an irregular volume representation approach, such as tetrahedrons can be applied to the collapsed regions.

In applying the external force (air pumping) model to foe colon model, foe magnitude of foe external force is first determined to properly separate the collapsed colon wall regions. A three dimensional growing model can be used to trace the internal and external colon wall surfaces in a parallel manner. The respective surfaces arc marked from a starting point at foe collapsed region to a growing source ροΐηζ and the force model is applied to expand the surfaces in a like and natural manner. The region between the internal and external surfaces, i.e., the colon wall, are classified as sharing regions. The external repulsive force model is applied to these sharing regions to separate arid expand foe collapsed colon wall segments in a natural manner.

To more clearly visualize the features of a virtual object, such as foe colon, which is subjected to virtual examination, it is advantageous to provide a rendering of foe various textures of the object. Such textures, which can be observed in the color images presented during optical colonoscopy, are often lost in foe black and white, grey scale images provided by the CT image data. Thus a system and method for texture imaging during virtual examination is required.

Figure 20 is a flow chart depicting a present method for generating virtual objects having a texture component. The purpose of this method is to map textures obtained by optical colonoscopy images in foe red-green-blue (RGB) color space, as for example from foe Visible Human, onto the gray scale monochrome CT image data used to generate virtual objects, The optical colonoscopsy images are acquired by conventional digital image acquistion techniques, such as by a digital “frame grabber*’ 1429 which receives analog optical images from a camera, such as a video camera, and converts the image to digital data which can be provided to CPU 1423 via interface port 1431 figure 14). The first step in this process is to segment the CT image data (step 2010). The above described image -tegmentatian techniques can be applied to choose intensity thresholds in the grey scale image to classify the CT image data into various tissue types, such as bone, colon wall tissue, air, and foe like.

In addition to performing image segmentation on the CT image data, the texture features of the optical image need to be extracted from the optical image data (step 2020). To do fols, a gausian filter can be applied to the optical image data followed by subsampling to decompose the data into a multircsolutioaal pyramid. A laplacian filter and steerable filter can also be applied to the multiresohitional pyramid to obtain oriented and non-oriented features of the data. While this method is effective at extracting and capturing fee texture features, the implementation offals approach requires a large amount of memory and processing power.

An alternative approach to extracting tbc texture features from the optical image is to utilize a wavelet transform. However, while wavelet transformations are generally computationally efficient, conventional wavelet transforms axe limited in that they only capture features with orientations parallel to the axes and cannot be applied directly to a region of interest To overcome these

1Q limitations, a non-separable filter can be employed. For example, a lifting sheme cam be employed to build filter banks for wavelets transform in arty dimension using a two step, prediction and updating approach. Such filter banks can be synthesized by the Boor-Rom algorithm for multidimensional polynomial interpolation.

After the textural features are extracted from the optical image data, 15 models must be generated to describe these features (step 2030). This can be performed, for example, by using a non-parametric multi-scale statistical model which is based on estimating and manipulating the entropy of ηοη-Gaussian distributions attributable to the natural textures.

Once texture models are generated from the optical image data, texture 20 matching must be performed to correlate these models to the segmented CT imaga data (step 2050). In regions of the CT image data where the texture is enntinvons, corresponding classes of texture are easily matched. However, in boundary regions between two or more texture regions, the process is more complex. Segmentation of the CT data around a boundary region often leads to drm> which is fuzzy, i.e., the 25 results reflect a percentage of texture from each material or tissue and vary depending on the various weighting of each. The weighting percentage can be used to set the importance of matching criteria.

In the case of the non-parametric multi-scalc statistical model, the cross entropy or a Kullback-Leiber divergence algorithm can be used to measure the distribution of different textures in a boundary region.

After texture matching, texture synthesis is performed on the CT image data (step 2050). This is done by fusing foe textures from the optical image data in to the CT image data. For isotropic texture patterns, such as presented by bone, the texture can be sampled directly from the optical data to foe segmented CT image data. For unisotropic texture regions, SUCh as colon mucosa, a multiresolution sampling procedure is preferred. In this process, selective resampling for homogenous and heterogenous regions is employed.

In addition to enhanced imaging, the above described techniques can also form the basis of a system for performing virtual electronic biopsy of a region being examined to effect a flexible and non-invasive biopsy. Volume rendering techniques employ a defined transfer function to map different ranges of sample values of the original volume d&amp;ta to different colors and opacities. Once a suspicious area is detected during virtual examination, the physician can Interactively change the transfer function used during foe volume rendering procedure such that the wall being viewed becomes substantially transparent and the interior ofthe area can be viewed.

fa addition to performing virtual biopsy, the present system and methods can be extended to perform automated polyp detection. Polyps which occur, for example, within the colon, are generally small convex hill-like structures extending from the colon wall. This geometry is distinct from the fold of the colon wall. Thus, a differential geometry model can be used to detect such polyps on the colon wall.

The surface of the colon lumen can be represented using a C-2 smoothness surface model. In this model, each voxel on the surface has an associated geometrical feature which has a Gaussian curvature, referred to as Gaussian curvature fields. A convex hill on the surface, which may be indicative of a polyp, possesses a unique local feature in the Gaussian curvature fields. Accordingly, by seamhing foe Gausian curvature fields for specific local features, polyps can be detected.

Each of foe foregoing methods can be implemented using a system as illustrated in Figure 14, with appropriate software being provided to control the operation of CPU 1409 and CPU 1423.

The foregoing merely ilhistraies the prinriples of the in^ It will thus be appreciated that those skilled in the art wiU be able to derise numerous systems, apparatus and methods which, although not explicitly shown or described herein, embody the principles of the invention and are thus within the spirit and scope of foe invention as defined by its claims.

For example, the methods and systems described herein could be applied to virtually examine 2n animal, fish or inanimate object Besides the stated uses in the medical field, applications of the technique could he used tn dctrot the contains of sealed objects ^,which cannot be opened. The technique could also be used inside an architectural structure such as a building or cavern and enable the operator to navigate through the structure.

Material which is outside the scope of the claims does not constitute part of the claimed invention.

5,898,784

TRANSFERRING ENCRYPTED PACKETS OVER A PUBLIC NETWORK

This is a continuation of application Ser. No. 08/586,230, filed Jan. 16, 1996, now abandoned.

BACKGROUND

This invention relates to transferring encrypted packets over a public network.

Referring to FIG. 1, while executing a variety of software applications, 10, 12, 14, for example, Telnet 10 or Microsoft™, Inc. Word™ 12, computers 16 and 18 may exchange data over networks 20, 21, for example, a telephone company network, a private network, or a public network such as the internet or X.25. The applications communicate using network protocols 22, 24, 26, for example, transmission control protocol/intcrnct protocol (TCP/IP) 22 or internet packet exchange (IPX) 24, through application programming interfaces 28, 30, 32. Through application programming interfaces 34, 36, 38, the network protocols communicate with network drivers 40, 42, 44 to direct network interface hardware 46, 48 to transfer data over the networks.

While on a network, data being transmitted, including the addresses of the source and destination computers 16,18, is accessible to others who may be monitoring the network. For security, the data is often encrypted before being sent on the network.

Referring also to FIG. 2, for additional security, firewall computers 16,18, which have direct access to a network 20 may bc used to prevent unauthorized access to internal/ private networks 50, 52. For example, when an internal network driver 53 within firewall computer 16 receives data from an internal computer 54 that is destined for a computer 56 on a public network, it encrypts the data and the addresses of source computer 54 and destination computer 56. Computer 16 then prepends to the encrypted data a new IP header including its own address as well as the address of a destination computer, which may also be a firewall computer, e.g., computer 18.

When a firewall computer receives a network packet from the network, it determines whether the transmission is authorized. If so, the computer examines the header within the packet to determine what encryption algorithm was used to encrypt the packet. Using this algorithm and a secret key, the computer decrypts the data and addresses of the source and destination computers 54, 56 and sends the data to the destination computer. If both the source and destination computers are firewall computers, the only addresses visible (i.e., unencrypted) on the network are those of the firewall computers. The addresses of computers on the internal networks, aod, hence, the internal network topology, arc hidden. This has been termed “virtual private networking” (VPN).

Encrypting/dccrypting data has been performed by complex security software within applications or, to simplify the applications, cncrypting/decrypting has been performed within the protocol stack of network protocols.

SUMMARY

In general, in one aspect, the invention features a method of handling network packets. Encrypted network packets are received from the network at a network interface computer and passed to a computer on an internal network.

Implementations of the invention may include one or more of the following features. Before passing the encrypted network packets to the computer on the internal network, the destination computer for each encrypted network packet is determined. Determining the destination computer may include determining whether a source computer that sent each encrypted network packet is authorized to send encrypted network packets to the destination computer. Determining the destination computer may also include examining a field in a header of the network packet, and the field may correspond to a virtual network tunnel.

An encrypted network packet may be passed to the computer on the internal network if the computer on the internal network is determined to be the destination computer. Instead, the encrypted network packet may be decrypted at the network interface computer when the network interface computer is determined to be the destination computer. Network packets decrypted by the network interface computer may be passed to a computer on an internal network.

The method may also include encrypting network packets and sending the encrypted network packets from the network interface computer to the network. The computer on the internal network may encrypt the network packets, and the method may further include passing the encrypted network packets to the network interface computer. The network interface computer may be a firewall computer, and the network may be a public network.

In general, in another aspect, the invention features receiving encrypted network packets at a first computer over a network from a second computer, and examining a field in each network packet to determine which of a plurality of encryption algorithms was used to encrypt the network packet. The network packet is then decrypted in accordance with the determined encryption algorithm.

Implementations of the invention may include one or more of the following features. The field may be examined to determine a destination computer for each encrypted network packet. A determination may be made as to whether a source computer that sent each encrypted network packet is authorized to send eucrypted network packets to the destination computer. Encrypted network packets may be passed to a computer on an internal network when the destination computer is determined to be the computer on the internal network. The network packets may be decrypted when the destination computer is determined to be the first computer, and the decrypted network packets may be passed to a computer on an internal network. The field may correspond to a virtual network tunnel, and the network may be a public network. The first computer may be a firewall computer.

In general, in another aspect, the invention features receiving network packets over a network, and determining which virtual tunnel each network packet was sent over is made. Each network packet is then routed to a destination computer in accordance with the determined virtual tunnel.

Implementations of the invention may include one or more of the following features. Each network packet may be decrypted in accordance with the determined virtual tunnel.

In general, in another aspect, the invention features encrypting network packets at a computer connected to an internal network and passing the network packets over the internal network to a network interface computer. The network interface computer then passes the encrypted network packets over a public network.

In general, in another aspect, the invention features receiving network packets from a network, and determining over which virtual tunnel each network packet was sent. A

5,898,784 determination is also made as to whether the source computcr that sent each network packet is authorized to send network packets over the determined virtual tunnel.

Implementations of the invention may include one or more of the following features. Each network packet may be routed to a destination computer in accordance with the determined virtual tunnel when the source computer is determined to be authorized.

Advantages of the invention may include one or more of the following. Using the policy id field to create virtual tunnels allows a receiving computer to determine both a packet’s encryption algorithm and where the packet should be routed. Multiple tunnels between the same two computers allows packets encrypted with different encryption algorithms to be sent between the same computers. The virtual tunnels permit the cncapsulating/decapsulating and encrypting/decrypting of network packets to be spread across multiple computers. Using the tunnel databases, the firewall computers may restrict access to particular tunnels and, in effect, perform packet filtering for each tunnel.

Other advantages and features will become apparent from the following description and from the claims.

DESCRIPTION

FIG. 1 is a block diagram of two computers connected together through two networks.

FIG. 2 is a block diagram of two firewall computers and networks.

FIG. 3 is a block diagram of a computer including a security network driver.

FIG. 4 is a flow chart of encapsulation and encryption. FIGS. 5 and 6 are block diagrams of network packets. FIG. 7 is a flow chart of decryption and decapsulation. FIG. 8 is a block diagram of virtual tunnels.

FIG. 9 is a block diagram of a computer network.

FIG. 10 is a flow chart of tunnel record generation.

FIG. 11 is a flow chart of tunnel record updating.

As seen in FIG. 3, security network driver software 72 is inserted between network protocol TCP/IP 22 and conespending network driver 40. The security network driver encrypts information before it is sent on the network by the network driver and decrypts information received from the network by the network driver before the information is sent to the network protocol. As a result, after choosing a security network driver with the required security features, users may freely choose among available applications and network protocols regardless of the required level of security and regardless of the available encryption/decryption libraries and without having to compromise their security needs. Moreover, the chosen applications and network protocols need not be modified. To change the level of security, the user may simply chose another security network driver or modify the current security network driver.

Generally, a computer’s operating system software defines a “road map” indicating which applications may communicate with each other. To insert a security network driver between a network protocol and a network driver, the road map is altered. The vendor of the operating system software may make the road map available or the road map may be determined through observation and testing. Once the road map is altered, functions such as send and receive, between the network protocol and the network driver arc diverted to the network security driver to encrypt data before it is sent on the network and to decrypt data when it is received from the network.

Referring to FIGS. 3 and 4, as an example, to send data from computer 16 to computer 18 on the internet, Telnet 10 issues (step 60) a send call to TCP/IP 22 through network protocol API 28. The send call includes a network packet 62 (FIG. 5) having a header 64 and data 66. The header includes information such as the addresses of the source and destination computers and the type of application that sent the data. The network protocol then issues (step 68) a send call to the network driver API which, in accordance with the altered road map, issues (step 70) a send call to a security network driver (SND) 72.

'111c security network driver issues (step 74) an cncapsulate call to an encapsulale/decapsulale library 76 through an API 77. In one example, the encapsulate/decapsulate library uses the swlPc IP Security Protocol created by J. loannidis of Columbia University and M. Blaze of AT&amp;T™, Inc. which is described in an Internet Draft dated Dec. 3, 1993 and incorporated by reference. Referring also to FIG. 6, the encapsulate call generates a new network packet 78 in accordance with the swlPc protocol, '!lie new packet includes a header 80, a swIPe protocol header 82, and data 84. According to options within the swlPc protocol, header 80 may be the original header 64 (FIG. 5), in which case, data 84 is the original data 66, or header 80 may be a new header including the address of a source firewall computer, e.g., computer 16 (FIG. 2), and a destination computer which may also be a firewall computer, e.g., 18. Where header 80 is a new header, data 84 includes the entire original network packet 62 (FIG. 5).

After encapsulating the network packet, the security network driver issues (step 88, FIG. 4) an encryption call to an encryption/decryption library 90 (FIG. 3) through an API 91. Library 90 encrypts a portion 92 of the encapsulated network packet including data 84 and part of swIPe protocol header 82. Header 80 (FIG. 6) is not encrypted. Thus, if, according to options within the swIPe protocol, header 80 is the original header 64 (FIG. 5), then the addresses of the source and destination computers are visible on the internet. On the other hand, if header 80 is a new header including the addresses of firewall computers, then the addresses of internal source and destination computers arc encrypted and not visible on the internet.

Library 90 may be of the type sold by RSA Data Security™, Inc. of Redwood City, California and may encrypt the data according to an RSA algorithm such as RC2 or RC4 or according to a federal information processing standard (FIPS) such as data encryption standard (DES).

The security network driver then issues (step 94) a send call, including the cncapsulatcd/cncryplcd network packet, to the API, and the API, in accordance with the altered road map, issues (step 96) a send call to a network driver, e.g., network driver 40. The network driver then causes hardware 46 to transmit (step 98) the encapsulated/encrypled network packet on the network.

Referring to FIGS. 3 and 7, the network drivers of each computer 16, 18 (FIGS. 2 and 3) maintain a database of addresses to which they will respond. For example, when network driver 40 receives (step 100) a properly addressed network packet from network 20, the network driver issues (step 102) a receive call to corresponding network protocol API 34. In accordance with the altered road map, the API issues (step 104) a receive call to security network driver (SND) 72 which issues (step 106) an authorization call to encapsulate/decapsulate library 76 through API 77. Library 76 examines the unencrypted portion of swIPe header 82 (FIG. 6) to determine (step 108) whether it is proper. If it is not proper, an error (step 110) is flagged.

5,898,784

If the header 82 is not a swIPe header, then the security network driver issues a receive call to the API including the unaltered packet.

If the swIPe header is proper, the security network driver issues (step 112) a decryption call to encryption/decryption library 90 through API 91. A portion of the unencrypted swIPe protocol header includes a policy identification (id) field 113. The policy id field indicates the encryption algorithm used to encrypt the data. Library 90 uses a secret key that was previously exchanged between the computers and the encryption algorithm to decrypt data 84.

After decryption, the security network driver issues (step 114, FIG. 7) a digital signature check call to encapsulate/ decapsulate library 76. The swIPe protocol header includes a digital signature 86. The digital signature is a unique number calculated using the data in the network packet, the secret key, and a digital signature algorithm. Library 76 recalculates the digital signature and compares (step 116) it to digital signature 86 in the network packet. If the network packet is tampered with during transmission and any data within the packet is changed, then the digital signature in the packet will not match the digital signature generated by the receiving computer and an error (step 118) will be flagged.

If the signatures match, then the security network driver issues (step 120) a receive call to the API which issues (step 121) a receive call to the TCP/IP network protocol including only the original network packet 62 (FIG. 5, data 66 and addresses of the source and destination computers 64). If (step 122) the network packet is destined for computer 16, then TCP/IP issues (step 124) a receive call to an application 10,12 and if the network packet is destined for a computer on an internal network, e.g., computer 54 (FIG. 2) on network 50, then TCP/IP issues (step 126) a receive call to internal network driver 53 which then sends (step 128) the data to the internal computer.

Referring to FIG. 8, the policy id field may be used to create virtual tunnels 140, 142 between firewall computers 146, 148 on internet 152. When computer 146 receives a network packet, it checks the policy id to determine which “tunnel” the packet came through. The tunnel indicates the type of encryption algorithm used to encrypt the packet.

Multiple tunnels 140, 142 may connect two computers 146, 148 and each tunnel may use a different encryption algorithm. For example, tunnel 140 may use the RC2 encryption algorithm from RSA Data Security™, Inc. while tunnel 142 uses the FIPS DES encryption algorithm. Because the RC2 encryption algorithm is less secure and requires less computer processing time than the FIPS DES standard, users may send a larger number of network packets requiring less security over tunnel 140 as opposed to tunnel 142. Similarly, predetermined groups of users or computers may be restricted to sending their packets over particular tunnels (effectively attaching a packet Alter to each tunnel).

The tunnel may also indicate where the packet is to be sent. Primary firewall computers 16, 18 store information about the internal path of each tunnel in a tunnel database. When computer 146 receives a packet whose policy id indicates that the packet came through a tunnel that ends at computer 146, e.g., tunnel 142, computer 146 dccapsulates and decrypts the packet and sends the decrypted packet over internal network 154 to the proper destination computer in accordance with the decrypted destination address. When computer 146 receives a packet whose policy id indicates that it came through a tunnel that does not end with computer 146, e.g., tunnel 140, computer 146 does not decapsulate and decrypt the packet. Instead, computer 146 sends the encrypted packet to internal firewall computer 158 in accordance with the tunnel database.

Internal firewall computer 158 also has a tunnel database in which the internal path of any tunnels connected to 5 computer 158 are stored. As a result, when computer 158 receives a packet whose policy id indicates that it came through a tunnel that ends with computer 158, e.g., tunnel 140, it decapsulates and decrypts the packet according to the policy id and sends the decrypted packet over internal 10 network 160 to computer 162 in accordance with the decrypted destination address.

The only addresses visible on the internet and on internal network 154 are the addresses of the firewall computers 146, 148, and 158. The address of internal computer 162 and, ¹⁵ hence, the network topology of network 160 are protected on both the internet and internal network 154.

The tunnel databases provide the firewall computers 146, 148, and 158 with information as to the internal path of the tunnels. Thus, if computer 162 was another firewall ⁰ computer, computer 146 may modify the destination address of packets received on tunnel 140 to be the address of computer 162 to cause computer 158 to send the packet directly to computer 162 without checking the policy id ₂₅^field'

Encapsulating/decapsulating and encrypting/decrypting network packets may require a large portion of a computer's processing power. Creating virtual tunnels using the policy id field allows the encapsulating/decapsulating and ₃₀ encrypting/decrypting of network packets to be spread across several computers. For example, computer 146 may decapsulate and decrypt network packets destined for computers connected to internal network 154 while computer 158 may decapsulate and decrypt network packets destined ₃5 for computers connected to internal networks 154 and 160. Similarly, computer 146 may encapsulate and encrypt network packets sent from computers connected to internal network 154 while computer 158 may encapsulate and encrypt network packets sent from computers connected to ₄₀ internal networks 154 and 160.

The Kerberos Key Distribution Center components of Kerberos Network Authentication System created under project Athena at Massachusetts Institute of Technology, defines one method of providing computers with secret keys. 45 Referring to FIG. 9, computer 130 is termed the “trusted computer, and before computers 132 and 134 may transfer encrypted data to each other over network 136, both computers send a request to trusted computer 130 for a secret key. For a more detailed description of the Kerberos Key so Distribution Center, see RFC1510 (request for comment) “Kerberos Network Authentication Service” by J. Kohl &amp; B. Neuman, Sept. 1(1,1993, which is incorporated by reference.

Referring back to FIG. 2, to transfer secure (i.e., encapsulatcd and/or encrypted) network packets between two 55 computers, operators of the two computers may verbally exchange a secret key for each tunnel between the computets and then manually initialize the computers to transfer data by generating a tunnel record including a secret key for each tunnel between the two computers. Firewall computers 60 are typically managed by skilled technicians capable of generating tunnel records. Typical users have non-firewall computers and may wish to transfer cncapsulated/encrypled data with a firewall computer. To avoid requiring that a typical user generate tunnel records and instead of having a 65 separate trusted computer provide secret keys to two computers, a firewall computer 16, 18 may provide secret keys to other computers.

5,898,784

Referring also to FIG. 10, when a user wishes to transfer packets between his/her computer and a firewall computer, the user requests (step 170) a password (a onetime pad) from the firewall operator. The operator then generates (step 172) tunnel records for each tunnel over which the user’s computer and the firewall computer may transfer network packets. The operator also stores (step 174) the password given to the user on the firewall computer. The user installs (step 176) the security network driver (SND) software on his/her computer and runs (step 178) a configuration program. The configuration program prompts (step 180) the user for the password and sends (step 182) a configuration request to the firewall computer.

'!^,he firewall computer identifies (step 184) the user’s computer as the sender of the request and notifies the user’s computer of the available tunnels by sending (step 186) the complete tunnel records, including secret keys, associated with each tunnel to the user’s computer. The tunnel records are sent through network packets that are encrypted using the password and the encryption algorithm. Afterwards, the firewall deletes (step 188) the password, and further network packets are transmitted between the two computers through the available tunnels and encrypted according to the secret key associated with each tunnel.

Referring to FIG. 11, generally, each time the user’s computer accesses (step 190) the internet, a new internet address is assigned. The firewall computer needs to know the new address in order to update the tunnel records. To notify the firewall computer of the new internet address, each time the user’s computer accesses the internet, the configuration software issues (step 192) a connect request to the firewall computer. The firewall computer identifies (step 194) the computer and may prompt the user for a user name and a user password. If the user name and password arc authorized (step 196), the firewall updates (step 198) the tunnel records with the internet address sent as part of the connect request. The configuration software also updates (step 200) the non-firewall computer’s tunnel records with the computer’s new internet address.

Other embodiments are within the scope of the following claims.

For example, instead of encapsulating the network packets using the swIPe protocol header, other internet security algorithms may be used.

Although the security network driver was described with respect to send and receive functions, APIs from different manufacturers, for example, Sun™, Inc. and Microsoft™, Inc., include a variety functions, and the security network driver is designed to respond to each possible function.

Ihe security network driver may also be simultaneously connected to multiple network protocols, e.g, both TCP/IP 22 and IPX 24, as shown in FIG. 3.