Abstract:
The present invention provides a method and apparatus for designing and visualizing the shape of eyeglass lenses and of the front rims of eyeglass frames, and for allowing the customer to modify the design by changing the shape and style interactively to suit his/her preference and perceived character. The present invention comprises an interface for a lens grinding machine that allows the retailer to manufacture the selected frame at the store for certain specified styles, or allows the retailer to transmit the shape and style data to a manufacturer that can implement the selected design and deliver it directly to the customer. Another embodiment of the present invention is to provide a method for designing, visualizing, modifying the shape and style of eyeglass lenses and frames remotely through the Internet or other communication channel, and to transmit the design to a manufacturer, which enables the customer to select and purchase eyeglasses directly from manufacturers.

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of U.S. Provisional Application No. 60/163,489, filed Nov. 4, 1999, which is hereby incorporated by reference in its entirety. 
    
    
     BACKGROUND OF THE INVENTION 
     This invention relates generally to eyeglasses and, more particularly, to a method and apparatus for designing and modifying the shape of eyeglass lenses and the front rims of eyeglass frames. 
     Eyeglass frames typically have a particular style (the combination of material, color, texture, feature decorations, and overall appearance) and a particular shape (the geometric description of the contour of the front rims of the eyeglass frame). For each style there may be several different shapes (e.g. round, square etc.), and for each shape there may be several different styles (metal, plastic, translucent, engraved, etc.). Eyeglasses, the combination of eyeglass lenses (hereinafter referred to as “lenses”) and eyeglass frames, typically include lenses having a certain shape, eyeglass frames having a matching shape, a certain style, and a particular combination of functional elements (legs, nose pads and other functional elements). 
     In the eyeglass industry there is a conflict between a customer&#39;s desire for personalized design and the mass production employed by the industry. On one hand, it is believed that eyeglasses greatly influence the looks and perceived character of a customer, who often wears the glasses daily for long periods of time. This influence drives a desire to obtain a personalized design that fits a variety of criteria (e.g. facial features and style preferences of the customer, current fashion guidelines, social constraints etc.). On the other hand, the manufacturing industry operates on a large scale production in which eyeglasses are distributed to consumers via retailers. This large scale production causes the need for standardized design of eyeglasses. It appears that the industry has addressed this conflict by producing a large variety of shapes and styles, that customers review in a lengthy and often complex selection process. In addition, retailers stock a large inventory of eyeglass frames, which changes often, and hire a relatively large number of experienced employees to guide customers in their selection process. 
     In today&#39;s optical stores, it is typically the responsibility of the retailer to translate a customer&#39;s personality, style, and social preferences into shapes and styles of eyeglass frames, leading to a lengthy and frustrating process for the customer. The process becomes even more lengthy and frustrating for the customer when the retailer is not experienced or esthetically sensitive, does not properly communicate with the customer, or is just trying to serve more than one customer at a time. 
     BRIEF SUMMARY OF THE INVENTION 
     In one embodiment, a user utilizes a method and system to design, select, and purchase eyeglasses. The user accesses the system and visualizes an inventory of eyeglass styles and shapes previously stored in a database and displayed by the system. The user selects a particular eyeglass style and “virtually tries on” the selected eyeglasses in a size that matches the user&#39;s facial features. In addition, the method and system allow the user to interactively modify the choice by changing the shape, style, and color of the eyeglass frames. The system reviews the choices made by the user and provides a notification to the user if a selected modification is not allowed for the particular eyeglass frame chosen by the user. In an alternative embodiment, the system only allows the user to make interactive modifications that can be implemented at the optical store. 
     A user is able to modify the design while satisfying predetermined constraints due to manufacturing procedures and materials, as well as inventory status. In addition, a user is able to interactively modify previous choices by specifying a desired “character”, e.g. more/less aggressive/assertive/personable etc. The system stores the current choice of style for later retrieval and comparison with other choices. The system further suggests alternative shapes and styles that reflect previous choices of the customer, or of other customers with similar taste preferences, utilizing collaborative filtering. The system also interfaces to machine tools (e.g. lens-cutting devices or eyeglass frame bending devices) that fabricate the selected design of shape and style and have the selected design ready to try on at an optical store. The system can be accessed remotely, such as from a home of the user, via a computer and an Internet connection, or other communication channel. 
     More particularly, the present method includes receiving at least one digital image of a face of a person, performing basic image processing operations such as color or light compensation, displaying to the user a variety of eyeglass shapes and styles available from manufacturers and retailers, matching a size of a selected eyeglass frame to a facial size and features of the person, and receiving input information such as inter-ocular distance or prescription details. In one embodiment, the system alters the image of the eyeglasses according to a motion of the person&#39;s head to simulate the appearance of wearing the eyeglasses on the person&#39;s face. In addition, the method includes interactively modifying the selected style and shape of the eyeglass frame while satisfying constraints due to manufacturing process and inventory. The system stores the generated images for later retrieval and comparison of different styles. 
     In another embodiment, the method further includes superimposing the selected eyeglasses to the digital image of the person&#39;s face to generate a virtual image of the person wearing the selected eyeglasses while moving. The system displays a visualization of the head of the person at video-rate and selects and tracks a number of features on the person&#39;s face. The system estimates the three-dimensional motion of the head, compensates for the motion, modifies the appearance of the model eyeglass frame, and superimposes the eyeglass image to make the eyeglasses appear stationary on the person&#39;s face. 
     In a further embodiment, the method and system can be utilized to modify the displayed shape of selected eyeglass lenses and front rims. The system includes a database of maps for shape, i.e., the position of a finite number of control points that determine the contour of the lens and the rim, and perceptual qualities, i.e., the “strength” of each adjective as recorded during experimental trials or setup by the retailer or by experts. The system modifies the selected shape by receiving information from the user regarding the amount of each descriptive quality. The system adapts the database to the clientele of a particular optical store and performs collaborative filtering to recommend shapes and styles that match the choices of previous customers with similar preferences. 
     In yet another embodiment, the system is given (e.g. by the manufacturer, based upon the material chosen) the constraints that a particular eyeglass frame must satisfy, e.g., the maximum curvature, tangent at the hinges and bridge, maximum size of the lenses, and others. The system verifies that the constraints of the selected eyeglass frames are met during the interactive modification procedure. The system also interfaces with machine tools for grinding eyeglasses and for shaping rims of eyeglass frames. 
     In a still further embodiment, the system is accessed remotely by a user who logs onto a remote access site and inputs one or more photographs of the person, or a live video stream. The user also inputs lens prescription data, when applicable, as well as the shape and style data. The system receives the information and transmits the shape and style data to eyeglass frame and lens manufacturers, who then ship the selected eyeglasses directly to the customer. 
     The above described system and method allow a customer to personalize the design of eyeglasses, and the retailer to reduce eyeglass inventory and the need for a high number of specialized employees. In the exemplary embodiment, the system includes a user interface that allows the customer to select desired modifications with minimal guidance by the retailer. The system can be operated remotely by the customer, for instance from home, by means of a computer, an Internet connection and a digitized picture of the customer&#39;s face, or a live camera connected to the computer, without going to an optical store. 
     The present invention thus relieves the customer from the lengthy and potentially frustrating process of selecting eyeglass shape and style through a retailer, relieves optical retailers from storing a large inventory of shapes and styles and having to hire experienced staff to assist customers in the process of selecting eyeglass frames, and it allows eyeglass manufacturers to sell their products directly to customers without intermediary distributors and retailers. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a block diagram of a system in accordance with one embodiment of the present invention; 
         FIG. 2  is an expanded block diagram of a first exemplary embodiment of the system shown in  FIG. 1 ; 
         FIG. 3  is an expanded block diagram of a second exemplary embodiment of the system shown in  FIG. 1 ; 
         FIG. 4  is an exemplary embodiment of a first user interface; 
         FIG. 5  is an exemplary embodiment of a second user interface; 
         FIG. 6  is an exemplary embodiment of a third user interface; and 
         FIG. 7  is a method for selecting and modifying eyeglass-frames. 
     
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     Exemplary embodiments of systems and processes that facilitate design, selection and purchasing of eyeglasses are described below in detail. The system provides for interactive customized design of eyeglass shape to fit physical and perceptual customer features. In a first exemplary embodiment, the system is accessed from a retail or wholesale outlet and in a second exemplary embodiment, the system is accessed remotely. Corresponding to each embodiment, there are three operating modalities, i.e., two-dimensional, three-dimensional and two and a half dimensional. 
     The systems and processes are not limited to the specific embodiments described herein. In addition, components of each system and each process can be practiced independent and separate from other components and processes described herein. Each component and process also can be used in combination with other components and processes. 
       FIG. 1  is a simplified block diagram of an interactive eyeglass system  10  including a server system  12 , hereinafter referred to as server  12 , and a plurality of client systems  14  connected to server  12 . In one embodiment, client systems  14  are computers including a web browser, such that server  12  is accessible to client systems  14  via the Internet. Client systems  14  are interconnected to the Internet through many interfaces including a network, such as a local area network (LAN) or a wide area network (WAN), dial-in-connections, cable modems and special high-speed ISDN lines. Client systems  14  could be any device capable of interconnecting to the Internet including a web-based phone or other web-based connectable equipment. 
     A database server  16  is connected to a centralized database  20  containing eyeglass-related information, as described below in greater detail. In one embodiment, centralized database  20  is stored on database server  16  and can be accessed by potential users at one of client systems  14  by logging onto server  12  through one of client systems  14 . In an alternative embodiment centralized database  20  is stored remotely from server  12 . 
     System  10  utilizes a web-enabled interactive database to automate customized selection and design of eyeglasses. System  10  receives all input information and provides feedback and recommendations based upon user input. In one exemplary embodiment, system  10  utilizes a Relational Database with a client user interface front-end for administration and a web interface for standard user input. Information is accessed in the database through Structured Query Language (SQL). 
       FIG. 2  is an expanded version block diagram of an exemplary embodiment of an interactive eyeglass system  50 . Components in system  50 , identical to components of system  10  (shown in  FIG. 1 ), are identified in  FIG. 2  using the same reference numerals used in  FIG. 1 . System  50  includes server system  12  and at least one client system  14  coupled to server  12  via an Internet connection. In an alternative embodiment, server  12  includes a database server  16 , an application server  52 , a web server (not shown), a fax server (not shown), a directory server (not shown), and a mail server (not shown). Servers  16 ,  52 , and the other servers are coupled in a local area network (LAN)  54 . In one embodiment, a system administrator&#39;s workstation (not shown), user workstation  14 , and a supervisor&#39;s workstation (not shown) are connected to server  12  via LAN  54 . Alternatively, workstation  14  and the other workstations are coupled to LAN  54  via an Internet link  56  or are connected through an Intranet (not shown). 
     Each workstation is a personal computer having a web browser. In another embodiment, server  12  is configured to be communicatively coupled to various individuals or employees and to third parties, e.g., manufacturers, wholesalers, and others via an ISP Internet connection. The communication in the exemplary embodiment is illustrated as being performed via the Internet, however, any other wide area network (WAN) type communication can be utilized in other embodiments, i.e., the systems and processes are not limited to being practiced via the Internet. In addition, and rather than a WAN, a LAN could be used in place of the WAN. 
     Database server  16  includes a style memory database  58 , a template software database  60  and an eyeglass frame size/shape selection software database  62 . User device  14  includes a facial image memory database  64 , a monitor/screen  66  and a digital camera  68 . In an alternative embodiment, system  50  includes multiple user devices. Server  12  is connected to user device  14  via a network, such as the Internet, an Intranet, or another wide area network. 
       FIG. 3  is an expanded version block diagram of an alternative embodiment of an interactive eyeglass system  70 . System  70  includes a computer  72  that includes a database server  74 , an application server  76 , a web server (not shown), a fax server (not shown), a directory server (not shown), and a mail server (not shown). Computer  72 , servers  16 ,  52 , and the other servers are coupled in a local area network (LAN)  78 . In one embodiment, multiple workstations are connected to computer  72  via LAN  78 . Although the functions performed by the servers are illustrated as being performed by separate servers, such functions can be performed at one or multiple servers coupled to LAN  78 . The servers are illustrated as being associated with separate functions only to facilitate an understanding of the different types of functions that can be performed by system  70 . Database server  74  includes a style memory database  80 , a template software database  82  and an eyeglass frame size/shape selection software database  84 . Computer  72  also includes a facial image memory database  86 , a monitor/screen  88  and a digital camera  90 . 
       FIG. 4  is an exemplary embodiment of a first user interface  100  including an image of a person&#39;s face  102  and a plurality of icons  104  representing a selection of eyeglass frames. The eyeglass frames are displayed sequentially, and the user scrolls up and down using a pointing device. In an alternative embodiment, the eyeglass frame are grouped according to a particular criterion such as material, manufacturer, shape (e.g. rounder shapes, angular shapes etc.), by fashion designer, etc. and organized, for instance, into a tree structure with pull-down menus and can be searched by such groupings. 
     The system computes a size of the eyeglass frames for the particular facial size and features, and superimposes the selected style to the image of the user to create a virtual image of the user wearing the selected eyeglass frame. In addition, the system requests scale information, such as inter-ocular distance. If such information is unavailable to the system, the system uses a default (inter-ocular distance=10 cm), and prompts the user for the correct distance upon ordering or purchasing the eyeglass frames. 
       FIG. 5  is an exemplary embodiment of a second user interface  110  including an image of a person&#39;s face  112  wearing a pair of eyeglass frames selected by the user from first user interface  100 . Interface  110  also includes a plurality of radio buttons including a load button  114 , a click button  116 , a draw default button  118 , a load glasses button  120 , a save glasses button  122 , a reset glasses button  124 , and a close button  126 . In addition, second user interface  110  includes a plurality of sliding buttons including a top horizontal button  128 , a top vertical button  130 , an outer horizontal button  132 , an outer vertical button  134 , an all vertical button  136 , a bottom horizontal button  138 , a bottom vertical button  140 , a bridge button  142 , a sophistication button  144 , and an assertiveness button  146 . 
     The selected shape is matched to the facial size and features of the person&#39;s face and displayed superimposed to the image of the face to create a virtual image of the user wearing the selected eyeglass frame. Utilizing a pointing device, such as a mouse, the user modifies the selected shape by dragging a certain number of control points  148  (seen as enlarged squares on the image) in different positions of the image. Alternatively, the user changes the shape by moving sliders  128 – 146  that control the horizontal and vertical position of each control point. The modified image is saved by storing the image. Another style is then loaded and the process is re-initiated. The user, at any time, can retrieve all the selected designs for comparison. 
       FIG. 6  is an exemplary embodiment of a third user interface  160  for simultaneous view of multiple selected designs for comparison, including a first image of a person&#39;s face  162  wearing a pair of eyeglass frames selected and manipulated by the user via interfaces  100  and  110  and a second image of a person&#39;s face  164  wearing a pair of eyeglass frames selected and manipulated by the user via interfaces  100  and  110 . A plurality of control points  166 , modified in the previous interface, are now fixed and indicated by a “+”. A user manipulates a position of the control points to alter the perceptual characteristics of the eyeglass frames as will be described in detail below. By using techniques such as collaborative filtering, the system can be prompted to suggest styles and shapes according to the preferences of other customers that best match the choices of the current customer. 
       FIG. 7  illustrates a method  200  for designing, selecting, and purchasing eyeglasses. Method  200  is illustrated in a logic diagram form. However, it should be understood that such method could be performed in any sequence, in a distributed manner, or in parallel, and no specific execution order is intended, expressed or implied, by such flow. Also, any one of the functions illustrated in  FIG. 7  could be performed without necessarily performing, within a certain time limitation, any of the other functions. 
     Data Acquisition and Visualization 
     A user logs on  202  to an eyeglass system, such as one of systems  10 ,  50 , and  70 , (shown in  FIGS. 1 ,  2 , and  3 , respectively), and is then presented with first user interface  100 . One or more images (such as image  102  shown in  FIG. 4 ) of a face of a person is acquired by a user utilizing one or more cameras. The image is received  204  by system  10  and is stored in electronic format utilizing a computer and other peripherals (e.g. a scanning device, or a frame-grabber board). In one embodiment, the camera is a conventional camera. In an alternative embodiment, the camera is a digital camera. 
     After the image is stored in electronic format on system  10 , the image is displayed  206  by system  10  (such as in first user interface  100  shown in  FIG. 4 ) utilizing a computer monitor, such as monitor  62  shown in  FIG. 2 , or other visualization device (e.g. a television monitor) as describe below in greater detail. User interface  100  includes a plurality of icons each representing a different style available for purchase. Each style has been previously inputted into a database (such as eyeglass frame size/shape selection software database  62  shown in  FIG. 2 ) that includes a prototype, including color, geometric properties (e.g. tangent directions at the hinges and bridge, perimeter of the rim for rimmed eyeglass frames), reflectance properties of the material, structural properties (such as maximum curvature of the rim) as well as photographs of the eyeglass frames taken from several viewpoints. 
     System  10  utilizes standard techniques from computer graphics to generate an image of the eyeglass frame as seen from any viewpoint as is known in the art. (See for example, Foley et al., “Computer Graphics”, Addison Wesley, 1997 [hereinafter referred to a Foley et al.] Chapter 16). Alternatively, photographs from several viewpoints can be combined to yield a panoramic view. See for example, “Quicktime VR©”, a commercial product available from Apple Computer, Inc. The icons display a frontal view of the eyeglass frame. In addition, the user can select a pair of eyeglass frames and change the viewpoint by using a pointing device as is known in the art. See for example, Foley et al., Chapter 17. 
     Two-Dimensional Model Acquisition and Visualization 
     In the two-dimensional modality, after a frontal image of the person&#39;s face is inputted into system  10 , a two-dimensional model of the face is generated by system  10 , which utilizes a two-dimensional orthonormal reference frame uniquely associated with the person&#39;s face. Such a reference frame is determined by the position of two points, one being the origin of the reference frame (i.e. the point with coordinates “(0,0)”) and the other being the unit along one of the two axes (e.g. the “x”-axis) having coordinates “(1,0)”. The other axis (e.g. the “y”-axis) is then automatically determined as the axis perpendicular to the “x”-axis and having the same unit. In an exemplary embodiment, the origin of the reference frame is chosen to be the mid-point of the linear segment that connects the centers of the pupils of the two eyes, and the unit along the “x”-axis is chosen to be the center of the pupil of one eye (e.g. the left eye). In the preferred embodiment, the location of the center of the pupil of the eyes is determined in two steps. First, the location is coarsely determined by the user who indicates the approximate location utilizing a pointing device (the user is requested to click on the center of each eye). Second, the location is refined automatically using a template search as is well known. (See, e.g., Blake and Isard, “Active Contours”, Springer Verlag, 1998). System  10  computes the correlation between a set of stored templates representing the eye, possibly at different levels of resolution, orientation, and size, and located in different positions around the point selected by the user as the approximate location of the center of the eye. In one embodiment, the templates are in gray-scale and for the template correlation, only the gray-scale version of the image is used. Sub-pixel interpolation can be performed by interpolating the value of pixels between points on the pixel grid and repeating the template correlation search on a finer grid, as is well known in the art. The point scoring the largest correlation value for all choices of templates is selected as being the center of the pupil of the eye. 
     In an alternative embodiment, an algorithm for face localization is utilized to locate the position of the eyes in the image. See for example, Burl et al., “Face localization by shape statistics”, In Proc. of the IEEE Intl. Conf. on Comp. Vision and Patt. Recog., 1996. 
     An outline of the person&#39;s face is then described as an ellipse, and is specified by a length of the face&#39;s two major axes and the position of the face&#39;s center. Such a length is determined utilizing another template search analogous to the template search used to locate the eyes. However, when determining the length of the face&#39;s two major axes, the template utilizes an ellipse that can be translated along the vertical (“y”) axis, and expanded along the “x” and “y” axes to score the highest correlation with the image of the face. The image is heavily sub-sampled to speed up the correlation search. Since faces are typically symmetric, a search along the “y” direction is not performed. A search along the “y” direction, however, can be added as a secondary feature for faces that are asymmetric, or where a user desires a more precise image. In the exemplary embodiment, system  10  assumes that the major axis is aligned with the vertical (“y”) axis and the minor axis is aligned with the horizontal (“x”) axis. However, the photograph of the customer may not be perfectly aligned along the vertical axis, and therefore the photograph needs to be compensated. Compensation is accomplished by allowing the template of the face to rotate, which adds a degree of freedom, and to be asymmetrical, thereby allowing an additional degree of freedom. In one embodiment, compensation of the photograph is performed automatically as a template search, as is standard in the art. In an alternative embodiment, compensation of the photograph is performed interactively by having the user select a number of key points. For example, the user is asked to select the center of the chin and the hairline, which together determine the position and orientation of the major axis of the ellipse, as well as the upper contour of the left and right ear, which determine the orientation of the minor axis of the ellipse. A variety of other implementation solutions are also possible, which do not distort the general embodiment and are therefore not discussed herein. 
     Three-Dimensional Model Acquisition and Visualization 
     In the three-dimensional modality, two or more cameras are rigidly mounted on a rig (a rigid infrastructure of pedestals), spaced about 1 m apart, and camera parameters are calibrated using standard techniques for stereo calibration as is well known. See for example, R. Tsai, “An Efficient and Accurate Camera Calibration Technique for 3D Machine Vision”, IEEE Transactions on Robotics and Automation, 1986. The calibration includes calibration of so-called “intrinsic parameters” (focal length, optical center, size of the pixel, skew factor, and lens distortion) as well as so-called “extrinsic parameters” (the relative position of each camera). The position of the epipoles (the projection of the focal point of a camera onto an image plane of another camera), is estimated first, and then compensated so that epipolar lines (the projection of the epipolar plane, i.e. the plane containing two optical centers and a point on the scene, as described in Faugeras) correspond to scan-lines according to standard techniques. (Faugeras, “Three-dimensional vision, a geometric viewpoint”, MIT press, 1992, [hereinafter Faugeras] which is incorporated by reference), described for instance in section 6.3 of Faugeras. 
     A digital picture of the person&#39;s face is then acquired simultaneously by the two (or more) cameras against a uniformly colored background (e.g. black) using controlled light (e.g. two diffusing lamps). A normalized correlation, as is well known (see for example, Faugeras, Chapter 6.4), is performed to determine a disparity of corresponding pixels in the images. Such correlation is performed in a multi-scale fashion. Standard triangulation techniques, as are well known, (see for example, Faugeras, Chapter 6) are used to obtain a mesh of the three-dimensional position of each pixel, which constitutes the first, rough three-dimensional model of the face. A refined model of the face is then obtained by a template search against a stored three-dimensional face template using standard techniques in Computer Graphics. Several templates are stored to accommodate a variety of faces (e.g. wider/narrower/rounder/angular). 
     Once a three-dimensional model of the face is generated, the two (or more) images are mapped onto the model to generate a three-dimensional image, using standard texture-mapping techniques. (See for example, Foley et al., Chapter 16.3). The three-dimensional image is then displayed to the user. The user can change a viewpoint of the image utilizing a pointing device, and a new image is displayed so the user can view the image from the selected viewpoint, again using standard rendering techniques. (See for example, Foley et al., Chapter 16). If the three-dimensional image is determined to not be satisfactory, system  10  displays one of a two-dimensional modality and a two-and-half-dimensional modality (described below in greater detail). 
     Style Selection and Size Determination 
     Once an accepted model of the face is obtained and displayed by system  10 , whether two-dimensional or three-dimensional, a set of icons is displayed adjacent the face model. Each icon represents one style of eyeglass frames available for purchase. In one embodiment, the eyeglass frames are available from a retailer. In an alternative embodiment, the eyeglass frames are available from a manufacturer. In a further embodiment, the eyeglass frames are available from a wholesaler. 
     The user selects a particular style by selecting an icon corresponding to a desired eyeglass frame. System  10  receives  208  the selection and uses information from the model to determine an appropriate size of the eyeglass frames. For example, the manufacturer may specify a recommended size (e.g. diameter of the lens, width of the bridge) in units of inter-ocular distance and/or as a function of the width of the eye. 
     Visualization of Selected Style 
     The selected style, in the selected material and in the size matched to the face of the customer according to the manufacturer&#39;s guidelines is displayed on the image of the person&#39;s face to create  210  a virtual image of the customer wearing the glasses. In the two-dimensional modality, a frontal view of the eyeglass frame is rendered using standard techniques obtained from ray tracing. (See for example, Foley et al., Chapter 14). The eyeglass frames are positioned on the model so that the centers of the lenses are aligned with center of the pupils of the eyes. Alternatively, the pixel values of a photo can be substituted to the image values so as to “superimpose” the photo of the eyeglass frames to the image of the user. If no inter-ocular distance is available, all geometric quantities will be rescaled to the inter-ocular distance as measured on the image in pixel coordinates. Although the inter-ocular distance is not an absolute number, the distance suffices for visualization, since all other geometric quantities will be scaled accordingly. However, in order for the customer to purchase an actual eyeglass frame, the system prompts the user to input an inter-ocular distance, as measured by an optometrist or as available from previous prescriptions or measured using any available method or apparatus. 
     In the three-dimensional modality, a full three-dimensional model is available including metric information. In this modality the eyeglasses are rendered as seen from the viewpoint selected by the user with a pointing device as is well known (See for example, Foley et al., Chapter 16) and/or using standard visualization packages. For the purpose of rendering, when system  10  is operated at an optical store, the user has available the position of the light sources, which is necessary for rendering the view of the glass-frames. In an alternative embodiment, system  10  defaults to diffuse illumination. In a further alternative embodiment, system  10  prompts the user to input a position of the light source. 
     In a still further embodiment, and to increase the realism of the displayed image, the appearance of the lenses is taken into account by system  10 . For sunglasses, the appearance of lenses is taken into account by coloring the area occupied by the lens in the image with a prescribed color. However, depending upon specifications of the desired lenses, prescription lenses typically require additional processing since the area occupied by each lens is warped with a template that depends upon a prescription strength and nature of the lens. In one embodiment, the template warps a larger area of the image into the area occupied by the lens such as in the case of myopia-correcting lenses. In an alternative embodiment, the template expands the area occupied by the lens and crops its edges such as in the case of far-sightedness. When the position of the light source is known, specular highlights are added to increase image realism. 
     Two-and-a-Half-Dimensional Model Visualization 
     In a 2½-dimensional modality, the user moves his/her head and system  10  displays a chosen eyeglass frame of the image and modifies the image so that the selected eyeglass frames appear to move with the viewer and therefore seem attached to his/her head. This 2½ dimensional modality does not utilize a full three-dimensional model and can be implemented with a single camera. 
     After the eyeglass frames image has been superimposed on the image of the person&#39;s face, a feature template is selected  212 , either manually by having the user click on relevant features such as the corners of the eyes, nostrils, eyebrows etc. of the image, or automatically by performing  214  correlation with a stored database of templates for eyes, mouths, eyebrows, nostrils etc. The location on an image plane that scores the highest correlation with the template is chosen as the candidate position for the corresponding feature. Each feature is then tracked from image to image by performing correlation only in a neighborhood of the corresponding position at the previous image. In one embodiment, the size of the neighborhood is fixed or adjusted by the user. In an alternative embodiment, the size of the neighborhood is set by system  10 . Alternatively, the correlation search is performed in a coarse-to-fine fashion by allowing a template to exist at several levels of resolution, and using feature locations at coarse resolution to initialize the search at the finer resolution. Coarser and finer representation of the image is obtained using standard techniques such as filtering and down-sampling, or wavelet transforms. 
     While the position of feature templates is tracked from image to image their relative position is used to define the motion of and select  216  a reference frame. This reference frame is one of a 2-D Euclidean, 2-D affine, 2-D projective and 3-D Euclidean, in increasing order of generality. In the 2-D Euclidean case, the constellation of positions of feature locations is interpreted as moving according to a Euclidean planar motion, which is described by 3 parameters. The parameters are a translation in the plane (one component along the “x” axis and another component along the “y” axis) and a rotation about an axis perpendicular to the plane. The eyeglass frames model is then animated by moving it rigidly onto the image plane and superimposing the eyeglass frames model onto the person&#39;s image, such that the eyeglass frames model has the same rotation and translation as the person&#39;s image. This 2-D Euclidean transformation only accounts for a restricted range of motions of the customer&#39;s head, i.e., a fronto-parallel translation and a rotation about the sagittal plane. 
     To accommodate rotations about a vertical axis, which the customer typically performs to see a profile, a more general transformation is necessary. The simplest translation that accommodates rotations about a vertical axis is an affine transformation, which is described by 6 parameters. The parameters include a translation and a linear deformation of the planar coordinates. This affine transformation takes into account rotations about a vertical plane only when the object of interest (in this case the eyeglass frame) is far enough from the camera, so that parallel projection is a good approximation of perspective. In particular, under a planar affine transformation parallel lines remain parallel, and therefore no “perspective” effect will be visible on the deformed appearance of the eyeglass frames. To take into account perspective effects, a projective transformation is necessary. This is described by 8 parameters, and models the image of a plane moving rigidly in space. To the extent that the features detected are well modeled as belonging to a plane (which is a good approximation for eyebrows, nostrils, corners of eyes etc.), the model generated using a projective transformation is accurate. 
     For an even higher precision one may estimate the full Euclidean motion of the configuration of feature points in space. This estimation can be accomplished using published algorithms in the field of Computer Vision, for instance Chiuso et al., “3D structure from visual motion causally integrated over time: experiments”, in Proc. of the IEEE Intl. Conf. on Comp. Vision and Patt. Recogn., 2000. 
     The estimated transformation, whether Euclidean, affine or projective, is used to modify the appearance of the template of the eyeglass frames. By animating the eyeglass frames with estimated motion parameters, and rendering the eyeglass frames using standard computer graphics techniques, the eyeglass frames will appear as if they were attached to the person&#39;s face and moving with it. The user is then free to move his/her head around, and the face is displayed as if the glasses were being worn, thus creating a moving, virtual image of the face wearing the glasses (acting as a “virtual mirror”). 
     Note that the two and a half dimensional modality does not require accurate knowledge of the shape of the head, but only of the motion of a few landmark points (e.g. corners of the eyes, mouth and ears). 
     When specular reflections are added to the appearance of the lenses for realism, it is necessary to move the position of the highlight corresponding to the motion of the head. Since rendering the appearance of a prescription lens requires processing the image, it may be inappropriate to render the appearance in this imaging modality, since significant computational resources would be needed for this rendering. 
     Classification of Eyeglass Frames and Constraints on Their Shape 
     While the shape of certain eyeglass frames can be modified to a great extent (e.g. rimless eyeglass frames) and still be manufactured at the optical store, other eyeglass frames (e.g. plastic eyeglass frames) can only be modified to a limited extent. Corresponding to each eyeglass frame, system  10  is equipped with a database of constraints on the maximum curvature, tangents at the hinges, and other shape constraints determined by the material. Eyeglass frames can be divided into three different categories depending upon the material properties of the eyeglass frame and an appropriate database of constraints identified  218 . 
     The first type of eyeglass frame is a highly deformable shape. Eyeglass frames having a highly deformable shape include rimless eyeglass frames and wire eyeglass frames where the constraints on the shape is restricted only by the shape of the lens. The second type of eyeglass frame is a locally deformable shape. Eyeglass frames having a locally deformable shape include metal eyeglass frames whose shape can be molded on the shape of the lens, as long as the shape preserves the perimeter, tangent at the hinges and bridge, and maximum curvature specified by the manufacturer. The third type of eyeglass frame is a minimally deformable shape. Eyeglass frames having a minimally deformable shape include plastic eyeglass frames whose shape can be deformed to a small extent, while preserving perimeter, tangent at the hinges, and maximum curvature. 
     In addition, a custom deformation option (CD) refers to the option, presented to a customer, to realize deformation not possible at the optical store. The shape and design information is transmitted to a manufacturer that fabricates a custom eyeglass frame to be shipped to the customer. The modifications allowed under the CD option depend upon the manufacturing facilities and the production plan adopted by the manufacturer. Based upon the style chosen by the customer, system  10  permits certain modifications and warns the user when a modification to be made requires the CD option. 
     Interactive Shape Modification 
     The user modifies  220  the selected eyeglass frames as described below. The shape of each of the eyeglass frames stored in memory is represented as a parameterized curve. In the exemplary embodiment, the curve is represented by a spline having a certain number of control points. For rimmed eyeglass frames, the cordal representation of the control points is used so that the perimeter of the front rim is approximately constant. The contour is then represented by a piecewise linear curve, where the control points are the junctions between linear segments. Once a style has been selected, the user is allowed to modify the shape interactively using a pointing device and changing the position of each control point, highlighted in the display by a square or a cross, or other identifier. In the case of rimmed eyeglass frames, where the contour of the eyeglass frame is represented using the cordal representation, changing the position of one control point alters the position of adjacent control points as well. After the modification request has been input by the user, system  10  refines the modification by finding the closest curve that has the prescribed perimeter, as is well known and described by (Olver et al., “Differential invariant signatures and flows in computer vision: a symmetry group approach”, Technical Report, Department of Electrical Engineering, University of Minnesota, Dec. 6, 1996). In addition to changing the position of the control points by dragging them using a pointing device, the customer moves the control points by acting on a set of rulers that correspond to the horizontal and vertical position of each control point. 
     Depending upon the material properties of the eyeglass frames selected, the system only allows certain modifications. For each modification of the position of a control point, the maximum curvature is computed utilizing known techniques, such as that described in Olver et al. (ref. cit.) or using the cordal approximation. Only positions of control points that meet the specifications on maximum curvature are permitted by system  10 . The constraints on modifications determine a region where control points can be moved, outside which the eyeglass frame does not meet the specifications set by the manufacturer. For rimless eyeglass frames the region will be large, while for plastic rimmed eyeglass frames the region will be small. In the cordal representation these constraints can be easily taken into account. The tangent at the hinges is kept constant by not allowing the two control points adjacent to the hinges to be modified. The maximum curvature is kept below a certain bound that depends upon the material of the particular eyeglass frame being designed. The maximum curvature is kept below the certain bound by limiting the maximum angle between two adjacent segments. 
     Shape Modification Based on Perceived Characteristics 
     In addition to allowing the user to modify the shape of the eyeglass frames by acting on the control points that represent the contour of the lens, system  10  changes the shape of the eyeglass frames by controlling the amount of certain perceptual properties of the shape of the eyeglass frames as described below. System  10  includes a database of maps between shape and perceptual characteristics. In the simplest instance, the user defines a one-to-one map between the position of a control point and a perceptual characteristic. For instance, the horizontal position of the intersection of the tangents at the edges of the top rim is put in one-to-one correspondence with perceived “aggressiveness”. When such a point is close to the center of the face, and therefore the upper rim appears to slant outward, the corresponding shape is declared as “non-aggressive”, while when such a point is close to the outside edge, so that the upper rim slants inward, the corresponding shape is declared to be “aggressive”; in between these two positions there is a continuum of eyeglass frames, see, for example,  FIGS. 5 and 6 . 
     The position of such a point is then mapped directly into the degree of “aggressiveness” and stored  222  in a database. In general, perceptual characteristics are mapped into combinations of positions of control points. Combinations of “geometric coordinates” (i.e. positions of the control points) can be made to correspond to one or more combinations of “perceptual coordinates” (i.e. amount of certain perceptual characteristics, such as “aggressiveness, assertiveness” etc.) as follows. Calling X=[x1, y1, x2, y2, . . . , xN, yN] the geometric coordinates (the position on the image plane of N control points) and P=[p1, p2, . . . , pM] the vector that represents the amount of each of M perceptual quantities as stored in the database, or determined by the manufacturer, the retailer or other expert. 
     For each image, there is a map between these two vectors of numbers. The simplest case consists of a linear map where a matrix A transforms perceptual coordinates into geometric coordinates X=AP. The matrix A can either be assigned by experts, or it can be estimated from data collected (a number of corresponding vectors X1, . . . , Xk, P1, . . . , Pk) during psychophysical experiments, using standard tools from statistical estimation and numerical linear algebra. Psychophysical experiments are designed by generating k random shapes (thereby providing the data X1, . . . , Xk) superimposed to images of random customers. Test subjects evaluate the amount of perceptual characteristics according to standard psychophysical procedures, thereby assigning amounts of perceptual characteristics P1, . . . , Pk. In a simple example, Shown in  FIGS. 5 and 6 , M=N=1, so that A is a scalar quantity (a number), which is assigned manually. More generally, any other map between perceptual and geometric coordinates can be implemented, including nonlinear functions, fuzzy maps, and neural networks etc. 
     The map database is flexible, since it has to fit the desires and the specifications of the manufacturer and/or the retailer. In particular, the manufacturer and/or the retailer are able to choose which perceptual characteristics to use as a “basis”, depending upon the particular eyeglass frame selected, or depending upon the particular clientele expected at a particular optical store. A characteristic of the design, however, is the presence of a map between geometric features and perceptual characteristics. In the exemplary embodiment, the features map is constructed ad-hoc by associating the perceptual characteristic “aggressiveness” to a horizontal position of the central control point of the upper contour of the rim. The map between the position of control points and a set of perceptual properties such as assertiveness, personability, conservativeness, intellectuality etc. represents a re-parameterization of the state-space of the eyeglass frame, which is the position of each control point. 
     Database Modification 
     The map database can be left un-modified, or can be modified interactively thereby adapting to particular clientele of a given optical store. Modification of the map database is achieved by allowing the users to input the amounts of a given perceptual quality as if the map was continuously being adapted. User input acts as additional data which system  10  uses to modify the map previously stored according to the same standard psychophysical procedures adopted to generate the map. 
     Storage of Selected Designs and Visualization for Comparison 
     Once a selected style and shape is considered to be satisfactory by the user, it is stored  224  by system  10  upon the transmission by the user of a save command, such as the user selecting a save icon. System  10  then allows the user to select a different eyeglass frame style and initiate the design process again. At any point in time the user can retrieve all selected eyeglass frame and view them one next to the other for comparison, as shown in  FIG. 6 . 
     Suggestion of Preferred Shapes and Collaborative Filtering 
     After the customer has saved a number of preferred choices of shapes and styles, system  10  uses collaborative filtering  226 , such as described in U.S. Pat. Nos. 4,870,579 and 4,996,642 to identify shapes and styles that are preferred by groups of customers whose choices most closely resemble the choices of the current customers. System  10  receives customer requests for assistance in selecting eyeglass frames upon the user selecting a help icon. System  10  then displays to the user choices obtained via collaborative filtering. 
     Interfacing to Lens-Cutting Machines 
     As described above, server  12  is connected to application server  52 . In one embodiment application server  52  controls a lens-cutting machine. In addition, application server  52  controls an eyeglass frame manufacturing machine. Server  12  transmits information and data to application server  52  which is utilized to fabricate  228  the lens and the eyeglass frame. The shape of the lens is determined by a parametric curve that is transmitted electronically to the lens-cutting machine which grinds a dummy lens to which the eyeglass frame is fitted. Since different grinders represent the shape of the lens differently, the interface between system  10  and the particular grinder converts the parameterization into the format used by the particular grinder. 
     Once the eyeglasses are fabricated, the eyeglasses are ready for the customer to try on to determine the comfort of fit of the selected design. If the eyeglass frame has been selected using the CD option, the data are transmitted directly to the manufacturer via system  10  for manufacturing. 
     During remote access of system  10 , The user connects to an access site, such as a dedicated manufacturers site. In the two-dimensional modality, system  10  requests the user to input the location in memory of a frontal image of his/her face in a standard image format (e.g. jpeg, gif, tiff, pict, ras etc.). In the three-dimensional modality, system  10  requests the user to input a file that stores the position of a number of points in a three-dimensional mesh in a standard format (e.g. VRML) and of a file that stores a texture map of his/her face. In the 2½ dimensional modality, system  10  requests the user to input a stream of images, either as live video, or pre-recorded in a standard format (e.g. animated GIF, MPEG etc.). 
     After the appropriate modifications have been chosen, the design is transmitted to the manufacturer, together with prescription information when applicable (including inter-ocular distance), and the complete eyeglass frame is shipped directly to the customer. 
     While the invention has been described in terms of various specific embodiments, those skilled in the art will recognize that the invention can be practiced with modification within the spirit and scope of the claims.