Prioritized searching methods for finding a coded symbol in a digitized image

• US 5,764,798 A
• Filed: 03/18/1996
• Issued: 06/09/1998
• Est. Priority Date: 03/18/1996
• Status: Expired due to Term

• Current Assignee: Intermec IP Corporation (Honeywell International Inc.)
• Original Assignee: Intermec Corporation (Honeywell International Inc.)
• Inventors: Liu, Lingnan
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Tadayon, Bijan
• Application Number:
  US08/617,026
• Time in Patent Office: 813 Days
• Field of Search: 382/101, 382/102, 382/113, 382/135, 382/137, 382/138, 382/139, 382/140, 382/181, 382/183, 382/184, 382/190, 382/191, 382/192, 382/193, 382/195, 382/199, 382/203, 382/318, 382/319, 382/173, 382/286, 382/186, 382/187, 382/194, 382/201, 382/202, 382/204, 382/205, 382/209, 382/224, 382/312, 382/321, 235/462, 377/10
• US Class Current: 382/190
• CPC Class Codes: G06V 10/25 Determination of region of interest [ROI] or a volume of interest [VOI]

Abstract

An electro-optical imaging system that utilizes an efficient search algorithm to find a coded symbol within a digitized image is provided. A digitized image of an area of an object having a coded symbol attached or printed thereon is created and stored in an image memory. A search algorithm is then activated to search for the coded symbol within the digitized image stored in the image memory. The search is limited to an area of the digitized image that is defined by boundary parameters. The search begins with the scan of an initial horizontal line of pixels that passes through the center of the search area, and an initial vertical line of pixels that also passes through the center of the search area. Subsequent horizontal and vertical lines of pixels are then scanned, one each subsequent line is located an integer multiple number of step sizes from one of the initial lines. Once the above described search pattern expands beyond the boundaries of the search area, the step sizes are reduced, and the search is continued.

Claims

1. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier; and

(e) determining whether to end said search for said predetermined symbol.

2. The method of claim 1 further comprising the step of:

repeating said steps (b)-(e) until it is determined at said determining step to end said search for said predetermined symbol.

3. The method of claim 2, wherein said determining step further comprises the step of:

determining to end said search for said predetermined symbol if one of said first initial line and said first subsequent line crosses at least a portion of said predetermined symbol.

4. The method of claim 2, wherein said determining step further comprises the step of:

determining to end said search for said predetermined symbol if said first subsequent line of said digitized image does not pass through at least a portion of said predefined search area.

6. The method of claim 1 further comprising the steps of:

(f) changing said location of said first scan point again such that a first additional subsequent line of said digitized image that is parallel to said first initial line and passes through said again changed first scan point is located a distance equal to a product of said first multiplier and said first step size away from said first initial line in a direction that is opposite to said first scan point change direction; and

(g) scanning said first additional subsequent line of said digitized image.

7. The method of claim 6 further comprising the step of:

repeating said steps (b)-(g) until it is determined at said step (e) to end said search for said predetermined symbol.

8. The method of claim 6, wherein said step (c) further comprises the step of scanning said first subsequent line in a first scan direction;

and said step (g) further comprises the step of scanning said first additional subsequent line in a direction that is opposite to said first scan direction.

13. The method of claim 1, wherein said predetermined symbol is a coded symbol.

14. An article of manufacture comprising a machine readable media embodying instructions for instructing said machine to perform the method of claim 1.

15. An article of manufacture comprising a machine readable media embodying instructions for instructing said machine to perform the method of claim 6.

5. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) determining whether to end said search for said predetermined symbol, said determining step comprising the steps of reducing said first step size and resetting said first multiplier if said first subsequent line does not pass through at least a portion of said predefined search area, and determining to end said search for said predetermined symbol if said first step size is less than a minimum first step size; and

(f) repeating said steps (b)-(e) until it is determined at said determining step to end said search for said predetermined symbol.

9. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) scanning a second initial line of said digitized image located within said predefined search area, said second initial line passing through a second scan point located along a second boundary of said predefined search area;

(f) changing a location of said second scan point such that a second subsequent line of said digitized image that is parallel to said second initial line and passes through said changed second scan point is located a distance equal to a product of a second multiplier and a second step size away from said second initial line in a second scan point change direction;

(g) scanning said second subsequent line of said digitized image;

(h) increasing a size of said second multiplier; and

(i) determining whether to end said search for said predetermined symbol.

10. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) determining whether to end said search for said predetermined symbol;

(f) scanning a second initial line of said digitized image located within said predefined search area, said second initial line passing through a second scan point located along a second boundary of said predefined search area;

(g) changing a location of said second scan point such that a second subsequent line of said digitized image that is parallel to said second initial line and passes through said changed second scan point is located a distance equal to a product of a second multiplier and a second step size away from said second initial line in a second scan point change direction;

(h) scanning said second subsequent line of said digitized image;

(i) increasing a size of said second multiplier; and

(j) repeating said steps (b)-(e) and (g)-(i) until it is determined at said step (e) to end said search for said predetermined symbol.

11. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) changing said location of said first scan point again such that a first additional subsequent line of said digitized image that is parallel to said first initial line and passes through said again changed first scan point is located a distance equal to a product of said first multiplier and said first step size away from said first initial line in a direction that is opposite to said first scan point change direction;

(f) scanning said first additional subsequent line of said digitized image;

(g) scanning a second initial line of said digitized image located within said predefined search area, said second initial line passing through a second scan point located along a second boundary of said predefined search area;

(h) changing said location of said second scan point such that a second subsequent line of said digitized image that is parallel to said second initial line and passes through said changed second scan point is located a distance equal to a product of a second multiplier and a second step size away from said second initial line in a second scan point change direction;

(i) scanning said second subsequent line of said digitized image;

(j) changing said location of said second scan point again such that a second additional subsequent line of said digitized image that is parallel to said second initial line and passes through said again changed second scan point is located a distance equal to a product of said second multiplier and said second step size away from said initial line in a direction that is opposite to said second scan point change direction;

(k) scanning said second additional subsequent line of said digitized image;

(l) increasing a size of said second multiplier; and

(m) determining whether to end said search for said predetermined symbol.

12. A method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located alone a first boundary of said Redefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) determining whether to end said search for said predetermined symbol;

(f) changing said location of said first scan point again such that a first additional subsequent line of said digitized image that is parallel to said first initial line and passes through said again changed first scan point is located a distance equal to a product of said first multiplier and said first step size away from said first initial line in a direction that is opposite to said first scan point change direction;

(g) scanning said first additional subsequent line of said digitized image;

(h) scanning a second initial line of said digitized image located within said predefined search area, said second initial line passing through a second scan point located along a second boundary of said predefined search area;

(i) changing said location of said second scan point such that a second subsequent line of said digitized image that is parallel to said second initial line and passes through said changed second scan point is located a distance equal to a product of a second multiplier and a second step size away from said second initial line in a second scan point change direction;

(j) scanning said second subsequent line of said digitized image;

(k) changing said location of said second scan point again such that a second additional subsequent line of said digitized image that is parallel to said second initial line and passes through said again changed second scan point is located a distance equal to a product of said second multiplier and said second step size away from said initial line in a direction that is opposite to said second scan point change direction;

(l) scanning said second additional subsequent line of said digitized image;

(m) increasing a size of said second multiplier; and

(n) repeating said steps (b)-(g) and (i)-(m) until it is determined at said step (e) to end said search for said predetermined symbol.

16. An article of manufacture comprising a machine readable media embodying instructions for instructing said machine to perform a method of searching for a predetermined symbol within a predefined search area of a digitized image comprising the steps of:

(a) scanning a first initial line of said digitized image located within said predefined search area, said first initial line passing through a first scan point located along a first boundary of said predefined search area;

