Dual video camera system for scanning hardcopy documents

[0002] 1. Field of the Invention

[0003] The present invention relates generally to an over-the-desk document scanning system, and more particularly to, a method and apparatus for generating a composite image of a hardcopy document using images from multiple video cameras.

[0004] 2. Description of Related Art

[0005] Over-the-desk scanning systems that position a video camera above a desk to capture images of hardcopy document are known. An example of such an over-the-desk scanning system is disclosed by Wellner in U.S. Pat. No. 5,511,148 entitled “Interactive Copying System.” In operation, the over-the-desk scanning system captures images of hardcopy documents and digitizes them for further processing. These captured images of hardcopy documents arranged on a desk are subsequently displayed on a computer monitor immediately coupled to the over-the-desk scanning system or remotely coupled via a network that form part of a video conferencing system.

[0006] Over-the-desk (i.e., face-up) scanning of hardcopy documents with a video camera has several advantages over traditional face-down scanning techniques. One advantage of face-up scanning is that a hardcopy document can be simultaneously read on a physical desktop and scanned without requiring the hardcopy document to be repositioned in a face down orientation. This advantage provides seamless integration between working hardcopy documents positioned on a physical desktop and the electronic document applications operating on a computer to which the over-the-desk video camera is coupled. Another advantage is that additional elements, such as a pointing finger, can be captured, for example, to annotate the hardcopy document in its corresponding scanned representation during a video conferencing session.

[0007] Although the use of video cameras is very effective with video conferencing applications, video cameras do not typically yield images with sufficient quality (i.e., resolution) to enable successful document decoding using OCR (Optical Character Recognition). Never the less, it would be desirable for an over-the-desk document scanning system to record large high resolution images of hardcopy documents. These recorded large high resolution images could then either be broadcast as part of a video conferencing system or be edited for use with or in other electronic documents. Furthermore, in order for such an interactive over-the-desk scanning system to perform effectively, it would be desirable that such a system be adapted to record images of hardcopy documents that have an undetermined thickness. It would therefore be advantageous to provide an over-the-desk document scanning system that is adapted to both efficiently generate large high resolution images using video cameras in a manner that is independent of the thickness of a hardcopy document.

[0008] In accordance the invention, there is provided an apparatus and method therefor, for scanning hardcopy documents. The apparatus includes an image acquisition system and a frame merger module. Initially, the image acquisition system simultaneously records parts of a hardcopy document positioned face-up on a work surface. The parts of the hardcopy document are recorded without perspective distortion in a first image and a second image by the image acquisition system. A portion of each of the parts of the hardcopy document recorded in the first image and the second image record an identical segment of the hardcopy document. Subsequently, the frame merger module forms a composite image of the hardcopy document by stitching the first image and the second image together at the portions in each image that record the identical segment of the hardcopy document. The frame merger module identifies the portion in the first image and the portion in the second image by computing correlation values of high gradient images of the first image and the second image for different regions of overlap between the first image and the second image.

[0009] These and other aspects of the invention will become apparent from the following description read in conjunction with the accompanying drawings wherein the same reference numerals have been applied to like parts and in which:

[0010] FIG. 1 illustrates an over-the-desk document scanning apparatus for generating a composite image of overlapping video images of a hardcopy document;

[0011] FIG. 2. illustrates a block diagram of a general purpose computer that includes hardware and software components for carrying out the present invention;

[0012] FIG. 3 illustrates a side view of the camera mount shown in FIG. 1;

[0013] FIG. 4 illustrates a top-down view of the camera housings shown in FIGS. 1 and 2;

[0014] FIG. 5 illustrates an example of two image segments recorded using a general imaging geometry;

[0015] FIG. 6 illustrates a top down view of the hardcopy document shown in FIG. 1 with a first image region recorded in a first image and a second image region recorded in a second image by two different video cameras before the two images are registered rotationally and translationally;

[0016] FIG. 7 illustrates an example in which the two image segments shown in FIG. 5 after they are registered rotationally and translationally in the x-direction using the camera mount adjustments shown in FIG. 4;

