DE20080319U1 - Video camera in which the main functions are implemented in the main computer software - Google Patents

Description

·* ♦•as* ■·■ *· ₄

VIDEO CAMERA WHERE THE MAIN FUNCTIONS ARE IN THE
MAIN COMPUTER SOFTWARE TO BE IMPLEMENTED

REFERENCES TO RELATED APPLICATIONS
.

This application is a continuation-in-part of U.S. Application No. 09/345,167, filed June 30, 1999, entitled "IMAGE SENSOR BASED VIGNETTING CORRECTION," U.S. Application No. 09/464,364, filed December 15, 1999, entitled "DYNAMIC ANOMALOUS PIXEL DETECTION AND CORRECTION," and U.S. Application No. 09/343,934, filed June 30, 1999, entitled "FAST DECODING," all of which are incorporated herein by reference.

BACKGROUND OF THE INVENTION

The present invention relates to video cameras, and more particularly to video cameras connected to a computer or other intelligent device through a shared interface such as the universal serial bus (USB).

Video cameras have been developed to provide both still and moving images that can connect to a computer to provide a digitized image. Such cameras can be connected to the computer via a shared bus, such as the USB. This limits the bandwidth of data that can be sent, requiring compression of the video data. Typically, cameras perform some of the pre-processing of the image in the camera electronics, thus both freeing the computer's CPU from processing and potentially reducing the amount of data that needs to be compressed and sent over the bus.

In such a design, some functions must be performed in the camera. For example, a CCD or CMOS sensor in the camera may have faulty detector positions that do not capture light correctly. These can be compensated for by averaging the amount of light detected at adjacent detector locations and substituting the value provided by the faulty location for it. This type of processing must be performed before other types of processing now typically performed in a video camera, such as color processing and scaling.

Fig. 1 is a block diagram of a typical video camera that can interface with a host computer via a bus. A lens 10 focuses light onto a sensor 12 with associated control logic for reading the sensor data. The data is supplied to an analog-to-digital converter (ADC) 14 where it is digitized. The data is then stored in a frame buffer 16. Pixel correction can be applied to the data using circuitry 18. The correction data can be stored in a programmable memory 20. This memory can be programmed during the manufacturing process before the camera is shipped.

A number of other functions are typically performed in the camera shown in Figure 1 in a particular order, although they may be in other orders or may be connected via a bus so that they vary when they are called. For example, a color processing circuit 22 may perform a number of color functions, such as converting the received data from one color format, such as YUV, to another format, such as RGB. A fixed value multiplier function 24 may scale the image to suit the display desired on the host computer. A compression circuit 26 compresses

izes the data to reduce the amount of data to be transferred over the shared bus. Finally, a bus interface circuit 28 implements the protocols of a bus 30 for transferring data to a remote host.

Huffman coding is one of the algorithms most widely used for compressing video data. Huffman coding has been used in various image and video compression standards, such as the MPEG-II, H.261, H.263, and H.323 standards established by the Joint Photographic Experts Group (JPEG) and the Motion Picture Experts Group (MPEG). These standards are incorporated herein by reference in their entirety and for all purposes. Huffman coding is a lossless statistical coding technique. Huffman coding uses probability to select the shortest codeword for the data that occurs most frequently. For example, when encoding English text, "E", which is a very common character in the English language, can be represented by a 2-bit codeword, whereas "A", which is not as commonly used, can be represented by an 8-bit codeword.

Thus, Huffman coding compresses the data by assigning shorter code words to more frequently occurring data and longer code words to less frequently occurring data. The assigned code words can be kept in a table which is then used by both the receivers and transmitters. Further details regarding Huffman coding can be found in "A Method for the Construction of Minimum Redundancy Codes", Proceedings of the IRE, Volume 40, No. 9, September 1952, pp. 1098-1101, by D.A. Huffman, which is incorporated by reference in its entirety and for all purposes.

Moreover, Huffman codewords are constructed such that no codeword is the prefix of another codeword. This ensures the unambiguous decoding of each symbol from a bitstream of data despite the variable lengths of the codes. An additional description of the properties of Huffman codes can be found in the Data Compression Book, M&T Books, 1996, by M. Nelson and JL GailIy ₁ , which is also incorporated by reference in its entirety and for all purposes. On pages 31-35, this reference proposes a decoding algorithm based on a tree sequence. However, this algorithm is not suitable for fast decompression using most currently available microprocessors, such as the Pentium® family from Intel®.

The vignetting effect occurs when the brightness around the edges of a screen is less than the brightness in the center of the screen, creating a halo effect.

Professional photographers sometimes try to intentionally create this effect using a suitable lens or filter to produce a softened image at the edges of an image. However, when this effect appears unintentionally in digital photographs, it's annoying. A variety of techniques have been developed to measure and address vignetting effects.

U.S. Patent No. 4,884,140 shows an analog circuit for providing vignetting compensation for a video camera that uses a zoom lens that causes vignetting.

US Patent No. 5,434,902 shows the measurement of the vignetting effect for an X-ray examination device using an image with constant brightness. A correction

•·&Ugr;7· ·:

The correction factor is then stored in memory for each pixel.

US Patent No. 5,576,797 shows the detection of vignetting effects in a camera with a focus detection device.

US Patent No. 5,381,174 shows the correction of vignetting due to the operation of a zoom lens using a field frequency sawtooth signal.

U.S. Patent No. 4,816,663 shows the detection of vignetting between a phototaking lens and an optical focus detection system.

.

Digital cameras for use with a personal computer for personal teleconferencing have become increasingly inexpensive. This puts pressure on camera manufacturers to use cheaper lenses that have more vignetting effect.

In addition, price pressures are forcing manufacturers to use fewer semiconductor chips, thus making the use of semiconductor memory to store vignetting corrections undesirable. Consequently, there is a need for a digital camera that is inexpensive to manufacture and also corrects the vignetting of a low-cost lens.

The processes used to manufacture image sensors, although very advanced, are not perfect. Photositems in an image sensor array can vary in their sensitivity or ability to convert light into electrical currents. Some variation is expected and tolerable, but on occasion individual photosites in an array can be dead, inactive or overactive. This can result in a displayed image with a dark or black dot, bright white dot or a dot.

t ·
&psgr;&phgr; «»&Ogr;&Igr;

with incorrect color, all of which are unwanted and undesirable for the end user. Those in the digital imaging field have also recognized the problems caused by incorrect digitization of target images and have proposed various solutions for detecting and correcting erroneous pixels. These prior art methods and systems can be broadly divided into two groups.

On the one hand, there are various hardware-based methods for detecting and correcting defective pixels extracted from an image sensor array. These hardware-based methods and systems are quite common for video camera manufacturers. Most conventional video cameras using a solid-state image pickup device include a defective pixel detection and correction circuit for correcting defective pixels extracted from an image sensor array. The defective pixels are generated when or after the image sensor array is manufactured. In such a camera, a defective pixel correction circuit detects a defective pixel and stores the position data and various data regarding the defective pixel in a read-only memory (ROM) or the like. When the video camera is in use, the pixel data from the defective pixel is replaced with data from a pixel near the defective pixel. Such a method and system is disclosed in U.S. Pat. No. 5,796,430. The disadvantage of such methods is the need to install and program memory devices during product assembly and testing, which adds cost and delay. In addition, hardware device costs also increase due to the need to add correction circuitry or logic to the application-specific integrated circuit (ASIC) for video processing.

On the other hand, there are various software-based methods for detecting and correcting bad pixels in digital images. One such method and system is disclosed in U.S. Pat. No. 5,982,946. Such software-based methods generally aim to correct bad image pixels in an already digitized and fully processed image. These already digitized images are in their final displayable and stored forms which have already undergone color processing, compression, and various other processing performed on the raw data read from an image sensor array. Therefore, such software-based methods dealing with fully processed digital images can correct anomalous pixels caused by any number of image defects, such as dust or dirt on the original scene, dust or dirt on the lens used to capture the scene, as well as anomalous pixels in the digitized image caused by bad photosites. These methods typically rely on fairly sophisticated and expensive systems and computer software to detect and correct bad pixels. These methods generally require user input to identify the location of the potentially bad image pixels. Once the user has visually scanned an entire image and marked potentially bad image pixels, the system containing the software program takes over the correction of the marked bad pixels. In addition to requiring user input, such methods are also expensive, tedious and very time-consuming.