(b) changing a location of said first scan point such that a first subsequent line of said digitized image that is parallel to said first initial line and passes through said changed first scan point is located a distance equal to a product of a first multiplier and a first step size away from said first initial line in a first scan point change direction;

(c) scanning said first subsequent line of said digitized image;

(d) increasing a size of said first multiplier;

(e) determining whether to end said search for said predetermined symbol;

(f) changing said location of said first scan point again such that a first additional subsequent line of said digitized image that is parallel to said first initial line and passes through said again changed first scan point is located a distance equal to a product of said first multiplier and said first step size away from said first initial line in a direction that is opposite to said first scan point change direction;

(g) scanning said first additional subsequent line of said digitized image;

(h) scanning a second initial line of said digitized image located within said predefined search area, said second initial line passing through a second scan point located along a second boundary of said predefined search area;

(i) changing said location of said second scan point such that a second subsequent line of said digitized image that is parallel to said second initial line and passes through said changed second scan point is located a distance equal to a product of a second multiplier and a second step size away from said second initial line in a second scan point change direction;

(j) scanning said second subsequent line of said digitized image;

(k) changing said location of said second scan point again such that a second additional subsequent line of said digitized image that is parallel to said second initial line and passes through said again changed second scan point is located a distance equal to a product of said second multiplier and said second step size away from said initial line in a direction that is opposite to said second scan point change direction;

(l) scanning said second additional subsequent line of said digitized image; and

(m) increasing a size of said second multiplier.

17. An apparatus for searching for a predetermined symbol within a predefined search area of a digitized image comprising:

a memory device in which said digitized image is stored;

means for setting a location of a first scan point equal to a first reference point located along a first boundary of said predefined search area;

first changing means for changing said location of said first scan point such that a line of said digitized image that is perpendicular to said first boundary and passes through said first scan point is located, in a first scan point change direction, a distance equal to a product of a first multiplier and a first step size away from a line that is perpendicular to said first boundary and passes through said first reference point;

means for scanning a line of said digitized image that is located within said predefined search area and passes through said first scan point;

means for increasing a size of said first multiplier; and

means for determining whether to end said search for said predetermined symbol.

18. The apparatus of claim 17 further comprising:

second changing means for changing said location of said first scan point such that a line that is perpendicular to said first boundary and passes through said first scan point is located, in a direction opposite to said first scan point change direction, a distance equal to said product of said first multiplier and said first step size away from said line that is perpendicular to said first boundary and passes through said first reference point.

19. The apparatus of claim 18, wherein said scanning means further includes:

means for scanning said line of said digitized image in a direction indicated by a scan direction indicator; and

means for changing said direction indicated by said scan direction indictor.

22. The apparatus of claim 17, wherein said determining means further comprises:

means for determining to end said search for said predetermined symbol if said line that is perpendicular to said first boundary and passes through said first scan point does not pass through at least a portion of said predefined search area.

23. The apparatus of claim 17, wherein said determining means further comprises:

means for determining to end said search for said predetermined symbol if said line of said digitized image scanned by said scanning means crosses at least a portion of said predetermined symbol.

24. The apparatus of claim 17, wherein said determining means further comprises:

means for reducing said first step size and resetting said first multiplier if said line that is perpendicular to said first boundary and passes through said first scan point does not pass through said predefined search area; and

means for determining to end said search for said predetermined symbol if said first step size is less than a minimum first step size.

25. The apparatus of claim 17, wherein said predetermined symbol is a coded symbol.

20. An apparatus for searching for a predetermined symbol within a predefined search area of a digitized image comprising:

a memory device in which said digitized image is stored;

means for setting a location of a first scan point equal to a first reference point located along a first boundary of said predefined search area;

first changing means for changing said location of said first scan point such that a line of said digitized image that is perpendicular to said first boundary and passes through said first scan point is located, in a first scan point change direction, a distance equal to a product of a first multiplier and a first step size away from a line that is perpendicular to said first boundary and passes through said first reference point;

