Segmented image coding (SIC) produces images of better subjective quality than techniques such as the Joint Photographic Experts Group standard at very low bit rates. It segments images into regions of similar texture and codes their contour and texture separately, Most SIC techniques represent the texture as a linear combination of orthonormal base functions, which differ from region to region. In earlier SIC methods, the orthonormal bases were generated by the Gram-Schmidt (GS) procedure, whose excessive computational requirements are unacceptable in many applications, This paper introduces a new class of weakly separable (WS) orthonormal bases, The WS base functions are the product of two components, which can be generated very quickly and using a modest amount of memory. The class of WS base functions includes polynomials, cosines, and warped polynomials. The paper describes the spatial properties of these base functions. Experimental data show that for typical coding parameters, WS SIC is 8 to 40 times faster than traditional SIC, at the expense of a 3% to 6’% larger root-mean-square error. However, the subject quality of the compressed images is only slightly smaller for the WS method. Considering its computational advantages, WS SIC is therefore a promising technique for fast, low bit rate coding.