0 agile. ■

The proliferation of low-cost digital still and video camera devices that interface with a PC requires solutions for fast, dynamic

· rni-f — ···. ···

see, inexpensive and intelligent detection and correction of faulty pixels.

SUMMARY OF THE INVENTION
5

The present invention provides a low cost camera by implementing the main functions in the host software. This is accomplished by sending digitized raw data directly from the camera to the host. The increased volume of raw data is handled by either an improved compression/decompression scheme using lossless compression, using lossy compression, or using a higher bandwidth shared bus. By moving such functions as color processing and scaling to the host, pixel correction can also be moved to the host. This in turn allows the frame buffer to be eliminated from the camera. Finally, the camera can use a low cost lens by implementing vignetting correction with a vignetting correction value stored in a register of the camera for later access by the host to make corrections.

In one embodiment, the host decompresses the transmitted data using a processor with the capability of simultaneous operations on multiple packed pixel values, such as Intel MMX™ technology. This maintains sufficient decompression speed 0 for a larger amount of data with minimal impact on the frame rate. In one embodiment, a group of bits from the data stream are duplicated and delivered to multiple locations in a register where they can be compared to multiple maximum values simultaneously. This achieves

allows a quick determination of how many bits of the variable bit coding correspond to a pixel value.

In an embodiment using lossy compression, vignetting, gamma, distortion or image blurring correction and pixel correction are performed in the camera itself, since the ability to correct would be degraded by the loss of information during the lossy compression/decompression process. However, color processing, scaling and other operations are still performed in the main computer, achieving a low-cost camera that does not require frame buffer memory and color processing and scaling circuitry.

In one embodiment, the camera can be made inexpensive using an inexpensive lens even if it has vignetting distortion. This is accomplished by providing a memory element such as a register in the camera. This memory element is programmed at the time of manufacture with a value corresponding to the amount of vignetting or correction required. The register can then be read by the host during operation to determine the amount of correction required in a vignetting correction algorithm which is performed in the host on the received data prior to any further processing. In an alternative embodiment, the memory element can store a correction or value factor for other defects in the lens or other aspects of the camera. For example, an indication of bad pixel locations could be stored for subsequent reading and correction by the host.

&iacgr;&ogr;

For a further understanding of the nature and advantages of the invention, reference should be made to the following description taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

Fig. 1 is a block diagram of a prior art video camera;

Fig. 2 is a block diagram of an embodiment of the invention in which the main functions are relocated to a main computer;

Fig. 3 is a diagram illustrating the operation of parallel Huffman decoding processes;

4 illustrates an example of a computer system used to carry out the methods of embodiments of the present invention;

5 illustrates a simplified system block diagram of a typical computer system 100 used to carry out the methods of embodiments of the present invention;

6 is a simplified block diagram of a SIMD system 300 according to an embodiment of the present invention;

7 illustrates a simplified block diagram of a system 400 according to an embodiment of the present invention; ■

ii

Fig. 8 illustrates a sequential decoding method 500 for decoding Huffman encoded data according to an embodiment of the present invention; and

Fig. 9 illustrates a parallel decoding method 600 for decoding Huffman encoded data according to another embodiment of the present invention,-

Fig. 10 is a drawing of a pixel matrix and a brightness curve illustrating the vignetting effect;

Fig. 11 is a block diagram of an embodiment of a vignetting correction according to the invention;

Fig. 12 illustrates a simplified flow chart of a method for detecting and correcting defective pixels according to an embodiment of the present invention,

Fig. 13 is a block diagram of a video camera system according to an embodiment of the present invention;

Figure 14 is a timing diagram of the pulses provided to a CMOS sensor array according to an embodiment of the present invention.
25

DESCRIPTION OF SPECIAL EMBODIMENTS

I OVERALL SYSTEM ^:

0 Fig. 2 is a block diagram of an embodiment of the invention. A camera 32 comprises a lens 10, a sensor and control logic 12 and an ADC 14 as in the prior art. However, the other main functions are eliminated, apart from a compression block 26 and a bus interface 28. In addition, a correction register 34 is provided.

• · '· t

to store a value corresponding to the vignetting of lens 10.

The camera connects to the main processor 36 via a shared bus 30. In the main processor 36, the blocks shown are programming blocks that are executed by the processor of the main processor 36. These are a decompression block 38, a vignetting correction block 40, a pixel correction block 42, a color processing block 44, and a scaling block 46. Also shown is a statistics memory 48, which may be part of the main processor memory, for storing statistical information about pixels that require correction.

II. HUFFMAN DECOMPRESSION

Preferably, the processor used by host computer 36 includes the ability to perform operations on multiple packed pixels in a single register in parallel. For example, Intel MMX™ technology provides a number of instructions for such operations on packed pixels in the microprocessor registers. Accordingly, it is desirable to exploit such functions to increase processing speed. However, certain operations do not lend themselves to such simultaneous operation. For example, Huffman compression is often used for video data and is used in the embodiment of this invention. This is a variable code length compression mechanism. In other words, the number of bits corresponding to a 0 pixel value could be 1, 2, 3, 4, etc., and can vary from pixel to pixel. Without knowing the number of bits in advance, and with different sizes, it is not immediately apparent how to use a packed pixel register that uses the same size for each of the pixel representations.

φ ·

With the limited bandwidth of today's USB technology, it is desirable to somehow be able to perform parallel decompression processing when the camera is to send raw data that has a much larger amount of data than data that has been preprocessed. This is only accomplished by using the packed pixel configuration to perform Huffman decoding.

Fig. 3 is a diagram generally illustrating how parallel Huffman decoding proceeds. An incoming data stream 50 is represented by a number of letters. Each letter is an arbitrary symbol indicating a different number of bits. In the example shown, the first of a number of bits, A, is duplicated four times and placed in four positions in a first register 52. A second register 54 stores four different masks. The masks allow comparison to be made with different portions of the bits in bit segment A. For example, the number of bits 0 of A being examined could be 1, 2, 3, and 4, respectively. These would then be compared with the maximum values for the Huffman codes for 1, 2, 3, and 4 bits. These four different maximum values are stored in another register 56. Thus, instead of comparing the number of bits A with four different values one after the other, this can be done in parallel even if the number of bits to be compared is variable. This variation is overcome using the masking operation. Thus, the same number of bits are stored in the register at each pixel location, but a different number of bits are compared for each of the pixel locations by the masking operation.

In the example shown, the bit segment A corresponds to the fact that it lies within the maximum segment M3, which

is then used in an equation to index a combined Huffman value table 58. Using the arithmetic result of the previous comparison as an index, what usually required three different table lookups in the prior art can now be performed in a single table lookup, thus saving further processing time.

Figure 4 illustrates an example of a computer system used to execute the software of the present invention. Figure 4 shows a computer system 100 that includes a monitor 104, a display 102, a chassis 108, a keyboard 214 (see Figure 5), and a mouse 110. The mouse 110 may include one or more buttons such as the mouse buttons 112. The chassis 108 may include a CD-ROM drive 106 and a hard disk drive (not shown) that may be used to store and retrieve software programs incorporating the present invention. Although the CD-ROM 106 is shown as a removable medium, other removable tangible media may be used, including floppy disks, tape drives, ZI P® drives, and flash memory. The chassis 108 may also include familiar computer components (not shown) such as a processor, memory, and the like.

Fig. 5 illustrates a simplified system block diagram of a typical computer system 100 used to execute the software of embodiments of the present invention. As shown in Fig. 1, the computer system 100 may include the monitor 104. The computer system 100 may further include subsystems such as an I/O controller 204, a system memory 206, a central processor 208, a speaker 210, a removable disk 212, a keyboard 214, a hard disk 216, and a network interface 218. Other computer systems suitable for use in the

The computer systems suitable for the present invention may include additional or fewer subsystems. For example, another computer system could include more than one processor 208 (i.e., a multiprocessor system) or a cache memory. Arrows such as 220 represent a system bus architecture of the computer system 100. However, these arrows 220 represent any interconnection scheme used to connect the subsystems.

