Method and system for locating and focusing on fiducial marks on specimen slides

Methods are disclosed for locating and focusing on a fiducial mark on a specimen slide. A plurality of pixels are identified as candidate pixels. A pixel is identified as a candidate pixel based on a number of empty pixels in an area defined by boundary lines extending from the pixel, and one or more dimensions, such as the perimeter, of the defined area. The candidate pixel enclosing the largest area is selected from the group or set of candidate pixels, and the coordinates of that pixel are considered to be the coordinates of the corner of the fiducial mark. The methods can be performed using different gray values that define dark or fiducial pixels and light or empty pixels. Differences between the results at different gray values can be used as focus scores for automatic focusing on the fiducial mark.

FIELD OF THE INVENTION

The invention relates to imaging and analysis of biological specimens, and more particularly, to locating and focusing on fiducial marks on specimen slides.

BACKGROUND

Medical professionals and cytotechnologists often prepare biological specimens on a specimen carrier, such as a slide, and review specimens to analyze whether a patient has or may have a particular medical condition or disease. For example, it is known to examine a cytological specimen in order to detect malignant or pre-malignant cells as part of a Papanicolaou (Pap) smear test and other cancer detection tests. To facilitate this review process, automated systems focus the technician's attention on the most pertinent cells or groups of cells, while discarding less relevant cells from further review. One known automated imaging system that has been effectively used in the past is the ThinPrep Imaging System, available from Cytyc Corporation, 250 Campus Drive, Marlborough, Mass. 01752.

FIG. 1generally illustrates one known biological screening system10that is configured for presenting a biological specimen12located on a microscope slide14(as shown inFIG. 2) to a technician, such as a cytotechnologist, who can then review objects of interest (OOIs) located in the biological specimen12. The OOIs are arranged in a number of fields of interest (FOIs) that cover portions of the slide14, so that the cytotechnologist's attention can be subsequently focused on OOIs within the FOIs, rather than slide regions that are not pertinent. The system10can be used for the presentation of cytological cervical or vaginal cellular material, such as that typically found on a Pap smear slide. In this case, the OOIs take the form of individual cells and cell clusters that are reviewed to check for the possible presence of an abnormal condition, such as malignancy or pre-malignancy.

The biological specimen12will typically be placed on the slide14as a thin cytological layer. A cover slip (not shown inFIG. 1) is preferably adhered to the specimen12to fix the specimen12in position on the slide14. The specimen12may be stained with any suitable stain, such as a Papanicolaou stain.

An imaging station18is configured to image the slide14, which is typically contained within a cassette (not shown inFIG. 1) along with other slides. During the imaging process, slides are removed from the respective cassettes, imaged, and returned to the cassettes in a serial fashion.

One known imaging station18includes a camera24, a microscope26, and a motorized stage28. The camera24captures magnified images of the slide14through the microscope26. The camera24may be any one of a variety of conventional cameras, such as cameras that can produce a digital output of sufficient resolution to allow processing of the captured images. A suitable resolution may be 640×480 pixels. Each pixel can be converted into an eight-bit value (0 to 255) depending on its optical transmittance. A value of “00000000” or “0” is the assigned value for least amount of light passing through the pixel, and a value of “11111111” or “255” is the assigned value for a greatest amount of light passing through the pixel. Thus, a “0” value indicates a dark value, e.g., a pixel of a fiducial mark, and a “255” value indicates a light value, e.g., an empty pixel.

The slide14is mounted on the motorized stage28, which scans the slide14relative to the viewing region of the microscope26, while the camera24captures images over various regions of the biological specimen12. The motorized stage28tracks the x−y coordinates of the images as they are captured by the camera24. Encoders (not shown) can be coupled to the respective motors of the motorized stage28in order to track the net distance traveled in the x- and y-directions during imaging.

Referring toFIG. 2, x−y coordinates tracked by the stage28are measured relative to fiducial marks16affixed to the slide14. A fiducial mark16may be a rectangular patch of paint; in this case, one corner of the mark may be considered to be the marks's location. These fiducial marks16are also used by the reviewing station22to ensure that the x−y coordinates of the slide14during the review process can be correlated to the x−y coordinates of the slide14obtained during the imaging process.