[0017] FIGS. 8 and 9 illustrate a flow diagram of the steps performed by the document scanning apparatus to register the two images translationally in the y-direction;

[0018] FIGS. 10 and 11 illustrate high gradient image segments for the image segments that are illustrated in the image segments 504 and 502 that are shown in FIG. 7;

[0019] FIG. 12 illustrates an example of a composite image generated after performing the steps shown in the flow diagram in FIG. 9;

[0020] FIG. 13 illustrates an example of a composite image that has been adaptively thresholded;

[0021] FIG. 14 illustrates an example of an adaptively thresholded image that has been analyzed to identify textual and formatting content; and

[0022] FIGS. 15-24 illustrate a detailed example of the steps performed in FIG. 9 for generating a composite image of two recorded images that overlap a portion of a hardcopy document.

[0023] A. Operating Environment

[0024] FIG. 1 illustrates a document scanning apparatus or arrangement 100 for generating a composite image of recorded video images that partially overlap a portion of different parts of a hardcopy document. The arrangement 100 includes a relatively planar surface 102 onto which a hardcopy document 104 is positioned and recorded by an image acquisition system 105. The surface 102, which may for example form part of a desk, is oriented in the Figures using an X, Y, Z Cartesian coordinate system.

[0025] In one embodiment, the image acquisition system 105 includes two video cameras 107 and 109 that are positioned in video camera housings 106 and 108, respectively. The video camera housings 106 and 108 are supported in stationary positions above the surface 102 by a camera mount 118 that is fixedly attached to the surface 102. In accordance with the present invention, the output of the video cameras 107 and 109 is transmitted to a general purpose computer 110 for further processing and viewing on a display 112.

[0026] The general purpose computer 110, which is shown in one embodiment in FIG. 2, includes hardware components 202 and software modules 204. The hardware components 202 are made up of a processor (i.e., CPU) 206, memory 208 (ROM, RAM, etc.), persistent storage 210 (e.g., CD-ROM, hard drive, floppy drive, tape drive, etc.), user I/O 212, and network I/O 214. The user I/O 212 can include a keyboard 116, a pointing device 117 (e.g., pointing stick, mouse, etc.), the display 112, and video cameras 107 and 109. The network I/O 214 is a communications gateway to a network 215 such as the Internet.

[0027] The software modules 204 of the general purpose computer 110 include an operating system 216, a frame merger module 218, a document editing module 220, and an image enhancement module 222. The operating system 216 permits processor 105 to control the various hardware devices such as the cameras 107 and 109, and the display 112. In addition, the frame merger module 218 enables the processor 105 to formulate a composite image of two images simultaneously recorded by the cameras 107 and 109.

[0028] As discussed in detail below, the frame merger module 218 is adapted to stitch together two images that are simultaneously recorded by the video cameras 107 and 109 for viewing as a single composite image on the display 112. Subsequently if desired, the composite image generated by the frame merger module 218 can be enhanced or edited by invoking the image enhancement module 222 or the document editing module 220, respectively.

[0029] It will be appreciated by those skilled in the art that the general purpose computer 110 can be defined by any one of a plurality of configurations. For instance, the processor 206 may in alternate embodiments be defined by a collection of microprocessors configured for multiprocessing. In yet other embodiments, the functions provided by software modules 204 may be distributed across multiple computers acting together as a single processing unit.

[0030] B. Overview of Multi-Camera Document Viewer

[0031] The document scanning arrangement 100 is adapted to form a high resolution image of the hardcopy document 104 using low resolution images recorded by the cameras 107 and 109. The high resolution image is formed using multiple low resolution images each of which records different parts of the same hardcopy document. A portion of each of the parts of the hardcopy document recorded in a first image and a second image record an identical segment of the hardcopy document 104. By rapidly identifying the overlapping portions of the parts of the hardcopy document recorded in the images, a composite image of the hardcopy document is formed.