For example, a local bus could be used to connect the central processor 208 to the system memory 206. An image capture device such as a charge-coupled device (CCD) camera may also be connected to the computer system 100 for capturing image data.

The image capture device may be connected to the computer system 100 via the same or a different bus architecture, such as a universal serial bus (USB), and the like. The USB may provide support for plugging and operating more than 100 connected peripheral devices using an identification number that is compared to a database of device drivers. The USB may also be connected to the computer system 100 via the I/O controller 204 or the network interface 218. In addition, the computer system 100 may be configured to communicate with the Internet via, for example, the I/O controller 204 or the network interface 218. Thus, data may be transferred to and from the computer system 100 by a variety of devices. The computer system 100 shown in FIG. 4 is just one example of a computer system suitable for use with the present invention. Other configurations of subsystems suitable for use with the present invention will be readily apparent to one of ordinary skill in the art.

. .

The present invention may be embodied in any microprocessor capable of single instruction multiple data (SIMD) execution. For example, the Intel® MMX™ microprocessors, the Sun® UltraSPARC® with Visual instruction set, 3DNow!™ from Advance Micro Device, Inc.®, Intel® MMX™ with streaming SIMD extensions, and the like may be used. For example, an implementation using the Intel® MMX™ is described. The MMX™ technology was formally introduced in January 1997 to accelerate multimedia applications requiring a CPU. The MMX™ technology provides a set of instructions (57 instructions) introduced by Intel® Corporation. It can perform addition, subtraction, multiplication, logical and place shifts on a unit of 64 bits in the same instruction. The unit of 64 bits may also be treated as 8 bytes, 4 words, 2 double words, or 1 quad word. Instructions for saturating arithmetic and packing/unpacking data are provided, as are those that transfer data between MMX™ registers and integer registers. More information regarding MMX™ technology can be found in "Introduction to the Intel® Architecture MMX™ Technology Developer's Manual," Intel® (1996), which is incorporated herein by reference in its entirety and for all purposes.

Fig. 6 is a simplified block diagram of a SIMD system 300. The system 300 includes an MMX™ processor 302 that currently supports a set of 57 instructions. The MMX™ processor may be implemented within a CPU or, alternatively, may be implemented in a separate chip.

-The MMX™ processor 302 receives data from the registers 304a-h. Each of the registers 304a-h is 64 bits wide. Each of these registers can contain 8x8, 16x4, 32x2, 64x1 data bits. The MMX™ processor 302 receives the data from the registers 304a-h.

17 ·*

star 304a-h and performs the required operations on the data in one cycle. The processed data is then returned to either a memory 306 or to the registers 304a-h. The memory 306 may be implemented within the MMX™ processor 302 or it may alternatively be a shared memory. Consequently, the MMX™ processor 302 can perform the same operations on different data simultaneously, hence it has a SIMD architecture. . .

.

Figure 7 illustrates a simplified block diagram of a system 400 using USB. A camera 402 captures images and provides them to a bitstream conversion block 404. The camera 402 may include circuitry for converting analog data to digital data. The camera 402 may also include circuitry for performing data compression and/or encoding. The camera 402 and the bitstream conversion block 404 are connected via a connector 406. The connector 406 may be selected from a number of connectors or bus architectures well known to those of ordinary skill in the art. The connector 406 is preferably a USB connector. In some implementations, USB provides a bandwidth of 12 MB/s. Another choice for the connector 406 may be Firewire (IEEE 1394), which may provide a bandwidth of 100 MB/s, 200, 400, or 800 MB/s. A USB connector is preferred for some embodiments because it is a powered bus that currently provides up to 500 μA and 5 V. The power provided by the USB may be used to operate the devices connected to the bus, such as the camera 402. In addition, the USB is less expensive to implement. Since the USB does not have the same bandwidth as Firewire, the USB may be used in some embodiments if the data is first compressed before being transmitted on the USB.

.35 will be. - ^: · . .

18 ·*·

Thus, camera 402 may include compression circuitry to compress the captured images prior to sending the data to bitstream conversion block 404. Camera 402 may be any number of devices for capturing images, including a CCD, a complementary metal oxide semiconductor (CMOS), and the like. Bitstream conversion block 404 may be configured to convert serially transmitted data into data packets. For example, bitstream conversion block 404 may accumulate data for each frame and send the accumulated data to a decompression block 408. The frame of data may be any size, but is preferably 352x288 pixels. The frame may also be a block of 320x240, 176x144, or 160x120 pixels. In some embodiments, the frame of data may be a block of 640x480 pixels. The decompression block 408 decompresses and/or decodes the data received from the bitstream conversion block 404. The decoding may be performed according to Huffman coding, arithmetic coding, other types of statistical coding, and the like. The bitstream conversion block 404 may also include buffers for storing the data received from the camera 402 and the data sent to the decompression block 408.

■ ..■'..-

The decompressed data from decompression block 408 is then provided to a color conversion block 410. The data from decompression block 408 may be in any format, but is preferably in YUV format, where Y is luminance, U is red chrominance (also known as CR), and V is blue chrominance (also known as CB). Conversion block 410 converts the YUV format data to a format suitable for display 412, including RGB (red, green, and blue). Display 412 may be any output device, including a printer.

ker, a handheld device, and the like. The system 400 also includes a memory 414 that may provide storage for the display 412, the color conversion block 410, and the bitstream conversion block 404. The memory 414 may be any type of memory, such as dynamic random access memory (DRAM), extended output DRAM (EDO DRAM), synchronous DRAM (SDRAM), video RAM (VRAM), static RAM (SRAM), and the like. Alternatively, the bitstream conversion block 404, the color conversion block 410, and the display 412 may have their own local memory. The decompression block 408 may also have its own memory or may use the memory 414 for its storage if desired.

Fig. 8 illustrates a sequential decoding method 500 for decoding Huffman encoded data. The sequential decoding method 500 uses the following four tables to generate the decoded value:

MINCODE[I] - minimum value of code words with length J;