More particularly, each reviewing station20includes a microscope38and a motorized stage40. The slide14(after image processing) is mounted on the motorized stage40, which moves the slide14relative to the viewing region of the microscope38based on the routing plan and a transformation of the x−y coordinates of the FOIs obtained from memory36. These x−y coordinates, which were acquired relative to the x−y coordinate system of the imaging station18, are transformed into the x−y coordinate system of the reviewing station20using the fiducial marks16affixed to the slide14(shown inFIG. 1). In this manner, the x−y coordinates of the slide14during the reviewing process are correlated to the x−y coordinates of the slide14during the imaging process. The motorized stage40then moves according to the transformed x−y coordinates of the FOIs, as dictated by the routing plan.

While known fiducial marks and coordinate systems used during imaging and review processes have been used effectively in the past, they can be improved. In particular, it can be difficult to locate fiducial marks in the presence of air bubbles and to focus on fiducial marks in the presence of dust and debris, as shown with reference toFIGS. 3-8.

FIG. 3is a top view of a specimen slide14having three fiducial marks16. A cover slip50is placed over the specimen12.FIG. 4is a top view of the slide14shown inFIG. 3having dust or debris (generally dust52) on the cover slip50.FIG. 4also illustrates an air bubble54underneath the cover slip50.FIG. 5is a side view ofFIG. 4, which further illustrates dust52on top of the cover slip50and an air bubble54between the top of the slide14and the bottom of the cover slip50.

Persons skilled in the art will appreciate that the dimensions shown inFIGS. 2-5and other figures may not reflect actual dimensions and may not be to relative scale and are provided for purposes of illustration.

Referring toFIG. 6, when a cover slip50is placed on a slide, one or more air bubbles54may be trapped in the mounting medium60between the cover slip50and the slide14. The fiducial mark16may appear to be a different shape and its true outline may be difficult to locate when an air bubble54or cellular debris overlaps the fiducial mark16.

In addition, assuming a fiducial mark16is located, dust and debris52on top of the cover slip50may cause focusing errors. Automatic focusing on a specimen is generally done by focusing up and down until the objects in the image are in focus. Referring toFIG. 7, dust52or other debris (such as a fingerprint) on top of the cover slip50may cause an automatic focusing system or algorithm to focus on the dust52, thereby resulting in a false plane72, rather than locating the correct focal plane70corresponding to the sample12on the slide (which is coplanar with the fiducial marks16).

The dotted line80inFIG. 8shows focus or sharpness values for a set of images taken of a single microscope field at different focal heights. The field contains a fiducial mark16and also contains dust52. The “x” axis represents a vertical distance (in microns) from the first or true focus plane70. The second, false focus plane72is about 110 microns higher than the first focus plane70; the false plane corresponds to the dust52, which rests on top of the cover slip50, which is about 100 microns thick. The “y” axis represents the logarithm of the Brenner score of the image. The Brenner score is a known method of quantifying image sharpness, and is the sum of the squares of the differences between the gray value of each pixel and its neighbor two pixels to the left, where differences less than a certain threshold are excluded from the sum to reduce the effect of image noise. A higher “y” axis value indicates that the image is in better focus and is sharper or clearer compared to lower “y” axis values. In the illustrated example, an automatic focusing system or algorithm that seeks to maximize the Brenner score would select the false focal plane72, because its score is higher than the true focal plane70.

Consequently, an imaging microscope26may focus on the dust52in the false focal plane72rather than on the fiducial mark16at the true focal plane70. If the imaging station18scans this false focal plane72for cells instead of the true focal plane70, many images taken of the sample12will be out of focus and objects of interest will be missed by the imaging software.

Thus, it would be desirable to have methods and systems that can more effectively locate fiducial marks on a specimen slide in the presence of air bubbles or other debris under the cover slip and that can focus on located fiducial marks in the presence of dust and debris on top of the cover slip.

SUMMARY OF THE INVENTION

In one embodiment, a method of locating a corner of a fiducial mark within an image of a specimen slide is provided, the image having a plurality of pixels, the method including selecting a pixel of the plurality of image pixels, the selected pixel defining an area based on lines extending from the selected pixel, the selected pixel being selected based on a ratio of a number of empty pixels in the defined area and one or more dimensions of the defined area satisfying a threshold, the method further including determining a location of the corner of the fiducial mark using the selected pixel. By way of one non-limiting example, the selected pixel may define the largest area compared to other image pixels that satisfy the threshold. By way of another non-limiting example(s), the boundary lines may be straight, and may extend from the selected pixel to an edge of the image, and an area defined by each pixel is a square or a rectangle. By way of a further, non-limiting example, the ratio can be a ratio of (number of empty pixels in the area defined by the selected pixel) to (one or more dimensions of the area defined by the selected pixel).