[0032] In accordance with one aspect of the invention, multiple video cameras are employed to quickly capture images of the hardcopy document 104 positioned on the surface 102. Because the arrangement 100 is recording and displaying images in real time, forming a composite image of simultaneously recorded images must be efficient. In accordance with another aspect of the invention, the composite image is formed using both physical registration using a multi-camera mount 118 (discussed in detail below in Section B.1) and computational registration using the frame merger module 218 (discussed in detail below in Section B.2). In accordance with yet another aspect of the invention, the camera mount 118, the camera housings 106 and 108, and the frame merger module 218 are adapted to generate a composite image of hardcopy documents that have varying degrees of thickness (in the z-direction).

[0033] B.1 Multi-Camera Mount

[0034] FIG. 3 illustrates a side view of the camera mount 118 shown in FIG. 1. A screw 304 on camera mount 118 provides a field of view adjustment for the cameras 107 and 109. The field of view adjustment moves cameras 107 and 109 in the vertical direction (i.e., z-direction) along a slider 307 relative to the surface 102 as indicated by arrow 306. Moving the cameras 107 and 109 closer to or further away from the surface 102 decreases or increases, respectively, the field of view and, therefore, the resolution of a composite image of the document 104 recorded by the arrangement 100. In addition, as shown in FIG. 3, the cameras 107 and 109 are arranged with a maximum field of view 308. This maximum field of view 308 in combination with a region of overlap 314 defines a maximum document thickness 310 at which a hardcopy document 104 can be scanned by the arrangement 100. Documents that exceed the maximum document thickness 310 cannot be stitched together by the frame merger module 218 because no region of overlap exists between simultaneously recorded images.

[0035] FIG. 4 illustrates a detailed top-down view of the camera housings 106 and 108 that are shown in FIGS. 1 and 2. The camera housing 106 includes the video camera 107, a top-to-bottom (i.e., y-direction) adjustment screw 406, an angular (i.e., φ) adjustment screw 408, and height adjustment screws 412. The camera housing 108 includes the video camera 109 and a side-to-side (i.e., x-direction) adjustment screw 410. In one embodiment, the video cameras 107 and 109 are the CCM-DS250 digital video camera, which is sold by Sony Electronics Inc. The adjustments 304, 406, 408, 410, and 412 are used to register the images that are simultaneously recorded by the video cameras 107 and 109 by imposing geometric constraints (i.e., rotational and translational in the x-direction). These geometric constraints simplify the number of operations that the frame merger module 218 must perform to form a composite image of the hardcopy document 104.

[0036] More specifically, the cameras 107 and 109 are fixedly positioned in the camera housings 106 and 108, respectively, at an angle that is substantially perpendicular to the x-y plane of the surface 102. This angle simplifies computations performed by the frame merger module by minimizing perspective distortion in the images recorded by the cameras 107 and 109. In addition, the lenses of the cameras 107 and 109 are selected to be substantially identical so that the simultaneously recorded images have the same or similar scale. However, if the simultaneously recorded images are out of scale, the height adjustment screws 412 are used to position the height of one camera relative to the other (i.e., in the z-direction). Advantageously, by minimizing perspective distortion the geometric arrangement of the two cameras 107 and 109 can be defined as purely Euclidean.

[0037] FIG. 5 illustrates an example that shows two image segments 502 and 504 from images recorded by the cameras 107 and 109, respectively, when the document scanning apparatus 100 is in a general imaging geometry. More specifically, the example illustrated in FIG. 5 shows alignment of the top-half of a hardcopy document recorded by the image segment 504 and the bottom-half the document recorded by the image segment 502. That is, FIG. 5 illustrates an example of two image segments 502 and 504 recorded by the cameras 107 and 109, respectively, before using the adjustments 406, 408, and 410 shown in FIG. 4 to align the recorded image segments 502 and 504 of the cameras 107 and 109 rotationally by the angle φ₁and translationally in the x-direction.

[0038] FIG. 6 illustrates a top down view of the hardcopy document 104 shown in FIG. 1 with a first image region 602 and a second image region 604 recorded by each of the video cameras 107 and 109, respectively. FIG. 6 illustrates the different corrections required to register the two image regions 602 and 604 rotationally by the angle φ₂and translationally in the x and y directions. The camera mount adjustments 406, 408, and 410 described above are used to register the image regions 602 and 604 rotationally by the angle φ₂and translationally in the x-direction.

