This study presents a method for detecting city-scale changes of a city from its street images and a 2D map. Using SfM to reconstruct point cloud of the structures of the city, the method estimates the existence of each building by matching the point cloud with the 3D building structures recovered from the map. There are multiple difficulties, such as inaccuracy of the recovered building structures, large differences in observation and thus in point cloud size of individual buildings, and mutual dependency of building existences due to potential occlusions. To solve these, we develop a model of how point cloud is generated in the sequential processes of SfM, an observation model of a building wall, and a greedy iterative approach to cope with the mutual dependency. We experimentally apply the method to the cities damaged by the tsunami that struck Japan in 2011. The results show the effectiveness of the method.