In another embodiment, a method of locating a corner of a fiducial mark within an image of a specimen slide is provided, the image having a plurality of pixels, the method including identifying a plurality of pixels as candidate pixels, each candidate pixel being identified based on a number of empty pixels in a bounding area defined by lines extending from the candidate pixel relative to one or more dimensions of the defined area; selecting one candidate pixel, wherein lines extending from the selected pixel define the largest bounding area compared to lines extending from other candidate pixels; and determining a location of the corner of the fiducial mark based on the selected candidate pixel. By way of non-limiting example, the bounding area corresponding to the selected pixel may contain the largest number of dark pixels compared to bounding areas defined by other candidate pixels. Again, by way of further non-limiting examples, the lines may be straight, may extend from the selected candidate pixel to an edge of the image, and the bounding area may be defined by each candidate pixel is a box or a rectangle.

The each candidate pixel may be identified based on a ratio satisfying a threshold, the ratio comprising a ratio of a number of empty pixels in the bounding area defined by lines extending from the selected candidate pixel to one or more dimensions of the bounding area. For example, each candidate pixel may be selected based on a ratio of the number of empty pixels in the bounding area to one or more dimensions of the bounding area being below a threshold, and the ratio may be a ratio of the number of empty pixels in the bounding area to the perimeter of the bounding area, e.g., a ratio of the number of empty pixels in the bounding area to the semiperimeter of the bounding area.

The method may optionally be performed in the presence of an air bubble or debris overlapping the fiducial mark, wherein a pixel may be treated as an empty pixel if a gray value of the pixel is greater than 128. Also, the method may optionally be performed at multiple gray value thresholds, and may further include calculating a focus score based on a difference between a first bounding area and a second bounding area, e.g., wherein the difference is the Euclidean distance between corners of the first and second bounding areas.

The method may optionally be performed at multiple gray value thresholds, wherein a first bounding area is identified using a first empty pixel threshold to identify a first location of the corner of the fiducial mark, and a second bounding area is identified using a second empty pixel threshold to identify a second location of the corner of the fiducial mark. The method may optionally further include calculating a focus score based on a distance between the first and second bounding areas, and automatically focusing an image device based on the calculated focus score, e.g., wherein the distance is the Euclidean distance between the corners of the first and second bounding areas.

DETAILED DESCRIPTION OF ILLUSTRATED EMBODIMENTS

Embodiments advantageously locate and focus on fiducial marks in the presence of air bubbles, dust and debris. Embodiments achieve these advantages by fitting a shape, such as a square, a rectangle a box or another shape (generally “bounding box” or “bounding area” or “area”), to an image of the corner of a fiducial mark. Embodiments can be implemented using bounding areas of various shapes. According to one embodiment, a boundary area is defined by two straight lines. The lines can be at various angles. Accordingly, references to a boundary area or box or rectangle are examples of some of the boundary area shapes that can be utilized.

The boundaries of the bounding box maximize the area of the bounding box while constraining the number of non-mark or empty pixels within the bounding box. A pixel of one image can be defined as a “dark,” fiducial mark pixel or a “light,” empty pixel based on a gray value cutoff. Focus settings or adjustments can be determined by comparing the bounding areas found using different gray value cutoffs.

FIG. 9illustrates an image of a corner of a fiducial mark16that extends beyond the top left corner of an image. The top left corner of the image can be specified as a (0, 0) location, and the bottom right corner of the fiducial mark16can be specified as a (x, y) location. Pixels above and to the left of the (x, y) location can be considered to be part of the fiducial mark16. Persons skilled in the art will appreciate that other coordinate assignments can be utilized if different portions of the fiducial mark16are visible. Thus,FIG. 9illustrates one example in which a bottom right corner of the fiducial mark16is visible and the coordinate system is based on the bottom right corner of the fiducial mark16.

In the illustrated example, a horizontal boundary line94and a vertical boundary line95extend from a point or pixel P to define a bounding box96. This specification refers to a bounding box being defined by a point or pixel in the sense that lines94and95extending from the point or pixel define a bounding box96, as well as a bounding box96being defined by boundary lines94and95themselves. In the illustrated embodiment, the boundary lines94and95are straight and have “x” and “y” dimensions and a perimeter of 2*(x+y). In the illustrated example, the “x” and “y” dimensions are the same, but in other images, they may be different.