[0039] For example, initially the adjustment screw 408 can be used to minimize the relative angle of rotation φ₂between the two image regions 602 and 604. Subsequently, the adjustment screw 410 can be used to minimize the translation between the two image regions 602 and 604 in the x-direction by moving the second image region relative to the first image region as indicated by arrow 606. Finally, the adjustment screw 406 can be used to define the region of overlap between the two image regions 602 and 604 as indicated by arrow 608.

[0040] In accordance with the invention, the adjustment screw 406 is not used to minimize the offset between the image regions in the y-direction. Instead, the adjustment screw 406 in combination with the adjustment knob 306 is used to define the maximum field of view 308 and the maximum document thickness 310 illustrated in FIG. 3. Advantageously, the scanning system 100 is adapted to record hardcopy documents having variable thickness by registering in the y-direction images recording the two image regions 602 and 604.

[0041] After registering the two image regions 602 and 604 rotationally by the angle φ₂and in the x-direction, an overlapping region between the bottom of the second image region 604 and the top of the first image region 602 remains to be registered. For example, FIG. 7 illustrates the two image segments 502 and 504 after they are registered rotationally by the angle φ₁and translationally in the x-direction but not translationally in the y-direction. To register the image segments 502 and 504 translationally in the y-direction they are processed by the frame merger module 218 as described in detail below.

[0042] B.2 Frame Merger Module

[0043] A composite image is formed from multiple images by stitching the multiple video images together at a boundary where the multiple images overlap. Exactly where the location of the boundary exists between the overlapping images is variable and depends on the thickness of the bound document 104. More specifically as illustrated in FIG. 3, the region of overlap 312 between recorded images is proportional to the thickness in the z-direction of the hardcopy document 104. Advantageously, the frame merger module 218 is adapted to stitch together images having varying degrees of overlap.

[0044] In operation, the frame merger module 218 identifies the region of overlap 312 between two images by computing the one-dimensional correlation of high gradient features between different regions of overlap. The correlation value of high gradient features is used by the frame merger module 218 to identify the degree of similarity between overlapping pixels in each of the regions of overlap and thereby identify the boundary between the overlapping images.

[0045] FIG. 8 illustrates a flow diagram of the steps performed by the frame merger module 218 for forming a composite image from two simultaneously recorded images. At step 800, the elements of the arrangement 100 (i.e., computer 100, display 112, and cameras 107 and 109) are turned on and initialized for scanning the hardcopy document 104. At step 802, a first image or frame A is recorded from camera A (e.g., camera 107) and a second image or frame B is recorded from camera B (e.g., camera 109). Once the two images A and B are recorded in the memory 208 of the computer 110, the frame merger module 218 is invoked at step 803 to form a composite image. FIG. 9 illustrates the steps for performing step 803 shown in FIG. 8.

[0046] At step 804, which is shown in FIG. 9, the recorded images A and B are binarized. The images A and B are binarized by thresholding the pixels in the images to one of two values (e.g., black/white; 0/1). At step 806, high gradient images A and B are computed for the binarized images A and B, respectively. A high gradient image is computed by locating the edge pixels in the overlap direction (i.e., y-direction) of binarized images A and B. That is, a high gradient image is computed by setting to white only those pixels that have black pixels with white neighbors in the overlap direction (i.e., y-direction). For example, FIGS. 10 and 11 illustrate high gradient image segments for the image segments 504 and 502 respectively, which are illustrated in FIG. 7.

[0047] At step 808, selected variables for forming a composite image are initialized. These variables include an overlap index N, which is initialized to one, a maximum correlation factor (CFMAX), which is initialized to zero, and an overlap value (NOUT) for a maximum correlation factor (CFMAX), which is initialized to zero. The overlap index N is used to increment the region of overlap between the high gradient images A and B after completing an iteration of the steps 810, 811, 812, 814, 815, 817 and 818. The variable NOUT records the value of the overlap index N at which the maximum correlation factor (CFMAX) is achieved for a particular region of overlap between the images A and B.