means for scanning a line of said digitized image that is located within said predefined search area and passes through said first scan point;

means for increasing a size of said first multiplier;

means for setting a location of a second scan point equal to a second reference point located along a second boundary of said predefined search area;

second changing means for changing said location of said second scan point such that a line that is perpendicular to said second boundary and passes through said second scan point is located, in a second scan point change direction, a distance equal to a product of a second multiplier and a second step size away from a line that is perpendicular to said second boundary and passes through said second reference point;

means for scanning a line of said digitized image that is located within said predefined search area, is perpendicular to said second boundary, and passes through said second scan point;

means for increasing a size of said second multiplier; and

means for determining whether to end said search for said predetermined symbol.

21. An apparatus for searching for a predetermined symbol within a predefined search area of a digitized image comprising:

a memory device in which said digitized image is stored;

means for setting a location of a first scan point equal to a first reference point located along a first boundary of said predefined search area;

first changing means for changing said location of said first scan point such that a line of said digitized image that is perpendicular to said first boundary and passes through said first scan point is located, in a first scan point change direction, a distance equal to a product of a first multiplier and a first step size away from a line that is perpendicular to said first boundary and passes through said first reference point;

means for scanning a line of said digitized image that is located within said predefined search area and passes through said first scan point;

means for increasing a size of said first multiplier;

means for setting a location of a second scan point equal to a second reference point located along a second boundary of said predefined search area;

second chancing means for changing said location of said second scan point such that a line that is perpendicular to said second boundary and passes through said second scan point is located, in a second scan point change direction, a distance equal to a product of a second multiplier and a second step size away from a line that is perpendicular to said second boundary and passes through said second reference point;

means for scanning a line of said digitized image that is located within said predefined search area, is perpendicular to said second boundary, and passes through said second scan point;

means for increasing a size of said second multiplier;

means for determining whether to end said search for said predetermined symbol;

third changing means for changing said location of said first scan point such that a line that is perpendicular to said first boundary and passes through said first scan point is located, in a direction opposite to said first scan point change direction, a distance equal to said product of said first multiplier and said first step size away from said line that is perpendicular to said first boundary and passes through said first reference point; and

fourth changing means for further changing said location of said second scan point such that a line that is perpendicular to said second boundary and passes through said second scan point is located, in a direction opposite to said second scan point change direction, a distance equal to said product of said second multiplier and said second step size away from said line that is perpendicular to said second boundary and passes through said second reference point.

26. A method of searching for a plurality of symbols within a digitized image comprising the steps of:

(a) initializing a step size to a value greater than one, said value calculated to minimize the number of steps needed to locate said plurality of symbols;

(a) scanning an initial line of said digitized image;

(b) calculating a subsequent line of said digitized image, said subsequent line parallel to said initial line and located a distance equal to a product of said step size and a multiplier away from said initial line;

(c) scanning said subsequent line;

(d) increasing the value of said multiplier; and

(e) determining whether to end said search for said plurality of symbols.

27. The method of claim 26 wherein the calculating step further includes determining whether said subsequent line is outside of said digitized image, and if so, resetting said multiplier, reducing said step size and recalculating said subsequent line.

28. An apparatus for searching for a plurality of symbols within a digitized image comprising:

an image memory in which said digitized image is stored; and

a processor and a program memory storing instructions to be performed by said processor, said instructions including;

initializing a step size such that said plurality of symbols will be located with a minimal number of scans,

defining an initial line of said digitized image,

defining a scan line a distance equal to a product of a multiplier and a step size away from said initial line,

scanning said scan line,

increasing the size of said multiplier, and

determining whether to end said search for said plurality of symbols.

29. The apparatus of claim 28 wherein said instructions further include determining whether said subsequent line is outside of said digitized image, and if so, resetting said multiplier, reducing said step size and recalculating said subsequent line.