Due to imprecision in the process of depositing fiducial marks16on a slide, edges92of the fiducial mark16have irregularities on a microscopic scale. For example, as shown inFIG. 9, the edges92of a fiducial mark16may have non-linear or wave-like shapes. As a result of the irregular edge shape, the bounding box96may contain some empty pixels98; exclude some fiducial mark pixels97, or both. Dark pixels97may be pixels of the fiducial mark16, and light pixels98may be empty pixels. For example, light pixels98may be empty pixels that are beyond the edge92of the fiducial mark16or pixels that represent gaps in the paint of the fiducial mark16. For purposes of locating a fiducial mark16, a bounding box96containing no empty pixels97will be too small; a bounding box96containing every fiducial mark pixel97will be too big. Therefore, the bounding box96should be allowed to contain some empty pixels98, but not too many empty pixels98.

FIGS. 10A and 10Billustrate how two images taken of the same fiducial mark16at different slide locations may appear. Point P1inFIG. 10Aand Point P2inFIG. 10Bhave been chosen in the two images at the same location relative to the mark16. Points P1and P2define respective bounding rectangles96by respective boundary lines94and95extending from respective points P1and P2to the edges of the images.

As shown in the figures, the empty pixels98are indentations in the mark16extending from an edge92of the fiducial mark16to different depths into the fiducial mark16. Assuming that the depth of the indentation of empty pixels98is a random function with a certain mean and variance, the expected number of empty pixels98for the best fit bounding box96is equal to that mean depth times the length of the edge92that is visible within the image.

In the illustrated example, the length of the edge (i.e., the sum of the “x” and “y” dimensions) of the bounding box96inFIG. 10Ais about twice as long as the length of the edge (i.e., the sum of the “x” and “y” dimensions) of the bounding box96inFIG. 10B. The bounding box96inFIG. 10Acontains twice as many empty pixels98compared to the box inFIG. 10B. This illustrates that the number of empty pixels98within a given bounding box96is proportional to the length of the edge (i.e., the sum of the “x” and “y” dimensions) of the bounding box96.

FIGS. 11A-Dfurther illustrate this proportionality. The indentations of empty pixels98in the fiducial mark edge92may be larger in some portions of the edge92than in others. However, indentions or pixels98have a certain average depth. Empty pixels or areas98within the bounding box96can be rearranged by distributing the empty areas98along a perimeter of the box96until empty areas98are evenly distributed at this average depth.

For example, a triangle shaped empty section111can be moved to corresponding section112within the rectangular area extending along the boundary lines94and95, and the triangular section112is at a certain depth. This process can be repeated for other indentations of empty pixels98until the empty pixels98are distributed along an edge of the fiducial mark at the same depth. The result of this process is shownFIG. 11B. Empty spaces98in the other image shown inFIG. 11Ccan be reorganized in a similar manner, the result of which is shown inFIG. 11D. Thus,FIGS. 11A-Dfurther illustrate that the area of the empty regions98within the bounding box96equals the average depth of the empty area98multiplied by the length of the edge (sum of “x” and “y” dimensions) of the box96.

Embodiments of the invention advantageously utilize this proportional relationship of changes in the numbers of empty pixels98relative to the dimensions of a bounding box96defined by boundary lines94and95for a given pixel or point P to more effectively locate fiducial marks16in the presence of air bubbles54and other debris that overlaps the fiducial mark16. Embodiments of the invention achieve these advantages by locating the fiducial mark16by selecting a point or pixel P on the specimen slide14that: 1. maintains an acceptable number of empty pixels98within the bounding box96defined by pixel P, e.g., below a threshold number that varies with the dimensions of the bounding box96, and 2. maximizes the area or size of the bounding box96which, in turn, may also maximize the number of dark pixels97within the bounding box96.

More specifically, referring toFIGS. 12 and 13, according to one embodiment, a method120of locating a fiducial mark16includes identifying a group or subset of image pixels130as candidate pixels132in step1205. A candidate pixel132is a pixel that defines an area or bounding box96(based on boundary lines94and95extending from the pixel) containing an acceptable number of empty pixels98for the dimensions of the bounding box96. According to one embodiment, a candidate pixel132is a pixel that defines a bounding box96containing an acceptable number of empty pixels98as a proportion of or relative to the perimeter of the bounding box96.