[0048] At step 810, the high gradient images A and B are overlapped by the number of rows of pixels defined by the value of the overlap index N initialized at step 808 to define a region of overlap between each of the high gradient images A and B. Subsequently at step 811, a maximum feature count (PSMAX) is determined by first computing a sum value for each high gradient image. The sum value for each high gradient image is computed by summing the number of white pixels in the region of overlap between the high gradient images. Subsequently, once each sum value is computed, the value of PSMAX is set equal to the greater of the sum values (i.e., the image having the greater number of white pixels in the region of overlap).

[0049] At step 812, the number of correlated pixels in the region of overlap is summed to define a pixel sum (PS). A pixel is a correlated pixel at step 812 when two overlapping pixels in the regions of overlap of the high gradient images A and B are both white. At step 814, a correlation factor (CF) is computed by dividing the pixel sum (PS), computed at step 812, by the value of the maximum feature count (PSMAX), computed at step 811. This computation is efficient because the correlation is a binary AND operation that changes depending on the number of rows of overlapping pixels in the overlap region, which is in part defined by the overlap index N. At step 815, if the correlation factor (CF) computed at step 814 is greater than the current value of the maximum correlation factor (CFMAX) then the current value of the correlation factor (CF) is stored in CFMAX and the current value of the overlap index N is stored in NOUT.

[0050] At step 817, if the overlap index N is greater than a maximum overlap index (NMAX) then step 819 is performed; otherwise, the pixel overlap N is incremented by one at step 818 and steps 810, 811, 812, 814, 815. and 817 are repeated. At step 819, a predetermined threshold value of 0.5, which is determined empirically, is compared to the maximum correlation factor (CFMAX). If the maximum correlation factor (CFMAX) is greater than the threshold 0.5 at step 819, then step 821 is performed; otherwise, step 820 is performed. At step 821, a composite image is defined by setting the overlap of the two images A and B to equal the variable NOUT, which records the overlap index at which the correlation factor is a maximum. A composite image is defined by generating a single image having dimensions in the x-direction equal to the images A and B and in the y-direction equal to the dimensions of the images A and B minus the number of pixels defining the overlap index N (i.e., eliminating the region of overlap in one of the images A and B).

[0051] At step 820, the overlap index NOUT determined from a prior frame of images is used to define the composite image. That is, if the correlation factor does not increase above the predetermined threshold value of 0.5 between iterations then no correlated pixels are said to exist in the overlap regions of the images A and B. The distance 314 shown in FIG. 3 defines the maximum overlap region that can exist between the high gradient images A and B. This distance is maximized when the adjustment screw 304 is used to maximize the distance between the cameras 107 and 109 and the surface 102. After completing steps 820 or 821, step 822 is performed.

[0052] Referring again to FIG. 8, if at step 822 the content of the composite image requires further processing, then steps 824 and 826 are performed; otherwise, the composite image is displayed or transmitted for display at step 828. An example of a composite image generated after performing step 818 is illustrated in FIG. 12. Whether the content of a composite image requires further processing at step 822 is a user definable setting at a user interface of the computer 110. At step 824, the image enhancement module 222 adaptively thresholds the composite image defined at step 818. Details of a method for adaptively thresholding the composite image is disclosed by Taylor et al. in U.S. patent application Ser. No. 09/081,259, now U.S. Pat. No. 6,072,907 entitled “Method and Apparatus For Enhancing And Thresholding Images,” which is hereby incorporated by reference. FIG. 13 illustrates an example of the composite image in FIG. 12 after being adaptively thresholded.

[0053] At step 826, the adaptively thresholded image defined at step 824 is analyzed using OCR (Optical Character Recognition) techniques to identify textual and other formatting content, which is subsequently displayed or transmitted at step 828. One advantage for performing step 826 is to improve legibility of the composite image formed at step 803. An example of an application that is adapted to convert the thresholded composite image into a simple ASCII text document or a formatted document with tables and pictures is TextBridge® (which is sold by ScanSoft, Inc.). FIG. 14 illustrates the appearance of the adaptively thresholded composite image shown in FIG. 13 after having been analyzed using OCR techniques. In an alternate embodiment, step 826 is performed after step 832 to minimize the processing performed when a composite image is prepared for display or transmission at step 828.