MAXCODE[IJ - maximum value of code words with length J;

HUFFVAL[J] - table of symbol values corresponding to the J-th codeword; and

VALPTR[I] - the index for the start of the list of values in HUFFVAL that are decoded by codewords of length I.

. The minimum length of all codewords is MinLength and the maximum length of all codewords is MaxLength. Therefore, the size of the MINCODE, MAXCODE and VALPTR tables is equal to [Max- 0 Length-MinLength+1] . The size of HUFFVAL depends on the number of codewords and is denoted as N. The three tables MINCODE, MAXCODE and VALPTR are used to decode a pointer into the HUFFVAL table for each valid Huffman code.

In a step 502, bitstream data is received for decoding. In a step 504, a current code length J is set to MinLength . Step 504 also initializes a variable CODE to NEXTBITS[MinLength] which contains the codewords from the bitstream provided by step 502. A step 506 compares the value of CODE to MAXCODE[I]. If the value of CODE is greater than the value of MAXCODE[I], it is indicated that the current codeword has a greater length than J, which was first initialized to MinLength in step 504, and step 506 is followed by a step 508. In step 508, the value of I is incremented by one. Step 508 also reads the next bit of the bitstream into CODE. Step 508 updates the value of CODE by performing a logical shift left (SLL) on the current value of CODE by one. Bit and filling the least significant bit of CODE with the next bit from the bit stream ■ (NEXTBIT) ...

On the other hand, if it is determined in step 506 that the value of CODE is not greater than the value of MAXCODE[I], the current codeword is indicated to have a length equal to or less than J, and step 506 is followed by a step 510. Step 510 decodes the symbol value. Step 510 calculates a code value pointer J and then uses J ₁ to calculate the symbol value. Step 510 sets J to [VALPTR[I-MinLength] +CODE-MINCODE [ I-MinLength] }. Step 510 then calculates the symbol value by setting VALUE to HUFFVAL[J]. Thus, step 510 performs three table lookups including VALPTJ?, MINCODE , and HUFFVAL to calculate the symbol value. The calculated symbol value (VALUE) is then provided for output to a step 512.

The sequential decoding process 500 is repeated for the next code word.

The Huffman table used for encoding and decoding can be customized for each implementation, but most coding standards provide a standard Huffman table. Table 1 below presents a recommended Huffman table for the luminance DC difference according to the JPEG standard. More information regarding the JPEG standard can be found in "JPEG - Still Image Data Compression Standard", Appendix A, ISO DIS 10918-1, Requirements and Guidelines, p. F-26, Van Nostrand Reinhold, 1993, by William B. Pennebaker and Joan L. Mitchell, which is incorporated by reference in its entirety and for all purposes.

In the JPEG standard, MinLength is 2 and MaxLength is 16. Codewords are further grouped by length and sorted in an ascending order of values in each length group. The values in MINCODE and MAXCODE are signed integers of 16 bits.

Huff Value Code length code word Huff Code 0 2 00 0 1 3 010 2 2 3 011 3 3 3 100 4 4 3 101 5 5 3 110 6 6 4 1110 14 7 5 11110 30 8th 6 111110 62 · . 9 7 1111110 126 10 8th 11111110 254 , 11 9 111111110 510

Table 1

In Table 1, Codeword represents the current codewords from the bitstream; CodeLength is the length of each codeword; HuffCode is the value of each codeword, and HuffValue is the Huffman code for each symbol.
■ ■ ■

Taking the values from Table 1 as an example, where MinLength = 2 and MaxLength = 9, the table values of the three tables used by the sequential decoding method 500 are as follows:
10

MINCODE[8] = {0, 2, 14, 30, 62, 126, 254, 510};
MAXCODE[8] = {0, 6, 14, 30, 62, 126, 254, 510}; and
VALPTR [8] = {0, 1, 6, 7, 8, 9, 10, 11}.

For example, considering an incoming bit stream "010", step 504 sets J to 2 and CODE to "01". Step 506 returns YES because "01" is greater than MAXCODE[2-2], which is 0. In step 508, J is incremented to 3 and CODE is set to "010". Step 506 repeats again, this time returning NO because "010" is less than MAXCODE[3-2] , which is 6. Then step 510 sets J" equal to 1. Step 510 also looks up the symbol value for HUFFVAL[I] and outputs that symbol value (VALCZB) in step 512.

Thus, the sequential method 500 repeatedly shifts the bit stream into CODE and compares the current code to the maximum code of the same length. Once the code length is known, decoding each value requires two additions and three table lookups. This algorithm is 0 in nature sequential because the code lengths are checked sequentially. That is, before checking the length I, there is no indication of whether the current code length is J, 1+1, 1+2, etc. . . ■ · ■ . .

·

9 illustrates a parallel decoding method 600 for decoding Huffman encoded data in accordance with an embodiment of the present invention. For example, an implementation of the parallel decoding method 600 as discussed with reference to FIG. 6 is described. Sample JPEG values discussed with reference to FIG. 8 and Table 1 are also used in the sample embodiment. However, the parallel decoding method 600 may be performed in any processor capable of SIMD implementations, including Intel® MMX™ microprocessors, the Sun® UltraSPARC® with Visual instruction set, 3DNowI™ from Advance Micro Device, Inc.®, Intel® MMX™ with streaming SIMD extensions, and the like.

As detailed above, MMX™ technology can perform operations on a unit of 64 bits in the same instruction. The unit of 64 bits can also be treated as 8 bytes, 4 words, 2 double words, or 1 quad word. For the example according to values from Table 1, the 64 bits can be treated as four 16-bit registers (or 4 words) since the maximum code word length in Table 1 is 9. For the exemplary embodiment of Figure 9, the MMX™ instructions PSRL, PSLL, and PSRA' are used to shift the contents of selected variables. PSRL denotes packed logical shift right. PSLL denotes packed logical shift left, and PSRA denotes packed arithmetic shift right.

The parallel decoding process 600 receives the bit stream in a step 602. In a step 604, the bit stream is arranged in 4-bit parts (or quadbits) with a thin-tail format. This means that if the original bit stream has the form bO,bl,b2,b3, ... (where bi stands for byte i), then the converted

converted bit stream has the following form: bl,b0 _/ bl _/ b0 _/ bl,b0,bl _/ b0,b3 _/ b2,b3 _/ b2,b3 _/ b2,b3,b2,b3 _/ b2,.·.

This conversion can be implemented using 5.5 cycles for each 16-bit word. In a step 606, the values of I, MASK and CODE4 are initialized. As discussed above for the JPEG example, J is initialized to 2. Step 606 initializes CODE4 to the first set of 4xl6-bit codes (or quadbits) from the bitstream. The parallel decoding method 600 uses MASK to mask out the bits for a comparison operation in step 608. The initial value for MASK is set to

"1100,0000,0000,0000,1110,0000,0000,0000,1111,0000,0000,0000, 1111,1000,0000,0000b" or "OXCOOO ₇ EOOO ₇ FOOCfSOO" is set.

This is the bit mask for code lengths 2 to 5 that are checked in the first iteration of the parallel decoding process 600.

In a step 608, CODE4 is masked by the value of MASK . Step 608 also sets MAXCODE4 to MAXCODE4_P[I~I+3], which represents values of MAXCODE4_P for I ₁ 1+1, 1+2, and 1+3 . Consequently, MAXCODE4 contains the maximum values for the four consecutive code lengths. Since the four values for MAXCODE4 are loaded in a single instruction, the MAXCODS table for the parallel decoding method 600 can be generated as follows:

1 = 0

while I is less than (MaxLength-MinLength+2) do
: J = (J/4)*4+3-I%4

MAXCODE4_P[I] = (2 ^{16 ' ^MinLength ' ^J) * MAXCODE [J] )+1

1=1 + 1 ■■ . . '

endwhile

where "/" denotes division by truncation and "%" denotes a modulo operation. The values of MAXCODE_P are 16-bit unsigned integers. The MAXCODE table only needs to be generated once for each Huffman table.
. .

Taking the same example as the sequential Huffman decoding algorithm discussed with reference to Fig. 8, the MAXCODE table for the parallel algorithm has the following values:
10

MAXC0DE_P[8] = {61441, 57345, 49153, 1, 65281, 65025, 64513, 63489}

For this example, the dimension of this table must be a multiple of 4. In addition, zero is assumed for those code lengths that do not exist in the Huffman code table.

In a step 610, the value of MAXCODE4 is compared to CODE4 , which was initialized and masked in steps 606 and 608. Since in the embodiments using MMX™ technology, the MMX™ instruction PCMPEQ only compares signed words, this comparison operation can be performed by an unsigned subtraction with saturation and a comparison with zero. The values of MAXCODE+1 can be stored in MAXCODE4 . If CODE4 is determined to be greater than MAXCODE4, then in a step 612, J is incremented by 4 and MASK is updated by arithmetically shifting its value 4 bits to the right. The new value of MASK generates the bit mask for 0 for the next remaining 4 codeword lengths (6 through 9). After step 612, steps 608 and 610 are repeated. Consequently, for the example of Table 1, steps 608 and 610 are repeated twice, once for codeword lengths 2 to 5 and once for codeword lengths 6 to 9.

· ■ ■ .

If

Once step 610 returns YES, step 614 determines which of the four lengths being tested contains the symbol. Consequently, step 614 calculates a value DIF ₁ which is set to [MAXC0DE4-CODEZ-I] logically shifted 4 bits to the right. Step 610 also performs a table lookup to provide the found symbol value (VALUE) . Step 614 looks up the symbol value (VALUE) in a table HUFFVAL_P. .

For this example, assuming 1<K17, a table HUFFVAL_P can be created using [1+16* (MAXCODE[I]-CODE)] as an index. The following applies:

M = max (MAXCODE[I] -MINCODE[I]) ; and
I=O, 1, 2, .... MaxLength-MinLength.

The table HUFFVAL_P has a size of [16*(M+2)]. CODENUM[I] shall denote the number of code words whose code length is ( I+MinLength) . CODE[J] shall denote the code value of the J-th code with code length I. The entries of the large HUFFVAL table can be calculated as follows:

1=0

while J is less than (MaxLength-MinLength+1) do

J=O
while J is less than CODENUM[I] do

HUFFVAL_P[ J+l6* (MAXCODE[I] +1- CODE[J]) ]=HUFFVAL[VALPTR[I] +CODE[J]
-MINCODE[I]]

- J = J +1 ■ , ■

endwhile
J = J + 1
endwhile
'■■..■

Consequently, the values in the HUFFVAL_P table are the maximum size of 16-bit unsigned integers depending on the number of Huffman codes. By combining the three table lookups of the sequential method into one, the instructions required to index a Huffman code value are significantly reduced. At the same time, reducing the number of table lookups saves valuable register space. Also note that {MAXCODE[I]+1-CODE) was calculated when the code length was determined and is available for this table lookup.

In a step 616, the calculated symbol value (VALUE) is output. Once the code length of the current Huffman code is determined in step 614, the current 4xl6-bit code word can be shifted to the left and the same number of bits from the next 4xl6-bit code word can be inserted. Decoding of the next Huffman code can then be started.

Thus, the parallel decoding method 600 reads 4 bits of data at a time from the bit stream. All consecutive 4-bit lengths are checked in parallel to determine if the current codeword falls within that range. Instead of the 16 checks required to cover the range 1 to 16 in the sequential algorithm, only 4 checks are required to cover the same range. Another significant improvement is to combine the three table lookups for decoding into a single table lookup. This has the effect of minimizing computations as well as register usage, which can be very valuable in many situations.

SAMPLE DESIGN EXAMPLE FOR LENGTHS 1 TO 8 ■ .'

' ■

The exemplary embodiment discussed above assumes that the codewords have lengths between 2 and 9. However, if the codewords have lengths between 1 and 8, the decoding can be performed in units of 8 bits. A maximum of one check instead of 8 is required for each codeword. This requires that the bitstream be expanded to 8x8 bits. For example, if the input bitstream is "bO,bl,..." (where bi stands for byte i), the converted bitstream is bO^CbCbO^O^O^O^O^l^l^l^l^l^l^l, . . . ". The initial bitmask is now

"10000000,11000000,11100000,11110000,11111000,11111100,111111 10,11111111 b" or

The table entries are created as follows:

J=O

while J is less than (MaxLength-MinLength +1) do

J = (1/8)*8 + 7 - J%8
MAXCODE_P [I ]= (2 ⁱ⁸ - ^MinLength ~ ^I) * MAXCODE [J] )+l