A candidate pixel132may or may not be a pixel that is ultimately used to locate a fiducial mark16. Depending on the image, there may be one, a few or many candidate pixels132. For example, an average image of about two million pixels may contain about five hundred thousand candidate pixels132. Thus,FIG. 13is provided for purposes of illustration to generally show that a subset of image pixels130is identified as candidate pixels132. Additionally, persons skilled in the art will appreciate that whether a pixel is a candidate pixel132can vary depending on, for example, the brightness value or cutoff that is used to distinguish a fiducial mark or dark pixel97from an empty pixel98.

Having identified a set or group of candidate pixels132, in step122, one candidate pixel134is selected to locate the corner of the fiducial mark16. According to one embodiment, the selected candidate pixel134is the candidate pixel that defines largest bounding box96, e.g., the bounding box96with the largest area or the largest perimeter.

In one embodiment of the invention, steps121and122can be performed such that all candidate pixels132are first identified, and then one candidate pixel134of all of the identified candidate pixels132is selected. In an alternative embodiment, the step121and122can be combined by generating the candidate pixels one by one and storing only the best candidate pixel134as the currently selected candidate pixel134. The stored candidate pixel134may be replaced by a new candidate pixel if the new candidate pixel defines larger bounding box96.

Referring toFIG. 14, a method140according to one embodiment of the invention includes selecting a pixel of the image130in step141. In step142, dimensions of the area or boundary box96defined by boundary lines94and95extending from the selected pixel are determined. The dimension can be the perimeter of the bounding box or a portion of the perimeter. For example, referring again toFIG. 9, in the illustrated embodiment, one boundary line94is a horizontal line with a length “x” and the other boundary line95is a vertical boundary line with a length “y” so that the perimeter of the bounding box area is 2*(x+y). In step143, the number or area of empty pixels98contained within the defined bounding box96is determined. Step143may involve, for example, counting the number of empty pixels98within the bounding box96and/or calculating an area of empty pixels98.