[0054] Finally at step 830, if a determination is made to suspend the continuous generation and display or transmission of composite images then step 832 is performed; otherwise, step 800 is repeated. For example if step 832 is performed, the user may want to suspend processing in order to edit the composite image by cutting and pasting elements from it to another document. Textual content can be cut from the image identified at step 826 and pasted in other electronic documents. Alternatively, the textual content can be cut directly from the composite image defined at step 818 using techniques described by Taylor et al., in U.S. patent application Ser. No. 09/081,266 now U.S. Pat. No. 6,178,270 entitled “Method and Apparatus for Selecting Text And Image Data From Video Images,” which is hereby incorporated by reference.

[0055] C. Detailed Example

[0056] FIGS. 15-24 illustrate a detailed example of the steps set forth in FIG. 9 for generating a composite image of two recorded images that overlap a portion of a hardcopy document. FIG. 15 illustrates an example of a segment of recorded images A and B, which are identified as reference numbers 1502 and 1504 and recorded by cameras 107 and 109, respectively. The squares in each image represent pixel values after each image has been binarized at step 804 in FIG. 9. The two image segments 1502 and 1504 shown in FIG. 15 have six black pixels each, and the remaining pixels in each image are white pixels.

[0057] FIG. 16 illustrates the outcome of performing step 806 shown in FIG. 9, which involves generating high gradient images 1602 and 1604 from the binarized image segments 1502 and 1504, respectively, that are shown in FIG. 15. The high gradient images 1602 and 1604 have white pixels where there exists black pixels with neighboring white pixels in the overlap direction (i.e., y-direction) in its corresponding binarized image. For example, the black pixel 1506 in binarized image 1502 in FIG. 15, yields two white pixels 1606 and 1608 in the high gradient image 1602 in FIG. 16.

[0058] FIGS. 17-24 illustrate the incremental overlapping of the high gradient images 1602 and 1604. The size of the overlapped region defined by the overlap index N in each of these Figures is indicated by the brackets identified by reference number 1700. FIG. 17 illustrates the high gradient images 1602 and 1604 with one row of overlapped pixels. FIGS. 18-24 illustrate the high gradient images 1602 and 1604 in which the value of the overlap index N is successively incremented by one starting at one. No white pixels in the overlapped regions 1700 of the high gradient images 1602 and 1604 shown in FIGS. 17, 18, 20, 22, and 24, exist because no two overlapping pixels in the overlapped regions 1700 were white. The pixel sum (PS) as well as the resulting correlation factor (CF) in these overlapping regions 1700 with no overlapping white pixels is equal to zero. In contrast, FIGS. 19, 21, and 23 illustrate nonzero pixel sums and therefore non-zero correlation factors. Because the overlap region 1700 shown in FIG. 23 has the highest correlation factor of all of the overlapped regions shown in FIGS. 17-22 and 24, the overlap region 1700 shown in FIG. 23 defines NOUT or the pixel overlap that is used to define a composite image for the recorded images A and B.

[0059] D. Summary

[0060] It will be appreciated by those skilled in the art that although the forgoing description concerned the recording and stitching of two low resolution images, the present invention can be used to form a composite image of an array of low resolution images greater than two. It will further be appreciated that an array of two or more images stitched together can be recorded by a number of cameras that may not equal the number of low resolution images recorded.

[0061] In addition, it will be appreciated that the operations performed by the frame merger module 218 may be readily implemented in software using software development environments that provide portable source code that can be used on a variety of hardware platforms. Alternatively, the disclosed system may be implemented partially or fully in hardware using standard logic circuits. Whether software or hardware is used to implement the system varies depending on the speed and efficiency requirements of the system and also the particular function and the particular software or hardware systems and the particular microprocessor or microcomputer systems being utilized.

[0062] The invention has been described with reference to a particular embodiment. Modifications and alterations will occur to others upon reading and understanding this specification taken together with the drawings. The embodiments are but examples, and various alternatives, modifications, variations or improvements may be made by those skilled in the art from this teaching which are intended to be encompassed by the following claims.