1=1 + 1
endwhile

J=I .

while J is less than 9 do

J=O
while J is less than CODENUM[I] do

HUFFVAL_P [J+8*( MAXCODE[I]+1-CODE [J] ) ] =HUFFVAL [ VALPTR [I] + CODE[J]
-MINCODE[I]]

J = J + 1
endwhile
1=1+1

end while . '

■35 ' ■ · . ■ ■ ' ' ■'-·

The values for the HUFFVAL_P table are 8-bit unsigned integers. The values for the MAXCODE_P table are 8-bit unsigned integers.

SAMPLE DESIGN EXAMPLE FOR LENGTHS 1 TO 32

If the length of the codewords is between 1 and 32, decoding can be performed on units of 32 bits. A maximum of 8 checks instead of 16 checks are required to determine the length of a codeword. The bit stream is expanded into a form of 2x32 bits as follows:

Input bit stream: b0,bl,b2,b3,b4,b5,b6,b7,...
Output bit stream:

b3,b2,bl,b0,b3,b2,bl,b0,b7,b6,b5,b4,b7,b6,b5,b4,...

The initial bitmask is now

"10000000,00000000,00000000,00000000,11000000,00000000,000000

00,00000000,00000000. b" or "0x8000,0000,C000,0000".
20

The table entries are also calculated as follows:

J=O ' '

while J is less than 32 do
J = (1/2)*2 + 1 - J%2