In step144, a determination is made whether a threshold number of empty pixels98or empty area is satisfied. According to one embodiment of the invention, step144involves calculating a ratio and comparing the ratio to a threshold. In one embodiment, the ratio is (number of empty pixels)/(perimeter of area), e.g., (number of empty pixels)/(2(x+y)). Thus, step144involves determining whether the ratio value is greater than or less than a certain threshold value. This is equivalent to determining whether (number of empty pixels)/(x+y) is greater than a threshold value that is twice as high. In step145, if the threshold is satisfied, e.g., if the value of (number of empty pixels/(x+y) is less than a certain threshold value, then the pixel is selected or identified as a candidate pixel132. If the threshold is not satisfied, then in step146, the pixel is not selected as a candidate pixel132and is discarded.

In step147, a determination is made whether additional pixels of the image130should be processed. If so, then steps141-147can be repeated for each additional pixel. If not, and all of the image pixels (or all of the necessary image pixels) have been processed, then in step148, one candidate pixel134of the group or set of identified candidate pixels132is selected. The selected candidate pixel134is used to locate the corner of the fiducial mark16. According to one embodiment, the selected candidate pixel134is the candidate pixel that defines a bounding box96having the largest area.

Thus, embodiments of the invention may utilize a ratio to identify candidate pixels132that define a constraint on the size of the bounding box96defined boundary lines94and95so that the number of empty pixels98contained within the bounding box96should be no greater than a multiple of the perimeter (or other dimension) of the bounding box96. The point at the corner location that is selected should define the largest area of the bounding box subject to this “empty pixel” constraint. According to one embodiment, this can be done by selecting the (x, y) location that maximizes x*y (i.e., the size or area of the bounding rectangle96) while, at the same time, the number of empty pixels98is less than a certain value d*(x+y), where d is the expected mean indentation depth.

Thus, a number of empty pixels98in a first bounding box is counted or calculated, a number of empty pixels98in a second bounding box is counted or calculated, and so on, for each pixel of the image so that a ratio of a number of empty pixels relative to a size or dimension of the bounding box can be calculated to determine whether a pixel is a candidate pixel132. One manner of determining the number of empty pixels98is to manually count the number of empty pixels98within a bounding box96defined by boundary lines94and95extending up and to the left of given (x, y) point or pixel in the image. This can be done for each pixel independently, and will take an amount of time proportional to the square of the number of pixels. Alternatively, according to one embodiment of the invention, the number of empty pixels98within a box96defined by a certain point or pixel can be determined based on a previous count of empty pixels98within a different box96defined by a different point pixel; this makes the amount of time necessary to process a set of pixels proportional to the number of pixels instead of the number squared, resulting in more efficient analysis.

FIGS. 15-19illustrate one embodiment of the invention, in which the number of empty pixels98for purposes of calculating the ratio (number of empty pixels)/(x+y), used to identify candidate pixels132.FIGS. 15-19show an example image comprising a grid of pixels. Pixels corresponding to the fiducial mark16paint are shaded. A light pixel98may be surrounded by dark pixels97when, for example, that particular light pixel98is not painted. In the illustrated grid, an x−y coordinate system is applied to the pixels so that (0, 0) is at the top left corner of the image130.

Referring toFIG. 15, a first point P1at the lower right corner of a first dark pixel97is identified by (x1, y1). The bounding area96defined by horizontal and vertical boundary lines94(1) and95(1) extending upwardly and to the left from P1includes one pixel, which is a dark pixel97. There are no empty pixels98in the area96defined above and to the right of P1. Similarly, a second point P2is identified by (x2, y2). The bounding area96defined by horizontal and vertical boundary lines94(2) and95(2) extending upwardly and to the left from P2includes two pixels. One pixel is the dark pixel97that was previously discussed with reference to point P1. The other pixel is the “next” pixel that is introduced into the area96when the next point P2is selected. The next pixel is also a dark pixel97. Thus, there are no empty pixels98in the area96defined above and to the right of P2. Further, a third point P3is identified by (x3, y3). The bounding area96defined by horizontal and vertical boundary lines94(3) and95(3) defined by P3includes three pixels including the two pixels previously considered. The third pixel is the “next” pixel that is introduced into the area96when the next point P3is selected. The third or next pixel is also a dark pixel97. Thus, there are no empty pixels in the area96defined above and to the right of P3.

As shown inFIGS. 16-18, grid cells can be labeled with a number, which represents the number of empty pixels above and to the left of a particular point. While the empty pixel count could be calculated independently for each pixel, according to one embodiment, a method of counting the number of empty pixels is done using previous counts of empty pixels, which can be significantly faster than counting independently, particularly considering that an image can have, for example, two million pixels.

For example, referring toFIG. 16, a “0” value can be assigned to the first pixel to represent that there are no empty pixels98above and to the left of P1. Similarly, a “0” value can be assigned to the second pixel to represent that there are no empty pixels98above and to the right of P2, and a “0” can be assigned to the third pixel to represent that there are no empty pixels98above and to the right of P3. This process can continue for additional pixels in the row.

FIG. 16illustrates a point P6that defines an area96defined by boundary lines94(6) and95(6) extending from the point P6. The area96contains five dark pixels97(each of which is assigned a “0” value) and an additional or next pixel as a result of selection of the next point P6. This pixel, in contrast to previously discussed pixels, is an empty pixel98. Thus, there is one empty pixel98above and to the left of point P6, and a value of “1” can be assigned to this pixel. Similarly for P7, the area defined by boundary lines extending from P7encloses the six previously analyzed dark pixels (five of which were assigned a “0” value; one of which was assigned a “1” value) and a new or next pixel. In this case, the next pixel is a dark pixel97. Thus, there are no new empty pixels98in the area96defined by boundary lines extending from point P7. As a result, a value of “1” can also be assigned to this seventh pixel since the empty pixel count remains the same. This process continues for each pixel of the image.

FIG. 17further illustrates how numbers can be assigned to represent empty pixel count values.FIG. 17only shows the pixel count values above and to the right of a point P for purposes of illustration and explanation. A shown inFIG. 17, boundary lines95and95extending to the left and upwardly from point P define an area96that includes 24 pixels. Three of these 24 pixels are empty pixels98and, therefore, the next pixel introduced by point P is assigned a value of “3” to indicate there are three empty pixels98in the area96defined by boundary lines94and95extending from point P.

Similarly, referring toFIG. 18, consider the pixel indicated as “Next point” inFIG. 18. Every pixel above or to the left of “Next Point” is contained in the region defined either by the pixel immediately above “Next Point” or the pixel immediately to the left of “Next Point”. If the empty counts for these two neighbor pixels are added together, all the pixels in the region defined by the pixel diagonally up and to the left of “Next Point” will be included twice in the sum. Therefore, the number of empty pixels above and to the left of “Next Point”, not counting “Next Point”, is equal to the count for the pixel above “Next Point”, plus the count for the pixel to the left, minus the count for the diagonal pixel. If “Next Point” is empty, an additional value of one should be added to this sum.FIG. 19further illustrates the “Next Point” analysis illustrated inFIG. 18.

In more mathematical terms, let E(x, y) be the number of empty pixels above and to the left of the pixel at image coordinates (x, y); that is, the number of empty pixels (x′, y′) for which x′≦x and y′≦y. Let E(x, y) be zero if (x, y) is not a point within the image. Then, for each (x, y) in the image, E(x, y) is equal to E(x−1, y)+E(x, y−1)−E(x−1, y−1) plus one if the pixel at (x, y) is itself empty.

According to one embodiment of the invention, a method locating a fiducial mark16by selecting a point or pixel that maximizes the area of dark or fiducial mark97while maintaining the number of empty or light pixels98(determined, e.g., by the method described above) below a certain number can be expressed as:

Thus, if E values in the image are calculated row by row (y=0 to y=image height), then by moving from left to right (x=0 to x=image width) within each row, each value representing the number of empty pixels98can be based on previously computed values, thereby reducing the computational complexity from O(n2) in the number of pixels to O(n).

This is expressed in other terms by the following pseudo code:

With the above-described methods, various embodiments of the invention can be used to quickly determine the number of empty pixels98contained within an area or bounding box96, thereby allowing the ratio of (number of empty pixels)/(x+y) to be calculated to determine whether a particular pixel is a candidate pixel132. Persons skilled in the art will appreciate that althoughFIGS. 15-19illustrate one method of determining the number of empty pixels98within a given bounding box or area96, other processing methods and techniques can also be used for this purpose. Accordingly, the example of determining empty pixel counts with a type of dynamic programming is provided for purposes of illustration and explanation, and other suitable methods can also be used to count the empty number of pixels within a given area or bounding box96.

Having located the fiducial mark16, embodiments also improve the manner in which the imaging station18focuses on the located fiducial mark16may be improved. In a well focused image of a fiducial mark16, the edge92of the mark16is an abrupt transition from dark to light. If the image is poorly focused, however, the transition is more of a blurred gradual gradient. The width of this blurred gradient region depends on the distance from the ideal focal plane and can, therefore, be used as a focus score for automatic focusing processes.

According to one embodiment, the width of the blurred region can be determined by using embodiments for locating a fiducial mark (e.g., the method shown inFIG. 14) and adjusting the intensity threshold between the “mark” and “empty” pixels. More particularly, according to one embodiment, focus improvements are achieved by performing, e.g., the method140shown inFIG. 14, using two different brightness or threshold levels that denote whether a pixel is an empty pixel98or a fiducial mark pixel97. For example, the method140can be performed based on a brightness or threshold value of 192 so that pixels having gray values less than or equal to 192 are considered fiducial mark pixels97, and pixels having gray values above 192 are empty pixels98, and also at another brightness or threshold level, e.g., 64, so that pixels having gray values less than or equal to 64 are considered fiducial mark pixels97, and pixels having gray values above 64 are empty pixels98. Persons skilled in the art will appreciate that other brightness threshold values can be utilized.

Use of different brightness or threshold values results in an automatic focusing system or process selecting different candidate pixels which, in turn results in different bounding boxes that are separated by a distance “d”. This distance can be used to indicate the focus quality and allow the image with the best focus to be selected. The presence of dust on top of the cover slip does not affect the measurement of blur, even though dust or other debris may be very sharply focused.

Thus, referring toFIG. 20, one embodiment of a method for focusing on a fiducial mark includes selecting a candidate pixel from a group or set of candidate pixels132having maximum fiducial mark area during processing at a first empty pixel brightness or threshold level in step201. In step202, a boundary box or area96defined by the selected candidate pixel is determined based on the first threshold level. In step203, a candidate pixel is selected from a group or set of candidate pixels132having maximum fiducial mark area during processing at a second empty pixel brightness or threshold level. In step204, a boundary box or area defined by the selected candidate pixel is determined based on the second empty pixel threshold level. Then, in step205, the degree to which a fiducial mark16is out of focus is determined based on the distance between the two boundary boxes. In step206, the image with the best focus can be selected. If necessary, in step207, the imaging microscope26can be adjusted to further improve the focus on the fiducial mark16.

FIGS. 21-23illustrate one example of how embodiments of the invention can be implemented to improve focus quality. In the illustrated embodiment, empty pixel threshold gray values of 64 and 192 were utilized, but persons skilled in the art will appreciate that other values can also be utilized. Referring toFIG. 21, an inner bounding box210is defined by boundary lines extending from a candidate pixel selected using a higher empty pixel threshold so that fewer pixels are selected as “dark” pixels97. An outer bounding212is defined by boundary lines extending from a different candidate pixel selected using a lower empty threshold so that more pixels are selected as “dark” pixels97. In the illustrated example, the inner and outer boxes210and212are separated by a small distance “d”. Thus, in this example, the different empty pixel threshold values of 64 and 192 do not significantly alter the resulting location of a fiducial mark16. However, as the fiducial mark16goes farther out of focus, the distance “d” between the two bounding boxes increases.

Referring toFIG. 22, the fiducial mark16is more out of focus compared toFIG. 21. The inner boundary box220corresponds to a fiducial mark16that is located when a higher empty pixel threshold is used so that fewer pixels are selected as “dark” pixels97. The outer boundary box222corresponds to a fiducial mark16that is located when a lower empty pixel threshold is used so that more pixels are selected as “dark” pixels97. ComparingFIGS. 21 and 22, the distance “d” between the boxes220and222is larger than the distance “d” between boxes210and212as a result of reduced quality of focus on the fiducial mark16.

Similarly, referring toFIG. 23, the fiducial mark16is even more out of focus, and the dust52below the fiducial mark16is more in focus compared toFIGS. 21 and 22. The inner boundary230corresponds to a fiducial mark16that is located when a higher empty pixel threshold is used so that fewer pixels are selected as “dark” pixels97. The outer boundary box232corresponds to a fiducial mark16that is located when a lower empty pixel threshold is used so that more pixels are selected as “dark” pixels97. ComparingFIG. 23toFIGS. 21 and 22, the distance “d” between the boxes230and232becomes increasingly larger as the fiducial mark16is increasingly out of focus. However, the dust52near the bottom of the fiducial mark16does not affect the focus measurement even with the larger in-focus dust particles shown inFIG. 23since embodiments advantageously ignore all objects except the fiducial mark16corner.

These advantages are further illustrated inFIG. 24, which is a chart illustrating how embodiments improve the process of focusing on a fiducial mark. InFIG. 24, the dotted line80contains a false peak (FIG. 8) that is produced as a result of focusing on dust52rather than a fiducial mark16when using known systems. Embodiments of the invention advantageously eliminate the false peak80as demonstrated by the solid line240, which represents the improved focus score achieved using one embodiment. The solid line240has a peak at 0 microns, i.e., at the correct focal plane70, without a false peak72, as inFIG. 7, which illustrates focusing known systems.

In another embodiment of the invention, the scale of blurring of the fiducial mark16can be calculated by comparing mark16locations or boundaries that are measured at different light/dark thresholds. For example, referring to the chart shown inFIG. 24, the solid line240is the Euclidean distance between the locations measured at thresholds of 64 and 192, inverted and scaled to align with the Brenner function. Using this distance for the fiducial mark16score, the imager microscope26and the review microscope38would focus on the true fiducial mark16focus plane rather than the higher, false focus plane72caused by dust and debris52.

Although particular embodiments have been shown and described, it should be understood that the above discussion is not intended to limit the scope of these embodiments. Various changes and modifications may be made without departing from the scope of embodiments. For example, candidate pixels could be chosen based on some other function of the empty pixel count. The best candidate pixel could be chosen by maximizing the perimeter or the number of dark pixels contained instead of by maximizing area. Additionally, although the specification has described embodiments with reference to fiducial marks, persons skilled in the art will appreciate that embodiments can also be used to locate and focus on other specimen slide marks. Further, although embodiments have been described with reference to rectangle and box shapes, persons skilled in the art will appreciate that embodiments can be implemented with other shapes if desired.

As a further example, embodiments can be applied where there is a dark object in a known location on a slide. The degree of blur of that object could be found by measuring its size (when thresholded at two different levels as discussed above) to provide a focus score that is not influenced by dust on the slide. Thus, embodiments are intended to cover alternatives, modifications, and equivalents that may fall within the scope of the claims.