RESNA Annual Conference - 2010

BACKGROUND

A typical modern supermarket stocks an average of 45,000 products and has a median store size of 4,529 square meters [3]. Many visually impaired (VI) people do not shop independently; they rely on friends, relatives, volunteers, and store employees. When these individuals are unavailable, VI shoppers reschedule or postpone shopping trips. When they can reach the store independently, they experience frequent delays waiting for store employees to assist them. Some staffers are unfamiliar with the store layout, others become irritated with long searches, and still others do not have adequate English skills to read the products' ingredients [4]. These difficulties cause VI shoppers to abandon searching for desirable products or settle for distant substitutes. PeaPod (http://www.peapod.com) and similar home delivery services provide grocery shopping alternatives. However, such services are not universally available and, when available, require shoppers to schedule and wait for deliveries, thereby reducing personal independence and making spontaneous shopping impossible

To help VI individuals overcome these challenges, in 2004 we began to develop RoboCart [5], a robotic supermarket shopping assistant for VI shoppers. A long-term collaborative agreement was negotiated with Lee's Market Place to grant us access to its store in Logan, UT, for experimental purposes. After several single subject studies in 2005 – 2006, a successful longitudinal formal study was executed in 2007 with ten VI participants recruited through the Utah NFB Chapter [6]. The supermarket experiments lasted four months, with each participant having to execute fifteen runs on two different days. In 2006, in parallel with our R&D activities with RoboCart, we started our research on ShopTalk, a wearable system for independent blind supermarket shopping [7]. In 2007 - 2008, after two successful single subject studies at Lee’s Market Place and another successful single subject study at Sweet Peas, an independent natural foods store in Logan, UT, ten VI participants were recruited for a longitudinal formal study in Lee’s Market Place. The experiment, performed during regular business hours, had each participant shop for the same set of three randomly chosen products five times. The product retrieval rate was 100% [8]. A key finding of ShopTalk is that independent VI travelers can execute verbal template-based route and product search instructions in supermarkets with 100% accuracy. In 2009, we ported ShopTalk onto a mobile platform [9], thereby reducing the system’s hardware to a Nokia E70 mobile phone and a small BaracodePencil2 wireless barcode scanner. Our next objective is to get rid of the barcode scanner altogether by making barcode scanning dependent only on the phone camera. In this paper, we describe a vision-based barcode scanning method for mobile phones and present its performance evaluation on a database of 187 images with barcodes.

METHOD

Figure 1:  ShopMobile system consisting of a camera-equipped smart phone in a hard case with two plastic stabilizers.

The new system, called ShopMobile, will consist of a camera-equipped smart phone in a hard case with two plastic stabilizers (≈ 10cm long) that will insert into a small jacket super-glued to the back of the case for aligning the camera with shelves and products (Fig. 1). The phone will have a screen reader and a screen magnifier (e.g., Nuance Talks and Zooms (www.nuance.com/talks/ )), and will have one wireless over-the-ear head piece. In a supermarket aisle, the user will place her phone into the hard case, if it is not already there, insert the stabilizers, and place them on the lip of a shelf to align the camera with it. Using our barcode scanning method, the system will find shelf barcodes in images. If part of a barcode is detected, the system will request the user to slide the phone to the left (right) along the shelf. When the target barcode is recognized, the user will reach above the barcode and take a product from the shelf

Figure 2:  A barcode with two lines drawn on it (left); the bit-string representations of the the two lines (right).

A fundamental problem is how the VI shopper can find shelf barcodes in the first place. To solve this problem, we have distinguished barcode recognition (the camera is aligned, the barcode is completely in the image, a shot is taken, and a vision-based barcode reader decodes the barcode) and barcode localization (the camera must first be aligned with the barcode so that it can be decoded by the reader). Vision-based barcode recognition is a solved problem in that there are open-source barcode reading libraries that read the barcodes provided that the barcode is completely in the image [10]. Barcode localization, on the other hand, is a performance gap, because VI shoppers must align the camera with a barcode before the barcode can be recognized. Our barcode localization method is based on the observation that a barcode can be viewed as a homogeneous region consisting of alternate black and white lines condensed in a small image region (See Fig. 2, left). Along the x-axis, the barcode can be characterized as a sequence of alternating black and white lines. We call this property alternating frequency. Along the y-axis, the barcode can be characterized by the vertical continuity of parallel black and white lines. We call this property vertical continuity. Consider two lines A and B that are both one pixel wide (Fig. 2, left). These lines can be encoded as bit strings where black pixels map to 0’s and white pixels to 1’s (Fig. 2, right). Alternating frequency can be measured by the number of 0-1 and 1-0 transitions in a bit string. Vertical continuity can be estimated as the longest common subsequence of two bit strings, such as the ones in Fig. 2 (right).

Figure 3:  An overview of the barcode localization algorithm detailed in the Method section.

Fig. 3 gives an overview of our barcode localization algorithm. The image is converted to grayscale and passed through a line detection filter oriented along the line orthogonal to the shelf. The line detection filter lets only vertical lines through. Since the barcode is comprised of vertical lines, it passes through this filter along with vertical lines belonging to other elements, e.g., text and graphics. The vertical lines that comprise the barcode must be distinguished from the other vertical lines in order to localize the barcode. The next step is to look for areas with high vertical continuity and high alternating frequency. A fast rasterized pattern search of the entire image is performed with long lines and large spacing between the lines (See Fig. 3d) to look for barcode regions. These candidate regions (shown in green in Fig. 3d) undergo a more thorough search by employing smaller lines and less spacing between them (See Fig. 3e) to find lines exhibiting high alternating frequency and high vertical continuity. A histogram analysis is performed on these lines to localize the barcode (See Fig. 3f). Each selected region is processed with ZXing (http://code.google.com/p/zxing ), an open source barcode recognizer.

RESULTS

A HTC Touch-Pro smartphone was used to capture 187 images of barcodes of actual products. The ZXing source code was compiled with the NetBeans 6.5 Java SE IDE. Our barcode localization algorithm was implemented and compiled with the same IDE. Each of the 187 images was first processed with ZXing alone and then with our barcode localization algorithm followed by ZXing. Barcodes in 91 images were recognized by ZXing alone; barcodes in 133 images were recognized by ZXing applied only to the regions selected by our barcode localization algorithm, which represents a 47.25% increase in the number of barcodes being successfully scanned. Our current implementation (barcode localization + ZXing) takes approximately 0.35 seconds per image of size 640 by 480 pixels on a Dell Optiplex 960 Core2Duo machine running at 3 GHz.

CONCLUSION

Since the mobile phone has become the de facto mobile computational hub with ever increasing computational power, the presented barcode localization algorithm will enable us to get rid of the barcode scanner altogether and make barcode scanning dependent only on the phone camera.