Image processing method and device

• US 6,259,826 B1
• Filed: 05/28/1998
• Issued: 07/10/2001
• Est. Priority Date: 06/12/1997
• Status: Expired due to Term

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: Hewlett-Packard Company (HP Inc.)
• Inventors: Pollard, Stephen Bernard, Kahn, Richard Oliver
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): Wu, Jingge
• Application Number:
  US09/086,304
• Time in Patent Office: 1,139 Days
• Field of Search: 382/284, 382/294, 382/450, 382/313, 382/240, 358/473, 358/474
• US Class Current: 382/284
• CPC Class Codes: H04N 1/047 Detection, control or error compensation of scanning velocity or position H04N1/0402 and H04N1/17 take precedence
• CPC Class Codes: H04N 1/107 with manual scanning
• CPC Class Codes: H04N 2201/02425 Self-adjusting arrangements, e.g. compensating for temperature fluctuations
• CPC Class Codes: H04N 2201/02439 Positioning method
• CPC Class Codes: H04N 2201/03162 Original guide plate
• CPC Class Codes: H04N 2201/0471 using dedicated detectors
• CPC Class Codes: H04N 2201/04729 in the main-scan direction
• CPC Class Codes: H04N 2201/04731 in the sub-scan direction
• CPC Class Codes: H04N 2201/04734 Detecting at frequent intervals, e.g. once per line for sub-scan control
• CPC Class Codes: H04N 2201/04737 by detecting the scanned medium directly, e.g. a leading edge
• CPC Class Codes: H04N 2201/04787 by changing or controlling the addresses or values of pixels, e.g. in an array, in a memory, by interpolation
• CPC Class Codes: H04N 2201/04789 in the main-scan direction
• CPC Class Codes: H04N 2201/04791 in the sub-scan direction
• CPC Class Codes: H04N 2201/04794 Varying the control or compensation during the scan, e.g. using continuous feedback or from line to line

Abstract

A method of reconstructing an image captured as a stream of image data, for example as input received from a linear sensor in unconstrained scanning, comprises reconstructing the image in the form of a plurality of tiles. Each tile comprises a pixel grid of predetermined dimension representing a specific spatial region of the image. The tiles tessellate a rectilinear image space. Tiles can be created when required and compressed when no longer active, thus minimizing memory requirements. Devices utilizing this method are provided. The method is especially appropriate for use in an unconstrained hand scanner, but can also be applied to panoramic capture with a digital camera.

Claims

1. A method of reconstructing an image from a plurality of discretely captured image elements, each image element comprising image data captured in an image sensor and position data indicating a position of that image element with respect to others of the image elements, the method comprising:

defining a reconstruction space having a plurality of tile locations, each tile location comprising a pixel grid of predetermined dimension representing a specific spatial region of the image in the reconstruction space;

mapping each image element onto one or more tiles in appropriate tile locations in the reconstruction space to provide a reconstructed image in the form of a plurality of tiles.

2. A method as claimed in claim 1, wherein the position data is derived from navigation means which provides the position data for an image element on capture of that image element by the image sensor.

3. A method as claimed in claim 1, wherein the position data is derived from a preceding step of determining from features of the image elements a relative position for each image element with respect to others of the image elements.

4. A method as claimed in claim 1, wherein said tiles are contiguous and do not overlap.

5. A method as claimed in claim 4, wherein said tiles are adapted to tessellate in two dimensions.

6. A method as claimed in claim 2, wherein the image is captured in the form of a stream of sensor readings, each sensor reading comprising image data and corresponding position data.

7. A method as claimed in claim 6, comprising the repeated steps of:

managing tiles by determining from the position data if tiles exist at tile locations corresponding to the spatial positions of one or more input sensor readings in the image, and by creating one or more new tiles as necessary so that tiles corresponding to the spatial positions of the one or more sensor readings exist; and

writing to tiles by assigning pixel values to the pixels of tiles corresponding to the spatial positions of the one or more input sensor readings on the basis of the image data and the position data.

