In Segmented Image Coding (SIC), an image is segmented into several homogeneous regions. In each of the regions, the image intensity function is represented by a weighted sum of orthogonal base functions. In existing SIC-methods, the bases are generated by Gram-Schmidt Orthogonalization of a nonorthogonal polynomial (or sometimes sinusoidal) starting base. Unfortunately, the orthogonal base for a segment depends on the segment's shape and must be recomputed for every region. Therefore, the computational demands of SIC are much higher than those of block coding. This paper shows that when the starting base is orthogonalized in a different order, the resulting orthogonal base functions are the product of two component functions. This property is called weak separability. In the weakly separable case, only the component functions appear in computations, which implies that it is not necessary to explicitly evaluate the orthogonal bases. The major advantage of the new approach is that the component functions can be generated quickly using three-term recurrences and that little memory is needed for storing them. Consequently the (components of) the new bases can be computed much faster than the classical bases (typically 10-25 times) and using less memory. This is true, even though both methods produce images of the same subjective quality. The paper also shows that a wide variety of other orthogonal bases is obtained by considering more general starting bases. The spatial properties of the corresponding base functions are described qualitatively; they are determined by two parameter functions and can be modified by appropriately selecting these parameter functions.