In this paper, we present a vision system for a depalletizing robot which recognizes carton objects. The algorithm consists of the extraction of object candidates and a labeling process to determine whether or not they actually exist. We consider this labeling a combinatorial optimization of labels, we propose a new labeling method applying Genetic Algorithm (GA). GA is an effective optimization method, but it has been inapplicable to real industrial systems because of its processing time and difficulty of finding the global optimum solution. We have solved these problems by using the following guidelines for designing GA: (1) encoding high-level information to chromosomes, such as the existence of object candidates; (2) proposing effective coding method and genetic operations based on the building block hypothesis; and (3) preparing a support procedure in the vision system for compensating for the mis-recognition caused by the pseudo optimum solution in labeling. Here, the hypothesis says that a better solution can be generated by combining parts of good solutions. In our problem, it is expected that a global desirable image interpretation can be obtained by combining subimages interpreted consistently. Through real image experiments, we have proven that the reliability of the vision system we have proposed is more than 98% and the recognition speed is 5 seconds/image, which is practical enough for the real-time robot task.