8. A method as claimed in claim 7, wherein said one or more sensor readings comprise a group of sensor readings, and wherein said steps of managing tiles and writing to tiles are repeated for successive groups of sensor readings.

9. A method as claimed in claim 8, wherein the step of managing tiles takes place for N successive sensor readings before the step of writing to tiles, and wherein the step of writing to tiles takes place for groups of M successive sensor readings, wherein N and M are positive integers greater than 1, (N−

1)/(M−

1) is a positive integer, and where the step of writing to tiles takes place (N−

1)/(M−

1) before a further tile managing step.

10. A method as claimed in claim 1, comprising creating a tile index indexing each tile created with its specific spatial region of the image.

11. A method as claimed in claim 10, wherein said tile index is provided as a tree, with each node of the tree pointing to a plurality of locations at a multiple of the spatial resolution of that node.

12. A method as claimed in claim 11, wherein each node points to four locations at twice the spatial resolution of that node.

13. A method as claimed in claim 7, wherein an active tile buffer is provided for storage of tiles in the tile managing step for tiles corresponding to the spatial positions of the one or more sensor readings operated on in the tile managing step.

14. A method as claimed in claim 7, wherein in the tile managing step some or all existing tiles not corresponding to the spatial positions of the one or more sensor readings are compressed.

15. A method as claimed in claim 14, wherein said one or more sensor readings comprise a group of sensor readings, and wherein said steps of managing tiles and writing to tiles are repeated for successive groups of sensor readings, and wherein in the tile managing step the tiles corresponding to the spatial positions of the previous group operated on are compared with the tiles corresponding to the spatial positions of the present group, and wherein newly required tiles are created and wherein tiles of the previous group not present in the present group are compressed.

16. A method as claimed in claim 14, wherein the tiles which are compressed are written to a compressed tile storage area.

17. A method as claimed in claim 13, wherein an active tile index is provided for reference to tiles in the tile writing step.

18. A method as claimed in claim 2, wherein the navigation means comprises one or more sensors for detecting inherent structure-related properties of a medium carrying the image captured.

19. A method as claimed in claim 1, wherein the sensor is comprised in a scanning device.

20. A method as claimed in claim 1, wherein the method is adapted for use with a sensor capable of unconstrained movement across the image captured.

21. A scanning system comprising:

an image capture device for discrete capture of a plurality of image elements, the image capture device comprising an image sensor wherein each image element comprises image data captured in the image sensor and position data indicating a position of that image element with respect to others of the image elements; and

a signal processor adapted to reconstructing the image from the plurality of image elements, wherein the signal processor defines a reconstruction space in the form of a plurality of tiles, each tile comprising a pixel grid of predetermined dimension representing a specific spatial region of the image, and wherein the signal processor is maps each image element onto one or more tiles in appropriate tile locations in the reconstruction space to provide a reconstructed image in the form of a plurality of tiles.

22. A scanning system as claimed in claim 21, wherein the image capture device further comprises a navigation means which provides the position data for an image element on capture of that image element by the image sensor.

23. A scanning system as claimed in claim 21, further comprising a means for determining from features of the image elements a relative position for each image element with respect to others of the image elements.

24. A scanning system as claimed in claim 22, wherein the image capture device is adapted to capture a stream of sensor readings, each sensor reading comprising image data and corresponding position data.

25. A scanning system as claimed in claim 22, wherein the navigation means comprises one or more sensors for detecting inherent structure related properties of a medium carrying the image captured.

26. A scanning system as claimed in claim 21, wherein the image sensor is capable of unconstrained movement across the image captured.

27. A scanning system as claimed in claim 21, wherein the image capture device and the signal processor are both comprised in a scanning device.

28. A scanning system as claimed in claim 21, wherein the image capture device is a scanning device and the signal processor is comprised within a computer system, wherein the scanning system further comprises a communications interface between the scanning device and the computer system for provision of the plurality of image elements from the scanning device to the computer system.