1. A scene change detection method that detects video scene changes, comprising: a region extraction step of extracting subregions for analysis from two frames of video data; and an occurrence of a scene change detection step of detecting an occurrence of a scene change between the two frames, based on a difference in video characteristic values in the entire subregions of the two frames extracted by the region extraction step; wherein when a scene change is detected to have occurred by the scene change detection step, a final judgment is made immediately that a scene change is present between said two frames; and wherein when no scene change is detected to occur by the scene change detection step, the region extraction step expands the regions for analysis by adding new regions extracted from regions that were not previously included in the regions for analysis, and the scene change detection step performs the detection of the scene change again, based on video differences between the entire expanded regions for analysis, wherein the entire expanded regions include the newly added regions and the regions which were previously used for the scene change, wherein the video characteristic values are histograms and the occurrence of a scene change is detected after obtaining cumulative histograms by adding histograms of the newly added regions to the histograms accumulated so far, and wherein when a judgment is made from the values of the cumulative histograms up to previous trial that whatever values the histograms of the newly added regions might take, they would not produce a scene change, a histogram accumulation process is carried out without carrying out the scene change detection step.