■ MAXCODE_P[I]=(2 ^{32 ~ ^MinLengch ' ^I) *MAXCODE[J] ) +1

1=1 + 1
endwhile

I=I ■ .·■ . ■

while I am less than 32 do
J=O
while J is less than CODENUM[I] do

HUFFVAL_P [ 1+ 32*( MAXCODE[I]+ 1- CODE[J])]=HUFFVAL[VALPTR[I]+CODE[J]

-MINCODE[I]]

J =_J +1
endwhile
J= J +' 1
endwhile

The values for the MAXCODE_P table are therefore 32-bit unsigned integers. The values of the HUFFVAL_P table are the maximum size of 32-bit unsigned integers.

PERFORMANCE EVALUATION

The proposed parallel Huffman decoding algorithm was implemented in an MMX™ assembly code. For this section, the CPU time to expand the original bitstream into 4xl6-bit parts is included in the decoding time.

If codewords of length I appear with a probability of 2" ¹ , then the probability that a codeword has length I is CODENUM [ I ]* 2' ¹ . If T[I] is the time to decode a codeword of length I, then the average decoding time for a symbol can be calculated as follows:

16

CODENUM[I] * T[I]

1 = 2

Assuming compression of ten images in Common Intermediate Format (CIF) using a sequential algorithm, and if only a quarter of the discrete cosine transform (DCT) coefficients are encoded using the RUN-LEVEL symbols, the number of Huffman codewords to be decoded can be calculated as follows:

(352*288/4)*10 = 253440

Even if DCT is chosen for this example, it would be obvious to one of ordinary skill in the art to use arbitrary transforms such as differential parse code modulation (DPCM), wavelength, subband transform, vector quantization, and the like. Using a 166 MHz Intel® Pentium® processor with MMX™, the decompression timing for the best case (where all codewords are 2 to 5 bits long), the worst case (where all codewords are 12 to 15 bits long), and the intermediate case (where code lengths are distributed between 2 and 16 bits) is shown in Table 2 below.

Decoding time (in ms) Parallel Huffman decoding best case 111 medium case 113 worst case 218

Table 2

Table 2 demonstrates that the parallel algorithm significantly reduces the worst case timing while providing superior performance for the middle case. Note also that even better results can be achieved by further optimizing the assembly code.

· ■ . .

As will be understood by those of ordinary skill in the art, the present invention may be embodied in other specific forms without departing from the spirit or essential characteristics thereof. For example, the methods of the present invention may also be applied to other SIMD systems.

such as the Sun® UltraSPARC® with Visual Instruction Set, 3DNow!™ from Advance Micro Device, Inc.®, and the like may be used.

Intel®'s new Pentium® III (also known as Katmai), the successor to the Pentium® II, also adds streaming SIMD extensions. The Pentium® III provides 70 new instructions. Many instructions are for floating point SIMD operations aimed at 3-D applications. Several instructions for fixed point number operations have also been added. These instructions are partly aimed at MPEG encoding/decoding (motion estimation, motion compensation). However, those of ordinary skill in the art would understand that these new instructions can be exploited to further speed up the decoding methods of the present invention. For example, min and max operations can speed up code length detection. An insert instruction for transferring integer registers and a portion of MMX™ registers also provides a speedup. Likewise, a collect instruction can duplicate the bit stream in a more efficient manner.

Alternatively, the methods of the present invention may be implemented in a computer system. For example, the methods 500 and 600 may be implemented in a peripheral component interconnect (PCI) card. The PCI card may be installed on the PCI bus of a personal computer. Other bus technologies such as NUBUS, ISA, EISA, universal serial bus (USB), 1394 Firewire, and accelerated graphics port (AGP) may also be used. Moreover, the methods of the present invention may be implemented using available routines and features such as caching, new instruction sets, multiprocessor systems, and their equivalents.

III. VIGNETTING CORRECTION

The register 34 of Fig. 2 allows vignetting correction to be applied, thus allowing a less expensive lens 10 to be used in the camera 32. This allows the cost of the camera to be brought down even further.

In operation, the processor in the host 36 polls the camera to read the value of register 34. This is then used in the vignetting correction block 40 of the host to correct camera vignetting errors. This is done before the pixel correction of block 42 to avoid the vignetting being mistaken for a bad pixel. The correction can be done by adding an offset value to the supplied pixel brightness value.

Fig. 10 illustrates a pixel matrix 11 and a corresponding brightness curve 13 over the Y axis. A central pixel 17 with the value (xo/Yo) corresponds to the point of maximum brightness of the lens. A second example pixel 15 is close to the minimum brightness, showing a vignetting effect "with the difference between the curve 13 and a maximum brightness value 19. The present invention corrects this vignetting effect in both the X and Y directions.

In one embodiment, a threshold indicated by r _T is shown within which the curve 13 is close to the maximum value 19 and no vignetting correction needs to be applied. Alternatively, the correction can still be applied to all pixels in order to avoid any transition effects at the points r _T .

Depending on the particular lens chosen, its specified amount of vignetting can be used to provide a constant in register 72. Thus, different lenses could be used in the manufacture of a camera by simply programming a different constant value into register 72. This allows multiple sources of lenses to be used and allows compensation for variations in lens quality from lot to lot or manufacturer to manufacturer.

An example of an equation for implementing and a hardware or software for performing vignetting correction is given below. Although the constant is stored in the camera, vignetting correction can be performed by either the hardware/software in the camera or the software in a host computer. The vignetting error of a low quality lens can be modeled as a pass through the center of the lens and a parabolic curve near the edge of the lens. The transformation function is isotropic: let pi and po be the pixel value before and after vignetting correction, and let x _o and y ₀ be the coordinate of the center of the lens (should be the center of the image if the lens is mounted correctly). Then

Po = pi*(a*r ² +l) ■'.,·■

= pi* (a* ((XX ₀ ) ² +(Y-Yo) ² )+l

"a" is a small positive constant. To be on the safe side, a maximum of 50% vignetting can be corrected, which means:

. 1.0 = 0.5*(a*(176*176+144*144)+l)

·

a = l,9338*10" ⁵

Normalized by 2 ²⁶ this gives a - 1298. By limiting a to 0 to 1023 and performing the reverse calculation, the maximum correctable vignetting is 56%.

Note that the above formula does not take the pixel aspect ratio into account. For a square pixel, the equation is exact, but for a pixel aspect ratio of 12/11, the result differs slightly. a is also scaled by ¹ A when the sensor format is unscaled QCIF (subsampled QCIF from CIF by dropping every other pixel in both horizontal and vertical directions). .'■'■

If y _A is 10 bits, (xx ₀ ) ² and (yy ₀ ) ² are 16 bits (for CIF size) and y ₀ is 10 bits, this specifies that a must be 10 bits (0 to 1023).

Fig. 11 is a block diagram of one embodiment of a hardware system or software blocks for implementing the equation described above. In particular, a random drive circuit/block 80 is applied to the drive input of a multiplexer 82. If the pixel position is less than the threshold 1C2 [r _T ], the input pixel pi on line 84 is simply passed through to the output pixel po on line 86. If it is greater than the threshold, vignetting correction is achieved by implementing the above formula with the hardware shown in Fig. 11.

0 applied. >

In particular, the current x-value of pixel xi is applied to the arithmetic circuit/block 88, where the central pixel Xo is subtracted from it. This value is then calculated by applying its input signal twice via a

Multiplexer 90 to a multiplier circuit/block 92 where it is summed in an adder/accumulator 94. Similarly, the y value yi is supplied to a circuit/block 96 where the difference from the central y value Yo is determined. This is also supplied as two values via multiplexer 90 to a multiplier 92 where it is squared and supplied to adder/accumulator 94 where it is added to the squared x value. The use of the multiplexer simply allows, by time division multiplexing, the same multiplier 92 to be used for both calculations. Obviously, an alternative would be to provide two separate multiplier units.

The output of accumulator 94 is then provided to a second multiplier 96 where it is multiplied by the constant value from register 72. The value of one is then subtracted in a unit 98 and this value is multiplied by the pixel value pi in a multiplier 100. The output is provided on a line 102 via multiplexer 82 to output line 86. Obviously, variations of the circuit could be provided, such as using the same multiplier circuit for multipliers 92, 96 and 100, with the multiplier being used for different purposes in different time slots.

The optional circuit/block 80 provides a comparator 104 which compares the output of the adder/accumulator 94 (the radius value of the values x ² +y ² ) with the threshold radius 0 in a register 106.

Preferably, the constant a has the same number of bits as the pixel value pi. If pi is 10 bits while the x and y values are 16 bits, the constant a would therefore be 10 bits, a can also be scaled by ¹ A if the sensor format

mat is unscaled QCIF (cropped). Thus, a correction is provided whereby the image is cropped before vignetting correction.

In addition, pixel aspect ratio correction can be made by multiplying the y value by 11/12 when a TV is used.

In one embodiment, the correction only takes place outside a predefined diameter. This assumes that the lens works satisfactorily around the center of the lens, which is often a reasonable assumption. A more accurate correction model can be derived. Let r _T be the diameter within which the vignetting error can be ignored. Then

if r<=r _T

Po=Pi/

if r>=r _T

Po=Pi* (a*(r ² -r _T ² )+l)

=Pi* (a* (( (XX ₀ ) ² + (Y-Yo) ² - ( (xt-Xo) ² + (Yt-

Yo) ² )

The present invention thus allows for variation in lenses, and also for cheaper lenses to be used. It improves the automatic gain control (AGC) and AWB in the host computer. It also allows for better object motion tracking. Object motion tracking is usually done by assuming that the luminance value is the same as the object moves to the edge of a sensor, and thus tracking by looking for the same luminance value. Obviously, vignetting effects can thwart efforts to locate the object. By applying vignetting correction close to the sensor, this can be overcome. The

finding also provides overall improved video quality.

IV. PIXEL CORRECTION
5

Block 42 of Fig. 2 performs pixel correction in the host computer. This allows faulty detector locations in the CMOS or CCD sensor array to be corrected. Generally, this is done by comparing a brightness value with the brightness value of the neighboring detector elements. If the difference is more than a threshold value, it is assumed that this is due to a faulty sensor element. Consequently, a corrected value is substituted, typically an average of the surrounding pixel values.

To allow this to be done in the host computer without affecting the frame rate of the video, the algorithm is kept simple. This is accomplished by two main features. First, the detection of bad pixels is not performed on any frame, but only on a subsample of the frames. For example, detection may only be performed every 32-128 frames. Second, the statistics kept are simple to reduce the amount of processing required. In particular, the statistics may simply include the location of the pixel element and the frequency or number of times a bad pixel was detected.

0 The system operates by reading or scanning the raw image data from an image capture device for pixels that differ in intensity from their neighboring pixels by more than a specified amount. The image sensor raw data is the unprocessed brightness data output signal obtained from the image sensor and does not contain any lossy

compression or color processing. The image sensor reads an analog voltage or current, converts it to digital and sends the signal to a host computer without further processing or compression. The photosites on the image sensor are used to create either digital color or monochrome still or
The raw image data is sent to the intelligent host computer over a bus at a data transfer rate determined by the bus protocol of the specific bus, such as a universal serial bus (USB) or a parallel port.

The raw image sensor data, the location and frequency of occurrence of each faulty pixel, and the results of any intermediate calculations performed by the computer program are all stored in memory. Other algorithms are then used to average the values of neighboring pixels of an anomalous pixel to replace the data from the faulty pixel. The corrected data can then be further processed and ultimately displayed on the monitor. The method involves video subsampling, which means that the detection is performed and repeated at different frame intervals. The video subsampling is performed on one in every 128 (1/128) frames. Alternatively, the video subsampling can be performed on every 1/64 video frames. And in yet another embodiment, the video subsampling is performed on every l/(n times X) frames, where η is an integer and X is not equal to 50 or 60. 50 and 60 correspond to 50 Hz and 60 Hz, which are AC lighting frequencies used in the United States and Europe, respectively. This ensures that anomalous raw data pixels are not image errors of the artificial lighting systems. The use of video subsampling enables fast and optimal corrections.

* * it**

doors without the need to sample each frame, which would adversely affect the processing speed of the processor and the system. Of course, video subsampling is not used when detecting and correcting bad pixels in still images.

A statistical database recording the location and frequency of occurrence of defective pixels is created and stored in memory to allow the system to learn and adapt its operation over time. The trends from the statistical database are stored so that truly anomalous pixels can be distinguished over time from false detections of true anomalies in the target image, lighting, or other anomalies induced by the environment. The operational logic of the statistical database and the details of the operation of the computer program are described below.

12 illustrates a simplified flow chart describing the operation of the software program implemented in a system for detecting and correcting defective pixels in accordance with an embodiment of the present invention. The first step in detecting and correcting defective pixels involves acquiring a portion of a frame of raw image data from an image sensor array, step 1210. The raw image data may be data corresponding to a live scene being digitized, or it may be data corresponding to a calibration or "black" background image. The "black" background image may be obtained by reducing the integration time of the sensor array or by reducing the gain of the image signal. The raw data from the "black" image may be used to detect overactive photosites. The raw data corresponding to the "black" image must also be black, and if any pixel is not

·' -&igr; » · ■··· * * * &iacgr; · * *
0 * ·
»»&diams;» · *

then it corresponds to an overactive photoelectric part. Using the "black" image can improve the detection of bad pixels by removing any brightness deviations that come from the scene itself.

Although data from an entire frame may be processed at once for faulty pixel detection and correction, the algorithm begins operation as soon as three lines of data from the image sensor have arrived at the host computer. Three lines of data from the image sensor array allow data for one pixel and all of its surrounding neighbors to be processed. Moreover, when the sensor array is used to capture video images, video subsampling is used so that not every frame of video captured by the image sensor array is required for the faulty pixel detection operation. In a preferred embodiment, fault detection is performed at predetermined frame intervals as described above and correction is applied to all video frames. Judicious use of video subsampling enables the method to be very fast and efficient.

In an alternative embodiment, no video subsampling is used, so that the detection of bad pixels is performed on each video frame. The use of video subsampling is a function of the speed of the intelligent host processor.

0 If a processor is fast enough to allow detection of anomalous pixels in every frame, then video subsampling is not used. On the other hand, if the processor is not fast enough to allow video processing at a desired frame rate, then video subsampling is used to speed up data transfer.

&bull;&phgr; · » φ · ·· φ φ φ φ φ φ _# φ φ · ·

ration at this desired frame rate. Without video subsampling, correction of anomalous pixels is immediate, so that errors are corrected exactly in the frame in which they are detected. With video subsampling, correction of anomalous pixels is delayed until a frame has been sampled to detect anomalous pixels. Therefore, the choice of using video subsampling and the rate of subsampling are a function of processor speed and a trade-off between processor performance and delay before correction.

After data acquisition, for each of the captured pixels, the local pixel brightness value and also the average brightness value of all of its immediately neighboring pixels are calculated and stored, step 1212. Next, a deviation threshold is set, step 1214. The deviation threshold sets the acceptable level of variance between the brightness value of a pixel and the average brightness value of all of its immediately neighboring pixels. Next, for each captured pixel, a local brightness deviation is calculated, step 1216. The local brightness deviation is the absolute value of the difference between the brightness value of a pixel and the average brightness value of all of its immediately neighboring pixels.

Next, for each pixel whose data was acquired, its local brightness deviation is compared to the deviation threshold, step 1218. Any pixel whose local brightness deviation exceeds the threshold deviation value is then marked as a defective pixel. The physical location and frequency of occurrence of each defective pixel is then recorded in a statistical database, step 1220. The statistical database is then queried to determine whether the data value of the defective pixel should be corrected, step 1222. The

By storing the location and frequency of the defective pixels, the statistical database develops trends over time that confirm which of the defective pixels warrants correction. The logic of the trends from the statistical database initially justifies correction of all flagged defective pixels as a default, and over time justifies pixel correction only when a particular pixel has a frequency of occurrence of at least two out of the last four samples.

The defective pixels that have passed through the statistical database filter are next corrected, step 1224. To correct a defective pixel, the raw defective brightness data for a defective pixel is replaced by the local average brightness value of that pixel, which is the average brightness value of all of its immediately neighboring pixels. Next, the corrected data from the defective pixels, as well as data from non-defective pixels, are prepared for subsequent processing, step 1226. Subsequent processing may include compression, color processing, and encoding into data formats suitable for display. Detection and correction of defective pixels is performed on the raw data from the image sensor array, since it is preferable to correct the data before any subsequent processing has taken place, since this processing itself may introduce image defects that are difficult to distinguish from image defects produced as a result of defective photosites.

The software algorithm is intentionally kept very simple so that the processor load and/or the video frame rate is minimally affected. Firstly, the software algorithm is kept simple because it only performs three functions, namely detection, correction and statistical functions. The statistical

stikroutine is kept simple, since only position information and the frequency of occurrence of anomalous pixels are tracked. Second, the software algorithm is kept simple so that there is minimal impact on the rate at which data is transferred to the host computer, so that while one frame is being scanned for faulty pixels, subsequent frames are not held up. The maximum impact of the software algorithm is, in the worst case, a reduction in the video data transfer rate from 10 frames per second (fps) to 9 fps. Third, the software algorithm is kept simple so that the load on the host computer processor is not increased by more than 1% when the algorithm is running. The anomalous pixels are detected in one frame, and corrections are later initiated on subsequent frames as they are read from the image sensor.

Thus, when the system is operating, as raw image data is received from the image sensor and sent for processing on a host computer, frame by frame is captured for detection and correction of defective pixels as described above. Once a defective pixel has been identified and its correction justified by the statistical database, this correction continues for all subsequent frame by frame until the next query to the statistical database is made. If at this time the initially identified defective pixel is still determined to be defective, then corrections continue as described above. On the other hand, if the statistical database does not justify correction of defective pixels, then these pixels will no longer be corrected until the next query to the statistical database is made. The dynamic nature of this system also allows corrections to be made to data from photosites that have been

may become faulty over time due to environmental changes after manufacturing.

The statistical analysis segment of the error detection and correction algorithm is an optional one. It aims to increase the efficiency of pixel corrections to correct anomalies not caused by defective photosites, and therefore saves processing time and load. However, the efficiency gains must be weighed against the burden imposed by the statistical analysis portion itself. In an alternative embodiment that does not use the statistical analysis portion, all pixels that are flagged as defective are corrected. As with the choice of using or not using video subsampling, the decision to use the statistical analysis portion of the error detection and correction algorithm depends on a trade-off between efficiency and processor performance. If the processor is fast enough, then efficiency concerns are not as important. On the other hand, if the processor is not fast enough, then pixel correction efficiency becomes important enough to justify implementing the statistical analysis portion of the error detection and correction algorithm.

As will be understood by those skilled in the art, the present invention may be embodied in other specific forms without departing from its essential characteristics. For example, the rate of video subsampling could be changed or not performed at all. Alternatively, the logic of the random statistical database could be changed from one for correcting defective pixels by default to one in which defective pixels are corrected only when justified by the trends from the statistical database.

■ ■ ' .■ ;■ . .-■.'-.

V. NO FRAME BUFFER MEMORY

Eliminating processing in the camera allows for elimination of the frame buffer since digital pixel data does not need to be stored for such processing ^. Another potential problem, however, is that the output of data from the sensor must be kept dependent on the availability of the bus. This can require a very large buffer. In one embodiment of the camera, only a small buffer is used in the bus interface. A small buffer is achievable by controlling the timing of when the sensor is read according to when the host bus is available and only reading an amount of data that can be buffered until the next bus availability.

Fig. 13 is a block diagram of a video camera according to the invention. The system includes a lens 1310 and a sensor array, such as a CMOS sensor array 1312, and is connected to a USB 1320. ■

The digitized signals from the CMOS sensor chip, rather than being stored in a frame buffer as in the prior art, are provided directly to a digital processing circuit 1348. They are first provided to a video digital signal processor 1350 which performs compression and optional scaling functions for minimized data transfer such as cropping, scaling and digital filtering. Once processed, the digital data is provided to a bus interface 1354.

The bus interface 1354 includes a bus control unit buffer 1356 and a bus control unit 1358. The buffer 1356 5 stores at least a single line of data from a

CMOS sensor line. Preferably, the bus controller buffer 1356 is capable of storing two USB frames at the maximum possible rate, or 2 kBytes. Depending on the frame rate, compression rate, etc., this can typically vary by up to 10 lines, or even 15-20 lines if decimation is performed.

The bus controller 1358 provides a control signal on line 1360 to the clock and control generator 1326. The clock generator 1326 provides clock signals on line 1364 to the GMOS sensor array 1322. The clock signals 1364 include the row and column transfer pulses. The column transfer pulses are provided as in the prior art, periodically loading the loaded values from the CMOS sensor array. However, the row transfer pulses are varied to coordinate the reading of the data from the CMOS sensor array with the processing by the following circuitry and the transfer of the data to the USB.

In one embodiment, digital processing circuitry 1348 is integrated into the same semiconductor chip substrate as CMOS sensor array 1312, clock generator 1326, ADC 1328, and row and column logic and buffers. Elimination of the frame buffer enables this single chip.

This makes it possible to construct a more compact, more cost-effective video camera.

Figure 14 illustrates the timing of the line transfer pulses provided on line 1364. Rather than a continuous stream of pulses, the bits are clocked out in groups as required by the processing circuitry, as shown. A first group of three lines 1466 is output, and then there is a delay while these pixels are processed and transferred to the bus. Then a next group of two lines 1468 can be output.

There could then be a delay depending on the availability in the line buffer and the timing of the transfer of data on the USB. A single line 1469 is shown being transferred next, followed by a subsequent group of four lines transferred by a number of pulses 1470. After an entire image has been transferred, a vertical transfer pulse 1472 is delivered. The example of Figure 14 is provided simply for illustration. Note that since the line transfer pulses are delivered between the same column pulses to allow for the gaps shown, the pulses are delivered much closer together. Thus, bursts of small groups of pulses are delivered to send pixel data quickly, as fast as the circuitry can process it. In one embodiment, an entire image can be clocked out in a series of closely spaced pulses, allowing processing to be completed before the next column transfer pulse. If processing has not finished at the time of the next column transfer pulse, there may be a delay corresponding to the timing of the processing and the availability of the USB. Thus, the row pulses can be delivered all in sequence, but at a faster rate than in the prior art, and the timing of this grouping of pulses after the column pulse can be changed to be just after or just before the next column pulse to accommodate the processing and bus timings.

0 VI. NO COMPRESSION

In one embodiment of the invention, the compression block 26 and the decompression block 38 of Fig.

2. This can be done, for example, if a new USB with higher bandwidth is developed

&bull;i&mdash;...·

However, earlier embodiments may still be desirable as sensors with increased sensitivity are developed, allowing higher resolution video image data to be transmitted, taking advantage of the additional bandwidth provided. One embodiment, however, takes advantage of the additional bandwidth by eliminating the need for compression, thus further simplifying the video camera and reducing its cost.

The same major functions shown in Figure 2 would be performed in the host computer, except for decompression. The camera would still include the correction register 34 in one embodiment, allowing the inexpensive lens 10 to be used.

VII. LOSSY COMPRESSION

In an alternative embodiment, a lossy compression method may be used. Lossy compression means that the recovered image may lose some resolution. A disadvantage of lossy compression is that any vignetting or pixel correction performed in the host computer would be degraded. Thus, in this alternative embodiment, the vignetting correction and pixel correction are performed in the video camera itself. This allows a lossy compression block to be used for block 26 of Figure 2. The color processing and scaling operations are still performed in the host computer, thus providing a simpler camera than the prior art of Figure 1. ■ . ' ■ '

&Ggr;:!"' O: &Pgr; j Xi

As will be understood by those skilled in the art, the present invention may be embodied in other specific forms without departing from the essential characteristics thereof. For example, in one embodiment, the correction register may correct for characteristics of a camera that may vary from camera to camera during manufacture, other than characteristics of the lens. Rather than a physical shared bus, the data may be transmitted wirelessly from the camera to the host computer or to a receiver connected to the host computer. The host computer itself may be a personal computer, an intelligent Internet device, or any other device or component having some type of processor or processing circuitry. Accordingly, the foregoing description is intended to be illustrative, but not limitative, of the scope of the invention, which is set forth in the following claims.

Claims (14)

1. Video camera system, which comprises: a) a video camera with
an image sensor, and
a processing element for performing data compression; b) an interface coupled to the video camera; and c) a processing unit for receiving compressed data from the interface, the processing unit being configured to perform the following
a decompression of the compressed data, wherein at least part of the decompression operations are performed in parallel,
a correction of anomalous pixels, and
a color processing;
so that the circuit for correcting abnormal pixels and for color processing in the video camera is not required, and the correction of the abnormal pixels is carried out before the color processing. 2. The video camera of claim 1, wherein the video camera includes a lens and the processing unit is further configured to perform vignetting correction for the lens. 3. A video camera according to claim 1, further comprising a memory element in the video camera for storing a constant value corresponding to an amount of vignetting of the lens. 4. A video camera according to claim 1, wherein the correction of the anomalous pixels is arranged to minimize their impact on the video frame rate by including video sub-sampling to detect faulty pixels and a statistical recording of only the pixel position and data regarding the frequency of the faulty pixels detected. 5. The system of claim 1, wherein the processing unit comprises a processor having instructions for processing a plurality of pixels in a register in parallel, the processor programmed to decompress a data stream with variable size compression codes, at least a portion of the decompression operations being performed in parallel on a plurality of fields in the register. 6. The system of claim 5, wherein the data stream is compressed using Huffman coding, and the operations include:
Duplicating a group of bits from the data stream to provide duplicates in multiple positions in a first register; and
performing an operation in parallel between values in a second register and the duplicates, using a different value for each duplicate. 7. Video camera system comprising: a) a video camera with
an image sensor, and
an analog-to-digital converter coupled to the image sensor; (b) an interface coupled to the video camera, the interface being a shared interface capable of simultaneous use by other peripheral devices; and. c) a processing unit for receiving digital data from the interface, the processing unit being configured to perform a correction of anomalous pixels, and
a colour processing;
so that the circuit for correcting abnormal pixels and for color processing in the video camera is not required, and the correction of the abnormal pixels is carried out before the color processing. 8. The system of claim 7, wherein the video camera further comprises a processing device for compressing digital data from the analog-to-digital converter. 9. Apparatus for decoding a Huffman-compressed data stream in a processor with instructions for parallel processing of multiple pixels in a register, comprising:
means for duplicating a group of bits from the data stream to provide duplicates in multiple positions in a first register; and
means for performing an operation between values in a second register and the duplicates in parallel, using a different value for each duplicate. 10. The apparatus of claim 9, further comprising:
means for using a result of the operation in an indexing operation to index a table of Huffman decoded values. 11. Video camera with:
an image sensor;
an analog-to-digital converter coupled to the image sensor;
a memory element for holding a value corresponding to a correction factor for an aspect of the camera, the value being transferable to a remote host computer; and
an interface coupled to the analog-to-digital converter and the memory element for establishing a connection to the remote host computer. 12. The camera of claim 11, further including a lens, and wherein the value is a lens vignetting value. 13. An apparatus for detecting and correcting defective pixels in raw data obtained from an image sensor used to obtain a digitized image, the raw data containing normal pixels and defective pixels, the apparatus comprising: a) means for receiving a raw data signal for each pixel in the image; b) means for calculating a brightness value for each pixel received from the image sensor; c) means for calculating a local brightness value for each pixel received from the image sensor; d) means for calculating a local brightness deviation of the brightness value from the local brightness value for each pixel received from the image sensor; (e) means for setting a deviation threshold; (f) means for comparing, for each pixel received from the image sensor, its local brightness deviation with the deviation threshold and for determining pixels with local brightness deviations greater than the deviation threshold as defective pixels; (g) means for recording the location of defective pixels in a statistical database; (h) means for recording the frequency of occurrence of the defective pixels in the statistical database; and (i) means for correcting the brightness value of the defective pixels, provided that the correction is justified by trends from the statistical database. 14. Video camera comprising:
a device for reading image data from an image sensor array;
means for processing the image data in a video digital signal processor (DSP), the processing comprising performing image compression;
a device for supplying processed image data to a bus; and
means for supplying a clock signal to the image sensor array to transfer image data from the image sensor array over the bus at a rate corresponding to a data transfer rate such that a frame buffer for storing an entire frame of the image is not required.